Linear Programming Solver PDF

9 Linear
Programming
9.1 Systems of Linear Inequalities
9.2 Linear Programming Involving Two Variables
9.3 The Simplex Method: Maximization
9.4 The Simplex Method: Minimization
9.5 The Simplex Method: Mixed Constraints
Product Advertising (p. 483)
Minimizing Steel Waste (p. 477)
Optimization Software (p. 461)
Restocking ATMs (p. 453)
Target Heart Rate (p. 446)
Clockwise from top left, Dmitrijs Dmitrijevs/Shutterstock.com; Gerald Bernard/Shutterstock.com;

Marquis/Shutterstock.com; wavebreakmedia ltd/Shutterstock.com; Grigoryeva Liubov Dmitrievna/Shutterstock.com
441
9781305658004_0901.indd 441 12/3/15 1:57 PM

442 Chapter 9 Linear Programming
9.1 Systems of Linear Inequalities

Sketch the graph of a linear inequality.
Sketch the graph of a system of linear inequalities.
Linear Inequalities and Their Graphs

The statements below are inequalities in two variables:
3x − 2y < 6 and x + y ≥ 6.
An ordered pair (a, b) is a solution of an inequality in x and y if the inequality is true
when a and b are substituted for x and y, respectively. For example, (1, 1) is a solution
of the inequality 3x − 2y < 6 because
3(1) − 2(1) = 1 < 6.
The graph of an inequality is the collection of all solutions of the inequality. To sketch
the graph of an inequality such as
3x − 2y < 6
begin by sketching the graph of the corresponding equation
3x − 2y = 6.
The graph of the equation separates the plane into two regions. In each region, one of
the following two statements listed below must be true.
1. All points in the region are solutions of the inequality.
2. No point in the region is a solution of the inequality.
So, you can determine whether the points in an entire region satisfy the inequality by
simply testing one point in the region.
REMARK Sketching the Graph of an Inequality in Two Variables

When possible, use test
points that are convenient to 1. Replace the inequality sign with an equal sign, and sketch the graph of
substitute into the inequality, the resulting equation. (Use a dashed line for < or > and a solid line for
such as (0, 0). ≤ or ≥.)
2. Test one point in each of the regions formed by the graph in Step 1. If the
point satisfies the inequality, then shade the entire region to denote that
every point in the region satisfies the inequality.
In this section, you will work with linear inequalities of the forms listed below.
ax + by < c
ax + by ≤ c
ax + by > c
ax + by ≥ c
The graph of each of these linear inequalities is a half-plane lying on one side of the
line ax + by = c. When the line is dashed, the points on the line are not solutions
of the inequality; when the line is solid, the points on the line are solutions of the
inequality. The simplest linear inequalities are those corresponding to horizontal or
vertical lines, as shown in Example 1 on the next page.
9781305658004_0901.indd 442 12/3/15 1:57 PM

9.1 Systems of Linear Inequalities 443
Sketching the Graph of a Linear Inequality

Sketch the graph of each linear inequality.
a. x > −2
b. y ≤ 3
solution
a. The graph of the corresponding equation x = −2 is a vertical line. The points that
satisfy the inequality x > −2 are those lying to the right of this line, as shown in
Figure 9.1(a).
b. The graph of the corresponding equation y = 3 is a horizontal line. The points that
satisfy the inequality y ≤ 3 are those lying below (or on) this line, as shown in
Figure 9.1(b).
a. b. y
x = −2 y
3
2 y=3
2
1
1
x
x −3 −2 −1 1 2 3
−3 −1 1 2 3
−2
−2
−3
−3
Figure 9.1
Sketching the Graph of a Linear Inequality
Sketch the graph of x − y < 2.

solution
The graph of the corresponding equation x − y = 2 is a line, as shown below. The
origin (0, 0) satisfies the inequality, so the graph consists of the half-plane lying above
the line. (Check a point below the line to see that it does not satisfy the inequality.)
y
1
(0, 0)
x
−3 −2 −1 1 2 3
−2
x− y=2
−3

For a linear inequality in two variables, you can sometimes simplify the graphing
procedure by writing the inequality in slope-intercept form. For example, by writing
x − y < 2 in the form
y > x−2
you can see that the solution points lie above the line y = x − 2.
9781305658004_0901.indd 443 12/3/15 1:57 PM

y
Systems of Inequalities
12 Many practical problems in business, science, and engineering involve systems of
x + y ≤ 12
3x − 4y ≤ 15
linear inequalities. An example of such a system is shown below.
9
x≥0 x+y ≤ 12
y≥0
6 3x − 4y ≤ 15
(2, 4)
x ≥ 0
3 y≥ 0
x A solution of a system of inequalities in x and y is a point (x, y) that satisfies each

6 9 12 inequality in the system. For example, (2, 4) is a solution of the above system because
(2, 4) is a solution because it x = 2 and y = 4 satisfy each of the four inequalities in the system. The graph of a
satisfies the system of inequalities. system of inequalities in two variables is the collection of all points that are solutions of
Figure 9.2 the system. For example, the graph of the above system is the region shown in Figure
9.2. Note that the point (2, 4) lies in the shaded region because it is a solution of the
system of inequalities.
To sketch the graph of a system of inequalities in two variables, first sketch the
graph of each individual inequality (on the same coordinate system) and then find the
region that is common to every graph in the system. This region represents the solution
set of the system. For systems of linear inequalities, it is helpful to find the vertices of
the solution region, as shown in Example 3.
Solving a System of Inequalities
Sketch the graph (and label the vertices) of the solution set of the system shown below.
x−y < 2
x > −2
y ≤ 3
solution
You have already sketched the graph of each of these inequalities in Examples 1 and 2.
The region common to all three graphs can be found by superimposing the graphs on
the same coordinate plane, as shown below. To find the vertices of the region, find the
points of intersection of the boundaries of the region.
Vertex A: (−2, −4) Vertex B: (5, 3) Vertex C: (−2, 3)
Obtained by finding Obtained by finding Obtained by finding
the point of the point of the point of
intersection of intersection of intersection of
x−y= 2 x−y=2 x = −2

x = −2. y = 3. y = 3.
y y
x−y<2 6 6
x > −2
4 C(−2, 3) B(5, 3)
2 2
x x
−4 2 4 6 8 −6 −4 2 4 6
−2 −2
−4
A(−2, −4)
−6 −6
y≤3

9781305658004_0901.indd 444 12/3/15 1:57 PM

9.1 Systems of Linear Inequalities 445
For the triangular region shown in Example 3, y

(Not a vertex)
each point of intersection of a pair of boundary lines
corresponds to a vertex. With more complicated
regions, two border lines can sometimes intersect
at a point that is not a vertex of the region, as
shown at the right. To determine which points x
of intersection are actually vertices of the region,
sketch the region and refer to your sketch as
you find each point of intersection.
When solving a system of inequalities, be
aware that the system might have no solution.
Border lines can intersect
For example, the system at a point that is not a vertex.
x+y > 3
x + y < −1
has no solution points because the quantity (x + y) cannot be both less than −1 and
greater than 3, as shown below.
1
x+y>3
x
−1 1 2 3
x + y < −1
No Solution
Another possibility is that the solution set of a system of inequalities can be

unbounded. For example, consider the system below.
x+ y < 3
x + 2y > 3
The graph of the inequality x + y < 3 is the half-plane that lies below the line
x + y = 3. The graph of the inequality x + 2y > 3 is the half-plane that lies above
the line x + 2y = 3. The intersection of these two half-planes is an infinite wedge
that has a vertex at (3, 0), as shown below. This unbounded region represents the
solution set.
3
x+y=3
2
x + 2y = 3 1
(3, 0)
x
−1 1 2 3
Unbounded Region
9781305658004_0901.indd 445 12/3/15 1:57 PM

Example 4 shows how a system of linear inequalities can arise in an applied

problem.
An Application of a System of Inequalities
See LarsonLinearAlgebra.com for an interactive version of this type of example.
The liquid portion of a diet is to provide at least 300 calories, 36 units of vitamin A,
and 90 units of vitamin C daily. A cup of dietary drink X provides 60 calories, 12 units
of vitamin A, and 10 units of vitamin C. A cup of dietary drink Y provides 60 calories,
6 units of vitamin A, and 30 units of vitamin C. Set up a system of linear inequalities
that describes the minimum daily requirements for calories and vitamins.
solution
Let
x = number of cups of dietary drink X and
y = number of cups of dietary drink Y.
To meet the minimum daily requirements, the inequalities listed below must be satisfied.
For calories: 60x + 60y ≥ 300
REMARK For vitamin A: 12x + 6y ≥ 36
Any point inside the shaded For vitamin C: 10x + 30y ≥ 90
region (or on its boundary) x ≥ 0
meets the minimum daily
requirements for calories and
y ≥ 0
vitamins. For example, 3 cups The last two inequalities are included y
of dietary drink X and 2 cups because x and y cannot be negative.
of dietary drink Y supply The graph of this system of linear 10
300 calories, 48 units of
inequalities is shown at the right. 8
vitamin A, and 90 units of
vitamin C. (0, 6)
6
(1, 4)
4
(3, 2)
2
(9, 0)
x
2 4 6 8 10
A heart rate monitor watch is designed to ensure that a

Linear person exercises at a healthy pace. It displays transmissions
Algebra from a chest strap that monitors the person’s pulse
Applied electronically. Researchers have identified target heart
rate ranges, or zones, for achieving specific results
from exercise. Fitness
Exercise Target Zone Chart
facilities and cardiology
treadmill rooms often
Ana
display wall charts, such erob
Heart rate (bpm)
ic /H
as the one shown at the igh
Inte
nsit
right, to help determine y
Targ
whether a person’s e t He
art R
ate
exercise heart rate is in a
healthy range. In Exercise Fat Bu
rning
60, you are asked to write Warm-Up/Co
ol Down
a system of inequalities for
a person’s target heart Age (years)
rates during exercise.
Daxiao Productions/Shutterstock.com
9781305658004_0901.indd 446 12/3/15 1:57 PM

9.1 Exercises 447
9.1 Exercises
Identifying the Graph of a Linear Inequality In Solving a System of Inequalities In Exercises 29–32,
Exercises 1– 6, match the linear inequality with its determine whether each ordered pair is a solution of the
graph. [The graphs are labeled (a)–(f).] system of linear inequalities.
1. x > 3 2. y ≤ 2 29. x ≥ −4 30. −2x + 5y ≥ 3
3. 2x + 3y ≤ 6 4. 2x − y ≥ −2 y > −3 y < 4
y y ≤ −8x − 3 −4x − 2y < 7
5. x ≥ 6. y > 3x (a) (0, 0) (a) (0, 2)
2
(b) (−1, −3) (b) (−6, 4)
(a) y (b) y
(c) (−4, 0) (c) (−8, −2)
2
(d) (−3, 11) (d) (−3, 2)
1
1 31. x ≥ 1 32. x ≥ 0
x
−2 −1 1 2
y ≥ 0 y ≥ 0
x
1 2 3 y ≤ 2x + 1 y ≤ 4x − 2
−2 (a) (0, 1) (a) (0, −2)
(1, 3) (b)
(b) (2, 0)
(c) y (d) y (2, 2) (c)
(c) (3, 1)
4 (2, 1) (d)
(d) (0, −1)
2
3
Solving a System of Inequalities In Exercises 33–48,
1 sketch the graph (and label any vertices) of the solution
1 set of the system of linear inequalities.
x
x
−2 33. x ≥ 0 34. x ≥ −1
−2 −1 1 2
y ≥ 0 y ≥ −1
(e) y (f ) y x ≤ 2 x ≤ 1
2 y ≤ 4 y ≤ 2
2
1
35. x + y ≤ 1 36. 3x + 2y < 6
1
−x + y ≤ 1 x > 0
x x
−2 −1 1 2 1 2 4
y ≥ 0 y > 0
−1 37. x + y ≤ 5 38. 2x + y ≥ 2
−2 −2 x ≥ 2 x ≤ 2
y ≥ 0 y ≤ 1
Sketching the Graph of a Linear Inequality In 39. −3x + 2y < 6 40. x − 7y > −36
Exercises 7–28, sketch the graph of the linear inequality.
x + 4y > −2 5x + 10y > 20
7. x ≥ 2 8. x ≤ 4 2x + y < 3 6x − 5y > 6
9. y ≤ 7 10. y ≥ −1 41. x ≥ 1 42. x + y < 10
11. y < 2 − x 12. y > 2x − 4 x − 2y ≤ 3 2x + y > 10

13. 2y − x ≥ 4 14. 5x + 3y ≥ −15 3x + 2y ≥ 9 x−y > 2
15. y ≤ x 16. 3x > y x+y ≤ 6
17. y ≥ 4 − 2x 18. y ≤ 3 + x 43. −3x + 2y < 6 44. −x + 3y ≤ 12
19. 3y + 4 ≥ x 20. 6 − 2y < x x − 4y > −2 5x + 2y > 5
x + 4y < 4 x − 3y < −3
21. 4x − 2y ≤ 12 22. y + 3x > 6
45. 2x + y > 2 46. x − 2y < −6
23. 5x − 2y > 10 24. 2x + 7y ≤ 28
6x + 3y < 2 5x − 3y > −9
25. y + 13 x ≥ 6 26. y − 12 x < 12
47. 3x − 6y ≤ 5 48. 12x + 15y ≥ 60
x y x y
27. + < 1 28. − ≥ 1 x − 2y ≥ −3 y ≤ − 45x + 4
3 2 6 5
9781305658004_0901.indd 447 12/3/15 1:57 PM

Writing a System of Inequalities In Exercises 49–52, 61. Furniture Production A furniture company produces
write a system of inequalities that describes the region. tables and chairs. Each table requires 1 hour in the
49. y 50. y assembly center and 113 hours in the finishing center.
4 6 Each chair requires 112 hours in the assembly center and
4 112 hours in the finishing center. The assembly center is
3
available 12 hours per day, and the finishing center is
2 2
available 15 hours per day. Let x and y be the numbers of
x
1
4 6
tables and chairs produced per day, respectively. Write
1
x −2 a system of inequalities describing all possible
1 2 3 4 production levels, and sketch the graph of the system.
51. y 52. y 62. Tablet Inventory A store sells two models of
tablet computers. Due to demand levels, it is necessary
8
8 to stock at least twice as many units of the Pro Series
6
6 as units of the Deluxe Series. The costs to the store of
4
4 the two models are $200 and $300, respectively.
2
2
The management does not want more than $5000 in
x
2 4 6 8 laptop inventory at any one time, and it wants at least
x −2
−2 2 4 6 four Pro Series models and two Deluxe Series models
in inventory at all times. Write a system of inequalities
Writing a System of Inequalities In Exercises 53–58, describing all possible inventory levels, and sketch the
write a system of inequalities that describes the region. graph of the system.
53. Rectangle with vertices at (2, 1), (5, 1), (5, 7), and (2, 7) 63. Diet Supplement A dietitian prescribes a special
54. Rectangle with vertices at (1, 3), (3, 1), (4, 6), and (6, 4) dietary supplement using two different foods. Each ounce
of food X contains 20 units of calcium, 15 units of iron,
55. Parallelogram with vertices at (−6, −2), (1, 8), (6, 5),
and 10 units of vitamin B. Each ounce of food Y contains
and (−1, −5)
10 units of calcium, 10 units of iron, and 20 units of
56. Parallelogram with vertices at (0, 0), (4, 0), (1, 4), and vitamin B. The minimum daily requirements for the diet
(5, 4) are 300 units of calcium, 150 units of iron, and 200 units
57. Triangle with vertices at (0, 0), (5, 0), and (2, 3) of vitamin B. Write a system of inequalities describing
58. Triangle with vertices at (−1, 0), (1, 0), and (0, 1) the different amounts of food X and food Y that the
dietitian can prescribe. Sketch the graph of the system.
59. Investment A person plans to invest no more than 64. Rework Exercise 63 using minimum daily requirements
$20,000 in two different interest-bearing accounts. Each of 280 units of calcium, 160 units of iron, and 180 units
account is to contain at least $5000. Moreover, one of vitamin B.
account should have at least twice the amount that is
65. Reasoning Consider the inequality 8x − 2y < 5.
in the other account. Write a system of inequalities
Without graphing, determine whether the solution
describing the various amounts that can be deposited in
points lie in the half-plane above or below the boundary
each account, and sketch the graph of the system.
line. Explain.
60. Target Heart Rate One formula for a person’s
maximum heart rate is 220 − x, where x is the person’s
age in years for 20 ≤ x ≤ 70. When a person 66. C APSTONE Consider the system of
exercises, it is recommended that the person strive for inequalities
a heart rate that is at least 50% of the maximum and ax + by ≤ c
at most 85% of the maximum. (Source: American Heart x ≥ d
Association) y > e
(a) Write a system of inequalities that describes the region where a > 0 and b > 0. Find values of a, b, c, d,
corresponding to these heart rate recommendations. and e such that (a) the origin is a solution of the
(b) Sketch a graph of the region in part (a). system and (b) the origin is not a solution of the
(c) Find two solutions of the system and interpret their system.
meanings in the context of the problem.
67. Changing the Inequality Symbol Sketch the graph
of x + 2y < 6. Then describe how the graph of each
inequality is different from your graph.
(a) x + 2y ≤ 6 (b) x + 2y > 6
9781305658004_0901.indd 448 12/3/15 1:57 PM

9.2 Linear Programming Involving Two Variables 449
9.2 Linear Programming Involving Two Variables

Find a maximum or minimum of an objective function subject to a
system of constraints.
Find an optimal solution to a real-world linear programming problem.
Solving a Linear Programming Problem

Many applications in business and economics involve a process called optimization,
which is used to find such quantities as minimum cost, maximum profit, and minimum
use of resources. In this section, you will study an optimization strategy called linear
y programming.
A two-dimensional linear programming problem consists of a linear objective
function and a system of linear inequalities called constraints. The objective function
gives the quantity that is to be maximized (or minimized), and the constraints determine
the set of feasible solutions.
Feasible
solutions
For the function
z = ax + by Objective function
subject to the set of constraints that determines the region in Figure 9.3, every point in
the region satisfies each constraint. So, it is not clear how to go about finding the point
x
that yields a maximum or minimum value of z. Fortunately, it can be shown that when
there is an optimal solution, it must occur at one of the vertices of the region. This
Figure 9.3 means that you can find the optimal value by testing z at each of the vertices.
THEOREM 9.1 Optimal Solution of a Linear

Programming Problem
If a linear programming problem has an optimal solution, then it must occur
at a vertex of the set of feasible solutions. If the problem has more than one
optimal solution, then at least one of them must occur at a vertex of the set of
feasible solutions. In either case, the value of the objective function is unique.
A linear programming problem can include hundreds, and sometimes even

thousands, of variables. However, in this section, you will solve linear programming
problems that involve only two variables. The graphical method for solving a linear
programming problem in two variables is outlined below.
Graphical Method for Solving a Linear Programming Problem

To solve a linear programming problem involving two variables by the graphical
method, use the steps listed below.
1. Sketch the region corresponding to the system of constraints. (The points
inside or on the boundary of the region are feasible solutions.)
2. Find the vertices of the region.
3. Test the objective function at each of the vertices and select the values of
the variables that optimize the objective function. For a bounded region,
both a minimum and maximum value will exist. (For an unbounded region,
if an optimal solution exists, then it will occur at a vertex.)
9781305658004_0902.indd 449 12/3/15 1:58 PM


Find the maximum value of
z = 3x + 2y Objective function
subject to the constraints listed below.

x ≥ 0
y ≥ 0
Constraints
x + 2y ≤ 4
x− y ≤ 1
solution
y The constraints form the region shown in Figure 9.4. At the four vertices of this region,
the objective function has the values listed below.
4
At (0, 0): z = 3(0) + 2(0) = 0
3 At (1, 0): z = 3(1) + 2(0) = 3
x + 2y = 4
(0, 2) At (2, 1): z = 3(2) + 2(1) = 8 (Maximum value of z)
x=0 At (0, 2): z = 3(0) + 2(2) = 4

(2, 1)
1 So, the maximum value of z is 8, and this occurs when x = 2 and y = 1.
x−y=1
x In Example 1, test some of the interior points of the region. You will see that the
(0, 0) (1, 0) 2 3
corresponding values of z are less than 8. Here are some examples.
y=0
At (1, 1): z = 3(1) + 2(1) = 5
Figure 9.4 At (1, 12 ): z = 3(1) + 2(12 ) = 4
At (32, 1): z = 3(32 ) + 2(1) = 13
2
To see why the maximum value of the objective function in Example 1 must occur
at a vertex, write the objective function in the form
3 z
y=− x+ .
2 2
This equation represents a family of lines, each of slope −32. Of these infinitely many
lines, you want the one that has the largest z-value, while still intersecting the region
determined by the constraints. In other words, of all the lines whose slope is −32,
you want the one that has the largest y-intercept and intersects the specified region, as
shown below. Such a line will pass through one (or more) of the vertices of the region.
3 z
3 y=− x+
2 2
x
1 2
z=
z=
z=
z=
2
4
6
8
9781305658004_0902.indd 450 12/3/15 1:58 PM

The graphical method for solving a linear programming problem works whether the
objective function is to be maximized or minimized. The steps used are precisely the
same in either case. After you have evaluated the objective function at the vertices of
the set of feasible solutions, simply choose the largest value as the maximum and the
smallest value as the minimum. For instance, the same test used in Example 1 to find
the maximum value of z can be used to conclude that the minimum value of z is 0, and
that this occurs at the vertex (0, 0).
Find the maximum value of the objective function

where x ≥ 0 and y ≥ 0, subject to the constraints
− x + y ≤ 11
x + y ≤ 27 Constraints
2x + 5y ≤ 90.
y solution
−x + y = 11
25 The region bounded by the constraints is shown in Figure 9.5. By testing the objective
2x + 5y = 90 function at each vertex, you obtain
20
(5, 16)
At (0, 0): z = 4(0) + 6(0) = 0
15 (15, 12)
At (0, 11): z = 4(0) + 6(11) = 66
10 (0, 11) x + y = 27
At (5, 16): z = 4(5) + 6(16) = 116 (Maximum value of z)
5
(0, 0) (27, 0) At (15, 12): z = 4(15) + 6(12) = 132
x
5 10 15 20 25 30 At (27, 0): z = 4(27) + 6(0) = 108.
Figure 9.5 So, the maximum value of z is 132, and this occurs when x = 15 and y = 12.
Minimizing an Objective Function
Find the minimum value of the objective function

where x ≥ 0 and y ≥ 0, subject to the constraints

2x + 3y ≥ 6
3x − y ≤ 15
Constraints
−x + y ≤ 4
2x + 5y ≤ 27.
solution
y
The region bounded by the constraints is shown in Figure 9.6. By testing the objective
(1, 5)
5 function at each vertex, you obtain
4 At (0, 2): z = 5(0) + 7(2) = 14 (Minimum value of z)
(0, 4) (6, 3)
3 At (0, 4): z = 5(0) + 7(4) = 28
(0, 2) At (1, 5): z = 5(1) + 7(5) = 40
2
1
At (6, 3): z = 5(6) + 7(3) = 51
x
At (5, 0): z = 5(5) + 7(0) = 25
1 2 (3, 0) 4 (5, 0) 6 At (3, 0): z = 5(3) + 7(0) = 15.
Figure 9.6 So, the minimum value of z is 14, and this occurs when x = 0 and y = 2.
9781305658004_0902.indd 451 12/3/15 1:58 PM

y When solving a linear programming problem, it is possible that the maximum (or
(0, 4) (2, 4) minimum) value occurs at two different vertices. For example, at the vertices of the
4
region shown in Figure 9.7, the objective function
3 z = 12 for any
point along z = 2x + 2y Objective function
2 this line. has the values below.
1 (5, 1)
(0, 0) At (0, 0): z = 2(0) + 2(0) = 0
x
1 2 3 4 (5, 0) At (0, 4): z = 2(0) + 2(4) = 8
Figure 9.7 At (2, 4): z = 2(2) + 2(4) = 12 (Maximum value of z)
At (5, 1): z = 2(5) + 2(1) = 12 (Maximum value of z)
At (5, 0): z = 2(5) + 2(0) = 10
In this case, the objective function has a maximum value of 12 not only at the vertices
(2, 4) and (5, 1), but at any point on the line segment connecting these two vertices.
Some linear programming problems have no optimal solution. This can occur
when the region determined by the constraints is unbounded. Example 4 illustrates such
a problem.
An Unbounded Region

where x ≥ 0 and y ≥ 0 subject to the constraints

x + 2y ≥ 4
3x + y ≥ 7 Constraints
−x + 2y ≤ 7.
solution
The region determined by the constraints is shown below.
5
(1, 4)
4
1 (2, 1)
x
1 2 3 (4, 0) 5
For this unbounded region, there is no maximum value of z. To see this, note that the
REMARK point (x, 0) lies in the region for all values of x ≥ 4. By choosing large values of x, you
can obtain values of
For this problem, the objective
function does have a minimum z = 4(x) + 2(0)
value, z = 10, which occurs at
= 4x
the vertex (2, 1).
that are large. So, there is no maximum value of z.
9781305658004_0902.indd 452 12/3/15 1:58 PM

Application
An Application: Optimal Cost
Example 4 in Section 9.1 set up a system of linear equations for the problem below.
The liquid portion of a diet is to provide at least 300 calories, 36 units of vitamin A,
and 90 units of vitamin C daily. A cup of dietary drink X provides 60 calories, 12 units
of vitamin A, and 10 units of vitamin C. A cup of dietary drink Y provides 60 calories,
6 units of vitamin A, and 30 units of vitamin C. Now, assume that dietary drink X costs
$0.12 per cup and drink Y costs $0.15 per cup. How many cups of each drink should be
consumed each day to minimize the cost and still meet the daily requirements?
solution
Begin by letting x be the number of cups of dietary drink X and y be the number of cups
of dietary drink Y. Moreover, to meet the minimum daily requirements, the inequalities
listed below must be satisfied.
For calories: 60x + 60y ≥ 300
For vitamin A: 12x + 6y ≥ 36
For vitamin C: 10x + 30y ≥ 90 Constraints
x ≥ 0
y ≥ 0
y
The cost C is
10 C = 0.12x + 0.15y. Objective function
8 The graph of the region corresponding to the constraints is shown in Figure 9.8.
(0, 6) To determine the minimum cost, test C at each vertex of the region, as shown below.
6
(1, 4) At (0, 6): C = 0.12(0) + 0.15(6) = 0.90
4
At (1, 4): C = 0.12(1) + 0.15(4) = 0.72
(3, 2)
2 At (3, 2): C = 0.12(3) + 0.15(2) = 0.66 (Minimum value of C)
(9, 0) At (9, 0): C = 0.12(9) + 0.15(0) = 1.08
x
2 4 6 8 10
So, the minimum cost is $0.66 per day, and this occurs when three cups of drink X and
Figure 9.8 two cups of drink Y are consumed each day.
When financial institutions replenish automatic teller

Linear machines (ATMs), they need to take into account a large
Algebra number of variables and constraints to keep the machines
Applied stocked appropriately. Demand for cash machines
fluctuates with such factors as weather, economic
conditions, day of the week, and even road construction.
Further complicating the matter in the United States is a
penalty for depositing and withdrawing money from the
Federal Reserve in the same week. To address this complex
problem, a company that specializes in providing financial
services technology can create high-end optimization
software to set up and solve a linear programming problem
with many variables and constraints. The company
determines an equation for the objective function to
minimize total cash in ATMs, while establishing constraints
on travel routes, service vehicles, penalty fees, and so on.
The optimal solution generated by the software allows the
company to build detailed ATM restocking schedules.
Marquis/Shutterstock.com
9781305658004_0902.indd 453 12/3/15 1:58 PM

9.2 Exercises
Solving a Linear Programming Problem In Exercises 1 7. Objective function: 8. Objective function:
and 2, find the minimum and maximum values of each (a) z = x (a) z = 4x + y
objective function and where they occur, subject to the
(b) z = y (b) z = x + 4y
constraints.
(c) z = x + y (c) z = 4x + 4y
1. Objective function: 2. Objective function:
Constraints: Constraints:
(a) z = 3x + 8y (a) z = 4x + 3y
x ≥ 0 x ≥ 0
(b) z = 5x + 0.5y (b)
z = x + 6y
y ≥ 0 y ≥ 0
Constraints: Constraints: 2x + 3y ≤ 60 x + 2y ≤ 40
x ≥ 0 x ≥ 0 2x + y ≤ 28 x+ y ≥ 30
y ≥ 0 y ≥ 0 4x + y ≤ 48 2x + 3y ≥ 72
x + 3y ≤ 15 2x + 3y ≥ 6
4x + y ≤ 16 3x − 2y ≤ 9 Finding Minimum and Maximum Values In Exercises
x + 5y ≤ 20 9–14, find the minimum and maximum values of the
objective function and the points ( x1, x2 ) where they
y y
occur, subject to the constraints 3x1 + x2 ≤ 15 and
5
(0, 5)
5 4x1 + 3x2 ≤ 30, where x1, x2 ≥ 0.
(3, 4) (0, 4)
4 4 9. z = 2x1 + x2 10. z = 5x1 + x2
(5, 3)
3 3 11. z = x1 + x2 12. z = 3x1 + x2
(0, 2)
2 2 13. z = x1 + 5x2 14. z = 4x1 + 5x2
1
(0, 0) (4, 0)
1 (3, 0)
x x Describing an Unusual Characteristic In Exercises
1 2 3 4 5 1 2 3 4 5 15–20, the linear programming problem has an unusual
characteristic. Sketch a graph of the solution region for
Solving a Linear Programming Problem In Exercises the problem and describe the unusual characteristic. (In
3–8, sketch the region determined by the constraints. each problem, the objective function is to be maximized.)
Then find the minimum and maximum values of each
objective function (if possible) and where they occur, 15. Objective function: 16. Objective function:
subject to the constraints. z = 2.5x + y z=x+y
3. Objective function: 4. Objective function: Constraints: Constraints:
(a) z = 10z + 7y (a) z = 50x + 35y x ≥ 0 x ≥ 0
(b) z = 25x + 30y (b) z = 16x + 18y y ≥ 0 y ≥ 0

3x + 5y ≤ 15 −x + y ≤ 1
5x + 2y ≤ 10 −x + 2y ≤ 4
x ≥ 0 x ≥ 0
x ≤ 60 y ≥ 0
y ≥ 0 8x + 9y ≤ 7200 z = −x + 2y z=x+y
y ≤ 45 8x + 9y ≥ 5400 Constraints: Constraints:
5x + 6y ≤ 420 x ≥ 0 x ≥ 0
5. Objective function: 6. Objective function: y ≥ 0 y ≥ 0

(a) z = 4x + 5y (a) z = 4x + 5y x ≤ 10 −x + y ≤ 0
x+y ≤ 7 −3x + y ≥ 3
(b) z = 2x − y (b) z = 2x + 7y
(c) z = −5x + y (c) z = −x − 3y
z = 3x + 4y z = x + 2y
x ≥ 0 x ≥ 0
y ≥ 0 y ≥ 0 x ≥ 0 x ≥ 0
2x + 2y ≤ 10 4x + 3y ≥ 27 y ≥ 0 y ≥ 0

x + 2y ≤ 6 x+ y ≥ 8 x+y ≤ 1 x + 2y ≤ 4
3x + 5y ≥ 30 2x + y ≥ 4 2x + y ≥ 4
9781305658004_0902.indd 454 12/3/15 1:59 PM

9.2 Exercises 455
21. Optimal Profit The costs to a store for two models of 26. Optimal Revenue The accounting firm in Exercise 25
Global Positioning System (GPS) receivers are $80 and lowers its charge for an audit to $2000. What numbers
$100. The $80 model yields a profit of $25 and the $100 of audits and tax returns will bring in an optimal
model yields a profit of $30. Market tests and available revenue?
resources determined the constraints below. 27. Determine, for each vertex, values of t such that the
(a) The merchant estimates that the total monthly objective function has a maximum value at the vertex
demand will not exceed 200 units. (if possible).
(b) The merchant does not want to invest more than Objective function:
$18,000 in GPS receiver inventory. z = 3x + ty
What is the optimal inventory level for each model? Constraints:
What is the optimal profit?
≥ 0
x
22. Optimal Profit A fruit grower has 150 acres of land ≥ 0
y
for raising crops A and B. The profit is $185 per acre ≤ 84
7x + 14y
for crop A and $245 per acre for crop B. Research and
≤ 30
5x + 4y
available resources determined the constraints below.
(0, 6) (b) (2, 5) (c) (6, 0) (d) (0, 0)
(a)
(a) It takes 1 day to trim an acre of crop A and 2 days
to trim an acre of crop B, and there are 240 days per
year available for trimming. 28. CAPSTONE A company determining an
(b) It takes 0.3 day to pick an acre of crop A and 0.1 day optimal profit finds that the objective function
to pick an acre of crop B, and there are 30 days per has a maximum value at the vertices shown in the
year available for picking. graph.
What is the optimal acreage for each fruit? What is the y
optimal profit? 14
23. Optimal Cost A farming cooperative mixes two 12 (0, 12)
brands of cattle feed. Brand X costs $30 per bag, and 10
brand Y costs $25 per bag. Research and available 8
(5, 7)
resources determined the constraints below. 6
(a) Brand X contains two units of nutritional element A, 4
two units of element B, and two units of element C. 2
x
(b) Brand Y contains one unit of nutritional element A, 2 4 6 8 10
nine units of element B, and three units of element C.
(a) Can you conclude that it also has a maximum value
(c) The minimum requirements for nutrients A, B, and C
at the point (3, 9)? Explain.
are 12 units, 36 units, and 24 units, respectively.
(b) Can you conclude that it also has a maximum value
What is the optimal number of bags of each brand that
at the point (6, 6)? Explain.
should be mixed? What is the optimal cost?
(c) Find two additional points that maximize the
24. Optimal Cost Rework Exercise 23 assuming that
objective function.
brand Y now costs $32 per bag, and it now contains one
unit of nutritional element A, twelve units of element B,
and four units of element C.
Finding an Objective Function In Exercises 29–32,
25. Optimal Revenue An accounting firm charges find an objective function that has a maximum or
$2500 for an audit and $350 for a tax return. The table minimum value at the specified vertex of the constraint
shows the times (in hours) required for staffing and region shown below. (There are many correct answers.)
reviewing.
29. Maximum at vertex A y
Component Audit Tax Return 30. Maximum at vertex B 6

5
31. Maximum at vertex C A(0, 4)
Staffing 75 12.5 B(4, 3)
32. Minimum at vertex C 3
Reviewing 10 2.5 2
1 C(5, 0)
x
The firm has 900 hours of staff time and 155 hours of 1 2 3 4 5 6
review time available each week. What numbers of
audits and tax returns will bring in an optimal revenue?
9781305658004_0902.indd 455 12/3/15 1:59 PM

9.3 The Simplex Method: Maximization

Write the simplex tableau for a linear programming problem.
Use pivoting to find an improved solution.
Use the simplex method to solve a linear programming problem
that maximizes an objective function.
Use the simplex method to find an optimal solution to a real-world
application.
The Simplex Tableau

For linear programming problems involving two variables, the graphical solution
method introduced in Section 9.2 is convenient. For problems involving more than two
variables or large numbers of constraints, it is better to use methods that are adaptable
to technology. One such method is the simplex method, developed by George Dantzig
in 1946. It provides a systematic way of examining the vertices of the feasible region
to determine the optimal value of the objective function.
Say you want to find the maximum value of z = 4x1 + 6x2, where the decision
variables x1 and x2 are nonnegative, subject to the constraints
− x1 + x2 ≤ 11
x1 + x2 ≤ 27
2x1 + 5x2 ≤ 90.
The left-hand side of each inequality is less than or equal to the right-hand side, so there
must exist nonnegative numbers s1, s2, and s3 that can be added to the left side of each
equation to produce the system of linear equations
− x1 + x2 + s1 = 11
x1 + x2 + s2 = 27
REMARK
2x1 + 5x2 + s3 = 90.
Note that for a linear
programming problem in The numbers s1, s2, and s3 are called slack variables because they represent the “slack”
standard form, the objective in each inequality.
function is to be maximized,
not minimized. (Minimization
problems are discussed in Standard Form of a Linear Programming Problem
Sections 9.4 and 9.5.)
A linear programming problem is in standard form when it seeks to maximize
the objective function z = c1x1 + c2 x2 + . . . + cn xn subject to the constraints
a11x1 + a12x2 + . . . + a1n xn ≤ b1
a21x1 + a22x2 + . . . + a2n xn ≤ b2
⋮
am1x1 + am2x2 + . . . + amn xn ≤ bm
where xi ≥ 0 and bi ≥ 0. After adding slack variables, the corresponding system
of constraint equations is
a11x1 + a12x2 + . . . + a1n xn + s1 = b1
a21x1 + a22x2 + . . . + a2n xn + s2 = b2
⋮
am1x1 + am2x2 + . . . + amn xn + sm = bm
where si ≥ 0.
9781305658004_0903.indd 456 12/3/15 2:00 PM

9.3 The Simplex Method: Maximization 457
A basic solution of a linear programming problem in standard form is a solution

(x1, x2, . . . , xn, s1, s2, . . . , sm ) of the constraint equations in which at most m
variables are nonzero, and the variables that are nonzero are called basic variables.
A basic solution for which all variables are nonnegative is a basic feasible solution.
The simplex method is carried out by performing elementary row operations on
a matrix called the simplex tableau. This tableau consists of the augmented matrix
corresponding to the constraint equations together with the coefficients of the objective
function written in the form
−c1x1 − c2x2 − . . . − cnxn + (0)s1 + (0)s2 + . . . + (0)sm + z = 0.
In the tableau, it is customary to omit the coefficient of z. For example, the simplex
tableau for the linear programming problem
z = 4x1 + 6x2 Objective function
− x1 + x2 + s1 = 11
x1 + x2 + s2 = 27 Constraints
2x1 + 5x2 + s3 = 90
is shown below.
Basic
x1 x2 s1 s2 s3 b Variables
−1 1 1 0 0 11 s1
1 1 0 1 0 27 s2
2 5 0 0 1 90 s3
−4 −6 0 0 0 0
→
Current z-value

For this initial simplex tableau, the basic variables are s1, s2, and s3, and the nonbasic
variables are x1 and x2. Note that the basic variables are labeled to the right of the
simplex tableau next to the appropriate rows. This technique is important as you
proceed through the simplex method. It helps keep track of the changing basic
variables, as shown in Example 1.
x1 and x2 are the nonbasic variables in this initial tableau, so they have an initial
value of zero, yielding a current z-value of zero. From the columns that are farthest to
the right, the basic variables have initial values of s1 = 11, s2 = 27, and s3 = 90. So
the current solution is
x1 = 0
x2 = 0
s1 = 11
s2 = 27
s3 = 90.
This solution is a basic feasible solution and is often written as
(x1, x2, s1, s2, s3 ) = (0, 0, 11, 27, 90).
The entry in the lower right corner of the simplex tableau is the current value of z. Note
that the bottom-row entries under x1 and x2 are the negatives of the coefficients of x1
and x2 in the objective function
z = 4x1 + 6x2.
To perform an optimality check for a solution represented by a simplex tableau,
look at the entries in the bottom row of the tableau. If any of these entries are negative
(as above), then the current solution is not optimal.
9781305658004_0903.indd 457 12/3/15 2:01 PM

Pivoting
After you have set up the initial simplex tableau for a linear programming problem, the
simplex method consists of checking for optimality and then, when the current solution
is not optimal, improving the current solution. (An improved solution is one that has a
larger z-value than the current solution.) To improve the current solution, bring a new
basic variable into the solution, the entering variable. This implies that one of the
current basic variables (the departing variable) must leave, otherwise you would have
too many variables for a basic solution. Choose the entering and departing variables
as listed below.
1. The entering variable corresponds to the least (the most negative) entry in the
bottom row of the tableau, excluding the “b-column.”
2. The departing variable corresponds to the least nonnegative ratio bi aij in the
column determined by the entering variable, when aij > 0.
3. The entry in the simplex tableau in the entering variable’s column and the departing
variable’s row is the pivot.
Finally, to form the improved solution, apply Gauss-Jordan elimination to the column
that contains the pivot, as illustrated in Example 1. (This process is called pivoting.)
Pivoting to Find an Improved Solution
Use the simplex method to find an improved solution for the linear programming
problem represented by the tableau shown below.
Basic
−1 1 1 0 0 11 s1
1 1 0 1 0 27 s2
2 5 0 0 1 90 s3
−4 −6 0 0 0 0
solution
The objective function for this problem is
z = 4x1 + 6x2.
Note that the current solution
(x1 = 0, x2 = 0, s1 = 11, s2 = 27, s3 = 90)
corresponds to a z-value of 0. To improve this solution, choose x2 as the entering
variable, because −6 is the least entry in the bottom row.
Basic
−1 1 1 0 0 11 s1
1 1 0 1 0 27 s2
2 5 0 0 1 90 s3
−4 −6 0 0 0 0
→
Entering

To see why you choose x2 as the entering variable, remember that z = 4x1 + 6x2. So, it
appears that a unit change in x2 produces a change of 6 in z, whereas a unit change in
x1 produces a change of only 4 in z.
9781305658004_0903.indd 458 12/3/15 2:01 PM

REMARK To find the departing variable, locate the bi’s that have corresponding positive
In the event of a tie when elements in the entering variable’s column and form the ratios
choosing entering and/or 11 27 90
departing variables, any of the = 11, = 27, and = 18.
1 1 5
tied variables may be chosen.
Here the least nonnegative ratio is 11, so choose s1 as the departing variable.
Basic
−1 1 1 0 0 11 s1 → Departing
1 1 0 1 0 27 s2
2 5 0 0 1 90 s3
−4 −6 0 0 0 0
→
Entering

Note that the pivot is the entry in the first row and second column. Now, use
Gauss-Jordan elimination to obtain the improved solution shown below.
Before Pivoting After Pivoting
[ ] [ ]
−1 1 1 0 0 11 −1 1 1 0 0 11
1 1 0 1 0 27 2 0 −1 1 0 16 − R1 + R2

2 5 0 0 1 90 7 0 −5 0 1 35 −5R1 + R3
−4 −6 0 0 0 0 −10 0 6 0 0 66 6R1 + R4
The new tableau is shown below.
Basic
−1 1 1 0 0 11 x2
2 0 −1 1 0 16 s2
7 0 −5 0 1 35 s3
−10 0 6 0 0 66
Note that x2 has replaced s1 in the basic variables column and the improved solution
(x1, x2, s1, s2, s3) = (0, 11, 0, 16, 35)
has a z-value of
z = 4x1 + 6x2 = 4(0) + 6(11) = 66.
In Example 1, the improved solution is not optimal because the bottom row has
a negative entry. So, apply another iteration of the simplex method to improve the
solution further. Choose x1 as the entering variable. Moreover, the lesser of the ratios
162 = 8 and 357 = 5 is 5, so s3 is the departing variable. Gauss-Jordan elimination
produces the matrices shown below.
[ ] [ ]
−1 1 1 0 0 11 −1 1 1 0 0 11
2 0 −1 1 0 16 2 0 −1 1 0 16
5 1
7 0 −5 0 1 35 1 0 −7 0 7 5 17R3
−10 0 6 0 0 66 −10 0 6 0 0 66
2 1
[ ]
0 1 7 0 7 16 R1 + R3
3 2
0 0 7 1 7 6 R2 − 2R3

0 − 57
1
1 0 7 5
0 − 87
10
−10 0 7 116 R4 + 10R3
9781305658004_0903.indd 459 12/3/15 2:01 PM

So, the new simplex tableau is as shown below.

Basic
2 1
0 1 7 0 7 16 x2
3
0 0 7 1 − 27 6 s2
1
1 0 − 57 0 7 5 x1
− 87 10
0 0 0 7 116
In this tableau, there is still a negative entry in the bottom row. So, choose s1 as the
entering variable and s2 as the departing variable, as shown in the next tableau.
Basic
2 1
0 1 7 0 7 16 x2
3
0 0 7 1 − 27 6 s2 → Departing
1
1 0 − 57 0 7 5 x1
− 87 10
0 0 → 0 7 116
Entering

One more iteration of the simplex method gives the tableau below. (Check this.)
Basic
− 23 1
0 1 0 3 12 x2
7
0 0 1 3 − 23 14 s1
1 0 0 5
3 − 13 15 x1
0 0 0 8
3
2
3 132 → Maximum z-value
In this tableau, there are no negative elements in the bottom row. So, the optimal
solution is
(x1, x2, s1, s2, s3) = (15, 12, 14, 0, 0)
with
z = 4x1 + 6x2 = 4(15) + 6(12) = 132.
The linear programming problem in Example 1 involved only two decision variables,
x1 and x2, so you could have used a graphical solution technique, as in Section 9.2,
Example 2. Notice in the figure below that each iteration in the simplex method
corresponds to moving from one vertex to an adjacent vertex with an improved z-value.
(0, 0) (0, 11) (5, 16) (15, 12)
z = 0 z = 66 z = 116 z = 132
x2
25
20
(5, 16)
15 (15, 12)
10 (0, 11)
5
(0, 0) (27, 0)
x1
5 10 15 20 25 30
9781305658004_0903.indd 460 12/3/15 2:01 PM

The Simplex Method

Here is a summary of the steps involved in the simplex method.
The Simplex Method (Standard Form)

To solve a linear programming problem in standard form, use the steps below.
1. Convert each inequality in the set of constraints to an equation by adding
slack variables.
2. Create the initial simplex tableau.
3. Locate the most negative entry in the bottom row, excluding the “b-column.”
This entry is called the entering variable, and its column is the entering
column. (If ties occur, then any of the tied entries can be used to determine
the entering column.)
4. Form the ratios of the entries in the “b-column” with their corresponding
positive entries in the entering column. (If all entries in the entering column
are 0 or negative, then there is no maximum solution.) The departing row
corresponds to the least nonnegative ratio bi aij. (For ties, choose any
corresponding row.) The entry in the departing row and the entering
column is called the pivot.
5. Use elementary row operations to change the pivot to 1 and all other entries
in the entering column to 0. This process is called pivoting.
6. When all entries in the bottom row are zero or positive, this is the final
tableau. Otherwise, go back to Step 3.
7. If you obtain a final tableau, then the linear programming problem has a
maximum solution. The maximum value of the objective function is the
entry in the lower right corner of the tableau.
Note that the basic feasible solution of an initial simplex tableau is

(x1, x2, . . . , xn, s1, s2, . . . , sm ) = (0, 0, . . . , 0, b1, b2, . . . , bm ).
This solution is basic because at most m variables are nonzero (namely, the slack
variables). It is feasible because each variable is nonnegative.
The next two examples illustrate the use of the simplex method to solve a problem
involving three decision variables.
There are many commercially available optimization

Linear software packages to aid operations researchers in such
Algebra areas as allocating resources to maximize profits and
Applied minimize costs. Many of these packages use the simplex
method as their foundation. Also, free online tools are
available that enable you to check your work in this chapter.
Many of these are user-friendly interfaces that use the
simplex method as well as the graphical method to solve
linear programming problems. These freeware programs
show the steps in the solution, which can be very helpful
in the learning process. Use online optimization freeware
to check the solution of Example 1 in this section and to
check the solution of Example 2 in Section 9.2. As you will
see in the next section, the simplex method can also be
applied to minimization problems. In addition to optimizing
the objective function, commercially available software
packages often contain built-in sensitivity reporting to
analyze how changes or errors in the data will affect the
outcome.
Marcin Balcerzak/Shutterstock.com
9781305658004_0903.indd 461 12/3/15 2:01 PM

The Simplex Method with

Three Decision Variables
Use the simplex method to find the maximum value of

z = 2x1 − x2 + 2x3 Objective function
subject to the constraints

2x1 + x2 ≤ 10
x1 + 2x2 − 2x3 ≤ 20
x2 + 2x3 ≤ 5
where x1 ≥ 0, x2 ≥ 0, and x3 ≥ 0.
solution
Using the basic feasible solution
(x1, x2, x3, s1, s2, s3) = (0, 0, 0, 10, 20, 5)
the initial and subsequent simplex tableaus for this problem are shown below. (Check the
computations, and note the “tie” that occurs when choosing the first entering variable.)
Basic
x1 x2 x3 s1 s2 s3 b Variables
2 1 0 1 0 0 10 s1
1 2 −2 0 1 0 20 s2
0 1 2 0 0 1 5 s3 → Departing
−2 1 −2 0 0 0 0
→
Entering

Basic
2 1 0 1 0 0 10 s1 → Departing
1 3 0 0 1 1 25 s2
1 1 5
0 2 1 0 0 2 2 x3
−2 2 0 0 0 1 5
→
Entering

Basic
1 1
1 2 0 2 0 0 5 x1
0 5
2 0 − 12 1 1 20 s2
1 1 5
0 2 1 0 0 2 2 x3
0 3 0 1 0 1 15
This implies that the optimal solution is
(x1, x2, x3, s1, s2, s3) = (5, 0, 52, 0, 20, 0)
and the maximum value of z is 15.
Note that s2 = 20. The optimal solution yields a maximum value of z = 15 provided
that x1 = 5, x2 = 0, and x3 = 52. Check that these values satisfy the constraints giving
equality in the first and third constraints, yet the second constraint has a slack of 20.

9781305658004_0903.indd 462 12/3/15 2:01 PM

Occasionally, the constraints in a linear programming problem will include an

equation. In such cases, add a “slack variable” called an artificial variable to form the
initial simplex tableau. Technically, this new variable is not a slack variable (because
there is no slack to be taken). Once you have determined an optimal solution in such a
problem, check that any equations in the original constraints are satisfied. Example 3
illustrates such a case.
T
he Simplex Method with
Three Decision Variables
Use the simplex method to find the maximum value of
z = 3x1 + 2x2 + x3 Objective function

4x1 + x2 + x3 = 30
2x1 + 3x2 + x3 ≤ 60
x1 + 2x2 + 3x3 ≤ 40
where x1 ≥ 0, x2 ≥ 0, and x3 ≥ 0.
solution
Using the basic feasible solution (x1, x2, x3, s1, s2, s3) = (0, 0, 0, 30, 60, 40), the initial
and subsequent simplex tableaus for this problem are shown below. (Note that s1 is an
artificial variable, rather than a slack variable.)
Basic
4 1 1 1 0 0 30 s1 → Departing
2 3 1 0 1 0 60 s2
1 2 3 0 0 1 40 s3
−3 −2 −1 0 0 0 0
→
Entering

Basic
1 1 1 15
1 4 4 4 0 0 2 x1
1
0 5
2 2 − 12 1 0 45 s2 → Departing
7 11
0 4 4 − 14 0 1
65
2 s3
− 14 3
− 54 45
0 4
0 0 2
→
Entering

Basic
1 3 1
1 0 5 10 − 10 0 3 x1
1
− 15 2
0 1 5 5 0 18 x2
12 1 7
0 0 5 10 − 10 1 1 s3
1 1
0 0 0 2 2
0 45
So the optimal solution is (x1, x2, x3, s1, s2, s3) = (3, 18, 0, 0, 0, 1) and the maximum
value of z is 45. This solution satisfies the equation provided in the constraints, because
4(3) + 1(18) + 1(0) = 30.
9781305658004_0903.indd 463 12/3/15 2:01 PM

Applications
Example 4 shows how to use the simplex method to maximize profits in a business
application.
A Business Application: Maximum Profit
A manufacturer produces three types of plastic fixtures. The table below shows the
times required for molding, trimming, and packaging. (Times are in hours per dozen
fixtures, and profits are in dollars per dozen fixtures.)
Process Type A Type B Type C

3
Molding 1 2 2
2 2
Trimming 3 3
1
1 1 1
Packaging 2 3 2
Profit $11 $16 $15
The maximum amounts of production time that the manufacturer can allocate to each
component are listed below.
Molding: 12,000 hours
Trimming: 4600 hours
Packaging: 2400 hours
How many dozen units of each type of fixture should the manufacturer produce to
obtain a maximum profit?
solution
Let x1, x2, and x3 represent the numbers of dozens of types A, B, and C fixtures,
respectively. The objective function to be maximized is
Profit = 11x1 + 16x2 + 15x3
where x1 ≥ 0, x2 ≥ 0, and x3 ≥ 0. Moreover, using the information in the table, you
can write the constraints below.
x1 + 2x2 + 32x3 ≤ 12,000
2 2
3 x1 + 3 x2 + x3 ≤ 4600
1 1 1
2 x1 + 3 x2 + 2 x3 ≤ 2400
So, the initial simplex tableau with the basic feasible solution
(x1, x2, x3, s1, s2, s3) = (0, 0, 0, 12,000, 4600, 2400)
is as shown below.
Basic
3
1 2 2 1 0 0 12,000 s1 → Departing
2 2
3 3 1 0 1 0 4600 s2
1 1 1
2 3 2 0 0 1 2400 s3
−11 −16 −15 0 0 0 0
→
Entering

Now, to this initial tableau, apply the simplex method as shown on the next page.
9781305658004_0903.indd 464 12/3/15 2:01 PM

Basic
1 3 1
2 1 4 2 0 0 6000 x2
1 1
3 0 2 − 13 1 0 600 s2
1 1
3 0 4 − 16 0 1 400 s3 → Departing
−3 0 −3 8 0 0 96,000
→
Entering

Basic
3 3
0 1 8 4 0 − 32 5400 x2
1
0 0 4 − 16 1 −1 200 s2 → Departing
3
1 0 4 − 12 0 3 1200 x1
− 34 13
0 0 2 0 9 99,600
→
Entering

Basic
0 1 0 1 − 32 0 5100 x2
0 0 1 − 23 4 −4 800 x3
1 0 0 0 −3 6 600 x1
0 0 0 6 3 6 100,200
So the maximum profit is $100,200, obtained by producing 600 dozen units of Type A,
5100 dozen units of Type B, and 800 dozen units of Type C.
In Example 4, note the “tie” that occurs when choosing the second entering
variable. Verify that choosing x3 instead of x1 as the second entering variable results in
the two intermediate simplex tableaus below, and the same final tableau (and optimal
solution) shown in Example 4.
Basic
1 3 1
2 1 4 2 0 0 6000 x2
1 1 1
3 0 2 −3 1 0 600 s2 → Departing
1 1
3 0 4 − 16 0 1 400 s3
−3 0 −3 8 0 0 96,000
→
Entering

Basic
0 1 0 1 − 32 0 5100 x2
2
3 0 1 − 23 2 0 1200 x3
1
6 0 0 0 − 12 1 100 s3 → Departing
−1 0 0 6 6 0 99,600
→
Entering

9781305658004_0903.indd 465 12/3/15 2:01 PM

Example 5 shows how to use the simplex method to maximize the audience in an
advertising campaign.
A Business Application: Media Selection
Advertising alternatives for a company include television, radio, and newspaper. The
table below shows the costs and estimates of audience coverage for each type of media.
Cost per Audience per

advertisement advertisement
Television $2000 100,000
Newspaper $600 40,000
Radio $300 18,000
The newspaper limits the number of weekly advertisements from a single company
to ten. Moreover, to balance the advertising among the three types of media, no more
than half of the total number of advertisements should occur on the radio, and at least
10% should occur on television. The weekly advertising budget is $18,200. How many
advertisements should run in each of the three types of media to maximize the total
audience?
solution
Let x1, x2, and x3 represent the numbers of advertisements on television, in the
newspaper, and on the radio, respectively. The objective function to be maximized is
z = 100,000x1 + 40,000x2 + 18,000x3 Objective function
where x1 ≥ 0, x2 ≥ 0, and x3 ≥ 0. The constraints for this problem are shown below.
2000x1 + 600x2 + 300x3 ≤ 18,200
x2 ≤ 10
x3 ≤ 0.5(x1 + x2 + x3)
x1 ≥ 0.1(x1 + x2 + x3)
Here is a more manageable form of this system of constraints.
20x1 + 6x2 + 3x3 ≤ 182
x2 ≤ 10
Constraints
−x1 − x2 + x3 ≤ 0
−9x1 + x2 + x3 ≤ 0
So, the initial simplex tableau is below.
Basic
x1 x2 x3 s1 s2 s3 s4 b Variables
20 6 3 1 0 0 0 182 s1 → Departing
0 1 0 0 1 0 0 10 s2
−1 −1 1 0 0 1 0 0 s3
−9 1 1 0 0 0 1 0 s4
−100,000 −40,000 −18,000 0 0 0 0 0
→
Entering

9781305658004_0903.indd 466 12/3/15 2:01 PM

Now, to this initial tableau, apply the simplex method, as shown below.
Basic
3 3 1 91
1 10 20 20 0 0 0 10 x1
0 1 0 0 1 0 0 10 s2 → Departing
7 23 1 91
0 − 10 20 20 0 1 0 10 s3
37 47 9 819
0 10 20 20 0 0 1 10 s4
0 −10,000 −3000 5000 0 0 0 910,000
→
Entering

Basic
3 1 3 61
1 0 20 20 − 10 0 0 10 x1
0 1 0 0 1 0 0 10 x2
23 1 7 161
0 0 20 20 10 1 0 10 s3 → Departing
47 9
− 37 449
0 0 20 20 10 0 1 10 s4
0 0 −3000 5000 10,000 0 0 1,010,000
→
Entering

Basic
1 9 3
1 0 0 23 − 23 − 23 0 4 x1
0 1 0 0 1 0 0 10 x2
1 14 20
0 0 1 23 23 23 0 14 x3
8
0 0 0 23 − 118
23 − 47
23 1 12 s4
118,000 272,000 60,000
0 0 0 23 23 23
0 1,052,000
From this final simplex tableau, the maximum weekly audience for an advertising
budget of $18,200 is
z = 1,052,000 Maximum weekly audience
which occurs when
x1 = 4
x2 = 10
x3 = 14.
The table below summarizes the results.
Number of
Media advertisements Cost Audience
Television 4 $8000 400,000
Newspaper 10 $6000 400,000
Radio 14 $4200 252,000
Total 28 $18,200 1,052,000

9781305658004_0903.indd 467 12/3/15 2:01 PM

9.3 Exercises
Standard Form In Exercises 1–4, explain why the 10. Basic
linear programming problem is not in standard form. x1 x2 s1 s2 s3 b Variables
1. (Minimize) 2. (Maximize) 9 15 1 0 0 750 s1

Objective function: Objective function: 15 −10 0 1 0 60 s2
z = x1 + x2 z = x1 + x2 −12 50 0 0 1 3000 s3
Constraints: Constraints: −45 −78 0 0 0 0
x1 + 2x2 ≤ 4 x1 + 2x2 ≤ 6
Using the Simplex Method In Exercises 11–24, use
x1, x2 ≥ 0 2x1 − x2 ≤ −1
the simplex method to maximize the objective function,
x1, x2 ≥ 0 subject to the constraints.
3. (Maximize) 4. (Maximize) 11. Objective function: 12. Objective function:
Objective function: Objective function:
z = x1 + 2x 2 z = x1 + x2
z = x1 + x2 z = x1 + x2
x1 + 4x2 ≤ 8 x1 + 2x2 ≤ 6
x1 + x2 + 3x3 ≤ 5 x + x2 ≥ 4
1 x1 + x2 ≤ 12 3x1 + 2x1 ≤ 12
2x1 − 2x3 ≥ 1 2x1 + x2 ≥ 6
x1, x2 ≥ 0 x1, x2 ≥ 0
x1, x2, x3 ≥ 0 x1, x2 ≥ 0
Writing a Simplex Tableau In Exercises 5–8, write the z = 3x1 + 2x2 z = 4x1 + 5x2
simplex tableau for the linear programming problem.
You do not need to solve the problem.
x1 + 3x2 ≤ 15 2x1 + 2x2 ≤ 10
5. (Maximize) 6. (Maximize)
4x1 + x2 ≤ 16 x1 + 2x2 ≤ 6
x1, x2 ≥ 0 x1, x2 ≥ 0
z = x1 + 2x2 z = x1 + 3x2
z = 10x1 + 7x2 z = 25x1 + 35x2
2x1 + x2 ≤ 8 x1 + x2 ≤ 4
x1 + x2 ≤ 5 x1 − x2 ≤ 1 Constraints: Constraints:
x1, x2 ≥ 0 x1, x2 ≥ 0 x1 ≤ 60 18x1 + 9x2 ≤ 7200
x2 ≤ 45 8x1 + 9x2 ≤ 3600
Objective function: Objective function: 5x1 + 6x2 ≤ 420 x1, x2 ≥ 0
x1, x2 ≥ 0
z = 2x1 + 3x2 + 4x3 z = 6x1 − 9x2
z = 4x1 + 5x2 z = x1 + 2x2
x1 + 2x2 ≤ 12 2x − 3x2 ≤ 6
1 Constraints: Constraints:
x1 + x3 ≤ 8 x1 + x2 ≤ 20
x1, x2, x3 ≥ 0 x1, x2 ≥ 0 x1 + x2 ≤ 10 x1 + 3x2 ≤ 15
3x1 + 7x2 ≤ 42 2x1 − x2 ≤ 12
Pivoting to Find an Improved Solution In Exercises 9 −3x1 + 7x2 ≤ 28 −4x1 + 3x2 ≤ 0
and 10, use one iteration of pivoting to find an improved x1, x2 ≥ 0 x1, x2 ≥ 0
solution for the linear programming problem represented
by the tableau. 19. Objective function: 20. Objective function:
9. Basic z = 5x1 + 2x 2 + 8x 3 z = x1 − x2 + 2x3
x1 x2 s1 s2 s3 b Variables Constraints: Constraints:
−10 3 1 0 0 32 s1 2x1 − 4x2 + x3 ≤ 42 2x1 + 2x 2 ≤ 8
2 −2 0 1 0 16 s2 2x1 + 3x2 − x3 ≤ 42 x3 ≤ 5
3 12 0 0 1 28 s3 6x1 − x2 + 3x3 ≤ 42 x1, x2, x3 ≥ 0
−5 −2 0 0 0 0 x1, x2, x3 ≥ 0
9781305658004_0903.indd 468 12/3/15 2:01 PM

9.3 Exercises 469
21. Objective function: 27. Optimal Revenue An accounting firm charges

z = x1 − x2 + x3 $2000 for an audit and $300 for a tax return. The table
shows the times (in hours) required for staffing and
Constraints:
reviewing.
2x1 + x2 − 3x3 ≤ 40
x1 + x3 ≤ 25
Component Audit Tax Return
2x2 + 3x3 ≤ 32
x1, x2, x3 ≥ 0 Staffing 100 12.5
22. Objective function: Reviewing 10 2.5
z = 3x1 + 4x2 + x3 + 7x4
The firm has 900 hours of staff time and 100 hours
Constraints:
of review time available each week. Use the simplex
8x1 + 3x2 + 4x3 + x4 ≤ 7 method to find the numbers of audits and tax returns
2x1 + 6x2 + x3 + 5x4 ≤ 3 that will bring in a maximum revenue.
x1 + 4x2 + 5x3 + 2x4 ≤ 8 28. Optimal Revenue The accounting firm in Exercise 27
x1, x2, x3, x4 ≥ 0 raises its charge for an audit to $2500. Use the simplex
23. Objective function: method to find the numbers of audits and tax returns
z = x1 + 2x2 − x4 that will bring in a maximum revenue.
Constraints: 29. Optimal Profit A fruit juice company makes two
special drinks by blending apple and pineapple juices.
x1 + 2x2 + 3x3 ≤ 24
The profit per liter is $0.60 for the first drink and
3x2 + 7x3 + x4 ≤ 42
$0.50 for the second drink. The table shows the portions
x1, x2, x3, x4 ≥ 0 of apple and pineapple juice in each drink.
24. Objective function:

z = x1 + 2x2 + x3 − x4 Ingredient First drink Second drink
Constraints: Apple juice 30% 60%
x1 + x2 + 3x3 + 4x4 ≤ 60
Pineapple juice 70% 40%
x2 + 2x3 + 5x4 ≤ 50

2x1 + 3x2 + 6x4 ≤ 72
There are 1000 liters of apple juice and 1500 liters of
4x1 − x3 + 3x4 ≤ 48
pineapple juice available. Use the simplex method to
x1, x2, x3, x4 ≥ 0 find the numbers of liters of each drink that should be
Using Artificial Variables In Exercises 25 and 26, use produced in order to maximize the profit.
an artificial variable to solve the linear programming 30. Optimal Profit Rework Exercise 29 assuming that
problem, and check your solution. the second drink was changed to contain 80% apple
25. Objective function: juice and 20% pineapple juice.
z = 10x1 + 5x2 + 12x3 31. O
ptimal Profit A manufacturer produces three
models of bicycles. The table shows the times (in hours)
Constraints: required for assembling, painting, and packaging each
−2x1 + x2 + 2x3 ≤ 80 model.
x1 − x3 = 35

− x2 + 3x3 ≤ 60 Model A Model B Model C
x1, x2, x3 ≥ 0
Assembling 2 2.5 3
26. Objective function:
Painting 1.5 2 1
z = 9x1 + x2 + 2x3
Constraints: Packaging 1 0.75 1.25
2x1 + 6x2 = 8
he total times available for assembling, painting, and
T
4x1 + 2x3 ≤ 21
packaging are 4006 hours, 2495 hours, and 1500 hours,
−2x1 − 3x2 + x3 ≤ 12
respectively. The profits per unit are $45 for model A,
x1, x2, x3 ≥ 0 $50 for model B, and $55 for model C. What is the
optimal production level for each model? What is the
optimal profit?
9781305658004_0903.indd 469 12/3/15 2:01 PM

32. Optimal Profit Rework Exercise 31 assuming that Unbounded Solutions In the simplex method, it may
the total times available for assembling, painting, and happen that in selecting the departing variable, all
packaging are 4000 hours, 2500 hours, and 1500 hours, the calculated ratios are negative. This signifies an
respectively, and that the profits per unit are $48 for unbounded solution. Demonstrate this in Exercises 37
model A, $50 for model B, and $52 for model C. and 38.
33. Optimal Profit A grower raises crops X, Y, and 37. (Maximize) 38. (Maximize)
Z. The profit is $60 per acre for crop X, $20 per acre Objective function: Objective function:
for crop Y, and $30 per acre for crop Z. Research and z = x1 + 2x2 z = x1 + 3x2
available resources determined the constraints below.
(a) The grower has 50 acres of land available. x1 − 3x2 ≤ 1 −x1 + x2 ≤ 20
(b) The costs per acre of producing crops X, Y, and Z −x1 + 2x2 ≤ 4 −2x1 + x2 ≤ 50
are $200, $80, and $140, respectively. x1, x2 ≥ 0 x1, x2 ≥ 0
(c) The grower’s total cost cannot exceed $10,000. Other Optimal Solutions If the simplex method
Use the simplex method to find the optimal number of terminates and one or more decision variables are
acres of land for each crop. What is the maximum profit? nonbasic and have bottom-row entries of zero, then
34. Investment An investor has up to $450,000 to invest bringing these variables into the solution will determine
in three types of investments. Type A investments other optimal solutions. Demonstrate this in Exercises
pay 6% annually and have a risk factor of 0. Type B 39 and 40.
investments pay 10% annually and have a risk factor of 39. (Maximize) 40. (Maximize)
0.06. Type C investments pay 12% annually and have Objective function: Objective function:
a risk factor of 0.08. To have a well-balanced portfolio, z = 2.5x1 + x2 z = x1 + 12x2
the investor imposes some conditions. The average risk
factor should be no greater than 0.05. Moreover, at least Constraints: Constraints:
one-half of the total portfolio is to be allocated to type 3x1 + 5x2 ≤ 15 2x1 + x2 ≤ 20
A investments and at least one-fourth of the portfolio 5x1 + 2x2 ≤ 10 x1 + 3x2 ≤ 35
is to be allocated to type B investments. How much x1, x2 ≥ 0 x1 x2 ≥ 0
should the investor allocate to each type of investment
to obtain a maximum return? Maximizing a Function In Exercises 41–44, use a
software program or a graphing utility to maximize the
35. Use the simplex method to find the value(s) of t such
objective function subject to the constraints
that the objective function z = 2x1 − tx2 + x3 has a
maximum value at (x1, x2, x3) = (8, 0, 6) using the x1 + x2 + 0.83x3 + 0.5x4 ≤ 65
constraints 1.2x1 + x2 + x3 + 1.2x4 ≤ 96
2x1 − 3x2 ≤ 16 0.5x1 + 0.7x2 + 1.2x3 + 0.4x4 ≤ 80

x2 + 2x3 ≤ 12 where x1, x2, x3, x4 ≥ 0.
x1, x2, x3 ≥ 0. 41. z = 2x1 + 7x2 + 6x3 + 4x4
42. z = 1.2x1 + x2 + x3 + x4
36. C
APSTONE Consider the initial simplex 43. z = 3x1 − 0.1x2 + 5x3 − 0.9x4
tableau below.
44. z = 2.8x1 + 2.7x2 + 2.2x3 + 2.3x4
Basic
x1 x2 x3 s1 s2 s3 b Variables True or False? In Exercises 45 and 46, determine
−1 1 3 1 0 0 15 s1 whether each statement is true or false. If a statement
1 1 −2 0 1 0 5 s2 is true, give a reason or cite an appropriate statement
from the text. If a statement is false, provide an example
9 3 12 0 0 1 48 s3
that shows the statement is not true in all cases or cite an
−1 0 −2 0 0 0 0 appropriate statement from the text.
(a) List the objective function and constraints 45. After creating the initial simplex tableau, the entering
corresponding to the tableau. column is chosen by locating the most positive entry in
(b) What solution does the tableau represent? Is it the bottom row.
optimal? Explain. 46. If all entries in the entering column are 0 or negative,
(c) To find an improved solution using an iteration of then there is no maximum solution.
the simplex method, which entering and departing
variables would you select? Explain.
9781305658004_0903.indd 470 12/3/15 2:01 PM

9.4 The Simplex Method: Minimization 471
9.4 The Simplex Method: Minimization

Determine the dual of a linear programming problem that
minimizes an objective function.
Use the simplex method to solve a linear programming problem
that minimizes an objective function.
The Dual of a Minimization Problem

In Section 9.3, you applied the simplex method to linear programming problems in
standard form where the objective function was to be maximized. In this section, you
will extend this procedure to linear programming problems in which the objective
function is to be minimized.
A minimization problem is in standard form when the objective function
w = c1x1 + c2 x2 + . . . + cn xn
is to be minimized, subject to the constraints
a11x1 + a12x2 + . . . + a1nxn ≥ b1
a21x1 + a22x2 + . . . + a2nxn ≥ b2
⋮
am1x1 + am2x2 + . . . + amnxn ≥ bm
where xi ≥ 0 and bi ≥ 0. The basic procedure used to solve such a problem is to
convert it to a maximization problem in standard form, and then apply the simplex
method as discussed in Section 9.3.
Consider Example 5 in Section 9.2, where you used geometric methods to solve
the minimization problem shown below.
Minimization Problem: Find the minimum value of
w = 0.12x1 + 0.15x2 Objective function

60x1 + 60x2 ≥ 300
12x1 + 6x2 ≥ 36 Constraints
10x1 + 30x2 ≥ 90
where x1 ≥ 0 and x2 ≥ 0.
To solve this problem using the simplex method, you must first convert it to a
maximization problem. The first step is to form the augmented matrix for this system
of inequalities. To this augmented matrix, add a last row that represents the coefficients
of the objective function, as shown below.
[ ]
60 60 300
12 6 36
10 30 90
0.12 0.15 0
Next, form the transpose of this matrix.
[ ]
60 12 10 0.12
60 6 30 0.15
300 36 90 0
Now, interpret this transposed matrix as a maximization problem, as shown on the next
page.
9781305658004_0904.indd 471 12/3/15 2:02 PM

To interpret the transposed matrix as a maximization problem, introduce new

variables, y1, y2, and y3. This corresponding maximization problem is called the dual of
the original minimization problem.
Dual Maximization Problem: Find the maximum value of
z = 300y1 + 36y2 + 90y3 Dual objective function

60y1 + 12y2 + 10y3 ≤ 0.12
Constaints
60y1 + 6y2 + 30y3 ≤ 0.15
where y1 ≥ 0, y2 ≥ 0, and y3 ≥ 0.
The solution of the original minimization problem can be found by applying the
simplex method to the new dual problem, as shown below.
Basic
y1 y2 y3 s1 s2 b Variables
60 12 10 1 0 0.12 s1 → Departing
60 6 30 0 1 0.15 s2
−300 −36 −90 0 0 0
→
Entering

Basic
1 1 1 1
1 5 6 60 0 500 y1
3
0 −6 20 −1 1 100 s2 → Departing
3
0 24 −40 5 0 5
→
Entering

Basic
1 1 1 7
1 4 0 40 − 120 4000 y1
3 1 1 3
0 − 10 1 − 20 20 2000 y3
33
0 12 0 3 2 50
→
x12 x

So, the solution of the dual maximization problem is z = 33
50 = 0.66. This is the
same value obtained in the minimization problem in Example 5 in Section 9.2. The
x-values corresponding to this optimal solution are the entries in the bottom row
corresponding to slack variable columns. In other words, the optimal solution occurs
when x1 = 3 and x2 = 2.
The fact that a dual maximization problem has the same solution as its original
minimization problem is stated formally below without proof in the von Neumann
Duality Principle, named after American mathematician John von Neumann
(1903–1957).
THEOREM 9.2 The von Neumann Duality Principle

The objective value w of a minimization problem in standard form has a
minimum value if and only if the objective value z of the dual maximization
problem has a maximum value. Moreover, the minimum value of w is equal to
the maximum value of z.
9781305658004_0904.indd 472 12/3/15 2:03 PM

Solving a Minimization Problem

A summary of the steps used to solve a minimization problem is below.

A minimization problem is in standard form when the objective function
w = c1x1 + c2 x2 + . . . + cn xn
is to be minimized, subject to the constraints
a11x1 + a12x2 + . . . + a1n xn ≥ b1
a21x1 + a22x2 + . . . + a2n xn ≥ b2
⋮
am1x1 + am2x2 + . . . + amnxn ≥ bm
where
xi ≥ 0 and bi ≥ 0.
To solve this problem, use the steps below.
1. Form the augmented matrix for the system of inequalities, and add a
bottom row consisting of the coefficients of the objective function.
[ ]
a11 a12 . . . a1n b1
a21 a22 . . . a2n b2
⋮ ⋮ ⋮ ⋮
am1 am2 . . . amn bm
c1 c2 . . . cn 0
2. Form the transpose of this matrix.
[ ]
a11 a21 . . . am1 c1
a12 a22 . . . am2 c2
⋮ ⋮ ⋮ ⋮
a1n a2n . . . amn cn
b1 b2 . . . bm 0
3. Form the dual maximization problem corresponding to this transposed
matrix. That is, find the maximum of the objective function
z = b1y1 + b2 y2 + . . . + bm ym
a11y1 + a21y2 + . . . + am1 ym ≤ c1
a12 y1 + a22 y2 + . . . + am2 ym ≤ c2
⋮
a1n y1 + a2n y2 + . . . + amn ym ≤ cn
where
y1 ≥ 0, y2 ≥ 0, . . . , and ym ≥ 0.
4. Apply the simplex method to the dual maximization problem. The
maximum value of z will be the minimum value of w. Moreover, the values
of x1, x2, . . . , xn will occur in the bottom row of the final simplex tableau,
in the columns corresponding to the slack variables.
Examples 1 and 2 illustrate the steps used to solve a minimization problem.
9781305658004_0904.indd 473 12/3/15 2:03 PM

Find the minimum value of

w = 3x1 + 2x2 Objective function

2x1 + x2 ≥ 6
Constraints
x1 + x2 ≥ 4
where x1 ≥ 0 and x2 ≥ 0.
solution
The augmented matrices corresponding to this problem are shown below.
[ ] [ ]
2 1 6 2 1 3
1 1 4 1 1 2
3 2 0 6 4 0
Minimization Problem Dual Maximization Problem

z = 6y1 + 4y2 Dual objective function

REMARK
2y1 + y2 ≤ 3
Both the minimization and Dual constraints
maximization linear y1 + y2 ≤ 2
programming problems in
where y1 ≥ 0 and y2 ≥ 0. Now apply the simplex method to the dual problem, as
Example 1 could have been
solved with a graphical shown below.
method, as shown below. Basic
Note that the maximum value y1 y2 s1 s2 b Variables
of z = 6y1 + 4y2 in part (a) 2 1 1 0 3 s1 → Departing
is the same as the minimum
value of w = 3x1 + 2x2 in 1 1 0 1 2 s2
part (b). −6 −4 0 0 0
a. y2
→
Entering
3 Maximum:
z = 6y1 + 4y2 = 10 Basic
y1 y2 s1 s2 b Variables
(0, 2) 1 1 3
1 2 2 0 2 y1
(1, 1) 1
− 12
1 1
0 2 1 2 s2 → Departing
y1
0 −1 3 0 9
(0, 0) ( 32, 0( 2 3
→
Entering
b. x2
(0, 6) Basic
6 y1 y2 s1 s2 b Variables
5 Minimum:
w = 3x1 + 2x2 = 10 1 0 1 −1 1 y1
3
0 1 −1 2 1 y2
2 (2, 2) 0 0 2 2 10
1
→
(4, 0)
x1 1 x
2 x
1 2 3 4 5 6
From this final simplex tableau, the maximum value of z is 10. So, the minimum value
of w is 10, and this occurs when x1 = 2 and x2 = 2.
9781305658004_0904.indd 474 12/3/15 2:03 PM

Find the minimum value of w = 2x1 + 10x2 + 8x3 subject to the constraints
x1 + x2 + x3 ≥ 6
x2 + 2x3 ≥ 8 Constraints
−x1 + 2x2 + 2x3 ≥ 4
where x1 ≥ 0, x2 ≥ 0, and x3 ≥ 0.
solution
The augmented matrices corresponding to this problem are shown below.
[ ]
1 1 1 6
0 1 2 8
−1 2 2 4
2 10 8 0
Minimization Problem
[ ]
1 0 −1 2
1 1 2 10
1 2 2 8
6 8 4 0
Dual Maximization Problem
z = 6y1 + 8y2 + 4y3 Dual objective function

y1 − y3 ≤ 2
y1 + y2 + 2y3 ≤ 10 Dual constraints
y1 + 2y2 + 2y3 ≤ 8
where y1 ≥ 0, y2 ≥ 0, and y3 ≥ 0. Now apply the simplex method to the dual problem
as shown below.
Basic
y1 y2 y3 s1 s2 s3 b Variables
1 0 −1 1 0 0 2 s1
1 1 2 0 1 0 10 s2
1 2 2 0 0 1 8 s3 → Departing
−6 −8 −4 0 0 0 0
→
Entering

Basic
1 0 −1 1 0 0 2 s1 → Departing
1
2
0 1 0 1 − 12 6 s2
1 1
2
1 1 0 0 2 4 y2
−2 0 4 0 0 4 32
→
Entering

9781305658004_0904.indd 475 12/3/15 2:03 PM

Basic
1 0 −1 1 0 0 2 y1
3
0 0 2 − 12 1 − 12 5 s2
3
− 12 1
0 1 2 0 2 3 y2
0 0 2 2 0 4 36
→
1 2 x 3x x

From this final simplex tableau, the maximum value of z is 36. So, the minmum value
of w is 36, and this occurs when x1 = 2, x2 = 0, and x3 = 4.
A Business Application: Minimum Cost

A petroleum company owns two refineries. Refinery 1 costs $20,000 per day to operate,
and refinery 2 costs $25,000 per day to operate. The table shows the numbers of barrels
of each grade of oil the refineries can produce each day.
Grade Refinery 1 Refinery 2

High-grade 400 300
Medium-grade 300 400
Low-grade 200 500
The company has orders totaling 25,000 barrels of high-grade oil, 27,000 barrels of
medium-grade oil, and 30,000 barrels of low-grade oil. How many days should it run
each refinery to minimize its costs and still refine enough oil to meet its orders?
solution
Let x1 and x2 represent the numbers of days the two refineries operate. Then the total
cost is
C = 20,000x1 + 25,000x2. Objective function
The constraints are
(High-grade) 400x1 + 300x2 ≥ 25,000
(Medium-grade) 300x1 + 400x2 ≥ 27,000 Constraints
(Low-grade) 200x1 + 500x2 ≥ 30,000
where x1 ≥ 0 and x2 ≥ 0. The augmented matrices corresponding to this problem are
shown below.
[ ]
400 300 25,000
300 400 27,000
200 500 30,000
20,000 25,000 0
Minimization Problem
[ ]
400 300 200 20,000
300 400 500 25,000
25,000 27,000 30,000 0
Dual Maximization Problem
Now apply the simplex method to the dual problem.
9781305658004_0904.indd 476 12/3/15 2:03 PM

Basic
400 300 200 1 0 20,000 s1
300 400 500 0 1 25,000 s2 → Departing
−25,000 −27,000 −30,000 0 0 0
→
Entering

Basic
280 140 0 1 − 25 10,000 s1 → Departing
3 4 1
5 5 1 0 500 50 y3
−7000 −3000 0 0 60 1,500,000
→
Entering

Basic
1 1 1 250
1 2 0 280 − 700 7 y1
1 3 1 200
0 2 1 − 1400 350 7 y3
0 500 0 25 50 1,750,000
→
1x 2 x

From this final simplex tableau, the minimum cost is
C = $1,750,000 Minimum cost
and this occurs when

x1 = 25 and x2 = 50.
So, the two refineries should be operated for the numbers of days shown below.
Refinery 1: 25 days
Refinery 2: 50 days
Note that by operating the two refineries for these numbers of days, the company
produces the amounts of oil listed below.
High-grade oil: 400(25) + 300(50) = 25,000 barrels
Medium-grade oil: 300(25) + 400(50) = 27,500 barrels
Low-grade oil: 200(25) + 500(50) = 30,000 barrels
So, the company refines enough of each grade of oil to meet its orders (with a surplus
of 500 barrels of medium-grade oil).
Minimization has a wide variety of real-life applications.

Linear For example, consider a situation in which steel coils must
Algebra be custom cut to a precise measurement. This can cause
Applied a sizable amount of waste metal. To minimize waste, a
manufacturer determines an objective function and
establishes detailed constraints on costs, production
time, order specifications, and available materials. The
manufacturer than uses specialized optimization software
to develop a production plan for each order, and can adapt
the constraints for different orders, changing conditions,
or varying customers’ needs.
Levent Konuk/Shutterstock.com
9781305658004_0904.indd 477 12/3/15 2:03 PM

9.4 Exercises
Finding the Dual In Exercises 1–6, determine the dual 11. Objective function: 12. Objective function:
of the minimization problem. w = x1 + 4x2 w = 2x1 + 6x2
w = 2x1 + 2x2 w = 2x1 + x2 x1 + x2 ≥ 3 − 2x + 3x2 ≥ 0
Constraints: Constraints: 1
−x1 + 2x2 ≥ 2 x1 + 3x2 ≥ 9
2x1 + x2 ≥ 6 5x1 + x2 ≥ 9 x1, x2 ≥ 0 x1, x2 ≥ 0

x1 + 2x2 ≥ 6 2x1 + 2x2 ≥ 10 x 2 x2
x1, x2 ≥ 0 x1, x2 ≥ 0
3 (0, 3) 10
3. Objective function: 4. Objective function: 8
2
w = 9x1 + 6x2 w = 4x1 + x2 + x3 ( (
4, 5 6
3 3
Constraints: Constraints: 4 (0, 3)
x1 + 2x2 ≥ 5 3x1 + 2x2 + x3 ≥ 23 x1 2 (3, 2)
1 2 3
2x1 + 2x2 ≥ 8 x1 + x3 ≥ 10 x1
2 4 6 8 10
2x1 + x2 ≥ 6 8x1 + x2 + 2x3 ≥ 40
x1, x2 ≥ 0 x1, x2, x3 ≥ 0
w = 6x1 + 3x2 w = x1 + 6x2
w = 14x1 + 20x2 + 24x3 w = 9x1 + 4x2 + 10x3
4x1 + x2 ≥ 4 2x1 + 3x2 ≥ 15
x2 ≥ 2 −x1 + 2x2 ≥ 3
x + x2 + 2x3 ≥ 7 2x + x2 + 3x3 ≥ 6
1 1 x1, x2 ≥ 0 x1, x2 ≥ 0
x1 + 2x2 + x3 ≥ 4 6x1 + x2 + x3 ≥ 9
x2 x2
x1, x2, x3 ≥ 0 x1, x2, x3 ≥ 0
8
Solving a Minimization Problem In Exercises 7–14, (0, 4)

4 6
(0, 5)
(a) solve the minimization problem by the graphical 3
4
method, (b) formulate the dual problem, and (c) solve
(3, 3)
the dual problem by the graphical method.
1 ( 2(
1
2
, 2
7. Objective function: 8. Objective function: x1 x1
2 3 4 5 2 4 6
w = 3x1 + 3x2 w = 14x1 + 20x2
Constraints: Constraints: Solving a Minimization Problem In Exercises 15–24,
x1 + 2x2 ≥ 3 x1 + 2x2 ≥ 4 solve the minimization problem by solving the dual
maximization problem with the simplex method.
3x1 + 2x2 ≥ 5 7x1 + 6x2 ≥ 20
x1, x2 ≥ 0 x1, x2 ≥ 0 15. Objective function: 16. Objective function:
x2 x2 w = x2 w = 3x1 + 8x2
(0, 52 ( (0, 103(
x1 + 5x2 ≥ 10 2x + 7x2 ≥ 9
3 1
2 −6x1 + 5x2 ≥ 3 x1 + 2x2 ≥ 4
(1, 1) (2, 1) x1, x2 ≥ 0 x1, x2 ≥ 0
1 1
(4, 0)
(3, 0) x1 17. Objective function: 18. Objective function:
x1 1 2 3 4
1 3 w = 4x1 + x2 w = x1 + x2
w = 5x1 + 8x2 w = 7x1 + 6x2 x1 + x2 ≥ 8 x1 + 2x2 ≥ 40

Constraints: Constraints: 3x1 + 5x2 ≥ 30 2x1 + 3x2 ≥ 72
(See Exercise 7.) (See Exercise 8.) x1, x2 ≥ 0 x1, x2 ≥ 0
9781305658004_0904.indd 478 12/3/15 2:03 PM

9.4 Exercises 479

28. C
APSTONE Consider the two related
w = x1 + 2x2 w = 2x1 + 5x2
optimization problems below.
Problem 1
3x1 + 5x2 ≥ 15 x1 + 3x2 ≥ 9
Objective function:
5x1 + 2x2 ≥ 10 2x1 + x2 ≥ 12
M = 8y1 + 50y2 + 10y3
x1, x2 ≥ 0 x1, x2 ≥ 0
Constraints:
2y1 + y2 + 2y3 ≤ 5
w = 8x1 + 4x2 + 6x3 w = 8x1 + 16x2 + 18x3
y1 + y2 ≤ 10
y3 ≥ 6y1 − 65
3x1 + 2x2 + x3 ≥ 6 2x1 + 2x2 − 2x3 ≥ 4
y1, y2, y3 ≥ 0
4x1 + x2 + 3x3 ≥ 7 −4x1 + 3x2 − x3 ≥ 1

Problem 2
2x1 + x2 + 4x3 ≥ 8 x1 − x2 + 3x3 ≥ 8
Objective function:
x1, x2, x3 ≥ 0 x1, x2, x3 ≥ 0
N = 5x1 + 10x2 + 65x3
Constraints:
w = 6x1 + 2x2 + 3x3 w = 42x1 + 5x2 + 17x3
2x1 + x2 + 6x3 ≥ 8
x1 + x2 ≥ 50
3x1 + 2x2 + x3 ≥ 28 3x1 − x2 + 7x3 ≥ 5
x3 ≤ 2x1 − 10
6x1 + x3 ≥ 24 −3x1 − x2 + 3x3 ≥ 8
x1, x2, x3 ≥ 0
3x1 + x2 + 2x3 ≥ 40 6x1 + x2 + x3 ≥ 16
x1, x2, x3 ≥ 0 x1, x2, x3 ≥ 0 (a) Which is the minimization problem? Explain.
(b) Which is the dual maximization problem? Explain.
25. Manufacturing An electronics manufacturing
(c) Write the corresponding augmented matrices and
company has three production plants, and each
explain how they are related.
produces three different models of a smart phone. The
table shows the daily capacities (in thousands of units)
of the three plants.
Optimal Cost In Exercises 29–32, two sports drinks
supply protein and carbohydrates. Drink A provides
Basic Gold Platinum 1 unit of protein and 3 units of carbohydrates in each
Model Model Model liter. Drink B supplies 2 units of protein and 2 units of
Plant 1 8 4 8 carbohydrates in each liter. An athlete requires 3 units
of protein and 5 units of carbohydrates. Find the amount
Plant 2 6 6 3 of each drink the athlete should consume to minimize the
Plant 3 12 4 8 cost and still meet the minimum dietary requirements.
29. Drink A costs $2 per liter and drink B costs $3 per liter.
The total demands are 300,000 units of the Basic model, 30. Drink A costs $4 per liter and drink B costs $2 per liter.
172,000 units of the Gold model, and 249,500 units
31. Drink A costs $1 per liter and drink B costs $3 per liter.
of the Platinum model. The daily operating costs are
$55,000 for plant 1, $60,000 for plant 2, and $60,000 32. Drink A costs $1 per liter and drink B costs $2 per liter.
for plant 3. How many days should each plant operate
Minimizing a Function In Exercises 33 and 34, use a
to fill the total demand while keeping the operating cost
software program or a graphing utility to minimize the
at a minimum?
objective function subject to the constraints
26. Manufacturing The company in Exercise 25 lowers
1.5x1 + x2 + 2x4 ≥ 35
the daily operating cost for plant 3 to $50,000. How
many days should each plant operate in order to fill 2x2 + 6x3 + 4x4 ≥ 120
the total demand while keeping the operating cost at a x1 + x2 + x3 + x4 ≥ 50
minimum? 0.5x1 + 2.5x3 + 1.5x4 ≥ 75
27. Standard Form Use a geometric argument to explain where x1, x2, x3, x4 ≥ 0.
why, for a minimization problem in standard form, the
33. w = x1 + 0.5x2 + 2.5x3 + 3x4
left-hand side of each constraint is greater than or equal
to the right-hand side. 34. w = 1.5x1 + x2 + 0.5x3 + 2x4
9781305658004_0904.indd 479 12/3/15 2:03 PM

9.5 The Simplex Method: Mixed Constraints

Find the maximum of an objective function subject to mixed
constraints.
Find the minimum of an objective function subject to mixed
constraints.
Mixed Constraints and Maximization

In Sections 9.3 and 9.4, you studied linear programming problems in standard form.
The constraints for the maximization problems all involved ≤ inequalities, and the
constraints for the minimization problems all involved ≥ inequalities.
As mentioned earlier, linear programming problems for which the constraints
involve both types of inequalities are called mixed-constraint problems. For example,
consider the linear programming problem below.
Mixed-Constraint Problem: Find the maximum value of
z = x1 + x2 + 2x3 Objective function

2x1 + x2 + x3 ≤ 50
2x1 + x2 ≥ 36 Constraints
x1 + x3 ≥ 10
where x1 ≥ 0, x2 ≥ 0, and x3 ≥ 0. This is a maximization problem, so you would
expect each of the inequalities in the set of constraints to involve ≤. The first inequality
does involve ≤, so add a slack variable to form the equation
2x1 + x2 + x3 + s1 = 50.
For the other two inequalities, a new type of variable, a surplus variable, is introduced,
as shown below.
2x1 + x2 − s2 = 36
x1 + x3 − s3 = 10
Notice that surplus variables are subtracted from (not added to) the left side of each
equation. They are called surplus variables because they represent the amounts by
which the left sides of the inequalities exceed the right sides. Surplus variables must
be nonnegative.
Now, to solve the problem, form an initial simplex tableau, as shown below.
Basic
2 1 1 1 0 0 50 s1
2 1 0 0 −1 0 36 s2
1 0 1 0 0 −1 10 s3
−1 −1 −2 0 0 0 0
REMARK
In fact, the values Solving mixed-constraint problems can be difficult. One reason for this is that
x1 = x2 = x3 = 0 do not even there is no convenient feasible solution to begin the simplex method. Note that the
satisfy the constraint
solution represented by the initial tableau above
equations.
(x1, x2, x3, s1, s2, s3) = (0, 0, 0, 50, −36, −10)
is not a feasible solution because the values of the two surplus variables are negative.
9781305658004_0905.indd 480 12/3/15 2:05 PM

9.5 The Simplex Method: Mixed Constraints 481
To eliminate the surplus variables from the current solution, use “trial and error.”
That is, in an effort to find a feasible solution, arbitrarily choose new entering variables.
For example, it seems reasonable to select x3 as the entering variable, because its
column has the most negative entry in the bottom row.
Basic
2 1 1 1 0 0 50 s1
2 1 0 0 −1 0 36 s2
1 0 1 0 0 −1 10 s3 → Departing
−1 −1 −2 0 0 0 0
→
Entering

After pivoting, the new simplex tableau is as shown below.
Basic
1 1 0 1 0 1 40 s1
2 1 0 0 −1 0 36 s2 → Departing
1 0 1 0 0 −1 10 x3
1 −1 0 0 0 −2 20
→
Entering

The current solution (x1, x2, x3, s1, s2, s3) = (0, 0, 10, 40, −36, 0) is still not feasible,
so choose x2 as the entering variable and pivot to obtain the simplex tableau below.
Basic
−1 0 0 1 1 1 4 s1 → Departing
2 1 0 0 −1 0 36 x2
1 0 1 0 0 −1 10 x3
3 0 0 0 −1 −2 56
→
Entering

At this point, you obtain a feasible solution
(x1, x2, x3, s1, s2, s3) = (0, 36, 10, 4, 0, 0).
From here, continue by applying the simplex method as usual. Note that the next
entering variable is s3. After pivoting one more time, you obtain the final simplex
tableau shown below.
Basic
−1 0 0 1 1 1 4 s3
2 1 0 0 −1 0 36 x2
0 0 1 1 1 0 14 x3
1 0 0 2 1 0 64
Note that this tableau is final because it represents a feasible solution and there are no
negative entries in the bottom row. So, the maximum value of the objective function is
z = 64 and this occurs when x1 = 0, x2 = 36, and x3 = 14.
9781305658004_0905.indd 481 12/3/15 2:05 PM


A Maximization Problem
with Mixed Constraints
z = 3x1 + 2x2 + 4x3 Objective function

3x1 + 2x2 + 5x3 ≤ 18
4x1 + 2x2 + 3x3 ≤ 16 Constraints
2x1 + x2 + x3 ≥ 4
where x1 ≥ 0, x2 ≥ 0, and x3 ≥ 0.
solution
To begin, add a slack variable to each of the first two inequalities and subtract a surplus
variable from the third inequality to produce the system of linear equations below.
3x1 + 2x2 + 5x3 + s1 = 18
4x1 + 2x2 + 3x3 + s2 = 16
2x1 + x2 + x3 − s3 = 4
Next form the initial simplex tableau.
Basic
3 2 5 1 0 0 18 s1
4 2 3 0 1 0 16 s2
2 1 1 0 0 −1 4 s3 → Departing
−3 −2 −4 0 0 0 0
This tableau does not represent a feasible solution because the value of s3 is negative.
So, s3 should be the departing variable. There are no real guidelines as to which variable
should enter the solution, and in fact, any choice will work. However, some entering
variables will require more tedious computations than others. For example, choosing x1
as the entering variable produces the tableau below.
Basic
1 7 3
0 2 2 1 0 2 12 s1
0 0 1 0 1 2 8 s2
1 1
1 2 2 0 0 − 12 2 x1
0 − 12 − 52 0 0 − 32 6
Choosing x2 as the entering variable on the initial tableau instead produces the tableau
shown below, which contains “nicer” numbers.
Basic
−1 0 3 1 0 2 10 s1
0 0 1 0 1 2 8 s2
2 1 1 0 0 −1 4 x2
1 0 −2 0 0 −2 8
Choosing x3 as the entering variable on the initial tableau will also produce a tableau
that does not contain fractions. (Verify this.)
9781305658004_0905.indd 482 12/3/15 2:05 PM

Notice that both of the tableaus shown represent feasible solutions. Any choice of
entering variables will lead to a feasible solution, so use trial and error to find an entering
variable that yields “nice” numbers. Once you have reached a feasible solution, follow
the standard pivoting procedure to choose entering variables and eventually reach an
optimal solution.
The rest of this solution uses the tableau produced by choosing x2 as the entering
variable. This tableau does represent a feasible solution, so proceed as usual, choosing
the most negative entry in the bottom row to be the entering variable. (In this case, there
is a tie, so arbitrarily choose x3 to be the entering variable.)
Basic
−1 0 3 1 0 2 10 s1 → Departing
0 0 1 0 1 2 8 s2
2 1 1 0 0 −1 4 x2
1 0 −2 0 0 −2 8
→
Entering

Basic
− 13 1 2 10
0 1 3 0 3 3 x3
1
− 13 4 14
3 0 0 1 3 3 s2 → Departing
7
− 13 2
3 1 0 0 − 53 3 x2
1 2
− 23 44
3 0 0 3 0 3
→
Entering

Basic
− 12 1
0 1 2 − 12 0 1 x3
1 7
− 14 3
4 0 0 4 1 2 s3
REMARK 11
4 1 0 − 34 5
4 0 13
2 x2
Verify that choosing x1 or x3 1 1 1
2 0 0 2 2 0 17
as the entering variable on the
initial simplex tableau yields
So, the maximum value of the objective function is z = 17, and this occurs when
the same solution.
x1 = 0, x2 = 13
2 , and x3 = 1.
As with standard form maximization and minimization,

Linear mixed constraint optimization has a wide variety of real-life
Algebra applications. For example, in Exercise 55 you are asked
Applied to determine how to allocate a company’s advertising
budget to maximize the total audience. This type of mixed
constraint problem is typical in advertising because market
research establishes minimums on the number of each
type of ad, while budgets put upper limits on expenses.
To maximize an audience, researchers must first determine
the ideal demographic and then estimate the time and
place at which those people will most likely see the ad,
considering traditional venues as well as digital formats
and social media. Other common real-life applications of
constrained optimization problems involve minimizing costs.
LIDOphotography/Shutterstock.com
9781305658004_0905.indd 483 12/3/15 2:05 PM

Mixed Constraints and Minimization

Section 9.4 discusses the solution of minimization problems in standard form.
Minimization problems that are not in standard form are more difficult to solve. One
technique is to change a mixed-constraint minimization problem to a mixed-constraint
maximization problem by multiplying each coefficient in the objective function by −1.
The next example demonstrates this technique.
A Minimization Problem
with Mixed Constraints
Find the minimum value of

w = 4x1 + 2x2 + x3 Objective function

2x1 + 3x2 + 4x3 ≤ 14
3x1 + x2 + 5x3 ≥ 4 Constraints
x1 + 4x2 + 3x3 ≥ 6
where x1 ≥ 0, x2 ≥ 0, and x3 ≥ 0.
solution
First, rewrite the objective function by multiplying each of its coefficients by −1, as
shown below.
z = −4x1 − 2x2 − x3 Revised objective function
Maximizing this revised objective function is equivalent to minimizing the original

objective function. Next, add a slack variable to the first inequality and subtract surplus
variables from the second and third inequalities to produce the initial simplex tableau
below.
Basic
2 3 4 1 0 0 14 s1
3 1 5 0 −1 0 4 s2
1 4 3 0 0 −1 6 s3
4 2 1 0 0 0 0
Note that the bottom row contains the negatives of the coefficients of the revised
objective function. Another way of looking at this is that when using this technique to
solve minimization problems in nonstandard form, the bottom row of the initial simplex
tableau consists of the coefficients of the original objective function.
As with maximization problems with mixed constraints, this initial simplex
tableau does not represent a feasible solution. By trial and error, choose x2 as the
entering variable and s2 as the departing variable.
Basic
2 3 4 1 0 0 14 s1
3 1 5 0 −1 0 4 s2 → Departing
1 4 3 0 0 −1 6 s3
4 2 1 0 0 0 0
→
Entering

9781305658004_0905.indd 484 12/3/15 2:05 PM

After pivoting, you obtain the tableau shown below.

Basic
−7 0 −11 1 3 0 2 s1
3 1 5 0 −1 0 4 x2
−11 0 −17 0 4 −1 −10 s3
−2 0 −9 0 2 0 −8
To transform the tableau into one that represents a feasible solution, multiply the third
row by −1.
Basic
−7 0 −11 1 3 0 2 s1
3 1 5 0 −1 0 4 x2
11 0 17 0 −4 1 10 s3
−2 0 −9 0 2 0 −8
Now that you have obtained a simplex tableau that represents a feasible solution,
continue with pivoting operations until you obtain an optimal solution.
Basic
−7 0 −11 1 3 0 2 s1
3 1 5 0 −1 0 4 x2
11 0 17 0 −4 1 10 s3 → Departing
−2 0 −9 0 2 0 −8
REMARK
→
Recall from page 458 that Entering

your choices for the entering Basic
variable exclude the entry in x1 x2 x3 s1 s2 s3 b Variables
the “b-column.” So, although 2 7 11 144
− 46 0 0 1 s1
17 is the least entry in the
17 17 17 17
4 3 5 18
bottom row here, it does not − 17 1 0 0 17 − 17 17 x2 → Departing
represent a variable that can 11 4 1 10
enter the solution. 17 0 1 0 − 17 17 17 x3
65 2 9
17 0 0 0 − 17 17 − 46
17
→
Entering
Basic
2
3 − 73 0 1 0 4
3 6 s1
− 43 17
3 0 0 1 − 53 6 s2
1 4
3 3 1 0 0 − 13 2 x3
11 2 1
3 3 0 0 0 3 −2
The maximum value of the revised objective function is z = −2, and so the minimum
value of the original objective function is
w=2
(the negative of the entry in the lower-right corner). This occurs when
x1 = 0, x2 = 0, and x3 = 2.
9781305658004_0905.indd 485 12/3/15 2:05 PM


A Business Application:
Minimum Shipment Costs
An automobile company has two factories. One factory has 400 cars of one model in
stock and the other factory has 300 cars (of the same model) in stock. Two customers
order this car model. The first customer needs 200 cars, and the second customer needs
300 cars. The table shows the costs of shipping cars from the two factories to the
customers.
Customer 1 Customer 2
Factory 1 $30 $25
Factory 2 $36 $30
How should the company ship the cars to minimize the shipping costs? What is the
minimum cost?
solution
To begin, let x1 and x2 represent the numbers of cars shipped from factory 1 to the first
and second customers, respectively. This means that the number of cars shipped from
factory 2 to the first customer is
200 − x1
and that the number of cars shipped from factory 2 to the second customer is
300 − x2.
(See figure.)
Factory 1
x1 x2
$30 $25
$36 $30
200 − x1 300 − x2
Factory 2
The total cost of shipping is

C = 30x1 + 25x2 + 36(200 − x1) + 30(300 − x2) = 16,200 − 6x1 − 5x2.
The constraints for this minimization problem are as listed below.
x1 + x2 ≤ 400
(200 − x1) + (300 − x2) ≤ 300 x1 + x2 ≥ 200
x1 ≤ 200
x2 ≤ 300
The corresponding maximization problem is to maximize z = 6x1 + 5x2 − 16,200.
The initial simplex tableau is shown below.
Basic
x1 x2 s1 s2 s3 s4 b Variables
1 1 1 0 0 0 400 s1
1 1 0 −1 0 0 200 s2
1 0 0 0 1 0 200 s3
0 1 0 0 0 1 300 s4
−6 −5 0 0 0 0 −16,200
9781305658004_0905.indd 486 12/3/15 2:05 PM

Note that the current z-value is −16,200 because

z = 6x1 + 5x2 − 16,200 = 6(0) + 5(0) − 16,200 = −16,200.
Now, to the initial tableau, apply the simplex method, as shown below.
Basic
1 1 1 0 0 0 400 s1
1 1 0 −1 0 0 200 s2 → Departing
1 0 0 0 1 0 200 s3
0 1 0 0 0 1 300 s4
−6 −5 0 0 0 0 −16,200
→
Entering
Basic
0 0 1 1 0 0 200 s1
1 1 0 −1 0 0 200 x1
0 −1 0 1 1 0 0 s3 → Departing
0 1 0 0 0 1 300 s4
0 1 0 −6 0 0 −15,000
→
Entering
Basic
0 1 1 0 −1 0 200 s1 → Departing
1 1 0 0 1 0 200 x1
0 −1 0 1 1 0 0 s2
0 1 0 0 0 1 300 s4
0 −5 0 0 6 0 −15,000
→
Entering
Basic
0 1 1 0 −1 0 200 x2
1 0 0 0 1 0 200 x1
0 0 1 1 0 0 200 s2
0 0 −1 0 1 1 100 s4
0 0 5 0 1 0 −14,000
From this final simplex tableau, the minimum shipping cost is $14,000. x1 = 200 and
x2 = 200, so you can conclude that the numbers of cars that should ship from the two
factories are as shown in the table.
Factory 1 200 cars 200 cars
Factory 2 0 100 cars

9781305658004_0905.indd 487 12/3/15 2:05 PM

9.5 Exercises
Slack and Surplus Variables In Exercises 1– 8, add 11. (Minimize) 12. (Minimize)
the appropriate slack and surplus variables to the Objective function: Objective function:
system and form the initial simplex tableau. w = x1 + 2x2 w = 3x1 + 2x2
1. (Maximize) 2. (Maximize) Constraints: Constraints:
2x1 + 3x2 ≤ 25 x1 + x2 ≥ 20
z = 10x1 + 4x2 z = x1 + 5x2
x1 + 2x2 ≥ 16 3x1 + 4x2 ≤ 70
x1, x2 ≥ 0 x1, x2 ≥ 0
2x1 + x2 ≥ 4 x1 + x2 ≤ 16
Entering x2, departing s2 Entering x1, departing s1
x1 + x2 ≤ 8 3x1 + 2x2 ≥ 19
x1, x2 ≥ 0 x1, x2 ≥ 0 Objective function: Objective function:
3. (Minimize) 4. (Minimize) z = x1 + x2 z = x1 + 2x2 + 2x3
w = x1 + x2 w = 2x1 + 3x2
−4x1 + 3x2 + x3 ≤ 40 x1 + x2 ≥ 50
−2x1 + x2 + x3 ≥ 10 2x1 + x2 + x3 ≤ 70
2x1 + x2 ≤ 4 3x1 + x2 ≥ 4
x2 + x3 ≤ 20 x2 + 3x3 ≥ 40
x1 + 3x2 ≥ 2 4x1 + 2x2 ≤ 3
x1, x2, x3 ≥ 0 x1, x2, x3 ≥ 0
x1, x2 ≥ 0 x1, x2 ≥ 0
Entering x2, departing s2 Entering x2, departing s1
5. (Maximize) 6. (Minimize)
Objective function: Objective function: Solving a Mixed-Constraint Problem In Exercises
z = x1 + x3 w = 3x1 + x2 + x3 15–20, rework the stated exercise using the specified
entering and departing variables.
15. Exercise 9; entering x1, departing s1
4x1 + x2 ≥ 10 x1 + 2x2 + x3 ≤ 10
x1 + x2 + 3x3 ≤ 30 x2 + 5x3 ≥ 6
2x1 + x2 + 4x3 ≥ 16 4x1 − x2 + x3 ≥ 16
x1, x2, x3 ≥ 0 x1, x2, x3 ≥ 0
7. (Minimize) 8. (Maximize)
Objective function: Objective function: 20. Exercise 14; entering x1, departing s1
w = 4x1 + 2x2 + x3 z = 4x1 + x2 + x3 Solving a Mixed-Constraint Problem In Exercises
Constraints: Constraints: 21–30, use the simplex method to solve the problem.
5x1 + 4x2 + 5x3 ≥ 12 2x + x2 + 4x3 ≤ 60 21. (Maximize) 22. (Maximize)
1 Objective function: Objective function:
x1 + 6x2 ≤ 5 x2 + x3 ≥ 40
x1, x2, x3 ≥ 0 x1, x2, x3 ≥ 0 z = 2x1 + 5x2 z = −x1 + 3x2
Solving a Mixed-Constraint Problem In Exercises
x1 + 2x2 ≥ 4 2x1 + x2 ≤ 4
9–14, use the specified entering and departing variables
to solve the mixed-constraint problem. x1 + x2 ≤ 8 x1 + 5x2 ≥ 5
9. (Maximize) 10. (Maximize) x1, x2 ≥ 0 x1, x2 ≥ 0
Objective function: Objective function: 23. (Maximize) 24. (Minimize)
z = −x1 + 2x2 z = 2x1 + x2 Objective function: Objective function:
Constraints: Constraints: z = x1 + 3x2 w = 5x1 + 3x2
x1 + x2 ≥ 3 x1 + x2 ≥ 4 Constraints: Constraints:
2x1 + x2 ≤ 36 3x1 − 4x2 ≥ 28
x1 + x2 ≤ 6 x1 + x2 ≤ 8
x1, x2 ≥ 0 x1, x2 ≥ 0 x1 + x2 ≥ 18 x1 + 12x2 ≤ 64
Entering x2, departing s1 Entering x1, departing s1 x1, x2 ≥ 0 x1, x2 ≥ 0
9781305658004_0905.indd 488 12/3/15 2:05 PM

9.5 Exercises 489
25. (Minimize) 26. (Minimize) Minimizing Cost In Exercises 47–50, a tire company
Objective function: Objective function: has two suppliers, S1 and S2 , S1 has 900 tires on hand
w = x1 + x2 w = 2x1 + 3x2 and S2 has 800 tires on hand. Customer C1 needs 500
tires and customer C2 needs 600 tires. Minimize the cost
of filling the orders subject to the data in the table
x1 + 2x2 ≥ 25 3x1 + 2x2 ≤ 22 (shipping costs per tire).

2x1 + 5x2 ≤ 60 x1 + x2 ≥ 10 47. 48.
C1 C2 C1 C2
x1, x2 ≥ 0 x1, x2 ≥ 0
27. (Maximize) 28. (Maximize) S1 0.60 1.20 S1 0.80 1.00
Objective function: Objective function: S2 1.00 1.80 S2 1.00 1.20
z = 2x1 + x2 + 3x3 z = 3x1 + 5x2 + 2x3
Constraints: Constraints: 49. 50.
C1 C2 C1 C2
x1 + 4x2 + 2x3 ≤ 85 9x1 + 4x2 + x3 ≥ 70
S1 1.20 1.00 S1 0.80 1.00
x2 − 5x3 ≥ 20 5x1 + 2x2 + x3 ≤ 40
3x1 + 2x2 + 11x3 ≥ 49 4x1 + x2 S2 1.00 1.20 S2 1.00 0.80
≥ 16
x1, x2, x3 ≥ 0 x1, x2, x3 ≥ 0
Minimizing Cost In Exercises 51 and 52, a
29. (Minimize) 30. (Minimize) manufacturer has two assembly plants, plant A and
Objective function: Objective function: plant B, and two distribution outlets, outlet I and
w = −2x1 + 4x2 − x3 w = x1 + x2 + x3 outlet II. Plant A can assemble 5000 units of a product in
Constraints: Constraints: a year and plant B can assemble 4000 units of the same
product in a year. Outlet I must have 3000 units per year
3x1 − 6x2 + 4x3 ≤ 30 x1 + 2x2 + x3 ≥ 30
and outlet II must have 5000 units per year. The table
2x1 − 8x2 + 10x3 ≥ 18 6x2 + x3 ≤ 54 shows the costs of transportation from each plant to each
x1, x2, x3 ≥ 0 x1 + x2 + 3x3 ≥ 20 outlet. Find the shipping schedule that will produce the
x1, x2, x3 ≥ 0 minimum cost. What is the minimum cost?
Maximizing with Mixed Constraints In Exercises

51.
Outlet I Outlet II
31–38, maximize the objective function subject to the
constraints listed below. Plant A $4 $5
x1 + x2 ≤ 5 Plant B $5 $6
−x1 + x2 ≤ 3
x2 ≥ 1 52.
Outlet I Outlet II
x1, x2 ≥ 0
31. z = 2x1 + x2 32. z = x1 + 2x2 Plant A $4 $5
33. z = x2 34. z = −x1 − x2 Plant B $6 $4
35. z = −3x1 + 2x2 36. z = 3x1
53. Minimizing Cost An automobile company has two
37. z = 4x1 + 5x2 38. z = −4x1 + 2x2
factories. One factory has 400 cars of one model in stock
Maximizing with Mixed Constraints In Exercises and the other factory has 300 cars (of the same model)
39–46, maximize the objective function subject to the in stock. Two customers order this car model. The first
constraints listed below. customer needs 200 cars, and the second customer
needs 300 cars. The table shows the costs of shipping
3x1 + 2x2 ≥ 6
cars from the two factories to the two customers.
x1 − x2 ≤ 2
−x1 + 2x2 ≤ 6
x1 ≤ 4
x1, x2 ≥ 0 Factory 1 $36 $30
39. z = −3x2 40. z = 4x1 Factory 2 $30 $25
41. z = x1 + x2 42. z = x1 − 2x2
43. z = −4x1 + x2 44. z = 4x1 − x2 (a) How should the company ship the cars to minimize
the shipping costs?
45. z = −2x1 − 2x2 46. z = −6x1 + 2x2
(b) What is the minimum cost?
9781305658004_0905.indd 489 12/3/15 2:05 PM

54. Minimizing Cost Rework Exercise 53 assuming that Identifying Feasible Solutions In Exercises 57–62,
the shipping costs for the two factories are as shown in determine whether the simplex tableau represents a
the table below. feasible solution. Explain.
57. Basic
Customer 1 Customer 2 x1 x2 s1 s2 b Variables
Factory 1 $25 $30 25 −19 1 0 12 s1
Factory 2 $35 $30 −19 25 0 1 12 s2

6 −6 0 0 0
55. Advertising A company is determining how to 58. Basic
advertise a product nationally on television and in a x1 x2 s1 s2 b Variables
newspaper. Each television ad is expected to be seen by 5 15 −1 0 60 s1
15 million viewers, and each newspaper ad is expected
to be seen by 3 million readers. The company has the 2 −2 0 1 8 s2
constraints below. 25 20 0 0 0
(a) The company has budgeted a maximum of $600,000 59. Basic
to advertise the product. x1 x2 s1 s2 b Variables
(b) Each minute of television time costs $60,000 and 3 9 −1 0 −28 s1

each one-page newspaper ad costs $15,000. 8 4 0 −1 −36 s2
(c) The company’s market research department −16 72 0 0 0
recommends using at least 6 television ads and at
60. Basic
least 4 newspaper ads. x1 x2 s1 s2 s3 b Variables
How should the company allocate its advertising budget −14 13 1 0 0 4 s1
to maximize the total audience? What is the maximum
−10 2 0 −1 0 3 s2
audience?
−8 6 0 0 1 5 s3
56. CAPSTONE Consider the initial simplex −2 −2 0 0 0 0

tableau below. 61. Basic
Basic
x1 x2 x3 s1 s2 s3 b Variables 1 2 1 0 0 32 s1
3 −1 8 a 0 0 48 s1 1 −5 0 1 0 10 s2
0 12 4 0 b 0 96 s2 0 2 0 0 −1 −50 s3
−2 2 0 0 0 c 5 s3 −4 −8 0 0 0 0
−9 −5 −2 0 0 0 0 62. Basic
(a) Does this tableau represent a maximization −10 0 1 −1 0 0 75 s1
problem or a minimization problem? Explain. 0 0 5 0 −1 0 30 s2
(b) Find values of a, b, and c such that the solution is
3 1 12 0 0 1 26 s3
feasible.
7 −24 16 0 0 0 0
(c) Use your answer to part (b) to write an objective
function and a set of constraints that the simplex True or False? In Exercises 63 and 64, determine
tableau could be used to represent. whether each statement is true or false. If a statement
(d) Find values of a, b, and c such that the solution is is true, give a reason or cite an appropriate statement
not feasible. from the text. If a statement is false, provide an example
(e) Let a = 1, b = 1, and c = 1. Which variable that shows the statement is not true in all cases or cite an
should you choose as the departing variable in the appropriate statement from the text.
first iteration of pivoting? Explain. 63.
One technique that can be used to change a
(f) Say you perform the simplex method on the mixed-constraint minimization problem to a
tableau above and obtain a final simplex tableau. mixed-constraint maximization problem is to multiply
Does the entry in the lower-right corner represent each coefficient of the objective function by −1.
the optimal value of the original objective 64.
Surplus variables, like slack variables, are always
function, or its opposite? Explain. positive because they represent the amount by which
the left side of the inequality is less than the right side.
9781305658004_0905.indd 490 12/3/15 2:05 PM

Review Exercises 491
9 Review Exercises
Solving a System of Inequalities In Exercises 1–6, 11. Objective function: 12. Objective function:
sketch the graph (and label any vertices) of the solution z = 25x + 30y z = 15x + 20y
set of the system of inequalities.
1. x + 2y ≤ 160 2. 2x + 3y ≤ 24
0 ≤ x ≤ 60 x ≥ 0
3x + y ≤ 180 2x + y ≤ 16
0 ≤ y ≤ 45 y ≥ 0
x ≥ 0 x ≥ 0
5x + 6y ≤ 420 8x + 9y ≤ 7200
y ≥ 0 y ≥ 0
8x + 9y ≥ 3600
3. 3x + 2y ≥ 24 4. 2x + y ≥ 16
x + 2y ≥ 12 x + 3y ≥ 18 y y

2 ≤ x ≤ 15 0 ≤ x ≤ 25 60 (0, 45)
800 (0, 800)
y ≤ 15 0 ≤ y ≤ 15 (30, 45)
40 (0, 400)
5. 2x − 3y ≥ 0 6. x − y ≤ 10 400 (900, 0)
20 (60, 20)
2x − y ≤ 8 2x + 3y < 30
(0, 0) (60, 0) x
0 ≤ y < 1 x ≥ 0 x 400
20 40 60 (450, 0)
Solving a Linear Programming Problem In Exercises
7–18, find the minimum and maximum values of the 13. Objective function: 14. Objective function:
objective function (if possible), and where they occur, by z = 5x + 0.5y z = 2x + y
the graphical method. Constraints: Constraints:
7. Objective function: 8. Objective function: x ≥ 0 x ≥ 0
z = 3x + 4y z = 10x + 7y y ≥ 0 2x + 3y ≥ 6

Constraints: Constraints: −x + 3y ≤ 75 3x − y ≤ 9
x ≥ 0 x ≥ 0 3x + y ≤ 75 x + 4y ≤ 16
y ≥ 0 y ≥ 0 y y

2x + 5y ≤ 50 2x + y ≥ 100 30 (15, 30) 5
(0, 4)
4x + y ≤ 28 x + y ≥ 75 25
(0, 25) 4
(4, 3)
20 3
y y
15 (0, 2)
2
(0, 10) 10
10 100 (0, 100) 1
(5, 8) 5 (3, 0)
8 75 (0, 0) (25, 0) x
6 x 1 2 3 4 5
50 (25, 50) 5 10 15 20 25 30
4
25 (75, 0)
2 (0, 0) (7, 0) 15. Objective function: 16. Objective function:
x x
2 4 6 8 10 25 50 75 100 z = x + 3y z = 4x − y
−2 −25
x ≥ 0 x ≥ 0
z = 4x + 3y z = 2x + 8y y ≥ 0 y ≥ 0
Constraints: Constraints: x + y ≥ 3 x+y ≥ 2
x ≥ 0 x ≥ 0 x− y ≤ 3 x ≥ y
y ≥ 0 y ≥ 0 x + 5y ≤ 15 3x − y ≤ 12
x+y ≤ 5 2x − y ≤ 4 17. Objective function: 18. Objective function:
y y z = 3x − y z = x − 2y
6 4 (0, 4) Constraints: Constraints:
5 (0, 5)
4 3 x ≥ 0 x ≥ 0
3 2 y ≥ 0 y ≥ 0
2
1 (5, 0)
x ≤ 3y 5x + y ≤ 36
(0, 0) (0, 0) (2, 0)
x x −x + 2y ≤ 12 5x − 2y ≥ 4
1 2 3 4 5 6 −1 1 2 3 4x + 3y ≤ 40 2x + 5y ≥ 19
9781305658004_090R.indd 491 12/3/15 2:06 PM

Using the Simplex Method In Exercises 19–26, use 31. Objective function: 32. Objective function:
the simplex method to maximize the objective function, w = 24x1 + 22x2 + 18x3 w = 32x1 + 36x2 + 4x3
subject to the constraints.
2x1 + 2x2 − 3x3 ≥ 24 4x1 + 3x2 − x3 ≥ 8
z = x1 + 2x2 z = 5x1 + 4x2 6x1 − 2x3 ≥ 21 −8x1 + 6x2 − 6x3 ≥ 0
Constraints: Constraints: −8x1 − 4x2 + 8x3 ≥ 12 −4x1 + 9x3 ≥ 4
2x1 + x2 ≤ 31 x1 − x2 ≤ 22 x1, x2, x3 ≥ 0 x1, x2, x3 ≥ 0

x1 + 4x2 ≤ 40 x1 + 2x2 ≤ 43 33. Objective function: 34. Objective function:
x1, x2 ≥ 0 x1, x2 ≥ 0 w = 16x1 + 54x2 + 48x3 w = 22x1 + 27x2 + 18x3
z = x1 + 2x2 + x3 z = 4x1 + 5x2 + 6x3 x1 + 2x2 + 3x3 ≥ 2 −2x1 + 7x2 + 3x3 ≥ 4
Constraints: Constraints: 2x1 + 7x2 + 4x3 ≥ 5 2x1 + x2 − 3x3 ≥ 12
2x1 + 2x2 + x3 ≤ 20 4x1 + 2x2 + x3 ≤ 30 x1 + 3x2 + 4x3 ≥ 1 x1 − 5x2 + 2x3 ≥ 16
x1 + x2 − 2x3 ≤ 23 x1 + 3x2 + 2x3 ≤ 54 x1, x2, x3 ≥ 0 x1, x2, x3 ≥ 0
−2x1 + x2 − 2x3 ≤ 8 x1 + x2 + 2x3 ≤ 24
Solving a Mixed-Constraint Problem In Exercises
x1, x2, x3 ≥ 0 x1, x2, x3 ≥ 0
35–40, use the simplex method to solve the
23. Objective function: 24. Objective function: mixed-constraint problem.
z = x1 + x2 z = 6x1 + 8x2 35. (Maximize) 36. (Maximize)
Constraints: Constraints: Objective function: Objective function:
3x1 + x2 ≤ 432 20x + 40x2 ≤ 200 z = x1 + 2x2 z = 2x1 + 3x2
1
x1 + 4x2 ≤ 628 30x1 + 42x2 ≤ 228 Constraints: Constraints:
x1, x2 ≥ 0 x1, x2 ≥ 0 −4x1 + 2x2 ≤ 26 −x + x2 ≥ 40
25. Objective function: 26. Objective function: 1
−3x1 + x2 ≥ 12 x2 ≤ 61
z = 3x1 + 5x2 + 4x3 z = 2x1 + 5x2 − x3 x1, x2 ≥ 0 x1, x2 ≥ 0
Constraints: Constraints: 37. (Maximize) 38. (Maximize)
6x1 − 2x2 + 3x3 ≤ 24 −x1 + 3x2 + 2x3 ≤ 92 Objective function: Objective function:
3x1 − 3x2 + 9x3 ≤ 33 −2x1 + 2x2 + 12x3 ≤ 76 z = 2x1 + x2 + x3 z = 3x1 + 2x2 + x3
−2x1 + x2 − 2x3 ≤ 25 3x1 + x2 − 6x3 ≤ 24 Constraints: Constraints:
x1, x2, x3 ≥ 0 x1, x2, x3 ≥ 0 x1 + x2 + x3 ≤ 60 2x1 + x2 + 3x3 ≤ 52
Finding the Dual In Exercises 27 and 28, determine −4x1 + 2x2 + x3 ≥ 52 x1 + x2 + 2x3 ≥ 24
the dual of the minimization problem. 2x1 + x3 ≥ 40 2x2 + x3 ≤ 52
x1, x2, x3 ≥ 0 x1, x2, x3 ≥ 0
39. (Minimize)
w = 7x1 + 3x2 + x3 w = 2x1 + 3x2 + 4x3
Objective function:
w = 9x1 + 4x2 + 10x3
x1 + x2 + 2x3 ≥ 30 x1 + 5x2 + 3x3 ≥ 90
Constraints:
3x1 + 6x2 + 4x3 ≥ 75 x1 + 2x2 + x3 ≥ 75
x1, x2, x3 ≥ 0 3x1 + 2x2 + x3 ≥ 56 32x1 + 16x2 + 8x3 ≤ 344
x1, x2, x3 ≥ 0 20x1 − 40x2 + 20x3 ≥ 200
−45x1 + 15x2 + 30x3 ≤ 525
Solving a Minimization Problem In Exercises 29–34, x1, x2, x3 ≥ 0
solve the minimization problem by solving the dual 40. (Minimize)
maximization problem by the simplex method. Objective function:
29. Objective function: 30. Objective function: w = 4x1 − 2x2 − x3
w = 9x1 + 15x2 w = 16x1 + 18x2 Constraints:
Constraints: Constraints: 2x1 − x2 − x3 ≤ 41
x1 + 5x2 ≥ 15 2x − 3x2 ≥ 14 x1 − 2x2 − x3 ≥ 10
1
4x1 − 10x2 ≥ 0 −4x1 + 9x2 ≥ 8 −x1 − 7x2 + 5x3 ≤ 11
x1, x2 ≥ 0 x1, x2 ≥ 0 x1, x2, x3 ≥ 0
9781305658004_090R.indd 492 12/3/15 2:06 PM

Review Exercises 493
Graphing a System of Inequalities In Exercises 41 49. Optimal Cost A farming cooperative mixes two
and 42, write a system of inequalities that models the brands of cattle feed. Brand X costs $35 per bag, and
description, and sketch a graph of the solution of the brand Y costs $40 per bag. Research and available
system. resources determined the constraints below.
41.
A Pennsylvania fruit grower has 1500 bushels of (a) Brand X contains one unit of nutritional element A,
apples and divides them between markets in Harrisburg one unit of element B, and one unit of element C.
and Philadelphia. These two markets need at least (b) Brand Y contains three units of nutritional element
400 bushels and 600 bushels, respectively. A, one unit of element B, and six units of element C.
42.
A warehouse operator has 24,000 square meters of (c) The minimum requirements for nutrients A, B, and
floor space in which to store two products. Each unit C are 21 units, 9 units, and 30 units, respectively.
of product I requires 20 square meters of floor space
What is the optimal number of bags of each brand that
and costs $12 per day to store. Each unit of product II
should be mixed? What is the optimal cost?
requires 30 square meters of floor space and costs $8
per day to store. The total storage cost per day cannot 50. Investment An investor has up to $250,000 to invest
exceed $12,400. in three types of investments. Type A investments
pay 8% annually and have a risk factor of 0. Type B
43. Optimal Revenue A tailor has 12 square feet of investments pay 10% annually and have a risk factor
cotton, 21 square feet of silk, and 11 square feet of of 0.06. Type C investments pay 14% annually and
wool. A vest requires 1 square foot of cotton, 2 square have a risk factor of 0.10. To have a well-balanced
feet of silk, and 3 square feet of wool. A purse requires portfolio, the investor imposes some conditions. The
2 square feet of cotton, 1 square foot of silk, and average risk factor should be no greater than 0.05.
1 square foot of wool. The purse sells for $80 and the Moreover, at least one-fourth of the total portfolio is
vest sells for $50. to be allocated to type A investments and at least
(a) How many purses and vests should the tailor make one-fourth of the portfolio is to be allocated to type B
to maximize revenue? investments. How much should the investor allocate to
each type of investment to obtain a maximum return?
(b) What is the maximum revenue?
51. Optimal Cost A company owns three mines that
44. O ptimal Income A wood carpentry workshop has
have the daily production levels (in metric tons) shown
400 board-feet of plywood, 487 board-feet of birch, and
in the table.
795 board-feet of pine. A bar stool requires 1 board-foot
of plywood, 2 board-feet of birch, and 1 board-foot of
pine. A step stool requires 1 board-foot of plywood, Grade of Ore
1 board-foot of birch, and 3 board-feet of pine. An Mine High Medium Low
ottoman requires 2 board-feet of plywood, 1 board-foot
of birch, and 1 board-foot of pine. The bar stool sells A 1 2 3
for $22, the step stool sells for $42, and the ottoman B 1 2 2
sells for $29. What combination of products yields the
maximum income? C 2 1 1
Optimal Cost In Exercises 45–48, an athlete uses two The company needs 60 metric tons of high-grade ore,
dietary supplement drinks that provide the nutritional 48 metric tons of medium-grade ore, and 55 metric
elements shown in the table. tons of low-grade ore. How many days should each
mine operate to minimize the cost of meeting these
Drink Protein Carbohydrates Vitamin D requirements when the daily operating costs are $200
for mine A, $200 for mine B, and $100 for mine C, and
I 4 2 1 what is the minimum total cost?
II 1 5 1 52. Optimal Cost Rework Exercise 51 using the daily
production schedule shown in the table.
Find the combination of drinks of minimum cost that will
meet the minimum requirements of 4 units of protein, Grade of Ore
10 units of carbohydrates, and 3 units of vitamin D.
Mine High Medium Low
45. Drink I costs $5 per liter and drink II costs $8 per liter.
46. Drink I costs $7 per liter and drink II costs $4 per liter. A 2 1 2
47. Drink I costs $1 per liter and drink II costs $5 per liter. B 1 1 1
48. Drink I costs $8 per liter and drink II costs $1 per liter. C 4 2 1
9781305658004_090R.indd 493 12/3/15 2:06 PM

9 Projects
1 Beach Sand Replenishment (I)
A lakeside state park is replenishing the sand on its beaches that was lost due to
erosion. The table shows the distances from the sand source sites to the beaches where
the sand will be used, the maximum numbers of truckloads of sand per day that can
be obtained from each site, and the minimum numbers of truckloads of sand required
per day at each beach.
Distance to beach (miles) Maximum truckloads

Sand source Beach 1 Beach 2 Beach 3 per day
A 8 15 50 20
B 10 17 20 30
C 30 26 15 45
Demand 30 35 30
(truckloads per day)
The average round-trip cost to operate the trucks is $2 per mile, regardless of
whether the trucks are loaded or empty. The northwest corner method can be used
to allocate truckloads to meet the demands.
1. Rewrite the table to show the daily round-trip costs from each source to each
beach.
2. In the top entry in the first column, corresponding to source A and beach 1,
allocate either all the demand for the row or all the supply for the column,
whichever is lesser. Repeat for each entry in the first column (if needed) until the
demand for that column is depleted.
3. Repeat part 2 for the second column, taking into consideration the amounts
already allocated in the first column.
4. Repeat part 2 for the thrid column, taking into consideration the amounts already
alloacted in the first and second columns.
5. Find the daily transporation cost corresponding to the allocations you made in
parts 2–4.
6. Use the Internet or some other reference source to research the northwest corner
method. Does the method give an optimal solution? Explain.
2 Beach Sand Replenishment (II)

Rework Project 1 using the simplex method.
1. Write an objective function to represent the situation.
2. Write the corresponding set of constraints to represent the situation.
3. Use a software program or a graphing utility to determine the daily numbers
of truckloads of sand that should be hauled from each source to each beach to
minimize the total daily transportation cost. Then find the minimum daily
transportation cost.
4. Compare your solution to that of Project 1.
Kurhan/Shutterstock.com
9781305658004_090R.indd 494 12/3/15 2:06 PM

Linear Programming Solver PDF

Uploaded by

Document Informationclick to expand document information

Copyright:

Available Formats

Linear Programming Solver PDF

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Linear Programming Solver PDF

Uploaded by

Copyright:

Available Formats

9 Linear

Product Advertising (p. 483)

Minimizing Steel Waste (p. 477)

Optimization Software (p. 461)

Restocking ATMs (p. 453)

Target Heart Rate (p. 446)

Clockwise from top left, Dmitrijs Dmitrijevs/Shutterstock.com; Gerald Bernard/Shutterstock.com;

9781305658004_0901.indd 441 12/3/15 1:57 PM

9.1 Systems of Linear Inequalities

Linear Inequalities and Their Graphs

REMARK Sketching the Graph of an Inequality in Two Variables

9781305658004_0901.indd 442 12/3/15 1:57 PM

Sketching the Graph of a Linear Inequality

Sketching the Graph of a Linear Inequality

Sketch the graph of x − y < 2.

9781305658004_0901.indd 443 12/3/15 1:57 PM

x A solution of a system of inequalities in x and y is a point (x, y) that satisfies each

Solving a System of Inequalities

9781305658004_0901.indd 444 12/3/15 1:57 PM

For the triangular region shown in Example 3, y

Another possibility is that the solution set of a system of inequalities can be

9781305658004_0901.indd 445 12/3/15 1:57 PM

Example 4 shows how a system of linear inequalities can arise in an applied

An Application of a System of Inequalities

See LarsonLinearAlgebra.com for an interactive version of this type of example.

A heart rate monitor watch is designed to ensure that a

9781305658004_0901.indd 446 12/3/15 1:57 PM

9781305658004_0901.indd 447 12/3/15 1:57 PM

9781305658004_0901.indd 448 12/3/15 1:57 PM

9.2 Linear Programming Involving Two Variables

Solving a Linear Programming Problem

THEOREM 9.1 Optimal Solution of a Linear

A linear programming problem can include hundreds, and sometimes even

Graphical Method for Solving a Linear Programming Problem

9781305658004_0902.indd 449 12/3/15 1:58 PM

Solving a Linear Programming Problem

subject to the constraints listed below.

x=0 At (0, 2): z = 3(0) + 2(2) = 4

9781305658004_0902.indd 450 12/3/15 1:58 PM

Solving a Linear Programming Problem

Find the maximum value of the objective function

where x ≥ 0 and y ≥ 0, subject to the constraints

Minimizing an Objective Function

Find the minimum value of the objective function

where x ≥ 0 and y ≥ 0, subject to the constraints

9781305658004_0902.indd 451 12/3/15 1:58 PM

See LarsonLinearAlgebra.com for an interactive version of this type of example.

Find the maximum value of

where x ≥ 0 and y ≥ 0 subject to the constraints

9781305658004_0902.indd 452 12/3/15 1:58 PM

When financial institutions replenish automatic teller

9781305658004_0902.indd 453 12/3/15 1:58 PM

9781305658004_0902.indd 454 12/3/15 1:59 PM

Component Audit Tax Return 30. Maximum at vertex B 6

9781305658004_0902.indd 455 12/3/15 1:59 PM

9.3 The Simplex Method: Maximization

The Simplex Tableau

9781305658004_0903.indd 456 12/3/15 2:00 PM

THEOREM 9.1 Optimal Solution of a Linear

The Simplex Method with

21. Objective function: 27. Optimal Revenue An accounting firm charges