البرمجة الخطية العشوائية — التحسين في ظل عدم اليقين مع معاملات عشوائية
- قدّمه
- George B. Dantzig
- السنة
- 1955
- النوع
- Stochastic optimization model
- العائلة
- Simulation / optimization
هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية
ماذا تفعل؟
تمتد البرمجة الخطية العشوائية (SLP) البرمجة الخطية الكلاسيكية إلى الحالات التي تكون فيها بعض معاملات النموذج — التكاليف، والطلبات، وتوافر الموارد — غير مؤكدة ويتم نمذجتها كمتغيرات عشوائية. من خلال تحسين التكاليف المتوقعة عبر توزيع احتمالي للسيناريوهات، تنتج البرمجة الخطية العشوائية قرارات تظل قابلة للتنفيذ وشبه مثلى عبر مجموعة من المستقبلات الممكنة بدلاً من حالة واحدة مفترضة للعالم.
الفكرة الحدسية وراء الطريقة
تفترض البرمجة الخطية الكلاسيكية أن كل معامل معروف بدقة. في الممارسة العملية، يكون الطلب المستقبلي والأسعار والمحصول غير مؤكد. تدمج البرمجة الخطية العشوائية هذا عدم اليقين مباشرة في النموذج: بدلاً من التحسين لسيناريو واحد ثابت، يختار المخطط إجراءات المرحلة الأولى الآن، ويلاحظ أي سيناريو يتحقق، ثم يتخذ إجراءات تصحيحية لتصحيح أي نقص أو فائض. الهدف يقلل من إجمالي التكلفة المتوقعة عبر جميع السيناريوهات، موازناً تكاليف الالتزام بتكاليف الإجراءات التصحيحية المتوقعة. هذا يعكس منطق الإدارة الحقيقي — أنت تقرر اليوم ما قبل الطلب، وغداً يمكنك شراء المزيد بسعر مميز أو بيع الفائض بخصم.
التاريخ
تمت ريادة البرمجة العشوائية بواسطة جورج دانتزيغ، الذي قدم نموذج المرحلتين في عام 1955 بعد فترة وجيزة من تطوير طريقة السمبلكس. اقترح بيل (1955) بشكل مستقل أفكارًا مماثلة. تم تنظيم المجال بواسطة كتاب بيرج ولويفو المؤثر لعام 1997 وتطوير خوارزمية تفكيك L-shaped (Benders) في الستينيات إلى الثمانينيات. أصبحت البرمجة الخطية العشوائية الآن أساسًا للقرارات التشغيلية في الطاقة والخدمات اللوجستية والتمويل في جميع أنحاء العالم.
متى تُستخدم
استخدم البرمجة الخطية العشوائية عندما: (1) تكون المعاملات الرئيسية مدخلات غير مؤكدة حقًا ويمكن توصيفها بتوزيع احتمالي أو مجموعة سيناريوهات تجريبية؛ (2) يجب اتخاذ القرارات قبل حل عدم اليقين، ولكن الإجراءات التصحيحية ممكنة بعد ذلك بتكلفة؛ (3) الهدف والقيود خطية في متغيرات القرار. تشمل التطبيقات النموذجية تخطيط الإنتاج، وتصميم سلسلة التوريد، وتوزيع الطاقة، وتحسين المحفظة. لا تستخدم البرمجة الخطية العشوائية عندما: لا يمكن قياس عدم اليقين احتماليًا (استخدم التحسين القوي بدلاً من ذلك)؛ العلاقة بين القرارات والنتائج غير خطية أو صحيحة (استخدم البرمجة الصحيحة العشوائية أو البرمجة الديناميكية العشوائية)؛ مجموعة السيناريوهات كبيرة جدًا بحيث لا يمكن تعدادها وتفكيكها غير ممكن حسابيًا؛ أو عندما يكون تحليل الحساسية الحتمي الأبسط كافياً لفهم تأثير عدم اليقين.
الحدود والاعتبارات
- تتطلب تحديد توزيع احتمالي أو مجموعة سيناريوهات للمعاملات غير المؤكدة — هذا الافتراض التوزيعي غالبًا ما يكون صعب التحقق منه.
- يزداد العبء الحسابي بسرعة مع عدد السيناريوهات ومتغيرات المرحلة الأولى؛ تتطلب المشاكل الكبيرة التفكيك وموارد حلال كبيرة.
- مقتصرة على الهدف والقيود الخطية؛ الهياكل غير الخطية أو الصحيحة تتطلب امتدادات تضيف مزيدًا من التعقيد.
- قد يتجاهل هدف القيمة المتوقعة مخاطر الذيل؛ المتغيرات المتحفظة تجاه المخاطر (CVaR، قيود الفرصة) تضيف عبئًا نمطيًا وحسابيًا إضافيًا.
لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.
نقاط القوة
- يدمج بشكل مباشر عدم اليقين الاحتمالي في التحسين، وينتج قرارات قوية عبر السيناريوهات بدلاً من مستقبل واحد مفترض.
- يعكس إطار المرحلتين عن كثب عمليات اتخاذ القرار الحقيقية: الالتزام الآن، والتكيف لاحقًا بالإجراءات التصحيحية.
- توفر قيمة الحل العشوائي (VSS) و EVPI مقاييس مبدئية لتوصيل فائدة نمذجة عدم اليقين.
- مدعومة جيدًا بخوارزميات ناضجة (L-shaped / Benders decomposition) وحلالات تجارية (CPLEX, Gurobi).
- تتوسع لتشمل مشاكل عملية كبيرة عبر التفكيك؛ قابلة للموازاة عبر السيناريوهات.
التطبيقات
- تخطيط نظام الطاقة الكهربائية والتزام الوحدات في ظل توليد متجدد وطلب غير مؤكد.
- تصميم شبكة سلسلة التوريد مع طلب عملاء غير مؤكد، أو أوقات تسليم، أو تكاليف نقل.
- تخطيط المحاصيل والري في ظل هطول أمطار وأسعار سلع غير مؤكدة.
- تحسين المحفظة المالية مع عوائد أصول غير مؤكدة في ظل قيود الميزانية والتنظيمية.
- إدارة إيرادات شركات الطيران وجدولة الطاقم في ظل طلب ركاب غير مؤكد.
- تحديد المواقع المسبق للإمدادات الإنسانية قبل سيناريوهات الكوارث غير المؤكدة.
كيف يعمل
كيف يعمل
صياغة نموذج المرحلتين: متغيرات المرحلة الأولى x تمثل قرارات هنا والآن التي يتم اتخاذها قبل حل عدم اليقين؛ الهدف يقلل من تكلفة المرحلة الأولى c^T x بالإضافة إلى تكلفة الإجراء التصحيحي المتوقعة E[Q(x,xi)] عبر المتجه العشوائي xi. يجب أن تتحقق القيود Ax = b لقرارات المرحلة الأولى بغض النظر عن السيناريو.
الصيغة
\min_{x} c^T x + \mathbb{E}_\xi[Q(x, \xi)] \quad \text{s.t. } Ax = b,\; x \geq 0تمثيل المتجه العشوائي xi عبر مجموعة سيناريوهات منفصلة {xi_1, ..., xi_S} لكل منها احتمال p_s يساوي 1. يمكن سحب السيناريوهات من البيانات التاريخية، أو تقييم الخبراء، أو أخذ عينات مونت كارلو. تحدد جودة مجموعة السيناريوهات بشكل حاسم جودة الحل؛ تُطبق تقنيات تقليل السيناريوهات (مثل تجميع مسافة واسرشتاين) بشكل شائع للحفاظ على حجم المشكلة قابلاً للإدارة.
لكل سيناريو xi_s، حل مشكلة الإجراء التصحيحي الفرعية: بالنظر إلى قرار المرحلة الأولى x، ابحث عن أرخص إجراء تصحيحي y_s يحقق W y_s = h(xi_s) - T(xi_s) x، y_s >= 0. إذا لم يكن هناك إجراء تصحيحي قابل للتنفيذ، يتم تكبد عقوبة كبيرة (أو عدم قابلية للتنفيذ)، مما يشير إلى أن قرار المرحلة الأولى كان جريئًا للغاية.
الصيغة
Q(x, \xi) = \min_{y} q(\xi)^T y \quad \text{s.t. } W y = h(\xi) - T(\xi) x,\; y \geq 0حل الشكل الموسع الكامل (جميع السيناريوهات مكدسة كمشكلة برمجة خطية واحدة كبيرة) لمجموعات السيناريوهات الصغيرة إلى المتوسطة، أو تطبيق تفكيك بندر (طريقة L-shaped) للمجموعات الكبيرة. تضيف طريقة L-shaped بشكل متكرر قيود الأمثلية وقابلية التنفيذ إلى مشكلة رئيسية حتى التقارب، مستغلة الهيكل القطري الكتلي لمشاكل السيناريوهات الفرعية.
تقييم جودة الحل عبر قيمة الحل العشوائي (VSS) — المكسب مقارنة بحل المتوسط الحتمي، وقيمة المعلومات المثالية المتوقعة (EVPI) — الحد الأعلى لما ستكون عليه المعرفة المستقبلية المثالية. الإبلاغ عن قرار المرحلة الأولى x*، والتكلفة الإجمالية المتوقعة، وتكاليف الإجراءات التصحيحية لكل سيناريو لتوصيل ملف المخاطر لصناع القرار.
الأخطاء الشائعة
- استخدام عدد قليل جدًا من السيناريوهات ينتج حلاً متحيزًا يؤدي أداءً ضعيفًا خارج العينة؛ تحقق دائمًا من خلال اختبار سيناريوهات خارج العينة.
- الخلط بين حل المتوسط الحتمي (تطبيق القيم المتوقعة) والحل العشوائي — يمكن أن تكون قيمة الحل العشوائي كبيرة حتى عندما تبدو المعاملات مستقرة.
- تجاهل قابلية تنفيذ الإجراء التصحيحي: إذا كانت مشكلة المرحلة الثانية الفرعية يمكن أن تكون غير قابلة للتنفيذ لبعض السيناريوهات، فإن النموذج يحتاج إلى قيود إجراء تصحيحي كاملة أو عقوبات صريحة.
- الإفراط في التكيف مع التوزيع التاريخي للسيناريوهات دون اختبار الضغط مقابل سيناريوهات الذيل أو السيناريوهات العدائية، خاصة في تطبيقات سلسلة التوريد أو المالية.
- معاملة البرمجة الخطية العشوائية كبديل مباشر للتحسين القوي عندما يكون صانع القرار غير محايد تجاه عدم اليقين بدلاً من محايد تجاه القيمة المتوقعة.
الأسئلة الشائعة
ما الفرق بين البرمجة الخطية العشوائية والتحسين القوي؟
تقلل البرمجة الخطية العشوائية من التكلفة المتوقعة عبر توزيع احتمالي للسيناريوهات وتسمح بإجراءات تصحيحية بعد حل عدم اليقين. بدلاً من ذلك، يحسن التحسين القوي الحالة الأسوأ عبر مجموعة عدم اليقين دون افتراض توزيع احتمالي وينتج عادةً حلاً ثابتًا واحدًا يكون قابلاً للتنفيذ لجميع السيناريوهات. البرمجة الخطية العشوائية مفضلة عندما يمكن تقدير الاحتمالات؛ التحسين القوي مفضل عندما تكون مجموعة عدم اليقين معروفة فقط أو عندما تكون حماية مخاطر الذيل ذات أهمية قصوى.
كم عدد السيناريوهات المطلوبة عادةً؟
يعتمد هذا على أبعاد المشكلة وتعقيد التوزيع. غالبًا ما تكون عشرات إلى بضع مئات من السيناريوهات كافية لمشاكل التخطيط إذا تم إنشاؤها بذكاء (على سبيل المثال، عبر مطابقة العزوم أو تقليل السيناريوهات). قد تتطلب تقنية تقريب متوسط العينة المستندة إلى مونت كارلو (SAA) آلاف السيناريوهات للحصول على حلول عالية الدقة، مع فترات ثقة توجه التقارب.
هل يمكن للبرمجة الخطية العشوائية التعامل مع القرارات الصحيحة أو الثنائية؟
ليس بشكل مباشر — تتطلب المتغيرات الصحيحة البرمجة الصحيحة العشوائية (SIP) أو البرمجة المختلطة الصحيحة العشوائية (SMIP)، وهي أصعب بكثير من الناحية الحسابية. تنطبق البرمجة الخطية العشوائية فقط عندما تكون جميع متغيرات القرار مستمرة.
ماذا تقيس قيمة الحل العشوائي (VSS)؟
VSS = EEV - RP، حيث EEV هي التكلفة المتوقعة لحل المتوسط الحتمي المقيم عبر جميع السيناريوهات، و RP هو الأمثل العشوائي الحقيقي (مشكلة الإجراء التصحيحي). تشير قيمة VSS العالية إلى أن تجاهل عدم اليقين واستخدام المعاملات المتوسطة يؤدي إلى نتائج أسوأ بكثير.
ما هي الحلالات والبرامج التي تدعم البرمجة الخطية العشوائية؟
يمكن للحلالات التجارية مثل CPLEX و Gurobi حل الشكل الموسع مباشرة. تشمل الأطر مفتوحة المصدر قارئات تنسيق SMPS، و PySP (جزء من Pyomo)، وحزمة Julia StochasticPrograms.jl. بالنسبة للمشاكل واسعة النطاق، غالبًا ما تكون تطبيقات تفكيك L-shaped المخصصة شائعة في البحث والصناعة.
طرق ذات صلة
المصادر
Dantzig, G. B., & Madansky, A. (1961). On the solution of two-stage linear programs under uncertainty. Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, 1, 165–176.
افتح مرجع المنشورتم النسخ.Birge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. Springer, New York.
ردمك: 9780387982175تم النسخ.