Online User اصطلاحات رایج در حل مدل برنامه ریزی خطی - مدیریت صنعتی Industrial Management

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

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

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

شاید در بسیاری از موارد اصطلاح «جواب» به معنای پاسخ نهایی یک مسئله باشد، اما در مباحث برنامه ریزی خطی این اصطلاح کاربرد کاملاً متفاوتی دارد. در برنامه ریزی خطی هر مقداری که به متغیرهای تصمیم داده شود بدون توجه به اینکه مطلوب است یا خیر، جواب نامیده می شود. انواع مختلف جواب را با استفاده از صفاتی که به این اصطلاح می دهند مشخص می کنند.

جواب موجه جوابی است که در همه محدودیت ها صدق کند و جواب غیرموجه جوابی است که حداقل از یکی از محدودیت ها انجراف داشته باشد و در آن صدق نکند. برای نمونه نقاط (2,3) و (4,1) در شکل 4 جواب های موجه هستند در حالیکه نقاط (-1,3) و (4,4) جواب های غیر موجه هستند. مجموعه همه جواب های موجه را فضای موجه می نامند. در شکل 4 منطقه هاشور خورده معادل فضای موجه است.

ممکن است مسئله ای دارای جواب موجه نباشد. در مثال شرکت ویندور اگر محدویت جدیدی با این عنوان اضافه کنیم که سود حاصل از محصولات جدید باید حداقل 50000 دلار در هفته باشد، رابطه جدیدی به صورت 3x1+5x2>=50 به مدل اضافه میگردد که در صورت رسم آن فضای موجه از بین می رود. به این معنی که هیچ ترکیبی از محصولات جدید نمی تواند در همه محدودیت ها صدق کند. این حالت در شکل 1 قابل مشاهده است.

شکل 1. مسئله شرکت ویندور با محدودیت جدید بدون فضای موجه

 در صورتی که مسئله دارای فضای موجه باشد، هدف یافتن بهترین جواب موجه است به طوریکه مقدار تابع هدف را به بهترین سطح در جهت مطلوب (ماکزیمم یا مینیمم) برساند. جواب بهینه یکی از جواب های موجه است که مطلوب ترین مقدار ممکن برای تابع هدف را ایجاد کند. مطلوب ترین مقدار ممکن عبارت است از بزرگترین مقدار در صورتی که مسئله ماکزیمم نمودن تابع هدف باشد و کمترین مقدار، اگر مسئله مینیمم نمودن تابع هدف باشد. بسیاری از مسائل تنها دارای یک جواب بهینه هستند ولی ممکن است مسئله ای دارای بیش از یک تابع هدف باشد. برای مثال اگر در مسئله شرکت ویندور سود حاصل از تولید یک دسته از محصول دوم به مقدار 2000 دلار تغییر یابد، تابع هدف نیز به شکل Z=3x1+2x2 تغییر خواهد کرد و بنابراین همه نقاطی که روی پارهخط بین (2,6) و (4,3) هستند جواب بهینه خواهند بود. این حالت را در شکل 2 می توانید ببینید. در اینگونه مسائل تعداد جواب های بهینه بینهایت است که مقادیر تابع هدف حاصل از آنها با هم برابر هستند و در اصطلاح می گویند مسئله دارای جواب بهینه چندگانه است.

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

حالت ممکن دیگر این است که مسئله دارای جواب بهینه نداشته باشد. این حالت زمانی رخ می دهد که یا مسئله اصلاً دارای فضای موجه نباشد و یا اینکه دارای فضای موجه باشد ولی محدودیت ها به گونه ای باشند که از افزایش مقدار تابع هدف در جهت مطلوب (مثبت یا منفی) جلوگیری نکنند و بتوان آن را تا بینهایت بهبود داد. به این مورد در اصطلاح شرایط z بیکران می گویند. برای نمایش ترسیمی این حالت فرض کنید دو محدودیت ساختاری مسئله شرکت ویندور حذف شوند. نتیجه مشابه شکل 3 خواهد شد:

 

شکل 3. مسئله شرکت ویندور بدون دو محدودیت ساختاری آخر و دارای Z بیکران

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

شکل 4. پنج نقطه مشخص شده جواب های CPF مسئله شرکت ویندور هستند.

 در ادامه درباره رابطه بین جواب بهینه و جواب CPF توضیح مختصری می دهیم. یک مسئله برنامه ریزی خطی را که دارای جوای های موجه و فضای موجه کراندار است را در نظر بگیرید. این مسئله لزوماً دارای چند جواب CPF و حداقل یک جواب بهینه است. در فصل های آینده ثابت خواهیم کرد که بهترین جواب CPF حتماً یکی از جواب های بهینه این مسئله است. بنابراین اگر مسئله تنها دارای یک جواب بهینه باشد، آن جواب همان بهترین جواب CPF است و اگر جزء مسائل دارای جواب بهینه چندگانه باشد، حداقل دو جواب CPF در بین جواب های بهینه وجود دارد. در مسئله شرکت ویندور تنها یک جواب بهینه، (2,6)، وجود دارد که با مشاهده شکل 4 مشخص می شود که این نقطه یکی از جواب های CPF است. در صورتی که شکل تغییر یافته این مسئله که دارای جواب بهینه چندگانه است را در نظر بگیریم که در شکل 2 نشان داده شده است، مشخص می شود که دو تا از جواب های بهینه (2,6) و (4,3) جواب CPF هستند.

پست مرتبط بعدی: فرضیات مدل برنامه ریزی خطی: تناسب

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