Online User حل مسائل غیر استاندارد با روش سیمپلکس- مقدمه - مدیریت صنعتی Industrial Management

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

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

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

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

تنها مشکل اساسی که در برخورد با مسائل غیر استاندارد ممکن است پیش بیاید تعیین جواب BF اولیه است. قبلاً به آسانی با قرار دادن متغیرهای کمبود به عنوان متغیرهای پایه اولیه، این جواب پایه اولیه بدست می آمد و برابر بود با مقادیر سمت راست محدودیت ها که غیر منفی نیز بودند. حال باید کار دیگری انجام داد. راهکار استانداردی که برای مواجهه با این موارد خاص مورد استفاده می گیرد عبارت است از تکنیک متغیرهای مصنوعی[1]. این تکنیک مسئله غیر استاندارد را به وسیله اضافه نمودن متغیرهای مصنوعی به محدودیت هایی که به آن نیاز دارند به مسئله جدیدی تبدیل می کند که شکل استاندارد دارد. این متغیرهای جدید با هدف تبدیل شدن به متغیر پایه اولیه به مدل اضافه می شوند. محدودیت های غیر منفی بودن برای این متغیرهای جدید به مدل اضافه می شود و در تابع هدف نیز اصلاحاتی صورت می گیرد که شامل افزودن جریمه هایی به آن به دلیل مثبت بودن متغیرهای مصنوعی است. در حقیقت متغیرهای مصنوعی متغیرهایی مجازی اند و باید از پایه خارج شوند، به همین دلیل تابع هدف مسئله جدید به گونه ای نوشته می شود که در صورت مثبت بودن یکی از متغیرهای مصنوعی مستحق جریمه شدن باشد. تکرارهای روش سیمپلکس به طور خودکار به سمت حذف متغیرهای مصنوعی (صفر کردن مقدار آنها) پیش می روند. زمانی که همه متغیرهای مصنوعی حذف شدند و جدول نهایی سیمپلکس نیز بهینه بود، جوابی که بدست می آید در حقیقت جواب مسئله اولیه نیز هست.

برای روشن تر شدن بحث در مطلب مرتبط بعدی موردی را در نظر می گیریم که تنها دلیل غیر استاندارد بودن مسئله آن حضور یک یا چند محدودیت مساوی باشد.



[1] Artificial-variable technique

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

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