15.082J and 6.855J and ESD.78JCycle Canceling Algorithm2A minimum cost flow problem12 43 510, $420, $120, $225, $225, $520, $630, $725000 -253The Original Capacities and Feasible Flow12 43 510,1020,2020,1025,525,1520,030,2525000 -25The feasible flow can be found by solving a max flow.4Capacities on the Residual Network12 43 5102020525101015520105Costs on the Residual Network12 43 52267-7-5-2-2-1-45Find a negative cost cycle, if there is one.6Send flow around the cycleSend flow around the negative cost cycle12 43 5202515The capacity of this cycle is 15.Form the next residual network.7Capacities on the residual network12 43 5102052010102552010158Costs on the residual network12 43 52267-7-2-2-1-4-6Find a negative cost cycle, if there is one.59Send flow around the cycle12 43 5Send flow around the negative cost cycleThe capacity of this cycle is 10.Form the next residual network.20201010Capacities on the residual network12 43 510105201020251510151011Costs in the residual network12 43 5122567-7-6-2-1-4Find a negative cost cycle, if there is one.12Send Flow Around the Cycle12 43 5Send flow around the negative cost cycleThe capacity of this cycle is 5.Form the next residual network.105102013Capacities on the residual network12 43 55102551525151020105514Costs in the residual network12 43 51227-7-6-2-1-44-25Find a negative cost cycle, if there is one.15Send Flow Around the CycleSend flow around the negative cost cycleThe capacity of this cycle is 5.Form the next residual network.12 43 51010516Capacities on the residual network12 43 55152552025205205517Costs in the residual network12 43 51227-7-6-2-1-445Find a negative cost cycle, if there is one.There is no negative cost cycle. But what is the proof?18Compute shortest distances in the residual network12 43 51227-7-6-2-1-445Let d(j) be the shortest path distance from node 1 to node j.Next let p(j) = -d(j)07111210And compute cp19Reduced costs in the residual network12 43 5071112100020-0400001The reduced costs in G(x*) for the optimal flow x* are all non-negative.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
Unlocking...