← Back to CSIR NET
CSIR NET > Linear Programming & Optimisation

Linear Programming & Optimisation

From the simplex method to game theory and convex optimisation — the mathematical foundations of decision-making and resource allocation under constraints.

LP Formulation Simplex Method Duality Theory Transportation & Assignment Game Theory Convex Optimisation
0 / 6 units completed0%
01 LP Formulation & Graphical Method

Linear programming concerns optimising a linear objective function subject to linear inequality and equality constraints. The graphical method provides geometric insight for two-variable problems.

◆ Standard LP Formulation
Definition — Linear Program A linear program in standard form is: $$\text{Maximise } \mathbf{c}^T\mathbf{x} \quad \text{subject to } A\mathbf{x} \le \mathbf{b},\; \mathbf{x} \ge \mathbf{0}$$ where $\mathbf{c} \in \mathbb{R}^n$ is the cost vector, $A \in \mathbb{R}^{m \times n}$, and $\mathbf{b} \in \mathbb{R}^m$.

The feasible region $\{\mathbf{x} : A\mathbf{x} \le \mathbf{b},\, \mathbf{x} \ge 0\}$ is a convex polyhedron. By the fundamental theorem of LP, if an optimal solution exists, it occurs at a vertex (extreme point) of the feasible region.

Theorem — Fundamental Theorem of LP If the feasible region of a linear program is non-empty and bounded, then the objective function attains its maximum (and minimum) at an extreme point of the feasible region.
★ Example
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$.
Solution: The corner points of the feasible region are $(0,0)$, $(4,0)$, $(3,1)$, and $(0,2)$. Evaluating: $z(0,0) = 0$, $z(4,0) = 12$, $z(3,1) = 11$, $z(0,2) = 4$. The intersection of $x_1 + x_2 = 4$ and $x_1 + 3x_2 = 6$ gives $x_2 = 1$, $x_1 = 3$. Maximum $z = 12$ at $(4, 0)$.
02 Simplex Method

The simplex algorithm systematically moves from vertex to vertex of the feasible polyhedron, improving the objective at each step, until optimality is reached.

◆ Standard Form & Tableau
Definition — Standard Form for Simplex Convert to equality constraints by introducing slack variables: $A\mathbf{x} + \mathbf{s} = \mathbf{b}$, $\mathbf{x}, \mathbf{s} \ge 0$. A basic feasible solution (BFS) is obtained by setting $n$ variables to zero and solving for the remaining $m$ variables (the basis).

The simplex tableau organises the computation. At each iteration:

  • Entering variable: Choose the non-basic variable with the most negative reduced cost (in maximisation).
  • Leaving variable: Apply the minimum ratio test to maintain feasibility.
  • Pivot: Perform row operations to update the tableau.

The algorithm terminates when all reduced costs are non-negative (optimality) or when the minimum ratio test fails (unbounded).

◆ Degeneracy & Cycling
Definition — Degeneracy A BFS is degenerate if one or more basic variables equal zero. Degeneracy can cause cycling — the simplex method revisiting the same BFS without improving the objective.

Anti-cycling rules:

  • Bland's rule: Always choose the entering and leaving variables with the smallest index among eligible candidates. This prevents cycling.
  • Lexicographic method: Uses lexicographic ordering to break ties consistently.
★ Example
Solve using simplex: 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$.
Solution: Adding slacks $s_1, s_2$: $6x_1 + 4x_2 + s_1 = 24$, $x_1 + 2x_2 + s_2 = 6$. Initial BFS: $s_1 = 24$, $s_2 = 6$, $z = 0$. Entering: $x_1$ (most negative, $-5$). Ratios: $24/6 = 4$, $6/1 = 6$. $s_1$ leaves. After pivot: $x_1 = 4$, $s_2 = 2$, $z = 20$. Next: $x_2$ enters (reduced cost $-2/3$). Ratios: $1/(2/3) = 3/2$, $2/(4/3) = 3/2$ (tie). Choose $s_2$ leaves. After pivot: $x_1 = 3$, $x_2 = 3/2$, $z = 21$. All reduced costs $\ge 0$. Optimal: $z^* = 21$ at $(3, 3/2)$.
03 Duality Theory

Every linear program has an associated dual. The relationship between primal and dual provides optimality conditions, economic interpretations, and computational shortcuts.

◆ Weak & Strong Duality
Definition — Dual Program Given the primal: $\max\, \mathbf{c}^T\mathbf{x}$ s.t. $A\mathbf{x} \le \mathbf{b}$, $\mathbf{x} \ge 0$, the dual is: $$\min\, \mathbf{b}^T\mathbf{y} \quad \text{s.t. } A^T\mathbf{y} \ge \mathbf{c},\; \mathbf{y} \ge 0.$$
Theorem — Weak Duality If $\mathbf{x}$ is primal feasible and $\mathbf{y}$ is dual feasible, then $\mathbf{c}^T\mathbf{x} \le \mathbf{b}^T\mathbf{y}$. Consequently, if equality holds, both are optimal.
Theorem — Strong Duality If the primal has a finite optimal value, then so does the dual, and the two optimal values are equal: $\max\,\mathbf{c}^T\mathbf{x}^* = \min\,\mathbf{b}^T\mathbf{y}^*$.
◆ Complementary Slackness
Theorem — Complementary Slackness $\mathbf{x}^*$ and $\mathbf{y}^*$ are optimal for the primal and dual respectively if and only if they are feasible and:
(i) $y_i^*(b_i - \sum_j a_{ij}x_j^*) = 0$ for all $i$ (if dual variable is positive, primal constraint is tight).
(ii) $x_j^*(\sum_i a_{ij}y_i^* - c_j) = 0$ for all $j$ (if primal variable is positive, dual constraint is tight).

Economic interpretation: The dual variables $y_i$ represent shadow prices — the marginal value of relaxing the $i$-th constraint by one unit. Complementary slackness says that a resource with slack has zero shadow price.

★ Example
Given the primal optimal $\mathbf{x}^* = (3, 3/2)$ from Unit 2 (with constraints $6x_1 + 4x_2 \le 24$, $x_1 + 2x_2 \le 6$), find the dual optimal solution using complementary slackness.
Solution: Both primal constraints are tight at $(3, 3/2)$: $6(3) + 4(3/2) = 24$ and $3 + 2(3/2) = 6$. So both $y_1, y_2 > 0$ is possible. Since $x_1^* > 0$ and $x_2^* > 0$, both dual constraints are tight: $6y_1 + y_2 = 5$ and $4y_1 + 2y_2 = 4$. Solving: $y_1 = 3/4$, $y_2 = 1/2$. Check: $\mathbf{b}^T\mathbf{y}^* = 24(3/4) + 6(1/2) = 18 + 3 = 21 = z^*$.
04 Transportation & Assignment Problems

Special structures in LP lead to efficient algorithms: the transportation problem for shipping goods from sources to destinations, and the assignment problem for one-to-one matching.

◆ Transportation Problem
Definition — Transportation Problem Minimise $\sum_{i=1}^{m}\sum_{j=1}^{n} c_{ij} x_{ij}$ subject to $\sum_j x_{ij} = a_i$ (supply), $\sum_i x_{ij} = b_j$ (demand), $x_{ij} \ge 0$. Balanced: $\sum a_i = \sum b_j$.

Initial BFS methods:

  • North-West Corner Rule (NWCR): Start at top-left; allocate as much as possible, then move right or down.
  • Vogel's Approximation Method (VAM): Compute row/column penalties (difference between two smallest costs), allocate to the cell with minimum cost in the row/column with largest penalty. Gives near-optimal starting solutions.

Optimality test — MODI method: Compute dual variables $u_i, v_j$ from basic cells ($u_i + v_j = c_{ij}$). For non-basic cells, check $\Delta_{ij} = c_{ij} - u_i - v_j \ge 0$. If some $\Delta_{ij} < 0$, perform a loop-based pivot.

◆ Assignment Problem & Hungarian Method
Definition — Assignment Problem Given an $n \times n$ cost matrix $[c_{ij}]$, assign each worker to exactly one job (and vice versa) to minimise total cost: $\min \sum_{i,j} c_{ij} x_{ij}$ where $x_{ij} \in \{0,1\}$, $\sum_j x_{ij} = 1$, $\sum_i x_{ij} = 1$.

Hungarian method:

  • Step 1: Subtract row minima, then column minima.
  • Step 2: Cover all zeros with minimum number of lines.
  • Step 3: If $n$ lines needed, optimal assignment exists among the zeros. Otherwise, adjust: subtract the smallest uncovered element from all uncovered entries and add it to doubly-covered entries. Repeat.
★ Example
Solve the assignment problem with cost matrix $C = \begin{pmatrix} 8 & 4 & 2 \\ 4 & 2 & 6 \\ 6 & 8 & 4 \end{pmatrix}$.
Solution: Subtract row minima: rows become $(6,2,0)$, $(2,0,4)$, $(2,4,0)$. Subtract column minima (col 1 min = 2): $(4,2,0)$, $(0,0,4)$, $(0,4,0)$. Cover zeros: lines through row 2, col 1, col 3 cover all zeros (3 lines for $3 \times 3$). Optimal assignment: $1 \to 3$ (cost 2), $2 \to 2$ (cost 2), $3 \to 1$ (cost 6). Total = 10.
05 Game Theory

Two-person zero-sum games model adversarial decision-making. The minimax theorem guarantees the existence of optimal mixed strategies.

◆ Two-Person Zero-Sum Games
Definition — Payoff Matrix & Saddle Point In a two-person zero-sum game with payoff matrix $A = [a_{ij}]$, Player I chooses row $i$, Player II chooses column $j$, and Player I receives $a_{ij}$ (Player II pays). A saddle point is an entry $a_{i^*j^*}$ that is simultaneously the minimum in its row and the maximum in its column: $\max_i \min_j a_{ij} = \min_j \max_i a_{ij} = a_{i^*j^*}$.
Theorem — Minimax Theorem (von Neumann) For every finite two-person zero-sum game, there exist mixed strategies $\mathbf{p}^*$ for Player I and $\mathbf{q}^*$ for Player II such that: $$\max_{\mathbf{p}} \min_{\mathbf{q}} \mathbf{p}^T A \mathbf{q} = \min_{\mathbf{q}} \max_{\mathbf{p}} \mathbf{p}^T A \mathbf{q} = v$$ where $v$ is the value of the game.
◆ Mixed Strategies & LP Formulation

A mixed strategy is a probability distribution over pure strategies. Player I uses $\mathbf{p} = (p_1, \ldots, p_m)$ with $\sum p_i = 1$, $p_i \ge 0$.

Finding the optimal mixed strategy for Player I reduces to an LP:

  • $\max\, v$ subject to $\sum_i p_i a_{ij} \ge v$ for all $j$, $\sum_i p_i = 1$, $p_i \ge 0$.

Player II's problem is the dual of Player I's.

★ Example
Find the value and optimal strategies for the game with payoff matrix $A = \begin{pmatrix} 3 & -1 \\ -2 & 4 \end{pmatrix}$.
Solution: No saddle point ($\max\min = -1$, $\min\max = 3$). For Player I: $p$ plays row 1 with probability $p$. Against column 1: $3p - 2(1-p) = 5p - 2$. Against column 2: $-p + 4(1-p) = 4 - 5p$. Set equal: $5p - 2 = 4 - 5p \Rightarrow p = 3/5$. Value $v = 5(3/5) - 2 = 1$. For Player II: $q$ plays col 1 with probability $q$. $3q - (1-q) = 4q - 1$ and $-2q + 4(1-q) = 4 - 6q$. Set equal: $4q - 1 = 4 - 6q \Rightarrow q = 1/2$. Check: $v = 4(1/2) - 1 = 1$.
06 Convex Optimisation

Convex optimisation generalises LP to nonlinear objectives and constraints while preserving the powerful property that every local minimum is global.

◆ Convex Sets & Functions
Definition — Convex Set A set $C \subseteq \mathbb{R}^n$ is convex if for all $x, y \in C$ and $\lambda \in [0,1]$: $\lambda x + (1-\lambda)y \in C$.
Definition — Convex Function A function $f: C \to \mathbb{R}$ (where $C$ is convex) is convex if $f(\lambda x + (1-\lambda)y) \le \lambda f(x) + (1-\lambda)f(y)$ for all $x, y \in C$, $\lambda \in [0,1]$. If $f$ is twice differentiable, $f$ is convex iff the Hessian $\nabla^2 f(x) \succeq 0$ (positive semidefinite) for all $x$.
Theorem For a convex function $f$ on a convex set $C$, every local minimum is a global minimum. If $f$ is strictly convex, the global minimum (if it exists) is unique.
◆ KKT Conditions
Theorem — Karush-Kuhn-Tucker (KKT) Conditions Consider $\min\, f(x)$ subject to $g_i(x) \le 0$, $h_j(x) = 0$. Under a constraint qualification (e.g., Slater's condition for convex problems), $x^*$ is optimal if and only if there exist $\mu_i \ge 0$, $\lambda_j$ such that:
(i) Stationarity: $\nabla f(x^*) + \sum_i \mu_i \nabla g_i(x^*) + \sum_j \lambda_j \nabla h_j(x^*) = 0$.
(ii) Primal feasibility: $g_i(x^*) \le 0$, $h_j(x^*) = 0$.
(iii) Dual feasibility: $\mu_i \ge 0$.
(iv) Complementary slackness: $\mu_i g_i(x^*) = 0$.
★ Example
Minimise $f(x,y) = x^2 + y^2$ subject to $x + y \ge 1$ using KKT conditions.
Solution: Rewrite constraint as $g(x,y) = 1 - x - y \le 0$. KKT: $\nabla f + \mu \nabla g = 0$ gives $(2x - \mu, 2y - \mu) = (0,0)$, so $x = y = \mu/2$. Complementary slackness: $\mu(1 - x - y) = 0$. If $\mu = 0$: $x = y = 0$, but $g(0,0) = 1 > 0$ (infeasible). So $\mu > 0$ and $x + y = 1$: $\mu/2 + \mu/2 = 1 \Rightarrow \mu = 1$, $x = y = 1/2$. Minimum $f = 1/4 + 1/4 = 1/2$.
★ Key Takeaways
✎ Practice Problems
Problem 1
An LP has the feasible region defined by $x_1 + 2x_2 \le 8$, $3x_1 + 2x_2 \le 12$, $x_1, x_2 \ge 0$. Find the maximum of $z = 4x_1 + 5x_2$.
Show Solution ▼
Corner points: $(0,0)$, $(4,0)$, $(2,3)$, $(0,4)$. Intersection of $x_1 + 2x_2 = 8$ and $3x_1 + 2x_2 = 12$: $2x_1 = 4$, $x_1 = 2$, $x_2 = 3$. Values: $z(0,0) = 0$, $z(4,0) = 16$, $z(2,3) = 23$, $z(0,4) = 20$. Maximum $z^* = 23$ at $(2, 3)$.
Problem 2
Write the dual of: Maximise $z = 2x_1 + 3x_2$ subject to $x_1 + x_2 \le 4$, $2x_1 + x_2 \le 6$, $x_1, x_2 \ge 0$. Verify strong duality by solving both.
Show Solution ▼
Dual: Minimise $w = 4y_1 + 6y_2$ subject to $y_1 + 2y_2 \ge 2$, $y_1 + y_2 \ge 3$, $y_1, y_2 \ge 0$. Primal optimal: corner points $(0,0), (3,0), (2,2), (0,4)$. At $(2,2)$: both constraints tight, $z = 10$. At $(0,4)$: $z = 12$. But $(0,4)$: check $2(0) + 4 = 4 \le 6$ yes. $z(0,4) = 12$. Dual: $y_1 + 2y_2 = 2$, $y_1 + y_2 = 3$ gives $y_2 = -1$ (infeasible). By complementary slackness with $x_2^* > 0$: $y_1 + y_2 = 3$. With $x_1^* = 0$, first dual constraint may be slack. Try: constraint 1 tight ($y_1 = 4 - 0 - 4 = 0$... let me recalculate). Primal: $(0,4)$ has $0 + 4 = 4$ (constraint 1 tight), $0 + 4 = 4 \le 6$ (slack). So $y_2 = 0$. Then $y_1 \ge 2$ and $y_1 \ge 3$, giving $y_1 = 3$. $w = 4(3) + 6(0) = 12 = z^*$. Strong duality verified.
Problem 3
Solve the transportation problem: 3 sources with supply $(20, 30, 25)$, 3 destinations with demand $(15, 25, 35)$, cost matrix $\begin{pmatrix} 2 & 7 & 4 \\ 3 & 3 & 1 \\ 5 & 4 & 7 \end{pmatrix}$. Use NWCR for initial BFS, then test optimality with MODI.
Show Solution ▼
Balanced ($\sum = 75$). NWCR: $x_{11} = 15$, $x_{12} = 5$, $x_{22} = 20$, $x_{23} = 10$, $x_{33} = 25$. Cost = $15(2) + 5(7) + 20(3) + 10(1) + 25(7) = 30 + 35 + 60 + 10 + 175 = 310$. MODI: set $u_1 = 0$. From basic cells: $v_1 = 2, v_2 = 7, u_2 = -4, v_3 = 5, u_3 = 2$. Check non-basic: $\Delta_{13} = 4 - 0 - 5 = -1 < 0$ (not optimal). Enter $x_{13}$, form loop $x_{13} \to x_{12} \to x_{22} \to x_{23}$: adjust by $\min(5, 10) = 5$. New solution: $x_{11} = 15, x_{13} = 5, x_{22} = 25, x_{23} = 5, x_{33} = 25$. Cost = 30 + 20 + 75 + 5 + 175 = 305. Re-check MODI for further improvement.
Problem 4
Find the value and optimal mixed strategies for the game $A = \begin{pmatrix} 1 & 3 \\ 4 & 2 \end{pmatrix}$.
Show Solution ▼
No saddle point ($\max\min = 2$, $\min\max = 3$). Player I: $E_1 = p + 4(1-p) = 4 - 3p$, $E_2 = 3p + 2(1-p) = p + 2$. Set $4 - 3p = p + 2$: $4p = 2$, $p = 1/2$. Value $v = 4 - 3/2 = 5/2$. Player II: $E_1 = q + 3(1-q) = 3 - 2q$, $E_2 = 4q + 2(1-q) = 2q + 2$. Set $3 - 2q = 2q + 2$: $4q = 1$, $q = 1/4$. Check: $v = 3 - 1/2 = 5/2$. Value $= 5/2$, $\mathbf{p}^* = (1/2, 1/2)$, $\mathbf{q}^* = (1/4, 3/4)$.
Problem 5
Minimise $f(x_1, x_2) = (x_1 - 3)^2 + (x_2 - 2)^2$ subject to $x_1 + x_2 \le 4$, $x_1, x_2 \ge 0$ using KKT conditions.
Show Solution ▼
$f$ is strictly convex (Hessian $= 2I$). Constraints: $g_1 = x_1 + x_2 - 4 \le 0$, $g_2 = -x_1 \le 0$, $g_3 = -x_2 \le 0$. Unconstrained minimum at $(3, 2)$: check $3 + 2 = 5 > 4$ (infeasible). So $g_1$ is active. KKT stationarity: $2(x_1 - 3) + \mu_1 - \mu_2 = 0$ and $2(x_2 - 2) + \mu_1 - \mu_3 = 0$. Try $\mu_2 = \mu_3 = 0$ (interior to $x_1, x_2 \ge 0$): $x_1 = 3 - \mu_1/2$, $x_2 = 2 - \mu_1/2$. From $x_1 + x_2 = 4$: $5 - \mu_1 = 4$, $\mu_1 = 1 > 0$. So $x_1 = 5/2$, $x_2 = 3/2$. Both positive, so $\mu_2 = \mu_3 = 0$ is consistent. $f^* = (5/2 - 3)^2 + (3/2 - 2)^2 = 1/4 + 1/4 = 1/2$.
🎯 Interactive Quiz
1. In a linear program, the optimal solution (if finite) must occur at:
A The centroid of the feasible region
B A vertex (extreme point) of the feasible region
C The midpoint of an edge
D Any interior point
2. In the simplex method, which condition indicates that the LP is unbounded?
A All reduced costs are non-negative
B The entering variable's column has all non-positive entries
C A basic variable equals zero
D Two variables have equal reduced costs
3. Strong duality in linear programming states that:
A The primal optimal is always less than or equal to the dual optimal
B The primal and dual optimal values are equal
C The dual of the dual is the primal
D The optimal solution is unique
4. In the Hungarian method for the assignment problem, the algorithm terminates when:
A All entries in the reduced matrix are zero
B The minimum number of lines to cover all zeros equals $n$
C There are exactly $n$ zeros in the matrix
D All row minima have been subtracted
5. Which of the following is NOT a KKT condition?
A Stationarity of the Lagrangian
B Complementary slackness
C The Hessian of the Lagrangian must be positive definite
D Dual feasibility ($\mu_i \ge 0$)