LP Solverحلّال البرمجة الخطية

Linear programming, solved step by stepمسائل البرمجة الخطية محلولة خطوة بخطوة

Graphical methodالحل بالرسم

For problems with two variables.للمسائل اللي فيها متغيرين.

How it worksالطريقة

  1. For each constraint, find two points: set X2 = 0 for the X1-intercept, and X1 = 0 for the X2-intercept.
  2. Draw the line through them. For ≤ the feasible side is below the line (towards the origin); for ≥ it is above.
  3. The feasible region is where all constraints overlap in the first quadrant.
  4. Find the corner points. Where two lines cross, solve the two equations together.
  5. Substitute each corner into Z. The largest value is the answer for Max, the smallest for Min.
  1. لكل قيد بنلاقي نقطتين: نعوّض X2 = 0 للتقاطع مع محور X1، و X1 = 0 للتقاطع مع محور X2.
  2. بنرسم الخط بينهم. إذا القيد ≤ منطقة الحل تحت الخط (باتجاه نقطة الأصل)، وإذا ≥ فوقه.
  3. منطقة الحل هي الجزء المشترك بين كل القيود بالربع الأول.
  4. بنلاقي رؤوس المنطقة، ونقطة تقاطع خطين بنلاقيها بحل المعادلتين مع بعض.
  5. بنعوّض كل رأس بدالة الهدف: أكبر قيمة هي الحل لـ Max، وأصغر قيمة للـ Min.
If two corners give the same best value, every point on the edge between them is optimal: multiple optimal solutions.إذا رأسين أعطوا نفس أفضل قيمة، فكل النقاط على الضلع بينهم حلول مثلى، وبنقول إنه في حلول مثلى متعددة.

Simplex methodطريقة السمبلكس

Max or Min, with ≤, ≥ or = constraints (Big-M method).Max أو Min، بقيود ≤ أو ≥ أو = (طريقة Big-M).

How it worksالطريقة

  1. Make every right-hand side positive (multiply a row by −1 if needed).
  2. Move the objective terms to the left: Z − 5X1 − 4X2 = 0.
  3. Add a slack variable to each ≤ constraint: 4X1 + 2X2 + S1 = 32.
  4. Big-M: a ≥ constraint gets a surplus −S and an artificial A; an = constraint gets an artificial A. Artificials cost −M (a huge number) so they leave the solution. A Min problem is solved as Max of −Z.
  5. Entering variable: the column with the most negative value in the Z row.
  6. Leaving variable: divide RHS by the positive values of the entering column. The smallest ratio picks the row.
  7. Pivot: where they meet. Divide the leaving row by the pivot so it becomes 1.
  8. Every other value: new = old − (value in entering column × value in leaving row) ÷ pivot.
  9. Repeat until the Z row has no negative values. That table is optimal.
  1. نخلي كل الأطراف اليمنى موجبة (نضرب الصف بـ −1 إذا لزم).
  2. ننقل حدود دالة الهدف لليسار: Z − 5X1 − 4X2 = 0.
  3. نضيف متغير راكد لكل قيد ≤: 4X1 + 2X2 + S1 = 32.
  4. Big-M: القيد ≥ بياخذ متغير فائض −S ومتغير اصطناعي A، وقيد = بياخذ متغير اصطناعي A. الاصطناعي إله −M (رقم كبير جداً) عشان يطلع من الحل. ومسألة Min بنحلها كـ Max لـ −Z.
  5. المتغير الداخل: العمود اللي فيه أكبر قيمة سالبة بصف Z.
  6. المتغير الخارج: نقسم RHS على قيم العمود الداخل الموجبة، وأصغر ناتج بيحدد الصف.
  7. العنصر المحوري: تقاطع العمود الداخل مع الصف الخارج. نقسم الصف الخارج عليه عشان يصير 1.
  8. باقي القيم: القيمة الجديدة = القيمة القديمة − (المقابل في عمود الداخل × المقابل في صف الخارج) ÷ العنصر المحوري.
  9. نكرر لحد ما ما يضل ولا قيمة سالبة بصف Z، وهاد هو الجدول الأمثل.

Standard formالصيغة القياسية

Rewrite the constraints so they all point the same way.ترتيب القيود عشان يكونوا كلهم بنفس الاتجاه.

Rulesالقواعد

  1. Max objective: every constraint must be ≤. Min objective: every constraint must be ≥.
  2. To flip a constraint's direction, multiply the whole constraint by −1.
  3. An equality becomes two constraints, one ≤ and one ≥; multiply one of them by −1 so both point the same way.
  1. إذا الهدف Max لازم كل القيود تكون ≤، وإذا Min لازم تكون ≥.
  2. لقلب اتجاه قيد بنضربه كامل بـ −1.
  3. قيد المساواة بنقسمه لقيدين، واحد ≤ وواحد ≥، وبنضرب واحد منهم بـ −1 عشان يصيروا بنفس الاتجاه.

Dual modelالنموذج المقابل

Build the dual of any linear program.كتابة النموذج المقابل لأي مسألة.

How it worksالطريقة

  1. Write the primal in standard form.
  2. The dual has one variable (Y) for each constraint.
  3. The right-hand sides become the coefficients of the dual objective W.
  4. A Max primal gives a Min dual with ≥ constraints, and a Min primal gives a Max dual with ≤ constraints.
  5. Columns become rows: each X gives one dual constraint, and the Z coefficients become its right-hand side.
  6. All dual variables are Y ≥ 0.
  1. نكتب المسألة الأصلية بالصيغة القياسية.
  2. عدد متغيرات المقابل (Y) = عدد القيود.
  3. أرقام الطرف الأيمن بتصير معاملات دالة الهدف W.
  4. إذا الأصلية Max بتصير المقابلة Min وقيودها ≥، وإذا Min بتصير Max وقيودها ≤.
  5. الأعمدة بتصير صفوف: كل X بيعطي قيد، ومعاملات Z بتصير الطرف الأيمن.
  6. متغيرات المقابل Y ≥ 0.