برمجة عشوائية

صياغه مشاكل المرحلتين التي تم شرحها مسبقا تفترض ان المعلومات الخاصة بالمرحلة الثانية يمكن وصفها علي انها متجه عشوائي ذات توزيع احتمالى معلوم . على سبيل المثال ${\displaystyle \xi }$ من الممكن ان يكون معلومات تم الوصول اليها عن طريق معلومات مسبقه مع العلم ان التوزيع لم يتغيرمع طول الفترة الزمنيه . في مثل هذه الحالات من الممكن حساب التوزيع الاحتمالي المطلوب والقيام بالنمذجة و يمكن ان تفسر بأستخدام قانون الارقام الكبيرة.

لحل مشاكل النمذجة العشوائيه ذات المرحلتين عددياً , نحتاج غالبا لفرض ان المتجه العشوائي يحتوي على عدد من الحالات الممكنه المسماة بسيناريوهات حيث ان ${\displaystyle \xi _{1},\dots ,\xi _{K}}$ مناظره للاحتمالات ${\displaystyle p_{1},\dots ,p_{K}}$ و بذلك ممكن ان تصاغ داله الهدف(Objective function) الاتي :

${\displaystyle E[Q(x,\xi )]=\sum \limits _{k=1}^{K}p_{k}Q(x,\xi _{k})}$

و بالمثل مشاكل المرحلة الثانية ممكن ان تصاغ كمشكله برمجه خطيه كبيرة (وهذا ما يطلق عليه التحديد المكافئ للمشكله العشوائيه).

بأستخدام عدد محدود من السيناريوهات، يمكن وصف مشاكل البرمجة الخطية العشوائيه ذات المرحلتين علي انها مشاكل برمجه خطيه كبيرة. هذه الصيغة غالبا ما يطلق عليها التحديد المكافئ للمشكله العشوائيه . التحديد المكافئ هو اي عمليه حسابيه يمكن ان تستخدم لحساب الحل الامثل للمرحله الاولى. على سبيل المثال نجعل الاحتماليه ${\displaystyle p_{k}}$ لكل سيناريو حيث ${\displaystyle k=1,\dots ,K}$ ثم نقوم بتقليل القيمة المتوقعه للهدف كالأتي

${\displaystyle {\begin{array}{lccccccccccccc}{\text{Minimize}}&f^{T}x&+&g^{T}y&+&p_{1}h_{1}^{T}z_{1}&+&p_{2}h_{2}^{T}z_{2}&+&\cdots &+&p_{K}h_{K}^{T}z_{K}&&\\{\text{subject to}}&Tx&+&Uy&&&&&&&&&=&r\\&&&V_{1}y&+&W_{1}z_{1}&&&&&&&=&s_{1}\\&&&V_{2}y&&&+&W_{2}z_{2}&&&&&=&s_{2}\\&&&\vdots &&&&&&\ddots &&&&\vdots \\&&&V_{K}y&&&&&&&+&W_{K}z_{K}&=&s_{K}\\&x&,&y&,&z_{1}&,&z_{2}&,&\ldots &,&z_{K}&\geq &0\\\end{array}}}$

لكل سيناريو ${\displaystyle k}$ يوجد متجه ${\displaystyle z_{k}}$ مختلف و المتغيرات ${\displaystyle x}$ و ${\displaystyle y}$ لا تتغير من سيناريو لاخر.

تستخدم طريقه مونت كارلو لتقليل السيناريوهات لحجم معقول. بفرض ان العدد السيناريوهات كبير جدا أو حتي لا نهائي و بفرض ايضا اننا نستطيع استخراج عينات ${\displaystyle \xi ^{1},\xi ^{2},\dots ,\xi ^{N}}$ لعدد ${\displaystyle N}$ من التكرارات للمتجه العشوائي ${\displaystyle \xi }$

${\displaystyle {\hat {q}}_{N}(x)={\frac {1}{N}}\sum _{j=1}^{N}Q(x,\xi ^{j})}$

حيث ان المشكله ذات المرحلة الاولي تصاغ كالأتي

${\displaystyle {\begin{array}{rlrrr}{\hat {g}}_{N}(x)=&\min \limits _{x\in \mathbb {R} ^{n}}&c^{T}x+{\frac {1}{N}}\sum _{j=1}^{N}Q(x,\xi ^{j})&\\&{\text{subject to}}&Ax&=&b\\&&x&\geq &0\end{array}}}$

و تعرف هذه الصيغة بتقريب متوسط العينة

بفرض ان مجموعه ${\displaystyle X}$ من مشاكل تقريب متوسط العينة ثابته، بمعنى ان تكون مستقله عن العينة . وبجعل ${\displaystyle \vartheta ^{*}}$ و ${\displaystyle S^{*}}$ القيمة الامثل و المجموعه الامثل للحلول بالترتيب.

1. بفرض ان ${\displaystyle g:X\rightarrow \mathbb {R} }$ هو تسلسل القيم الحقيقيه للدوال
2. إذا كان الـ objective الخاص بـ تقريب متوسط العينة ${\displaystyle {\hat {g}}_{N}(x)}$ يتقارب مع objective المشكله الحقيقيه حيث تكون الاحتماليه = 1 ${\displaystyle N\rightarrow \infty }$
3. • بفرض ان :
   • المجموعه ${\displaystyle S}$ من الحلول الامثل للمشاكل الحقيقيه واردة في ال${\displaystyle C}$
   • الدالة${\displaystyle g(x)}$ محدودة القيمة و متصله عند الـ ${\displaystyle C}$
   • المتسلسله الخاصة بالدالة ${\displaystyle {\hat {g}}_{N}(x)}$ تقترب من الـ ${\displaystyle g(x)}$ ان تكون الاحتماليه 1 لكل ${\displaystyle N\rightarrow \infty }$