کد گمز مسئله حمل و نقل – تخصیص با الگوریتم L-شکل

توضیحاتی در مورد الگوریتم L شکل (L-shaped)

روش L شکل برای حل مسائل برنامه ریزی تصادفی دو مرحله ای خطی استفاده می شود. در این گونه مسائل تعداد متناهی سناریو وجود دارد.

هرسناریو بیانگر حالتی از پارامترهای تصادفی است و احتمال وقوع آن را با ps نشان می دهیم. هدف، تعیین مقدار متغیرهای تصمیم مرحله اول است به طوری که برای هر سناریو شدنی باشد و مقدار متوسط هزینه را مینیمم کند.

ابتدا این روش را برای حالت خاصی که تنها یک سناریو وجود دارد شرح می دهیم. بدین منظور، مدل زیر را در نظر بگیرید:

ایده کلی بر این است که تعمیمی از روش بندرز به کارگرفته شود، بدین منظور، مجددا روش بندرز را برای حل مدل بالا شرح می دهیم. دراین روش ابتدا مدل زیر حل می شود. فرض کنید این مسئله شدنی و جواب بهینه متناهی دارد. ( برای بررسی حالتی که این مسئه بی کران است، به مرجع [۱] مراجعه نمایید)

[۱]  L-shaped linear programs with applications to optimal control and stochastic programming , R. V. Van slyke and R. Wets