Simplex Method - Crest Essays

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

…

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

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

A(0, 16)

D(0, 21)

E(32, 0)

B(20, 6)

O(0, 0)

C(28, 0)

Feasible region

3x1 _ 4x2 _ 84

x1 _ 2x2 _ 32

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.

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

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.

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

A(0, 16)

D(0, 21)

E(32, 0)

B(20, 6)

O(0, 0)

C(28, 0)

Feasible region

3x1 _ 4x2 _ 84

x1 _ 2x2 _ 32

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?

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

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?

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

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

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

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

(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

(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 ?

(D) ? 0 0 ?

(E) ? 0 ? 0

(F) ? ? 0 0

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.)

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

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

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

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,

s1 s1

s1, s2,

x1 x2 s1 s2 P

1 2 1 0 0

3 4 0 1 0

-50 -80 0 0 1

P = $0.

x1 = 0, x2 = 0, s1 = 32, s2 = 84, P = 0

x1 x2

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

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

x1 x2 s1 s2 P

1 2 1 0 0

3 4 0 1 0

_50 _80 0 0 1

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

2 = 16 (smallest)

4 = 21

x1 x2 s1 s2 P

1 2 1 0 0

3 4 0 1 0

-50 -80 0 0 1

x2 s1 s2

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.

x1 = 0, x2

s1 s2,

x1 = 0, x2 = 0, s1 = 32, s2 = 84, P = 0

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

Exiting variable B

Pivot element

Pivot

column

s¡

s™

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.

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

(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

Exit B 12

s¡

s™

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,

x1 x2 s1 s2 P

1 12

0 0

1 0 -2 1 0

-10 0 40 0 1

1,280

-10x1 + 40s1 + P = 1,280

x1 – 2s1 + s2 = 20

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:

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

Exit B

s™

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

x1 x2 s1 s2 P

0 1 32

-12

1 0 -2 1 0

0 0 20 10 1

1,480

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

Exit B 20

1/2

1 16=32

s™

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

A(0, 16)

B(20, 6)

O(0, 0)

C(28, 0)

Feasible region

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.

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

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

Exit B

s¡

s™

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

Exit B

s¡

s™

x¡

s™

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

Exit B

0.25

2.5

s™

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

(–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™

x¡

~x™

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.

x1 x2 s1 s2 P

-2 3 1 0 0

-1 3 0 1 0

-6 -3 0 0 1

-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

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

1 2 1 0 0 1 0

160

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

0.5 1 0.5 0 0 0.5 0

–100 –300 –200 0 0 0 1 0 300R3+R4 B R4

Enter

Exit B

s¡

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

0.5 1 0.5 0 0 0.5 0

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

0.5 1 0.5 0 0 0.5 0

(–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

0 1 0 –1 0 1 0

100 0 0 100 0 100 1 26,000

Enter

Exit B

s¡

s™

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

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

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.

In Problems 5–8, find the pivot element, identify the entering and

exiting variables, and perform one pivot operation.

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

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

x1 x2 s1 s2 P

1 6 1 0 0

3 1 0 1 0

-1 -2 0 0 1

x1 x2 s1 s2 P

1 4 1 0 0

3 5 0 1 0

-8 -5 0 0 1

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

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

x1 x2 s1 s2 P

1 4 -2 0 0

0 2 3 1 0

0 5 6 0 1

x1 x2 s1 s2 P

2 1 0 3 0

3 0 1 -2 0

-4 0 0 4 1

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.

10.

11. Repeat Problem 9 with the objective function changed to

12. Repeat Problem 10 with the objective function changed to

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.

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.

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

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).

2×1 + 5×2 U 50

x1 + 3×2 U 27

16×1 + 45×2 = C

A = C

2 5

1 3

16 45

Minimize C = 16×1 + 45×2

subject to 2×1 + 5×2 U 50

x1 + 3×2 U 27

x1, x2 U 0

…,

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

2 1

5 3

50 27

…

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,

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

AT,

A = C

2 1 5

4 1 1

40 12 40

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.

10 20

(0, 10)

(15, 4)

(27, 0) 5 10 15

(8, 0)

(0, 15)

(3, 10)

(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

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

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.

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

5 1 0 0 1 0

–20 –30 0 0 0 1 0

1 0 0 0 10

1 1 0 1 0 0 12 (–1)R1+R2 B R2

5 1 0 0 1 0

(–1)R1+R3 B R3

–20 –30 0 0 0 1 0 30R1+R4 B R4

1 1 0 1 0 0 12

1 0 0 0 10

0 – 1 0 0 2

0 – 0 1 0

–5 0 0 0 1 300

1 0 0 0 10

1 0 – 2 0 0 4

0 – 0 1 0

–5 0 0 0 1 300

0 1 –1 0 0 8

1 0 – 2 0 0 4

0 0 2 –9 1 0

0 0 5 10 0 1 320

12 92

1292

1412

1212

1414

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

0 1 1 -1 0 0

1 0 -1 2 0 0

0 0 4 -9 1 0

0 0 10 10 0 1

320

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

A = C S

1 -1

-1 1

5 10

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

Pivot column

No positive elements

above dashed line in

pivot column

_5 5

_x1 _ x2 _ 2

x1 _ x2 _ 1

x1 _ x2 _ 1 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

x1 x2 x3

y1 y2 y3 y4

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

A = E

-1 -1 0 0

0 0 -1 -1

1 0 1 0

0 1 0 1

6 5 4 8

-700

-900

500

1,000

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

x1 x2

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

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.

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

0 1 5 -2 0

1 0 -7 3 0

0 0 1 2 1

121

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

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

7 3 -1 3

-6 1 0 -9

c d

2 1 -6 0 -1

5 2 0 1 3

-4

D T

-2

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

y1 y2 x1 x2 P

0 1 5 -3 0

1 0 -3 2 0

0 0 5 3 1

155

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

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.

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

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

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

-x1 + x2 – s2 = 2

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.

x1 x2 s1 s2 a1 P

1 1 1 0 0 0

-1 1 0 -1 1 0

-2 -1 0 0 M 1

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:

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,

1 1 1 0 0 0 10

-1 1 0 -1 1 0 2 S

-2 -1 0 0 M 1

†

1 1 1 0 0 0 10

~C -1 1 0 -1 1 0 2

M – 2 -M – 1 0 M 0 1

†

-2M

(-M)R2 + R3: R3

x1 x2 s1 s2 a1 P

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

Pivot column

Pivot row B

101

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

s¡

a¡

x™

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

a1 Z 0

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.

…

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

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.

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

-15M

-5M

-1

-M – 3

‘ D

-M – 1

-1

-3

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

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.

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

0 1 1 0 0 –1 1 0

(–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

–1 1 0 0 –1 –1 1 0

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

–1 1 0 0 –1 –1 1 0

3 0 0 0 M+4 1 M-1 1 10

a¡

s¡

x™

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

a¡

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.

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

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

5 10

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.

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

–6M

a¡

–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

–M – 50

–100

a¡

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

Minimize C = 30×1 + 30×2 + 10×3

-1

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.

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.

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)

x2 + x4

+ 110

x2 + x4

U 105

0 U 5×1 – 15×3

90×1 + 110×3 U 95(x1 + x3)

90 x1 + x3

x1 + x3

+ 110

x1 + x3

U 95

x3>(x1 + x3)

x1>(x1 + x3)

x1 + x3

+ 110

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.

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

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

-1 1 0 0 0

0 0 1 0 0

0 0 0 1 0

0 106 0 0 1

30,000

20,000

10,000

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.

SECTION 6-4 Maximization and Minimization with Mixed Problem Constraints 327

Exercises 6-4

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.

Use the big M method to solve Problems 9–22.

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.

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.

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.

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.

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.

Ex. 1, p. 303

Ex. 2, p. 306

Ex. 3, p. 308

Answers to Matched Problems

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.

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.

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.

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

4 1 0 0 0

2 0 1 1 0

-2 0 3 0 1

x1 x2 x3 s1 s2 s3 P

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

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.

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

1 -2 0 4 0

0 2 1 6 0

0 3 0 2 1

x1 x2 s1 s2 P

-1 3 0 1 0

0 2 1 0 0

-2 1 0 0 1

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.

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

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.

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.

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.

Use the order calculator below and get started! Contact our live support team for any assistance or inquiry.

[order_calculator]