# Linear Programming

CREATED: 200904010235 Speaker: Leong Hon Wai ** Linear Programming

- minimizing a linear objective function, subject to a finite number of linear equality and inequality constraints
- network flow, MST is linear programming
- constraints define a feasible set, optimal solution occurs at corner of feasible set
- forms of LP ** canonical form $\min cx$ subject to $Ax \ge r, x \ge 0$ ** standard form $\min cs$ subject to $Ax = 0, x \ge 0$, may need to introduce slack variables