ParametricProgramming[1]

‫برنامه ریزی خطی پارامتری‬ ‫مبحث برنامه ریزی پارامتری ادامه و مکمل تحلیل حساسیت می باشد‪.‬‬ ‫تحلیل حساسیت‪:‬میزان حساسیت جواب بهینه در مقابل تغییرات‬ ‫پارامترها( ‪) , ,‬‬ ‫در تحلیل حساسیت ‪،‬تأثیر گسسته پارامترهای مدل بر جواب نهایی بررسی‬ ‫می شد‪،‬یا تغییرات پیوسته پارامترها تنها در یک دامنه مشخص ‪،‬تعیین‬ ‫می گشت‪.‬اما در برنامه ریزی پارامتری تأثیر تغییرات پیوسته‬ ‫پارامترها در تمام دامنه های ممکن مد نظر است‪.‬‬ ‫حالت اول‪:‬تغییرات پارامتری در ضرایب تابع هدف‬ ‫صورت عادی تابع هدف در برنامه ریزی خطی چنین است‪:‬‬ ‫=‪Z‬‬ ‫‪1‬‬ ‫در برنامه ریزی پارامتری این تابع با تابع هدف زیر تعویض می شود‪:‬‬ ‫‪1‬‬ ‫برای سادگی فرض می شود‬ ‫=) (‪Z‬‬ ‫𝛉 باشد‪.‬‬ ‫خالصه رویه انجام عملیات برنامه ریزی پارامتری در مورد تغییرات‬ ‫پارامترهای تابع هدف به شرح زیر است‪:‬‬ ‫گام‬ ‫‪ )1‬مسأله را به روش سیمپلکس به ازای‬ ‫𝛉 حل کنید‪.‬‬ ‫گام ‪ )2‬با استفاده از رویه تحلیل حساسیت ‪،‬تغییرات ناشی از وجود 𝛉‬ ‫را در سطر صفر وارد کنید‪.‬‬ ‫گام ‪ )3‬مقدار 𝛉 را آنقدر اضافه کنید تا ضریب یکی از متغییر های‬ ‫غیراساسی در سطر صفر منفی شود‪.‬‬ ‫گام ‪ )4‬از این متغییر به عنوان متغییر اساسی ورودی تکرار بعدی روش‬ ‫سیمپلکس استفاده کنید و جواب بهینه جدید را به دست آورید و به گام‬ ‫‪ 3‬بازگردید‪.‬‬  ‫*‬ ‫این شیوه تا جایی ادامه میابد تا سرانجام 𝛉 به مقداری میرسد که‬ ‫جواب یا وجود ندارد یا بدون تغییر باقی می ماند‪.‬‬ ‫مثال) مسأله زیر را در نظر بگیرید‪.‬‬ ‫‪2‬‬ ‫‪6‬‬ ‫‪4‬‬ ‫‪Max Z=3‬‬ ‫‪1‬‬ ‫‪2‬‬ ‫‪2‬‬ ‫‪0‬‬ ‫‪s.t. 2 1 33‬‬ ‫‪2 1+‬‬ ‫‪1, 2‬‬ ‫اگر تابع ‪ Z‬به صورت پارامتری به شکل زیر تغییر نماید تمام جواب های‬ ‫بهینه مسأله را به دست آورید‪.‬‬ ‫‪2‬‬ ‫‪2‬‬ ‫‪1‬‬ ‫‪1‬‬ ‫‪Z( )=(33‬‬ ‫حل‪:‬‬ ‫𝛉 حل کنید‪.‬‬ ‫گام ‪ )1‬مسأله را به ازای‬ ‫اعداد سمت راست‬ ‫‪6‬‬ ‫‪2‬‬ ‫‪2‬‬ ‫‪1‬‬ ‫‪2‬‬ ‫‪2‬‬ ‫‪0 3/2‬‬ ‫‪-1‬‬ ‫‪1/2‬‬ ‫‪1‬‬ ‫‪1/2‬‬ ‫‪0‬‬ ‫‪1‬‬ ‫‪0‬‬ ‫‪1‬‬ ‫‪0‬‬ ‫‪1‬‬ ‫‪2‬‬ ‫‪1/2‬‬ ‫متغیر های‬ ‫اساسی‬ ‫‪Z‬‬ ‫‪ Z‬شماره‬ ‫سطر‬ ‫‪0‬‬ ‫‪11 0‬‬ ‫‪21 0‬‬ ‫گام ‪ )2‬با استفاده از روش تحلیل حساسیت ‪،‬تغییرات ناشی از تابع هدف‬ ‫را در جدول بهینه اعمال کنید‪.‬‬ ‫‪=-‬‬ ‫‪1‬‬ ‫‪2‬‬ ‫=‬‫‪2‬‬ ‫‪3‬‬ ‫‪=1/2-2‬‬ ‫‪1‬‬ ‫جدول نهایی بعد از اعمال تغییرات‬ ‫اعداد سمت راست‬ ‫‪2‬‬ ‫‪1‬‬ ‫‪2‬‬ ‫‪3 2‬‬ ‫‪3 2‬‬ ‫‪1‬‬ ‫‪Z‬‬ ‫‪0‬‬ ‫‪0‬‬ ‫‪2‬‬ ‫شماره‬ ‫سطر‬ ‫‪3‬‬ ‫‪1‬‬ ‫‪1‬‬ ‫‪1‬‬ ‫‪2‬‬ ‫‪2‬‬ ‫متغیر های‬ ‫اساسی‬  ‫‪6‬‬ ‫‪2‬‬ ‫‪2‬‬ ‫‪1/2-2‬‬ ‫‪03/2‬‬ ‫‪-1‬‬ ‫‪1/2‬‬ ‫‪1‬‬ ‫‪0‬‬ ‫چون بردار متغیر اساسی‬ ‫جدول نهایی برای‬ ‫اعداد سمت راست‬ ‫‪632‬‬ ‫‪2‬‬ ‫‪2‬‬ ‫‪2‬‬ ‫‪1/2‬‬ ‫‪1‬‬ ‫‪0‬‬ ‫‪0‬‬ ‫‬‫‪0‬‬ ‫‪1‬‬ ‫‪0‬‬ ‫‪11‬‬ ‫‪21‬‬ ‫(‪Z‬‬ ‫یکه نیست باید آن را یکه کرد‪.‬‬ ‫𝛉‬ ‫‪2‬‬ ‫‪2‬‬ ‫‪1‬‬ ‫‪0 3/231/2‬‬ ‫‪1‬‬ ‫‪-1‬‬ ‫‪0‬‬ ‫‪1/2‬‬ ‫‪ Z‬شماره‬ ‫سطر‬ ‫‪0‬‬ ‫‪1‬‬ ‫‪11 0‬‬ ‫‪21 0‬‬ ‫‪1‬‬ ‫‪0 1/2-3/2‬‬ ‫‪0‬‬ ‫‪2‬‬ ‫‪1‬‬ ‫‪1/2‬‬ ‫متغیر های‬ ‫اساسی‬ ‫(‪Z‬‬ ‫جدول فوق وقتی بهینه است که تمام عناصر سطر صفر غیر منفی باشند‪.‬‬ ‫‪0‬‬ ‫‪1 3‬‬ ‫همواره مثبت‬ ‫با فرض‪0‬‬ ‫گام ‪ )3‬در صورتیکه‬ ‫مسأله دیگر بهینه نیست‪.‬‬ ‫‪1‬‬ ‫‪2‬‬ ‫‪3‬‬ ‫‪2‬‬ ‫است‬ ‫𝛉 شود ضریب‬ ‫‪0‬‬ ‫در تابع هدف منفی می شود و‬ ‫به عنوان متغیر ورودی انتخاب ‪،‬و‬ ‫گام ‪ )4‬متغیر‬ ‫شود‪.‬جدول زیر تکرار بعدی سیمپلکس را نشان می دهد‪.‬‬ ‫جدول نهایی برای‪7‬‬ ‫اعداد سمت راست‬ ‫‪11/2+2/2‬‬ ‫‪1‬‬ ‫‪3/2‬‬ ‫𝛉‬ ‫‪3/231/2‬‬ ‫خروجی می‬ ‫‪1/3‬‬ ‫‪2‬‬ ‫‪1‬‬ ‫‪(3/4 -1/4((2/4-1/4‬‬ ‫‪1/2‬‬ ‫‪-1/2‬‬ ‫‪-1/4‬‬ ‫‪3/4‬‬ ‫‪1‬‬ ‫‪2‬‬ ‫‪0‬‬ ‫‪1‬‬ ‫‪0‬‬ ‫‪0‬‬ ‫‪0‬‬ ‫‪1‬‬ ‫‪ Z‬شماره‬ ‫سطر‬ ‫‪0‬‬ ‫‪1‬‬ ‫‪01 2 0‬‬ ‫‪21 0‬‬ ‫متغیر های‬ ‫اساسی‬ ‫(‪Z‬‬ ‫جدول وقتی بهینه است که‪:‬‬ ‫‪1 3‬‬ ‫‪0‬‬ ‫‪2‬‬ ‫‪0‬‬ ‫متغیر ورودی و‬ ‫𝛉 جدول غیر بهینه است و‬ ‫گام ‪ 3‬و ‪)4‬برای‬ ‫خروجی خواهد بود‪.‬جدول زیر تکرار بعدی سیمپلکس را نشان می دهد‪.‬‬ ‫‪1‬‬ ‫‪4‬‬ ‫‪3/4‬‬ ‫‪2/4-1/4‬‬  ‫جدول نهایی برای‬ ‫اعداد سمت‬ ‫‪2‬‬ ‫راست‬ ‫‪234‬‬ ‫‪0‬‬ ‫‪2‬‬ ‫‪0‬‬ ‫‪2‬‬ ‫‪1‬‬ ‫𝛉‬ ‫‪1‬‬ ‫‪(1/332/3‬‬ ‫‪1/3‬‬ ‫‪-1/3‬‬ ‫‪2‬‬ ‫‪Z‬‬ ‫‪1‬‬ ‫‪(-2/331/3 θ‬‬ ‫‪2/3‬‬ ‫‪4/3‬‬ ‫‪0‬‬ ‫‪1‬‬ ‫‪0‬‬ ‫‪1‬‬ ‫‪0‬‬ ‫‪0‬‬ ‫متغیر های‬ ‫اساسی‬ ‫(‪Z‬‬ ‫شماره‬ ‫سطر‬ ‫‪0‬‬ ‫‪12‬‬ ‫‪2 02‬‬ ‫به دلیل اینکه با افزایش بیشتر 𝛉 مسأله هیچ گاه از حالت بهینگی‬ ‫خارج نمیشود ‪،‬مراحل عملیاتی پایان میابد‪.‬‬ ‫حالت دوم_تغییرات پارامتری در اعداد سمت راست‬ ‫در این حالت‬ ‫به صورت عبارت‬ ‫( 𝜽‪+‬‬ ‫تغییر میابد‪.‬‬ ‫خالصه رویه انجام عملیات برنامه ریزی پارامتری در مورد تغییرات‬ ‫پارامترهای اعداد سمت راست به شرح زیر است‪:‬‬ ‫گام‬ ‫‪ )1‬مسأله را به روش سیمپلکس به ازای‬ ‫𝛉 حل کنید‪.‬‬ ‫گام ‪ )2‬با استفاده از رویه تحلیل حساسیت ‪،‬تغییرات ناشی از وجود 𝛉‬ ‫را در ستون سمت راست وارد کنید‪.‬‬ ‫گام ‪ )3‬مقدار 𝛉 را آنقدر اضافه کنید تا مقدار یکی از متغییر های‬ ‫اساسی در ستون سمت راست منفی شود‪.‬‬ ‫گام ‪ )4‬از این متغییر به عنوان متغییر اساسی خروجی تکرار بعدی روش‬ ‫سیمپلکس ثانویه استفاده کنید و جواب بهینه جدید را به دست آورید و‬ ‫به گام ‪ 3‬بازگردید‪.‬‬ ‫*‬ ‫این شیوه تا جایی ادامه میابد تا سرانجام 𝛉 به مقداری میرسد که‬ ‫جواب یا وجود ندارد یا بدون تغییر باقی می ماند‪.‬‬ ‫مثال) مسأله زیر را در نظر بگیرید‪:‬‬ ‫‪2‬‬ ‫‪32‬‬ ‫‪1‬‬ ‫‪Max Z=3‬‬  ‫‪6‬‬ ‫‪2‬‬ ‫‪33‬‬ ‫‪1‬‬ ‫‪2‬‬ ‫‪4‬‬ ‫‪2‬‬ ‫‪+‬‬ ‫‪1‬‬ ‫‪2‬‬ ‫‪0‬‬ ‫‪1‬‬ ‫‪S,t.‬‬ ‫‪2‬‬ ‫اگر اعداد سمت راست به صورت پارامتری به شکل زیر تغییر یابند ‪،‬تمام‬ ‫جواب های بهینه را به دست آورید‪.‬‬ ‫𝛉 حل کنید‪.‬‬ ‫حل‪:‬گام ‪ )1‬مسأله را به ازای‬ ‫اعداد سمت راست‬ ‫‪13/2‬‬ ‫‪1‬‬ ‫‪3/2‬‬ ‫‪2‬‬ ‫‪1‬‬ ‫‪2‬‬ ‫‪1/4 4/4‬‬ ‫‪0‬‬ ‫‪0‬‬ ‫‪1/2‬‬ ‫‪-1/4‬‬ ‫‪-1/2‬‬ ‫‪3/4‬‬ ‫‪1‬‬ ‫‪1‬‬ ‫‪0‬‬ ‫‪1‬‬ ‫‪1‬‬ ‫‪0‬‬ ‫)‪ Z‬شماره‬ ‫سطر‬ ‫‪0‬‬ ‫‪01 2 0‬‬ ‫‪02 1 0‬‬ ‫گام ‪ )2‬با استفاده از روش تحلیل حساسیت ‪،‬تغییرات ناشی‬ ‫تغییراعداد سمت راست را در جدول بهینه اعمال کنید‪.‬‬ ‫‪13‬‬ ‫‪2‬‬ ‫=‬ ‫‪0‬‬ ‫‪1‬‬ ‫‪2‬‬ ‫‪3‬‬ ‫‪4‬‬ ‫‪1‬‬ ‫‪3‬‬ ‫‪2‬‬ ‫‪13/2 +‬‬ ‫‪1‬‬‫‪3/23‬‬ ‫‪1/4 4/4‬‬ ‫‪-1/2‬‬ ‫‪3/4‬‬ ‫‪4‬‬ ‫‪4‬‬ ‫‪0‬‬ ‫از‬ ‫‪0‬‬ ‫‪0‬‬ ‫‪1‬‬ ‫𝛉‬ ‫‪1‬‬ ‫‪0‬‬ ‫‪1‬‬ ‫‪0‬‬ ‫‪0‬‬ ‫‪1‬‬ ‫‪1‬‬ ‫‪2‬‬ ‫‪1‬‬ ‫‪4‬‬ ‫جدول نهایی بعد از انجام تغییرات برای‬ ‫اعداد سمت راست‬ ‫‪2‬‬ ‫‪1‬‬ ‫‪2‬‬ ‫‪1/2‬‬ ‫‪-1/4‬‬ ‫‪4‬‬ ‫‪1‬‬ ‫متغیر های‬ ‫اساسی‬ ‫(‪Z‬‬ ‫‪1‬‬ ‫‪0‬‬ ‫‪1‬‬ ‫متغیر های‬ ‫اساسی‬ ‫(‪Z‬‬ ‫)‪ Z‬شماره‬ ‫سطر‬ ‫‪0‬‬ ‫‪01 2 0‬‬ ‫‪02 1 0‬‬ ‫‪0‬‬ ‫جدول وقتی موجه و بهینه است که اعداد سمت راست همگی غیر منفی‬ ‫باشند‪:‬‬ ‫‪1‬‬ ‫‪0‬‬ ‫‪0‬‬ ‫‪1-‬‬  ‫متغیر‬ ‫𝛉 ‪ 1-𝛉 ،‬منفی شده و جدول غیر موجه و‬ ‫گام ‪ 3‬و‪ )4‬برای‬ ‫خروجی می باشد‪.‬جدول زیر سیمپلکس ثانویه مسأله فوق می باشد‪.‬‬ ‫جدول نهایی برای‬ ‫اعداد سمت راست‬ ‫‪9-3/2‬‬ ‫‪-232‬‬ ‫‪3- 2‬‬ ‫𝛉‬ ‫‪2‬‬ ‫‪0‬‬ ‫‪1‬‬ ‫‪0‬‬ ‫‪2‬‬ ‫‪1‬‬ ‫‪3/2‬‬ ‫‪-1‬‬ ‫‪1/2‬‬ ‫)‪ Z‬شماره‬ ‫سطر‬ ‫‪0‬‬ ‫‪1‬‬ ‫‪01 2 0‬‬ ‫‪02 1 0‬‬ ‫‪1‬‬ ‫‪4/2‬‬ ‫‪-2‬‬ ‫‪3/2‬‬ ‫‪0‬‬ ‫‪0‬‬ ‫‪1‬‬ ‫متغیر های‬ ‫اساسی‬ ‫(‪Z‬‬ ‫‪0‬‬ ‫جدول وقتی موجهه است که‪:‬‬ ‫‪0‬‬ ‫‪6‬‬ ‫‪θ‬‬ ‫‪1‬‬ ‫‪9-3/2‬‬ ‫‪0‬‬ ‫‪0‬‬ ‫‪-232‬‬ ‫‪2‬‬ ‫‪3-‬‬ ‫𝛉 جدول غیر موجهه است و متغیر خروجی می‬ ‫گام ‪ 3‬و‪ )4‬به ازای‬ ‫باشد‪.‬اما از آنجایی که در سطر دوم عدد منفی وجود ندارد نمی توان‬ ‫سیمپلکس ثانویه نوشت و روند برنامه ریزی پارامتری متوقف می گردد‪.‬‬ ‫حالت سوم_تغییرات پارامتری در ضرایب مربوط به متغیر های غیر اساسی‬ ‫) مربوط‬ ‫در این حالت فقط به بررسی تغییرات پارامتری در ضرایب فنی(‬ ‫) مربوط‬ ‫به یک متغیر غیر اساسی می پردازیم ‪.‬در مورد ضرایب فنی (‬ ‫به متغیر های اساسی ‪،‬مسأله پیچیده خواهد شد که مورد بحث قرار نمی‬ ‫گیرد‪.‬‬ ‫در این حالت‬ ‫به صورت ( 𝜽‪+‬‬ ‫)‬ ‫تغییر می کند‪.‬‬  ‫𝛉 حل می کنیم‪ .‬آنگاه با استفاده از تحلیل‬ ‫مسأله را به ازای‬ ‫حساسیت‪ ،‬تغییرات پارامترها را در جدول بهینه اعمال می کنیم‪.‬این‬ ‫تغییرات تنها می تواند بر بهینگی مسأله تأثیر بگذارد‪.‬‬ ‫*‬ ‫توجه‪:‬در این حالت نمی توان تمامی دامنه 𝛉 را به دست آورد زیرا با‬ ‫حصول اولین 𝛉 ‪𝛉 ،‬‬ ‫𝛉 ‪،‬بردار این متغیر اساسی شده ‪،‬لذا مشمول تحلیل‬ ‫اخیر نخواهد شد‪.‬‬ ‫مثال ) مسأله زیر را در نظر بگیرید‪.‬‬ ‫‪3‬‬ ‫‪40‬‬ ‫‪1 32 2 + 3‬‬ ‫‪60‬‬ ‫‪3‬‬ ‫‪3 1 32‬‬ ‫‪30‬‬ ‫‪1 34 2‬‬ ‫‪0‬‬ ‫اگر ضرایب فنی مربوط به متغیر های اساسی‬ ‫‪،‬تمام جواب های بهینه را به دست آورید‪.‬‬ ‫‪Max Z=3 1 32 2 34‬‬ ‫‪2‬‬ ‫‪1‬‬ ‫‪s.t‬‬ ‫‪3‬‬ ‫به شکل زیر تغییر یابند‬ ‫‪1‬‬ ‫‪= 3 2‬‬ ‫‪1 3‬‬ ‫حل‪:‬گام ‪ )1‬مسأله را به ازای‬ ‫جدول نهایی برای‬ ‫سمت‬ ‫‪2‬‬ ‫اعداد ‪3‬‬ ‫راست‬ ‫‪0‬‬ ‫‪160‬‬ ‫‪11‬‬ ‫‪21‬‬ ‫‪31‬‬ ‫𝛉 حل کنید‪.‬‬ ‫𝛉‬ ‫‪1‬‬ ‫‪2‬‬ ‫‪3‬‬ ‫متغیر های‬ ‫اساسی‬ ‫‪z‬‬ ‫‪z‬‬ ‫‪1‬‬ ‫‪1‬‬ ‫‪2‬‬ ‫‪1‬‬ ‫‪0‬‬ ‫‪0‬‬ ‫‪4‬‬ ‫‪4‬‬ ‫‪0‬‬ ‫‪-1/4‬‬ ‫½‬ ‫‪0‬‬ ‫‪1‬‬ ‫‪-1/4‬‬ ‫‪20‬‬ ‫‪30‬‬ ‫‪10‬‬ ‫‪0‬‬ ‫‪1‬‬ ‫½‬ ‫‪1‬‬ ‫‪0‬‬ ‫‪-2‬‬ ‫‪1‬‬ ‫‪0‬‬ ‫‪0‬‬ ‫‪0‬‬ ‫‪3/2‬‬ ‫‪2‬‬ ‫‪30‬‬ ‫‪0‬‬ ‫‪3‬‬  ‫گام ‪ )2‬با استفاده از رویه تحلیل حساسیت بعد اعمال تغییرات فوق‬ ‫عبارت خواهد شد از‪:‬‬ ‫مقدار‬ ‫‪=-‬‬ ‫‪1‬‬ ‫‪3‬‬ ‫‪1‬‬ ‫‪0 3 2‬‬ ‫‪1 3‬‬ ‫‪4‬‬ ‫‪2‬‬ ‫‪1‬‬ ‫‪3‬‬ ‫‪1‬‬ ‫‪1‬‬ ‫این مسأله وقتی بهینه است که ‪:‬‬ ‫‪4 3‬‬ ‫‪0‬‬ ‫‪4-3‬‬ ‫طبق توضیحات داده شده اولین 𝛉 بدست آمد ‪،‬با ادامه حل و تکرار بعدی‬ ‫متغیر اساسی خواهد شد که مشمول تحلیل اخیر نمی باشد‬ ‫سیمپلکس‬ ‫بنابراین حل مسأله همین جا متوقف می شود‪.‬‬ ‫حالت چهارم‪-‬تغییرات هم زمان در ضرایب تابع هدف ‪،‬اعداد سمت راست‪ ،‬ضرایب متغیر های تصمیم در محدودیت ها‬ ‫این حالت در واقع ترکیبی از سه حالت قبل می باشد‪.‬‬ ‫برای مطالعه بیشتر به کتاب مهرگان ص ‪ 222‬مراجعه فرمایید‪.‬‬