به وبلاگ دانشجویان مدیریت خوش آمدید

تحقیق در عملیات 1

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

خصوصیات:

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

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

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

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

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

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

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

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

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

MAXZ=3X1+2X2+5x3                                     MAXZ-3X1-2X2-5x3 =0

                                                                                     استاندارد

 s.t:  x1+2x2 +x3    ≤ 430                            s.t:    x1+2x2 +x+s= 430

        3 x1+    2x3   ≤ 460                                    3 x1+    2x3 +s2  = 460           

        x1+4x2         ≤ 420                                   x1+4x2       +s3  = 420

در ادامه تمامی متغیر های موجود در s.t را به سطر 1 جدول 1 انتقال میدهیم –  Z و متغیر های کمکی و مصنوعی که در s.t علامت مثبت دارند بعنوان متغیر های اساسی شناخته شده و به ستون 1 جدول 1 انتقال میدهیم- اعداد سمت راست تابع هدف و s.t را به ستون 8 جدول 1 انتقال میدهیم- اعدادسطر Z جدول 1 ،ضرایب متغیرهای اساسی و غیر اساسی در تابع هدف می باشند( ضرایب متغیرهای کمکی S در تابع هدف صفرو ضرایب متغیرهای مصنوعی R،M  می باشد- اعدا د سطر S1, S2, S3  در جدول 1 ، مربوط به ضرایب متغیرهای اساسی و غیر اساسی s.t می باشند.سطر s1 مربوط به محدودیت اول، سطر s2 مربوط به محدودیت دوم و سطر s3 مربوط به محدودیت سوم می باشد.

جدول1

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

X1

X2

X3

S1

S2

S3

R.H.S

Z

-3

-2

-5

0

0

0

0

S1

1

2

1

1

0

0

430

S2

3

0

2

0

1

0

460

S3

1

4

0

0

0

1

420

 

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

1-    برای انتخاب متغیر ورودی ،متغیر های اساسی باید یکه باشند(S1,S2,S3 در جدول یکه هستند)

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

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

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

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

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

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

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

1-    سطر S2 جدول 1 را بر 2 تقسیم کرده حاصل را به سطر X 3 جدول 2 انتقال میدهیم

2-    سطر X3 در جدول2 را در 1- ضرب کرده باسطرS1 جدول1 جمع کرده حاصل را به سطر S1 جدول 2 انتقال می دهیم

3-    سطر X3 در جدول2 را در 5 ضرب کرده باسطرZ جدول 1 جمع کرده حاصل را به سطر Z جدول 2 انتقال میدهیم

4-    متغیر X2 بعنوان متغیر ورودی و S1 بعنوان متغیر خروجی انتخاب شده و2 عدد لولا می باشد. مراحل یکه شدن را دوباره برای X2 انجام داده به جدول 3 انتقال میدهیم.

جدول2

 

X1

X2

X3

S1

S2

S3

R.H.S

Z

9/2

-2

0

0

5/2

0

1150

S1

-1/2

2

0

1

-1/2

0

200

X3

3/2

0

1

0

1/2

0

230

S3

1

4

0

0

0

1

420

جدول3

 

X1

X2

X3

S1

S2

S3

R.H.S

Z

4

0

0

1

2

0

1350

X2

-1/4

1

0

1/2

-1/4

0

100

X3

3/2

0

1

0

1/2

0

230

S3

2

0

0

-2

1

1

20

 

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

X1=0    ,X2=100   ,X3=230     ,Z*=1350

 


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

مثال:

Minz = 20X1+15X2                     استاندارد               MAX-Z=-20 X1-15X2  - MR1-MR2-MR3

                                                                                  MAX-Z+20 X1+15X2+MR1+MR2+MR3=0

 

   S.t:      X1+X2   ≥ 20                          s.t:       X1+X2 –S1+R1  =20                                        

             2X1+X2≥ 30                                        2X1+X2 –S2+R2= 30

              X1+2X2≥ 50                                        X1+2X2-S3+R3= 50

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

جدول1

 

X1

X2

S1

S2

S3

R1

R2

R3

R.H.S

Z

20

15

0

0

0

M

M

M

0

R1

1

1

-1

0

0

1

0

0

20

R2

2

1

0

-1

0

0

1

0

30

R3

1

2

0

0

-1

0

0

1

50

برای شروع باید متغیر های اساسی یکه باشند.همانطور که مشاهده می شود در جدول 1 متغیر های اساسی R1و R2و R3یکه نیستند به همین منظور سطرهای R1و R2و R3بطور جداگانه در –M ضرب کرده ،با سطر Zجدول 1 جمع کرده و حاصل رابه جدول 2 انتقال میدهیم.

جدول2 

 

X1

X2

S1

S2

S3

R1

R2

R3

R.H.S

Z

20-4m

15-4m

m

m

m

0

0

0

-100m

R1

1

1

-1

0

0

1

0

0

20

R2

2

1

0

-1

0

0

1

0

30

R3

1

2

0

0

-1

0

0

1

50

X2 وارد و R1خارج می شود.چون عدد لولا(1 ) یکه میباشد ،سطر R1 به سطر X2در جدول 3 منتقل می شود و در ادامه اعداد بالا و پائین عدد لولا با استفاده از عملیات سطری و ستونی به صفر تبدیل می شوند(شرط دوم یکه بودن)

جدول3

 

X1

X2

S1

S2

S3

R1

R2

R3

R.H.S

Z

5

0

15-3m

m

m

-15+4m

0

0

-300-20m

X2

1

1

-1

0

0

1

0

0

20

R2

1

0

1

-1

0

-1

1

0

10

R3

-1

0

2

0

-1

-2

0

1

10

جدول4

 

X1

X2

S1

S2

S3

R1

R2

R3

R.H.S

Z

25/2-3/2m

0

0

m

15/2-1/2m

m

0

-15/2+3/2m

-375-5m

X2

1/2

1

0

0

-1/2

0

0

1/2

25

R2

3/2

0

0

-1

1/2

0

1

-1/2

5

S1

-1/2

0

1

0

-1/2

-1

0

1/2

5

جدول5

 

X1

X2

S1

S2

S3

R1

R2

R3

R.H.S

Z

0

0

0

50/6

20/6

m

-50/6+m

-20/6+m

-2500/6

X2

0

1

0

1/3

-2/3

0

-1/3

2/3

70/3

X1

1

0

0

-2/3

1/3

0

2/3

-1/3

10/3

S1

0

0

1

1/3

-1/3

-1

-1/3

1/3

20/3

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

X1=10/3  , X2=70/3  ,max-Z=-2500/6         minz=2500/6           کمترین هزینه

 


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

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

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

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

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

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

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

Minz=20x1+15x2+25x3                                                     MinR=R2+R3

                                                               استاندارد

 s.t :          X1+2X2+X≤  200                       s.t:          X1+2X2+X3+S1      =  200

                X1+2X2            ≥  50                                      X1+2X2 –S2+R2           = 50

                  2X1+2X2+X3= 100                                      2X1+2X2+X3+R3        = 100

جدول 1

 

X1

X2

X3

S1

S2

R2

R3

RHS

R

0

0

0

0

0

1

1

-

S1

1

2

1

1

0

0

0

200

R2

1

2

0

0

-1

1

0

50

R3

2

2

1

0

0

0

1

100

متغیرهای اساسی R2 و R3  باید یکه شوند به همین منظور سطرهای R2 و R3  جدول 1 را در 1- ضرب کرده با سطر  Z جدول 1 جمع می کنیم و حاصل را به سطر Z  در جدول 2 انتقال می دهیم .

جدول2

 

X1

X2

X3

S1

S2

R2

R3

RHS

R

-3

-4

-1

0

1

0

0

-150

S1

1

2

1

1

0

0

0

200

R2

1

2

0

0

-1

1

0

50

R3

2

2

1

0

0

0

1

100

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

جدول3

 

X1

X2

X3

S1

S2

R2

R3

RHS

R

-1

0

-1

0

-1

2

0

-50

S1

0

0

1

1

1

-1

0

150

X2

1/2

1

0

0

-1/2

1/2

0

25

R3

1

0

1

0

1

-1

1

50

جدول4

 

X1

X2

X3

S1

S2

R2

R3

RHS

R

0

0

0

0

0

1

1

0

S1

-1

0

0

1

0

0

-1

100

X2

1

1

1/2

0

0

0

1/2

50

S2

1

0

1

0

1

-1

1

50

 

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

استاندارد

تذکر : متغیرهای مصنوعی R2 و R3  در جدول 5 قرار نمی گیرند.

MAX-Z=-20x1-15x2-25x3                   MAX(-Z)+20x1+15x2+25x3 =0         

جدول5

 

X1

X2

X3

S1

S2

RHS

Z

20

15

25

0

0

0

S1

-1

0

0

1

0

100

X2

1

1

1/2

0

0

50

S2

1

0

1

0

1

50

 

X2 باید یکه شود.سطر X2 در جدول 5 را در 15- ضرب کرده با سطر Z  جدول 5 جمع میکنیم و حاصل را به سطر Z جدول 6 انتقال می دهیم.

جدول6

 

X1

X2

X3

S1

S2

RHS

Z

5

0

35/2

0

0

-750

S1

-1

0

0

1

0

100

X2

1

1

1/2

0

0

50

S2

1

0

1

0

1

50

 

X1=0  , X2=50    ,X3=0    ,  MAX(-Z)=-750            MINZ=750


                                                        

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

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

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

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

مثال:

جدول بهینه

RHS

S2

S1

X2

X1

 

60

0

5

0

0

Z

3

0

-1/4

1

1

X2

2

1

-1/2

0

1

S2

 

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

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

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

مثال:

MAXZ=2X1+3X2

s.t:

X1+X2 ≤ 10

X1+X2 ≥ 20

جدول1

 

X1

X2

S1

S2

R2

RHS

Z

-2

-3

0

0

M

0

S1

1

1

1

0

0

10

R2

1

1

0

-1

1

20

جدول2

 

X1

X2

S1

S2

R2

RHS

Z

-M-2

-M-3

0

M

0

-20M

S1

1

1

1

0

0

10

R2

1

1

0

-1

1

20

جدول بهینه

 

X1

X2

S1

S2

R2

RHS

Z

1

0

3+M

M

0

30-10M

X2

1

1

1

0

0

10

R2

0

0

-1

-1

1

10

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

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

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

مثال:

MAXZ=2X1+3X2

s.t:

X1+X2 ≥ 3

X1-2X2 ≤ 4

X1 ,X2 ≥ 0                                                      جدول1

 

X1

X2

S1

S2

R1

RHS

Z

-2

-3

0

0

M

0

R1

1

1

-1

0

1

3

S2

1

-2

0

1

0

4

 جدول2

 

X1

X2

S1

S2

R1

RHS

Z

-M-2

-M-3

M

0

0

-3M

R1

1

1

-1

0

1

3

S2

1

-2

0

1

0

4

جدول3

 

X1

X2

S1

S2

R1

RHS

Z

1

0

-3

0

3+M

9

X2

1

1

-1

0

1

3

S2

3

0

-2

1

2

10

 

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

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

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

مثال:

MAXZ=4X1+6X2

s.t:

6x1+4x2 ≤ 24

          X≤  3

5x1+10x2 ≤ 40

جدول1

 

X1

X2

S1

S2

S3

RHS

Z

-4

-6

0

0

0

0

S1

6

4

1

0

0

24

S2

0

1

0

1

0

3

S3

5

10

0

0

1

40

جدول2

 

X1

X2

S1

S2

S3

RHS

Z

-4

0

0

6

0

18

S1

6

0

1

-4

0

12

X2

0

1

0

1

0

3

S3

5

0

0

-10

1

10

در جدول 2 همانطور که مشخص است برای ورودی  X1دو متغیر خروجی  S1و S3 وجود دارد بنابراین حالت خاص تبهگن وجود دارد. اگر به دلخواه S3 بعنوان متغیر خروجی انتخاب شود در جدول 3 داریم:

جدول3

 

X1

X2

S1

S2

S3

RHS

Z

0

0

0

-2

4/5

26

S1

0

0

1

8

-6/5

0

X2

0

1

0

1

0

3

X1

1

0

0

-2

1/5

2

جدول4

 

X1

X2

S1

S2

S3

RHS

Z

0

0

1/4

0

1/2

26

S2

0

0

1/8

1

-3/20

0

X2

0

1

-1/8

0

3/20

3

X1

1

0

2/8

0

-1/10

2

 

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

مثال:

MAXZ=2X1+X2

s.t:

4X1+3X2 ≤ 12

4X1+X2   ≤  8

4X1-X2   ≤   8

جدول1

 

X1

X2

S1

S2

S3

RHS

Z

-2

-1

0

0

0

0

S1

4

3

1

0

0

12

S2

4

1

0

1

0

8

S3

4

-1

0

0

1

8

جدول2

 

X1

X2

S1

S2

S3

RHS

Z

0

-1/2

0

1/2

0

4

S1

0

2

1

-1

0

4

X1

1

1/4

0

1/4

0

2

S3

0

-2

0

-1

1

0

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

جدول بهینه

 

X1

X2

S1

S2

S3

RHS

Z

0

0

1/4

1/4

0

5

X2

0

1

1/2

-1/2

0

2

X1

1

0

-1/8

3/8

0

3/2

S3

0

0

1

-3/2

1

4

 

+ نوشته شده در  شنبه چهارم آبان 1392ساعت 9:45  توسط علیرضا  |