Skip to content

Lesson 5: The Simplex Method II: The Tableau Algorithm

5.1 Learning Outcomes

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

  1. Set up the initial simplex tableau from an LP.
  2. Execute pivot operations accurately and efficiently.
  3. Read the optimal solution, slack values and shadow prices from the final tableau.
  4. Verify a solution independently.
  5. Recognise alternate optima from the final tableau.

5.2 Setting Up the Tableau

The recipe.

1. Convert to standard form (L02): all constraints '=', all b_i >= 0
2. Identify an initial basis -- the slack variables, if all constraints were <=
3. Build the table:  Basis | c_B | all variable columns | RHS
4. Compute the z_j - c_j row

Layout convention used throughout this course.

\(c_j \to\) \(c_1\) \(c_2\) \(\cdots\) \(c_n\)
Basis \(c_B\) \(x_1\) \(x_2\) \(\cdots\) \(x_n\) RHS
\(x_{B_1}\) \(c_{B_1}\) \(a_{11}\) \(a_{12}\) \(a_{1n}\) \(b_1\)
\(\vdots\)
\(x_{B_m}\) \(c_{B_m}\) \(a_{m1}\) \(a_{m2}\) \(a_{mn}\) \(b_m\)
\(z_j - c_j\) \(\Delta_1\) \(\Delta_2\) \(\Delta_n\) \(Z\)

5.3 The Pivot Operation, Step by Step

Given pivot element p = a[r][k]  (row r, column k):

1.  New pivot row  =  old pivot row / p
2.  For every other row i:
        new row i  =  old row i  -  a[i][k] x (new pivot row)
3.  Replace the basis label in row r by x_k, and c_B by c_k
4.  Recompute z_j - c_j

Three checks after every pivot — do these every time and errors become rare:

  1. The pivot column now reads \((0,\ldots,0,1,0,\ldots,0)^T\) with the 1 in the pivot row.
  2. All RHS values are \(\ge 0\).
  3. \(Z\) has improved (or stayed the same, under degeneracy).

Work in fractions, not decimals. Simplex tableaus produce values like \(2/3\) and \(5/14\); decimal rounding accumulates and eventually corrupts the \(z_j-c_j\) signs, causing wrong termination.

5.4 Worked Example — Complete Trace

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

(This is the problem solved graphically in L03; the optimum is \((3, 1.5)\) with \(Z = 21\).)

Standard form.

\[ 6x_1 + 4x_2 + s_1 = 24, \qquad x_1 + 2x_2 + s_2 = 6 \]
\[ \max\ Z = 5x_1 + 4x_2 + 0s_1 + 0s_2 \]

Iteration 0

Basis \(c_B\) \(x_1\) (5) \(x_2\) (4) \(s_1\) (0) \(s_2\) (0) RHS Ratio
\(s_1\) 0 6 4 1 0 24 \(24/6 = 4\) ←
\(s_2\) 0 1 2 0 1 6 \(6/1 = 6\)
\(z_j-c_j\) −5 ↑ −4 0 0 0

Reading it. Basis \(\{s_1, s_2\}\), so \(x_1 = x_2 = 0\) — this is the origin, \(Z = 0\).

Since \(c_B = (0,0)\), every \(z_j = 0\) and \(z_j - c_j = -c_j\).

Entering: \(x_1\) (most negative, \(-5\)). Ratios: \(\{4, 6\}\); minimum is 4 in row 1. Leaving: \(s_1\). Pivot = 6.

Iteration 1

Divide row 1 by 6; then row 2 ← row 2 − 1×(new row 1).

Basis \(c_B\) \(x_1\) \(x_2\) \(s_1\) \(s_2\) RHS Ratio
\(x_1\) 5 1 \(2/3\) \(1/6\) 0 4 \(4 \div \frac23 = 6\)
\(s_2\) 0 0 \(4/3\) \(-1/6\) 1 2 \(2 \div \frac43 = 3/2\) ←
\(z_j-c_j\) 0 \(-2/3\) ↑ \(5/6\) 0 20

Reading it. \(x_1 = 4\), \(s_2 = 2\), \(Z = 20\) — the corner \((4, 0)\) from L03 ✓.

Check the \(z_j-c_j\) row: \(z_2 = 5(\frac23)+0(\frac43) = \frac{10}{3}\), so \(z_2-c_2 = \frac{10}{3}-4 = -\frac23\) ✓.

Not optimal (\(-2/3 < 0\)). Entering: \(x_2\). Leaving: \(s_2\). Pivot = \(4/3\).

Iteration 2

Row 2 ← row 2 ÷ \(\frac43\), giving \((0,\ 1,\ -\frac18,\ \frac34,\ \frac32)\). Row 1 ← row 1 − \(\frac23\)×(new row 2).

Row 1 detail: \(s_1\): \(\frac16 - \frac23(-\frac18) = \frac16+\frac{1}{12} = \frac14\); \(s_2\): \(0 - \frac23(\frac34) = -\frac12\); RHS: \(4 - \frac23(\frac32) = 3\).

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

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

\[ \boxed{\ x_1^{*} = 3,\quad x_2^{*} = \tfrac32,\quad Z^{*} = 21\ } \]

Exactly matching the graphical answer of L03 ✓.

5.5 Reading the Final Tableau

The final tableau contains far more than the answer.

The optimal solution

Basic variables take their RHS values; non-basic variables are zero:

\[ x_1 = 3, \quad x_2 = \tfrac32, \quad s_1 = 0, \quad s_2 = 0 \]

Both slacks are zero ⟹ both constraints are binding, so both resources are fully consumed.

Shadow prices (dual values)

\[ \boxed{\ \text{Shadow price of constraint } i \ =\ (z_j - c_j) \text{ in the column of slack } s_i\ } \]
\[ y_1 = \tfrac34 = 0.75, \qquad y_2 = \tfrac12 = 0.5 \]

Interpretation. One additional unit of resource 1 raises the optimum by ₹0.75; one additional unit of resource 2 raises it by ₹0.50.

Verification. Change \(b_1\) from 24 to 25 and re-solve: the new intersection of \(6x_1+4x_2 = 25\) and \(x_1+2x_2 = 6\) is \(x_1 = 13/4\), \(x_2 = 11/8\), giving

\[ Z = 5\left(\tfrac{13}{4}\right)+4\left(\tfrac{11}{8}\right) = \tfrac{65}{4}+\tfrac{11}{2} = 16.25 + 5.5 = 21.75 = 21 + 0.75 \ \checkmark \]

The shadow price is exact. This tells management the maximum they should pay for an extra unit of each resource — one of the most commercially valuable outputs of an LP.

The dual solution

The shadow prices \((y_1, y_2) = (0.75, 0.5)\) are the optimal solution of the dual problem (L07). Note

\[ 24y_1 + 6y_2 = 24(0.75) + 6(0.5) = 18 + 3 = 21 = Z^{*} \ \checkmark \]

— strong duality, verified numerically.

Detecting alternate optima

\[ \boxed{\ \textbf{A \emph{non-basic} variable with } z_j - c_j = 0 \textbf{ at optimality } \Longrightarrow \textbf{ alternate optima.}\ } \]

Here \(s_1\) and \(s_2\) have \(z_j-c_j = \frac34, \frac12 > 0\) — both strictly positive — so this optimum is unique, agreeing with L03's slope analysis.

5.6 Solved Problems

Problem 1 — Full simplex on the furniture problem

Solve \(\max\ Z = 450x_1+300x_2\) s.t. \(5x_1+3x_2\le120\), \(2x_1+4x_2\le90\), \(x_1,x_2\ge0\) by simplex, and extract the shadow prices.

Solution.

Standard form. \(5x_1+3x_2+s_1 = 120\), \(2x_1+4x_2+s_2 = 90\).

Iteration 0.

Basis \(c_B\) \(x_1\) (450) \(x_2\) (300) \(s_1\) \(s_2\) RHS Ratio
\(s_1\) 0 5 3 1 0 120 \(24\) ←
\(s_2\) 0 2 4 0 1 90 \(45\)
\(z_j-c_j\) −450 −300 0 0 0

Entering \(x_1\); ratios \(120/5 = 24\) and \(90/2 = 45\); leaving \(s_1\); pivot 5.

Iteration 1. Row 1 ÷ 5; row 2 ← row 2 − 2(new row 1).

Basis \(c_B\) \(x_1\) \(x_2\) \(s_1\) \(s_2\) RHS Ratio
\(x_1\) 450 1 \(3/5\) \(1/5\) 0 24 \(40\)
\(s_2\) 0 0 \(14/5\) \(-2/5\) 1 42 \(15\) ←
\(z_j-c_j\) 0 −30 90 0 10 800

Check: \(z_2 = 450(\frac35) = 270\), so \(z_2-c_2 = 270-300 = -30\) ✓.

This is the corner \((24, 0)\) with \(Z = 10{,}800\) ✓ (matching L03's table).

Entering \(x_2\); ratios \(24 \div \frac35 = 40\) and \(42\div\frac{14}{5} = 15\); leaving \(s_2\); pivot \(14/5\).

Iteration 2. Row 2 ÷ \(\frac{14}{5}\) gives \((0,\ 1,\ -\frac17,\ \frac{5}{14},\ 15)\). Row 1 ← row 1 − \(\frac35\)(new row 2): \(s_1\): \(\frac15 - \frac35(-\frac17) = \frac15+\frac{3}{35} = \frac{10}{35} = \frac27\); \(s_2\): \(0 - \frac35\cdot\frac{5}{14} = -\frac{3}{14}\); RHS: \(24 - \frac35(15) = 15\).

Basis \(c_B\) \(x_1\) \(x_2\) \(s_1\) \(s_2\) RHS
\(x_1\) 450 1 0 \(2/7\) \(-3/14\) 15
\(x_2\) 300 0 1 \(-1/7\) \(5/14\) 15
\(z_j-c_j\) 0 0 \(600/7\) \(75/7\) 11 250

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

\[ \boxed{\ x_1^{*} = 15 \text{ tables},\ x_2^{*} = 15 \text{ chairs},\ Z^{*} = ₹11{,}250\ } \]

Shadow prices.

\[ y_1 = \frac{600}{7} = ₹85.71 \ \text{per carpentry hour}, \qquad y_2 = \frac{75}{7} = ₹10.71 \ \text{per finishing hour} \]

Management interpretation. Carpentry hours are worth 8× more than finishing hours at the margin. If overtime carpentry can be bought for less than ₹85.71/hour, buy it; if finishing overtime costs more than ₹10.71/hour, do not.

Duality check. \(120(600/7) + 90(75/7) = \frac{72000+6750}{7} = \frac{78750}{7} = 11{,}250 = Z^{*}\) ✓.

Iteration count. 2 pivots for a 2-constraint problem — consistent with the \(2m\)–\(3m\) rule of L04.

Problem 2 — A three-variable problem

Solve \(\max\ Z = 3x_1+5x_2+4x_3\) s.t. \(2x_1+3x_2\le8\), \(2x_2+5x_3\le10\), \(3x_1+2x_2+4x_3\le15\).

Solution.

Iteration 0. Basis \(\{s_1,s_2,s_3\}\), \(Z=0\); \(z_j-c_j = (-3,-5,-4,0,0,0)\).

Entering \(x_2\) (most negative, \(-5\)). Column \(x_2 = (3, 2, 2)^T\); ratios \(\frac83 = 2.67\), \(\frac{10}{2}=5\), \(\frac{15}{2}=7.5\). Minimum in row 1 ⟹ \(s_1\) leaves, pivot 3.

Iteration 1. Row 1 ÷ 3: \((\frac23,\ 1,\ 0,\ \frac13,\ 0,\ 0\ |\ \frac83)\).

Basis \(c_B\) \(x_1\) \(x_2\) \(x_3\) \(s_1\) \(s_2\) \(s_3\) RHS Ratio
\(x_2\) 5 \(2/3\) 1 0 \(1/3\) 0 0 \(8/3\) —
\(s_2\) 0 \(-4/3\) 0 5 \(-2/3\) 1 0 \(14/3\) \(14/15\) ←
\(s_3\) 0 \(5/3\) 0 4 \(-2/3\) 0 1 \(29/3\) \(29/12\)
\(z_j-c_j\) \(1/3\) 0 −4 \(5/3\) 0 0 \(40/3\)

Entering \(x_3\); minimum ratio \(14/15\) in row 2 ⟹ \(s_2\) leaves, pivot 5.

Iteration 2. Row 2 ÷ 5: \((-\frac{4}{15},\ 0,\ 1,\ -\frac{2}{15},\ \frac15,\ 0\ |\ \frac{14}{15})\). Row 3 ← row 3 − 4(new row 2).

Basis \(c_B\) \(x_1\) \(x_2\) \(x_3\) \(s_1\) \(s_2\) \(s_3\) RHS
\(x_2\) 5 \(2/3\) 1 0 \(1/3\) 0 0 \(8/3\)
\(x_3\) 4 \(-4/15\) 0 1 \(-2/15\) \(1/5\) 0 \(14/15\)
\(s_3\) 0 \(41/15\) 0 0 \(-2/15\) \(-4/5\) 1 \(89/15\)
\(z_j-c_j\) \(-11/15\) 0 0 \(17/15\) \(4/5\) 0 \(256/15\)

Check \(z_1-c_1\): \(z_1 = 5(\frac23)+4(-\frac{4}{15})+0 = \frac{10}{3}-\frac{16}{15} = \frac{50-16}{15} = \frac{34}{15}\), so \(z_1-c_1 = \frac{34}{15}-3 = -\frac{11}{15}\) ✓.

Not optimal. Entering \(x_1\); ratios: row 1 \(\frac{8/3}{2/3} = 4\); row 2 has a negative entry (skip); row 3 \(\frac{89/15}{41/15} = \frac{89}{41} \approx 2.17\) ← minimum. Leaving \(s_3\).

Iteration 3. Pivot on \(\frac{41}{15}\). Row 3 ÷ \(\frac{41}{15}\); then eliminate.

Basis \(c_B\) \(x_1\) \(x_2\) \(x_3\) \(s_1\) \(s_2\) \(s_3\) RHS
\(x_2\) 5 0 1 0 \(15/41\) \(8/41\) \(-10/41\) \(50/41\)
\(x_3\) 4 0 0 1 \(-6/41\) \(5/41\) \(4/41\) \(62/41\)
\(x_1\) 3 1 0 0 \(-2/41\) \(-12/41\) \(15/41\) \(89/41\)
\(z_j-c_j\) 0 0 0 \(45/41\) \(24/41\) \(11/41\) \(765/41\)

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

\[ \boxed{\ x_1 = \tfrac{89}{41} = 2.171,\ \ x_2 = \tfrac{50}{41} = 1.220,\ \ x_3 = \tfrac{62}{41} = 1.512,\ \ Z^{*} = \tfrac{765}{41} = 18.659\ } \]

Independent verification. Substitute into the original constraints:

\[ 2(2.171)+3(1.220) = 4.342+3.659 = 8.00 \le 8 \ \checkmark \ \text{(binding)} \]
\[ 2(1.220)+5(1.512) = 2.439+7.561 = 10.00 \le 10 \ \checkmark \ \text{(binding)} \]
\[ 3(2.171)+2(1.220)+4(1.512) = 6.512+2.439+6.049 = 15.00 \le 15 \ \checkmark \ \text{(binding)} \]

All three binding — as expected with 3 constraints and 3 variables at a non-degenerate optimum.

\[ Z = 3(2.171)+5(1.220)+4(1.512) = 6.512+6.098+6.049 = 18.659 \ \checkmark \]

Problem 3 — Recognising alternate optima in the tableau

A final tableau shows \(z_j - c_j = (0, 0, 0, 5/2, 0)\) where columns 1 and 2 are basic and columns 3, 4, 5 are non-basic. What do you conclude, and how do you find the second optimum?

Solution.

Diagnosis. Columns 3 and 5 are non-basic yet have \(z_j - c_j = 0\).

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

Why. Bringing \(x_3\) (or \(x_5\)) into the basis changes \(Z\) by \(-(z_j-c_j)\cdot\theta = 0\) — the objective is unchanged. So a different corner achieves the same optimal value.

Finding the second optimum. Perform one more pivot with \(x_3\) entering:

  1. Apply the minimum-ratio test to column 3 to find the leaving variable.
  2. Pivot as usual.
  3. The new tableau has the same \(Z\) but a different basic solution — the second optimal corner.

Describing all optima. With optimal corners \(\vec x^{(1)}\) and \(\vec x^{(2)}\), every point

\[ \vec x(\lambda) = \lambda\vec x^{(1)} + (1-\lambda)\vec x^{(2)}, \qquad \lambda\in[0,1] \]

is optimal, by the linearity argument of L03, Problem 3.

A caution. If the minimum-ratio test on column 3 gives no positive entries, then \(x_3\) can increase without limit at constant \(Z\) — the optimal set is an unbounded ray, not a bounded edge. The objective is still bounded; only the optimal set is infinite in extent.

Why report alternate optima. They give the decision-maker freedom to satisfy criteria the model omitted — supplier relationships, workforce stability, ease of implementation — at zero cost. A report that hides them gives away that freedom.

Problem 4 — Degeneracy in action

Solve \(\max\ Z = 3x_1+9x_2\) s.t. \(x_1+4x_2\le8\), \(x_1+2x_2\le4\), \(x_1,x_2\ge0\), noting the degeneracy.

Solution.

Iteration 0.

Basis \(c_B\) \(x_1\) (3) \(x_2\) (9) \(s_1\) \(s_2\) RHS Ratio
\(s_1\) 0 1 4 1 0 8 \(8/4 = 2\) ←
\(s_2\) 0 1 2 0 1 4 \(4/2 = 2\) ←
\(z_j-c_j\) −3 −9 0 0 0

A TIE in the minimum ratio (\(2 = 2\)) ⟹ degeneracy will occur.

Take row 1 (arbitrary choice); \(s_1\) leaves, pivot 4.

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

Basis \(c_B\) \(x_1\) \(x_2\) \(s_1\) \(s_2\) RHS
\(x_2\) 9 \(1/4\) 1 \(1/4\) 0 2
\(s_2\) 0 \(1/2\) 0 \(-1/2\) 1 0 ← degenerate
\(z_j-c_j\) \(-3/4\) 0 \(9/4\) 0 18

\(s_2 = 0\) while basic ⟹ DEGENERATE BFS.

Not optimal (\(z_1-c_1 = -\frac34\)). Entering \(x_1\); ratios: row 1 \(2\div\frac14 = 8\); row 2 \(0\div\frac12 = \mathbf{0}\) ← minimum. Leaving \(s_2\), pivot \(\frac12\).

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

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

OPTIMAL. \(Z = 18\) — unchanged from iteration 1.

\[ \boxed{\ x_1^{*} = 0,\quad x_2^{*} = 2,\quad Z^{*} = 18\ } \]

What happened — a degenerate pivot. The ratio was \(\theta = 0\), so the entering variable came in at value zero. The basis changed, but the point did not move and \(Z\) did not improve. This is a stalling step.

Geometrically. Three lines pass through \((0,2)\): \(x_1+4x_2 = 8\), \(x_1+2x_2 = 4\) and \(x_1 = 0\). With three constraints meeting at a corner in 2-D, the corner is over-determined and corresponds to multiple bases — exactly what degeneracy means.

Why cycling is the theoretical risk. If a chain of such zero-improvement pivots returned to a previously seen basis, the algorithm would loop forever. Here it terminated after one degenerate pivot; Bland's rule (L04) guarantees this in general.

Practical note. Degeneracy is very common — every transportation problem with a degenerate basic solution (L09) exhibits it — but harmless. Recognise it, do not fear it.

Problem 5 — Using shadow prices for a business decision

From the furniture problem's optimal tableau, \(y_1 = ₹85.71\) per carpentry hour and \(y_2 = ₹10.71\) per finishing hour. A supplier offers 10 extra carpentry hours for ₹700 total. Should the firm accept? What about 20 extra finishing hours for ₹150?

Solution.

Offer 1 — carpentry.

\[ \text{Value gained} = 10 \times ₹85.71 = ₹857.14 \]
\[ \text{Cost} = ₹700 \qquad\Longrightarrow\qquad \textbf{Net gain} = ₹157.14 \]
\[ \boxed{\textbf{ACCEPT}} \]

But check the validity range. Shadow prices hold only while the basis stays optimal. From the final tableau, the \(s_1\) column is \((\frac27,\ -\frac17)^T\). Increasing \(b_1\) by \(\Delta\) changes the basic variables to

\[ x_1 = 15 + \tfrac27\Delta, \qquad x_2 = 15 - \tfrac17\Delta \]

Feasibility requires \(x_2 \ge 0\):

\[ 15 - \tfrac{\Delta}{7} \ge 0 \ \Longrightarrow\ \Delta \le 105 \]

\(\Delta = 10\) is well within range ✓, so the ₹85.71 rate applies fully.

Confirming: new plan \(x_1 = 15+\frac{20}{7} = 17.857\), \(x_2 = 15-\frac{10}{7} = 13.571\), giving

\[ Z = 450(17.857)+300(13.571) = 8035.7 + 4071.4 = ₹12{,}107.1 = 11{,}250 + 857.14 \ \checkmark \]

Offer 2 — finishing.

\[ \text{Value gained} = 20\times₹10.71 = ₹214.29 \]
\[ \text{Cost} = ₹150 \qquad\Longrightarrow\qquad \textbf{Net gain} = ₹64.29 \]
\[ \boxed{\textbf{ACCEPT}} \]

Range check. The \(s_2\) column is \((-\frac{3}{14},\ \frac{5}{14})^T\). Increasing \(b_2\) by \(\Delta\):

\[ x_1 = 15 - \tfrac{3}{14}\Delta \ge 0 \ \Longrightarrow\ \Delta \le 70 \]

\(\Delta = 20\) is within range ✓.

A crucial caveat if both offers are accepted together. Shadow prices are marginal rates valid for one-at-a-time changes. Simultaneous changes require the 100 % rule:

\[ \frac{10}{105} + \frac{20}{70} = 0.095 + 0.286 = 0.381 \ \le\ 1 \]

Since the fractions sum to less than 1, the basis remains optimal and both shadow prices remain valid, so the combined gain of ₹157.14 + ₹64.29 = ₹221.43 is correct.

\[ \boxed{\ \textbf{Accept both. Combined net gain ₹221.43 — verified by the 100 \% rule.}\ } \]

This is the kind of concrete, defensible recommendation that makes LP valuable to management, and it comes entirely from the final tableau at no extra computational cost.

5.7 Practice Problems

  1. Solve by simplex: \(\max\ 4x_1+3x_2\) s.t. \(2x_1+x_2\le10\), \(x_1+3x_2\le15\). [Ans: \(x_1=3,x_2=4\), \(Z=24\)]
  2. From the L05 example's final tableau, what is the shadow price of constraint 2? [Ans: 1/2]
  3. Perform one pivot on: pivot element 3 in row 2, column 1, with row 2 \(= (3, 6, 1, 0 \mid 9)\).
  4. A final tableau has \(z_j-c_j = (0,0,4,0)\) with column 4 non-basic. Interpret.
  5. Verify the duality check \(\vec b^{T}\vec y = Z^{*}\) for Problem 1 of §5.
  6. Solve \(\max\ 2x_1+3x_2\) s.t. \(x_1+x_2\le4\), \(x_1+3x_2\le6\) and identify any degeneracy.
  7. If a shadow price is 0, what does that tell you about the constraint?

5.8 Summary

  • Build the tableau from standard form with the slacks as the initial basis; work in fractions.
  • Pivot: divide the pivot row by the pivot element, then eliminate the pivot column from every other row. Check the unit column, non-negative RHS and improved \(Z\) each time.
  • Read from the final tableau: optimal values (basic RHS), slacks (zero ⟹ binding), and shadow prices in the slack columns' \(z_j-c_j\) entries.
  • Shadow price = the marginal value of one extra unit of a resource; it is exactly the dual variable, and \(\vec b^T\vec y = Z^{*}\) (strong duality).
  • A non-basic variable with \(z_j-c_j = 0\) at optimality signals alternate optima — always report them.
  • Degeneracy (a basic variable equal to zero, arising from a tie in the ratio test) causes a \(\theta = 0\) pivot that changes the basis but not the solution. Common and harmless in practice.
  • Shadow prices are valid only within a range; simultaneous changes are checked by the 100 % rule (the fractions of the allowable ranges must sum to at most 1).

Next lesson: L06 — Big-M and two-phase methods, and the special cases.

Practise now: unit1-lp-lab.html → Simplex Stepper: enter any LP and step through the tableaus one pivot at a time, with the entering/leaving choices and ratios highlighted.