روش سیمپلکس

حل مسائل برنامه ریزی خطی به روش سیمپلکس

خصوصیات:

۱-    سیمپلکس در مسائل  maxقابل حل میباشد

۲-    مسائل سیمپلکس فقط معادلات را حل میکند

۳-    نقطه شروع سیمپلکس مبدا مختصات است

۴-    متغیر های اساسی در هر جدول میبایست یکه باشند یعنی خودش یک و اعداد بالا و پائین آن صفر باشد

مثال: مدل برنامه ریزی خطی زیر را به روش سیمپلکس حل کنید

برای حل مسئله باید ابتدا تابع هدف بشکل استاندارد درآید که برای این منظور باید آنرا مساوی صفر قرار دهیم.برای استاندراد کردن s.t به روش ذیل عمل می کنیم:

۱-    نامعادلاتی که بصورت ≥ هستند، با اضافه شدن متغیر کمکی s بصورت استاندارد درمی آیند

۲-    نامعادلاتی که بصورت ≤ هستند ، با اضافه شدن متغیر مصنوعی R و کم کردن S بشکل استاندارد درمی آیند

۳-    معادلاتی که بصورت = هستند فقط با اضافه شدن متغیر مصنوعی R بشکل استاندارد درمی آیند

				
					MAXZ=3X۱+۲X۲+۵x۳                                     MAXZ-3X۱-۲X۲-۵x۳ =۰
                                                                                     استاندارد
 s.t:  x۱+۲x۲ +x۳    ≤ ۴۳۰                            s.t:    x۱+۲x۲ +x۳  +s۱  = ۴۳۰
        ۳ x۱+    ۲x۳  ≤ ۴۶۰                                    ۳ x۱+    ۲x۳ +s۲ = ۴۶۰
        x۱+۴x۲         ≤ ۴۲۰                                   x۱+۴x۲       +s۳  = ۴۲۰' );
				
			

در ادامه تمامی متغیر های موجود در s.t را به سطر ۱ جدول ۱ انتقال میدهیم –  Z و متغیر های کمکی و مصنوعی که در s.t علامت مثبت دارند بعنوان متغیر های اساسی شناخته شده و به ستون ۱ جدول ۱ انتقال میدهیم- اعداد سمت راست تابع هدف و s.t را به ستون ۸ جدول ۱ انتقال میدهیم- اعدادسطر Z جدول ۱ ،ضرایب متغیرهای اساسی و غیر اساسی در تابع هدف می باشند( ضرایب متغیرهای کمکی S در تابع هدف صفرو ضرایب متغیرهای مصنوعی R،M  می باشد- اعدا د سطر S_۱, S_۲, S_۳ در جدول ۱ ، مربوط به ضرایب متغیرهای اساسی و غیر اساسی s.t می باشند.سطر s_۱ مربوط به محدودیت اول، سطر s_۲ مربوط به محدودیت دوم و سطر s_۳ مربوط به محدودیت سوم می باشد.

جدول۱

مقالات آماری

گام های حل مسئله:

۱-    برای انتخاب متغیر ورودی ،متغیر های اساسی باید یکه باشند(S_۱,S_۲,S_۳ در جدول یکه هستند)

۲-    در سطح(Z) منفی ترین عدد  بعنوان متغیر ورودی انتخاب می شود

۳-    اعداد سمت راست (RHS)  بر اعداد مثبت و غیر صفر متغیر ورودی تقسیم کرده و کوچکترین عدد بعنوان متغیر خروجی انتخاب می شود

۴-    از تلاقی متغیر ورودی و خروجی ،عدد ۲ بعنوان عدد لولا انتخاب شده یکه میشود

شروط یکه بودن :

۱-    عدد لولا باید ۱ باشد

۲-    اعداد  بالا و پائین عدد لولا باید صفر شود(با استفاده از اعمال سطری و ستونی ماتریس)

برای رفتن به جدول ۲ اعمال زیر را جهت یکه شدن انجام داده و حاصل را به جدول ۲ انتقال میدهیم

۱-    سطر S_۲ جدول ۱ را بر ۲ تقسیم کرده حاصل را به سطر X _۳ جدول ۲ انتقال میدهیم

۲-    سطر X_۳ در جدول۲ را در ۱- ضرب کرده باسطرS_۱ جدول۱ جمع کرده حاصل را به سطر S_۱ جدول ۲ انتقال می دهیم

۳-    سطر X_۳ در جدول۲ را در ۵ ضرب کرده باسطرZ جدول ۱ جمع کرده حاصل را به سطر Z جدول ۲ انتقال میدهیم

۴-    متغیر X_۲ بعنوان متغیر ورودی و S_۱ بعنوان متغیر خروجی انتخاب شده و۲ عدد لولا می باشد. مراحل یکه شدن را دوباره برای X_۲ انجام داده به جدول ۳ انتقال میدهیم.

جدول۲

جدول۳

چون سطر Z مثبت شده به جدول بهنیه رسیده ایم و جواب بهینه به صورت زیر از جدول بهینه استخراج می شود.

X_۱=۰    ,X_۲=۱۰۰   ,X_۳=۲۳۰     ,Z*=1350

آزمون های آماری

حل مسائل سیمپلکس به روش حداقل یا M بزرگ

مثال:

Minz = 20X_۱+۱۵X_۲                   

MAX-Z=-20 X_۱-۱۵X_۲  – MR_۱-MR_۲-MR_۳

MAX-Z+20 X_۱+۱۵X_۲+MR_۱+MR_۲+MR_۳=۰

   S.t:      X_۱+X_۲   ≥ ۲۰                          s.t:       X_۱+X_۲ –S_۱+R_۱  =۲۰

             ۲X_۱+X_۲≥ ۳۰                                        ۲X_۱+X_۲ –S_۲+R_۲= ۳۰

              X_۱+۲X_۲≥ ۵۰                                        X_۱+۲X_۲-S_۳+R_۳= ۵۰

چون محدودیت ها بصورت ≤ می باشند متغیرهای مصنوعی R_۱و R_۲و R_۳به محدودیتها اضافه میشوند و بدین ترتیب سیمپلکس از مبدا مختصات شروع می شودو جریمه ای به اندازه M دارد چون سیمپلکس در مبدا مختصات جواب می دهد در حا لیکه محدویت های مسئله در مبدا مختصات جواب ندارند.در واقع با افزودن متغیرهای مصنوعی R_۱و R_۲و R_۳خطوط مربوط به محدودیت ها بصورت فرضی به سمت مبدا مختصات میل داده می شود.اگر محدودیت بشکل= باشد فقط R اضافه میشود.

جدول۱

برای شروع باید متغیر های اساسی یکه باشند.همانطور که مشاهده می شود در جدول ۱ متغیر های اساسی R_۱و R_۲و R_۳یکه نیستند به همین منظور سطرهای R_۱و R_۲و R_۳بطور جداگانه در –M ضرب کرده ،با سطر Zجدول ۱ جمع کرده و حاصل رابه جدول ۲ انتقال میدهیم.

جدول۲

X_۲ وارد و R_۱خارج می شود.چون عدد لولا(۱ ) یکه میباشد ،سطر R_۱ به سطر X_۲در جدول ۳ منتقل می شود و در ادامه اعداد بالا و پائین عدد لولا با استفاده از عملیات سطری و ستونی به صفر تبدیل می شوند(شرط دوم یکه بودن)

جدول۳

جدول۴

جدول۵

چون سطر Z مثبت شده به جدول بهنیه رسیده ایم

X_۱=۱۰/۳  , X_۲=۷۰/۳  ,max-Z=-2500/6         minz=2500/6           کمترین هزینه

نرم افزار های آماری

حل مسائل سیمپلکس به روش دو مرحله ای یا دو فازی

۱-    در مرحله ۱ ضریب متغیرهای مصنوعی(R) در جدول اولیه در سطر R برابر ۱ است و بقیه ضرائب سطر R صفر میباشند.

۲-    پایان مرحله اول زمانی است که RHS(R)=0 و متغیر مصنوعی (R) در پایه نباشد

۳-    در مرحله اول min بهmax  تبدیل نمی شود .

۴-    در آغاز مرحله دوم تابع هدف استاندارد شده و متغیر های مصنوعی حذف می شوند.

۵-    در ادامه مسئله را به روش سیمپلکس معمولی حل میکنیم.

مثال: مدل برنامه ریزی خطی زیر را به روش دو مرحله ای حل کنید

Minz=20x_۱+۱۵x_۲+۲۵x_۳                                                     MinR=R_۲+R_۳

 s.t :          X_۱+۲X_۲+X_۳  ≤  ۲۰۰                       s.t:          X1+2X2+X3+S_۱      =  ۲۰۰

                X_۱+۲X_۲            ≥  ۵۰                                      X_۱+۲X_۲ –S_۲+R_۲           = ۵۰

                  ۲X_۱+۲X_۲+X_۳= ۱۰۰                                      ۲X_۱+۲X_۲+X_۳+R_۳        = ۱۰۰

جدول ۱

متغیرهای اساسی R_۲ و R_۳  باید یکه شوند به همین منظور سطرهای R_۲ و R_۳  جدول ۱ را در ۱- ضرب کرده با سطر  Z جدول ۱ جمع می کنیم و حاصل را به سطر Z  در جدول ۲ انتقال می دهیم .

جدول۲

مانند سیمپلکس معمولی ادامه می دهیم تا زمانیکه مقدار R در RHS مساوی صفر و متغیر مصنوعی در پایه نباشد.

جدول۳

جدول۴

جدول ۴ پایان مرحله اول را نشان می دهد زیرا مقدار Rدر RHS برابر صفر است و متغیر مصنوعی در پایه وجود ندارد.در ادامه برای شروع مرحله دوم ابتدا تابع هدف را استاندارد می کنیم ادامه مسئله را طبق فرایند سیمپلکس معمولی پی می گیریم.

تذکر : متغیرهای مصنوعی R_۲ و R_۳  در جدول ۵ قرار نمی گیرند.

MAX-Z=-20x_۱-۱۵x_۲-۲۵x_۳                   MAX(-Z)+20x_۱+۱۵x_۲+۲۵x_۳ =۰

جدول۵

X_۲ باید یکه شود.سطر X_۲ در جدول ۵ را در ۱۵- ضرب کرده با سطر Z  جدول ۵ جمع میکنیم و حاصل را به سطر Z جدول ۶ انتقال می دهیم.

جدول۶

X_۱=۰  , X_۲=۵۰    ,X_۳=۰    ,  MAX(-Z)=-750            MINZ=750

موارد خاص در برنامه ریزی خطی (سیمپلکس)

۱-    جواب بهینه چند گانه

الف- هرگاه ضریب یک متغیر غیر اساسی در سطر Z تابلوی بهینه سیمپلکس مساوی صفر باشد آن مسئله دارای جواب بهینه چند گانه است

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

مثال:

جدول بهینه

جدول بالا جدول بهینه می باشد . در سطر Z تابلوی فوق مقدار X_۱ صفر می باشد و از طرفی چون X_۱ متغیر غیر اساسی می باشد بنابراین مسئله دارای حالت خاص بهینه چند گانه می باشد.

۲-    فاقد ناحیه موجه

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

مثال:

MAXZ=2X_۱+۳X_۲

s.t:

X_۱+X_۲ ≤ ۱۰

X_۱+X_۲ ≥ ۲۰

جدول۱

جدول۲

جدول بهینه

اعداد سطر صفر(z ) همگی نامنفی می باشند بنابراین شرط بهینگی برقرار است اما چون متغیر مصنوعیR  در این جدول به عنوان متغیر اساسی باقیمانده و مقدار بزرگتر از صفر (۱۰) دارد بنابراین این مسئله فاقد منطقه موجه است.

۳-    ناحیه جواب بیکران

هر گاه در تابلوی آخر سیمپلکس امکان انتخاب متغیر ورودی وجود داشته باشد ولی متغیر خروجی بدلیل مثبت نبودن ضرایب ستون لولا قابل تعریف نباشند مدل برنامه ریزی خطی دارای جواب بیکران است.

مثال:

MAXZ=2X_۱+۳X_۲

s.t:

X_۱+X_۲ ≥ ۳

X_۱-۲X_۲ ≤ ۴

X_{۱ ,}X_۲ ≥ ۰                                                      جدول۱

 جدول۲

جدول۳

 متغیر کمکی S_۱ به عنوان متغیر ورودی انتخاب می شود اما انتخاب متغیر خروجی به دلیل مثبت نبودن ضرایب ستون لولا غیر ممکن است در نتیجه مدل دارای ناحیه جواب بیکران است.

۴-    جواب تبهگن (دمورژه)

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

مثال:

MAXZ=4X_۱+۶X_۲

s.t:

۶x_۱+۴x_۲ ≤ ۲۴

          X_۲  ≤  ۳

۵x_۱+۱۰x_۲ ≤ ۴۰

جدول۱

جدول۲

در جدول ۲ همانطور که مشخص است برای ورودی  X_۱دو متغیر خروجی  S_۱و S_۳ وجود دارد بنابراین حالت خاص تبهگن وجود دارد. اگر به دلخواه S_۳ بعنوان متغیر خروجی انتخاب شود در جدول ۳ داریم:

جدول۳

جدول۴

چون عدد سمت راست S_۲ (متغیر اساسی) در جدول ۴ (جدول بهینه) صفر است ،مسئله دارای حالت خاص تبهگن دائم است.

مثال:

MAXZ=2X_۱+X_۲

s.t:

۴X_۱+۳X_۲ ≤ ۱۲

۴X_۱+X_۲   ≤  ۸

۴X_۱-X_۲   ≤   ۸

جدول۱

جدول۲

همانطور که در جدول ۲ آمده است عدد سمت راست s_۳  صفر است و حالت خاص تبهگن وجود دارد اما چون صفر بر ۲- تقسیم نمی شود ،پس حالت خاص تبهگن موقت است و در جدول بعدی صفر موجود در اعداد سمت راست از بین میرود.

جدول بهینه