أما أيجاد الحل الأمثل لنموذج البرمجة الخطية بطريقة (Minimize ) فتوجد طريقتان هما:
1 – طريقة (M) الكبيرة Big (M) Method
تتلخص هذه الطريقة بإضافة متغيرات اصطناعية (Artificial Variables) إضافة إلى المتغيرات الوهمية (S_i) إلى قيود النموذج عندما تكون معاملات القيود مكتوبة بصيغة (=أو ?) إلى دالة الهدف (x_0) ويتم أتباع الخطوات التالية على أن تقترن المتغيرات الأصطناعية (R_i) في دالة الهدف (x_0) بمعاملات تدعى (M) تحمل أشارة موجبة في حالة (Minimize) وسالبة في حالة (Maximize):
1 – تحويل نموذج البرمجة الخطية من الصيغة القانونية إلى الصيغة القياسية بعد إضافة المتغيرات الوهمية (S_i) و المتغيرات الأصطناعية (R_i) إلى قيود دالة الهدف.
2 – صياغة دالة هدف جديدة (x_0) بدلالة المتغيرات (x_j) و (S_i) بعد التعويض عن قيم (R_i) بما يساويها من المتغيرات وجعل الدالة مساوية الى (M).
3 – تصميم جدول الحل الأساسي بتحديد المتغير الداخل على أساس أكبر قيمة موجبة في صف دالة الهدف (x_0).
4 – أعتماد الخطوات التي تم توضيحها في حالة (Maximize).
5 – يتم الحصول على الحل الأمثل عندما تكون جميع قيم (c_j) أقل أو تساوي صفر (c_j?0).
مثال (2 - 9):
جد الحل الأمثل لنموذج البرمجة الخطية التالي باستخدام طريقة (M) الكبيرة .
Min x_0=6x_1+4x_2
s.to
?2x?_1+3x_2?8
x_1+x_2?4
x_1,x_2?0
الحل:
Min x_0=6x_1+4x_2-0S_1-0S_2
s.to
?2x?_1+3x_2-S_1=8
x_1+x_2-S_2=4
x_1,x_2,? S?_1,S_2?0
Min x_0=6x_1+4x_2-0S_1-0S_2+M? R?_1+M? R?_2
s.to
?2x?_1+3x_2-S_1+? R?_1=8
x_1+x_2-S_2+? R?_2=4
x_1,x_2,? S?_1,S_2,? R?_1,? R?_2 ?0
? R?_1=8-?2x?_1-3x_2+S_1
? R?_2=4-x_1-x_2+S_2
x_0=6x_1+4x_2+M(8-?2x?_1-3x_2+S_1 )+
M(4-x_1-x_2+S_2)
x_0=6x_1+4x_2+M{12-3x_1-4x_2+S_1+S_2}
x_0=(6-3M) x_1+(4-4M) x_2+12M+MS_1+MS_2
x_0-(6-3M) x_1-(4-4M) x_2-MS_1-MS_2=12M
يتكون لدينا جدول الحل الأساسي التالي:
x_1 x_2 S_1 S_2 ? R?_1 ? R?_2 R.H.S Ratio
? R?_1 2 3 -1 0 1 0 8 2.7
? R?_2 1 1 0 -1 0 1 4 4
x_0 (-6+3M) (-4+4M) -M -M 0 0 12M
المتغير الداخل (x_2) يقابل أكبر قيمة موجبة (-4+4M) في صف دالة الهدف (x_0) والخارج هو (? R?_1) كونه يقابل أقل قيمة موجبة (2.7) في عمود النسبة والعنصر العمودي هو (3) وستكون الدالة المحورية هي:
Pivot Equation= [0.67,1,-0.33,0,0.33,0,2.7]
New (R_1 )=[?(1@1@?(0@-1@?(0@1@4)))]-{1[?(0.67@1@?(-0.33@0@?(0.33@0@2.7)))]}=[?(0.33@0@?(0.33@-1@?(-0.33@1@1.3)))]
New (x_0 )=[?(-6+3M@-4+4M@?(-M@-M@?(0@0@12M)))]-{-4+4M[?(0.67@1@?(-0.33@0@?(0.33@0@2.7)))]}=[?(-3.32+0.32M@0@?(-1.32+0.32M@-M@?(1.32-1.32M@0@10.8+1.2M)))]
يتكون لدينا جدول الحل الثاني التالي:
x_1 x_2 S_1 S_2 ? R?_1 ? R?_2 R.H.S Ratio
? x?_2 0.67 1 -0.33 0 0.33 0 2.7 4.03
? R?_2 0.33 0 0.33 -1 -0.33 1 1.3 3.94
x_0 -3.32+0.32M 0 -1.32+0.32M -M 1.32-1.32M 0 10.8+1.2M
المتغير الداخل (x_1) يقابل أكبر قيمة موجبة (-3.32+0.32M) في صف دالة الهدف (x_0) والخارج هو (? R?_2) كونه يقابل أقل قيمة موجبة (3.94) في عمود النسبة والعنصر العمودي هو (3) وستكون الدالة المحورية هي:
Pivot Equation= [1,0,1,-3.03,-1,3.03,3.94]
New (x_2 )=[?(0.67@1@?(-0.33@0@?(0.33@0@2.7)))]-{0.67[?(1@0@?(1@-3.03@?(-1@3.03@3.94)))]}=[?(0@1@?(-1@2.03@?(1@2.03@0.6)))]
New (x_0 )=[?(-3.32+0.32M@0@?(-1.32+0.32M@-M@?(1.32-1.32M@0@10.8+1.2M)))]-{-3.32+0.32M[?(1@0@?(1@-3.03@?(-1@3.03@3.94)))]}
=[?(0@0@?(-2@-10.06@?(-2+M@10.06-M@23.88)))]
يتكون لدينا جدول الحل الثالث التالي:
x_1 x_2 S_1 S_2 ? R?_1 ? R?_2 R.H.S
? x?_2 0 1 -1 2.03 1 2.03 0.06
? x?_1 1 0 1 -3.03 -1 3.03 3.94
x_0 0 0 -2 -10.06 -2+M 10.06-M 23.88
وبذلك يكون الحل الأمثل هو:
x_1=3.94,x_2=0.06,x_0=23.8
المادة المعروضة اعلاه هي مدخل الى المحاضرة المرفوعة بواسطة استاذ(ة) المادة . وقد تبدو لك غير متكاملة . حيث يضع استاذ المادة في بعض الاحيان فقط الجزء الاول من المحاضرة من اجل الاطلاع على ما ستقوم بتحميله لاحقا . في نظام التعليم الالكتروني نوفر هذه الخدمة لكي نبقيك على اطلاع حول محتوى الملف الذي ستقوم بتحميله .
الرجوع الى لوحة التحكم
|