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

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

المشاكل ذات المرحلتين

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

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

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

حيث $Q(x,\xi )$ هي القيمة المثلى للمشكله ذات المرحلة الثانية

$\min _{y}\{q(y,\xi )|T(\xi )x+W(\xi )y=h(\xi )\}$

مشاكل البرمجة الخطية العشوائيه يمكن صياغتها كالاتي

${\begin{array}{llr}\min \limits _{x\in \mathbb {R} ^{n}}&g(x)=c^{T}x+E[Q(x,\xi )]&\\{\text{subject to}}&Ax=b&\\&x\geq 0&\end{array}}$

حيث $Q(x,\xi )$ هي القيمة المثلى للمشكله ذات المرحلة الثانية

${\begin{array}{llr}\min \limits _{y\in \mathbb {R} ^{m}}&q(\xi )^{T}y&\\{\text{subject to}}&T(\xi )x+W(\xi )y=h(\xi )&\\&y\geq 0&\end{array}}$

في هذه الصيغة $x\in \mathbb {R} ^{n}$ هو المتجه الخاص بمتغيرات القرار في المرحلة الاولي و $y\in \mathbb {R} ^{m}$ هو المتجه الخاص بـمتغيرات القرار في المرحلة الثانية. في هذه الصيغة ; في حاله المرحلة الاولي نكون بحاجه لأتخاذ قرار $x$ حالا قبل ادراك المعلومات الغير مؤكدة $\xi$. في المرحلة الثانية بعد ادراك $\xi$, نقوم بتحسين الاداء عن طريق حل المشكله المناسبة.

في الخطوة الاولي نقوم بأمثله الـ $c^{T}x$ الخاص ب المرحلة الاولي الي جانب الـ $c^{T}x$ الخاص بالمرحلة الثانية ووهذا يمكننا من عرض مشاكل المرحلة الثانية علي انها مشكله نمذجه حيث انها تقوم بوصف الحل الافتراضي الامثل في حاله ان تكون المعلومات غير مؤكدة.

فرض التوزيع

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

التقسيم

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

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

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

البرمجة العشوائيه الخطية

هي حاله خاصه بمشاكل المرحلتين الاعتياديه للبرمجة العشوائيه. البرمجة العشوائيه الخطية قائمه علي تجميع المشاكل الخطية ذات الفترات المتعددة كل منها له نفس البناء لكن بأختلاف بسيط في البيانات. البرمجة الخطية ذات الفترتين تقوم بعرض الـ$k^{th}$ سيناريو في الصيغة الاتيه:

${\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}}$

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

لاحظ ان حل مشاكل البرمجة الخطية للفترتين مكافئه لفرض الـ $k^{th}$ سيناريو في الفترة الثانية مع عدم التأكد.

التحديد المكافئ للمشكله العشوائيه

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

${\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}}$

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

بناء السيناريوهات

من الممكن بناء سيناريوهات عن طريق أراء خبير.يجب ان يكون عدد السيناريوهات معتدل ليكون من السهل حلها بمجهود اقل. غالبا ما يكون الحل الامثل القائم علي بعض السيناريوهات يوفر خطط احسن سيناريو واحد.

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

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

أخذ العينات بطريقه مونت كارلو

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

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

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

${\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}}$

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

الاستدلال الإحصائي

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

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

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

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

اتساق مقدرات تقريب متوسط العينة

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

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

التطبيقات البيولوجية

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

التطبيقات الاقتصاديه

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

مراجع

Stochastic programming

قراءات أخرى

• John R. Birge and François V. Louveaux. Introduction to Stochastic Programming. Springer Verlag, New York, 1997.
• Kall، Peter؛ Wallace، Stein W. (1994). Stochastic programming. Wiley-Interscience Series in Systems and Optimization. Chichester: John Wiley & Sons, Ltd. ص. xii+307. ISBN:0-471-95158-7. MR:1315300. مؤرشف من الأصل في 2012-03-20.
• G. Ch. Pflug: Optimization of Stochastic Models. The Interface between Simulation and Optimization. Kluwer, Dordrecht, 1996.
• Andras Prekopa. Stochastic Programming. Kluwer Academic Publishers, Dordrecht, 1995.
• Andrzej Ruszczynski and Alexander Shapiro (eds.) (2003) Stochastic Programming. Handbooks in Operations Research and Management Science, Vol. 10, Elsevier.
• Shapiro، Alexander؛ Dentcheva، Darinka؛ Ruszczyński، Andrzej (2009). Lectures on stochastic programming: Modeling and theory (PDF). MPS/SIAM Series on Optimization. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). Mathematical Programming Society (MPS). ج. 9. ص. xvi+436. ISBN:978-0-89871-687-0. MR:2562798. مؤرشف من الأصل (PDF) في 2017-03-29.
• Stein W. Wallace and William T. Ziemba (eds.) (2005) Applications of Stochastic Programming. MPS-SIAM Book Series on Optimization 5
• King، Alan J.؛ Wallace، Stein W. (2012). Modeling with Stochastic Programming. Springer Series in Operations Research and Financial Engineering. New York: Springer. ISBN:978-0-387-87816-4. مؤرشف من الأصل في 2014-10-04.