Linear Programming

LP formulation, graphical method, simplex algorithm, duality theory, transportation and assignment problems — with step-by-step worked examples, key theorems, and interactive practice.

LP Formulation Graphical Method Simplex Method Duality Theory Transportation & Assignment

0 / 5 units completed0%

Formulation of LP Problems

A linear programming (LP) problem seeks to optimise a linear objective function subject to linear constraints. Formulating real-world problems as LPs is the first and most important step.

◆ Standard and Canonical Forms

Definition — Linear Programming Problem A linear programming problem in standard form is: $$\text{Maximise } z = \mathbf{c}^T\mathbf{x} \quad \text{subject to } A\mathbf{x} \le \mathbf{b}, \quad \mathbf{x} \ge \mathbf{0}$$ where $\mathbf{c} \in \mathbb{R}^n$ is the cost vector, $A \in \mathbb{R}^{m \times n}$ is the constraint matrix, $\mathbf{b} \in \mathbb{R}^m$ is the resource vector, and $\mathbf{x} \in \mathbb{R}^n$ is the decision variable vector.

Definition — Feasible Region and Optimal Solution

Feasible region: The set $S = \{\mathbf{x} : A\mathbf{x} \le \mathbf{b}, \mathbf{x} \ge \mathbf{0}\}$. This is always a convex polyhedron (possibly empty or unbounded).
Feasible solution: Any $\mathbf{x} \in S$.
Optimal solution: A feasible solution $\mathbf{x}^*$ at which $z$ attains its maximum.
Basic feasible solution (BFS): A vertex (extreme point) of the feasible polyhedron.

Fundamental Theorem of Linear Programming If an LP has an optimal solution, then there exists an optimal solution that is a basic feasible solution (vertex of the polyhedron). Thus, the optimum is always attained at a vertex.

★ Example — Production Planning

A factory makes two products: chairs (profit $40 each) and tables (profit $70 each). Each chair requires 2 hours of carpentry and 1 hour of finishing. Each table requires 3 hours of carpentry and 2 hours of finishing. Available: 120 carpentry hours and 80 finishing hours. Formulate as an LP.

Solution: Let $x_1$ = chairs, $x_2$ = tables.
Maximise $z = 40x_1 + 70x_2$
Subject to: $2x_1 + 3x_2 \le 120$ (carpentry), $x_1 + 2x_2 \le 80$ (finishing), $x_1, x_2 \ge 0$.

◆ Converting to Standard Form

Any LP can be converted to the form: Maximise $\mathbf{c}^T\mathbf{x}$ subject to $A\mathbf{x} = \mathbf{b}$, $\mathbf{x} \ge 0$, using these transformations:

Minimisation to maximisation: $\min z = \max(-z)$.
$\le$ to equality: Add a slack variable $s \ge 0$: $a^T\mathbf{x} + s = b$.
$\ge$ to equality: Subtract a surplus variable $s \ge 0$: $a^T\mathbf{x} - s = b$.
Unrestricted variable: Replace $x_j$ by $x_j^+ - x_j^-$ where $x_j^+, x_j^- \ge 0$.

Graphical Method

For LP problems with two decision variables, the feasible region can be drawn in the plane and the optimal vertex identified by inspection or by evaluating the objective at each vertex.

◆ Steps of the Graphical Method

Algorithm:

Step 1: Plot each constraint as a line and shade the feasible half-plane.
Step 2: Identify the feasible region (the intersection of all half-planes and the non-negativity constraints).
Step 3: Find all vertices (corner points) of the feasible region by solving pairs of constraint equations simultaneously.
Step 4: Evaluate the objective function at each vertex and select the maximum (or minimum).

★ Example — Graphical Solution

Solve the production LP: Maximise $z = 40x_1 + 70x_2$ subject to $2x_1 + 3x_2 \le 120$, $x_1 + 2x_2 \le 80$, $x_1, x_2 \ge 0$.

Solution: The vertices of the feasible region are:

$(0, 0)$: $z = 0$
$(60, 0)$: $z = 2400$
$(0, 40)$: $z = 2800$
Intersection of $2x_1 + 3x_2 = 120$ and $x_1 + 2x_2 = 80$: solving gives $x_1 = 2(120 - 3x_2)/2$ and substituting, $x_1 = 0$... Let us solve correctly: from the second equation $x_1 = 80 - 2x_2$. Substituting: $2(80 - 2x_2) + 3x_2 = 120 \Rightarrow 160 - 4x_2 + 3x_2 = 120 \Rightarrow x_2 = 40$, $x_1 = 0$.

Wait — that gives $(0, 40)$ again. Check: the constraints $2x_1 + 3x_2 = 120$ and $x_1 + 2x_2 = 80$ intersect at $(0, 40)$. The vertex $(60, 0)$ comes from $2x_1 + 3(0) = 120$, $x_1 = 60$, and checking: $60 + 0 = 60 \le 80$ (feasible). Also check $(0, 40)$: $0 + 2(40) = 80 \le 80$ (feasible) and $0 + 3(40) = 120 \le 120$ (feasible). So the vertices are $(0,0)$, $(60,0)$, $(0,40)$. Maximum $z = 2800$ at $(0, 40)$: make 0 chairs and 40 tables.

◆ Special Cases

Unbounded solution: The feasible region is unbounded in the direction of optimisation. The LP has no finite optimal value.
Infeasible problem: The feasible region is empty (constraints are contradictory).
Multiple optimal solutions: The objective function is parallel to a binding constraint, so the entire edge (between two optimal vertices) is optimal.
Degenerate vertex: More than two constraint lines pass through the same point.

Simplex Method

The simplex method is the workhorse algorithm of linear programming. It systematically moves from one basic feasible solution to an adjacent one with a better (or equal) objective value, reaching optimality in finitely many steps.

◆ Simplex Tableau

Setup Convert the LP to standard equality form by adding slack variables. The initial tableau has the identity matrix in the slack columns, forming the initial basis.

Basic variables: Variables currently in the basis (their columns form an identity submatrix).
Non-basic variables: Variables set to $0$.
Pivot column: The column with the most negative coefficient in the objective row (entering variable).
Pivot row: Determined by the minimum ratio test: $\min\{b_i / a_{ij} : a_{ij} > 0\}$ (leaving variable).

★ Example — Simplex Step-by-Step

Solve: Maximise $z = 5x_1 + 4x_2$ subject to $6x_1 + 4x_2 \le 24$, $x_1 + 2x_2 \le 6$, $x_1, x_2 \ge 0$.

Step 1 — Standard form: Add slacks $s_1, s_2$:
$6x_1 + 4x_2 + s_1 = 24$, $x_1 + 2x_2 + s_2 = 6$, $x_1, x_2, s_1, s_2 \ge 0$.

Initial tableau:
$\begin{array}{c|cccc|c} & x_1 & x_2 & s_1 & s_2 & \text{RHS} \\ \hline s_1 & 6 & 4 & 1 & 0 & 24 \\ s_2 & 1 & 2 & 0 & 1 & 6 \\ \hline z & -5 & -4 & 0 & 0 & 0 \end{array}$

Iteration 1: Most negative in $z$-row: $-5$ ($x_1$ enters). Ratios: $24/6 = 4$, $6/1 = 6$. Min ratio $= 4$ (row 1). Pivot on $a_{11} = 6$.
Divide row 1 by 6: $(1, \frac{2}{3}, \frac{1}{6}, 0 \mid 4)$.
Row 2 $\leftarrow$ Row 2 $- 1 \cdot$ (new Row 1): $(0, \frac{4}{3}, -\frac{1}{6}, 1 \mid 2)$.
$z$-row $\leftarrow$ $z$-row $+ 5 \cdot$ (new Row 1): $(0, -\frac{2}{3}, \frac{5}{6}, 0 \mid 20)$.

Iteration 2: Most negative: $-\frac{2}{3}$ ($x_2$ enters). Ratios: $4/(2/3) = 6$, $2/(4/3) = 3/2$. Min ratio $= 3/2$ (row 2). Pivot on $\frac{4}{3}$.
Divide row 2 by $\frac{4}{3}$: $(0, 1, -\frac{1}{8}, \frac{3}{4} \mid \frac{3}{2})$.
Row 1 $\leftarrow$ Row 1 $- \frac{2}{3} \cdot$ (new Row 2): $(1, 0, \frac{1}{4}, -\frac{1}{2} \mid 3)$.
$z$-row $\leftarrow$ $z$-row $+ \frac{2}{3} \cdot$ (new Row 2): $(0, 0, \frac{3}{4}, \frac{1}{2} \mid 21)$.

Result: All $z$-row coefficients $\ge 0$. Optimal solution: $x_1 = 3$, $x_2 = 3/2$, $z^* = 21$.

◆ Big-M and Two-Phase Method

Artificial Variables When the initial basis is not readily available (e.g., constraints have $\ge$ or $=$ types), we introduce artificial variables to form the initial identity basis. These must be driven to zero.

Big-M Method: Add artificial variables $a_i$ with a very large penalty $-Ma_i$ in the objective (for maximisation, where $M \gg 0$). If any artificial variable remains positive in the optimal solution, the original LP is infeasible.

Two-Phase Method:

Phase I: Minimise the sum of artificial variables. If the minimum is $0$, a BFS for the original problem is found.
Phase II: Drop artificial variables and optimise the original objective starting from the Phase I basis.

Duality Theory

Every LP (the primal) has a companion LP (the dual). Duality theory provides deep insights into the structure of optimal solutions and economic interpretation of constraints.

◆ Primal-Dual Pair

Definition — Dual LP Given the primal: $\max\; \mathbf{c}^T\mathbf{x}$ subject to $A\mathbf{x} \le \mathbf{b}$, $\mathbf{x} \ge 0$, the dual is: $$\min\; \mathbf{b}^T\mathbf{y} \quad \text{subject to } A^T\mathbf{y} \ge \mathbf{c}, \quad \mathbf{y} \ge \mathbf{0}.$$ The dual of the dual is the primal.

Theorem — Weak Duality If $\mathbf{x}$ is feasible for the primal and $\mathbf{y}$ is feasible for the dual, then: $$\mathbf{c}^T\mathbf{x} \le \mathbf{b}^T\mathbf{y}.$$ The primal objective value never exceeds the dual objective value.

Theorem — Strong Duality If the primal has an optimal solution $\mathbf{x}^*$, then the dual also has an optimal solution $\mathbf{y}^*$, and: $$\mathbf{c}^T\mathbf{x}^* = \mathbf{b}^T\mathbf{y}^*.$$ The optimal primal and dual values are equal.

Theorem — Complementary Slackness Optimal $\mathbf{x}^*$ and $\mathbf{y}^*$ satisfy:

$x_j^*\left(\sum_i a_{ij}y_i^* - c_j\right) = 0$ for all $j$ — if $x_j^* > 0$, the corresponding dual constraint is tight.
$y_i^*\left(b_i - \sum_j a_{ij}x_j^*\right) = 0$ for all $i$ — if $y_i^* > 0$, the corresponding primal constraint is tight.

★ Example

Write the dual of: $\max\; 5x_1 + 4x_2$ subject to $6x_1 + 4x_2 \le 24$, $x_1 + 2x_2 \le 6$, $x_1, x_2 \ge 0$.

Solution: The dual is: $\min\; 24y_1 + 6y_2$ subject to $6y_1 + y_2 \ge 5$, $4y_1 + 2y_2 \ge 4$, $y_1, y_2 \ge 0$. From the simplex solution, the optimal primal value is $z^* = 21$. By strong duality, the optimal dual value is also $21$. The dual variables $y_1, y_2$ represent the shadow prices of the carpentry and finishing constraints.

Transportation & Assignment Problems

Transportation and assignment problems are special LP problems with efficient solution methods that exploit their network structure.

◆ Transportation Problem

Definition The transportation problem ships goods from $m$ sources (with supply $s_i$) to $n$ destinations (with demand $d_j$) at cost $c_{ij}$ per unit. The LP is: $$\min \sum_{i=1}^m \sum_{j=1}^n c_{ij} x_{ij} \quad \text{s.t.} \quad \sum_j x_{ij} = s_i, \; \sum_i x_{ij} = d_j, \; x_{ij} \ge 0.$$ The problem is balanced if $\sum s_i = \sum d_j$ (add a dummy source/destination otherwise).

Initial BFS methods:

North-West Corner: Start at $(1,1)$ and allocate as much as possible, moving right or down.
Least Cost Method: Allocate first to the cell with the smallest $c_{ij}$.
Vogel's Approximation (VAM): For each row/column, compute the penalty (difference between the two smallest costs). Allocate to the cell with the smallest cost in the row/column with the largest penalty. Repeat. VAM generally produces a near-optimal initial solution.

★ Example — North-West Corner

Supply: $s_1 = 20$, $s_2 = 30$. Demand: $d_1 = 10$, $d_2 = 25$, $d_3 = 15$. Find the NW corner initial BFS.

Solution:
Cell $(1,1)$: $\min(20, 10) = 10$. $x_{11} = 10$. Remaining: $s_1 = 10$, $d_1 = 0$. Move right.
Cell $(1,2)$: $\min(10, 25) = 10$. $x_{12} = 10$. Remaining: $s_1 = 0$, $d_2 = 15$. Move down.
Cell $(2,2)$: $\min(30, 15) = 15$. $x_{22} = 15$. Remaining: $s_2 = 15$, $d_2 = 0$. Move right.
Cell $(2,3)$: $\min(15, 15) = 15$. $x_{23} = 15$. Done.
Initial BFS: $x_{11} = 10$, $x_{12} = 10$, $x_{22} = 15$, $x_{23} = 15$.

◆ Assignment Problem (Hungarian Method)

Definition The assignment problem is a special transportation problem where $m = n$, $s_i = d_j = 1$, and each source is assigned to exactly one destination. Minimise $\sum_{i,j} c_{ij}x_{ij}$ with $x_{ij} \in \{0, 1\}$.

Hungarian Algorithm:

Step 1: Subtract the row minimum from each row.
Step 2: Subtract the column minimum from each column.
Step 3: Cover all zeros using the minimum number of lines (rows/columns).
Step 4: If the number of lines equals $n$, an optimal assignment exists. Otherwise, find the smallest uncovered element $\varepsilon$, subtract $\varepsilon$ from all uncovered elements, add $\varepsilon$ to doubly-covered elements, and repeat Step 3.

★ Example — Hungarian Method

Solve the $3 \times 3$ assignment problem with cost matrix: $C = \begin{pmatrix} 9 & 2 & 7 \\ 6 & 4 & 3 \\ 5 & 8 & 1 \end{pmatrix}$

Step 1 (Row reduction): Row mins: $2, 3, 1$. Subtract: $\begin{pmatrix} 7 & 0 & 5 \\ 3 & 1 & 0 \\ 4 & 7 & 0 \end{pmatrix}$.
Step 2 (Column reduction): Col mins: $3, 0, 0$. Subtract: $\begin{pmatrix} 4 & 0 & 5 \\ 0 & 1 & 0 \\ 1 & 7 & 0 \end{pmatrix}$.
Step 3: Zeros can be covered by 3 lines (e.g., row 2, col 2, col 3). Since $3 = n$, we can find an optimal assignment.
Assignment: $(1,2)$: cost $2$; $(2,1)$: cost $6$; $(3,3)$: cost $1$. Total cost $= 2 + 6 + 1 = 9$.

★ Key Takeaways

An LP has a linear objective and linear constraints. The feasible region is a convex polyhedron, and the optimum occurs at a vertex.
The graphical method works for 2-variable problems by evaluating the objective at each vertex of the feasible polygon.
The simplex method moves between adjacent vertices, improving the objective at each step, using the most negative coefficient to select the entering variable and the minimum ratio test for the leaving variable.
Weak duality: $\mathbf{c}^T\mathbf{x} \le \mathbf{b}^T\mathbf{y}$ for any primal-dual feasible pair. Strong duality: equality holds at optimality.
Complementary slackness links primal and dual solutions: a positive variable implies its constraint is tight, and vice versa.
Transportation and assignment problems have specialised algorithms (VAM, Hungarian method) that are much faster than general simplex.

✎ Practice Problems

Problem 1

Solve graphically: Maximise $z = 3x_1 + 2x_2$ subject to $x_1 + x_2 \le 4$, $x_1 + 3x_2 \le 6$, $x_1, x_2 \ge 0$.

Show Solution ▼

Vertices: $(0,0)$, $(4,0)$, $(0,2)$, and the intersection of $x_1 + x_2 = 4$ and $x_1 + 3x_2 = 6$: subtracting gives $2x_2 = 2$, so $x_2 = 1$, $x_1 = 3$. Vertex $(3,1)$. Check $(4,0)$: $4 + 0 = 4 \le 6$? Yes. Values: $z(0,0) = 0$, $z(4,0) = 12$, $z(0,2) = 4$, $z(3,1) = 11$. Maximum $z = 12$ at $(4,0)$.

Problem 2

Use the simplex method to solve: Maximise $z = 2x_1 + 3x_2$ subject to $x_1 + 2x_2 \le 8$, $3x_1 + 2x_2 \le 12$, $x_1, x_2 \ge 0$.

Show Solution ▼

Add slacks: $x_1 + 2x_2 + s_1 = 8$, $3x_1 + 2x_2 + s_2 = 12$. Initial: basis $\{s_1, s_2\}$, $z = 0$. Enter $x_2$ (coefficient $-3$). Ratios: $8/2 = 4$, $12/2 = 6$. Pivot row 1. After pivoting: $x_2 = 4$, $s_2 = 4$, $z = 12$. Next: enter $x_1$ (coefficient $-1/2$). Ratios: $4/(1/2) = 8$, $4/2 = 2$. Pivot row 2. After: $x_1 = 2$, $x_2 = 3$, $z = 13$. Optimal: $z^* = 13$ at $(2, 3)$.

Problem 3

Write the dual of: Minimise $w = 4y_1 + 6y_2$ subject to $y_1 + 3y_2 \ge 2$, $2y_1 + y_2 \ge 3$, $y_1, y_2 \ge 0$. Verify weak duality with the feasible solution $y_1 = 1, y_2 = 1$.

Show Solution ▼

The primal (rewritten as max): $\max\; -(4y_1 + 6y_2)$ s.t. $-y_1 - 3y_2 \le -2$, $-2y_1 - y_2 \le -3$, $y_1, y_2 \ge 0$. The dual of the original min problem is: $\max\; 2x_1 + 3x_2$ s.t. $x_1 + 2x_2 \le 4$, $3x_1 + x_2 \le 6$, $x_1, x_2 \ge 0$. For $y = (1,1)$: $w = 10$, and $y$ is feasible ($1+3 = 4 \ge 2$, $2+1 = 3 \ge 3$). For any dual feasible $x$: $2x_1 + 3x_2 \le w = 10$ (weak duality holds).

Problem 4

Using Vogel's Approximation Method, find an initial BFS for the transportation problem: supply $s = (30, 40, 20)$, demand $d = (20, 25, 35, 10)$, cost matrix $C = \begin{pmatrix} 2 & 3 & 1 & 4 \\ 5 & 1 & 2 & 3 \\ 4 & 2 & 4 & 1 \end{pmatrix}$.

Show Solution ▼

VAM penalties: Row 1: $2-1=1$, Row 2: $2-1=1$, Row 3: $2-1=1$. Col 1: $3$, Col 2: $1$, Col 3: $1$, Col 4: $1$. Largest penalty: Col 1 ($3$). Smallest cost in Col 1: $c_{11}=2$. Allocate $x_{11} = \min(30,20) = 20$. Cross out Col 1. Recompute and continue. The process yields a near-optimal initial solution with total cost that can then be optimised using the stepping-stone or MODI method.

Problem 5

Solve the assignment problem: $C = \begin{pmatrix} 8 & 4 & 2 \\ 4 & 2 & 6 \\ 6 & 8 & 4 \end{pmatrix}$ using the Hungarian method.

Show Solution ▼

Row reduction (subtract row min): $\begin{pmatrix} 6 & 2 & 0 \\ 2 & 0 & 4 \\ 2 & 4 & 0 \end{pmatrix}$. Column reduction (subtract col min $2,0,0$): $\begin{pmatrix} 4 & 2 & 0 \\ 0 & 0 & 4 \\ 0 & 4 & 0 \end{pmatrix}$. Cover zeros: need 2 lines (row 2 and col 3). Since $2 < 3$, find smallest uncovered element $= 2$. Subtract from uncovered, add to intersections: $\begin{pmatrix} 2 & 0 & 0 \\ 0 & 0 & 6 \\ 0 & 4 & 2 \end{pmatrix}$. Now 3 lines needed. Assign: $(1,3)=2$, $(2,2)=2$, $(3,1)=6$. Total $= 10$.

🎯 Interactive Quiz

1. The Fundamental Theorem of LP states that if an optimal solution exists, it occurs at:

A The centre of the feasible region

B A vertex (extreme point) of the feasible polyhedron

C An interior point of the feasible region

D The midpoint of a constraint edge

2. In the simplex method, the entering variable is selected based on:

A The most negative coefficient in the objective row

B The minimum ratio test

C The largest value in the RHS column

D The most positive coefficient in the objective row

3. Weak duality states that for feasible primal $\mathbf{x}$ and dual $\mathbf{y}$:

A $\mathbf{c}^T\mathbf{x} = \mathbf{b}^T\mathbf{y}$

B $\mathbf{c}^T\mathbf{x} \le \mathbf{b}^T\mathbf{y}$

C $\mathbf{c}^T\mathbf{x} \ge \mathbf{b}^T\mathbf{y}$

D $|\mathbf{c}^T\mathbf{x} - \mathbf{b}^T\mathbf{y}| \le 1$

4. In the transportation problem, Vogel's Approximation Method selects cells based on:

A Starting from the top-left corner

B The globally smallest cost

C The penalty (difference between two smallest costs) for each row and column

D Random selection

5. The Hungarian method for the assignment problem works by:

A Enumerating all possible assignments

B Reducing the cost matrix and finding a zero-cost assignment

C Applying the simplex method directly

D Greedy assignment of the cheapest available option