الانتقال إلى المحتوى
العودة إلى نتائج البحث

البرمجة الخطية المتينة — التحسين في ظل عدم اليقين

قدّمه
Ben-Tal, A. and Nemirovski, A.; further developed by Bertsimas, D. and Sim, M.
السنة
1999–2004
النوع
Uncertainty-robust linear optimization
العائلة
Simulation / optimization

هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية

حجم الخط

ماذا تفعل؟

تمثل البرمجة الخطية المتينة (RLP) امتدادًا للبرمجة الخطية الكلاسيكية للتعامل مع عدم اليقين في بيانات المشكلة — معاملات التكلفة، أو معاملات القيود، أو الأطراف اليمنى — عن طريق مطالبة الحلول بالبقاء مجدية وشبه مثلى عبر جميع تجليات المعلمات غير المؤكدة ضمن مجموعة عدم يقين محددة. وهي تستبدل الافتراضات الاحتمالية بضمانات أسوأ حالة، مما يجعلها عملية عندما تكون المعرفة التوزيعية محدودة.

الفكرة الحدسية وراء الطريقة

تجد البرمجة الخطية العادية أفضل حل بافتراض أن جميع البيانات معروفة بدقة. في الممارسة العملية، يتم تقدير المعاملات أو التنبؤ بها أو قياسها بخطأ. تسأل البرمجة الخطية المتينة: ما هو أفضل قرار يبقى مجديًا بغض النظر عن كيفية تغير المعلمات غير المؤكدة ضمن نطاق معقول؟ يحدد المحلل مجموعة عدم اليقين — صندوق، أو قطع ناقص، أو منطقة متعددة السطوح — ويجد الحل الخطة المثلى لأسوأ حالة داخل تلك المجموعة. تسمح صياغة ميزانية عدم اليقين لـ Bertsimas و Sim للمحلل بضبط التحفظ: يتحكم المعامل Gamma في عدد المعاملات التي يُسمح لها بالانحراف في وقت واحد، مما يؤدي إلى استيفاء بين البرمجة الخطية الاسمية وأسوأ حالة المحافظة بالكامل.

التاريخ

تم وضع التحسين المتين على أساس نظري متين من قبل Ben-Tal و Nemirovski (1999)، الذين أظهروا أن البرامج الخطية غير المؤكدة مع مجموعات عدم اليقين ذات القطع الناقص تؤدي إلى برامج مخروطية من الدرجة الثانية قابلة للمعالجة. قدم Bertsimas و Sim (2004) إطار عمل ميزانية عدم اليقين، والذي يحافظ على إعادة الصياغة كبرنامج خطي ويجعل المتانة قابلة للضبط عبر معلمة واحدة، مما يوسع بشكل كبير التبني العملي في بحوث العمليات والهندسة.

متى تُستخدم

استخدم البرمجة الخطية المتينة عندما يكون عدم اليقين في البيانات حقيقيًا ولكن التوزيعات الاحتمالية غير معروفة أو غير موثوقة، كما هو الحال في تخطيط سلسلة التوريد مع الطلب غير المؤكد، أو إرسال الطاقة مع أخطاء التنبؤ، أو بناء المحافظ المالية تحت عوائد غامضة. وهي مناسبة عندما تكون جدوى القيود في جميع السيناريوهات غير قابلة للتفاوض. تجنب البرمجة الخطية المتينة عندما يكون عدم اليقين ضئيلًا مقارنة بمقياس الهدف، وعندما تكون التوزيعات الاحتمالية محددة جيدًا (قد يكون البرمجة العشوائية مفضلة)، وعندما يكون عدد المعلمات غير المؤكدة كبيرًا جدًا بحيث يصبح المكافئ المتين غير قابل للمعالجة، أو عندما يكون سيناريو أسوأ حالة متشائمًا بشكل غير واقعي للتطبيق.

الحدود والاعتبارات

  • يمكن أن يؤدي اتجاه أسوأ حالة إلى حلول متحفظة بشكل مفرط عندما تكون السيناريوهات المتطرفة غير مرجحة للغاية.
  • تؤدي مجموعات عدم اليقين ذات القطع الناقص إلى برامج مخروطية من الدرجة الثانية قابلة للمعالجة ولكنها لم تعد برامج خطية بحتة، مما يزيد من متطلبات الحل.
  • تتطلب من المحلل تحديد مجموعة عدم يقين، وهي بحد ذاتها خيار نمذجة يؤثر بشكل كبير على النتائج.
  • لا تقدم مباشرة عبارات احتمالية الانتهاك؛ البرمجة العشوائية أفضل إذا كانت احتمالات الذيل مهمة.
  • تتحول إلى البرنامج الخطي الاسمي عندما Gamma = 0، ولا تقدم أي حماية ضد عدم اليقين.

لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.

نقاط القوة

  • توفر ضمانات جدوى صارمة لأسوأ حالة دون الحاجة إلى افتراضات توزيعية.
  • تنتج صياغة ميزانية Bertsimas-Sim مكافئًا خطيًا قابلاً للمعالجة يمكن حله باستخدام حلول جاهزة.
  • يمنح معامل ميزانية المتانة Gamma المحلل مفتاحًا بديهيًا للموازنة بين جودة الحل والتحفظ.
  • فعالة حسابيًا — المكافئات المتينة لمجموعات الميزانية لها تعقيد مماثل للبرنامج الخطي الأصلي.
  • مناسبة بشكل خاص للمشاكل التي يكون فيها انتهاك القيود مكلفًا أو غير آمن.

التطبيقات

  • تصميم شبكة سلسلة التوريد مع تكاليف نقل غير مؤكدة وطلب غير مؤكد
  • إرسال نظام الطاقة الكهربائية تحت عدم يقين التنبؤ بالطاقة المتجددة
  • تحسين المحفظة مع نطاقات عائد أصول غامضة
  • تخطيط علاج العلاج الإشعاعي مع عدم يقين حركة المريض
  • جدولة طاقم الطيران تحت تأخيرات رحلات غير مؤكدة
  • تخصيص موارد المياه مع عدم يقين هطول الأمطار والتبخر

كيف يعمل

كيف يعمل

1

صياغة البرنامج الخطي الاسمي: تقليل دالة الهدف الخطية c^T x مع مراعاة قيود عدم المساواة الخطية Ax <= b وعدم السلبية. تحديد المعاملات التي — عادةً إدخالات مصفوفة القيود a_ij — غير مؤكدة. هذه الخطوة تعكس نمذجة البرمجة الخطية القياسية ولكنها تميز كل معلمة غير مؤكدة.

الصيغة
\min c^T x \text{ s.t. } Ax \leq b, \; x \geq 0
2

إنشاء مجموعة عدم يقين U تلتقط نطاق قيم المعلمات المعقولة دون الحاجة إلى توزيع احتمالي. تشمل الخيارات الشائعة مجموعات الصندوق (تتغير كل معلمة بشكل مستقل ضمن [a_bar - a_hat, a_bar + a_hat])، ومجموعات القطع الناقص (Ben-Tal and Nemirovski, 1999)، ومجموعات الميزانية (Bertsimas and Sim, 2004). تحدد معلمة الميزانية Gamma عدد المعلمات التي يمكن أن تأخذ قيم أسوأ حالة لها في وقت واحد.

الصيغة
\mathcal{U} = \{ a_i : a_i = \bar{a}_i + \hat{a}_i \xi_i, \; \|\xi\|_\infty \leq 1 \}
3

استبدال كل قيد غير مؤكد بنظيره المتين: المطالبة بالجدوى لكل تجلٍ في U. هذا يحول المشكلة الأصلية إلى برنامج شبه لا نهائي — عدد لا نهائي من القيود، واحد لكل عنصر من U.

الصيغة
\max_{a_i \in \mathcal{U}} a_i^T x \leq b_i \quad \forall i
4

اشتقاق مكافئ حتمي قابل للمعالجة. بالنسبة لمجموعات عدم اليقين ذات الميزانية، يعيد المكافئ المتين صياغته كبرنامج خطي قياسي أو برنامج خطي مختلط صحيح بنفس الحجم تقريبًا، قابل للحل باستخدام الحلول التقليدية. تقدم إعادة الصياغة الرئيسية متغيرات مساعدة تضفي خطية على الحد الأقصى الداخلي على مجموعة عدم اليقين.

الصيغة
\bar{a}_i^T x + \Gamma_i \max_{\{S: |S| \leq \Gamma_i\}} \sum_{j \in S} \hat{a}_{ij} |x_j| \leq b_i
5

حل البرنامج الخطي المعاد صياغته باستخدام حل قياسي (simplex أو interior-point). تقييم الحل: التحقق من انتهاك قيد أسوأ حالة عبر مجموعة عدم اليقين، والإبلاغ عن سعر المتانة (زيادة الهدف بالنسبة للبرنامج الخطي الاسمي)، وإجراء تحليل الحساسية لمعامل ميزانية المتانة Gamma.

الأخطاء الشائعة

  • جعل Gamma مرتفعًا جدًا يجعل كل قيد في أسوأ حالة في وقت واحد، مما يؤدي إلى حل متحفظ ومكلف للغاية.
  • قد يؤدي سوء تحديد مجموعة عدم اليقين (على سبيل المثال، تجاهل هيكل الارتباط) إلى حماية مفرطة أو ناقصة.
  • الخلط بين البرمجة الخطية المتينة والبرمجة الخطية العشوائية: تزيد البرمجة الخطية المتينة من أداء أسوأ حالة، وليس الأداء المتوقع.
  • تجاهل تقرير سعر المتانة — قارن دائمًا الحل المتين بهدف البرنامج الخطي الاسمي لقياس تكلفة التحفظ.
  • تطبيق البرمجة الخطية المتينة على مشاكل ذات متغيرات صحيحة دون التحول إلى صياغة البرمجة الخطية المختلطة الصحيحة المتينة، والتي تتطلب صياغات مختلفة.

الأسئلة الشائعة

كيف تختلف البرمجة الخطية المتينة عن البرمجة الخطية العشوائية؟

تقوم البرمجة الخطية العشوائية بتحسين الأداء المتوقع بالنظر إلى توزيع احتمالي عبر السيناريوهات، وتتطلب معرفة توزيعية. تقوم البرمجة الخطية المتينة بتحسين أداء أسوأ حالة عبر مجموعة عدم يقين، وتتطلب فقط حدودًا — لا يوجد توزيع احتمالي. تُفضل البرمجة الخطية المتينة عندما تكون التوزيعات غير موثوقة؛ تُفضل البرمجة الخطية العشوائية عندما تكون مقدرة جيدًا.

ما هو سعر المتانة؟

سعر المتانة هو الزيادة في قيمة الهدف (التكلفة) للحل المتين مقارنة بحل البرنامج الخطي الاسمي. أثبت Bertsimas و Sim (2004) أن هذا السعر ينمو فقط مع الجذر التربيعي لعدد المعلمات غير المؤكدة لمجموعات الميزانية، مما يجعل المتانة ميسورة التكلفة بشكل مدهش.

ما هي ميزانية المتانة Gamma؟

Gamma هي معلمة في نموذج Bertsimas-Sim تتحكم في عدد المعاملات غير المؤكدة التي يُسمح لها بأخذ قيم أسوأ حالة لها في وقت واحد. Gamma = 0 يستعيد البرنامج الخطي الاسمي؛ Gamma = n يحمي ضد انحراف جميع المعلمات n دفعة واحدة. يختار المحللون عادةً Gamma بناءً على حدود احتمالية الانتهاك المقبولة.

هل تتطلب البرمجة الخطية المتينة حلاً خاصًا؟

لا. بالنسبة لمجموعات عدم اليقين من نوع الصندوق والميزانية، فإن المكافئ المتين هو بحد ذاته برنامج خطي، قابل للحل بواسطة أي حل خطي قياسي (CPLEX، Gurobi، HiGHS، إلخ). تتطلب مجموعات القطع الناقص حلاً لبرنامج مخروطي من الدرجة الثانية، والذي يتم دعمه أيضًا على نطاق واسع.

متى يجب أن أستخدم البرمجة الخطية المختلطة الصحيحة المتينة بدلاً من ذلك؟

إذا كان يجب أن تكون متغيرات القرار صحيحة (على سبيل المثال، قرارات نعم/لا ثنائية، أحجام دفعات)، فإن المكافئ المتين يحتوي على متغيرات صحيحة ويصبح برنامجًا خطيًا مختلطًا صحيحًا متينًا. نهج مجموعة عدم اليقين هو نفسه، ولكن متطلبات إعادة الصياغة والحل تتغير وفقًا لذلك.

طرق ذات صلة

المصادر

  1. Bertsimas, D., Sim, M. (2004). The price of robustness. Operations Research, 52(1), 35–53.

    افتح مرجع DOI
    تم النسخ.
  2. Ben-Tal, A., Nemirovski, A. (1999). Robust solutions of uncertain linear programs. Operations Research Letters, 25(1), 1–13.

    افتح مرجع DOI
    تم النسخ.