Fourth Stage Asst.

Lecturer Ahmed Razzaq

Lecture Four

The Simplex Method and Application in Simplex

Method

4.1 The Simplex Method: Maximization

 Write the simplex tableau for a linear programming problem.

 Use pivoting to find an improved solution.
 Use the simplex method to solve a linear programming problem that
maximizes an objective function.
 Use the simplex method to find an optimal solution to a real-world
application.

4.1.1 The Simplex Tableau

For linear programming problems involving two variables, the graphical
solution method introduced in previous lecture is convenient. For problems
involving more than two variables or large numbers of constraints, it is better to
use methods that are adaptable to technology. One such method is the simplex
method, developed by George Dantzig in 1946. It provides a systematic way of
examining the vertices of the feasible region to determine the optimal value of
the objective function.
Say you want to find the maximum value of z = 4x1 + 6x2, where the decision
variables x1 and x2 are nonnegative, subject to the constraints

1
Fourth Stage Asst. Lecturer Ahmed Razzaq

The left-hand side of each inequality is less than or equal to the right-hand side,
so there must exist nonnegative numbers s1, s2, and s3 that can be added to the
left side of each equation to produce the system of linear equations

The numbers s1, s2, and s3 are called slack variables because they represent the
“slack” in each inequality.

Remark I: Standard Form of a Linear Programming Problem

A linear programming problem is in standard form when it seeks to maximize
the objective function z = c1x1 + c2x2 + . . . + cnxn subject to the constraints

Where xi ≥ 0 and bi ≥ 0, after adding slack variables, the corresponding system

of constraint equations is

A basic solution of a linear programming problem in standard form is a solution

(x1, x2, . . . , xn, s1, s2, . . . , sm) of the constraint equations in which at most m
variables are nonzero, and the variables that are nonzero are called basic
variables. A basic solution for which all variables are nonnegative is a basic
feasible solution.

2
Fourth Stage Asst. Lecturer Ahmed Razzaq

The simplex method is carried out by performing elementary row operations on

a matrix called the simplex tableau. This tableau consists of the augmented
matrix corresponding to the constraint equations together with the coefficients of
the objective function written in the form

In the tableau, it is customary to omit the coefficient of z. For example, the

simplex tableau for the linear programming problem

For this initial simplex tableau, the basic variables are s1, s2, and s3, and the
non-basic variables are x1 and x2. Note that the basic variables are labeled to
the right of the simplex tableau next to the appropriate rows. This technique is
important as you proceed through the simplex method. It helps keep track of the
changing basic variables.
x1 and x2 are the non-basic variables in this initial tableau, so they have an
initial value of zero, yielding a current z-value of zero. From the columns that
are farthest to the right, the basic variables have initial values of s1 = 11, s2 =
27, and s3 = 90. So the current solution is

3
Fourth Stage Asst. Lecturer Ahmed Razzaq

This solution is a basic feasible solution and is often written as

The entry in the lower right corner of the simplex tableau is the current value of
z. Note that the bottom-row entries under x1 and x2 are the negatives of the
coefficients of x1and x2 in the objective function

To perform an optimality check for a solution represented by a simplex tableau,

look at the entries in the bottom row of the tableau. If any of these entries are
negative (as above), then the current solution is not optimal.

4.1.2 Pivoting
After you have set up the initial simplex tableau for a linear programming
problem, the simplex method consists of checking for optimality and then, when
the current solution is not optimal, improving the current solution. (An improved
solution is one that has a larger z-value than the current solution.) To improve
the current solution, bring a new basic variable into the solution, the entering
variable. This implies that one of the current basic variables (the departing
variable) must leave; otherwise you would have too many variables for a basic
solution. Choose the entering and departing variables as listed below.
1. The entering variable corresponds to the least (the most negative) entry in
the bottom row of the tableau, excluding the “b-column.”
2. The departing variable corresponds to the least nonnegative ratio bi/aij in the
column determined by the entering variable, when aij > 0.
3. The entry in the simplex tableau in the entering variable’s column and the
departing variable’s row is the pivot.

4
Fourth Stage Asst. Lecturer Ahmed Razzaq

Finally, to form the improved solution, apply Gauss-Jordan elimination to the

column that contains the pivot. (This process is called pivoting.)
Example 4.1: Pivoting to Find an Improved Solution
Use the simplex method to find an improved solution for the linear
programming problem represented by the tableau shown below.

Solution:
The objective function for this problem is
z = 4x1 + 6x2.
Note that the current solution
(x1 = 0, x2 = 0, s1 = 11, s2 = 27, s3 = 90)
Corresponds to a z-value of 0, to improve this solution, choose x2 as the
entering variable, because −6 is the least entry in the bottom row.

To see why you choose x2 as the entering variable, remember that z = 4x1 + 6x2.
So, it appears that a unit change in x2 produces a change of 6 in z, whereas a unit
change in x1 produces a change of only 4 in z.
To find the departing variable, locate the bi’s that have corresponding positive
elements in the entering variable’s column and form the ratios

5
Fourth Stage Asst. Lecturer Ahmed Razzaq

11/1 = 11, 27/1 = 27, and 90/5 = 18.

Here the least nonnegative ratio is 11, so choose s1 as the departing variable.

Note that the pivot is the entry in the first row and second column. Now, use
Gauss-Jordan elimination to obtain the improved solution shown below

Note that x2 has replaced s1 in the basic variables column and the improved
solution
(x1, x2, s1, s2, s3) = (0, 11, 0, 16, 35)
has a z-value of
z = 4x1 + 6x2 = 4(0) + 6(11) = 66.
The improved solution is not optimal because the bottom row has a negative
entry. So, apply another iteration of the simplex method to improve the solution
further. Choose x1 as the entering variable. Moreover, the lesser of the ratios

6
Fourth Stage Asst. Lecturer Ahmed Razzaq

16/2 = 8 and 35/7 = 5 is 5, so s3 is the departing variable. Gauss-Jordan

elimination produces the matrices shown below.

So, the new simplex tableau is as shown below.

In this tableau, there is still a negative entry in the bottom row. So, choose s1 as
the entering variable and s2 as the departing variable, as shown in the next
tableau.

One more iteration of the simplex method gives the tableau below. (Check this.)

7
Fourth Stage Asst. Lecturer Ahmed Razzaq

In this tableau, there are no negative elements in the bottom row. So, the optimal
solution is
(x1, x2, s1, s2, s3) = (15, 12, 14, 0, 0)
with
z = 4x1 + 6x2 = 4(15) + 6(12) = 132.

Remark II: Here is a summary of the steps involved in the simplex method. To
solve a linear programming problem in standard form, use the steps below:
1. Convert each inequality in the set of constraints to an equation by adding
slack variables.
2. Create the initial simplex tableau.
3. Locate the most negative entry in the bottom row, excluding the “b-column.”
This entry is called the entering variable, and its column is the entering column.
(If ties occur, then any of the tied entries can be used to determine the entering
column.)
4. Form the ratios of the entries in the “b-column” with their corresponding
positive entries in the entering column. (If all entries in the entering column are
0 or negative, then there is no maximum solution.) The departing row
corresponds to the least nonnegative ratio bi/aij. (For ties, choose any
corresponding row.) The entry in the departing row and the entering column is
called the pivot.
5. Use elementary row operations to change the pivot to 1 and all other entries in
the entering column to 0. This process is called pivoting.

8
Fourth Stage Asst. Lecturer Ahmed Razzaq

6. When all entries in the bottom row are zero or positive, this is the final
tableau. Otherwise, go back to Step 3.
7. If you obtain a final tableau, then the linear programming problem has a
maximum solution. The maximum value of the objective function is the entry in
the lower right corner of the tableau.
Example 4.2:
Use the simplex method to find the maximum value of
z = 2x1 − x2 + 2x3 Objective function
Subject to the constraints:

Solution:
Using the basic feasible solution
(x1, x2, x3, s1, s2, s3) = (0, 0, 0, 10, 20, 5)
The initial and subsequent simplex tableaus for this problem are shown below.
(Check the computations, and note the “tie” that occurs when choosing the first
entering variable.)

9
Fourth Stage Asst. Lecturer Ahmed Razzaq

This implies that the optimal solution is

(x1, x2, x3, s1, s2, s3) = (5, 0, 5/2, 0, 20, 0)
and the maximum value of z is 15.
Note that s2 = 20. The optimal solution yields a maximum value of z = 15
provided that x1 = 5, x2 = 0, and x3 = 5/2 . Check that these values satisfy the
constraints giving equality in the first and third constraints, yet the second
constraint has a slack of 20.
Example 4.3: Business Application: Maximum Profit
A manufacturer produces three types of plastic fixtures. The table below shows
the times required for molding, trimming, and packaging. (Times are in hours
per dozen fixtures, and profits are in dollars per dozen fixtures.)

The maximum amounts of production time that the manufacturer can allocate to
each component are listed below.
Molding: 12,000 hours
Trimming: 4600 hours
Packaging: 2400 hours
How many dozen units of each type of fixture should the manufacturer produce
to obtain a maximum profit?

10
Fourth Stage Asst. Lecturer Ahmed Razzaq

Solution:
Let x1, x2, and x3 represent the numbers of dozens of types A, B, and C
fixtures, respectively. The objective function to be maximized is
Profit = 11x1 + 16x2 + 15x3
where x1 ≥ 0, x2 ≥ 0, and x3 ≥ 0. Moreover, using the information in the table,
you can write the constraints below.

So, the initial simplex tableau with the basic feasible solution
(x1, x2, x3, s1, s2, s3) = (0, 0, 0, 12,000, 4600, 2400)
is as shown below.

Now, to this initial tableau, apply the simplex method as shown on the next
page.

11
Fourth Stage Asst. Lecturer Ahmed Razzaq

So the maximum profit is 100,200 $, obtained by producing 600 dozen units of

Type A, 5100 dozen units of Type B, and 800 dozen units of Type C.

12
Fourth Stage Asst. Lecturer Ahmed Razzaq

4.2 The Simplex Method: Minimization

 Determine the dual of a linear programming problem that minimizes an

objective function.
 Use the simplex method to solve a linear programming problem that
minimizes an objective function.
4.2.1 The Dual of a Minimization Problem
In Section 4.1, you applied the simplex method to linear programming problems
in standard form where the objective function was to be maximized. In this
section, you will extend this procedure to linear programming problems in
which the objective function is to be minimized.
A minimization problem is in standard form when the objective function
w = c1x1 + c2x2 + . . . + cnxn
is to be minimized, subject to the constraints

where xi ≥ 0 and bi ≥ 0. The basic procedure used to solve such a problem is to

convert it to a maximization problem in standard form, and then apply the
simplex method as discussed in previous Section.
Minimization Problem: Find the minimum value of
w = 0.12x1 + 0.15x2 Objective function
subject to the constraints

where x1 ≥ 0 and x2 ≥ 0.

13
Fourth Stage Asst. Lecturer Ahmed Razzaq

To solve this problem using the simplex method, you must first convert it to a
maximization problem. The first step is to form the augmented matrix for this
system of inequalities. To this augmented matrix, add a last row that represents
the coefficients of the objective function, as shown below.

Now, interpret this transposed matrix as a maximization problem, as shown on

the next page.
To interpret the transposed matrix as a maximization problem, introduce new
variables, y1, y2, and y3. This corresponding maximization problem is called the
dual of the original minimization problem.
Dual Maximization Problem: Find the maximum value of
z = 300y1 + 36y2 + 90y3 Dual objective function
subject to the constraints

The solution of the original minimization problem can be found by applying the
simplex method to the new dual problem, as shown below.

14
Fourth Stage Asst. Lecturer Ahmed Razzaq

So, the solution of the dual maximization problem is z = 33/50 = 0.66. The x-
values corresponding to this optimal solution are the entries in the bottom row
corresponding to slack variable columns. In other words, the optimal solution
occurs when x1 = 3 and x2 = 2.
The fact that a dual maximization problem has the same solution as its original
minimization problem is stated formally below without proof in the von
Neumann Duality Principle, named after American mathematician John von
Neumann (1903–1957).
Theorem: The von Neumann Duality Principle
The objective value w of a minimization problem in standard form has a
minimum value if and only if the objective value z of the dual maximization
problem has a maximum value. Moreover, the minimum value of w is equal to
the maximum value of z.

Remark III: Solving a Minimization Problem

A minimization problem is in standard form when the objective function
w = c1x1 + c2x2 + . . . + cnxn

15
Fourth Stage Asst. Lecturer Ahmed Razzaq

is to be minimized, subject to the constraints

To solve this problem, use the steps below.

1. Form the augmented matrix for the system of inequalities, and add a bottom
row consisting of the coefficients of the objective function.

2. Form the transpose of this matrix.

3. Form the dual maximization problem corresponding to this transposed

matrix. That is, find the maximum of the objective function

16
Fourth Stage Asst. Lecturer Ahmed Razzaq

4. Apply the simplex method to the dual maximization problem. The maximum
value of z will be the minimum value of w. Moreover, the values of x1, x2, . . . ,
xn will occur in the bottom row of the final simplex tableau, in the columns
corresponding to the slack variables.

Example 4.4: Solving a Minimization Problem

Find the minimum value of
w = 3x1 + 2x2 Objective function
subject to the constraints

Solution:
The augmented matrices corresponding to this problem are shown below.

Dual Maximization Problem: Find the maximum value of

z = 6y1 + 4y2 Dual objective function
Subject to the constraints

where y1 ≥ 0 and y2 ≥ 0. Now apply the simplex method to the dual problem, as
shown below.

17
Fourth Stage Asst. Lecturer Ahmed Razzaq

From this final simplex tableau, the maximum value of z is 10. So, the minimum
value of w is 10, and this occurs when x1 = 2 and x2 = 2.

Example 4.5: Solving a Minimization Problem

Find the minimum value of w = 2x1 + 10x2 + 8x3 subject to the constraints

Solution:
The augmented matrices corresponding to this problem are shown below.

18
Fourth Stage Asst. Lecturer Ahmed Razzaq

Dual Maximization Problem: Find the maximum value of

z = 6y1 + 8y2 + 4y3 Dual objective function
subject to the constraints

where y1 ≥ 0, y2 ≥ 0, and y3 ≥ 0. Now apply the simplex method to the dual

problem as shown below.

19
Fourth Stage Asst. Lecturer Ahmed Razzaq

From this final simplex tableau, the maximum value of z is 36. So, the minimum
value of w is 36, and this occurs when x1 = 2, x2 = 0, and x3 = 4.
Example 4.6: A Business Application: Minimum Cost
A petroleum company owns two refineries. Refinery 1 costs $20,000 per day to
operate, and refinery 2 costs $25,000 per day to operate. The table shows the
numbers of barrels of each grade of oil the refineries can produce each day.

The company has orders totaling 25,000 barrels of high-grade oil, 27,000 barrels
of medium-grade oil, and 30,000 barrels of low-grade oil. How many days
should it run each refinery to minimize its costs and still refine enough oil to
meet its orders?
Solution:
Let x1 and x2 represent the numbers of days the two refineries operate. Then the
total cost is
C = 20,000 x1 + 25,000 x2 Objective function
The constraints are

20
Fourth Stage Asst. Lecturer Ahmed Razzaq

where x1 ≥ 0 and x2 ≥ 0. The augmented matrices corresponding to this problem

are shown below.

Now apply the simplex method to the dual problem.

From this final simplex tableau, the minimum cost is

C = 1,750,000 $ Minimum cost
21
Fourth Stage Asst. Lecturer Ahmed Razzaq

and this occurs when

x1 = 25 and x2 = 50.
So, the two refineries should be operated for the numbers of days shown below.
Refinery 1: 25 days
Refinery 2: 50 days
Note that by operating the two refineries for these numbers of days, the
company produces the amounts of oil listed below.
High-grade oil: 400(25) + 300(50) = 25,000 barrels
Medium-grade oil: 300(25) + 400(50) = 27,500 barrels
Low-grade oil: 200(25) + 500(50) = 30,000 barrels
So, the company refines enough of each grade of oil to meet its orders (with a
surplus of 500 barrels of medium-grade oil).

22