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

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

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

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

تغییر شکل معادله (0) . پس از تبدیل شدن مسئله مصنوعی به شکل افزوده، دستگاه معادلات عبارت خواهد بود از:

 متغیرهای پایه مسئله بالا عبارتند از (x3,x4,x5-). با این حال دستگاه معادله بالا هنوز قالب مناسب برای عملیات حذف گوسی را ندارد زیرا یکی از متغیرهای پایه، x5-، دارای ضریب غیر صفر در معادله (0) است. یادآوری می کنیم که برای اینکه روش سیمپلکس قادر به اجرای تست بهینگی یا یافتن متغیر پایه ورودی باشد، باید همه متغیرهای پایه به لحاظ جبری از سطر (0) حذف شوند. با حذف ضرایب مربوط به متغیرهای پایه در سطر (0) ضرایب متغیرهای غیر پایه در این سطر به گونه ای تغییر می کنند که ضریب منفی هر متغیر غیرپایه نشان دهنده نرخ افزایش Z در صورت افزایش آن متغیر غیرپایه باشد.

برای حذف جبری x5- از معادله (0) لازم است x5- برابر معادله (3) را از معادله (0) کم کنیم:

بکارگیری روش سیمپلکس. همانطور که مشاهده می کنید معادله (0) جدید تنها شامل متغیرهای غیرپایه (x1,x2) است:

در رابطه بالا چون 3M+3>2M+5 است، (یادآوری میکنیم که M نماد عددی بسیار بزرگ است) افزایش x1 مقدار Z را با نرخ بیشتری نسبت به افزایش x2 ارتقاء می دهد و بنابراین متغیر x1 به عنوان متغیر ورودی انتخاب می شود. این انتخاب باعث می شود در تکرار اول از نقطه (0,0) به نقطه (4,0) حرکت کنیم و مقدار تابع هدف،Z، به مقدار 4(3M+3) افزایش یابد.

در دستگاه معادلات، نمادM تنها در عبارات معادله (0) ممکن است ظاهر شود. در نتیجه تنها برای آزمون بهینگی و تعیین متغیر پایه ورودی باید به این مقدار توجه نمود. یکی از راه های مواجهه با عبارات و محاسبات M دار، قرار دادن یک عدد بسیار بزرگ به جای آن و انجام محاسبات است. اما این روش حل ممکن است نتایج گمراه کننده ای به همراه داشته باشد و انجام آزمون بهینگی را کمی مشکل نماید. بنابراین بهتر است با اینگونه عبارات به صورت پارامتری برخورد شود. برای مثال معادله (0) را به صورت تابع خطی aM+b در نظر بگیرید و دو عبارت ضریب a و عبارت جمعی b را در محاسبات به طور جداگانه شرکت دهید. از آنجا که فرض کردیم M عددی بسیار بزرگ است، مقدار b در مقایسه با M بسیار ناچیز و قابل حذف است (در صورتی که a برابر با صفر نباشد). بنابراین در چنین مواردی برای آزمون بهینگی و همچنین برای انتخاب متغیر پایه ورودی مقدار a باید مورد نظر قرار گیرد، مگر در مواردی که حتی با در نظر گرفتن مقدار a همچنان چندین انتخاب وجود داشته باشد که در این صورت باید به مقدار b توجه شود.

با استفاده از این روند، جداول سیمپلکس مسئله به صورت جداول 1 خواهد شد. متغیر مصنوعی x5- در دو جدول اول متغیر پایه و در دو جدول نهایی متغیر غیر پایه است. بنابراین دو جواب BF اولیه برای مسئله مصنوعی، برای مسئله اصلی غیرموجه هستند و دو جواب نهایی برای هر دو مسئله موجه می باشند.

 

جدول 1. مجموعه جداول سیمپلکس مسئله

مثالی که در اینجا بررسی شد تنها دارای یک محدودیت معادله ای بود. اگر یک مدل برنامه ریزی خطی دارای بیش از یک معادله باشد، با هر یک به طور مجزا به شیوه توضیح داده شده برخورد می شود. دقت داشته باشید اگر محدودیتی به صورت معادله بود و عدد سمت راست آن نیز منفی بود ابتدا باید دو طرف معادله مذکور را در یک 1 - ضرب نمود.

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

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