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

خصوصیات:

۱-    سیمپلکس در مسائل  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۳ مربوط به محدودیت سوم می باشد.

جدول۱

متغیر های اساسی

X۱

X۲

X۳

S۱

S۲

S۳

R.H.S

Z

۰

۰

۰

۰

S۱

۱

۲

۱

۱

۰

۰

۴۳۰

S۲

۳

۰

۲

۰

۱

۰

۴۶۰

S۳

۱

۴

۰

۰

۰

۱

۴۲۰

 

مقالات آماری

 

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

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

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

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

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

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

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

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

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

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

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

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

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

جدول۲

 

X۱

X۲

X۳

S۱

S۲

S۳

R.H.S

Z

۹/۲

۰

۰

۵/۲

۰

۱۱۵۰

S۱

-۱/۲

۲

۰

۱

-۱/۲

۰

۲۰۰

X۳

۳/۲

۰

۱

۰

۱/۲

۰

۲۳۰

S۳

۱

۴

۰

۰

۰

۱

۴۲۰

جدول۳

 

X۱

X۲

X۳

S۱

S۲

S۳

R.H.S

Z

۴

۰

۰

۱

۲

۰

۱۳۵۰

X۲

-۱/۴

۱

۰

۱/۲

-۱/۴

۰

۱۰۰

X۳

۳/۲

۰

۱

۰

۱/۲

۰

۲۳۰

S۳

۲

۰

۰

۱

۱

۲۰

چون سطر 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 اضافه میشود.

جدول۱

 

X۱

X۲

S۱

S۲

S۳

R۱

R۲

R۳

R.H.S

Z

۲۰

۱۵

۰

۰

۰

M

M

M

۰

R۱

۱

۱

۰

۰

۱

۰

۰

۲۰

R۲

۲

۱

۰

۰

۰

۱

۰

۳۰

R۳

۱

۲

۰

۰

۰

۰

۱

۵۰

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

جدول۲

 

X۱

X۲

S۱

S۲

S۳

R۱

R۲

R۳

R.H.S

Z

۲۰-۴m

۱۵-۴m

m

m

m

۰

۰

۰

-۱۰۰m

R۱

۱

۱

۰

۰

۱

۰

۰

۲۰

R۲

۲

۱

۰

۰

۰

۱

۰

۳۰

R۳

۱

۲

۰

۰

۰

۰

۱

۵۰

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

جدول۳

 

X۱

X۲

S۱

S۲

S۳

R۱

R۲

R۳

R.H.S

Z

۵

۰

۱۵-۳m

m

m

-۱۵+۴m

۰

۰

-۳۰۰-۲۰m

X۲

۱

۱

۰

۰

۱

۰

۰

۲۰

R۲

۱

۰

۱

۰

۱

۰

۱۰

R۳

۰

۲

۰

۰

۱

۱۰

جدول۴

 

X۱

X۲

S۱

S۲

S۳

R۱

R۲

R۳

R.H.S

Z

۲۵/۲-۳/۲m

۰

۰

m

۱۵/۲-۱/۲m

m

۰

-۱۵/۲+۳/۲m

-۳۷۵-۵m

X۲

۱/۲

۱

۰

۰

-۱/۲

۰

۰

۱/۲

۲۵

R۲

۳/۲

۰

۰

۱/۲

۰

۱

-۱/۲

۵

S۱

-۱/۲

۰

۱

۰

-۱/۲

۰

۱/۲

۵

جدول۵

 

X۱

X۲

S۱

S۲

S۳

R۱

R۲

R۳

R.H.S

Z

۰

۰

۰

۵۰/۶

۲۰/۶

m

-۵۰/۶+m

-۲۰/۶+m

-۲۵۰۰/۶

X۲

۰

۱

۰

۱/۳

-۲/۳

۰

-۱/۳

۲/۳

۷۰/۳

X۱

۱

۰

۰

-۲/۳

۱/۳

۰

۲/۳

-۱/۳

۱۰/۳

S۱

۰

۰

۱

۱/۳

-۱/۳

-۱/۳

۱/۳

۲۰/۳

چون سطر 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۳        = ۱۰۰

جدول ۱

 

X۱

X۲

X۳

S۱

S۲

R۲

R۳

RHS

R

۰

۰

۰

۰

۰

۱

۱

S۱

۱

۲

۱

۱

۰

۰

۰

۲۰۰

R۲

۱

۲

۰

۰

۱

۰

۵۰

R۳

۲

۲

۱

۰

۰

۰

۱

۱۰۰

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

جدول۲

 

X۱

X۲

X۳

S۱

S۲

R۲

R۳

RHS

R

۰

۱

۰

۰

-۱۵۰

S۱

۱

۲

۱

۱

۰

۰

۰

۲۰۰

R۲

۱

۲

۰

۰

۱

۰

۵۰

R۳

۲

۲

۱

۰

۰

۰

۱

۱۰۰

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

جدول۳

 

X۱

X۲

X۳

S۱

S۲

R۲

R۳

RHS

R

۰

۰

۲

۰

-۵۰

S۱

۰

۰

۱

۱

۱

۰

۱۵۰

X۲

۱/۲

۱

۰

۰

-۱/۲

۱/۲

۰

۲۵

R۳

۱

۰

۱

۰

۱

۱

۵۰

جدول۴

 

X۱

X۲

X۳

S۱

S۲

R۲

R۳

RHS

R

۰

۰

۰

۰

۰

۱

۱

۰

S۱

۰

۰

۱

۰

۰

۱۰۰

X۲

۱

۱

۱/۲

۰

۰

۰

۱/۲

۵۰

S۲

۱

۰

۱

۰

۱

۱

۵۰

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

استاندارد

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

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

جدول۵

 

X۱

X۲

X۳

S۱

S۲

RHS

Z

۲۰

۱۵

۲۵

۰

۰

۰

S۱

۰

۰

۱

۰

۱۰۰

X۲

۱

۱

۱/۲

۰

۰

۵۰

S۲

۱

۰

۱

۰

۱

۵۰

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

جدول۶

 

X۱

X۲

X۳

S۱

S۲

RHS

Z

۵

۰

۳۵/۲

۰

۰

-۷۵۰

S۱

۰

۰

۱

۰

۱۰۰

X۲

۱

۱

۱/۲

۰

۰

۵۰

S۲

۱

۰

۱

۰

۱

۵۰

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


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

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

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

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

مثال:

جدول بهینه

RHS

S۲

S۱

X۲

X۱

۶۰

۰

۵

۰

۰

Z

۳

۰

-۱/۴

۱

۱

X۲

۲

۱

-۱/۲

۰

۱

S۲

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

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

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

مثال:

MAXZ=2X۱+۳X۲

s.t:

X۱+X۲ ≤ ۱۰

X۱+X۲ ≥ ۲۰

جدول۱

 

X۱

X۲

S۱

S۲

R۲

RHS

Z

۰

۰

M

۰

S۱

۱

۱

۱

۰

۰

۱۰

R۲

۱

۱

۰

۱

۲۰

جدول۲

 

X۱

X۲

S۱

S۲

R۲

RHS

Z

-M-2

-M-3

۰

M

۰

-۲۰M

S۱

۱

۱

۱

۰

۰

۱۰

R۲

۱

۱

۰

۱

۲۰

جدول بهینه

 

X۱

X۲

S۱

S۲

R۲

RHS

Z

۱

۰

۳+M

M

۰

۳۰-۱۰M

X۲

۱

۱

۱

۰

۰

۱۰

R۲

۰

۰

۱

۱۰

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

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

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

مثال:

MAXZ=2X۱+۳X۲

s.t:

X۱+X۲ ≥ ۳

X۱-۲X۲ ≤ ۴

X۱ ,X۲ ≥ ۰                                                      جدول۱

 

X۱

X۲

S۱

S۲

R۱

RHS

Z

۰

۰

M

۰

R۱

۱

۱

۰

۱

۳

S۲

۱

۰

۱

۰

۴

 جدول۲

 

X۱

X۲

S۱

S۲

R۱

RHS

Z

-M-2

-M-3

M

۰

۰

-۳M

R۱

۱

۱

۰

۱

۳

S۲

۱

۰

۱

۰

۴

جدول۳

 

X۱

X۲

S۱

S۲

R۱

RHS

Z

۱

۰

۰

۳+M

۹

X۲

۱

۱

۰

۱

۳

S۲

۳

۰

۱

۲

۱۰

 

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

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

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

مثال:

MAXZ=4X۱+۶X۲

s.t:

۶x۱+۴x۲ ≤ ۲۴

          X۲  ≤  ۳

۵x۱+۱۰x۲ ≤ ۴۰

جدول۱

 

X۱

X۲

S۱

S۲

S۳

RHS

Z

۰

۰

۰

۰

S۱

۶

۴

۱

۰

۰

۲۴

S۲

۰

۱

۰

۱

۰

۳

S۳

۵

۱۰

۰

۰

۱

۴۰

جدول۲

 

X۱

X۲

S۱

S۲

S۳

RHS

Z

۰

۰

۶

۰

۱۸

S۱

۶

۰

۱

۰

۱۲

X۲

۰

۱

۰

۱

۰

۳

S۳

۵

۰

۰

-۱۰

۱

۱۰

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

جدول۳

 

X۱

X۲

S۱

S۲

S۳

RHS

Z

۰

۰

۰

۴/۵

۲۶

S۱

۰

۰

۱

۸

-۶/۵

۰

X۲

۰

۱

۰

۱

۰

۳

X۱

۱

۰

۰

۱/۵

۲

جدول۴

 

X۱

X۲

S۱

S۲

S۳

RHS

Z

۰

۰

۱/۴

۰

۱/۲

۲۶

S۲

۰

۰

۱/۸

۱

-۳/۲۰

۰

X۲

۰

۱

-۱/۸

۰

۳/۲۰

۳

X۱

۱

۰

۲/۸

۰

-۱/۱۰

۲

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

مثال:

MAXZ=2X۱+X۲

s.t:

۴X۱+۳X۲ ≤ ۱۲

۴X۱+X۲   ≤  ۸

۴X۱-X۲   ≤   ۸

جدول۱

 

X۱

X۲

S۱

S۲

S۳

RHS

Z

۰

۰

۰

۰

S۱

۴

۳

۱

۰

۰

۱۲

S۲

۴

۱

۰

۱

۰

۸

S۳

۴

۰

۰

۱

۸

جدول۲

 

X۱

X۲

S۱

S۲

S۳

RHS

Z

۰

-۱/۲

۰

۱/۲

۰

۴

S۱

۰

۲

۱

۰

۴

X۱

۱

۱/۴

۰

۱/۴

۰

۲

S۳

۰

۰

۱

۰

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

جدول بهینه

 

X۱

X۲

S۱

S۲

S۳

RHS

Z

۰

۰

۱/۴

۱/۴

۰

۵

X۲

۰

۱

۱/۲

-۱/۲

۰

۲

X۱

۱

۰

-۱/۸

۳/۸

۰

۳/۲

S۳

۰

۰

۱

-۳/۲

۱

۴

 

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