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

202 PRICE MECHANISM AND SENSITIVITY ANALYSIS

(a) Solve the linear program with DTZG Simplex Primal software option to

obtain the optimal solution x

∗

.

(b) By hand, compute ranges on each right hand side for which the solution x

∗

stays optimal. How does the objective value change over the two ranges?

Clearly show your calculations.

(c) By hand compute ranges on the cost coeﬃcients for which the solution x

∗

stays optimal. How does the objective value change over these ranges?

Clearly show your calculations.

(d) By hand compute ranges on each of the matrix coeﬃcients for which the

solution x

∗

stays optimal. How does the objective value change over these

ranges? Clearly show your calculations.

(e) Re-run the DTZG Simplex Primal software option together with the Sen-

sitivity Analysis software option and verify your hand calculations.

(f) Add a new column



−6

2

−3



corresponding to a new variable x

5

. Without

re-solving the problem, determine whether it enters the basis. If it does,

re-solve the linear program with this new column.

(g) Add the new row x

1

− x

2

+ x

3

= 10. Without re-solving the problem,

determine whether it causes the optimal solution to change. If it does,

re-solve the linear program with this row included.

7.9 Ph.D. Comprehensive Exam, June 13, 1968, at Stanford. Consider the linear

program, ﬁnd x and min z such that

Ax = b, x ≥ 0,c

T

x = z (Min).

Assume that x

o

=(x

o

1

,x

o

2

,... ,x

o

n

)

T

is an optimal solution to the problem.

Suppose further that a constraint a

T

x ≤ θ has been omitted from the original

problem and that a feasible program results from adjoining this constraint.

(a) Prove that if a

T

x

o

≤ θ, then x

o

is still optimal for the augmented problem.

(b) Prove that if a

T

x

o

>θ, then either there exists no feasible solution a

T

x

o

≤ b

or there exists an optimal solution x

∗

such that a

T

x

∗

= θ.

7.10 Dantzig [1963]. Given an optimal basic feasible solution and the corresponding

system in canonical form, show that ¯c

j

represents the change necessary in the

unit cost of the jth nonbasic activity before it would be a candidate to enter the

basis. If the other coeﬃcients as well as cost coeﬃcients can vary, show that

¯c

j

= c

j

−

m



i=1

π

i

a

ij

is the amount of change where π

i

are the prices associated with the basic set of

variables.

7.11 Let B be an optimal basis for a linear program in standard form. Prove or

disprove (by means of a counter example) the claim that if some of the basic

costs c

B

are decreased, B will remain optimal.

7.9 PROBLEMS 203

7.12 Dantzig [1963]. Develop a formula for the change in cost c

j

of a basic activity

before it is a candidate for being dropped from the basis. Which activity would

enter in its place?

7.13 Suppose we have an optimal solution for a linear program and the cost coef-

ﬁcient c

s

of nonbasic variable x

s

is reduced suﬃciently so that x

s

in positive

amount enters the basic set. Prove that in any optimal solution to the linear

program, x

s

is a basic variable.

7.14 Modify the analysis in Section 7.6 for the case when all the coeﬃcients in a

column A

•j

change. Consider the cases where j is a basic column or a nonbasic

column when the linear program is in standard form with upper and lower

bounds on the variables.

7.15 Ph.D. Comprehensive Exam, September 26, 1992, at Stanford. Consider a linear

program in standard form:

Minimize c

T

x

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

x ≥ 0.

Assume that every basic solution is nondegenerate. Let

K =



x | Ax = b, x ≥ 0

,

K



=



x | Ax = b, x ≥ 0,x

n

=0

,

where x

n

is a scalar variable. Assume that the sets K and K



are nonempty and

bounded.

Suppose that we allow only the cost coeﬃcient c

n

to vary. Show that there

exists a constant γ such that x

n

is a nonbasic for c

n

>γ, and x

n

is basic for

c

n

<γ, in all optimal bases. Show how to compute the scalar γ. What happens

if c

n

= γ?

This page intentionally left blank

CHAPTER 8

TRANSPORTATION AND

ASSIGNMENT PROBLEM

The general case of the transportation and assignment problem is the minimum-cost

capacitated network-ﬂow problem

Minimize c

T

x

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

l ≤ x ≤ u,

(8.1)

where each column A

•j

has at most one positive coeﬃcient +1 and at most one

negative coeﬃcient −1. This matrix structure implies that every basis is triangular

and that all basic solutions have integer values if the right-hand side and upper and

lower bounds have integer values.

The classical transportation problem, see (8.3), was studied as early as 1941

by Hitchcock, who proposed a solution technique that has points in common with

the Simplex Method. This case and the general case (which will be discussed in

Chapter 9) are reducible to one another.

8.1 THE CLASSICAL

TRANSPORTATION

PROBLEM

The classical transportation problem, see (8.3), is to determine an optimal schedule

of shipments that:

1. originate at sources where known quantities of a commodity are available;

205

206 TRANSPORTATION AND ASSIGNMENT PROBLEM

2. are allocated and sent directly to their ﬁnal destinations, where the total

amount received must equal the known quantities required;

3. exhaust the supply and fulﬁll the demand; hence, total given demands must

equal total given supplies;

4. and ﬁnally, the cost of each shipment from a source to a destination is propor-

tional to the amount shipped, and the total cost is the sum of the individual

costs; i.e., the costs satisfy a linear objective function.

8.1.1 MATHEMATICAL STATEMENT

Suppose, for example, that m warehouses (origins) contain various amounts of a

commodity that must be allocated to n cities (destinations). Speciﬁcally, the ith

warehouse must dispose of exactly the quantity a

i

≥ 0, while the jth city must

receive exactly the quantity b

j

≥ 0. For this problem, it is assumed that the total

demand equals the total supply, that is,

m



i=1

a

i

=

n



j=1

b

j

= T, a

i

≥ 0,b

j

≥ 0. (8.2)

The cost c

ij

of shipping a unit quantity from i to j is given; typically c

ij

≥ 0 but

c

ij

< 0 is also possible. The problem then is to determine the number of units to

be shipped from i to j at an overall minimum cost.

The problem can be stated mathematically as

Minimize

m



i=1

n



j=1

c

ij

x

ij

= z

subject to

n



j=1

x

ij

= a

i

,i=1,...,m

m



i=1

x

ij

= b

j

,j=1,...,n

x

ij

≥ 0,i=1,...,m, j =1,...,n.

(8.3)

Note that in this chapter, the symbols m and n denote the number of sources and

demand centers respectively, and are not the symbols used to denote the number

of constraints and variables for a general linear program. In this case the number

of equations is m + n and the number of variables is mn.

8.1.2 PROPERTIES OF THE SYSTEM

This problem has a very nice structure that can be exploited to compute an initial

basic feasible solution very easily and then to compute improving solutions until an

8.1 THE CLASSICAL TRANSPORTATION PROBLEM 207

.

•

.

1

2

m

.

•

.

1

2

n

................................................................................................................................................................................................................................................................................

.

................................................................................................................................................................................................................................................................................

.

................................................................................................................................................................................................................................................................................

.

a

1

a

2

a

m

b

1

b

2

b

n

c

11

c

12

c

1n

c

21

c

22

c

2n

c

m1

c

m2

c

mn

S

O

U

R

C

E

S

D

E

S

T

I

N

A

T

I

O

N

S

Costs

c

ij

Supply

a

i

Demand

b

j

Figure 8-1: Network Representation of the Transportation Problem

optimal solution is determined. The nonzero pattern of coeﬃcients (other than the

objective function) is evident when the equations are displayed as shown below.

x

11

+ x

12

+ ···+ x

1n

= a

1

x

21

+ x

22

+ ···+ x

2n

= a

2

.

x

m1

+ x

m2

+ ···+ x

mn

= a

m

x

11

+ x

21

x

m1

= b

1

x

12

+ x

22

+ x

m2

= b

2

.

x

1n

+ x

2n

+ x

mn

= b

n

(8.4)

The transportation problem is a special case of the more general network problem. A

network representation of the classical transportation problem is shown in Figure 8-

1.

Example 8.1 (Prototype Example) The example presented here is one that we shall

use to illustrate several aspects of the transportation problem. Consider the following

m = 3 (sources), n = 4 (destinations): Find

min z =7x

11

+2x

12

+5x

13

+4x

14

+3x

21

+5x

22

208 TRANSPORTATION AND ASSIGNMENT PROBLEM

+4x

23

+1x

24

+2x

31

+1x

32

+3x

33

+4x

34

(8.5)

subject to

x

11

+ x

12

+ x

13

+ x

14

=3

x

21

+ x

22

+ x

23

+ x

24

=4

x

31

+ x

32

+ x

33

+ x

34

=5

x

11

+ x

21

+ x

31

=3

x

12

+ x

22

+ x

32

=4

x

13

+ x

23

+ x

33

=2

x

14

+ x

24

+ x

34

=3

(8.6)

and x

ij

≥ 0, for i =1,...,3, j =1,...,4. The detached coeﬃcients have the following

structure:







1111

111







. (8.7)

The system of equations (8.6) may be written more compactly as follows:

x

11

x

12

x

13

x

14

x

21

x

22

x

23

x

24

x

31

x

32

x

33

x

34

=3

=4

=5

=

3

=

4

=

2

=

3

 Exercise 8.1 Draw the network representation for the prototype Example 8.1 (see

Figure 8-1).

FEASIBILITY OF THE SYSTEM

It turns out that the assumption (8.2) that total supply equals total demand is

necessary for feasibility of (8.3), because adding the ﬁrst m equations in (8.3) results

in

m



i=1

n



j=1

x

ij

=

m



i=1

a

i

and adding the last n equations in (8.3) results in

m



i=1

n



j=1

x

ij

=

m



j=1

b

j

.

8.1 THE CLASSICAL TRANSPORTATION PROBLEM 209

Therefore,



m

i=1

a

i

=



m

j=1

b

j

. In addition, the assumption (8.2) is suﬃcient for

feasibility because

x

ij

=

a

i

b

j

T

≥ 0

is a feasible solution for (8.3).

 Exercise 8.2 Verify that x

ij

= a

i

b

j

/T is a feasible solution for (8.3).

Example 8.2 (Illustration of Feasibility) In the system (8.6) of Example 8.1 suppose

that we change the right-hand side of the ﬁrst equation to 4. Now, subtracting the sum of

the ﬁrst three equations from the sum of the last four equations results in 0 = 1, showing

that the system is infeasible. This demonstrates that



m

i=1

a

i

=



n

j=1

b

j

is a necessary

condition for feasibility.

 Exercise 8.3 Suppose that the total supply



m

i=1

a

i

available at the sources exceeds

the sum of the demands



n

i=1

b

j

at the destinations. Show that we can make the system

feasible by introducing a dummy destination to absorb the excess supply at no cost. If,

on the other hand,



m

i=1

a

i

<



n

j=1

b

j

show that we can introduce a dummy source to

supply the excess requirement at, for example, the market price.

 Exercise 8.4 In the case of excess supply, elaborate the model of Exercise 8.3 to include

the possibility of storage at various external places at a transportation and holding cost,

and also the possibility of storing at the supply site at a holding cost. Similarly, in the

case of excess demand, elaborate the model of Exercise 8.3 to include the possibility of

buying from various external suppliers.

RANK OF THE SYSTEM

The necessary and suﬃcient condition (8.2) for feasibility renders the system (8.4)

dependent since it implies that the sum of the ﬁrst m equations is the same as the

sum of the last n. Therefore the rank of the system is at most m + n − 1.

LEMMA 8.1 (Rank of the Transportation Problem) The rank of the sys-

tem (8.3) is exactly m + n − 1. Furthermore, each equation is a linear combination

of the other m + n −1 equations, so that any one equation may be called redundant

and may be discarded if it is convenient to do so.

COROLLARY 8.2 (Number of Basic Variables) There are exactly m+n−1

basic variables x

ij

.

Example 8.3 (Illustration of Rank) In the system (8.6) of Example 8.1 it is easy to

verify that if we subtract the sum of the ﬁrst three equations from the sum of the last four

equations we obtain the zero equation 0 = 0, implying that the system contains at least

one redundant equation.

Dropping the ﬁrst (or, for that matter, any other) equation will result in a full rank

system, as we will now illustrate on Example 8.1. Clearly the last four equations are of full

210 TRANSPORTATION AND ASSIGNMENT PROBLEM

rank because they each contain exactly one of the variables x

11

, x

12

, x

13

, x

14

, implying that

none of these equations can be generated by a linear combination of the other equations.

The second and third equations contain no variables in common and cannot be generated

from each other. Furthermore, the second equation cannot be generated from the third

and the last four equations. Similarly, the third equation also cannot be generated from

the second and the last four equations. This implies that the remaining system is of full

rank.

 Exercise 8.5 Prove Lemma 8.1 and Corollary 8.2.

BASIS TRIANGULARITY

A fundamental property of a transportation (or network ﬂow) problem is that every

basis is triangular.

Deﬁnition (Triangular Matrix): We give the following two equivalent deﬁni-

tions of a triangular matrix.

1. A square matrix is said to be triangular if it satisﬁes the following prop-

erties.

(a) The matrix contains at least one row having exactly one nonzero

element.

(b) If the row with a single nonzero element and its column are deleted,

the resulting matrix will once again have this same property.

2. Equivalently, we can deﬁne a square matrix to be triangular if its rows

and columns can be permuted to be either an upper triangular or lower

triangular matrix. See Section A.8 in the linear algebra Appendix A for

a deﬁnition of upper and lower triangular matrices.

Example 8.4 (Basis Triangularity) A basis can be formed by using the columns

corresponding to the variables x

11

, x

13

, x

21

, x

24

, x

31

, and x

32

(as we shall see later) for

the transportation problem of Example 8.1. Below we display the system of equations

after deleting the nonbasic variables and deleting the last equation as redundant.

x

11

+ x

13

=3

x

21

+ x

24

=4

x

31

+ x

32

=5

x

11

+ x

21

+ x

31

=3

+ x

32

=4

x

13

=2.

(8.8)

It is easy to verify directly that this system is triangular by applying the ﬁrst deﬁnition.

It can also be veriﬁed by the second deﬁnition by rearranging the rows and columns to

8.1 THE CLASSICAL TRANSPORTATION PROBLEM 211

.

Figure 8-2: Illustration of the Basis Triangularity Theorem

obtain the lower triangular form

x

13

=2

x

32

=4

x

13

+ x

11

=3

x

32

+ x

31

=5

x

11

+ x

31

+ x

21

=3

x

21

+ x

24

=2.

(8.9)

 Exercise 8.6 Find another basis for Example 8.1 and by reordering rows and columns,

demonstrate its triangularity.

 Exercise 8.7 Prove that the above two deﬁnitions of triangularity of a square matrix

are equivalent.

 Exercise 8.8 Show that an upper triangular matrix can be permuted to become a lower

triangular matrix.

If a system has the property that every basis is triangular, then given a basic

set of variables, it is easy to compute the associated basic solution. We can start by

setting the values of all nonbasic variables to zero. The resulting system of equa-

tions will then involve only the basic variables. Since the system is triangular the

basic variables can be easily evaluated by applying the ﬁrst deﬁnition of triangu-

larity deﬁned above. The following is known as the Fundamental Theorem for the

Transportation Problem.

THEOREM 8.3 (Basis Triangularity) Every basis of the transportation prob-

lem (8.3) is triangular.

Example 8.5 (Illustration of the Basis Triangularity Theorem) Suppose on the

contrary that the set of basic variables are those circled in Figure 8-2 and they do not

have the property that there is an equation (i.e., a row or column) with exactly one circled

(basic) variable. Then every row and every column has two or more circled variables.

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

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