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

طريقة Simplex: الخطوات والـ Slack Variables والـ Tableau

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

طريقة الـ simplex بتحل LP بمتغيرات كتير بالانتقال بين نقط الأركان. هتتعلم الـ slack وقواعد الـ pivot column وrow واختبار الـ optimality.

طريقة الـ simplex بتحل مسائل الـ linear programming اللي فيها أكتر من متغيرين بالانتقال من ركن في الـ feasible region لركن مجاور أحسن لحد ما يبقى مفيش تحسن. أول حاجة اكتب المسألة في الـ standard form: في مسألة maximize بقيود <= ضيف slack variable لكل قيد علشان يبقى معادلة، وأعد كتابة الهدف Z - c1 x1 - c2 x2 = 0. الـ slack variables بتكوّن الحل الأساسي الابتدائي والمتغيرات الأصلية عند صفر.

كل iteration في الـ tableau ليها 3 خطوات. واحد، اختار الـ pivot column: العمود اللي فيه أكتر معامل سالب في صف الهدف (الـ entering variable). لو مفيش معامل سالب فالحل الحالي optimal. اتنين، اختار الـ pivot row بـ minimum ratio test: اقسم كل RHS على القيمة الموجبة في عمود الـ pivot وخد أصغر نسبة (الـ leaving variable). لو مفيش قيمة موجبة تبقى المسألة unbounded. تلاتة، اعمل الـ pivot: اقسم صف الـ pivot على عنصر الـ pivot واستخدم row operations علشان باقي عناصر العمود تبقى أصفار.

اقرا الإجابة من آخر tableau. المتغيرات الـ basic بتاخد القيمة في عمود الـ RHS والـ non-basic بصفر. والخانة اللي فوق يمين هي القيمة المثلى لـ Z. في مسائل minimize ممكن تعمل maximize لسالب الهدف، أو تستخدم Big M أو two-phase لما يبقى فيه قيود >= أو = وبتحتاج artificial variables. وتعادل في الـ minimum ratio بيدّي حل degenerate.

أهم النقاط

  • ضيف slack علشان تحوّل <= لمعادلات.
  • Entering variable: أكتر قيمة سالبة في صف الهدف.
  • Leaving variable: أقل نسبة (RHS / قيمة موجبة في عمود الـ pivot).
  • وقّف لما صف الهدف مفيهوش سالب.
  • Big M أو two-phase للقيود >= و=.

مثال محلول

Maximize Z = 3x + 2y بشروط x + y <= 4 وx + 3y <= 6. ضيف slacks s1 وs2. الصفوف الابتدائية: s1: x + y + s1 = 4؛ s2: x + 3y + s2 = 6؛ Z - 3x - 2y = 0. الـ entering هو x (الأكثر سلبية، -3). النسب: 4/1 = 4 و6/1 = 6 فـ s1 هي اللي بتخرج. بعد الـ pivot، x = 4 وs2 = 2 وZ = 12 وصف الهدف بيبقى y: +1 وs1: +3 كلهم غير سالبين. الحل الأمثل Z = 12 عند x = 4 وy = 0.

أسئلة شائعة

يعني إيه slack variable؟

متغير غير سالب بنضيفه لقيد <= علشان يبقى معادلة، وبيقيس الكمية الغير مستخدمة من المورد.

إزاي أعرف إن الـ simplex tableau بقى optimal؟

في maximize لما كل عناصر صف الهدف تبقى صفر أو موجبة.