DOC PREVIEW
MIT 15 082J - MITA

This preview shows page 1-2-24-25 out of 25 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

MIT 15 082J - MITA

Download MITA
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view MITA and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view MITA 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?