تمرين حول البرمجة العددية

مثال (2):- اوجد الحل الأمثل للنموذج الرياضي الخطي الاتي:
Max Z=X1+X2
S.t 2X1+X26, X1+4X2 = 12, XL, X20 and integer.
Example (2):- Find the optimal solution for the mathematical linear programming model:
Max Z=X1+X2
S.t 2X1+X2?6
X1+4X2 < 12
X1, X2?0 and integer
الحل: 1- من خلال استخدام طريقة السمبلكس الاعتيادية نحصل على الحل الامثل كما موضح في الجدول أدناه:
RHS S2 S1 X2 X1 B.V
4.3 0.1 0.4 0 0 Z
1.7 -0.1 0.6 0 1 X1
2.6 0.3 -0.1 1 0 X2

1- كما نلاحظ أن النتائج التي تم الحصول عليها في الخطوة الأولى ليست ذات قيم عددية
صحيحة لجميع المتغيرات ننتقل إلى الخطوة رقم (3)
2- نكون قيد قطع ثانوي يضاف الى جدول الحل الامثل (1) وتعتمد عملية تكوين هذا القطع على المتغير الأساس ذو القيمة الحقيقية في عمود الحل ( R.H.S ) الذي يمتلك اكبر جزء حقيقي من بين المتغيرات الحقيقية الأخرى, ومن جدول (1) نلاحظ ان الجزء الحقيقي للمتغير X1 هو(0 . 7) أما الجزء الحقيقي للمتغير X2 هو(0.6)ىلذلك سنختار صف المتغير X1 أما المعادلة التي تقابل هذا المتغير في جدول الحل الجديد فتحسب بالشكل الاتي:-
(X1+0.6S1-0.1S2=1.7)
اذ يمكن اعادة كتابة المعادلة اعلاه ب صيغة أخرى بعد تطبيق القواعد المذكورة سابقة في حساب معادلة قيد القطع الكسري.
(0+1)X1+0+0.6)S1+(-1+0.9)S2= 1+0.7
0.6S1+0.9S2 = 0.7
-0.6S1-0.9S2 <= -0.7
ويتحويل القيد الأخير الى معادلة باضافة المتغير 3S نحصل على
-0.6S1-0.9S2 +S3= -0.7
أن المعادلة اعلاه تمثل معادلة القيد الذي سيقطع جزء معينا من حيز الحل مقتربين بذلك من الحيز الذي يحتوي على الحل العددي الأمثل فتضاف تلك المعادلة الى الجدول (1) لينتج جدول اخر يكون على الشكل الاتي:
RHS S3 S2 S1 X2 X1 B.V
4.3 0 0.1 0.4 0 0 Z
1.7 0 -0.1 0.6 0 1 X1
2.6 0 0.3 -0.1 1 0 X2
-0.7 1 -0.9 -0.6 0 0 S3

الان سيكون المتغير الخارج الذي يحمل قيمة سالبة هو المتغير S3 والمتغير الداخل هو المتغير S2 حسب طريقة السمبلكس المقابلة وبعد اجراء الحسابات نحصل على الجدول الاتي
RHS S3 S2 S1 X2 X1 B.V
4.2 0.2 0 0.3 0 0 Z
1.8 -0.2 0 0.7 0 1 X1
2.3 0.3 0 -0.3 1 0 X2
0.8 -1.2 1 0.7 0 0 S2

وكم نلاحظ ان النتائج لاتزال ذات قيم حقيقية غير عددية لذا نحتاج إلى تكوين قيد قطع ثانوي اخر معتمدين على المتغير الأساس الذي يمتلك اكبر قيمة حقيقية لذا سنختار X1 (0.8) وستكون المعادلة المقابلة لهذا المتغير كما مر سابقا
(0+1)X1+0+0.7)S1+(-1+0.8) S3=1+0.8 0.7S1+0.8S3> 0.8