مرجع
آخر الزيارات

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

1٬035 كلمة•0 مشاهدة•🗒️ منذ يوم
باختصار: في مجال الاستمثال، تعتبر البرمجة العشوائية الهيكل الأساسي لحل المشاكل المتعلقة بالنمذجة القائمة على عدم التأكد. في هذه المقالة 16 قسماً: «الدالة محدودة القيمة ومتصلة عند الـ»، «التحديد المكافئ للمشكلة العشوائية» و«اتساق مقدرات تقريب متوسط العينة» وغيرها.
المحتويات
  1. الدالة محدودة القيمة ومتصلة عند الـ
  2. التحديد المكافئ للمشكلة العشوائية
  3. اتساق مقدرات تقريب متوسط العينة
  4. بناء السيناريوهات
  5. بفرض أن هو تسلسل القيم الحقيقية للدوال
  6. بفرض أن مشكلة البرمجة العشوائية تكون كالتالي
  7. التقسيم
  8. فرض التوزيع
  9. التطبيقات البيولوجية
  10. المشاكل ذات المرحلتين
  11. مشاكل البرمجة الخطية العشوائية يمكن صياغتها كالآتي
  12. أخذ العينات بطريقة مونت كارلو
  13. البرمجة العشوائية الخطية
  14. الصيغة العامة للمشاكل ذات المرحلتين توصف كالتالي
  15. التطبيقات الاقتصادية
  16. قراءات أخرى

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

الدالة محدودة القيمة ومتصلة عند الـ

ومن جهة أخرى، المتسلسلة الخاصة بالدالة تقترب من الـ أن تكون الاحتمالية 1 لكل

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

ومن ناحية أخرى، لكل سيناريو يوجد متجه مختلف والمتغيرات و لا تتغير من سيناريو لأخر.

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

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

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

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

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

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

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

بفرض أن هو تسلسل القيم الحقيقية للدوال

المجموعة من الحلول الأمثل للمشاكل الحقيقية واردة في ال

وعلى صعيد آخر، إذا كان الـ objective الخاص بـ تقريب متوسط العينة يتقارب مع objective المشكلة الحقيقية حيث تكون الاحتمالية = 1

• بفرض أن:

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

كذلك، بفرض أن هناك عينات لعدد حلول للمتجه العشوائي . العينة العشوائية من الممكن أن توصف على أنها معطيات سابقة لعدد ملاحظات ل أو يمكن استنباطها بطريقة مونت كارلو ويمكن صياغة تقريب متوسط العينة كالآتي:

التقسيم

كذلك، لحل مشاكل النمذجة العشوائية ذات المرحلتين عددياً، نحتاج غالبا لفرض أن المتجه العشوائي يحتوي على عدد من الحالات الممكنة المسماة بسيناريوهات حيث أن مناظره للاحتمالات وبذلك ممكن أن تصاغ دالة الهدف (Objective function) الآتي:

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

فرض التوزيع

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

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

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

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

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

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

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

من جانب آخر، في هذه الصيغة هو المتجه الخاص بمتغيرات القرار في المرحلة الأولى و هو المتجه الخاص بـمتغيرات القرار في المرحلة الثانية. في هذه الصيغة; في حاله المرحلة الاولي نكون بحاجه لاتخاذ قرار حالا قبل إدراك المعلومات غير المؤكدة . في المرحلة الثانية بعد إدراك , نقوم بتحسين الأداء عن طريق حل المشكلة المناسبة.

حيث هي القيمة المثلى للمشكلة ذات المرحلة الثانية

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

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

  • حيث أن المشكلة ذات المرحلة الأولى تصاغ كالآتي
  • و تعرف هذه الصيغة بتقريب متوسط العينة.
  • الاستدلال الإحصائي

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

وفي هذا السياق، هي حالة خاصة بمشاكل المرحلتين الاعتيادية للبرمجة العشوائية. البرمجة العشوائية الخطية قائمة على تجميع المشاكل الخطية ذات الفترات المتعددة كل منها له نفس البناء لكن باختلاف بسيط في البيانات. البرمجة الخطية ذات الفترتين تقوم بعرض الـ سيناريو في الصيغة الآتية:

وعلى صعيد آخر، المتجهين و يشملان متغيرات الفترة الاولي حيث انه يجب اختيار قيمتهم فورا. المتجه يحتوي على جميع المتغيرات للفترات التالية. القيود تشمل متغيرات الفترة الأولى ولا تتغير من سيناريو لأخر، القيود الخرى تتضمن متغيرات الفترات الأخرى وتختلف من سيناريو لأخر وتعكس عدم التأكد من المستقبل.

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

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

حيث هي القيمة المثلى للمشكلة ذات المرحلة الثانية

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

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

مراجع

Stochastic programming

قراءات أخرى

علاوةً على ذلك، 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.

وعلى صعيد آخر، Stein W. Wallace and William T. Ziemba (eds.) (2005) Applications of Stochastic Programming. MPS-SIAM Book Series on Optimization 5

من جهة ثانية، G. Ch. Pflug: Optimization of Stochastic Models. The Interface between Simulation and Optimization. Kluwer, Dordrecht, 1996.

كذلك، John R. Birge and François V. Louveaux. Introduction to Stochastic Programming. Springer Verlag, New York, 1997.

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.