Principles of Mathematics in Operations Research

260 Solutions

and the formulation will be

Min 5/i + • • • + 10/ 20

s.t.

A + • • • + /e = 10

h + • • • + hi = 10

/12 + • • • + /20 = 10

fl+f2 + f 3 + U + h + f6< 10

/l + /2 + /3 + h + h + k + /l6 + /l9 + /20 < 10

/l,--- ,/20 > 0 (integer)

The first three constraints make the capacity constraints for arcs a, c, i

and k redundant.

c)

Wa -B- ]P ^ iap/p < t/a

TTfc «-» ]T] fp= Dk

P<EVk

Then, the reduced cost of a path P will be

^(Cia + Wa) -TTfc,

and the current solution is optimal when

min I YVcfca + wa) } > ^k, Vfc.

°^

k

P6V [ftp J

The above problem is equivalent to find the shortest path between s^ and t^
using arc costs Cfc 0 + wa for each commodity k. The problem is decomposed
into K single commodity shortest path problems with a dynamic objective
function that favors paths with arcs that have not appeared many times in
current paths.

d)

[fli f2i f3, f4, fei f6i f7, f8, f9, flQ, fll, fl2, fl3, fl4, flbi fl6i fl7i flS, fl9, f2o\

l^bi Sd-> ^ei &f 1 Sg-> ^/i; $j 1 &fo $mi Sni ^01 Sp\*