بخشی از پاورپوینت
اسلاید 1 :
بنام خدا
برنامه ریزی خطی پیشرفته (21715)
Advanced Linear Programming
اسلاید 2 :
برنامه ریزی خطی پیشرفته (21715)
ارتباط هر مساله برنامه ریزی خطی یک مساله برنامه ریزی خطی دیگر
حل هر دو مساله با حل یکی از این مساله ها
بدست آوردن اطلاعات کامل از وضعیت جواب بهینه یکی از روی جواب بهینه مساله دیگر
کشف وجود مساله دوگان توسط John von Neumann دانشمند فعال در زمینه تئوری بازی ها، اقتصاد و ریاضیات (ظاهرا قبل از طرح مساله برنامه ریزی خطی)
اسلاید 3 :
برنامه ریزی خطی پیشرفته (21715)
این اطلاعات می تواند اطلاعات بسیار مناسبی را برای تعبیرهای اقتصادی مساله ها فراهم کند.
مساله اصلی را مساله اولیه و مساله مرتبط با آن را مساله دوگان آن می گوییم.
این امر کمک می کند که در حل مساله های برنامه ریزی خطی همواره مساله ساده تر را حل کنیم.
اسلاید 4 :
مثال:
خانواده ای را در نظر بگیرید که می خواهد ویتامین مورد نیاز خود را از میان شش ماده با هدف کمینه کردن هزینه ها تامین کند.
اطلاعات مورد نیاز در مورد ویتامین های موجود در مواد، قیمت مواد و محدوده ویتامین های مورد نیاز بصورت جدول زیراست:
اسلاید 5 :
مدل برنامه ریزی خطی مساله به منظور کاهش هزینه ها بصورت زیر است:
فرض کنید سازمانی به خانواده پیشنهاد دهد که به جای مصرف غذا از قرص های ویتامین A و C استفاده کند.
برای این منظور قرص های ارایه شده توسط سازمان علاوه بر کاهش هزینه برای خانواده باید ویتامین های مورد نیاز را تامین کنند.
اسلاید 6 :
با توجه به این مساله سازمان با محدودیت هایی در زمینه ارایه قیمت قرص ها رو به رو خواهد بود.
فرض کنید قیمت هایی که سازمان برای قرص های ویتامین A وC می خواهد ارایه کند با π1و π2 نمایش داده شوند.
ماده شماره پنج را در نظر بگیرید. یک کیلو گرم از این ماده قیمتی معادل 27 سنت دارد و دارای یک واحد ویتامین C و یک واحد ویتامین A است. برای اینکه برای مشتریان خرید این قرص ها به صرفه باشد و همچنین موارد مورد نیاز خانواده را تامین کند بایستی رابطه زیر میان قیمت ها برقرار باشد:
π1 + 3π2 ≤ 27
اسلاید 7 :
با توجه به این مطالب اگر سازمان بخواهد قرص ها را به فروش برساند باید محدودیت های زیر را در مورد قیمت قرص ها مدنظر بگیرد:
π1 + 0π2 ≤ 35
0π1 + π2 ≤ 30
2π1 + 3π2 ≤ 60
2π1 + π2 ≤ 50
π1 + 3π2 ≤ 27
2π1 + 2π2 ≤ 22
واضح است که به دلیل سود آوری سازمان مقادیر π1 و π2باید مثبت باشند.
اسلاید 8 :
از آنجا که هدف خانواده کاهش هزینه ها است، مقادیر ویتامین خریداری شده تنها برابر مقادیری است که حداقل ویتامین مورد نیاز خانواده را تامین کند.
لذا سود سازمان در اثر فروش ویتامین به این خانواده از رابطه زیر حاصل می شود:
V(π) = 9π1 + 19π2
واضح است که هدف سازمان بیشینه کردن مقدار سود خود است.
مشخص است که مساله بیان شده معادل مساله اصلی است.
اسلاید 9 :
مشخص است که تنها در صورتی خانواده به خرید ویتامین ها اقدام می کنند که:
The maximum value of V(π) ≤ The minimum value of z(x)
این مطلب نتیجه قضیه ضعیف دوگانگی است که بعدا مورد بحث قرار می گیرد.
اسلاید 10 :
دو مساله بیان شده دوگان یکدیگر نام دارند.
هر متغیر مساله اولیه با یک محدودیت مساله دوگان ارتباط دارد و برعکس.
اگر فردی تصمیم بگیرد که قرص های ویتامین A را خریداری کند، مسلم است که بیش از نیاز خود خریداری نمی کند (9 واحد).
در این حالت قطعا محدودیت اول مساله که تفاضل ویتامین A تامین شده و مقدار نیاز واقعی است قطعا بصورت تساوی ارضا می شود.
اسلاید 11 :
اگر دوگان یک مساله دارای جواب بهینه یکتا باشد، متغیرهای دوگان مساله قیمت های سایه نام دارند.
در این حالت به این متغیرها ضریب های سیمپلکس و یا ضریب های لاگرانژ نیز می گویند.
اگر جواب بهینه مساله اصلی تبهگن باشد چنین امری صحیح نیست.
دوگان دوگان یک مساله با خود مساله برابر است.
اسلاید 12 :
قیمت های سایه و مساله های تبهگن
اگر جواب بهینه مساله ای تبهگن باشد، محاسبه قیمت های سایه و مقدارهای متغیرهای تصمیم دوگان ساده نیست.
مساله برنامه ریزی خطی زیر و مساله دوگان آن را در نظر بگیرید:
اسلاید 13 :
قیمت های سایه و مساله های تبهگن (ادامه)
جدول بهینه این دو مساله به شرح زیر است:
اسلاید 14 :
قیمت های سایه و مساله های تبهگن (ادامه)
مساله دوگان دارای جواب بهینه چندگانه است. جواب دیگر بهینه عبارت است از:
لذا محاسبه مقدار متغیرهای دوگان و قیمت های سایه در حالتی که جواب بهینه مساله تبهگن باشد پیچیده است.
اسلاید 15 :
تمرین:
دوگان مساله برنامه ریزی خطی زیر را بنویسید:
Min Z = X1 +X2 +X3
-X2 +X3 ≥ -1
X1 -X3 ≥ -1
-X1 +X2 ≥ -1
Xi ≥ 0
اسلاید 16 :
به چنین مساله هایی مساله های Self-dual می گویند.
سوال
ماتریس ضرایب در محدودیت ها، ضرایب تابع هدف و مقدارهای بردارهای سمت راست باید چه خصوصیت هایی داشته باشند تا مساله برنامه ریزی خطی self-dual باشد؟
اسلاید 17 :
قضیه
مساله های دوگان دو مساله برنامه ریزی خطی معادل معادل همدیگر هستند.
اسلاید 18 :
قضیه ضعیف دوگانگی
در یک مساله برنامه ریزی خطی و دوگان آن فرض کنید x یک جواب موجه اولیه و z(x) مقدار تابع هدف نقطه مربوطه باشد. فرض کنید تابع هدف مساله اولیه min باشد.
فرض کنید π جواب موجه مساله دوگان و v(π) مقدار تابع هدف نقطه مربوطه با تابع هدف maxباشد.
در این حالت همواره خواهیم داشت:
z(x) ≥ v(π)
تعبیر:
در هر مساله برنامه ریزی خطی و دوگان آن هر جواب موجه مساله اولیه ((min بزرگتر یا مساوی هر جواب موجه مساله (max) است.
اسلاید 19 :
نتایج جانبی قضیه ضعیف دوگانگی.
هر جواب موجه مساله اولیه (min) کران بالایی برای جواب بهینه همچنین جواب های موجه مساله ثانویه (max)است.
هر جواب موجه مساله دوگان (max) کران پایینی برای جواب بهینه هر دو مساله و همچنین جواب های موجه مساله اولیه (min) است.
اگر مساله اولیه دارای جواب موجه بوده و مقدار بهینه تابع هدف آن بی نهایت باشد، مساله دوگان نمی تواند دارای جواب موجه باشد.
اسلاید 20 :
نتایج جانبی قضیه ضعیف دوگانگی (ادامه).
اگر مساله دوگان (max) دارای جواب موجه باشد و جواب بهینه مساله نامحدود باشد مساله اولیه (min) بدون منطقه موجه است.
اگر مساله دوگان فاقد منطقه موجه باشد و مساله اولیه دارای منطقه موجه باشد، جواب بهینه مساله اولیه قطعا نامحدود خواهد بود.
مساله های اولیه و دوگان بطور همزمان می توانند بدون منطقه موجه باشند.
