Stochastic programming

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

لحل مشكلة الاحتمالات ذات المرحلتين عدديًا، غالبًا ما يحتاج المرء إلى افتراض أن المتجه العشوائي${\displaystyle \xi }$يحتوي على عدد محدود من الاحتمالات الممكنة، والتي تسمى سيناريوهات ، على سبيل المثال${\displaystyle \xi _{1},\dots ,\xi _{K}}$، مع كتل الاحتمالية الخاصة بها${\displaystyle p_{1},\dots ,p_{K}}$ثم يمكن كتابة القيمة المتوقعة في دالة الهدف لمسألة المرحلة الأولى على شكل مجموع: $${\displaystyle E[Q(x,\xi )]=\sum \limits _{k=1}^{K}p_{k}Q(x,\xi _{k})}$$ وعلاوة على ذلك، يمكن صياغة المشكلة ذات المرحلتين كمشكلة برمجة خطية كبيرة واحدة (يسمى هذا المكافئ الحتمي للمشكلة الأصلية، انظر القسم §  المكافئ الحتمي للمشكلة العشوائية ).

متى${\displaystyle \xi }$بما أن التوزيع له عدد لا نهائي (أو كبير جدًا) من الاحتمالات الممكنة، فإن النهج القياسي هو تمثيل هذا التوزيع من خلال سيناريوهات. يثير هذا النهج ثلاثة أسئلة، وهي:

1. كيفية بناء السيناريوهات، انظر §  بناء السيناريو ؛
2. كيفية حل المكافئ الحتمي. يمكن لبرامج التحسين مثل CPLEX و GLPK حل المسائل الخطية/غير الخطية الكبيرة. يتيح خادم NEOS ^{[ 6 ]} ، المُستضاف في جامعة ويسكونسن، ماديسون ، الوصول المجاني إلى العديد من برامج الحل الحديثة. يُعد هيكل المكافئ الحتمي مناسبًا بشكل خاص لتطبيق أساليب التفكيك ^{[ 7 ]،} مثل تفكيك بيندرز أو تفكيك السيناريو.
3. كيفية قياس جودة الحل الذي تم الحصول عليه بالنسبة إلى الحل الأمثل "الحقيقي".

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

البرنامج الخطي العشوائي هو حالة خاصة من البرنامج العشوائي الكلاسيكي ذي المرحلتين. يُبنى البرنامج الخطي العشوائي من مجموعة من البرامج الخطية متعددة الفترات، لكل منها نفس البنية ولكن ببيانات مختلفة نوعًا ما.${\displaystyle k^{th}}$يمثل LP ذو الفترتين${\displaystyle k^{th}}$يمكن اعتبار السيناريو على النحو التالي:

${\displaystyle {\begin{array}{lccccccc}{\text{Minimize}}&f^{T}x&+&g^{T}y&+&h_{k}^{T}z_{k}&&\\{\text{subject to}}&Tx&+&Uy&&&=&r\\&&&V_{k}y&+&W_{k}z_{k}&=&s_{k}\\&x&,&y&,&z_{k}&\geq &0\end{array}}}$

المتجهات${\displaystyle x}$و${\displaystyle y}$تحتوي على متغيرات الفترة الأولى، والتي يجب اختيار قيمها فورًا. المتجه${\displaystyle z_{k}}$يحتوي على جميع المتغيرات للفترات اللاحقة. القيود${\displaystyle Tx+Uy=r}$تتضمن هذه القيود متغيرات الفترة الأولى فقط، وهي نفسها في جميع السيناريوهات. أما القيود الأخرى فتتضمن متغيرات فترات لاحقة، وتختلف في بعض الجوانب من سيناريو لآخر، مما يعكس حالة عدم اليقين بشأن المستقبل.

لاحظ أن حل${\displaystyle k^{th}}$يُعادل نموذج البرمجة الخطية ذو الفترتين افتراض${\displaystyle k^{th}}$سيناريو في الفترة الثانية بدون أي غموض. ولإدراج حالات عدم اليقين في المرحلة الثانية، ينبغي تحديد احتمالات للسيناريوهات المختلفة وحل المكافئ الحتمي المقابل لها.

عمليًا، قد يكون من الممكن بناء سيناريوهات من خلال استطلاع آراء الخبراء حول المستقبل. ينبغي أن يكون عدد السيناريوهات المبنية محدودًا نسبيًا حتى يمكن حل المكافئ الحتمي الناتج بجهد حسابي معقول. يُزعم غالبًا أن الحل الأمثل الذي يستخدم عددًا قليلًا من السيناريوهات يوفر خططًا أكثر مرونة من الحل الذي يفترض سيناريو واحدًا فقط. في بعض الحالات، يمكن التحقق من هذا الزعم عن طريق المحاكاة. نظريًا، تضمن بعض المقاييس أن الحل المُستنتج يحل المشكلة الأصلية بدقة معقولة. عادةً في التطبيقات، يكون الحل الأمثل هو حل المرحلة الأولى فقط.${\displaystyle x^{*}}$لها قيمة عملية لأنه في أغلب الأحيان يكون التحقيق "الحقيقي" للبيانات العشوائية مختلفًا عن مجموعة السيناريوهات التي تم إنشاؤها (توليدها).

يفترض${\displaystyle \xi }$يتضمن${\displaystyle d}$إذا كانت لدينا مكونات عشوائية مستقلة، لكل منها ثلاثة احتمالات (على سبيل المثال، يتم تصنيف الاحتمالات المستقبلية لكل معلمة عشوائية على أنها منخفضة ومتوسطة وعالية)، فإن العدد الإجمالي للسيناريوهات هو${\displaystyle K=3^{d}}$إن هذا النمو الهائل في عدد السيناريوهات يجعل تطوير النماذج باستخدام آراء الخبراء أمراً بالغ الصعوبة حتى بالنسبة للأحجام المعقولة.${\displaystyle d}$ويزداد الوضع سوءًا إذا كانت بعض المكونات العشوائية من${\displaystyle \xi }$لها توزيعات متصلة.

ضع في اعتبارك مسألة البرمجة العشوائية التالية

${\displaystyle \min \limits _{x\in X}\{g(x)=f(x)+E[Q(x,\xi )]\}}$

هنا${\displaystyle X}$هي مجموعة فرعية مغلقة غير فارغة من${\displaystyle \mathbb {R} ^{n}}$،${\displaystyle \xi }$هو متجه عشوائي توزيع احتمالاته${\displaystyle P}$مدعوم على مجموعة${\displaystyle \Xi \subset \mathbb {R} ^{d}}$، و${\displaystyle Q:X\times \Xi \rightarrow \mathbb {R} }$في إطار البرمجة العشوائية ذات المرحلتين،${\displaystyle Q(x,\xi )}$يتم تحديدها من خلال القيمة المثلى لمسألة المرحلة الثانية المقابلة.

افترض أن${\displaystyle g(x)}$محددة جيدًا وذات قيمة محدودة لجميع${\displaystyle x\in X}$وهذا يعني أنه لكل${\displaystyle x\in X}$القيمة${\displaystyle Q(x,\xi )}$هو محدود بشكل شبه مؤكد .

لنفترض أن لدينا عينة${\displaystyle \xi ^{1},\dots ,\xi ^{N}}$ل${\displaystyle N}$تحققات المتجه العشوائي${\displaystyle \xi }$يمكن اعتبار هذه العينة العشوائية بمثابة بيانات تاريخية لـ${\displaystyle N}$ملاحظات حول${\displaystyle \xi }$أو يمكن توليدها باستخدام تقنيات أخذ العينات مونت كارلو. عندئذٍ يمكننا صياغة تقريب متوسط ​​العينة المقابل.

${\displaystyle \min \limits _{x\in X}\{{\hat {g}}_{N}(x)=f(x)+{\frac {1}{N}}\sum _{j=1}^{N}Q(x,\xi ^{j})\}}$

بحسب قانون الأعداد الكبيرة ، لدينا أنه في ظل بعض شروط الانتظام${\displaystyle {\frac {1}{N}}\sum _{j=1}^{N}Q(x,\xi ^{j})}$يتقارب نقطيًا باحتمالية 1 إلى${\displaystyle E[Q(x,\xi )]}$مثل${\displaystyle N\rightarrow \infty }$علاوة على ذلك، في ظل شروط إضافية بسيطة، يكون التقارب منتظمًا. لدينا أيضًا${\displaystyle E[{\hat {g}}_{N}(x)]=g(x)}$، أي،${\displaystyle {\hat {g}}_{N}(x)}$هو مُقدِّر غير متحيز لـ${\displaystyle g(x)}$لذلك، من الطبيعي أن نتوقع أن تتقارب القيمة المثلى والحلول المثلى لمسألة SAA مع نظيراتها في المسألة الحقيقية عندما${\displaystyle N\rightarrow \infty }$.

اتساق مقدرات SAA

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

1. يترك${\displaystyle g:X\rightarrow \mathbb {R} }$و${\displaystyle {\hat {g}}_{N}:X\rightarrow \mathbb {R} }$لتكن متتالية من الدوال الحقيقية (الحتمية). الخاصيتان التاليتان متكافئتان:
   • لأي${\displaystyle {\overline {x}}\in X}$وأي تسلسل${\displaystyle \{x_{N}\}\subset X}$يتقارب إلى${\displaystyle {\overline {x}}}$ويترتب على ذلك أن${\displaystyle {\hat {g}}_{N}(x_{N})}$يتقارب إلى${\displaystyle g({\overline {x}})}$
   • الوظيفة${\displaystyle g(\cdot )}$مستمر على${\displaystyle X}$و${\displaystyle {\hat {g}}_{N}(\cdot )}$يتقارب إلى${\displaystyle g(\cdot )}$بشكل منتظم على أي مجموعة فرعية مضغوطة من${\displaystyle X}$
2. إذا كان هدف مشكلة SAA${\displaystyle {\hat {g}}_{N}(x)}$يتقارب مع هدف المشكلة الحقيقية${\displaystyle g(x)}$باحتمالية 1، كما${\displaystyle N\rightarrow \infty }$، بشكل منتظم على المجموعة الممكنة${\displaystyle X}$. ثم${\displaystyle {\hat {\vartheta }}_{N}}$يتقارب إلى${\displaystyle \vartheta ^{*}}$باحتمالية 1${\displaystyle N\rightarrow \infty }$.
3. لنفترض أن هناك مجموعة مضغوطة${\displaystyle C\subset \mathbb {R} ^{n}}$بحيث
   • المجموعة${\displaystyle S}$مجموعة الحلول المثلى للمسألة الحقيقية غير فارغة ومحتواة في${\displaystyle C}$
   • الوظيفة${\displaystyle g(x)}$دالة ذات قيم محدودة ومتصلة على${\displaystyle C}$
   • تسلسل الوظائف${\displaystyle {\hat {g}}_{N}(x)}$يتقارب إلى${\displaystyle g(x)}$باحتمالية 1، كما${\displaystyle N\rightarrow \infty }$، بشكل موحد في${\displaystyle x\in C}$
   • ل${\displaystyle N}$كبيرة بما يكفي للمجموعة${\displaystyle {\hat {S}}_{N}}$غير فارغ و${\displaystyle {\hat {S}}_{N}\subset C}$باحتمالية 1

ثم${\displaystyle {\hat {\vartheta }}_{N}\rightarrow \vartheta ^{*}}$و${\displaystyle \mathbb {D} (S^{*},{\hat {S}}_{N})\rightarrow 0}$باحتمالية 1${\displaystyle N\rightarrow \infty }$. لاحظ أن${\displaystyle \mathbb {D} (A,B)}$يشير إلى انحراف المجموعة${\displaystyle A}$من المجموعة${\displaystyle B}$، كما هو مُعرَّف

${\displaystyle \mathbb {D} (A,B):=\sup _{x\in A}\{\inf _{x'\in B}\|x-x'\|\}}$

في بعض الحالات، تكون المجموعة الممكنة${\displaystyle X}$إذا تم تقدير مسألة SAA، فإن مسألة SAA المقابلة تأخذ الشكل التالي

${\displaystyle \min _{x\in X_{N}}{\hat {g}}_{N}(x)}$

أين${\displaystyle X_{N}}$هي مجموعة فرعية من${\displaystyle \mathbb {R} ^{n}}$يعتمد ذلك على العينة، وبالتالي فهو عشوائي. ومع ذلك، لا يزال من الممكن استخلاص نتائج الاتساق لمُقدِّرات SAA في ظل بعض الافتراضات الإضافية:

1. لنفترض أن هناك مجموعة مضغوطة${\displaystyle C\subset \mathbb {R} ^{n}}$بحيث
   • المجموعة${\displaystyle S}$مجموعة الحلول المثلى للمسألة الحقيقية غير فارغة ومحتواة في${\displaystyle C}$
   • الوظيفة${\displaystyle g(x)}$دالة ذات قيم محدودة ومتصلة على${\displaystyle C}$
   • تسلسل الوظائف${\displaystyle {\hat {g}}_{N}(x)}$يتقارب إلى${\displaystyle g(x)}$باحتمالية 1، كما${\displaystyle N\rightarrow \infty }$، بشكل موحد في${\displaystyle x\in C}$
   • ل${\displaystyle N}$كبيرة بما يكفي للمجموعة${\displaystyle {\hat {S}}_{N}}$غير فارغ و${\displaystyle {\hat {S}}_{N}\subset C}$باحتمالية 1
   • لو${\displaystyle x_{N}\in X_{N}}$و${\displaystyle x_{N}}$يتقارب باحتمالية 1 إلى نقطة${\displaystyle x}$، ثم${\displaystyle x\in X}$
   • إلى حد ما${\displaystyle x\in S^{*}}$يوجد تسلسل${\displaystyle x_{N}\in X_{N}}$بحيث${\displaystyle x_{N}\rightarrow x}$باحتمالية 1.

ثم${\displaystyle {\hat {\vartheta }}_{N}\rightarrow \vartheta ^{*}}$و${\displaystyle \mathbb {D} (S^{*},{\hat {S}}_{N})\rightarrow 0}$باحتمالية 1${\displaystyle N\rightarrow \infty }$.

السلوك التقاربي للقيمة المثلى لـ SAA

لنفترض العينة${\displaystyle \xi ^{1},\dots ,\xi ^{N}}$هي مستقلة ومتطابقة التوزيع، وحدد نقطة${\displaystyle x\in X}$ثم مقدر متوسط ​​العينة${\displaystyle {\hat {g}}_{N}(x)}$، ل${\displaystyle g(x)}$، وهو غير متحيز وله تباين${\displaystyle {\frac {1}{N}}\sigma ^{2}(x)}$، أين${\displaystyle \sigma ^{2}(x):=Var[Q(x,\xi )]}$من المفترض أن تكون محدودة. علاوة على ذلك، وبحسب نظرية النهاية المركزية، لدينا أن

${\displaystyle {\sqrt {N}}[{\hat {g}}_{N}-g(x)]{\xrightarrow {\mathcal {D}}}Y_{x}}$

أين${\displaystyle {\xrightarrow {\mathcal {D}}}}$يشير إلى التقارب في التوزيع و${\displaystyle Y_{x}}$يتبع التوزيع الطبيعي بمتوسط${\displaystyle 0}$والتباين${\displaystyle \sigma ^{2}(x)}$، مكتوبة على النحو التالي${\displaystyle {\mathcal {N}}(0,\sigma ^{2}(x))}$.

بعبارة أخرى،${\displaystyle {\hat {g}}_{N}(x)}$له توزيع طبيعي تقاربياً ، أي بالنسبة للقيم الكبيرة${\displaystyle N}$،${\displaystyle {\hat {g}}_{N}(x)}$يتبع توزيعًا طبيعيًا تقريبًا بمتوسط${\displaystyle g(x)}$والتباين${\displaystyle {\frac {1}{N}}\sigma ^{2}(x)}$وهذا يؤدي إلى ما يلي (تقريبًا)${\displaystyle 100(1-\alpha )}$النسبة المئوية لفترة الثقة لـ${\displaystyle f(x)}$:

${\displaystyle \left[{\hat {g}}_{N}(x)-z_{\alpha /2}{\frac {{\hat {\sigma }}(x)}{\sqrt {N}}},{\hat {g}}_{N}(x)+z_{\alpha /2}{\frac {{\hat {\sigma }}(x)}{\sqrt {N}}}\right]}$

أين${\displaystyle z_{\alpha /2}:=\Phi ^{-1}(1-\alpha /2)}$(هنا${\displaystyle \Phi (\cdot )}$(يشير إلى دالة التوزيع التراكمي للتوزيع الطبيعي القياسي) و

${\displaystyle {\hat {\sigma }}^{2}(x):={\frac {1}{N-1}}\sum _{j=1}^{N}\left[Q(x,\xi ^{j})-{\frac {1}{N}}\sum _{j=1}^{N}Q(x,\xi ^{j})\right]^{2}}$

هو تقدير تباين العينة لـ${\displaystyle \sigma ^{2}(x)}$أي أن خطأ تقدير${\displaystyle g(x)}$هو (احتماليًا) من الرتبة${\displaystyle O({\sqrt {N}})}$.

تُستخدم البرمجة الديناميكية العشوائية بكثرة لنمذجة سلوك الحيوانات في مجالات مثل علم البيئة السلوكي . ^{[ 8 ] [ 9 ]} وقد أظهرت الاختبارات التجريبية لنماذج البحث الأمثل عن الغذاء ، ومراحل التحول في دورة حياة الحيوانات مثل مرحلة الترييش لدى الطيور ووضع البيض لدى الدبابير الطفيلية ، أهمية هذه التقنية في تفسير تطور عملية اتخاذ القرارات السلوكية. وعادةً ما تكون هذه النماذج متعددة المراحل، وليست ثنائية المراحل.

تُعدّ البرمجة الديناميكية العشوائية أداةً مفيدةً لفهم عملية اتخاذ القرارات في ظلّ عدم اليقين. ويُعدّ تراكم رأس المال في ظلّ عدم اليقين مثالاً على ذلك؛ إذ يستخدمها خبراء اقتصاديات الموارد غالبًا لتحليل المشكلات الاقتصادية الحيوية ^{[ 10 ]} التي يدخل فيها عدم اليقين، مثل تقلبات الطقس، وما إلى ذلك.

فيما يلي مثال من مجال التمويل على البرمجة العشوائية متعددة المراحل. لنفترض أنه في الوقت${\displaystyle t=0}$لدينا رأس مال أولي${\displaystyle W_{0}}$للاستثمار في${\displaystyle n}$الأصول. لنفترض كذلك أنه يُسمح لنا بإعادة توازن محفظتنا في أوقات${\displaystyle t=1,\dots ,T-1}$ولكن دون ضخ أموال إضافية فيه. في كل فترة${\displaystyle t}$نتخذ قراراً بشأن إعادة توزيع الثروة الحالية${\displaystyle W_{t}}$من بين${\displaystyle n}$الأصول. دع${\displaystyle x_{0}=(x_{10},\dots ,x_{n0})}$لنفترض أن المبالغ الأولية المستثمرة في الأصول n هي. نشترط أن يكون كل${\displaystyle x_{i0}}$وهي غير سالبة وأن معادلة التوازن${\displaystyle \sum _{i=1}^{n}x_{i0}=W_{0}}$ينبغي أن يستمر.

ضع في اعتبارك إجمالي العوائد${\displaystyle \xi _{t}=(\xi _{1t},\dots ,\xi _{nt})}$لكل فترة${\displaystyle t=1,\dots ,T}$يشكل هذا عملية عشوائية ذات قيم متجهة${\displaystyle \xi _{1},\dots ,\xi _{T}}$في فترة زمنية${\displaystyle t=1}$يمكننا إعادة توازن المحفظة عن طريق تحديد المبالغ${\displaystyle x_{1}=(x_{11},\dots ,x_{n1})}$تم استثمارها في الأصول المعنية. في ذلك الوقت، تكون العوائد في الفترة الأولى قد تحققت، لذا من المعقول استخدام هذه المعلومات في قرار إعادة التوازن. وبالتالي، فإن قرارات المرحلة الثانية، في ذلك الوقت${\displaystyle t=1}$، هي في الواقع دوال لتحقيق المتجه العشوائي${\displaystyle \xi _{1}}$، أي،${\displaystyle x_{1}=x_{1}(\xi _{1})}$وبالمثل، في وقت${\displaystyle t}$القرار${\displaystyle x_{t}=(x_{1t},\dots ,x_{nt})}$هي دالة${\displaystyle x_{t}=x_{t}(\xi _{[t]})}$من المعلومات المتاحة المقدمة من${\displaystyle \xi _{[t]}=(\xi _{1},\dots ,\xi _{t})}$تاريخ العملية العشوائية حتى وقت${\displaystyle t}$سلسلة من الوظائف${\displaystyle x_{t}=x_{t}(\xi _{[t]})}$،${\displaystyle t=0,\dots ,T-1}$، مع${\displaystyle x_{0}}$يُحدد ثبات هذه الخاصية سياسة قابلة للتنفيذ في عملية اتخاذ القرار. ويُقال إن هذه السياسة قابلة للتطبيق إذا استوفت قيود النموذج باحتمالية 1، أي قيود عدم السلبية.${\displaystyle x_{it}(\xi _{[t]})\geq 0}$،${\displaystyle i=1,\dots ,n}$،${\displaystyle t=0,\dots ,T-1}$وتوازن قيود الثروة،

${\displaystyle \sum _{i=1}^{n}x_{it}(\xi _{[t]})=W_{t},}$

أين في الفترة${\displaystyle t=1,\dots ,T}$الثروة${\displaystyle W_{t}}$يُعطى بواسطة

${\displaystyle W_{t}=\sum _{i=1}^{n}\xi _{it}x_{i,t-1}(\xi _{[t-1]}),}$

والذي يعتمد على تحقق العملية العشوائية والقرارات المتخذة حتى وقت معين${\displaystyle t}$.

لنفترض أن الهدف هو تعظيم المنفعة المتوقعة لهذه الثروة في الفترة الأخيرة، أي النظر في المشكلة

${\displaystyle \max E[U(W_{T})].}$

هذه مسألة برمجة عشوائية متعددة المراحل، حيث يتم ترقيم المراحل من${\displaystyle t=0}$ل${\displaystyle t=T-1}$تُجرى عملية التحسين على جميع السياسات القابلة للتنفيذ والممكنة. ولإكمال وصف المشكلة، يلزم أيضًا تحديد التوزيع الاحتمالي للعملية العشوائية.${\displaystyle \xi _{1},\dots ,\xi _{T}}$يمكن القيام بذلك بطرق مختلفة. على سبيل المثال، يمكن إنشاء شجرة سيناريوهات محددة تُعرّف التطور الزمني للعملية. إذا سُمح في كل مرحلة للعائد العشوائي لكل أصل بأن يكون له استمراران، مستقلان عن الأصول الأخرى، فإن العدد الإجمالي للسيناريوهات هو${\displaystyle 2^{nT}.}$

لكتابة معادلات البرمجة الديناميكية ، يجب النظر إلى المسألة متعددة المراحل المذكورة أعلاه بشكل عكسي في الزمن. في المرحلة الأخيرة${\displaystyle t=T-1}$، إدراك${\displaystyle \xi _{[T-1]}=(\xi _{1},\dots ,\xi _{T-1})}$إن طبيعة العملية العشوائية معروفة و${\displaystyle x_{T-2}}$تم اختيارها. لذلك، يجب حل المشكلة التالية

${\displaystyle {\begin{array}{lrclr}\max \limits _{x_{T-1}}&E[U(W_{T})|\xi _{[T-1]}]&\\{\text{subject to}}&W_{T}&=&\sum _{i=1}^{n}\xi _{iT}x_{i,T-1}\\&\sum _{i=1}^{n}x_{i,T-1}&=&W_{T-1}\\&x_{T-1}&\geq &0\end{array}}}$

أين${\displaystyle E[U(W_{T})|\xi _{[T-1]}]}$يشير إلى التوقع الشرطي لـ${\displaystyle U(W_{T})}$منح${\displaystyle \xi _{[T-1]}}$تعتمد القيمة المثلى للمسألة المذكورة أعلاه على${\displaystyle W_{T-1}}$و${\displaystyle \xi _{[T-1]}}$ويُشار إليه بـ${\displaystyle Q_{T-1}(W_{T-1},\xi _{[T-1]})}$.

وبالمثل، في المراحل${\displaystyle t=T-2,\dots ,1}$ينبغي على المرء حل المشكلة

${\displaystyle {\begin{array}{lrclr}\max \limits _{x_{t}}&E[Q_{t+1}(W_{t+1},\xi _{[t+1]})|\xi _{[t]}]&\\{\text{subject to}}&W_{t+1}&=&\sum _{i=1}^{n}\xi _{i,t+1}x_{i,t}\\&\sum _{i=1}^{n}x_{i,t}&=&W_{t}\\&x_{t}&\geq &0\end{array}}}$

والتي يُرمز إلى قيمتها المثلى بـ${\displaystyle Q_{t}(W_{t},\xi _{[t]})}$وأخيرًا، في المرحلة${\displaystyle t=0}$، يحل المرء المشكلة

${\displaystyle {\begin{array}{lrclr}\max \limits _{x_{0}}&E[Q_{1}(W_{1},\xi _{[1]})]&\\{\text{subject to}}&W_{1}&=&\sum _{i=1}^{n}\xi _{i,1}x_{i0}\\&\sum _{i=1}^{n}x_{i0}&=&W_{0}\\&x_{0}&\geq &0\end{array}}}$

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

• AIMMS – يدعم تعريف مشاكل البرمجة الرياضية
• EMP SP (البرمجة الرياضية الموسعة للبرمجة العشوائية) - وحدة من GAMS تم إنشاؤها لتسهيل البرمجة العشوائية (تتضمن كلمات مفتاحية للتوزيعات البارامترية، وقيود الاحتمالات، ومقاييس المخاطر مثل القيمة المعرضة للخطر والعجز المتوقع ).
• SAMPL - مجموعة من الامتدادات لـ AMPL مصممة خصيصًا للتعبير عن البرامج العشوائية (تتضمن بناء الجملة لقيود الاحتمال، وقيود الاحتمال المتكاملة، ومسائل التحسين القوي ).

كلاهما قادر على إنشاء تنسيق على مستوى مثيل SMPS، والذي ينقل بشكل غير متكرر بنية المشكلة إلى المُحلِّل.