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

البرمجة الصحيحة المختلطة العشوائية — الأمثلية في ظل عدم اليقين مع قرارات متقطعة ومستمرة

قدّمه
Birge, J. R.; Louveaux, F.; Sen, S.
السنة
1990s–2000s
النوع
Stochastic optimization model
العائلة
Simulation / optimization

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

حجم الخط

ماذا تفعل؟

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

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

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

التاريخ

نشأت البرمجة العشوائية مع Dantzig (1955) و Beale (1955) كبرمجة خطية على مرحلتين. ظهر الامتداد الصحيح المختلط بشكل بارز في التسعينيات مع تكييفات طريقة الشكل L للاسترداد الصحيح بواسطة Laporte و Louveaux (1993) والمعالجة الشاملة في كتاب Birge و Louveaux لعام 1997. تقدم خوارزمية C3/D2 لـ Sen و Higle (2005) حلول SMIP قابلة للتوسع، مما يؤسس المجال كتخصص ناضج ضمن بحوث العمليات.

متى تُستخدم

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

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

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

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

نقاط القوة

  • تتعامل مع قرارات منفصلة توافقية في ظل عدم اليقين في نموذج أمثلية واحد متماسك.
  • تنتج خطط مرحلة أولى متحوطة توازن الأداء المتوقع عبر جميع السيناريوهات.
  • توفر مقاييس VSS و EVPI تبريرًا شفافًا لقيمة النمذجة العشوائية.
  • خوارزميات التحلل (الشكل L، الترحيل التدريجي) تتوسع لتشمل مجموعات سيناريوهات كبيرة.
  • مدعومة على نطاق واسع في الحلول التجارية (CPLEX، Gurobi) ولغات النمذجة (AMPL، Pyomo).

التطبيقات

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

كيف يعمل

كيف يعمل

1

تحديد متغيرات القرار: قرارات المرحلة الأولى x المتخذة قبل الكشف عن عدم اليقين (أعداد صحيحة و/أو ثنائية من بينها)، ومتغيرات الاسترداد للمرحلة الثانية y(xi) المتخذة بعد تحقق السيناريو xi. تحديد معاملات الهدف، ومصفوفات القيود، وتوزيع الاحتمالات أو مجموعة السيناريوهات المنفصلة للمعلمات غير المؤكدة.

2

إنشاء مجموعة سيناريوهات منفصلة {xi_1, ..., xi_S} مع احتمالات مرتبطة بها {p_1, ..., p_S} تقريب التوزيع الأساسي. يمكن اشتقاق السيناريوهات من البيانات التاريخية، أو استخلاص آراء الخبراء، أو أخذ عينات من فضاء لاتين هايبركيوب، أو طرق مطابقة العزوم. جودة السيناريو تؤثر بشكل مباشر على جودة الحل.

3

صياغة المكافئ الحتمي: تقليل c'x + sum_s p_s Q(x, xi_s) مع مراعاة قيود المرحلة الأولى والصحة. Q(x, xi_s) هي دالة قيمة المرحلة الثانية — تكلفة الإجراءات الاستردادية المثلى بالنظر إلى x والسيناريو xi_s. البرنامج المدمج هو برنامج برمجة صحيحة مختلطة كبير ينمو حجمه مع عدد السيناريوهات.

الصيغة
\min_{x \in X} c^T x + \mathbb{E}_\xi[Q(x,\xi)] \quad \text{s.t. } Ax = b,\; x \in \mathbb{Z}^p \times \mathbb{R}^{n-p}
4

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

5

تقييم الحل عبر قيمة الحل العشوائي (VSS = EEV - RP) وقيمة المعلومات المثالية المتوقعة (EVPI = RP - WS)، حيث RP هي القيمة المثلى لمشكلة الاسترداد، وEEV هي التكلفة المتوقعة لاستخدام حل القيمة المتوسطة الحتمية، وWS هي قيمة الانتظار والمشاهدة. هذه المقاييس تحدد فائدة نمذجة عدم اليقين بشكل صريح.

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

  • استخدام عدد قليل جدًا من السيناريوهات يقلل من تمثيل عدم اليقين، مما ينتج حلولًا مفرطة الثقة؛ الكثير منها يجعل النموذج غير قابل للحل حسابيًا.
  • الخلط بين أدوار متغيرات المرحلة الأولى والمرحلة الثانية يؤدي إلى صياغات لا تحترم توقيت الكشف عن المعلومات.
  • الاعتماد على حل القيمة المتوقعة (تجاهل العشوائية) يمكن أن يكون دون المستوى الأمثل بشكل كبير — احسب دائمًا VSS لتبرير جهد SMIP.
  • إهمال الصحة في مرحلة الاسترداد عندما تكون موجودة بالفعل ينتج عنه استرخاء قد يكون غير عملي في الممارسة العملية.
  • غالبًا ما تحتاج إعدادات الحل الافتراضية لـ MIP إلى ضبط (أولويات التفرع، استراتيجيات القطع) في أطر عمل تحلل SMIP.

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

ما الفرق بين SMIP والبرمجة الصحيحة المختلطة العادية؟

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

كم عدد السيناريوهات التي أحتاجها؟

لا توجد قاعدة عالمية. قد يكون عدد قليل من 10-50 سيناريو كافيًا لقرارات مرحلة أولى مستقرة في بعض المشاكل؛ البعض الآخر يتطلب الآلاف. تساعد تقنيات تقليل السيناريوهات واختبارات الاستقرار (التحقق من أن الحل الأمثل لا يتغير عند إضافة المزيد من السيناريوهات) في تحديد الكفاية.

ما هي طريقة الشكل L؟

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

متى يجب أن أستخدم الترحيل التدريجي بدلاً من الشكل L؟

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

هل يمكن لـ SMIP التعامل مع أكثر من مرحلتين؟

نعم، ولكن البرمجة الصحيحة المختلطة العشوائية متعددة المراحل تتطلب شجرة سيناريوهات تنمو بشكل أسي مع عدد المراحل، ويصبح التحلل أكثر تعقيدًا بشكل كبير. في الممارسة العملية، تستخدم معظم نماذج SMIP التطبيقية مرحلتين، وتقرب ديناميكيات متعددة الفترات عبر أفق متجدد أو تجميع.

طرق ذات صلة

المصادر

  1. Birge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. Springer Series in Operations Research. New York: Springer.

    ردمك: 9780387982175
    تم النسخ.
  2. Sen, S., & Higle, J. L. (2005). The C3 theorem and a D2 algorithm for large scale stochastic mixed-integer programming: Set convexification. Mathematical Programming, 104(1), 1–20.

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