بهینه‌سازی استوار (Robust Optimization) -قسمت سوم

  

مروری بر آنچه تا به حال گفته شد...

نخستین گام در طراحی روشهای استوار در سال 1973 توسط سویستر برداشته شد. در مدل پیشنهادی وی به ازای کلیه مقادیر متعلق به یک مجموعه عدم قطعیت، جواب بهینه شدنی باقی می ماند. جوابهای تولید شده با این روش بسیار محافظه کارانه است و از جواب بهینه اسمی فاصله نسبتاً زیادی دارد. در واقع، رویکرد پیشنهادی سویستر بسیار سختگیرانه بود و تا حد زیادی از تابع هدف صرف نظر میکرد.

بنتال و نمیرفسکی با فرض اینکه داده ها در مجموعه های محدب دارای عدم قطعیت هستند، قدم مؤثری در زمینه بهینه سازی استوار برداشتند. رویکرد پیشنهادی این نویسندگان نسبت  به سویستر محافظه کاری کمتری داشت و شامل حل نظیر استوار می شد.

در بهینه سازی استوار مبتنی بر مجموعه های محدب فرض می شود که داده های غیرقطعی در یک مجموعه عدم قطعیت مشخص تغییر می کند و هدف انتخاب بهترین جواب است که باید از تغییرات و غیرقطعی بودن داده ها در امان باشد. این بدان معناست که جواب های بدست آمده به ازای تمامی مقادیر داده ها در بازه یا مجموعه تعیین شده شدنی باشد. اساس مدل های استوار مبتنی بر مجموعه های محدب بر برنامه ریزی مخروطی و قضایای دوگان استوار است. این مجموعه های محدب بر اساس نرم های فاصله ای مختلف (از یک تا بینهایت) ساخته می شوند.

مجموعه عدم قطعیت جعبه: (نرم بی نهایت یا ماکزیمم)

همانطور که در شکل بالا می بینید فضای عدم قطعیت بین دو پارامتر (دو بعدی) در سمت راست، به شکل متقارن سمت چپ تصویر شده است. همانطور که دیده می شود برای تشکیل این فضای عدم قطعیت متقارن از تعریف نرم بی نهایت استفاده شده است. خطوط کناری این فضا با توجه به علامت متغیر حالت، نشان دهنده بدترین مقدار پارامتر یا (worst case) هستند.

مجموعه عدم قطعیت چندوجهی: (نرم 1 یا قدرمطلق)

در اینجا نیز فضای عدم قطعیت دو بعدی در راست، به شکل متقارن سمت چپ تصویر شده است. برای تشکیل این فضای عدم قطعیت متقارن از تعریف نرم درجه اول استفاده شده است. این فضاا همان دوران یافته حالت جعبه می باشد که با این دوران از worst case بودن فضا کاسته شده است.

چگونگی تشکیل همزاد استوار در فضای عدم قطعیت جعبه:

مدل بهینه سازی خطی زیر را در نظر بگیرید:

در مدل بالا پارامترهای دارای عدم قطعیت به صورت زیر تعریف می شوند:

بر طبق گفته بنتال و نمیروسکی با تعریف مجموعه عدم قطعیت جعبه، هدف یافتن جوابی است که به ازای تمامی مقادیر p در مجموعه عدم قطعیت شدنی باشد. در نتیجه مدل به صورت زیر تبدیل خواهد شد:

همزاد استوار مسئله مورد بحث را به صورت ذیل می توان تعریف کرد:

هنگامی که مجموعه عدم قطعیت جعبه باشد مدل همزاد استوار به صورت مدل خطی زیر تبدیل خواهد شد:

در پست های بعدی به بررسی جزئیات رویکردها و مدل های مختلف استوار می پردازیم.

به منظور دسترسی آسان‌تر به این سلسله مطالب، از این پس خوانندگان عزیز می‌توانند به بخش بهینه‌سازی استوار  در وبلاگ مراجعه نمایند. 

(مونا عیسی‌بخش  mـ[e-mail])