البرمجة الصحيحة العشوائية — تحسين القرارات المنفصلة في ظل عدم اليقين
- قدّمه
- Dantzig, G. B.; Beale, E. M. L.
- السنة
- 1955
- النوع
- Optimization under uncertainty with discrete decisions
- العائلة
- Simulation / optimization
هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية
ماذا تفعل؟
تُعد البرمجة الصحيحة العشوائية (SIP) إطارًا تحسينًا يجمع بين متغيرات القرار الصحيحة (المنفصلة) والنمذجة الاحتمالية الصريحة لعدم اليقين. تسعى إلى تحديد أفضل قرار فوري (here-and-now) يقلل التكلفة المتوقعة (أو يزيد المنفعة المتوقعة) عبر توزيع لسيناريوهات مستقبلية، مع الأخذ في الاعتبار حقيقة أن بعض القرارات يجب اتخاذها قبل حل عدم اليقين.
الفكرة الحدسية وراء الطريقة
العديد من القرارات الواقعية تكون منفصلة (بناء منشأة أم لا؛ تعيين عامل أم لا) وغير مؤكدة (الطلب، التكاليف، والقيود غير معروفة وقت اتخاذ القرار). تعالج البرمجة الصحيحة العشوائية هاتين التحديين في وقت واحد. فهي تُنمذج المستقبل غير المؤكد كمجموعة من السيناريوهات ذات الاحتمالات المرتبطة بها، ثم تجد الحل الصحيح الذي يؤدي أفضل أداء في المتوسط — أو الذي يتحوط ضد أسوأ النتائج. على عكس البرمجة الخطية العشوائية، فإن الهيكل المنفصل يجعل المشكلة أصعب من الناحية التوافقية، ولكن القرارات الناتجة قابلة للتنفيذ مباشرة دون تقريب أو تقدير.
التاريخ
تعود جذور البرمجة العشوائية إلى Dantzig (1955) و Beale (1955)، اللذين اقترحا بشكل مستقل نماذج إجراء تصحيحي ذات مرحلتين للبرامج الخطية في ظل عدم اليقين. ظهر الامتداد الصحيح مع نضوج البرمجة الصحيحة خلال الستينيات إلى الثمانينيات. قام كتاب Birge and Louveaux (1997) بتدوين هذا المجال، وأسس Kleywegt et al. (2002) تقريب متوسط العينة كنهج حسابي قياسي للتحسين المتقطع واسع النطاق.
متى تُستخدم
استخدم البرمجة الصحيحة العشوائية عندما تكون القرارات منفصلة بطبيعتها (خيارات ثنائية، تخصيص وحدات كاملة، تعيينات توجيه) وتكون المعلمات الرئيسية غير مؤكدة وقت اتخاذ القرار. وهي مناسبة لتخطيط السعة، تصميم شبكة سلسلة التوريد، الجدولة في ظل عدم يقين الطلب، توزيع الطاقة، وتخصيص الموارد ذات الإنتاجية العشوائية. لا تستخدمها عندما تكون جميع المتغيرات مستمرة (تكفي البرمجة الخطية العشوائية)، عندما يكون عدم اليقين ضئيلًا أو يمكن ملاحظته بالكامل قبل اتخاذ القرار، عندما يكون حجم المشكلة يجعل تعداد السيناريوهات غير قابل للحساب حسابيًا دون بنية تحتية للتفكيك، أو عندما يكون سيناريو حتمي واحد فقط ذا صلة.
الحدود والاعتبارات
- تنمو التعقيدات الحسابية بسرعة مع عدد السيناريوهات والمتغيرات الصحيحة؛ الحالات الكبيرة هي NP-hard.
- يتطلب إنشاء السيناريوهات توزيعات احتمالية موثوقة، والتي قد يكون من الصعب استخلاصها أو تقديرها من بيانات محدودة.
- تمتد الامتدادات متعددة المراحل (أكثر من مرحلتين) إلى نمو أسي في أشجار السيناريو ونادرًا ما تكون قابلة للحساب بعد ثلاث مراحل.
- تتطلب مهارة نمذجة لتحديد جدوى الإجراء التصحيحي بشكل صحيح، وقيود عدم الاستباقية، وهياكل العقوبات.
لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.
نقاط القوة
- تُنمذج عدم اليقين بشكل صريح بدلاً من استخدام تقديرات نقطية، مما ينتج عنه حلول قوية للسيناريوهات المحققة.
- تتعامل مع القرارات المنفصلة والثنائية بشكل أصلي، لذا فإن الحلول قابلة للتنفيذ مباشرة دون تقريب لاحق.
- يفصل إطار المرحلتين بوضوح بين قرارات المرحلة الأولى الاستراتيجية وإجراءات الإجراء التصحيحي للمرحلة الثانية التشغيلية.
- تدعم هياكل الإجراء التصحيحي الغنية بما في ذلك شراء الموارد، تكاليف العقوبات، والجدولة التصحيحية.
- تسمح الحدود الإحصائية للجودة (عبر SAA) للممارسين بالمصادقة على شبه الأمثلية بثقة مُقاسة.
التطبيقات
- تصميم شبكة سلسلة التوريد في ظل الطلب وأوقات التسليم العشوائية
- تخطيط توسيع توليد الطاقة مع إنتاج متجدد غير مؤكد
- جدولة غرف العمليات في المستشفى في ظل أوقات إجراءات متغيرة
- جدولة طاقم الطائرات في ظل تأخيرات رحلات عشوائية
- تحديد المواقع المسبق للخدمات اللوجستية الإنسانية للإمدادات قبل الكوارث
- تحسين المحفظة المالية مع اختيار الأصول المنفصلة وعوائد قائمة على السيناريوهات
كيف يعمل
كيف يعمل
صياغة مشكلة المرحلة الأولى: اختيار متغيرات القرار الصحيحة (أو المختلطة الصحيحة) x قبل الكشف عن عدم اليقين. تحديد هدف يشمل كلاً من التكلفة الفورية وتكلفة الإجراء التصحيحي المتوقعة عبر جميع السيناريوهات. يتم تحديد القيود التي تربط x بشروط الجدوى هنا.
الصيغة
\min_{x \in \mathbb{Z}^n} c^T x + \mathbb{E}_\xi[Q(x, \xi)]تمثيل عدم اليقين من خلال مجموعة محدودة من السيناريوهات. كل سيناريو يُسند قيمًا محددة للمعلمات العشوائية (مستويات الطلب، التكاليف، توفر الموارد). يمكن إنشاء السيناريوهات عبر أخذ عينات تاريخية، أو سحوبات مونت كارلو من توزيعات مُلائمة، أو حالات تمثيلية محددة من قبل الخبراء. يحمل كل سيناريو وزنًا احتماليًا مجموعه واحد.
في الصياغة القياسية ذات المرحلتين، بعد تثبيت x وتحقق السيناريو xi، تحدد مشكلة الإجراء التصحيحي (المرحلة الثانية) الإجراءات التصحيحية y. غالبًا ما تكون مشكلة الإجراء التصحيحي برنامجًا خطيًا أو صحيحًا. النموذج الكامل يقلل c^T x بالإضافة إلى تكلفة الإجراء التصحيحي المتوقعة E[Q(x, xi)].
الصيغة
Q(x, \xi) = \min_{y \geq 0} q(\xi)^T y \;\text{ s.t. } W(\xi)y = h(\xi) - T(\xi)xحل مشكلات السيناريو الفرعية لتقييم تكلفة الإجراء التصحيحي لكل سيناريو بالنظر إلى x. تشمل التقنيات طريقة التفرع والحد (branch-and-bound)، تفكيك Benders، الاسترخاء اللاغرانجي، وطريقة تقريب متوسط العينة (SAA). بالنسبة لأشجار السيناريو الكبيرة، تستغل خوارزميات التفكيك الهيكل الكتلي عبر السيناريوهات.
تجميع نتائج المشكلات الفرعية لتقدير تكلفة الإجراء التصحيحي المتوقعة. في SAA، هذا هو المتوسط عبر S سيناريو مُعين. التقريب الناتج يتقارب إلى التوقع الحقيقي مع نمو S. يمكن حساب حدود إحصائية لجودة الحل من تباين العينة.
الصيغة
\mathbb{E}_\xi[Q(x,\xi)] \approx \frac{1}{S} \sum_{s=1}^{S} Q(x, \xi_s)التحقق من الأمثلية أو شبه الأمثلية عبر فجوات الأمثلية، معايير التقارب، أو فترات الثقة الإحصائية من SAA. إذا لم تكن الفجوة مقبولة، قم بتنقيح مجموعة السيناريوهات، زيادة حجم العينة، أو تشديد الاسترخاءات. قم بالإبلاغ عن حل المرحلة الأولى x* وتكلفته الإجمالية المتوقعة.
الأخطاء الشائعة
- استخدام عدد قليل جدًا من السيناريوهات ينتج عنه حلول مفرطة الثقة؛ استخدام عدد كبير جدًا يجعل المشكلة غير قابلة للحساب — يتم تحقيق التوازن عبر تشخيصات تقارب SAA.
- تجاهل التكاملية في المرحلة الثانية عندما تكون مطلوبة فعليًا يؤدي إلى تقديرات تكلفة متفائلة وإجراءات تصحيحية غير مجدية.
- افتراض استقلال السيناريوهات عندما تكون المعلمات مترابطة (مثل، الطلب والسعر المترابطان) يُدخل تحيزًا منهجيًا في تقدير التكلفة المتوقعة.
- نسيان قيود عدم الاستباقية في المشكلات متعددة المراحل يسمح للنموذج باستغلال المعلومات المستقبلية التي لن تكون متاحة في الممارسة العملية.
الأسئلة الشائعة
كيف تختلف البرمجة الصحيحة العشوائية عن التحسين القوي؟
تقلل البرمجة الصحيحة العشوائية من التكلفة المتوقعة عبر مجموعة سيناريوهات مرجحة احتماليًا، مع قبول أن بعض السيناريوهات قد تسفر عن تكلفة عالية إذا كانت غير محتملة. التحسين القوي يقلل من أسوأ تكلفة عبر مجموعة عدم اليقين، دون افتراضات احتمالية. تتطلب البرمجة الصحيحة العشوائية توزيعًا احتماليًا؛ التحسين القوي يتطلب فقط مجموعة عدم اليقين. البرمجة الصحيحة العشوائية أقل تحفظًا بشكل عام ولكنها تتطلب بيانات أكثر.
كم عدد السيناريوهات المطلوبة عمليًا؟
يعتمد هذا على بُعد المشكلة والدقة المطلوبة. يوفر نهج تقريب متوسط العينة (SAA) فترات ثقة إحصائية حول فجوة الأمثلية. تستخدم الدراسات التطبيقية النموذجية عشرات إلى آلاف السيناريوهات؛ تشخيصات التقارب (تباين مقدر الفجوة) توجه الاختيار. بالنسبة للمشكلات المهيكلة، يمكن لتقنيات تقليل السيناريوهات (مثل Heitsch-Romisch) تقليل عدد السيناريوهات بشكل كبير.
هل يمكن للبرمجة الصحيحة العشوائية التعامل مع أكثر من مرحلتين؟
نعم، ولكن البرمجة الصحيحة العشوائية متعددة المراحل أصعب بكثير. تنمو شجرة السيناريو بشكل أسي مع المراحل، ويجب فرض قيود عدم الاستباقية عند كل عقدة. عمليًا، نماذج المرحلتين هي القاعدة للتطبيقات القابلة للحساب؛ ما وراء ذلك، عادة ما تكون هناك حاجة إلى تقريبات مثل الأفق المتداول أو تقليل شجرة السيناريو.
ما هي البرامج التي يمكنها حل نماذج البرمجة الصحيحة العشوائية؟
تشمل الحلول الشائعة CPLEX و Gurobi (عبر لغات النمذجة الجبرية مثل AMPL، JuMP في Julia، أو PuLP/Pyomo في Python)، والتي تدعم تفكيك السيناريوهات. تشمل أطر البرمجة العشوائية المتخصصة PySP (Python)، وصيغة SMPS للحلول، وحزمة Julia StochasticPrograms.jl، التي تنفذ SAA والتمويل التدريجي (progressive hedging).
هل البرمجة الصحيحة العشوائية هي نفسها البرمجة الصحيحة المختلطة العشوائية؟
البرمجة الصحيحة العشوائية هي الفئة الأوسع؛ تشير البرمجة الصحيحة المختلطة العشوائية (SMIP) تحديدًا إلى النماذج التي تكون فيها بعض المتغيرات مستمرة والبعض الآخر صحيح في مرحلة واحدة أو كليهما. SMIP هو الشكل الأكثر عمومية والأكثر شيوعًا في الممارسة العملية.
طرق ذات صلة
المصادر
Birge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. Springer, New York.
ردمك: 978-1-4614-0237-4تم النسخ.Kleywegt, A. J., Shapiro, A., & Homem-de-Mello, T. (2002). The sample average approximation method for stochastic discrete optimization. SIAM Journal on Optimization, 12(2), 479-502.
افتح مرجع DOIتم النسخ.