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

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

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

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

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

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

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

برای یادآوری، مدل و گراف این مسئله در شکل آورده شده است. مرزهای پنج محدودیت و نقاط تقاطع آنها در این شکل علامت گذاری شده اند زیرا این موارد نقشی کلیدی در این روش دارند. هر مرز محدودیت[2] خطی است که دو نیم صفحه شامل نقاطی که در این محدودیت صدق می کنند و نقاطی که در آن صدق نمی کنند را از هم جدا می کند. نقاط تلاقی محدودیت ها را جواب های گوشه ای[3]  مسئله می نامند. نقطه هایی از این جواب ها را که در گوشه های فضای موجه قرار می گیرند، (4,3) , (2,6) , (0,6) , (0,0) و (4,0) جواب های گوشه ای موجه (CPF) می نامند و به بقیه نقطه های گوشه ای، (4,6) , (0,9) و (6,0) جواب های گوشه ای ناموجه[4] می گویند.

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

 در این مثال هر جواب گوشه ای در نقطه تلاقی 2 مرز محدودیت قرار می گیرد. برای یک مسئله برنامه ریزی خطی با n متغیر تصمیم، هر جواب گوشه ای در نقطه تلاقی n مرز محدودیت واقع می شود. البته در برخی از موارد ممکن است یک یا چند مرز محدودیت دیگر نیز از این نقطه تلاقی گذر کنند. همانطور که در شکل 1 مشخص است دو سر هر مرز محدودیت دو عدد CPF وجود دارد. برای هر مسئله برنامه ریزی خطی با n متغیر تصمیم به دو جواب CPF مجاور[5] یا همسایه می گویند اگر در n-1 مرز محدودیت شریک باشند. این دو جواب CPF مجاور با یک پاره خط که بر مرزهای محدودیت مشترک واقع شده اند به هم متصل می شوند. این پاره خط ها را در اصطلاح لبه[6] یا حاشیه های فضای موجه می نامند.

در مثال مورد بحث ما چون n=2 است، یک جفت جواب CPF را مجاور می گویند اگر در یک مرز محدودیت مشترک باشند. برای مثال (0,0) و (0,6) مجاور هستند زیرا در مرز محدودیت x1=0 مشترک می باشند. فضای موجه شکل 1 دارای 5 لبه، یعنی 5 پارخ خط است که مرزهای این فضا را تشکیل می دهند. دقت داشته باشید که از هر جواب CPF دو لبه می گذرد. بنابراین هر جواب CPF دارای دو جواب CPF مجاور است که در انتهای یکی از دو لبه گذرنده از آن قرار دارند. در جدول 1 برای هر جواب CPF، جواب های CPF مجاور آن مشخص شده است. در این جدول برای هر جواب CPF ذکر شده در ستون اول، جواب های مجاور آن در ستون دوم ارائه شده اند. دقت داشته باشید که دو جواب CPF آورده شده در ستون دوم با یکدیگر مجاور نیستند.

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

جواب های CPF

جواب های CPF مجاور با آن

(0,0)

(0,6) و (4,0)

(0,6)

(0,0) و (2,6)

(2,6)

(0,6) و (4,3)

(4,3)

(2,6) و (4,0)

(4,0)

(0,0) و (4,3)

 یکی از دلایل اهمیت تعیین جواب های CPF مجاور ویژگی خاصی از این جواب هاست که روش موثری را جهت بررسی اینکه یک جواب CPF جواب بهینه است یا خیر ارائه می دهد. این ویژگی را با عنوان آزمون بهینگی در زیر آورده ایم:

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

بنابراین در مثال بالا (2,6) باید جواب بهینه باشد زیرا مقدار Z مرتبط با آن برابر است با 36 که بزرگتر است از Z=30 برای (0,6) و Z=27 برای (4,3). در مطالب آینده به اثبات این ویژگی خواهیم پرداخت. این آزمون بهینگی یکی از اصول مورد استفاده روش سیمپلکس است. در مطلب مرتبط بعدی روش سیمپلکس را در مورد مسئله بالا بکار می گیریم.



[1] simplex method

[2] constraint boundary

[3] corner-point solutions

[4] corner-point infeasible solutions

[5] adjacent

[6] edge

پست مرتبط بعدی: مثالی برای دیدگاه هندسی روش سیمپلکس

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

http://imi.persianblog.ir/post/77/