Online User حل مسائل غیراستاندارد با سیمپلکس: وجود محدودیت های بزرگتر مساوی (روش M بزرگ) - مدیریت صنعتی Industrial Management

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

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

حل مسائل غیراستاندارد با سیمپلکس: وجود محدودیت های بزرگتر مساوی (روش M بزرگ)
نویسنده : محسن رحیمی - ساعت ۸:٠٦ ‎ب.ظ روز ۱۳٩٠/٧/٢
 

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

حل ترسیمی مثال مذکور در شکل 1 آورده شده است. سه خط رسم شده در شکل و دو محور افقی و عمودی، مرزهای محدودیت مسئله را تشکیل می دهند. نقاط تقاطع این مرزهای محدودیت جاب های گوشه ای مسئله هستند. از بین کلیه این نقاط تنها (6,6) و (7.5,4.5) جواب های موجه هستند و منطقه موجه نیز پاره خط حاصل از اتصال این دو نقطه است. جواب بهینه عبارت است از (x1,x2)=(7.5,4.5) که مقدار تابع هدف مربوط به آن Z=5.25 خواهد بود.

شکل 1 . حل ترسیمی مسئله بالا

به زودی نشان خواهیم داد که روش سیمپلکس چگونه به کمک متغیرهای مصنوعی این مسئله را حل می کند اما در ابتدا باید نحوه برخورد با محدودیت سوم را شرح دهیم.

راهکاری که باید مورد توجه قرار گیرد وارد کردن دو متغیر، یکی متغیر مازاد (Surplus variable) و دیگری متغیر مصنوعی است. متغیر مازاد در اینجا x5 است که به صورت

تعریف می شود و متغیر مصنوعی مربوطه را نیز با x6 (بار) نشان می دهیم. این متغیرها به صورت زیر به محدودیت سوم وارد می شوند.

 متغیر x5 را متغیر مازاد می نامند زیرا مقدار آن برابر است با اختلاف مقدار عبارت سمت راست و عبارت سمت چپ نامعادله و با اضافه نمودن آن به سمت چپ محدودیت نامعادله به معادله تبدیل می شود. پس از اضافه نمودن این متغیر و تبدیل محدودیت به یک محدودیت مساوی، بر اساس رویه توضیح داده شده در بخش مواجهه با محدودیت های مساوی، یک متغیر مصنوعی به این معادله وارد می شود.

پس از آنکه متغیر کمبود x3 وارد محدودیت اول گردید، یک متغیر مصنوعی، x4(بار) به محدودیت دوم که از نوع مساوی است اضافه می گردد و سپس به کمک روش M بزرگ مسئله مصنوعی زیر در فرمت افزوده حاصل می شود:

نکته ای که باید مورد توجه قرار گیرد این است که ضرایب متغیرهای مصنوعی در تابع هدف به جای M-، در این مورد M+ است زیرا مسئله حاضر از نوع حداقل سازی است. بنابراین اگر x4(بار) و/یا x6(بار) بزرگتر از صفر باشند مقدار جریمه بسیار بزرگ M+ از رسیدن تابع هدف به جواب بهینه جلوگیری می کند.

افزودن متغیر مصنوعی به مسئله باعث بزرگ تر شدن منطقه موجه می شود. وارد کردن متغیر مصنوعی x4(بار) که به نوعی نقش متغیر کمبود را برای محدودیت دوم بازی می کند باعث می شود نقاط(x1,x2) بتوانند زیر خط 0.5x1+0.5x2=6 نیز که در شکل 1 قابل مشاهده است، قرار گیرند. افزودن متغیرهای x5 و x6(بار) به محدودیت سوم مسئله اصلی و انتقال آنها به سمت راست این رابطه، معادله زیر را می دهد:

از آنجا که هر دو متغیر x5 و x6(بار) باید غیر منفی باشند، اختلاف آنها، می تواند مقداری مثبت یا منفی باشد. بنابراین 0.6x1+0.4x2 می تواند هر مقداری بگیرد. به این ترتیب می توان گفت محدودیت سوم در حقیقت از مسئله مصنوعی حذف می شود زیرا هیچ قیدی راجع به قرار گرفتن نقطه (x1,x2) بیان نمی کند. البته این محدودیت سوم در دستگاه معادله ها باقی می ماند زیرا بعد از اینکه در روشM بزرگ متغیر x6(بار) از پایه خارج و به صفر رسید این محدودیت تاثیرگذار می شود. نتیجتاً منطقه موجه برای مسئله مصنوعی نقاط مرزی و نقاط داخلی یک چهارضلعی با نقاط گوشه ای (7.5,4.5), (9,0), (0,0) و (0,12) است که می توانید در شکل 1 آن را تصور کنید.

با توجه به این منطقه موجه جدید، نقطه مبداء نیز موجه است و روش سیمپلکس می تواند نقطه (0,0) را به عنوان جواب CPF اولیه برای شروع استفاده کند. این نقطه معادل جواب BF اولیه

است. در حقیقت هدف اصلی ساختن مسئله مصنوعی، ایجاد شرایطی است که بتوان نقطه مبداء را به عنوان یک نقطه شروع موجه در روش سیمپلکس استفاده نمود. در مباحث آینده مسیر حرکت روش سیمپلکس از مبداء به نقطه بهینه را در هر دو مسئله اصلی و مصنوعی بررسی و مقایسه خواهیم کرد. ولی ابتدا به این سوال پاسخ خواهیم داد که برای حل مسائل حداقل سازی (MIN) چگونه باید از روش سیمپلکس استفاده کنیم؟

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

مطلب مرتبط قبلی: حل مسائل غیراستاندارد با روش سیمپلکس: منفی بودن اعداد سمت راست (RHS)