بخشی از مقاله
روش سیمپلکس
ضرورت :
روش ترسیمی تنها برای حل مسائل برنامه ریزی خطی دو یا حداکثر سه متغیری می توان استفاده کرد. در عمل استفاده از مدل برنامه ریزی خطی برای حل مسائل واقعی، مستلزم بکارگیری تعداد زیادی متغیر و محدودیت است. بنابراین، به روش کاراتری به نام سیمپلس نیاز است.
روش سیمپلکس در سال 1947 به وسیلۀ جرج بی دانتزیگ برای حل مسائل برنامه ریزی خطی ایجاد شد. این روش یک الگوریتم است.
فرم استاندارد :
فرم استاندارد برای ایجاد رویدادی عمومی و هماهنگ در حل مسائل بکار گرفته می شود.
1 ) تابع هدف مسأله باید به صورت max باشد.
2 ) تمامی محدودیتها به صورت کوچکتر یا مساوی باشند.
3 ) همگی متغیرها غیر منفی باشند.
سیمپلکس عمدتاً عملیات خود را از مبدأ مختصات شروع می کند و سپس به نقطۀ گوشۀ موج مجاور که مقدار تابع هدف را بهبود بخشد و حرکت خواهد کرد. این کار، تا رسیدن به نقطۀ موج از نقاط موج اطرافش بهتر باشد، ادامه می دهد.
مبانی روش سیمپلکس با حل یک مسئله نمونه :
مسئله A ) به منظور تولید دو کالای مختلف، از چهار منبع c , b , a استفاده می شود. کل مقادیر موجود از هر یک از عوامل تولید فوق عبارتند از d = 32 , c = 22 , b = 7 , a = 9 تولید هر واحد از کالای اول مستلزم مورد ادامه از عامل a ، 2 واحد از عامل c و ادامه از عامل d می باشد. برای
تولید هر واحد از کالای دوم باید 1 واحد از عامل b و ادامه از عامل c و 4 واحد از عامل d را بکار برد.
سود خالص تولید کننده از تولید هر واحد کالای اول و دوم به ترتیب 1 و 2 می باشد. از هر نوع کالا چه مقدار بایستی تولید شود تا سود حداکثر گردد :
قدم اول : مدلسازی
قدم دوم : تبدیل محدودیتها به مبادله :
برای تبدیل محدودیتها به معادله برای اینکه بتوانیم مسأله به روش سیمپلکس حل نمائیم نیاز است که با استفاده از متغیرهای برابر ساز (که با S نشان داده می شود) محدودیتها را به معادلات تبدیل کنیم. روش به صورت زیر است :
حالت محدودیتهای کوچکتر مساوی :
کمبود S : Slack
حالت محدودیتهای بزرگتر یا مساوی :
مازاد S : Surplus
قدم سوم : شروع تکرار :
• در روش سیمپلکس همدان از مبدأ مختصات شروع می کنیم. مبدأ مختصات در منطقه موجود جواب قرار دارد.
• در سیمپلکس درون متغییر داریم : 1 ) متغیر اساسی : متغیرای که دارای مقدار چند صفر باشد . 2 ) متغیر غیراساسی : متغیرهای که متواضعند دارند.
• در شروع مراحل تکرار سیمپلیکس : مقادیر متغیرهای تصمیم یعنی x 4 (x1 و x2 در این مسأله) صفر بالا و مقادیر متغیرهای کمکی (S4 , S3 , S2 , S1 در این مسأله) غیر صفر می باشند. بنابراین XDX1 متغیرهای غیراساسی بوده و S 1,2,3,4 متغیرهای اساسی شروع مسأله می باشند.
• در منطقۀ مبدأ مختصات، مبادلات معرفی (معادلاتی که نقاط واگذار شده تمرین می کنند.) می باشد.
• در مبداء مختصات باید جواب بهینه یعنی حداکثر سود بخواهیم رسید پس به دنبال جواب گوشه موج دیگری که بتواند تابع هدف max کند می گردیم.
جدول سیمپلکس در نقطۀ گوشه جواب موج مبداء مختصات
حداکثر اعداد سمت راست S4 S3 S2 S1 X2 X1 Z شماره سطر متغیرهای اساسی
0 0 0 0 0 3- 1- 1 0 Z
متغیری 9 0 0 0 1 0 1 0 1 S1
خروجی 7 0 0 1 0 1 0 0 2 S2
22 0 1 0 0 1 2 0 3 S3
32 1 0 0 0 4 1 0 4 S4
0 = Z 32 = S4 22 = S3 7 = S2 9 = S1 0 = X1 0 = X1
این جدول مربوط به مبدأ مختصات است. چون x1 و x2 برابر صفر است. در این منطقه با حل مبادلات تبدیل شده محدودیتها مقادیر 32 = S4 22 = S3 7 = S2 9 = S1 خواهد شد. این مقادیر نشان امیدانسیت که در صورت عدم تولید، سود صفر خواهد شد و از بالا a = a عدد، از بالا 7 , b عدد ، از بالا 2c و از حالا a 31 عدد باقی خواهد ماند.
قدم چهارم : امتحان کردن گوشه موج مجاور :
در ادامه اولین سوابق که به ذهن می رسد اینست که با منابع موجود، اگر قرار باشد در این مرحله تنها به تولید یک محصول اقدام شود، کدام محصول انتخاب خواهد شد. به عنوان یک قرارداد بهتر است مخصوص تولید را که تولید هر واحد آن سود بیشتری را عاید کند.
برای این منظور باید گوشه موج مجاور را امتحان نمائیم. همانطور که در بالا قید شده گوشه ای را اول انتخاب خواهیم کرد که احتمال سود بیشتری را داشته باشند.
با تبدیل یکی از متغیرهای غیراساسی براساس (متغیر ورودی) در مقابل تبدیل یکی از متغیرهای اساسی به غیراساسی (متغیر خروجی) می توان از جواب اساسی موج فعلی به یک جواب اساسی موج جدید رسید. و این تعریف تفاوت دو جواب اساسی موج مجاور، در تعویض یکی از متغیرهای اساسی آنها به متغیری غیراساسی می باشد.
متغیر ورودی همان محصولی است که برای ما سود بیشتری خواهد داشت. در این مثال x1 متغیر ورودی خواهد شد.
ظاهراً با تولید محصول دوم (x1 ) که سود دهی بیشتری خواهم داشت. ولی تولید این محصول وابسته به میزان نتایج موجود می باشد. برای اینکه بدانیم کدام منبع در میزان تولید محصول ها (درونی) تعیین کننده است، ادوار سمت راست را بر مقادیر ستون زیر x1 (ستون اولا) تقسیم کرده و در قسمت حداکثر ما می نویسیم. کمترین مقدار در ستون (حداکثر) فاینگر آن منبع است که در تعیین میزان تولید محصول دوم تعیین کننده است. با این منبع را به عنوان خروجی درنظر می گیریم و بر مدار سطر فراگیری بین محصول خواهی کنیم. (سطر اولا)
حداکثر اعداد سمت راست S4 S3 S2 S1 X2 X1 Z شماره سطر متغیرهای اساسی
- 0 0 0 0 0 3- 1- 1 0 Z
9 0 0 0 1 0 1 0 1 S1
7 7 0 0 1 0 1 0 0 2 S2
22 22 0 1 0 0 1 2 0 3 S3
8 32 1 0 0 0 4 1 0 4 S4
حال جواب اساسی موج گوشه مجاور را امتحان کرده و مقدار آن را به دست می آوریم. برای این منظور متغیر اساسی را با متغیر غیراساسی تعویض می کنیم. سپس سطر دولای جدید به دست می آوریم. متغیر اساسی جدید می باشد.
برای آنکه متغیر اساسی جدید از سایر معاملات خونه شود، در سطر (به استثنای سطر اول) را به ترتیب زیر جدول جدید تغییر می دهیم.
سطر اولی جدید × (ضریب ستون اول) – سطر قدیم = سطر جدید.
[0 0 0 0 0 0 3 1- 1 ] : سطر صفر
[7 0 0 1 0 1 0 0] 3
ـــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ
[21 0 0 3 0 0 1- 1]
چون ضریب ستون اول صفر می باشد سطر جدید مانند سطر قدیم است : سطر 1
[22 0 1 0 0 1 2 0] : سطر 2
[7 0 0 1 0 1 0 0] 1 –
ـــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ
[15 0 1 1- 0 0 2 0]
[32 1 0 0 0 4 1 0] : سطر 3
[7 0 0 1 0 1 0 0] 4
ـــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ
[4 1 0 4- 0 0 1 0]
دستور توقف :
اگر تمامی ضرایب سطر، مقادیری غیرمستقر باشند، آن وقت جواب اساسی موج به دست آمده بهینه است.
حداکثر اعداد سمت راست S4 S3 S2 S1 X2 X1 Z شماره سطر متغیرهای اساسی
- 21 0 0 3 0 0 1- 1 0 Z
9 9 0 0 0 1 0 1 0 1 S1
7 0 0 1 0 1 0 0 2 S2
7 15 0 1 1- 0 0 2 0 3 S3
4 4 1 0 4- 0 0 1 0 4 S4
21 = Z 4 = S4 15= S3 9 = S1 7 = X1
قدم پنجم : امتحان کردن جواب اساسی گزینه مجاور دیگر :
چون مقادیر سطر صفر، دارای رقم متغیر است، لذا می بایست به دنبال جواب بهینه دیگر باشیم چرا که جواب قبلی بهینه تر باشد.
بسیاری x1 محصولی می باشد که با تولید آن احتمال افزایش سود بیشتر خواهد شد لذا x1 به عنوان متغیر ورودی انتخاب می شود و با تقسیم اعداد سمت راست به مقادیر متون x1 حداکثر، به دست می آید. ماده شماره 4 متغیر d تعیین کننده می باشد لذا خروجی خواهد شد. چرا که کمترین مقدار را دارد.
روند قبلی تکرار و جدول جدید ایجاد می شود.
حداکثر اعداد سمت راست S4 S3 S2 S1 X2 X1 Z شماره سطر متغیرهای اساسی
25 1 0 1- 0 0 0 1 0 Z
25/1 5 1- 0 4 1 0 0 0 1 S1
7 7 0 0 1 0 1 0 0 2 X2
1 7 2- 1 7 0 0 0 0 3 S3
- 4 1 0 4- 0 0 1 0 4 X1
تکرار مراحل
حداکثر اعداد سمت راست S4 S3 S2 S1 X2 X1 Z شماره سطر متغیرهای اساسی
26 7/5 7/1 0 0 0 0 1 0 Z
1 2/1- 7/4- 0 1 0 0 0 1 S1
6 7/2 7/1- 0 0 1 0 0 2 X2
1 7/2- 7/1 1 0 0 0 0 3 S3
8 7/1- 7/4 1 0 0 1 0 4 X1
1 = S2 1= S1 26 = Z 6 = X2 8 = X1
فرمهای غیراستاندارد :
1 ) مسائل با تابع هدف حداقل :
با ضرب کردن تابع هدف در یک متغیر، تابع هدف حداقل را به حداکثر تبدیل می کنیم و مسأله را به روش قبلی حل می نماییم. در این حالت برای انتخاب متغیر ورودی و یا توقف عملیات، سطر صفر سیمپلکس را بزرگترین عدد مثبت و عدم وجود عدد مثبت در سطر صفر آخرین جدول سیمپلس خواهد بود.
4 ) محدودیتهای به صورت بزرگتر یا مساوی و یا مساوی :
در محدودیتهای بزرگتر یا مساوی از آنجا که متغیرهای کمکی از سمت چپ نامعادله بایستی کم کرد تا حالت تساوی در محدودیت برقرار گردد، متغیرهای کمکی را نمی توان به عنوان یک متغیر اساسی برای شروع مسأله درنظر گرفت چون این متغیر دارای ضریب 1- می باشد و این به جهت خارج بودن از مبداء مختصلت از منطقه ی موج، یا نداشتن جواب موج ابتدایی است.
در محدودیتهایی که صورت تساوی دارند نیز از آنجا که متغیرهای کمکی به کار گرفته نمی شوند، در شروع عملیات این محدودیتها فاقد متغیر اساسی می باشد.
روش M بزرگ یا روش متغیرهای مصنوعی Artificial Varietals :
در روش M بزرگ از متغیرهای مصنوعی غیرمتغیر جدیدی برای رفع مشکل محدودیتهای بزرگتر یا مساوی استفاده کرد. متغیرهای مصنوعی فقط جنبه های محاسباتی دارند و فاقد مصداق و معنی فیزیک می باشند. در صورتی که یک مسأله دارای منطقه موج و جوراب بهینه باشد، مقدار متغیر مصنوعی که با R نشان داده می شود، در جدول نهایی به صفر می رسد و غیر صفر شدن این متغیر در جدول نهایی به معنی فاقد منطقه موج بودن مسأله است.
مسأله 1 )
با اضافه کردن R ، مبدأ مختصات در منطقه موج بزرگ شده ناشی از اضافه شدن R قرار گرفته و می تواند به عنوان یک جواب اساسی موج ابتدایی مورد استفاده قرار گیرد. با بزرگ شدن منطقه موج، این احتمال را به وجود می آورد که جواب بهینه بر روی یکی از نقاط گوشه ای که در منطقه موج ناشی از اضافه شدن R قرار دارد، واقع گردد که چون در منطقه موج مسأله اصلی قرار ندارند، جوابی غیرموج برای این مسأله خواهد بود. برای جلوگیری از این کار از مقدار تابع هدف مقدار MR از سمت راست تساوی تابع هدف max ( و اضافه کردن MR به سمت راست تساوی تابع هدف min ) بسته می شود.
به اضافه کردن R و با افزایش آن از صفر مرتباً این خط رو به پایین حرکت کرده و منطقه موج بزرگتر می شود.
0 = x2 + MR 2 – x1 3 – 2 m تابع هدف جدید
حداکثر اعداد سمت راست S4 S2 S1 X2 X1 Z شماره سطر متغیرهای اساسی
0 M 0 0 2- 3- 1 0 Z
1 4 1 0 1 1 2 0 1 S1
0 6 0 1- 0 2 1 0 2 R2
M 6- 0 M 0 (M -3-) (M -3-) 1 0 Z
4 4 0 0 1 1 2 0 1 S1
3 6 0 1- 0 2 1 0 2 R
6 1+M 1- 0 0 2- 1 0 Z
3/2 1 2/1- 2/1 1 0 2/3 0 1 S1
6 3 2/1 2/1- 0 1 2/1 0 2 X1
3/71 3/+M 3/1- 3/4 0 0 1 0 Z
3 3/2 3/1- 3/1 3/2 0 1 0 1 X1
- 3/22 3/2 3/2- 3/1- 1 0 0 2 X2
8 M 0 2 0 1 1 0 Z
2 1- 1 2 0 3 0 1 S2
4 0 0 1 1 2- 0 2 X2
2 = S2 0= S1 8= Z 4= X2 0= X1
روش دو مرحله ای :
روش M بزرگ در محاسبات کامپیوتری از ثبات کمتری برخوردار است.
1 ) پیدا کردن جواب موج ابتدایی (با استفاده از تابع هدف مصنوعی)
2 ) پیدا کردن جواب بهینه مسأله (با استفاده از تابع هدف اصلی مسأله)
مسأله 2 :
مرحله اول :
در پایان مرحله اول در صورتی که مسأله دارای جواب بهینه باشد مقدار W به صفر می رسد و با به صفر رسیدن W و حذف متغیرهای مصنوعی از ستون متغیرهای اساسی جدول سیمپلیکس، جواب گوشه به دست آمده نشانۀ رسیدن به منطقه موج می باشد.
چون تمامی اعداد سطر صفر در آخرین جدول غیرمتغیر هستند، شرط بهینگی برقرار می باشد.
حداکثر اعداد سمت راست R2 S2 S1 X2 X1 W شماره سطر متغیرهای اساسی
0 1 0 0 0 0 1- 0 W
4 0 0 1 1 2 0 1 S1
6 1 1- 0 2 1 0 2 R2
6- 0 1 0 2- 1- 1- 0 W
4 4 0 0 1 1 2 0 1 S1
3 6 1 1- 0 2 1 0 2 R2
0 1 0 0 0 0 1- 0 W
1 2/1- 2/1 1 0 2/3 0 1 S1
3 2/1 2/1- 0 1 2/1 0 2 X2
متغیر شدن ضریب W و یا Z در سطر صفر، بیانگر غیر بهینه بودن مسأله شدن و تنها win بودن تابع هدف صورت مسأله را بیان می دارد. اگر ضریب Z در سطر صفر 1 باشد و نشان دهنده max بدون تابع هدف و اگر 1- باشد، بیانگر min بودن تابع هدف است.
