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