دانلو پاورپوینت آماده درسی و دانشگاهی

نام فایل : برنامه ریزی خطی پیشرفته

فرمت : .ppt

تعداد صفحه/اسلاید : 82

حجم : 1328 کیلوبایت

*
بنام خدا



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

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

ناکارا بودن مدل های متداول برنامه ریزی عدد صحیح عادی با توجه به این شاخص
*
برنامه ریزی خطی پیشرفته (21715)

ارایه روش های مدل سازی و حل مساله با این هدف مانند:
روش Branch-and-cut
روش Branch-and- price

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

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

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

*
برنامه ریزی خطی پیشرفته (21715)
خلاصه ای از الگوریتم Branch-and-cut (ادامه)

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

....