9781118041581

Formulation and Computer Solution for Larger LP Problems 727

amounts of labor and capital—two inputs in fixed supply. The firm has 60

machine-hours and 90 labor-hours per day to devote to the product. The

processes require the following inputs to produce one unit of output.

Process 1 Process 2 Process 3

Machine-hours .5 1 2

Labor-hours 21. 5

The firm seeks to maximize output by using the processes singly or in combi-

nation. How much output should it produce, and by which processes?

The LP formulation is as follows:

Maximize:

Subject to:

.

All decision variables are nonnegative.

The decision variables (x 1 , x 2 ,and x 3 ) denote the quantities of output produced

via each process. The firm wishes to maximize total output, the sum of the out-

puts produced by each process subject to the constraints that the total amounts

of labor and capital used to produce total output cannot exceed available sup-

plies of inputs.

This problem involves two constraints (plus three nonnegativity con-

straints) and three decision variables. Here, the previous graphical method will

not work because there are more decision variables than axes of the graph.

However, we can find the solution graphing the two constraintson the axes

instead. The method is shown in Figure 17.6, where available input supplies—

rather than decision variables—are placed on the axes. The rectangle OLMK

represents the feasible region, whose sides indicate the available amounts of

capital and labor (60 and 90 units, respectively).

The next step is to graph a contour of the objective function. Figure 17.6

shows two such contours. The inner contour shows combinations of inputs nec-

essary to produce 40 units of output; the outer contour corresponds to pro-

ducing 70 units. For instance, if the firm seeks to produce 40 units, it can do so

via process 1, using 20 machine-hours and 80 labor-hours; this input combina-

tion is shown as point A in the figure. Alternatively, it could use process 2, using

40 units of each input (point B), or process 3, using 80 and 20 units (point C).

To complete the production contour we draw the segments connecting

these points. For instance, the firm could produce the 40 units using a combi-

nation of processes 1 and 2. Consider the outputs x 1 20, x 2 20, and x 3 0.

Total production is 40 units, using a total of 10  20 30 machine-hours and

2x 1 x 2 .5x 3  90

.5x 1 x 2 2x 3  60

x 1 x 2 x 3

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