Linear Programming: Simplex and Duality
CSIR NET operations research: LP formulation, basic feasible solutions, the simplex method, Big-M and two-phase, duality theorems and complementary slackness.
- 23 min
On this page · 14 sections
Prerequisites
- Rank, Determinants and Systems of Linear Equations: a basic solution is a solution of \( Bx_B = b \) for an invertible \( m \times m \) submatrix \( B \); rank and invertibility do the work.
- Vector Spaces and Linear Maps: linear independence of the columns of \( A \) decides which variable sets can be a basis.
- Gauss Elimination and Gauss-Seidel: a simplex pivot is one Gauss-Jordan elimination step on a chosen column.
- The chapter map is on Reliability and Operations Research.
The Hook: Two Products, Three Machines
Formulation and Standard Form
A linear programming problem (LPP) optimises a linear function subject to linear equality and inequality constraints. The canonical forms are
$$\text{(P)}\quad \max\ c^T x \ \ \text{s.t.}\ \ Ax \le b,\ x \ge 0; \qquad \text{standard form:}\quad \max\ c^T x \ \ \text{s.t.}\ \ Ax = b,\ x \ge 0,\ b \ge 0.$$Conversions:
| Feature | Conversion |
|---|---|
| \( \le \) constraint | add a slack \( s \ge 0 \): \( a^T x + s = b \) |
| \( \ge \) constraint | subtract a surplus \( s \ge 0 \) (and later add an artificial variable) |
| \( b_i < 0 \) | multiply the row by \( -1 \) (flips \( \le \) and \( \ge \)) |
| unrestricted \( x_j \) | write \( x_j = x_j^+ - x_j^- \) with \( x_j^\pm \ge 0 \) |
| \( \min c^T x \) | \( \max (-c^T x) \), then negate the optimal value |
Geometry: Convexity and Extreme Points
- The feasible region \( S = \{x : Ax = b, x \ge 0\} \) is a convex polyhedron (an intersection of half-spaces). It may be empty, bounded (a polytope) or unbounded.
- A point of \( S \) is an extreme point (vertex) if it is not a strict convex combination of two other points of \( S \).
- With \( A \) of size \( m \times n \) and rank \( m \): choose \( m \) linearly independent columns (a basis \( B \)), set the other \( n - m \) variables to 0, and solve \( Bx_B = b \). This is a basic solution; if also \( x_B \ge 0 \), a basic feasible solution (BFS).
A BFS is degenerate if some basic variable equals 0. It then has fewer than \( m \) positive variables, and several bases describe the same vertex.
Graphical method (two variables)
Draw the constraints, shade the feasible polygon, list its vertices and evaluate \( z \). For the hook:
| Vertex | How found | \( z = 3x_1 + 2x_2 \) |
|---|---|---|
| \( (0, 0) \) | origin | 0 |
| \( (4, 0) \) | \( 2x_1 + x_2 = 8 \), \( x_2 = 0 \) | 12 |
| \( (3, 2) \) | \( 2x_1 + x_2 = 8 \), \( x_1 + 2x_2 = 7 \) | 13 |
| \( (1, 3) \) | \( x_1 + 2x_2 = 7 \), \( x_2 = 3 \) | 9 |
| \( (0, 3) \) | \( x_2 = 3 \), \( x_1 = 0 \) | 6 |
At \( (3, 2) \) the painting constraint is slack: \( x_2 = 2 < 3 \).
The Simplex Method
Simplex moves from a BFS to an adjacent BFS (one basic variable swapped) that does not decrease \( z \), and stops when no adjacent vertex is better.
graph TD
A["Start: a BFS (slacks basic)"] --> B{"Any z_j - c_j < 0?"}
B -- "No" --> C["Optimal: stop"]
B -- "Yes" --> D["Entering variable: most negative z_j - c_j"]
D --> E{"Any positive entry in its column?"}
E -- "No" --> F["Unbounded: stop"]
E -- "Yes" --> G["Leaving variable: minimum ratio b_i / a_ij over a_ij > 0"]
G --> H["Pivot: Gauss-Jordan on the pivot element"]
H --> B(This is for maximisation with the row \( z_j - c_j \), where \( z_j = c_B^T B^{-1} a_j \). For minimisation, either maximise \( -z \) or reverse the sign tests.)
Why the ratio test. Increasing the entering variable \( x_k \) changes basic variable \( i \) at rate \( -\bar a_{ik} \). Only rows with \( \bar a_{ik} > 0 \) drive a basic variable towards 0, and the first to hit 0 (the smallest ratio) must leave, or feasibility is lost.
Worked example: the hook by simplex
Add slacks \( s_1, s_2, s_3 \). Initial tableau (basis \( s_1, s_2, s_3 \)):
| Basis | \( x_1 \) | \( x_2 \) | \( s_1 \) | \( s_2 \) | \( s_3 \) | RHS |
|---|---|---|---|---|---|---|
| \( s_1 \) | 2 | 1 | 1 | 0 | 0 | 8 |
| \( s_2 \) | 1 | 2 | 0 | 1 | 0 | 7 |
| \( s_3 \) | 0 | 1 | 0 | 0 | 1 | 3 |
| \( z_j - c_j \) | \( -3 \) | \( -2 \) | 0 | 0 | 0 | 0 |
\( x_1 \) enters (\( -3 \)). Ratios: \( \frac{8}{2} = 4 \), \( \frac{7}{1} = 7 \) (no ratio for \( s_3 \), entry 0). \( s_1 \) leaves; pivot on 2.
| Basis | \( x_1 \) | \( x_2 \) | \( s_1 \) | \( s_2 \) | \( s_3 \) | RHS |
|---|---|---|---|---|---|---|
| \( x_1 \) | 1 | \( \frac{1}{2} \) | \( \frac{1}{2} \) | 0 | 0 | 4 |
| \( s_2 \) | 0 | \( \frac{3}{2} \) | \( -\frac{1}{2} \) | 1 | 0 | 3 |
| \( s_3 \) | 0 | 1 | 0 | 0 | 1 | 3 |
| \( z_j - c_j \) | 0 | \( -\frac{1}{2} \) | \( \frac{3}{2} \) | 0 | 0 | 12 |
\( x_2 \) enters. Ratios: \( \frac{4}{1/2} = 8 \), \( \frac{3}{3/2} = 2 \), \( \frac{3}{1} = 3 \). \( s_2 \) leaves; pivot on \( \frac{3}{2} \).
| Basis | \( x_1 \) | \( x_2 \) | \( s_1 \) | \( s_2 \) | \( s_3 \) | RHS |
|---|---|---|---|---|---|---|
| \( x_1 \) | 1 | 0 | \( \frac{2}{3} \) | \( -\frac{1}{3} \) | 0 | 3 |
| \( x_2 \) | 0 | 1 | \( -\frac{1}{3} \) | \( \frac{2}{3} \) | 0 | 2 |
| \( s_3 \) | 0 | 0 | \( \frac{1}{3} \) | \( -\frac{2}{3} \) | 1 | 1 |
| \( z_j - c_j \) | 0 | 0 | \( \frac{4}{3} \) | \( \frac{1}{3} \) | 0 | 13 |
All \( z_j - c_j \ge 0 \): optimal, \( x^* = (3, 2) \), \( z^* = 13 \), with \( s_3 = 1 \) hour of painting unused. The entries under the slack columns, \( \left(\frac{4}{3}, \frac{1}{3}, 0\right) \), are the optimal dual variables (shadow prices).
Reading a final tableau
| What you see (maximisation) | Conclusion |
|---|---|
| All \( z_j - c_j \ge 0 \) | current BFS optimal |
| A non-basic \( x_j \) with \( z_j - c_j = 0 \) (and a positive entry in its column) | alternative optima: pivoting it in gives another optimal vertex |
| \( z_j - c_j < 0 \) and every entry in column \( j \) is \( \le 0 \) | unbounded objective |
| A basic variable equal to 0 | degenerate BFS |
| An artificial variable positive at the end of Phase I (or with Big-M at optimality) | the LP is infeasible |
| Entries under the slack columns in the \( z \)-row | optimal dual values \( y^* \) |
| Columns under the initial basis | \( B^{-1} \) for the current basis |
Artificial Variables: Big-M and Two-Phase
When constraints are \( \ge \) or \( = \), the slacks do not give a starting BFS. Add an artificial variable \( a_i \ge 0 \) to each such row.
- Big-M method. Penalise artificials in the objective: \( \max\ c^T x - M\sum a_i \) with \( M \) a very large positive number. Run simplex. If an artificial is still positive at the optimum, the original LP is infeasible.
- Two-phase method. Phase I: minimise \( w = \sum a_i \). If \( w^* > 0 \), the LP is infeasible. If \( w^* = 0 \), drive any artificials out of the basis and start Phase II with the original objective from that BFS. Two-phase avoids choosing a numerical \( M \).
Degeneracy and cycling. A tie in the ratio test produces a degenerate BFS; a later pivot may then change the basis without moving the point (\( z \) unchanged). In rare constructed examples the simplex method cycles through the same bases forever. Anti-cycling rules (Bland’s smallest-index rule, the lexicographic rule) prevent this; with them, simplex terminates in finitely many steps.
Example of a degenerate vertex. For \( x_1 + x_2 \le 4 \), \( x_1 + 3x_2 \le 6 \), \( x_1 \le 3 \), all three lines pass through \( (3, 1) \). In two dimensions only two tight constraints are needed, so at \( (3, 1) \) one basic slack equals 0.
Duality
Every LP (the primal) has a dual. In symmetric form:
$$\text{(P)}\ \max\ c^T x \ \text{ s.t. } Ax \le b,\ x \ge 0 \qquad \longleftrightarrow \qquad \text{(D)}\ \min\ b^T y \ \text{ s.t. } A^T y \ge c,\ y \ge 0.$$One dual variable per primal constraint, one dual constraint per primal variable; the cost vector and the right-hand side swap; \( A \) is transposed.
| Primal (max) | Dual (min) |
|---|---|
| constraint \( i \): \( \le \) | \( y_i \ge 0 \) |
| constraint \( i \): \( \ge \) | \( y_i \le 0 \) |
| constraint \( i \): \( = \) | \( y_i \) unrestricted |
| variable \( x_j \ge 0 \) | constraint \( j \): \( \ge \) |
| variable \( x_j \le 0 \) | constraint \( j \): \( \le \) |
| variable \( x_j \) unrestricted | constraint \( j \): \( = \) |
Read the table backwards for a min primal. The dual of the dual is the primal.
Dual of the hook. \( \min w = 8y_1 + 7y_2 + 3y_3 \) s.t. \( 2y_1 + y_2 \ge 3 \), \( y_1 + 2y_2 + y_3 \ge 2 \), \( y \ge 0 \). At \( y^* = \left(\frac{4}{3}, \frac{1}{3}, 0\right) \): \( 2 \cdot \frac{4}{3} + \frac{1}{3} = 3 \) and \( \frac{4}{3} + \frac{2}{3} + 0 = 2 \) (both tight), \( w^* = \frac{32}{3} + \frac{7}{3} = 13 \).
Complementary slackness
Feasible \( x \) and \( y \) are both optimal if and only if
$$y_i\,(b_i - a_i^T x) = 0 \ \ \text{for every } i, \qquad x_j\,(A^T y - c)_j = 0 \ \ \text{for every } j.$$In words: a primal constraint with slack has a zero dual price; a dual variable that is positive forces its primal constraint to be tight; a positive primal variable forces its dual constraint to be tight.
Shadow prices and when to solve the dual
- \( y_i^* \) is the rate of change of the optimal value with \( b_i \), valid while the optimal basis stays feasible. In the hook, raising cutting hours from 8 to 9 moves the optimum to \( \left(\frac{11}{3}, \frac{5}{3}\right) \) with \( z = \frac{43}{3} = 13 + \frac{4}{3} \). The basis stays optimal for \( 5 \le b_1 \le 14 \), the range in which \( x_B = B^{-1}b \ge 0 \).
- A minimisation with many \( \ge \) constraints and few variables is often easier through its dual. For \( \min x_1 + x_2 \) s.t. \( x_1 + 2x_2 \ge 4 \), \( 3x_1 + x_2 \ge 6 \), \( x \ge 0 \), the dual \( \max 4y_1 + 6y_2 \) s.t. \( y_1 + 3y_2 \le 1 \), \( 2y_1 + y_2 \le 1 \) has optimum \( y = \left(\frac{2}{5}, \frac{1}{5}\right) \), value \( \frac{14}{5} \), equal to the primal optimum at \( \left(\frac{8}{5}, \frac{6}{5}\right) \).
- The dual simplex method keeps \( z_j - c_j \ge 0 \) (dual feasibility) and works towards primal feasibility; it is the natural tool after adding a new constraint to a solved LP.
Memory Tricks
Don’t Confuse
| This | vs | That |
|---|---|---|
| Unbounded feasible region | unbounded objective (a bounded optimum can exist on an unbounded region) | |
| Degenerate BFS (a basic variable is 0) | alternative optima (a non-basic \( z_j - c_j = 0 \)) | |
| Infeasible: artificial positive at the end | unbounded: entering column has no positive entry | |
| Weak duality: \( c^T x \le b^T y \) for feasible pairs | strong duality: equality at the optima | |
| Shadow price \( y_i^* \): value of one more unit of resource \( i \) | reduced cost \( z_j - c_j \): loss from forcing non-basic \( x_j \) to 1 | |
| Big-M: one phase, large penalty | two-phase: separate feasibility phase, no \( M \) |
Common Mistakes
Practice
All questions below are original practice questions written for this page. They are not from any CSIR NET paper. In Level 3, as in Part C, one or more options may be correct.
Level 1: Foundation
- An LP in standard form has 3 equality constraints (rank 3) and 5 variables. At most how many basic feasible solutions can it have?
- What is the dual of the dual of an LP?
- In a maximisation simplex tableau, what does an entering column with no positive entries mean?
Answers
- \( \binom{5}{3} = 10 \).
- The original (primal) LP.
- The objective is unbounded: the entering variable can increase indefinitely without any basic variable becoming negative.
Level 2: Part B Style
Practice Q1. The maximum of \( z = 2x_1 + 3x_2 \) subject to \( x_1 + x_2 \le 4 \), \( x_1 + 3x_2 \le 6 \), \( x_1, x_2 \ge 0 \) is
(a) 6 (b) 8 (c) 9 (d) 12
Answer: (c)
Vertices: \( (0, 0) \to 0 \); \( (4, 0) \to 8 \); \( (0, 2) \to 6 \); the intersection of \( x_1 + x_2 = 4 \) and \( x_1 + 3x_2 = 6 \) is \( (3, 1) \to 6 + 3 = 9 \). Maximum 9.
Practice Q2. For the LP \( \max 4x_1 + 3x_2 \) s.t. \( x_1 + x_2 \le 5 \), \( 2x_1 + x_2 \le 8 \), \( x \ge 0 \), the optimal dual solution \( (y_1, y_2) \) is
(a) \( (1, 2) \) (b) \( (2, 1) \) (c) \( (3, 0) \) (d) \( (0, 4) \)
Answer: (b)
Primal optimum \( (3, 2) \) with both variables positive, so both dual constraints \( y_1 + 2y_2 \ge 4 \), \( y_1 + y_2 \ge 3 \) are tight: \( y = (2, 1) \), \( w = 18 = z^* \). (a) is dual feasible but gives \( w = 21 > 18 \), so it is not optimal; (c) gives \( w = 15 \) but violates \( y_1 + 2y_2 \ge 4 \); (d) is feasible with \( w = 32 > 18 \), not optimal.
Practice Q3. The final tableau of a maximisation problem (slacks \( s_1, s_2 \)) is
| Basis | \( x_1 \) | \( x_2 \) | \( x_3 \) | \( s_1 \) | \( s_2 \) | RHS |
|---|---|---|---|---|---|---|
| \( x_1 \) | 1 | 0 | 2 | 1 | \( -1 \) | 4 |
| \( x_2 \) | 0 | 1 | \( -1 \) | 0 | 1 | 3 |
| \( z_j - c_j \) | 0 | 0 | 0 | 2 | 1 | 17 |
Which conclusion is correct?
(a) The optimum is unique. (b) The problem is unbounded. (c) There are alternative optimal solutions. (d) The current solution is degenerate.
Answer: (c)
All \( z_j - c_j \ge 0 \), so the BFS \( (4, 3, 0) \) is optimal. The non-basic \( x_3 \) has \( z_3 - c_3 = 0 \) and a positive entry (2) in the \( x_1 \) row; pivoting it in (ratio \( \frac{4}{2} = 2 \)) gives \( x_3 = 2 \), \( x_1 = 0 \), \( x_2 = 3 + 2 = 5 \) with the same \( z = 17 \). (This tableau comes from \( \max 2x_1 + 3x_2 + x_3 \) s.t. \( x_1 + x_2 + x_3 \le 7 \), \( x_2 - x_3 \le 3 \); both \( (4, 3, 0) \) and \( (0, 5, 2) \) give 17.) No basic variable is 0, so it is not degenerate.
Practice Q4. If a linear programming problem is infeasible, its dual
(a) must be unbounded (b) must be infeasible (c) is either infeasible or unbounded (d) must have an optimal solution
Answer: (c)
By strong duality the dual cannot have an optimum (else the primal would too). So it is unbounded or infeasible, and both happen (see Trap 3 for a both-infeasible pair).
Level 3: Part C Style
Practice Q5. Consider \( \max z = 3x_1 + 2x_2 \) s.t. \( 2x_1 + x_2 \le 8 \), \( x_1 + 2x_2 \le 7 \), \( x_2 \le 3 \), \( x \ge 0 \). Which statements are true?
(a) The optimal value of the dual is 13. (b) In every optimal dual solution, the variable of the constraint \( x_2 \le 3 \) is 0. (c) If the right-hand side 8 is changed to 9, the optimal value becomes \( \frac{43}{3} \). (d) The problem has more than one optimal solution.
Answer: (a), (b) and (c)
- (a) True. Primal optimum 13 at \( (3, 2) \); strong duality.
- (b) True. At the (unique) primal optimum \( x_2 = 2 < 3 \), the constraint is slack; complementary slackness forces \( y_3 = 0 \) in every optimal dual solution.
- (c) True. \( y_1^* = \frac{4}{3} \) and the basis stays feasible for \( 5 \le b_1 \le 14 \). New optimum: solve \( 2x_1 + x_2 = 9 \), \( x_1 + 2x_2 = 7 \): \( \left(\frac{11}{3}, \frac{5}{3}\right) \), \( z = 11 + \frac{10}{3} = \frac{43}{3} \).
- (d) False. The vertex values are 0, 12, 13, 9, 6; only \( (3, 2) \) gives 13. In the final tableau every non-basic \( z_j - c_j \) (\( \frac{4}{3}, \frac{1}{3} \)) is strictly positive.
Practice Q6. Which statements about linear programming are true?
(a) If \( x^* \) is primal feasible, \( y^* \) is dual feasible and \( c^T x^* = b^T y^* \), then both are optimal. (b) If the feasible region is unbounded, the objective function is unbounded. (c) The set of optimal solutions of an LP is convex. (d) A basic feasible solution of a system with 3 equality constraints has at most 3 positive variables.
Answer: (a), (c) and (d)
- (a) True. Weak duality: every feasible \( x \) has \( c^T x \le b^T y^* = c^T x^* \); symmetric argument for \( y^* \).
- (b) False. Trap 2 gives an unbounded region with a finite optimum.
- (c) True. If \( x, x' \) are optimal with value \( z^* \), then \( \lambda x + (1 - \lambda)x' \) is feasible (convex region) and has value \( z^* \).
- (d) True. Only the \( m = 3 \) basic variables can be non-zero; there are fewer than 3 positive ones exactly when the BFS is degenerate.
Practice Q7. Consider \( \min z = x_1 + x_2 \) s.t. \( x_1 + 2x_2 \ge 4 \), \( 3x_1 + x_2 \ge 6 \), \( x_1, x_2 \ge 0 \). Which statements are true?
(a) The optimal value is \( \frac{14}{5} \). (b) The dual is \( \max 4y_1 + 6y_2 \) s.t. \( y_1 + 3y_2 \le 1 \), \( 2y_1 + y_2 \le 1 \), \( y \ge 0 \). (c) The optimal dual solution is \( \left(\frac{2}{5}, \frac{1}{5}\right) \). (d) Starting the simplex method with the surplus variables as the initial basis gives a basic feasible solution.
Answer: (a), (b) and (c)
- (a) True. Vertices of the (unbounded) feasible region: \( (0, 6) \to 6 \), \( (4, 0) \to 4 \), and the intersection \( x_1 + 2x_2 = 4 \), \( 3x_1 + x_2 = 6 \): \( x_1 = \frac{8}{5} \), \( x_2 = \frac{6}{5} \), \( z = \frac{14}{5} = 2.8 \). Since the costs are positive, \( z \) is bounded below and the minimum is at a vertex.
- (b) True. Min with \( \ge \) constraints and \( x \ge 0 \) is the symmetric form; transpose \( A \), swap \( b \) and \( c \).
- (c) True. Both \( x_j^* > 0 \), so both dual constraints are tight: \( y_1 + 3y_2 = 1 \), \( 2y_1 + y_2 = 1 \) give \( y = \left(\frac{2}{5}, \frac{1}{5}\right) \), value \( \frac{8}{5} + \frac{6}{5} = \frac{14}{5} \).
- (d) False. With \( x = 0 \) the surplus variables would be \( s_1 = -4 \), \( s_2 = -6 \), infeasible. That is why artificial variables (Big-M or two-phase) are needed, or the dual is solved instead.
Quick Revision Table
| Idea | Fact |
|---|---|
| Vertices | extreme points = BFS; at most \( \binom{n}{m} \) |
| Optimum | if it exists, attained at a BFS; optimal set convex |
| Entering (max) | most negative \( z_j - c_j \) |
| Leaving | minimum \( \frac{b_i}{a_{ik}} \) over \( a_{ik} > 0 \) |
| Optimal | all \( z_j - c_j \ge 0 \) |
| Alternative optima | non-basic \( z_j - c_j = 0 \) |
| Unbounded | entering column \( \le 0 \) |
| Infeasible | artificial positive after Phase I / Big-M |
| Degenerate | a basic variable is 0; cycling possible, Bland’s rule prevents it |
| Dual (symmetric) | \( \max c^Tx, Ax \le b, x \ge 0 \leftrightarrow \min b^Ty, A^Ty \ge c, y \ge 0 \) |
| Duality | weak \( c^Tx \le b^Ty \); strong: equal optima; unbounded \( \Rightarrow \) other infeasible |
| Complementary slackness | \( y_i \cdot \text{slack}_i = 0 \), \( x_j \cdot \text{surplus}_j = 0 \) |
| Shadow prices | \( z \)-row entries under the slack columns |
Key Takeaways
What’s Next
- Queuing Models: from deterministic allocation to random arrivals and services.
- Quadratic Forms: the convexity and definiteness ideas that extend LP to quadratic programming.
- Reliability and Operations Research: Quick Revision.