Skip to content

Lesson 6: Big-M, Two-Phase Methods and Special Cases

6.1 Learning Outcomes

By the end of this hour a student will be able to:

  1. Explain why \(\ge\) and \(=\) constraints need artificial variables.
  2. Apply the Big-M method and interpret its tableaus.
  3. Apply the two-phase method and know when to prefer it.
  4. Detect infeasibility, unboundedness, alternate optima and degeneracy from a tableau.
  5. Diagnose and repair a failing model.

6.2 Why Artificial Variables Are Needed

Simplex requires a starting basic feasible solution. When every constraint is \(\le\) with \(b_i \ge 0\), the slacks provide one immediately: set all real variables to zero and read \(s_i = b_i \ge 0\). The origin is feasible.

With a \(\ge\) constraint this fails. Consider \(3x_1 + x_2 \ge 6\). In standard form,

\[ 3x_1 + x_2 - s_1 = 6 \]

Setting \(x_1 = x_2 = 0\) gives \(s_1 = -6 < 0\) — not feasible. The surplus variable enters with coefficient \(-1\), so it cannot be a starting basic variable.

Similarly for \(=\): \(3x_1+x_2 = 3\) has no slack at all, so no basic variable exists in that row.

The fix. Add an artificial variable \(A_i \ge 0\) with coefficient \(+1\):

\[ 3x_1 + x_2 - s_1 + A_1 = 6, \qquad 3x_1 + x_2 + A_2 = 3 \]

Now \(A_1 = 6\) and \(A_2 = 3\) give a starting basis. But this solves a different problem — the artificials must be driven to zero before the answer means anything.

\[ \boxed{\ \textbf{Artificial variables buy a starting point at the price of having to expel them.}\ } \]

6.3 The Big-M Method

Idea. Attach a huge penalty \(M\) to each artificial variable so that the optimiser expels them automatically.

\[ \text{maximisation: } \ \max\ Z = \sum c_jx_j - M\sum A_i \]
\[ \text{minimisation: } \ \min\ Z = \sum c_jx_j + M\sum A_i \]

with \(M\) larger than any number that could otherwise arise.

The three outcomes.

At optimality Conclusion
All \(A_i = 0\) the solution is optimal for the original problem ✓
Some \(A_i > 0\) the original problem is INFEASIBLE
\(Z\) unbounded with all \(A_i = 0\) the original problem is UNBOUNDED

Handling M in the tableau

Entries in the \(z_j - c_j\) row become expressions like \(-6996\) or, symbolically, \(-7M + 4\). Two equivalent conventions:

  • Symbolic: keep \(M\) as a symbol and compare coefficients of \(M\) first, then the constants.
  • Numeric: set \(M\) to a large number (say 1000, safely above any coefficient in the problem).

This lesson uses \(M = 1000\) for readability; the symbolic form is given alongside.

6.4 Worked Big-M Example

\[ \begin{aligned} \min\ & Z = 4x_1 + x_2\\ \text{s.t. } & 3x_1 + x_2 = 3\\ & 4x_1 + 3x_2 \ge 6\\ & x_1 + 2x_2 \le 4\\ & x_1, x_2 \ge 0 \end{aligned} \]

Standard form. Convert to maximisation of \(Z' = -4x_1 - x_2\):

\[ \begin{aligned} 3x_1 + x_2 + A_1 &= 3\\ 4x_1 + 3x_2 - s_2 + A_2 &= 6\\ x_1 + 2x_2 + s_3 &= 4 \end{aligned} \]
\[ \max\ Z' = -4x_1 - x_2 + 0s_2 + 0s_3 - MA_1 - MA_2 \]

Iteration 0

Basis \(c_B\) \(x_1\) \(x_2\) \(s_2\) \(A_1\) \(A_2\) \(s_3\) RHS Ratio
\(A_1\) \(-M\) 3 1 0 1 0 0 3 \(1\) ←
\(A_2\) \(-M\) 4 3 −1 0 1 0 6 \(3/2\)
\(s_3\) 0 1 2 0 0 0 1 4 \(4\)
\(z_j-c_j\) \(-7M{+}4\) \(-4M{+}1\) \(M\) 0 0 0 \(-9M\)

With \(M = 1000\): \(z_j-c_j = (-6996,\ -3999,\ 1000,\ 0,\ 0,\ 0)\), \(Z' = -9000\).

Entering \(x_1\) (most negative). Ratios \(\{1,\ 3/2,\ 4\}\) ⟹ leaving \(A_1\). Pivot 3.

Iteration 1

Row 1 ÷ 3; then eliminate.

Basis \(c_B\) \(x_1\) \(x_2\) \(s_2\) \(A_1\) \(A_2\) \(s_3\) RHS Ratio
\(x_1\) −4 1 \(1/3\) 0 \(1/3\) 0 0 1 \(3\)
\(A_2\) \(-M\) 0 \(5/3\) −1 \(-4/3\) 1 0 2 \(6/5\) ←
\(s_3\) 0 0 \(5/3\) 0 \(-1/3\) 0 1 3 \(9/5\)
\(z_j-c_j\) 0 \(-1667\) \(1000\) \(2332\) 0 0 \(-2004\)

(Symbolically \(z_2-c_2 = -\frac53M + \frac13\).)

\(A_1\) has left the basis ✓ — one down, one to go. Entering \(x_2\), leaving \(A_2\), pivot \(5/3\).

Iteration 2

Basis \(c_B\) \(x_1\) \(x_2\) \(s_2\) \(A_1\) \(A_2\) \(s_3\) RHS Ratio
\(x_1\) −4 1 0 \(1/5\) \(3/5\) \(-1/5\) 0 \(3/5\) \(3\)
\(x_2\) −1 0 1 \(-3/5\) \(-4/5\) \(3/5\) 0 \(6/5\) —
\(s_3\) 0 0 0 1 1 −1 1 1 \(1\) ←
\(z_j-c_j\) 0 0 \(-1/5\) \(4992/5\) \(5001/5\) 0 \(-18/5\)

Both artificials are now out of the basis ✓, and \(Z' = -\frac{18}{5}\), i.e. \(Z = 3.6\).

But not yet optimal: \(z_{s_2} - c_{s_2} = -\frac15 < 0\). Entering \(s_2\), leaving \(s_3\), pivot 1.

Iteration 3

Basis \(c_B\) \(x_1\) \(x_2\) \(s_2\) \(A_1\) \(A_2\) \(s_3\) RHS
\(x_1\) −4 1 0 0 \(2/5\) 0 \(-1/5\) 2/5
\(x_2\) −1 0 1 0 \(-1/5\) 0 \(3/5\) 9/5
\(s_2\) 0 0 0 1 1 −1 1 1
\(z_j-c_j\) 0 0 0 \(4993/5\) \(1000\) \(1/5\) \(-17/5\)

All \(z_j-c_j \ge 0\) ⟹ OPTIMAL.

\[ \boxed{\ x_1^{*} = \tfrac25 = 0.4,\quad x_2^{*} = \tfrac95 = 1.8,\quad Z_{\min} = -Z'_{\max} = \tfrac{17}{5} = 3.4\ } \]

Verification against the original problem.

\[ 3(0.4)+1.8 = 1.2+1.8 = 3 = 3 \ \checkmark \ \text{(equality holds)} \]
\[ 4(0.4)+3(1.8) = 1.6+5.4 = 7.0 \ge 6 \ \checkmark \ \text{(surplus } s_2 = 1) \]
\[ 0.4+2(1.8) = 0.4+3.6 = 4.0 \le 4 \ \checkmark \ \text{(binding, } s_3 = 0) \]
\[ Z = 4(0.4)+1.8 = 1.6+1.8 = 3.4 \ \checkmark \]

Both artificials are zero, so the answer is valid for the original problem.

Note the near-miss at iteration 2. Both artificials had left, yet the solution \((0.6,\ 1.2)\) with \(Z = 3.6\) was not optimal. Expelling the artificials makes the solution feasible, not optimal — the algorithm must continue until the \(z_j-c_j\) test passes.

6.5 The Two-Phase Method

Idea. Split the work into two clean stages instead of juggling \(M\).

Phase I — find feasibility. Replace the objective by

\[ \min\ W = \sum_i A_i \qquad\left(\text{equivalently } \max\ -\sum_i A_i\right) \]

subject to the same constraints.

  • If \(W^{*} > 0\) ⟹ the original problem is INFEASIBLE. Stop.
  • If \(W^{*} = 0\) ⟹ a BFS of the original problem has been found. Proceed.

Phase II — find optimality. Drop the artificial columns, restore the original objective, recompute the \(z_j - c_j\) row, and continue simplex from the Phase I final tableau.

Big-M versus two-phase

Big-M Two-phase
Number of tableaus fewer more
Arithmetic mixes \(M\) with ordinary numbers clean numbers throughout
Numerical stability poor — huge \(M\) swamps small coefficients in floating point good
Infeasibility detection at the end at the end of Phase I — earlier
Hand calculation fine fine
Computer implementation avoided used in practice
\[ \boxed{\ \textbf{Every real solver uses two-phase (or a dual/crash start). Big-M is a teaching device.}\ } \]

Why Big-M fails numerically. With \(M = 10^{6}\) and a genuine coefficient of \(10^{-3}\), double precision (≈16 significant digits) cannot represent their sum accurately. Round-off then corrupts the \(z_j-c_j\) signs and the algorithm terminates at a wrong basis.

Phase I on the same example

\[ \min\ W = A_1 + A_2 \quad\Longleftrightarrow\quad \max\ -A_1 - A_2 \]

Iteration 0. \(c_B = (-1,-1,0)\), \(W = 3+6 = 9\). The \(z_j-c_j\) row is obtained by summing the artificial rows and negating the real-variable entries:

\[ z_j - c_j \ =\ (-7,\ -4,\ +1,\ 0,\ 0,\ 0), \qquad W = 9 \]

Entering \(x_1\), leaving \(A_1\) — the same pivots as Big-M, because the \(M\)-terms dominated there and the \(M\)-terms are the Phase I objective.

Phase I terminates at iteration 2 with \(W^{*} = 0\) and the BFS \((x_1, x_2) = (0.6, 1.2)\).

Phase II restores \(\max\ Z' = -4x_1 - x_2\), recomputes \(z_j-c_j\), finds \(z_{s_2}-c_{s_2} = -\frac15\), performs the one remaining pivot, and reaches the same optimum.

\[ \boxed{\ \text{Two-phase does the same work, but with numbers instead of } M.\ } \]

6.6 The Four Special Cases in the Tableau

Case Tableau signature Action
Infeasible some \(A_i > 0\) at optimality (or \(W^{*}>0\) in Phase I) relax a constraint
Unbounded entering column has no positive entry add the missing constraint
Alternate optima a non-basic variable has \(z_j - c_j = 0\) pivot to find the second optimum
Degenerate a basic variable equals 0 continue; watch for stalling

6.7 Solved Problems

Problem 1 — Detecting infeasibility with Big-M

Solve \(\max\ Z = 3x_1+2x_2\) s.t. \(x_1+x_2 \le 4\), \(x_1+x_2\ge 8\), \(x_1,x_2\ge0\).

Solution.

Standard form.

\[ x_1+x_2+s_1 = 4, \qquad x_1+x_2-s_2+A_1 = 8 \]
\[ \max\ Z = 3x_1+2x_2 - MA_1 \]

Iteration 0. Basis \(\{s_1, A_1\}\), \(Z = -8M\).

\[ z_j - c_j = (-M-3,\ -M-2,\ 0,\ M,\ 0) \]

Entering \(x_1\); ratios \(\frac41 = 4\) and \(\frac81 = 8\) ⟹ leaving \(s_1\), pivot 1.

Iteration 1.

Basis \(c_B\) \(x_1\) \(x_2\) \(s_1\) \(s_2\) \(A_1\) RHS
\(x_1\) 3 1 1 1 0 0 4
\(A_1\) \(-M\) 0 0 −1 −1 1 4
\(z_j-c_j\) 0 1 \(M+3\) \(M\) 0 \(12-4M\)

All \(z_j - c_j \ge 0\) (since \(M\) is large) ⟹ the algorithm STOPS.

But \(A_1 = 4 > 0\).

\[ \boxed{\ \textbf{INFEASIBLE.}\ } \]

Why, obviously. The constraints demand \(x_1+x_2 \le 4\) and \(x_1+x_2\ge8\) simultaneously — impossible since \(4 < 8\).

What the tableau tells us more precisely. The final \(Z = 12 - 4M\) contains the term \(-4M\): the "cost" of the infeasibility is 4 units of violation. Modern solvers report exactly this — the minimum total constraint violation — which points the modeller straight at the problem.

Practical response. Either the capacity 4 is wrong, or the requirement 8 is wrong. The infeasibility of 4 units tells management exactly how much extra capacity (or how much demand reduction) would be needed.

Problem 2 — Two-phase method, complete

Solve by two-phase: \(\min\ Z = 2x_1+3x_2\) s.t. \(x_1+x_2\ge5\), \(x_1+2x_2\ge6\), \(x_1,x_2\ge0\).

Solution.

Standard form.

\[ x_1+x_2-s_1+A_1 = 5, \qquad x_1+2x_2-s_2+A_2 = 6 \]

PHASE I: min W = A₁+A₂, i.e. max -A₁-A₂

Iteration 0. Basis \(\{A_1,A_2\}\), \(W = 5+6 = 11\).

\[ z_j-c_j: \quad x_1: -(1+1) = -2, \quad x_2: -(1+2) = -3, \quad s_1: +1, \quad s_2: +1 \]
Basis \(x_1\) \(x_2\) \(s_1\) \(s_2\) \(A_1\) \(A_2\) RHS Ratio
\(A_1\) 1 1 −1 0 1 0 5 5
\(A_2\) 1 2 0 −1 0 1 6 3 ←
\(z_j-c_j\) −2 −3 1 1 0 0 \(W=11\)

Entering \(x_2\); leaving \(A_2\); pivot 2.

Iteration 1. Row 2 ÷ 2: \((\frac12,\ 1,\ 0,\ -\frac12,\ 0,\ \frac12\ |\ 3)\). Row 1 ← row 1 − (new row 2): \((\frac12,\ 0,\ -1,\ \frac12,\ 1,\ -\frac12\ |\ 2)\).

Basis \(x_1\) \(x_2\) \(s_1\) \(s_2\) \(A_1\) RHS Ratio
\(A_1\) \(1/2\) 0 −1 \(1/2\) 1 2 4 ←
\(x_2\) \(1/2\) 1 0 \(-1/2\) 0 3 6
\(z_j-c_j\) \(-1/2\) 0 1 \(-1/2\) 0 \(W=2\)

Entering \(x_1\); leaving \(A_1\); pivot \(\frac12\).

Iteration 2. Row 1 ÷ \(\frac12\): \((1,\ 0,\ -2,\ 1\ |\ 4)\). Row 2 ← row 2 − \(\frac12\)(new row 1): \((0,\ 1,\ 1,\ -1\ |\ 1)\).

Basis \(x_1\) \(x_2\) \(s_1\) \(s_2\) RHS
\(x_1\) 1 0 −2 1 4
\(x_2\) 0 1 1 −1 1
\(z_j-c_j\) 0 0 0 0 \(W = \mathbf{0}\)
\[ \boxed{\ W^{*} = 0 \ \Longrightarrow\ \textbf{FEASIBLE. Proceed to Phase II.}\ } \]

Both artificials have left the basis, and \((x_1, x_2) = (4, 1)\) is a BFS of the original problem.

PHASE II: min Z = 2x₁ + 3x₂

Drop the artificial columns and restore the true objective. With \(c_B = (2, 3)\):

\[ z_{s_1} = 2(-2) + 3(1) = -1, \qquad z_{s_1}-c_{s_1} = -1 - 0 = -1 \]
\[ z_{s_2} = 2(1) + 3(-1) = -1, \qquad z_{s_2}-c_{s_2} = -1 \]
Basis \(c_B\) \(x_1\) \(x_2\) \(s_1\) \(s_2\) RHS
\(x_1\) 2 1 0 −2 1 4
\(x_2\) 3 0 1 1 −1 1
\(z_j-c_j\) 0 0 −1 −1 \(Z = 11\)

For a MINIMISATION in this form, optimality requires \(z_j - c_j \le 0\). Both are \(-1 \le 0\) ✓.

\[ \boxed{\ \textbf{OPTIMAL: } x_1^{*} = 4,\ x_2^{*} = 1,\ Z_{\min} = 2(4)+3(1) = 11\ } \]

Verification.

\[ 4+1 = 5 \ge 5 \ \checkmark \text{ (binding)}, \qquad 4+2(1) = 6 \ge 6 \ \checkmark \text{ (binding)} \]

Graphical cross-check. The corners of the feasible region are \((6,0)\) with \(Z = 12\), \((4,1)\) with \(Z = 11\), and \((0,5)\) with \(Z = 15\). Minimum is \((4,1)\), \(Z = 11\) ✓.

Problem 3 — Detecting unboundedness

Solve \(\max\ Z = 2x_1 + x_2\) s.t. \(x_1 - x_2 \le 10\), \(2x_1 - x_2 \le 40\), \(x_1,x_2\ge0\).

Solution.

Iteration 0. Basis \(\{s_1, s_2\}\).

Basis \(c_B\) \(x_1\) \(x_2\) \(s_1\) \(s_2\) RHS Ratio
\(s_1\) 0 1 −1 1 0 10 10 ←
\(s_2\) 0 2 −1 0 1 40 20
\(z_j-c_j\) −2 −1 0 0 0

Entering \(x_1\); ratios \(\{10, 20\}\); leaving \(s_1\); pivot 1.

Iteration 1. Row 2 ← row 2 − 2(row 1).

Basis \(c_B\) \(x_1\) \(x_2\) \(s_1\) \(s_2\) RHS
\(x_1\) 2 1 −1 1 0 10
\(s_2\) 0 0 1 −2 1 20
\(z_j-c_j\) 0 −3 2 0 20

Entering \(x_2\) (\(-3\)). Column entries: \((-1,\ 1)^T\). Ratio for row 2: \(20/1 = 20\). Leaving \(s_2\).

Iteration 2.

Basis \(c_B\) \(x_1\) \(x_2\) \(s_1\) \(s_2\) RHS
\(x_1\) 2 1 0 −1 1 30
\(x_2\) 1 0 1 −2 1 20
\(z_j-c_j\) 0 0 −4 3 80

Entering \(s_1\) (\(-4\)). Column entries \((-1, -2)^T\) — BOTH NEGATIVE.

\[ \boxed{\ \textbf{No positive entry in the pivot column} \ \Longrightarrow\ \textbf{UNBOUNDED.}\ } \]

The direction of unboundedness. Increasing \(s_1\) by \(t\) gives

\[ x_1 = 30 + t, \qquad x_2 = 20 + 2t, \qquad Z = 80 + 4t \ \longrightarrow\ \infty \]

Check feasibility along the ray. At \(x_1 = 30+t\), \(x_2 = 20+2t\):

\[ x_1 - x_2 = 10 - t \le 10 \ \checkmark \quad \text{for all } t \ge 0 \]
\[ 2x_1 - x_2 = 60+2t - 20-2t = 40 \le 40 \ \checkmark \quad \text{always binding} \]

Both constraints remain satisfied for every \(t \ge 0\) ✓ — genuinely unbounded.

Why it happened. Both constraints have the form (something) \(-x_2 \le\) (constant). Increasing \(x_2\) loosens both. Nothing in the model limits \(x_2\), yet \(x_2\) contributes positively to profit.

The modelling lesson. Every LP claiming unbounded profit has a missing constraint — here, no limit on the resource consumed by \(x_2\). The unbounded ray names the culprit precisely.

Problem 4 — Alternate optima found by pivoting

A final tableau for \(\max\ Z = 2x_1+4x_2\) is shown. Identify alternate optima and find the second optimal solution.

Basis \(c_B\) \(x_1\) \(x_2\) \(s_1\) \(s_2\) RHS
\(x_2\) 4 \(1/2\) 1 \(1/2\) 0 4
\(s_2\) 0 \(3/2\) 0 \(-1/2\) 1 2
\(z_j-c_j\) 0 0 2 0 16

Solution.

Diagnosis. \(x_1\) is non-basic (it is not a basis label) yet \(z_1 - c_1 = 0\).

\[ \boxed{\ \textbf{ALTERNATE OPTIMA.}\ } \]

Current optimum. \(x_1 = 0\), \(x_2 = 4\), \(Z = 4(4) = 16\) ✓.

Find the second. Bring \(x_1\) into the basis. Column \(x_1 = (\frac12,\ \frac32)^T\); ratios

\[ \frac{4}{1/2} = 8, \qquad \frac{2}{3/2} = \frac43 \ \leftarrow \text{minimum} \]

Leaving \(s_2\); pivot \(\frac32\).

Row 2 ÷ \(\frac32\): \((1,\ 0,\ -\frac13,\ \frac23\ |\ \frac43)\). Row 1 ← row 1 − \(\frac12\)(new row 2): \((0,\ 1,\ \frac12+\frac16,\ -\frac13\ |\ 4-\frac23)\) \(= (0,\ 1,\ \frac23,\ -\frac13\ |\ \frac{10}{3})\).

Basis \(c_B\) \(x_1\) \(x_2\) \(s_1\) \(s_2\) RHS
\(x_2\) 4 0 1 \(2/3\) \(-1/3\) \(10/3\)
\(x_1\) 2 1 0 \(-1/3\) \(2/3\) \(4/3\)
\(z_j-c_j\) 0 0 2 0 16
\[ \boxed{\ \text{Second optimum: } x_1 = \tfrac43,\ x_2 = \tfrac{10}{3},\ Z = 16\ } \]

Check. \(Z = 2(\frac43)+4(\frac{10}{3}) = \frac83+\frac{40}{3} = \frac{48}{3} = 16\) ✓ — identical, as required.

The complete optimal set.

\[ \vec x(\lambda) = \lambda(0,\ 4) + (1-\lambda)\left(\tfrac43,\ \tfrac{10}{3}\right), \qquad \lambda\in[0,1] \]

At \(\lambda = \frac12\): \(\vec x = (\frac23,\ \frac{11}{3})\), giving \(Z = \frac43 + \frac{44}{3} = \frac{48}{3} = 16\) ✓.

Note that \(s_2\) also has \(z_j-c_j = 0\) but is BASIC in the first tableau — that is not a signal of alternate optima. Only non-basic zeros count.

Problem 5 — Diagnosing and repairing a failing model

A production LP returns "infeasible". The model is: produce \(x_1, x_2\) with \(2x_1+3x_2 \le 100\) (machine hours), \(x_1 \ge 30\) (contract), \(x_2 \ge 25\) (contract). Diagnose and propose three repairs, quantifying each.

Solution.

Diagnosis. The two contracts consume, at minimum,

\[ 2(30) + 3(25) = 60 + 75 = \mathbf{135\ \text{machine hours}} \]

but only 100 are available.

\[ \boxed{\ \textbf{Infeasible by 35 machine hours.}\ } \]

How the simplex method reports this. Phase I terminates with \(W^{*} = 35/1 = 35\) (in units of the violated constraint), or in Big-M form an artificial variable remains at a positive value. Commercial solvers additionally report the Irreducible Infeasible Subsystem — here, exactly these three constraints, since removing any one restores feasibility.

Repair 1 — buy capacity. Increase machine hours to at least 135.

\[ \text{extra needed} = 35 \text{ hours}. \]

If overtime costs ₹200/hour, the cost is ₹7 000. Feasible if the contract penalties exceed ₹7 000.

Repair 2 — renegotiate a contract. Suppose \(x_2 \ge 25\) is relaxed to \(x_2 \ge q\). Feasibility requires

\[ 2(30) + 3q \le 100 \ \Longrightarrow\ 3q \le 40 \ \Longrightarrow\ q \le 13.33 \]

So product 2's commitment must fall from 25 to at most 13 units — a 48 % reduction.

Alternatively relax \(x_1 \ge 30\) to \(x_1 \ge p\):

\[ 2p + 75 \le 100 \ \Longrightarrow\ p \le 12.5 \ \Longrightarrow\ p \le 12 \]

— a 60 % reduction. Relaxing product 2 is the cheaper repair in units of commitment.

Repair 3 — soften the constraints (goal programming). Convert the hard contracts to soft targets with penalties, using the technique of L02 Problem 3:

\[ x_1 + d_1^{-} - d_1^{+} = 30, \qquad x_2 + d_2^{-} - d_2^{+} = 25 \]
\[ \min\ Z = p_1d_1^{-} + p_2d_2^{-} \qquad \text{s.t. } 2x_1+3x_2 \le 100 \]

where \(p_1, p_2\) are the per-unit penalties for missing each contract. This model is always feasible and tells you the least-cost way to break the promises — which is exactly the decision management actually faces.

Worked example of Repair 3. With penalties \(p_1 = ₹500\) and \(p_2 = ₹300\) per unit short:

Since product 1 costs 2 hours/unit and product 2 costs 3 hours/unit, the shortfall penalty per machine hour saved is

\[ \text{product 1: } \frac{500}{2} = ₹250/\text{hour}, \qquad \text{product 2: } \frac{300}{3} = ₹100/\text{hour} \]

Cut product 2 — it is cheaper per hour saved. Need to save 35 hours:

\[ \text{units of } x_2 \text{ to cut} = \frac{35}{3} = 11.67 \ \Longrightarrow\ x_2 = 25 - 11.67 = 13.33 \]
\[ x_1 = 30, \quad x_2 = 13.33, \quad d_2^{-} = 11.67 \]
\[ \text{Check: } 2(30)+3(13.33) = 60+40 = 100 \ \checkmark \]
\[ \boxed{\ \text{Minimum penalty} = 11.67\times₹300 = ₹3{,}500\ } \]

Compare the three repairs.

Repair Cost Notes
Buy 35 overtime hours ₹7 000 keeps both contracts intact
Goal programming (cut product 2) ₹3 500 cheapest — breaks the cheaper promise
Cut product 1 instead \(\frac{35}{2}\times500 = ₹8{,}750\) worst option
\[ \boxed{\ \textbf{Recommendation: buy overtime only if the ₹7 000 cost is below the true reputational cost of breaking the product-2 contract.}\ } \]

The general lesson. "Infeasible" is not a failure of the algorithm — it is information. It says the requirements as stated cannot all be met, and the Phase I objective quantifies by exactly how much. The right response is to model the trade-off explicitly, which is what goal programming does.

6.8 Practice Problems

  1. Set up the Big-M tableau for \(\min\ 3x_1+5x_2\) s.t. \(x_1+x_2\ge4\), \(2x_1+x_2 = 6\).
  2. Solve Problem 2 of §6 by Big-M and confirm the same answer.
  3. A Phase I ends with \(W^{*} = 3\). What do you conclude?
  4. Column entries in the pivot column are \((0, -2, -5)^T\). Diagnose. [Ans: unbounded]
  5. Why is Big-M numerically dangerous on a computer?
  6. In a minimisation tableau, state the optimality condition.
  7. A final tableau has a basic variable equal to 0 and all \(z_j-c_j > 0\). Is it optimal? [Ans: yes — optimal and degenerate]

6.9 Summary

  • \(\ge\) and \(=\) constraints leave no starting basic feasible solution, so artificial variables are added — they buy a starting point and must then be expelled.
  • Big-M: penalise artificials with a huge \(M\). At optimality, all \(A_i = 0\) ⟹ valid; any \(A_i > 0\) ⟹ INFEASIBLE.
  • Expelling the artificials gives feasibility, not optimality — continue until the \(z_j-c_j\) test passes.
  • Two-phase: Phase I minimises \(\sum A_i\) (if \(W^{*}>0\), infeasible); Phase II restores the real objective. Numerically far safer, and what real solvers use.
  • Tableau signatures: infeasible (\(A_i > 0\) / \(W^{*}>0\)), unbounded (no positive entry in the pivot column), alternate optima (a non-basic variable with \(z_j-c_j = 0\)), degenerate (a basic variable equal to 0).
  • Infeasibility is information. The Phase I objective measures the total violation, and goal programming converts hard constraints into penalised targets — always feasible, and it prices the trade-off management actually faces.

Next lesson: L07 — Duality and sensitivity analysis.

Practise now: unit1-lp-lab.html → Simplex Stepper: switch on artificial variables and watch Big-M and two-phase run side by side on the same problem.