دانلود پاورپوینت فرم های غیر استاندارد برنامه ریزی خطی روش دو مرحله ای

بنام خدا فرم های غیر استاندارد برنامه ریزی خطی روش دو مرحله ای (دو فازی) Max Z = 5x1 – 6x2 – 7x3 ‏s.T ‏x1 + 5x2 – 3x3 ≥ 15 5x1 – 6x2 + 10x3 ≤ 20 ‏x1 + x2 + x3 = 5 میشود : حلx1 , x (فاز)2 , x همانگونه که از نام این روش پیداست ،مسئله در دو مرحله3 ≥ 0 مرحله (فاز) اول :پیدا کردن یک جواب موجه ابتدایی با استفاده از یک تابع هدف مصنوعی و محدودیت های مسئله اصلی گام : 1پس از تخصیص متغیرهای کمکی Siو Riبه محدودیت ها ،متغیرهای مصنوعی مورد نیاز برای حل مسئله را معین میکنیم. گام : 2یک تابع هدف مصنوعی بصورت Min Wایجاد کرده و آن را برابر مجموع متغیرهای مصنوعی بکار رفته در مسئله قرار میدهیم. گام : 3مسئلة برنامه ریزی خطی ای که تابع هدف آن Min W = ∑Riو محدودیت هایش همان محدودیت های مسئله اصلی است را تا رسیدن به یک جواب موجه ابتدایی حل مینماییم. Max (-W) +R1 +R3 = 0 ‏x1 + 5x2 - 3x3 – s1 + R1 = 15 5x1 - 6x2 +10x3 + s2 = 20 ‏x1 + x2 + x3 + R3 = 5 • ‏Max (-W) = -R1 - R3 ‏Min W = R1 + R3 ‏x1 + 5x2 - 3x3 ≥ 15 ‏S.t • 5x1 - 6x2 +10x3 ≤ 20 • ‏x1 + x2 + x3 = 5 • برای آماده سازی محدودیت ها جهت ورود به جدول ابتدایی ،به طریق زیر عمل میکنیم : • – 1به محدودیتهایی که دارای عالمت کوچکتر یا مساوی هستند ،یک siبا عالمت مثبت اضافه میکنیم .مثبت siبعنوان متغیر اساسی این محدودیتها وارد جدول میشود. • -2به محدودیتهایی که دارای عالمت بزرگتر یا مساوی هستند ،یک siبا عالمت منفی و یک Riبا عالمت مثبت اضافه میکنیم .مثبت Riبه عنوان متغیر اساسی این محدودیتها وارد جدول میشود. • – 3به محدودیتهایی که دارای مساوی هستند ،یک Riبا عالمت مثبت اضافه میکنیم. مثبت Riبعنوان متغیر اساسی این محدودیتها وارد جدول میشود.. B.V R. No W x1 x2 x3 s1 s2 R1 R3 R.H.S θ W 0 -1 0 0 0 0 0 1 1 0 R1 1 0 1 5 -3 -1 0 1 0 15 S2 2 0 5 -6 10 0 1 0 0 20 R3 3 0 1 1 1 0 0 0 1 5 B.V R. No W x1 x2 x3 s1 s2 R1 R3 R.H.S W 0 -1 -2 -6 2 1 0 0 0 -20 R1 1 0 1 5 -3 -1 0 1 0 15 3 S2 2 0 5 -6 10 0 1 0 0 20 - R3 3 0 1 1 1 0 0 0 1 5 5 B.V R. No W x1 x2 x3 s1 s2 R1 R3 R.H.S θ W 0 -1 -4/5 0 -8/5 -1/5 0 6/5 0 -2 x2 1 0 1/5 1 -3/5 -1/5 0 1/5 0 3 - S2 2 0 31/5 0 32/5 -6/5 1 6/5 0 38 5.9 R3 3 0 4/5 0 8/5 1/5 0 -1/5 1 2 1.2 θ θ ‏θ ‏R.H.S ‏R3 ‏R1 ‏s2 ‏s1 ‏x3 ‏x2 ‏x1 ‏W ‏R. No ‏B.V -2 0 6/5 0 -1/5 -8/5 0 -4/5 -1 0 ‏W 3 0 1/5 0 -1/5 -3/5 1 1/5 0 1 ‏x2 38 0 6/5 1 -6/5 32/5 0 31/5 0 2 ‏S2 2 1 -1/5 0 1/5 8/5 0 4/5 0 3 ‏R3 ‏R.H.S ‏R3 ‏R1 ‏s2 ‏s1 ‏x3 ‏x2 ‏x1 ‏W ‏R. No ‏B.V 0 1 1 0 0 0 0 0 -1 0 ‏W 15/4 3/8 1/8 0 -1/8 0 1 0.5 0 1 ‏x2 30 -4 2 1 -2 0 0 3 0 2 ‏S2 5/4 5/8 -1/8 0 1/8 1 0 0.5 0 3 ‏x3 ‏از آنجاییکYه دیگYر قYادر بYه انتخYاب متغYیر ورودی نیسYتیم ،مرحلYه (فYاز) اول بYه پایان رسیده است. ‏در پایYان مرحلYة اول اگYر مقYدار تYابع هYدف مصYنوعی ( )WبYه صYفر برسYد و هیچ متغYیر مصYنوعی در سYتون متغیرهYای اساسYی بYا مقYدار غیرصYفر بYاقی نمانYده باشYد ،بYدین معناسYت کYه مسYئله دارای جYواب بهینYه اسYت و بنYابراین مجوز ورود به مرحله (فاز) دوم صادر میشود. ‏پیش از ورود بYه مرحلYة دوم بایYد تمYامی سYتون هYای مربYوط بYه متغیرهYای  مرحله (فاز) دوم :پیدا کردن جواب بهینة مسئله با استفاده از تابع هدف مسئلة اصلی و محدودیت های بدست آمده از جدول نهایی مرحلة اول. گام : 1سطر صفر (سطر تابع هدف) جدول نهایی مرحلة اول را حذف کرده و به جایش تابع هدف اصلی مسئله (یعنی )Zو ضرایب مربوط به آن را قرار میدهیم. گام : 2سطرهای مربوط به محدودیت ها (یعنی از سطر 1تا سطر )mرا به همان ترتیب بدست آمده در پایان مرحلة اول نگه میداریم. یادآوری میشود که پیش از شروع مرحلة دوم باید ستونهای مربوط به متغیرهای مصنوعی را از جدول نهایی مرحلة اول حذف نماییم. جدول سیمپلکس حاصل را (که سطر صفر آن همان تابع هدف مسئلة اصلی و مابقی سطرهای آن همان سطرهای جدول نهایی مرحلة اول است) ،تا رسیدن به جواب بهینة نهایی حل مینماییم. B.V R. No Z x1 x2 x3 s1 s2 R.H.S θ Z 0 1 -5 6 7 0 0 0 x2 1 0 0.5 1 0 -1/8 0 15/4 S2 2 0 3 0 0 -2 1 30 x3 3 0 0.5 0 1 1/8 0 5/4 B.V R. No Z x1 x2 x3 s1 s2 R.H.S Z 0 1 -23/2 0 0 -1/8 0 -125/4 x2 1 0 0.5 1 0 -1/8 0 15/4 7.5 S2 2 0 3 0 0 -2 1 30 10 x3 3 0 0.5 0 1 1/8 0 5/4 2.5 B.V R. No Z x1 x2 x3 s1 s2 R.H.S θ Z 0 1 0 0 23 11/4 0 -5/2 x2 1 0 0 1 -1 -1/4 0 5/2 S2 2 0 0 0 -6 11/4 1 45/2 x1 3 0 1 0 2 1/4 0 5/2 θ B.V R. No Z x1 x2 x3 s1 s2 R.H.S Z 0 1 0 0 23 11/4 0 -5/2 x2 1 0 0 1 -1 -1/4 0 5/2 S2 2 0 0 0 -6 11/4 1 45/2 x1 3 0 1 0 2 1/4 0 5/2 x*1 = 2.5 , x*2 = 2.5 , x*3 = 0 , s*1 = 0 , s*2 = 22.5 , R*1 = 0 , R*3 = 0 Z* = -2.5 θ