البرمجة الخطية
فكرة الدرس نمذجة مواقف حياتية بمسألة يُمكن حلّها باستعمال طريقة البرمجة الخطية بيانيًّا.
•• البرمجة الخطية ( linear programming ) : هي طريقة تعتمد التمثيل البياني على المستوى الإحداثي لإيجاد أكبر قيمة مُمكنة (قيمة عظمى) ، أو أصغر قيمة مُمكِنة (قيمة صغرى) لاقتران يُسمّى الاقتران الهدف ، ضمن مجموعة قيود ، يُمثّل كلٌّ منها متباينة خطية. فبتمثيل المتباينات الخطية (القيود) تتحدّد منطقة حلّ مشتركة لها تُسمّى منطقة الحلول المُمكنة ، وفيها تتحقَّق أكبر قيمة مُمكنة، أو أصغر قيمة مُمكنة للاقتران الهدف عند رؤوس المضلع الذي يُحدّد منطقة الحلول المُمكنة.
•• تُعرَّف البرمجة الخطية أيضًا بأنَّها طريقة البحث عن الحلّ الأمثل، وتتكوَّن مسألتها ممّا يأتي :
1) الاقتران الهدف : يكون في صورة: P = a x + b y ، حيث :
P : اسم الاقتران (مثل الربح).
a , b : عددان حقيقيان . x , y : متغيران.
2) القيود : نظام من المتباينات الخطية، وهي تُكتَب بدلالة المتغيرين x , y ، وتُحدِّد منطقة الحلول المُمكنة كما في الشكل المجاور.
مفهوم أساسي :
إذا وُجِدت قيمة عظمى أو قيمة صغرى للاقتران الهدف، فإنَّها تكون عند واحد أو أكثر من رؤوس منطقة الحلول المُمكِنة.
مثال 1
أجد إحداثيي النقطة ( 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
•• يُمكن حلُّ المسائل الحياتية التي تتضمَّن إيجاد أكبر ربح مُمكن بطريقة البرمجة الخطية ، واتباع خطوات تُشبه الخطوات الواردة في المثال 1، ولكن يتعيَّن قبل ذلك تحديد متغيرين ، مثل x , y ، وكتابة نظام متباينات خطية بدلالة كلٍّ منهما لتمثيل قيود المسألة ، وكتابة اقتران الربح بدلالتيهما أيضًا.
مثال 2 :
يمتلك مُزارِع 40 دونمًا من الأرض، ويريد تهيئة التربة في جزء منها لزراعتها بالذرة ، أو بالقمح، أو بكليهما ، إذا كان تكلفة تهيئة التربة لكل دونم لزراعة الذرة 50 دينارًا ، وتكلفة تهيئة التربة لكل دونم لزراعة القمح 25 دينارًا ، ويستغرق العمل لتهيئة كل دونم لزراعته بالذرة 3 أيام ، ويستغرق العمل لتهيئة كل دونم لزراعته بالقمح 4 أيام ، والربح المتوقع من كل دونم لمحصول الذرة 160 دينارًا ، والربح المتوقع من كل دونم لمحصول القمح 90 ديناراً ، إذا كان المبلغ الذي سينفقهُ المزارع على ذلك لا يزيد عن 1200 دينار ، وعليه تهيئة التربة وزراعتها في 120 يوماً . كم دونمًا سيزرع من كل محصول لتحقيق أكبر ربح ممكن؟
الحل :
الخطوة 1 : صياغة الفرضيات.
يُمكن تنظيم المعلومات الواردة في السؤال في جدول لتسهيل صياغة الفرضيات :
افرض أن عدد الدونمات التي ستُزرع ذرة = x ، وأنّ عدد الدونمات التي ستُزرع قمح = y
متباينة تكلفة تهيئة التربة لكل دونم : 50x + 25y ≤ 1200
متباينة عدد أيام العمل في كل دونم : 3x + 4y ≤ 120
إذا افترضتُ أنّ المُزارع سيبيع كل إنتاجه من المحصولين ، فإنَّ الربح المُتوقَّع هو :
P = 160 x + 90y
إذن : أراد المُزارِع أنْ يكون الربح أكبر ما يُمكن ضمن القيود الآتية :
50x + 25y ≤ 1200 , 3x + 4y ≤ 120 , x ≥ 0 , y ≥ 0
الخطوة 2 : تمثيل القيود بيانيًّا.
أُمثِّل نظام المتباينات الخطية، ثم أُظلِّل منطقة الحلول المُمكنة كما في الشكل المجاور.
الخطوة 3 : تحديد رؤوس منطقة الحلول المُمكِنة.
أُحدِّد إحداثيي كلٍّ من النقاط: A, B, C, D ، ثم أجد قيمة الربح P عند كلٍّ منها كما في الجدول الآتي :
| P = 180x + 100y | رؤوس منطقة الحلول المُمكِنة |
| P = 160(0) + 90(0) = 0 | A(0, 0) |
| P = 160(24) + 90(0) = 3840 | B(24, 0) |
| P = 160(14.4) + 90(19.2) = 4032 | C(14.4, 19.2) |
| P = 160(0) + 90(30) = 2700 | D(0, 30) |
( ملاحظة : أجد النقطة C بحل المعادلتين بالحذف أو التعويض )
الخطوة 4 : تحديد القيمة العظمى أو القيمة الصغرى.
أُلاحِظ من الجدول أنَّ أكبر ربح مُمكن هو 4032 دينارًا، وأنَّه يتحقق عند زراعة 14.4 دونمًا بالذرة ، وَ 19.2 دونمًا بالقمح.
•• أُلاحِظ من المثالين السابقين أنَّ منطقة الحلول المُمكنة التي تُحدِّدها القيود كانت مغلقة ؛ لأنَّ هذه القيود فرضت ذلك، ولكنَّ بعض المسائل الحياتية تتضمَّن إيجاد أقل تكلفة مُمكنة، أو أقل كمية مُستهلكة، وغير ذلك، فتكون منطقة الحلول عندئذٍ مفتوحة ؛ لأنَّ قيودها تفرض ذلك.
مثال 3 :
يخلط بعض مُربّي الماشية نوعين من العلف للحصول على مزيج ذي تكلفة أقل. ويُبيِّن الجدول المجاور تكلفة الكيس الواحد من كل نوع، وعدد الوحدات التي يحويها من البروتينات والمعادن والفيتامينات. إذا احتاجت الماشية يوميًّا إلى 150 وحدة من البروتينات، و 90 وحدة من المعادن، و 60 وحدة من الفيتامينات على الأقل، فكم كيسًا من النوع A والنوع B معًا يُمكن أن تستهلكه الماشية بأقل تكلفة مُمكنة؟
| النوع B | النوع A | |
| تكلفة الكيس الواحد | 12 JD | 10 JD |
| عدد وحدات البروتينات | 30 | 40 |
| عدد وحدات المعادن | 20 | 20 |
| عدد وحدات الفيتامينات | 30 | 10 |
الحل :
الخطوة 1 : صياغة الفرضيات
أفترض أنَّ عدد الأكياس من النوع A هو x ، وأنَّ عدد الأكياس من النوع B هو y
إذا افترضْتُ أنَّ هذه الماشية تستهلك كل ما يُقدَّم لها من النوعين يوميًّا، فإنَّ التكلفة C هي : C = 10 x + 12 y
المطلوب أنْ تكون التكلفة أقل ما يُمكن ضمن القيود الآتية :
40x + 30y ≥ 150 , 20x + 20y ≥ 90 , 10x + 30y ≥ 60 , x ≥ 0 , y ≥ 0
الخطوة 2 : تمثيل القيود بيانيًّا.
أُمثِّل نظام المتباينات الخطية ، ثم أُظلِّل منطقة الحلول المُمكنة كما في الشكل الآتي :
الخطوة 3 : تحديد رؤوس منطقة الحلول المُمكِنة.
أُحدّد إحداثيي كلٍّ من النقاط : A, B, C, D ، ثم أجد قيمة التكلفة C عند كلٍّ منها كما في الجدول الآتي:
| C = 10x + 12y | رؤوس منطقة الحلول المُمكنة |
| C = 10(0) + 12(5) = 60 | A(0, 5) |
| C = 10(1.5) + 12(3) = 51 | B(1.5, 3) |
| C = 10(3.75) + 12(0.57) = 46.5 | C(3.75, 0.75) |
| C = 10(6) + 12(0) = 60 | D(6, 0) |
الخطوة 4 : تحديد القيمة العظمى أو القيمة الصغرى.
أُلاحِظ من الجدول أنَّ أقل تكلفة مُمكنة هي 46.5 دينارًا، وأنَّ الماشية تستهلك وقتئذٍ 3.75 أكياس من العلف A ، و 0.75 كيس من العلف B ، لتلبية الحد الأدنى الذي يلزمها من البروتينات والمعادن والفيتامينات.