MATH 340 Lecture Notes - Lecture 7: Slack Variable, Linear Programming
Document Summary
Started discussing this last time, with the example: maximize 2x1 x2 subject to, x1 + x2 1, x1 2x2 2, x2 1, x1, x2 0. Setting up the slack variables gives us an infeasible dictionary, i. e. one where putting in x1 = x2 = 0 is not a feasible solution: x3 = 1 +x1 x2 x4 = 2 +x1 +2x2. What we said we should do is introduce an auxiliary lp with the goal of nding us a feasible dictionary. The idea is to add some wiggle room in the form of an extra variable x0, to the right-hand side of our initial constraints. Then we get the constraints: x1 + x2 1 + x0, x1 2x2 2 + x0, x2 1 + x0. Here you can see why i"m thinking of it as wiggle room - if we make x0 really big, our inequalities become less stringent, and it"s easier to nd feasible solutions.
