اثبات نتیجه ای از قضیه ضعیف دوگان

Question

ثابت کنید اگر مساله اولیه نا متناهی باشد,مساله دوگان نشدنی است.

Answer 1

در حقیقت مسئله به صورت اگر و فقط اگر نیست و به صورت زیر است:

اگر مسئله اولیه (دوگان) نامحدود باشد آنگاه مسئله دوگان (اولیه) نشدنی است.

برعکس آن صحیح نیست.

مسئله اولیه:

$max \ \ cx \qquad \qquad \qquad \qquad$

$s.t \qquad \qquad \qquad \qquad$

$Ax \leqslant b \ \ \qquad \qquad \qquad$

$x \geqslant 0 \ \ \ \ \qquad \qquad \qquad$

مسئله دوگان:

$min \ \ yb \qquad \qquad \qquad \qquad$

$s.t \qquad \qquad \qquad \qquad$

$yA \geqslant c \ \ \qquad \qquad \qquad$

$y \geqslant 0 \ \ \ \ \qquad \qquad \qquad$

اثبات

فرض خلف: فرض کنیم مسئله اولیه با نقطه $x=x_0$ نامحدود باشد و مسائله دوگان متناظر شدنی باشد و $y=y_0$ یک جواب شدنی برای مسئله دوگان باشد آن گاه طبق قضیه ضعیف دوگانگی داریم که $cx_0 \leqslant y_0b$ ، پس یک کران برای مسئله اولیه پیدا کردیم و این در تناقض با نامتناهی بودن مسئله اولیه است پس فرض خلف باطل و مسئله دوگان نشدنی است

Comments

@مانی حق با آقای محمدی هستش,این قضیه به صورت اگروفقط اگر نیست.

---

wahedmohammadi@
شایدم منظور مانی این بوده که: اگر مساله اولیه نامتناهی باشد آنگاه مساله دوگان نشدنی است.همچنین اگر مساله دوگان نامتناهی باشد آنگاه مساله اولیه نشدنی است.

---

آره احتمالا منظورشون همین بوده.
با تشکر از توجهتون

---

ممنون.اصلاحش کردم

Answer 2

پاسخ آقای محمدی کاملا درسته ولی شاید این ملموس تر باشه.

فرض کنیم مساله اولیه در شکل متعارفی خود باشد یعنی:$$min \ cx$$ $$s.t.\ Ax \geq b$$$$x \geq 0$$

فرض مساله اولیه نامتناهی است.به برهان خلف فرض کنیم مساله دوگان شدنی باشد.طبق قضیه ضعیف دوگان می دانیم که $cx^0 \geq w^0b$ که $x^0$ و $w^0$ به ترتیب نقاط شدنی مسایل اولیه و دوگان هستند.حال چون مساله اولیه نامتناهی است لذا $- \infty > w^0b$ (توجه کنید چون مساله اولیه به شکل مینیمایز است $ - \infty $ نوشتیم) که این یک تناقض است چون عددی پیدا شده که از $- \infty $ کمتر است.پس دوگان نشدنی است.

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

فرض خلف) مساله اولیه شدنی است.

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

$+ \infty < cx^0$ که این یک تناقض است.درواقع عددی پیدا شده که از $+ \infty $ بیشتر است.

لذا اثبات کامل می شود.