summary and PowerPoint2

untitled.pdf

Home >Engineering homework help >summary and PowerPoint2

How to Analyze the Results of Linear Programs—Part 2: Price Interpretation

HARVEY J. GREENBERG Mathematics Department University of Colorado at Deliver POBoxU3364 Denver, Colorado 80217-3364

In the second part of a four-part series, I consider an exercise in analysis that arises in many applications: Why is the price of (some co77imodityy equal to (whatever its solution valuey? The ability to interpret dual prices in a linear programming solution is part of economic analysis, and the mathematical basis is as old as linear programming, itself. New approaches, however, go beyond the usual duality arguments in answering this ques- tion in more practical terms. One of these new approaches is path tracing, which seeks a portion of the linear program that accounts for the row's price by activity costs from sources to the row. In some cases this is a simple path in a network prob- lem. More generally, in ordinary network terms, it can be a tree or involve embedded cycles, but it is regarded as a path in hypergraph terms.

T his paper is concerned with interpret- and partly because of its simplicity. 1 shall ing dual prices in an optima! instance show how we can go deeper into explain-

of a linear program. 1 use terms and con- ing why a price has a particular value at cepts that were introduced in Part 1 optimality. Then, I shall consider another [Greenberg 1993a] of this series. problem, witb which I shall illustrate a

I shall begin with the transportation path tracing procedure. After stepping problem, partly because of its familiarity through the analysis as an LP expert, I CDpyn^hl "- iyy3, Thf Insliluli' of Mdn^gi'mL-nt SCKncvs PROGRAMMING—LINLAR OO91-2lO2/')3/2305/0O97$(ll.25 This paper was refereed.

INTERFACES 23: 5 September-October 1993 {pp. 97-114)

GREENBERG

shall demonstrate automatic interpretation with the ANALYZE rule-base [Greenberg 1988, 1993b]. Transportation Problem

1 start with the transportation problem. We are given a set of suppliers, which t denote by / in the set [ 1, 2, . . . , m}, and a set of consumers, which I denote by / in the set {I, 2, . . . , n\. The /-th supplier has s, units, and the j-th consumer demands d, units. Assume total supply is at least as great as total demand: 2, s, > Z,tf,. The cost to ship one unit from the /-th supplier to the ;'-th consumer is c,,, and assume total cost is a linear function of shipment levels. An algebraic formulation is given by

minimize

subject to

X > 0;

2 -v,y < S; for / - 1, . . . , m; I

2 y:,, ^ df for ; =̂ 1, . . . , n.

A solution to an instance of the trans- portation problem not only gives optimal levels of flows, x*, but also gives dual prices associated with the constraints. Let us interpret these prices with a few basic properties, then I shall consider numerical examples to go deeper into price interpre- tation.

Let Xi be the /-th supplier price, and let TT, be the/-th consumer price. Mathemati- cally, the dual linear program is given by

maximize

subject to

X, IT > 0 ; TT, - X, < c,i

for i = 1, . . . , m, j = 1, . . . , n.

The dual constraint says, in ettect, that no consumer will pay more than the deliv- ered price. The delivered price from the /-th supplier to the y-th consumer is X, + c,,—that is, the sum of the /-th supplier's price and the transportation cost. This con- straint represents a behavioral condition of a competitive market It is useful to think of a bidding system, where the/-th con- sumer will buy from the lowest bidder.

From this perspective, an optimal solu- tion has the property that if the /-th con- sumer buys from the /-th supplier, the con- sumer's price equals the delivered price. Mathematically, this is known as comple- mentary slackness: if A* > 0, then x, ^ Xj + c,/. {See Greenberg and Murphy [1985] for a way to see the linear program as a model of market equilibrium conditions.)

To see how to use this property, con- sider the following implications: (1) Two suppliers that ship to a common consumer differ in their prices precisely by the difference in their transportation costs—that is, X, - X( ^ c,, - Ci,j.

This follows because the consumer's price equals the delivered price of the /-th sup- plier and of the ^-th supplier: x* > 0 and xl > 0 i m p l y Xi + c^, ^ ir, = X, + c,,.

(2) Two consumers that receive from a

INTERFACES 23:5 98

LINEAR PROGRAMS

common supplier differ in their prices pre-

cisely by the difference in their transporta-

tion costs—that is, TTJ - TT̂ ^ c,̂ - c,^.

TTi

C,i ^>rii)

K (0

This property can be used to aid model validation in the following sense. If this price relation does not make sense for an application, the network model is not valid—that is, it does not accurately model what it is intended to represent. It may be, for example, that shipments are con- strained by some fixed shares among sup- pliers and consumers. In general, when we establish a property of a formulation, it is basic science to ask whether this property is valid. If not, the formulation is not valid.

The graph depiction of these two prop- Supply

erties is the row digraph of the linear pro- gram, and I used it to explain a coal model to a consortium formed by Chase Econo- metrics. Once the coal-producing compa- nies saw this property, they immediately raised the validity question. The supply prices in the coal model are mine-mouth prices, and the company representatives know that they are not related simply by differential transportation costs. That ob- servation revealed an erroneous assump- tion, which was fixed by incorporating fixed shares of movements from mines to markets. This revision of the transportation activity structure still represents price rela- tions, but now each dual price relation in- volves more than one supply price and one market price.

Now let us consider some numerical ex- amples. Rubin and Wagner [1990| have il- lustrated some interesting interpretations of optimal solutions. Figure 1 shows one of their examples that illustrates unique dual

Supplier Prices .

Demand: Consumer Prices:

(0)

(10)

(5)

(10)

(0)

io 50

10 55

15 65

10 75

Figure 1: In this example with alternative optimal shipping patterns and unique prices [Rubin and Wagner 1990], each of the 2 X 3 cells corresponds to the link from the associated supplier to the associated consumer. The number boxed in the Northwest corner of each cell is the shipping cost. The number in the Southeast corner of each cell is the level of shipment, above which is an alternative optimal shipment in parentheses.

September-October 1993 99

GREENBERG

prices with alternative shipment patterns. For example, in the first optimal solu-

tion, the first supplier sends 10 units to consumer 1, five units to consumer 2, and none to consumer 3. His total supply is 20, so he has five units of surplus (that is, not shipped). In the second solution, the first supplier sends none to consumer 1, five to consumer 2, and 10 to consumer 3. His surplus is still five units.

Because the first supplier has surplus, the price is zero because that is the value of adding one unit or taking one away. If the first supplier has 21 (or a million) units, only 15 would still be used, as they are in this optimal solution, so there is no value to having extra units. Similarly, if a unit is taken away, so the first supplier has only 19 units, it also would not change the so- lution. No value is lost, hence the zero price whenever there is surplus.

Now 1 shall interpret the $50 price of the second supplier. Suppose the supplier can obtain one more unit (21 instead of 20). What would it be worth? Using the first optimal solution, he could send that one unit to the first consumer who then would decrease his purchase from the first supplier. The first consumer currently pays $55 {= Xl + fl, = 0 + 55). Subtracting the transportation cost, C21 ^ 5- the second supplier could ask any price up to $50 and sell this unit to the first consumer. The so- lution price, X2 "= 50, reflects this.

Consumer 2 is paying $65. His pur- chases are split between the two suppliers, and their prices differ by their transporta- tion costs: X] — Xj ^ C]3 — C22 ^ 6 5 — 15 = 50. Since Xi = 0, we must have X2 ^ 50, as shown.

Consumer 3 is already buying all of his

units from supplier 2, at the delivered price of $75 ($50 supply price -I- $25 transporta- tion cost). We can, however, ask the re- lated question, "What if supplier 2 loses one unit, so he has only 19 to distribute in- stead of 20?" There are two possibilities to consider: (1) Supplier 2 reduces sales to consumer 3, causing consumer 3 to buy one unit from supplier I (who has surplus units to sell). (2) Supplier 2 reduces sales to consumer 2, causing consumer 2 to buy an additional unit from supplier 1. j

In case 1, consumer 3 still pays $75 since that is his delivered price from supplier 1. In case 2, consumer 2 still pays $65 since that is his delivered price from supplier 1. In both cases, the loss or gain of one unit of supply from supplier 2 results in a $50 loss or gain, respectively, and the ship- ments adjust accordingly.

Now consider a more complex situation, in which there are alternative dual prices (for a uniquely optimal shipping pattern). Figure 2 shows such a case, and Figure 3 gives a graphic view.

Let us begin the price interpretations with the supply side.

(1) The 0 price of supplier 1 means added supply has no value. He already has surplus supply in the optimal flow, so more would just add to the surplus. Fur- ther, loss of one unit has no value as well since it is not taken away from any con- sumer.

(2) If supplier 2 lost a unit of supply (As2 ^ ~1), the optimal flows adjust by having either consumer 2 or consumer 3 buy the missing unit from supplier 1. The least costly choice is reasoned as follows. If consumer 2 is chosen, ACost ^ 6 5 - 1 5

INTERFACES 23:5 100

LINEAR PROGRAMS

Supply

Supplier Prices

0 (0)

50 (45)

Demand: Consumer Prices;

10 10 10 (55)55 (60)65 (70)75

Figure 2: In this example, there is a unique optimal shipping pattern and alternative dual prices [Rubin and Wagner 1990].

= 50. If consumer 3 is chosen, ACost ̂ 80 - 25 ^ 55. The best choice, therefore, is to choose consumer 2. The net change in cost is ACost = -50AS2 (for Asa < 0).

Now suppose supplier 2 obtains one more unit of supply (AS2 ^ 1). He could send it to consumer 1, displacing one of the units consumer 1 currently obtains from supplier 1. The change in total cost is ACost - 10 - 55 - -45As.. This is the

meaning of the $45 supplier price in the alternative solution. Summarizing, the $50 represents the rate at which the minimum cost increases if the supply is decreased; and, the $45 represents the rate at which the minimum cost decreases if the supply is increased. This asymmetry in the rates arises because the response to a loss is dif- ferent from the response to a gain in the amount of supply for supplier 2.

Surplus = 10

= 10@ $55 10

Price = 0 Price = 55

= 10 @ $15

= 10 @ $25 Price = 65

(D3) Price = 50 Price = 75

Figure 3: A graphic view of optimal flows shows two components in the solution.

September-October 1993 101

GREENBERG

Now consider the demand side. (1) The $55 price of consumer 1 is the

marginal cost of shipping with the optimal pattern. He buys from supplier 1 at $55, and he would continue to do so if his de- mand increased or decreased one unit. The total cost then changes at the rate of $55 per unit of demand change: ACost = 55 Ad,.

(2) If the demand increased a bit {Ad2 > 0), consumer 2 would have to buy from supplier 1 at a cost of $65 per unit. This is the meaning of the consumer price: ACost = 65 At/2- There is, however, an alternative to consider. Suppose the added demand is satisfied by supplier 2, at a cost of only $15. Then, this would take away from consumer 3, whose demand must be made up with his purchase from supplier 1. The net effect, for Arfj = 1, is ACost - 15 - 25 -I- 80 = 70. It is therefore better to choose the first adjustment, giving the least in- crease in total cost.

Now what accounts for the $60 price in the alternative solution? If the demand of consumer 2 is decreased (AJ; < 0), not only do we save the $15, but also that unit of supply can be shipped to consumer 1, displacing one of the units currently shipped by supplier 1, at a net savings of $10 - $55, or -$45. Adding this savings to the $15 unspent by consumer 2, the net effect is ACost = 60 Ai/j (for Adj < 0). Summarizing, the $65 represents the rate at which the min-cost increases if demand is increased; and, the $60 represents the rate at which the min-cost decreases if the demand is decreased. The asymmetry is again due to different responses, depend- ing upon whether the demand is increased or decreased.

(3) The alternative prices for demand in the third market have an asymmetry simi- lar to that for the second market. If the de- mand is increased a bit {Ad^ > 0), con- sumer 3 would buy from supplier 2 at a unit cost uf $25. Supplier 2, however, is using all of his supply, so he must decrease shipment to market 2. This reduces the net change in cost by $15, but then consumer 2 must buy the unit from supplier 1 at a cost of $65. The net change in flows to ac- commodate this increase in demand 3 is thus 25 - 15 + 65, which equals the con- sumer 3 price, $75.

On the other hand, if the demand de- creases a bit {Ad-i < 0), consumer 3 reduces his purchase from supplier 2. This not only saves the $25 shipping cost, but also makes another unit available for supplier 2 to sell to market 1. Doing so saves $45 {the difference between the $10 from supplier 2 to market 1 and the $55 from supplier 1 to market 1). The net effect, therefore, is the sum of the direct savings ($25) plus the savings from displacement ($45) for a total savings of $70, which is the alternative dual price. Reduced Costs and Economic Rents

ln this section, I describe the notion of economic rent and its connection with dual prices. Basically, an economic rent is the difference between a market clearing price (under perfect competition) and a selling price. Imagine, for example, two sources of supply, A and B, in increasing order of cost. Suppose the less expensive A has lim- ited capacity, and the demand requires some supply from source B. The marginal price is the cost of supplying B, say %h, but this is the (only) market price. This means that while the supplier would be content to

INTERFACES 23:5 102

LINEAR PROGRAMS

sell A at $fl (where a < b), he actually re- ceives $b fur all goods brought to market. He is said to receive an economic rent of $(/' - fl).

Figure 4 makes this concrete. There is one supplier, labelled s, that is much farther from the n:\arket than the other suppliers, shown with small boxes. Sup- pose each supplier's production cost is $1, and each of the nearby suppliers have zero transportation cost while the distant sup- plier has a transportation cost of $9. If the market demand is less than the total quan- tity that the nearby suppliers can supply, the market price is only $1, and the distant supplier ships nothing. Suppose, however, the nearby suppliers can provide only 100 units, but the market demand is 110 units. Then, the distant supplier ships 10 units, and the market price is $10 ($1 production cost + $9 transportation cost). The nearby suppliers also receive the market price of $10, so they receive an economic rent of $9.

In general, we have the following terms: Delivered cost ^ Production cost

+ Transportation cost. Marginal price = Delivered cost

+ Economic Rent. To see this connection with LP, consider Figure 5, which shows a price-quantity supply function. The first step represents the nearby supply of 100 units at $1; the second step represents the distant supplier

D D

D Figure 4: An economic rent arises when market demands require shipments from a distant supplier.

Price

10-1-

s Market

100 150 Quantity

Minimize COST subject to: COST = P1 + 10*P2 SUPPLY = P1 + P 2 - M = 0 DEMAND = M = 110 0 < PI < 100, 0 < P2 < 50

Figure 5: An LP can represent a step function of supply price quantity with an activity per step.

of another 50 units at $10. Activity PI is the production from the

nearby suppliers; its bound is the first step's width (100), and its cost coefficient is the step's height ($1). Activity P2 is the production from the distant supplier; its bound is the second step's width (50), and its cost coefficient is the step's height ($10). Activity M logically moves all production from the SUPPLY row to the DEMAND row (actual transportation costs are ab- sorbed in the production activities). The DEMAND equation requires the level of M to be the demand of 110 units. This causes the optimal level of PI to be at its bound of 100 and activity P2 to be basic with a production level of 10 units. The cost of P2 sets the marginal price of the SUPPLY row to be $10, and the reduced cost of PI is —9, which represents an economic rent of $9 to the nearby suppliers.

If, instead of a demand of 110 units, the demand is less than 100 units, activity P2 is nonbasic at zero level with a reduced cost of 9, while the level of PI equals the

September-October 1993 103

GREENBERG

demand and PI sets the SUPPLY price at $1. In this case, the meaning of the re- duced cost of P2, which is 9, is the differ- ence between the distant supplier's deliv- ered cost to market ($10) and the market price ($1).

A special demand value is 100 units, which is the capacity of the nearby sup- pliers. In this case, there are alternative dual solutions (with a unique shipment of PI = M = 100 and P2 - 0). The first solu- tion is with PI in the basis at its upper bound value, and the dual price is $1 (of both SUPPLY and DEMAND rows, equal- ity implied by the zero cost of activity M). The second solution is with P2 in the basis at zero level, and the dual price is $10.

The first solution gives the rate at which the min-cost changes with respect to a de- crease in demand, say to 99. That is, the cost decreases at $1 per decrease in de- mand, which is the savings from the asso- ciated level of PI. The second solution gives the rate at which the min-cost changes with respect to an increase in de- mand, say to 101. That is, the cost in- creases at $10 per increase in demand, which is the cost from the associated level of P2. These simple examples form the ba- sis for what I describe in the next section. Another Problem

The foregoing examples give us a start- ing point for going deeper into price inter- pretation (see, also, [Akgul 1984; Gal 1979; Greenberg 1986; and Ho and Smith 1987]). Now consider another problem, where I shall show how to use path tracing for problems too large to see on one screen. The figures show the information, as obtained from ANALYZE [Greenberg 1983, 1987, 1988, 1992a,b, 1993b] (com-

mands used are suppressed). I begin to gain an understanding of the

linear program by seeing its syntax. Figure 6 gives an overview of a linear program we shall consider, called WOODNET. First, it displays the schema, which shows three activity classes and two row classes (and the objective row, named COST). Row class S balances supplies, and row class D balances demands. The domain informa- tion gives the meaning of each of the three sets in the model. Then, it displays the translations of the row and column classes.

In this formulation, all right-hand sides are zero. Supply limits are represented by upper bounds on the supply activity levels, and demands are fixed values of demand activity levels. This is an equivalent model of the transportation problem. Each cell entry gives the range of nonzeroes in this instance, where a blank means that there are no nonzero coefficients in the subma- trix defined by the row and column classes. For example, the supply activities (whose names begin with S) do not inter- sect any of the demand balance rows (whose names begin with D). !l

The analysis problem is to interpret the demand prices in the solution. 1 shall first go through the analysis to arrive at what we can regard as a mathematical solution. Then, we have the second phase of putting the response into English, which uses the syntax information, summarized in Fig- ure 6.

Figure 7 displays the demand prices. The first demand price we want to explain is the $73 for mahogany (MO in the set of materials, MT) in Chicago (CH in the set of demand regions, DR). The name of the as- sociated demand balance row is DMOCH.

INTERFACES 23:5 104

LINEAR PROGRAMS

S(MT,SR) D(MT.DR) COST :L0 :UP DOMAIN

MT SR DR

S(MT.SR) 1

10760 0 57* INFORMATION materi al 1ocation 1ocati on

T(MT -1 1 5720 0 *

BLOCK SCHEMA .SR.DR) D(MT.DR}

-1

57100

HOMOGEN = 0 = 0 ...MIN

S balances supply of some material in

D balances demand of some material in

Row syntax has 2 classes A row that begins with

some location. A row that begins with

some location. Column syntax has 3 classes

A column that begins with S supplies some material at some location.

A column that begins with T transports some location to some location.

A column that begins with D demands some 1ocation.

some material from

material at some

Figure 6: An overview of the WOODNET syntax gives insights into the LP structure.

From the schema, we can view the initial portion of the fundamental digraph, as fol- lows.

(DMOCH) -* [DMOCH] -* Price - 73

We want to obtain a delivery path that accounts not only for the flow from some source{s) to satisfy the demand, but also for the price of $73. We begin our analysis by finding all the basic columns that inter- sect row DMOCH in order to find the link(s) in the delivery path. Doing so adds one more link, as follows.

[TMOSECH] - (DMOCH) - [DMOCH] -

We have found a basic transportation activity, namely TMOSECH, which trans-

ports mahogany to Chicago, and we must continue the trace back to the source. Equivalently, we want to expand the sub- matrix, which contains the demand row (DMOCH) and its adjacent activities, to bring in other rows that intersect the trans-

MT MO OK PI WA

Pri

CH 73 60 22 78

ces

DE 75 69 22 68

of D(

LA 68 62 17 75

MT.DR

SE 71 65 20 78

)

SF 65 60 24 70

Figure 7: The table display of WOODNFT de- mand prices gives a quick view of what they are, by material (MT) and location (DR).

September-October 1993 105

GREENBERG

COST DMOCH SMOSE

D M rl

0 c H 1

—

s M rl 0s E 1

T M rl

0 s E C H + =

— —

MIN 0 0

Figure 8: After completing the path trace, we can picture the submatrix to see how mahogany is delivered to Chicago.

portation column. This, in turn, can lead to bringing in other rows and columns, pref- erably basic, until we eventually reach a complete submatrix^that is, with each equation balanced by positive and negative coefficients. Because the LP is feasible, a balance must be achievable in order to sat-

isfy the (homogeneous) balance equations. The result of the path trace is the subma- trix pictured in Figure 8.

The 3 X 3 submatrix shows the COST and a flow from the supply activity SMOSEl, shipped by the transportation activity TMOSECH, and finally consumed by the demand activity, DMOCH 1. The picture is useful for seeing sign patterns and having a quick look at a submatrix. Figure 9 shows the graph-based view of the delivery path in the fundamental di- graph.

To complete the interpretation, we re- quire additional information. Figure 10 lists the equations in the submatrix, so we can use the COST values, and it displays the three columns in the submatrix, so we can see their levels and bounds. The demand activity (namely, DMOCH 1) is at its fixed level. The associated transportation activity {namely, TMOSECH) is thus at this same level (25), but the supply activity (SMOSEl) level is 75 because it is used to

[SMOSE1]—•(SMOSE)—•[TMOSECH]—•{DMOCH)—•[DMOCH]- Figure 9: The final portion of the fundamental digraph is the delivery path of mahogany lo Chicago.

MIN 0 0

COL

DMOCHl SMOSEl TMOSECH

COST DMOCH SMOSE

STAT

L B B

= 55 SMOSEl + 18 TMOSECH =-DMOCHl + = SMOSEl -

LEVEL

25 75 25

000 000 000

TMOSECH TMOSECH

LO_BOUND UP

25.000 0 0

_BOUND

25.000 * *

PRICE

73 G 0

(D)

.000

Figure 10: To get the numbers, we can list the submatrix equations and display its columns, which are in the delivery path.

INTERFACES 23:5 106

LINEAR PROGRAMS

75 @$55 Seattle

25@$18 Chicago

25 @0

D = 0 P = 55 D = 0 P = 73 D - 7 3 Figure 11: A flow diagram corresponding to the submatrix in Figure 10 gives visual insight into the price relations through activities in the delivery path.

satisfy other demands. We are now in a position to give an al-

gebraic answer to this exercise. The trace, working back from the initial demand row, reveals a path from supply to demand (Figure 11). The levels of the activities in this path can be perturbed to accommo- date a change in the right-hand side of the demand row DMOCH {equivalently, the fixed level of the associated demand activ- ity, DMOCHl). The $73 is the total unit cost of this perturbation. The last listing (compare Figure 10) shows that the total (input) cost is $55 for the supply activity (SMOSEl) and $18 for the transportation activity {TMOSECH). Because there are no loss or gain factors {that is, the body coeffi- cients are ±1), the actual delivered cost is $55 + $18, or $73.

It is not usually the case that the deliv- ered cost equals the marginal price, owing to economic rents to lower cost suppliers sending all of their supply. We next ana- lyze such a case by performing the same exercise for row DMOLA. The problem is to explain the $68 (compare Figure 7) in terms of the model s structure and the par- ticular data. Figure 12 presents the result of tracing activities, but now a nonbasic activity plays an important role in finishing the analysis.

In Figure 13 we see that the supply ac- tivity (SMOSFl) is at its upper bound (STAT - U), which is 30. Upon listing the COST row, we see that its delivered cost is

only $50 ($45 for supply activity SMOSFl and $5 for transportation activity TMOSFLA). The difference of $50 and $68 is what we seek to explain. This is pre- cisely the reduced cost of the capacitated supply activity, which is displayed as - 1 8 , which represents an economic rent of $18. Because this nonbasic reduced cost is non- zero, the supply bound is binding, so the $18 must be due to the value of the capac- ity in fulfilling some other demand{s). That is the story we want to develop.

We must now trace the flow out of this supplier to explain its reduced cost. We be- gin to explain the $18 difference by seeing which consumers receive the other 10 units of supply from San Francisco. Figure 14 shows the result of listing the associated

COST DMOLA SMOSF

D M rl

0 L A 1

—

S M rl

0s F 1

T M rl 0s

Ll_

L A + - + = — =

MIN 0 0

Figure 12: After the price trace for row DMOLA is complete, we can picture the sub- matrix to see the relevant portion of the LP.

September-October 1993 107

GREENBERG

supply row (SMOSF) with the columns of not only basic activities, but also of all col- umns with zero reduced cost. (This distinc- tion will become apparent, as our problem needs to include dual degeneracy when tracing prices.)

First, the submatrix that contains row SMOSF and its adjacent columns that have zero reduced cost are defined. The result is the following 1 X 3 system.

0 - SMOSF = -TMOSFDE

- TMOSFLA - TMOSFSE.

We then apply the trace procedure to this 1 X 3 submatrix to balance its flows with price-setting activities, and Figure 14 pic- tures the resulting submatrix.

We now want to see the flows and the reduced costs on the activities in this sub- matrix. To do so, we display the rows and columns, shown in Figure 15. Our story starts to take shape, as the San Francisco supplier ships to other places.

Now we want to see the costs of the submatrix columns:

COST = 45 SMOSFl + 12 TMOSFDE

+ 5 TMOSFLA -I- 8 TMOSFSE

This tells us the delivered costs to Denver, Los Angeles, and Seattle. That is, we al- ready know the supply cost in San Fran- cisco is $45, and the trace told us that there are three activities with zero reduced cost. The first is TMOSFDE, which trans- ports mahogany from San Francisco to Denver at a unit cost of $12. The second is TMOSFLA, which transports mahogany from San Francisco to Los Angeles at a unit cost of $5, which is the one we al- ready saw when we started this exercise. The third is TMOSFSE, which transports mahogany from San Francisco to Seattle at a unit cost of $8. '

Notice that the consumer prices differ by their transportation costs since they receive their supply from (he same supplier. For

COL

DMOLAl SMOSFl TMOSFLA

ROW

STAT

L U B

STAT

COST B DMOLA L SMOSF L

MIN COST = 45

LEVEL (X)

20.000 30.000 20.000

LEVEL (Y)

25135.000 0 0

SMOSFl + 5

LO_BOUND

20.000 0 0

LO_BOUND

0 0

TMOSFLA

UP_BOUND

20.000 30.000 *

UP_BOUND

* 0 0

PRICE (D)

68.000 -18.000

PRICE (P)

-1.0 68.000 63.000

Figure 13: We use the display of columns and rows in the path to see solution values and bounds. We then list the COST Row to see supply and transportation costs. Because the delivered cost is only $50, more analysis is needed to explain the marginal price of $68.

INTERFACES 23:5 108

LINEAR PROGRAMS

COST DMODE DMOLA DMOSE SMOSF

D M 0 D E 1

D M 0 L A 1

D M 0 S E 1

S M 0 S E 1

T M 0 S

Ll_

D E +

T M 0 S E L A +

T M 0 S F S E -t-

= MIN = 0 = 0 - 0 = 0

Figure 14; Afler tracing the margin-setting flows from the San Francisco supplier of mahogany, we can picture the resulting submatrix.

example, the transportation costs from San Francisco to Denver and from San Fran- cisco to Los AngL'les are $12 and $5, re- spectively. Their consumer prices must

therefore differ by $7. From Figure 15, the consumer prices are $75 and $68, respec- tively, which do indeed differ by $7. Simi- larly, note that the $71 consumer price in Seattle differs from these by transportation cost differences: $4 from Denver's price and $3 from Los Angeles' price.

From Figure 16, we see that only two of these margin-setting flows—that is, the ac- tivities with zero reduced cost—are posi- tive. The status uf activity TMOSFDH is basic, but its level is zero. We could ex- plore the link with Seattle, but it is the de- generacy of the flow to Denver that holds the key for the answer we seek. Figure 16 pictures the submatrix with the associated demand row (DMODE) and all columns whose activity level is positive. We then apply the path-tracing procedure to obtain the answer to the question, "Where does Denver gets its mahogany?"

ROW

DMODE DMOLA DMOSE SMOSF

COL

DMODEl DMOLAl DMOSEl SMOSFl TMOSFDE TMOSFLA TMOSFSE

STAT

L L L L

STAT

L L L U B B B

LEVEL (Y)

0 0 0 0

LEVEL (X)

20.000 20.000 10.000 30.000 0

20.000 10.000

LO_BOUND

0 0 0 0

LO_BOUND

20.000 20.000 10.000 0 0 0 0

UP_BOUND

0 0 0 0

UP_BOUND

20. 20. 10. 30. * * *

000 000 000 000

PRICE (P)

75.000 68.000 71.000 63.000

PRICE (D)

75.000 68.000 71.000

-18.000 0 0 0

Figure 15: Displaying the rows and columns in the submatrix of Figure 14 gives us the prices and activity levels, respectively.

September-October 1993 109

GREENBERG

D M rl 0 D E 1

DMODE -

T M n 0 s E D

LLJ

+ - 0

Figure 16: We initialize the submatrix to trace the price of mahogany in Denver (that is, the price of row DMODE).

Skipping the new picture after the trace, we immediately list the costs of the sub- matrix columns:

COST - 55 SMOSEl + 20 TMOSEDE.

This tells us two things. First, the mahog- any comes from only one supplier, namely Seattle. Second, the delivered cost is $75 ($55 supply, which is activity SMOSEl, and $20 transportation, which is TMOSEDE). This is like the first case (for the price of row DMOCH): Denver re- ceives all of its mahogany from a single supplier, and there are no binding capacity constraints in the flow path, so the mar- ginal price of row DMODE is its delivered cost of $75.

Now we can put the pieces together and construct the analysis story. Figure 17 shows a flow graph that describes the situ- ation. The San Francisco supplier sends to Los Angeles (where we started) and to Seattle. The latter flow turns out to be ir- relevant to our original exercise of explain- ing the $68 marginal price for row DMOLA because it is not the cause of the $18 economic rent, which shows up as the

- 1 8 reduced cost of the supply activity (SMOSFl). The margin-setting link is the one to Denver, even though there is no positive flow across that arc (activity TMOSFDE).

The story is that the consumer price for mahogany in Denver, which is P = 75 for row DMODE, is determined as in the first case: it receives its shipment from another supplier, namely from Seattle (via the transportation activity TMOSEDE), with the delivered cost of $75. The presence of the link from San Francisco to Denver, however, allows displacement if the capac- ity of the San Francisco supplier would in- crease. The (actual) cost of shipping from San Francisco to Denver is $57 ($45 supply + $12 transportation), so the savings from displacement would be $18. This is what determined the economic rent we have sought to explain.

There are a number of ways to compose the final explanation. One is that the con- sumer's price of mahogany in Los Angeles ($68) is due to demand in Denver and the limited supply in San Francisco. Even if we reduce the production cost and the trans- portation cost from San Francisco to Los Angeles, the price would still be $68 due to the market pressure resulting from lim- ited supply capacity. The only way to re- duce the $68 price is to reduce the deliv- ered cost from Seattle to Denver. If, for ex- ample, we reduce the transportation cost from San Francisco to Denver, the effect is to increase the economic rent—that is, the reduced cost of activity SMOSF becomes less than —18; the consumer price in Los Angeles remains at $68. Automatic Interpretation >

What the examples suggest is that it is

INTERFACES 23:5 110

LINEAR PROGRAMS

possible to shift stjme of the art of analysis into the realm of science. I illustrate this using rules for automatic price interpreta- tion that include English translations built on the linear program's syntax.

The analysis we just did can be auto- mated to a great extent, at least for linear programs with the same syntax as the WOODNET model. Figure 18 shows that a complete demand price interpretation de- pends upon a supply price interpretation. That is, once the $18 economic rent of supply activity SMOSFl is explained, the rest follows. (The term economic rent is used, but this may not be understood by the analyst. It depends on how the model builder (or manager) wrote the rule file.) The result is a successful interpretation (but now automatically when we're not there for someone else with the same question).

I now go through the response gener- ated by the price interpretation rule to

elaborate on how this was generated. In general, a rule file in ANALYZE is com- posed of free text (perhaps with some for- matting instructions) until some LP infor- mation is needed. There are two ways to obtain LP information: simple "lookup," like the meaning of a row or column or a value associated with it, and execution of an ANALYZE command, like the path- tracing procedure. In addition, there are control statements, such as conditional branching, that enable logical reasoning based on the information obtained.

To form the first sentence in Figure 18, the ANALYZE rule file uses a syntactic translation of the row in question (DMOLA), and the second sentence is a "literal" up to the price, $68, which is a simple "lookup" of the price of the row in question. Before the third sentence is com- posed, the rule file tested some conditions (such as whether the row is simply slack with zero price). Then, the rule file exe-

30 @$45 •• San Francisco

20@$5 Los Angeles

20@$0

D - - 1 8 P = 63

10@$8

P - 68 = Consumer Price

10@$0 Seattle

P = 71 = Consumer Price

20 @$55 Seattle

0@$12

20 @$20 Denver

20@$0

P = 75 - Consumer Price

D = 0 P = 55 Figure 17: A graph of the final analysis shows how the degenerate flow from San Francisco to Denver is the key to understanding the consumer price in Los Angeles (D = reduced cost of supply activity; P = dual price of demand row).

September-October 1993 111

GREENBERG

Row DMOLA b a l a n c e s demand of m a h o g a n y in Los A n g e l e s . I shall try to I n t e r p r e t its p r i c e of $ 6 8 . The c o n s u m e r s in Los A n g e l e s receive all of their m a h o g a n y from San F r a n c i s c o with d e l i v e r e d cost = $50 (this s u p p l i e r , h o w e v e r , has an e c o n o m i c rent of $ 1 8 ) . The marginal price ($68) = d e l i v e r e d cost + rent. We now Interpret the $18 r e n t , a s s o c i a t e d with the level of activity SMOSFl being at its c a p a c i t y l i m i t .

The ( i n p u t ) supply cost = $45 (excluding e c o n o m i c r e n t ) . This supply is d e l i v e r e d to 2 c o n s u m e r s - - n a m e l y , to Los A n g e l e s with t r a n s p o r t a t i o n cost = $ 5 ; and. to S e a t t l e with t r a n s p o r t a t i o n cost = $ 8 . This supplier does not send any m a h o g a n y to D e n v e r , but it is this c o n s u m e r that is setting the s u p p l i e r ' s e c o n o m i c rent. That i s , any increase in the supply of m a h o g a n y in San F r a n c i s c o would go to Denver and d i s p l a c e its most e x p e n s i v e current d e l i v e r e d c o s t .

Figure 18: ANALYZE automatically gives a price interpretation, even in the more complex case when the price is not equal to the delivered cost. Exact wording can be controlled by the rule base.

cuted the path-tracing procedure, just as we did. Upon looping over the resulting submatrix, the rule file obtains the delivery path. The resulting sentence is composed from a template into which the material (mahogany), the supplier (San Francisco), and the delivered cost ($50) is substituted. It also branched to the logic for the situa- tion at hand, which is the presence of an economic rent.

After identifying the activity that sup- plies mahogany in San Francisco (SMOSFl) as the key to explaining the price of $68, another rule is instantiated to explain the economic rent of $18.

The second part of the interpretation proceeds by first giving the supply cost and then executing the path-tracing proce- dure, as we did, to find the two consumers that receive the San Francisco supply. All of the response so far parallels what we did by obtaining the meanings and values

of the rows and columns, executing path- tracing, then deciding what we must ex- amine next. This reasoning is what makes the automatic response formation intelli- gent, as the logic reflects what we do as LP experts. The rule contains logic to look for a degenerate link. In this case, Denver is found, and the logic goes through the same reasoning as we did.

After giving the two consumers for which there is positive flow from San Francisco, the rule identifies Denver as a key link in the solution. The actual words are formed by templates plus "lookups" to substitute meanings, based upon the syn- tax, and values of elements, like the trans- portation costs. Concluding Remarks

The examples of price interpretation given here are among the easy ones, nota- bly because the linear programs are net- works. The methods of analysis for more

INTERFACES 23:5 112

LINEAR PROGRAMS

genera! models, however, are similar. One still tries to trace a margin-setting substruc- ture that has causal properties, but instead of a path in the sense of an ordinary net- work, it is a hyperpath in the fundamental digraph. It is important, however, that the LP be in canonical form for path-tracing to work properly. The A matrix in the equa- tion, 1/ = Ax, should be signed such that a negative coefficient represents an activity s input, and a positive coefficient represents its output. Otherwise, the I/O structure could be confusing to any heuristic, like path-tracing, that depends upon this inter- pretation.

With tl means for obtaining causal infor- mation to support analysis, automatic in- terpretation becomes a reasonable consid- eration. Besides the examples given here, the methods have been applied success- fully to blending problems and other non- network linear programs using ANALYZF. A key to this is the use of the fundamental digraph and related graphs to represent model structures apart from data values.

There are some aspects of understanding prices in connection with marginal sensi- tivity analysis that I did not explain, due to limited time and space. In addition to ref- erences already cited, I suggest looking at the interior point approach [lansen, Roos, and Terlaky 1992). For many applications, using one particular basis from a collection of alternative optima can give false or mis- leading results. The unique partition ob- tained by an interior point solufion can be much better. Also, the range of data for which the solution structure does not change is important. The basis-driven ap- proach, which is appropriate with a sim- plex method solution, has undergone some

recent enhancements by Wendell [1985] (see also [Ward and Wendell, 1990]). Again, the interior point approach gives the better range of information, but I can- not explain here.

As we articulate the analysis process more precisely, we can extend and sharpen the rules used by ANALYZF. This devel- opment is in progress, including experi- ments with automatic interpretation for a variety of models and situations. There is no substitute, however, for human analy- sis. Many interesting applications are be- yond the reach of current capabilities for automatic analysis, but the gap is closing. Acknowledgments

I gratefully acknowledge encouragement and technical help from Frederic H. Murphy. I also received valuable com- ments from John Stone and an anonymous referee that led to an improved version. In addition, support for the ongoing project that produced ANALYZE (among other things) comes from a consortium of com- panies: Amoco Oil Company, IBM, Shell Development Company, Chesapeake Deci- sion Sciences, GAMS Development Corpo- ration, Ketron Management Science, and MathPro, Incorporated. References AkgiJl, M. 1984, "A note on shadow prices in

linear prugramming," journal oj Operational Research Society, Vol. 35, No. 5, pp. 425-431.

Gal, T. 1979, Postoptimal Analyses, Parametric Programming, and Relafeii Topics, McGraw- Hill International, New York.

Greenberg, H. ). 1983, "A functional descrip- tion of ANALYZE: A computer-assisted anal- ysis system for linear programming models," ACM Transactions on Mathematical Software, Vol, 9, No. 1, pp. 18-56.

Greenberg, H. I. 1986, "An analysis of degener- acy," Naval Logistics Research Quarterly, Vol. 33, pp. 635-655.

September-October 1993 113

GREENBERG

Greenberg, H. I. 1987, "ANALYZE: A com- puter-assisted analysis system for linear pro- gramming models," Operations Research Let- ters, Vol. 6, No. 5, pp. 249-255.

Greenberg, H. J. 1988, "ANALYZE rulebase," in Mathematical Models for Decision Support, eds. G. Mitra, H. |. Greenberg, F. A. Lootsma, M. J. Rijckaert, and H-J. Zimmermann, Pro- ceedings of NATO ASI, luly 26-August 6, Springer-Verlag, Berlin, pp. 229-238.

Greenberg, H. J, 1992, "Intelligent analysis sup- port for linear programs," Computers and Chemical Engineering, Vol. 16, No. 7, pp. 6 5 9 - 674.

Greenberg, H. J. 1993a, "How to analyze the results of linear programs—Part 1: Prelimi- naries," Interfaces, Vol. 23, No. 4, pp. 56-67.

Greenberg, H. I. 1993b, A Computer-Assisted Analysis System for Mathematical Programming Models and Solutions: A User's Guide for ANALYZE, Kluwer, Boston, Massachusetts.

Greenberg, H. J. and Murphy, F. II. 1985, "Computing market equilibria with price reg- ulations using mathematical programming," Operations Research, Vol. 33, No. 5, pp. 9 3 5 - 954.

Ho, I. K. and Smith, D. 1987, Computing True Shadow Prices in Linear Programming, Techni- cal Report, College of Business Administra- tion, University of Tennessee, Knoxville, Tennessee.

Jansen, B.; Roos, C.; and Terlaky, T. 1992, "An interior point approach to postoptimal and parametric analysis in linear programming," Technical Report, Faculty of Technical Math- ematics and Informatics/Computer Science, Delft University of Technology, Delft, The Netherlands.

Rubin, D. S. and Wagner, H. M. 1990, "Shadow prices: Tips and traps for manag- ers," Interfaces, Vol. 20, No. 4, pp. 150-157.

Ward, ]. E. and Wendell, R. E. 1990, "Ap- proaches to sensitivity analysis in linear pro- gramming," Technical report. Graduate School of Business, University of Pittsburgh, Pittsburgh, Pennsylvania.

Wendell, R. E. 1985, "The tolerance approach to sensitivity analysis in linear program- ming," Management Science, Vol. 31, No. 5, pp. 564-578.

INTERFACES 23:5 114