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

_{}

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:

** 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

_{}

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

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 x _{1}, x_{2},…, x_{n}
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 *b _{j}* 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:

_{}

*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:

* *

*Maximize:*

_{}

*subject to the constraints:*

* *

* *

_{}

If *(x _{1} , x_{2} ,…, x_{6})*
is a solution to this new problem, then

_{}

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

_{}

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, 4 ^{th}
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 *x _{1} *or

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 *x _{4}* is no longer basic because it had a 1 in the same row
as the pivot. It is called the

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 *x*_{1} 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 *x _{1}*,

_{}

The corresponding basic feasible solution (setting *x _{3}=x_{4}=x_{5}=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 *x _{3}*,

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.