# Mathematics Prelims

## June 4, 2009

### Linear Programming, Part II – Slack and Surplus

Filed under: Linear Programming — cjohnson @ 6:57 pm

Recall from last time that a linear program is an optimization problem of the form

Maximize $c^T x$

Subject to $Ax \leq b$ and $x \geq 0$

Where the system of constraints $Ax \leq b$ is just a convenient way to write something of the form

$\displaystyle a_{11} x_1 + a_{12} x_2 + ... + a_{1n} x_n \leq b_1$

$\displaystyle a_{21} x_1 + a_{22} x_2 + ... + a_{2n} x_n \leq b_2$

$\displaystyle \vdots$

$\displaystyle a_{m1} x_1 + a_{m2} x_2 + ... + a_{mn} x_n \leq b_m$

Notice that our use of maximization, instead of minimization, is immaterial as any maximization problem can be turned into an equivalent minimization problem and vice versa.  The problem of maximizing $f(x)$ is equivalent (has precisely the same solutions) as the problem of minimizing $-f(x)$.

Likewise, our use of $\leq$ inequalities instead of $\geq$ is more a matter of taste and convenience than necessity: $f(x) \leq b$ is the same thing as $-f(x) \geq -b$.  What we would like to do, though, is get rid of those inequalities altogheter.  If we can turn these constraints into a system of equations of the form $Ax = b$, then we’ll be able to apply techniques from linear algebra to help us manipulate the LP (linear program).  Later we’ll see how to cleverly use elementary row operations to traverse the set of potential optimal solutions.  But first we have to lose those nasty little inequalities.

So here’s the idea: say we have $x \leq 5$.  We can turn this into an equation by inserting a non-negative variable, $y$, which equals $5 - x$.  That is, $y$ takes up the slack left by $x$, and $x \leq 5$ becomes $x + y = 5$.  Algebraically, if we set $y = 5 - x$, we have $x + y = x + (5 - x) = 5$ and that’s why we have equality.

If our inequality goes the other way, say $x \geq 7$, we’ll just subtract off the surplus: set $y = x - 7$ (note that this means $y \geq 0$) and so $x \geq 7$ becomes $x - y = 7$.  So in the system of inequalities above we can get a system of equations by tacking on a slack, or taking out the surplus, for each inequality.  The earlier system then becomes

$\displaystyle a_{11} x_1 + a_{12} x_2 + ... + a_{1n} x_n + s_1 = b_1$

$\displaystyle a_{21} x_1 + a_{22} x_2 + ... + a_{2n} x_n + s_2 = b_2$

$\displaystyle \vdots$

$\displaystyle a_{m1} x_1 + a_{m2} x_2 + ... + a_{mn} x_n + s_m = b_m$

Where $s_i$ is the slack (surplus) we add (subtract) for the $i$-th constraint.  Now our matrices will of course have to change a little bit to take these new variables into account.  Originally, $A$ was an $m \times n$ matrix, $x$ was a $n$-vector, and $b$ was a $m$-vector.  For our system of equations we’ll let $\hat{A} = [ A, \, I ]$ and $\hat{x} = [ x, \, s_1, \, ..., \, s_m ]^T$ where $I$ is the $m \times m$ identity matrix; note that $b$ doesn’t change.  Note too that we append the identity because we have only slack variables; if some of those had been surplus variables, the corresponding entries we append would be negative.

So by throwing in an extra variable for each inequality constraint we have a system of equations which is amenable to the techniques of linear algebra.  If it were to happen that the resultant matrix was invertible (which requires it to be square — an equal number of equations and unknowns) then we could just multiply by the inverse and find the solution.  This doesn’t work for our general problem though since there will normally be infinitely many possible solutions.  Our goal will be to weed out the best solution from those possibilities.  In the next post we’ll look at this space of possible solutions.