صفحه محصول - پاورپوینت برنامه ریزی عددصحیح

پاورپوینت برنامه ریزی عددصحیح (pptx) 30 اسلاید

دسته بندی : پاورپوینت

نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )

تعداد اسلاید: 30 اسلاید

قسمتی از متن PowerPoint (.pptx) :

موضوع ارائه: برنامه ریزی عددصحیح برنامه ريزي عدد صحيحInteger Programming انواع برنامه ريزي عدد صحيح الف)برنامه ريزي عدد صحيح محض ب)برنامه ريزي عدد صحيح مختلط ج)برنامه ریزی صفر و یک مقدمه در اکثر مسائل طبیعی برقراری فرض بخش پذیری امکان پذیر نمی باشد و متغیرها صحیح می باشند. اگر تنها تفاوت فرموله کردن مساله ای با یک مساله برنامه ریزی خطی، در نظر گرفتن محدودیت عددصحیح باشد،به آن برنامه ریزی خطی با متغیرهای صحیح یا بطور خلاصه برنامه ریزی عددصحیح می گوییم. در مسائل برنامه ریزی عدد صحیح اگر فرض صحیح بودن برای تمام متغیرها موجود باشد آنرا برنامه ریزی عدد صحیح محض می نامیم. Max Z= 4x1+7x2 x1+3x2≤6 x1+x2 ≤12 x1 ,x2 ≥0 ,xi integer اگر فرض صحیح بودن برای بعضی متغیرها موجود باشد آنرا برنامه ریزی عدد صحیح مختلط می نامیم. Max Z= 4x1+7x2 x1+3x2≤6 x1+x2 ≤12 x1 ,x2 ≥0 , x1 integer اگر تمام متغیرها فقط شامل مقادیر یک وصفر باشند آنرا برنامه ریزی صفرو یک می نامیم. Max Z= 4x1+7x2 x1+3x2≤6 x1+x2 ≤12 x1 ,x2 = 0 or 1 حل مسائل برنامه ریزی عدد صحیح تنها تفاوت مسئله برنامه ریزی عدد صحیح با برنامه ریزی خطی این است که تعداد جوابها به مراتب کمتر است برای حل این مسائل الگوریتمهای پیشرفته ای توسعه پیدا کرده اند که میتوانند تا حدودی بهتر از شمارش عمل کنندولیکن به علت رشد نمایی پیچیدگی حتی این الگوریتم هاهم قادر به حل بیش از ده متغیرنیستند حل مسائل برنامه ریزی عدد صحیح مساله p1 که یک مساله ILP می باشد درنظر بگیرید. مساله LP آزاد شده آن را که فرض صحیح بودن متغیرهای آن کنار گذاشته شده را هم در نظر بگیرید: برای حل مساله p1 که یک مساله ILP می باشد، مساله LP آزاد شده آن یعنی P2را با یکی از الگوریتم های LPحل می کنیم. اگر جواب بهینه P2 صحیح باشد، که جواب P1 هم بدست آمده است و بدون حل ILP جواب بهینه P1 بدست آمده است. پس حل یک مساله ILP با حل یک مساله ILP آزاد شده شروع می گردد آنگاه بررسی می شود که آیا جواب بدست آمده عدد صحیح است یا خیر؟ نکات ناحیه شدنی P1 زیرمجموعه ناحیه شدنی P2 می باشد پس اگرP1 شدنی باشد P2 هم شدنی است. ولی اگر P2 شدنی باشدالزاما P1 شدنی نیست . مقدار بهینه تابع هدف P1 بهتر از مقدار بهینه مساله P2 نمی باشد. یعنی مقدار بهینه تابع هدف مساله ILP از مقدار تابع هدف LP آزاد شده خودش بهترنخواهد بود. تعداد متغیرهای پایه ای جدول بهینه P1 بزرگتر مساوی تعداد متغیرهای پایه ای جدول بهینه P2 می باشد. روشهاي حل مدلهاي برنامه ريزي عدد صحيح محض روش گرد کردن روش مجموعه تراز روش شاخه و کران روش برش گومري ( Gomery)