Online User موارد خاص روش سیمپلکس: جواب بهینه چندگانه - مدیریت صنعتی Industrial Management

مدیریت صنعتی Industrial Management

مدیریت صنعتی - تحقیق در عملیات - مدیریت تولید - ...

موارد خاص روش سیمپلکس: جواب بهینه چندگانه
نویسنده : محسن رحیمی - ساعت ۱٠:٤۸ ‎ب.ظ روز ۱۳٩٠/٦/٥
 

در مطالب مرتبط قبل عنوان شد که یک مسئله می تواند بیش از یک جواب بهینه داشته باشد. این مورد با مثالی که در شکل 1 ارائه شده است و با تغییر تابع هدف مسئله شرکت ویندور به صورت

بدست آمده است قبلاً نیز ارائه شد. هر نقطه واقع بر پاره خط بین نقاط (2,6) و (4,3) نقطه بهینه است. بنابراین همه جواب های بهینه، میانگین وزنی این دو جواب CPF بهینه هستند:

که وزن های w1 و w2 اعدادی هستند که در روابط زیر صدق کنند:

برای مثال با داشتن:

خواهیم داشت:

که یک جواب بهینه خواهد بود. به طور کلی هر میانگین وزنی از دو یا چند جواب که وزن های مورد استفاده غیر منفی باشند و مجموع آنها عدد یک گردد را ترکیب محدب (convex combination) این جوابها می نامند. بنابراین، هر جواب بهینه در این مثال ترکیبی محدب از نقاط (2,6) و (4,3) است.

شکل 1. وجود چندین جواب بهینه با تغییر تابع هدف مسئله شرکت ویندور

همانطور که در مطالب قبل هم اشاره شد، هر مسئله برنامه ریزی خطی با جواب چندگانه و منطقه موجه کراندار حداقل دارای دو جداب CPF بهینه است. هر جواب بهینه این مسئله ترکیبی محدب از این دو جواب CPF بهینه است. در نتیجه می توان گفت هر جواب بهینه ترکیبی محدب از جواب های BF بهینه است.

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

پس از آنکه جدول سیمپلکس یکی از جواب های BF بهینه را پیدا کرد به ترتیب زیر می توانید بقیه جواب های بهینه را در صورت وجود، بیابید:هر زمان که مسئله ای دارای بیش از یک جواب BF بهینه باشد، حداقل یکی از متغیرهای غیرپایه دارای ضریب صفر در سطر 0 جدول پایانی است. بنابراین افزایش هر یک از این متغیرهای غیر پایه باعث تغییر در Z نمی گردد. بنابراین جواب های BF بهینه دیگر مسئله را می توان با انجام یک تکرار دیگر در جدول سیمپلکس بدست آورد. در جدول جدید متغیر غیر پایه با ضریب صفر در سطر 0 به عنوان متغیر پایه ورودی انتخاب می شود. دقت داشته باشید اگر در این تکرار حالت عدم وجود متغیر پایه خروجی نیز برقرار باشد، به این معناست که منطقه موجه کراندار نیست و متغیر پایه ورودی می تواند تا بینهایت افزایش یابد بدون آنکه مقدار Z تغییر کند.

برای روشن تر شدن بحث مثالی که در شکل 1 ارائه شده است را در نظر بگیرید. روش سیمپلکس با سه جدول اول نشان داده شده در جدول 1 به اولین جواب BF بهینه می رسد و متوقف می گردد. با این حال بدلیل آنکه متغیر غیر پایه x3 دارای ضریب صفر در سطر 0 است یک تکرار اضافه که با نام extra در جدول 1 آورده شده است انجام می گیرد تا جواب BF بهینه بعدی نیز محاسبه شود. نتیجه نشان می دهد که دو جواب BF بهینه مسئله عبارتند از (2,6,2,0,0) و (4,3,0,6,0) که مقدار تابع هدف در این نقاط برابر و Z=18 است. همانطور که مشاهده می کنید جدول سیمپلکس نهایی نیز دارای متغیر غیر پایه x4 دارای ضریب صفر در سطر 0 است. این شرایط بیان می کند که این تکرار اضافی باعث تغییر تابع هدف نشده است. انتخاب x4 به عنوان متغیر پایه ورودی باعث بازگشت ما به جدول سوم (جدول قبل) خواهد شد. بنابراین این دو جواب تنها جواب هایBF بهینه هستند و دیگر جواب های بهینه ترکیب محدب این دو جواب هستند:

 جدول 1 . مجموعه کامل جداول سیمپلکس برای یک مسئله با جواب های بهینه چندگانه

 مطلب مرتبط بعدی: حل مسائل غیر استاندارد با روش سیمپلکس- مقدمه

مطلب مرتبط قبلی: موارد خاص روش سیمپلکس: عدم وجود متغیر پایه خروجی