2 – طريقة المرحلتين Two – Stages Method
أن أسلوب المرحلتين هو أسلوب بديل عن أسلوب (M) حيث يستخدم هذا الأسلوب عندما يكون هناك على الأقل قيد واحد على شكل مساواة أو متباينات على شكل أكبر أو يساوي, اذ تضاف المتغيرات الأصطناعية والتي ير مز لها (R_i) على القيود من النوع أعلاه وذلك للحصول على المصفوفة الأحادية والتي هي شرط الحل الأساسي الأولي المقبول. وهي أبسط من الطريقة السابقة من خلال الحصول على قيمة دالة الهدف الجديدة (f) مساوية للصفر ويتم الحل باستخدام مرحلتين هما:
المرحلة الأولى:
1 – تحويل النموذج من الصيغة القانونية الى الصيغة القياسية مع أضافة المتغيرات الأصطناعية فقط الى النموذج.
2 – صياغة دالة هدف جديدة (f) بالأعتماد على المتغيرات الأصطناعية (R_i).
f=R_1+R_2+?+R_n
3 – تكوين جدول يتضمن الحل الأولي بالأعتماد على المتغيرات (R_i,S_i ?,x?_j) في قيود النموذج ودالة الهدف ونتبع خطوات الحل السابقة الى أن نحصل على (f=0,c_j?0).
المرحلة الثانية:
1 – أعتماد الحل الأساسي النهائي في الخطوة (3) من المرحلة الأولى بعد أستبعاد (R_i) ودالة الهدف (f).
2 – أعتماد دالة الهدف الأصلية (x_0) وتحسين قيمتها للحصول على الحل الأمثل.
3 – يكون الحل الأمثل عندما (c_j?0).
مثال (2 - 10):
جد الحل الأمثل لنموذج البرمجة الخطية التالي باستخدام طريقة المرحلتين .
Min x_0=6x_1+4x_2
s.to
?2x?_1+3x_2?8
x_1+x_2?4
x_1,x_2?0
الحل:
نحول القيود الى (=) بطرح (slack variable).
Min x_0=?20x?_1+15x_2-0S_1-0S_2
s.to
?2x?_1+3x_2-S_1=10
?4x?_1 -S_2=10
x_1,x_2,? S?_1,S_2?0
يضاف لكل قيد طرح منه (? S?_i) متغير اصطناعي (? R?_i) وكالآتي:
?2x?_1+3x_2-S_1+? R?_1=10
4x_1 -S_2+? R?_2=10
x_1,x_2,? S?_1,S_2,? R?_1,? R?_2 ?0
? R?_1=10-2x_1-3x_2+S_1
? R?_2=10-4x_1+S_2
f=? R?_1+? R?_2=10-2x_1-3x_2+S_1+10-4x_1+S_2
f=20-6x_1-3x_2+S_1+S_2
f+6x_1+3x_2-S_1-S_2=20
جدول الحل الأساسي سيكون:
x_1 x_2 S_1 S_2 ? R?_1 ? R?_2 R.H.S Ratio
? R?_1 2 3 -1 0 1 0 10 5
? R?_2 4 0 0 -1 0 1 10 2.5
f 6 3 -1 -1 0 0 20
المتغير الداخل الذي يقابل أكبر قيمة موجبة في دالة الهدف (f) هو (x_1) والخارج الذي يمثل أقل قيمة موجبة في عمود النسبة هو(? R?_2) والقيمة المحورية هي (4).
Pivot Equation= [1,0,0,-0.25,0,0.25,2.5]
New (R_1 )=[?(2@3@?(-1@0@?(1@0@10)))]-{2[?(1@0@?(0@-0.25@?(0@0.25@2.5)))]}=[?(0@3@?(-1@0.5@?(1@-0.5@5)))]
New (f)=[?(6@3@?(-1@-1@?(0@0@20)))]-{-6[?(1@0@?(0@-0.25@?(0@0.25@2.5)))]}=[?(0@3@?(-1@0.5@?(0@-1.5@5)))]
جدول الحل الثاني سيكون:
x_1 x_2 S_1 S_2 ? R?_1 ? R?_2 R.H.S Ratio
? R?_1 0 3 -1 0.5 1 -0.5 5 1.67
? x?_1 1 0 0 -0.25 0 0.25 2.5 ?
f 0 3 -1 0.5 0 -1.5 5
المتغير الداخل (x_2), والمتغير الخارج (? R?_1), القيمة المحورية (3).
Pivot Equation= [0,1,-0.33,0.17,0.33,-0.17,1.67]
New (x_1 )=[?(1@0@?(0@-0.25@?(0@0.25@2.5)))]-{0[?(0@1@?(-0.33@0.17@?(0.33@-0.17@1.67)))]}=[?(1@0@?(0@-0.25@?(0@0.25@2.5)))]
New (f)=[?(0@3@?(-1@0.5@?(0@-1.5@5)))]-{3[?(0@1@?(-0.33@0.17@?(0.33@-0.17@1.67)))]}=[?(0@0@?(0@0@?(-0.5@-1@0)))]
جدول الحل الثالث سيكون:
x_1 x_2 S_1 S_2 ? R?_1 ? R?_2 R.H.S
? x?_2 0 1 -0.33 0.17 0.33 -0.17 1.67
? x?_1 1 0 0 -0.25 0 0.25 2.5
f 0 0 0 0 0.5 -1 0
بما أن قيمة (f) مساوية للصفر فيتم أعتماد نتائج الجدول الثالث بعد استبعاد المتغيرات الأصطناعية (? R?_2 ?,R?_1) ودالة الهدف (f) من الجدول أعلاه مع أعتماد دالة الهدف الأصلية والتي هي:
Min x_0=?20x?_1+15x_2+0S_1+0S_2
نقوم بتحسين قيمة دالة الهدف للحصول على الحل الأمثل النهائي وكما يأتي:
x_1 x_2 S_1 S_2 R.H.S
x_1 0 1 -0.33 0.17 1.67
x_2 1 0 0 -0.25 2.5
x_0 20 15 0 0 0
x_2-0.33? S?_1+0.17? S?_2=1.67 … (1)
x_1 -0.25? S?_2=1.67 …(2)
x_1=2.5+0.25? S?_2
x_2=1.67+0.33? S?_1-0.17? S?_2
نعوض النتيجتين في دالة الهدف الأصلية نحصل على:
x_0=20(2.5+0.25? S?_2)+15(1.67+0.33? S?_1-0.17? S?_2)
x_0=75.05+4.95? S?_1+2.45? S?_2
x_0-4.95? S?_1-2.45? S?_2=75.05
وبذلك سيكون جدول الحل النهائي هو:
x_1 x_2 S_1 S_2 R.H.S
x_1 0 1 -0.33 0.17 1.67
x_2 1 0 0 -0.25 2.5
x_0 0 0 -4.95 -2.45 75.05
من الجدول أعلاه نجد أن جميع معاملات دالة الهدف هي أقل أو تساوي صفر وبذلك يكون الحل الأمثل هو:
x_1=2.5, x_2=1.67, x_0=75.05
مثال (2 - 11):
جد الحل الأمثل لنموذج البرمجة الخطية التالي باستخدام طريقة المرحلتين.
Min x_0=?3x?_1+8x_2
s.to
x_1+x_2=200
x_1 ?80
x_2 ?60
x_1,x_2?0
الحل:
نكتب المسألة بالصيغة القياسية:
Min x_0=?3x?_1+8x_2+0S_1+0S_2
s.to
x_1+x_2=200
x_1+S_2=80
x_2-S_3=60
x_1,x_2,S_2,S_3?0
المرحلة الأولى
Min x_0=R_1+R_3
s.to
x_1+x_2+R_1=200
x_1+S_2=80
x_2-S_3+R_3=60
x_1,x_2,S_2,S_3,R_1,R_3?0
B.V.C B.V x_1 x_2 S_3 R_1 S_2 R_3 Sol.
1 R_1 1 1 0 1 0 0 200
0 S_2 1 0 0 0 1 0 80
1 R_3 0 1 -1 0 0 1 60
x_0 1 2 -1 0 0 0 260
1 R_1 1 0 1 1 0 -1 140
0 S_2 1 0 0 0 1 0 80
0 x_2 0 1 -1 0 0 1 60
x_0 1 0 1 0 0 -2 140
1 R_1 0 0 1 1 -1 -1 60
0 x_1 1 0 0 0 1 0 80
0 x_2 0 1 -1 0 0 1 60
x_0 0 0 1 0 -1 -2 60
0 S_3 0 0 1 1 -1 -1 60
0 x_1 1 0 0 0 1 0 80
0 x_2 0 1 0 1 -1 0 120
x_0 0 0 0 -1 0 -1 0
بما أن (x_0=0) فأن الحل مقبول.
المرحلة الثانية
B.V.C B.V x_1 x_2 S_3 S_2 Sol.
0 S_3 0 0 1 -1 60
3 x_1 1 0 0 1 80
8 x_2 0 1 0 -1 120
x_0 0 0 0 -5 1200
بما أن (x_0?0) فأن الحل أمثل.
x_1=80,x_2=120,x_0=1200
المادة المعروضة اعلاه هي مدخل الى المحاضرة المرفوعة بواسطة استاذ(ة) المادة . وقد تبدو لك غير متكاملة . حيث يضع استاذ المادة في بعض الاحيان فقط الجزء الاول من المحاضرة من اجل الاطلاع على ما ستقوم بتحميله لاحقا . في نظام التعليم الالكتروني نوفر هذه الخدمة لكي نبقيك على اطلاع حول محتوى الملف الذي ستقوم بتحميله .
الرجوع الى لوحة التحكم
|