مقالات

3.1: تطبيقات التعظيم


أهداف التعلم

ستتعلم في هذا القسم:

  1. التعرف على الشكل النموذجي لمشكلة البرمجة الخطية
  2. صياغة مشاكل البرمجة الخطية للتعظيم
  3. رسم مناطق الجدوى من أجل تعظيم مشاكل البرمجة الخطية
  4. تحديد الحلول المثلى لتعظيم مشاكل البرمجة الخطية.

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

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

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

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

نبدأ بحل مشكلة تعظيم.

مثال ( PageIndex {1} )

يشغل نيكي وظيفتين بدوام جزئي ، الوظيفة الأولى والوظيفة الثانية. لا تريد أبدًا أن تعمل أكثر من 12 ساعة في الأسبوع. لقد قررت أنه مقابل كل ساعة تعمل فيها في الوظيفة 1 ، تحتاج إلى ساعتين من وقت التحضير ، ولكل ساعة تعمل في الوظيفة الثانية ، تحتاج إلى ساعة واحدة من وقت التحضير ، ولا يمكنها قضاء أكثر من 16 ساعة في التحضير.

إذا كانت نيكي تجني 40 دولارًا في الساعة في الوظيفة الأولى ، و 30 دولارًا في الساعة في الوظيفة الثانية ، فكم عدد الساعات التي يجب أن تعمل في الأسبوع في كل وظيفة لزيادة دخلها؟

المحلول

نبدأ باختيار متغيراتنا.

  • Let (x ) = عدد الساعات في الأسبوع سيعمل Niki في Job I.
  • Let (y ) = عدد الساعات في الأسبوع التي سيعمل فيها Niki في Job II.

الآن نكتب دالة الهدف. نظرًا لأن Niki تحصل على 40 دولارًا في الساعة في الوظيفة الأولى ، و 30 دولارًا في الساعة في الوظيفة الثانية ، فإن إجمالي دخلها الأول يتم إعطاؤه من خلال المعادلة التالية.

[I = 40x + 30y nonumber ]

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

[x + y leq 12 nonumber ]

تنص الجملة الثالثة على ما يلي: "لكل ساعة تعمل في الوظيفة الأولى ، تحتاج إلى ساعتين من وقت التحضير ، ولكل ساعة تعمل في الوظيفة الثانية ، تحتاج إلى ساعة واحدة من وقت التحضير ، ولا يمكنها قضاء أكثر من 16 ساعة في تجهيز." يتبع الترجمة.

[2x + y leq 16 nonumber ]

يتم تمثيل حقيقة أن (x ) و (y ) لا يمكن أن تكون سالبة مطلقًا بالقيدين التاليين:

[x geq 0 text {، and} y geq 0 nonumber. ]

حسنًا ، أخبار جيدة! لقد صاغنا المشكلة. نحن نعيد صياغتها كـ

ابدأ {مجموعة} {ll}
textbf {Maximize} & mathrm {I} = 40 mathrm {x} +30 mathrm {y}
textbf {Subject to:} & mathrm {x} + mathrm {y} leq 12
& 2 mathrm {x} + mathrm {y} leq 16
& mathrm {x} geq 0؛ mathrm {y} geq 0
نهاية {مجموعة}

لحل المشكلة ، نرسم القيود ونظلل المنطقة التي ترضي الكل قيود عدم المساواة.

يمكن استخدام أي طريقة مناسبة لرسم خطوط القيود. ومع ذلك ، غالبًا ما تكون أسهل طريقة هي رسم الخط عن طريق رسم تقاطع x وتقاطع y.

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

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

في الرسم البياني أدناه ، بعد رسم الخطوط التي تمثل القيود باستخدام طريقة مناسبة من الفصل 1 ، تم استخدام النقطة (0،0) كنقطة اختبار لتحديد ذلك

  • (0،0) يلبي القيد (x + y leq 12 ) لأن (0 + 0 <12 )
  • (0،0) يلبي القيد (2x + y leq 16 ) لأن (2 (0) + 0 <16 )

لذلك ، في هذا المثال ، نقوم بتظليل المنطقة الموجودة أسفل وعلى يسار على حد سواء خطوط القيد ، ولكن أيضًا فوق المحور x وعلى يمين المحور y ، من أجل تلبية المزيد من القيود (x geq 0 ) و (y geq 0 ).

المنطقة المظللة حيث يتم استيفاء جميع الشروط تسمى منطقة الجدوى أو مضلع الجدوى.

ال النظرية الأساسية للبرمجة الخطية ينص على أن القيمة القصوى (أو الدنيا) للدالة الموضوعية تحدث دائمًا عند رؤوس منطقة الجدوى.

لذلك ، سوف نحدد جميع الرؤوس (نقاط الزاوية) لمنطقة الجدوى. نسمي هذه النقاط نقاط حرجة. يتم سردها كـ (0 ، 0) ، (0 ، 12) ، (4 ، 8) ، (8 ، 0). لتعظيم دخل Niki ، سنقوم باستبدال هذه النقاط في الوظيفة الموضوعية لمعرفة النقطة التي تعطينا أعلى دخل في الأسبوع. نسرد النتائج أدناه.

نقاط حرجةدخل
(0, 0)40(0) + 30(0) = $0
(0, 12)40(0) + 30(12) = $360
(4, 8)40(4) + 30(8) = $400
(8, 0)40(8) + 30(0) = $320

من الواضح أن النقطة (4 ، 8) تحقق أكبر ربح: 400 دولار.

لذلك ، نستنتج أن Niki يجب أن يعمل 4 ساعات في Job I و 8 ساعات في Job II.

مثال ( PageIndex {2} )

يقوم المصنع بتصنيع نوعين من الأجهزة ، العادية والمميزة. تتطلب كل أداة استخدام عمليتين ، التجميع والتشطيب ، وتتوفر 12 ساعة على الأكثر لكل عملية. تتطلب الأداة العادية ساعة واحدة من التجميع وساعتين من الانتهاء ، بينما تحتاج الأداة المتميزة إلى ساعتين من التجميع وساعة واحدة من التشطيب. نظرًا لقيود أخرى ، يمكن للشركة أن تصنع 7 أدوات على الأكثر يوميًا. إذا تم تحقيق ربح قدره 20 دولارًا لكل أداة عادية و 30 دولارًا للأداة المتميزة ، فكم عددًا يجب تصنيعه من كل جهاز لزيادة الربح؟

المحلول

نختار متغيراتنا.

  • اسمحوا (x ) = عدد الأدوات العادية المصنعة كل يوم.
  • و (y ) = عدد الأدوات المتميزة المصنعة كل يوم.

وظيفة الهدف هي

[P = 20x + 30y بلا رقم ]

نكتب الآن القيود. تنص الجملة الرابعة على أن الشركة يمكنها صنع 7 أدوات على الأكثر في اليوم. هذا يترجم كـ

[x + y leq 7 nonumber ]

نظرًا لأن الجهاز العادي يتطلب ساعة واحدة من التجميع والأداة المتميزة تتطلب ساعتين من التجميع ، وهناك 12 ساعة متاحة على الأكثر لهذه العملية ، نحصل عليها

[x + 2y leq 12 nonumber ]

وبالمثل ، تتطلب الأداة العادية ساعتين من الانتهاء والأداة المتميزة ساعة واحدة. مرة أخرى ، هناك 12 ساعة متاحة على الأكثر للتشطيب. هذا يعطينا القيد التالي.

[2x + y leq 12 nonumber ]

يتم تمثيل حقيقة أن (x ) و (y ) لا يمكن أن تكون سالبة مطلقًا بالقيدين التاليين:

[x geq 0 text {، and} y geq 0 nonumber. ]

لقد صاغنا المشكلة على النحو التالي:

[ ابدأ {مجموعة} {كامل}
textbf {Maximize} & mathrm {P} = 20 mathrm {x} +30 mathrm {y}
textbf {Subject to:} & mathrm {x} + mathrm {y} leq 7
& mathrm {x} +2 mathrm {y} leq 12
& 2 mathrm {x} + mathrm {y} leq 12
& mathrm {x} geq 0؛ mathrm {y} geq 0
نهاية {مجموعة} غير رقم ]

لحل المشكلة ، نرسم بعد ذلك القيود ومنطقة الجدوى.

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

نظرًا لأن القيمة القصوى للدالة الموضوعية تحدث دائمًا عند رؤوس منطقة الجدوى ، فإننا نحدد جميع النقاط الحرجة. يتم سردها كـ (0 ، 0) ، (0 ، 6) ، (2 ، 5) ، (5 ، 2) ، و (6 ، 0). لتعظيم الربح ، سنقوم باستبدال هذه النقاط في الوظيفة الموضوعية لمعرفة النقطة التي تعطينا أقصى ربح كل يوم. النتائج مسجلة في الاسفل.

نقطة حرجةدخل
(0, 0)20(0) + 30(0) = $0

(0, 6)
20(0) + 30(6) = $180

(2, 5)
20(2) + 30(5) = $190

(5, 2)
20(5) + 30(2) = $160
(6,0)
20(6) + 30(0) = $120

النقطة (2 ، 5) هي التي تحقق أقصى ربح ، وهذا الربح هو 190 دولارًا.
لذلك ، نستنتج أنه يجب علينا تصنيع 2 أدوات عادية و 5 أدوات مميزة يوميًا للحصول على أقصى ربح قدره 190 دولارًا.

حتى الآن ركزنا على "مشاكل التعظيم القياسية" بحيث

  1. يجب تعظيم الوظيفة الهدف
  2. جميع القيود من الشكل (ax + by leq c )
  3. جميع المتغيرات مقيدة بـ غير سالب ( (س ≥ 0 ) ، (ص ≥ 0 ))

سننظر بعد ذلك في مثال لا يكون هذا هو الحال فيه. يقال إن مشكلتنا التالية "قيود مختلطة"، نظرًا لأن بعض قيود عدم المساواة هي من الشكل (ax + by ≤ c ) وبعضها على الشكل (ax + by ≥ c ). لا تزال القيود غير السلبية مطلبًا مهمًا في أي برنامج خطي.

مثال ( PageIndex {3} )

حل مسألة التكبير التالية بيانياً.

[ ابدأ {مجموعة} {كامل}
textbf {Maximize} & mathrm {P} = 10 mathrm {x} +15 mathrm {y}
textbf {Subject to:} & mathrm {x} + mathrm {y} geq 1
& mathrm {x} +2 mathrm {y} leq 6
& 2 mathrm {x} + mathrm {y} leq 6
& mathrm {x} geq 0؛ mathrm {y} geq 0
نهاية {مجموعة} غير رقم ]

المحلول

الرسم البياني مبين أدناه.

تم سرد النقاط الخمس الحرجة في الشكل أعلاه. يجب على القارئ أن يلاحظ أن القيد الأول (x + y ≥ 1 ) يتطلب أن منطقة الجدوى يجب أن تكون محدودة بالسطر (x + y = 1 ) ؛ لا تفي نقطة الاختبار (0،0) (x + y ≥ 1 ) ، لذلك نقوم بتظليل المنطقة على الجانب الآخر من الخط من نقطة الاختبار (0،0).

نقطة حرجةدخل
(1, 0)10(1) + 15(0) = $10
(3, 0)10(3) + 15(0) = $30
(2, 2)10(2) + 15(2) = $50
(0, 3)10(0) + 15(3) = $45
(0,1)10(0) + 15(1) = $15

من الواضح أن النقطة (2 ، 2) تزيد من وظيفة الهدف إلى أقصى قيمة قدرها 50.

من المهم ملاحظة أنه إذا كانت النقطة (0،0) تقع على خط القيد ، فلا يمكن استخدام (0،0) كنقطة اختبار. سنحتاج إلى تحديد أي نقطة أخرى نريدها لا تقع على الخط لاستخدامها كنقطة اختبار في تلك الحالة.

أخيرًا ، نتناول سؤالًا مهمًا. هل من الممكن تحديد النقطة التي تعطي القيمة القصوى دون حساب القيمة عند كل نقطة حرجة؟

الجواب نعم.

على سبيل المثال ( PageIndex {2} ) ، استبدلنا النقاط (0 ، 0) ، (0 ، 6) ، (2 ، 5) ، (5 ، 2) ، و (6 ، 0) ، في الهدف دالة (P = 20x + 30y ) ، وحصلنا على القيم $ 0 ، $ 180 ، $ 190 ، $ 160 ، $ 120 ، على التوالي.

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

لتحديد أكبر (P ) ، نقوم بالرسم البياني (P = 20x + 30y ) لأي قيمة (P ) من اختيارنا. لنفترض أننا نختار (P = 60 ). رسم بياني (20x + 30y = 60 ).

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

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

نلخص:

تعظيم مشاكل البرمجة الخطية

  1. اكتب دالة الهدف.
  2. اكتب القيود.
    1. بالنسبة لمشاكل البرمجة الخطية الخاصة بالتعظيم القياسي ، تكون القيود على الشكل: (ax + by ≤ c )
    2. نظرًا لأن المتغيرات غير سالبة ، فإننا نقوم بتضمين القيود: (x ≥ 0 ) ؛ (ص ≥ 0 ).
  3. ارسم القيود.
  4. تظليل منطقة الجدوى.
  5. ابحث عن نقاط الزاوية.
  6. حدد نقطة الزاوية التي تعطي القيمة القصوى.
    1. يتم ذلك عن طريق إيجاد قيمة الوظيفة الهدف في كل نقطة زاوية.
    2. يمكن القيام بذلك أيضًا عن طريق تحريك الخط المرتبط بوظيفة الهدف.


شاهد الفيديو: . Применение графика кривых равной громкости (شهر نوفمبر 2021).