Online User آیا تعداد جواب های گوشه ای همه مسائل برنامه ریزی خطی متناهی است؟ - مدیریت صنعتی Industrial Management

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

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

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

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

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

(450 کلمه)

 

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

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


با توجه به شکل های 1 و 2 می توان دید که تعداد نقاط گوشه ای موجه این مسائل به ترتیب 5 و 10 می باشد. برای درک این مطلب که چرا تعداد نقاط گوشه ای موجه متناهی است، به خاطر آورید که هر نقطه گوشه ای در حقیقت حل دستگاه معادلاتی شامل n معادله از تعداد کل n+m معادله مرز محدودیت است که n تعداد متغیرها و m تعداد محدودیت های مسئله است. تعداد ترکیبات nتایی مختلفی که می توان از n+m معادله استخراج نمود عبارت است از:

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

شکل 1

در شکل 1 تعداد محدودیت ها و تعداد متغیرها به ترتیب برابر است با m=3 و n=2، بنابراین تعداد 10 دستگاه معادلات که شامل دو معادله مرز محدودیت باشند وجود خواهد داشت اما تنها نیمی از این نقاط گوشه ای، موجه هستند.

شکل 2

در شکل 2 نیز m=4 و n=3 است که با اینکه 34 دستگاه معادلات سه معادله ای را نشان می دهند، اما مسئله تنها 10 نقطه گوشه ای موجه دارد.

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

متاسفانه با اینکه تعداد نقاط گوشه ای موجه متناهی می باشد اما می تواند بسیار بزرگ باشد. برای نمونه یک مسئله برنامه ریزی خطی نسبتا کوچک را با تنها m=50 و n=50 در نظر بگیرید. بر اساس رابطه بالا این مسئله حدود 1029 دستگاه معادلات برای حل دارد. در مقابل این روش، روش سیمپلکس برای یافتن جواب بهینه تقریباً حدود 100 نقطه گوشه ای موجه را برای مسئله ای در این اندازه بررسی می کند. این مقدار صرفه جویی فاحش، در اثر آزمون بهینگی حاصل می شود که قبلاً به آن پرداختیم و بر این اصل استوار است که «اگر یک جواب گوشه ای موجه، از همه جواب های گوشه ای موجه مجاور خود بهتر باشد (از نظر بهبود تابع هدف) آنگاه هیچ جواب گوشه ای موجه دیگری وجود ندارد که از آن بهتر باشد»، که در مطلب مرتبط بعدی به آن خواهیم پرداخت.

 

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

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