البرمجة الخطية

• نمذجة مواقف حياتية بمسألة يُمكن حلّها باستعمال طريقة البرمجة الخطية بيانيًّا.

ما البرمجة الخطية، وكيف تبدأ مسألة سلمى؟

دخلت سلمى محلًّا لبيع الأشتال، وأرادت شراء نوعين من شتلات البندورة، بما لا يزيد على ⁦4 JD⁩ ثمنًا ل 15 شتلة على الأكثر. وقد أظهرت اللوحة المجاورة المُعلّقة داخل المحلّ معلومات عن النوعين. كم شتلة ستشتري سلمى من كل نوع لإنتاج أكبر كمٍّ مُمكن من البندورة؟

• تتكوّن مسألة البرمجة الخطّية بمتغيّرين ممّا يأتي:

• $P$: اسم الاقتران (مثل الربح).
• $a, b$: عددان حقيقيان.
• $x, y$: متغيّران.

• أين تتحقق القيمتان؟ عند رؤوس المُضلَّع الذي يُحدّد منطقة الحلول المُمكِنة.

فأين نبحث عن الحلّ الأمثل بين كل نقاط المنطقة؟

أين تقع أكبر قيمة وأصغر قيمة للاقتران الهدف؟

أجد إحداثيي النقطة $(x, y)$ التي تجعل الاقتران $T = 4x + 5y$ أكبر ما يُمكن ضمن القيود الآتية:

$x + 2y \leq 16$ $3x + 2y \leq 24$ $x \geq 0, y \geq 0$

فما الخطوات العامة التي نتّبعها في كل مسألة من هذا النوع؟

ما خطوات حلّ أي مسألة برمجة خطية؟

• يسعى القائمون على الشركات والأعمال إلى تخفيض الكلفة وزيادة الإنتاجية وتحقيق أكبر ربح مُمكن.
• لكنّ ذلك يخضع لقيود ومُحدّدات، مثل: التمويل، وعدد العُمّال، وعدد ساعات العمل، وعوامل العرض والطلب.
• لحلّ هذا النوع من المسائل، أستعمل البرمجة الخطّية، وذلك باتّباع الخطوات الآتية:

فلنطبّق الخطوات الأربع على مسألة من الحياة.

كم جهازًا يُوفّر المتجر ليحقّق أكبر ربح؟

يُنتج مشغل صغير للأثاث المعدني 36 خزانة على الأكثر أسبوعيًا من نوعين مختلفين: ⁦A⁩، و ⁦B⁩.

يبلغ ربح الخزانة الواحدة من النوع ⁦A 35 JD⁩، ومن النوع ⁦B 45 JD⁩.

إذا كان ما يُباع من النوع ⁦A⁩ لا يقلّ عن 3 أمثال ما يُباع من النوع ⁦B⁩، فأجد عدد الخزائن التي يُنتجها المشغل من كل نوع لتحقيق أكبر ربح ممكن.

ماذا لو كانت منطقة الحلّ غير محدودة؟

• في المثالين السابقين كانت منطقة الحلّ الممكنة التي تُحدّدها القيود محدودة.
• لكنَّ بعض المسائل تتضمَّن إيجاد أقل تكلفة ممكنة، أو أقل كمية مُستهلكة، فتكون منطقة الحلّ عندئذ غير محدودة؛ لأنَّ قيودها تفرض ذلك.

حمية غذائية: يشترط نظام للحمية الغذائية توافر ما لا يقل عن 300 سعرة حرارية، و36 وحدة من فيتامين $A$، و90 وحدة من فيتامين $C$، ضمن الجزء السائل من الوجبة الغذائية.

ويُبيّن الجدول المجاور تكلفة العلبة الواحدة من نوعين مختلفين من الألبان، وعدد السعرات الحرارية، ووحدات فيتامين $A$ وفيتامين $C$ التي تحويها العلبة الواحدة.

كم علبة من كل نوع يُمكن أن يستهلكها يوميًا شخص يتّبع نظام الحمية الغذائية، ويريد تحقيق شروطها بأقل تكلفة مالية مُمكنة؟

إرشاد: أستعمل أوراق الرسم البياني الموجودة في نهاية كتاب التمارين.

تدرّب على إيجاد القيمة العظمى والقيمة الصغرى

أجد إحداثيي النقطة $(x, y)$ التي تجعل اقتران الهدف أكبر ما يُمكن ضمن القيود المعطاة في كلّ ممّا يأتي:

1. $P = 4x + 3y$ $x + 2y \le 4$

$x - y \le 1$ $x \ge 0, y \ge 0$

أكبر قيمة:

2. $R = 10x + 7y$ $0 \le x \le 60$

$0 \le y \le 60$ $5x + 6y \le 420$

3. $Z = 1.5x + y$ $x + 3y \le 15$

$4x + y \le 16$ $x \ge 0, y \ge 0$

أصغر قيمة:

4. $Q = 4x + 5y$ $x + y \ge 8$

$3x + 5y \ge 30$ $x \ge 0, y \ge 0$

5. $C = 8x + 4y$ $x + 2y \ge 4$

$3x + y \ge 7$ $2y - x \ge 7$ $x \ge 0, y \ge 0$

6. $K = 25x + 35y$ $8x + 9y \le 7200$

$8x + 9y \ge 3600$ $x \ge 0, y \ge 0$

زراعة: يُباع في محل للوازم الزراعية نوعان من الأسمدة هما $A, B$، ويُبيّن الجدول المجاور مكوّنات الكيلوغرام الواحد من هذين السمادين:

يُريد مزارع أن يكون مزيجًا من السمادين يحتوي على 36 وحدة على الأقلّ فوسفات، و24 وحدة على الأقلّ نيترات، و30 وحدة على الأقلّ أمونيا.

7. إذا كان ثمن الكيلوجرام من النوع $A$ دينارًا واحدًا، ومن النوع $B$ ⁦1.5 JD⁩، فأكتب اقتران التكلفة ونظام متباينات يصف هذا الموقف.

8. أُمثّل منطقة حل نظام المتباينات، وأجد إحداثيات رؤوسها.

9. أجد عدد الكيلوغرامات التي يشتريها من كل نوع؛ ليُحقّق غايته بأقل تكلفة.

10. دعاية: أراد صلاح طباعة كتيبات ونشرات دعائية لتسويق منتجات مزرعته من العسل الطبيعي، بحيث يحوي الكتيب الواحد 3 صفحات، وتحوي النشرة الواحدة صفحتين. تبلغ تكلفة طباعة الكتيب الواحد 0.2 من الدينار، وتكلفة طباعة النشرة الواحدة 0.1 من الدينار. وقد قرّر صلاح أنه بحاجة إلى طباعة ما لا يزيد على 600 صفحة، مُمثّلةً في 50 كتيبًا على الأقل، و150 نشرة على الأقل. كم عدد الكتيبات والنشرات التي يجب طباعتها بحيث تكون التكلفة أقل ما يُمكن؟

11. أحلّ المسألة الواردة في بند (مسألة اليوم).

تبرير وتحدٍّ: متى يكون الاقتران الهدف أكبر ما يُمكن؟

12. تبرير: أجد أكبر قيمة مُمكنة لاقتران الهدف $P = 5x + 6y$ ضمن منطقة الحلول الممكنة التي يُمثّلها الشكل المجاور، وأُبرّر إجابتي، ثمَّ أجد نقاطًا أخرى ضمن منطقة الحلّ يتحقّق عندها أكبر قيمة لاقتران الهدف، وأُبرّر إجابتي.

13. تحدّ: أجد اقتران هدف صورته $G = ax + by$، حيث $a, b$ عددان حقيقيان موجبان، وله أكبر قيمة عند النقطة $(2, 3)$، وهي 18، ضمن القيود المجاورة:

$x + 2y \le 8$ $x + y \le 5$ $x \ge 0, y \ge 0$ إرشاد: يوجد أكثر من إجابة.

14. تحدّ: أجد مجموعة قيم $n$ (حيث $n$ عدد صحيح موجب) التي تجعل لاقتران الهدف $D = 3x + ny$ أكبر قيمة مُمكنة عند النقطة $(3, 4)$، ضمن القيود المجاورة:

$x + 3y \le 15$ $4x + y \le 16$ $x \ge 0, y \ge 0$

اختبر نفسك على الوحدة كلها

• أختار رمز الإجابة الصحيحة في كلٍّ ممّا يأتي:

1. الزوج الذي يُمثّل حلًّا لنظام المتباينات الآتي هو:

$y + 5x < 7$ $2x - y \ge -3$ $\mathrm{a)}\ (3, 2)$ $\mathrm{b)}\ (0, 0)$ $\mathrm{c)}\ (-4, -2)$ $\mathrm{d)}\ (2, 8)$

2. إذا كان لنظام متباينات خطّيّة منطقة حلٍّ محدودة، رؤوسها هي: $P(0, 2), Q(2, 3), R(4, 2), S(3, 0)$؛ فإنّ القيمة العظمى لاقتران الهدف $T = 2x + y$ تتحدّد عند الرأس:

$\mathrm{a)}\ P$ $\mathrm{b)}\ Q$ $\mathrm{c)}\ R$ $\mathrm{d)}\ S$

3. نظام المتباينات الذي ليس له حلٌّ هو:

$\mathrm{a)}\ 3x + 5y \ge 15,\ 2x + 3y \ge 6$ $\mathrm{b)}\ x + 2y \ge 2,\ 2x + 4y \le 0$ $\mathrm{c)}\ 4x + 3y \ge 6,\ 4x + 3y \le 10$ $\mathrm{d)}\ x + y \ge 6,\ x + y \ge 3$

4. نظام المتباينات الذي له التمثيل البياني الآتي هو:

$\mathrm{a)}\ y \le 2x + 2,\ y > -x - 1$ $\mathrm{b)}\ y \ge 2x + 2,\ y < -x - 1$ $\mathrm{c)}\ y < 2x + 2,\ y \le -x - 1$ $\mathrm{d)}\ y > 2x + 2,\ y \le -x - 1$

أحُلُّ كلَّ نظام متباينات خطّيّة ممّا يأتي:

5. $x - 8y \le 9$ $4x + 7y > 3$

6. $12x + 10y > 1$ $-5x - 8y < 2$

7. أجد جميع الحلول المُمكِنة لنظام المتباينات الآتي، حيث $x$ و $y$ عددان صحيحان موجبان:

$x + y > 4$ $3x + 7y \le 21$

8. أجد أكبر قيمة للاقتران $P = 4x + y$ ضمن القيود الآتية:

$x + y \le 50$ $3x + y \le 90$ $x \ge 0, y \ge 0$

9. أجد أصغر قيمة للاقتران $C = 200x + 500y$ ضمن القيود الآتية:

$x + 2y \ge 10$ $3x + 4y \le 24$ $x \ge 0, y \ge 0$

طرود خيرية: يريد تاجر مواد تموينية تشغيل عدد من العُمّال يومًا واحدًا لتجهيز طرود تُباع في شهر رمضان. حدَّد التاجر أجرة العامل الماهر في هذا اليوم بـ ⁦30 JD⁩، وأجرة العامل المبتدئ بـ ⁦20 JD⁩، لكنَّه لا يريد أن يُنفِق أكثر من ⁦630 JD⁩ على تجهيز الطرود. استطاع التاجر إيجاد 15 عاملًا ماهرًا فقط؛ لذا قرَّر أن يُشغِّل عاملًا ماهرًا واحدًا على الأقل مُقابِل كل 3 عُمّال مُبتدِئين، علمًا بأنَّ العامل الماهر يُجهِّز 25 طردًا في الساعة، والعامل المُبتدِئ يُجهِّز 18 طردًا في الساعة:

10. أكتب نظام متباينات يُمثّل هذه المعلومات، ثمَّ أُمثِّله.

11. أجد عدد العُمّال المَهَرة والعُمّال المُبتدِئين الذين يجب تشغيلهم لتجهيز أكبر عدد مُمكِن من الطرود.

تعليم: يعقد مصنع دورة تدريبية لطلبة الهندسة في إحدى الجامعات، بحيث يكون عدد الطالبات المُتدرِّبات $x$، وعدد الطلاب المُتدرِّبين $y$، ولا يقلُّ العدد الإجمالي للطالبات والطلاب عن 5، ولا يزيد على 15، ولا يقلُّ عدد الطلاب عن نصف عدد الطالبات:

12. أشرح بالكلمات معنى: $2y \ge x$.

13. إذا كان عدد الطالبات المُتدرِّبات 6، فما العدد المُمكِن للطلاب المُتدرِّبين؟

14. يُنتِج مصنع نوعين من القطع المعدنية باستعمال الآلتين $A$ و $B$ معًا. ويُبيِّن الجدول التالي الزمن الذي تستغرقه معالجة القطعة الواحدة في كلٍّ من الآلتين، ومقدار ربح المصنع من بيع القطعة الواحدة من كل نوع. إذا كان عدد ساعات العمل اليومي للآلة $A$ لا يزيد على ⁦10 h⁩، وعدد ساعات العمل اليومي للآلة $B$ لا يزيد على ⁦6 h⁩، فكم قطعة من كل نوع يجب أن يُنتِج المصنع يوميًا لتحقيق أكبر ربح مُمكِن؟