البرمجة الخطية الكسرية

📅 آخر تحديث: ٢٧ يوليو ٢٠٢٦
✍️ نُشر في: ٢٧ يوليو ٢٠٢٦
📷 يحتوي على 23 صور
الموسوعة الحرة

في مجال التحسين الرياضي ، تُعدّ البرمجة الخطية الكسرية ( LFP ) تعميمًا للبرمجة الخطية (LP). فبينما تكون دالة الهدف في البرنامج الخطي دالة خطية ، فإن دالة الهدف في البرنامج الخطي الكسري هي نسبة بين دالتين خطيتين. ويمكن اعتبار البرنامج الخطي حالة خاصة من البرنامج الخطي الكسري حيث يكون المقام هو الدالة الثابتة 1.

بشكل رسمي، يُعرَّف البرنامج الخطي الكسري بأنه مشكلة تعظيم (أو تصغير) نسبة الدوال الخطية على متعدد السطوح ،

أقصىجتيx+αدتيx+βرهناً بـأx≤ب،{\displaystyle {\begin{aligned}{\text{maximize}}\quad &{\frac {\mathbf {c} ^{T}\mathbf {x} +\alpha }{\mathbf {d} ^{T}\mathbf {x} +\beta }}\\{\text{subject to}}\quad &A\mathbf {x} \leq \mathbf {b} ,\end{aligned}}}

أينx∈Rن{\displaystyle \mathbf {x} \in \mathbb {R} ^{n}}يمثل متجه المتغيرات المطلوب تحديدها،ج،د∈Rن{\displaystyle \mathbf {c} ,\mathbf {d} \in \mathbb {R} ^{n}}وب∈Rم{\displaystyle \mathbf {b} \in \mathbb {R} ^{m}}هي متجهات من المعاملات (المعروفة)،أ∈Rم×ن{\displaystyle A\in \mathbb {R} ^{m\times n}}هي مصفوفة (معروفة) من المعاملات وα،β∈R{\displaystyle \alpha ,\beta \in \mathbb {R} }هي ثوابت. يجب أن تحد القيود المنطقة الممكنة إلى{x|دتيx+β>0}{\displaystyle \{\mathbf {x} |\mathbf {d} ^{T}\mathbf {x} +\beta >0\}}أي المنطقة التي يكون فيها المقام موجبًا. [ 1 ] [ 2 ] أو بدلاً من ذلك، يجب أن يكون مقام دالة الهدف سالبًا تمامًا في كامل المنطقة الممكنة.

التحفيز عن طريق المقارنة بالبرمجة الخطية

يُمثل كل من البرمجة الخطية والبرمجة الخطية الكسرية مسائل التحسين باستخدام المعادلات الخطية والمتباينات الخطية ، والتي تُحدد لكل حالة من حالات المسألة مجموعة الحلول الممكنة . تتميز البرامج الخطية الكسرية بمجموعة أوسع من دوال الهدف. ببساطة، تحسب البرمجة الخطية سياسة تُحقق أفضل النتائج، مثل أقصى ربح أو أقل تكلفة. في المقابل، تُستخدم البرمجة الخطية الكسرية لتحقيق أعلى نسبة بين الناتج والتكلفة، حيث تُمثل هذه النسبة أعلى كفاءة. على سبيل المثال، في سياق البرمجة الخطية، نُعظم دالة الهدف الربح  =  الدخل - التكلفة   ، وقد نحصل على أقصى ربح قدره 100 دولار (أي  1100 دولار  دخل -  1000 دولار تكلفة). وبالتالي، في البرمجة الخطية ، لدينا كفاءة قدرها 100 دولار / 1000 دولار = 0.1. باستخدام البرمجة الخطية الكسرية، قد نحصل على كفاءة قدرها 10 دولارات / 50 دولارًا = 0.2 مع ربح قدره 10 دولارات فقط، ولكن باستثمار لا يتجاوز 50 دولارًا.      

التحويل إلى برنامج خطي

يمكن تحويل أي برنامج خطي كسري إلى برنامج خطي، بافتراض أن المنطقة الممكنة غير فارغة ومحدودة، باستخدام تحويل تشارنز-كوبر . [ 1 ] الفكرة الرئيسية هي إدخال متغير جديد غير سالب.ت{\displaystyle t}إلى البرنامج الذي سيُستخدم لإعادة ضبط الثوابت الداخلة في البرنامج (α،β،ب{\displaystyle \alpha ,\beta ,\mathbf {b} }وهذا يسمح لنا باشتراط أن يكون مقام دالة الهدف (دتيx+β{\displaystyle \mathbf {d} ^{T}\mathbf {x} +\beta }) يساوي 1. (لفهم التحويل، من المفيد النظر في الحالة الخاصة الأبسط معα=β=0{\displaystyle \alpha =\beta =0}.)

بشكل رسمي، يستخدم البرنامج الخطي الذي تم الحصول عليه عبر تحويل تشارنز-كوبر المتغيرات المحولةy∈Rن{\displaystyle \mathbf {y} \in \mathbb {R} ^{n}}وت≥0{\displaystyle t\geq 0}:

أقصىجتيy+αترهناً بـأy≤بتدتيy+βت=1ت≥0.// t=1\\&t\geq 0.\end{محاذاة}}}

حلx{\displaystyle \mathbf {x} }يمكن ترجمة البرنامج الخطي الكسري الأصلي إلى حل للبرنامج الخطي المحوّل عبر المعادلات.

y=1دتيx+β⋅xوت=1دتيx+β.{\displaystyle \mathbf {y} ={\frac {1}{\mathbf {d} ^{T}\mathbf {x} +\beta }}\cdot \mathbf {x} \quad {\text{and}}\quad t={\frac {1}{\mathbf {d} ^{T}\mathbf {x} +\beta }}.}

وعلى النقيض من ذلك، فإن الحل لـy{\displaystyle \mathbf {y} }وت{\displaystyle t}يمكن ترجمة البرنامج الخطي المحوّل إلى حل للبرنامج الخطي الكسري الأصلي عبر

x=1تy.{\displaystyle \mathbf {x} ={\frac {1}{t}}\mathbf {y} .}

الازدواجية

لنفترض أن المتغيرات الثنائية المرتبطة بالقيودأy-بت≤0{\displaystyle A\mathbf {y} -\mathbf {b} t\leq \mathbf {0} }ودتيy+βت-1=0{\displaystyle \mathbf {d} ^{T}\mathbf {y} +\beta t-1=0}يُشار إليه بـu{\displaystyle \mathbf {u} }وλ{\displaystyle \lambda }على التوالي. ثم يكون ثنائي LFP أعلاه هو [ 3 ] [ 4 ]

تقليلλرهناً بـأتيu+λد=ج-بتيu+λβ≥αu∈R+م،λ∈R،{\displaystyle {\begin{aligned}{\text{minimize}}\quad &\lambda \\{\text{subject to}}\quad &A^{T}\mathbf {u} +\lambda \mathbf {d} =\mathbf {c} \\&-\mathbf {b} ^{T}\mathbf {u} +\lambda \beta \geq \alpha \\&\mathbf {u} \in \mathbb {R} _{+}^{m},\lambda \in \mathbb {R} ,\end{aligned}}}

وهو برنامج خطي ويتطابق مع البرنامج الخطي المزدوج المكافئ الناتج عن تحويل تشارنز-كوبر.

الخصائص والخوارزميات

تكون دالة الهدف في المسألة الخطية الكسرية شبه مقعرة وشبه محدبة (وبالتالي شبه خطية) مع خاصية رتيبة ، وهي خاصية التحدب الزائف ، التي تُعد أقوى من خاصية التحدب الزائف . تكون دالة الهدف في المسألة الخطية الكسرية شبه محدبة وشبه مقعرة، وبالتالي شبه خطية . وبما أنه يمكن تحويل المسألة الخطية الكسرية إلى مسألة خطية، فإنه يمكن حلها باستخدام أي طريقة من طرق حل المسائل الخطية، مثل خوارزمية سيمبلكس ( لجورج ب. دانتزيج )، [ 5 ] [ 6 ] [ 7 ] [ 8 ] أو خوارزمية التقاطع ، [ 9 ] أو طرق النقطة الداخلية .

ملحوظات

  1. 1 2 تشارنز، أ.؛ كوبر، و.و. (1962). "البرمجة باستخدام الدوال الكسرية الخطية". مجلة البحوث اللوجستية البحرية الفصلية . 9 ( 3-4 ): 181-186 . doi : 10.1002/nav.3800090303 . MR 0152370 . 
  2. ↑ بويد، ستيفن ب.؛ فاندنبيرغ، ليفين (2004). التحسين المحدب (ملف PDF) . مطبعة جامعة كامبريدج. ص 151. ISBN  978-0-521-83378-3تم الاطلاع عليه بتاريخ 15 أكتوبر 2011 .
  3. ^ شيبل ، سيغفريد (1974). “البرامج المكافئة والمزدوجة الخالية من المعلمات”. Zeitschrift لبحوث العمليات . 18 (5): 187– 196. دوى : 10.1007 / BF02026600 . السيد 0351464 . S2CID 28885670 .  
  4. ↑ شايبل، سيغفريد (1976). "البرمجة الكسرية 1: الازدواجية". مجلة علوم الإدارة . 22 (8): 858-867 . doi : 10.1287/mnsc.22.8.858 . JSTOR 2630017. MR 0421679 .   
  5. ↑ الفصل الخامس: كرافن، ب. د. (1988). البرمجة الكسرية . سلسلة سيجما في الرياضيات التطبيقية. المجلد 4. برلين: دار نشر هيلدرمان. ص 145. ISBN   978-3-88538-404-5MR 0949209 .​ 
  6. ↑ كروك، سيرج؛ وولكوفيتش، هنري (1999). "البرمجة شبه الخطية". مجلة SIAM . 41 (4): 795-805 . Bibcode : 1999SIAMR..41..795K . CiteSeerX 10.1.1.53.7355 . doi : 10.1137/S0036144598335259 . JSTOR 2653207. MR 1723002 .   
  7. ↑ ماثيس، فرانك هـ.؛ ماثيس، لينورا جين (1995). " خوارزمية برمجة غير خطية لإدارة المستشفيات". مجلة SIAM Review . 37 (2): 230-234 . doi : 10.1137/1037046 . JSTOR 2132826. MR 1343214. S2CID 120626738 .   
  8. ↑ مورتي (1983 ، الفصل 3.20 (الصفحات 160-164) والصفحات 168 و 179)    
  9. ^ إليس، تيبور. سزيرماي، أكوس؛ ترلاكي، تاماس (1999). “طريقة التقاطع المحدود للبرمجة الزائدية”. المجلة الأوروبية للبحوث التشغيلية . 114 (1): 198-214 . سيتيسيركس 10.1.1.36.7090 . دوى : 10.1016/S0377-2217(98)00049-6 . زبل 0953.90055 . طبعة بوستسكريبت .  

مصادر

  • مورتي، كاتا  ج. (1983). "3.10 البرمجة الكسرية (ص 160-164)". البرمجة الخطية . نيويورك: جون وايلي وأولاده، ص  482+19. ISBN 978-0-471-09725-9MR 0720547 .​ 

للمزيد من القراءة

  • باجالينوف، إي بي (2003). البرمجة الخطية الكسرية: النظرية والأساليب والتطبيقات والبرمجيات . بوسطن: دار نشر كلوير الأكاديمية.
  • باروس، آنا إيزابيل (1998). تقنيات البرمجة المنفصلة والكسرية لنماذج الموقع . التحسين التوافقي. المجلد  3. دوردريخت: دار كلوير للنشر الأكاديمي. الصفحات:  178+18. ISBN 978-0-7923-5002-6. MR 1626973 . 
  • مارتوس، بيلا (1975). البرمجة غير الخطية: النظرية والأساليب . أمستردام-أكسفورد: دار نشر نورث هولاند، ص  279. ISBN 978-0-7204-2817-9MR 0496692 .​ 
  • شايبل، س. (1995). "البرمجة الكسرية". في راينر هورست وبانوس م. باردالوس (محرران). دليل التحسين العالمي . التحسين غير المحدب وتطبيقاته. المجلد  2. دوردريخت: كلوير أكاديميك بابليشرز. الصفحات 495-608 . ISBN  978-0-7923-3120-9MR 1377091 .​ 
  • ستانكو-ميناسيان، آي إم (1997). البرمجة الكسرية: النظرية والأساليب والتطبيقات . الرياضيات وتطبيقاتها. المجلد  409. ترجمة فيكتور جيورجيوتيو من النسخة الرومانية لعام 1992. دوردريخت: مجموعة كلوير للنشر الأكاديمي. الصفحات:  418 صفحة + 8 صفحات تمهيدية. ISBN 978-0-7923-4580-0MR 1472981 .​