Application to Linear Programming

Introduction Many real-life problems consist of maximizing or minimizing a certain quantity subject to some constraints. Linear programming is one approach to this kind of problem. We will see examples in which we are maximizing or minimizing a linear expression in any number of variables subject to some linear constraints. This technique is applied to a wide variety of problems in industry and science.

1) Case of two variables only: a geometric approach

General problem Given a linear expression z=ax+by in two variables x and y, find values of x and y that either maximize or minimize z subject to the linear constraints:

and

(In the above conditions, any one of the symbols can be used). The function z in the above problem is called the objective function. If (x, y) satisfies all the constraints, then it is called a feasible solution. The set of all feasible solutions is a subset of the xy-plane called the feasible region.

Note that each constraint of the form ax+by=c represents a straight line in the xy-plane, whereas each constraint of the form  defines a half-plane that includes its boundary line .

The feasible region is then an intersection of finitely many lines and half-planes. If the feasible region can be enclosed in a sufficiently large circle, it is called bounded; otherwise it is called unbounded.

If a feasible region is empty (contains no points), then the constraints are inconsistent and the problem has no solution.  The extreme points of a feasible region are those boundary points that are intersections of the straight-line boundary segments of the region. In a linear programming problem, the following theorem tells us when we will be successful and what points to search for:

# If the feasible region of a linear programming problem is nonempty and bounded, then the objective function attains both a maximum and minimum value and these occur at extreme points of the feasible region. If the feasible region is unbounded, then the objective function may or may not attain a maximum or minimum value; however, if it attains a maximum or minimum value, it does so at an extreme point.

Example 1 A candy manufacturer has 130 pounds of chocolate-covered cherries and 170 pounds of chocolate-covered mints in stock. He decides to sell them in the form of two different mixtures. One mixture will contain half cherries and half mints by weight and will sell for \$2.00 per pound. The other mixture will contain one-third cherries and two-thirds mints by weight and will sell for \$1.25 per pound. How many pounds of each mixture should the candy manufacturer prepare in order to maximize his sales revenue?

Solution For simplicity, let us call A the mixture of half cherries and half mints, and B the mixture which is one-third cherries and two-thirds mints. Let x be the number of pounds of A to be prepared and y the number of pounds of B to be prepared. The revenue function can then be written as

Since each pound of A contains one-half pound of cherries and each pound of B contains one-third pound of cherries, the total number of pounds of cherries used in both mixtures is

Similarly, the total number of pounds of mints used in both mixtures is:

Now, since the manufacturer can use at most 130 pounds of cherries and 170 pounds of mints, we have the constraints:

Also, we must have  Therefore, the above problem can be formulated as follows: find x and y that maximize  subject to the constraints:

To solve the problem, we will use the technique of linear programming described above. We start by drawing the feasible region of the problem and locate our extreme points:

Since the feasible region is bounded in this case, we are sure that the optimal solution is attained at one of the extreme points shown on the diagram above. So we evaluate the objective function at each of these points:

 Extreme point Value of z=2x+1.25y (0, 0) 0 (0, 255) 318.75 (180, 120) 510.00 (260, 0) 520.00

The table shows that the largest value for z is 520.00 and the corresponding optimal solution is (260, 0). Thus the candy manufacturer attains maximum sales of \$520 when he produces 260 pounds of mixture A and none of mixture B.

Example 2 The Osgood County refuse department runs two recycling centers. Center 1 costs \$40 to run for an eight hour day. In a typical day 140 pounds of glass and 60 pounds of aluminum are deposited at Center 1. Center 2 costs \$50 for an eight-hour day, with 100 pounds of glass and 180 pounds of aluminum deposited per day. The county has a commitment to deliver at least 1540 pounds of glass and 1440 pounds of aluminum per week to encourage a recycler to open up a plant in town. How many days per week should the county open each center to minimize its cost and still meet the recycler’s needs?

Solution. Let x be the number of days per week Center 1 is open and y be the number of days per week Center 2 is open. The linear programming problem associated with this question is as follows:

Minimize the function

(Cost of operating the two centers)

subject to the constraints:

The feasible region of the problem, together with the extreme points are shown in the following diagram

The region is unbounded, with three finite extreme points. Two are easy to obtain from the graph:

(0, 15.4) and (24, 0). The third is found algebraically to be: (6.94, 5.69). Also, we can assume that there is other  “infinite extreme points” since the region is unbounded. One can see  that these infinite extreme points are not going to be “optimal” since we are minimizing and not maximizing. So we evaluate the objective function at each of the finite extreme points:

 Extreme point Value of z=40x+50y (0, 15.4) 770 (24, 0) 960 (6.94, 5.69) 562.10

So, the minimal cost is \$562.10 and it is attainted when Center 1 is open for about 7 days a week (eight-hours a day) and Center 2 is open for about 6 days a week (eight-hours a day) .

2) Linear programming with more than two variables

It is also possible to solve a linear programming problem in three variables graphically, but the corner points become more difficult to locate visually. It is impossible however to solve a problem with more than three variables using our graphical method. The corner points of the feasible region must be found somehow using algebra and then checked to find the optimal value. The Simplex algorithm developed by Danzig solves the problem using this idea.

Discovered by George Dantzig in the 40’s, the simplex algorithm is a efficient method of solving linear programming problems which does just this. The idea is to identify certain “basic” feasible points and to prove that the maximum value (if it exists) of the objective function f occurs at one of these points. We will explain the algorithm only for a standard linear programming problem which can be formulated as follows:

Maximize the objective function:

of the variables x1, x2,…, xn subject to the constraints:

In the above form, the fact that the objective function is linear is crucial, but the condition that the variables are nonnegative and the fact that we are maximizing f and not minimizing it are not severe restrictions. The condition that the constants bj are nonnegative is serious although it is satisfied in many practical applications. For the nonstandard case, please see some of the links below.

Let us describe this algorithm with an example:

### Maximize:

subject to the constraints:

Solution The first step is to convert the inequalities in the above constraints into equalities. This can be done be adding new variables: x4, x5 and x6 called the slack variables, one in each constraint. In  this way, we obtain a new problem:

Maximize:

subject to the constraints:

If (x1 , x2 ,…, x6) is a solution to this new problem, then (x1, x2, x3) is a solution to the original problem. Indeed, the constraints are clearly satisfied. Moreover, if (y1, y2, y3) were another feasible point for the original problem yielding a larger value of f, then taking

would give a feasible point  for the new problem yielding a larger value for f, which is a contradiction. So it suffices to solve the new problem. For this, write the relation  as a fourth equation to get the linear system in which f is treated as yet another variable:

The augmented matrix of the above system is:

This is called the initial simplex tableau for the problem. We will use elementary row operations to create a sequence of such tableaux keeping f in the bottom row. This is analogous to the modification of the augmented matrix in Gaussian elimination, except that here we allow only feasible solutions.

Note that the way the slack variables were introduced guarantees that the columns corresponding to these variables all consist of 0’s and a single 1 and that the 1’s are in different rows. These columns will be called basic columns and the slack variables are called the basic variables in the initial tableau (they are indicated by  in the above tableau). Because of this, there is one obvious solution to the equations: set all the nonbasic variables equal to zero and solve for the basic variables:

In other words, (0,0,0,6,9,20) is a feasible solution yielding f=0. Such a solution (with all nonbasic variables equal to zero) is called a basic feasible solution. Note that the bottom entry in the last column is the value of f  at the basic feasible solution (0 in this case). The key to the whole algorithm is the following theorem (for a proof, the reader is referred to any textbook on linear programming such as S.I. Gass, Linear Programming, 4th edition):

If a standard linear programming problem has a solution, then there is a basic feasible solution that yields the maximum value of the objective function. Such basic feasible solutions are called optimal.

Hence our goal is to find an optimal basic feasible point. Our construction using slack variables guarantees an initial basic feasible solution; we check next if it is optimal.

The bottom row of the initial tableau gives f in terms of the nonbasic variables

The fact that some of the coefficients here are positive suggests that this value of f  is not optimal since increasing x1 or x2 will increase f. It would seem better to increase x2 in this case since it has the larger of the two positive coefficients (equivalently, the most negative entry in the last row of the tableau). This in turn suggests that we try to modify the tableau so that x2 becomes a new basic variable. For this reason, x2  is called the entering variable. Its column is called the pivot column.

This modification is accomplished by doing elementary row operations to convert the pivot column into a basic column. The question is where to locate the 1. We don’t put the 1 in the last row because we don’t want to disturb f, but it can be placed at any other location in the pivot column where the present entry is nonzero (in the above example they all qualify). The chosen entry is called the pivot, and one chooses it as follows:

1.      The pivot entry must be positive.

2.      Among the positive entries available, the pivot is the one that produces the smallest ratio when divided into the right-most entry in its row.

Returning to our example, we rewrite the initial tableau and put a  symbol around the pivot entry. The ratios corresponding to the two positive entries in the pivot column (column 2 here) are shown on the right. No ratio is computed for row 2, because the corresponding entry in the pivot column is negative. One can see then that the pivot is 2.

Now perform elementary operations to convert the pivot to 1 and all other entries in its column to 0. This results in:

Note that the former basic variable x4 is no longer basic because it had a 1 in the same row as the pivot. It is called the departing variable. The new basic variables are x2, x5, and x6, and the new feasible solution (taking the new nonbasic variables equal to zero) is x2=0, x5=12, x6=11, and f=9. In other words, (0, 3, 0, 0, 12, 11) is the feasible solution yielding f=9.

This is better than before; f has increased from 0 to 9.

Now repeat the process. The last row here yields

so there is still hope of increasing f  by making x1 basic (it has a positive coefficient). Hence the first column is the pivot column and all three entries above the bottom row are positive. The tableau is displayed once more, with the ratios given and the next pivot (with the smallest ratio) is marked with a :

Row operations give the third tableau with x1, x2, x6 as basic variables.

The corresponding basic feasible solution (setting x3=x4=x5=0) is

In other words, (24/7, 9/7, 0, 0, 0, 65/7) is a feasible solution yielding f=75/7.

We claim that this is optimal. The last row of the third tableau gives

thus, as x3, x4 and x5 are nonnegative, f can be no greater than 75/7. The preceding solution achieves f=75/5, so it must be optimal. This completes the solution of the example.

For more on the simplex method, consult the following pages:

1.      The Simplex Method (A step by step description of the algorithm)

2.      Simplex Algorithm in 3D (Click to see a graphical approach in 3D)

3.      Interactive Demo (Use this Java Applet program to solve your linear programming problem)

References

ANTON, H. and C. RORRES. Elementary Linear Algebra: Applications Version, 8th ed. New York: John Wiley & Sons, Inc., 2000.

W. KEITH NICHOLSON. Linear Algebra with Applications, third ed. PWS Publishing Company, Boston, 1993.