9781118041581

FORMULATION ISSUES In some cases, LP problems have no solution or the

solution is unbounded. Consider the following formulation:

Maximize:

Subject to:

The difficulty here lies in the constraints. It is impossible to find values of the

decision variables that simultaneously satisfy both inequalities. (Graph the con-

straints to confirm this.) In short, the problem itself is infeasible. It lacks a fea-

sible region and, therefore, has no possibility of an optimal solution.^5

A different formulation difficulty arises if we make a slight modification in

the preceding example. Suppose that the variable y is omitted in the first con-

straint so that the inequality reads x 12. The new problem has a feasible

region—in fact, too large a region. The feasible region consists of all points to

the left of the vertical line x 12 and above the downward-sloping line x y 

15. Now the feasible region is unbounded; it extends vertically indefinitely.
    Clearly, we can make the value of the objective function as large as we like by
    making y as large as possible—all the while keeping x below 12. This linear
    program has an unbounded solution, which tells us that we have poorly for-
    mulated the problem. After all, in the real world, no firm has the opportunity
    to make an infinite profit. Somehow we have omitted the real constraints that
    limit the firm’s profitability.

SENSITIVITY ANALYSIS AND SHADOW PRICES

The solution of the basic linear program provides management with its optimal

decision. The solution is also the starting point for considering a range of

related decisions and what-if questions. For instance, managers of the com-

puter firm recognize that changing market prices are a fact of life in the PC

industry. How might the firm change its production mix in response to changes

in product prices? As a second example, the firm might consider increasing

(at a cost) one or more of its production capacities (labor or hard-drive capac-

ity, for instance). How much would such an increase in capacity be worth, and

would it be worth the cost?

Sensitivity analysis is important in almost all decision contexts, but espe-

cially so in LP problems. As we shall see, analysts use computers to solve almost

all medium- and large-scale LP problems. Standard computer output provides

xy15.

x2y 12

3xy

718 Chapter 17 Linear Programming

(^5) This kind of infeasibility can arise quite naturally. In this problem, for instance, let the decision
variables denote the quantity of two products. Total production is limited due to fixed capacity
(the first constraint). At the same time, the firm has contracted to deliver a minimum of 15 total
units to a buyer (the second constraint). Here, there is no solution, because the firm has con-
tracted to deliver more than it possibly can supply.
c17LinearProgramming.qxd 9/26/11 11:05 AM Page 718