شارح الدرس: البرمجة الخطية الرياضيات

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

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

في التمثيل الخطي، تكون دالة الهدف هي دالة خطية في متغيِّرات. بعبارة أخرى، لأي مسألة دالة برمجة خطية في متغيِّرين، يجب أن تكون دالة الهدف مكتوبة على الصيغة: 󰎨(𞸎،𞸑)=𝛼𞸎+𝛽𞸑+𝛾، لأي ثوابت 𝛼، 𝛽، 𝛾.

وقيود البرمجة الخطية مُعطاة على صورة مجموعة من المتباينات الخطية، بمعنى أنها تكون متباينات على الصورة: 󰏡𞸎+𞸁𞸑+𞸢٠ لأي ثوابت أ، ب، 𞸢. وتكون المتباينات في القيود غير صارمة بوجه عام، والحل الأمثل لمسألة برمجة خطية، إن وُجِد، يقع على أحد رءوس منطقة الحل. يمكن أن يكون هناك أيُّ عدد من المتباينات في صورة قيود لمسألة واحدة من مسائل البرمجة الخطية.

وكل قيد على الصورة 󰏡𞸎+𞸁𞸑+𞸢٠ يُعرِّف منطقة نصف مستوى على المستوى 𞸎𞸑، نرسم حدودها بالخط المستقيم 󰏡𞸎+𞸁𞸑+𞸢=٠. إنَّ رسم المنطقة المُعطاة من القيد مهارة مهمة في البرمجة الخطية.

هيا نرسم المنطقة المُعطاة من القيد ٤𞸎𞸑+١٠. أولًا، علينا رسم الخط الفاصل ٤𞸎𞸑+١=٠. يمكننا إعادة ترتيب هذه المعادلة لنكتبها 𞸑=٤𞸎+١، وهو ما يعطينا المعادلة القياسية للخط المستقيم. هذا الخط يتضمَّن جزءًا مقطوعًا من المحور 𞸑 قيمته ١، وميلًا موجبًا قيمته ٤. علينا أولًا تمثيل هذا الخط بيانيًّا على المستوى𞸎𞸑.

هذا الخط يقسم المستوى 𞸎𞸑 إلى منطقتين. لتحديد المنطقة التي تحقِّق القيد المُعطى، يمكننا اختيار أي نقطة ليست على الخط لاختبار إذا ما كانت النقطة تحقِّق القيد المُعطى. ويُنصَح باختيار أبسط نقطة ممكنة لهذا الغرض. وإذا لم تكن نقطة الأصل (٠،٠) على الخط الحدودي، فهذا دائمًا هو أبسط اختيار. يمكننا التحقُّق ممَّا إذا كانت نقطة الأصل واقعة على الخط المستقيم بالتعويض بالنقطة (𞸎،𞸑)=(٠،٠) في المتباينة. وإذا تحقَّق «التساوي»، فهذا يشير إلى أن نقطة الأصل تقع على الخط المستقيم. في هذا المثال، عندما نعوِّض بالنقطة (٠،٠) في المتباينة ٤𞸎𞸑+١٠، نلاحظ أن الطرف الأيسر يساوي ٤(٠)+١=١. وبما أن التساوي لم يتحقَّق، ٤(٠)+١٠، إذن نقطة الأصل لا تقع على الخط.

والآن، يمكننا التحقُّق ممَّا إذا كانت نقطة الأصل تقع داخل المنطقة المُعطاة من القيد عن طريق اختبار المتباينة التامة ٤𞸎𞸑+١<٠. نعوِّض بالنقطة (٠،٠) في التعبير ٤𞸎𞸑+١، ويكون الناتج: ٤(٠)٠+١=١.

لكن، بما أن ١>٠، وهو ما يناقض المتباينة المُعطاة، إذن لا تحقِّق النقطة (٠،٠) المتباينة ٤𞸎𞸑+١<٠. بعبارة أخرى، نقطة الأصل (٠،٠) لا تقع في المنطقة التي وصفتها هذه المتباينة. وهذا يعني أن المنطقة المُعطاة بالقيد ٤𞸎𞸑+١٠ هي منطقة لا تتضمَّن نقطة الأصل. هذه المنطقة مظلَّلة في التمثيل البياني الآتي.

في البرمجة الخطية، تُوجَد عدة قيود؛ بحيث تكون المنطقة الناتجة هي المنطقة المشتركة بين كل منطقة على حِدَةٍ. على سبيل المثال، انظر القيود الثلاثة الموضَّحة هنا.

عندما ندمج القيود الثلاثة نحصل على المنطقة المثلثة المشتركة الموجودة بالأسفل.

في البرمجة الخطية، تشترك عدة قيود خطية لتكوين منطقة حدِّية على شكل مضلَّع. يُسمَّى هذا الجزء المشترك الذي تَحدُّه جميع القيود منطقة الحل، وتُسمَّى رءوس المضلع الحدِّي النقاط القصوى.

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

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

نظرية: النظرية الأساسية للبرمجة الخطية

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

لفهم هذا المبدأ على نحوٍ أفضل، نتناول مثالًا معًا. هيا نُوجِد القيمة العظمى لـ ٣𞸎+𞸑+٢ باستخدم القيود: 𞸎+𞸑١٠،𞸑٠،𞸎٠.

من خلال المناقشات التي أجريناها سابقًا، نجد أن منطقة الحل المثلثة موضَّحة هنا.

دعونا نرمز إلى دالة الهدف بالرمز 𞸓=٣𞸎+𞸑+٢. نريد إيجاد أكبر قيمة ممكنة للدالة 𞸓 في حين نُقيِّد قيم 𞸎، 𞸑؛ بحيث يقع (𞸎،𞸑) داخل منطقة الحل المثلثة. يمكننا حل معادلة دالة الهدف لإيجاد قيمة 𞸑 لنكتب: 𞸑=٣𞸎+𞸓٢.

ولقيم مختلفة من 𞸓، هذه هي معادلة الخط المستقيم الذي ميله ٣ والجزء المقطوع من المحور 𞸑 يساوي (٠،𞸓٢). على سبيل المثال، علينا أن نمثِّل هذا الخط بيانيًّا 𞸓=١، 𞸓=٢، 𞸓=٣، 𞸓=٤ فوق التمثيل البياني لمنطقة الحل. نلاحظ هنا أن: 𞸓=١𞸑=٣𞸎١،𞸓=٢𞸑=٣𞸎،𞸓=٣𞸑=٣𞸎+١،𞸓=٤𞸑=٣𞸎+٢.

لدينا إذن الخطوط التي تقطع المحور 𞸑، في النقطة (٠،١) عندما تكون 𞸓=١، والنقطة (٠،٠) عندما تكون 𞸓=٢، والنقطة (٠،١) عندما تكون 𞸓=٣، والنقطة (٠،٢) عندما تكون 𞸓=٤.

كل خط من الخطوط الحمراء المرسومة بيانيًّا سابقًا يمثِّل قيمًا مختلفة لدالة الهدف، كما هو موضَّح. نلاحظ أن جميع الخطوط الحمراء لها الميل نفسه. ولن تؤثِّر القيم المختلفة لـ 𞸓 إلا على الجزء المقطوع من المحور 𞸑. ومن ثَمَّ، فإن مجموعة الخطوط التي تمثِّل دالة الهدف متوازية.

إذا كان أيُّ خط يتداخل مع منطقة الحل، حتى لو عند نقطة واحدة، فسيكون هناك زوج من قيم (𞸎،𞸑) داخل منطقة الحل يمكن أن يُنتِج قيمة لدالة الهدف المرتبطة بالخط المستقيم. إذا كان الخط لا يتقاطع مع منطقة الحل عند أيِّ نقطة من النقاط، فإن قيمة 𞸓 لا تتحقَّق داخل منطقة الحل. على سبيل المثال، 𞸓=٤ لا يتقاطع مع المنطقة المظلَّلة بالأعلى؛ لذا، لا يمكن تحقيق هذه القيمة.

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

يمكننا ملاحظة أن هذا الخط يرتبط بـ 𞸓=٣، وهو يتقاطع مع منطقة الحل عند نقطة وحيدة هي (٠،١). أيُّ خط يرتبط بـ 𞸓>٣ لن يتقاطع على الإطلاق مع المنطقة؛ لذا، 𞸓>٣ لا يمكن تحقيقه. وهذا يقودنا إلى استنتاج أن 𞸓=٣ هي القيمة العظمى لدالة الهدف داخل منطقة الحل.

في هذا المثال، نبحث عن «الخط الأخير» الملامس لمنطقة الحل. إذا كان هذا الخط موجودًا، فلا بد أن يمر عبر خط من الخطوط التي تحد المنطقة. وأيضًا، إذا كان الخط المستقيم يحتوي على رأس (أو أكثر)، فيجب أن يتقاطع «الخط الأخير» مع الخط في رأسٍ واحد. وهذا يوفر مبرِّرًا بديهيًّا للنظرية الأساسية في البرمجة الخطية.

مع أنه من الجيد وَضْع الحدس الهندسي في الاعتبار عند حل المسائل المتعلِّقة بالبرمجة الخطية، تُوجَد طريقة حسابية أبسط عندما تكون منطقة الحل محدودة. تذكَّر أن المنطقة المحدودة تعني أنه يمكن رسم دائرة حولها. منطقة الحل الموجودة في المثال السابق هي منطقة محدودة، كما هو موضَّح في الآتي.

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

نظرية: البرمجة الخطية لمناطق حل محدودة

في مسائل البرمجة الخطية التي تتضمَّن منطقة حل محدودة غير فارغة يجب أن يُوجَد حل عند أحد رءوس المنطقة.

بعبارة أخرى، يمكننا حل أي مسألة برمجة خطية تتضمَّن مناطق حل محدودة بالبحث عن القيمة المثلى بين رءوس المنطقة. وهذا يقودنا إلى الطريقة التالية لحل مسألة برمجة خطية باستخدام مناطق حل محدودة.

كيف نستخدم البرمجة الخطية في مناطق الحل المحدودة

ننظر إلى دالة هدف خطية 󰎨(𞸎،𞸑) باستخدام مجموعة من القيود الخطية. نفترض أن منطقة الحل محدودة. لإيجاد القيمة العظمى أو القيمة الصغرى لـ 󰎨(𞸎،𞸑) وفقًا للقيود المُعطاة، علينا اتباع الخطوات الآتية.

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

هيا نستخدم هذه الطريقة في المثال السابق. من منطقة الحل، نلاحظ أن الرءوس موجودة عند: (١،٠)،(٠،١)،(٠،٠).

نعوِّض بهذه النقاط في دالة الهدف 󰎨(𞸎،𞸑)=𞸎+٤𞸑+٢، لنحصل على: 󰎨(١،٠)=٣(١)+٠+٢=١،󰎨(٠،١)=٣(٠)+١+٢=٣،󰎨(٠،٠)=٣(٠)+٠+٢=٢.

أكبر قيمة لدالة الهدف في القائمة السابقة هي ٣؛ لذا، هذا هو حل هذا المثال. بعبارة أخرى، القيمة العظمى لـ 𞸎+٤𞸑+٢ عند التقيُّد بالمنطقة المظلَّلة تساوي ٣، وتقع عند 𞸎=٠، 𞸑=١. وهذا يتفق مع الإجابة باستخدام الطريقة السابقة.

هيا نتناول الأمثلة المتعلِّقة بالبرمجة الخطية التي تتضمَّن مناطق حل محدودة باستخدام هذه الطريقة.

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

باستخدام البرمجة الخطية، أوجد القيمة الصغرى والقيمة العظمى للدالة 𞸓=٤𞸎٣𞸑، علمًا بأن 𞸎٠، 𞸑٠، 𞸎+𞸑٩، 𞸑٥.

الحل

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

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

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

بعد ذلك، نعوِّض بهذه القيم في دالة الهدف 𞸓=𞸓(𞸎،𞸑)=٤𞸎٣𞸑: 𞸓(٠،٥)=٤(٠)٣(٥)=٥١،𞸓(٠،٩)=٤(٠)٣(٩)=٧٢،𞸓(٤،٥)=٤(٤)٣(٥)=١.

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

إذن ٧٢ هو القيمة الصغرى لـ 𞸓 (عندما تكون 𞸎=٠، 𞸑=٩)، و١ هو القيمة العظمى لـ 𞸓 (عندما تكون 𞸎=٤، 𞸑=٥).

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

أوجد القيمة العظمى لدالة الهدف 𞸓=٢𞸎+٦𞸑، علمًا بأن القيود 𞸎٠، 𞸑٠، 𞸎+𞸑٦، ٣𞸎+𞸑٩، 𞸎+٢𞸑٨.

الحل

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

بالنظر إلى الصورة المُعطاة، نلاحظ أن الرءوس هي النقاط: (٠،٠)،(٠،٤)،(٢،٣)،(٣،٠).

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

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

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

يمكن استخدام البرمجة الخطية في مسائل حياتية لإيجاد الحلول المثلى. في الأمثلة القليلة التالية، نتناول مسائل كلامية تتضمَّن مواقف حياتية.

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

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

الحل

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

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

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

وأخيرًا علينا التأكُّد من أن 𞸎٠، 𞸑٠؛ لأنه لا يمكن إنتاج عدد سالب من المكاتب. بوضعهما معًا، لدينا القيود ودالة الهدف: 𞸎٠،𞸑٠،٤𞸎+٣𞸑٥،٣𞸎+٤𞸑٧،𞸓=٠٦𞸎+٠٦𞸑.

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

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

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

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

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

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

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

الحل

الجزء الأول

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

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

ونلاحظ أن نقطة الأصل (٠،٠) تحقِّق المتباينة الصعبة ٥٫٢𞸎+٥٫٣𞸑<٠٤٢، وبما أن ٥٫٢(٠)+٥٫٣(٠)<٠٤٢، إذن هذه المتباينة تناظر المنطقة التي تشمل نقطة الأصل. بالتقاطع مع القيدين 𞸎٠، 𞸑٠، نحصل على المنطقة المظلَّلة التالية.

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

ونلاحظ أن نقطة الأصل (٠،٠) تحقِّق المتباينة الصارمة ٢𞸎+٠١𞸑<٠٨٤؛ لأن ٢(٠)+٠١(٠)<٠٨٤، إذن هذه المتباينة تناظر المنطقة التي تشمل نقطة الأصل. بالتقاطع مع القيدين 𞸎٠، 𞸑٠، نحصل على المنطقة المظلَّلة الآتية.

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

الجزء الثاني

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

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

الجزء الثالث

لعلنا نتذكَّر أن مسائل البرمجة الخطية التي تقع في منطقة حل محدودة لا بد أن يوجد حلها الأمثل عند أحد الرءوس. إذن منطقة الحل الموضَّحة في الجزء الأول لها أربعة رءوس. نقطة الأصل (٠،٠) من الرءوس الواضحة، ورأس آخر هو نقطة التقاطع مع المحور 𞸑، ويُحسَب من العلاقة ٢𞸎+٠١𞸑=٠٨٤ عندما تكون 𞸎=٠: ٢(٠)+٠١𞸑=٠٨٤٠١𞸑=٠٨٤𞸑=٨٤.

هذا الرأس إذن هو (٠،٨٤). وهناك رأس آخر هو نقطة التقاطع مع المحور 𞸎، والمُعطى من العلاقة ٥٫٢𞸎+٥٫٣𞸑=٠٤٢. يمكننا حساب ذلك بوضع 𞸑=٠: ٥٫٢𞸎+٥٫٣(٠)=٠٤٢٥٫٢𞸎=٠٤٢𞸎=٦٩.

هذا الرأس إذن هو (٦٩،٠). والرأس الأخير هو نقطة تقاطع الخطين المستقيمين المُعطيين من المعادلتين. ومن ثَمَّ، علينا حل نظام المعادلات الخطية: ٢𞸎+٠١𞸑=٠٨٤،٥٫٢𞸎+٥٫٣𞸑=٠٤٢.

يمكننا إعادة ترتيب المعادلة الأولى لإيجاد 𞸎، لنحصل على 𞸎=٠٤٢٥𞸑. وبالتعويض بذلك في المعادلة الثانية، نحصل على: ٥٫٢(٠٤٢٥𞸑)+٥٫٣𞸑=٠٤٢٠٠٦٥٫٢١𞸑+٥٫٣𞸑=٠٤٢٩𞸑=٠٦٣𞸑=٠٤.

ونعوِّض بقيمة ص في 𞸎=٠٤٢٥𞸑=٠٤٢٥(٠٤)=٠٤، فنحصل على الرأس (٠٤،٠٤). إذن حصلنا على الرءوس الأربعة: (٠،٠)،(٠،٨٤)،(٦٩،٠)،(٠٤،٠٤).

وأخيرًا، نعوِّض بهذه الرءوس في دالة الهدف ٨𞸎+٠١𞸑 لإيجاد نقطة الحل الأمثل. 𞸓(٠،٠)=٨(٠)+٠١(٠)=٠،𞸓(٠،٨٤)=٨(٠)+٠١(٨٤)=٠٨٤،𞸓(٦٩،٠)=٨(٦٩)+٠١(٠)=٨٦٧،𞸓(٠٤،٠٤)=٨(٠٤)+٠١(٠٤)=٠٢٧.

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

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

لقد تناولنا حتى الآن أمثلة فيها منطقة الحل محدودة. في هذه الحالة، من المؤكَّد أن حل مسألة البرمجة الخطية موجود؛ لذا، يمكننا اتباع الطريقة المذكورة لإيجاد الحل.

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

على سبيل المثال، هيا نحصل على أكبر قيمة لدالة الهدف 𞸓=٣𞸎+𞸑+٢ بالقيود: 𞸎+𞸑١٠،𞸑٠،𞸎٠.

منطقة الحل ممثَّلة بيانيًّا في الآتي.

نلاحظ أن المنطقة المظلَّلة غير محدودة؛ لأنه لا يمكن رسم دائرة حولها. وكما فعلنا من قبل، يمكننا حل دالة الهدف 𞸑، لنحصل على 𞸑=٣𞸎٢+𞸓. بعد ذلك نمثِّل بيانيًّا لمجموعة الخطوط: 𞸓=١𞸑=٣𞸎١،𞸓=٢𞸑=٣𞸎،𞸓=٣𞸑=٣𞸎+١،𞸓=٤𞸑=٣𞸎+٢.

وبتمثيل هذين الخطين بيانيًّا في أعلى منطقة الحل، نحصل على:

ونلاحظ، دون النظر إلى كبر مساحة 𞸓، أن الخط المستقيم يظل يتقاطع مع منطقة الحل. وهذا يعني ضمنيًّا أن 𞸓 يمكن أن تكون كبيرة كما نشاء، حتى في ظل هذه القيود. في هذه الحالة، نقول إنه لا توجد قيمة عظمى لدالة الهدف. بعبارة أخرى، الحل الخاص بالبرمجة الخطية غير موجود.

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

كيف: التحقُّق من حلول البرمجة الخطية لمناطق الحل غير المحدودة

افترض أن 𞸓=𞸓(𞸎،𞸑) هي دالة الهدف على منطقة حل غير محدودة. ومن ثمَّ:

  • إذا كانت 𞸓 محدودة من الأسفل (أي 𞸓𞸖 لثابت ما 𞸖)، فإن 𞸓 لها قيمة صغرى تقع في منطقة الحل.
  • وإذا كانت 𞸓 محدودة من الأعلى ( أي 𞸓𞸖 لثابت ما 𞸖)، فإن 𞸓 لها قيمة عظمى تقع في منطقة الحل.
  • إذا كانت الشروط السابقة غير واضحة، فعلينا تمثيل مجموعة من الخطوط تناظر دالة الهدف لنرى إذا ما كانت القيمة المثلى قابلة للتحقيق.

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

في المثال الأخير، سنتناول مسألة برمجة خطية بمنطقة حل غير محدودة.

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

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

السمادعدد وحدات مركبات النيتروجين لكل كيلوجرام عدد وحدات مركبات الفوسفات لكل كيلوجرامالتكلفة لكل كيلوجرام (جنيه مصري)
أ ٣ ٢ ١٧٠
ب ٦ ١ ١٢٠

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

الحل

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

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

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

إذن القيود هي: ٣𞸎+٦𞸑٨١،٢𞸎+𞸑٦،𞸎٠،𞸑٠.

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

بعد ذلك، دعونا نُحدِّد دالة الهدف. تريد المزرعة تقليل تكلفة الأسمدة المستخدَمة. استنادًا إلى الجدول التالي، تُعطى التكلفة الإجمالية للأسمدة من العلاقة ٠٧١𞸎+٠٢١𞸑. ومن ثَمَّ، تكون دالة الهدف هي: 𞸢=٠٧١𞸎+٠٢١𞸑.

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

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

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

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

نعوِّض بهذه النقاط في دالة الهدف 𞸢(𞸎،𞸑)=٠٧١𞸎+٠٢١𞸑. 𞸢(٠،٦)=٠٧١(٠)+٠٢١(٦)=٠٢٧،𞸢(٢،٢)=٠٧١(٢)+٠٢١(٢)=٠٨٥،𞸢(٦،٠)=٠٧١(٦)+٠٢١(٠)=٠٢٠١.

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

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

بدلًا من ذلك، يمكننا التحقُّق من أن الحل موجود بالنظر إلى التمثيل البياني لمجموعة من الخطوط لدالة الهدف. في هذه الطريقة، نبدأ بإعادة ترتيب دالة الهدف لإيجاد 𞸑، لنحصل على: 𞸑=٧١٢١𞸎+𞸢٠٢١.

وميل هذا الخط هو ٧١٢١، وهو يقع بين ميل خطين مستقيمين (١٢، ٢). يمكننا التمثيل بيانيًّا لبعض الخطوط المناظرة لـ: 𞸢=٠٢١𞸑=٧١٢١𞸎+١،𞸢=٠٢٧𞸑=٧١٢١𞸎+٥،𞸢=٠٠٢١𞸑=٧١٢١𞸎+٠١.

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

في الواقع، بتحريك الخطوط المتوازية إلى أعلى وإلى أسفل منطقة الحل، يمكننا أن نعرف أن «الخط الأخير» يجب أن يتقاطع مع منطقة الحل عند الرأس (٢،٢). إذن بالتعويض بـ (٢،٢) في دالة الهدف، نحصل على القيمة الصغرى: 𞸢(٢،٢)=٠٧١(٢)+٠٢١(٢)=٠٨٥.

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

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

النقاط الرئيسية

  • البرمجة الخطية طريقة تُستخدَم لإيجاد الحل الأمثل لدالة الهدف الخطية، وذلك باستخدام مجموعة من القيود الخطية.
  • بالنسبة إلى المتغيِّرات الفيزيائية التي لا يمكن أن تكون سالبة، تذكَّر القيدين 𞸎٠، 𞸑٠.
  • يمكننا التحقُّق ممَّا إذا كانت إحدى المسائل المتعلِّقة بالبرمجة الخطية تتضمَّن حلًّا بالطرق الآتية.
    • إذا كانت منطقة الحل محدودة، فستوجد قيمة عظمى وقيمة صغرى.
    • إذا كانت دالة الهدف محدودة من أسفل، فستوجد قيمة صغرى.
    • إذا كانت دالة الهدف محدودة من أعلى، فستوجد قيمة عظمى.
    • إذا لم ينطبق أيٌّ ممَّا سبق، فعلينا رسم مجموعة من الخطوط تمثِّل دالة الهدف؛ للتأكُّد ممَّا إذا كان الحل الأمثل قابلًا للتحقيق.
  • إذا كان للبرمجة الخطية حل، يجب أن يقع الحل على حد المنطقة، وإذا كان كل خط حَدِّي يحتوي على رأس أو رءوس، فلا بد أن يكون الحل عند أحد الرءوس.
  • في حالة وجود حل للبرمجة الخطية، يمكننا إيجاد الحل باستخدام الخطوات الآتية.
    • مثِّل منطقة الحل بيانيًّا باستخدام القيود.
    • أوجد كل الرءوس.
    • عوِّض بإحداثيات كل رأس في دالة الهدف.
    • حدِّد الحل.

تستخدم نجوى ملفات تعريف الارتباط لضمان حصولك على أفضل تجربة على موقعنا. معرفة المزيد حول سياسة الخصوصية لدينا.