e eBook Collection
Linear Programming:
The Simplex Method
279
Introduction
The geometric method of solving linear programming problems (presented in
Chapter 5) provides an overview of linear programming. But, practically speaking,
the geometric method is useful only for problems involving two decision variables
and relatively few problem constraints. What happens when we need more decision
variables and more problem constraints? We use an algebraic method called the
simplex method, developed by George B. Dantzig (1914–2005) in 1947. Ideally
suited to computer use, the simplex method is used routinely on applied problems
involving thousands of variables and problem constraints. In this chapter, we move
from a geometric introduction of the simplex method to the big M method, which
can be used to solve linear programming problems with a large number of variables
and constraints. We also explore many applications. For example, we determine
allocations of resources that maximize profit, and we determine production schedules
that minimize cost (see Problem 44 in Section 6-2 on bicycle manufacturing
and Problem 45 in Section 6-3 on ice-cream production).
6-1 A Geometric Introduction
to the Simplex Method
6-2 The Simplex Method:
Maximization with Problem
Constraints of the Form
6-3 The Dual Problem:
Minimization with Problem
Constraints of the Form
6-4 Maximization and
Minimization with Mixed
Problem Constraints
Chapter 6 Review
Review Exercises
U
…
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
Prkentaice Hjalol. Ckopyarig htj ©20k11 Pjeaorsokn Eadu cajtioon,
6-1 A Geometric Introduction to the Simplex Method
• Standard Maximization Problems
in Standard Form
• Slack Variables
• Basic and Nonbasic Variables:
Basic Solutions and Basic
Feasible Solutions
• Basic Feasible Solutions and the
Simplex Method
280 CHAPTER 6 Linear Programming: The Simplex Method
In Chapter 5, we denoted variables with single letters such as x and y. In this chapter,
we will denote variables with subscript forms such as x1 and x2.This change is essential
to computer implementation of the simplex method. The algebraic procedures
utilized in the simplex method require the problem constraints to be written as equations
rather than inequalities.This new form of the linear programming problem also
prompts the use of new terminology.We introduce this new terminology through a
simple example and an appropriate geometric interpretation. From this example,
we can illustrate what the simplex method does geometrically before immersing
ourselves in the algebraic details.
Standard Maximization Problems in Standard Form
We now return to the tent production problem in Example 1, Section 5-3, and
restate the model using subscript notation.
Objective function
Cutting department constraint
(1)
Assembly department constraint
Non-negative constraints
The decision variables and are the number of standard and expedition tents,
respectively, produced each day.
Notice that the problem constraints involve inequalities with positive constants
to the right of the inequality. Maximization problems that satisfy this condition
are called standard maximization problems. In this and the next section, we
restrict our attention to standard maximization problems.
…
x1 x2
x1, x2 U 0
3×1 + 4×2 … 84
subject to x1 + 2×2 … 32
Maximize P = 50×1 + 80×2
DEFINITION Standard Maximization Problem in Standard Form
A linear programming problem is said to be a standard maximization problem in
standard form if its mathematical model is of the following form:
Maximize the objective function
subject to problem constraints of the form
with non-negative constraints
Note: Mathematical model (1) is a standard maximization problem in standard
form.The coefficients of the objective function can be any real numbers.
x1, x2, . . . , xn U 0
a1x1 + a2x2 + A + anxn … b b U 0
P = c1x1 + c2x2 + A + cnxn
EXPLORE & DISCUSS 1 Find an example of a standard maximization problem in standard form involving
two variables and one problem constraint such that
(A) The feasible region is bounded.
(B) The feasible region is unbounded.
Is it possible for a standard maximization problem to have no solution? Explain.
Slack Variables
To adapt a linear programming problem to the matrix methods used in the
simplex process (as discussed in the next section), we convert the problem
constraint inequalities into a system of linear equations using slack variables.
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
bjyo Prkentiace Hjalol. Ckopyarigh tj ©20k11 Pjeaorsokn Eaduc ajtioon,
SECTION 6-1 A Geometric Introduction to the Simplex Method 281
In particular, to convert the system of problem constraint inequalities from
model (1),
Cutting department constraint
(2)
Assembly department constraint
into a system of equations, we add variables and to the left sides of inequalities
(2) to obtain
(3)
The variables and are called slack variables because each makes up the difference
(takes up the slack) between the left and right sides of an inequality in system (2).
For example, if we produced 20 standard tents and 5 expedition tents
then the number of labor-hours used in the cutting department would be
leaving a slack of 2 unused labor-hours out of the 32 available. So
would have the value of 2.
Notice that if the decision variables and satisfy the system of constraint
inequalities (2), then the slack variables and are non-negative.
Basic and Nonbasic Variables: Basic Solutions
and Basic Feasible Solutions
Observe that system (3) has infinitely many solutions—just solve for and in
terms of and and then assign and arbitrary values. Certain solutions of
system (3), called basic solutions, are related to the intersection points of the
(extended) boundary lines of the feasible region in Figure 1.
x1 x2, x1 x2
s1 s2
s1 s2
x1 x2
20 + 2(5) = 30, s1
(x2 = 5),
(x1 = 20)
s1 s2
3×1 + 4×2 + s2 = 84
x1 + 2×2 + s1 = 32
s1 s2
3×1 + 4×2 … 84
x1 + 2×2 … 32
0 10 30 40
10
A(0, 16)
D(0, 21)
E(32, 0)
B(20, 6)
O(0, 0)
C(28, 0)
20
Feasible region
3x1 _ 4x2 _ 84
x1 _ 2x2 _ 32
x1
x2
Figure 1
How are basic solutions to system (3) determined? System (3) involves four
variables and two equations. We divide the four variables into two groups, called
basic variables and nonbasic variables, as follows: Basic variables are selected arbitrarily
with the restriction that there are as many basic variables as there are equations.
The remaining variables are nonbasic variables.
Since system (3) has two equations, we can select any two of the four variables
as basic variables.The remaining two variables are then nonbasic variables.A solution
found by setting the two nonbasic variables equal to 0 and solving for the two
basic variables is called a basic solution. [Note that setting two variables equal to 0 in
system (3) results in a system of two equations with two variables, which has exactly
one solution, infinitely many solutions, or no solution.]
EXAMPLE 1 Basic Solutions and the Feasible Region
(A) Find two basic solutions for system (3) by first selecting and as basic
variables, and then by selecting and as basic variables.
(B) Associate each basic solution found in part (A) with an intersection point of
the (extended) boundary lines of the feasible region in Figure 1, and indicate
which boundary lines produce each intersection point.
(C) Indicate which of the intersection points found in part (B) are in the feasible
region.
x2 s1
s1 s2
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
Prkentaice Hjalol. Ckopyarig htj ©20k11 Pjeaorsokn Eadu cajtioon,
282 CHAPTER 6 Linear Programming: The Simplex Method
SOLUTION (A) With and selected as basic variables, and are nonbasic variables.
A basic solution is found by setting the nonbasic variables equal to 0 and
solving for the basic variables. If and then system (3) becomes
O O
and the basic solution is
(4)
If we select and as basic variables, then and are nonbasic variables.
Setting the nonbasic variables equal to 0, system (3) becomes
O O
Solving, we see that and and the basic solution is
(5)
(B) Basic solution (4)—since and —corresponds to the origin
O(0, 0) in Figure 1, which is the intersection of the boundary lines
and Basic solution (5)—since and —corresponds to
the intersection point D(0, 21), which is the intersection of the boundary
lines and
(C) The intersection point O(0, 0) is in the feasible region; so it is natural to call
the corresponding basic solution a basic feasible solution. The intersection
point D(0, 21) is not in the feasible region; so the corresponding basic solution
is not feasible.
x1 = 0 3×1 + 4×2 = 84.
x2 = 0. x1 = 0 x2 = 21
x1 = 0
x1 = 0 x2 = 0
x1 = 0, x2 = 21, s1 = -10, s2 = 0
x2 = 21 s1 = -10,
4×2 = 84 3x1 + 4x2 + s2 = 84
2×2 + s1 = 32 x1 + 2x2 + s1 = 32
x2 s1 x1 s2
x1 = 0, x2 = 0, s1 = 32, s2 = 84
s2 = 84 3x1 + 4x2 + s2 = 84
s1 = 32 x1 + 2x2 + s1 = 32
x1 = 0 x2 = 0,
s1 s2 x1 x2
Matched Problem 1 (A) Find two basic solutions for system (3) by first selecting and as basic
variables, and then by selecting and as basic variables.
(B) Associate each basic solution found in part (A) with an intersection point of
the (extended) boundary lines of the feasible region in Figure 1, and indicate
which boundary lines produce each intersection point.
(C) Indicate which of the intersection points found in part (B) are in the feasible
region.
x1 s2
x1 s1
Proceeding systematically as in Example 1 and Matched Problem 1, we can
obtain all basic solutions to system (3).The results are summarized in Table 1, which
also includes geometric interpretations of the basic solutions. Figure 2 summarizes
these interpretations. A careful study of Table 1 and Figure 2 is very worthwhile.
(Note that to be sure we have listed all possible basic solutions in Table 1, it is convenient
to organize the table in terms of the zero values of the nonbasic variables.)
Table 1 Basic Solutions
Basic Solutions
x1 x2 s1 s2 Intersection Point Intersecting Boundary Lines Feasible
0 0 32 84 O(0, 0)
x2 = 0
x1 = 0 Yes
0 16 0 20 A(0, 16)
x1 + 2×2 = 32
x1 = 0 Yes
0 21 -10 0 D(0, 21)
3×1 + 4×2 = 84
x1 = 0 No
32 0 0 -12 E(32, 0)
x1 + 2×2 = 32
x2 = 0 No
28 0 4 0 C(28, 0)
3×1 + 4×2 = 84
x2 = 0 Yes
20 6 0 0 B(20, 6)
3×1 + 4×2 = 84
x1 + 2×2 = 32 Yes
CONCEPTUAL INSIGHT
In Table 1, observe that a basic
solution that is not feasible
includes at least one negative
value and that a basic feasible
solution does not include any
negative values.That is, we can
determine the feasibility of a
basic solution simply by examining
the signs of all the variables
in the solution.
In Table 1 and Figure 2,
observe that basic feasible solutions
are associated with the
corner points of the feasible
region, which include the optimal
solution to the original linear
programming problem.
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
bjyo Prkentiace Hjalol. Ckopyarigh tj ©20k11 Pjeaorsokn Eaduc ajtioon,
SECTION 6-1 A Geometric Introduction to the Simplex Method 283
DEFINITION Basic Variables and Nonbasic Variables; Basic Solutions
and Basic Feasible Solutions
Given a system of linear equations associated with a linear programming problem
(such a system will always have more variables than equations),
The variables are divided into two (mutually exclusive) groups as follows:
Basic variables are selected arbitrarily with the one restriction that there are
as many basic variables as there are equations. The remaining variables are
called nonbasic variables.
A solution found by setting the nonbasic variables equal to 0 and solving for
the basic variables is called a basic solution. If a basic solution has no negative
values, it is a basic feasible solution.
0 10 30 40
10
A(0, 16)
D(0, 21)
E(32, 0)
B(20, 6)
O(0, 0)
C(28, 0)
20
Feasible region
3x1 _ 4x2 _ 84
x1 _ 2x2 _ 32
x1
x2
Figure 2 Basic feasible solutions: O,A, B, C
Basic solutions that are not feasible: D, E
Before proceeding further, let us formalize the definitions alluded to in the discussion
above so that they apply to standard maximization problems in general,
without any reference to geometric interpretation.
EXAMPLE 2 Basic Variables and Basic Solutions Suppose that there is a system of three problem
constraint equations with eight (slack and decision) variables associated with
a standard maximization problem.
(A) How many basic variables and how many nonbasic variables are associated
with the system?
(B) Setting the nonbasic variables equal to 0 will result in a system of how many
linear equations with how many variables?
(C) If a basic solution has all non-negative elements, is it feasible or not feasible?
SOLUTION (A) Since there are three equations in the system, there should be three basic
variables and five nonbasic variables.
(B) Three equations with three variables
(C) Feasible
Matched Problem 2 Suppose that there is a system of five problem constraint equations with eleven
(slack and decision) variables associated with a standard maximization problem.
(A) How many basic variables and how many nonbasic variables are associated
with the system?
(B) Setting the nonbasic variables equal to 0 will result in a system of how many
linear equations with how many variables?
(C) If a basic solution has one or more negative elements, is it feasible or not
feasible?
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
Prkentaice Hjalol. Ckopyarig htj ©20k11 Pjeaorsokn Eadu cajtioon,
284 CHAPTER 6 Linear Programming: The Simplex Method
THEOREM 1 Fundamental Theorem of Linear Programming: Version 2
If the optimal value of the objective function in a linear programming problem
exists, then that value must occur at one (or more) of the basic feasible solutions.
EXPLORE & DISCUSS 2 If we know that a standard maximization problem has an optimal solution, how can
we use a table of basic solutions like Table 1 to find the optimal solution?
We have taken the first step toward finding a general method of solving linear
programming problems involving any number of variables and problem constraints.
That is, we have found a method of identifying all the corner points (basic feasible
solutions) of a feasible region without drawing its graph. This is a critical step if we
want to consider problems with more than two decision variables. Unfortunately,
the number of corner points increases dramatically as the number of variables and
constraints increases. In real-world problems, it is not practical to find all the corner
points in order to find the optimal solution. So the next step is to find a method that
locates the optimal solution without finding every corner point.
The simplex method, using a special matrix and row operations, automatically
moves from one basic feasible solution to another—that is, from one corner point of
the feasible region to another—each time getting closer to an optimal solution (if
one exists), until an optimal solution is reached. Then the process stops.A remarkable
property of the simplex method is that in large linear programming problems it
usually arrives at an optimal solution (if one exists) by testing relatively few of the
large number of basic feasible solutions (corner points) available.
With this background, we will discuss the algebraic details of the simplex
method in the next section.
Basic Feasible Solutions and the Simplex Method
The following theorem is equivalent to the fundamental theorem (Theorem 1 in
Section 5-3) and is stated here without proof:
Now you can understand why the concepts of basic and nonbasic variables and
basic solutions and basic feasible solutions are so important—these concepts are
central to the process of finding optimal solutions to linear programming problems.
Exercises 6-1
A
1. Discuss the relationship between a standard maximization
problem with two problem constraints and three decision
variables, and the associated system of problem constraint
equations. In particular, find each of the following quantities
and explain how each was determined:
(A) The number of slack variables that must be
introduced to form the system of problem constraint
equations
(B) The number of basic variables and the number of nonbasic
variables associated with the system
(C) The number of linear equations and the number of
variables in the system formed by setting the nonbasic
variables equal to 0
2. Repeat Problem 1 for a standard maximization problem
with three problem constraints and four decision variables.
3. Discuss the relationship between a standard maximization
problem and the associated system of problem constraint
equations, if the system of problem constraint equations has
nine variables, including five slack variables. In particular,
find each of the following quantities and explain how each
was determined:
(A) The number of constraint equations in the system
(B) The number of decision variables in the system
(C) The number of basic variables and the number of nonbasic
variables associated with the system
(D) The number of linear equations and the number of
variables in the system formed by setting the nonbasic
variables equal to 0
4. Repeat Problem 3 if the system of problem constraint equations
has 10 variables, including 4 slack variables.
5. Listed in the table below are all the basic solutions for the
system
For each basic solution, identify the nonbasic variables and
the basic variables. Classify each basic solution as feasible
4×1 + 3×2 + s2 = 36
2×1 + 3×2 + s1 = 24
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
bjyo Prkentiace Hjalol. Ckopyarigh tj ©20k11 Pjeaorsokn Eaduc ajtioon,
SECTION 6-2 The Simplex Method: Maximization with Problem Constraints of the Form … 285
6. Repeat Problem 5 for the system
whose basic solutions are given in the following table:
x1 + 5×2 + s2 = 60
2×1 + x2 + s1 = 30
x1 x2 s1 s2
(A) 0 0 24 36
(B) 0 8 0 12
(C) 0 12 -12 0
(D) 12 0 0 -12
(E) 9 0 6 0
(F) 6 4 0 0
x1 x2 s1 s2
(A) 0 0 30 60
(B) 0 30 0 -90
(C) 0 12 18 0
(D) 15 0 0 45
(E) 60 0 -90 0
(F) 10 10 0 0
or not feasible. Explain how you could use the basic feasible
solutions to find the maximum value of z = 2×1 + 3×2.
7. Listed in the table below are all the possible choices of nonbasic
variables for the system
In each case, find the values of the basic variables and determine
whether the basic solution is feasible.
x1 + 2×2 + s2 = 40
2×1 + x2 + s1 = 50
8. Repeat Problem 7 for the system
3×1 + 2×2 + s2 = 24
x1 + 2×2 + s1 = 12
x1 x2 s1 s2
(A) 0 0 ? ?
(B) 0 ? 0 ?
(C) 0 ? ? 0
(D) ? 0 0 ?
(E) ? 0 ? 0
(F) ? ? 0 0
B
Graph the systems of inequalities in Problems 9–12. Introduce
slack variables to convert each system of inequalities to a system
of equations, and find all the basic solutions of the system. Construct
a table (similar to Table 1) listing each basic solution, the
corresponding point on the graph, and whether the basic solution
is feasible. (You do not need to list the intersecting lines.)
9.
10.
11.
12.
Answers to Matched Problems
1. (A) Basic solution corresponding to basic variables
and Basic solution
corresponding to basic variables and
(B) The first basic solution corresponds to C(28, 0), which
is the intersection of the boundary lines and
The second basic solution corresponds
to E(32, 0), which is the intersection of the
boundary lines and
(C) C(28, 0) is in the feasible region (so the corresponding
basic solution is a basic feasible solution); E(32, 0) is
not in the feasible region (so the corresponding basic
solution is not feasible).
2. (A) Five basic variables and six nonbasic variables
(B) Five equations and five variables
(C) Not feasible
x2 = 0 x1 + 2×2 = 32.
3×1 + 4×2 = 84.
x2 = 0
x2 = 0, s1 = 0, s2 = -12.
x1 s2: x1 = 32,
s1: x1 = 28, x2 = 0, s1 = 4, s2 = 0.
x1
x1, x2 U 0
x1 + x2 … 13
2×1 + x2 … 16
4×1 + x2 … 28
x1, x2 U 0
x1 + 2×2 … 20
x1 + x2 … 12
2×1 + x2 … 22
x1, x2 U 0
4×1 + x2 … 32
5×1 + x2 … 35
x1, x2 U 0
2×1 + x2 … 20
x1 + x2 … 16
6-2 The Simplex Method: Maximization with
Problem Constraints of the Form ◊
• Initial System
• Simplex Tableau
• Pivot Operation
• Interpreting the Simplex Process
Geometrically
• Simplex Method Summarized
• Application
Now we can develop the simplex method for a standard maximization problem.The
simplex method is most useful when used with computers. Consequently, it is not
intended that you become an expert in manually solving linear programming problems
using the simplex method. But it is important that you become proficient in
constructing the models for linear programming problems so that they can be solved
using a computer, and it is also important that you develop skill in interpreting the
results. One way to gain this proficiency and interpretive skill is to set up and manually
solve a number of fairly simple linear programming problems using the simplex
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
Prkentaice Hjalol. Ckopyarig htj ©20k11 Pjeaorsokn Eadu cajtioon,
286 CHAPTER 6 Linear Programming: The Simplex Method
DEFINITION Basic Solutions and Basic Feasible Solutions for Initial Systems
1. The objective function variable P is always selected as a basic variable.
2. Note that a basic solution of system (3) is also a basic solution of system (2)
after P is deleted.
3. If a basic solution of system (3) is a basic feasible solution of system (2)
after deleting P, then the basic solution of system (3) is called a basic
feasible solution of system (3).
4. A basic feasible solution of system (3) can contain a negative number, but
only if it is the value of P, the objective function variable.
THEOREM 1 Fundamental Theorem of Linear Programming: Version 3
If the optimal value of the objective function in a linear programming problem
exists, then that value must occur at one (or more) of the basic feasible solutions
of the initial system.
These changes lead to a small change in the second version of the fundamental
theorem (see Theorem 1, Section 6-1).
method.This is the main goal in this section and in Sections 6-3 and 6-4.To assist you
in learning to develop the models, the answer sections for Exercises 6-2, 6-3, and 6-4
contain both the model and its solution.
Initial System
We will introduce the concepts and procedures involved in the simplex method
through an example—the tent production example discussed earlier.We restate the
problem here in standard form for convenient reference:
Objective function
Problem constraints (1)
Non-negative constraints
Introducing slack variables and we convert the problem constraint inequalities
in problem (1) into the following system of problem constraint equations:
(2)
Since a basic solution of system (2) is not feasible if it contains any negative values,we
have also included the non-negative constraints for both the decision variables and
and the slack variables and From our discussion in Section 6-1, we know that
out of the infinitely many solutions to system (2), an optimal solution is one of the
basic feasible solutions, which correspond to the corner points of the feasible region.
As part of the simplex method we add the objective function equation
in the form to system (2) to create what is
called the initial system:
(3)
When we add the objective function equation to system (2), we must slightly
modify the earlier definitions of basic solution and basic feasible solution so that
they apply to the initial system (3).
x1, x2, s1, s2 U 0
-50×1 – 80×2 + P = 0
3×1 + 4×2 + s2 = 84
x1 + 2×2 + s1 = 32
P = 50×1 + 80×2 -50×1 – 80×2 + P = 0
x2 s1 s2.
x1
x1, x2, s1, s2 U 0
3×1 + 4×2 + s2 = 84
x1 + 2×2 + s1 = 32
s1 s2,
x1, x2 U 0
subject to x1 + 2×2 … 32
3×1 + 4×2 … 84
f
Maximize P = 50×1 + 80×2
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
bjyo Prkentiace Hjalol. Ckopyarigh tj ©20k11 Pjeaorsokn Eaduc ajtioon,
SECTION 6-2 The Simplex Method: Maximization with Problem Constraints of the Form … 287
With these adjustments understood, we start the simplex process with a basic
feasible solution of the initial system (3), which we will refer to as an initial basic
feasible solution. An initial basic feasible solution that is easy to find is the one
associated with the origin.
Since system (3) has three equations and five variables, it has three basic variables
and two nonbasic variables. Looking at the system, we see that and
appear in all equations, and and P each appear only once and each in a different
equation.A basic solution can be found by inspection by selecting and P as
the basic variables (remember,P is always selected as a basic variable) and and
as the nonbasic variables to be set equal to 0. Setting and equal to 0 and solving
for the basic variables, we obtain the basic solution:
This basic solution is feasible since none of the variables (excluding P) are negative.
This is the initial basic feasible solution that we seek.
Now you can see why we wanted to add the objective function equation to
system (2): A basic feasible solution of system (3) not only includes a basic feasible
solution of system (2), but, in addition, it includes the value of P for that basic feasible
solution of system (2).
The initial basic feasible solution we just found is associated with the origin. Of
course, if we do not produce any tents, we do not expect a profit, so Starting
with this easily obtained initial basic feasible solution, the simplex process moves
through each iteration (repetition) to another basic feasible solution, each time
improving the profit. The process continues until the maximum profit is reached,
then the process stops.
Simplex Tableau
To facilitate the search for the optimal solution, we turn to matrix methods discussed
in Chapter 4. Our first step is to write the augmented matrix for the initial
system (3).This matrix is called the initial simplex tableau,* and it is simply a tabulation
of the coefficients in system (3).
Initial simplex tableau (4)
In tableau (4), the row below the dashed line always corresponds to the
objective function. Each of the basic variables we selected above, and P, is
also placed on the left of the tableau so that the intersection element in its row
and column is not 0. For example, we place the basic variable on the left so that
the intersection element of the row and the column is 1 and not 0. The basic
variable is similarly placed. The objective function variable P is always placed
at the bottom. The reason for writing the basic variables on the left in this way is
that this placement makes it possible to read certain basic feasible solutions
directly from the tableau. If and the basic variables on the left of
tableau (4) are lined up with their corresponding values, 32, 84, and 0, to the right
of the vertical line.
Looking at tableau (4) relative to the choice of and P as basic variables,we
see that each basic variable is above a column that has all 0 elements except for a single
1 and that no two such columns contain 1’s in the same row. These observations
s1, s2,
x1 = 0 x2 = 0,
s2
s1 s1
s1
s1, s2,
s1
s2
P
C
x1 x2 s1 s2 P
1 2 1 0 0
3 4 0 1 0
-50 -80 0 0 1
3
32
84
0
S
P = $0.
x1 = 0, x2 = 0, s1 = 32, s2 = 84, P = 0
x1 x2
x1 x2
s1, s2,
s1, s2,
x1 x2
*The format of a simplex tableau can vary. Some authors place the objective function coefficients in the
first row rather than the last. Others do not include a column for P.
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
Prkentaice Hjalol. Ckopyarig htj ©20k11 Pjeaorsokn Eadu cajtioon,
288 CHAPTER 6 Linear Programming: The Simplex Method
PROCEDURE Selecting Basic and Nonbasic Variables
for the Simplex Method
Given a simplex tableau,
Step 1 Numbers of variables. Determine the number of basic variables and the
number of nonbasic variables. These numbers do not change during the
simplex process.
Step 2 Selecting basic variables. A variable can be selected as a basic variable
only if it corresponds to a column in the tableau that has exactly one
nonzero element (usually 1) and the nonzero element in the column is
not in the same row as the nonzero element in the column of another
basic variable. This procedure always selects P as a basic variable, since
the P column never changes during the simplex process.
Step 3 Selecting nonbasic variables. After the basic variables are selected in step 2,
the remaining variables are selected as the nonbasic variables.The tableau
columns under the nonbasic variables usually contain more than one
nonzero element.
The earlier selection of and P as basic variables and and as nonbasic
variables conforms to this prescribed convention of selecting basic and nonbasic
variables for the simplex process.
Pivot Operation
The simplex method swaps one of the nonbasic variables, or for one of the
basic variables, or (but not P), as a step toward improving the profit. For a nonbasic
variable to be classified as a basic variable, we need to perform appropriate
row operations on the tableau so that the newly selected basic variable will end
up with exactly one nonzero element in its column. In this process, the old basic
variable will usually gain additional nonzero elements in its column as it becomes
nonbasic.
Which nonbasic variable should we select to become basic? It makes sense to
select the nonbasic variable that will increase the profit the most per unit change in
that variable. Looking at the objective function
we see that if stays a nonbasic variable (set equal to 0) and if becomes a new
basic variable, then
and for each unit increase in P will increase $80. If stays a nonbasic variable
and becomes a new basic variable, then (reasoning in the same way) for each unit
increase in P will increase only $50. So, we select the nonbasic variable to
enter the set of basic variables, and call it the entering variable. (The basic variable
leaving the set of basic variables to become a nonbasic variable is called the exiting
variable, which will be discussed shortly.)
The column corresponding to the entering variable is called the pivot column.
Looking at the bottom row in tableau (4)—the objective function row below the
dashed line—we see that the pivot column is associated with the column to the left
of the P column that has the most negative bottom element. In general, the most
negative element in the bottom row to the left of the P column indicates the variable
above it that will produce the greatest increase in P for a unit increase in that
variable. For this reason, we call the elements in the bottom row of the tableau, to
the left of the P column, indicators.
x1, x2
x1
x2, x2
P = 50(0) + 80×2 = 80×2
x1 x2
P = 50×1 + 80×2
s1 s2
x1 x2,
s1, s2, x1 x2
lead to a formalization of the process of selecting basic and nonbasic variables that is
an important part of the simplex method:
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
bjyo Prkentiace Hjalol. Ckopyarigh tj ©20k11 Pjeaorsokn Eaduc ajtioon,
SECTION 6-2 The Simplex Method: Maximization with Problem Constraints of the Form … 289
We illustrate the indicators, the pivot column, the entering variable, and the initial
basic feasible solution below:
Entering
variable
s1
s2
P
C
x1 x2 s1 s2 P
1 2 1 0 0
3 4 0 1 0
_50 _80 0 0 1
3
32
84
0
S
T
Pivot
column
Initial basic feasible solution
Now that we have chosen the nonbasic variable as the entering variable (the
nonbasic variable to become basic), which of the two basic variables, or should
we choose as the exiting variable (the basic variable to become nonbasic)? We saw
above that for each unit increase in the entering variable results in an
increase of $80 for P. Can we increase without limit? No! A limit is imposed by the
non-negative requirements for and (Remember that if any of the basic variables
except P become negative, we no longer have a feasible solution.) So we rephrase the
question and ask: How much can be increased when without causing or
to become negative? To see how much can be increased, we refer to tableau (5)
or system (3) and write the two problem constraint equations with
Solving for and we have
For and to be non-negative, must be chosen so that both and
are non-negative.That is, so that
For both inequalities to be satisfied, must be less than or equal to the smaller of
the values, which is 16. So can increase to 16 without either or becoming negative.
Now, observe how each value (16 and 21) can be obtained directly from the
following tableau:
Entering
variable
(6)
Pivot
column
From tableau (6) we can determine the amount that the entering variable can
increase by choosing the smallest of the quotients obtained by dividing each element
c
32
2 = 16 (smallest)
84
4 = 21
s1
s2
P
C
x1 x2 s1 s2 P
1 2 1 0 0
3 4 0 1 0
-50 -80 0 0 1
3
32
84
0
S
T
x2 s1 s2
x2
x2 … 32
2 = 16 x2 … 84
4 = 21
-2×2 U -32 -4×2 U -84
32 – 2×2 U 0 and 84 – 4×2 U 0
84 – 4×2
s1 s2 x2 32 – 2×2
s2 = 84 – 4×2
s1 = 32 – 2×2
s1 s2,
4×2 + s2 = 84
2×2 + s1 = 32
x1 = 0:
s2 x2
x2 x1 = 0 s1
s1 s2.
x2
x1 = 0, x2
s1 s2,
x2
x1 = 0, x2 = 0, s1 = 32, s2 = 84, P = 0
T
Initial simplex tableau
(5)
Indicators are shown in color.
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
Prkentaice Hjalol. Ckopyarig htj ©20k11 Pjeaorsokn Eadu cajtioon,
290 CHAPTER 6 Linear Programming: The Simplex Method
x¡ x™ s¡ s™ P
1 2 1 0 0 32 b Pivot row
C 3 4 0 1 0 3 84 S
–50 –80 0 0 1 0
Entering
variable
A
Exiting variable B
Pivot element
a
Pivot
column
s¡
s™
P
In order for to be classified as a basic variable, we perform row operations on
tableau (7) so that the pivot element is transformed into 1 and all other elements in the
column into 0’s.This procedure for transforming a nonbasic variable into a basic variable
is called a pivot operation, or pivoting, and is summarized in the following box.
x2
PROCEDURE Selecting the Pivot Element
Step 1 Locate the most negative indicator in the bottom row of the tableau to
the left of the P column (the negative number with the largest absolute
value).The column containing this element is the pivot column. If there is
a tie for the most negative indicator, choose either column.
Step 2 Divide each positive element in the pivot column above the dashed line
into the corresponding element in the last column. The pivot row is the
row corresponding to the smallest quotient obtained. If there is a tie for
the smallest quotient, choose either row. If the pivot column above the
dashed line has no positive elements, there is no solution, and we stop.
Step 3 The pivot (or pivot element) is the element in the intersection of the pivot
column and pivot row.
Note: The pivot element is always positive and never appears in the bottom row.
Remember: The entering variable is at the top of the pivot column, and the exiting
variable is at the left of the pivot row.
PROCEDURE Performing a Pivot Operation
A pivot operation, or pivoting, consists of performing row operations as follows:
Step 1 Multiply the pivot row by the reciprocal of the pivot element to transform
the pivot element into a 1. (If the pivot element is already a 1, omit this step.)
Step 2 Add multiples of the pivot row to other rows in the tableau to transform
all other nonzero elements in the pivot column into 0’s.
in the last column above the dashed line by the corresponding positive element in the
pivot column.The row with the smallest quotient is called the pivot row, and the variable
to the left of the pivot row is the exiting variable. In this case, will be the exiting
variable, and the roles of and will be interchanged.The element at the intersection
of the pivot column and the pivot row is called the pivot element, and we circle
this element for ease of recognition. Since a negative or 0 element in the pivot column
places no restriction on the amount that an entering variable can increase, it is not
necessary to compute the quotient for negative or 0 values in the pivot column.
A negative or 0 element is never selected for the pivot element.
The following tableau illustrates this process, which is summarized in the next box.
x2 s1
s1
(7)
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
bjyo Prkentiace Hjalol. Ckopyarigh tj ©20k11 Pjeaorsokn Eaduc ajtioon,
SECTION 6-2 The Simplex Method: Maximization with Problem Constraints of the Form … 291
Performing a pivot operation has the following effects:
1. The (entering) nonbasic variable becomes a basic variable.
2. The (exiting) basic variable becomes a nonbasic variable.
3. The value of the objective function is increased, or, in some cases, remains
the same.
We now carry out the pivot operation on tableau (7). (To facilitate the process,
we do not repeat the variables after the first tableau, and we use “Enter” and “Exit”
for “Entering variable” and “Exiting variable,” respectively.)
CONCEPTUAL INSIGHT
A pivot operation uses some of the same row operations as those used in Gauss–Jordan
elimination, but there is one essential difference. In a pivot operation, you can never
interchange two rows.
x¡ x™ s¡ s™ P
1 2 1 0 0 32 R1 B R1
C 3 4 0 1 0 † 84 S
–50 –80 0 0 1 0
1 0 0 16
C 3 4 0 1 0 † 84 S (–4)R1+R2 B R2
–50 –80 0 0 1 0 80R1+R3 B R3
1 0 0 16
C 1 0 –2 1 0 † 20 S
–10 0 40 0 1 1,280
Enter
A
Exit B 12
1
2
1
2
1
2
1
2
s¡
s™
P
_
_
We have completed the pivot operation, and now we must insert appropriate
variables for this new tableau. Since replaced the basic variables are now
and P, as indicated by the labels on the left side of the new tableau. Note that this
selection of basic variables agrees with the procedure outlined on page 288 for
selecting basic variables.We write the new basic feasible solution by setting the nonbasic
variables and equal to 0 and solving for the basic variables by inspection.
(Remember, the values of the basic variables listed on the left are the corresponding
numbers to the right of the vertical line.To see this, substitute and in
the corresponding system shown next to the simplex tableau.)
x1 = 0 s1 = 0
x1 s1
x2 s1, x2, s2,
x2
s2
P
C
x1 x2 s1 s2 P
12
1 12
0 0
1 0 -2 1 0
-10 0 40 0 1
3
16
20
1,280
S
-10x1 + 40s1 + P = 1,280
x1 – 2s1 + s2 = 20
12
x1 + x2 + 12
s1 = 16
A profit of $1,280 is a marked improvement over the $0 profit produced by the
initial basic feasible solution. But we can improve P still further, since a negative
indicator still remains in the bottom row. To see why, we write out the objective
function:
or
P = 10×1 – 40s1 + 1,280
-10×1 + 40s1 + P = 1,280
x1 = 0, x2 = 16, s1 = 0, s2 = 20, P = $1,280
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
Prkentaice Hjalol. Ckopyarig htj ©20k11 Pjeaorsokn Eadu cajtioon,
x¡ x™ s¡ s™ P
1 0 0 16 (– )R2+R1 B R1
C 1 0 –2 1 0 3 20 S
–10 0 40 0 1 1,280 10R2+R3 B R3
0 1 – 0 6
C 1 0 –2 1 0 3 20 S
0 0 20 10 1 1,480
Enter
A
Exit B
12
1
2
1
2
3
2
1
2
s™
P
x2
_
292 CHAPTER 6 Linear Programming: The Simplex Method
Since there are no more negative indicators in the bottom row, we are done. Let
us insert the appropriate variables for this last tableau and write the corresponding
basic feasible solution.The basic variables are now and P, so to get the corresponding
basic feasible solution, we set the nonbasic variables and equal to 0
and solve for the basic variables by inspection.
To see why this is the maximum, we rewrite the objective function from the bottom
row:
Since and cannot be negative, any increase of either variable from 0 will make
the profit smaller.
Finally, returning to our original problem, we conclude that a production schedule
of 20 standard tents and 6 expedition tents will produce a maximum profit of
$1,480 per day, just as was found by the geometric method in Section 5-3. The fact
that the slack variables are both 0 means that for this production schedule, the plant
will operate at full capacity—there is no slack in either the cutting department or
the assembly department.
s1 s2
P = 1,480 – 20s1 – 10s2
20s1 + 10s2 + P = 1,480
x1 = 20, x2 = 6, s1 = 0, s2 = 0, P = 1,480
x2
x1
P
C
x1 x2 s1 s2 P
0 1 32
-12
0
1 0 -2 1 0
0 0 20 10 1
3
6
20
1,480
S
s1 s2
x1, x2,
x¡ x™ s¡ s™ P
C 1 0 –2 1 0 3 20 S =20
–10 0 40 0 1 1,280
Enter
A
Exit B 20
1
1/2
1 16=32
2
1
2
s™
P
x2 1 0 0 16
We now pivot on (the circled) 1.That is, we perform a pivot operation using this
1 as the pivot element. Since the pivot element is 1, we do not need to perform the
first step in the pivot operation, so we proceed to the second step to get 0’s above
and below the pivot element 1. As before, to facilitate the process, we omit writing
the variables, except for the first tableau.
If stays a nonbasic variable (set equal to 0) and becomes a new basic variable,
then
and for each unit increase in P will increase $10.
We now go through another iteration of the simplex process using another pivot
element.The pivot element and the entering and exiting variables are shown in the
following tableau:
x1,
P = 10×1 – 40(0) + 1,280 = 10×1 + 1,280
s1 x1
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
bjyo Prkentiace Hjalol. Ckopyarigh tj ©20k11 Pjeaorsokn Eaduc ajtioon,
SECTION 6-2 The Simplex Method: Maximization with Problem Constraints of the Form … 293
Table 1 Basic Feasible Solution (obtained above)
x1 x2 s1 s2 P($) Corner Point
0 0 32 84 0 O(0, 0)
0 16 0 20 1,280 A(0, 16)
20 6 0 0 1,480 B(20, 6)
10 20 30 40
10
A(0, 16)
B(20, 6)
O(0, 0)
C(28, 0)
20
Feasible region
x1
x2
Figure 1
Looking at Table 1 and Figure 1, we see that the simplex process started at the
origin, moved to the adjacent corner point A(0, 16), and then to the optimal solution
B(20, 6) at the next adjacent corner point.This is typical of the simplex process.
Simplex Method Summarized
Before presenting additional examples, we summarize the important parts of the
simplex method schematically in Figure 2.
Step 1:
Write the standard maximization
problem in standard form, introduce
slack variables to form the initial
system, and write the initial tableau.
Step 2:
Are there any negative
indicators in the
bottom row?
Step 4:
Are there any positive
elements in the pivot
column above the
dashed line?
Step 3:
Select the pivot column.
STOP
The optimal solution has
been found.
Step 5:
Select the pivot element and
perform the pivot operation.
STOP
The linear programming
problem has no optimal solution.
No
No
Yes
Yes
Figure 2 Simplex algorithm for standard maximization problems
(Problem constraints are of the form with non-negative constants on the right.
The coefficients of the objective function can be any real numbers.)
…
Interpreting the Simplex Process Geometrically
We can interpret the simplex process geometrically in terms of the feasible region
graphed in the preceding section.Table 1 lists the three basic feasible solutions we
just found using the simplex method (in the order they were found).Table 1 also includes
the corresponding corner points of the feasible region illustrated in Figure 1.
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
Prkentaice Hjalol. Ckopyarig htj ©20k11 Pjeaorsokn Eadu cajtioon,
294 CHAPTER 6 Linear Programming: The Simplex Method
28
4
x¡ x™ s¡ s™ P
4 1 1 0 0 28 =7
C 2 3 0 1 0 3 24 S =12
–10 –5 0 0 1 0
Enter
A
Exit B
24
2
s¡
s™
P
x¡ x™ s¡ s™ P
4 1 1 0 0 28 R1 B R1
C 2 3 0 1 0 3 24 S
–10 –5 0 0 1 0
1 0.25 0.25 0 0 7
C 2 3 0 1 0 3 24 S (–2)R1+R2 B R2
–10 –5 0 0 1 0 10R1+R3 B R3
1 0.25 0.25 0 0 7
C 0 2.5 –0.5 1 0 3 10 S
0 –2.5 2.5 0 1 70
Enter
A
Exit B
_
14
s¡
s™
P
_
x¡
s™
P
x¡ x™ s¡ s™ P
1 0.25 0.25 0 0 7 =28
C 0 2.5 –0.5 1 0 3 10 S =4
0 –2.5 2.5 0 1 70
Enter
A
Exit B
7
0.25
10
2.5
s™
P
x¡
EXAMPLE 1 Using the Simplex Method Solve the following linear programming problem
using the simplex method:
SOLUTION Introduce slack variables and and write the initial system:
Write the simplex tableau, and identify the first pivot element and the entering
and exiting variables:
x1, x2, s1, s2 U 0
-10×1 – 5×2 + P = 0
2×1 + 3×2 + s2 = 24
4×1 + x2 + s1 = 28
s1 s2,
Maximize P = 10×1 + 5×2
subject to 4×1 + x2 … 28
2×1 + 3×2 … 24
x1, x2 U 0
Perform the pivot operation:
Since there is still a negative indicator in the last row, we repeat the process
by finding a new pivot element:
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
bjyo Prkentiace Hjalol. Ckopyarigh tj ©20k11 Pjeaorsokn Eaduc ajtioon,
x¡ x™ s¡ s™ P
1 0.25 0.25 0 0 7
C 0 2.5 –0.5 1 0 3 10 S
0 –2.5 2.5 0 1 70
1 0.25 0.25 0 0 7
C 0 1 –0.2 0.4 0 3 4 S
0 –2.5 2.5 0 1 70
Enter
A
(–0.25)R2 + R1 B R1
2.5R2 + R3 B R3
Exit B R2 B R2
1 0 0.3 –0.1 0 6
C 0 1 –0.2 0.4 0 3 4 S
0 0 2 1 1 80
x¡
s™
P
~
x¡
~x™
P
SECTION 6-2 The Simplex Method: Maximization with Problem Constraints of the Form … 295
Since all the indicators in the last row are non-negative, we stop and read the
optimal solution:
(To see why this makes sense, write the objective function corresponding to the
last row to see what happens to P when you try to increase s1 or s2.)
Max P = 80 at x1 = 6, x2 = 4, s1 = 0, s2 = 0
Matched Problem 1 Solve the following linear programming problem using the simplex method:
Maximize P = 2×1 + x2
subject to 5×1 + x2 … 9
x1 + x2 … 5
x1, x2 U 0
Performing the pivot operation, we obtain
EXPLORE & DISCUSS 1 Graph the feasible region for the linear programming problem in Example 1 and
trace the path to the optimal solution determined by the simplex method.
EXAMPLE 2 Using the Simplex Method Solve using the simplex method:
SOLUTION Write the initial system using the slack variables and
Write the simplex tableau and identify the first pivot element:
Pivot column
Since both elements in the pivot column above the dashed line are negative, we are
unable to select a pivot row.We stop and conclude that there is no optimal solution.
c
s1
s2
P
x1 x2 s1 s2 P
C
-2 3 1 0 0
-1 3 0 1 0
-6 -3 0 0 1
3
9
12
0
S
-6×1 – 3×2 + P = 0
-x1 + 3×2 + s2 = 12
-2×1 + 3×2 + s1 = 9
s1 s2:
Maximize P = 6×1 + 3×2
subject to -2×1 + 3×2 … 9
-x1 + 3×2 … 12
x1, x2 U 0
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
Prkentaice Hjalol. Ckopyarig htj ©20k11 Pjeaorsokn Eadu cajtioon,
296 CHAPTER 6 Linear Programming: The Simplex Method
Matched Problem 2 Solve using the simplex method:
Refer to Examples 1 and 2. In Example 1 we concluded that we had found the
optimal solution because we could not select a pivot column. In Example 2 we concluded
that the problem had no optimal solution because we selected a pivot column
and then could not select a pivot row. Notice that we do not try to continue
with the simplex method by selecting a negative pivot element or using a different
column for the pivot column. Remember:
If it is not possible to select a pivot column, then the simplex method
stops and we conclude that the optimal solution has been found. If the
pivot column has been selected and it is not possible to select a pivot row,
then the simplex method stops and we conclude that there is no optimal
solution.
Application
Maximize P = 2×1 + 3×2
subject to -3×1 + 4×2 … 12
x2 … 2
x1, x2 U 0
EXAMPLE 3 Agriculture A farmer owns a 100-acre farm and plans to plant at most three crops.
The seed for crops A, B, and C costs $40, $20, and $30 per acre, respectively.
A maximum of $3,200 can be spent on seed. Crops A, B, and C require one, two,
and one work days per acre, respectively, and there are a maximum of 160 work
days available. If the farmer can make a profit of $100 per acre on crop A, $300 per
acre on crop B, and $200 per acre on crop C, how many acres of each crop should
be planted to maximize profit?
SOLUTION The farmer must decide on the number of acres of each crop that should be
planted. So the decision variables are
The farmer’s objective is to maximize profit:
The farmer is limited by the number of acres available for planting, the money
available for seed, and the available work days.These limitations lead to the following
constraints:
Acreage constraint
Monetary constraint
Labor constraint
Adding the non-negative constraints, we have the following model for a linear
programming problem:
Objective function
Problem constraints
x1, x2, x3 U 0 Non-negative constraints
subject to x1 + x2 + x3 … 100
40×1 + 20×2 + 30×3 … 3,200
x1 + 2×2 + x3 … 160
s
Maximize P = 100×1 + 300×2 + 200×3
x1 + 2×2 + x3 … 160
40×1 + 20×2 + 30×3 … 3,200
x1 + x2 + x3 … 100
P = 100×1 + 300×2 + 200×3
x3 = number of acres of crop C
x2 = number of acres of crop B
x1 = number of acres of crop A
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
bjyo Prkentiace Hjalol. Ckopyarigh tj ©20k11 Pjeaorsokn Eaduc ajtioon,
SECTION 6-2 The Simplex Method: Maximization with Problem Constraints of the Form … 297
Next, we introduce slack variables and form the initial system:
Notice that the initial system has nonbasic variables and 4 basic variables.
Now we form the simplex tableau and solve by the simplex method:
7 – 4 = 3
x1, x2, x3, s1, s2, s3 U 0
-100×1 – 300×2 – 200×3 + P = 0
x1 + 2×2 + x3 + s3 = 160
40×1 + 20×2 + 30×3 + s2 = 3,200
x1 + x2 + x3 + s1 = 100
x¡ x™ x£ s¡ s™ s£ P
1 1 1 1 0 0 0 100
40 20 30 0 1 0 0 3,200
D
1 2 1 0 0 1 0
4
160
T
0.5R3 B R3
–100 –300 –200 0 0 0 1 0
1 1 1 1 0 0 0 100 (–1)R3+R1 B R1
40 20 30 0 1 0 0 3,200 (–20)R3+R2 B R2
D
0.5 1 0.5 0 0 0.5 0
4
80
T
–100 –300 –200 0 0 0 1 0 300R3+R4 B R4
Enter
A
Exit B
s2
s3
s¡
P
_
x¡ x™ x£ s¡ s™ s£ P
0.5 0 0.5 1 0 –0.5 0 20 2R1 B R1
30 0 20 0 1 –10 0 1,600
D
0.5 1 0.5 0 0 0.5 0
4
80
T
50 0 –50 0 0 150 1 24,000
1 0 1 2 0 –1 0 40
30 0 20 0 1 –10 0 1,600 (–20)R1+R2 B R2
D
0.5 1 0.5 0 0 0.5 0
4
80
T
(–0.5)R1+R3 B R3
50 0 –50 0 0 150 1 24,000 50R1+R4 B R4
1 0 1 2 0 –1 0 40
10 0 0 –40 1 10 0 800
D
0 1 0 –1 0 1 0
4
60
T
100 0 0 100 0 100 1 26,000
Enter
A
Exit B
x2
s¡
s™
P
_
P
s™
x2
x3
_
All indicators in the bottom row are non-negative, and now we can read the optimal
solution:
So if the farmer plants 60 acres in crop B, 40 acres in crop C, and no crop A, the
maximum profit of $26,000 will be realized.The fact that tells us (look at
the second row in the equations at the start) that this maximum profit is reached
by using only $2,400 of the $3,200 available for seed; that is, we have a slack of
$800 that can be used for some other purpose.
s2 = 800
x1 = 0, x2 = 60, x3 = 40, s1 = 0, s2 = 800, s3 = 0, P = $26,000
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
Prkentaice Hjalol. Ckopyarig htj ©20k11 Pjeaorsokn Eadu cajtioon,
Investment per Acre Maximum
Crop A Crop B Crop C Available
Seed cost $24 $40 $30 $3,600
Work days 1 2 2 160
Profit $140 $200 $160
298 CHAPTER 6 Linear Programming: The Simplex Method
Matched Problem 3 Repeat Example 3 modified as follows:
Figure 3
The feasible region for the linear programming problem in Example 3 has eight
corner points, but the simplex method found the solution in only two steps. In larger
problems, the difference between the total number of corner points and the number
of steps required by the simplex method is even more dramatic. A feasible region
may have hundreds or even thousands of corner points, yet the simplex method will
often find the optimal solution in 10 or 15 steps.
To simplify this introduction to the simplex method, we have purposely avoided
certain degenerate cases that lead to difficulties. Discussion and resolution of these
problems is left to a more advanced treatment of the subject.
CONCEPTUAL INSIGHT
If you are solving a system of linear equations or inequalities, then you can multiply both
sides of an equation by any nonzero number and both sides of an inequality by any positive
number without changing the solution set.This is still the case for the simplex method, but
you must be careful when you interpret the results. For example, consider the second problem
constraint in the model for Example 3:
Multiplying both sides by before introducing slack variables simplifies subsequent calculations.
However, performing this operation has a side effect—it changes the units of the
slack variable from dollars to tens of dollars. Compare the following two equations:
s2 represents dollars
represents tens of dollars
In general, if you multiply a problem constraint by a positive number, remember to take
this into account when you interpret the value of the slack variable for that constraint.
soe 2 4×1 + 2×2 + 3×3 + soe 2 = 320
40×1 + 20×2 + 30×3 + s2 = 3,200
1
10
40×1 + 20×2 + 30×3 … 3,200
There are many types of software that can be used to solve linear programming
problems by the simplex method. Figure 3 illustrates a solution to Example 3 in
Excel, a popular spreadsheet for personal computers.
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
bjyo Prkentiace Hjalol. Ckopyarigh tj ©20k11 Pjeaorsokn Eaduc ajtioon,
SECTION 6-2 The Simplex Method: Maximization with Problem Constraints of the Form … 299
Exercises 6-2
A
For the simplex tableaux in Problems 1–4,
(A) Identify the basic and nonbasic variables.
(B) Find the corresponding basic feasible solution.
(C) Determine whether the optimal solution has been found, an
additional pivot is required, or the problem has no optimal
solution.
1.
2.
3.
4.
In Problems 5–8, find the pivot element, identify the entering and
exiting variables, and perform one pivot operation.
5.
6.
7.
8.
D
x1 x2 s1 s2 s3 P
0 0 2 1 1 0
1 0 -4 0 1 0
0 1 5 0 2 0
0 0 -6 0 -5 1
4
2
3
11
18
T
D
x1 x2 s1 s2 s3 P
2 1 1 0 0 0
3 0 1 1 0 0
0 0 2 0 1 0
-4 0 -3 0 0 1
4
4
8
2
5
T
C
x1 x2 s1 s2 P
1 6 1 0 0
3 1 0 1 0
-1 -2 0 0 1
3
36
5
0
S
C
x1 x2 s1 s2 P
1 4 1 0 0
3 5 0 1 0
-8 -5 0 0 1
3
4
24
0
S
D
x1 x2 x3 s1 s2 s3 P
0 2 -1 1 4 0 0
0 1 2 0 -2 1 0
1 3 0 0 5 0 0
0 -5 4 0 -3 0 1
4
5
2
11
27
T
D
x1 x2 x3 s1 s2 s3 P
-2 0 1 3 1 0 0
0 1 0 -2 0 0 0
-1 0 0 4 1 1 0
-4 0 0 2 4 0 1
4
5
15
12
45
T
C
x1 x2 s1 s2 P
1 4 -2 0 0
0 2 3 1 0
0 5 6 0 1
3
10
25
35
S
C
x1 x2 s1 s2 P
2 1 0 3 0
3 0 1 -2 0
-4 0 0 4 1
3
12
15
50
S
In Problems 9–12,
(A) Using slack variables, write the initial system for each linear
programming problem.
(B) Write the simplex tableau, circle the first pivot, and identify
the entering and exiting variables.
(C) Use the simplex method to solve the problem.
9.
10.
11. Repeat Problem 9 with the objective function changed to
12. Repeat Problem 10 with the objective function changed to
B
Solve the linear programming problems in Problems 13–28 using
the simplex method.
13.
14.
15.
16. Repeat Problem 15 with
17.
18. Repeat Problem 17 with
19.
20.
x1, x2, x3 U 0
3×1 + 2×2 + 2×3 … 22
subject to x1 + 2×2 – x3 … 5
Maximize P = 4×1 – 3×2 + 2×3
x1, x2, x3 U 0
2×1 + 4×2 + 3×3 … 30
subject to x1 + x2 – x3 … 10
Maximize P = 5×1 + 2×2 – x3
P = x1 + 2×2.
x1, x2 U 0
x1 – 4×2 … 4
-x1 + 3×2 … 12
subject to -x1 + x2 … 2
Maximize P = -x1 + 2×2
P = -x1 + 3×2.
x1, x2 U 0
x2 … 6
-x1 + x2 … 5
subject to -2×1 + x2 … 2
Maximize P = 2×1 + 3×2
x1, x2 U 0
x1 + 2×2 … 10
x1 + x2 … 6
subject to 2×1 + x2 … 9
Maximize P = 15×1 + 20×2
x1, x2 U 0
x1 + 2×2 … 12
x1 + x2 … 7
subject to 2×1 + x2 … 10
Maximize P = 30×1 + 40×2
P = x1 + 3×2.
P = 30×1 + x2.
x1, x2 U 0
3×1 + 2×2 … 16
subject to 5×1 + 2×2 … 20
Maximize P = 3×1 + 2×2
x1, x2 U 0
x1 + 3×2 … 10
subject to 2×1 + x2 … 10
Maximize P = 15×1 + 10×2
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
Prkentaice Hjalol. Ckopyarig htj ©20k11 Pjeaorsokn Eadu cajtioon,
300 CHAPTER 6 Linear Programming: The Simplex Method
21.
22.
23.
24.
C
25.
26. Repeat Problem 25 with
27.
28.
In Problems 29 and 30, first solve the linear programming problem
by the simplex method, keeping track of the basic feasible solutions
at each step.Then graph the feasible region and illustrate the path to
the optimal solution determined by the simplex method.
29.
30.
Solve Problems 31 and 32 by the simplex method and also by the
geometric method. Compare and contrast the results.
31.
x1, x2 U 0
x2 … 10
subject to -2×1 + x2 … 4
Maximize P = 2×1 + 3×2
x1, x2 U 0
x1 … 10
4×1 + x2 … 42
2×1 + x2 … 28
subject to 5×1 + 4×2 … 100
Maximize P = 5×1 + 3×2
x1, x2 U 0
x2 … 14
x1 + 4×2 … 60
x1 + 3×2 … 48
subject to x1 + 2×2 … 40
Maximize P = 2×1 + 5×2
x1, x2, x3 U 0
3×1 + 6×2 + 9×3 … 108
6×1 – 2×2 + 4×3 … 48
subject to 3×1 + 3×2 + 3×3 … 66
Maximize P = 10×1 + 50×2 + 10×3
x1, x2, x3 U 0
3×1 + 2×2 + x3 … 400
x1 + 3×2 + 2×3 … 600
subject to 2×1 + 2×2 + 8×3 … 600
Maximize P = x1 + 2×2 + 3×3
P = 20×1 + 20×2.
x1, x2 U 0
0.3×1 + 0.2×2 … 270
0.03×1 + 0.04×2 … 36
subject to 0.6×1 + 1.2×2 … 960
Maximize P = 20×1 + 30×2
x1, x2, x3 U 0
x1 + 3×2 + 2×3 … 20
2×1 + 3×2 + x3 … 20
subject to x1 + x2 + x3 … 11
Maximize P = 4×1 + 2×2 + 3×3
x1, x2, x3 U 0
x1 + x2 + 2×3 … 7
2×1 + x2 + x3 … 8
subject to 3×1 + 2×2 + 5×3 … 23
Maximize P = 4×1 + 3×2 + 2×3
x1, x2, x3 U 0
2×1 + x2 + 2×3 … 28
subject to x1 – 2×2 + x3 … 9
Maximize P = x1 + x2 + 2×3
x1, x2, x3 U 0
x2 + x3 … 3
subject to x1 + x3 … 4
Maximize P = 2×1 + 3×2 + 4×3 32.
In Problems 33–36, there is a tie for the choice of the first pivot
column. Use the simplex method to solve each problem two different
ways: first by choosing column 1 as the first pivot column,
and then by choosing column 2 as the first pivot column. Discuss
the relationship between these two solutions.
33.
34.
35.
36.
Applications
In Problems 37–50, construct a mathematical model in the form
of a linear programming problem. (The answers in the back of the
book for these application problems include the model.) Then
solve the problem using the simplex method. Include an interpretation
of any nonzero slack variables in the optimal solution.
37. Manufacturing: resource allocation. A small company
manufactures three different electronic components for
computers. Component A requires 2 hours of fabrication
and 1 hour of assembly; component B requires 3 hours of
fabrication and 1 hour of assembly; and component C
requires 2 hours of fabrication and 2 hours of assembly.The
company has up to 1,000 labor-hours of fabrication time
and 800 labor-hours of assembly time available per week.
The profit on each component, A, B, and C, is $7, $8, and
$10, respectively. How many components of each type
should the company manufacture each week in order to
maximize its profit (assuming that all components manufactured
can be sold)? What is the maximum profit?
38. Manufacturing: resource allocation. Solve Problem 37 with
the additional restriction that the combined total number of
components produced each week cannot exceed 420. Discuss
the effect of this restriction on the solution to Problem 37.
39. Investment. An investor has at most $100,000 to invest in
government bonds, mutual funds, and money market funds.
The average yields for government bonds, mutual funds,
and money market funds are 8%, 13%, and 15%, respectively.
The investor’s policy requires that the total amount
x1, x2, x3 U 0
2×1 + 4×2 + 5×3 … 24
subject to x1 + x2 + 3×3 … 10
Maximize P = 2×1 + 2×2 + x3
x1, x2, x3 U 0
2×1 + x2 + 4×3 … 32
subject to x1 + x2 + 2×3 … 20
Maximize P = 3×1 + 3×2 + 2×3
x1, x2 U 0
x2 … 4
x1 … 6
subject to x1 + 2×2 … 10
Maximize P = x1 + x2
x1, x2 U 0
x2 … 10
x1 … 6
subject to 2×1 + x2 … 16
Maximize P = x1 + x2
x1, x2 U 0
x2 … 4
subject to -x1 + x2 … 2
Maximize P = 2×1 + 3×2
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
bjyo Prkentiace Hjalol. Ckopyarigh tj ©20k11 Pjeaorsokn Eaduc ajtioon,
SECTION 6-2 The Simplex Method: Maximization with Problem Constraints of the Form … 301
invested in mutual and money market funds not exceed the
amount invested in government bonds. How much should
be invested in each type of investment in order to maximize
the return? What is the maximum return?
40. Investment. Repeat Problem 39 under the additional
assumption that no more than $30,000 can be invested in
money market funds.
41. Advertising. A department store has up to $20,000 to
spend on television advertising for a sale. All ads will be
placed with one television station. A 30-second ad costs
$1,000 on daytime TV and is viewed by 14,000 potential customers,
$2,000 on prime-time TV and is viewed by 24,000
potential customers, and $1,500 on late-night TV and is
viewed by 18,000 potential customers.The television station
will not accept a total of more than 15 ads in all three time
periods. How many ads should be placed in each time
period in order to maximize the number of potential
customers who will see the ads? How many potential customers
will see the ads? (Ignore repeated viewings of the ad
by the same potential customer.)
42. Advertising. Repeat Problem 41 if the department store
increases its budget to $24,000 and requires that at least half
of the ads be placed during prime-time.
43. Home construction. A contractor is planning a new housing
development consisting of colonial, split-level, and ranchstyle
houses. A colonial house requires acre of land,
$60,000 capital, and 4,000 labor-hours to construct, and
returns a profit of $20,000. A split-level house requires acre
of land, $60,000 capital, and 3,000 labor-hours to construct,
and returns a profit of $18,000. A ranch house requires
1 acre of land, $80,000 capital, and 4,000 labor-hours to construct,
and returns a profit of $24,000. The contractor has
30 acres of land, $3,200,000 capital, and 180,000 labor-hours
available. How many houses of each type should be constructed
to maximize the contractor’s profit? What is the
maximum profit?
44. Bicycle manufacturing. A company manufactures threespeed,
five-speed, and ten-speed bicycles. Each bicycle passes
through three departments: fabrication, painting & plating,
and final assembly. The relevant manufacturing data are
given in the table.
12
1
2
46. Bicycle manufacturing. Repeat Problem 44 if the profit on
a ten-speed bicycle increases from $100 to $110 and all
other data remain the same. If the slack associated with any
problem constraint is nonzero, find it.
47. Home building. Repeat Problem 43 if the profit on a colonial
house increases from $20,000 to $25,000 and all other
data remain the same. If the slack associated with any problem
constraint is nonzero, find it.
48. Bicycle manufacturing. Repeat Problem 44 if the profit on
a five-speed bicycle increases from $70 to $110 and all other
data remain the same. If the slack associated with any problem
constraint is nonzero, find it.
49. Animal nutrition. The natural diet of a certain animal consists
of three foods: A, B, and C. The number of units of
calcium, iron, and protein in 1 gram of each food and the
average daily intake are given in the table. A scientist
wants to investigate the effect of increasing the protein in
the animal’s diet while not allowing the units of calcium
and iron to exceed their average daily intakes. How many
grams of each food should be used to maximize the
amount of protein in the diet? What is the maximum
amount of protein?
Labor-Hours
per Bicycle
Maximum
Labor-Hours
Three-
Speed
Five-
Speed
Ten-
Speed
Available
per Day
Fabrication 3 4 5 120
Painting & plating 5 3 5 130
Final assembly 4 3 5 120
Profit per bicycle ($) 80 70 100
Units per Gram
Food
A
Food
B
Food
C
Average Daily
Intake (units)
Calcium 1 3 2 30
Iron 2 1 2 24
Protein 3 4 5 60
50. Animal nutrition. Repeat Problem 49 if the scientist wants
to maximize the daily calcium intake while not allowing the
intake of iron or protein to exceed the average daily intake.
51. Opinion survey. A political scientist received a grant to fund
a research project on voting trends. The budget includes
$3,200 for conducting door-to-door interviews on the day
before an election. Undergraduate students, graduate students,
and faculty members will be hired to conduct the interviews.
Each undergraduate student will conduct 18 interviews
for $100. Each graduate student will conduct 25 interviews
for $150. Each faculty member will conduct 30 interviews for
$200. Due to limited transportation facilities, no more than
20 interviewers can be hired. How many undergraduate students,
graduate students, and faculty members should be hired
in order to maximize the number of interviews? What is the
maximum number of interviews?
52. Opinion survey. Repeat Problem 51 if one of the requirements
of the grant is that at least 50% of the interviewers be
undergraduate students.
Answers to Matched Problems
1. Max when and
2. No optimal solution
3. 40 acres of crop A, 60 acres of crop B, no crop C;
max (since $240 out of the $3,600
will not be spent).
P = $17,600 s2 = 240,
P = 6 x1 = 1 x2 = 4
How many bicycles of each type should the company manufacture
per day in order to maximize its profit? What is the
maximum profit?
45. Home building. Repeat Problem 43 if the profit on a colonial
house decreases from $20,000 to $17,000 and all other
data remain the same. If the slack associated with any problem
constraint is nonzero, find it.
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
Prkentaice Hjalol. Ckopyarig htj ©20k11 Pjeaorsokn Eadu cajtioon,
302 CHAPTER 6 Linear Programming: The Simplex Method
6-3 The Dual Problem: Minimization with
Problem Constraints of the Form ≫
• Formation of the Dual Problem
• Solution of Minimization
Problems
• Application: Transportation
Problem
• Summary of Problem Types and
Solution Methods
In the preceding section, we restricted attention to standard maximization problems
(problem constraints of the form with non-negative constants on the right and
any real numbers as objective function coefficients). Now we will consider minimization
problems with problem constraints. These two types of problems turn
out to be very closely related.
Formation of the Dual Problem
Associated with each minimization problem with constraints is a maximization
problem called the dual problem. To illustrate the procedure for forming the dual
problem, consider the following minimization problem:
(1)
The first step in forming the dual problem is to construct a matrix using the
problem constraints and the objective function written in the following form:
CAUTION Do not confuse matrix A with the simplex tableau.We use a solid
horizontal line in matrix A to help distinguish the dual matrix from the simplex
tableau. No slack variables are involved in matrix A, and the coefficient of C is in
the same column as the constants from the problem constraints.
Now we will form a second matrix called the transpose of A. In general, the
transpose of a given matrix A is the matrix formed by interchanging the rows and
corresponding columns of A (first row with first column, second row with second
column, and so on).
AT
2×1 + 5×2 U 50
x1 + 3×2 U 27
16×1 + 45×2 = C
A = C
2 5
1 3
16 45
3
50
27
1
S
Minimize C = 16×1 + 45×2
subject to 2×1 + 5×2 U 50
x1 + 3×2 U 27
x1, x2 U 0
U
U
…,
2 5 50 R1 in A=C1 in AT
A=C 1 3 3 27 S R2 in A=C2 in AT
16 45 1 R3 in A=C3 in AT
2 1 16
AT=C 5 3 3 45 S AT is the transpose of A.
50 27 1
We can use the rows of to define a new linear programming problem. This
new problem will always be a maximization problem with problem constraints.To
avoid confusion, we will use different variables in this new problem:
2y1 + y2 … 16
5y1 + 3y2 … 45
50y1 + 27y2 = P
AT =
y1 y2
C
2 1
5 3
50 27
3
16
45
1
S
…
AT
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
bjyo Prkentiace Hjalol. Ckopyarigh tj ©20k11 Pjeaorsokn Eaduc ajtioon,
SECTION 6-3 The Dual Problem: Minimization with Problem Constraints of the Form U 303
EXPLORE & DISCUSS 1 Excluding the non-negative constraints, the components of a linear programming
problem can be divided into three categories: the coefficients of the objective function,
the coefficients of the problem constraints, and the constants on the right side
of the problem constraints. Write a verbal description of the relationship between
the components of the original minimization problem (1) and the dual maximization
problem (2).
The procedure for forming the dual problem is summarized in the following box:
PROCEDURE Formation of the Dual Problem
Given a minimization problem with problem constraints,
Step 1 Use the coefficients and constants in the problem constraints and the
objective function to form a matrix A with the coefficients of the objective
function in the last row.
Step 2 Interchange the rows and columns of matrix A to form the matrix the
transpose of A.
Step 3 Use the rows of to form a maximization problem with problem
constraints.
AT …
AT,
U
The dual of the minimization problem (1) is the following maximization problem:
(2)
Maximize P = 50y1 + 27y2
subject to 2y1 + y2 … 16
5y1 + 3y2 … 45
y1, y2 U 0
EXAMPLE 1 Forming the Dual Problem Form the dual problem:
SOLUTION Step 1 Form the matrix A:
Step 2 Form the matrix the transpose of A:
Step 3 State the dual problem:
y1, y2 U 0
5y1 + y2 … 40
y1 + y2 … 12
subject to 2y1 + 4y2 … 40
Maximize P = 20y1 + 30y2
AT = D
2 4
1 1
5 1
20 30
4
40
12
40
1
T
AT,
A = C
2 1 5
4 1 1
40 12 40
3
20
30
1
S
Minimize C = 40×1 + 12×2 + 40×3
subject to 2×1 + x2 + 5×3 U 20
4×1 + x2 + x3 U 30
x1, x2, x3 U 0
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
Prkentaice Hjalol. Ckopyarig htj ©20k11 Pjeaorsokn Eadu cajtioon,
304 CHAPTER 6 Linear Programming: The Simplex Method
Matched Problem 1 Form the dual problem:
Solution of Minimization Problems
The following theorem establishes the relationship between the solution of a minimization
problem and the solution of its dual problem:
x1, x2, x3 U 0
2×1 + x2 + x3 U 16
subject to x1 + x2 + 3×3 U 12
Minimize C = 16×1 + 9×2 + 21×3
THEOREM 1 Fundamental Principle of Duality
A minimization problem has a solution if and only if its dual problem has a solution.
If a solution exists, then the optimal value of the minimization problem is the
same as the optimal value of the dual problem.
x1
x2
10 20
20
10
30
(0, 10)
(15, 4)
(27, 0) 5 10 15
5
10
15
(8, 0)
(0, 15)
(3, 10)
y1
y2
(0, 0)
ORIGINAL PROBLEM (1)
x1, x2 U 0
x1 + 3×2 U 27
subject to 2×1 + 5×2 U 50
Minimize C = 16×1 + 45×2
DUAL PROBLEM (2)
y1, y2 U 0
5y1 + 3y2 … 45
subject to 2y1 + y2 … 16
Maximize P = 50y1 + 27y2
Note that the minimum value of C in problem (1) is the same as the maximum
value of P in problem (2). The optimal solutions producing this optimal value are
different: (15, 4) is the optimal solution for problem (1), and (3, 10) is the optimal
solution for problem (2). Theorem 1 only guarantees that the optimal values of a
minimization problem and its dual are equal, not that the optimal solutions are the
same. In general, it is not possible to determine an optimal solution for a minimization
problem by examining the feasible set for the dual problem. However, it is
possible to apply the simplex method to the dual problem and find both the optimal
value and an optimal solution to the original minimization problem. To see
how this is done, we will solve problem (2) using the simplex method.
Corner Point
(x1, x2) C = 16×1 + 45×2
(0, 10) 450
(15, 4) 420
(27, 0) 432
Corner Point
(y1, y2) P = 50y1 + 27y2
(0, 0) 0
(0, 15) 405
(3, 10) 420
Min C = 420 at (15, 4) (8, 0) 400
Max P = 420 at (3, 10)
The proof of Theorem 1 is beyond the scope of this text. However, we can illustrate
Theorem 1 by solving minimization problem (1) and its dual maximization
problem (2) geometrically. (Note that Theorem 2, Section 5-3, guarantees that both
problems have solutions.)
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
bjyo Prkentiace Hjalol. Ckopyarigh tj ©20k11 Pjeaorsokn Eaduc ajtioon,
SECTION 6-3 The Dual Problem: Minimization with Problem Constraints of the Form U 305
For reasons that will become clear later, we will use the variables and from
the original problem as the slack variables in the dual problem:
Initial system for the dual problem
-50y1 – 27y2 + P = 0
5y1 + 3y2 + x2 = 45
2y1 + y2 + x1 = 16
x1 x2
y¡ y™ x¡ x™ P
2 1 1 0 0 16 0.5R1 B R1
C 5 3 0 1 0 3 45 S
–50 –27 0 0 1 0
1 0.5 0.5 0 0 8
C 5 3 0 1 0 3 45 S (–5)R1+R2 B R2
–50 –27 0 0 1 0 50R1+R3 B R3
_
x2
x1
P
1 0.5 0.5 0 0 8
C 0 0.5 –2.5 1 0 3 5 S 2R2 B R2
0 –2 25 0 1 400
1 0.5 0.5 0 0 8 (–0.5)R2+R1 B R1
C 0 1 –5 2 0 3 10 S
0 –2 25 0 1 400 2R2+R3 B R3
1 0 3 –1 0 3
C 0 1 –5 2 0 3 10 S
0 0 15 4 1 420
_
_ x2
y1
P
_
y1
y2
P
Since all indicators in the bottom row are non-negative, the solution to the dual
problem is
which agrees with our earlier geometric solution. Furthermore, examining the bottom
row of the final simplex tableau, we see the same optimal solution to the minimization
problem that we obtained directly by the geometric method:
This is no accident.
An optimal solution to a minimization problem always can be
obtained from the bottom row of the final simplex tableau for the
dual problem.
We can see that using and as slack variables in the dual problem makes it
easy to identify the solution of the original problem.
x1 x2
Min C = 420 at x1 = 15, x2 = 4
y1 = 3, y2 = 10, x1 = 0, x2 = 0, P = 420
EXPLORE & DISCUSS 2 The simplex method can be used to solve any standard maximization problem.
Which of the following minimization problems have dual problems that are standard
maximization problems? (Do not solve the problems.)
(A)
x1, x2 U 0
x1 – 3×2 U -6
subject to 2×1 – 5×2 U 4
Minimize C = 2×1 + 3×2
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
Prkentaice Hjalol. Ckopyarig htj ©20k11 Pjeaorsokn Eadu cajtioon,
306 CHAPTER 6 Linear Programming: The Simplex Method
PROCEDURE Solution of a Minimization Problem
Given a minimization problem with non-negative coefficients in the objective
function,
Step 1 Write all problem constraints as inequalities. (This may introduce negative
numbers on the right side of some problem constraints.)
Step 2 Form the dual problem.
Step 3 Write the initial system of the dual problem, using the variables from the
minimization problem as slack variables.
Step 4 Use the simplex method to solve the dual problem.
Step 5 Read the solution of the minimization problem from the bottom row of
the final simplex tableau in step 4.
Note: If the dual problem has no optimal solution, the minimization problem has
no optimal solution.
U
EXAMPLE 2 Solving a Minimization Problem Solve the following minimization problem by
maximizing the dual problem:
SOLUTION From Example 1, the dual problem is
Using and for slack variables, we obtain the initial system for the dual
problem:
-20y1 – 30y2 + P = 0
5y1 + y2 + x3 = 40
y1 + y2 + x2 = 12
2y1 + 4y2 + x1 = 40
x1, x2, x3
y1, y2 U 0
5y1 + y2 … 40
y1 + y2 … 12
subject to 2y1 + 4y2 … 40
Maximize P = 20y1 + 30y2
x1, x2, x3 U 0
4×1 + x2 + x3 U 30
subject to 2×1 + x2 + 5×3 U 20
Minimize C = 40×1 + 12×2 + 40×3
(B)
What conditions must a minimization problem satisfy so that its dual problem is a
standard maximization problem?
x1, x2 U 0
-x1 + 3×2 U 6
subject to -2×1 + 5×2 U 4
Minimize C = 2×1 – 3×2
The procedure for solving a minimization problem by applying the simplex
method to its dual problem is summarized in the following box:
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
bjyo Prkentiace Hjalol. Ckopyarigh tj ©20k11 Pjeaorsokn Eaduc ajtioon,
SECTION 6-3 The Dual Problem: Minimization with Problem Constraints of the Form U 307
Now we form the simplex tableau and solve the dual problem:
y¡ y™ x¡ x™ x£ P
2 4 1 0 0 0 40 R1 B R1
D
5 1 0 0 1 0
4
40
T
–20 –30 0 0 0 1 0
1 0 0 0 10
1 1 0 1 0 0 12 (–1)R1+R2 B R2
D
5 1 0 0 1 0
4
40
T
(–1)R1+R3 B R3
–20 –30 0 0 0 1 0 30R1+R4 B R4
14
1
2
1
4
P
x2
x3
x1
_
1 1 0 1 0 0 12
1 0 0 0 10
0 – 1 0 0 2
D
0 – 0 1 0
4
30
T
–5 0 0 0 1 300
1 0 0 0 10
1 0 – 2 0 0 4
D
0 – 0 1 0
4
30
T
–5 0 0 0 1 300
0 1 –1 0 0 8
1 0 – 2 0 0 4
D
0 0 2 –9 1 0
4
12
T
0 0 5 10 0 1 320
12 92
12
12
92
1292
14
1412
1212
14
1414
15
2
15
2
_
P
x3
x2
y2
_
P
x3
y2
_
y1
From the bottom row of this tableau, we see that
Min C = 320 at x1 = 5, x2 = 10, x3 = 0
Matched Problem 2 Solve the following minimization problem by maximizing the dual problem (see
Matched Problem 1):
x1, x2, x3 U 0
2×1 + x2 + x3 U 16
subject to x1 + x2 + 3×3 U 12
Minimize C = 16×1 + 9×2 + 21×3
CONCEPTUAL INSIGHT
In Section 6-2, we noted that multiplying a problem constraint by a number changes the
units of the slack variable.This requires special interpretation of the value of the slack
variable in the optimal solution, but causes no serious problems. However, when using the
dual method, multiplying a problem constraint in the dual problem by a number can have
serious consequences—the bottom row of the final simplex tableau may no longer give
the correct solution to the minimization problem.To see this, refer to the first problem
constraint of the dual problem in Example 2:
If we multiply this constraint by and then solve, the final tableau is:
y1 y2 x1 x2 x3 P
D
0 1 1 -1 0 0
1 0 -1 2 0 0
0 0 4 -9 1 0
0 0 10 10 0 1
4
8
4
12
320
T
12
2y1 + 4y2 … 40
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
Prkentaice Hjalol. Ckopyarig htj ©20k11 Pjeaorsokn Eadu cajtioon,
308 CHAPTER 6 Linear Programming: The Simplex Method
EXAMPLE 3 Solving a Minimization Problem Solve the following minimization problem by
maximizing the dual problem:
SOLUTION
The dual problem is
Introduce slack variables and and form the initial system for the dual problem:
Form the simplex tableau and solve:
-y1 – 2y2 + P = 0
-y1 + y2 + x2 = 10
y1 – y2 + x1 = 5
x1 x2,
y1, y2 U 0
-y1 + y2 … 10
subject to y1 – y2 … 5
Maximize P = y1 + 2y2
AT = C
1 -1
-1 1
1 2
3
5
10
1
A = C S
1 -1
-1 1
5 10
3
1
2
1
S
x1, x2 U 0
-x1 + x2 U 2
subject to x1 – x2 U 1
Minimize C = 5×1 + 10×2
y¡ y™ x¡ x™ P
1 –1 1 0 0 5 R2+R1 B R1
C –1 1 0 1 0 3 10 S
–1 –2 0 0 1 0 2R2+R3 B R3
0 0 1 1 0 15
C –1 1 0 1 0 3 10 S
–3 0 0 2 1 20
a
Pivot column
_
P
x1
x2
No positive elements
above dashed line in
pivot column
x1
x2
5
_5
_5 5
_x1 _ x2 _ 2
_x1 _ x2 _ 2
x1 _ x2 _ 1
x1 _ x2 _ 1 A _ B__
A
B
Figure 1
The in the bottom row indicates that column 1 is the pivot column. Since no
positive elements appear in the pivot column above the dashed line, we are unable
to select a pivot row.We stop the pivot operation and conclude that this maximization
problem has no optimal solution (see Figure 2, Section 6-2). Theorem 1 now
implies that the original minimization problem has no solution. The graph of the
inequalities in the minimization problem (Fig. 1) shows that the feasible region is
empty; so it is not surprising that an optimal solution does not exist.
-3
Matched Problem 3 Solve the following minimization problem by maximizing the dual:
x1, x2 U 0
-x1 + x2 U 1
subject to x1 – 2×2 U 2
Minimize C = 2×1 + 3×2
The bottom row of this tableau indicates that the optimal solution to the minimization problem
is at and This is not the correct answer ( is the correct
answer).Thus, you should never multiply a problem constraint in a maximization problem by a
number if that maximization problem is being used to solve a minimization problem.You may
still simplify problem constraints in a minimization problem before forming the dual problem.
C = 320 x1 = 10 x2 = 10. x1 = 5
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
bjyo Prkentiace Hjalol. Ckopyarigh tj ©20k11 Pjeaorsokn Eaduc ajtioon,
SECTION 6-3 The Dual Problem: Minimization with Problem Constraints of the Form U 309
From A to I
Plant A
Outlet I
Plant B Outlet II
From B to II
From B to I
A to II From
Figure 2
Application: Transportation Problem
One of the first applications of linear programming was to minimize the cost of transporting
materials. Problems of this type are referred to as transportation problems.
Distribution Outlet Assembly
I II Capacity
Plant A $6 $5 700
Plant B $4 $8 900
Minimum required 500 1,000
Transportation Problem A computer manufacturing company has two assembly
plants, plant A and plant B, and two distribution outlets, outlet I and outlet II.
Plant A can assemble at most 700 computers a month, and plant B can assemble
at most 900 computers a month. Outlet I must have at least 500 computers a
month, and outlet II must have at least 1,000 computers a month.Transportation
costs for shipping one computer from each plant to each outlet are as follows: $6
from plant A to outlet I; $5 from plant A to outlet II; $4 from plant B to outlet I;
$8 from plant B to outlet II. Find a shipping schedule that minimizes the total cost
of shipping the computers from the assembly plants to the distribution outlets.
What is this minimum cost?
SOLUTION To form a shipping schedule, we must decide how many computers to ship from
either plant to either outlet (Fig. 2).This will involve four decision variables:
Next, we summarize the relevant data in a table. Note that we do not follow the
usual technique of associating each variable with a column of the table. Instead,
sources are associated with the rows, and destinations are associated with the
columns.
x4 = number of computers shipped from plant B to outlet II
x3 = number of computers shipped from plant B to outlet I
x2 = number of computers shipped from plant A to outlet II
x1 = number of computers shipped from plant A to outlet I
The total number of computers shipped from plant A is Since this cannot
exceed the assembly capacity at A, we have
Number shipped from plant A
Similarly, the total number shipped from plant B must satisfy
Number shipped from plant B
The total number shipped to each outlet must satisfy
Number shipped to outlet I
and
Number shipped to outlet II
Using the shipping charges in the table, the total shipping charges are
We must solve the following linear programming problem:
Available from A
Available from B
Required at I
Required at II
x1, x2, x3, x4 U 0
x2 + x4 U 1,000
x1 + x3 U 500
x3 + x4 … 900
subject to x1 + x2 … 700
Minimize C = 6×1 + 5×2 + 4×3 + 8×4
C = 6×1 + 5×2 + 4×3 + 8×4
x2 + x4 U 1,000
x1 + x3 U 500
x3 + x4 … 900
x1 + x2 … 700
x1 + x2.
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
Prkentaice Hjalol. Ckopyarig htj ©20k11 Pjeaorsokn Eadu cajtioon,
–1 0 1 0 1 0 0 0 0 6
–1 0 0 1 0 1 0 0 0 5
E 0 –1 1 0 0 0 1 0 0 5 4 U
0 –1 0 1 0 0 0 1 0 8
700 900 –500 –1,000 0 0 0 0 1 0
–1 0 1 0 1 0 0 0 0 6
–1 0 0 1 0 1 0 0 0 5
E 0 –1 1 0 0 0 1 0 0 5 4 U
1 –1 0 0 0 –1 0 1 0 3
–300 900 –500 0 0 1,000 0 0 1 5,000
_
P
x1
x2
x3
x4
x1 x2 x3
x4
y1 y2 y3 y4
y4
P
x1
x3
x4
P
310 CHAPTER 6 Linear Programming: The Simplex Method
Before we can solve this problem, we must multiply the first two constraints
by so that all the problem constraints are of the type. This will introduce
negative constants into the minimization problem but not into the dual problem.
Since the coefficients of C are non-negative, the constants in the dual problem
will be non-negative and the dual will be a standard maximization problem. The
problem can now be stated as
The dual problem is
Introduce slack variables and and form the initial system for the
dual problem:
Form the simplex tableau and solve:
-y1 + y3 + x1 = 6
-y1 + y4 + x2 = 5
-y2 + y3 + x3 = 4
-y2 + y4 + x4 = 8
700y1 + 900y2 – 500y3 – 1,000y4 + P = 0
x1, x2, x3, x4,
y1, y2, y3, y4 U 0
-y2 + y4 … 8
-y2 + y3 … 4
-y1 + y4 … 5
subject to -y1 + y3 … 6
Maximize P = -700y1 – 900y2 + 500y3 + 1,000y4
AT = E
-1 0 1 0
-1 0 0 1
0 -1 1 0
0 -1 0 1
-700 -900 500 1,000
5
6
5
4
8
1
U
A = E
-1 -1 0 0
0 0 -1 -1
1 0 1 0
0 1 0 1
6 5 4 8
5
-700
-900
500
1,000
1
U
x1, x2, x3, x4 U 0
x2 + x4 U 1,000
x1 + x3 U 500
– x3 – x4 U -900
subject to -x1 – x2 U -700
Minimize C = 6×1 + 5×2 + 4×3 + 8×4
-1 U
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
bjyo Prkentiace Hjalol. Ckopyarigh tj ©20k11 Pjeaorsokn Eaduc ajtioon,
SECTION 6-3 The Dual Problem: Minimization with Problem Constraints of the Form U 311
From the bottom row of this tableau, we have
The shipping schedule that minimizes the shipping charges is 700 from plant A to
outlet II, 500 from plant B to outlet I, and 300 from plant B to outlet II.The total
shipping cost is $7,900.
Figure 3 shows a solution to Example 4 in Excel. Notice that Excel permits the
user to organize the original data and the solution in a format that is clear and easy
to read.This is one of the main advantages of using spreadsheets to solve linear programming
problems.
Min C = 7,900 at x1 = 0, x2 = 700, x3 = 500, x4 = 300
–1 0 0 1 0 1 0 0 0 5
E 0 –1 1 0 0 0 1 0 0 5 4 U
1 –1 0 0 0 –1 0 1 0 3
–300 400 0 0 0 1,000 500 0 1 7,000
0 0 0 0 1 –1 –1 1 0 5
0 –1 0 1 0 0 0 1 0 8
E 0 –1 1 0 0 0 1 0 0 5 4 U
1 –1 0 0 0 –1 0 1 0 3
0 100 0 0 0 700 500 300 1 7,900
–1 1 0 0 1 0 –1 0 0 2
_
_
P
y4
y3
x4
y4
P
x1
x1
y3
y1
x1 x2
x3
x4
y1 y2 y3 y4 P
Figure 3
Table 1 Summary of Problem Types and Simplex Solution Methods
Problem Type
Problem
Constraints
Right-Side
Constants
Coefficients of
Objective Function Method of Solution
1. Maximization … Non-negative Any real numbers Simplex method with
slack variables
2. Minimization U Any real numbers Non-negative Form dual and solve by simplex
method with slack variables
Matched Problem 4 Repeat Example 4 if the shipping charge from plant A to outlet I is increased to
$7 and the shipping charge from plant B to outlet II is decreased to $3.
Summary of Problem Types and Solution Methods
In this and the preceding sections, we have solved both maximization and minimization
problems, but with certain restrictions on the problem constraints, constants on
the right, and/or objective function coefficients. Table 1 summarizes the types of
problems and methods of solution we have considered so far.
The next section develops a generalized version of the simplex method that can
handle both maximization and minimization problems with any combination of
…, U, and = problem constraints.
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
Prkentaice Hjalol. Ckopyarig htj ©20k11 Pjeaorsokn Eadu cajtioon,
312 CHAPTER 6 Linear Programming: The Simplex Method
Exercises 6-3
A
In Problems 1–8, find the transpose of each matrix.
1. 2.
3. 4.
5. 6.
7. 8.
In Problems 9 and 10,
(A) Form the dual problem.
(B) Write the initial system for the dual problem.
(C) Write the initial simplex tableau for the dual problem and
label the columns of the tableau.
9.
10.
In Problems 11 and 12, a minimization problem, the corresponding
dual problem, and the final simplex tableau in the solution of
the dual problem are given.
(A) Find the optimal solution of the dual problem.
(B) Find the optimal solution of the minimization problem.
11.
12. Minimize C = 16×1 + 25×2
subject to 3×1 + 5×2 U 30
2×1 + 3×2 U 19
x1, x2 U 0
y1 y2 x1 x2 P
C
0 1 5 -2 0
1 0 -7 3 0
0 0 1 2 1
3
5
3
121
S
Maximize P = 12y1 + 17y2
subject to 2y1 + 3y2 … 21
5y1 + 7y2 … 50
y1, y2 U 0
Minimize C = 21×1 + 50×2
subject to 2×1 + 5×2 U 12
3×1 + 7×2 U 17
x1, x2 U 0
Minimize C = 12×1 + 5×2
subject to 2×1 + x2 U 7
3×1 + x2 U 9
x1, x2 U 0
Minimize C = 8×1 + 9×2
subject to x1 + 3×2 U 4
2×1 + x2 U 5
x1, x2 U 0
E
1 -1 3 2
1 -4 0 2
4 -5 6 1
-3 8 0 -1
2 7 -3 1
D U
1 2 -1
0 2 -7
8 0 1
4 -1 3
T
c
7 3 -1 3
-6 1 0 -9
c d
2 1 -6 0 -1
5 2 0 1 3
d
D
9
5
-4
0
D T
1
-2
0
4
T
[-5 0 3 -1 8] [1 0 -7 3 -2]
In Problems 13–20,
(A) Form the dual problem.
(B) Find the solution to the original problem by applying the
simplex method to the dual problem.
13.
14.
15.
16.
17.
18.
19.
20. Minimize C = 10×1 + 15×2
subject to -4×1 + x2 U 12
12×1 – 3×2 U 10
x1, x2 U 0
Minimize C = 7×1 + 9×2
subject to -3×1 + x2 U 6
x1 – 2×2 U 4
x1, x2 U 0
Minimize C = 40×1 + 10×2
subject to 2×1 + x2 U 12
3×1 – x2 U 3
x1, x2 U 0
Minimize C = 11×1 + 4×2
subject to 2×1 + x2 U 8
-2×1 + 3×2 U 4
x1, x2 U 0
Minimize C = 3×1 + 5×2
subject to 2×1 + 3×2 U 7
x1 + 2×2 U 4
x1, x2 U 0
Minimize C = 7×1 + 12×2
subject to 2×1 + 3×2 U 15
x1 + 2×2 U 8
x1, x2 U 0
Minimize C = x1 + 4×2
subject to x1 + 2×2 U 5
x1 + 3×2 U 6
x1, x2 U 0
Minimize C = 9×1 + 2×2
subject to 4×1 + x2 U 13
3×1 + x2 U 12
x1, x2 U 0
C
y1 y2 x1 x2 P
0 1 5 -3 0
1 0 -3 2 0
0 0 5 3 1
3
5
2
155
S
Maximize P = 30y1 + 19y2
subject to 3y1 + 2y2 … 16
5y1 + 3y2 … 25
y1, y2 U 0
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
bjyo Prkentiace Hjalol. Ckopyarigh tj ©20k11 Pjeaorsokn Eaduc ajtioon,
SECTION 6-3 The Dual Problem: Minimization with Problem Constraints of the Form U 313
B
Solve the linear programming problems in Problems 21–32 by
applying the simplex method to the dual problem.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30. Minimize C = 14×1 + 8×2 + 20×3
subject to x1 + x2 + 3×3 U 6
2×1 + x2 + x3 U 9
x1, x2, x3 U 0
Minimize C = 10×1 + 7×2 + 12×3
subject to x1 + x2 + 2×3 U 7
2×1 + x2 + x3 U 4
x1, x2, x3 U 0
Minimize C = 4×1 + 5×2
subject to 2×1 + x2 U 12
x1 + x2 U 9
x2 U 4
x1, x2 U 0
Minimize C = 5×1 + 7×2
subject to x1 U 4
x1 + x2 U 8
x1 + 2×2 U 10
x1, x2 U 0
Minimize C = 40×1 + 10×2
subject to 3×1 + x2 U 24
x1 + x2 U 16
x1 + 4×2 U 30
x1, x2 U 0
Minimize C = 10×1 + 30×2
subject to 2×1 + x2 U 16
x1 + x2 U 12
x1 + 2×2 U 14
x1, x2 U 0
Minimize C = 10×1 + 4×2
subject to 2×1 + x2 U 6
x1 – 4×2 U -24
-8×1 + 5×2 U -24
x1, x2 U 0
Minimize C = 7×1 + 5×2
subject to x1 + x2 U 4
x1 – 2×2 U -8
-2×1 + x2 U -8
x1, x2 U 0
Minimize C = 2×1 + x2
subject to x1 + x2 U 8
x1 + 2×2 U 4
x1, x2 U 0
Minimize C = 3×1 + 9×2
subject to 2×1 + x2 U 8
x1 + 2×2 U 8
x1, x2 U 0
31.
32.
33. A minimization problem has 4 variables and 2 problem constraints.
How many variables and problem constraints are in
the dual problem?
34. A minimization problem has 3 variables and 5 problem constraints.
How many variables and problem constraints are in
the dual problem?
35. If you want to solve a minimization problem by applying the
geometric method to the dual problem, how many variables
and problem constraints must be in the original problem?
36. If you want to solve a minimization problem by applying
the geometric method to the original problem, how many
variables and problem constraints must be in the original
problem?
In Problems 37–40, determine whether a minimization problem
with the indicated condition can be solved by applying the simplex
method to the dual problem. If your answer is yes, describe
any necessary modifications that must be made before forming
the dual problem. If your answer is no, explain why.
37. A coefficient of the objective function is negative.
38. A coefficient of a problem constraint is negative.
39. A problem constraint is of the form.
40. A problem constraint has a negative constant on the right side.
C
Solve the linear programming problems in Problems 41–44 by
applying the simplex method to the dual problem.
41.
42.
43.
44. Repeat Problem 43 with C = 4×1 + 7×2 + 5×3 + 6×4.
x1, x2, x3, x4 U 0
x2 + x4 U 15
x1 + x3 U 20
x3 + x4 … 25
subject to x1 + x2 … 12
Minimize C = 5×1 + 4×2 + 5×3 + 6×4
Minimize C = 6×1 + 8×2 + 12×3
subject to x1 + 3×2 + 3×3 U 6
x1 + 5×2 + 5×3 U 4
2×1 + 2×2 + 3×3 U 8
x1, x2, x3 U 0
Minimize C = 16×1 + 8×2 + 4×3
subject to 3×1 + 2×2 + 2×3 U 16
4×1 + 3×2 + x3 U 14
5×1 + 3×2 + x3 U 12
x1, x2, x3 U 0
…
Minimize C = 6×1 + 8×2 + 3×3
subject to -3×1 – 2×2 + x3 U 4
x1 + x2 – x3 U 2
x1, x2, x3 U 0
Minimize C = 5×1 + 2×2 + 2×3
subject to x1 – 4×2 + x3 U 6
-x1 + x2 – 2×3 U 4
x1, x2, x3 U 0
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
Prkentaice Hjalol. Ckopyarig htj ©20k11 Pjeaorsokn Eadu cajtioon,
314 CHAPTER 6 Linear Programming: The Simplex Method
Applications
In Problems 45–54, construct a mathematical model in the form
of a linear programming problem. (The answers in the back of the
book for these application problems include the model.) Then
solve the problem by applying the simplex method to the dual
problem.
45. Ice cream. A food processing company produces regular
and deluxe ice cream at three plants. Per hour of operation,
the Cedarburg plant produces 20 gallons of regular ice
cream and 10 gallons of deluxe ice cream. The Grafton
plant produces 10 gallons of regular and 20 gallons of
deluxe, and the West Bend plant produces 20 gallons of regular
and 20 gallons of deluxe. It costs $70 per hour to operate
the Cedarburg plant, $75 per hour to operate the
Grafton plant, and $90 per hour to operate the West Bend
plant.The company needs to produce at least 300 gallons of
regular ice cream and at least 200 gallons of deluxe ice
cream each day. How many hours per day should each plant
operate in order to produce the required amounts of ice
cream and minimize the cost of production? What is the
minimum production cost?
46. Mining. A mining company operates two mines, each producing
three grades of ore.The West Summit mine can produce
2 tons of low-grade ore, 3 tons of medium-grade ore,
and 1 ton of high-grade ore in one hour of operation. The
North Ridge mine can produce 2 tons of low-grade ore,
1 ton of medium-grade ore, and 2 tons of high-grade ore in
one hour of operation. To satisfy existing orders, the company
needs to produce at least 100 tons of low-grade ore,
60 tons of medium-grade ore, and 80 tons of high-grade
ore. The cost of operating each mine varies, depending on
conditions while extracting the ore. If it costs $400 per hour
to operate the West Summit mine and $600 per hour to operate
the North Ridge mine, how many hours should each
mine operate to supply the required amounts of ore and
minimize the cost of production? What is the minimum
production cost?
47. Ice cream. Repeat Problem 45 if the demand for deluxe ice
cream increases from 200 gallons to 300 gallons per day and
all other data remain the same.
48. Mining. Repeat Problem 46 if it costs $300 per hour to
operate the West Summit mine and $700 per hour to operate
the North Ridge mine and all other data remain the same.
49. Ice cream. Repeat Problem 45 if the demand for deluxe ice
cream increases from 200 gallons to 400 gallons per day and
all other data remain the same.
50. Mining. Repeat Problem 46 if it costs $800 per hour to
operate the West Summit mine and $200 per hour to operate
the North Ridge mine and all other data remain the same.
51. Human nutrition. A dietitian arranges a special diet using
three foods: L, M, and N. Each ounce of food L contains
20 units of calcium, 10 units of iron, 10 units of vitamin A,
and 20 units of cholesterol. Each ounce of food M contains
10 units of calcium, 10 units of iron, 15 units of vitamin A, and
24 units of cholesterol. Each ounce of food N contains
10 units of calcium, 10 units of iron, 10 units of vitamin A, and
18 units of cholesterol. If the minimum daily requirements
are 300 units of calcium, 200 units of iron, and 240 units of
vitamin A, how many ounces of each food should be used to
meet the minimum requirements and simultaneously minimize
the cholesterol intake? What is the minimum cholesterol
intake?
52. Plant food. A farmer can buy three types of plant food:
mix A, mix B, and mix C. Each cubic yard of mix A
contains 20 pounds of phosphoric acid, 10 pounds of
nitrogen, and 10 pounds of potash. Each cubic yard of
mix B contains 10 pounds of phosphoric acid, 10 pounds
of nitrogen, and 15 pounds of potash. Each cubic yard of
mix C contains 20 pounds of phosphoric acid, 20 pounds
of nitrogen, and 5 pounds of potash. The minimum
monthly requirements are 480 pounds of phosphoric acid,
320 pounds of nitrogen, and 225 pounds of potash. If
mix A costs $30 per cubic yard, mix B costs $36 per cubic
yard, and mix C costs $39 per cubic yard, how many
cubic yards of each mix should the farmer blend to meet
the minimum monthly requirements at a minimal cost?
What is the minimum cost?
53. Education: resource allocation. A metropolitan school district
has two overcrowded high schools and two underenrolled
high schools. To balance the enrollment, the school
board decided to bus students from the overcrowded
schools to the underenrolled schools. North Division High
School has 300 more students than normal, and South Division
High School has 500 more students than normal. Central
High School can accommodate 400 additional students,
and Washington High School can accommodate 500 additional
students. The weekly cost of busing a student from
North Division to Central is $5, from North Division to
Washington is $2, from South Division to Central is $3, and
from South Division to Washington is $4. Determine the
number of students that should be bused from each overcrowded
school to each underenrolled school in order to
balance the enrollment and minimize the cost of busing the
students.What is the minimum cost?
54. Education: resource allocation. Repeat Problem 53 if the
weekly cost of busing a student from North Division to
Washington is $7 and all other data remain the same.
Answers to Matched Problems
1.
2.
3. Dual problem:
No optimal solution
4. 600 from plant A to outlet II, 500 from plant B to outlet I,
400 from plant B to outlet II; total shipping cost is $6,200
y1, y2 U 0
-2y1 + y2 … 3
subject to y1 – y2 … 2
Maximize P = 2y1 + y2
Min C = 136 at x1 = 4, x2 = 8, x3 = 0
Maximize P = 12y1 + 16y2
subject to y1 + 2y2 … 16
y1 + y2 … 9
3y1 + y2 … 21
y1, y2 U 0
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
bjyo Prkentiace Hjalol. Ckopyarigh tj ©20k11 Pjeaorsokn Eaduc ajtioon,
SECTION 6-4 Maximization and Minimization with Mixed Problem Constraints 315
6-4 Maximization and Minimization with
Mixed Problem Constraints
• Introduction to the Big MMethod
• Big MMethod
• Minimization by the Big M
Method
• Summary of Solution Methods
• Larger Problems: Refinery
Application
In the preceding two sections, we have seen how to solve both maximization and
minimization problems, but with rather severe restrictions on problem constraints,
right-side constants, and/or objective function coefficients (see the summary in
Table 1 of Section 6-3). In this section we present a generalized version of the
simplex method that will solve both maximization and minimization problems with
any combination of and problem constraints.The only requirement is that
each problem constraint must have a non-negative constant on the right side. (This
restriction is easily accommodated, as you will see.)
Introduction to the Big M Method
We introduce the big M method through a simple maximization problem with mixed
problem constraints. The key parts of the method will then be summarized and
applied to more complex problems.
Consider the following problem:
(1)
To form an equation out of the first inequality, we introduce a slack variable as
before, and write
How can we form an equation out of the second inequality? We introduce a second
variable and subtract it from the left side:
The variable is called a surplus variable because it is the amount (surplus) by
which the left side of the inequality exceeds the right side.
Next, we express the linear programming problem (1) as a system of equations:
(2)
It can be shown that a basic solution of system (2) is not feasible if any of the variables
(excluding P) are negative. So a surplus variable is required to satisfy the nonnegative
constraint.
The basic solution found by setting the nonbasic variables and equal to 0 is
But this basic solution is not feasible, since the surplus variable is negative (which
is a violation of the non-negative requirements of all variables except P). The simplex
method works only when the basic solution for a tableau is feasible, so we cannot
solve this problem simply by writing the tableau for (2) and starting pivot
operations.
To use the simplex method on problems with mixed constraints, we turn to an
ingenious device called an artificial variable. This variable has no physical meaning
in the original problem. It is introduced solely for the purpose of obtaining a basic
feasible solution so that we can apply the simplex method. An artificial variable is a
variable introduced into each equation that has a surplus variable. As before, to
s2
x1 = 0, x2 = 0, s1 = 10, s2 = -2, P = 0
x1 x2
x1, x2, s1, s2 U 0
-2×1 – x2 + P = 0
-x1 + x2 – s2 = 2
x1 + x2 + s1 = 10
s2
-x1 + x2 – s2 = 2
s2
x1 + x2 + s1 = 10
s1,
Maximize P = 2×1 + x2
subject to x1 + x2 … 10
-x1 + x2 U 2
x1, x2 U 0
…, U, =
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
Prkentaice Hjalol. Ckopyarig htj ©20k11 Pjeaorsokn Eadu cajtioon,
316 CHAPTER 6 Linear Programming: The Simplex Method
ensure that we consider only basic feasible solutions, an artificial variable is required
to satisfy the non-negative constraint. (As we will see later, artificial variables are
also used to augment equality problem constraints when they are present.)
Returning to the problem at hand, we introduce an artificial variable into the
equation involving the surplus variable
To prevent an artificial variable from becoming part of an optimal solution to
the original problem, a very large “penalty” is introduced into the objective function.
This penalty is created by choosing a positive constant M so large that the artificial
variable is forced to be 0 in any final optimal solution of the original problem.
(Since the constant M can be as large as we wish in computer solutions, M is often
selected as the largest number the computer can hold!) Then we add the term
to the objective function:
We now have a new problem, which we call the modified problem:
(3)
The initial system for the modified problem (3) is
(4)
We next write the augmented coefficient matrix for system (4), which we call the
preliminary simplex tableau for the modified problem. (The reason we call it the
“preliminary” simplex tableau instead of the “initial” simplex tableau will be made
clear shortly.)
(5)
To start the simplex process, including any necessary pivot operations, the preliminary
simplex tableau should either meet the two requirements given in the following
box or be transformed by row operations into a tableau that meets these two
requirements.
C
x1 x2 s1 s2 a1 P
1 1 1 0 0 0
-1 1 0 -1 1 0
-2 -1 0 0 M 1
3
10
2
0
S
x1, x2, s1, s2, a1 U 0
-2×1 – x2 + Ma1 + P = 0
-x1 + x2 – s2 + a1 = 2
x1 + x2 + s1 = 10
Maximize P = 2×1 + x2 – Ma1
subject to x1 + x2 + s1 = 10
-x1 + x2 – s2 + a1 = 2
x1, x2, s1, s2, a1 U 0
P = 2×1 + x2 – Ma1
-Ma1
-x1 + x2 – s2 + a1 = 2
s2:
a1
DEFINITION Initial Simplex Tableau
For a system tableau to be considered an initial simplex tableau, it must satisfy the
following two requirements:
1. The requisite number of basic variables must be selectable by the process
described in Section 6-2. That is, a variable can be selected as a basic variable
only if it corresponds to a column in the tableau that has exactly one
nonzero element and the nonzero element in the column is not in the same
row as the nonzero element in the column of another basic variable. The
remaining variables are then selected as nonbasic variables to be set equal
to 0 in determining a basic solution.
2. The basic solution found by setting the nonbasic variables equal to 0 is
feasible.
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
bjyo Prkentiace Hjalol. Ckopyarigh tj ©20k11 Pjeaorsokn Eaduc ajtioon,
SECTION 6-4 Maximization and Minimization with Mixed Problem Constraints 317
Tableau (5) satisfies the first initial simplex tableau requirement, since and P
can be selected as basic variables according to the first requirement. (Not all preliminary
simplex tableaux satisfy the first requirement; see Example 2.) However, tableau
(5) does not satisfy the second initial simplex tableau requirement since the basic solution
is not feasible To use the simplex method, we must use row operations
to transform tableau (5) into an equivalent matrix that satisfies both initial simplex
tableau requirements. Note that this transformation is not a pivot operation.
To get an idea of how to proceed, notice in tableau (5) that in the column
is in the same row as 1 in the column. This is not an accident! The artificial variable
was introduced so that this would happen. If we eliminate M from the bottom
of the column, the nonbasic variable will become a basic variable and the
troublesome basic variable will become a nonbasic variable.We proceed to eliminate
M from the column using row operations:
From this last matrix we see that the basic variables are and P.The basic solution
found by setting the nonbasic variables and equal to 0 is
The basic solution is feasible (P can be negative), and both requirements for an initial
simplex tableau are met.We perform pivot operations to find an optimal solution.
The pivot column is determined by the most negative indicator in the bottom
row of the tableau. Since M is a positive number, is certainly a negative
indicator.What about the indicator Remember that M is a very large positive
number. We will assume that M is so large that any expression of the form
M – k is positive. So the only negative indicator in the bottom row is -M – 1.
M – 2?
-M – 1
x1 = 0, x2 = 0, s1 = 10, s2 = 0, a1 = 2, P = -2M
x1, x2, s2
s1, a1,
C
1 1 1 0 0 0 10
-1 1 0 -1 1 0 2 S
-2 -1 0 0 M 1
†
0
1 1 1 0 0 0 10
~C -1 1 0 -1 1 0 2
M – 2 -M – 1 0 M 0 1
†
-2M
S
(-M)R2 + R3: R3
x1 x2 s1 s2 a1 P
a1
s2
a1 a1
a1
a1
-1 s2
(s2 = -2).
s1, s2,
x¡ x™ s¡ s™ a¡ P
1 1 1 0 0 0 10 =10
C –1 1 0 –1 1 0 3 2 S =2
M-2 –M-1 0 M 0 1 –2M
a
Pivot column
Pivot row B
101
21
Having identified the pivot element, we now begin pivoting:
_
_
x¡ x™ s¡ s™ a¡ P
1 1 1 0 0 0 10 (–1)R2+R1 B R1
C –1 1 0 –1 1 0 3 2 S
M-2 –M-1 0 M 0 1 –2M (M+1)R2+R3 B R3
2 0 1 1 –1 0 8 R1 B R1
C –1 1 0 –1 1 0 3 2 S
–3 0 0 –1 M+1 1 2
1 0 – 0 4
C –1 1 0 –1 1 0 3 2 S R1+R2 B R2
–3 0 0 –1 M+1 1 2 3R1+R3 B R3
1 0 – 0 4
C 0 1 – 0 3 6 S
0 0 M- 1 14
12
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
3
2
1
2
1
2
P
s¡
a¡
x™
P
P
s¡
_
x¡
x™
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
Prkentaice Hjalol. Ckopyarig htj ©20k11 Pjeaorsokn Eadu cajtioon,
318 CHAPTER 6 Linear Programming: The Simplex Method
Since all the indicators in the last row are non-negative ( is non-negative
becauseMis a very large positive number), we can stop and write the optimal solution:
This is an optimal solution to the modified problem (3). How is it related to the original
problem (2)? Since in this solution,
(6)
is certainly a feasible solution for system (2). [You can verify this by direct substitution
into system (2).] Surprisingly, it turns out that solution (6) is an optimal solution
to the original problem.To see that this is true, suppose we were able to find feasible
values of and that satisfy the original system (2) and produce a value of
Then by using these same values in problem (3) along with we
have would a feasible solution of problem (3) with This contradicts the fact
that is the maximum value of P for the modified problem. Solution (6) is an
optimal solution for the original problem.
As this example illustrates, if is an optimal solution for the modified
problem, then deleting produces an optimal solution for the original problem.
What happens if in the optimal solution for the modified problem? In this
case, it can be shown that the original problem has no optimal solution because its
feasible set is empty.
In larger problems, each problem constraint will require the introduction of a
surplus variable and an artificial variable. If one of the problem constraints is an
equation rather than an inequality, then there is no need to introduce a slack or surplus
variable. However, constraint will require the introduction of
another artificial variable to prevent the initial basic solution from violating the
equality constraint—the decision variables are often 0 in the initial basic solution
(see Example 2). Finally, each artificial variable also must be included in the objective
function for the modified problem. The same constant M can be used for each
artificial variable. Because of the role that the constant Mplays in this approach, this
method is often called the big M method.
Big M Method
We summarize the key steps of the big M method and use them to solve several
problems.
each = problem
U
a1 Z 0
a1
a1 = 0
P = 14
P 7 14.
P 7 14. a1 = 0,
x1, x2, s1, s2
x1 = 4, x2 = 6, s1 = 0, s2 = 0, P = 14
a1 = 0
Max P = 14 at x1 = 4, x2 = 6, s1 = 0, s2 = 0, a1 = 0
M – 12
PROCEDURE Big M Method: Introducing Slack, Surplus, and Artificial
Variables to Form the Modified Problem
Step 1 If any problem constraints have negative constants on the right side, multiply
both sides by to obtain a constraint with a non-negative constant. (If the
constraint is an inequality, this will reverse the direction of the inequality.)
Step 2 Introduce a slack variable in each constraint.
Step 3 Introduce a surplus variable and an artificial variable in each constraint.
Step 4 Introduce an artificial variable in
Step 5 For each artificial variable add to the objective function. Use the
same constant M for all artificial variables.
ai, -Mai
each = constraint.
U
…
-1
EXAMPLE 1 Finding the Modified Problem Find the modified problem for the following linear
programming problem. (Do not attempt to solve the problem.)
x1, x2, x3 U 0
2×1 – x2 + 4×3 = 6
x1 + 4×2 + 3×3 U 1
-x1 + x2 – 2×3 … -5
subject to x1 + 2×2 – x3 … 7
Maximize P = 2×1 + 5×2 + 3×3
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
bjyo Prkentiace Hjalol. Ckopyarigh tj ©20k11 Pjeaorsokn Eaduc ajtioon,
SECTION 6-4 Maximization and Minimization with Mixed Problem Constraints 319
SOLUTION First, we multiply the second constraint by to change to 5:
Next, we introduce the slack, surplus, and artificial variables according to the procedure
stated in the box:
Finally, we add and to the objective function:
The modified problem is
x1, x2, x3, s1, s2, s3, a1, a2, a3 U 0
2×1 – x2 + 4×3 + a3 = 6
x1 + 4×2 + 3×3 – s3 + a2 = 1
x1 – x2 + 2×3 – s2 + a1 = 5
subject to x1 + 2×2 – x3 + s1 = 7
Maximize P = 2×1 + 5×2 + 3×3 – Ma1 – Ma2 – Ma3
P = 2×1 + 5×2 + 3×3 – Ma1 – Ma2 – Ma3
-Ma1, -Ma2, -Ma3
2×1 – x2 + 4×3 + a3 = 6
x1 + 4×2 + 3×3 – s3 + a2 = 1
x1 – x2 + 2×3 – s2 + a1 = 5
x1 + 2×2 – x3 + s1 = 7
x1 – x2 + 2×3 U 5
(-1) (-x1 + x2 – 2×3) U (-1) (-5)
-1 -5
Matched Problem 1 Repeat Example 1 for
x1, x2, x3 U 0
3×1 – x2 – x3 = -15
2×1 + 4×2 + 5×3 … 20
-x1 – 3×2 + 4×3 … -10
subject to x1 – 2×2 + x3 U 5
Maximize P = 3×1 – 2×2 + x3
PROCEDURE Big M Method: Solving the Problem
Step 1 Form the preliminary simplex tableau for the modified problem.
Step 2 Use row operations to eliminate the M’s in the bottom row of the preliminary
simplex tableau in the columns corresponding to the artificial variables.
The resulting tableau is the initial simplex tableau.
Step 3 Solve the modified problem by applying the simplex method to the initial
simplex tableau found in step 2.
Now we can list the key steps for solving a problem using the big M
method. The various steps and remarks are based on a number of important
theorems, which we assume without proof. In particular, step 2 is based on the
fact that (except for some degenerate cases not considered here) if the modified
linear programming problem has an optimal solution, then the preliminary
simplex tableau will be transformed into an initial simplex tableau by eliminating
the M’s from the columns corresponding to the artificial variables in the
preliminary simplex tableau. Having obtained an initial simplex tableau, we
perform pivot operations.
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
Prkentaice Hjalol. Ckopyarig htj ©20k11 Pjeaorsokn Eadu cajtioon,
320 CHAPTER 6 Linear Programming: The Simplex Method
EXAMPLE 2 Using the Big M Method Solve the following linear programming problem using
the big M method:
SOLUTION State the modified problem:
Write the preliminary simplex tableau for the modified problem, and find the initial
simplex tableau by eliminating the M’s from the artificial variable columns:
‘ D
1 1 0 1 0 0 0 0
1 0 1 0 1 0 0 0
0 1 1 0 0 -1 1 0
-M – 1 -M + 1 -2M – 3 0 0 M 0 1
4
20
5
10
-15M
T
20
5
10
-5M
T
0
0
0
1
4
0
0
1
M
0
0
-1
0
0
1
0
0
1
0
0
0
0
1
1
-M – 3
1
0
1
1
‘ D
1
1
0
-M – 1
20
5
10
0
T
0
0
0
1
4
0
0
1
M
0
0
-1
0
0
1
0
M
1
0
0
0
0
1
1
-3
1
0
1
1
D
1
1
0
-1
x1 x2 x3 s1 a1 s2 a2 P
x1, x2, x3, s1, s2, a1, a2 U 0
x2 + x3 – s2 + a2 = 10
x1 + x3 + a1 = 5
subject to x1 + x2 + s1 = 20
Maximize P = x1 – x2 + 3×3 – Ma1 – Ma2
x1, x2, x3 U 0
x2 + x3 U 10
x1 + x3 = 5
subject to x1 + x2 … 20
Maximize P = x1 – x2 + 3×3
Eliminate M from the a1
column
Eliminate M from the a2
column
(-M)R3 + R4: R4
(-M)R2 + R4 : R4
From this last matrix we see that the basic variables are and P.The basic
solution found by setting the nonbasic variables and equal to 0 is
The basic solution is feasible, and both requirements for an initial simplex
tableau are met.We perform pivot operations to find the optimal solution.
x1 = 0, x2 = 0, x3 = 0, s1 = 20, a1 = 5, s2 = 0, a2 = 10, P = -15M
x1, x2, x3, s2
s1, a1, a2,
Step 4 Relate the optimal solution of the modified problem to the original problem.
(A) If the modified problem has no optimal solution, then the original
problem has no optimal solution.
(B) If all artificial variables are 0 in the optimal solution to the modified
problem, then delete the artificial variables to find an optimal solution
to the original problem.
(C) If any artificial variables are nonzero in the optimal solution to the
modified problem, then the original problem has no optimal solution.
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
bjyo Prkentiace Hjalol. Ckopyarigh tj ©20k11 Pjeaorsokn Eaduc ajtioon,
x¡ x™ x£ s¡ a¡ s™ a™ P
1 1 0 1 0 0 0 0 20
1 0 1 0 1 0 0 0 5
D
0 1 1 0 0 –1 1 0
4
10
T
(–1)R2+R3 B R3
–M-1 –M+1 –2M-3 0 0 M 0 1 –15M (2M+3)R2+R4 B R4
1 1 0 1 0 0 0 0 20 (–1)R3+R1 B R1
1 0 1 0 1 0 0 0 5
D
–1 1 0 0 –1 –1 1 0
4
5
T
M+2 –M+1 0 0 2M+3 M 0 1 –5M+15 (M-1)R3+R4 B R4
2 0 0 1 1 1 –1 0 15
1 0 1 0 1 0 0 0 5
D
–1 1 0 0 –1 –1 1 0
4
5
T
3 0 0 0 M+4 1 M-1 1 10
_
_
P
a¡
a2
s¡
x3
P
a2
s¡
x3
x™
P
s¡
SECTION 6-4 Maximization and Minimization with Mixed Problem Constraints 321
Since the bottom row has no negative indicators, we can stop and write the
optimal solution to the modified problem:
Since and the solution to the original problem is
Max P = 10 at x1 = 0, x2 = 5, x3 = 5
a1 = 0 a2 = 0,
x1 = 0, x2 = 5, x3 = 5, s1 = 15, a1 = 0, s2 = 0, a2 = 0, P = 10
Matched Problem 2 Solve the following linear programming problem using the big M method:
x1, x2, x3 U 0
x1 – x2 – x3 U 1
x1 – x3 = 6
subject to x2 + x3 … 4
Maximize P = x1 + 4×2 + 2×3
EXAMPLE 3 Using the Big M Method Solve the following linear programming problem using
the big M method:
SOLUTION Introducing slack, surplus, and artificial variables, we obtain the modified problem:
Modified problem
-3×1 – 5×2 + Ma1 + P = 0
x1 + 2×2 – s2 + a1 = 10
2×1 + x2 + s1 = 4
x1, x2 U 0
x1 + 2×2 U 10
subject to 2×1 + x2 … 4
Maximize P = 3×1 + 5×2
Preliminary simplex tableau
x¡ x™ s¡ s™ a¡ P
2 1 1 0 0 0 4 Eliminate M in the a1 column.
C 1 2 0 –1 1 0 3 10 S
–3 –5 0 0 M 1 0 (–M)R2+R3 B R3
Initial simplex tableau
2 1 1 0 0 0 4 Begin pivot operations.
C 1 2 0 –1 1 0 3 10 S (–2)R1+R2 B R2
–M-3 –2M-5 0 M 0 1 –10M (2M+5)R1+R3 B R3
2 1 1 0 0 0 4
C –3 0 –2 –1 1 0 3 2 S
3M+7 0 2M+5 M 0 1 –2M+20
_
_
P
a¡
a¡
P
s¡
x™
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
Prkentaice Hjalol. Ckopyarig htj ©20k11 Pjeaorsokn Eadu cajtioon,
322 CHAPTER 6 Linear Programming: The Simplex Method
Matched Problem 3 Solve the following linear programming problem using the big M method:
Minimization by the Big MMethod
In addition to solving any maximization problem, the big M method can be used to
solve minimization problems. To minimize an objective function, we need only to
maximize its negative. Figure 2 illustrates the fact that the minimum value of a function
f occurs at the same point as the maximum value of the function Furthermore,
if m is the minimum value of f, then is the maximum value of and
conversely. So we can find the minimum value of a function f by finding the maximum
value of -f and then changing the sign of the maximum value.
-m -f,
-f.
x1, x2 U 0
2×1 + x2 U 12
subject to x1 + 5×2 … 5
Maximize P = 3×1 + 2×2
x
y
_m
m
y _ f(x)
y _ _f(x)
Figure 2
J K L
Cutting 1 hr 1 hr 1 hr
Polishing 2 hr 1 hr 2 hr
Cost per stone $30 $30 $10
EXAMPLE 4 Production Scheduling: Minimization Problem A small jewelry manufacturer hires
a highly skilled gem cutter to work at least 6 hours per day. On the other hand,
the polishing facilities can be used for at most 10 hours per day. The company
specializes in three kinds of semiprecious gemstones, J, K, and L. Relevant cutting,
polishing, and cost requirements are listed in the table. How many gemstones
of each type should be processed each day to minimize the cost of the
finished stones? What is the minimum cost?
SOLUTION Since we must decide how many gemstones of each type should be processed
each day, the decision variables are
x3 = number of type L gemstones processed each day
x2 = number of type K gemstones processed each day
x1 = number of type J gemstones processed each day
x1
x2
5 10
5
0
B
A
2x1 _ x2 _ 4
x1 _ 0, x2 _ 0
x1 _ 2x2 _ 10
x1 _ 0, x2 _ 0
A _ B__
The optimal solution of the modified problem is
Since the original problem has no optimal solution. Figure 1 shows that
the feasible region for the original problem is empty.
a1 Z 0,
a1 = 2, P = -2M + 20
x1 = 0, x2 = 4, s1 = 0, s2 = 0,
Figure 1
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
bjyo Prkentiace Hjalol. Ckopyarigh tj ©20k11 Pjeaorsokn Eaduc ajtioon,
SECTION 6-4 Maximization and Minimization with Mixed Problem Constraints 323
1 1 1 –1 1 0 0
C 2 1 2 0 0 1 0 3 S 0.5R2 B R2
–M+30 –M+30 –M+10 M 0 0 1
1 1 1 –1 1 0 0 (–1)R2+R1 B R1
C 1 0.5 1 0 0 0.5 0 3 S
–M+30 –M +30 –M+10 M 0 0 1 (M-10)R2+R3 B R3
6
10
–6M
6
5
–6M
_
P
a¡
s2
_
–M
0 0.5 0 –1 1 –0.5 0 2R1 B R1
C 1 0.5 1 0 0 0.5 0 3 S
20 –0.5M+25 0 M 0 0.5M-5 1
0 1 0 –2 2 –1 0
C 1 0.5 1 0 0 0.5 0 3 S (–0.5)R1+R2 B R2
20 –0.5M+25 0 M 0 0.5M-5 1 (0.5M-25)R1+R3 B R3
0 1 0 –2 2 –1 0
C 1 0 1 1 –1 1 0 3 S
20 0 0 50 M-50 20 1 –100
1
5
2
5
–M – 50
–M – 50
2
4
–100
_
a¡
x3
P
_
_
P
x2
x3
Begin pivot operations. Assume M is so large
that –M + 30 and –M + 10 are negative
Eliminate M in the a1
column
(-M)R1 + R3: R3
The bottom row has no negative indicators, so the optimal solution for the
modified problem is
x1 = 0, x2 = 2, x3 = 4, s1 = 0, a1 = 0, s2 = 0, P = -100
Since the data is already summarized in a table, we can proceed directly to the
model:
Objective function
Problem constraints
Non-negative constraints
We convert this to a maximization problem by letting
We get
and Min To solve, we first state the modified problem:
x1, x2, x3, s1, s2, a1 U 0
30×1 + 30×2 + 10×3 + Ma1 + P = 0
2×1 + x2 + 2×3 + s2 = 10
x1 + x2 + x3 – s1 + a1 = 6
C = -Max P.
x1, x2, x3 U 0
2×1 + x2 + 2×3 … 10
subject to x1 + x2 + x3 U 6
Maximize P = -30×1 – 30×2 – 10×3
P = -C = -30×1 – 30×2 – 10×3
x1, x2, x3 U 0
subject to x1 + x2 + x3 U 6
2×1 + x2 + 2×3 … 10
f
Minimize C = 30×1 + 30×2 + 10×3
S
6
10
0
3
0
0
1
0
1
0
1
0
M
-1
0
0
1
2
10
1
1
30
1
2
30
C
x1 x2 x3 s1 a1 s2 P
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
Prkentaice Hjalol. Ckopyarig htj ©20k11 Pjeaorsokn Eadu cajtioon,
324 CHAPTER 6 Linear Programming: The Simplex Method
EXAMPLE 5 Petroleum Blending A refinery produces two grades of gasoline, regular and premium,
by blending together two components, A and B. Component A has an octane
rating of 90 and costs $28 a barrel. Component B has an octane rating of 110 and
costs $32 a barrel.The octane rating for regular gasoline must be at least 95, and the
octane rating for premium must be at least 105. Regular gasoline sells for $34 a
barrel and premium sells for $40 a barrel. Currently, the company has 30,000 barrels
of component A and 20,000 barrels of component B. It also has orders for 20,000
barrels of regular and 10,000 barrels of premium that must be filled. Assuming that
all the gasoline produced can be sold, determine the maximum possible profit.
SOLUTION This problem is similar to the transportation problem in Section 6-3. That is, to
maximize the profit, we must decide how much of each component must be used
to produce each grade of gasoline.Thus, the decision variables are
x4 = number of barrels of component B used in premium gasoline
x3 = number of barrels of component B used in regular gasoline
x2 = number of barrels of component A used in premium gasoline
x1 = number of barrels of component A used in regular gasoline
Larger Problems: Refinery Application
Up to this point, all the problems we have considered could be solved by hand.
However, the real value of the simplex method lies in its ability to solve problems
with a large number of variables and constraints, where a computer is generally used
to perform the actual pivot operations. As a final application, we consider a problem
that would require the use of a computer to complete the solution.
Table 1 Summary of Problem Types and Simplex Solution Methods
Problem Type
Problem
Constraints
Right-Side
Constants
Coefficients of
Objective Function Method of Solution
1. Maximization … Non-negative Any real numbers Simplex method with slack variables
2. Minimization U Any real numbers Non-negative Form dual and solve by the preceding
method
3. Maximization Mixed
(…, U, =)
Non-negative Any real numbers Form modified problem with slack, surplus,
and artificial variables, and solve by the big
M method
4. Minimization Mixed
(…, U, =)
Non-negative Any real numbers Maximize negative of objective function by
the preceding method
Since deleting produces the optimal solution to the original maximization
problem and also to the minimization problem.Thus,
That is, a minimum cost of $100 for gemstones will be realized if no type J, 2 type K,
and 4 type L stones are processed each day.
Min C = -Max P = -(-100) = 100 at x1 = 0, x2 = 2, x3 = 4
a1 = 0, a1
Matched Problem 4 Repeat Example 4 if the gem cutter works at least 8 hours a day and all other
data remain the same.
Summary of Solution Methods
The big M method can be used to solve any minimization problems, including those
that can be solved by the dual method. (Note that Example 4 could have been solved
by the dual method.) Both methods of solving minimization problems are important.
You will be instructed to solve most minimization problems in Exercise 6-4 by the big
M method in order to gain more experience with this method. However, if the
method of solution is not specified, the dual method is usually easier.
Table 1 should help you select the proper method of solution for any linear
programming problem.
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
bjyo Prkentiace Hjalol. Ckopyarigh tj ©20k11 Pjeaorsokn Eaduc ajtioon,
SECTION 6-4 Maximization and Minimization with Mixed Problem Constraints 325
Table 2
Component Octane Rating Cost ($) Available Supply
A 90 28 30,000 barrels
B 110 32 20,000 barrels
Grade Minimum Octane Rating Selling Price ($) Existing Orders
Regular 95 34 20,000 barrels
Premium 105 40 10,000 barrels
Next, we summarize the data in table form (Table 2). Once again, we have to
adjust the form of the table to fit the data.
The total amount of component A used is This cannot exceed the
available supply.Thus, one constraint is
The corresponding inequality for component B is
The amounts of regular and premium gasoline produced must be sufficient to
meet the existing orders:
Regular
Premium
Now consider the octane ratings. The octane rating of a blend is simply the
proportional average of the octane ratings of the components. So the octane rating
for regular gasoline is
where is the percentage of component A used in regular gasoline
and is the percentage of component B. The final octane rating of
regular gasoline must be at least 95; so
Multiply by .
Collect like terms on the right side.
Octane rating for regular
The corresponding inequality for premium gasoline is
Octane rating for premium
The cost of the components used is
The revenue from selling all the gasoline is
and the profit is
= 6×1 + 12×2 + 2×3 + 8×4
= (34 – 28)x1 + (40 – 28)x2 + (34 – 32)x3 + (40 – 32)x4
= 34(x1 + x3) + 40(x2 + x4) – 28(x1 + x2) – 32(x3 + x4)
P = R – C
R = 34(x1 + x3) + 40(x2 + x4)
C = 28(x1 + x2) + 32(x3 + x4)
0 U 15×2 – 5×4
90×2 + 110×4 U 105(x2 + x4)
90
x2
x2 + x4
+ 110
x4
x2 + x4
U 105
0 U 5×1 – 15×3
90×1 + 110×3 U 95(x1 + x3)
90 x1 + x3
x1
x1 + x3
+ 110
x3
x1 + x3
U 95
x3>(x1 + x3)
x1>(x1 + x3)
90
x1
x1 + x3
+ 110
x3
x1 + x3
x2 + x4 U 10,000
x1 + x3 U 20,000
x3 + x4 … 20,000
x1 + x2 … 30,000
x1 + x2.
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
Prkentaice Hjalol. Ckopyarig htj ©20k11 Pjeaorsokn Eadu cajtioon,
326 CHAPTER 6 Linear Programming: The Simplex Method
EXPLORE & DISCUSS 1 Interpret the values of the slack and surplus variables in the computer solution to
Example 5.
Matched Problem 5 Suppose that the refinery in Example 5 has 35,000 barrels of component A, which
costs $25 a barrel, and 15,000 barrels of component B, which costs $35 a barrel. If
all other data remain the same, formulate a linear programming problem to find
the maximum profit. Do not attempt to solve the problem (unless you have
access to software that can solve linear programming problems).
To find the maximum profit, we must solve the following linear programming
problem:
Profit
Available A
Available B
Required regular
Required premium
Octane for regular
Octane for premium
We will use technology to solve this large problem. There are many types of
software that use the big M method to solve linear programming problems,
including Java applets, graphing calculator programs, and spreadsheets. Because
you are likely to use different software than we did, we will simply display the
initial and final tableaux. Notice that in the last row of the initial tableau, we
entered a large number, , instead of the symbol M. This is typical of software
implementations of the big M method.
The final table produced by the software is
From the final tableau, we see that the refinery should blend 26,250 barrels of
component A and 8,750 barrels of component B to produce 35,000 barrels of regular
gasoline.They should blend 3,750 barrels of component A and 11,250 barrels
of component B to produce 15,000 barrels of premium gasoline.This will result in
a maximum profit of $310,000.
s4 a2 s5 s6 P
0 0 -0.1 -0.1 0
1 -1 0.1 0.1 0
0 0 -0.075 -0.025 0
0 0 0.075 0.025 0
0 0 -0.025 -0.075 0
0 0 0.025 0.075 0
0 106 0.6 0.6 1
7
15,000
5,000
8,750
11,250
26,250
3,750
310,000
G W
x1 x2 x3 x4 s1 s2 s3 a1
0 0 0 0 1.5 -0.5 1 -1
0 0 0 0 -0.5 1.5 0 0
0 0 1 0 0.375 -0.125 0 0
0 0 0 1 -0.375 1.125 0 0
1 0 0 0 1.125 -0.375 0 0
0 1 0 0 -0.125 0.375 0 0
0 0 0 0 3 11 0 106
s4 a2 s5 s6 P
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
-1 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 106 0 0 1
7
30,000
20,000
20,000
10,000
0
0
0
G W
x1 x2 x3 x4 s1 s2 s3 a1
1 1 0 0 1 0 0 0
0 0 1 1 0 1 0 0
1 0 1 0 0 0 -1 1
0 1 0 1 0 0 0 0
5 0 -15 0 0 0 0 0
0 15 0 -5 0 0 0 0
-6 -12 -2 -8 0 0 0 106
106
x1, x2, x3, x4 U 0
15×2 – 5×4 … 0
5×1 – 15×3 … 0
x2 + x4 U 10,000
x1 + x3 U 20,000
x3 + x4 … 20,000
subject to x1 + x2 … 30,000
Maximize P = 6×1 + 12×2 + 2×3 + 8×4
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
bjyo Prkentiace Hjalol. Ckopyarigh tj ©20k11 Pjeaorsokn Eaduc ajtioon,
SECTION 6-4 Maximization and Minimization with Mixed Problem Constraints 327
Exercises 6-4
A
In Problems 1–8,
(A) Introduce slack, surplus, and artificial variables and form the
modified problem.
(B) Write the preliminary simplex tableau for the modified problem
and find the initial simplex tableau.
(C) Find the optimal solution of the modified problem by applying
the simplex method to the initial simplex tableau.
(D) Find the optimal solution of the original problem, if it exists.
1.
2.
3.
4.
5.
6.
7.
8.
B
Use the big M method to solve Problems 9–22.
9.
10.
x1, x2 U 0
x1 + 2×2 U 16
subject to 3×1 + x2 … 28
Minimize and maximize P = -4×1 + 16×2
x1, x2 U 0
5×1 + 3×2 U 30
subject to x1 + x2 … 8
Minimize and maximize P = 2×1 – x2
x1, x2 U 0
3×1 + 5×2 U 15
subject to x1 + x2 … 2
Maximize P = 4×1 + 6×2
x1, x2 U 0
2×1 + 3×2 U 12
subject to x1 + x2 … 3
Maximize P = 5×1 + 10×2
x1, x2 U 0
x1 + x2 U 5
subject to x1 – 2×2 … 2
Maximize P = 3×1 + 4×2
x1, x2 U 0
x1 + x2 U 4
subject to -x1 + 2×2 … 2
Maximize P = 4×1 + 3×2
x1, x2 U 0
x1 + x2 = 12
subject to x1 + 3×2 … 24
Maximize P = 4×1 + 3×2
x1, x2 U 0
x1 + x2 = 6
subject to 2×1 + x2 … 8
Maximize P = 3×1 + 5×2
x1, x2 U 0
x1 + x2 U 6
subject to 2×1 + x2 … 16
Maximize P = 3×1 + 7×2
x1, x2 U 0
x1 + x2 U 4
subject to x1 + 2×2 … 12
Maximize P = 5×1 + 2×2
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
x1, x2, x3 U 0
2×1 + x2 U 150
2×1 + 2×2 + x3 U 140
subject to 2×1 + 3×1 + 5×3 … 280
Maximize P = 2×1 + 4×2 + x3
x1, x2, x3 U 0
x1 – 2×2 + x3 U 40
2×1 + 5×2 + 2×3 U 50
subject to x1 + 3×2 + 2×3 … 60
Maximize P = x1 + 2×2 + 5×3
x1, x2, x3 U 0
-x1 + 5×2 + x3 U 120
3×1 + 3×2 + x3 … 90
subject to 2×1 + 4×2 + x3 … 150
Maximize P = 5×1 + 2×2 + 9×3
x1, x2, x3 U 0
x1 + 2×2 – x3 U 10
2×1 + x2 + 2×3 … 60
subject to x1 + 2×2 + x3 … 25
Maximize P = 2×1 + 3×2 + 4×3
x1, x2, x3 U 0
2×1 – 2×2 + x3 = 0
subject to 2×1 + 2×2 + 3×3 … 12
Maximize P = 3×1 + 6×2 + 2×3
x1, x2, x3 U 0
2×1 + x2 – 2×3 = 0
subject to 2×1 + x2 + 2×3 … 8
Maximize P = 3×1 + 5×2 + 6×3
x1, x2, x3 U 0
x1 – 3×2 + x3 = 2
x1 + 2×2 + x3 U 6
subject to 2×1 + x2 + 3×3 … 24
Maximize C = -3×1 + 15×2 – 4×3
x1, x2, x3 U 0
2×1 + x2 – x3 = 1
2×1 + 3×2 + x3 U 6
subject to x1 + 2×2 + x3 … 10
Minimize C = -5×1 – 12×2 + 16×3
x1, x2, x3 U 0
2×1 + x2 + 5×3 = 35
subject to x1 – x2 + x3 U 20
Maximize P = 5×1 + 7×2 + 9×3
x1, x2, x3 U 0
x1 – x2 + 2×3 = 6
subject to 3×1 + x2 + 2×3 U 12
Maximize P = 10×1 + 12×2 + 20×3
x1, x2 U 0
x1 + x2 U 9
2×1 + x2 … 16
subject to x1 + 2×2 … 20
Maximize P = 6×1 + 2×2
x1, x2 U 0
x1 + x2 U 10
2×1 + x2 … 21
subject to x1 + 2×2 … 18
Maximize P = 2×1 + 5×2
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
Prkentaice Hjalol. Ckopyarig htj ©20k11 Pjeaorsokn Eadu cajtioon,
328 CHAPTER 6 Linear Programming: The Simplex Method
23. Solve Problems 5 and 7 by the geometric method. Compare
the conditions in the big Mmethod that indicate no optimal
solution exists with the conditions stated in Theorem 2 in
Section 5-3.
24. Repeat Problem 23 with Problems 6 and 8.
C
Problems 25–32 are mixed. Some can be solved by the methods
presented in Sections 6-2 and 6-3, while others must be solved by
the big M method.
25.
26.
27.
28.
29.
30.
31.
32.
Applications
In Problems 33–47, construct a mathematical model in the form
of a linear programming problem. (The answers in the back of the
book for these application problems include the model.) Then
solve the problem using the big M method.
33. Advertising. An advertising company wants to attract new
customers by placing a total of at most 10 ads in 3 newspapers.
Each ad in the Sentinel costs $200 and will be read by
2,000 people. Each ad in the Journal costs $200 and will be
read by 500 people. Each ad in the Tribune costs $100 and
will be read by 1,500 people. The company wants at least
16,000 people to read its ads. How many ads should it place
x1, x2, x3 U 0
3×1 – x2 – 4×3 … 10
subject to 4×1 + 2×2 + 3×3 U 20
Minimize C = 10×1 + 12×2 + 28×3
x1, x2, x3 U 0
2×1 + x2 + 3×3 … 60
subject to x1 + 3×2 + x3 … 40
Maximize P = 12×1 + 9×2 + 5×3
x1, x2, x3 U 0
4×1 – x2 + 2×3 … -7
subject to x1 + x2 – 3×3 … 6
Maximize P = 8×1 + 2×2 – 10×3
x1, x2, x3 U 0
4×2 + x3 U 3
subject to x1 + 3×2 U 6
Minimize C = 10×1 + 40×2 + 5×3
x1, x2, x3 U 0
x1 – 2×2 – 2×3 U 1
subject to 2×1 + 3×2 + x3 … 24
Minimize C = -5×1 + 10×2 + 15×3
x1, x2, x3 U 0
x1 – 2×2 – 2×3 U 1
subject to 2×1 + 3×2 + x3 … 24
Maximize P = -5×1 + 10×2 + 15×3
x1, x2, x3 U 0
x1 – x2 + x3 … 10
subject to x1 – 2×2 + x3 U -8
Maximize P = 7×1 – 5×2 + 2×3
x1, x2, x3 U 0
4×2 + x3 … 3
subject to x1 + 3×2 … 6
Minimize C = 10×1 – 40×2 – 5×3
36. Human nutrition. Discuss the effect on the solution to
Problem 35 if the cost of brand C liquid diet food increases
to $1.50 per bottle.
37. Plant food. A farmer can use three types of plant food:
mix A, mix B, and mix C. The amounts (in pounds) of nitrogen,
phosphoric acid, and potash in a cubic yard of each mix
are given in the table. Tests performed on the soil indicate
that the field needs at least 800 pounds of potash. The tests
also indicate that no more than 700 pounds of phosphoric
acid should be added to the field.The farmer plans to plant
a crop that requires a great deal of nitrogen. How many
cubic yards of each mix should be added to the field in
order to satisfy the potash and phosphoric acid requirements
and maximize the amount of nitrogen? What is the
maximum amount of nitrogen?
in each paper in order to minimize the advertising costs?
What is the minimum cost?
34. Advertising. Discuss the effect on the solution to Problem
33 if the Tribune will not accept more than 4 ads from the
company.
35. Human nutrition. A person on a high-protein, lowcarbohydrate
diet requires at least 100 units of protein and
at most 24 units of carbohydrates daily.The diet will consist
entirely of three special liquid diet foods: A, B, and C. The
contents and costs of the diet foods are given in the table.
How many bottles of each brand of diet food should be consumed
daily in order to meet the protein and carbohydrate
requirements at minimal cost? What is the minimum cost?
Units per Bottle
A B C
Protein 10 10 20
Carbohydrates 2 3 4
Cost per bottle ($) 0.60 0.40 0.90
Pounds per Cubic Yard
A B C
Nitrogen 12 16 8
Phosphoric acid 12 8 16
Potash 16 8 16
38. Plant food. Discuss the effect on the solution to Problem
37 if the limit on phosphoric acid is increased to
1,000 pounds.
In Problems 39–47, construct a mathematical model in the form
of a linear programming problem. Do not solve.
39. Manufacturing. A company manufactures car and truck
frames at plants in Milwaukee and Racine. The Milwaukee
plant has a daily operating budget of $50,000 and can
produce at most 300 frames daily in any combination. It
costs $150 to manufacture a car frame and $200 to manufacture
a truck frame at the Milwaukee plant.The Racine plant
has a daily operating budget of $35,000, and can produce a
maximum combined total of 200 frames daily. It costs $135
to manufacture a car frame and $180 to manufacture a
truck frame at the Racine plant. Based on past demand, the
company wants to limit production to a maximum of
250 car frames and 350 truck frames per day. If the company
realizes a profit of $50 on each car frame and $70 on each
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
bjyo Prkentiace Hjalol. Ckopyarigh tj ©20k11 Pjeaorsokn Eaduc ajtioon,
SECTION 6-4 Maximization and Minimization with Mixed Problem Constraints 329
truck frame, how many frames of each type should be
produced at each plant to maximize the daily profit?
40. Loan distributions. A savings and loan company has $3 million
to lend. The types of loans and annual returns offered
are given in the table. State laws require that at least 50% of
the money loaned for mortgages must be for first mortgages
and that at least 30% of the total amount loaned must be for
either first or second mortgages. Company policy requires
that the amount of signature and automobile loans cannot
exceed 25% of the total amount loaned and that signature
loans cannot exceed 15% of the total amount loaned. How
much money should be allocated to each type of loan in
order to maximize the company’s return?
Type of Loan Annual Return (%)
Signature 18
First mortgage 12
Second mortgage 14
Automobile 16
Type of Mix Ingredients
Regular At least 20% nuts
At most 40% cereal
Deluxe At least 30% nuts
At most 25% cereal
41. Oil refining. A refinery produces two grades of gasoline,
regular and premium, by blending together three components:
A, B, and C. Component A has an octane rating of
90 and costs $28 a barrel, component B has an octane rating
of 100 and costs $30 a barrel, and component C has an
octane rating of 110 and costs $34 a barrel. The octane
rating for regular must be at least 95 and the octane rating
for premium must be at least 105. Regular gasoline sells for
$38 a barrel and premium sells for $46 a barrel.The company
has 40,000 barrels of component A, 25,000 barrels of
component B, and 15,000 barrels of component C. It must
produce at least 30,000 barrels of regular and 25,000 barrels
of premium. How should the components be blended in
order to maximize profit?
42. Trail mix. A company makes two brands of trail mix, regular
and deluxe, by mixing dried fruits, nuts, and cereal. The
recipes for the mixes are given in the table. The company
has 1,200 pounds of dried fruits, 750 pounds of nuts, and
1,500 pounds of cereal for the mixes.The company makes a
profit of $0.40 on each pound of regular mix and $0.60 on
each pound of deluxe mix. How many pounds of each ingredient
should be used in each mix in order to maximize the
company’s profit?
43. Investment strategy. An investor is planning to divide her
investments among high-tech mutual funds, global mutual
funds, corporate bonds, municipal bonds, and CDs. Each of
these investments has an estimated annual return and a risk
factor (see the table). The risk level for each choice is the
product of its risk factor and the percentage of the total
funds invested in that choice. The total risk level is the sum
of the risk levels for all the investments.The investor wants
at least 20% of her investments to be in CDs and does not
want the risk level to exceed 1.8. What percentage of her
total investments should be invested in each choice to maximize
the return?
Investment Annual Return (%) Risk Factor
High-tech funds 11 2.7
Global funds 10 1.8
Corporate bonds 9 1.2
Muncipal bonds 8 0.5
CDs 5 0
Units per Bottle
L M N
Calcium 30 10 30
Iron 10 10 10
Vitamin A 10 30 20
Cholesterol 8 4 6
Calories 60 40 50
Cost per ounce ($) 0.40 0.60 0.80
Weekly Transportation
Cost per Student ($)
School I School II
Town A 4 8
Town B 6 4
Town C 3 9
44. Investment strategy. Refer to Problem 43. Suppose the
investor decides that she would like to minimize the total
risk factor, as long as her return does not fall below 9%.
What percentage of her total investments should be invested
in each choice to minimize the total risk level?
45. Human nutrition. A dietitian arranges a special diet using
foods L,M, and N. The table gives the nutritional contents
and cost of 1 ounce of each food. The diet’s daily requirements
are at least 400 units of calcium, at least 200 units of
iron, at least 300 units of vitamin A, at most 150 units
of cholesterol, and at most 900 calories. How many ounces
of each food should be used in order to meet the diet’s
requirements at a minimal cost?
46. Mixing feed. A farmer grows three crops: corn, oats, and
soybeans. He mixes them to feed his cows and pigs. At least
40% of the feed mix for the cows must be corn.The feed mix
for the pigs must contain at least twice as much soybeans as
corn. He has harvested 1,000 bushels of corn, 500 bushels of
oats, and 1,000 bushels of soybeans. He needs 1,000 bushels
of each feed mix for his livestock.The unused corn, oats, and
soybeans can be sold for $4, $3.50, and $3.25 a bushel,
respectively (thus, these amounts also represent the cost of
the crops used to feed the livestock). How many bushels of
each crop should be used in each feed mix in order to produce
sufficient food for the livestock at a minimal cost?
47. Transportation. Three towns are forming a consolidated
school district with two high schools. Each high school has a
maximum capacity of 2,000 students. Town A has 500 high
school students, town B has 1,200, and town C has 1,800.The
weekly costs of transporting a student from each town to
each school are given in the table. In order to balance the
enrollment, the school board decided that each high school
must enroll at least 40% of the total student population.
Furthermore, no more than 60% of the students in any
town should be sent to the same high school. How many
students from each town should be enrolled in each school
in order to meet these requirements and minimize the cost
of transporting the students?
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
Prkentaice Hjalol. Ckopyarig htj ©20k11 Pjeaorsokn Eadu cajtioon,
330 CHAPTER 6 Linear Programming: The Simplex Method
Chapter 6 Review
Important Terms, Symbols, and Concepts
6-1 A Geometric Introduction to the Simplex Method
• A linear programming problem is said to be a standard maximization problem in standard form if its mathematical
model is of the following form: Maximize the objective function
subject to problem constraints of the form
with non-negative constraints
• A system of inequalities is converted to a system of equations by adding a slack variable to each inequality.
Variables are divided into two groups: basic and nonbasic. Basic variables are selected arbitrarily, with the
restriction that there are as many basic variables as there are equations.A basic solution is found by setting
the nonbasic variables equal to 0 and solving for the remaining basic variables.A basic solution is feasible if
it contains no negative values.
• The fundamental theorem of linear programming states that an optional solution, if one exists, must occur at
one (or more) basic feasible solutions.
x1, x2, . . . , xn U 0
a1x1 + a2x2 + A + anxn … b b U 0
P = c1x1 + c2x2 + A + cnxn
6-2 The Simplex Method: Maximization with Problem Constraints of the Form ◊
• Adding the objective function to the system of constraint equations produces the initial system. Negative
values of the objective function variable are permitted in a basic feasible solution as long as all other
variables are non-negative.The fundamental theorem of linear programming also applies to initial
systems.
• The augmented coefficient matrix of the initial system is called the initial simplex tableau.The simplex
method consists of performing pivot operations, starting with the initial simplex tableau, until an optimal
solution is found (if one exists).The procedure is illustrated in Figure 2 (p. 293).
Ex. 1, p. 294
Ex. 2, p. 295
Ex. 3, p. 296
6-3 The Dual Problem: Minimization with Problem Constraints of the Form ≫
• By the Fundamental Principle of Duality, a linear programming problem that asks for the minimum of the
objective function over a region described by problem constraints can be solved by first forming the dual
problem and then using the simplex method.
U
Ex. 1, p. 303
Ex. 2, p. 306
Ex. 3, p. 308
Answers to Matched Problems
1.
2. Max at
3. No optimal solution
P = 22 x1 = 6, x2 = 4, x3 = 0
x1, x2, x3, s1, a1, s2, a2, s3, a3 U 0
-3×1 + x2 + x3 + a3 = 15
2×1 + 4×2 + 5×3 + s3 = 20
x1 + 3×2 – 4×3 – s2 + a2 = 10
subject to x1 – 2×2 + x3 – s1 + a1 = 5
Maximize P = 3×1 – 2×2 + x3 – Ma1 – Ma2 – Ma3
4. A minimum cost of $200 is realized when no type J, 6 type K,
and 2 type L stones are processed each day.
5.
x1, x2, x3, x4 U 0
15×2 – 5×4 … 0
5×1 – 15×3 … 0
x2 + x4 U 10,000
x1 + x3 U 20,000
x3 + x4 … 15,000
subject to x1 + x2 … 35,000
Maximize P = 9×1 + 15×2 – x3 + 5×4
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
bjyo Prkentiace Hjalol. Ckopyarigh tj ©20k11 Pjeaorsokn Eaduc ajtioon,
Review Exercises 331
Review Exercises
Work through all the problems in this chapter review and check
your answers in the back of the book.Answers to all review problems
are there along with section numbers in italics to indicate
where each type of problem is discussed. Where weaknesses show
up, review appropriate sections in the text.
A
1. Given the linear programming problem
Convert the problem constraints into a system of equations
using slack variables.
2. How many basic variables and how many nonbasic variables
are associated with the system in Problem 1?
3. Find all basic solutions for the system in Problem 1, and
determine which basic solutions are feasible.
4. Write the simplex tableau for Problem 1, and circle the
pivot element. Indicate the entering and exiting variables.
5. Solve Problem 1 using the simplex method.
6. For the simplex tableau below, identify the basic and nonbasic
variables. Find the pivot element, the entering and
exiting variables, and perform one pivot operation.
7. Find the basic solution for each tableau. Determine whether
the optimal solution has been reached, additional pivoting is
required, or the problem has no optimal solution.
(A)
x1 x2 s1 s2 P
C
4 1 0 0 0
2 0 1 1 0
-2 0 3 0 1
3
2
5
12
S
x1 x2 x3 s1 s2 s3 P
D
2 1 3 -1 0 0 0
3 0 4 1 1 0 0
2 0 5 2 0 1 0
-8 0 -5 3 0 0 1
4
20
30
10
50
T
x1, x2 U 0
x1 + 2×2 … 10
subject to 2×1 + x2 … 8
Maximize P = 6×1 + 2×2
(B)
(C)
8. Form the dual of
9. Write the initial system for the dual in Problem 8.
10. Write the first simplex tableau for the dual in Problem 8
and label the columns.
11. Use the simplex method to find the optimal solution of the
dual in Problem 8.
12. Use the final simplex tableau from Problem 11 to find the
optimal solution of the linear programming problem in
Problem 8.
B
13. Solve the linear programming problem using the simplex
method.
14. Form the dual of the linear programming problem
15. Solve Problem 14 by applying the simplex method to the
dual problem.
x1, x2 U 0
x2 U 3
x1 + 2×2 U 15
subject to x1 + x2 U 10
Minimize C = 3×1 + 8×2
x1, x2 U 0
4×1 + 2×2 … 20
3×1 + 3×2 … 21
subject to 2×1 + 4×2 … 24
Maximize P = 3×1 + 4×2
x1, x2 U 0
2×1 + x2 U 20
subject to x1 + 3×2 U 15
Minimize C = 5×1 + 2×2
C
1 -2 0 4 0
0 2 1 6 0
0 3 0 2 1
3
6
15
10
S
x1 x2 s1 s2 P
C
-1 3 0 1 0
0 2 1 0 0
-2 1 0 0 1
3
7
0
22
S
6-4 Maximization and Minimization with Mixed Problem Constraints
• The big M method can be used to find the maximum of any objective function on any feasible region.The
solution process involves the introduction of two new types of variables, surplus variables and artificial
variables, and a modification of the objective function.The result is an initial tableau that can be transformed
into the tableau of a modified problem.
• Applying the simplex method to the modified problem produces a solution to the original problem, if
one exists.
• The dual method can be used to solve only certain minimization problems. But all minimization problems
can be solved by using the big M method to find the maximum of the negative of the objective function.The
big M method also lends itself to computer implementation.
Ex. 1, p. 318
Ex. 2, p. 320
Ex. 3, p. 321
Ex. 4, p. 322
Ex. 5, p. 324
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
Prkentaice Hjalol. Ckopyarig htj ©20k11 Pjeaorsokn Eadu cajtioon,
332 CHAPTER 6 Linear Programming: The Simplex Method
Solve the linear programming Problems 16 and 17.
16.
17.
In Problems 18 and 19,
(A) Introduce slack, surplus, and artificial variables and form the
modified problem.
(B) Write the preliminary simplex tableau for the modified
problem and find the initial simplex tableau.
(C) Find the optimal solution of the modified problem by
applying the simplex method to the initial simplex tableau.
(D) Find the optimal solution of the original problem, if it exists.
18.
19.
20. Find the modified problem for the following linear programming
problem. (Do not solve.)
Write a brief verbal description of the type of linear programming
problem that can be solved by the method indicated in Problems
21–23. Include the type of optimization, the number of variables,
the type of constraints, and any restrictions on the coefficients and
constants.
21. Basic simplex method with slack variables
22. Dual method
23. Big M method
C
24. Solve the following linear programming problem by the
simplex method, keeping track of the obvious basic solution
at each step. Then graph the feasible region and illustrate
the path to the optimal solution determined by the simplex
method.
x1, x2 U 0
x2 … 10
x1 … 8
3×1 + x2 … 26
subject to x1 + 2×2 … 22
Maximize P = 2×1 + 3×2
x1, x2, x3 U 0
3×1 + 2×2 – x3 = 4
-x1 – x2 + 2×3 … -2
subject to x1 – 3×2 + x3 … 7
Maximize P = 2×1 + 3×2 + x3
x1, x2 U 0
x1 + 2×2 … 4
subject to x1 + x2 U 5
Maximize P = x1 + x2
x1, x2 U 0
x1 + 2×2 … 8
subject to x1 + x2 U 6
Maximize P = x1 + 3×2
x1, x2, x3 U 0
x1 + x2 … 5
subject to x1 – x2 – 2×3 … 3
Maximize P = 5×1 + 3×2 – 3×3
x1, x2, x3 U 0
2×1 + 2×2 – 5×3 … 10
subject to x1 – x2 – 2×3 … 3
Maximize P = 5×1 + 3×2 – 3×3
25. Solve by the dual method:
26. Solve Problem 25 by the big M method.
27. Solve by the dual method:
Applications
In Problems 28–33, construct a mathematical model in the form
of a linear programming problem. (The answers in the back of the
book for these application problems include the model.) Then
solve the problem by the simplex, dual, or big M methods.
28. Investment. An investor has $150,000 to invest in oil stock,
steel stock, and government bonds. The bonds are guaranteed
to yield 5%, but the yield for each stock can vary. To
protect against major losses, the investor decides that the
amount invested in oil stock should not exceed $50,000 and
that the total amount invested in stock cannot exceed the
amount invested in bonds by more than $25,000.
(A) If the oil stock yields 12% and the steel stock yields
9%, how much money should be invested in each alternative
in order to maximize the return? What is the
maximum return?
(B) Repeat part (A) if the oil stock yields 9% and the steel
stock yields 12%.
29. Manufacturing. A company manufactures outdoor furniture
consisting of regular chairs, rocking chairs, and chaise
lounges. Each piece of furniture passes through three different
production departments: fabrication, assembly, and finishing.
Each regular chair takes 1 hour to fabricate, 2 hours
to assemble, and 3 hours to finish. Each rocking chair takes
2 hours to fabricate, 2 hours to assemble, and 3 hours to finish.
Each chaise lounge takes 3 hours to fabricate, 4 hours to
assemble, and 2 hours to finish.There are 2,500 labor-hours
available in the fabrication department, 3,000 in the assembly
department, and 3,500 in the finishing department. The
company makes a profit of $17 on each regular chair, $24 on
each rocking chair, and $31 on each chaise lounge.
(A) How many chairs of each type should the company
produce in order to maximize profit? What is the maximum
profit?
(B) Discuss the effect on the optimal solution in part (A) if
the profit on a regular chair is increased to $25 and all
other data remain the same.
(C) Discuss the effect on the optimal solution in part (A) if
the available hours on the finishing department are
reduced to 3,000 and all other data remain the same.
x1, x2, x3, x4 U 0
x2 + x4 U 300
x1 + x3 U 400
x3 + x4 … 500
subject to x1 + x2 … 240
Minimize C = 15×1 + 12×2 + 15×3 + 18×4
x1, x2 U 0
x1 + x2 U 6
2×1 + x2 U 9
subject to 2×1 + x2 … 20
Minimize C = 3×1 + 2×2
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
bjyo Prkentiace Hjalol. Ckopyarigh tj ©20k11 Pjeaorsokn Eaduc ajtioon,
Review Exercises 333
Plant X Plant Y
Maximum
Production
Factory A $5 $8 1,500
Factory B $9 $7 1,000
Minimum Requirement 900 1,200
30. Shipping schedules. A company produces motors for washing
machines at factory A and factory B. The motors are
then shipped to either plant X or plant Y, where the washing
machines are assembled. The maximum number of
motors that can be produced at each factory monthly, the
minimum number required monthly for each plant to meet
anticipated demand, and the shipping charges for one
motor are given in the table. Determine a shipping schedule
that will minimize the cost of transporting the motors from
the factories to the assembly plants.
31. Blending—food processing. A company blends long-grain
rice and wild rice to produce two brands of rice mixes:
brand A, which is marketed under the company’s name; and
brand B, which is marketed as a generic brand. Brand A
must contain at least 10% wild rice, and brand B must contain
at least 5% wild rice. Long-grain rice costs $0.70 per
pound, and wild rice costs $3.40 per pound. The company
sells brand A for $1.50 a pound and brand B for $1.20 a
pound. The company has 8,000 pounds of long-grain rice
and 500 pounds of wild rice on hand. How should the company
use the available rice to maximize its profit? What is
the maximum profit?
ISBN 0-558-67351-1
Finite Mathematics for Business, Economics, Life Sciences, and Social Sciences, Twelfth Edition, by Raymond A. Barnett, Michael R. Ziegler, and Karl E. Byleen.
Prkentaice Hjalol. Ckopyarig htj ©20k11 Pjeaorsokn Eadu cajtioon,
Use the order calculator below and get started! Contact our live support team for any assistance or inquiry.
[order_calculator]