برنامه ریزی خطیدرس های رایگان

نظریه همزادی

تهیه شده توسط گروه آموزشی بهینه یاب

برای دانلود بسته طلایی آموزش تئوری همزادی شامل : جزوه کامل آموزش این درس، فایل ویدیوی آموزش این درس، فایل صوتی آموزش این درس، فایل ارایه حین درس مدرس بر روی دکمه زیر کلیک کنید.

دانلود بسته طلایی آموزش تئوری همزادی

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

دانلود جزوه آموزش تئوری همزادی

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

دانلود ویدیو آموزش تئوری همزادی

درس 3: نظریه همزادی

تهیه شده توسط گروه بهینه یاب

 

از جمله مهمترین نتایجی که در دوره‌های نخستین توسعه برنامه‌ریزی خطی بدست آمد، شناخت نظریه دوگانگی یا نظریه همزادی و شاخه‌های مربوط به آن بوده است. در مطالعه‌های اولیه نشان داده شد که هر مسئله برنامه‌ریزی خطی با یک مسئله برنامه‌ریزی خطی دیگر که مسئله همزاد (Dual problem) نامیده می‌شود، ارتباط دارد. برای روشن شدن موضوع نظریه همزادی، مسئله اولیه به شکل استاندارد به صورت زیر را در نظر بگیرید.

نظریه همزادی

اگر yi را متغیر همزاد هر محدودیت در نظر بگیریم، مسئله همزاد (که از نظریه همزادی گرفته می شود) مدل فوق به صورت زیر بیان می‌شود.

نظریه همزادی و تئوری همزادی و تئوری دوگانگی
مثال: مدل اولیه زیر را در نظر بگیرید:

نظریه همزادی و تئوری همزادی و تئوری دوگانگی
مدل همزاد مدل فوق را بنویسید.

حل:

نظریه همزادی و تئوری همزادی و تئوری دوگانگی

جواب بهینه دو مدل فوق به صورت زیر است:

نظریه همزادی و تئوری همزادی و تئوری دوگانگی

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

نظریه همزادی و تئوری همزادی و تئوری دوگانگی

….

از جدول فوق مشاهده می‌شود که تنها در یک مورد جواب‌های مسئله اولیه و همزاد موجه هستند و در مابقی حالات یکی از دو مسئله غیر موجه هستند. در جوابی که هر دو مسئله موجه هستند، به جواب بهینه رسیده‌ایم.

مشاهده: اگر یک جواب اساسی در مسائل اولیه و همزاد امکان پذیر باشد، آن جواب اساسی، جواب اساسی بهینه است.

تمرین: یک مدل با دو متغیر و دو محدودیت عملکردی بسازید که مدل اولیه جواب نامحدود داشته باشد. از طریق ترسیمی نشان دهید که مسئله همزاد امکان ناپذیر است.

حل:

نظریه همزادی و تئوری همزادی و تئوری دوگانگی

اگر x1 = x2 = c و c به سمت بینهایت میل کند، آنگاه z = 2c و لذا تابع هدف به سمت بینهایت می رود. همزاد مدل فوق به صورت زیر است.

.نظریه همزادی و تئوری همزادی و تئوری دوگانگی

حل ترسیمی مدل‌های اولیه و همزاد به صورت زیر است.

.نظریه همزادی و تئوری همزادی و تئوری دوگانگی

نظریه همزادی و تئوری همزادی و تئوری دوگانگی

واضح است که محدوده امکان پذیر مدل همزاد، تهی است.

سیمپلکس همزاد

روش سیمپلکس همزاد برمبنای نظریه همزادی را می‌توان عکس روش سیمپلکس اولیه دانست. روش سیمپلکس اولیه مستقیما با جواب‌های امکان پذیر سروکار دارد و سعی می‌کند تا با ایجاد شرایط بهینگی به طرف جواب بهینه نزدیک شود. در مقابل، روش سیمپلکس همزاد با جواب‌هایی کار می‌کند که شرط بهینگی دارند و با کوشش در جهت موجه کردن آن‌ها، به جواب‌های موجه بهینه نزدیک شود و این روش بر مبنای نظریه همزادی است.

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

برنامه‌ریزی خطی زیر را در نظر بگیرید.

نظریه همزادی و تئوری همزادی و تئوری دوگانگی

مدل فوق را با اضافه کردن متغیرهای کمبود Si به فرم استاندارد به صورت زیر در می‌آوریم.

 

نظریه همزادی و تئوری همزادی و تئوری دوگانگی

 

با توجه به مدل فوق، بیان رسمی این روش به صورت زیر می‌شود:

گام 0: در مسئله فوق، cj ≥ 0 برای تمامی j ها برقرار باشد. اگر برقرار نبود با تغییر متغیر این شرط برقرار شود.

گام 1: اگر به ازای i=1,…,n رابطه bi ≥ 0 برقرار باشد، توقف کنید زیرا به جواب بهینه حاصل شده است. در صورتی که 0 > bi باشد، به گام 2 می رویم.

گام 2: سطر لولا ( یعنی متغیر که از پایه حذف می‌شود ) را با استفاده از رابطه زیر انتخاب کنید.

نظریه همزادی و تئوری همزادی و تئوری دوگانگی

اگر تمامی ضرایب متغیرها در سطر r-ام نا منفی باشد( arj ≥ 0, j=1,…,n∀ )، توقف کنید زیرا مسئله امکان ناپذیر است. اگر به ازای مقادیر j=1,…,n داشته باشیم 0 > arj برقرار باشد، به گام 3 بروید.

گام 3: ستون s را طبق رابطه زیر تعیین کنید.

نظریه همزادی و تئوری همزادی و تئوری دوگانگی

در این گام متغیر ورودی به پایه تعیین می‌شود.

گام 4: متغیر S را جایگزین متغیر پایه موجود در سطر r کنید و دوباره فرم استاندارد مدل را با عمل چرخش لولا استاندارد کنید.

گام 5: به گام 1 بروید.

برای روشن شدن الگوریتم فوق، مثال زیر را حل می‌کنیم.

مثال: مدل زیر را به روش سیمپلکس همزاد حل نمایید.

….
نظریه همزادی و تئوری همزادی و تئوری دوگانگی

برای آغاز حل، می‌بایستی محدودیت ها به صورت و سپس با اضافه کردن متغیرهای کمبود، فرم محدودیت ها به صورت تساوی درآید. در این صورت مدل به صورت زیر می‌شود.

نظریه همزادی و تئوری همزادی و تئوری دوگانگی

 

 

جواب اساسی مدل فوق به صورت (5-,3-,0,0,0) و Z = 0 است. چون متغیرهای x4 و x5 نا مثبت هستند، لذا این جواب اساسی غیر موجه است. اجرای روش سیمپلکس همزاد به صورت زیر می‌شود.

نظریه همزادی

تکرار 0: متغیر را به دلیل این که 5>3 به عنوان متغیر ورودی به پایه انتخاب می‌کنیم. برای انتخاب متغیر خروجی از جواب پایه، از آزمون نسبت استفاده می‌کنیم چون ( 18/2 > 12/2 ) لذا متغیر x2 به عنوان متغیر خروجی از جواب پایه انتخاب می‌شود. برای خروج x2 از پایه و ورود x5 به پایه، سطر معادله 2 را بر 2- تقسیم می‌کنیم.

تکرار 1: شرط توقف را کنترل می‌کنیم. چون 3- بزرگتر از صفر نیست، لذا شرط امکان پذیری جواب برقرار نیست. x4 به عنوان متغیر خروجی از پایه و با توجه به آزمون نسبت چون ( 6/3 < 4/1 ) است لذا متغیر x3 وارد پایه می‌شود. برای انجام این تغییرات در جداول سیمپلکس، سطر معادله 1 را بر 3- تقسیم می‌کنیم.

تکرار 2: چون سمت راست معادله نامنفی است لذا شرط امکان پذیری برقرار است و لذا به جواب بهینه رسیدیم و الگوریتم متوقف می‌شود.

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

نظریه همزادی

 

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

نظریه همزادی

حل مدل فوق به روش سیمپلکس همزاد به صورت زیر می شود.

نظریه همزادی

توجه: برای مطالعه ادامه این درس و دانلود سایر محصولات مربوط به این درس می توانید به موارد زیر مراجعه کنید.

برای دانلود بسته طلایی آموزش تئوری همزادی شامل : جزوه کامل آموزش این درس، فایل ویدیوی آموزش این درس، فایل صوتی آموزش این درس، فایل ارایه حین درس مدرس بر روی دکمه زیر کلیک کنید.

دانلود بسته طلایی آموزش تئوری همزادی

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

دانلود جزوه آموزش تئوری همزادی

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

دانلود ویدیو آموزش تئوری همزادی

دیدگاهتان را بنویسید

دکمه بازگشت به بالا