درس 4: برنامه ریزی خطی پارامتری

تهیه شده توسط گروه بهینه‌یاب

در بخش تحلیل حساسیت، توجه خود را به تغییراتی در داده‌ها پرداخته شد که جواب اساسی بهینه تغییر نکند. در صورت تجاوز مقادیر از مقداری که باعث چرخش لولا شود، دیگر معتبر نیست. بررسی نظام‌مند تحلیل حساسیت به ازای تغییر همزمان و تدریجی پارامترها در روش برنامه ریزی خطی پارامتری بررسی می‌شود.

تغییر نظام گرای پارامترهای c_j

تابع هدف زیر را در نظر بگیرید:

در برنامه ریزی خطی پارامتری، تابع هدف فوق با تابع زیر جایگزین می‌شود.

α_j داده‌های ثابتی هستند که معرف آهنگ تغییرات ضرایب تابع هدف خواهند بود. مقدار θ به تدریج از صفر بزرگتر می‌شود. برای تشریح عملکرد مدل برنامه‌ریزی خطی با تغییر θ ، مثال زیر را در نظر بگیرید.

مثال:

حل: مقدار 1- = α₂ و 2 = α₁ در نظر بگیرید. لذا تابع هدف به صورت زیر می‌شود.

از جدول نهایی سیمپلکس با θ = 0 شروع می‌کنیم که تابع هدف به صورت زیر می‌شود.

تغییرات تابع هدف را به سمت چپ تابع هدف اضافه می‌کنیم که به صورت زیر می‌شود.

چون x₁ و x₂ متغیرهای اساسی هستند ( که در معادلات 2 و 3 ظاهر شدند)، باید ضریب این دو متغیر در تابع هدف فوق برابر صفر شود. این کار با اضافه کردن معادلات 2 و 3 به تابع هدف میسر می‌شود که به صورت زیر می‌شود:

با توجه به دستور توقف الگوریتم سیمپلکس اولیه، مادامیکه ضرایب متغیرهای غیراساسی غیرمنفی باقی بمانند، جواب اساسی موجه فعلی بهینه خواهد ماند. پس داریم:

بنابراین اگر θ >9/7 شود، x₄ به عنوان متغیر اساسی ورودی تکرار بعدی سیمپلکس انتخاب می‌گردد و تا جواب بهینه جدید بدست آید. می‌توان θ را باز هم اضافه کرد تا اینکه ضریب دیگری منفی شود و به همین ترتیب می‌توان θ را تا هر مقداری افزایش داد. خلاصه رویه فوق با افزایش θ در جدول زیر آمده است.

مقدار تابع هدف جواب بهینه به عنوان تابعی از θ به صورت زیر می‌شود.

تغییرات نظام گرا پارامترهای سمت راست b_i

در این حالت از برنامه ریزی خطی پارامتری، تغییری که داده می‌شود این است که به جای b_i عبارت b_i+θα_i قرار می‌گیرد که α_i داده‌های ثابتی هستند. بنابراین، مسئله به صورت زیر در می‌آید.

هدف از این بخش، مشخص کردن جواب بهینه به عنوان تابعی از θ است. رویه حلی که در زیر بیان می‌شود شباهت زیادی با روند آنچه که به ازای تغییر c_j گفته شده دارد. دلیل آن معادل بودن تغییر در ضرایب تابع هدف مسئله اولیه با تغییر ضرایب سمت راست مسئله همزاد است. برای تشریح بیشتر موضوع چند تمرین حل می‌کنیم.

تمرین: از رویه برنامه ریزی خطی پارامتری برای انجام تغییرات نظام گرا در b_i استفاده کنید و جواب بهینه مسئله زیر را به صورت تابعی از θ برای [0,25] = θ بدست آورید.

حل:

خلاصه نتایج در جدول زیر آمده است.