Online User اثبات جبری قرار گیری جواب بهینه در حداقل یکی از نقاط گوشه ای - مدیریت صنعتی Industrial Management

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

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

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

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

...


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

(550 کلمه)

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

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


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

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

رای اثبات این ویژگی از برهان خلف استفاده می کنیم یعنی فرض می کنیم مسئله برنامه ریزی خطی خاصی وجود دارد که تنها دارای یک جواب بهینه است و آین جواب جزء جواب های CPF نیست.

در ادامه ثابت خواهیم کرد که این فرض نمی تواند صحیح باشد. جواب فرض شده را با و مقدار تابع هدف متناظر با این جواب را با نشان می دهیم.

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

که برای مقداری از که در رابطه صدق کند برقرار است. از آن جهت که تابع هدف مسئله، یک تابع خطی است لذا داریم:

با کمی عملیات جبری عبارت بالا را می توان به صورت زیر نوشت:

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

اگر مقداری مثبت باشد، از آنجا که ضریب عددی مثبت و کوچکتر از یک است خواهیم داشت:

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

اگر مقداری منفی باشد، از آنجا که ضریب عددی مثبت و کوچکتر از یک است خواهیم داشت:

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

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

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

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

 

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

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