Tan S.T. Finite Mathematics for the Managerial, Life, and Social Sciences

Подождите немного. Документ загружается.

192 3 LINEAR PROGRAMMING: A GEOMETRIC APPROACH

APPLIED EXAMPLE 2

Shadow Prices Consider the problem posed in

Example 1:

Maximize P ⫽ 2x ⫹ 1.5y

subject to Constraint 1

Constraint 2

Constraint 3

a. Find the range of values that resource 1 (the constant on the right-hand side

of constraint 1) can assume.

b. Find the shadow price for resource 1.

Solution

a. Suppose the right-hand side of constraint 1 is replaced by 1000 ⫹ h, where

h is a real number. Then the new optimal solution occurs at the point D⬘

(Figure 21).

x ⱖ 0, y ⱖ 0

x ⱕ 180

6x ⫹ 3y ⱕ 1200

3x ⫹ 4y ⱕ 1000

PORTFOLIO

As a land use planner for the

city of Burien, Washington, I assist

property owners every day in the

development of their land. By defi-

nition, land use planners develop plans and recommend

policies for managing land use. To do this, I must take into

account many existing and potential factors such as public

transportation, zoning laws, and other municipal laws. By

using the basic ideas of linear programming, I work with the

property owners to figure out maximum and minimum use

requirements for each individual situation. Then, I am able

to review and evaluate proposals for land use plans and

prepare recommendations. All this is necessary to process

an application for a land development permit.

Here’s how it works. A property owner who wants to

start a business on a vacant commercially zoned piece of

property comes to me. We have a discussion to find out

what type of commercial zone the property is in and

whether the use is permitted or would require additional

land use review. If the use is permitted and no further land

use review is required, I let the applicant know what criteria

have to be met and shown on the building plans. At this

point, the applicant begins working with his or her building

contractor, architect, or engineer and landscape architect

to meet the zoning code criteria. Once the applicant has

worked with one or more of these professionals, building

plans can be submitted for review. The plans are routed to

several different departments (building, engineer, public

works, and the fire department). Because I am the land use

planner for the project, one set of plans is routed to my

desk for review.

During this review, I determine whether or not the zon-

ing requirements have been met in order to make a final

determination of the application. These zoning requirements

are assessed by asking the applicant to give us a site plan

showing lot area measurements, building and impervious

surface coverage calculations, and building setbacks, just to

name a few. Additionally, I have to determine the parking

requirements. How many off-street parking spaces are

required? What are the isle widths? Is there enough room

for backing up? Then, I look at the landscaping require-

ments. Plans need to be drawn up by a landscape architect

and list specifics about the location, size, and types of

plants that will be used.

By weighing all these factors and measurements,

I can determine the viability of a

land development project. The basic

ideas of linear programming are

fundamentally at the heart of this

determination and are key to the

day-to-day choices that I must make

in my profession.

Morgan Wilson

TITLE Land Use Planner

INSTITUTION City of Burien

87533_03_ch3_p155-200 1/30/08 9:48 AM Page 192

To find the coordinates of D⬘, we solve the system

Multiplying the first equation by ⫺2 and then adding the resulting equation to

the second equation gives

Substituting this value of y into the second equation in the system gives

The nonnegativity of y implies that h ⱖ⫺400, and the nonnegativity of x

implies that h ⱕ 600. But constraint 3 dictates that x must also satisfy

Therefore, h must satisfy ⫺300 ⱕ h ⱕ 600. This tells us that the amount of

resource 1 must lie between 1000 ⫺ 300, or 700, and 1000 ⫹ 600, or 1600—

that is, between 700 and 1600 pounds.

b. If we set h ⫽ 1 in part (a), we obtain

y ⫽

1400 ⫹ 12⫽

802

x ⫽

1600 ⫺ 12⫽

599

h ⱖ⫺300

⫺h ⱕ 300

600 ⫺ h ⱕ 900

x ⫽

1600 ⫺ h2ⱕ 180

x ⫽

1600 ⫺ h2

x ⫹

1400 ⫹ h2⫽ 200

6x ⫹

1400 ⫹ h2⫽ 1200

y ⫽

1400 ⫹ h2

⫺5y ⫽⫺800 ⫺ 2h

6x ⫹ 3y ⫽ 1200

3x ⫹ 4y ⫽ 1000 ⫹ h

D′

3x + 4y = 1000 + h

3x + 4y = 1000 (constraint 1)

6x + 3y = 1200

(constraint 2)

x = 180 (constraint 3)

400

180

3.4 SENSITIVITY ANALYSIS 193

FIGURE 21

As the amount of resource 1 changes,

the point at which the optimal solution

occurs shifts from D to D⬘.

⫺6

⫺ 8

⫽⫺2000 ⫺ 2

⫹ 3

⫽ 1200

⫺5

⫽⫺800 ⫺ 2

87533_03_ch3_p155-200 2/18/08 10:31 AM Page 193

Therefore, the profit realized at this level of production is

Since the original optimal profit is $480 (see Example 1), we see that the

shadow price for resource 1 is $.20.

If you examine Figure 21, you can see that increasing resource 3 (the constant on the

right-hand side of constraint 3) has no effect on the optimal solution D(120, 160) of

the problem at hand. In other words, an increase in the resource associated with con-

straint 3 has no economic benefit for Kane Manufacturing. The shadow price for this

resource is zero. There is a surplus of this resource. Hence, we say that the constraint

x ⱕ 180 is not binding on the optimal solution D(120, 160).

On the other hand, constraints 1 and 2, which hold with equality at the optimal

solution D(120, 160), are said to be binding constraints. The objective function can-

not be increased without increasing these resources. They have positive shadow

prices.

Importance of Sensitivity Analysis

We conclude this section by pointing out the importance of sensitivity analysis in

solving real-world problems. The values of the parameters in these problems may

change. For example, the management of Ace Novelty might wish to increase the

price of a type-A souvenir because of increased demand for the product, or they might

want to see how a change in the time available on machine I affects the (optimal)

profit of the company.

When a parameter of a linear programming problem is changed, it is true that one

need only re-solve the problem to obtain a new solution to the problem. But since a

real-world linear programming problem often involves thousands of parameters, the

amount of work involved in finding a new solution is prohibitive. Another disadvan-

tage in using this approach is that it often takes many trials with different values of a

parameter in order to see their effect on the optimal solution of the problem. Thus, a

more analytical approach such as that discussed in this section is desirable.

Returning to the discussion of Ace Novelty, our analysis of the changes in the

coefficients of the objective (profit) function suggests that if management decides to

raise the price of a type-A souvenir, it can do so with the assurance that the optimal

solution holds as long as the new price leaves the contribution to the profit of a type-

A souvenir between $.40 and $2.40. There is no need to re-solve the linear program-

ming problem for each new price being considered. Also, our analysis of the changes

in the parameters on the right-hand side of the constraints suggests, for example, that

a meaningful solution to the problem requires that the time available for machine I lie

in the range between 100 and 600 minutes. Furthermore, the analysis tells us how to

compute the increase (decrease) in the optimal profit when the resource is adjusted, by

using the shadow price associated with that constraint. Again, there is no need to re-

solve the linear programming problem each time a change in the resource available is

anticipated.

Using Technology examples and exercises that are solved using Excel’s Solver can be

found on pages 222–226 and 237–241.

⫽

2401

⫽ 480.2

P ⫽ 2 x ⫹

y ⫽ 2 a

599

b⫹

802

194 3 LINEAR PROGRAMMING: A GEOMETRIC APPROACH

87533_03_ch3_p155-200 1/30/08 9:48 AM Page 194

3.4 SENSITIVITY ANALYSIS 195

Consider the linear programming problem:

Maximize P ⫽ 2x ⫹ 4y

subject to

Constraint 1

Constraint 2

1. Use the method of corners to solve this problem.

x ⱖ 0, y ⱖ 0

3x ⫹ 2y ⱕ 12

2x ⫹ 5y ⱕ 19

2. Find the range of values that the coefficient of x can

assume without changing the optimal solution.

3. Find the range of values that resource 1 (the constant on the

right-hand side of constraint 1) can assume without chang-

ing the optimal solution.

4. Find the shadow price for resource 1.

5. Identify the binding and nonbinding constraints.

Solutions to Self-Check Exercises can be found on page 197.

a. Write the inequality that represents an increase of h units

in resource 1.

b. Write the inequality that represents an increase of k units

in resource 2.

3. Explain the meaning of (a) a shadow price and (b) a bind-

ing constraint.

1. Suppose P ⫽ 3x ⫹ 4y is the objective function in a linear

programming (maximization) problem, where x denotes

the number of units of product A and y denotes the number

of units of product B to be made. What does the coefficient

of x represent? The coefficient of y?

2. Given the linear programming problem

Maximize P ⫽ 3x ⫹ 4y

subject to

Resource 1

Resource 22x ⫹ y ⱕ 5

x ⫹ y ⱕ 4

1. Refer to the production problem discussed on pages

185–187.

a. Show that the optimal solution holds if the contribution

to the profit of a type-B souvenir lies between $.50 and

$3.00.

b. Show that if the contribution to the profit of a type-A

souvenir is $1.50 (with the contribution to the profit of

a type-B souvenir held at $1.20), then the optimal profit

of the company will be $172.80.

c. What will be the optimal profit of the company if the

contribution to the profit of a type-B souvenir is $2.00

(with the contribution to the profit of a type-A souvenir

held at $1.00)?

2. Refer to the production problem discussed on pages

189–191.

a. Show that, for a meaningful solution, the time available

on machine II must lie between 90 and 540 min.

b. Show that, if the time available on machine II is

changed from 300 min to (300 ⫹ k) min, with no change

in the maximum capacity for machine I, then Ace Nov-

elty’s profit is maximized by producing

type-A souvenirs and type-B souvenirs,

1420 ⫹ 2k 2

1240 ⫺ k 2

c. Show that the shadow price for resource 2 (associated

with constraint 2) is $.28.

3. Refer to Example 2.

a. Find the range of values that resource 2 can assume.

b. By how much can the right-hand side of constraint

3 be changed such that the current optimal solution still

holds?

4. Refer to Example 2.

a. Find the shadow price for resource 2.

b. Identify the binding and nonbinding constraints.

In Exercises 5–10, you are given a linear programming

problem.

a. Use the method of corners 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 (requirement 1)

can assume.

d. Find the shadow price for resource 1 (requirement 1).

e. Identify the binding and nonbinding constraints.

5. Maximize P ⫽ 3x ⫹ 4y

subject to

Resource 1

Resource 2

x ⱖ 0, y ⱖ 0

2x ⫹ y ⱕ 8

2x ⫹ 3y ⱕ 12

3.4 Exercises

3.4 Self-Check Exercises

3.4 Concept Questions

where ⫺210 ⱕ k ⱕ 240.

87533_03_ch3_p155-200 1/30/08 9:48 AM Page 195

6. Maximize P ⫽ 2x ⫹ 5y

subject to

Resource 1

Resource 2

7. Minimize C ⫽ 2x ⫹ 5y

subject to

Requirement 1

Requirement 2

8. Minimize C ⫽ 3x ⫹ 4y

subject to

Requirement 1

Requirement 2

9. Maximize P ⫽ 4x ⫹ 3y

subject to

Resource 1

Resource 2

Resource 3

10. Maximize P ⫽ 4x ⫹ 5y

subject to

Resource 1

Resource 2

Resource 3

11. M

ANUFACTURING

—P

RODUCTION

CHEDULING

A company

manufactures two products, A and B, on machines I and II.

The company will realize a profit of $3/unit of product A

and a profit of $4/unit of product B. Manufacturing 1 unit

of product A requires 6 min on machine I and 5 min on

machine II. Manufacturing 1 unit of product B requires

9 min on machine I and 4 min on machine II. There are

5 hr of time available on machine I and 3 hr of time avail-

able on machine II in each work shift.

a. How many units of each product should be produced in

each shift to maximize the company’s profit?

b. Find the range of values that the contribution to the

profit of 1 unit of product A can assume without chang-

ing the optimal solution.

c. Find the range of values that the resource associated

with the time constraint on machine I can assume.

d. Find the shadow price for the resource associated with

the time constraint on machine I.

12. A

GRICULTURE

—C

ROP

LANNING

A farmer plans to plant two

crops, A and B. The cost of cultivating crop A is $40/acre

whereas that of crop B is $60/acre. The farmer has a max-

imum of $7400 available for land cultivation. Each acre of

crop A requires 20 labor-hours, and each acre of crop B

requires 25 labor-hours. The farmer has a maximum of

3300 labor-hours available. If he expects to make a profit

of $150/acre on crop A and $200/acre on crop B, how

many acres of each crop should he plant in order to maxi-

mize his profit?

a. Find the range of values that the contribution to the

profit of an acre of crop A can assume without chang-

ing the optimal solution.

b. Find the range of values that the resource associated

with the constraint on the available land can assume.

x ⱖ 0, y ⱖ 0

x ⱕ 25

x ⫹ 2y ⱕ 40

x ⫹ y ⱕ 30

x ⱖ 0, y ⱖ 0

x ⱕ 4

2x ⫹ 3y ⱕ 21

5x ⫹ 3y ⱕ 30

x ⱖ 0, y ⱖ 0

x ⫹ y ⱖ 4

x ⫹ 3y ⱖ 8

x ⱖ 0, y ⱖ 0

x ⫹ y ⱖ 3

x ⫹ 2y ⱖ 4

x ⱖ 0, y ⱖ 0

4x ⫹ y ⱕ 16

x ⫹ 3y ⱕ 15

c. Find the shadow price for the resource associated with

the constraint on the available land.

13. M

INING

—P

RODUCTION

Perth Mining Company operates

two mines for the purpose of extracting gold and silver.

The Saddle Mine costs $14,000/day to operate, and it

yields 50 oz of gold and 3000 oz of silver per day. The

Horseshoe Mine costs $16,000/day to operate, and it yields

75 oz of gold and 1000 ounces of silver per day. Company

management has set a target of at least 650 oz of gold and

18,000 oz of silver.

a. How many days should each mine be operated so that

the target can be met at a minimum cost?

b. Find the range of values that the Saddle Mine’s daily

operating cost can assume without changing the optimal

solution.

c. Find the range of values that the requirement for gold

can assume.

d. Find the shadow price for the requirement for gold.

14. T

RANSPORTATION

Deluxe River Cruises operates a fleet of

river vessels. The fleet has two types of vessels: a type-A ves-

sel has 60 deluxe cabins and 160 standard cabins, whereas a

type-B vessel has 80 deluxe cabins and 120 standard cabins.

Under a charter agreement with the 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.

a. How many of each type of vessel should be used in

order to keep the operating costs to a minimum?

b. Find the range of values that the cost of operating a

type-A vessel can assume without changing the optimal

solution.

c. Find the range of values that the requirement for deluxe

cabins can assume.

d. Find the shadow price for the requirement for deluxe

cabins.

15. M

ANUFACTURING

—P

RODUCTION

CHEDULING

Soundex pro-

duces two models of satellite radios. Model A requires

15 min of work on assembly line I and 10 min of work on

assembly line II. Model B requires 10 min of work on

assembly line I and 12 min of work on assembly line II. At

most 25 hr of assembly time on line I and 22 hr of assem-

bly time on line II are available each day. Soundex antici-

pates a profit of $12 on model A and $10 on model B.

Because of previous overproduction, management decides

to limit the production of model A satellite radios to no

more than 80/day.

a. To maximize Soundex’s profit, how many satellite

radios of each model should be produced each day?

b. Find the range of values that the contribution to the

profit of a model A satellite radio can assume without

changing the optimal solution.

c. Find the range of values that the resource associated

with the time constraint on machine I can assume.

d. Find the shadow price for the resource associated with

the time constraint on machine I.

e. Identify the binding and nonbinding constraints.

196

3 LINEAR PROGRAMMING: A GEOMETRIC APPROACH

87533_03_ch3_p155-200 1/30/08 9:48 AM Page 196

16. M

ANUFACTURING

Refer to Exercise 15.

a. If the contribution to the profit of a model A satellite

radio is changed to $8.50/radio, will the original optimal

solution still hold? What will be the optimal profit?

b. If the contribution to the profit of a model A satellite

radio is changed to $14.00/radio, will the original opti-

mal solution still hold? What will be the optimal profit?

17. M

ANUFACTURING

—P

RODUCTION

CHEDULING

Kane Manufac-

turing has a division that produces two models of fireplace

grates, model A and model B. To produce each model-A

grate requires 3 lb of cast iron and 6 min of labor. To pro-

duce each model-B grate requires 4 lb of cast iron and 3 min

of labor. The profit for each model-A grate is $2, and the

profit for each model-B grate is $1.50. 1000 lb of cast iron

and 20 labor-hours are available for the production of grates

each day. Because of an excess inventory of model-B grates,

management has decided to limit the production of model-B

grates to no more than 200 grates per day. How many grates

of each model should the division produce daily to maxi-

mize Kane’s profit?

a. Use the method of corners to solve the problem.

b. Find the range of values that the contribution to the

profit of a model-A grate can assume without changing

the optimal solution.

c. Find the range of values that the resource for cast iron

can assume without changing the optimal solution.

d. Find the shadow price for the resource for cast iron.

e. Identify the binding and nonbinding constraints.

18. M

ANUFACTURING

Refer to Exercise 17.

a. If the contribution to the profit of a model-A grate is

changed to $1.75/grate, will the original optimal solu-

tion still hold? What will be the new optimal solution?

b. If the contribution to the profit of a model-A grate is

changed to $2.50/grate, will the original optimal solu-

tion still hold? What will be the new optimal solution?

3.4 SENSITIVITY ANALYSIS 197

3.4 Solutions to Self-Check Exercises

1. The feasible set for the problem is shown in the accompa-

nying figure.

Evaluating the objective function P ⫽ 2x ⫹ 4y at each fea-

sible corner point, we obtain the following table:

Vertex P ⴝ 2x ⴙ 4y

A(0, 0) 0

B(4, 0) 8

C(2, 3) 16

We conclude that the maximum value of P is 16 attained at

the point (2, 3).

2. Assume that P ⫽ cx ⫹ 4y. Then

The slope of the isoprofit line is and must be less than

or equal to the slope of the line associated with constraint

1; that is,

⫺

y ⫽⫺

x ⫹

D10,

A(0, 0)

C(2, 3)

B(4, 0)

2x + 5y = 19 (constraint 1)

3x + 2y = 12 (constraint 2)

−2

Solving, we find A similar analysis shows that the

slope of the isoprofit line must be greater than or equal to

the slope of the line associated with constraint 2; that is,

Solving, we find c ⱕ 6. Thus, we have shown that if

1.6 ⱕ c ⱕ 6 then the optimal solution obtained previously

remains unaffected.

3. Suppose the right-hand side of constraint 1 is replaced by

19 ⫹ h, where h is a real number. Then the new optimal

solution occurs at the point whose coordinates are found by

solving the system

Multiplying the second equation by ⫺5 and adding the

resulting equation to 2 times the first equation, we obtain

Substituting this value of x into the second equation in the

system gives

y ⫽ 3 ⫹

2 y ⫽ 12 ⫺ 6 ⫹

3 a2 ⫺

h b⫹ 2y ⫽ 12

x ⫽ 2 ⫺

⫺11x ⫽⫺60 ⫹ 2119 ⫹ h 2⫽⫺22 ⫹ 2h

3 x ⫹ 2y ⫽ 12

2 x ⫹ 5y ⫽ 19 ⫹ h

⫺

ⱖ⫺

c ⱖ

⫺

ⱕ⫺

87533_03_ch3_p155-200 1/30/08 9:48 AM Page 197

The nonnegativity of x implies or h ⱕ 11.

The nonnegativity of y implies or h ⱖ⫺11.

Therefore, h must satisfy ⫺11 ⱕ h ⱕ 11. This tells us that

the amount used of resource 1 must lie between 19 ⫺ 11

and 19 ⫹ 11—that is, between 8 and 30.

4. If we set h ⫽ 1 in Exercise 3, we find that and

Therefore, for these values of x and y,y ⫽

x ⫽

3 ⫹

h ⱖ 0,

2 ⫺

h ⱖ 0,

Since the original optimal value of P is 16, we see that the

shadow price for resource 1 is

5. Since both constraints hold with equality at the optimal

solution C(2, 3), they are binding constraints.

P ⫽ 2 a

b⫹ 4 a

b⫽

184

⫽ 16

198 3 LINEAR PROGRAMMING: A GEOMETRIC APPROACH

Summary of Principal Terms

CHAPTER 3

TERMS

solution set of a system of linear inequalities (159) feasible solution (172) sensitivity analysis (185)

bounded solution set (160) feasible set (172) shadow price (191)

unbounded solution set (160) optimal solution (172) binding constraint (194)

objective function (164) isoprofit line (173)

linear programming problem (164) method of corners (174)

Concept Review Questions

CHAPTER 3

Fill in the blanks.

1. a. The solution set of the inequality ax ⫹ by ⬍ c (a, b not

both zero) is a/an

_____ _____

that does not include the

_____

with equation ax ⫹ by ⫽ c.

b. If ax ⫹ by ⬍ c describes the lower half-plane, then the

inequality

_____

describes the lower half-plane to-

gether with the line having equation

_____

2. a. The solution set of a system of linear inequalities in the

two variables x and y is the set of all

_____

satisfying

_____

inequality of the system.

b. The solution set of a system of linear inequalities is

_____

if it can be

_____

by a circle.

3. A linear programming problem consists of a linear func-

tion, called a/an

_____ _____

to be

_____

sub-

ject to constraints in the form of

_____

equations or

_____

4. a. If a linear programming problem has a solution, then it

must occur at a/an

_____ _____

of the feasible set.

b. If the objective function of a linear programming prob-

lem is optimized at two adjacent vertices of the feasible

set, then it is optimized at every point on the

_____

segment joining these vertices.

5. In sensitivity analysis, we investigate how changes in the

_____

of a linear programming problem affect the

_____

solution.

6. The shadow price for the ith

_____

is the

_____

by which

the

_____

of the objective function is

_____

if the right-

hand side of the ith constraint is

_____

by 1 unit.

Review Exercises

CHAPTER 3

In Exercises 1 and 2, find the optimal value(s) of the

objective function on the feasible set S.

1. Z ⫽ 2 x ⫹ 3y

(3, 4)

(0, 0) (5, 0)

(0, 6)

2. Z ⫽ 4x ⫹ 3y

(3, 5)

(1, 1)

(6,

(1, 3)

87533_03_ch3_p155-200 1/30/08 9:48 AM Page 198

In Exercises 3–12, use the method of corners to solve the

linear programming problem.

3. Maximize P ⫽ 3x ⫹ 5y

subject to

4. Maximize P ⫽ 2x ⫹ 3y

subject to

5. Minimize C ⫽ 2x ⫹ 5y

subject to

6. Minimize C ⫽ 3x ⫹ 4y

subject to

7. Maximize P ⫽ 3x ⫹ 2y

subject to

8. Maximize P ⫽ 6x ⫹ 2y

subject to

9. Minimize C ⫽ 2x ⫹ 7y

subject to

10. Minimize C ⫽ 3x ⫹ 2y

subject to

11. Minimize C ⫽ 4x ⫹ y

subject to

12. Find the maximum and minimum values of Q ⫽ 3x ⫹ 4y

subject to

7 x ⫹ 4y ⱕ 140

x ⫹ 3y ⱖ 30

x ⫺ y ⱖ⫺10

x ⱖ 0, y ⱖ 0

x ⫹ 4y ⱖ 12

2x ⫹ y ⱖ 10

6x ⫹ y ⱖ 18

x ⱖ 0, y ⱖ 0

2x ⫹ 3y ⱖ 14

x ⫹ y ⱖ 6

2x ⫹ y ⱖ 8

x ⱖ 0, y ⱖ 0

3x ⫹ 10y ⱖ 60

3x ⫹ 5y ⱖ 45

x ⱖ 0, y ⱖ 0

2x ⫺ 3y ⱖ 6

x ⫹ y ⱕ 8

x ⫹ 2y ⱕ 12

x ⱖ 0, y ⱖ 0

4x ⫹ 5y ⱖ 28

2x ⫹ 3y ⱕ 36

2x ⫹ y ⱕ 16

x ⱖ 0, y ⱖ 0

2x ⫹ 5y ⱖ 10

2x ⫹ y ⱖ 4

x ⱖ 0, y ⱖ 0

4x ⫹ y ⱖ 16

x ⫹ 3y ⱖ 15

x ⱖ 0, y ⱖ 0

x ⫺ 2y ⱕ 1

2x ⫹ y ⱕ 12

x ⱖ 0, y ⱖ 0

x ⫹ y

ⱕ 5

2x ⫹ 3y ⱕ 12

13. Find the maximum and minimum of Q ⫽ x ⫹ y subject to

14. Find the maximum and minimum of Q ⫽ 2x ⫹ 5y subject to

15. F

INANCIAL

NALYSIS

An investor has decided to commit no

more than $80,000 to the purchase of the common stocks of

two companies, company A and company B. He has also esti-

mated that there is a chance of at most a 1% capital loss on

his investment in company A and a chance of at most a 4%

loss on his investment in company B, and he has decided that

together these losses should not exceed $2000. On the other

hand, he expects to make a 14% profit from his investment in

company A and a 20% profit from his investment in company

B. Determine how much he should invest in the stock of each

company in order to maximize his investment returns.

16. M

ANUFACTURING

—P

RODUCTION

CHEDULING

Soundex pro-

duces two models of satellite radios. Model A requires

15 min of work on assembly line I and 10 min of work on

assembly line II. Model B requires 10 min of work on

assembly line I and 12 min of work on assembly line II. At

most, 25 labor-hours of assembly time on line I and 22

labor-hours of assembly time on line II are available each

day. It is anticipated that Soundex will realize a profit of

$12 on model A and $10 on model B. How many satellite

radios of each model should be produced each day in order

to maximize Soundex’s profit?

17. M

ANUFACTURING

—P

RODUCTION

CHEDULING

Kane Manufac-

turing has a division that produces two models of grates,

model A and model B. To produce each model-A grate

requires 3 lb of cast iron and 6 min of labor. To produce each

model-B grate requires 4 lb of cast iron and 3 min of labor.

The profit for each model-A grate is $2.00, and the profit for

each model-B grate is $1.50. Available for grate production

each day are 1000 lb of cast iron and 20 labor-hours. Because

of a backlog of orders for model-B grates, Kane’s manager

has decided to produce at least 180 model-B grates/day. How

many grates of each model should Kane produce to maxi-

mize its profit?

18. M

INIMIZING

HIPPING

OSTS

A manufacturer of projection

TVs must ship a total of at least 1000 TVs to its two cen-

tral warehouses. Each warehouse can hold a maximum of

750 TVs. The first warehouse already has 150 TVs on

hand, whereas the second has 50 TVs on hand. It costs $8

to ship a TV to the first warehouse, and it costs $16 to ship

a TV to the second warehouse. How many TVs should be

shipped to each warehouse to minimize the cost?

x ⱖ 0, y ⱖ 0

x ⱕ 12

x ⫹ 3y ⱕ 30

⫺x ⫹ y ⱕ 6

x ⫹ y ⱖ 4

x ⱖ 0, y ⱖ 0

x ⫹ 4y ⱕ 22

x ⫹ 2y ⱖ 8

5 x ⫹ 2y ⱖ 20

REVIEW EXERCISES 199

87533_03_ch3_p155-200 1/30/08 9:48 AM Page 199

1. Determine graphically the solution set for the following

systems of inequalities.

2. Find the maximum and minimum values of Z ⫽ 3x ⫺ y on

the following feasible set.

3. Maximize P ⫽ x ⫹ 3y

subject to

x ⱖ 0, y ⱖ 0

3x ⫹ 7y ⱕ 24

2x ⫹ 3y ⱕ 11

(28, 8)

(16, 24)

(8, 2)

(3, 16)

y ⱖ 2

x ⱖ 0

2x ⫹ 3y ⱖ 15

2x ⫹ y ⱖ 8

x ⱖ 0, y ⱖ 0

x ⱕ 4

x ⫹ 3y ⱕ 15

2x ⫹ y ⱕ 10

4. Minimize C ⫽ 4x ⫹ y

subject to

5. Sensitivity Analysis Consider the following linear pro-

gramming problem:

Maximize P ⫽ 2x ⫹ 3y

subject to

a. Solve the problem.

b. Find the range of values that the coefficient of x can as-

sume without changing the optimal solution.

c. Find the range of values that resource 1 (requirement 1)

can assume.

d. Find the shadow price for resource 1.

e. Identify the binding and nonbinding constraints.

x ⱖ 0, y ⱖ 0

3x ⫹ 2y ⱕ 24

x ⫹ 2y ⱕ 16

x ⱖ 0, y ⱖ 0

x ⫹ 3y ⱖ 15

2x ⫹ 3y ⱖ 24

2x ⫹ y ⱖ 10

200 3 LINEAR PROGRAMMING: A GEOMETRIC APPROACH

Before Moving On . . .

CHAPTER 3

87533_03_ch3_p155-200 1/30/08 9:48 AM Page 200

How can Acrosonic fill its orders and

at the same time keep its shipping

costs to a minimum? The company

manufactures its loudspeaker

systems in two locations and ships

them to three warehouses that serve

as distribution centers. In Example 5,

page 231, we find the shipping

schedule that minimizes the shipping

costs while meeting the needs of the

distribution centers.

HE GEOMETRIC APPROACH introduced in the previous

chapter may be used to solve linear programming problems

involving two or even three variables. But for linear programming

problems involving more than two variables, an algebraic

approach is preferred. One such technique, the simplex method,

was developed by George Dantzig in the late 1940s and remains

in wide use to this day.

We begin Chapter 4 by developing the simplex method for

solving standard maximization problems. We then see how,

thanks to the principle of duality discovered by the great

mathematician John von Neumann, this method can be used to

solve a restricted class of standard minimization problems.

Finally, we see how the simplex method can be adapted to solve

nonstandard problems—problems that do not belong to the

other aforementioned categories.

LINEAR

PROGRAMMING:

AN ALGEBRAIC

APPROACH

87533_04_ch4_p201-256 1/30/08 9:51 AM Page 201