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.

About these ads

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

The Rubric Theme Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: