البرمجة الخطية تبحث عن أكبر أو أصغر قيمة لدالة خطية ضمن قيود خطية. يوضح الرسم بمتغيرين المنطقة المشتركة للقيود وقيم دالة الهدف. [1]
ما الذي نحدده قبل الرسم؟
نحدد المتغيرات ودالة الهدف والقيود. المنطقة الممكنة تقاطع حلول كل القيود. تظهر المتغيرات الخطية من الدرجة الأولى، دون جداء بينها أو قوى أعلى. [1]
نختار نموذجًا تعليميًا لكميتين x و y، ونسمح في هذا المثال بأجزاء الوحدة. القيود المختارة هي x+y ≤ 8، و 2x+y ≤ 10، و x ≤ 4، مع x ≥ 0 و y ≥ 0.
نريد تعظيم Z = 3x + 2y. الأعداد مختارة للتعليم، ولا تمثل قياسات مورد حقيقي أو أسعارًا. كما أن شرط عدم السلبية هنا جزء من النموذج المختار؛ لا نفترضه لكل متغير في كل مسألة.
رسم المنطقة الممكنة
في مثالنا نرسم x+y=8 و 2x+y=10 و x=4، ثم نحتفظ بالجهات التي تحقق المتباينات في الربع الأول. تتكون منطقة مغلقة محدودة بخمس زوايا: (0,0)، و (4,0)، و (4,2)، و (2,6)، و (0,8).
لإيجاد التقاء القيدين الأولين، نطرح x+y=8 من 2x+y=10 فنحصل على x=2، ثم y=6. أما عند x=4 فيسمح القيد الثاني حتى y=2، في حين يسمح الأول حتى y=4؛ نأخذ الشرط الأشد.
توضح الطريقة البيانية التقاطع، وفي المنطقة المغلقة المحدودة غير الفارغة يمكن إيجاد قيمة مثلى للدالة الخطية عند زاوية. هذا هو النطاق الذي نستعمله هنا عند مقارنة الزوايا. [1][2]
جدول المقارنة: أين تتحقق أكبر قيمة؟
| الزاوية في المثال | التعويض في Z | القيمة |
|---|---|---|
| (0,0) | 3×0+2×0 | 0 |
| (4,0) | 3×4+2×0 | 12 |
| (4,2) | 3×4+2×2 | 16 |
| (2,6) | 3×2+2×6 | 18 |
| (0,8) | 3×0+2×8 | 16 |
أكبر القيم في الجدول 18، عند (2,6). نفحص القيود: 2+6=8، و 2×2+6=10، و 2≤4؛ وكلتا الكميتين غير سالبتين. هذه مقارنة مكتملة للمثال، وليست اختيارًا للنقطة التي تبدو أعلى في الرسم فقط.
ماذا يحدث إذا تغيرت دالة الهدف؟
نبقي القيود ونغير الهدف إلى تعظيم W = 2x + y. يفرض أحد القيود W ≤ 10. النقطتان (4,2) و (2,6) تحققان القيمة 10، وكذلك كل نقطة على القطعة الواصلة بينهما؛ مثلًا (3,4) تعطي 2×3+4=10 وتحقق سائر القيود.
عندما تقع قيمة مثلى عند زاويتين متجاورتين، تكون القطعة بينهما مثلى أيضًا في هذا النموذج الخطي. لذلك قد توجد حلول مثلى متعددة بدل نقطة منفردة. [2]
أما المنطقة الفارغة فتعني أن القيود لا تتحقق معًا. والمنطقة غير المحدودة تحتاج فحصًا للهدف؛ شكل المنطقة وحده لا يثبت أن كل دالة عليها بلا قيمة عظمى. لا نمد نتيجة المثال المحدود إلى حالات لم نفحصها.
فحص سريع للحل
راجع أن النقطة تحقق جميع القيود، ثم احسب دالة الهدف بها. تغيير الدالة قد يغير الحل دون تغيير المنطقة. وإذا كانت الكميات المطلوبة أعدادًا صحيحة، فلا تفترض أن الحل المستمر يجيب وحده عن تلك المسألة المختلفة.
المصادر ومتابعة القراءة
- Highline College: المنطقة الممكنة ودالة الهدف والحلول البيانية (يفتح في نافذة جديدة)math.libretexts.org
- LibreTexts: حدود المنطقة الممكنة وتعدد نقاط الحل الأمثل (يفتح في نافذة جديدة)math.libretexts.org
أُعدّ هذا المقال بصياغة عربية أصلية بالاستناد إلى المصادر أعلاه، وهو مدخل تمهيدي إلى الموضوع. اقرأ منهجية المحتوى وحدوده.