بخشی از پاورپوینت
اسلاید 1 :
بنام خدا
برنامه ریزی خطی پیشرفته (21715)
Advanced Linear Programming
اسلاید 2 :
برنامه ریزی خطی پیشرفته (21715)
برای حل کارای بهینه یک مساله برنامه ریزی خطی عدد صحیح با اندازه بزرگ، لازم است که مساله ایجاد شده با فرض پیوسته بودن متغیرهای تصمیم، تقریب مناسبی از جواب بهینه ایجاد کند.
به عبارت دیگر جواب بهینه مساله با پیوسته فرض کردن متغیرهای تصمیم عدد صحیح به جواب بهینه مساله اصلی نزدیک باشد.
ناکارا بودن مدل های متداول برنامه ریزی عدد صحیح عادی با توجه به این شاخص
اسلاید 3 :
ارایه روش های مدل سازی و حل مساله با این هدف مانند:
روش Branch-and-cut
روش Branch-and- price
برای این منظور الگوریتم Branch-and-cut در دهه 80 میلادی پایه گذاری شده و تا اوایل دهه 90 توسعه پیدا کرد.
اسلاید 4 :
خلاصه ای از الگوریتم(B&C) Branch-and-cut
جدا سازی دسته هایی (کلاس هایی) از محدودیت های معتبر مساله (ترجیحا face های convex hull منطقه موجه) از مساله LP relaxation مساله اصلی
علت این مساله زیاد بودن تعداد محدودیت ها و در نظر گرفتن این مساله که اغلب این محدودیت ها در جواب بهینه بصورت تساوی ارضا نمی شوند.
اسلاید 5 :
خلاصه ای از الگوریتم Branch-and-cut (ادامه)
در این حالت اگر جواب بهینه مساله LP relaxed موجه نبود با حل یک مساله برنامه ریزی خطی دیگر با نام Separation Problem سعی در پیدا کردن محدودیت هایی داریم که ارضا نشده اند.
اگر چنین محدودیت هایی پیدا شدند، تعدادی از آنها به مساله LP relaxed اضافه شده تا جواب بهتری پیدا شود.
سپس مساله LP relaxed مجددا حل می شود.
اسلاید 6 :
خلاصه ای از الگوریتم Branch-and-cut (ادامه)
در صورتی که تمامی محدودیت های مساله ارضا شوند، فرایند شاخه زنی انجام می شود.
عملا این فرایند در داخل روش حل شاخه و حد انجام می شود.
اصول این روش در Hoffman and Padberg (1985) و Nemhauser and Wolsey (1988) قابل مشاهده است.
اسلاید 7 :
روش Branch-and-Price
الگوریتم Branch-and-Price (B&P) همان روش B&C است با این تفاوت که نیازی نیست با پیشروی در مراحل محدودیت های جدیدی به مساله اضافه شود.
تمرکز این الگوریتم به روی تولید ستون های جدید برای مساله است تا تولید سطر (محدودیت) جدید
در این روش به جای کنار گذاشتن محدودیت های مساله، ستون های (جواب های موجه مساله) بطور موقت کنار گذارده می شوند.
اسلاید 8 :
توجه کنید که هدف این تکنیک ترکیب روش های pricing و cutting با هدف ایجاد مساله LP relaxed با جواب با کیفیت تر است.
در روش B&P مساله برنامه ریزی خطی به صورتی فرموله می شود که شامل تعداد بسیار زیادی متغیر تصمیم (ستون) باشد.
اسلاید 9 :
سپس تعداد بسیار زیادی از این ستون ها بصورت موقت به دلایل زیر کنار گذارده می شوند:
مساله با تعداد ستون کمتری بصورت آسان تری حل شود.
تعداد بسیار زیادی از این ستون ها تاثیری در جواب بهینه ندارند. به عبارتی متغیر تصمیم مربوط به آنها در جواب بهینه مساله مقداری برابر با صفر خواهد داشت.
اسلاید 10 :
سپس به منظور آزمایش بهینگی مساله یک یا چند مساله فرعی با عنوان “pricing problem” و یا “sub problem” حل می شوند.
pricing problemبر پایه مساله دوگان مساله اصلی، با فرض پیوسته فرض کردن متغیرهای تصمیم مساله، ایجاد می شود.
وظیفه pricing problem پیدا کردن ستون هایی است که می توانند وارد پایه شده و مقدار تابع هدف مساله را بهبود دهند.
اسلاید 11 :
اگر چنین ستونی پیدا شود، مساله با در نظر گرفتن این ستون مجددا حل می شود.
در صورتی که چنین ستونی پیدا نشود و مقدار متغیرهای تصمیم عدد صحیح دارای مقدار صحیح نباشند، عملیات شاخه زنی به روی متغیرهای تصمیم عدد صحیح مساله اصلی انجام می شود.
اسلاید 12 :
بطور خلاصه:
روش branch-and-price روش عمومیت داده شده شاخه و حد است برای حل مساله های برنامه ریزی خطی عدد صحیح با پیوسته فرض کردن متغیرهای تصمیم بصورتی که تکنیک تولید ستون در طول درخت شاخه و حد اعمال می شود.
اسلاید 13 :
در این روش مساله مجددا فرموله شده به یک مساله master و یک یا چند مساله فرعی تجزیه می شود.
در ابتدا مساله master تنها با در نظر گرفتن چندین ستون موجه حل می شود (تعداد ستون های موجه معمولا بی نهایت است و مقدار متغیر تصمیم اغلب آنها در جواب بهینه برابر با صفر است).
اسلاید 14 :
سپس برای بررسی بهینگی جواب مساله master مساله یا مساله هایی فرعی حل می شوند که مشخص شود آیا ستونی برای ورود به مساله به منظور بهبود تابع هدف وجود دارد یا خیر.
اگر چنین ستون هایی پیدا شوند مساله master مجددا با در نظر گرفتن این ستون ها حل می شود.
اگر چنین ستونی پیدا نشد و جواب بهینه مساله master محدودیت های صحیح بودن متغیرهای تصمیم را ارضا نکرد، فرایند شاخه زنی انجام می شود.
اسلاید 15 :
الگوریتم B&P که توسعه یافته الگوریتم شاخه و حد است در واقع تکنیک تولید ستون را در مرحله های مختلف شاخه زنی با الگوریتم ترکیب می کند تا حل مساله خطی در مراحل میانی ساده شده و جواب هایی با کیفیت بهتر ایجاد شود.
الگوریتم B&P، تنها استفاده از روش تجزیه دنزینگ-ولف در روش شاخه و حد نیست و دارای پیچیدگی های فراوان تری است.
اسلاید 16 :
دلایل فرمول بندی مجدد مساله با تعداد ستون زیاد
عموما پیوسته فرض کردن متغیرهای تصمیم در مساله های برنامه ریزی خطی عدد صحیح منجر به ایجاد جوابی برای تابع هدف می شود که فاصله بسیاری با جواب بهینه مساله اصلی دارد. در صورتی که مساله به این صورت فرموله شود، پیوسته فرض کردن متغیرهای تصمیم مساله منجر به ارایه جواب نزدیک تری به جواب بهینه نسبت به حالت قبلی می شود.
اسلاید 17 :
دلایل فرمول بندی مجدد مساله با تعداد ستون زیاد (ادامه)
عموما استفاده از فرمول بندی عمومی منجر به ایجاد ساختار قرینه ای برای مساله می شود. در این حالت بازدهی روش شاخه و حد برای حل مساله مناسب نیست زیرا که ندرتا مقدار تابع هدف مساله با پیشروی در شاخه ها افزایش پیدا می کند. فرمول بندی مجدد مساله با تعداد زیادی متغیر این مشکل را برطرف می کند.
اسلاید 18 :
دلایل فرمول بندی مجدد مساله با تعداد ستون زیاد (ادامه)
در صورت فرمول بندی مجدد مساله با تعداد زیادی متغیر می توان مساله را به یک مساله master و یک یا چند مساله فرعی مجزا تقسیم کرد.
در مواردی این تنها روش فرموله کردن مساله است.
اسلاید 19 :
استفاده از تکنیک تولید ستون برای مساله های برنامه ریزی خطی با متغیرهای تصمیم عدد صحیح آسان نیست. دلایل عمده این مساله عبارتند از:
هنگام شاخه زدن مقدار یک متغیر در شاخه های پایینی ثابت فرض می شود. این مساله می تواند اصول تکنیک تولید ستون را با اشکال مواجه کند.
حل مساله های برنامه ریزی خطی ایجاد شده در مراحل کار بصورت بهینه به صرفه نیست.
لذا نیاز به ایجاد قوانینی است که فرایند شاخه زدن را بر اساس روش خاصی ((Branch-and-price انجام دهد.
اسلاید 20 :
روش های متفاوتی برای استفاده از روش B&P در ادبیات وجود دارند.
کاربردهای زیادی از این تکنیک در حل مساله های توالی عملیات و مسیریابی در ادبیات مشاهده می شود.
