به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
سایت پرسش و پاسخ ریاضی
+2 امتیاز
2,155 بازدید
در دانشگاه توسط مانی (25 امتیاز)
ویرایش شده توسط مانی

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

مرجع: کتاب تحقیق در عملیات زاهدی سرشت

2 پاسخ

+5 امتیاز
توسط wahedmohammadi (1,612 امتیاز)
ویرایش شده توسط wahedmohammadi

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

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

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

مسئله اولیه:

$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$ ، پس یک کران برای مسئله اولیه پیدا کردیم و این در تناقض با نامتناهی بودن مسئله اولیه است پس فرض خلف باطل و مسئله دوگان نشدنی است

توسط رها (1,165 امتیاز)
+2
@مانی حق با آقای محمدی هستش,این قضیه به صورت اگروفقط اگر نیست.
توسط رها (1,165 امتیاز)
+2
wahedmohammadi@
شایدم منظور مانی این بوده که: اگر مساله اولیه نامتناهی باشد آنگاه مساله دوگان نشدنی است.همچنین اگر مساله دوگان نامتناهی باشد آنگاه مساله اولیه نشدنی است.
توسط wahedmohammadi (1,612 امتیاز)
+2
آره احتمالا منظورشون همین بوده.
با تشکر از توجهتون
توسط مانی (25 امتیاز)
+1
ممنون.اصلاحش کردم
سوال شده بهمن ۱, ۱۳۹۳ در دانشگاه توسط reza91 (97 امتیاز)
ویرایش شده بهمن ۱, ۱۳۹۳ توسط wahedmohammadi
نتیجه ای از قضیه دوگان
+4 امتیاز
توسط رها (1,165 امتیاز)
ویرایش شده توسط رها

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

فرض کنیم مساله اولیه در شکل متعارفی خود باشد یعنی:$$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 $ بیشتر است.

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


حمایت مالی

کانال تلگرام محفل ریاضی
امروز : تاریخ شمسی اینجا نمایش داده می‌شود
...