The Simplex Method

Maximization
1. Set up the problem. That is, write the objective function and the inequality 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 the pivot 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.
 Now, we use the simplex method to solve Example 3.1.1
solved geometrically in section 3.1.

Example 3.3.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 2 hours 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
1
In solving this problem, we will follow the
algorithm listed above.

 STEP 1. Set up the problem. 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
Let x = The number of hours per week Niki will work at Job I and y = 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 lesson.
Maximize Z=40x+30y
Subject to x+y ≤12
2x+y ≤16
x ≥ 0; y ≥ 0
 STEP 2. Convert the inequalities into equations. This is done by adding one slack 2
variable for each inequality.
For example to convert the inequality x1+x2≤12 into an equation, we add a non-
negative variable S , and we get;
x+y+S=12
Here the variable S picks up the slack, and it represents the amount by which x+y
falls short of 12. In this problem, if Niki works fewer than 12 hours, say 10, then S 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 rewrite the objective function Z=40x+30y as −40x−30y+Z=0 .
After adding the slack variables, our problem reads
Objective function −40x−30y+Z=0
Subject to constraints: x+y+S1=12
2x+y+S2=16
x≥0; y≥0
 3
STEP 3. Construct the initial simplex tableau. Each inequality
constraint appears in its own row. (The non-negativity constraints do not
appear as rows in the 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.
x y S1 S2 Z C
 3

S1 S2 Z C
 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 which reads S1=12, S2=16,
matrix for the solution of a system of Z=0
equations. If we arbitrarily choose x=0 and
y=0 , we get
 3

x y S1 S2 Z C

S1

S
Z

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 above.
 4
STEP 4.
The most negative entry in the bottom row identifies the pivot column.
 

Pivot column

Question 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 x , y , x2 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=40x+30y, it will make more sense to increase the value of x rather than
y. The variable x 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 x will increase the
objective function by $40 for a unit of increase in the variable x.
 5
STEP 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.

=12
  =16 ÷2 = 8

 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.
Question
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 x . But we cannot choose any
value for x . Can we let x=100 ? Definitely not! That is because Niki never wants to
work for more than 12 hours at both jobs combined: x+y ≤12 . Can we let x=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; using the quotients to identify the pivot
element guarantees that we do not violate the
constraints.
 Question
Why do we identify the pivot element?
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.

Note
 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 x , and it was identified by the most negative entry in the bottom row. The
departing variable S2 was identified by the lowest of all quotients.
 STEP 6. 6

Perform pivoting to make all other entries in this column zero.

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.

x y S1 S2 Z C
 To obtain a zero in the entry first above 6
the pivot element, we multiply the
second row by -1 and add it to row 1.  To obtain a zero in the element
We get S1
below the pivot, we multiply the
second row by 40 and add it to the
x y S1 S2 Z C
last row.

x y S1 S2 Z C

X1
We now determine the basic solution associated with this tableau. By arbitrarily 6
choosing x2=0 and S2=0 , we obtain x=8 , S1=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.

o We can restate the solution associated

with this matrix as x=8 , y=0 , S1=4
x S1 Z C , S2=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 3.1.1 in section 3.1 that (8,
0) was one of our corner points. Here
S1=4 and S2=0 mean that she will
be left with 4 hours of working time
and no preparation time.
STEP 7 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, x y S1 S2 Z C  

-10, in the bottom row, we need to
begin, again, from step 4. This time we
will not repeat the details of every = 41/2=8
step, instead, we will identify the
column and row that give us the pivot
= 8÷1/2=16
element, and highlight the pivot
element. The result is as follows.
We make the pivot element 1 by multiplying row 1 by 2, and 7
we get

x y S1 S2 Z C
Now to make all other entries as zeros in this column, we first multiply 7
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.
X Y S1 S2 Z C

y-
x
Z  
 We no longer have
negative entries in the
bottom row, therefore
we are finished.
 
Question
Why are we finished when there are no
negative entries in the bottom row?
 The answer lies in the bottom row. The bottom row
corresponds to the equation:
0x+0y+20S1+10S2+Z=400 or Z=400−20S1−10S2

 Since all variables are

non-negative, the highest
value Z can ever achieve
is 400, and that will
happen only when S1
and S2 are zero.
STEP 8 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
S1 and S2 are not such columns, we arbitrarily choose S1=0 , and S2=0 , and we get

x y Z C
 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
The matrix reads x1=4 , y=8 and preparation time, and none will be left.
Z=400 .