بخشی از پاورپوینت
اسلاید 1 :
بنام خدا
برنامه ریزی خطی پیشرفته (21715(
Advanced Linear Programming
بهینه سازی استوار (Robust Optimization)
اسلاید 4 :
هدف از ارایه
بررسی مساله های بهینه سازی در حالت قطعی نبودن داده ها
ارایه مطالب اولیه با تاکید بر:
توضیح پدیده عدم قطعیت در داده ها و دلایل اهمیت آن
توضیح برخورد با مساله عدم قطعیت داده ها در بهینه سازی استوار
مقایسه بهینه سازی استوار با تکنیک های متداول برای حل مساله های بهینه سازی با داده های غیر قطعی
اسلاید 5 :
عدم قطعیت در داده ها در بهینه سازی
آیا عدم قطعیت در داده های (مقدار پارامترهای) مساله های بهینه سازی نیاز به توجه ویژه دارد؟
اسلاید 6 :
مثال
مساله ای شناخته شده از مجموعه مساله های NETLIB (مساله PILOT4)
مساله شامل 1000 متغیر تصمیم و 410 محدودیت
یکی از محدودیت های مساله :
اسلاید 7 :
مثال-ادامه
جواب بهینه مساله با استفاده از نرم افزار CPLEX:
ارضای محدودیت بصورت تساوی با توجه به دقت نرم افزار
اسلاید 8 :
مثال-ادامه
ثبت ضریب های تکنولوژیکی مساله بطور غیر واقعی دقیق و با اعشار بالا
امکان پذیر نبودن چنین دقتی در مساله های واقعی
حساسیت بالای جواب بهینه در بیشتر موارد نسبت به مقدار پارامترهای مساله
غیر بهینه و یا حتی غیر موجه شدن جواب بهینه با تغییر مقدار یک پارامتر
اسلاید 9 :
نتایج یک تحقیق در سال 1990 میلادی:
حل 90 مساله انتخاب شده از مجموع مساله های برنامه ریزی خطی نمونه در NETLAB
انجام تغییرات جزیی در حد تغییر 0.01 درصدی یکی از پارامترها در تعدادی از محدودیت ها و حل مجدد مساله
ارضا نشدن محدودیت ها در اثر این تغییر در 13 مساله
مشاهده بزرگی مقدار غیر موجه یکی از محدودیت ها بیش از 100% در شش مساله
نتیجه گیری
تغییر قابل توجه جواب بهینه مساله در بسیاری از مساله های دنیای واقعی با انجام تغییر بسیار ناچیز در یکی از پارامترها
اسلاید 10 :
نگرانی مهم کاربران تحقیق در عملیات
خطای پیش بینی: عدم قطعیت در داده ها و مشخص نبودن مقدار پارامترها زمان حل مساله
خطای اندازه گیری: خطاهای اندازه گیری و تخمین پارامترها
خطای اجرا: خطاهای پیاده سازی و استفاده از جواب بهینه (مثال عددی ارایه شده)
امکان ناموجه شدن یا بی معنی شدن جواب بهینه مساله در اثر تغییر جزیی در یکی از پارامترها
اسلاید 11 :
نگرانی مهم کاربران تحقیق در عملیات
نیاز به وجود یک متدولوژی برای:
شناسایی وضعیت های عدم قطعیت
شناسایی تاثیرهای آن بر وضعیت جواب بهینه
ارایه یک جواب استوار بر پایه این محدودیت ها به منظور ارایه جوابی ایمن نسبت به این عدم قطعیت ها
اسلاید 12 :
مثال هایی واقعی از عدم قطعیت
عدم قطعیت در تمامی فعالیت های زنجیره تامین
عدم قطعیت در قیمت سهام در بازار بورس برای فاصله های زمانی آینده
عدم قطعیت در مقدار تقاضای محصول در دوره بعدی
عدم قطعیت در مقدار پارامترهای مساله های زمان بندی واقعی مانند زمان بندی اتاق های عمل
اسلاید 13 :
روش های کلاسیک در مورد برخورد با مساله های عدم قطعیت
تحلیل حساسیت(Sensitivity Analysis)
برنامه ریزی احتمالی(Stochastic Programming)
منطق فازی
اسلاید 14 :
بهینه سازی تصادفی و تحلیل حساسیت
کاربرد تحلیل حساسیت در مساله های پیوسته و قطعی
تغییر یک پارامتر در حالت ثابت بودن سایر پارامترها
ماهیت قطعی بودن مقدار پارامترها در تکنیک های تحلیل حساسیت
اسلاید 15 :
مقایسه بهینه سازی استوار با برنامه ریزی احتمالی
Stochastic Optimization (SO)
فرض پایه
تعیین مقدار پارامترهای مدل بر پایه یک مقدار تصادفی از یک تابع توزیع احتمالی مشخص (در مواردی نامشخص)
ناشناخته بودن تابع توزیع احتمالی مقدار پارامترها در مواردی
تبدیل مساله غیر قطعی خطی به یک مساله قرین (counterpart) با عنوان chance constraint problem
اسلاید 16 :
مقایسه بهینه سازی استوار با برنامه ریزی احتمالی-ادامه
نمایش برنامه ریزی احتمالی بصورت زیر:
اپسیلون یک عددبسیار کوچک
P تابع توزیع داده های مساله (c, A, b) که بصورت کامل شناخته شده نیست.
اسلاید 17 :
مقایسه بهینه سازی استوار با برنامه ریزی احتمالی -ادامه
می توان مدل برنامه ریزی احتمالی را بصورت زیر نیز نمایش داد:
محافظه کاری کمتر برنامه ریزی احتمالی نسبت به بهینه سازی استوار )که همواره بدترین حالت های ممکن را نیز در نظر می گیرد) اگر بتوانیم تابع توزیعی برای تخمین پارامترهای مساله شناسایی کنیم.
چنین شانسی همواره وجود ندارد.
اسلاید 18 :
مقایسه بهینه سازی استوار با برنامه ریزی احتمالی –ادامه
از یک دیدگاه می توان خاصیت محافظه کارانه تر بهینه سازی استوار را مزیتی نسبت به برنامه ریزی احتمالی دانست.
اسلاید 19 :
مثال
مراحل طراحی یک بنا مانند یک پل راه آهن
تلاش مهندسین طراحی برای افزایش مقدار پارامترهای ایمنی طراحی پل با استفاده از تکنیک های کمی
غیر قطعی بودن این پارامترها در اثر متغیر بودن شرایط محیطی و جوی (زلزله، سیل و.)
در صورت استفاده از تکنیک های بهینه سازی استوار در این فرایند
انتخاب بزرگترین منطقه عدم اطمینان با هدف نزدیک شدن تا حد ممکن به حالت ایمن
اسلاید 20 :
مثال-ادامه
این عمل در برنامه ریزی احتمالی ممکن نیست زیرا که بودجه تحمل عدم اطمینان بر اساس رابطه زیر از قبل ثابت فرض شده است.
به عبارت دیگر مجموع احتمال شناسایی عدم قطعیت ها باید برابر یک باشد.
با تلاش برای افزایش احتمال رویداد یک سناریو، احتمال رویداد سناریوهای دیگر کاهش پیدا می کنند.
در مواردی کنترل این فرایند بسیار مشکل می شود.
