Online User روش سیمپلکس - مدیریت صنعتی Industrial Management

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

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

اثبات جبری قرار گیری جواب بهینه در حداقل یکی از نقاط گوشه ای
نویسنده : محسن - ساعت ٦:٤٦ ‎ب.ظ روز ۱۳٩۱/۸/۱۸
 

در مطلب مرتبط قبلی به معرفی سه ویژگی مهم و کلیدی جواب های گوشه ای موجه (جواب های CPF) پرداختیم. در اینجا قصد داریم ویژگی اول را به صورت جبری اثبات نماییم. جهت یادآوری ابتدا این ویژگی را دوباره ذکر می کنیم:

...


برای مطالعه متن کامل مقاله روی ادامه مطلب کلیک نمایید.

(550 کلمه)

مطلب مرتبط بعدی: آیا تعداد جواب های گوشه ای مسائل برنامه ریزی خطی متناهی است؟

مطلب مرتبط قبلی: سه ویژگی مهم جواب های گوشه ای موجه


 
 
سه ویژگی مهم جواب های گوشه ای موجه
نویسنده : محسن - ساعت ۸:٤٤ ‎ب.ظ روز ۱۳٩۱/۱/٢۳
 

در اینجا قصد داریم به معرفی سه ویژگی مهم و کلیدی جواب های گوشه ای موجه (جواب های CPF) بپردازیم که در هر مسئله برنامه ریزی خطی دارای فضای موجه کراندار صدق می کند...

  

جهت مطالعه متن کامل مقاله روی "ادامه مطلب" کلیک کنید.

(1000 کلمه)

مطلب مرتبط بعدی: اثبات جبری قرار گیری جواب بهینه در حداقل یکی از نقاط گوشه ای

مطلب مرتبط قبلی: جواب های گوشه ای موجه مجاور در فضای چند بعدی


 
 
جواب های گوشه ای موجه مجاور در فضای چند بعدی
نویسنده : محسن - ساعت ۱۱:٠۱ ‎ب.ظ روز ۱۳٩٠/۱۱/۱۸
 

در مطالب گذشته به معرفی جواب های گوشه ای موجه (جواب های CPF) مجاور و نقش آنها در حل مسائل برنامه ریزی خطی پرداختیم، اما در این مقاله سعی داریم کمی تخصصی تر و عمیق تر به آنها نگاهی دوباره بیندازیم. قبلاً به این نکته اشاره کرده ایم که هر تکرار روش سیمپلکس، در حقیقت حرکت از یک جواب CPF به یکی از جواب های CPF مجاور آن است. در این فرآیند چه مسیری طی می شود؟ ...

جهت مطالعه متن کامل مقاله روی ادامه مطلب کلیک کنید.

(1500 کلمه)

مطلب مرتبط بعدی: سه ویژگی مهم جواب های گوشه ای موجه

مطلب مرتبط قبلی: نگاهی عمیق تر به روش سیمپلکس: اصطلاحات فضای سه بعدی


 
 
نگاهی عمیق تر به روش سیمپلکس: اصطلاحات فضای سه بعدی
نویسنده : محسن - ساعت ٥:٥٧ ‎ب.ظ روز ۱۳٩٠/۱٠/٢۳
 

در مطالب مرتبط گذشته به معرفی مفاهیم هندسی جواب های گوشه ای موجه (CPF) و نقش کلیدی آنها در روش سیمپلکس پرداختیم. همچنین مفاهیم جبری مرتبط با این مفاهیم هندسی ارائه گردید. با این حال هر آنچه در گذشته در این رابطه مطرح شد مربوط به مسائلی مانند مسئله شرکت ویندور بود که دارای تنها دو متغیر تصمیم می باشند و لذا تفسیر و ترسیم هندسی آنها ساده و مفهوم است...

جهت مطالعه متن کامل مقاله روی "ادامه مطلب" کلیک کنید.

(1260 کلمه)

مطلب مرتبط بعدی:جواب های گوشه ای مجاور در فضای چند بعدی

مطلب مرتبط قبلی: قوانین ترکیب روش سیمپلکس با روش نقاط داخلی


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

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

جهت مطالعه متن کامل مقاله روی "ادامه مطلب" کلیک کنید.

(760 کلمه)

مطلب مرتبط بعدی:نگاهی عمیق تر به روش سیمپلکس: اصطلاحات فضای سه بعدی

مطلب مرتبط قبلی: تفاوت روش نقاط داخلی و روش سیمپلکس


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

یکی از راه‌های مقایسه الگوریتم‌های نقاط داخلی با روش سیمپلکس بررسی پیچیدگی محاسبات و خصوصیات تئوری آن‌هاست. ثابت شده است که ورژن اصلی الگوریتم نقاط داخلی یک الگوریتم زمان چند جمله‌ای (Polynomial time algorithm) است به این معنی که زمان لازم برای حل هر مسئله برنامه ریزی خطی به کمک این الگوریتم، تابعی چند جمله‌ای از اندازه مسئله است. مثال‌های گوناگونی ساخته شده‌اند که نشان می‌دهد روش سیمپلکس این‌گونه نیست و به نوعی در زمره الگوریتم‌های زمان نمایی  ...

جهت مطالعه متن کامل مقاله روی "ادامه مطلب" کلیک کنید.

(670 کلمه)

مطلب مرتبط بعدی: قوانین ترکیب روش سیمپلکس با روش نقاط داخلی

مطلب مرتبط قبلی: روش نقاط داخلی


 
 
تحلیل های پس از بهینه سازی به کمک سیمپلکس (Postoptimality analysis)
نویسنده : محسن - ساعت ٧:٤۳ ‎ب.ظ روز ۱۳٩٠/۸/٢٥
 

سوال: پس از بهینه سازی چه تحلیل هایی باید انجام شود؟

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

برای مطالعه متن کامل مقاله روی گزینه "ادامه مطلب" کلیک کنید.

(250 کلمه)

مطلب مرتبط بعدی: روش نقاط داخلی (Interior-point approach)

مطلب مرتبط قبلی: حل مسائل دارای متغیر آزاد در علامت با سیمپلکس


 
 
حل مسائل دارای متغیر آزاد در علامت با سیمپلکس
نویسنده : محسن - ساعت ٩:٥۱ ‎ب.ظ روز ۱۳٩٠/۸/۱٧
 

 سوال: چگونه مسائلی را که دارای متغیرهای آزاد در علامت هستند، با روش سیمپلکس حل کنیم؟

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

 برای مطالعه متن کامل این مقاله روی "ادامه مطلب" کلیک کنید

 (1018 کلمه)

 مطلب مرتبط بعدی: تحلیل های پس از بهینه سازی به کمک سیمپلکس (Postoptimality analysis)

 مطلب مرتبط قبلی: تشخیص عدم وجود فضای موجه از جدول سیمپلکس


 
 
تشخیص عدم وجود فضای موجه از جدول سیمپلکس
نویسنده : محسن - ساعت ٩:٥٦ ‎ب.ظ روز ۱۳٩٠/۸/٤
 

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

برای مطالعه متن کامل مقاله روی گزینه "ادامه مطلب" کلیک کنید.

(436 کلمه/0 شکل/1 جدول)

مطلب مرتبط بعدی: حل مسائل دارای متغیر آزاد در علامت با سیمپلکس

مطلب مرتبط قبلی: روش M بزرگ یا روش دوفازی؟


 
 
روش M بزرگ یا روش دوفازی؟
نویسنده : محسن - ساعت ۱٠:۳٩ ‎ب.ظ روز ۱۳٩٠/٧/٢۸
 

در این قسمت می خواهیم مقایسه ای بین دو روش M بزرگ و روش دوفازی داشته باشیم. برای این کار از مثال زیر استفاده می کنیم ...

برای مطالعه متن کامل این مقاله رو گزینه "ادامه مطلب" کلیک کنید.

(504 کلمه/0 عکس/2 جدول)

مطلب مرتبط بعدی: تشخیص عدم وجود فضای موجه از جدول سیمپلکس

مطلب مرتبط قبلی: روش دو فازی


 
 
روش دوفازی (The Two-Phase Method)
نویسنده : محسن - ساعت ٦:٤٥ ‎ب.ظ روز ۱۳٩٠/٧/٢٥
 

در این بخش برای آشنایی با روش دوفازی، مسئله زیر را بوسیله روش دوفازی حل می کنیم.

 

 برای مطالعه متن کامل این مقاله روی "ادامه مطلب" کلیک کنید.

(1050 کلمه/1 عکس/3 جدول)

مطلب مرتبط بعدی: روش M بزرگ یا روش دوفازی؟

مطلب مرتبط قبلی: حل مسائل غیر استاندارد با روش سیمپلکس: حداقل سازی


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

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

در حقیقت معادل مسئله حداکثر سازی زیر:

است. حل هر دو مسئله بالا، به جواب های بهینه مشابه خواهد رسید. این دو رابطه معادل یکدیگرند زیرا کوچکترین مقدارZ برابر است با بزرگتریم مقدارZ-، بنابراین جوابی از منطقه موجه که کوچکترین مقدارZ را می دهد باید بزرگترین مقدارZ- را نیز حاصل کند. بنابراین در مسئله ارائه شده در مطلب مرتبط قبلی باید تغییر زیر را برای حل مسئله اعمال کنیم:

پس از افزودن متغیرهای مصنوعی به محدودیت ها و اعمال روش M بزرگ، تبدیل تابع هدف به صورت زیر خواهد بود:

مطلب مرتبط بعدی: روش دوفازی (The Two-Phase Method)

مطلب مرتبط قبلی: حل مسائل غیر استاندارد با روش سیمپلکس: وجود محدودیت های با علامت بزرگتر مساوی


 
 
حل مسائل غیراستاندارد با سیمپلکس: وجود محدودیت های بزرگتر مساوی (روش M بزرگ)
نویسنده : محسن - ساعت ۸:٠٦ ‎ب.ظ روز ۱۳٩٠/٧/٢
 

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

حل ترسیمی مثال مذکور در شکل 1 آورده شده است. سه خط رسم شده در شکل و دو محور افقی و عمودی، مرزهای محدودیت مسئله را تشکیل می دهند. نقاط تقاطع این مرزهای محدودیت جاب های گوشه ای مسئله هستند. از بین کلیه این نقاط تنها (6,6) و (7.5,4.5) جواب های موجه هستند و منطقه موجه نیز پاره خط حاصل از اتصال این دو نقطه است. جواب بهینه عبارت است از (x1,x2)=(7.5,4.5) که مقدار تابع هدف مربوط به آن Z=5.25 خواهد بود.

شکل 1 . حل ترسیمی مسئله بالا

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

راهکاری که باید مورد توجه قرار گیرد وارد کردن دو متغیر، یکی متغیر مازاد (Surplus variable) و دیگری متغیر مصنوعی است. متغیر مازاد در اینجا x5 است که به صورت

تعریف می شود و متغیر مصنوعی مربوطه را نیز با x6 (بار) نشان می دهیم. این متغیرها به صورت زیر به محدودیت سوم وارد می شوند.

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

پس از آنکه متغیر کمبود x3 وارد محدودیت اول گردید، یک متغیر مصنوعی، x4(بار) به محدودیت دوم که از نوع مساوی است اضافه می گردد و سپس به کمک روش M بزرگ مسئله مصنوعی زیر در فرمت افزوده حاصل می شود:

نکته ای که باید مورد توجه قرار گیرد این است که ضرایب متغیرهای مصنوعی در تابع هدف به جای M-، در این مورد M+ است زیرا مسئله حاضر از نوع حداقل سازی است. بنابراین اگر x4(بار) و/یا x6(بار) بزرگتر از صفر باشند مقدار جریمه بسیار بزرگ M+ از رسیدن تابع هدف به جواب بهینه جلوگیری می کند.

افزودن متغیر مصنوعی به مسئله باعث بزرگ تر شدن منطقه موجه می شود. وارد کردن متغیر مصنوعی x4(بار) که به نوعی نقش متغیر کمبود را برای محدودیت دوم بازی می کند باعث می شود نقاط(x1,x2) بتوانند زیر خط 0.5x1+0.5x2=6 نیز که در شکل 1 قابل مشاهده است، قرار گیرند. افزودن متغیرهای x5 و x6(بار) به محدودیت سوم مسئله اصلی و انتقال آنها به سمت راست این رابطه، معادله زیر را می دهد:

از آنجا که هر دو متغیر x5 و x6(بار) باید غیر منفی باشند، اختلاف آنها، می تواند مقداری مثبت یا منفی باشد. بنابراین 0.6x1+0.4x2 می تواند هر مقداری بگیرد. به این ترتیب می توان گفت محدودیت سوم در حقیقت از مسئله مصنوعی حذف می شود زیرا هیچ قیدی راجع به قرار گرفتن نقطه (x1,x2) بیان نمی کند. البته این محدودیت سوم در دستگاه معادله ها باقی می ماند زیرا بعد از اینکه در روشM بزرگ متغیر x6(بار) از پایه خارج و به صفر رسید این محدودیت تاثیرگذار می شود. نتیجتاً منطقه موجه برای مسئله مصنوعی نقاط مرزی و نقاط داخلی یک چهارضلعی با نقاط گوشه ای (7.5,4.5), (9,0), (0,0) و (0,12) است که می توانید در شکل 1 آن را تصور کنید.

با توجه به این منطقه موجه جدید، نقطه مبداء نیز موجه است و روش سیمپلکس می تواند نقطه (0,0) را به عنوان جواب CPF اولیه برای شروع استفاده کند. این نقطه معادل جواب BF اولیه

است. در حقیقت هدف اصلی ساختن مسئله مصنوعی، ایجاد شرایطی است که بتوان نقطه مبداء را به عنوان یک نقطه شروع موجه در روش سیمپلکس استفاده نمود. در مباحث آینده مسیر حرکت روش سیمپلکس از مبداء به نقطه بهینه را در هر دو مسئله اصلی و مصنوعی بررسی و مقایسه خواهیم کرد. ولی ابتدا به این سوال پاسخ خواهیم داد که برای حل مسائل حداقل سازی (MIN) چگونه باید از روش سیمپلکس استفاده کنیم؟

مطلب مرتبط بعدی: حل مسائل غیر استاندارد با روش سیمپلکس: حداقل سازی

مطلب مرتبط قبلی: حل مسائل غیراستاندارد با روش سیمپلکس: منفی بودن اعداد سمت راست (RHS)


 
 
حل مسائل غیر استاندارد با روش سیمپلکس: منفی بودن اعداد سمت راست (RHS)
نویسنده : محسن - ساعت ۸:۱٠ ‎ب.ظ روز ۱۳٩٠/٦/٢۸
 

تکنیکی که در انتهای بخش قبل برای مواجهه با محدودیت های مساوی دارای عدد سمت راست (Right-Hand Sides) منفی عنوان شد، یعنی ضرب نمودن دو طرف معادله در یک 1-، برای هر محدودیت نامعادله ای که دارای عدد سمت راست منفی باشد نیز قابل استفاده است. ضرب نمودن دو طرف یک نامعادله در 1-جهت نامعادله را نیز تغییر می دهد برای نمونه <= به >= تبدیل می شود و بر عکس. برای مثال، محدودیت زیر:

با ضرب 1- در دو طرف آن به محدودیت زیر تبدیل می گردد:

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

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

مطلب مرتبط بعدی: حل مسائل غیراستاندارد با روش سیمپلکس: وجود محدودیت های با علامت بزرگتر مساوی

مطلب مرتبط قبلی: حل مسائل غیر استاندارد با روش سیمپلکس: وجود محدودیت مساوی (قسمت دوم)


 
 
حل مسائل غیر استاندارد با سیمپلکس- وجود محدودیت مساوی (قسمت دوم)(روش M بزرگ)
نویسنده : محسن - ساعت ۸:٥٧ ‎ب.ظ روز ۱۳٩٠/٦/٢۳
 

تغییر شکل معادله (0) . پس از تبدیل شدن مسئله مصنوعی به شکل افزوده، دستگاه معادلات عبارت خواهد بود از:

 متغیرهای پایه مسئله بالا عبارتند از (x3,x4,x5-). با این حال دستگاه معادله بالا هنوز قالب مناسب برای عملیات حذف گوسی را ندارد زیرا یکی از متغیرهای پایه، x5-، دارای ضریب غیر صفر در معادله (0) است. یادآوری می کنیم که برای اینکه روش سیمپلکس قادر به اجرای تست بهینگی یا یافتن متغیر پایه ورودی باشد، باید همه متغیرهای پایه به لحاظ جبری از سطر (0) حذف شوند. با حذف ضرایب مربوط به متغیرهای پایه در سطر (0) ضرایب متغیرهای غیر پایه در این سطر به گونه ای تغییر می کنند که ضریب منفی هر متغیر غیرپایه نشان دهنده نرخ افزایش Z در صورت افزایش آن متغیر غیرپایه باشد.

برای حذف جبری x5- از معادله (0) لازم است x5- برابر معادله (3) را از معادله (0) کم کنیم:

بکارگیری روش سیمپلکس. همانطور که مشاهده می کنید معادله (0) جدید تنها شامل متغیرهای غیرپایه (x1,x2) است:

در رابطه بالا چون 3M+3>2M+5 است، (یادآوری میکنیم که M نماد عددی بسیار بزرگ است) افزایش x1 مقدار Z را با نرخ بیشتری نسبت به افزایش x2 ارتقاء می دهد و بنابراین متغیر x1 به عنوان متغیر ورودی انتخاب می شود. این انتخاب باعث می شود در تکرار اول از نقطه (0,0) به نقطه (4,0) حرکت کنیم و مقدار تابع هدف،Z، به مقدار 4(3M+3) افزایش یابد.

در دستگاه معادلات، نمادM تنها در عبارات معادله (0) ممکن است ظاهر شود. در نتیجه تنها برای آزمون بهینگی و تعیین متغیر پایه ورودی باید به این مقدار توجه نمود. یکی از راه های مواجهه با عبارات و محاسبات M دار، قرار دادن یک عدد بسیار بزرگ به جای آن و انجام محاسبات است. اما این روش حل ممکن است نتایج گمراه کننده ای به همراه داشته باشد و انجام آزمون بهینگی را کمی مشکل نماید. بنابراین بهتر است با اینگونه عبارات به صورت پارامتری برخورد شود. برای مثال معادله (0) را به صورت تابع خطی aM+b در نظر بگیرید و دو عبارت ضریب a و عبارت جمعی b را در محاسبات به طور جداگانه شرکت دهید. از آنجا که فرض کردیم M عددی بسیار بزرگ است، مقدار b در مقایسه با M بسیار ناچیز و قابل حذف است (در صورتی که a برابر با صفر نباشد). بنابراین در چنین مواردی برای آزمون بهینگی و همچنین برای انتخاب متغیر پایه ورودی مقدار a باید مورد نظر قرار گیرد، مگر در مواردی که حتی با در نظر گرفتن مقدار a همچنان چندین انتخاب وجود داشته باشد که در این صورت باید به مقدار b توجه شود.

با استفاده از این روند، جداول سیمپلکس مسئله به صورت جداول 1 خواهد شد. متغیر مصنوعی x5- در دو جدول اول متغیر پایه و در دو جدول نهایی متغیر غیر پایه است. بنابراین دو جواب BF اولیه برای مسئله مصنوعی، برای مسئله اصلی غیرموجه هستند و دو جواب نهایی برای هر دو مسئله موجه می باشند.

 

جدول 1. مجموعه جداول سیمپلکس مسئله

مثالی که در اینجا بررسی شد تنها دارای یک محدودیت معادله ای بود. اگر یک مدل برنامه ریزی خطی دارای بیش از یک معادله باشد، با هر یک به طور مجزا به شیوه توضیح داده شده برخورد می شود. دقت داشته باشید اگر محدودیتی به صورت معادله بود و عدد سمت راست آن نیز منفی بود ابتدا باید دو طرف معادله مذکور را در یک 1 - ضرب نمود.

مطلب مرتبط بعدی: حل مسائل غیر استاندارد با روش سیمپلکس: منفی بودن اعداد سمت راست (RHS)

مطلب مرتبط قبلی: حل مسائل غیر استاندارد با روش سیمپلکس- وجود محدودیت مساوی (قسمت اول)


 
 
حل مسائل غیر استاندارد با سیمپلکس – وجود محدودیت مساوی (قسمت اول) (روش M بزرگ)
نویسنده : محسن - ساعت ۸:٢٩ ‎ب.ظ روز ۱۳٩٠/٦/۱۸
 

هر محدودیت به شکل معادله

در اصل برابر است با جفت محدودیت غیر مساوی زیر:

با این حال، به جای استفاده از این جایگزینی و افزایش دادن تعداد محدودیت ها، بهتر است از تکنیک متغیرهای مصنوعی استفاده کنیم. این تکنیک را با مثال زیر تشریح می کنیم:

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

به یک معادله به صورت

تبدیل خواهد شد.

بنابراین مدل کامل مسئله جدید به صورت روابط نشان داده شده در گوشه بالا، سمت راست شکل 1 تغییر خواهد کرد. همچنین از شکل کاملاً مشخص است که منطقه موجه تنها یک پاره خط بین نقاط (2,6) و (4,3) است.

پس از آنکه متغیرهای کمبود مورد نیاز به محدودیت های نامعادله افزوده شد، مجموعه معادلات مربوط به فرمت افزوده مسئله به شرح زیر خواهد بود:

متاسفانه این معادلات دارای یک جواب BF اولیه واضح نیستند زیرا معادله (3) دارای متغیر کمبود نیست که بتوان از آن به عنوان متغیر پایه اولیه استفاده نمود. برای شروع روش سیمپلکس لازم است به یک جواب BF اولیه دسترسی داشته باشیم.

شکل 1 . حالت ترسیمی مسئله شرکت ویندور در صورت تبدیل شدن محدودیت ساختاری سوم به معادله

بدست آوردن جوابBF ابتدایی: این فرآیند شامل ساخت یک مسئله مصنوعی است که جواب بهینه آن، جواب بهینه مسئله اصلی نیز می باشد. در این فرایند دو تغییر زیر در مسئله اصلی صورت می گیرد:

  • بکاربردن تکنیک متغیرهای مصنوعی با افزودن یک متغیر مصنوعی غیر منفی به معادله 3، که معادله مذکور را به شکل زیر تغییر می دهد:

  • تخصیص یک جریمه بسیار زیاد به تابع هدف برای شرایط

    که تابع هدف را به صورت زیر تغییر خواهد داد:

    که M نماد یک عدد مثبت بسیار بزرگ است. (در این روش که باعث می شود مقدار صفر گردد را روش M بزرگ (Big M) می گویند.)

حال با استفاده از روش سیمپلکس و بکارگیری آن بر روی مسئله مصنوعی، جواب بهینه ای بدست می آید که جواب بهینه مسئله اصلی نیز می باشد. برای شروع از جواب BF اولیه زیر استفاده می کنیم:

متغیرهای غیر پایه: 

متغیرهای پایه: 

از آنجا که در مسئله مصنوعی نقش متغیر کمبود را برای محدودیت سوم بازی می کند، این محدودیت مشابه محدودیت

(که دقیقاً در مدل مسئله اصلی نیز وجود دارد) عمل می کند. در زیر مسئله اصلی و مسئله مصنوعی حاصل از آن آورده شده است:

بنابراین منطقه موجه مسئله مصنوعی برای (x1,x2) منطقه ای است که در شکل 2 آورده شده است. تنها بخشی از این منطقه موجه که بر منطقه موجه مسئله اصلی منطبق است زمانی حاصل می شود که داشته باشیم

یعنی داشته باشیم:

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

به تابع هدف مسئله مصنوعی است.

شکل 2 . حالت ترسیمی مسئله شرکت ویندور در صورت تبدیل شدن محدودیت ساختاری سوم به معادله

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

مطلب مرتبط بعدی: حل مسائل غیر استاندارد با روش سیمپلکس- وجود محدودیت مساوی (قسمت دوم)

مطلب مرتبط قبلی: حل مسائل غیر استاندارد با روش سیمپلکس – مقدمه


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

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

تنها مشکل اساسی که در برخورد با مسائل غیر استاندارد ممکن است پیش بیاید تعیین جواب BF اولیه است. قبلاً به آسانی با قرار دادن متغیرهای کمبود به عنوان متغیرهای پایه اولیه، این جواب پایه اولیه بدست می آمد و برابر بود با مقادیر سمت راست محدودیت ها که غیر منفی نیز بودند. حال باید کار دیگری انجام داد. راهکار استانداردی که برای مواجهه با این موارد خاص مورد استفاده می گیرد عبارت است از تکنیک متغیرهای مصنوعی[1]. این تکنیک مسئله غیر استاندارد را به وسیله اضافه نمودن متغیرهای مصنوعی به محدودیت هایی که به آن نیاز دارند به مسئله جدیدی تبدیل می کند که شکل استاندارد دارد. این متغیرهای جدید با هدف تبدیل شدن به متغیر پایه اولیه به مدل اضافه می شوند. محدودیت های غیر منفی بودن برای این متغیرهای جدید به مدل اضافه می شود و در تابع هدف نیز اصلاحاتی صورت می گیرد که شامل افزودن جریمه هایی به آن به دلیل مثبت بودن متغیرهای مصنوعی است. در حقیقت متغیرهای مصنوعی متغیرهایی مجازی اند و باید از پایه خارج شوند، به همین دلیل تابع هدف مسئله جدید به گونه ای نوشته می شود که در صورت مثبت بودن یکی از متغیرهای مصنوعی مستحق جریمه شدن باشد. تکرارهای روش سیمپلکس به طور خودکار به سمت حذف متغیرهای مصنوعی (صفر کردن مقدار آنها) پیش می روند. زمانی که همه متغیرهای مصنوعی حذف شدند و جدول نهایی سیمپلکس نیز بهینه بود، جوابی که بدست می آید در حقیقت جواب مسئله اولیه نیز هست.

برای روشن تر شدن بحث در مطلب مرتبط بعدی موردی را در نظر می گیریم که تنها دلیل غیر استاندارد بودن مسئله آن حضور یک یا چند محدودیت مساوی باشد.



[1] Artificial-variable technique

مطلب مرتبط بعدی: حل مسائل غیر استاندارد با روش سیمپلکس – وجود محدودیت مساوی (قسمت اول)

مطلب مرتبط قبلی: موارد خاص روش سیمپلکس: جواب بهینه چندگانه


 
 
موارد خاص روش سیمپلکس: جواب بهینه چندگانه
نویسنده : محسن - ساعت ۱٠:٤۸ ‎ب.ظ روز ۱۳٩٠/٦/٥
 

در مطالب مرتبط قبل عنوان شد که یک مسئله می تواند بیش از یک جواب بهینه داشته باشد. این مورد با مثالی که در شکل 1 ارائه شده است و با تغییر تابع هدف مسئله شرکت ویندور به صورت

بدست آمده است قبلاً نیز ارائه شد. هر نقطه واقع بر پاره خط بین نقاط (2,6) و (4,3) نقطه بهینه است. بنابراین همه جواب های بهینه، میانگین وزنی این دو جواب CPF بهینه هستند:

که وزن های w1 و w2 اعدادی هستند که در روابط زیر صدق کنند:

برای مثال با داشتن:

خواهیم داشت:

که یک جواب بهینه خواهد بود. به طور کلی هر میانگین وزنی از دو یا چند جواب که وزن های مورد استفاده غیر منفی باشند و مجموع آنها عدد یک گردد را ترکیب محدب (convex combination) این جوابها می نامند. بنابراین، هر جواب بهینه در این مثال ترکیبی محدب از نقاط (2,6) و (4,3) است.

شکل 1. وجود چندین جواب بهینه با تغییر تابع هدف مسئله شرکت ویندور

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

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

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

برای روشن تر شدن بحث مثالی که در شکل 1 ارائه شده است را در نظر بگیرید. روش سیمپلکس با سه جدول اول نشان داده شده در جدول 1 به اولین جواب BF بهینه می رسد و متوقف می گردد. با این حال بدلیل آنکه متغیر غیر پایه x3 دارای ضریب صفر در سطر 0 است یک تکرار اضافه که با نام extra در جدول 1 آورده شده است انجام می گیرد تا جواب BF بهینه بعدی نیز محاسبه شود. نتیجه نشان می دهد که دو جواب BF بهینه مسئله عبارتند از (2,6,2,0,0) و (4,3,0,6,0) که مقدار تابع هدف در این نقاط برابر و Z=18 است. همانطور که مشاهده می کنید جدول سیمپلکس نهایی نیز دارای متغیر غیر پایه x4 دارای ضریب صفر در سطر 0 است. این شرایط بیان می کند که این تکرار اضافی باعث تغییر تابع هدف نشده است. انتخاب x4 به عنوان متغیر پایه ورودی باعث بازگشت ما به جدول سوم (جدول قبل) خواهد شد. بنابراین این دو جواب تنها جواب هایBF بهینه هستند و دیگر جواب های بهینه ترکیب محدب این دو جواب هستند:

 جدول 1 . مجموعه کامل جداول سیمپلکس برای یک مسئله با جواب های بهینه چندگانه

 مطلب مرتبط بعدی: حل مسائل غیر استاندارد با روش سیمپلکس- مقدمه

مطلب مرتبط قبلی: موارد خاص روش سیمپلکس: عدم وجود متغیر پایه خروجی


 
 
موارد خاص روش سیمپلکس: عدم وجود متغیر پایه خروجی (تابع هدف بیکران)
نویسنده : محسن - ساعت ٩:۱۸ ‎ب.ظ روز ۱۳٩٠/٦/٢
 

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

شکل 1. مسئله شرکت ویندور بدون دو محدودیت ساختاری آخر و دارای Z بیکران

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

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

تفسیر جدولی مانند جدول 1 به این شرح است که محدودیت های مسئله مانع افزایش Z تا بینهایت نیستند و نتیجه نهایی روش سیمپلکس در این مورد تنها جمله «تابع هدف بیکران است» می باشد. نکته مهم اینجاست که هیچ مسئله واقعی وجود ندارد که تابع هدف آن سود باشد و بیکران گردد. لذا در صورت مواجهه با چنین موردی می توان نتیجه گرفت در فرآیند حل اشتباهی وجود دارد. در مرحله اول احتمالاً مدل درست ساخته نشده است و محدودیتی از قلم افتاده و یا محدودیتی درست ساخته نشده است. در نهایت ممکن است این امر در اثر اشتباه در محاسبات جدول سیمپلکس صورت گرفته باشد.

مطلب مرتبط بعدی: موارد خاص روش سیمپلکس: جواب بهینه چندگانه

مطلب مرتبط قبلی:موارد خاص روش سیمپلکس: امکان انتخاب همزمان چند متغیر به عنوان متغیر پایه خروجی


 
 
موارد خاص روش سیمپلکس: امکان انتخاب همزمان چند متغیر به عنوان متغیر پایه خروجی
نویسنده : محسن - ساعت ٩:٠٤ ‎ب.ظ روز ۱۳٩٠/٦/۱
 

فرض کنید در مرحله دوم تکراری بیش از یک متغیر پایه شرایط انتخاب شدن به عنوان متغیر پایه خروجی را داشته باشد. آیا مهم است کدام یک به عنوان خروجی انتخاب گردد؟ برای پاسخ دادن به این سوال باید عنوان نمود که از لحاظ تئوری به دلیل امکان پیش آمدن مورد زیر، اینکه کدام متغیر از پایه خارج گردد اهمیت دارد. در ابتدا همه متغیرهایی که امکان انتخاب به عنوان متغیر پایه خروجی را دارند با افزایش مقدار متغیر پایه ورودی همزمان صفر می شوند و بنابراین آن متغیرهایی که به عنوان متغیر خروجی انتخاب نمی شوند علی رغم اینکه دارای مقدار صفر هستند در جواب BF جدید به عنوان متغیرپایه وجود خواهند داشت. لازم به ذکر است در اصطلاح به متغیر پایه ای که دارای مقدار صفر باشد متغیر فاسد[1] می گویند و از همین اصطلاح برای جواب BF مربوطه نیز استفاده می کنند. اگر یکی از متغیرهای پایه فاسد که دارای مقدار صفر است در تکرارهای بعدی به عنوان متغیر پایه خروجی انتخاب گردد، متغیر پایه ورودی در آن تکرار نیز باید صفر باقی بماند، زیرا هرگونه افزایش متغیر ورودی منجر به ظهور مقدار منفی برای متغیر پایه خروجی می گردد که امکان پذیر نیست. بنابراین مقدار Z نیز بدون تغییر باقی می ماند. در نتیجه اگر مقدار Z در تکرارهای متوالی بدون تغییر باقی بماند و افزایش نداشته باشد گفته می شود روش سیمپلکس درون یک چرخه (loop) گرفتار شده است. در یک چرخه دنباله ای از جواب ها به صورت دوره ای بدست می آیند بدون اینکه مقدار Z افزایش یابد و به سمت جواب بهینه حرکت کند و این در حالی است که آزمون بهینگی صحت بهینه بودن جواب ها را تایید نمی کند. در واقع، جواب های بدست آمده جواب هایی مصنوعی هستند  و در یک حلقه دائمی تبدیل گیرافتاده است.

خوشبختانه، اگر چه امکان وقوع حلقه دائمی از لحاظ تئوری ممکن است، در مسائل عملی به ندرت مشاهده شده است. در صورت مواجه شدن با یک حلقه می توانید با تغییر متغیر انتخاب شده به عنوان متغیر پایه خروجی از آن خارج شوید. علاوه بر این قوانین خاصی نیز در برخی مراجع ذکر شده است که با رعایت آنها از برخورد با چنین حلقه هایی می توان جلوگیری نمود. با این حال رعایت این قوانین در بسیاری از مسائل واقعی پیچیده و گاهاً غیر ممکن است که در اینجا مجال پرداختن به این قوانین وجود ندارد. برای کسانی که به دنبال مرجع معتبری در رابطه با این قوانین هستند کتاب mathematics of Operations research (1977) نوشته R. Bland صفحات 103 الی 107 توصیه می شود. در نتیجه پیشنهاد می شود بدون نگرانی از برخورد با حلقه ها به صورت اختیاری متغیر پایه خروجی را انتخاب نمایید و در صورت قرار گرفتن در حلقه انتخاب خود را تغییر داده و مجدداً به حل مسئله بپردازید.



[1]  degenerate

مطلب مرتبط بعدی: موارد خاص روش سیمپلکس: عدم وجود متغیر پایه خروجی (تابع هدف بیکران)

مطلب مرتبط قبلی: موارد خاص روش سیمپلکس: امکان انتخاب همزمان چند متغیر به عنوان متغیر پایه ورودی


 
 
موارد خاص روش سیمپلکس: امکان انتخاب همزمان چند متغیر به عنوان متغیر پایه ورودی
نویسنده : محسن - ساعت ٢:٤٧ ‎ب.ظ روز ۱۳٩٠/٥/۳٠
 

تاکنون در مطالب ارائه شده در مبحث سیمپلکس به این نکته اشاره نکردیم که اگر در هر یک از مراحل روش سیمپلکس به موارد خاص و مبهمی برخورد کردیم چه باید بکنیم. در این سلسله مطالب قصد داریم به تشریح این موارد و راه های مواجهه با آنها بپردازیم:

امکان انتخاب همزمان چند متغیر به عنوان متغیر پایه ورودی

مرحله اول در هر تکرار مربوط است به انتخاب یکی از متغیرهای غیرپایه که دارای منفی ترین ضریب در معادله 0 است که همان متغیر پایه ورودی است. حال فرض کنید دو متغیر یا بیشتر از متغیرهای غیرپایه دارای منفی ترین ضریب باشند. برای مثال اگر تابع هدف مسئله شرکت ویندور به صورت Z=3x1+3x2 تغییر یابد، در نتیجه معادله 0 مربوطه در تکرار اول عبارت خواهد بود از Z-3x1-3x2=0. به این ترتیب هر دو متغیر غیرپایه x1 و x2 دارای ضریب -3 هستند که منفی ترین ضریب در معادله 0 می باشند. سوال اینجاست که کدام متغیر باید به عنوان متغیر پایه ورودی انتخاب گردد؟ چگونه می توان این مشکل را برطرف نمود؟

پاسخ این سوال این است که انتخاب بین این دو متغیر امری اختیاری است زیرا در صورت انتخاب هر یک از این دو متغیر به عنوان متغیر پایه ورودی، در نهایت جواب بهینه بدست خواهد آمد. البته ممکن است با انتخاب یکی از متغیرهای ممکن با تکرار کمتری به جواب نهایی رسید اما هیچ روش کاملاً مطمئنی برای پیش بینی این مطلب که انتخاب کدام متغیر باعث دستیابی زودتر به جواب بهینه می شود وجود ندارد. برای مثال با در نظر گرفتن تابع هدف جدید اشاره شده در بالا، انتخاب متغیر x1 به عنوان متغیرپایه ورودی باعث می شود با 3 تکرار به جواب بهینه، (2,6)، برسیم و با انتخاب x2 به عنوان متغیر پایه ورودی با 2 تکرار به جواب بهینه خواهیم رسید.

مطلب مرتبط بعدی: موارد خاص روش سیمپلکس: امکان انتخاب همزمان چند متغیر به عنوان متغیر پایه خروجی

مطلب مرتبط قبلی: فرمت جدولی روش سیمپلکس (قسمت دوم)


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

مرحله سوم: جواب BF جدید را بیابید. برای این کار با استفاده از روش حذف گوسی یا همان عملیات جبری روی سطرها (ضرب یا تقسیم عددی ثابت و غیر صفر در یک سطر و یا جمع یا کسر نمودن مضربی از یک سطر با سطری دیگر) جدول سیمپلکس جدید را بسازید و زیر جدول کنونی وارد نمایید. پس از این عملیات دوباره آزمون بهینگی را انجام دهید. برای حذف گوسی مراحلی که در زیر اشاره شده است باید انجام گیرد.

  • اعداد سطر لولا را بر عدد لولا تقسیم کنید و این سطر جدید را در دو گام بعدی استفاده نمایید.
  • برای سطرهای دیگر (که شامل سطر 0 نیز می شود) اگر ضریب مربوطه در ستون لولا منفی است، اعداد هر سطر را با اعداد متناظر در سطر جدید بدست آمده در گام اول که در قدر مطلق ضریب منفی مذکور ضرب شده است جمع نمایید.

در مثال: از آنجا که x2 باید جایگزین x4 گردد لازم است جدول سیمپلکس جدیدی تهیه شود که در آن الگوی ضرایب ستون x2 به شکل (0,0,1,0) باشد. برای شروع، سطر لولا (سطر دوم) را بر عدد لولا (2) تقسیم نمایید و سطر جدیدی را که در سطر دوم جدول 3 نشان داده شده است بدست آورید. سپس پنج برابر سطر لولای جدید را به سطر 0 اضافه نمایید. همچنین دو برابر سطر لولای جدید را از سطر 3 کم کنید. این محاسبات جدول سیمپلکس جدیدی را ارائه می دهد که در جدول 4 آورده شده است. بنابراین جواب BF جدید عبارت خواهد بود از (0,6,4,0,6) که بر اساس آن خواهیم داشت Z=30. در مرحله بعد برای تعیین اینکه این جواب BF جدید بهینه است یا خیر باید آزمون بهینگی را بکار بگیریم. از آنجا که در سطر 0 جدید همچنان عدد منفی وجود دارد (-3 برای ستون x1)، جواب بهینه نیست و حداقل یک تکرار دیگر برای رسیدن به جواب بهینه لازم است.

جدول 3. جدول سیمپلکس مسئله شرکت ویندور پس از تقسیم سطر لولا بر عدد لولا

 

جدول 4. دو جدول سیمپلکس اول مسئله شرکت ویندور

تکرار دوم و رسیدن به جواب بهینه

تکرار دوم برای یافتن جواب BF جدید از جدول سیمپلکس دوم استفاده خواهد کرد که در جدول 4 آورده شده است. با انجام مراحل اول و دوم متوجه خواهیم شد که متغیر x1 متغیر پایه ورودی است و متغیر x3 متغیر پایه خروجی است. این مراحل در جدول 5 آورده شده است.

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

برای انجام مرحله سوم نیز سطر لولا (سطر 3) را بر عدد لولا (3) تقسیم می کنیم. سپس 3 برابر این سطر محاسبه شده را به سطر 0 می افزاییم و از سطر 1 سطر جدید را کم می کنیم.

پس از انجام مراحل سه گانه جدول سیمپلکس جدیدی خواهیم داشت که در جدول 6 ارائه شده است. بنابراین جواب BF جدید عبارت خواهد بود از (2,6,2,0,0) و خواهیم داشت Z=36. با انجام آزمون بهینگی نتیجه خواهد شد که جواب مذکور بهینه است زیرا هیچ یک از ضرایب سطر 0 منفی نیستند و بنابراین الگوریتم متوقف می شود. نتیجتاً جواب بهینه مسئله شرکت ویندور (بدون در نظر گرفتن متغیرهای کمبود) عبارت خواهد بود از x1=2 و x2=6.

حال می توانید جدول 6 را با مراحل انجام شده در مطلب مربوط به روش جبری مقایسه کنید و ببینید که روش سیمپلکس جدولی و روش سیمپلکس جبری در اصل یک منطق و یک ساختار مشترک دارند. با این حال روش جبری برای درک منطق حاکم بر روش سیمپلکس روش بهتری است و روش جدولی از لحاظ ساختارمندی مراحل و راحتی کار روش مناسب تری است. از این به بعد از شکل جدولی روش سیمپلکس استفاده خواهیم کرد.

 

جدول 6. مجموعه کامل جداول سیمپلکس برای مسئله شرکت ویندور

 مطلب مرتبط بعدی: موارد خاص روش سیمپلکس: امکان انتخاب همزمان چند متغیر به عنوان متغیر ژایه ورودی

مطلب مرتبط قبلی: فرمت جدولی روش سیمپلکس (قسمت اول)


 
 
فرمت جدولی روش سیمپلکس (قسمت اول)
نویسنده : محسن - ساعت ٩:۱۳ ‎ب.ظ روز ۱۳٩٠/٥/٢۳
 

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

شکل جدولی روش سیمپلکس تنها اطلاعات ضروری مسئله مانند (1) ضرایب متغیرها، (2) اعداد ثابت در سمت راست معادلات و (3) متغیرهای پایه مربوط به هر معادله را را در خود جای می دهد. این ویژگی باعث می شود نوشتن نمادها و اسامی متغیرها در هر معادله لزومی نداشته باشد و البته از آن مهمتر این حقیقت است که این ویژگی باعث می شود اعداد و مقادیر مورد استفاده و محاسبه شده در هر تکرار به صورت کاملاً مختصر و فشرده ذخیره سازی شوند تا بتوان برای ارزیابی ها و تحلیل های لازم از آنها استفاده نمود.

در جدول 1 سعی شده است مقایسه بین دستگاه معادلات اولیه مسئله شرکت ویندور در فرمت جبری و فرمت جدولی آورده شود که به جدول ارائه شده در سمت راست در اصطلاح جدول سیمپلکس (Simplex tableau) می گویند. متغیرهای پایه در جدول ابتدایی عبارت بودند از x3، x4 و x5 و متغیرهای دیگر متغیرهای غیرپایه هستند. بعد از قرار دادن x1=0 و x2=0، ستون سمت راست مقادیر متغیرهای پایه را می دهد و به این ترتیب جواب BF اولیه عبارت خواهد بود از (x1,x2,x3,x4,x5)=(0,0,4,12,18) که بر اساس این جواب خواهیم داشت Z=0.

شکل جدولی روش سیمپلکس برای نمایش مختصر و مفید دستگاه معادلات مورد استفاده جهت یافتن جواب BF صحیح از جدول سیمپلکس استفاده می کند. در جدول سیمپلکس مقدار هر متغیری که در ستون سمت چپ قرار داشته باشد برابر است با عدد واقع در همان سطر و در ستون سمت راست جدول و هر متغیری نیز که در ستون مذکور قرار ندارد متغیر غیر پایه بوده و مقدارش صفر است. هنگام انجام آزمون بهینگی و همچنین هنگام انجام مراحل هر تکرار تنها اعدادی که در سمت راست ستون Z واقع شده اند مورد استفاده قرار می گیرند. اصطلاح سطر تنها به ردیفی از اعداد که در سمت راست ستون Z واقع شده اند و اعداد سمت راست را نیز شامل می شود اطلاق می گردد. سطر iام مربوط است به معادله iام.

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

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

فرمت جدولی

فرمت جبری

سمت راست

ضرایب

معادله

متغیر پایه

 

x5

x4

x3

x2

x1

Z

0

0

0

0

-5

-3

1

(0)

Z

4

0

0

1

0

1

0

(1)

x3

12

0

1

0

2

0

0

(2)

x4

18

1

0

0

2

3

0

(3)

x5

 خلاصه ای از روش سیمپلکس جدولی در تکرار اول

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

در مثال: فعالیت های اشاره شده در این مرحله برای مسئله شرکت ویندور جدول سیمپلکس اولیه با جواب BF اولیه (0,0,4,12,18) را که در جدول 1 آورده شده است حاصل خواهد نمود.

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

در مثال: با توجه به اینکه معادله Z=3x1+5x2 بیانگر این مطلب است که افزایش هر یک از دو متغیر x1 و x2 باعث افزایش Z می گردد، جواب BF کنونی بهینه نیست. این نکته را می توان از جدول سیمپلکس نیز دریافت به این صورت که با دیدن دو مقدار منفی -3 و -5 در ضرایب موجود در سطر صفر جدول سیمپلکس اولیه می توان به این نتیجه رسید که جواب کنونی بهینه نیست.

تکرار اول.

مرحله 1: متغیر غیرپایه ای را که دارای منفی ترین مقدار ضریب در سطر 0 است به عنوان متغیر پایه ورودی انتخاب کنید. ستون مربوط به متغیر ورودی را با رسم یک خط اطراف آن مشخص نمایید. به این ستون در اصطلاح ستون لولا (Pivot column) گفته می شود.

در مثال: منفی ترین ضریب در سطر 0 مربوط است به متغیر x2 که برابر است با -5 و بنابراین x2 از متغیر غیر پایه به متغیر پایه تبدیل خواهد شد. (این تغییر در جدول 2 با خطی که اطراف ستون مربوط به x2 و زیر -5 رسم شده است مشخص شده است.)

مرحله 2: با انجام آزمون حداقل نسبت، متغیری پایه خروجی را تعیین کنید. مراحل آزمون حداقل نسبت در شکل جدولی روش سیمپلکس به ترتیب زیر است:

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

اطراف سطر مربوط به متغیر پایه خروجی را نیز با خطی بسته مشخص کنید و آن را سطر لولا (Pivot row) بنامید. همچنین به عددی که در تقاطع سطر و ستون لولا قرار دارد عدد لولا (Pivot number) گویند.

در مثال: محاسبات مربوط به آزمون حداقل نسبت در سمت راست جدول 2 نشان داده شده است. طبق این محاسبات سطر 2 سطر لولا و متغیر x4 متغیر پایه خروجی خواهد بود. در جدول سیمپلکس بعدی که در جدول 3 (در مطلب مرتبط بعدی خواهید دید) نمایش داده شده است متغیر x2 در سطر دوم جایگزین متغیر x4 در ستون مربوط به متغیرهای پایه گردیده است.

جدول 2. تعیین متغیر ورودی و متغیر خروجی برای جدول سیمپلکس اولیه مسئله شرکت ویندور

  مطلب مرتبط بعدی: فرمت جدولی روش سیمپلکس (قسمت دوم)

مطلب مرتبط قبلی: دیدگاه جبری روش سیمپلکس (قسمت دوم)


 
 
دیدگاه جبری روش سیمپلکس (قسمت دوم)
نویسنده : محسن - ساعت ۸:٠۸ ‎ب.ظ روز ۱۳٩٠/٥/٢۱
 

یافتن جواب BF جدید (مرحله سوم تکرار)

افزایش مقدار متغیر x2از صفر به 6 ما را از جواب BF اولیه به جواب BF جدید منتقل می کند.

 

جواب BF اولیه

جواب BF جدید

متغیرهای غیرپایه 

x1=0, x2=0

x1=0, x4=0

متغیرهای پایه 

x3=4, x4=12, x5=18

x3=?, x2=6, x5=?

 هدف از مرحله سوم تبدیل سیستم معادلات به شکلی ساده تر برای محاسبه آزمون بهینگی و در صورت لزوم رفتن به تکرار بعدی با این جواب BF جدید است که این قالب ساده تر از طریق فرآیندی به نام حذف گوسی بدست می آید. در حین این فرآیند مقادیر x3 و x5 نیز برای جواب جدید محاسبه می شوند.

در اینجا دوباره سیستم معادلات اصلی مسئله را ارائه می کنیم. همانطور که مشاهده می کنید Z در تابع هدف نقش یک متغیر پایه را بازی می کند:

تنها تفاوتی که وجود دارد این مطلب است که متغیر x2 به جای متغیر x4 وارد متغیرهای پایه شده است. برای حل این دستگاه معادلات و محاسبه Z، x2، x3 و x5 لازم است به منظور ایجاد الگوی ضرایب (0,0,1,0) برای متغیر x2 به جای متغیر x4 و باز نویسی دستگاه معادلات، از چند عملیات جبری اولیه استفاده شود. برای این کار می توان از دو نوع عملیات جبری ساده زیر استفاده نمود:

  • ضرب (تقسیم) یک معادله در (بر) یک عدد ثابت غیر صفر.
  • جمع (کسر) مضربی از یک معادله با (از) معادله ای دیگر.

برای استفاده از این عملیات ها، دقت داشته باشید که ضرایب متغیر x2 در دستگاه معادلات بالا به ترتیب عبارتند از 2, 0, -5 و 3 که باید به 1, 0, 0 و 0 تبدیل شوند. برای تبدیل ضریب 2 در معادله (2) به 1، از اولین نوع عملیات جبری استفاده نموده و معادله (2) را بر 2 تقسیم می کنیم و حاصل عبارت خواهد بود از:

برای تبدیل ضرایب -5 و 3 به صفر، باید از عملیات نوع دوم استفاده شود. برای این کار ما پنج برابر معادله (2) جدید را به معادله (0) اضافه می نماییم و 2 برابر معادله (2) جدید را از معادله (3) کسر می کنیم. دستگاه معادلات جدید عبارت خواهد بود از:

 از آنجا که داریم x1=0 و x4=0، به کمک دستگاه بازنویسی شده بالا به سادگی می توان جواب BF جدید را به صورت (x1,x2,x3,x4,x5)=(0,6,4,0,6) بدست آورد که در این نقطه جواب جدید داریم Z=30.

به این فرآیند که برای ایجاد دستگاه معادلات جدید و حل آن انجام می گیرد روش حذفی گوس جردن (Gauss-Jordan method of elimination) و یا به اختصار حذف گوسی می گویند. مفهوم کلیدی این روش استفاده از عملیات های جبری ساده جهت تبدیل دستگاه معادلات اصلی به دستگاهی جدید از معادلات است که در آن هر متغیر پایه تنها در یک معادله و آن هم یا ضریب +1 دیده می شود و از دیگر معادلات حذف شده است.

آزمون بهینگی برای جواب BF جدید

معادله (0) جدید مقدار تابع هدف را در حالی می دهد که تنها متغیرهای غیرپایه در رابطه آن وجود دارند:

افزایش هر کدام از این متغیرهای غیر پایه (تا حدی که تغییر در متغیرهای پایه باعث خروج از منطقه موجه نشود) باعث حرکت در جهت یکی از جواب های BF مجاور می گردد. از آنجا که ضریب x1 مقداری مثبت است، افزایش x1 ما را به سمت جواب BF مجاوری خواهد برد که از جواب BF کنونی بهتر است، در نتیجه می توان گفت جواب کنونی بهینه نیست.

تکرار دوم و محاسبه جواب بهینه

با توجه به معادله

،

مقدار Z با افزایش متغیر x1 و نه متغیر x4 افزایش خواهد داشت. بنابراین مرحله اول متغیر x1 را به عنوان متغیر پایه ورودی در این تکرار انتخاب می کند.

در مرحله دوم برای محاسبه حداکثر مقداری که متغیر x1 می توان افزایش یابد از آزمون حداقل نسبت استفاده نموده و محاسبات آن با توجه به اینکه x4=0 به شرح زیر است:

بنابراین، آزمون حداقل نسبت بیان می کند که متغیر x5، متغیر پایه خروجی است.

در مرحله سوم، با جایگزینی متغیر x1 به جای x5 در متغیر های پایه و بکارگیری عملیات های جبری برای بازنویسی دستگاه معادلات فعلی به دستگاه معادلاتی که در آن ضرایب متغیر پایه ورودی،x1، به صورت (0,0,0,1) باشد خواهیم داشت:

بنابراین جواب BF بعدی عبارت است از (x1,x2,x3,x4,x5)=(2,6,2,0,0) که در این نقطه داریم Z=36. برای بکارگیری آزمون بهینگی در رابطه با جواب BF جدید، از معادله (0) کنونی که مقدار Z را بر اساس متغیرهای غیرپایه ارائه می دهد استفاده می کنیم:

با توجه به این معادله افزایش هر کدام از دو متغیر غیرپایه x4 و x5 باعث کاهش مقدار Z می گردد و در نتیجه هیچ کدام از جواب های BF مجاور به خوبی جواب فعلی نیست. بنابراین بر اساس مفهوم کلیدی 6 جواب BF کنونی جواب بهینه است.

با توجه به شکل اصلی مدل مسئله که دارای متغیرهای کمبود نمی باشد، جواب بهینه عبارت است از x1=2 ، x2=6 که در نتیجه خواهیم داشت:

.

در بخش آینده خلاصه ای از روش سیمپلکس بر اساس فرمت جدولی آن که کاربرد بسیار زیاد و راحتی دارد بیان خواهد شد.

مطلب مرتبط بعدی:فرمت جدولی روش سیمپلکس (قسمت اول)

مطلب مرتبط قبلی:دیدگاه جبری روش سیمپلکس (قسمت اول)


 
 
دیدگاه جبری روش سیمپلکس (قسمت اول)
نویسنده : محسن - ساعت ٤:٢٠ ‎ب.ظ روز ۱۳٩٠/٥/٢٠
 

برای ادامه بحث در روش سیمپلکس و توضیح دیدگاه جبری این روش همچنان از مسئله شرکت ویندور کمک می گیریم. برای بررسی رابطه مفاهیم هندسی و مفاهیم جبری روش سیمپلکس، مرحله به مرحله چگونگی حل مسئله مذکور از دو دیدگاه هندسی و جبری، در جدول 1 آورده شده است. دیدگاه هندسی که در مطالب قبل اشاره شد بر اساس قالب اصلی مدل که دارای متغیرهای کمبود نمی باشد ارائه گردید. در ادامه به جزئیات هر مرحله از دیدگاه جبری (ستون سوم جدول) اشاره شده است.

جدول 1. تفسیر هندسی و جبری چگونگی حل مسئله شرکت ویندور به کمک روش سیمپلکس

مرحله حل 

تفسیر هندسی 

تفسیر جبری 

شروع

(0,0) را به عنوان جواب CPF اولیه انتخاب کنید.

X1 و x2 را به عنوان متغیرهای غیرپایه برای جواب BF اولیه قرار دهید: (0,0,4,12,18)

تست بهینگی 

جواب بهینه نیست، زیرا حرکت بر هر دو لبه خروجی از (0,0) باعث افزایش Z می گردد.

جواب بهینه نیست، زیرا افزایش هر یک از متغیرهای غیرپایه (x1 و x2) باعث افزایش Z می گردد.

تکرار اول 

   

مرحله 1 

بر روی لبه واقع بر محور x2 حرکت کنید

مقدار x2 را تا حدی افزایش می دهیم که تغییر در متغیرهای پایه دیگر منجر به خروج از منطقه موجه نگردد.

مرحله 2 

هنگامی که به اولین مرز محدودیت جدید (2x2=12) برخورد کردید حرکت را متوقف نمایید.

زمانیکه اولین متغیر پایه به صفر رسید متوقف شوید. (x4)

مرحله 3 

نقطه تقاطع جفت مرز محدودیت جدید را بیابید: (0,6) جوای CPF جدید است.

با وارد شدن متغیر x2 در متغیرهای پایه و خارج شدن متغیر x4 از پایه و تبدیل آن به متغیر غیر پایه، دستگاه معادلات جدید حل شود: (0,6,4,0,6) جواب BF جدید است.

آزمون بهینگی 

جواب بهینه نیست زیرا با حرکت بر لبه خروجی از (0,6) به سمت راست مقدار Z افزایش می یابد.

جواب بهینه نیست زیرا افزایش متغیر غیر پایه x1 باعث افزایش Z می گردد.

تکرار دوم 

   

مرحله 1 

بر روی لبه انتخاب شده به جلو حرکت کنید 

مقدار x1 را تا حدی افزایش می دهیم که تغییر در متغیرهای پایه دیگر منجر به خروج از منطقه موجه نگردد.

مرحله 2 

هنگامی که به اولین مرز محدودیت جدید (3x1+2x2=18) برخورد کردید حرکت را متوقف نمایید.

زمانیکه اولین متغیر پایه به صفر رسید متوقف شوید. (x5)

مرحله 3 

نقطه تقاطع جفت مرز محدودیت جدید را بیابید: (2,6) جوای CPF جدید است.

با وارد شدن متغیر x1 در متغیرهای پایه و خارج شدن متغیر x5 از پایه و تبدیل آن به متغیر غیر پایه، دستگاه معادلات جدید حل شود: (2,6,2,0,0) جواب BF جدید است.

آزمون بهینگی 

جواب (2,6) بهینه است زیرا با حرکت بر هر کدام از لبه های خروجی از (2,6)، مقدار Z کاهش می یابد.

جواب (2,6,2,0,0) بهینه است زیرا افزایش هیچ کدام از متغیرهای غیر پایه، باعث افزایش Z نمی گردد.

 شروع

انتخاب x1 و x2 به عنوان متغیرهای غیرپایه (متغیرهایی که مقدار صفر می گیرند) در جواب BF اولیه بر اساس مفهوم کلیدی حل شماره 3 ارائه شده در مطلب 6 مفهوم کلیدی که بیان می کند در صورت امکان در مرحله شروع روش سیمپلکس بهتر است نقطه مبداء، یعنی نقطه ای که همه متغیرهای تصمیم برابر با صفر باشند، به عنوان جواب CPF اولیه انتخاب گردد؛ صورت گرفته است. این تصمیم باعث می شود متغیرهای پایه (x3,x4,x5) در مدل زیر به سادگی محاسبه شوند.

بنابراین جواب BF اولیه (0,0,4,12,18) خواهد بود.

همانطور که ملاحظه می کنید هر معادله تنها دارای یک متغیر پایه است که دارای ضریب یک می باشد و این متغیرهای پایه تنها در یک معادله حضور دارند و در معادلات دیگر وجود ندارند و به واسطه این دلایل، جواب اولیه را می توان به راحتی با مشاهده سیستم معادلات نیز بدست آورد. در ادامه خواهید دید هنگامی که مجموعه متغیرهای پایه تغییر می کنند، روش سیمپلکس از یک رویه جبری (حذف گوسی) برای تبدیل معادلات جاری به معادلاتی به همین قالب ساده استفاده می کنند تا بتوان جواب BF بعدی را به راحتی محاسبه نمود. به این قابل ساده از معادلات در اصطلاح فرم صحیح حاصل از حذف گوسی (proper form from Gaussian elimination) می گویند.

تست بهینگی

تابع هدف عبارت است از

بنابراین برای جواب BF اولیه Z=0 می گردد زیرا هیچ یک از متغیرهای پایه (x3,x4,x5) دارای ضریب غیر صفر در تابع هدف نیستند. ضریب هر متغیر غیر پایه (x1,x2) نشان دهنده نرخ بهبود در Z در صورت افزایش آن متغیر از مقدار 0 است. مقدار تغییر در متغیر غیر پایه تا حدی باید ادامه یابد که مقدار متغیرهای پایه جدید همچنان در معادلات صدق کنند. نرخ های بهبود در این مسئله (3 و 5) مقادیری مثبت هستند. بنابراین بر اساس مفهوم کلیدی شماره 6 نتیجه می گیریم که (0,0,4,12,18) بهینه نیست.

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

تعیین جهت حرکت (مرحله اول تکرار)

افزایش یک متغیر غیرپایه از مقدار 0 (تا حدی که مقدار متغیرهای پایه جدید همچنان در معادلات صدق کنند) یعنی حرکت بر روی یکی از لبه های خروجی از جواب CPF جاری. اینکه کدام متغیر غیر پایه باید برای افزایش انتخاب گردد، بر اساس مفاهیم کلیدی شماره 4 و 5 ارائه شده در مطلب 6 مفهوم کلیدی صورت می گیرد. از آنجا که نرخ بهبود تابع هدف، Z، برای متغیر x1 برابر است با 3 و برای متغیر x2 برابر است با 5، بنابراین متغیری انتخاب می شود که نرخ بهبود بیشتری داشته باشد یعنی در این مرحله متغیر x2 انتخاب می شود. بر اساس توضیحی که در ادامه می آید متغیر x2 به عنوان متغیر پایه ورودی برای تکرار اول انتخاب می شود.

در هر تکرار از روش سیمپلکس، هدف مرحله اول انتخاب یک متغیر غیر پایه برای افزایش از مقدار 0 است تا حدی که که مقدار متغیرهای پایه جدید همچنان در معادلات صدق کنند. افزایش مقدار متغیر غیرپایه انتخاب شده از صفر، این متغیر را به متغیری پایه برای جواب BF بعدی تبدیل می کند. بنابراین به این متغیر، متغیر پایه ورودی (entering basic variable) برای تکرار جاری می گویند.

تعیین محل توقف حرکت (مرحله دوم تکرار)

مرحله دوم تکرار به این سوال پاسخ می دهد که افزایش متغیر پایه ورودی باید تا کجا ادامه یابد. افزایش متغیر x2 باعث افزایش مقدار Z می گردد، بنابراین باید این افزایش تا حد ممکن ادامه یابد بدون آنکه جواب از منطقه موجه خارج شود. زمانی که متغیر غیر پایه x1=0 ثابت نگه داشته شود و x2 افزایش یابد، مقادیر متغیرهای پایه دیگر نیز با توجه به رابطه های زیر تغییر می کند:

تغییر در این متغیرهای پایه باید به گونه ای باشد که غیر منفی بمانند. متغیرهای غیر پایه (که متغیر ورودی را نیز شامل می شود) غیر منفی هستند اما باید کنترل کنیم که مقدار متغیر x2 تا چه مقدار می تواند افزایش یابد به شکلی که متغیر های پایه نیز در محدودیت های غیر منفی بودن صدق کنند:

روابط بالا نشان می دهد که متغیر x2 تا مقدار 6 می تواند افزایش یابد. در این مقدار متغیر x4 به مقدار صفر نزول می کند و افزایش بیشتر متغیر x2 باعث غیر منفی شدن متغیر x4 می گردد و این یعنی خروج از منطقه موجه.

به محاسباتی که در بالا انجام شد در اصطلاح آزمون حداقل نسبت (Minimum ratio test) می گویند. هدف از این آزمون تعیین متغیر پایه ای است که با افزایش متغیر ورودی زودتر از بقیه به مقدار صفر می رسد. اگر در هر یک از معادلات محدودیت های مسئله، ضریب متغیر ورودی صفر یا منفی باشد، متغیرهای پایه موجود در این معادلات در اثر افزایش متغیر ورودی کاهش نخواهند داشت. برای مثال در معادله اول متغیر x3 از افزایش متغیر x2 تاثیر نمی پذیرد و در نتیجه لازم نیست آزمون حداقل نسبت در رابطه با این متغیر انجام شود. همینطور دقت کنید که برای هر معادله ای که ضریب متغیر ورودی مثبت مطلق است (>0)، این آزمون نسبت مقدار سمت راست به ضریب متغیر ورودی در معادله مورد نظر را محاسبه می کند. متغیر پایه ای که در معادله ای قرار دارد که کمترین نسبت را داراست، اولین متغیری است که با افزایش متغیر ورودی به مقدار صفر نزول می کند.

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

بنابراین متغیر x4، متغیر پایه خروجی برای تکرار اول این مثال است.

مطلب مرتبط بعدی: دیدگاه جبری روش سیمپلکس (قسمت دوم)

مطلب مرتبط قبلی: آماده سازی مسئله برای حل با روش جبری سیمپلکس


 
 
آماده سازی مسئله برای حل با روش جبری سیمپلکس
نویسنده : محسن - ساعت ٧:٤٧ ‎ب.ظ روز ۱۳٩٠/٥/۱٩
 

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

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

انجام عملیات تبدیل علامت، احتیاج به وارد کردن متغیرهای کمبود (Slack variables) دارد. برای نمونه اولین محدودیت ساختاری مسئله شرکت ویندور را در نظر بگیرید:

متغیر کمبود برای این محدودیت به صورت زیر تعریف می شود:

که برابر است با مقدار کمبود عبارت سمت چپ نامعادله محدودیت. بنابراین داریم:

با در نظر گرفتن این معادله، x1 کوچکتر مساوی 4 خواهد بود اگر و تنها اگر

بنابراین محدودیت اولیه، معادل دو محدودیت زیر خواهد بود:

و

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

شکل 1. قالب اصلی مدل در سمت چپ و قالب افزوده مدل در سمت راست

اگرچه هر دو قالب مدل در اصل یک مسئله را نشان می دهند ولی قالب افزوده برای حل جبری و تعیین جواب های CPF بسیار راحت تر است. به این قالب از آن جهت قالب افزوده می گویند که با افزودن تعدادی متغیر کمکی به قالب مدل اصلی بدست می آید.

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

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

جواب افزوده (augmented solution) جوابی است برای متغیرهای اصلی مسئله (متغیرهای تصمیم) که متغیرهای کمبود را نیز شامل می شوند. برای مثال نقطه جواب (3,2) در مثال بالا به صورت افزوده به شکل جواب افزوده (3,2,1,8,5) در خواهد آمد زیرا مقادیر متغیرهای کمبود مرتبط عبارتند از x3=1، x4=8 و x5=5

جواب پایه (basic solution) عبارت است از یک جواب گوشه ای افزوده.

این حقیقت که جواب های گوشه ای و همچنین جواب های پایه می توانند موجه یا غیر موجه باشند تعریف زیر را الزامی می کند:

جواب پایه موجه (basic feasible (BF) solution) یک جواب CPF افزوده است.

بنابراین یکی از جوابهای CPF مسئله شرکت ویندور به صورت (0,6) معادل یک جواب پایه موجه (BF) به صورت (0,6,4,0,6) برای قالب افزوده آن مسئله است.

بنابراین تنها تفاوت جواب های پایه و جواب های گوشه ای (یا بین جواب های CPF و جواب های BF) وجود متغیرهای کمبود در جواب است و جواب گوشه ای مرتبط با هر جواب پایه با کنارگذاشتن متغیرهای کمبود از جواب به سادگی بدست می آید. بنابراین رابطه هندسی و جبری بین این دو جواب بسیار به هم نزدیک است که در مطالب بعدی بیشتر به آن می پردازیم.

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

2 = 3 – 5 = تعداد معادلات – تعداد متغیرها

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

جواب پایه دارای ویژگی های زیر است:

  1. هر متغیر در جواب پایه یا متغیر پایه است یا متغیر غیر پایه.
  2. تعداد متغیرهای پایه برابر است با تعداد محدودیت های ساختاری (که در قالب افزوده به صورت معادله درآمده اند). بنابراین تعداد متغیرهای غیرپایه برابر است با تعداد کل متغیرها منهای تعداد محدودیت های ساختاری.
  3. متغیرهای غیرپایه برابر با صفر تنظیم می شوند.
  4. مقدار متغیرهای پایه با قرار دادن مقدار صفر برای متغیرهای غیرپایه در مجموعه معادلات قالب افزوده و حل مجموعه معادلات بدست می آیند. به مجموعه متغیرهای پایه در اصطلاح پایه (basis) می گویند.
  5. اگر متغیرهای پایه در محدودیت های غیرمنفی صدق کنند، جواب پایه یک جواب BF خواهد بود.

برای مثال جواب BF اشاره شده در مثال بالا، (0,6,4,0,6)، را دوباره در نظر بگیرید. این جواب قبلاً با افزودن متغیرهای کمبود به جواب CPF مربوط به آن یعنی (0,6) بدست آمد. با این حال راه دیگر بدست آوردن این جواب به این شرح است که ابتدا دو متغیر x1 و x4 را به صورت اختیاری به عنوان متغیر غیر پایه انتخاب نموده و مقدار فرضی صفر را به آنها بدهید. سپس سه معادله مسئله را حل نمایید که به ترتیب جواب های x3=4، x2=6 و x5=6 از حل سه معادله بدست می آید که متغیرهای پایه جواب هستند و به ترتیب زیر بدست می آیند:

از آنجا که هر سه متغیر پایه غیر منفی هستند بنابراین این جواب پایه یک جواب پایه موجه یعنی جواب BF است.

جواب های BF مربوط به جواب های CPF مجاور را نیز در اصطلاح مجاور می نامند. یک راه ساده برای تعیین اینکه دو جواب BF مجاور هستند یا خیر به شرح زیر است:

دو جواب BF را مجاور گویند اگر به غیر از یکی از متغیرهای غیر پایه همه آنها مشابه باشند یا زمانیکه به غیر از یکی از متغیرهای پایه، همه آنها مشابه باشند.

در نتیجه حرکت از جواب BF جاری به یک جواب مجاور یعنی تبدیل یک متغیر غیر پایه به یک متغیر پایه و بالعکس تبدیل یک متغیر پایه به یک متغیر غیر پایه با مقدار صفر.

پس از تبدیل مسئله به شکل افزوده، در روش سیمپلکس باید معادله تابع هدف را به صورت یک معادله محدودیت جدید به مدل اضافه نمود. بنابراین قبل از شروع حل به روش سیمپلکس مسئله افزوده بالا را به صورت زیر بازنویسی می کنیم.

معادله شماره (0) در مدل بالا شبیه به یک محدودیت ساختاری است با این تفاوت که بدلیل آنکه به شکل معادله می باشد احتیاج به متغیر کمبود ندارد. با اضافه شدن یک معادله جدید به مجموعه معادلات، یک متغیر مجهول (Z) نیز به سیستم اضافه شده است. بنابراین هنگامی که از معادلات (1) تا (3) برای یافتن جواب پایه استفاده می شود به طور همزمان می توان از معادله (0) برای محاسبه Z نیز استفاده نمود.

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

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

مطلب مرتبط قبلی: 6 مفهوم کلیدی حل در روش سیمپلکس


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

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

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

مفهوم کلیدی 2: روش سیمپلکس یک الگوریتم تکراری است. این روش دارای یک رویه حل نظام مند است که در آن مجموعه ای از مراحل، که به آنها تکرار[1] می گویند، به طور متوالی انجام می شوند تا اینکه نتیجه مطلوب بدست آید. ساختار این تکرارها به صورت زیر است:

 

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

مفهوم کلیدی 3: در صورت امکان در مرحله شروع روش سیمپلکس بهتر است نقطه مبداء، یعنی نقطه ای که همه متغیرهای تصمیم برابر با صفر باشند، به عنوان جواب CPF اولیه انتخاب گردد. این انتخاب به ویژه در مسائلی که تعداد زیادی متغیرهای تصمیم دارند بسیار کمک می کند، به طوریکه نیازی نیست در مرحله شروع برای یافتن یک جواب CPF اولیه عملیات جبری استفاده شود.

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

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

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

در تکرار اول حل مسئله شرکت ویندور، با در نظر داشتن تابع هدف Z=3x1+5x2، حرکت روی لبه واقع بر محور x2 تابع هدف را با سرعت بیشتری نسبت به حرکت روی لبه واقع بر محور x1 افزایش می دهد. هر یک واحد حرکت بر لبه واقع بر محور x2 تابع هدف را 5 واحد افزایش می دهد در صورتی که هر یک واحد حرکت بر لبه واقع بر محور x1 تابع هدف را 3 واحد افزایش می دهد. بنابراین حرکت باید بر لبه واقع بر محور x2 صورت گیرد. در مرحله تکرار دوم تنها لبه خروجی از (0,6) که نرخ رشد تابع هدف در مسیر آن مثبت است، لبه ای است که به (2,6) ختم می شود، در نتیجه حرکت در مسیر این لبه صورت می گیرد.

مفهوم کلیدی 6: در مفهوم کلیدی 5 اشاره شد که روش سیمپلکس چگونه هر یک از لبه هاب خروجی از جواب CPF جاری را بررسی می کند. این بررسی با تعیین نرخ رشد تابع هدف در جهت لبه ها صورت می گیرد. اگر نرخ رشد تابع هدف در مسیر یک لبه مثبت باشد به این معناست که نقطه CPF مجاور که در انتهای لبه مذکور قرار دارد بهتر از جواب CPF جاری است. به همین ترتیب اگر این نرخ منفی باشد جواب CPF مجاور انتهای لبه مورد نظر از جواب CPF جاری بدتر است. اگر هیچ کدام از لبه های خروجی از جواب  CPFجاری دارای نرخ رشد مثبت نباشند، این جواب بهینه است.

در مثال مرتبط قبل حرکت بر روی هر دو لبه خروجی از (2,6) باعث کاهش مقدار تابع هدف می شود و از آنجا که هدف ماکزیمم کردن تابع هدف است، در نتیجه نقطه (2,6) جواب بهینه خواهد بود.

پست مرتبط بعدی: آماده سازی مسئله برای حل با روش جبری سیمپلکس

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



[1] iteration


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

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

شروع: نقطه (0,0) را به عنوان جواب CPF اولیه آزمون می کنیم. (اینکه کدام نقطه به عنوان نقطه CPF اولیه انتخاب شود کاملاً اختیاری است اما به دلیل راحتی محاسبه اغلب نقطه (0,0) به عنوان CPF اولیه انتخاب می شود.)

آزمون بهینگی: نتیجه می شود که (0,0) جواب بهینه نیست. (مقدار تابع هدف جواب های CPF مجاور (0,0) بهتر هستند.)

تکرار 1: با رعایت موارد زیر به سمت یک جواب CPF مجاور بهتر،(0,6)، حرکت نمایید.

  1. با در نظر گرفتن دو لبه خروجی از نقطه (0,0)، بر روی لبه ای که روی محور x2 واقع شده است حرکت می کنیم. (با در نظر داشتن تابع هدف Z=3x1+5x2، حرکت روی لبه واقع بر محور x2 تابع هدف را با سرعت بیشتری نسبت به حرکت روی لبه واقع بر محور x1 افزایش می دهد. هر یک واحد حرکت بر لبه واقع بر محور x2 تابع هدف را 5 واحد افزایش می دهد در صورتی که هر یک واحد حرکت بر لبه واقع بر محور تابع هدف را 3 واحد افزایش می دهد.)
  2. حرکت را تا جایی ادامه می دهیم که به یک مرز محدودیت جدید برسیم که در اینجا مرز محدودیت 2x2=12 است. (حرکت بیشتر در جهت انتخاب شده در مرحله 1 باعث خروج از فضای موجه می شود.)
  3. نقطه تلاقی این دو مرز محدودیت را محاسبه کنید: (0,6) (از دو معادله این مرز محدودیت ها، x1=0 و 2x2=12 می توان این نقطه را محاسبه نمود.)

آزمون بهینگی: نتیجه می شود که (0,6) جواب بهینه نیست. (مقدار تابع هدف یکی از جواب های CPF مجاور (0,6) بهتر هستند.)

تکرار 2: با رعایت موارد زیر به سمت جواب CPF مجاور بهتر،(2,6)، حرکت نمایید.

  1. با در نظر گرفتن دو لبه خروجی از نقطه (0,6)، بر روی لبه ای که به سمت راست می رود حرکت می کنیم. (حرکت روی این لبه تابع هدف را افزایش می دهد در حالیکه حرکت بر لبه دیگر که به سمت پایین هدایت می کند تابع هدف را کاهش می دهد.)
  2. حرکت را تا جایی ادامه می دهیم که به یک مرز محدودیت جدید برسیم که در اینجا مرز محدودیت 3x1+2x2=12 است. (حرکت بیشتر در جهت انتخاب شده در مرحله 1 باعث خروج از فضای موجه می شود.)
  3. نقطه تلاقی این دو مرز محدودیت را محاسبه کنید: (2,6) (از دو معادله این مرز محدودیت ها، 3x1+2x2=12 و 2x2=12 می توان این نقطه را محاسبه نمود.)

آزمون بهینگی: نتیجه می شود (2,6) جواب بهینه است در نتیجه توقف می کنیم. (هیچکدام از جواب های CPF مجاور بهتر نیستند.)

دنباله جوابهای CPF آزمون شده در شکل 1 نشان داده شده است. اعداد داخل دایره های کوچک نشان دهنده شماره تکراری است که جواب CPF در آن بررسی شده است.

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

 در مطلب مرتبط بعدی به 6 مفهوم کلیدی روش سیمپلکس پرداخته می شود که به نوعی منطق قرار گرفته پشت هر یک از مراحل بالا را بیان می کنند.

پست مرتبط بعدی:6 مفهوم کلیدی حل در روش سیمپلکس

پست مرتبط قبلی: مقدمه ای بر روش سیمپلکس


 
 
مقدمه ای بر روش سیمپلکس - 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/