الدرس 2 من 3
تلخيص درس البرمجة الخطية
الدرس باختصار
البرمجة الخطّية طريقة بيانية لاختيار أفضل قرار عندما تكون الموارد محدودة، كأن نريد أكبر ربح أو أقل تكلفة. تُستعمل في المصانع والمتاجر والمزارع لتوزيع المال والوقت والمواد بين أنواع مختلفة من المنتجات.
مصطلحات الدرس
- الاقتران الهدف
- اقتران خطّي في المتغيّرين، مثل ، نريد إيجاد أكبر قيمة له أو أصغر قيمة.
- القيود
- متباينات خطّية تعبّر عن الحدود المفروضة على المتغيّرين، مثل المال المتاح أو عدد الساعات.
- منطقة الحلول المُمكِنة
- المنطقة المشتركة التي تحقّق جميع القيود معًا عند تمثيلها بيانيًّا.
- رؤوس المنطقة
- نقاط تقاطع المستقيمات الحدودية التي تشكّل زوايا المضلّع الذي يحدّ منطقة الحلول.
- الحلّ الأمثل
- النقطة من منطقة الحلول المُمكِنة التي تعطي أكبر قيمة أو أصغر قيمة للاقتران الهدف.
- شروط عدم السالبية
- القيدان و اللذان يعنيان أنّ الكمّيات لا يمكن أن تكون سالبة.
أهم الأفكار
مكوّنات المسألة
تتكوّن المسألة من اقتران هدف ومن نظام قيود، كلّ قيد منها متباينة خطّية في و .
الأمثل عند رأس
إذا وُجدت قيمة عظمى أو صغرى للاقتران الهدف فإنّها تتحقّق عند رأس واحد على الأقل من رؤوس منطقة الحلول المُمكِنة.
خطوات الحلّ
(1) نفترض المتغيّرين ونكتب الاقتران الهدف والقيود. (2) نمثّل القيود ونظلّل منطقة الحلول. (3) نجد إحداثيات الرؤوس بحلّ معادلتي المستقيمين المتقاطعين. (4) نعوّض كلّ رأس في الاقتران الهدف ونختار الأكبر أو الأصغر.
المنطقة غير المحدودة
في مسائل أقلّ تكلفة تكون المنطقة غالبًا غير محدودة، فنبحث عن القيمة الصغرى فقط، لأنّ القيمة العظمى غير موجودة.
أمثلة محلولة
مثال 1: رؤوس جاهزة من قيود بسيطة
أجد النقطة التي تجعل أكبر ما يُمكِن ضمن القيود: ، ، ، .
اعرض الحل
- نمثّل القيود: المنطقة مضلّع رؤوسه من تقاطع المستقيمات و والمحورين.
- الرؤوس هي و و و ؛ فالنقطة تحقّق و .
- نعوّض: عند تكون ، وعند تكون ، وعند تكون ، وعند تكون .
- أكبر قيمة هي وتحدث عند .
الجواب: النقطة وقيمة العظمى .
مثال 2: إيجاد رأس بحلّ معادلتين
أجد النقطة التي تجعل أكبر ما يُمكِن ضمن القيود: ، ، ، .
اعرض الحل
- الرؤوس من المحورين: و (من مع ) و (من مع ).
- الرأس الرابع من تقاطع و : بالطرح فتكون و .
- نعوّض: ، ، ، .
- أكبر قيمة عند .
الجواب: النقطة وقيمة العظمى .
مثال 3: مسألة حياتية: أكبر ربح
ينتج مشغل نوعين من الكراسي: كرسيًّا من النوع الأول و كرسيًّا من النوع الثاني. ربح الأول JD 8 وربح الثاني JD 6. لا يزيد عدد الكراسي على 20، وتحتاج الكراسي إلى ساعات عمل: 2 للأول و 3 للثاني، ومجموع الساعات المتاحة 48. كم كرسيًّا من كل نوع يحقّق أكبر ربح؟
اعرض الحل
- الاقتران الهدف: .
- القيود: ، ، ، .
- الرؤوس: و و (من مع ).
- تقاطع المستقيمين: من نضرب في 2 فنطرح: فتكون و ، فالرأس .
- نعوّض: ، ، ، .
- أكبر ربح JD 160 عند إنتاج 20 كرسيًّا من الأول ولا شيء من الثاني.
الجواب: 20 كرسيًّا من النوع الأول ولا شيء من الثاني، والربح JD 160.
مثال 4: أقلّ تكلفة: منطقة غير محدودة
تخلط مزرعة نوعين من العلف: الكيس من النوع الأول يكلّف JD 5 والكيس من النوع الثاني JD 4. تحتاج الماشية على الأقل إلى 12 وحدة بروتين و 10 وحدات معادن؛ الكيس الأول فيه 3 وحدات بروتين و 1 معادن، والثاني فيه 1 بروتين و 2 معادن. كم كيسًا من كل نوع بأقلّ تكلفة؟
اعرض الحل
- نفترض و عدد الأكياس. الاقتران الهدف: .
- القيود: ، ، ، ؛ والمنطقة غير محدودة.
- الرؤوس: (من مع ) و (من مع ).
- تقاطع المستقيمين: من نعوّض في : فتكون و .
- نعوّض: ، ، .
- أقلّ تكلفة JD 28.4 عند 2.8 كيس من الأول و 3.6 أكياس من الثاني.
الجواب: أقلّ تكلفة JD عند .
أخطاء شائعة
اختيار الرأس الذي يعطي أكبر إحداثيات بدل تعويض كلّ الرؤوس.
ليش غلط: القيمة المثلى تعتمد على معاملات الاقتران الهدف، وليس على كِبَر الإحداثيات.
الصح: عوّض كلّ رأس في الاقتران الهدف وقارن النتائج.
نسيان شروط عدم السالبية و .
ليش غلط: تؤثّر هذه الشروط في شكل منطقة الحلول وفي رؤوسها.
الصح: أضفها دائمًا إلى القيود في المسائل الحياتية.
البحث عن القيمة العظمى في مسألة أقلّ تكلفة ذات منطقة غير محدودة.
ليش غلط: الاقتران الهدف غير محدود من الأعلى في هذه الحالة.
الصح: ابحث عن القيمة الصغرى فقط عندما يكون المطلوب أقلّ تكلفة.
خطأ في إيجاد الرأس عند حلّ معادلتي المستقيمين.
ليش غلط: أي خطأ حسابي هنا يغيّر القيمة المحسوبة ويقلب القرار.
الصح: تحقّق بتعويض الرأس في المعادلتين معًا.
اختبر حالك
1. رأسان من رؤوس منطقة الحلول هما و والاقتران . ما قيمة العظمى بينهما؟
اعرض الجواب
الجواب:
و والأكبر .
2. أجد نقطة تقاطع المستقيمين و .
اعرض الجواب
الجواب:
بالجمع فتكون و .
3. ما قيمة الاقتران عند الرأس ؟
اعرض الجواب
الجواب:
.
جاهز تتدرّب؟
27 سؤال على هالدرس، بتتصحّح خطوة خطوة، ومعها تلميحات لما تعلق. أول أسئلة مجانية.
تدرّب على 27 سؤال من هالدرس مجانًا