Tan S.T. Finite Mathematics for the Managerial, Life, and Social Sciences
Подождите немного. Документ загружается.
Solution
Upon multiplying each of the first two inequalities of (14) by 1, we
obtain the following equivalent system of constraints in which each of the expres-
sions involving the variables is greater than or equal to a constant:
x
1
x
2
x
3
400
x
4
x
5
x
6
600
x
1
x
4
200
x
2
x
5
300
x
3
x
6
400
x
1
0, x
2
0, . . . , x
6
000
The problem may now be solved by duality. First, we write the tableau:
Interchanging the rows and columns of this tableau and heading the five columns
of the resulting array of numbers by the variables u
1
, u
2
, u
3
, u
4
, and u
5
, we obtain
the tableau:
from which we construct the associated dual problem: Maximize P 400u
1
600u
2
200u
3
300u
4
400u
5
subject to
u
1
u
3
20
u
1
u
4
8
u
1
u
5
10
u
2
u
3
12
u
2
u
4
22
u
2
u
5
18
u
1
0, u
2
0, . . . , u
5
00
Solving the standard maximization problem by the simplex algorithm, we
obtain the following sequence of tableaus (x
1
, x
2
, . . . , x
6
are slack variables):
232 4 LINEAR PROGRAMMING: AN ALGEBRAIC APPROACH
x
1
x
2
x
3
x
4
x
5
x
6
Constant
1 1 1000 400
0001 1 1 600
100 100 200
0 1 0 0 1 0 300
001001 400
20 810122218
u
1
u
2
u
3
u
4
u
5
Constant
1 0100 20
1 0010 8
1 0001 10
0 1100 12
0 1010 22
0 1001 18
400 600 200 300 400
87533_04_ch4_p201-256 1/30/08 9:52 AM Page 232
4.2 THE SIMPLEX METHOD: STANDARD MINIMIZATION PROBLEMS 233
u
1
u
2
u
3
u
4
u
5
x
1
x
2
x
3
x
4
x
5
x
6
P Constant
⫺1 0 1 0 01000000 20
⫺1 0 0 1 00100000 8
⫺1 0 0 0 10010000 10
0 ⫺1 1 0 00001000 12
0 ⫺1 0 1 00000100 22
0 ⫺1 0 0 10000010 18
400 600 ⫺200 ⫺300 ⫺4000000001 0
u
1
u
2
u
3
u
4
u
5
x
1
x
2
x
3
x
4
x
5
x
6
P Constant
⫺1 0 1 0010 00000 20
⫺1 0 0 1001 00000 8
⫺1 0 0 0100 10000 10
0 ⫺1 1 0000 01000 12
0 ⫺10100000100 22
1 ⫺1 0 0000 ⫺10010 8
0 600 ⫺200 ⫺300 0 0 0 400 0 0 0 1 4000
u
1
u
2
u
3
u
4
u
5
x
1
x
2
x
3
x
4
x
5
x
6
P Constant
⫺1 0 1001 0 00000 20
⫺1 0 0100 1 00000 8
⫺1 0 0010 0 10000 10
0 ⫺1 1000001000 12
1 ⫺10000⫺1 00100 14
1 ⫺1 0000 0 ⫺10010 8
⫺300 600 ⫺2000003004000001 6400
Ratio
—
—
10
—
—
18
Pivot
씮
row
앖
Pivot column
Ratio
—
8
—
—
22
—
Pivot
씮
row
R
6
⫺ R
3
⎯⎯⎯⎯→
R
7
⫹ 400R
3
앖
Pivot column
앖
Pivot column
R
5
⫺ R
2
⎯⎯⎯⎯→
R
7
⫹ 300R
2
Ratio
—
—
—
—
14
8
Pivot
씮
row
u
1
u
2
u
3
u
4
u
5
x
1
x
2
x
3
x
4
x
5
x
6
P Constant
R
1
⫹ R
6
0 ⫺1 1001 0 ⫺100 10 28
0 ⫺1 0100 1 ⫺100 10 16
0 ⫺1 0010 0 000 10 18
0 ⫺1 1000 0 010 00 12
0 0 0000 ⫺1 101⫺10 6
1 ⫺1 0000 0 ⫺100 10 8
0 300 ⫺200000300100003001 8800
u
1
u
2
u
3
u
4
u
5
x
1
x
2
x
3
x
4
x
5
x
6
P Constant
0 00001 0 ⫺1 ⫺10 10 16
0 ⫺10100 1 ⫺10010 16
0 ⫺10010 0 0 00 10 18
0 ⫺11000001000 12
0 00000 ⫺1101⫺10 6
1 ⫺10000 0 ⫺10010 8
0100000030010020003001 11,200
Ratio
28
—
—
12
—
—
Pivot
row
씮
R
2
⫹ R
6
⎯⎯⎯⎯→
R
3
⫹ R
6
R
5
⫺ R
6
R
7
⫹ 300R
6
앖
Pivot column
R
1
⫺ R
4
⎯⎯⎯⎯→
R
7
⫹ 200R
4
87533_04_ch4_p201-256 2/18/08 10:35 AM Page 233
234 4 LINEAR PROGRAMMING: AN ALGEBRAIC APPROACH
1. Write the dual problem associated with the following
problem:
Minimize C 2x 5y
subject to 4x y 40
2x y 30
x 3y 30
x 0, y 0
2. Solve the primal problem posed in Exercise 1.
Solutions to Self-Check Exercises 4.2 can be found on
page 236.
The last tableau is final, and we find that
x
1
0 x
2
300 x
3
100 x
4
200
x
5
0 x
6
300 P 11,200
Thus, to minimize shipping costs, Acrosonic should ship 300 loudspeaker sys-
tems from plant I to warehouse B, 100 systems from plant I to warehouse C,
200 systems from plant II to warehouse A, and 300 systems from plant II to
warehouse C. The company’s total shipping cost is $11,200.
4.2 Exercises
4.2 Self-Check Exercises
4.2 Concept Questions
1. Suppose you are given the linear programming problem
Minimize C 3x 5y
subject to 5x 2y 30
x 3y 21
x 0, y 0
Give the associated standard maximization problem that
you would use to solve this linear programming problem
via the simplex method.
2. Give three characteristics of a standard minimization linear
programming problem.
3. What is the primal problem associated with a standard
minimization linear programming problem? The dual
problem?
4. a. What does the fundamental theorem of duality tell us
about the existence of a solution to a primal problem?
b. How are the optimal values of the primal and dual prob-
lems related?
c. Given the final simplex tableau associated with a dual
problem, how would you determine the optimal solu-
tion to the associated primal problem?
In Exercises 1–6, use the technique developed in this
section to solve the minimization problem.
1. Minimize C 2x y
subject to x 2y 6
3x 2y 12
x 0, y 0
2. Minimize C 2x 3y
subject to 3x 4y 24
7x 4y 16
x 0, y 0
3. Minimize C 3x 2y subject to the constraints of Exer-
cise 2.
4. Minimize C x 2y z
subject to x 2y 3z 10
2x y 2z 15
2x y
3z 20
x 0, y 0, z 0
5. Minimize C 2x 3y 4z
subject to x 2y z 8
x 2y 2z 10
2x 4y 3z 12
x 0, y 0, z 0
6. Minimize C 3x 2y z subject to the constraints of
Exercise 5.
87533_04_ch4_p201-256 1/30/08 9:52 AM Page 234
4.2 THE SIMPLEX METHOD: STANDARD MINIMIZATION PROBLEMS 235
In Exercises 7–10, you are given the final simplex tableau
for the dual problem. Give the solution to the primal prob-
lem and the solution to the associated dual problem.
7.
Problem: Minimize C 8x 12y
subject to x 3y 2
2x 2y 3
x 0, y 0
Final tableau:
u √xyP Constant
01
3
4
1
4
03
10
1
2
1
2
02
00
5
4
1
4
113
8. Problem: Minimize C 3x 2y
subject to 5x y 10
2x 2y 12
x 4y 12
x 0, y 0
Final tableau:
u √ w xyP Constant
10
3
4
1
4
1
4
0
1
4
01
1
8
9
1
8
5
8
0
7
8
00 9 1 51 13
9. Problem: Minimize C 10x 3y 10z
subject to 2x y 5z 20
4x y z 30
x 0, y 0, z 00
Final tableau:
u √ x yzP Constant
01
1
2
100 2
10
1
2
200 1
00 2910 3
00 5 1001 80
10. Problem: Minimize C 2x 3y
subject to x 4y 8
x y 5
2x y 7
x 0, y 0
Final tableau:
u √ w xyP Constant
01
7
3
4
3
1
3
0
5
3
10
1
3
1
3
1
3
0
1
3
002411 11
In Exercises 11–20, construct the dual problem associ-
ated with the primal problem. Solve the primal problem.
11. Minimize C 2x 5y 12. Minimize C 3x 2y
subject to x 2y 4 subject to 2x 3y 90
3x 2y 63x 2y 120
x 0, y 0 x 0, y 0
13. Minimize C 6x 4y 14. Minimize C 10x y
subject to 6x y 60 subject to 4x y 16
2x y 40 x 2y 12
x y 30
x 2
x 0, y 0 x 0, y 00
15. Minimize C 200x 150y 120z
subject to 20x 10y z 10
x y 2z 20
x 0, y 0, z 0
16. Minimize C 40x 30y 11z
subject to 2x y z 8
x y z 6
x 0, y 0, z 0
17. Minimize C 6x 8y 4
z
subject to x 2y 2z 10
2x y z 24
x y z 16
x 0, y 0, z 0
18. Minimize C 12x 4y 8z
subject to 2x 4y z 6
3x 2y 2z 2
4x y z 2
x 0, y 0, z 0
19. Minimize C 30x 12y 20z
subject to 2x 4y
3z 6
6x z 2
6y 2z 4
x 0, y 0, z 0
20. Minimize C 8x 6y 4z
subject to 2x 3y z 6
x 2y 2z 4
x y 2z 2
x 0, y 0, z 0
87533_04_ch4_p201-256 1/30/08 9:52 AM Page 235
21. T
RANSPORTATION
Deluxe River Cruises operates a fleet of
river vessels. The fleet has two types of vessels: A type-A
vessel has 60 deluxe cabins and 160 standard cabins,
whereas a type-B vessel has 80 deluxe cabins and 120 stan-
dard cabins. Under a charter agreement with Odyssey
Travel Agency, Deluxe River Cruises is to provide
Odyssey with a minimum of 360 deluxe and 680 standard
cabins for their 15-day cruise in May. It costs $44,000 to
operate a type-A vessel and $54,000 to operate a type-B
vessel for that period. How many of each type vessel
should be used in order to keep the operating costs to a
minimum? What is the minimum cost?
22. S
HIPPING
C
OSTS
Acrosonic manufactures a model-G loud-
speaker system in plants I and II. The output at plant I is at
most 800/month, and the output at plant II is at most
600/month. Model-G loudspeaker systems are also shipped
to the three warehouses—A, B, and C—whose minimum
monthly requirements are 500, 400, and 400 systems,
respectively. Shipping costs from plant I to warehouse A,
warehouse B, and warehouse C are $16, $20, and $22 per
loudspeaker system, respectively, and shipping costs from
plant II to each of these warehouses are $18, $16, and $14,
respectively. What shipping schedule will enable Acrosonic
to meet the requirements of the warehouses while keeping
its shipping costs to a minimum? What is the minimum cost?
23. A
DVERTISING
Everest Deluxe World Travel has decided to
advertise in the Sunday editions of two major newspapers
in town. These advertisements are directed at three groups
of potential customers. Each advertisement in newspaper I
is seen by 70,000 group-A customers, 40,000 group-B
customers, and 20,000 group-C customers. Each advertise-
ment in newspaper II is seen by 10,000 group-A, 20,000
group-B, and 40,000 group-C customers. Each advertise-
ment in newspaper I costs $1000, and each advertisement
in newspaper II costs $800. Everest would like their adver-
tisements to be read by at least 2 million people from group
A, 1.4 million people from group B, and 1 million people
from group C. How many advertisements should Everest
place in each newspaper to achieve its advertising goals at
a minimum cost? What is the minimum cost?
24. S
HIPPING
C
OSTS
Steinwelt Piano manufactures uprights and
consoles in two plants, plant I and plant II. The output of
plant I is at most 300/month, and the output of plant II is at
most 250/month. These pianos are shipped to three ware-
houses that serve as distribution centers for Steinwelt. To fill
current and projected future orders, warehouse A requires a
minimum of 200 pianos/month, warehouse B requires at
least 150 pianos/month, and warehouse C requires at least
200 pianos/month. The shipping cost of each piano from
plant I to warehouse A, warehouse B, and warehouse C is
$60, $60, and $80, respectively, and the shipping cost of
each piano from plant II to warehouse A, warehouse B, and
warehouse C is $80, $70, and $50, respectively. What ship-
ping schedule will enable Steinwelt to meet the requirements
of the warehouses while keeping the shipping costs to a min-
imum? What is the minimum cost?
25. N
UTRITION
—D
IET
P
LANNING
The owner of the Health Juice-
Bar wishes to prepare a low-calorie fruit juice with a high
vitamin A and vitamin C content by blending orange juice
and pink grapefruit juice. Each glass of the blended juice is
to contain at least 1200 International Units (IU) of vitamin
A and 200 IU of vitamin C. One ounce of orange juice con-
tains 60 IU of vitamin A, 16 IU of vitamin C, and 14 calo-
ries; each ounce of pink grapefruit juice contains 120 IU of
vitamin A, 12 IU of vitamin C, and 11 calories. How many
ounces of each juice should a glass of the blend contain if
it is to meet the minimum vitamin requirements while con-
taining a minimum number of calories?
26. P
RODUCTION
C
ONTROL
An oil company operates two
refineries in a certain city. Refinery I has an output of 200,
100, and 100 barrels of low-, medium-, and high-grade oil
per day, respectively. Refinery II has an output of 100, 200,
and 600 barrels of low-, medium-, and high-grade oil per
day, respectively. The company wishes to produce at least
1000, 1400, and 3000 barrels of low-, medium-, and high-
grade oil to fill an order. If it costs $200/day to operate
refinery I and $300/day to operate refinery II, determine
how many days each refinery should be operated in order
to meet the production requirements at minimum cost to
the company. What is the minimum cost?
In Exercises 27 and 28, determine whether the statement
is true or false. If it is true, explain why it is true. If it is
false, give an example to show why it is false.
27. If a standard minimization linear programming problem
has a unique solution, then so does the corresponding max-
imization problem with objective function P C, where
C a
1
x
1
a
2
x
2
a
n
x
n
is the objective function for
the minimization problem.
28. The optimal value attained by the objective function of the
primal problem may be different from that attained by the
objective function of the dual problem.
236
4 LINEAR PROGRAMMING: AN ALGEBRAIC APPROACH
4.2 Solutions to Self-Check Exercises
1. We first write down the following tableau for the given
(primal) problem:
xy Constant
41 40
21 30
13 30
25 0
Next, we interchange the columns and rows of the tableau
and head the three columns of the resulting array with the
three variables, u, √, and w, obtaining the tableau
u √ w Constant
421 2
113 5
40 30 30 0
87533_04_ch4_p201-256 1/30/08 9:52 AM Page 236
4.2 THE SIMPLEX METHOD: STANDARD MINIMIZATION PROBLEMS 237
Interpreting the last tableau as if it were the initial tableau
for a standard linear programming problem—with the
exception that the signs of the coefficients pertaining to
the objective function are not reversed—we construct the
required dual problem as follows:
2. We introduce slack variables x and y to obtain the system
of linear equations
Using the simplex algorithm, we obtain the sequence of
simplex tableaus
The last tableau is final, and the solution to the primal
problem is x 12 and y 6 with a minimum value for C
of 54.
USING
TECHNOLOGY
The Simplex Method: Solving Minimization Problems
Graphing Utility
A graphing utility can be used to solve minimization problems using the simplex
method.
EXAMPLE 1
Minimize C 2x 3y
subject to 8x y 80
3x 2y 100
x 4y 80
x 0, y 0
Maximize P 40u 30√ 30w
subject to 4u 2√ w 2
u √ 3w 5
u 0, √ 0, w 0
4u 2√ w x 2
u √ 3w y 5
40u 30√ 30w P 0
Solution for the
primal problem
u √ w x yP Constant
4 2 1100 2
1 1 3010 5
40 30 30001 0
u √ wx yP Constant
1
1
2
1
4
1
4
00
1
2
1 1 3010 5
40 30 30001 0
u √ wxyPConstant
1
1
2
1
4
1
4
00
1
2
0
1
2
1
4
1
1
4
10
9
2
0 10 20 10 0 1 20
Pivot
씮
row
Ratio
5
1
5
2
4
1
2
R
2
R
1
————
씮
R
3
40R
1
앖
Pivot
column
Ratio
9/2
11/4
18
11
1/2
1/4
2
Pivot
씮
row
앖
Pivot
column
R
1
⎯→
1
4
R
2
⎯→
4
11
u √ wxyPConstant
1
1
2
1
4
1
4
00
1
2
0
1
2
1
1
1
1
1
1
4
1
0
1
1
8
1
0 10 20 10 0 1 20
u √ wx yPConstant
1
1
5
1
0
1
3
1
1
1
1
0
1
1
1
0
1
2
1
1
1
1
1
1
4
1
0
1
1
8
1
0
7
1
0
1
0
9
1
0
1
8
1
0
1
1
5
1
8
1
0
u √ wxyPConstant
1
5
1
10
3
5
1
5
0
1
5
0
1
2
1
1
1
1
1
1
4
1
0
1
1
8
1
0
7
1
0
1
0
9
1
0
1
8
1
0
1
1
5
1
8
1
0
u √ wx yPConstant
1
5
1
10
3
5
1
5
0
1
5
2
5
01
1
5
2
5
0
8
5
14 0 0 12 6 1 54
앖
Pivot
column
Pivot
씮
row
Ratio
18/11
2/11
9
1/11
5/11
1
5
R
1
⎯→
11
5
R
1
R
2
———씮
R
3
20R
2
1
4
R
2
R
1
⎯⎯⎯→
R
3
R
1
70
11
2
11
(continued)
87533_04_ch4_p201-256 1/30/08 9:52 AM Page 237
u √ wx y P Constant
8 3 1100 2
1 2 4010 3
80 100 80001 0
u √ wxyPConstant
2.67 1 0.33 0.33 0 0 0.67
1240103
80 100 800010
u √ wxyPConstant
2.67 1 0.33 0.33 0 0 0.67
4.33 0 3.33 0.67 1 0 1.67
186.67 0 46.67 33.33 0 1 66.67
u √ wxyPConstant
2.67 1 0.33 0.33 0 0 0.67
1.30 0 1 0.2 0.3 0 0.5
186.67 0 46.67 33.33 0 1 66.67
Solution
We begin by writing the dual problem associated with the given primal
problem. From the tableau for the primal problem
we obtain—upon interchanging the columns and rows of this tableau and heading
the three columns of the resulting array with the variables u, √, and w—the tableau
This tells us that the dual problem is
To solve this standard maximization problem, we proceed as follows:
238 4 LINEAR PROGRAMMING: AN ALGEBRAIC APPROACH
xy Constant
81 80
3 2 100
14 80
23
u √ w Constant
831 2
124 3
80 100 80
Maximize P 80u 100√ 80w
subject to 8u 3√ w 2
u 2√ 4w 3
u 0, √ 0, w 0
Pivot row 씮
앖
Pivot column
Ratio
3
2
2
3
*rowÓ
1
3
, A, 1Ô 䉴 B
⎯⎯⎯⎯⎯⎯⎯→
*rowⴙ(2, B, 1, 2)
䉴 C
⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯→
*rowⴙ(100, C, 1, 3) 䉴 B
Pivot
씮
row
Ratio
2
0.5
앖
Pivot column
*rowÓ
3.
1
33
, B, 2Ô 䉴 C
⎯⎯⎯⎯⎯⎯⎯⎯→
*rowⴙ(0.33, C, 2, 1) 䉴 B
⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯→
*rowⴙ(46.67, B, 2, 3) 䉴 C
87533_04_ch4_p201-256 1/30/08 9:52 AM Page 238
4.2 THE SIMPLEX METHOD: STANDARD MINIMIZATION PROBLEMS 239
From the last tableau, we see that x 23.99, y 14.02, and the minimum value of
C is 90.03.
Excel
EXAMPLE 2
Solution
We use Solver as outlined in Example 2, pages 223–226, to obtain the
spreadsheet shown in Figure T1. (In this case, select next to Equal to:
instead of M
ax because this is a minimization problem. Also select in the Add
Constraint dialog box because the inequalities in the problem are of the form .)
From the spreadsheet, we read off the solution: x 24, y 14, and C 90.
EXAMPLE 3
Sensitivity Analysis* Solve the following linear programming
problem:
Maximize P 2x 4y
subject to 2x 5y 19
Constraint 1
3x 2y 12 Constraint 2
x 0, y 0
ABCDEFGHI
1
Minimization Problem
2
3
Decision Variables
4
5
6
7
8
Objective Function
9
10
Constraints
11
80
12
100
13
80
80
Formulas for indicated cells
C8: = 2
*
C4 + 3
*
C5
C11: = 8
*
C4 + C5
C12: = 3
*
C4 + 2
*
C5
C13: = C4 + 4
*
C5
y
x
>=
100
>=
206
90
14
24
>=
>=
Min
(continued)
u √ wxyPConstant
3.1 1 0 0.4 0.1 0 0.50
1.3 0 1 0.2 0.3 0 0.50
125.93 0 0.05 23.99 14.02 1 90.03
Solution for the
primal problem
FIGURE T1
Completed spreadsheet after using Solver
Note: Boldfaced words/characters enclosed in a box (for example, ) indicate that an action (click, select, or press) is
required. Words/characters printed blue (for example, Chart sub-t
ype) indicate words/characters that appear on the screen.
Words/characters printed in a typewriter font (for example, =(—2/3)*A2+2) indicate words/characters that need to be typed
and entered.
*For those who have completed Section 3.4.
Enter
Minimize C 2x 3y
subject to 8x y 80
3x 2y 100
x 4y 80
x 0, y 0
87533_04_ch4_p201-256 1/30/08 9:52 AM Page 239
240 4 LINEAR PROGRAMMING: AN ALGEBRAIC APPROACH
a. Use Solver to solve the problem.
b. Find the range of values that the coefficient of x can assume without changing
the optimal solution.
c. Find the range of values that resource 1 (the constant on the right-hand side of
constraint 1) can assume without changing the optimal solution.
d. Find the shadow price for resource 1.
e. Identify the binding and nonbinding constraints.
Solution
a. Use Solver as outlined in Example 2, pages 223–226, to obtain the spreadsheet
shown in Figure T2.
b. In the Solver Results dialog box, hold down while selecting
and under Reports, and then click
. By clicking the
and tabs that appear at the bottom of
your worksheet, you can obtain the reports shown in Figures T3a and T3b.
(a) The Answer Report
(b) The Sensitivity Report
Adjustable Cells
Final Reduced Objective Allowable Allowable
Cell Name Value Cost Coefficient Increase Decrease
Final Shadow Constraint Allowable Allowable
Cell Name Value Price R.H. Side Increase Decrease
Constraints
$C$4 x 2 0 2 4 0.4
$C$5 y 3 0 4 1 2.666666667
$C$11 19 0.727272727 19 11 11
$C$12 12 0.181818182 12 16.5 4.4
Target Cell (Max)
Cell Name Original Value Final Value
$C$8 Objective Function 0 16
Cell Name Original Value Final Value
$C$4 x 0 2
$C$5 y 0 3
Cell Name Cell Value Formula Status Slack
$C$11 19 $C$11<=$E$11 Binding 0
$C$12 12 $C$12<=$E$12 Binding 0
Adjustable Cells
Constraints
Sensitivity Report 1Answer Report 1
OKSensitivity
AnswerCtrl
ABCDEFGHI
1
Maximization Problem
2
3
Decision Variables
4
5
6
7
8
Objective Function
9
10
Constraints
11
19
12
12
Formulas for indicated cells
C8: = 2
*
C4 + 4
*
C5
C11: = 2
*
C4 + 5
*
C5
C12: = 3
*
C4 + 2
*
C5
y
x
12
<=
19
16
3
2
<=
FIGURE T2
Completed spreadsheet for a maximiza-
tion problem
FIGURE T3
The Solver reports
87533_04_ch4_p201-256 1/30/08 9:52 AM Page 240
From the sensitivity report, we see that the value of the Objective Coefficient for
x is 2, the Allowable Increase for the coefficient is 4, and the Allowable Decrease
for the coefficient is 0.4. Thus, the coefficient can vary from 1.6 to 6 without
affecting the optimal solution.
c. From the sensitivity report, we see that the Final Value of the constraint for
resource 1 is 19 and the Allowable Increase and Allowable Decrease for this
value is 11. Thus, the value of the constraint must lie between 19 11 and
19 11—that is, between 8 and 30.
d. From the sensitivity report, we see that the Shadow Price for resource 1 is
0.727272727.
e. From the answer report, we conclude that both Constraints are binding.
4.2 THE SIMPLEX METHOD: STANDARD MINIMIZATION PROBLEMS 241
TECHNOLOGY EXERCISES
In Exercises 1–4, solve the linear programming problem
by the simplex method.
1. Minimize C x y 3z
subject to 2x y 3z 6
x 2y 4z 8
3x y 2z 4
x 0, y 0, z 0
2. Minimize C 2x 4y z
subject to x 2y 4z 7
3x y z 6
x 4y 2z 24
x 0, y 0, z 0
3. Minimize C x 1.2y
3.5z
subject to 2x 3y 5z 12
3x 1.2y 2.2z 8
1.2x 3y 1.8z 14
x 0, y 0, z 0
4. Minimize C 2.1x 1.2y z
subject to x y z 5.2
x 2.1y 4.2z 8.4
x 0, y 0, z 0
Exercises 5–8 are for Excel users only. You are
given a linear programming problem:
a. Use Solver to solve the problem.
b. Find the range of values that the coefficient of x can
assume without changing the optimal solution and
the range of values that the coefficient of y can
assume without changing the optimal solution.
c. Find the range of values that each resource (require-
ment) can assume.
d. Find the shadow price for each resource (require-
ment).
e. Identify the binding and nonbinding constraints.
5. Maximize P 3x 4y
subject to 2x 3y 12
Resource 1
2x y 8 Resource 2
x 0, y 0
6. Maximize P 2x 5y
subject to x 3y 15 Resource 1
4x y 16 Resource 2
x 0, y 0
7. Minimize C 2x 5y
subject to x 2y 4 Requirement 1
x y 3 Requirement 2
x 0, y 0
8. Minimize C 3x 4y
subject to x 3y 8 Requirement 1
x y 4 Requirement 2
x 0, y 0
87533_04_ch4_p201-256 1/30/08 9:52 AM Page 241