9781118041581

Linear Programs 715

A Minimization Problem

The production problem the PC company faces is typical of a large class of

profit-maximization problems. A second important class of decisions involves

cost minimization. The next example illustrates the point.

REGULATION AT LEAST COST An environmental regulatory agency is

launching a program to reduce water pollution in one of the region’s major

rivers. As a first step, it has set standards for two key measures of water quality.

It seeks (1) to increase the level of dissolved oxygen (essential to fish and other

life in the estuary) by 6 milligrams (mg) per liter and (2) to reduce the con-

centrations of chlorides by 70 mg per liter. Its aim is to meet both these stan-

dards at minimum cost by allocating funds between two programs.

Program 1: Direct treatment of effluents. Each $1 million spent in this

program will increase dissolved oxygen by 3 mg/liter and reduce

chlorides by 10 mg/liter.

Program 2: Flow regulation. Each $1 million spent in this program will

increase dissolved oxygen by 1 mg/liter and reduce chlorides by 20

mg/liter.

How much should the agency spend on one or both programs to meet its goals?

Let’s formulate and solve the agency’s problem. As always, we begin by

identifying the decision variables. Here, the agency must choose how much to

spend on direct treatment and how much to spend on flow regulation. We label

the spending (in millions of dollars) on the respective programs by D and F.

The agency seeks to minimize the total cost (C) of the programs, subject to

meeting its goals.

. [OF]

The goals it must meet can be expressed by the following inequalities.

[O]

10D20F 70. [C]

Subject to: 3DF 6

Minimize: CDF

CHECK

STATION 1

A farmer raises two crops, wheat and barley. Wheat sells at $1.60 per bushel and bar-

ley at $1.00 per bushel. The production of each crop requires land and labor in dif-

fering amounts. Each 1,000 bushels of wheat requires one acre of farmland and

4 labor-hours per week. An equal quantity of barley also requires 1 acre but requires

only 2 hours of labor per week. The farmer has 10 acres of land and an average of

32 hours of labor per week to devote to wheat and barley production. How much of

each crop should the farmer produce? In your answer, formulate and graph the appro-

priate LP problem.

c17LinearProgramming.qxd 9/26/11 11:05 AM Page 715