Online User ویژگی بهینگی یک جواب گوشه ای موجه - مدیریت صنعتی Industrial Management

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

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

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

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

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

(800 کلمه)

 

مطلب مرتبط بعدی:روش سیمپلکس تجدید نظر شده یا Revised Simplex Method (مقدمه)

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


برای آشنایی بیشتر با این ویژگی، شکل 1 را در نظر بگیرید. در این شکل، جواب گوشه ای موجه (2،6)، دارای دو جواب گوشه ای موجه مجاور به مختصات (0،6) و (4،3) است که هیچ کدام از این دو نقطه دارای مقدار تابع هدف بهتری نسبت به (2،6) نیستند. بر اساس ویژگی بهینگی می توان نتیجه گرفت که هیچ جواب گوشه ای موجه دیگری نیز (در اینجا (0،0) و (4،0)) نمی توانند دارای مقدار هدف بالاتری باشند و در نتیجه (2،6) نقطه بهینه مسئله است.

شکل 1

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

شکل2

مسئله شکل نشان داده شده تقریباً شبیه به مسئله قبل است با این تفاوت که فضای موجه در این مسئله جدید به سمت راست نقطه (5، 3/8) توسعه یافته و کشیده شده است. در نتیجه جواب های گوشه ای موجه مجاور کنونی نقطه (2،6) عبارتند از (0،6) و (5، 3/8) که مقدار هدف مربوط به هیچ کدام بهتر از مقدار هدف در نقطه (2،6) نیست. با این حال جواب گوشه ای موجه دیگری، (4،5) وجود دارد که مقدار تابع هدف متناظر با آن بهتر از مقدار هدف متناظر با نقطه (2،6) است و این یعنی نقض ویژگی بهینگی. دلیل آن هم این است که مرز منطقه موجه به گونه ای است که پس از عبور از نقطه (2،6) و رسیدن به نقطه (5، 3/8) ، با چرخش به سمت راست به سمت نقطه (4،5) می رود که فراتر از خط تابع هدف گذرنده از نقطه (2،6) قرار دارد.

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

از دو محدودیت

 

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

محدودیت

حذف شده و جای خود را به

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

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

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

مطلب مرتبط بعدی:روش سیمپلکس تجدید نظر شده یا Revised Simplex Method (مقدمه)

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