Linear Programming:
The Simplex Method
In this
chapter, you will learn to:
1. Solve linear
programming maximization problems using
the simplex method.
2. Solve the
minimization problems using the simplex method.
4.1 Maximization By The Simplex Method
In the last chapter, we used the geometrical method to solve
linear programming problems, but the geometrical approach will not work for
problems that have more than two variables.
In real life situations, linear programming problems consist of literally
thousands of variables and are solved by computers. We can solve these problems algebraically,
but that will not be very efficient.
Suppose we were given a problem with, say, 5 variables and 10
constraints. By choosing all
combinations of five equations with five unknowns, we could find all the corner
points, test them for feasibility, and come up with the solution, if it
exists. But the trouble is that even for
a problem with so few variables, we will get more than 250 corner points, and
testing each point will be very tedious.
So we need a method that has a systematic algorithm and can be
programmed for a computer. The method
has to be efficient enough so we wouldn't have to evaluate the objective
function at each corner point. We have
just such a method, and it is called the simplex
method.
The simplex method was developed during the Second World War
by Dr. George Dantzig. His linear
programming models helped the Allied forces with transportation and scheduling
problems. In 1979, a Soviet scientist
named Leonid Khachian developed a method called the ellipsoid algorithm which
was supposed to be revolutionary, but as it turned out it is not any better
than the simplex method. In 1984,
Narendra Karmarkar, a research scientist at AT&T Bell Laboratories
developed Karmarkar's algorithm which has been proven to be four times faster
than the simplex method for certain problems.
But the simplex method still works the best for most problems.
The simplex method uses an approach that is very
efficient. It does not compute the value
of the objective function at every point, instead, it begins with a corner
point of the feasibility region where all the main variables are zero and then
systematically moves from corner point to corner point, while improving the
value of the objective function at each stage.
The process continues until the optimal solution is found.
To learn the simplex method, we try a rather unconventional
approach. We first list the algorithm,
and then work a problem. We justify the
reasoning behind each step during the process.
A thorough justification is beyond the scope of this course.
We start out with an example we solved in the last chapter
by the graphical method. This will
provide us with some insight into the simplex method and at the same time give
us the chance to compare a few of the feasible solutions we obtained previously
by the graphical method.
But first, we list the algorithm for the simplex method.
|
THE SIMPLEX
METHOD
1. Set
up the problem.
That is, write the objective function and the
constraints.
2. Convert the inequalities into equations.
This is done by adding one slack variable for each
inequality.
3. Construct
the initial simplex tableau.
Write the objective function as the bottom row.
4. The most negative entry in the bottom
row identifies a column.
5. Calculate the quotients. The smallest quotient identifies a
row. The element in the intersection
of the column identified in step 4 and the row identified in this step is
identified as the pivot element.
The quotients are computed by dividing the far right
column by the identified column in step 4.
A quotient that is a zero, or a negative number, or that has a zero in
the denominator, is ignored.
6. Perform
pivoting to make all other entries in
this column zero.
This is done the same way as we did with the
Gauss-Jordan method.
7. When
there are no more negative entries in the bottom row, we are finished;
otherwise, we start again from step 4.
8. Read
off your answers.
Get the variables using the columns with 1 and 0s. All other variables are zero. The maximum value you are looking for
appears in the bottom right hand corner.
|
And now,
Example 1 we solved in section 3.1.
uExample
1 Niki holds two
part-time jobs, Job I and Job II. She
never wants to work more than a total of 12 hours a week. She has determined that for every hour she
works at Job I, she needs 2 hours of preparation time, and for every hour she
works at Job II, she needs one hour of preparation time, and she cannot spend
more than 16 hours for preparation. If
she makes $40 an hour at Job I, and $30 an hour at Job II, how many hours
should she work per week at each job to maximize her income?
Solution: In solving this problem, we will follow the algorithm listed above.
1. Set up the problem. That is, write the objective function and
the constraints.
Since the simplex method is used for problems that consist
of many variables, it is not practical to use the variables x, y, z etc. We use the symbols x1, x2, x3, and so on.
Let
x1 = The number of hours per week Niki will work
at Job I.
and
x2 = The number of hours per week Niki will work
at Job II.
It is customary to choose the variable that is to be maximized
as Z.
The problem is formulated the same way as we did in the last
chapter.
Maximize
Z = 40x1 + 30x2
Subject to: x1 + x2 ≤ 12
2x1 + x2 ≤ 16
x1 ≥ 0; x2 ≥ 0
2. Convert
the inequalities into equations. This is done by adding one slack variable for
each inequality.
For example to convert the inequality x1 + x2 ≤ 12
into an equation, we add a non-negative variable y1,
and we get
x1 + x2 + y1 = 12
Here the variable y1 picks up the slack, and it represents the
amount by which x1 + x2 falls
short of 12. In this problem, if Niki
works fewer that 12 hours, say 10, then y1 is 2.
Later when we read off the final solution from the simplex table, the
values of the slack variables will identify the unused amounts.
We can even rewrite the objective function Z = 40x1 + 30x2 as – 40x1 – 30x2 + Z = 0.
After adding the slack variables,
our problem reads
Objective function: –
40x1 – 30x2 +
Z = 0
Subject
to constraints: x1 + x2 + y1 = 12
2x1 + x2 + y2 = 16
x1 ≥ 0; x2 ≥ 0
3. Construct
the initial simplex tableau.
Write the objective function as the bottom row.
Now that the inequalities are converted into equations, we
can represent the problem into an augmented matrix called the initial simplex
tableau as follows.
|
x1
|
x2
|
y1
|
y2
|
Z
|
C
|
|
1
|
1
|
1
|
0
|
0
|
12
|
|
2
|
1
|
0
|
1
|
0
|
16
|
|
–40
|
–30
|
0
|
0
|
1
|
0
|
Here the vertical line separates the left hand side of the
equations from the right side. The
horizontal line separates the constraints from the objective function. The right side of the equation is represented
by the column C.
The reader needs to observe that the last four columns of
this matrix look like the final matrix for the solution of a system of
equations. If we arbitrarily choose x1 = 0 and x2 = 0, we
get
Which reads
y1 = 12
y2 = 16
Z = 0
The solution obtained by arbitrarily assigning values to
some variables and then solving for the remaining variables is called the basic solution associated with the tableau. So the above solution is the basic solution
associated with the initial simplex tableau.
We can label the basic solution variable in the right of the last column
as shown in the table below.
|
x1
|
x2
|
y1
|
y2
|
Z
|
|
|
|
1
|
1
|
1
|
0
|
0
|
12
|
y1
|
|
2
|
1
|
0
|
1
|
0
|
16
|
y2
|
|
–40
|
–30
|
0
|
0
|
1
|
0
|
Z
|
4. The
most negative entry in the bottom row
identifies a column.
The most negative entry in the bottom row is –40, therefore
the column 1 is identified.
|
x1
|
x2
|
y1
|
y2
|
Z
|
|
|
|
1
|
1
|
1
|
0
|
0
|
12
|
y1
|
|
2
|
1
|
0
|
1
|
0
|
16
|
y2
|
|
–40
|
–30
|
0
|
0
|
1
|
0
|
Z
|
uQuestion Why do we choose the most
negative entry in the bottom row?
Answer The most negative entry in the bottom row
represents the largest coefficient in the objective function – the coefficient
whose entry will increase the value of the objective function the quickest.
The simplex method begins at a corner point where all the
main variables, the variables that have symbols such as x1, x2, x3 etc., are zero.
It then moves from a corner point to the adjacent corner point always
increasing the value of the objective function. In the case of the objective function Z = 40x1+
30x2, it will make more sense to increase
the value of x1 rather than x2. The variable x1 represents the number of hours per week Niki works at Job I. Since Job I pays $40 per hour as opposed to
Job II which pays only $30, the variable x1 will increase the objective function by $40
for a unit of increase in the variable x1.
5. Calculate
the quotients. The smallest quotient
identifies a row. The element in the
intersection of the column identified in step 4 and the row identified in this
step is identified as the pivot element.
As
mentioned in the algorithm, in order to calculate the quotient, we divide the
entries in the far right column by the entries in column 1, excluding the entry in the bottom
row.
|
x1
|
x2
|
y1
|
y2
|
Z
|
|
|
|
|
1
|
1
|
1
|
0
|
0
|
12
|
y1
|
12 ÷ 1 = 12
|
|
|
1
|
0
|
1
|
0
|
16
|
y2
|
¬ 16 ÷ 2 = 8
|
|
–40
|
–30
|
0
|
0
|
1
|
0
|
Z
|
|
The smallest of the two quotients, 12 and 8, is 8. Therefore row 2 is identified. The intersection of column 1 and row 2 is
the entry 2, which has been highlighted.
This is our pivot element.
uQuestion Why do we find quotients, and why does the
smallest quotient identify a row?
Answer When we choose the most negative entry in
the bottom row, we are trying to increase the value of the objective function
by bringing in the variable x1. But we cannot choose any value for x1. Can we
let x1 = 100?
Definitely not! That is because
Niki never wants to work for more than 12 hours at both jobs combined. In other words, x1 + x2 ≤ 12.
Now can we let x1 = 12?
Again, the answer is no because the preparation time for Job I is two
times the time spent on the job. Since
Niki never wants to spend more than 16 hours for preparation, the maximum time
she can work is 16 ÷ 2 = 8. Now you see the purpose of computing the
quotients.
uQuestion Why do we identify the pivot element?
Answer As we have mentioned earlier, the simplex
method begins with a corner point and then moves to the next corner point
always improving the value of the objective function. The value of the objective function is
improved by changing the number of units of the variables. We may add the number of units of one
variable, while throwing away the units of another. Pivoting allows us to do just that.
The variable whose units are being added is called the entering variable, and the variable whose units are
being replaced is called the departing
variable. The entering variable in the above table is
x1, and it was identified by the most
negative entry in the bottom row. The
departing variable y2 was
identified by the lowest of all quotients.
6. Perform
pivoting to make all other entries in
this column zero.
In chapter 2, we used pivoting to obtain the row echelon
form of an augmented matrix. Pivoting is
a process of obtaining a 1 in the location of the pivot element, and then
making all other entries zeros in that column.
So now our job is to make our pivot element a 1 by dividing the entire
second row by 2. The result follows.
|
x1
|
x2
|
y1
|
y2
|
Z
|
|
|
1
|
1
|
1
|
0
|
0
|
12
|
|
|
1/2
|
0
|
1/2
|
0
|
8
|
|
–40
|
–30
|
0
|
0
|
1
|
0
|
To obtain a zero in the entry first above the pivot element,
we multiply the second row by –1 and add it to row 1. We get
|
x1
|
x2
|
y1
|
y2
|
Z
|
|
|
0
|
1/2
|
1
|
–1/2
|
0
|
4
|
|
|
1/2
|
0
|
1/2
|
0
|
8
|
|
–40
|
–30
|
0
|
0
|
1
|
0
|
To obtain a zero in the element below the pivot, we multiply
the second row by 40 and add it to the last row.
|
x1
|
x2
|
y1
|
y2
|
Z
|
|
|
|
0
|
1/2
|
1
|
–1/2
|
0
|
4
|
y1
|
|
|
1/2
|
0
|
1/2
|
0
|
8
|
x1
|
|
0
|
–10
|
0
|
20
|
1
|
320
|
Z
|
We now determine the basic solution associated with this
tableau. By arbitrarily choosing x2 = 0 and y2 = 0, we obtain
x1 = 8, y1 = 4, and z = 320. If we write the augmented matrix, whose left
side is a matrix with columns that have one 1 and all other entries zeros, we
get the following matrix stating the same thing.
We can restate the solution associated with this matrix as x1 = 8, x2 = 0, y1 = 4, y2 = 0 and z = 320. At this stage of the game, it reads that if
Niki works 8 hours at Job I, and no hours at Job II, her profit Z will be
$320. Recall from Example 1 in section
3.1 that (8, 0) was one of our corner points.
Here y1 = 4 and y2 = 0 mean that she will be left with 4 hours of
working time and no preparation time.
7. When
there are no more negative entries in the bottom row, we are finished;
otherwise, we start again from step 4.
Since there is still a negative entry, –10, in the bottom
row, we need to begin, again, from step
4. This time we will not repeat the
details of every step, instead, we will identify the column and row that give
us the pivot element, and highlight the pivot element. The result is as follows.
|
x1
|
x2
|
y1
|
y2
|
Z
|
|
|
|
|
0
|
|
1
|
–1/2
|
0
|
4
|
y1
|
¬ 4 ÷ 1/2 = 8
|
|
1
|
1/2
|
0
|
1/2
|
0
|
8
|
x1
|
8 ÷ 1/2 = 16
|
|
0
|
–10
|
0
|
20
|
1
|
320
|
Z
|
|
We make the pivot element 1 by multiplying row 1 by 2, and
we get
|
x1
|
x2
|
y1
|
y2
|
Z
|
|
|
0
|
|
2
|
–1
|
0
|
8
|
|
1
|
1/2
|
0
|
1/2
|
0
|
8
|
|
0
|
–10
|
0
|
20
|
1
|
320
|
Now to make all other entries as zeros in this column, we
first multiply row 1 by –1/2 and add it to row 2, and then multiply row 1 by 10
and add it to the bottom row.
|
x1
|
x2
|
y1
|
y2
|
Z
|
|
|
|
0
|
1
|
2
|
–1
|
0
|
8
|
x2
|
|
1
|
0
|
–1
|
1
|
0
|
4
|
x1
|
|
0
|
0
|
20
|
10
|
1
|
400
|
Z
|
We no longer have negative entries in the bottom row,
therefore we are finished.
uQuestion Why are we finished when there are no
negative entries in the bottom row?
Answer The answer lies in the bottom row. The bottom row corresponds to the following
equation.
0x1 + 0x2+ 20y1 + 10y2 + Z = 400
or
Z
= 400 - 20y1 - 10y2
Since all variables are non-negative, the highest value Z
can ever achieve is 400, and that will happen only when y1 and y2 are zero.
8. Read
off your answers.
We now read off our answers, that is, we determine the basic
solution associated with the final simplex tableau. Again, we look at the columns that have a 1
and all other entries zeros. Since the
columns labeled y1 and y2 are not such columns, we arbitrarily choose y1 = 0, and
y2 = 0, and we get
The matrix reads x1 = 4 , x2=
8 and z = 400.
The final solution says that if Niki works 4 hours at Job I
and 8 hours at Job II, she will maximize her income to $400. Since both slack variables are zero, it means
that she would have used up all the working time, as well as the preparation
time, and none will be left.
4.2 Minimization By The Simplex Method
In this section, we will solve the standard linear
programming minimization problems using the simplex method. Once again, we remind the reader that in the
standard minimization problems all constraints are of the form ax + by ≥ c. The procedure to solve these problems was
developed by Dr. John Von Neuman. It
involves solving an associated problem called the dual problem. To every minimization problem there
corresponds a dual problem. The solution
of the dual problem is used to find the solution of the original problem. The dual problem is really a maximization
problem which we already learned to solve in the last section. We will first solve the dual problem by the
simplex method and then, from the final simplex tableau, we will extract the
solution to the original minimization problem.
Before we go any further, however, we first learn to convert
a minimization problem into its corresponding maximization problem called its
dual.
uExample
1 Convert the following
minimization problem into its dual.
Minimize
Z = 12x1 + 16x2
Subject to: x1 + 2x2 ≥ 40
x1 + x2 ≥ 30
x1 ≥ 0; x2 ≥ 0
Solution: To achieve our goal, we first express our
problem as the following matrix.
|
1
|
2
|
40
|
|
1
|
1
|
30
|
|
12
|
16
|
0
|
Observe
that this table looks like an initial simplex tableau without the slack
variables. Next, we write a matrix whose
columns are the rows of this matrix, and the rows are the columns. Such a matrix is called a transpose of the original matrix. We get
|
1
|
1
|
12
|
|
2
|
1
|
16
|
|
40
|
30
|
0
|
The following maximization problem associated with the above
matrix is called its dual.
Maximize
Z = 40y1 + 30y2
Subject to: y1 + y2 ≤ 12
2y1 + y2 ≤ 16
y1 ≥ 0; y2 ≥ 0
We have chosen the variables as y's, instead of x's, to
distinguish the two problems.
uExample
2 Solve graphically
both the minimization problem and its dual, the maximization problem.
Solution: Our minimization problem is as
follows.
Minimize
Z = 12x1 + 16x2
Subject to: x1 + 2x2 ≥ 40
x1 + x2 ≥ 30
x1 ≥ 0; x2 ≥ 0
We now graph the inequalities.
We have plotted the graph,
shaded the feasibility region,
and labeled the corner points. The
corner point (20, 10) gives the lowest value for the objective function and
that value is 400.
Now its dual.
Maximize
Z = 40y1 + 30y2
Subject to: y1 + y2 ≤ 12
2y1 + y2 ≤ 16
y1 ≥ 0; y2 ≥ 0
We graph the inequalities.
Again, we have plotted the graph, shaded the feasibility
region, and labeled the corner points.
The corner point (4, 8) gives the highest value for the objective
function, with a value of 400.
The reader may recognize that
this problem is the same as Example 1, in section 3.1. This is also the same problem as Example 1 in
section 4.1, where we solved it by the simplex method.
We observe that the minimum value of the minimization problem is the same as the
maximum value of the maximization problem; they are both 400. This is not a coincident. We state the duality principle.
The Duality Principle: The objective function of the minimization
problem reaches its minimum if and only if the objective function of its dual
reaches its maximum. And when they do,
they are equal.
Our next goal is to extract the solution for our
minimization problem from the corresponding dual. To do this, we solve the dual by the simplex
method.
uExample
3 Find the solution to
the minimization problem in Example 1 by solving its dual using the simplex
method. We rewrite our problem.
Minimize
Z = 12x1 + 16x2
Subject to: x1 + 2x2 ≥ 40
x1 + x2 ≥ 30
x1 ≥ 0; x2 ≥ 0
Solution: The dual is as follows:
Maximize
Z = 40y1 + 30y2
Subject to: y1 + y2 ≤ 12
2y1 + y2 ≤ 16
y1 ≥ 0; y2 ≥ 0
Once again, we remind the reader that we solved the above
problem by the simplex method in Example 1, section 4.1. Therefore, we will only show the initial and
final simplex tableau.
The initial simplex tableau is
|
y1
|
y2
|
x1
|
x2
|
Z
|
C
|
|
1
|
1
|
1
|
0
|
0
|
12
|
|
2
|
1
|
0
|
1
|
0
|
16
|
|
–40
|
–30
|
0
|
0
|
1
|
0
|
Observe an important change.
Here our main variables are y1 and y2 and the slack variables are x1 and x2.
The final simplex tableau reads as follows:
|
y1
|
y2
|
x1
|
x2
|
Z
|
|
|
|
0
|
1
|
2
|
–1
|
0
|
8
|
|
|
1
|
0
|
–1
|
1
|
0
|
4
|
|
|
0
|
0
|
20
|
10
|
1
|
400
|
|
A closer look at this table reveals that the x1 and x2 values along
with the minimum value for the minimization problem can be obtained from the
last row of the final tableau. We have
highlighted these values by the arrows.
We restate the solution as follows:
The minimization problem has a minimum value of 400 at the
corner point (20, 10).
We now summarize our discussion so far.
|
MINIMIZATION BY THE SIMPLEX METHOD
1. Set up the
problem.
2. Write a matrix
whose rows represent each constraint with the objective function as its
bottom row.
3. Write the
transpose of this matrix by interchanging the rows and columns.
4. Now write the
dual problem associated with the transpose.
5. Solve the dual
problem by the simplex method learned in section 4.1.
6. The optimal
solution is found in the bottom row of the final matrix in the columns
corresponding to the slack variables, and the minimum value of the objective
function is the same as the maximum value of the dual.
|
