15.082J and 6.855J and ESD.78JSuccessive Shortest Path Algorithm2The Original Costs and Node Potentials123 54412256700 0003The Original Capacities and Supplies/Demands123 5410202025252030235 -2-7-194Select a supply node and find the shortest paths123 54412256770688shortest path distanceThe shortest path tree is marked in bold and blue.5Update the Node Potentials and the Reduced Costs123 5441225670-7 -8-8-60000636Send Flow From a Supply Node to a Demand Node Along Shortest Paths(along arcs with reduced costs of 0)123 5410202025252030235 -2-7-19send 7 units from node 1 to node 3Arc numbers are residual capacities.Red arcs have a reduced cost of 07Update the Residual Network123 5410202025251330235 -2-7-19Arc (3,1) has a reduced cost of 07160If an arc is added to G(x), then it has a reduced cost of 0, and it is red.Arcs in the residual network will always have a non-negative reduced cost8A commentAt this point, one would choose a source node, and then find the shortest path from the source node to all other nodes, and then update the residual network.However, there are still paths of 0 reduced cost in the residual network, and it makes sense to use them. This heuristic is quite useful in practice.9Send Flow From a Supply Node to a Demand Node Along Shortest Paths123 54102020252513305 -2-19Send 2 units of flow from node 1 to node 47160Recall that red arcs have a reduced cost of 010Update the Residual Network123 54102018252511305 -2-192 units of flow were sent from node 1 to node 4 on 1-3-49160214011Send Flow From a Supply Node to a Demand Node Along Shortest Paths123 54102018252511305-19Send flow from node 1 to node 5902140How much flow should be sent?12Update the Residual Network123 541020181425305-1911 units of flow were sent from node 1 to node 52002140113-813Select a supply node and find the shortest paths123 5410-7 -8-8-600006300The shortest path tree is marked in bold and blue.The values on the nodes are the current node potentials14Update the node potentials and the reduced costs123 5410-7 -8-8-603003300-11-11-90To obtain new node potentials, subtract the shortest path distances from the old potentials.15Send Flow From a Supply Node to a Demand Node Along Shortest Paths123 541020181425305Send flow from node 1 to node 520020113-8How much flow will be sent?16Update the Residual Network123 548202012252852000131-8223-62 units of flow were sent from node 1 to node 517Select a supply node and find the shortest paths123 5410-7 -11-11-9030030000The shortest path tree is marked in bold and blue.18Update the Node Potentials and the Reduced Costs123 5400-7 -11-12-10040120000-9-11To obtain the new node potential, subtract the shortest path distance from the old potential.19Send Flow From a Supply Node to a Demand Node Along Shortest Paths123 54820201225285200013122-6Send flow from node 2 to node 5How much flow can be sent?20Update the Residual Network123 54315201225285200013127-60-155 units of flow were sent from node 2 to node 6.21Send Flow From a Supply Node to a Demand Node123 54315201225282000131270-15Send flow from node 1 to node 522Update the Residual Network123 542142012252720001313800-161 unit of flow was sent from node 1 to node 5.0The resulting flow is feasible, and also optimal.23The Final Optimal Flow123 5410,820,62025,132520,2030,3235 -2-7-1924The Final Optimal Node Potentials and the Reduced Costs123 5400-7 -11-12-100-40120Flow is at upper boundFlow is at lower bound.MIT OpenCourseWarehttp://ocw.mit.edu 15.082J / 6.855J / ESD.78J Network OptimizationFall 2010 For information about citing these materials or our Terms of Use, visit:
View Full Document