Online User تحقیق در عملیات - مدیریت صنعتی Industrial Management

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

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

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

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

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

(800 کلمه)

مطلب مرتبط بعدی:

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

 


 
 
آیا تعداد جواب های گوشه ای همه مسائل برنامه ریزی خطی متناهی است؟
نویسنده : محسن - ساعت ٥:۱۱ ‎ب.ظ روز ۱۳٩٢/۱/۱٦
 

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

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

(450 کلمه)

 

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

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


 
 
ترجمه جزوه بهینه سازی عدم قطعیت دانشگاه MIT
نویسنده : محسن - ساعت ٥:۳٦ ‎ب.ظ روز ۱۳٩۱/۱٠/٢٩
 

جزوه ای که در این مطلب ارائه شده است ترجمه بخش "بهینه سازی عدم قطعیت" (optimization under Uncertainty) جزوه درس بهینه سازی سیستم ها: مدل ها و محاسبات دانشگاه MIT آمریکا است که توسط دکتر Robert M.Freund در سال 2004 تدریس شده است.  این بخش از جزوه توسط نویسنده وبلاگ ترجمه شده و در 23 صفحه و در قالب  PDF ارائه می گردد.

   فهرست مطالب و یک صفحه نمونه را می توانید در ادامه مطلب ببینید.

جهت دریافت اطلاعات نحوه خرید این فایل با m.rahimi.m@gmail.com تماس بگیرید.


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

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

...


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

(550 کلمه)

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

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


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

عنوان جزوه: برنامه ریزی آرمانی

درس: پژوهش عملیاتی 3

استاد: دکتر سلیمی فرد (phd, Lancaster university, UK)

دانشگاه: خلیج فارس

 با کلیک روی آیکون زیر می توانید دانلود کنید:

       

   PDF - 9 pages - 2.2MB

برای دریافت فایل های دانلود و اطلاع از مطالب به روز شده در ایمیل خود کافیست درخواست عضویت خود را همراه با ادرس ایمیل از طریق بخش نظرات یا سامانه "تماس با ما" (ستون سمت چپ وبلاگ) و یا ارسال یک ایمیل به آدرس m.rahimi.m@gmail.com اعلام فرمایید.


 
 
محصول جدید: کتاب مقدمه ای بر تحقیق در عملیات و برنامه ریزی خطی
نویسنده : محسن - ساعت ۱۱:٢٧ ‎ق.ظ روز ۱۳٩۱/٧/۱٤
 

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

تالیف: هیلیر و لیبرمن

ترجمه: محسن رحیمی (مدیر وبلاگ)

فرمت: PDF

تعداد صفحات: 133

حجم: Mb 7.7 

فهرست کتاب را می توانید از اینجا دانلود کنید.

 

  جهت دریافت اطلاعات نحوه خرید این کتاب با m.rahimi.m@gmail.com تماس بگیرید.


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

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

  

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

(1000 کلمه)

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

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


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

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

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

(1500 کلمه)

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

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


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

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

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

(1260 کلمه)

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

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


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

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

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

(760 کلمه)

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

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


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

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

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

(670 کلمه)

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

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


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

عنوان جزوه: برنامه ریزی صفر و یک

درس: پژوهش عملیاتی 3

استاد: دکتر سلیمی فرد (phd, Lancaster university, UK)

دانشگاه: خلیج فارس

 با کلیک روی آیکون زیر می توانید دانلود کنید:

       

   PDF - 5 pages (29 slides)- 1.4MB


 
 
روش نقاط داخلی (Interior-point approach)
نویسنده : محسن - ساعت ٩:۳٦ ‎ب.ظ روز ۱۳٩٠/٩/٥
 

جالب‌ترین روشی که در دهه 1980 برای حل مسائل برنامه ریزی خطی ابداع شد روشی بود به نام روش نقاط داخلی (Interior-point approach) که توسط یک ریاضیدان جوان به نام نارندرا کارمارکار در آزمایشگاه AT&T Bell در سال 1984 معرفی شد. اگر چه این روش در ابتدا در مقایسه با روش سیمپلکس توجه‌ها را به خود جلب ننمود اما اصول و مفاهیم کلیدی به کار رفته در آن که در ادامه نیز به آن‌ها می‌پردازیم نشان می‌داد که این روش خاص پتانسیل حل مسائل برنامه ریزی خطی بسیار بزرگ را به گونه‌ای دارد که روش سیمپلکس به سختی آن‌ها را حل می‌کند.

 

 

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

(588 کلمه)

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

مطلب مرتبط قبلی: تحلیل های پس از بهینه سازی به کمک سیمپلکس


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

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

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

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

(250 کلمه)

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

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


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

عنوان جزوه: برنامه ریزی عدد صحیح

درس: پژوهش عملیاتی 3

استاد: دکتر سلیمی فرد (phd, Lancaster university, UK)

دانشگاه: خلیج فارس

 با کلیک روی آیکون زیر می توانید دانلود کنید:

       

   PDF - 17 pages - 2.2MB


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

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

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

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

 (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/


 
 
فرضیات مدل برنامه ریزی خطی: فرض تقسیم پذیری و فرض معین بودن
نویسنده : محسن - ساعت ۳:۳٦ ‎ب.ظ روز ۱۳٩٠/٤/٢٧
 

فرض تقسیم پذیری

فرض اساسی دیگری که در مدل برنامه ریزی خطی مطرح است، فرض تقسیم پذیری[1] است که به مقادیر قابل قبول متغیرهای تصمیم می پردازد:

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

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

فرض معین بودن

آخرین فرضی که باید برقرار گردد مربوط است به پارامترهای مدل که شامل ضریب تابع هدف، cj، ضرایب محدودیت های ساختاری، aij و مقادیر سمت راست محدودیت های ساختاری، bi است.این فرض اغلب به این صورت بیان می شود:

مقادیر اختصاص یافته به پارامترهای مدل برنامه ریزی خطی باید ثابت و معین باشند.

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

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

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



[1] Divisibility assumption

[2] integer programming models

[3] certainty assumption

[4] sensitivity analysis

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

پست مرتبط قبلی: فرضیات برنامه ریزی خطی: فرض جمع پذیری


 
 
فرضیات مدل برنامه ریزی خطی: فرض جمع پذیری Additivity assumption
نویسنده : محسن - ساعت ٢:٥٢ ‎ب.ظ روز ۱۳٩٠/٤/٢٥
 

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

هر تابعی در مدل برنامه ریزی خطی (چه تابع هدف و چه توابع محدودیت) باید به صورت مجموع سهم فعالیت های مجزا در آن تابع ارائه شده باشد.

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

جدول 1. نمونه هایی از رعایت فرض جمع پذیری و عدم رعایت آن در تابع هدف

(x1,x2)

مقدار Z

جمع پذیری رضایتبخش

انحراف از جمع پذیری

مورد اول

مورد دوم

(1,0)

3

3

3

(0,1)

5

5

5

(1,1)

8

9

7

 ستون مربوط به مورد اول جدول 1 مربوط است به تابع هدفی به شکل Z=3x1+5x2+x1x2 به طوریکه برای (x1,x2)=(1,1) داریم Z=3+5+1=9 و در نتیجه از فرض جمع پذیری انحراف دارد. از آنجا که همه متغیرها دارای توان یک هستند فرض تناسب در این تابع رعایت شده است. این مورد زمانی پیش می آید که برای مثال دو کالا از لحاظ اقتصادی مکمل یکدیگر باشند و سود را افزایش دهند. برای مثال فرض کنید تبلیغات برای یکی از کالاها منجر شود که به طور موثری هر دو کالا فروش روند. از آن جهت که هزینه های تبلیغاتی برای یکی از کالا ها حذف شده است، در نتیجه سود کل حاصل از فروش هر دو کالا بیشتر از مجموع سود حالاتی است که محصولات یک و دو به تنهایی تولید شوند.

ستون مربوط به مورد دوم جدول 1 نیز مربوط است به تابع هدفی به شکل Z=3x1+5x2-x1x2 به طوریکه برای (x1,x2)=(1,1) داریم Z=3+5-1=7 و در نتیجه از فرض جمع پذیری انحراف دارد. برعکس مورد اول، این مورد زمانی پیش می آید که برای مثال دو کالا حالت رقابتی داشته باشند و سود حاصل از تولید هردو محصول کمتر از مجموع سود حالاتی است که محصولات یک و دو به تنهایی تولید شوند. برای مثال فرض کنید هر دو محصول برای تولید احتیاج به یکی از تجهیزات کارخانه داشته باشند. اگر تصمیم گرفته شود تنها یکی از محصولات تولید شود، این ماشین تمام وقت در اختیار تولید محصول مورد نظر خواهد بود. اما در صورتی که تصمیم گرفته شود هر دو محصول تولید شوند این ماشین باید در ساعاتی از روز به تولید محصول اول و در ساعاتی از روز به تولید محصول دوم بپردازد و این کار مستلزم از دست رفتن زمان و همچنین صرف هزینه های خاموش کردن و راه اندازی مجدد آن است. به دلیل وجود این هزینه های اضافی، سود حاصل از تولید هر دو محصول کمتر از مجموع سود حالاتی است که محصولات یک و دو به تنهایی تولید شوند که احتیاج به صرف هزینه های خاموش کردن و راه اندازی مجدد ندارند.

در توابع محدودیت نیز حالات مشابهی از تعامل بین متغیرها می تواند منجر به انحراف از فرض جمع پذیری گردد. برای مثال، محدودیت ساختاری سوم مسئله شرکت ویندور، 3x1+2x2<=18، را در نظر بگیرید. این محدودیت تنها محدودیتی در مسئله است که هر دو متغیر را شامل می شود. این محدودیت مربوط است به محدودیت ظرفیت زمانی کارخانه سوم که بیشتر از 18 ساعت در هفته نمی تواند در فرآیند تولید شرکت کند و عبارت سمت راست این محدودیت، 3x1+2x2، نشان می دهد که برای تولید یک دسته در هفته از هر محصول به چه مقدار زمان نیاز است. ستون جمع پذیری رضایتبخش در جدول 2 حالت بالا را نشان می دهد و دو ستون بعدی مواردی را نشان میدهند که در تابع محدودیت آنها عبارات ضربی به کار رفته است و در نتیجه فرض جمع پذیری در رابطه با آنها صدق نمی کند. برای هر سه ستون سهم مجزای هر محصول از ظرفیت زمانی کارخانه سوم همانند آنچه در جدول 1 آمده است ارائه شده است، یعنی برای محصول اول 3x1 و برای محصول دوم 2x2 و یا 3(2)=6 به ازای x1=2 و 2(3)=6 به ازای x2=3. همچنین همانند جدول 1 اعدادی که در سطر آخر ارائه شده است مربوط است به مقدار کل تابع محدودیت زمانی که هر دو محصول با هم تولید شوند.

جدول 2. نمونه هایی از رعایت فرض جمع پذیری و عدم رعایت آن در محدودیت ها

(x1,x2)

مقدار منبع استفاده شده

جمع پذیری رضایتبخش

انحراف از جمع پذیری

مورد سوم

مورد چهارم

(2,0)

6

6

6

(0,3)

6

6

6

(2,3)

12

15

8/10

 ستون مربوط به مورد سوم جدول 2 مربوط است به محدودیتی به شکل 3x1+2x2+0.5x1x2 به طوریکه برای (x1,x2)=(2,3) داریم 6+6+3=15 و در نتیجه از فرض جمع پذیری 6+6=12 انحراف دارد. این حالت دقیقاً مانند مورد دوم جدول 1 زمانی پیش می آید که باید زمانی را صرف خاموش کردن و دوباره راه اندازی کردن دستگاهی نمود تا بتوان هر دو محصول را تولید کرد. عبارت ضربی حاضر در تابع محدودیت، (0.5x1x2)، بیانگر میزان زمان هدر رفته در این فرآیند است. دقت داشته باشید که زمان هدر رفته به دلیل تغییر محصول با علامت مثبت در تابع محدودیت آورده شده است زیرا مقدار این تابع، زمان تولید است در حالیکه در مورد دوم جدول 1  عبارت ضربی با علامت منفی در تابع هدف ظاهر می شود چون این تابع سود را اندازه گیری می کند.

ستون مربوط به مورد چهارم جدول 2 مربوط است به محدودیتی به شکل 3x1+2x2-0.1x12x2 به طوریکه برای (x1,x2)=(2,3) داریم 6+6-1.2=10.8 و در نتیجه از فرض جمع پذیری 6+6=12 انحراف دارد. این مورد نیز در مواردی مشابه مورد سوم بروز می کند فرض کنید هر دو محصول برای تولید به به یکی از تجهیزات کارخانه نیازمند باشند ولی زمان لازم برای تغییر کاربری دستگاه ناچیز باشد. از آن جهت که هر محصول برای تولید از رشته ای از تجهیزات عبور می کند، زمان هایی وجود خواهد داشت که یک دستگاه تولیدی بلا استفاده باشد. بنابراین می توان از این زمان های به اصطلاح مرده برای تولید محصول دیگر استفاده نمود. در نتیجه کل زمان تولید مورد استفاده برای تولید دو محصول کمتر از مجموع زمان لازم برای تولید دو محصول در حالتی است که تنها تولید شوند.

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

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


[1] Additivity assumption

پست مرتبط بعدی:فرضیات مدل برنامه ریزی خطی: فرض تقسیم پذیری و فرض معین بودن

پست مرتبط قبلی: فرضیات مدل برنامه ریزی خطی: فرض تناسب


 
 
فرضیات مدل برنامه ریزی خطی: فرض تناسب - Proportionality assumption
نویسنده : محسن - ساعت ۸:٤٠ ‎ب.ظ روز ۱۳٩٠/٤/۱٩
 

همه فرضیات برنامه ریزی خطی در مدل مسئله شرکت ویندور رعایت شده اند. با این حال بهتر است این فرضیات بیشتر تشریح شود تا بتوان ارزیابی ساده تر و مناسب تری راجع به امکان استفاده از تکنیک های برنامه ریزی خطی در مسائل مختلف انجام داد. بنابراین در این مطلب و مطالب بعدی به این سوال پاسخ می دهیم که چرا تیم OR در رابطه با مسئله شرکت ویندور به این نتیجه رسیدند که مدل برنامه ریزی خطی می تواند نمایشی رضایت بخش از مسئله ارائه دهد.

فرض تناسب

فرض تناسب که هم درباره تابع هدف باید وجود داشته باشد و هم درباره محدودیت های ساختاری، به صورت زیر بیان می شود:

سهم هر فعالیت در مقدار تابع هدف،Z، متناسب است با سطح آن فعالیت،xj، که به صورت cjxj در تابع هدف نشان داده می شود. همچنین سهم هر فعالیت در عبارت سمت راست هر محدودیت، متناسب است با سطح آن فعالیت،xj، که به صورت aijxj در محدودیت نشان داده می شود. در نتیجه این فرض باعث می شود هیچ یک از متغیرها در هیچ یک از عبارات مدل برنامه ریزی خطی، توانی غیر یک نداشته باشند.

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

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

جدول 1. نمونه هایی از رعایت فرض تناسب و عدم رعایت آن

تناسب رضایتبخش

مثال هایی از عدم رعایت فرض تناسب

مورد اول

مورد دوم

مورد سوم

0

0

0

0

0

1

3

2

3

3

2

6

5

7

5

3

9

8

12

6

4

12

11

18

6

ستون مربوط به مورد اول را در جدول 1 در نظر بگیرید. این مورد می تواند زمانی پیش بیاید که برای تولید محصول اول نیاز به صرف هزینه های راه اندازی باشد، برای مثال اگر برای تنظیم تجهیزات و دستگاه ها برای شروع کار تولید لازم باشد هزینه ای صرف شود و یا اگر لازم باشد برای توزیع محصول مراکز توزیع جدید ایجاد شود. از آنجا که تنها برای یک بار این هزینه ها پرداخت می شوند، برای وارد کردن آنها در تابع هدف، واحد هزینه های راه اندازی باید بر پایه هزینه بر هفته تغییر یابند تا قابل اضافه شدن در تابع هدف Z که سود بر هفته است باشند. فرض کنید این تغییر واحد صورت گرفته باشد و کل هزینه راه اندازی که باید از کاسته شود معادل عدد یک محاسبه شده باشد. به این ترتیب سهم تولید محصول اول در تابع هدف Z، باید به صورت 3x1-1 برای x1>0 باشد و برای زمانی که محصول یک تولید نشود یعنی x1=0، این سهم به صورت 3x1=0 باید محاسبه شود. این تابع سود که در شکل 1 رسم شده است مشخصاً با x1 متناسب نیست و در نتیجه فرض تناسب در مورد آن رعایت نشده است. اگر سهم محصول اول در Z به ازای همه x1>=0 برابر بود با 3x1-1 آنگاه می توانستیم عدد ثابت، -1، را از تابع هدف حذف کنیم بدون اینکه تغییری در جواب بهینه حاصل شود و همچنین فرض تناسب نیز رعایت شده است. اما از آنجا که برای x1=0 شرط بالا صحیح نیست در نتیجه نمی توان از این تکنیک استفاده نمود.

شکل 1. ترسیم مثال مورد اول انحراف از فرض تناسب در جدول 1

مورد دوم جدول 1 نیز شباهت زیادی با مورد اول دارد، با این حال این مورد در شرایط کاملاً متفاوت ظهور می کند. در این مورد هیچ هزینه راه اندازی وجود ندارد و سود حاصل از تولید اولین دسته از محصول برابر است با 3 (هزار دلار) است که با مثال دارای فرض تناسب یکسان است. با این حال در این مورد افزایش نرخ سود وجود دارد به این معنا که شیب تابع سود محصول یک (در شکل 2 ببینید) با افزایش x1 افزایش می یابد. این نوع انحراف از فرض تناسب ممکن است در اثر صرفه جویی در مقیاس حاصل شود که گاهی در سطوح بالای تولید ایجاد می شود. صرفه جویی در مقیاس در اثر مواردی مانند استفاده از اتوماسیون و تجهیزات حجم بالای با کیفیت، خرید ارزان تر حجم زیادی از مواد اولیه و یا اثر منحنی یادگیری نیروی کار که باعث می شود نیروی کار در اثر تجربه بیشتر اثربخشی و کارایی بالاتری داشته باشند، ایجاد می شود. به عبارت دیگر در هر شرایطی که با افزایش تولید، نرخ رشد هزینه ها کاهش یابد و قیمت فروش کالا ثابت بماند، نرخ رشد سود افزایش می یابد و می تواند مثالی از مورد دوم جدول 1 باشد.

شکل 2. ترسیم مثال مورد دوم انحراف از فرض تناسب در جدول 1

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

شکل 3. ترسیم مثال مورد سوم انحراف از فرض تناسب در جدول 1

 

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

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

 پست مرتبط بعدی:فرضیات مدل برنامه ریزی خطی: فرض جمع پذیری

پست مرتبط قبلی: اصطلاحات رایج در حل مدل برنامه ریزی خطی


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

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

جواب موجه جوابی است که در همه محدودیت ها صدق کند و جواب غیرموجه جوابی است که حداقل از یکی از محدودیت ها انجراف داشته باشد و در آن صدق نکند. برای نمونه نقاط (2,3) و (4,1) در شکل 4 جواب های موجه هستند در حالیکه نقاط (-1,3) و (4,4) جواب های غیر موجه هستند. مجموعه همه جواب های موجه را فضای موجه می نامند. در شکل 4 منطقه هاشور خورده معادل فضای موجه است.

ممکن است مسئله ای دارای جواب موجه نباشد. در مثال شرکت ویندور اگر محدویت جدیدی با این عنوان اضافه کنیم که سود حاصل از محصولات جدید باید حداقل 50000 دلار در هفته باشد، رابطه جدیدی به صورت 3x1+5x2>=50 به مدل اضافه میگردد که در صورت رسم آن فضای موجه از بین می رود. به این معنی که هیچ ترکیبی از محصولات جدید نمی تواند در همه محدودیت ها صدق کند. این حالت در شکل 1 قابل مشاهده است.

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

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

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

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

 

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

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

شکل 4. پنج نقطه مشخص شده جواب های CPF مسئله شرکت ویندور هستند.

 در ادامه درباره رابطه بین جواب بهینه و جواب CPF توضیح مختصری می دهیم. یک مسئله برنامه ریزی خطی را که دارای جوای های موجه و فضای موجه کراندار است را در نظر بگیرید. این مسئله لزوماً دارای چند جواب CPF و حداقل یک جواب بهینه است. در فصل های آینده ثابت خواهیم کرد که بهترین جواب CPF حتماً یکی از جواب های بهینه این مسئله است. بنابراین اگر مسئله تنها دارای یک جواب بهینه باشد، آن جواب همان بهترین جواب CPF است و اگر جزء مسائل دارای جواب بهینه چندگانه باشد، حداقل دو جواب CPF در بین جواب های بهینه وجود دارد. در مسئله شرکت ویندور تنها یک جواب بهینه، (2,6)، وجود دارد که با مشاهده شکل 4 مشخص می شود که این نقطه یکی از جواب های CPF است. در صورتی که شکل تغییر یافته این مسئله که دارای جواب بهینه چندگانه است را در نظر بگیریم که در شکل 2 نشان داده شده است، مشخص می شود که دو تا از جواب های بهینه (2,6) و (4,3) جواب CPF هستند.

پست مرتبط بعدی: فرضیات مدل برنامه ریزی خطی: تناسب

پست مرتبط قبلی: قالب استاندارد مدل برنامه ریزی خطی


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

حال که به کمک مسئله شرکت ویندور آشنایی اولیه ای با برنامه ریزی خطی و مدل آن بدست آمد، می توانیم مدلی ریاضی برای شکل عمومی مسئله تخصیص منابع به فعالیت ها بسازیم. این مسئله به دنبال یافتن مقادیر مناسب برای x1,x2,…xn است به طوریکه تابع Z ماکزیمم گردد، یعنی:

و همچنین محدودیت های زیر نیز رعایت شود:

و

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

تابعی را که باید ماکزیمم شود، تابع هدف می نامند. قید های ذکر شده در مدل را نیز محدودیت می گویند. m محدودیت اول را ، محدودیتهای تابعی یا محدودیتهای ساختاری می گویند. همچنین به محدودیت های xj>=0، محدودیت های غیر منفی یا شرط غیر منفی بودن می گویند.

قالب های دیگر

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

  • تابع هدف به جای ماکزیمم شدن باید مینیمم گردد:

  • برخی از محدودیتهای تابعی از نوع نامعادلات بزرگتر مساوی هستند:برای تعدادی از iها
  • برخی از محدودیتهای تابعی از نوع معادله هستند:برای تعدادی از iها
  • برای برخی از متغیرهای تصمیم شرط غیر منفی بودن وجود ندارد و در اصطلاح می نویسند:

    برای تعدادی از jها xj آزاد در علامت

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

 پست مرتبط بعدی: اصطلاحات رایج در حل مدل برنامه ریزی خطی

پست مرتبط قبلی: اصطلاحات و اجزای مدل برنامه ریزی خطی


 
 
اصطلاحات و اجزای مدل برنامه ریزی خطی
نویسنده : محسن - ساعت ۸:۱۱ ‎ب.ظ روز ۱۳٩٠/٤/۱٤
 

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

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

اصطلاحات رایج در برنامه ریزی خطی

مسئله شرکت ویندور

مسئله عمومی

ظرفیت تولید کارخانه ها

3 کارخانه

منابع

m منبع

تولید محصولات

2 محصول

نرخ تولید محصول jام، xj

فعالیت ها

n فعالیت

سطح انجام فعالیت jام، xj

سود Z

معیار ارزیابی عملکرد کل سیستم Z

 

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

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

مقدار معیار ارزیابی عملکرد کل سیستم

Z =   

سطح فعالیت jام (برای j = 1,2,…,n)

xj =   

مقدار افزایش Z در اثر افزایش یک واحدی سطح فعالیتj ام

cj =   

مقدار موجود از منبع ام (برای i = 1,2, …, m)

bi =   

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

aij =  

از آنجا که هدف برنامه ریزی خطی کمک به تصمیم گیری در مورد انتخاب سطح انجام فعالیت ها است، لذا به x1,x2,…,xn در اصطلاح متغیرهای تصمیم[1] می­گویند. طبق جدول مقادیر cj، bj و aij (برای i=1,2,…,m و j = 1,2,…,n) داده های ثابت مدل هستند که در اصطلاح به آنها پارامترهای مدل می گویند.



[1]  decision variables

پست مرتبط بعدی: قالب استاندارد مدل برنامه ریزی خطی

پست مرتبط قبلی: حل یک مسئله ساده برنامه ریزی خطی


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

 این پروژه تحقیقی با نام «روشی برای رتبه بندی در مسائل تصمیم گیری چند معیاری؛ PROMETHEE» در فرمت PDF به حجم 555 KB و در 14 صفحه با فهرست زیر تنظیم شده است:

  • مقدمه
  • اصول تکنیک PROMETHEE
  • توسعه مفهوم معیار
  • نوع i معیار معمولی
  • نوع II : شبه معیار
  • نوع III: معیار با ترجیح خطی
  • نوع IV: معیار سطحی
  • نوع V: معیار با ترجیح خطی و منطقه بی تفاوتی
  • نوع VI: معیار گوسی
  • گراف رتبه بندی
  • بهره برداری از گراف رتبه بندی
  • روش PROMETHEE I: رتبه بندی نسبی گزینه ها
  • روش PROMETHEE II: رتبه بندی کامل گزینه ها
  • مراجع

 برای نمونه صفحه شماره 9 این پروژه در عکس زیر ارائه شده است.

جهت دریافت اطلاعات نحوه خرید این پروژه با m.rahimi.m@gmail.com تماس بگیرید.

 


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

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

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

محصول جدید اول: در شیشه ای 8 فوت با چارچوب آلومینیومی

محصول جدید دوم: پنجره 4 در 6 فوت با قاب چوبی

محصول اول برای تولید به بخشی از ظرفیت تولید کارخانه 1 و 3 نیاز دارد و به تجهیزات کارخانه 2 احتیاجی ندارد. محصول دوم نیز تنها به کارخانه های 2 و 3 نیاز دارد. گزارش های بازاریابی نشان می دهند، هر تعداد که شرکت بتواند از این دو محصول تولید کند، در بازار به فروش خواهد رسید. با این حال، چون هر دو محصول جدید برای تولید به ظرفیت کارخانه سوم نیاز دارند، مشخص نیست چه تر کیبی از این دو محصول تولید شود تا سود بیشتری حاصل گردد. برای پاسخگویی به این سوال، شرکت یک تیم OR تشکیل داده است.

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

«تعیین کنید چه نرخی از دو محصول جدید باید تولید شوند تا سود کل شرکت ماکزیمم گردد و در عین حال محدودیت های مربوط به ظرفیت تولید هر سه کارخانه نیز در نظر گرفته شود. هر محصول در دسته های 20 تایی تولید می شود، در نتیجه نرخ تولید به صورت تعداد دسته های تولیدی در هر هفته تعریف می شود. همچنین هر ترکیبی از نرخ تولید دو محصول که در محدودیتها صدق کند قابل قبول است و از این نظر محدودیتی وجود ندارد؛ حتی اگر از یک محصول اصلاً تولید نشود و کل ظرفیت به تولید محصول دیگر اختصاص یابد.»

حل این مسئله و تفسیرهای آن در فایل پیوست قابل دانلود است.

دانلود:          PDF - 8 pages - 857Kb

 

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

پست مرتبط قبلی: مقدمه ای بر برنامه ریزی خطی


 
 
مقدمه ای بر برنامه ریزی خطی (Linear Programming)
نویسنده : محسن - ساعت ۳:۳۱ ‎ب.ظ روز ۱۳٩٠/٤/٧
 

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

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

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

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


[1] Linear Programming

[2] Simplex

 

پست مرتبط بعدی: حل یک مسئله ساده برنامه ریزی خطی

پست مرتبط قبلی: اثرات تحقیق در عملیات


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

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

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

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

پست مرتبط بعدی: مقدمه ای بر برنامه ریزی خطی

پست مرتبط قبلی: ماهیت تحقیق در عملیات


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

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


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

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

مشخصه دیگری که برای OR می توان بیان کرد این است که OR همیشه تلاش می کند بهترین جواب (که به آن پاسخ بهینه[2] می گویند) را برای مسئله تحت بررسی خود ارائه دهد. در این علم هدف تنها بهبود وضع موجود نیست بلکه تعیین بهترین تصمیم های ممکن است. اگر چه در مسائل مختلف معنا و تفسیر بهینه بودن پاسخ ها متفاوت است با این حال جستجوی بهینگی از مهمترین موضوعات در علم OR است.

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



[1] Model Validation

[2] Optimal Solution

 

پست مرتبط بعدی: اثرات تحقیق در عملیات

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


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

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

این عکس در سال 1969 در دانشکده OR دانشگاه استنفورد گرفته شده است و دانشمندان مشهور OR را در کنار هم نشان می دهد. از چپ به راست: دانتزیگ، آلن مان، فردریک هایلر، دونالد ایگلهارت، آرتور وینوت، رادولف کالمن، جرالد لیبرمن، کنث آرو و ریچارد کتل

 

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

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

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

جرج دانتزیگ

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

پست مرتبط بعدی: ماهیت تحقیق در عملیات