274 CHAPTER9 Linear Programming Models

B (3,4)

A(7,0)
C=43

5x + 7y = 43
C= 28 5x + 7y = 35
C=21 5x+ 7y = 28
C=14 5x + 7y = 21

5x + 7y = 14
C=0
5x + 7y =7
5x + 7y = 0
FIGURE 9.6

position in the family of lines 5x + 7y =C: It is the line farthest from the origin that
of C: 43.
still passes through the set of feasible solutions. It yields the largest value
(Remember, we are not interested in what happens outside the region OABC.) Thus the
largest value of the function f(x, y) = 5x + 7y subject to the condition that the point
at the
(x, y) must belong to the region 0ABC is 43; clearly this maximum value occurs
point B (3,4).
Consider the polygonal region 0ABC in Figure 9.6. This shaded region has the
property that the line segment PO joining any two points P and in the region lies

FIGURE 9.7
 9,2 LINEAR PROGRAMMING MODELS 275

entirely within the region. Such aset of points in a plane is called a convex set, For
xample,tthe shaded regions in Figure 9,7 are convex, while those in Figure 9,8 are not.
nce the convex set in Figure 9.6 is bounded by the polygon OABC, it is calleda
olygonal convex set.

FIGURE 9.8

the maximum value of the

An interesting observation about Exanple 9.5 is thatpolygonal convex set OABC. the
point of the
objective function ffoccurs at a corner theorem indicates that it was not accidental
noint B(3,4). The following celebrated
THEOREM 9.1 (Fundamental theorem of linear programming)

A linear objective functionf defined over a polygonal convex set

attains a maximum (or minimum) value at a corner point of the set.

Let us return to Example 9.5. Observe that the corner points of the region OABC
are O(0,0),A (7,0), B(3,4), and C(0,2). We evaluate the function f(o,y) = 5x + 7y
at these corner points:
f(O) =f(0,0) = S 0+7-0 =0
f(A) =f(7,0) = 5 7+7-0= 35
fB) =f3,4) =53+ 7-4= 43
f(C) =f(0,2) =5 0+72 = 14
Since 43 is the largest of these four values, the given function takes on the maximum
value 43 for x=3 andy = 4,subject to the given constraints.Consequently (3,4) is
the optimal solution of the problem.
EXAMPLE 9.6 Minimize the function g(x, y) = 13x- 15y subject to the constraints
in Example 9.5.
SOLUTION Since the set of feasible solutions remains the same as that in the above
example, let us now evaluate g(x,y) at the corner points O, 4, B, and C:
g(0) =g(0,0) =13 -0-15 -0 =0
gA) =g(7, 0) = 13 7-15 0 =91
gB) =g(3,4) =133-15 4=-21
g(C) =g(0,2) =13 -0-15 2 =-30
Thus the function g has minimum value -30 at x = 0,y =2.
 Models
276
CHAPTER9 Linear Programming

We now summarize the procedure for solving a linear programming problem.

1. Graph the polygonal region determined by the constraints.

2. Find the coordinates of the corner points of the polygon.
3. Evaluate the objective function at the corner points.
4. Identify the corner point at which the function has an optimal
value.

The following examples are typical linear programming problems of practical

importance. In every case,we shall first construct a mathematical model of the prob.
lem in terms of equations and inequalities; then we shall follow the steps given above.
EXAMPLE 9.7 Amanufacturing company makes two types of television sets: one
is black and white and the other is color. The company has resources to make at most
300 sets a week. It takes $180 to make a black and white set and$270 to make a color
set. The company does not want tospend more than S64,800 a week to make televi
sion sets. If they make a protit of $170 per black and white set and S225 per color
set, how many sets of each type should the company make to have amaximum profit?
soLUTION We first rewrite the problem in terms of mathematical symbols. Let x
denote the number of black and white sets and y. the number of color sets made each
week. Then the total number of sets made each week is x ty. Since the company
cannot make more than 300 sets a week, we have
x ty<300
Clearly, the total weekly cost of manufacturing television sets is 180x+ 270y and the
company does not want to spend more than $64,800 a week. Therefore
180x + 270y <64,800
2x + 3y <720
Also, since, thecompany cannot make a negative number of sets, we have x>0 and
y>0. Thus the problem is to maximize the profit function f(x, y) =170x +225y
subject to the constraints
x>0, y>0
xty<300
2x + 3y <720
Notice that these four linear constraints define the shaded region in Figure 9.9 with
corner points 0, A, B, and C. Evaluating the function f(x,y) at these points, we have
f(O) =f(0,0) = 170 -0+ 225 -0 = S0
f(A) =f(300,0) = 170 300 + 225 -0= $51,000
f(B) =f(180, 120) =170- 180 +225 120 =$57,600
f(C) =f(0, 240) = 170·0 + 225 240 = $54.000
Consequently, the company should make x= 180 black and white sets and y=120
color sets to make a maximum profit of $57,600.
 9.2 LINEAR PROGRAMMING MODELS 277

(0, 240) C
X+y= 30 B (180, 120)

23x +
31y= 720
ol0.0) (300,0) A

FIGURE 9.9

Incidentally, you should consider Example 9.7 if the company wants to make a
profit of $150on every black and white set and $225 on every color set.
EXAMPLE 9.8 Afarmer grows tomatoes and beans on his 125-acre farm. It costs
S20to grow an acre of tomatoes and S1O to grow an acre of beans; however, he has
only $1500 to meet the expenses. It takes 18 man-hours to grow an acre of tomatoes
and 6 man-hours to grow an acre of beans. He has at most 1080 man-hours for the
whole job. If the profits from an acre of tomatoes and an acre of beans are $40 and
$25, respectively, how many acresof each should he grow to maximize his total profit?
What is the maximum possible profit?
SOLUTION Assume that the farmer should grow x acres of tomatoes andy acres of
beans to maximize his profits. Clearly,
X+y< 125 constraint on available land

His total growing expense is

20x +10y <1500 constraint on expense
2x +y < 150
The total number of require dman-hours is
constraint on man-hours
18x + 6y<1080
3x +y< 180
is to maximize the profit function
Notice that x> 0 and y> 0. Thus the problem
px,y) = 40x + 25y
subject to the constraints
X>0,y >0
xty<125
2x +y<150
3x +y< 180
 Models
278
CHAPTER 9 Linear Programming

3x +y= 180

(0, 125) D
C (25, 100)

B(30, 90)

(0,0)
(60,0) A

x+y =125
2* +y = 150

FIGURE 9.10

points O, A, B, C,
These conditions define the shaded region in Figure 9.10 with corner
and D. Let us now evaluate the function p(x, y) at these points:
p(0) =p(0,0) = 40 0+ 250= $0
pA) =p(60,0) = 40 60 + 25 -0 = $2400
pB) =p(30,90) =40- 30 + 25 90 = $3450
p(C) =P(25, 100) = 40 - 25 + 25 100 = $3500
pD) =p(0, 125) =40-0 + 25 125 = $3125
The farmer should thus grow 25 acres of tomatoes and 100 acres of beans to yield a
maximum profit of $3500.

EXAMPLE 9.9 (The diet problemn) A nutritionist in a children's hospital has to

prepare menus for lunch and dinner. One unit of lunch contains 12 units of carbohy
drates, 6 units of protein, and 6 units of vitamin C. One unit of dinner contains 8 units
of carbohydrates, 6 units of protein, and 10 units of vitamin C. The minimum nutri
tional requirements per child are 64 units of carbohydrates, 42 units of protein, and
54 units of vitamin C. If one unit of lunch costs 25¢ and one unit of dinner costs 40¢,
how many units of lunch and dinner should be served to each child to satisfy the
minimum nutritional requirements at a minimum cost?
280 CHAPTER9 Linear Programming Models

EXERCISES 9.2
1. Find the corner points of the regions defined by the
a) x>0, y>0 following inequalities
b) x>0, y>0
2x+y6
c) x>0, y>0 d) x>0,y>0
x+y<S x<6
X-y<3 y<6
2x-yK4 2x + 3y<24
2. Maximize the functionf= 1lx + 7y subject to the constraints in Exercise 1
3. Minimize the function g=13x- 5y subject to the constraints in
Exer cise 1.
4. Minimize each function f subject to the given contraints.
a) f=5x1 +4x, b) f= 5xË + 7x2
X1>0, X)>0 x0, X,>0
X tx >13
x} t 2x;> 20 X} +4x2>20
2x1 tx>20 2x1 + 3*,>30
8x1 + 5x,>80
5. A dietitian in a hospital wishes to design a meal that includes food I
and food II.
The meal should contain at least 48 units of protein and 20 units of iron.
One
unit of food Icontains 8 units of protein and 4 units of iron, while 1 unit of
food II contains 6 units of protein and 2 units of iron. One unit of
food I
40¢ and lunit of food II costs 25 ¢. Let x denote the units of food I and ycosts
denote the units of food II.
a) Find the linear constraints.
b) Find the objective function.
c) Graph the solution set of the inequalities in part a.
d) Find the corner points of the region obtained in part c.
e) Evaluate the objective function at the corner points.
f) How many units of food Iand food II should the meal include to meet the
required nutritional demnands at a minimum cost?
g) What is the minimum cost?
6. A certain company makes two types of sweaters: type A and type B. It
costs $9
to make a type A Sweater and $3 to make a type B sweater. The
make at most 300 sweaters and spend at most $1800 a day. The number companyofcan
Sweaters of type B cannot exceed the number of sweaters of type A by more than
100. The company makes a profit of $5 for every sweater of type
A and $3 for
every sweater of type B.
a) Find the linear constraints.
b) Find the corner points of the region defined by the
c) What is the objective function? constraints in part a.
d) How many sweaters of each type should the
a maximum profit? company make a day to yield
e) What is the maximum
profit?
7. Paul wants to invest part of his $4000 in
a business
savings bank that pays 6% interest annually. Since and deposit the rest at a
riskier, he does not want to invest more than three investing in the business is
times what he would deposit
in the bank, He wants to make a profit of
15% from his business investment. How
should he divide his money to make a
return? maximum total income? What is the total
 9.2 LINEAR PROGRAMMING MODELS 20

)TION Letx denote the number of units of lunch andy the number of units
of dinner. The problenm now is to minimize the cost function f(*, y) 25x +40y
subject to the constraints
x>0,)>0
12r + 8y> 64 carbohydrate constraint
6r t6p 42 protein constraint
6r + 10 >54 vitamin C constraint
constraints can be rewritten as
The last three

xty>7
}r+ Sp >27
Vou shouldverify that Figure 9|l is the graph of these inequalities. We evaluate the
obtain
cOst function at the corner points and
fA) =f(9,0)= 259+ 40 0= $2.25
fB) =f(4,3) = 25 -4 +40 3 =$2.20
f(C) =f(2,5)= 25 2 + 40 5 = $2.50
fD) =f(0,8)= 25 0+40-8 = $3.20

D (0, 8)

C(2, 5)

B(4,3)

3x +
5y =27
X+y =7 A (9,0)

3x + 2y = 16

FIGURE 9.11
minimum nutritional
Clearly, 4 units of lunch and 3 units of dinner will meet the
requirements for each child; the minimum cost will be $2.20.
zH0 CAPTER OLinear Programming MMooets

EXERCISES 9.2

1 Find the corner paints of the tegiots efined by the following inequalities
a) 2D, y>0 b) x>0,y>0
S3

Zr+ 3y <24
2. Maximize the function f 1lx + 7y subject to the constraints in Exercise 1
1 Minimire the function g=|3r Sy subject to the constraints in Exercse
4. Minimize cach function f subject to the given conttaints.
alSx4r b) f5x, +7x
20, x0 X20, kg20
K4230
2x+>20
Sr5Y,280
S. Adietitian in a hospital wishes to desugn a meal that incudes food Land food I
The meal ahould contain at least 48 units of protein and 20 units of iton. One
food ll contains 6units of proten nd 2 unitsof ton. One unit of foot Lcosts
404 and unit of food Il costs 25¢ Letx denote the units of food [anda
denote the units of food li.

)Gaph the solution set of the inequalities in part a

d) Find the cotnet ponth of the regioontainca n patt e
) How many units of food Tand food Il hould the meal include to meet the
requited iitritional demands at a mininüm cost?
g Whut is the inimun cost

6 Acerta copany kesoyotzaeute ype d an ype cort S9

makeat ot 300 sweaters and spend at mot 51800 a day. The number of
sweatets of type B eännot exceed the nmber of sweaters of type A by more than
et omo 3to eery weater of type Aand S3 for
a) Find the linear costratnts
Wh me region defined by the constraints in nart

d) How mnywcaters of each type should the company make a day to yield
profit
Paul want
savis hunk that vM iiterrtanialu h
tskiet, he does ot wänt to itvest more than three times what he would depasit

aum totalincomeT What ithe total

return?
 9,3 THE SIMPLEX ALGORITHM 281
and Omega Company
8. The Alpha manager wants to makes two types of
The production
company make at least 600 batteries,
type Aand type B,
800 a week. The does not have
enough batteries, but not more than
500 batteries of type A or
700 resources
batteries of type Ba week. toAboutmake8% more than
batteries and 5% of type Bbatteries are of type A
batteries of each type should be damaged during production, How
to minimize the
number of
damagedmanufactured per week if the
Company
many
wants
batteries and still wants to make at least 100
batteries of type A per week?
transportation problem) An oil
9. (A
location A and 60,000 gallons of company has 30,000 gallons of gasoline at
gasoline at location B.
ae
to be transported to soston and
50,000 to New York.TwentyIt coststhousand
4¢ and 5¢gallons
transport from l cation A to Boston and New York, a
gts and 6¢ a gallon to transport from location B to theserespectively, while
3d
roenectively. How shouid gasoline be distributed to minimize thetwo
costcities,
of trans
portation? What is the minimum cost)
The AAA Calculator Company makes three models of calculators, model A.
dl Rand model C, at factory I and factory II. The company has orders for
t 6400 model A calculators, 4000 model B calculators, and 4800 model C
calculators. At factory I, 50 model 4, 50 model B, and 30 model Ccalculators
are made every day; at factory I, 40 model A, 20 model B, and 40 model C
calculators are manufactured every day. Each day, it costs S12,000 and $15,000
to operate factory I and factory II,respectively. Find the number of days each
factory should operate to minimize the operating costs and still meet the con
sumer demands,

11 Solve Example 9.8 if the farmer has a profit of $50 from an acre of tomatoes
and $20 from an acre of beans,
1) Aretired carpenter makes hi-fi cabinets and bookcases to supplement his social
security income. He can work, at most, 36 hours a week. A hi-fi cabinet requires
4hours of hand work, including 2 hours on saws and 1 hour on drill and sander:
a bookcase requires 3 hours of hand work, including 1 hour on saws and1hour
on drill and sander. Since the carpenter's son is also using the tools, the carpenter
cannot use his saws for more than 16 hours a week, and his drill and sander forfor
more than 11 hours a week. If he sells a hi-fi cabinet for $70 and a bookcase
What is
$40, how many of each kind should he make to maximize his revenue?
his maximum possible income from sales?

9.3 THE SIMPLEX ALGORITHM

objective function and the linear constraints in the problems we discussed in the
The
two unknowns. Butmany real-world problems
preceding section contained only Unfortunately, the graphical method is not very
involve more than two variables.
variables, it is very time-consuming to find
nelptul in those cases: if there are threesolutions and then to evaluate the objective
feasible
he corner points of the set of the optimal solution. If the problem
Tunctions at these points in order to identify it is impossible to find the feasible solutions
three unknowns. then
contains more than
 282 CHAPTER 9 Linear Programming Models

by grouning. Therefore, in this section we Shall llustrate a systematic

the simplex algorithm for solving linear programming procedure called
ions are to be maximized. This method was developed by problems where objective fus
Dantzig in 1947 when he
was working for the United States Air Force and makes use of the
operations discuSsed in Section 8.3 elementary row
Since 3 <5, there is a number x> 0 such that 3 + x= 5,
generally, let a and b be any two numbers; then a <b if and namelyx =2. More
only we can find a
if
number x>0such that a tx=b.The simplex method employs this simple fact
Warning : All the constraints inequalities, except the conditions that variables be non.
negative, must be stated in terms <.

EXAMPLE 9.10 Let us consider the problem of maximizing the function f= 5x + 3y

subject to the constraints
x>0, y>0
xty<7
3x +y <1S
Using the property discussed above, the last two inequalities can be converted to
equalities by introducing two new variables s 0and s>0:
x+y +Sj =7
3x +y + S, = 15
These two variables, S; and s;, are called slack variables. Notice that the equation
f= 5x + 3y can be written as -5x-3y +f= 0. We now have
xty +Sj =7
3x +y+ s, = 15
Sx-3y +f= 0
This system can be rewritten as
xt y+ Si =7
3x + y + S2 = 15
-5x -3y +f= 0

By taking the coefficients and the constant terms, we can form the matrix
slack variables

S S

1 1 1 0 0 7
3 1 1 15
-3 0 1 0

indica tors
This matrix is the augmented matrix of the system. It is called the initial simplex
tableau. The entries of its last row, except the last entry 0, are called indicators. In our
remaining discussion we shall, for convenience, omit the parentheses of all tableaux.
 9,3 THE SIMPLEX ALGORITHM 283

E9.11
EXAMPLE Set up tthe initial
simplex
functionJ , ) = 170x + 225y subject to thetableau for Example 9,7:
constraints maximize the
x>0, y>0
xty<300
2x +3y <720
sOLUTION By introducing two slack
inequalities can be written
as variables S,>0 and s,>0,the last two
xty +s, = 300
2x + 3y t s = 720
Ve now have the system of equations
xt yt si =300
2x+ 3y + S2 = 720
-170x - 225y +f=0

Accordingly, the initial simplex tableau is

S1 S2 f
1 1 0 300
0 1 0 720
-170 -225 0 0 10

Let us now return to the initial tableau in Example 9.10.

S1 S
1 1
3 1 1 0 15

-5-3 0 0 0
The snallest negative indicator of this tableau is -5; the column that contains the
smallest negative indicator is called the pivotal column. Divide each positive number
of the pivotal column into the corresponding entry of the last coluimn. In this case,
we have 7÷1=7and 15 3 =5. The row that yields the smallest of these quotients,
namely 5, is called the pivotal row. The number that belongs to the pivotal column
and pivotal row has a central position in the simplex method; accordingly, it is called
the pivot. In our above tableau, the pivot is 3. It is circled in Table 9.1.

TABLE 9,1
yS1 S
1 1 1 0 7
1 0 0 1 15 pivotal row
-5 -30 0 1 0
-pivotal column
 284 CHAPTER 9 Linear Programming Models

EXAMPLE 9.12 Locate the pivot of the tableau in Example 9.11.

SOLUTION Since the
smallest negative indicator in this tableau is
column is the second column, headed by y. When we divide each -225, the pivotal
this column into the positive number of
300 1= 300 and 720corresponding entry of the last column, we get
3 = 240, of which 24O is the quotients
second row is the pivotal row. Consequently, the clearly the smallest. Hence the
second column is the pivot, as shown in Table 9.2. number 3 in the second row and

TABLE 9.2

1 1 1 0 300
2 (3) 0 1 0 720 pivotal row
-170 -225 0 0 1 0
-pivotal column
Thus far, we have illustrated the first two of the following steps in the simplex
method:
STEP 1 Set up the initial simplex tableau.
STEP 2 Locate the pivot p of the tableau.
STEP 3 If the pivot p is 1, then go to Step 4; otherwise, divide the pivotal row
by p to give 1 in the pivotal position.
STEP 4 Convert the remaining entries of the pivotal column into zeros by using
the elementary row operations discussed in Section 8.2.
STEP 5 Repeat Steps 2-4 until a tableau with nonnegative indicators is obtained.
This is the final tableau we need in this algorithm; it is called the terminal simplex
tableau.
STEP 6 The optimal solution and the maximum value of the objective function
can be read from this terminal tableau.

Let us now illustrate Steps 3-6 for the problem in Example 9.10. The initial tableau,
shown in Table 9.1, is
Sj
1 1 1 7
1 1 0 15 pivotal row
-5 -3 0 0 1
-pivotal column
To change the pivot 3 to 1, we divide the pivotal row by 3. This yields the tableau
S
1 1 0 7
00
-5 -3 0 0 1 |0
 9.3 THE SIMPLEX ALGORITHM 285
the other two entries of the pivotal
To make column zero, we add -1
and 5 times the
rowtothe first row second row to the third row. The times the second
now becomes above tableau
S1 S2

2 -pivo tal row

1 0
1 0 5
0 25
pivotal column

Sincethe second indicator is still negative, we look for the pivot of this tableau, which
is clearly $. Therefore we divide the first row by to get 1in the pivot; use this new
pivot I to transform the other entries of the pivotal column into zeros. You should
check that the resulting tableau is
S1 S) f
1 0 3
1 0 4

0 0 2 1 29 maximum value
This is clearly the terminal tableau.
How do we now read the optimal solution and the maximum alue of the function
irom this tableau? This tableau is the augmented matrix of the system
=3

1
X =4

2s t S tf= 29
This can be rewritten as

1 1
x=4t ,s; ,52
3 1
y=3-,5; z'2
f= 29-2s, - S2
the maximum value 29 when s, =0 and
It is clear from the last equation that fattains
s, =0=s, we have x=4 and y=3.
S =0. (Remember, S, >0 and s, >0.)When
value 29 when x = 4 and y =3. You should
Thus the function f takes on the maximum
verify this by graphing.