Solutions 263Bn1 00
0 10
00 1
001
001
010
100
00 1
100
001
000
100
010
010
100000
000
000
100
010
00 1
000
000
000
000
000
000
000
000
000000
000
001
000
000
000
100
010
001
00 1
000
000
000
000
000000
000
000
000
000
000
000
000
000
100
0 10
001
000
000
000000
000
000
000
000
000
000
000
000
000
000
000
100
010
001cl 2 = [5 4600000400000 0]2/2 = [7 4 6|0 0 0 0 0-2 0 0 0 0 0 0]Then, the lengths of arcs are Cka + u> 0 = 1+0 = 1, V arcs except arc h, whose
length is 1 - 2 = -1.
For commodity one, the minimum shortest path P2 : a^b^d^m^-p
has length 5, which is strictly less than the corresponding dual variable wi = 7.
Thus, fi enters to the basis with the updated column
{B^lA^2 )T =[101000-1-1-100000-1]and the updated RHS is
XB 2 = (B 2 lb)T = [fl h /l3 Sb Sd Se Sf Sg /12 Sj Si Sm Sn S 0 Sp]xTB2 = (B^bf = [10 10 10 0 0 0 0 0 0 0 10 0 0 0 0] ;therefore, either /x or fa leaves. We choose /1!