9781118041581

Linear Programs 717

Obviously, large values of F and D (i.e., greater spending on the programs) will

make it easier to meet the dual improvement goals, but the point is to do it at min-

imumcost. When it comes to cost contours, the object is to get to the lowest one

(i.e., the one farthest to the southwest) while meeting both goals. Figure 17.3

shows the relevant part of the “least-cost” contour. Note that it touches the fea-

sible region at point Z, the corner formed by the binding oxygen and chlorine

constraints. The precise amounts to spend on each program are found by solving

the equations 3D F 6 and 10D 20F 70. The solution D 1 and F  3

is the result.^4 In short, $1 million and $3 million should be spent on the respec-

tive programs. The least-cost total outlay is $4 million.

ALGEBRAIC SOLUTIONS The mathematics for solving small-scale linear pro-

grams involves two main steps: (1) identifying the correct set of simultaneous

equations and (2) solving these equations for the optimal values of the decision

variables. In the preceding example we used simple graphics to solve the first

step. (Caution: We cannot simply assume certain constraints will be binding

and go ahead and solve them. In the computer example, there are five inequal-

ities, including the nonnegativity constraints, only two of which are binding

equalities in the optimal solution. Without a graph or other analysis, which two

constraints will be binding is a pure guess.)

Once you understand the general points of the graphical method, you may

be interested in a quick way of finding the optimal corner. The method relies

on a comparison of slopes:

The optimal corner is formed by the constraints whose slopes most closely bracket

the slope of the objective function.

To apply this rule, we simply note the slope of each constraint from the graph.

In the computer problem, the slopes of the labor constraint, hard-disk con-

straint, and DVD constraint are 1, 2, and , respectively. The slope of the

contribution contour is 5/3, and this falls between the first two slopes.

Accordingly, the optimal output in Figure 17.2 occurs at point C, where the

labor and hard-disk constraints are binding. Similarly, in the regulator’s prob-

lem (Figure 17.3), point Z is optimal because the slope of the cost contour

( 1) falls between the slope of the oxygen constraint ( 3) and the chlorine

constraint ( 1/2).

(^4) Recall that there are two equivalent ways to solve simultaneous equations. The first method is by
substitution.For instance, in the regulator’s problem, we transform the equation 3D F 6 to the
form F  6 3D. Then we insert this expression for F into the second equation, 10D 20F 70.
We are left with one equation in one unknown: 10D 20(6 3D) 70. The solution is D 1.
Putting this value back into the first equation, we find F  6 (3)(1) 3. The second method is
by elimination.It is easiest to eliminate F by multiplying both sides of the first equation by 20 to
obtain 60D 20F 120. Then we subtract the second equation from this expression. Note that
20F in each equation cancels out, leaving 60D 10D  120 70; this implies D 1 and F 3.
Either method works equally well.
c17LinearProgramming.qxd 9/26/11 11:05 AM Page 717