Dantzig G., Thapa M. Linear programming. Vol.1. Introduction

Подождите немного. Документ загружается.

172 PRICE MECHANISM AND SENSITIVITY ANALYSIS

variabilities in processes and materials not taken account of in the model, it

may be desirable to move away from the optimum solution in order to achieve

a solution less sensitive to such changes in the input parameters.

2. Values of the input-output coeﬃcients, objective function coeﬃcients, and/or

constraint constants may be to some extent controllable at some cost; in this

case we want to know the eﬀects that would result from changing these values

and what the cost would be to make these changes.

3. Even if the input-output and objective function coeﬃcients and constraint

constants are not controllable, their values may be only approximate; thus it

is still important to know for what ranges of their values the solution is still

optimal. If it turns out that the optimal solution is extremely sensitive to

their values, it may become necessary to seek better estimates.

The problem of ﬁnding optimal solutions to linear programs whose coeﬃcients

and right-hand sides are uncertain is called stochastic programming or planning

under uncertainty. The idea is to ﬁnd solutions that hedge against various com-

binations of contingencies that might arise in the future and at the same time are

solutions that are minimal in some expected-value sense.

7.1 THE PRICE MECHANISM OF THE

SIMPLEX METHOD

Recall that in previous chapters we often referred to the simplex multipliers as

prices. In this section we shall show how this viewpoint of multipliers arises natu-

rally and we shall provide an economic interpretation of the Simplex Method. In

fact, it will turn out that an important part of sensitivity analysis is being able to

interpret the price mechanism of the Simplex Method.

For the discussion we shall once again consider the primal problem in standard

form:

Minimize c

x = z

subject to Ax = b, A : m × n,

x ≥ 0;

(7.1)

and its dual

Maximize b

π = v

subject to A

π ≤ c, A : m × n.

(7.2)

For the purpose of our discussion, suppose that an optimal solution is available

to the primal-dual system shown above. Let x

∗

=(x

∗

) be the optimal primal

solution, and let π

∗

be the corresponding dual solution (or multipliers). Let the

optimal primal objective value be

∗

= c

∗

= c

∗

, (7.3)

7.1 THE PRICE MECHANISM OF THE SIMPLEX METHOD 173

and the optimal dual objective value be

∗

= b

∗

, (7.4)

where v

∗

= z

∗

and the optimal basic indices are denoted by B. Let ¯c = c−A

∗

≥ 0

be the optimal reduced costs.

7.1.1 MARGINAL VALUES OR SHADOW PRICES

The price of an item is its exchange ratio relative to some standard item. If the

item measured by the objective function is taken as a standard, then the price π

∗

of item i is the change it induces in the optimal value of the objective z per unit

change of b

, for inﬁnitesimally small changes of b

Deﬁnition (Price, Marginal Value, Shadow Price): The price,ormarginal

value,orshadow price of a constraint i is deﬁned to be the rate of the change

in the objective function as a result of a change in the value of b

, the right-

hand side of constraint i.

At an optimal solution, the primal objective and dual objective are equal. Thus,

∗

= v

∗

= b

∗

is a function of the right-hand sides b, and hence this relation can be used to

show that the price associated with b

at the optimum is π

∗

if the basic solution

is nondegenerate. If so, then for small changes in any b

, the basis, and hence the

simplex multipliers, will remain constant. Under nondegeneracy the change in value

of z per change of b

for small changes in b

is obtained by partially diﬀerentiating

z with respect to the right-hand side b

, i.e.,

∂z

∂b

= π

∗

, (7.5)

and thus, by the above deﬁnition, π

∗

can be interpreted as the price that, when

associated with the right-hand side, is referred to as the shadow price, a term

attributed to Paul Samuelson.

Example 7.1 (Shadow Prices Under Nondegeneracy) Consider the linear pro-

gram to ﬁnd min z, x ≥ 0 such that

−x

− 2x

− 3x

+ x

= z

+2x

+3x

− x

=1.

It is easy to verify that the optimal basic solution is

=6,x

=2,x

=1,x

=0,z= −13.

174 PRICE MECHANISM AND SENSITIVITY ANALYSIS

The shadow prices associated with the optimal basis (columns 1, 1, 3) are

= −1,π

= −2,π

= −3,

because

z = b

+ b

, where b =(6, 2, 1),

implies

∂z

∂b

= π

= −1,

∂z

∂b

= π

= −2,

∂z

∂b

= π

= −3.

Note that these do not change for small values of b

If the basic solution is degenerate, then the situation is not so straightforward.

However, it is easy to see from the above discussion that the objective function is

piecewise linear in the parameter b

. A price interpretation can still be obtained by

examining positive and negative changes to b

. In the case of degeneracy of a single

basic variable, a change in a particular b

will either result in no change in the value

of the degenerate basic variable, in which case there is no change in the shadow

prices, or it will result in no change in prices if b

is changed in one direction, but

will result in a complete set of new prices if b

is changed in the other direction.

In general the two sets of prices can be obtained by applying parametric tech-

niques; see Section 7.8.

Example 7.2 (Shadow Prices Under Degeneracy) Suppose that in Example 7.1,

we replace b

=1byb

= 0; then ∂z/∂b

= −3 if the change in b

is positive. But if

the change in b

is negative, then x

drops out of the basis and x

becomes basic and the

shadow prices are π

= −1, π

= −2, π

= ∂z/∂b

−

= −9.

7.1.2 ECONOMIC INTERPRETATION OF THE

SIMPLEX METHOD

When applied to the primal problem (7.1), the goal of the Simplex Method is to

determine a basic feasible solution that uses the available resources in the most

cost-eﬀective manner. The objective function of the dual (7.2) at iteration t is the

total cost:

v = π

b =



i=1

, (7.6)

where π

are the simplex multipliers associated with the basis B. As we will see,

(or π

∗

at the optimal solution) can be interpreted as implicit revenues to oﬀset

direct costs (i.e., the shadow price) per unit of resource i given the primal basic

variables at iteration t.Thusπ

can be interpreted as the oﬀsets to the direct

costs



j=1

of having b

units of resource i available in the primal problem.

With this interpretation of the dual variables π and dual objective function v

we can examine each row j of the dual problem corresponding to column j of the

primal problem. Each unit of activity j in the primal problem consumes a

units of

resource i. Using shadow prices, the left-hand side,



i=1

, of the jth constraint

of the dual problem is the implicit indirect cost of the mix of resources that would

7.1 THE PRICE MECHANISM OF THE SIMPLEX METHOD 175

be consumed and/or produced by one unit of activity j. On the other hand, the

right hand side, c

, of the jth constraint of the dual problem is the direct cost of

one unit of activity j. That is, the jth dual constraint,



i=1

≤ c

, can be

interpreted as saying that the implicit indirect costs of the resources consumed by

activity j less the implicit indirect costs of the resources produced by activity j

must not exceed the direct costs c

; and if these costs are strictly less than c

,it

does not pay to engage in activity j. On the other hand, if



i=1

,it

means that it does pay to engage in activity j.

In other words, the dual constraints associated with the nonbasic variables x

may be satisﬁed, feasible, or infeasible. That is, letting

¯c = c

− N

π, (7.7)

where π solves B

π = c

, at any iteration t we could have ¯c

≥ 0 (the dual constraint

j is feasible) or ¯c

< 0 (the dual constraint j is infeasible). From an economic

standpoint, ¯c

< 0 implies that activity j can use its resources more economically

than any combination of activities in the basis, whose net input-output vector is

the same as activity j, implying an improved solution is possible. If, on the other

hand, ¯c

≥ 0, then the resources used by activity j are already being used by the

activities in the basis in a more cost-eﬀective way elsewhere. The prices of the dual

problem are selected so as to maximize the implicit indirect costs of the resources

consumed by all the activities.

The complementary slackness conditions of dual optimality can be given the

following economic interpretation: Whenever an activity j is “operated” at a strictly

positive level, i.e., x

basic and x

> 0, the marginal value of the resources it

consumes (



i=1

) per unit level of this activity must exactly equal the cost c

and all nonbasic activities must “operate” at a zero level.

When the primal-dual system is expressed in the von Neumann symmetric form

(see Section 5.1), if a slack variable is strictly positive in an optimal solution, this

implies that the corresponding dual variable, π

, is equal to 0. That is, the resource i

for which the primal slack variable is positive is a free resource, i.e., the marginal

value of obtaining the resource is zero. If the slack variable corresponding to the

diﬀerence between the direct and indirect costs of activity j is positive, this implies

that the corresponding primal activity level is zero.

7.1.3 THE MANAGER OF A MACHINE TOOL PLANT

The example of this section is based on material supplied by Clopper Almon Jr. to

one of the authors. Consider the dilemma of a manager of a machine tool plant, say

in an economy that has just been socialized by a revolution (for example, Russia

just after the 1917 revolution). The central planners have allocated to this manager

input quantities +b

,... ,+b

of materials (which we designate by 1,...,k) and

have instructed this manager to produce output quantities −b

k+1

,... ,−b

of the

machine tools (which we designate by k+1,...,m). The b

,... ,b

, being inputs, are

nonnegative, and b

k+1

,... ,b

, being outputs, are nonpositive by our conventions.

176 PRICE MECHANISM AND SENSITIVITY ANALYSIS

The planners further direct the manager that he shall use as little labor as possible

to meet his required production goals and that he must pay the workers with labor

certiﬁcates as wages, one certiﬁcate for each hour of labor. The central planners

have declared that the prices of items of the old free market economy are no longer

to be used but have not provided any new prices to guide the manager.

The manager has at his disposal many production activities, say n of them,

each of which he can describe by a column vector, A

•j

=(a

,... ,a

)

. If the jth

process inputs a

units of the ith item per unit level of operation, a

is positive.

If, on the other hand, the jth process outputs a

units of item i per unit level of

operation, a

is negative. The jth process also requires c

units of labor per unit

level of operation. The manager’s problem then is to ﬁnd levels of operation for all

the processes, x

,... ,x

, that satisfy

+ a

+ ···+ a

= b

+ a

+ ···+ a

= b

+ a

+ ···+ a

= b

(7.8)

and minimize the total amount of labor used,

+ c

+ ···+ c

= z (min).

The components of x must, of course, be nonnegative. In matrix notation,

Ax = b, x ≥ 0,c

x = z.

The manager knows of m old reliable processes (activities), namely 1,...,m,

which he is sure he can use in some combination to produce the required outputs

from the given inputs. However, the labor requirements may be excessive. Thus,

he knows he can ﬁnd nonnegative x

,... ,x

such that

+ a

+ ···+ a

= b

+ a

+ ···+ a

= b

+ a

+ ···+ a

= b

(7.9)

or in matrix notation,

= b.

We shall assume that B is a feasible basis for (7.8).

This manager knows, alas, that his workers are prone to be extravagant with

materials, using far more inputs or producing far fewer outputs for each activity j

than that speciﬁed in (7.8). Unless he can keep this tendency in check, he knows he

will fail to meet his quotas, and he knows that failure to meet quotas is dangerous

to his health. Before the revolution, he deducted the cost of the excess use of

materials from the worker’s wages; but now that all prices have been swept away,

7.1 THE PRICE MECHANISM OF THE SIMPLEX METHOD 177

he lacks a monetary measure for computing the cost of materials or the value of

items produced. Suddenly, in a stroke of genius, it occurs to him that he can

make up his own prices in terms of labor certiﬁcates, charge the operators of each

process for the materials they use, credit them for their products, and give them

the diﬀerence as their pay. (This sounds like a pretty good idea, it might even work

in our free market economy.)

Being a fair man, he wants to set prices such that the eﬃcient workers can

take home a certiﬁcate for each hour worked. That is, he wants to set the prices,

,π

,... ,π

, for raw material and products produced such that the net yield on a

unit level of each basic activity j is equal to the amount of labor c

that it requires:

+ π

+ ···+ π

= c

+ π

+ ···+ π

= c

+ π

+ ···+ π

= c

(7.10)

or in matrix notation,

π = c

The manager now uses his PC to solve (7.9) for x

and verify that x

≥ 0, and

to solve (7.10) for π. Common sense tells the manager that by using his pricing

device he would have to pay out exactly as many labor certiﬁcates as he would if

he paid the labor by the hour and all labor worked eﬃciently. Indeed, this is easily

proved since the total cost, using his calculated prices for basic activities, is, noting

=0,

b = π

(Bx

)=(π

B)x

= c

where c

x is the cost of paying wages directly.

The manager harbors one qualm about his pricing device, however. He remem-

bers that there are other processes besides the m he is planning to use and suspects

that his lazy, wily workers will try to substitute one or more of these in place of

some combination of the basic ones that he is planning to use, and he could end up

issuing more labor certiﬁcate hours than actual hours worked. In order to discover

whether such activities exist he “prices out” each activity j, that is,



= π

+ π

+ ···+ π

, (7.11)

and sees whether any of them is greater than the direct wages c

. On looking over

the list of processes in (7.8), the manager ﬁnds several for which the inequality



holds. Denoting the excess wages of the jth process by ¯c

, the manager

determines

¯c

= c

− (π

+ π

+ ···+ π

)

and singles out process s, the one oﬀering the most excess wages:

¯c

= min

¯c

< 0. (7.12)

178 PRICE MECHANISM AND SENSITIVITY ANALYSIS

Before devising repressive measures to keep the workers from using processes

that yield excess wages, the manager, a meditative sort of fellow, who worries about

his health, pauses to reﬂect on the meaning of these excess wages. Having always had

a bent for mathematics, he soon discovers a relation that mathematically we express

by saying that the vector of coeﬃcients ¯a

, for any activity j in the canonical form,

can be interpreted as weights to form a linear combination of the original vectors

of the basic activities that has the same net input and output coeﬃcients for all

items as those of activity j, except possibly the cost coeﬃcient c

. In particular, he

ﬁnds that he can represent activity s, the one yielding the most excess wages, as a

linear combination of his “old reliable” activities as follows:













¯a













¯a

+ ···+













¯a













, (7.13)

where ¯a

are the coeﬃcients of x

in the canonical form. In words, (7.13) tells

him that x

units of activity s can be simulated by a combination of the basic set

of activities (1,...,m); i.e., by ¯a

, ¯a

,... ,¯a

units. Thus, if the workers

introduce x

units of activity s, the levels of the basic activities must be adjusted

by these amounts (up or down, depending on sign) if the material constraints and

output quotas are to remain satisﬁed. Now, the labor cost of simulating one unit

of activity s by the m old reliables is

¯a

+ c

¯a

+ ···+ c

¯a

This amount is precisely what the manager would pay for the various inputs and

outputs of one unit of the real activity s if he were to use the prices π

. For consid-

ering the vector equation (7.13) as m equations and multiplying the ﬁrst equation

through by π

, the second by π

, etc. and summing, one obtains immediately from

(7.10)

¯a

+ c

¯a

+ ···+ c

¯a

= π

+ π

+ ···+ π

. (7.14)

It is now readily shown that the fact that the process s yields excess wages means

to the manager that it takes less labor to operate s directly than to simulate it with

some combination of the m old activities. This is clear from (7.11), (7.12), and

(7.14), which yield

¯a

+ ···+ c

¯a

+ ···+ c

¯a

. (7.15)

Hence, he reasons, s must be in a sense more eﬃcient than at least one of these old

processes. Recalling that the central planners instructed him to use as little labor

as possible, the manager decides to use activity s in place of one of the original m.

He soon discovers that if he wishes to avoid the nonsensical situation of planning

7.1 THE PRICE MECHANISM OF THE SIMPLEX METHOD 179

to use some activity at a negative level, the process r to be replaced by process s

must be chosen so that

¯a

= min

{ i| ¯a

>0 }

¯a

, (¯a

> 0).

Because ¯a

> 0, it follows from (7.15) that

¯a

+ ···+ c

r−1

¯a

r−1,s

+ c

r+1

¯a

r+1,s

···+ c

¯a

− c

−¯a

. (7.16)

The coeﬃcients ¯a

/(−¯a

)ofc

for j =1,...,r−1,r+1,...,mand the coeﬃcient

−1/(−¯a

)ofc

in (7.16) are precisely the weights required to simulate activity r

out of the activities in the new basis, as can be seen by re-solving (7.13) for column

r in terms of the others. But, for example, c

¯a

/(−¯a

) is the labor cost of the ﬁrst

activity in the simulation of activity r, so that the left-hand side of (7.16) represents

the total labor cost of simulating a unit level of activity r by the activities in the

new basis, while c

is the labor cost of one unit of the real activity r. Hence (7.16)

shows that activity r is indeed less eﬃcient in its use of labor than those in the new

basis.

In summary, the manager now knows that if there exist processes for which his

pricing device yields more labor certiﬁcates than are actually required, then he had

better substitute one of these more eﬃcient processes for one in the original set

and thereby bring about a more eﬃcient use of labor. Since the central planners

instructed him to use as little labor as possible, it is clearly wise for him to plan

production using activity s instead of one of the m he had originally intended to

use, to readjust the levels of use of the remaining ones, and to change the prices.

Having learned this lesson, the manager proceeds again to look for more eﬃcient

processes that provide his wily workers with excess wages by being more eﬃcient

than one in his new basis. If there are any, he makes the substitution, readjusts

prices, and again looks for more eﬃcient processes, and so on until he ﬁnds a set of

prices π

∗

under which no process prices out as more eﬃcient. Fortunately for him,

it turns out (as we know) that in a ﬁnite number of steps he will ﬁnd such a set of

prices.

Let us pause for a moment to ponder the meaning of one of these prices, say π

Suppose we introduce into the manager’s A matrix in equation (7.8) a ﬁctitious

activity that consists simply in increasing his allotment of item i if b

> 0orin

decreasing his production quota on i if b

< 0. Such an activity will be represented

by a column that has all zeros except for a one in the ith row. Thus the labor cost

of simulating this activity by a combination of those of the ﬁnal basis is, by (7.11),

precisely π

.Thusπ

is the labor value, the labor that can be displaced by one

additional unit of item i.

The manager has now achieved his objective of ﬁnding a set of prices to charge

for raw materials and to pay for ﬁnished goods that will keep his workers from

wasting inputs and yet oﬀer no possibilities of his paying out more labor certiﬁcates

than actual hours worked. But he now begins to wonder whether he is truly safe

180 PRICE MECHANISM AND SENSITIVITY ANALYSIS

from the central planners’ criticism for the amount of labor he uses. He begins by

specifying explicitly what he intends to do. His operating plan consists of a set of

activity levels x

∗

=(x

∗

,... ,x

∗

)

satisfying

∗

= z

∗

= b,

∗

≥ 0

(7.17)

and a set of prices π

∗

=(π

∗

,π

∗

,... ,π

∗

)

satisfying B

∗

= c

with the property

that

¯c

= c

−



i=1

∗

> 0=⇒ x

∗

=0. (7.18)

We shall now prove that the manager’s operating plan has minimized his labor

costs. Writing ¯c = c − A

∗

, we have from (7.17) that

¯c

∗

=(c − A

∗

)

∗

= z

∗

− b

∗

, (7.19)

where, by (7.17), z

∗

is the total labor requirement of the manager’s operating plan.

But because of (7.18), ¯c

∗

= 0, and therefore

∗

= b

∗

. (7.20)

Now let x =(x

,... ,x

)

be any other feasible operating plan, and let z be

its labor requirements; then

x = z,

Ax = b,

x ≥ 0.

(7.21)

It follows by multiplying Ax = b by π

∗

, subtracting from c

x = z, and noting (7.20),

that

(c − A

∗

)

x = z − b

∗

= z − z

∗

, or



j=1

¯c

= z − z

∗

. (7.22)

But the left member is the sum of nonnegative terms and therefore z ≥ z

∗

. Hence,

no other feasible operating plan exists whose labor requirement is less than the one

found by the manager.

At this point, we can imagine the manager’s delight at his genius, for as a by-

product of his search for prices that will cause his workers to work eﬃciently, he

has also discovered those processes that minimize his labor requirements. Without

explicitly trying, he has solved his assigned task of keeping his use of labor to a

minimum!

Let us review the requirements satisﬁed by the prices found by the manager.

First, there will be no excess wages in any activity; that is,

π ≤ c. (7.23)

7.1 THE PRICE MECHANISM OF THE SIMPLEX METHOD 181

Second, the total amount of wages to be paid for all activities should be the same

whether they are paid directly or by use of the pricing device; that is

∗

= c

∗

= b

π, (7.24)

where x

∗

is an optimal solution to (7.8).

Let us now show that these prices π themselves represent the optimal solution

to another linear programming problem—speciﬁcally, to the dual problem of our

manager’s original production problem. By multiplying the jth equation of (7.23)

by x

∗

and summing, we ﬁnd that



j=1

∗

+ π



j=1

∗

+ ···+ π



j=1

∗

≤



j=1

∗

. (7.25)

Substituting from (7.8)



j=1

∗

,i=1,...,m, (7.26)

gives

+ π

+ ···+ π

≤ c

+ c

+ ···+ c

Thus, π

b ≤ c

∗

for any π that satisﬁes (7.23). The prices π

∗

found by the

manager give b

∗

= c

∗

, and thus π

∗

maximizes b

π, subject to the constraints

(7.23). Hence, π = π

∗

may be viewed as an optimal solution to the dual linear

programming problem, namely,

π = v (max),

π ≤ c.

(7.27)

The relation b

∗

= c

∗

, where π

∗

is an optimal solution to (7.27) and x

∗

optimal solution to (7.8), agrees with the Strong Duality Theorem (see Theorem 5.3).

 Exercise 7.1 Interpret the economic meaning of maximizing b

π in the case of the tool

plant manager.

7.1.4 THE AMBITIOUS INDUSTRIALIST

In this section we shall present a situation where the primal formulation and the dual

formulation both are problems that a planner would like to have solved. Consider

a defense plant that has just been built for the government. The plant has been

designed to produce certain deﬁnite amounts −b

, i = k +1,...,m, of certain

defense items and to use only certain deﬁnite amounts, +b

, i =1,...,k, of certain

scarce materials that will be provided without cost by other government plants.

The consulting engineers who designed the plant provided the government with