9781118041581

Formulation and Computer Solution for Larger LP Problems 729

Returning to the mathematical formulation, we know from the graph that

x 3 0 and that

because both constraints are binding. Solving these equations simultaneously,

we find x 1 20, x 2 50, and maximum total output is 70.

PRODUCTION AT MINIMUM COST Suppose that we have the same produc-

tion processes as in the previous example, but inputs are variable rather than

fixed. In particular, the firm can rent machine time at a price of $8 per machine-

hour and can hire labor at a wage of $10 per hour. How should the firm use the

available processes to produce 40 units of output at minimum cost?

To find the optimal decision, we must formulate correctly the objective

function. The cost of producing a single unit via process 1 is (.5)($8) 

(2)($10) $24. (The cost is simply the sum of inputs used multiplied by their

prices.) The total input costs per unit for processes 2 and 3 come to $18 and

$21, respectively. Therefore, the formulation is

Minimize:

Subject to:.

All decision variables are nonnegative.

This problem is simple enough that it can be solved by just looking at it. To

minimize cost, the firm should produce exclusively via process 2, because it has

the lowest cost per unit ($18). Thus, the optimal production plan is x 2 40,

x 1 x 3 0.

REMARK The solution to the minimum-cost problem features a single bind-

ing constraint. Furthermore, the optimal production plan uses only a single

process. In the solution to the maximum-output problem, two of the three con-

straints are binding. The optimal production plan involves two processes

(whose values are found by solving the two binding constraints simultaneously).

The findings for these examples illustrate a general result:

In any linear programming problem, the number of decision variables that take

nonzero values in the optimal solution always is equal to the number of binding

constraints.

Therefore, in decision problems in which the number of decision variables

(call this number N) greatly exceeds the number of constraints (call this M),

at least N M decision variables will be zero in the optimal solution.

x 1 x 2 x 3  40

24x 1 18x 2 21x 3

2x 1 x 2  90

.5x 1 x 2  60

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