البرمجة الخطية
البرمجة الخطِّية: هي طريقة تعتمد التمثيل البياني في المستوى الإحداثي لإيجاد أكبر قيمة مُمكِنة (قيمة عظمى)، أو أصغر قيمة مُمكِنة (قيمة صغرى) لاقتران يُسمّى الاقتران الهدف، ضمن مجموعة قيود، يُمثِّل كلٌّ منها متباينة خطِّية. فبتمثيل المتباينات الخطِّية (القيود) تتحدَّد منطقة حلٍّ مُشترَكة لها تُسمّى منطقة الحلول المُمكِنة، وفيها تتحقَّق أكبر قيمة مُمكِنة أو أصغر قيمة مُمكِنة للاقتران الهدف عند رؤوس المُضلَّع الذي يُحدِّد منطقة الحلول المُمكِنة.
تُعرَّف البرمجة الخطِّية بمُتغيِّرين أيضًا بأنَّها طريقة البحث عن الحلِّ الأمثل، وتتكوَّن مسألتها ممّا يأتي:
1) الاقتران الهدف : يكون في صورة: P = ax + by ، حيث :
P : اسم الاقتران (مثل الربح).
a , b : عددان حقيقيان . x , y : متغيران.
2) القيود : نظام من المتباينات الخطية، وهي تُكتَب بدلالة المتغيرين x , y ، وتُحدِّد منطقة الحلول المُمكنة كما في الشكل المجاور.
مفهوم: الحل الأمثل
إذا وُجِدت قيمة عظمى أو قيمة صغرى للاقتران الهدف، فإنَّها تكون عند واحد أو أكثر من رؤوس منطقة الحلول المُمكِنة.
مثال
أجد إحداثيي النقطة ( x, y ) التي تجعل الاقتران : P = 4x + y أكبر ما يُمكن ضمن القيود الآتية :
x + y ≤ 3
x – y ≤ 1
x ≥ 0 , y ≥ 0
الحل :
الخطوة 1 : تمثيل القيود بيانيًّا.
أُمثِّل نظام المتباينات الخطية (القيود) بيانيًّا، ثم أُحدّد منطقة الحلول المُمكنة كما في الشكل الآتي :
الخطوة 2 : تحديد رؤوس منطقة الحلول المُمكنة.
أُعيّن إحداثيي كلٍّ من نقاط رؤوس منطقة الحلول المُمكنة ، وهي: A, B, C, D ، ثم أضعها في جدول أحسب فيه قيمة الاقتران الهدف عند كلٍّ منها.
| P = 4x + y | رؤوس منطقة الحلول المُمكنة |
| P = 4(0) + 0 = 0 | A (0 , 0) |
| P = 4(1) + 0 = 4 | B (1 , 0) |
| P = 4(2) + 1 = 9 | C (2 , 1) |
| P = 4(0) + 3 = 3 | D (0 , 3) |
الخطوة 3 : تحديد القيمة العظمى أو القيمة الصغرى.
أُلاحِظ أنّ أكبر قيمة للاقتران P هي 9 ، وأنَّها تتحقَّق عندما x = 2 , y = 1
يسعى القائمون على الشركات الصناعية والتجارية ومختلف الأعمال إلى تخفيض الكلفة وزيادة الإنتاجية وتحقيق أكبر ربح مُمكِن، لكنَّ ذلك يخضع لقيود ومُحدِّدات، مثل: التمويل، وعدد العُمّال، وعدد ساعات العمل، وعوامل العرض والطلب، وغير ذلك من المُتغيِّرات.
لحلِّ هذا النوع من المسائل، أستعمل البرمجة الخطِّية، وذلك باتِّباع الخطوات الآتية:
① صياغة الفرضيات، وكتابة اقتران الهدف الذي يُراد إيجاد قيمته العظمى أو قيمته الصغرى، ثمَّ تحديد القيود.
② تمثيل نظام المتباينات بيانيًّا، ثمَّ تظليل منطقة الحلول المُمكِنة.
③ تحديد إحداثيات رؤوس منطقة الحلول المُمكِنة، وذلك بإيجاد نقاط تقاطع المستقيمات الحدودية عند تلك الرؤوس.
④ اختيار القيمة العظمى أو القيمة الصغرى وَفقًا لِما هو مطلوب في المسألة، وذلك بتعويض إحداثيات الرؤوس في اقتران الهدف.
مثال:
يخلط بعض مُربّي الماشية نوعين من العلف للحصول على مزيج ذي تكلفة أقل. ويُبيِّن الجدول المجاور تكلفة الكيس الواحد من كل نوع، وعدد الوحدات التي يحويها من البروتينات والمعادن والفيتامينات. إذا احتاجت الماشية يوميًّا إلى 150 وحدة من البروتينات، و 90 وحدة من المعادن، و 60 وحدة من الفيتامينات على الأقل، فكم كيسًا من النوع 1 والنوع 2 معًا يُمكِن أنْ تستهلكه الماشية بأقل تكلفة مُمكِنة؟
الخطوة 1 : أصوغ الفرضيات.
أفترض أنَّ عدد الأكياس من النوع 1 هو x، وأنَّ عدد الأكياس من النوع 2 هو .y إذا افترضْتُ أنَّ هذه الماشية تستهلك كل ما يُقدَّم لها من النوعين يوميًّا، فإنَّ التكلفة C هي:
T = 10 x + 12 y
المطلوب أنْ تكون التكلفة أقل ما يُمكِن ضمن القيود الآتية:
الخطوة 2 : أُمثِّل القيود بيانيًّا.
أُمثِّل نظام المتباينات الخطِّية، ثمَّ أُظلِّل منطقة الحلول المُمكِنة كما في الشكل المجاور.
الخطوة 3 : أُحدِّد رؤوس منطقة الحلول المُمكِنة.
أُحدِّد إحداثيي كلٍّ من النقاط: ،A, B, C, D
ثمَّ أجد قيمة التكلفة T عند كلٍّ منها كما في الجدول الآتي:
الخطوة 4 : أُحدِّد القيمة العظمى أو القيمة الصغرى.
أُلاحِظ من الجدول أنَّ أقل تكلفة مُمكِنة هي JD 46.5 ، وأنَّ الماشية تستهلك وقتئذٍ 3.75 أكياس من العلف 1، و 0.75 كيس من العلف 2، لتوفير الحدِّ الأدنى الذي يَلزمها من البروتينات والمعادن والفيتامينات.
