الأوبريشنز ريسيرش

البرمجة الخطية: الـ Formulation وطريقة الرسم Graphical

الأوبريشنز ريسيرش شروحات ومراجعات

الـ linear programming بتختار أحسن قيمة لدالة هدف خطية تحت قيود خطية. هتتعلم تعرّف المتغيرات وتكتب القيود وترسم الـ feasible region وتجرب نقط الأركان.

مسألة الـ linear programming (LP) بتعمل maximize أو minimize لدالة هدف خطية بشروط قيود خطية وعدم سالبية. علشان تكتبها، أول حاجة عرّف الـ decision variables (مثلًا x = وحدات المنتج A وy = وحدات المنتج B). بعدين اكتب الهدف زي maximize Z = 40x + 30y للربح. بعدين اكتب قيد لكل مورد محدود زي 2x + y <= 100 لساعات الماكينة، وضيف x >= 0 وy >= 0.

الطريقة الـ graphical بتنفع لمتغيرين. ارسم كل قيد كخط، وظلّل الجهة اللي بتحققه، وتقاطع كل الجهات المظللة هو الـ feasible region. لو الـ region مش فاضية والهدف محدود، الحل الأمثل دايمًا عند corner point (extreme point). فاحسب كل ركن بحل أزواج خطوط القيود، واحسب Z عند كل ركن، واختار الأكبر (maximize) أو الأصغر (minimize).

حالات خاصة بتيجي في الامتحان. لو خط الهدف موازي لقيد binding يبقى فيه حلول مثلى متعددة على حرف كامل. لو الـ region مفتوحة في اتجاه التحسن تبقى المسألة unbounded. ولو القيود متعارضة ومفيش منطقة مشتركة تبقى infeasible. القيد اللي بيلمس النقطة المثلى هو binding وslack بتاعه صفر، والباقي ليهم slack أو surplus متبقي.

أهم النقاط

  • عرّف المتغيرات والهدف والقيود وعدم السالبية.
  • الـ feasible region = تقاطع كل القيود.
  • الحل الأمثل عند corner point.
  • هدف موازي بيدّي حلول مثلى متعددة.
  • الـ unbounded والـ infeasible هما الحالات الخاصة.

مثال محلول

Maximize Z = 40x + 30y بشروط 2x + y <= 100 وx + y <= 70 وx, y >= 0. الأركان: (0, 0) وZ = 0؛ (50, 0) وZ = 2000؛ (0, 70) وZ = 2100؛ وتقاطع 2x + y = 100 مع x + y = 70 بيدّي x = 30 وy = 40 وZ = 1200 + 1200 = 2400. يبقى الأعلى Z = 2400 عند (30, 40).

أسئلة شائعة

ليه الحل الأمثل عند corner point؟

لأن الهدف خطي فقيمته بتتغير بانتظام جوّه المنطقة، فأحسن قيمة بتتحقق عند extreme point.

يعني إيه LP مش feasible؟

يعني القيود بتتناقض مع بعض فمفيش نقطة بتحقق كلها.