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

في مجال الاستمثال، تعتبر البرمجة العشوائية الهيكل الأساسي لحل المشاكل المتعلقة بالنمذجة القائمة على عدم التأكد. في حين أن مشاكل النمذجة المحددة تصاغ باستخدام بارامترات معلومة. وتشمل مشاكل الواقع بعض البارامترات غير المعلومة، في حال وقوع البارامترات ضمن حدود معينة تكون هناك طريقة واحدة لحل هذا النوع من المشاكل تسمى النمذجة القوية (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). ج. 9. ص. xvi+436. ISBN:978-0-89871-687-0. MR:2562798. مؤرشف من الأصل (PDF) في 2017-03-29. {{استشهاد بكتاب}}: الوسيط غير المعروف |agency= تم تجاهله (مساعدة)
• 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.