Linear Programming

UPSC Mathematics Optional · Paper II · LPP, Duality, Transportation & Game Theory

1. LPP Formulation & Standard Form 2. Graphical Method 3. Simplex Method 4. Big-M & Two-Phase Methods 5. Duality Theory 6. Sensitivity Analysis 7. Transportation Problem 8. Assignment Problem 9. Game Theory

§1 · LPP Formulation & Standard Form

General LPP

Maximize (or minimize) \(Z=\mathbf{c}^T\mathbf{x}\) subject to \(A\mathbf{x}\le\mathbf{b}\) (or \(=\), \(\ge\)), \(\mathbf{x}\ge\mathbf{0}\).

Standard form (for Simplex): \(A\mathbf{x}=\mathbf{b}\), \(\mathbf{x}\ge\mathbf{0}\), \(\mathbf{b}\ge\mathbf{0}\).

Convert: \(\le\) → add slack variable; \(\ge\) → subtract surplus + add artificial; \(=\) → add artificial.

Fundamental Theorems of LPP PYQ★★★

If a feasible solution exists, a basic feasible solution (BFS) exists.
If an optimal solution exists, an optimal BFS exists (optimum at a vertex).
The feasible region is a convex set. Optimal occurs at extreme point (corner).
A BFS corresponds to a vertex of the feasible polytope.

§2 · Graphical Method

Graphical Method (2 variables) PYQ★★★

Plot each constraint as a line; shade feasible region.
Evaluate objective function at each corner point.
Optimal is at a corner (or along an edge if objective is parallel to a constraint).
Unbounded region: check if objective can go to \(\infty\) — if so, no optimal.

§3 · Simplex Method

Simplex Algorithm Steps PYQ★★★

Start with initial BFS (identity columns for basic variables).
Optimality check: All \(\bar c_j=c_j-c_B^TB^{-1}A_j\ge 0\) (minimization) → optimal.
Entering variable: most negative \(\bar c_j\) (Bland's rule: smallest index if cycling).
Leaving variable: min-ratio test: \(\min\left\{\dfrac{\bar b_i}{\bar a_{ij}}:\bar a_{ij}>0\right\}\).
Pivot: row reduce to make entering column a unit vector.
Degenerate BFS: \(\bar b_i=0\) for some \(i\) → possible cycling; use Bland's rule.

§4 · Big-M & Two-Phase Methods

Handling Artificial Variables PYQ★★

Big-M method: Add artificial variables \(a_i\) with coefficient \(M\) (very large) in objective. If optimal solution has \(a_i>0\) → infeasible LPP.

Two-phase method:
Phase I: Minimize \(\sum a_i\) s.t. constraints. If min \(>0\) → infeasible.
Phase II: Use phase I optimal BFS as starting point; optimize original objective.

§5 · Duality Theory

Primal-Dual Construction PYQ★★★

Primal: Max \(\mathbf{c}^T\mathbf{x}\), s.t. \(A\mathbf{x}\le\mathbf{b}\), \(\mathbf{x}\ge\mathbf{0}\).

Dual: Min \(\mathbf{b}^T\mathbf{y}\), s.t. \(A^T\mathbf{y}\ge\mathbf{c}\), \(\mathbf{y}\ge\mathbf{0}\).

Dual of dual = primal.
\(\le\) primal constraint ↔ \(\ge 0\) dual variable.
\(\ge\) primal constraint ↔ \(\le 0\) dual variable.
\(=\) primal constraint ↔ unrestricted dual variable.
Primal unrestricted variable ↔ dual \(=\) constraint.

Weak & Strong Duality PYQ★★★

Weak: Any primal feasible \(\mathbf{x}\) and dual feasible \(\mathbf{y}\): \(\mathbf{c}^T\mathbf{x}\le\mathbf{b}^T\mathbf{y}\).

Strong: If primal has optimal \(\mathbf{x}^*\) and dual has optimal \(\mathbf{y}^*\): \(\mathbf{c}^T\mathbf{x}^*=\mathbf{b}^T\mathbf{y}^*\).

Complementary Slackness: At optimality: \(y_i(b_i-A_i\mathbf{x})=0\) and \(x_j(A^T_j\mathbf{y}-c_j)=0\).

§6 · Sensitivity Analysis

Sensitivity / Post-Optimality PYQ★★

Range for \(c_j\) (obj. coefficient): how much can it change before current basis changes?
Range for \(b_i\) (RHS): how much can it change keeping current basis feasible?
Shadow price (dual variable \(y_i\)): increase in optimal value per unit increase in \(b_i\).
Reduced cost \(\bar c_j\): amount by which \(c_j\) must improve for \(x_j\) to enter basis.

§7 · Transportation Problem

Transportation Problem Setup PYQ★★★

Minimize \(\sum_{i,j}c_{ij}x_{ij}\) s.t. \(\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\). If not balanced, add dummy row/column with 0 cost.

A BFS has \(m+n-1\) allocations (non-degenerate).

Initial BFS Methods PYQ★★★

Northwest Corner: Start top-left, allocate max possible, move right or down.
Minimum Cost (Least Cost): Allocate to cheapest cell first.
Vogel's Approximation (VAM): Compute penalty = difference of two smallest costs in each row/col. Allocate to min-cost cell in max-penalty row/col. Best initial BFS.

Optimality Test — MODI / UV Method PYQ★★★

Assign \(u_i+v_j=c_{ij}\) for basic cells (set \(u_1=0\)). Compute \(d_{ij}=c_{ij}-u_i-v_j\) for non-basic cells.

Optimal iff all \(d_{ij}\ge 0\). If any \(d_{ij}<0\): enter that cell, form a loop, reallocate \(\theta\) (min of alternating cells with \(-\theta\)).

§8 · Assignment Problem

Hungarian Method PYQ★★★

Row reduction: subtract row minimum from each row.
Column reduction: subtract column minimum from each column.
Cover all zeros with minimum number of lines. If lines = \(n\): optimal (assign on zeros).
If lines \(

Maximization: convert to minimization by subtracting all entries from max element.

§9 · Game Theory

Two-Person Zero-Sum Game PYQ★★★

Payoff matrix \(A\) (player I's gain = player II's loss). Player I: max; Player II: min.

Saddle point: \(a_{ij}^*\) is simultaneously row-max of its row and col-min of its column. Value of game \(v=a_{ij}^*\).

Saddle point exists iff \(\max_i\min_j a_{ij}=\min_j\max_i a_{ij}\) (minimax = maximin).

Mixed Strategies PYQ★★★

If no saddle point: use mixed strategies \(\mathbf{p}=(p_1,\ldots,p_m)\) for player I, \(\mathbf{q}=(q_1,\ldots,q_n)\) for II.

Expected payoff \(E=\mathbf{p}^TA\mathbf{q}\). Player I maximizes, II minimizes.

For 2×2 matrix \(\begin{pmatrix}a&b\\c&d\end{pmatrix}\):

\(p_1=\dfrac{d-c}{a+d-b-c}\), \(p_2=1-p_1\). \(v=\dfrac{ad-bc}{a+d-b-c}\).

Dominance: If row \(i\) dominates row \(j\) (all entries \(\ge\)), player II will never use col \(j\) → reduce matrix.

Reduction to LPP: Player I: max \(v\) s.t. \(A^T\mathbf{p}\ge v\mathbf{1}\), \(\sum p_i=1\), \(\mathbf{p}\ge\mathbf{0}\).