Stochastic programming — البرمجة التصادفية

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

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

Mathematical formulation - الصياغة الرياضية

بشكل عام، يمكن صياغة مسألة البرمجة التصادفية على النحو التالي: $\underset{x\in X}{\min }\mathbb{𝔼}[f(x,\xi )]$ حيث:

• $x$ — متجه متغيرات التحكم (القرارات) التي يجب تحديدها.
• $X$ — مجموعة الحلول الممكنة للمتجه $x$، والتي تحددها القيود الحتمية.
• $\xi$ — متجه عشوائي يمثل المعلمات غير المؤكدة في المسألة (مثل الطلب، الأسعار، الظروف الجوية).
• $f(x,\xi )$ — دالة الهدف، التي تعتمد قيمتها على كل من القرار المتخذ $x$ وتحقق المتجه العشوائي $\xi$.
• $\mathbb{𝔼}[\cdot ]$ — عامل القيمة المتوقعة، والذي يتم حسابه وفقًا للتوزيع الاحتمالي للمتجه $\xi$.

من أهم المبادئ التي تقوم عليها النماذج التصادفية متعددة المراحل هو مبدأ عدم التوقع (بالإنجليزية: non-anticipativity principle). ينص هذا المبدأ على أن القرارات المتخذة في أي مرحلة يمكن أن تعتمد فقط على المعلومات المتاحة حتى تلك اللحظة، ولا يمكنها «استبصار المستقبل».

Two-stage stochastic program with recourse - مسألة المرحلتين مع حق التعويض

النموذج الأكثر شيوعًا هو مسألة المرحلتين مع حق التعويض (بالإنجليزية: two-stage stochastic program with recourse). تنقسم عملية اتخاذ القرار إلى مرحلتين:

1. المرحلة الأولى: يتم اتخاذ قرار «هنا والآن» (here-and-now) — بتحديد المتجه $x$. يجب اتخاذ هذا القرار قبل معرفة التحقق المحدد للمتجه العشوائي $\xi$.
2. المرحلة الثانية: بعد وقوع الحدث العشوائي، يتم اتخاذ قرار تصحيحي أو تعويضي (recourse decision) — المتجه $y(\xi )$، يهدف إلى تقليل العواقب السلبية أو استغلال الفرص المواتية التي نشأت نتيجة للجمع بين قرار المرحلة الأولى $x$ ونتيجة $\xi$.

رياضيًا، تصاغ مسألة البرمجة الخطية التصادفية ذات المرحلتين على النحو التالي: $\underset{x\in {\mathbb{ℝ}}^{n_1}}{\min }\{c^{T}x+{\mathbb{𝔼}}_{\xi }[Q(x,\xi )]\}$ مع مراعاة قيود المرحلة الأولى: $Ax=b,x\ge 0$. هنا $Q(x,\xi )$ هي دالة التعويض (recourse function)، والتي تمثل القيمة المثلى لمسألة المرحلة الثانية: $Q(x,\xi )=\underset{y\in {\mathbb{ℝ}}^{n_2}}{\min }\{q(\xi {)}^{T}y\mid T(\xi )x+Wy=h(\xi ),y\ge 0\}$ حيث $\xi$ هو متجه عشوائي يشمل المعلمات $q(\xi ),T(\xi )$ و $h(\xi )$؛ بينما $c,A,b$ و $W$ هي معلمات حتمية.

الخصائص والنظريات الرئيسية

• المحدّبية (Convexity): من النتائج الأساسية في هذه النظرية أن دالة التعويض المتوقعة $Q(x)={\mathbb{𝔼}}_{\xi }[Q(x,\xi )]$ في مسألة البرمجة الخطية التصادفية ذات المرحلتين هي دالة محدبة. لهذه الخاصية أهمية كبيرة لأنها تضمن أن مسألة المرحلة الأولى الإجمالية هي مسألة برمجة محدبة، والتي توجد لها طرق حل فعالة ويتطابق فيها الحل الأمثل العام مع الحل الأمثل المحلي.
• المكافئ الحتمي (Deterministic equivalent): إذا كان للمتجه العشوائي $\xi$ عدد محدود من التحققات الممكنة (السيناريوهات) ${\xi }_1,\dots ,{\xi }_K$ باحتمالات $p_1,\dots ,p_K$، فيمكن إعادة صياغة مسألة البرمجة التصادفية في شكل مسألة أمثلية حتمية واحدة كبيرة. في هذه الحالة، يتم استبدال القيمة المتوقعة بمجموع مرجح لجميع السيناريوهات. ومع ذلك، يزداد حجم هذه المسألة خطيًا مع عدد السيناريوهات، مما يؤدي إلى «لعنة الأبعاد» ويجعل هذا النهج غير قابل للحل حسابيًا لعدد كبير من السيناريوهات.

Comparison with robust optimization - المقارنة مع الأمثلية المتينة

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

مقارنة بين مناهج الأمثلية في ظل عدم اليقين

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

أمثلة

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

انظر أيضًا

• البرمجة الرياضية
• بحوث العمليات
• الأمثلية المتينة
• البرمجة الديناميكية
• نظرية التحكم