پاورپوینت بررسی حالات خاص برنامه ریزی خطی در الگوریتم سیمپلکس (pptx) 15 اسلاید
دسته بندی : پاورپوینت
نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )
تعداد اسلاید: 15 اسلاید
قسمتی از متن PowerPoint (.pptx) :
بنام خدا
بررسی حالات خاص برنامه ریزی خطی در الگوریتم سیمپلکس
هر گاه در سطر تابع هدف (سطر صفر) جدول بهینه، یکی (یا چندتا) از متغیرهای غیر اساسی ضریبشان برابر صفر باشد، مسئله دارای جواب بهینة چندگانه خواهد بود.
در این حالت ضمن پذیرفتن جواب بدست آمده در جدول بهینة مورد نظر، میتوان با انتخاب آن متغیر غیراساسیِ دارای ضریب صفر به عنوان متغیر ورودی، به جوابهای بهینة دیگری نیز برسیم.
مثال
Max Z = 40x1 + 30x2
S.t x1 + 2x2 ≤ 40
4x1 + 3x2 ≤120
x1 , x2 ≥ 0
Z*= 1200
x*1=30
x*2=0
s*1=10
s*2=0
Z*= 1200
x*1=24
x*2=8
s*1=0
s*2=0
بررسی حالات خاص برنامه ریزی خطی در الگوریتم سیمپلکس
فقدان منطقه موجه (فقدان فضای شدنی)،
فقدان جواب موجه و بهینه
هرگاه در جدول نهایی سیمپلکس (یعنی جدولی که همة ضرایب سطر تابع هدف آن نامنفی هستند)، در ستون متغیرهای اساسی حداقل یک متغیر مصنوعی (Ri) با مقدار سمت راست بزرگتر از صفر وجود داشته باشد، مسئله فاقد منطقة موجه و بنابراین فاقد جواب موجه و جواب بهینه خواهد بود.
نکته : وجود متغیر مصنوعی مابین متغیرهای اساسی جدول نهایی بیانگر آن است که جریمة M در نظر گرفته شده کافی نبوده و نتوانسته افزایش مصنوعی منطقة موجه را جبران نماید.
نکته : اگر مسئله ای که فاقد منطقه موجه است را با روش دومرحله ای حل نماییم، در پایان مرحلة اول (یعنی وقتی در سطر صفر جدول نهایی مرحلة اول هیچ ضریب منفی وجود ندارد)، حداقل یک متغیر مصنوعی با مقدار بزرگتر از صفر در ستون متغیرهای اساسی حاضر خواهد بود؛ و این یعنی حق ورود به مرحلة دوم را نداریم.
مثال
Max Z = 5x1 + 3x2
S.t 4x1 + 2x2 ≤ 8
x1 ≥ 4
x2 ≥ 6
x1 , x2 ≥ 0
MaxZ = 5x1 + 3x2 – MR2 – MR3
4x1 + 2x2 + s1 = 8
X1 – s2 + R2 = 4
X2 – s3 + R3 = 6
> 0
> 0
بررسی حالات خاص برنامه ریزی خطی در الگوریتم سیمپلکس
منطقه موجه نامحدود
الف) منطقه موجه نامحدود – جواب بهینة محدود
ب) منطقه موجه نامحدود – جواب بهینة نامحدود
هرگاه در هرکدام از تکرارهای سیمپلکس، تمامی ستون اعداد مربوط به یک متغیر غیراساسی (به جز ضریبِ سطرِ صفر آن متغیر)، مقادیری نامثبت (یعنی یا صفر و یا منفی) باشند. منطقة موجه مسئلة مورد نظر نامحدود خواهد بود.
الف ) منطقه موجه نامحدود – جواب بهینة محدود
اگر متغیر غیراساسی که ستون اعدادش نامثبت است به عنوان متغیر ورودی انتخاب نشود، در آن صورت علیرغم نامحدود بودن منطقة موجه، مسئله دارای جواب بهینة محدود و معین خواهد بود.
ب) منطقه موجه نامحدود – جواب بهینة نامحدود
هرگاه در هرکدام از تکرارهای سیمپلکس، یک متغیر غیراساسی، که ستون اعدادش نامثبت هستند، بعنوان متغیر ورودی انتخاب شود، در اینصورت علیرغم وجود متغیر ورودی، قادر به انتخاب متغیر خروجی نیستم. در چنین حالتی میگوییم علاوه بر نامحدود بودن منطقة موجه، جواب بهینة مسئله نیز نامحدود است.