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

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

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

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

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

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

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

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

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

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

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

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

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

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

فرض التوزيع

صياغه مشاكل المرحلتين التي تم شرحها مسبقا تفترض ان المعلومات الخاصة بالمرحلة الثانية يمكن وصفها علي انها متجه عشوائي ذات توزيع احتمالى معلوم . على سبيل المثال ${\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 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 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 }$ تشمل ${\displaystyle d}$ عناصر عشوائيه مستقله، كل منها له ثلاث حالات ممكنه لذلك يكون عدد السيناريوهات ${\displaystyle K=3^{d}}$ .النموالطبيعى لعدد السيناريوهات يجعل تحسين النماذج بالاستناد الي رأي خبير صعب للغايه .

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

تستخدم طريقه مونت كارلو لتقليل السيناريوهات لحجم معقول. بفرض ان العدد السيناريوهات كبير جدا أو حتي لا نهائي و بفرض ايضا اننا نستطيع استخراج عينات ${\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 \xi ^{1},\dots ,\xi ^{N}}$ لعدد ${\displaystyle N}$ حلول للمتجه العشوائي ${\displaystyle \xi }$ . العينة العشوائيه من الممكن ان توصف علي انها معطيات سابقه لعدد ${\displaystyle N}$ ملاحظات ل${\displaystyle \xi }$ أو يمكن استنباطها بطريقه مونت كارلو ويمكن صياغه تقريب متوسط العينة كالأتي :

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

بفرض ان مجموعه ${\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 }$

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

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

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

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

مراجع

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. Chichester: John Wiley & Sons, Ltd. صفحات xii+307.  . MR = 1315300 1315300. مؤرشف من الأصل في 20 مارس 2012.
• 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 ). 9. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). Mathematical Programming Society (MPS). صفحات xvi+436.  . MR = 2562798 2562798. مؤرشف من الأصل ( كتاب إلكتروني PDF ) في 29 مارس 2017.
• 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. New York: Springer.  . مؤرشف من الأصل في 04 أكتوبر 2014.

موسوعات ذات صلة :

• موسوعة علم الحاسوب