نسخة الفيديو النصية
في هذا الفيديو، سوف نتعلم كيف نوجد الحل الأمثل لنظام خطي يتضمن دالة هدف وعدة قيود. تعرف الطريقة التي سنستخدمها لإيجاد هذا الحل الأمثل باسم «البرمجة الخطية». فدعونا نبدأ بتناول التعريف.
البرمجة الخطية هي طريقة لإيجاد الحل الأمثل، أي القيمة العظمى أو القيمة الصغرى، لدالة هدف خطية معطاة ومحددة بقيود تمثلها متباينات خطية. فلنتناول إذن دالة خطية، أي دالة تتضمن متغيرين ﺱ وﺹ وتكتب على الصيغة د ﺱ وﺹ يساوي ﺃﺱ زائد ﺏﺹ زائد ﺟ. تعرف هذه الدالة باسم «دالة الهدف»، وتكون معرفة لجميع قيم ﺱ وﺹ. كما ذكرنا، تتضمن طريقة البرمجة الخطية أيضًا القيود التي تمثلها المتباينات الخطية. على سبيل المثال، يمكن أن يكون كل من ﺱ وﺹ أكبر من أو يساوي صفرًا. وقد تكون لدينا أيضًا قيود تتضمن كلا المتغيرين معًا. على سبيل المثال، ﺱ زائد ﺹ أقل من أو يساوي خمسة.
بمعلومية دالة الهدف هذه ومجموعة من القيود، يتعين علينا إيجاد الحل الأمثل الذي نحصل عليه من خلال إيجاد القيمة العظمى أو الصغرى لدالة الهدف. إحدى طرق تمثيل ذلك هي رسم تمثيل بياني ثنائي الأبعاد. نبدأ برسم المستوى ﺱﺹ، كما هو موضح. يمكننا الآن استخدام القيود لتحديد منطقة على التمثيل البياني تحقق هذه القيود. أولًا، بما أن ﺱ أكبر من أو يساوي صفرًا، يمكننا أن نرسم خطًّا مستقيمًا عند ﺱ يساوي صفرًا. وفي هذه الحالة، سيكون خطًّا متصلًا. ولكن إذا كانت المتباينة تامة، أي ﺱ أكبر من صفر، فسنستخدم خطًّا متقطعًا.
في هذه المرحلة، يمكننا التظليل إما خارج المنطقة المطلوبة وإما داخلها. نحن نعلم أن جميع قيم ﺱ التي تقع على يسار هذا الخط الرأسي ستكون خارج المنطقة. لذلك، سنظلل، في هذا المثال، خارج المنطقة. يمكننا اتباع الأمر نفسه مع القيد الثاني. بما أن ﺹ أكبر من أو يساوي صفرًا، يمكننا رسم خط مستقيم عند ﺹ يساوي صفرًا. والمساحة أسفل المحور ﺱ لن تقع في منطقة الحل. لنتناول الآن القيد الثالث. ﺱ زائد ﺹ أقل من أو يساوي خمسة. ولتمثيل ذلك بيانيًّا، سنرسم أولًا الخط المستقيم الذي معادلته ﺱ زائد ﺹ يساوي خمسة. بالتعويض عن ﺱ بصفر في هذه المعادلة، نحصل على ﺹ يساوي خمسة. وبالمثل، عند ﺹ يساوي صفرًا، فإن ﺱ يساوي خمسة. إذن، يمكننا استنتاج أن النقطتين اللتين إحداثياتهما صفر، خمسة؛ وخمسة، صفر ستقعان على هذا الخط المستقيم.
بعد ذلك، علينا أن نحدد المنطقة التي تمثلها هذه المتباينة الخطية على التمثيل البياني. إحدى طرق تحديد ذلك هي جعل ﺹ المتغير التابع. بطرح ﺱ من طرفي المتباينة، يصبح لدينا ﺹ أقل من أو يساوي سالب ﺱ زائد خمسة. هذا يعني أن معادلة الخط المستقيم المرسوم هي ﺹ يساوي سالب ﺱ زائد خمسة. ومن ثم، تقع المنطقة التي يكون فيها الإحداثي ﺹ أقل من سالب ﺱ زائد خمسة أسفل الخط المستقيم؛ حيث تكون إحداثيات ﺹ ذات قيم أقل. وعليه، يمكننا تظليل المنطقة أعلى الخط المستقيم. لدينا الآن منطقة مظللة باللون الأخضر تحقق هذه القيود الثلاثة. وهذه المنطقة تعرف باسم «منطقة الحل». وأي نقطة تقع خارج هذه المنطقة تخالف قيدًا واحدًا على الأقل.
أي نقطة تقع داخل منطقة الحل هذه يمكن أن تكون الحل الأمثل لدالة الهدف. لكن لدينا مشكلة، وهي أنه يوجد عدد لا نهائي من الحلول داخل هذه المنطقة. عندئذ، تتضح إحدى الخواص الرائعة لهذه الطريقة المستخدمة. وهي أنه عندما نحصل على منطقة حل معرفة تمامًا كما في هذا المثال، فإن النقاط التي علينا التحقق منها لإيجاد الحل الأمثل تقتصر على رءوس منطقة الحل فقط، أي النقاط التي إحداثياتها هنا تساوي صفر، صفر؛ وصفر، خمسة؛ وخمسة، صفر. هذه هي النقاط الوحيدة التي يمكن أن تقع عندها القيمة العظمى أو القيمة الصغرى. ولمعرفة سبب ذلك، دعونا نتناول رسمًا ثلاثي الأبعاد.
بصفة عامة، تحتوي دالة الهدف على متغيرين، وهما ﺱ وﺹ في هذه الحالة. وتعطينا الدالة قيمة مخرجة معينة باستخدام المتغيرين. سنسمي هذه القيمة ﻉ. ويمكننا تمثيل ذلك على المحور ﻉ بإطار الإحداثيات. وبما أن دالة الهدف تتضمن كلًّا من قيم ﺱ وقيم ﺹ، فلا يمكن تمثيلها باستخدام خط مستقيم، وإنما باستخدام مستوى. بعبارة أخرى، إذا رسمنا دالة الهدف لجميع قيم ﺱ وﺹ، فسيبدو المستوى بهذا الشكل تقريبًا؛ حيث تمثل النقاط الواقعة على هذا المستوى جميع قيم ﻉ أو قيم دالة الهدف لجميع الأزواج الممكنة من قيم ﺱ وﺹ المدخلة. يعني هذا أن قيم ﻉ قد تكون موجبة إلى ما لا نهاية أو سالبة إلى ما لا نهاية. لكننا في مسائل البرمجة الخطية، لا نتعامل إلا مع مجموعة جزئية من قيم ﻉ هذه. وهذه المجموعة تتضمن قيم ﻉ التي تناظر قيم ﺱ وﺹ في منطقة الحل.
لمعرفة قيم ﻉ الممكنة هذه، يمكننا إسقاط منطقة الحل لأعلى على المستوى. وبذلك، سنحصل على منطقة أخرى على شكل مثلث. لكن هذا المثلث يوازي اتجاه ميل المستوى. إذا نظرنا إلى رءوس منطقة الحل في المستوى ﺱﺹ، فسنلاحظ أنها تناظر أعلى قيم لـ ﻉ وأدناها. هذا يعني أن القيمة العظمى أو القيمة الصغرى للحل ستكون عند أحد هذه الرءوس. وعلى الرغم من أن هذا ليس برهانًا قاطعًا على أن الحل الأمثل يقع عند أحد رءوس منطقة الحل، فإنه يشير على الأقل إلى إمكانية حدوث ذلك. لكن، هذا صحيح. فبغض النظر عن نوع المستوى الذي لدينا وزاوية ميله، فعند إسقاط منطقة الحل عليه، سيمثل رأس واحد أو أكثر الحل الأمثل.
خلاصة القول، لإيجاد الحل الأمثل، نعوض بإحداثيات رءوس منطقة الحل في دالة الهدف. وسيمكننا فعل ذلك مع جميع الرءوس من إيجاد القيمة العظمى والقيمة الصغرى للحل. لنتناول الآن كيفية تطبيق ذلك بشكل عملي.
باستخدام البرمجة الخطية، أوجد القيمتين العظمى والصغرى للدالة ر تساوي أربعة ﺱ ناقص ثلاثة ﺹ، علمًا بأن ﺱ أكبر من أو يساوي صفرًا، وﺹ أكبر من أو يساوي صفرًا، وﺱ زائد ﺹ أقل من أو يساوي تسعة، وﺹ أكبر من أو يساوي خمسة.
بالإضافة إلى المعطيات الموجودة في السؤال، لدينا تمثيل بياني يوضح منطقة الحل وفقًا للقيود. توجد أربعة قيود تمثلها متباينات خطية. نلاحظ أنه بما أن ﺹ أكبر من أو يساوي صفرًا وأكبر من أو يساوي خمسة، فعلينا تناول المتباينة الثانية فقط. وهذه المتباينة يمثلها الخط المستقيم الأفقي الذي يمر بالعدد خمسة على المحور ﺹ. والمتباينة ﺱ أكبر من أو يساوي صفرًا يمثلها الخط المستقيم ﺱ يساوي صفرًا. ومنطقة الحل تتضمن جميع القيم الواقعة على هذا الخط المستقيم أو على يمينه، أي جميع قيم ﺱ الأكبر من أو تساوي صفرًا.
وأخيرًا، لدينا الخط المستقيم ﺱ زائد ﺹ يساوي تسعة. وبما أن ﺱ زائد ﺹ أقل من أو يساوي تسعة أو ﺹ أقل من أو يساوي سالب ﺱ زائد تسعة، فإن منطقة الحل تحتوي على كل النقاط التي تقع على هذا الخط المستقيم أو أسفله. وإذا كانت علامة المتباينة أقل من فقط، فإن منطقة الحل ستقع أسفل الخط المستقيم.
في هذا السؤال، مطلوب منا إيجاد القيمتين العظمى والصغرى للدالة ر تساوي أربعة ﺱ ناقص ثلاثة ﺹ. وباستخدام البرمجة الخطية، نعلم أن هاتين القيمتين تقعان عند أحد رءوس منطقة الحل. هذه الرءوس الثلاثة إحداثياتها صفر، خمسة؛ وصفر، تسعة؛ وأربعة، خمسة. هذه هي القيم الوحيدة التي نحصل عندها على الحل الأمثل، أي نحصل عندها على القيمة الصغرى أو القيمة العظمى. بالتعويض عن ﺱ بصفر وعن ﺹ بخمسة في الدالة، يصبح لدينا ر يساوي أربعة مضروبًا في صفر ناقص ثلاثة مضروبًا في خمسة. وهذا يساوي سالب ١٥. وعند النقطة صفر، تسعة، لدينا ر يساوي أربعة مضروبًا في صفر ناقص ثلاثة مضروبًا في تسعة. وهذا يساوي سالب ٢٧.
وأخيرًا، عند رأس منطقة الحل، حيث ﺱ يساوي أربعة وﺹ يساوي خمسة، لدينا ر يساوي واحدًا. يمكننا الآن ببساطة اختيار القيمة الصغرى والقيمة العظمى لهذه النتائج الثلاث. نلاحظ أن سالب ٢٧ هو القيمة الصغرى وواحدًا هو القيمة العظمى. إذن، القيمتان الصغرى والعظمى للدالة ر تساوي أربعة ﺱ ناقص ثلاثة ﺹ، وفقًا للقيود المعطاة، هما سالب ٢٧ وواحد.
سنتناول الآن مسألة كلامية.
تقوم شركة صغيرة بصبغ القمصان بلون واحد أو بعدة ألوان، وترغب إدارة الشركة في تحديد عدد القمصان من كل نوع لتجهيزها لموسم التخفيضات المقبل. تبلغ الميزانية ٢٤٠ دولارًا أمريكيًّا. يتكلف شراء قميص غير مصبوغ دولارين أمريكيين. يتكلف صبغ القميص بلون واحد ٥٠ سنتًا إضافية ويتكلف صبغ القميص بعدة ألوان دولارًا أمريكيًّا و ٥٠ سنتًا. لا يتبقى للشركة سوى ثماني ساعات لتجهيز جميع القمصان لموسم التخفيضات. ويستغرق صبغ القميص بلون واحد دقيقتين، ويستغرق صبغه بعدة ألوان ١٠ دقائق. قررت الشركة أن ترسم تمثيلًا بيانيًّا للمساعدة في زيادة الأرباح، علمًا بأن القمصان ذات اللون الواحد تحقق ربحًا مقداره ثمانية دولارات أمريكية لكل قميص، والقمصان المتعددة الألوان تحقق ربحًا مقداره ١٠ دولارات أمريكية لكل قميص. افترض أن ﺱ يمثل عدد القمصان ذات اللون الواحد، وﺹ يمثل عدد القمصان المتعددة الألوان.
يتضمن السؤال ثلاثة أجزاء سنتناولها بعد قليل. لكن قبل أن نفعل ذلك، دعونا نفكر في بعض المعطيات. يوجد نوعان من القمصان التي تنتجها الشركة؛ وهما القمصان ذات اللون الواحد التي يمثلها ﺱ، والقمصان المتعددة الألوان التي يمثلها ﺹ. سنحل هذه المسألة باستخدام البرمجة الخطية من خلال تحديد دالة الهدف وبعض القيود التي تمثلها متباينات خطية أولًا. تتطلع الشركة إلى زيادة الأرباح. وعلمنا أن بيع كل قميص من القمصان ذات اللون الواحد يحقق للشركة ربحًا مقداره ثمانية دولارات أمريكية، ويحقق بيع كل قميص من القمصان المتعددة الألوان ربحًا مقداره ١٠ دولارات أمريكية. هذا يعني أن الربح بالدولار ر يساوي ثمانية ﺱ زائد ١٠ﺹ. يمكننا أيضًا كتابة ذلك على صورة دالة بدلالة ﺱ وﺹ؛ حيث د ﺱ وﺹ يساوي ثمانية ﺱ زائد ١٠ﺹ.
تشمل القيود المفروضة على الشركة كلًّا من الزمن المستغرق والنقود. إذا تناولنا القيود المتعلقة بالنقود أولًا، فسنجد أن السؤال يوضح لنا أن ميزانية الشركة تبلغ ٢٤٠ دولارًا أمريكيًّا. كما يوضح أيضًا أن تكلفة شراء قميص غير مصبوغ تساوي دولارين أمريكيين وتكلفة صبغ القميص بلون واحد تساوي ٥٠ سنتًا إضافية، وتكلفة صبغ القميص بعدة ألوان تساوي دولارًا أمريكيًّا و ٥٠ سنتًا إضافية. ومن ثم، يتكلف كل قميص مصبوغ بلون واحد دولارين أمريكيين و ٥٠ سنتًا. وبما أن الشركة تنتج ﺱ من هذه القمصان، يمكن كتابة ذلك على الصورة ٢٫٥ﺱ. يتكلف كل قميص متعدد الألوان ثلاثة دولارات أمريكية و ٥٠ سنتًا. ويمكن كتابة ذلك على الصورة ٣٫٥ﺹ. نعلم أن مجموع هذين الحدين يجب أن يكون أقل من أو يساوي ٢٤٠؛ لأن الميزانية الإجمالية تساوي ٢٤٠ دولارًا.
لنتناول الآن القيود المتعلقة بالزمن المستغرق. علمنا أن صبغ قميص بلون واحد يستغرق دقيقتين، وصبغه بألوان متعددة يستغرق ١٠ دقائق. ويتبقى للشركة ثماني ساعات أو ٤٨٠ دقيقة لتجهيز جميع القمصان. يمكن تمثيل ذلك بالمتباينة اثنان ﺱ زائد ١٠ﺹ أقل من أو يساوي ٤٨٠. سنفرغ الآن بعض المساحة لنتناول الأجزاء الثلاثة لهذا السؤال.
تشمل الأجزاء الثلاثة لهذا السؤال ما يلي. أي الاختيارات الآتية يوضح منطقة الحل؟ حدد دالة الهدف. ما عدد القمصان من كل نوع التي يجب على الشركة إنتاجها لزيادة أرباحها؟
لقد أجبنا بالفعل عن الجزء الثاني من السؤال. دالة الهدف أو دالة الربح هنا هي د ﺱ وﺹ تساوي ثمانية ﺱ زائد ١٠ﺹ. في الجزء الأول من السؤال، لدينا أربعة تمثيلات بيانية تتضمن الخطين المستقيمين ٢٫٥ﺱ زائد ٣٫٥ﺹ يساوي ٢٤٠، واثنان ﺱ زائد ١٠ﺹ يساوي ٤٨٠. نعلم أن اثنين ﺱ زائد ١٠ﺹ يجب أن يكون أقل من أو يساوي ٤٨٠. وهذا يعني أن منطقة الحل تقع أسفل هذا الخط المستقيم. إذن، يمكننا استبعاد الخيار (ب).
علمنا أيضًا أن ٢٫٥ﺱ زائد ٣٫٥ﺹ أقل من أو يساوي ٢٤٠. ومن ثم، يجب أن تقع منطقة الحل أيضًا أسفل الخط المستقيم الأزرق في التمثيلات البيانية. وهذا يجعلنا نستبعد الخيار (ج). لكي نحدد إذا ما كان التمثيل البياني (أ) هو الخيار الصحيح أو التمثيل البياني (د)، علينا التفكير في قيدين آخرين. بما أن عدد القمصان لا يمكن أن يكون سالبًا، يجب أن تكون قيمة كل من ﺱ وﺹ أكبر من أو تساوي صفرًا. هذا يعني أن منطقة الحل يجب أن تقع أعلى المحور ﺱ وعلى يمين المحور ﺹ. وعليه، يمكننا استبعاد الخيار (أ) لأن جزءًا من منطقة الحل يقع عند ﺱ أقل من صفر. إذن، الإجابة الصحيحة للجزء الأول من السؤال هي الخيار (د).
سنفرغ الآن بعض المساحة ونحل الجزء الثالث من هذا السؤال. لعلنا نتذكر أنه مطلوب منا في هذا الجزء إيجاد عدد القمصان من كل نوع التي يجب على الشركة إنتاجها لزيادة أرباحها. نتذكر أن دالة الربح أو الهدف تساوي ثمانية ﺱ زائد ١٠ﺹ، وأن منطقة الحل تخضع لأربعة قيود. نحن نعلم أن القيم العظمى الممكنة للدالة تقع عند رءوس منطقة الحل. لذا، سنبدأ بإيجاد إحداثيات هذه النقاط. أولًا، لدينا النقطة صفر، صفر. نعلم أنه عندما يتقاطع خط مستقيم مع المحور ﺱ، فإن ﺹ يساوي صفرًا. وبالتعويض بذلك في المعادلة ٢٫٥ﺱ زائد ٣٫٥ﺹ يساوي ٢٤٠، نحصل على ﺱ يساوي ٩٦. إذن، إحداثيات هذا الرأس هي ٩٦، صفر.
وبالمثل، عندما يتقاطع خط مستقيم مع المحور ﺹ، فإن الإحداثي ﺱ يساوي صفرًا. وبالتعويض بذلك في المعادلة اثنان ﺱ زائد ١٠ﺹ يساوي ٤٨٠، نحصل على ﺹ يساوي ٤٨، ومن ثم يقع الرأس الآخر عند صفر، ٤٨. يقع الرأس الرابع في منطقة الحل عند نقطة تقاطع المستقيمين القطريين. إحدى طرق إيجاد هذه النقطة هي إيجاد حل المعادلتين الآنيتين الموضحتين. وهناك العديد من الطرق لحلهما. إحدى هذه الطرق هي ضرب المعادلة الثانية في اثنين. وهذا يعطينا المعادلة خمسة ﺱ زائد سبعة ﺹ يساوي ٤٨٠.
بإعادة كتابة المعادلة الأولى أسفل المعادلة الثانية ثم طرح المعادلتين، نحصل على ثلاثة ﺱ ناقص ثلاثة ﺹ يساوي صفرًا. وبإضافة ثلاثة ﺹ إلى طرفي هذه المعادلة ثم قسمة الطرفين على ثلاثة، نحصل على ﺱ يساوي ﺹ. ومن ثم، يمكننا التعويض بذلك في المعادلة الأولى، فيصبح لدينا اثنان ﺹ زائد ١٠ﺹ يساوي ٤٨٠. وعند حل هذه المعادلة، نحصل على ﺹ يساوي ٤٠، وﺱ يساوي ذلك أيضًا. إذن، إحداثيات الرأس الرابع هي ٤٠، ٤٠.
يمكننا الآن التعويض بكل زوج من هذه الإحداثيات في دالة الهدف. تجدر الإشارة هنا إلى أن أي نقطة من هذه النقاط يمكن أن تكون الحل الأمثل وليس بالضرورة نقطة التقاطع التي حصلنا عليها للتو. بالتعويض بقيم ﺱ وﺹ، نحصل على دالة الهدف تساوي صفرًا و٤٨٠ و٧٦٨ و٧٢٠. ونظرًا لأن الشركة تسعى إلى زيادة الأرباح، فستختار أعلى قيمة. وبما أن ﺱ يمثل عدد القمصان المصبوغة بلون واحد، وﺹ يمثل عدد القمصان المصبوغة بعدة ألوان، فإن إنتاج ٩٦ قميصًا بلون واحد وعدم إنتاج قمصان بعدة ألوان سيؤدي إلى زيادة الأرباح. وإذا افترضنا أن جميع القمصان قد بيعت، فإن الأرباح ستساوي ٧٦٨ دولارًا أمريكيًّا.
سنلخص الآن بعض النقاط الرئيسية التي تناولناها في هذا الفيديو. البرمجة الخطية هي طريقة لإيجاد الحل الأمثل لدالة هدف خطية معطاة ومحددة بقيود تمثلها متباينات خطية. لاحظنا أيضًا أن المساحة المحددة بالقيود هي منطقة الحل، كما أن الحل الأمثل يقع عند رءوس هذه المنطقة.
