262 SolutionsB, =100
010
001
001
001
010
100
001
100
00 1
000
100
010
010
100000
000
000
100
010
001
000
000
000
000
000
000
000
000
000000
000
000
000
000
000
100
0 10
00 1
000
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
00 1c^ = [5 4600000000000 0]2/i =CTB 1 BI l = [Aw] [5,4,6|0].
Then, the lengths of arcs are c&a + wa = 1 + 0 = 1, V arcs.
For commodity one, the minimum shortest path (P2 : a464d4
m-$ p) other than Pi has length 5 which is equal to the corresponding dual
variable 7Ti = 5. For commodity two, the minimum shortest path has length 6
which is strictly greater than the corresponding dual variable n2 = 4. However,
P12 : k i->- j i-t h i-+ i has length 4 < 6 = ^3! Thus, /12 enters to the basis
with the updated column
{B-lA^12 )T =[001-1-100-11000000]and the updated RHS is
XBl = (Bllb)T =[fl h /l3 H Sd Se Sf Sg Sh Sj Si Sm Sn S 0 Sp]XTBY = (B^bf = [10 10 10 0 0 0 0 0 0 0 10 0 0 0 0] ,therefore the slack variable corresponding to arc h, s/,, leaves.