قدم سوم: مدل اپسیلون-محدودیت زیر را به ازای هر یک از مقادیر εk بدست آمده در مرحله قبل حل کنید. تعداد کل حل ها برابر خواهد شد با . (q1 + ۱) × (q2 + ۱) ×…× (qj-1 + ۱) × (qj+1 + ۱) ×…× (qK+ 1)
(۴-۵) | |
(۴-۶) | |
(۴-۷) |
که در آن ،θ یک عدد کوچک دلخواه است و بسته به مقدار تابع هدف اصلی تعیین میگردد و متغیر کمکی مربوط به محدودیت تابع هدف k ام است.
توجه شود که در هر تکرار بایستی یک مسئله برنامه ریزی تصادفی دو مرحله ای حل گردد. برای بدست آوردن جواب مسئله برای این مدل، از یک الگوریتم دیگر به نام ال-شکل استفاده میگردد. برای تولید سناریوها از الگوریتم نمونه گیری مونت کارلوی توسعه یافته استفاده میگردد. که در بخش بعدی توضیح آن خواهد آمد.
روش ال-شکل
همانطور که قبلاً اشاره شد، مدل پیشنهادی دوم یک مسئله چند هدفه تصادفی پایدار است که در آن عدم قطعیت بر اساس یک مجموعه از سناریوهای گسسته بیان می شود. برای تولید سناریوها از یک الگوریتم توسعه یافته مونت کارلو استفاده میکنیم. مزیت استفاده از این روش عدم حساسیت نسبی آن به نوع تابع توزیع پارامترهای غیرقطعی است. با این وجود، به دلیل ساختار تو در توی برنامه ریزی تصادفی دو مرحله ای، با افزایش تعداد سناریوها، ابعاد مسئله به صورت نمائی افزایش یافته که متعاقباً باعث افزایش زمان حل میگردد.
بنابراین ضروری به نظر میرسد که از یک الگوریتم کارا برای فائق آمدن بر چالشهای محاسباتی استفاده گردد. ضمن اینکه استفاده از رویکرد اپسیلون-محدودیت در مواجهه با چند هدفه بودن مدل پیشنهادی و ذکر این نکته که روش مزبور تولید جواب پارتوئی مینماید، پیچیدگیهای محاسباتی دو چندان می شود. بنابراین روش ال-شکل را که یک روش شناخته شده برای حل مسائل برنامه ریزی تصادفی دو مرحله ای است به کار میبندیم که از ساختار ویژه تجزیه پذیر برنامه ریزی تصادفی دو مرحله ای استفاده مینماید.
مسئله P1 به فرم استاندارد زیر را در نظر بگیرید:
P1:
(۴-۸) | |
(۴-۹) | |
(۴-۱۰) |
که در آن x بردار مربوط به متغیرهای مرحله اول و yn متغیرهای مرحله دوم به ازای سناریوی n است. معادله (۴-۸) یکی از اهداف مدل پیشنهادی دوم است که به عنوان هدف اصلی جهت بهینه سازی در مدل اپسیلون-محدودیت ارتقاء یافته در نظر گرفته شده است (که در اینجا Z1 به عنوان تابع هدف اصلی در نظر گرفته می شود) . معادله (۴-۹) مربوط به محدودیت هایی می شود که مختص متغیرهای مرحله اول و فاقد متغیرهای مرحله دوم است. یعنی همه محدودیتهای مدل پیشنهادی دوم به غیر از محدودیتهای شماره (۳-۳۹)، (۳-۴۳) و (۳-۴۵). معادله (۴-۱۰) مربوط به محدودیتهای است که شامل متغیرهای مرحله دوم میباشد یعنی محدودیتهای شماره (۳-۳۹)، (۳-۴۳) و (۳-۴۵) و سایر اهداف مسئله که بصورت محدودیت وارد مدل اپسیلون-محدودیت شده اند (معادلات (۳-۳۷) و (۳-۳۸)). c و qn ماتریس ضرایب برای متغیرهای تصمیم مرحله اول و دوم در تابع هدف است (برای مثال هزینه های واحد نگهداری، کمبود، حمل و نقل و هزینه های واحد مرتبط با نیروی کار). A و b ماتریس پارامترهای مستقل از سناریوها هستند و wn، hn و Tn ماتریس ضرایب تحت سناریویn N هستند. ایده ای که روش ال-شکل از آن استفاده می کند به این قرار است که ابتدا مدل بیرونی (تابع هدف و محدودیت هایی که شامل متغیرهای مرحله دوم نمی شوند) برای بدست آوردن مقادیر متغیرهای مرحله اول حل می شود. سپس مقادیر بدست آمده برای متغیرهای مرحله اول را در مدل جایگزاری میکنیم و مسئله داخلی (یعنی تابع هدف و محدودیت هایی که شامل متغیرهای مرحله دوم است) به ازای تک تک سناریوها حل می شود تا مقادیر بهینه متغیرهای مرحله دوم به ازای هر سناریو بدست آید. اگر مقدار تابع هدف مدل داخلی را تحت سناریوی n، Qn(x) بنامیم، خواهیم داشت: