شارح الدرس: البرمجة الخطية الرياضيات • الصف الأول الثانوي

مثال ١: إيجاد النقطة التي تحقِّق القيمة العظمى لدالة الهدف بمعلومية التمثيل البياني للقيود

باستخدام البرمجة الخطية، أوجد القيمة الصغرى والقيمة العظمى للدالة ، علمًا بأن ، ، ، .

الحل

في هذا المثال، نستخدم التمثيل البياني لمنطقة الحل. نلاحظ أن منطقة الحل الممكنة محدودة (بمعنى أنه يمكن أن تقع داخل دائرة). نتذكَّر هنا أنه إذا كانت منطقة الحل محدودة، فستكون القيمتان العظمى والصغرى لدالة الهدف الخطية عند رأسٍ من الرءوس. وفيما يلي خطوات تحديد القيمتين العظمى والصغرى.

1. مثِّل منطقة الحل بيانيًّا باستخدام القيود.
2. أوجد كل الرءوس.
3. عوِّض بإحداثيات كل رأس في دالة الهدف.
4. حدِّد الحل.

بما أن التمثيل البياني لمنطقة الحل مُعطى، ننتقل لإيجاد الرءوس. في هذا التمثيل البياني، نلاحظ أن رءوس منطقة الحل المثلثة هي:

بعد ذلك، نعوِّض بهذه القيم في دالة الهدف :

من القائمة السابقة، أكبر قيمة لـ تساوي ١، وأصغر قيمة لـ تساوي .

إذن هو القيمة الصغرى لـ (عندما تكون ، )، و١ هو القيمة العظمى لـ (عندما تكون ، ).

مثال ٢: إيجاد القيمة العظمى لدالة الهدف بمعلومية القيود والتمثيل البياني

أوجد القيمة العظمى لدالة الهدف ، علمًا بأن القيود ، ، ، ، .

الحل

لدينا التمثيل البياني لثلاث مناطق مظلَّلة، تناظر القيود المُعطاة. المنطقة المشتركة هي الشكل الرباعي البني الذي له رأس عند نقطة الأصل. هذه هي منطقة الحل في مسألة البرمجة الخطية المُعطاة.

بالنظر إلى الصورة المُعطاة، نلاحظ أن الرءوس هي النقاط:

نتذكَّر هنا أنه إذا كانت منطقة الحل محدودة (أي يمكن أن تقع داخل دائرة)، فإن كلًّا من القيم العظمى والصغرى ينبغي أن تقع عند أحد هذه الرءوس. نعوِّض بإحداثيات كل رأس في دالة الهدف :

أكبر قيمة في القائمة السابقة هي ٢٤.

إذن القيمة العظمى لدالة الهدف تساوي ٢٤، وهي تحدث عندما تكون ، .

مثال ٣: تكوين مجموعة المتباينات ودالة الهدف لمسألة كلامية تتعلَّق بالبرمجة الخطية

تُنتِج ورشة بها عاملان نوعَيْن من المكاتب المعدنية: النوع أ والنوع ب. يقوم أحد العاملَيْن بتصنيع المكاتب، ويقوم الآخر بطلائها. يستغرق العامل الأول ٤ ساعات لصناعة وحدة واحدة من النوع أ، و٣ ساعات لصناعة وحدة واحدة من النوع ب. في حين يستغرق العامل الثاني ٣ ساعات لطلاء وحدة واحدة من النوع أ، و٤ ساعات لطلاء وحدة واحدة من النوع ب. يعمل العامل الأول ٥ ساعات على الأقل يوميًّا، ويعمل الآخر ٧ ساعات يوميًّا كحدٍّ أقصى. إذا كانت الورشة تحقِّق ربحًا قيمته ٦٠ جنيهًا مصريًّا (من كل وحدة)، فأوجد دالة الهدف والمتباينة المطلوبة لحساب عدد الوحدات اللازم إنتاجها يوميًّا من كل نوع لزيادة الربح .

الحل

هيا نُحدِّد المتغيِّرات الأساسية لهذه المسألة. نُعرِّف بأنه عدد الوحدات المنتجة من النوع أ، ونُعرِّف بأنه عدد الوحدات المنتجة من النوع ب. تحقِّق الورشة ربحًا قيمته ٦٠ جنيهًا مصريًّا لكل مكتب من أيِّ نوعٍ منهما؛ لذا، فإن الربح يُعطى من العلاقة . هذه هي دالة الهدف التي نريد إيجادها في هذا المثال.

بعد ذلك، دعونا نتناول الوقت الذي يستغرقه العامل الأول. يستغرق العامل الأول ٤ ساعات لصناعة وحدة واحدة من النوع أ، و٣ ساعات لصناعة وحدة واحدة من النوع ب. لذا، فإن عدد الساعات الإجمالي الذي يقضيه العامل الأول يُعطى من . ويعمل العامل الأول يوميًّا على الأقل، وبذلك نحصل على القيد:

الآن، دعونا نتناول الوقت الذي يستغرقه العامل الثاني. يستغرق العامل الثاني ٣ ساعات لطلاء وحدة واحدة من النوع أ، و٤ ساعات لطلاء وحدة واحدة من النوع ب. لذا، فإن عدد الساعات الإجمالي الذي يقضيه العامل الثاني يُعطى من العلاقة . ويعمل العامل الثاني ٧ ساعات يوميًّا بحدٍّ أقصى، وهذا يعطينا القيد:

وأخيرًا علينا التأكُّد من أن ، ؛ لأنه لا يمكن إنتاج عدد سالب من المكاتب. بوضعهما معًا، لدينا القيود ودالة الهدف:

مثال ٤: استخدام الحل الخطِّي الأمثل في تحقيق أعلى ربح

تقوم شركة صغيرة بصبغ القمصان بلون واحد أو بعدة ألوان، وترغب إدارة الشركة في تحديد عدد القمصان من كل نوع لتجهيزها لموسم التخفيضات المقبل. تبلغ الميزانية ٢٤٠ دولارًا أمريكيًّا. ويتكلَّف شراء كل قميص دولارين أمريكيين. ويتكلَّف صبغ القميص بلون واحد ٠٫٥٠ دولار أمريكي، في حين تبلغ تكلفة صبغه بعدة ألوان ١٫٥٠ دولار أمريكي. لا يتبقى للشركة سوى ٨ ساعات لتجهيز جميع القمصان، وتستغرق دقيقتين لصبغ قميص بلون واحد، وتستغرق ١٠ دقائق لصبغ قميص متعدِّد الألوان.

تريد الشركة زيادة الأرباح، علمًا بأنه يمكن بيع القمصان التي بلون واحد مقابل ٨ دولارات أمريكية لكل قميص، والقمصان المتعددة الألوان مقابل ١٠ دولارات أمريكية لكل قميص.

افترض أن تمثِّل عدد القمصان ذات اللون الواحد، وتمثِّل عدد القمصان المتعدِّدة الألوان.

أيُّ الاختيارات الآتية يوضِّح المنطقة الممثِّلة للحل؟

حدِّد دالة الهدف.

ما عدد القمصان من كل نوع التي يجب على الشركة إنتاجها لزيادة أرباحها؟

الحل

الجزء الأول

علينا أولًا تحديد قيود هذه المسألة. افترض أن تمثِّل عدد القمصان ذات اللون الواحد، وتمثِّل عدد القمصان المتعدِّدة الألوان. وبما أنه لا يمكن أن يكون هناك عدد سالب من القمصان، إذن ينبغي أن تكون ، .

بعد ذلك، دعونا نتناول التكلفة الإجمالية. يتكلَّف شراء كل قميص دولارين أمريكيين، ولكن هناك تكلفة إضافية للصبغ. ويتكلَّف صبغ القميص بلون واحد ٠٫٥٠ دولار أمريكي، إذن التكلفة الكلية هي ٢٫٥٠ دولار أمريكي لكل قميص بلون واحد. ويتكلَّف صبغ القميص بعدة ألوان ١٫٥٠ دولار أمريكي، إذن التكلفة الكلية هي ٣٫٥٠ دولارات أمريكية لكل قميص متعدِّد الألوان. إذن التكلفة الإجمالية للقمصان بفئة دولار أمريكي تُعطى من العلاقة . وبما أن التكلفة الإجمالية لا يمكن أن تزيد على ٢٤٠ دولارًا أمريكيًّا نحصل على القيد:

ونلاحظ أن نقطة الأصل تحقِّق المتباينة الصعبة ، وبما أن ، إذن هذه المتباينة تناظر المنطقة التي تشمل نقطة الأصل. بالتقاطع مع القيدين ، ، نحصل على المنطقة المظلَّلة التالية.

هيا نتناول الآن الزمن الإجمالي. يستغرق صبغ قميص بلون واحد دقيقتين، ويستغرق صبغ قميص بعدة ألوان ١٠ دقائق. ومن ثَمَّ، فإن إجمالي الزمن (بالدقيقة) يُعطى بالعلاقة . وبما أن الزمن لا يمكن أن يتجاوز ٨ ساعات (أي: )، إذن نحصل على القيد:

ونلاحظ أن نقطة الأصل تحقِّق المتباينة الصارمة ؛ لأن ، إذن هذه المتباينة تناظر المنطقة التي تشمل نقطة الأصل. بالتقاطع مع القيدين ، ، نحصل على المنطقة المظلَّلة الآتية.

عند تداخل هاتين المنطقتين، نحصل على منطقة الحل الموضَّحة بالأسفل.

الجزء الثاني

نريد إيجاد أعلى ربح. لقد عرفنا أن الشركة تبيع القمصان التي بلون واحد مقابل ٨ دولارات أمريكية لكل قميص، والقمصان المتعدِّدة الألوان مقابل ١٠ دولارات أمريكية لكل قميص. إذن يُعطى الربح من العلاقة:

هذه هي دالة الهدف المطلوب إيجاد قيمتها العظمى.

الجزء الثالث

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

هذا الرأس إذن هو . وهناك رأس آخر هو نقطة التقاطع مع المحور ، والمُعطى من العلاقة . يمكننا حساب ذلك بوضع :

هذا الرأس إذن هو . والرأس الأخير هو نقطة تقاطع الخطين المستقيمين المُعطيين من المعادلتين. ومن ثَمَّ، علينا حل نظام المعادلات الخطية:

يمكننا إعادة ترتيب المعادلة الأولى لإيجاد ، لنحصل على . وبالتعويض بذلك في المعادلة الثانية، نحصل على:

ونعوِّض بقيمة ص في . من ثَمَّ، نحصل على الرأس . إذن حصلنا على الرءوس الأربعة:

وأخيرًا، نعوِّض بهذه الرءوس في دالة الهدف لإيجاد نقطة الحل الأمثل.

وبناءً على ذلك، فإن أعلى ربح هو ٧٦٨ دولارًا أمريكيًّا، ويتحقَّق عندما تكون ، .

لتحقيق أعلى ربح يجب أن تُنتِج الشركة ٩٦ قميصًا ملوَّنًا بلون واحدٍ ولا تنتج أي قمصان متعدِّدة الألوان.

مثال ٥: تكوين دوال الهدف لخفض التكلفة إلى الحد الأدنى، بمعلومية التمثيل البياني للقيود

يستطيع مُزارعٌ تحسين جودة إنتاجه في حال استخدامه ١٨ وحدة على الأقل من مركَّبات النيتروجين، و٦ على الأقل من مركَّبات الفوسفات. يمكنه استخدام نوعين من الأسمدة: أ، ب. يوضِّح الجدول تكلفة كل نوع من الأسمدة ومحتوياته.

إذا كان التمثيل البياني يمثِّل القيود المذكورة بالجدول، فأوجد أقل تكلفة يدفعها المُزارع لشراء الأسمدة؛ ليوفر كمية كافية من مركَّبات كلا النوعين.

الحل

نبدأ باستنتاج القيود الممثَّلة في التمثيل البياني. افترض أن الكمية المُستخدَمة من السماد أ بالكيلوجرمات، وأن الكمية المستخدمة من السماد ب بالكيلوجرمات. بعد ذلك، بناءً على الجدول الموضَّح، يمكن الحصول على كمية مركبات النيتروجين من العلاقة: . وبما أن المُزارع يحتاج إلى ١٨ وحدة على الأقل من مركبات النيتروجين، فسنحصل على:

ويُعطى مقدار مركَّبات الفوسفات حسب: . وبما أن المُزارع يحتاج إلى ٦ وحدات على الأقل من المركبات، نحصل على:

وبما أنه لا يمكن استخدام كمية سالبة من الأسمدة، إذن نحتاج أيضًا إلى القيدين ، .

إذن القيود هي:

هذه هي المنطقة المظلَّلة باللون الأرجواني في التمثيل البياني الموضَّح.

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

هناك طريقتان مختلفتان لحل هذه المسألة. وبما أن منطقة الحل غير محدودة (أي لا يمكن أن تقع داخل دائرة)، إذن علينا أولًا التحقُّق ممَّا إذا كان للمسألة حل.

الطريقة الأولى

نبدأ بالإشارة إلى أن دالة الهدف تمثِّل التكلفة، التي لا يمكن أن تكون سالبة. إذن ، ما يعني أن محدودة من أسفل. نتذكَّر أنه إذا كانت دالة الهدف محدودة من أسفل، فسيكون لها القيمة الصغرى في منطقة الحل. ومن ثَمَّ، يوجد حل.

ونتذكَّر أنه إذا كان يُوجَد حل لمسألة برمجية خطية، فلا بد أن يقع على خطٍّ حَدِّي. علاوةً على ذلك، إذا كان كل خط حَدِّي يحتوي على رأس، فلا بد أن يقع الحل عند أحد الرءوس. في التمثيل البياني المذكور، نلاحظ أن الرءوس هي:

نعوِّض بهذه النقاط في دالة الهدف .

بما أن أصغر قيمة فيما سبق هي ٥٨٠، إذن هذه هي القيمة الصغرى لدالة الهدف . ونلاحظ أيضًا أن هذه القيمة موجودة عندما يكون ، وهو ما توقَّعناه باستخدام التمثيل البياني.

الطريقة الثانية

بدلًا من ذلك، يمكننا التحقُّق من أن الحل موجود بالنظر إلى التمثيل البياني لمجموعة من الخطوط لدالة الهدف. في هذه الطريقة، نبدأ بإعادة ترتيب دالة الهدف لإيجاد ، لنحصل على:

وميل هذا الخط هو ، وهو يقع بين ميل خطين مستقيمين (، ). يمكننا التمثيل بيانيًّا لبعض الخطوط المناظرة لـ:

ونلاحظ أنه كلما كانت أصغر، انخفض الخط إلى أسفل أكثر. والخط المرتبط بـ لا يتداخل على الإطلاق مع منطقة الحل؛ أي هذه القيمة لـ لا يمكن تحقيقها. من ناحية أخرى، الخطان المرتبطان بـ ، يتداخل كلٌّ منهما مع منطقة الحل؛ ومن ثَمَّ، يمكن تحقيقهما. يمكننا من الصورة ملاحظة أنه لا بد من وجود قيمة صغرى ، وهو ما يعطينا «الخط الأخير» قبل أن يخرج هذا الخط بالكامل من منطقة الحل.

في الواقع، بتحريك الخطوط المتوازية إلى أعلى وإلى أسفل منطقة الحل، يمكننا أن نعرف أن «الخط الأخير» يجب أن يتقاطع مع منطقة الحل عند الرأس . إذن بالتعويض بـ في دالة الهدف، نحصل على القيمة الصغرى:

نلاحظ أن هذا يتفق مع إجابة الطريقة الأولى.

وبناءً على ذلك، فإن أقل تكلفة يمكن أن يدفعها المُزارع مقابل السماد مع توفير كميات كافية من المركَّبين هي ٥٨٠ جنيهًا مصريًّا باستخدام ٢ كجم من السماد أ، و٢ كجم من السماد ب.