Principles of Mathematics in Operations Research

264 Solutions

Ba

100

0 10

00 1

101

101

010

000

001

000

001

000

100

010

010

000

000

000

000

100

0 10

001

000

000

000

000

000

000

000

000

000

0000

0000

0010

0000

0000

0000

1000

0 100

0010

00 11

0000

0000

0000

0000

0000

00000

00000

00000

00000

00000

00000

00000

00000

00000

00000

10000

01000

00100

00010

00001

cl 3 = [5 4600000400000 0]

2/3 = [5 4 6J0 0 0 0 0 -2000000]

Then, the lengths of arcs are Cka + wa = 1 + 0 = 1, V arcs except arc h, whose

length is 1 — 2 = —1. For all the three commodities, the minimum shortest

distances between the source and the sink nodes are greater and equal to the

corresponding dual variables. Therefore, the current solution given below is

optimal.

X^3 = (B 3 lb)T = [h h /l3 Sb Sd Se Sf Sg /l2 Sj Si Sm Sn S 0 Sp]

xl 3 = (B^bf =[ 10 10 0 0 0 0 10 10 10 0 10 0 0 0 10]

The optimum solution is depicted in Figure S.16.

e) When the number of variables (columns of A) is huge, the following ques-
tion is asked: Can one generate column A* by some oracle that can answer
the question, Does there exist a column with with reduced cost < 0? If so,
the oracle returns one. So, the sketch of so called "A Column Generation
Algorithm" is given below:

SI. Solve LP(J):

mm

for some J C I — {1,..., n).
S2. Using dual variables 7r that are optimal for LP(J), ask the oracle if there
exists j 0 J such that CjirA^ < 0. If so, add it to J and perform pivot(s)
to solve new LP(J); Go back SI. If not, we have the optimal solution to
LP over all columns.