مرجع دانلود پاورپوینت های درسی

حجم فایل : 612.5 KB
نوع فایل : پاور پوینت
تعداد اسلاید ها : 82
1 بنام خدا



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

به عبارت دیگر جواب بهینه مساله با پیوسته فرض کردن متغیرهای تصمیم عدد صحیح به جواب بهینه مساله اصلی نزدیک باشد.

ناکارا بودن مدل های متداول برنامه ریزی عدد صحیح عادی با توجه به این شاخص 3 برنامه ریزی خطی پیشرفته (21715)
ارایه روش های مدل سازی و حل مساله با این هدف مانند:
روش Branch-and-cut
روش Branch-and- price

برای این منظور الگوریتم Branch-and-cut در دهه 80 میلادی پایه گذاری شده و تا اوایل دهه 90 توسعه پیدا کرد. 4 برنامه ریزی خطی پیشرفته (21715) خلاصه ای از الگوریتم(B&C) Branch-and-cut

جدا سازی دسته هایی (کلاس هایی) از محدودیت های معتبر مساله (ترجیحا face های convex hull منطقه موجه) از مساله LP relaxation مساله اصلی

علت این مساله زیاد بودن تعداد محدودیت ها و در نظر گرفتن این مساله که اغلب این محدودیت ها در جواب بهینه بصورت تساوی ارضا نمی شوند.
5 برنامه ریزی خطی پیشرفته (21715) خلاصه ای از الگوریتم Branch-and-cut (ادامه)

در این حالت اگر جواب بهینه مساله LP relaxed موجه نبود با حل یک مساله برنامه ریزی خطی دیگر با نام Separation Problem سعی در پیدا کردن محدودیت هایی داریم که ارضا نشده اند.

اگر چنین محدودیت هایی پیدا شدند، تعدادی از آنها به مساله LP relaxed اضافه شده تا جواب بهتری پیدا شود.

سپس مساله LP relaxed مجددا حل می شود.
6 برنامه ریزی خطی پیشرفته (21715) خلاصه ای از الگوریتم Branch-and-cut (ادامه)

در صورتی که تمامی محدودیت های مساله ارضا شوند، فرایند شاخه زنی انجام می شود.

عملا این فرایند در داخل روش حل شاخه و حد انجام می شود.
اصول این روش در Hoffman and Padberg (1985) و Nemhauser and Wolsey (1988) قابل مشاهده است. 7 برنامه ریزی خطی پیشرفته (21715) روش Branch-and-Price

الگوریتم Branch-and-Price (B&P) همان روش B&C است با این تفاوت که نیازی نیست با پیشروی در مراحل محدودیت های جدیدی به مساله اضافه شود.

تمرکز این الگوریتم به روی تولید ستون های جدید برای مساله است تا تولید سطر (محدودیت) جدید

در این روش به جای کنار گذاشتن محدودیت های مساله، ستون های (جواب های موجه مساله) بطور موقت کنار گذارده می شوند. 8 برنامه ریزی خطی پیشرفته (21715) روش Branch-and-Price

توجه کنید که هدف این تکنیک ترکیب روش های pricing و cutting با هدف ایجاد مساله LP relaxed با جواب با کیفیت تر است.

در روش B&P مساله برنامه ریزی ...