برمجة الأعداد الصحيحة
تعريف برمجة الأعداد الصحيحة
تعريف برمجة الأعداد الصحيحة هي عبارة عن مسألة أمثلة رياضية أو برنامج لدراسة الجدوى، الذي فيه بعض أو كل المتغيرات لابد أن تكون أعداد صحيحة
فالبرمجة الخطية الأصلية لها حلول ممتازة ، فعندما يقتصر المتغير المستقل على الأعداد الصحيحة ستظهر حلول برمجة الأعداد الصحيحة على النحو التالي:
1- الحلول المثلى للبرمجة الخطية الأصلية كلها أعداد صحيحة ، لذا فإن الحلول المثلى لبرمجة الأعداد الصحيحة تتوافق مع الحلول المثلى للبرمجة الخطية.
2- لا يوجد حل عملي لبرمجة الأعداد الصحيحة.
3- هناك حلول مجدية (بالطبع هناك حلول جيدة) ، لكن قيمة الحلول الجيدة تصبح أسوأ.
(2) لا يمكن الحصول على الحل الأمثل لبرمجة الأعداد الصحيحة بمجرد تقريب الى الرقم الحقيقي
خطوات برمجة الأعداد الصحيحة
فهم المشكلة : الهدف من مسائل البرمجة الخطية إيجاد طريقة لحساب الربح أو النفقات، وهي ما يسمى الهدف، وتعتمد الإجابة على مقدار المتغيرات المختارة، التي تكون محدّدة بالقيود التي تتضمّنها المشكلة.
وصف الهدف : الهدف هو الأمر المراد الوصول له في نهاية العملية الإنتاجية وليس خلالها
وصف القيود : وصف حدود المتغيرات بالبحث عن كلمات مثل على الأقل، ليس أكثر من …إلخ.
تحديد المتغيرات : يجب اختيار المتغيرات التي تعبر عن مقدار بعض الأشياء
كتابة القيود باستخدام المتغيرات : لكل قيد يجب كتابة متباينة باستخدام المتغيرات الكتابة بطريقة سلسة ومفهومة : يجب أن تكون صيغة الكتابة مفهومة وبسيطة، وبعيدة عن التعقيد، فالهدف هو فهمها لتنفيذها.
طرق الحل الأمثل للبرمجة الصحيحة
: طريقة المستوى القاطع
طريقة المستوى القاطع لجوموري تعتمد على الخطوات التالية
1- نجد الحل الأمثل بطريقة الرسم البياني وتحديد منطقة الحل ونقطة الحل الأمثل
2- نعمل قاطع لمنطقة الحل بالقرب من نقطة الحل لمحور X2 ونجد قيم X1,X2 ثم قيم Z
عند هذه النقطة.
3- نعمل قاطع أخر ل X1 عند أقرب عدد صحيح لنقطة الحل نجد قيم X1,X2 عند هذا القاطع لتكون هذه النقطة اعداد صحيحة فقط
تمرين : حل نموذج البرمجة بأعداد الصحيحة التالي :
Z = 14 X₁ + 16X2 : Max
S.T
4X₁ + 3 X₂ ≤ 12
6X₁ + 8X₂ ≤ 24
X₁ X₂ ≥ 0 are integers
الحـــــل :
باستخدام المعلم البياني :
1. نقوم بتحويل القيود إلى رسم بياني
• القيد الأول
X1 | X2 |
0 | 4 |
3 | 0 |
• القيد الثاني
X1 | X2 |
0 | 3 |
4 | 0 |
ثم نقوم بالرسم البياني : 
2. نعتبر أن نقطة الحل الأمثل هي نقط تقاطع منحنيين C
3. ثم نقوم بإسقاط على المحورين
فنجـــــــــد النقطتين
1.6 = X1
X2 = 2.2
4. نقوم بتحويل النقطتين إلى أعداد صحيحة الأقرب لهما داخل المجال الحل :
فنجـــــــــــــد :
2 = X1 2 : X1
2 = X2
5. نقوم بتعويض في دالة الهدف :
فنجد : Z = 60
و هو الحـــــــــل الأمثل
البرمجة الصحيحة الثنائية
تمرين :
MAX Z = 60X1 + 48X2 + 84X3 + 78X4
القيود :
10X1 + 7X2+14+X3+12X4 ≤ 36
3X1+2X2+4X3 ≤ 6
كل المتغيرات = صفر او واحد
يمكن تحقيق هذا المطلوب من خلال اعداد الجدول التالي :
نختار البديل رقم 15 لأنه يحقق أكبر قيمة في دالة الهدف : 210
فإن حلول مشكلة البرمجة الأعداد الصحيحة كما يلي :
X1 = 0
X2 = 1
X3 = 1
X4 = 1