Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

Section 5.6 Linear Programming

Before Starting this Section, Review

1 Intersection of sets (Section P.1 , page 8)
2 Graphing a line (Section 2.3 , page 204)
3 Solving systems of linear inequalities (Section 5.5 , page 562)

Objectives

1 State linear programming problems.
2 Solve linear programming problems.
3 Use linear programming in applications.

The Success of Linear Programming

From 1941 to 1946, George Dantzig was head of the Combat Analysis Branch, U.S. Army Air Corps Headquarters Statistical Control. During this period, he became an expert on planning methods involving troop supply problems that arose during World War II. With a war on several fronts, the size of the problem of coordinating supplies was daunting. This problem was known as programming, a military term that at the time referred to plans or schedules for training, logistical supply, or the deployment of forces. Dantzig mechanized the planning process by introducing linear programming, where programming has the military meaning.

In recent years, linear programming has been applied to problems in almost all areas of human life. A quick check in the library at a university may uncover entire books on linear programming applied to business, agriculture, city planning, and many other areas. Even feedlot operators use linear programming to decide how much and what kinds of food they should give their livestock each day. In Example 3 and in the exercises, we consider several linear programming problems involving two variables.

Linear Programming

1 State linear programming problems.

Recall that if a function f with domain [a, b] has a largest and a smallest value, the largest value is called the maximum value and the smallest value is called the minimum value. The process of finding the maximum or minimum value of a quantity is called optimization. For example, for the function

f (x) = x^{2}, - 2 \leq x \leq 3,

$f (x) = x^{2}, - 2 \leq x \leq 3,$

the maximum value of f occurs at $x = 3$ $x = 3$ and is given by $f (3) = 3^{2} = 9,$ $f (3) = 3^{2} = 9,$ while the minimum value occurs at $x = 0$ $x = 0$ and is given by $f (0) = 0^{2} = 0 .$ $f (0) = 0^{2} = 0 .$ See Figure 5.18. This is an example of an optimization problem involving one variable.

Now we will investigate optimization problems involving two variables, say, x and y. Assume the following conditions:

The quantity f to be maximized or minimized can be written as a linear expression in x and y; that is,

$f = a x + b y, where a \neq 0, b \neq 0 are constants .$ $f = a x + b y, where a \neq 0, b \neq 0 are constants .$
The domain of the variables x and y is restricted to a region S that is determined by (is a solution set of) a system of linear inequalities.

A problem that satisfies conditions (1) and (2) is called a linear programming problem.

The inequalities that determine the region S are called constraints, the region S is called the set of feasible solutions, and $f = a x + b y$ $f = a x + b y$ is called the objective function. A point in S at which f reaches its maximum (or minimum) value, together with the value of f at that point, is called an optimal solution.

Consider the following linear programming problem:

Find values of x and y that will make $f = 2 x + 3 y$ $f = 2 x + 3 y$ as large as possible (in other words, that will result in a maximum value for f), where x and y are restricted by the following constraints:

{\begin{array}{rcl} 3 x + 5 y & \leq & 15 \\ x & \geq & 0 \\ y & \geq & 0 \end{array}

${\begin{array}{rcl} 3 x + 5 y & \leq & 15 \\ x & \geq & 0 \\ y & \geq & 0 \end{array}$

To solve the problem, first sketch the graph of the permissible values of x and y; that is, find the set of feasible solutions determined by the constraints of the problem. Using the method explained in Section 5.5, you find that the set of feasible solutions is the shaded region shown in Figure 5.19.

Now you have to find the values of $f = 2 x + 3 y$ $f = 2 x + 3 y$ at each of the points in the shaded region of Figure 5.19 and then see where f takes on the maximum value. The shaded region, however, has infinitely many points. Because you cannot evaluate f at each point, you need another method to solve the problem.

Fortunately, it can be shown that if there is an optimal solution, it must occur at one of the vertices (corner points) of the feasible solution set. This means that when there is an optimal solution, we can find the maximum (or minimum) value of f by computing the value of f at each vertex and then picking the largest (or smallest) value that results.

Solving Linear Programming Problems

2 Solve linear programming problems.

We next describe a procedure for solving linear programming problems that have a solution.

Procedure in Action

Example 1 Solving a Linear Programming Problem

OBJECTIVE	EXAMPLE
Solve a linear programming problem.	Maximize $f = 2 x + 3 y$ $f = 2 x + 3 y$ subject to the constraints given below.
Step 1 Write an expression for the quantity to be maximized or minimized. This expression is the objective function.	Maximize the objective function $f = 2 x + 3 y$ $f = 2 x + 3 y$
Step 2 Write all constraints as linear inequalities.	subject to the constraints ${\begin{array}{rcl} 3 x + 5 y & \leq & 15 \\ x & \geq & 0 \\ y & \geq & 0 \end{array}$ ${\begin{array}{rcl} 3 x + 5 y & \leq & 15 \\ x & \geq & 0 \\ y & \geq & 0 \end{array}$
Step 3 Graph the solution set of the constraint inequalities. This set is the set of feasible solutions.	See Figure 5.19 for the solution set of the constraints.
Step 4 Find all vertices of the solution set in Step 3 by solving all pairs of equations corresponding to the constraint inequalities.	Find $\begin{array}{l} A (0, 0) by solving {\begin{cases} x = 0 \\ y = 0 \end{cases} \\ B (5, 0) by solving {\begin{array}{rcl} y & = & 0 \\ 3 x + 5 y & = & 15 \end{array} \end{array}$ $\begin{array}{l} A (0, 0) by solving {\begin{cases} x = 0 \\ y = 0 \end{cases} \\ B (5, 0) by solving {\begin{array}{rcl} y & = & 0 \\ 3 x + 5 y & = & 15 \end{array} \end{array}$ and $C (0, 3) by solving {\begin{array}{rcl} x & = & 0 \\ 3 x + 5 y & = & 15. \end{array}$ $C (0, 3) by solving {\begin{array}{rcl} x & = & 0 \\ 3 x + 5 y & = & 15. \end{array}$
Step 5 Find the values of the objective function at each of the vertices in Step 4.	$\begin{array}{l} At A (0, 0), f = 2 (0) + 3 (0) = 0. \\ At B (5, 0), f = 2 (5) + 3 (0) = 10. \\ At C (0, 3), f = 2 (0) + 3 (3) = 9. \end{array}$ $\begin{array}{l} At A (0, 0), f = 2 (0) + 3 (0) = 0. \\ At B (5, 0), f = 2 (5) + 3 (0) = 10. \\ At C (0, 3), f = 2 (0) + 3 (3) = 9. \end{array}$
Step 6 The largest of the values (if any) in Step 5 is the maximum value of the objective function, and the smallest of the values (if any) in Step 5 is the minimum value of the objective function.	At `B`(5, 0), the objective function `f` has a maximum value of 10. Although you are not asked for the minimum value, it is 0 at `A`(0, 0).

Practice Problem 1

Maximize $f = 4 x + 5 y$ $f = 4 x + 5 y$ subject to the constraints

${\begin{array}{rcl} 5 x + 7 y & \leq & 35 \\ x & \geq & 0 \\ y & \geq & 0 \end{array}$ ${\begin{array}{rcl} 5 x + 7 y & \leq & 35 \\ x & \geq & 0 \\ y & \geq & 0 \end{array}$

We stated in the box on page 571 that the optimal value of the objective function f is unique, but the solution (the point (x, y) at which f attains this optimal value) may not be unique. We next solve a linear programming problem that has infinitely many solutions.

Example 2 Solving a Linear Programming Problem Having a Nonunique Solution

Minimize $f = 60 x + 40 y$ $f = 60 x + 40 y$ subject to the constraints $x + 7 \leq 8, x + 2 y \geq 4, 3 x + 2 y \geq 6, x \geq 0, y \geq 0.$ $x + 7 \leq 8, x + 2 y \geq 4, 3 x + 2 y \geq 6, x \geq 0, y \geq 0.$

Solution

Step 1 The objective function is $f = 60 x + 40 y .$ $f = 60 x + 40 y .$
Step 2 We want to find the minimum value of f that can occur at the points (x, y) that satisfy the constraints

${\begin{array}{rcrcl} x & + & y & \leq & 8 \\ x & + & 2 y & \geq & 4 \\ 3 x & + & 2 y & \geq & 6 \\ x & \geq & 0 \\ y & \geq & 0 \end{array}$ ${\begin{array}{rcrcl} x & + & y & \leq & 8 \\ x & + & 2 y & \geq & 4 \\ 3 x & + & 2 y & \geq & 6 \\ x & \geq & 0 \\ y & \geq & 0 \end{array}$
Step 3 The graph of the solution of the inequalities in Step 2 is shaded in Figure 5.20 .

Figure 5.20

Feasible solutions
Step 4 Solving the pairs of equations corresponding to the constraint inequalities, we get the coordinates of the vertices $A = (4, 0), B = (8, 0), C = (0, 8),$ $A = (4, 0), B = (8, 0), C = (0, 8),$ $D = (0, 3),$ $D = (0, 3),$ and $E = (1, 1.5) .$ $E = (1, 1.5) .$

Step 5 Table 5.2 lists the vertices and the corresponding values of the objective function.

Table 5.2

Vertex (`x`, `y`)	Value of the Objective Function $f = 60 x + 40 y$ $f = 60 x + 40 y$
$A = (4, 0)$ $A = (4, 0)$	$f = (60) (4) + (40) (0) = 240$ $f = (60) (4) + (40) (0) = 240$
$B = (8, 0)$ $B = (8, 0)$	$f = (60) (8) + (40) (0) = 480$ $f = (60) (8) + (40) (0) = 480$
$C = (0, 8)$ $C = (0, 8)$	$f = (60) (0) + (40) (8) = 320$ $f = (60) (0) + (40) (8) = 320$
$D = (0, 3)$ $D = (0, 3)$	$f = (60) (0) + (40) (3) = 120$ $f = (60) (0) + (40) (3) = 120$
$E = (1, 1.5)$ $E = (1, 1.5)$	$f = (60) (1) + (40) (1.5) = 120$ $f = (60) (1) + (40) (1.5) = 120$

Step 6 We observe from Table 5.2 that the minimum value of f is 120 and that it occurs at two vertices, D and E. In fact, the unique minimum value occurs at every point on the line segment DE. So the linear programming problem has infinitely many solutions, each of which satisfies the equation $3 x + 2 y = 6 .$ $3 x + 2 y = 6 .$

Practice Problem 2

Repeat Example 2 with $f = \frac{1}{2} x + y .$ $f = \frac{1}{2} x + y .$

Applications

3 Use linear programming in applications.

The next example shows how linear programming is used to minimize the number of calories in a diet.

Example 3 Nutrition; Minimizing Calories

Peter Griffin wants to go on a diet and needs your help in designing a lunch menu. The menu is to include two items: soup and salad. The vitamin units (milligrams) and calorie counts in each ounce of soup and salad are given in Table 5.3.

Table 5.3

Item	Vitamin A	Vitamin C	Calories
Soup	1	3	50
Salad	1	2	40

The menu must provide at least

10 units of vitamin A.
24 units of vitamin C.

Find the number of ounces of each item in the menu needed to provide the required vitamins with the fewest number of calories.

Solution

State the problem mathematically.
1. Step 1 Write the objective function. Let the lunch menu contain x ounces of soup and y ounces of salad. You need to minimize the total number of calories in the menu. Because the soup has 50 calories per ounce (see Table 5.3 ), x ounces of soup has 50x calories. Likewise, the salad has 40y calories. The number f of calories in the two items is therefore given by the objective function
  
  $f = 50 x + 40 y .$ $f = 50 x + 40 y .$
2. Step 2 Write the constraints. Because each ounce of soup provides 1 unit of vitamin A and each ounce of salad provides 1 unit of vitamin A, the two items together provide $1 \cdot x + 1 \cdot y = x + y$ $1 \cdot x + 1 \cdot y = x + y$ units of vitamin A. The lunch must have at least 10 units of vitamin A; this means that
  
  $x + y \geq 10 .$ $x + y \geq 10 .$
  
  Similarly, the two items provide $3 x + 2 y$ $3 x + 2 y$ units of vitamin C. The menu must provide at least 24 units of vitamin C, so
  
  $3 x + 2 y \geq 24 .$ $3 x + 2 y \geq 24 .$
  
  The fact that x and y cannot be negative means that $x \geq 0$ $x \geq 0$ and $y \geq 0 .$ $y \geq 0 .$ You now have four constraints.
  
  Summarize your information. Find x and y such that the value of
  
  $f = 50 x + 40 y Objective function from Step 1$ $f = 50 x + 40 y Objective function from Step 1$
  
  is a minimum, with the restrictions
  
  ${\begin{array}{rcrcr} x & + & y & \geq & 10 \\ 3 x & + & 2 y & \geq & 24 \\ x & \geq & 0 \\ y & \geq & 0 \end{array} Constraints from Step 2$ ${\begin{array}{rcrcr} x & + & y & \geq & 10 \\ 3 x & + & 2 y & \geq & 24 \\ x & \geq & 0 \\ y & \geq & 0 \end{array} Constraints from Step 2$

Solve the linear programming problem.

Step 3 Graph the set of feasible solutions. The set of feasible solutions is shaded in Figure 5.21 . This set is bounded by the lines whose equations are

$x + y = 10, 3 x + 2 y = 24, x = 0, and y = 0 .$ $x + y = 10, 3 x + 2 y = 24, x = 0, and y = 0 .$

Figure 5.21

Feasible solutions
Step 4 Find the vertices. The vertices of the set of feasible solutions are

$\begin{array}{l} A (10, 0), found by solving {\begin{array}{rcl} y & = & 0 \\ x + y & = & 10 \end{array} \\ B (4, 6), found by solving {\begin{array}{rcrcl} x & + & y & = & 10 \\ 3 x & + & 2 y & = & 24 \end{array} \\ C (0, 12), found by solving {\begin{array}{rcrcl} x & = & 0 \\ 3 x & + & 2 y & = & 24 \end{array} \end{array}$ $\begin{array}{l} A (10, 0), found by solving {\begin{array}{rcl} y & = & 0 \\ x + y & = & 10 \end{array} \\ B (4, 6), found by solving {\begin{array}{rcrcl} x & + & y & = & 10 \\ 3 x & + & 2 y & = & 24 \end{array} \\ C (0, 12), found by solving {\begin{array}{rcrcl} x & = & 0 \\ 3 x & + & 2 y & = & 24 \end{array} \end{array}$

Step 5 Find the value of f at the vertices. The value of f at each of the vertices is given in Table 5.4 .

Table 5.4

Vertex (`x`, `y`)	Value of $f = 50 x + 40 y$ $f = 50 x + 40 y$
(10, 0)	$50 (10) + 40 (0) = 500$ $50 (10) + 40 (0) = 500$
(4, 6)	$50 (4) + 40 (6) = 440$ $50 (4) + 40 (6) = 440$
(0, 12)	$50 (0) + 40 (12) = 480$ $50 (0) + 40 (12) = 480$

Step 6 Find the maximum or minimum value of f. From Table 5.4 , the smallest value of f is 440, which occurs when $x = 4$ $x = 4$ and $y = 6 .$ $y = 6 .$

State the conclusion.

The lunch menu for Peter Griffin should contain 4 ounces of soup and 6 ounces of salad. His intake of 440 calories will be as small as possible under the given constraints.

Practice Problem 3

How does the answer to Example 3 change if 1 ounce of soup contains 30 calories and 1 ounce of salad contains 60 calories?

Notice in Example 3 that the value of the objective function $f = 50 x + 40 y$ $f = 50 x + 40 y$ can be made as large as you want by choosing x or y (or both) to be very large. So f has a minimum value of 440 but no maximum value.

Section 5.6 Exercises

Concepts and Vocabulary

The process of finding the maximum or minimum value of a quantity is called .
In a linear programming problem, the linear expression f that is to be maximized or minimized is called a(n) .
The inequalities that determine the region S in a linear programming problem are called , and S is called the set of solutions.
In linear programming, the expression for the objective function is , and all of the constraint inequalities are .
True or False. In linear programming, the term linear means that all mathematical relations used in the problem are linear relations.
True or False. A linear programming problem cannot have infinitely many solutions.
True or False. In a linear programming problem, the optimal value of the objective function is unique.
True or False. In a linear programming problem, the optimal value of the objective function occurs at a unique point.

Building Skills

In Exercises 9–14, find the maximum and the minimum value of each objective function f. The graph of the set of feasible solutions is as follows:

$f = x + y$ $f = x + y$
$f = 2 x + y$ $f = 2 x + y$
$f = x + 2 y$ $f = x + 2 y$
$f = 2 x + 5 y$ $f = 2 x + 5 y$
$f = 5 x + 2 y$ $f = 5 x + 2 y$
$f = 8 x + 5 y$ $f = 8 x + 5 y$

In Exercises 15–26, you are given an objective function f and a set of constraints. Find the set of feasible solutions determined by the given constraints and then maximize or minimize the objective function as directed.

Maximize $f = 9 x + 13 y,$ $f = 9 x + 13 y,$ subject to the constraints $x \geq 0, y \geq 0, 5 x + 8 y \leq 40, 3 x + y \leq 12$ $x \geq 0, y \geq 0, 5 x + 8 y \leq 40, 3 x + y \leq 12$
Maximize $f = 7 x + 6 y,$ $f = 7 x + 6 y,$ subject to the constraints $x \geq 0, y \geq 0, 2 x + 3 y \leq 13, x + y \leq 5$ $x \geq 0, y \geq 0, 2 x + 3 y \leq 13, x + y \leq 5$
Maximize $f = 5 x + 7 y,$ $f = 5 x + 7 y,$ subject to the constraints $x \geq 0, y \geq 0, x + y \leq 70, x + 2 y \leq 100, 2 x + y \leq 120$ $x \geq 0, y \geq 0, x + y \leq 70, x + 2 y \leq 100, 2 x + y \leq 120$
Maximize $f = 2 x + y,$ $f = 2 x + y,$ subject to the constraints $x \geq 0, y \geq 0, x + y \geq 5, 2 x + 3 y \leq 21, 4 x + 3 y \leq 24$ $x \geq 0, y \geq 0, x + y \geq 5, 2 x + 3 y \leq 21, 4 x + 3 y \leq 24$
Minimize $f = x + 4 y,$ $f = x + 4 y,$ subject to the constraints $x \geq 0, y \geq 0, x + 3 y \geq 3, 2 x + y \geq 2$ $x \geq 0, y \geq 0, x + 3 y \geq 3, 2 x + y \geq 2$
Minimize $f = 5 x + 2 y,$ $f = 5 x + 2 y,$ subject to the constraints $x \geq 0, y \geq 0, 5 x + y \geq 10, x + y \geq 6$ $x \geq 0, y \geq 0, 5 x + y \geq 10, x + y \geq 6$
Minimize $f = 13 x + 15 y,$ $f = 13 x + 15 y,$ subject to the constraints $x \geq 0, y \geq 0, 3 x + 4 y \geq 360, 2 x + y \geq 100$ $x \geq 0, y \geq 0, 3 x + 4 y \geq 360, 2 x + y \geq 100$
Minimize $f = 40 x + 37 y,$ $f = 40 x + 37 y,$ subject to the constraints $x \geq 0, y \geq 0, 10 x + 3 y \geq 180, 2 x + 3 y \geq 60$ $x \geq 0, y \geq 0, 10 x + 3 y \geq 180, 2 x + 3 y \geq 60$
Maximize $f = 15 x + 7 y,$ $f = 15 x + 7 y,$ subject to the constraints $3 x + 8 y \leq 24, 2 x + 2 y \leq 8, 5 x + 3 y \leq 18, x \geq 0, y \geq 0 .$ $3 x + 8 y \leq 24, 2 x + 2 y \leq 8, 5 x + 3 y \leq 18, x \geq 0, y \geq 0 .$
Maximize $f = 17 x + 10 y,$ $f = 17 x + 10 y,$ subject to the constraints $2 x + 3 y \geq 12, 5 y - 6 x \leq 6, x \leq 4, x \geq 0, y \geq 2 .$ $2 x + 3 y \geq 12, 5 y - 6 x \leq 6, x \leq 4, x \geq 0, y \geq 2 .$
Minimize $f = 8 x + 16 y,$ $f = 8 x + 16 y,$ subject to the constraints $2 x + y \geq 40, x + 2 y \geq 50, x + y \geq 35, x \geq 0, y \geq 0 .$ $2 x + y \geq 40, x + 2 y \geq 50, x + y \geq 35, x \geq 0, y \geq 0 .$
Minimize $f = 12 x + 12 y,$ $f = 12 x + 12 y,$ subject to the constraints $2 x + 3 y \geq 4, 3 x + y \leq 6, x \geq 0, y \geq 0 .$ $2 x + 3 y \geq 4, 3 x + y \leq 6, x \geq 0, y \geq 0 .$

Applying the Concepts

Agriculture: crop planning. A farmer owns 240 acres of cropland. He can use his land to produce corn and soybeans. A total of 320 labor hours is available to him during the production period of both of these commodities. Each acre for corn production requires two hours of labor, and each acre for soybean production requires one hour of labor. Assuming that the profit per acre in corn production is $50 and that in soybean production is $40, find the number of acres that he should allocate to the production of corn and soybeans so as to maximize his profit.
Repeat Exercise 27, assuming that the profit per acre in corn production is $30 and that in soybean production is $40.
Manufacturing: production scheduling. Two machines (I and II) each produce two grades of plywood: Grade A and Grade B. In one hour of operation, machine I produces 20 units of Grade A and 10 units of Grade B plywood. Also in one hour of operation, machine II produces 30 units of Grade A and 40 units of Grade B plywood. The machines are required to meet a production schedule of at least 1400 units of Grade A and 1200 units of Grade B plywood. Assuming that the cost of operating machine I is $50 per hour and the cost of operating machine II is $80 per hour, find the number of hours each machine should be operated so as to minimize the cost.
Repeat Exercise 29, assuming that the cost of operating machine I is $70 per hour and the cost of operating machine II is $90 per hour.
Advertising. The Sundial Cheese Company wants to allocate its $6000 advertising budget to two local media—television and newspaper—so that the exposure (number of viewers) to its advertisements is maximized. There are 60,000 viewers exposed to each minute of television time and 20,000 readers exposed to each page of newspaper advertising. Each minute of television time costs $1000, and each page of newspaper advertising costs $500. How should the company allocate its budget if it has to buy at least one minute of television time and at least two pages of newspaper advertising?
Advertising. The Fantastic Bread Company allocates a maximum of $24,000 to advertise its product to television and newspaper. Each hour of television costs $4000, and each page of newspaper advertising costs $3000. The exposure from each hour of television time is assumed to be 120,000, and the exposure from each page of newspaper advertising is 80,000. Furthermore, the board of directors requires at least two hours of television time and one page of newspaper advertising. How should the advertising budget be divided to maximize exposure to the advertisements?
Agriculture. A Florida citrus company has 480 acres of land for growing oranges and grapefruit. Profits per acre are $40 for oranges and $30 for grapefruit. The total labor hours available during the production are 800. Each acre for oranges uses two hours of labor, and each acre for grapefruit uses one hour of labor. If the fixed costs are $3000, what is the maximum profit?
Agriculture. The Florida Juice Company makes two types of fruit punch—Fruity and Tangy—by blending orange juice and apple juice into a mixture. The fruit punch is sold in 5-gallon bottles. A bottle of Fruity earns a profit of $3, and a bottle of Tangy earns a $2 profit. A bottle of Fruity requires 3 gallons of orange juice and 2 gallons of apple juice, and a bottle of Tangy requires 4 gallons of orange juice and 1 gallon of apple juice. If 200 gallons of orange juice and 120 gallons of apple juice are available, find the maximum profit for the company.
Manufacturing. The Fantastic Furniture Company manufactures rectangular and circular tables. Each rectangular table requires one hour of assembling and one hour of finishing, and each circular table requires one hour of assembling and two hours of finishing. The company’s 20 assemblers and 30 finishers each work 40 hours per week. Each rectangular table brings a profit of $3, and each circular table brings a profit of $4. If all of the tables manufactured are sold, how many of each type should be made to maximize profits?
Manufacturing. A company produces a portable global positioning system (GPS) and a portable digital video disc (DVD) player, each of which requires three stages of processing. The length of time for processing each unit is given in the following table.

Stage GPS (hr/unit) DVD (hr/unit) Maximum Process Capacity (hr/day)

I 12 12 840

II 3 6 300

III 8 4 480

Profit per unit $6 $4

How many of each product should the company produce per day to maximize profit?
Building houses. A contractor has 100 units of concrete, 160 units of wood, and 400 units of glass. He builds terraced houses and cottages. A terraced house requires 1 unit of concrete, 2 units of wood, and 2 units of glass; a cottage requires 1 unit of concrete, 1 unit of wood, and 5 units of glass. A terraced house sells for $40,000, and a cottage sells for $45,000. How many houses of each type should the contractor build to obtain the maximum amount of money?
Hospitality. Mrs. Adams owns a motel consisting of 300 single rooms and an attached restaurant that serves breakfast. She knows that 30% of the male guests and 50% of the female guests will eat in the restaurant. Suppose she makes a profit of $18.50 per day from every guest who eats in her restaurant and $15 per day from every guest who does not eat in her restaurant. Assuming that Mrs. Adams never has more than 125 female guests and never more than 220 male guests, find the number of male and female guests that would provide the maximum profit.
Hospitality. In Exercise 38, find Mrs. Adams’s maximum profit during a season in which she always has at least 100 guests, assuming that she makes a profit of $15 per day from every guest who eats in her restaurant and she suffers a loss of $2 per day from every guest who does not eat in her restaurant.
Transportation. Major Motors, Inc., must produce at least 5000 luxury cars and 12,000 medium-priced cars. It must produce, at most, 30,000 units of compact cars. The company owns one factory in Michigan and one in North Carolina. The Michigan factory produces 20, 40, and 60 units of luxury, medium-priced, and compact cars, respectively, per day, and the North Carolina factory produces 10, 30, and 20 luxury, medium-priced, and compact cars, respectively, per day. If the Michigan factory costs $60,000 per day to operate and the North Carolina factory costs $40,000 per day to operate, find the number of days each factory should operate to minimize the cost and meet the requirements.
Nutrition. Elisa Epstein is buying two types of frozen meals: a meal of enchiladas with vegetables and a vegetable loaf meal. She wants to guarantee that she gets a minimum of 60 grams of carbohydrates, 40 grams of proteins, and 35 grams of fats. The enchilada meal contains 5, 3, and 5 grams of carbohydrates, proteins, and fats, respectively, per kilogram, and the vegetable loaf contains 2, 2, and 1 gram of carbohydrates, proteins, and fats, respectively, per kilogram. If the enchilada meal costs $3.50 per kilogram and the vegetable loaf costs $2.25 per kilogram, how many kilograms of each should Elisa buy to minimize the cost and still meet the minimum requirement?
Temporary help. The personnel director of the main post office plans to hire extra helpers during the holiday season. Because office space is limited, the number of temporary workers cannot exceed ten. She hires workers sent by Super Temps and by Ready Aid. From her past experience, she knows that a typical worker sent by Super Temps can handle 300 letters and 80 packages per day and that a typical worker from Ready Aid can handle 600 letters and 40 packages per day. The post office expects that the additional daily volume of letters and packages will be at least 3900 and 560, respectively. The daily wages for a typical worker from Super Temps and Ready Aid are $96 and $86, respectively. How many workers from each agency should be hired to keep the daily wages to a minimum?

Stage	GPS (hr/unit)	DVD (hr/unit)	Maximum Process Capacity (hr/day)
I	12	12	840
II	3	6	300
III	8	4	480
Profit per unit	$6	$4

Beyond the Basics

Maximize $f = 8 x + 7 y,$ $f = 8 x + 7 y,$ subject to the constraints $x + 2 y \geq 10, 8 y - 7 x \leq 40, x + y \leq 20, 4 x - y \leq 40, x \geq 0, y \geq 0 .$ $x + 2 y \geq 10, 8 y - 7 x \leq 40, x + y \leq 20, 4 x - y \leq 40, x \geq 0, y \geq 0 .$
Minimize $f = 3 x + 2 y,$ $f = 3 x + 2 y,$ subject to the constraints $6 y - 5 x \leq 80, 7 x - 5 y \leq 80, 5 x + 8 y \geq 115, 10 x - y \geq 60, 0 \leq x \leq 20, y \geq 0 .$ $6 y - 5 x \leq 80, 7 x - 5 y \leq 80, 5 x + 8 y \geq 115, 10 x - y \geq 60, 0 \leq x \leq 20, y \geq 0 .$
Minimize $f = 5 x + 6 y,$ $f = 5 x + 6 y,$ subject to the constraints $y \leq x + 5, 7 x + 2 y \leq 28, 0 \leq x \leq 3, 0 \leq y \leq 6 .$ $y \leq x + 5, 7 x + 2 y \leq 28, 0 \leq x \leq 3, 0 \leq y \leq 6 .$
Maximize $f = 7 x + 3 y,$ $f = 7 x + 3 y,$ subject to the constraints $x + y \leq 100, x + y \geq 50, 2 x + 5 y \geq 150, 2 x + y \geq 80, x \geq 0, y \geq 0 .$ $x + y \leq 100, x + y \geq 50, 2 x + 5 y \geq 150, 2 x + y \geq 80, x \geq 0, y \geq 0 .$
Suppose an objective function $f = a x + b y$ $f = a x + b y$ has the same value M at two different points $P (x_{1}, y_{1})$ $P (x_{1}, y_{1})$ and $Q (x_{2}, y_{2}) .$ $Q (x_{2}, y_{2}) .$ Prove that f has the value M at every point of the line segment PQ.
Suppose the feasible solution set of a linear programming problem is a quadrilateral. Is it possible that the optimal solution also occurs at an interior point of the quadrilateral?

Critical Thinking / Discussion / Writing

Consider this problem: Maximize $f = 2 x + 3 y,$ $f = 2 x + 3 y,$ subject to the constraints $y - x \leq 6, x \geq 0, 0 \leq y \leq 8 .$ $y - x \leq 6, x \geq 0, 0 \leq y \leq 8 .$
1. Explain why the region S of feasible solutions is unbounded.
2. Show that the problem has no solution.
Diet problem. The objective of a diet problem is to have certain quantities of food on the menu that meet nutritional requirements at a minimum cost. Suppose the consideration is limited to milk, chicken, and vegetables and to vitamins A, B, and C. The number of milligrams of each of these vitamins contained within a unit of each food is given to the right.

Vitamin Liters of Milk Pounds of Chicken Pounds of Vegetable Minimum Daily Requirement

A 1 2 5 1 mg

B 10 5 4 50 mg

C 6 20 7 10 mg

Cost $3.20 $2.50 $1.30

Write a linear programming formulation of this problem if a daily diet consists of x liters of milk, y pounds of chicken, and z pounds of vegetables.

Vitamin	Liters of Milk	Pounds of Chicken	Pounds of Vegetable	Minimum Daily Requirement
A	1	2	5	1 mg
B	10	5	4	50 mg
C	6	20	7	10 mg
Cost	$3.20	$2.50	$1.30

Getting Ready for the Next Section

In Exercises 51–54, solve each system of linear equations by the Gaussian elimination method (See page 529.)

${\begin{array}{rcl} x - 2 y & = & 4 \\ - 3 x + 5 y & = & - 7 \end{array}$ ${\begin{array}{rcl} x - 2 y & = & 4 \\ - 3 x + 5 y & = & - 7 \end{array}$
${\begin{array}{rcl} 3 x + 5 y & = & 6 \\ 2 x - y & = & 17 \end{array}$ ${\begin{array}{rcl} 3 x + 5 y & = & 6 \\ 2 x - y & = & 17 \end{array}$
${\begin{array}{rcl} x - 4 y - z & = & 11 \\ 2 x - 5 y + 2 z & = & 39 \\ - 3 x + 2 y + z & = & 1 \end{array}$ ${\begin{array}{rcl} x - 4 y - z & = & 11 \\ 2 x - 5 y + 2 z & = & 39 \\ - 3 x + 2 y + z & = & 1 \end{array}$
${\begin{array}{rcl} x + 3 y - 2 z & = & 5 \\ 2 x + y + 4 z & = & 8 \\ 6 x + y - 3 z & = & 5 \end{array}$ ${\begin{array}{rcl} x + 3 y - 2 z & = & 5 \\ 2 x + y + 4 z & = & 8 \\ 6 x + y - 3 z & = & 5 \end{array}$
Consider the following rectangular array of numbers:

$[\begin{array}{r} 2 & 4 & - 6 & 10 \\ 3 & - 2 & 4 & 12 \end{array}] \begin{array}{l} \leftarrow row 1 \\ \leftarrow row 2 \end{array}$ $[\begin{array}{r} 2 & 4 & - 6 & 10 \\ 3 & - 2 & 4 & 12 \end{array}] \begin{array}{l} \leftarrow row 1 \\ \leftarrow row 2 \end{array}$

Write the new rectangular array after multiplying each number in row 1 by $\frac{1}{2} .$ $\frac{1}{2} .$
In the rectangular array obtained in Exercise 55, add $- 3$ $- 3$ times each number in row 1 to the corresponding number in row 2.
In the rectangular array obtained in Exercise 56, multiply each number in row 2 by $- \frac{1}{8} .$ $- \frac{1}{8} .$
In the rectangular array obtained in Exercise 57, add $- 2$ $- 2$ times each number in row 2 to the corresponding number in row 1.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for Section 5.6 Linear Programming

Create new playlist

Sign In

Sign Up

Table of Contents for
Section 5.6 Linear Programming