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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

/ 5 نظر / 275 بازدید
دانیال

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

محمد

با سلام من برا اولين بار به وبلاگ شما سر زدم خيلي كمك حال دانشجو ها هستيد كمال تشكر را از راهنماي هاي شما را دارم خواستم محبتي كنيد و من را در درس پژوهشعملياتي راهنمايي كنيد من دانشجو رشته اتش نشاني هستم و در اين درس مشكل دارم ......نميدانم روش سيمپلكس چگونه مي باشد اگر امكان دارد به روشي ساده توضيح بدهيد .

سمیه یادافرین

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

آرمان عسگریان

سلام.ممنونم از کمکتان.انشاالله موفق باشید.اثبات قسمت b چطوری هست؟

صفری

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