Linear Programming
Linear Programming in GATE MA covers formulation, the simplex method, duality, and network models (transportation, assignment) plus two-person zero-sum games. Expect small numerical LPs and duality checks.
Core rules
- Standard form: maximize c^T x subject to Ax≤b, x≥0; add slack variables to get equality constraints.
- Simplex moves between basic feasible solutions; optimality holds when all reduced costs are ≤0 for maximization.
- Dual of max c^T x, Ax≤b, x≥0 is min b^T y, A^T y≥c, y≥0.
- Strong duality: if either problem has a finite optimum, both do and the optimal values are equal.
- Complementary slackness: x_j>0 implies the j-th dual constraint is tight; y_i>0 implies the i-th primal constraint is tight.
- The transportation problem is a special LP; the assignment problem is a 0-1 LP solved by the Hungarian method.
Worked example
Maximize 3x+2y subject to x+y≤4, x≤2, y≤3, x,y≥0. Vertices include (0,0), (2,0), (2,2), (1,3), (0,3). Values: 0, 6, 10, 9, 6. The maximum is 10 at (2,2). The dual variables for x+y≤4 and x≤2 are positive, and both constraints are tight there.
Traps
- An LP can be infeasible or unbounded; do not assume a finite optimum from the constraints alone.
- Degeneracy can cause cycling in naive simplex; Bland's rule prevents it.
- The LP relaxation of an integer program may give fractional solutions; rounding is not generally optimal.
- In game theory, the value is unique but optimal mixed strategies need not be.