Skip to content

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 read
  • Updated
On this page · 14 sections
  1. Prerequisites
  2. The Hook: Two Products, Three Machines
  3. Formulation and Standard Form
  4. Geometry: Convexity and Extreme Points
  5. The Simplex Method
  6. Artificial Variables: Big-M and Two-Phase
  7. Duality
  8. Memory Tricks
  9. Don’t Confuse
  10. Common Mistakes
  11. Practice
  12. Quick Revision Table
  13. Key Takeaways
  14. What’s Next

Prerequisites

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:

FeatureConversion
\( \le \) constraintadd a slack \( s \ge 0 \): \( a^T x + s = b \)
\( \ge \) constraintsubtract 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:

VertexHow found\( z = 3x_1 + 2x_2 \)
\( (0, 0) \)origin0
\( (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 \)211008
\( s_2 \)120107
\( s_3 \)010013
\( z_j - c_j \)\( -3 \)\( -2 \)0000

\( 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} \)004
\( s_2 \)0\( \frac{3}{2} \)\( -\frac{1}{2} \)103
\( s_3 \)010013
\( z_j - c_j \)0\( -\frac{1}{2} \)\( \frac{3}{2} \)0012

\( 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 \)10\( \frac{2}{3} \)\( -\frac{1}{3} \)03
\( x_2 \)01\( -\frac{1}{3} \)\( \frac{2}{3} \)02
\( s_3 \)00\( \frac{1}{3} \)\( -\frac{2}{3} \)11
\( z_j - c_j \)00\( \frac{4}{3} \)\( \frac{1}{3} \)013

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 0degenerate 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 \)-rowoptimal 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 \) unrestrictedconstraint \( 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

ThisvsThat
Unbounded feasible regionunbounded 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 endunbounded: entering column has no positive entry
Weak duality: \( c^T x \le b^T y \) for feasible pairsstrong 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 penaltytwo-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

  1. An LP in standard form has 3 equality constraints (rank 3) and 5 variables. At most how many basic feasible solutions can it have?
  2. What is the dual of the dual of an LP?
  3. In a maximisation simplex tableau, what does an entering column with no positive entries mean?
Answers
  1. \( \binom{5}{3} = 10 \).
  2. The original (primal) LP.
  3. 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 \)1021\( -1 \)4
\( x_2 \)01\( -1 \)013
\( z_j - c_j \)0002117

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

IdeaFact
Verticesextreme points = BFS; at most \( \binom{n}{m} \)
Optimumif it exists, attained at a BFS; optimal set convex
Entering (max)most negative \( z_j - c_j \)
Leavingminimum \( \frac{b_i}{a_{ik}} \) over \( a_{ik} > 0 \)
Optimalall \( z_j - c_j \ge 0 \)
Alternative optimanon-basic \( z_j - c_j = 0 \)
Unboundedentering column \( \le 0 \)
Infeasibleartificial positive after Phase I / Big-M
Degeneratea 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 \)
Dualityweak \( 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