最 低 价：￥43.20
定 价：￥108.00
作 者：Ravindra K.Ahuja,Thomas L.Magnanti,James B.Orlin 著
出 版 社：机械工业出版社
出版时间：2005 年5月
I S B N：7111159195
| 拉文德拉K．间胡亚 印度理工学院坎普尔分校工业与管理工程系副教授。1986年至1988年，他曾在麻省理工学院斯隆管理学院做访问学者，与沃林教授合作研究若干网络流问题的快速算法，这期间的工作促成了本书的面世。他的研究方向为网络流、组合优化、算法的计算测试。 托马斯L．马南提 麻省理工学院斯隆管理学院管理科学系教授。他曾任美国运筹学会的会长和《OperationsResearch》杂志的主编。他是美国国家工程院院士。他的研究方向为大规模优化，包括网络设计、整数规划及其在通信、制造和交.. << 查看详细 |
| 前言 1 introduction, 1 1.1 introduction, 1 1.2 network flow problems, 4 1.3 applications, 9 1.4 summary, 18 reference notes, 19 exercises, 20 2 paths, trees, and cycles, 28 2.1 introduction, 23 2.2 notation and definitions, 24 2.3 network representations, 31 2.4 network transformations, 38 2.5 summary, 46 reference notes, 47 exercises, 47 3 algorithm design and analysis, 58 3.1 introduction, 53 3.2 complexity analysis, 56 3.3 developing polynomial-time algorithms, 66 .3.4 search algorithms, 73 3.5 flow decomposition algorithms, 79 3.6 summary, 84 reference notes, 85 exercises, 86 4 shortest patio: label-setting alg-orithms, 93 4.1 introduction, 93 4.2 applications, 97 4.3 tree of shortest paths, 106 4.4 shortest path problems in acyclic networks, 107 4.5 dijkstra's algorithm, 108 4.6 dial's implementation, 113 4.7 heap implementations, 115 4.8 radix heap implementation, 116 4.9 summary, 121 reference notes, 122 exercises, 124 5 shortest paths:label-correcting algorithm,133 5.1 introduction, 133 5.2 optimality conditions, 135 5.3 generic label-correcting algorithms, 136 5.4 special implementations of the modified label-correcting algorithm, 141 5.5 detecting negative cycles, 143 5.6 all-pairs shortest path problem, 144 5.7 minimum cost-to-time ratio cycle problem, 150 5.8 summary, 154 reference notes, 156 exercises, 157 6 maximum flows:basicc ideas, 168 6.1 introduction, 166 6.2 applications, 169 6.3 flows and cuts, 177 6.4 generic augmenting path algorithm, 180 6.5 labeling algorithm and the max-flow min-cut theorem, 184 6.6 combinatorial implications of the max-flow min-cut theorem, 188 6.7 flows with lower bounds, 191 6.8 summary, 196 reference notes, 197 exercises, 198 7 maximum flows:polynomial alg-orithms,2o7 7.1 introduction, 207 7.2 distance labels, 209 7.3 capacity scaling algorithm, 210 7.4 shortest augmenting path algorithm, 213 7.5 distance labels and layered networks, 221 7.6 generic prefiow-push algorithm, 223 7.7 fifo prefiow-push algorithm, 231 7.8 highest-label prefiow-push algorithm, 233 7.9 excess scaling algorithm, 237 7.10 summary, 241 reference notes, 241 exercises, 243 8 maximum flows:additional topics,25o 8.1 introduction, 250 8.2 flows in unit capacity networks, 252 8.3 flows in bipartite networks, 255 8.4 flows in planar undirected networks, 260 8.5 dynamic tree implementations, 265 8.6 network connectivity, 273 8.7 all-pairs minimum value cut problem, 277 8.8 summary, 285 reference notes, 287 exercises, 288 9 minlmum cost flows:basic algorithms,294 9.1 introduction, 294 9.2 applications, 298 9.3 optimality conditions, 306 9.4 minimum cost flow duality, 310 9.5 relating optimal flows to optimal node potentials, 315 9.6 cycle-canceling algorithm and the integrality property, 317 9.7 successive shortest path algorithm, 320 9.8 primal-dual algorithm, 324 9.9 out-of-kilter algorithm, 326 9.10 relaxation algorithm, 332 9.11 sensitivity analysis, 337 9.12 summary, 339 reference notes, 341 exercises, 344 10 minimum cost flows:polynomial algorithms,357 10.1 introduction, 357 10.2 capacity scaling algorithm, 360 10.3 cost scaling algorithm, 362 10.4 double scaling algorithm, 373 10.5 minimum mean cycle-canceling algorithm, 376 10.6 repeated capacity scaling algorithm, 382 10.7 enhanced capacity scaling algorithm, 387 10.8 summary, 395 reference notes, 396 exercises, 397 11 minimum cost flows: network simplex algorithms, 402 11.1 introduction, 402 11.2 cycle free and spanning tree solutions, 405 11.3 maintaining a spanning tree structure, 409 11.4 computing node potentials and flows, 411 11.5 network simplex algorithm, 415 11.6 strongly feasible spanning trees, 421 11.7 network simplex algorithm for the shortest path problem, 425 11.8 network simplex algorithm for the maximum flow problem, 430 11.9 related network simplex algorithms, 433 11.10 sensitivity analysis, 439 11.11 relationship to simplex method, 441 11.12 unimodularity property, 447 11.13 summary, 450 reference notes, 451 exercises, 453 12 assignments and matchings, 461 12.1 introduction, 461 12.2 applications, 463 12.3 bipartite cardinality matching problem, 469 12.4 bipartite weighted matching problem, 470 12.5 stable marriage problem, 473 12.6 nonbipartite cardinality matching problem, 475 12.7 matchings and paths, 494 12.8 summary, 498 reference notes, 499 exercises, 501 13 minimum spanning trees, 510 13.1 introduction, 510 13.2 applications, 512 13.3 optimality conditions, 516 13.4 kruskai's algorithm, 520 13.5 prim's algorithm, 523 13.6 sollin's algorithm, 526 13.7 minimum spanning trees and matroids, 528 13.8 minimum spanning trees and linear programming, 530 13.9 summary, 533 reference notes, 535 exercises, 536 14 convex cost flows, 543 14.1 introduction, 543 14.2 applications, 546 14.3 transformation to a minimum cost flow problem, 551 14.4 pseudopolynomial-time algorithms, 554 14.5 polynomial-time algorithm, 556 14.6 summary, 560 reference notes, 561 exercises, 562 15 generalixed flows, 568 15.1 introduction, 566 15.2 applications, 568 15.3 augmented forest structures, 572 15.4 determining potentials and flows for an augmented forest structure, 577 15.5 good augmented forests and linear programming bases, 582 15.6 generalized network simplex algorithm, 583 15.7 summary, 591 reference notes, 591 exercises, 593 16 lagrangian relaxation and network optlmization, 598 16.1 introduction, 598 16.2 problem relaxations and branch and bound, 602 16.3 lagrangian relaxation technique, 605 16.4 lagrangian relaxation and linear programming, 615 16.5 applications of lagrangian relaxation, 620 16.6 summary, 635 reference notes, 637 exercises, 638 17 multicommodity flows, 649 17.1 introduction, 649 17.2 applications, 653 17.3 optimality conditions, 657 17.4 lagrangian relaxation, 660 17.5 column generation approach, 665 17.6 dantzig-woffe decomposition, 671 17.7 resource-directive decomposition, 674 17.8 basis partitioning, 678 17.9 summary, 682 reference notes, 684 exercises, 686 18 computational testing of algorithms, 695 18.1 introduction, 695 18.2 representative operation counts, 698 18.3 application to network simplex algorithm, 702 18.4 summary, 713 reference notes, 713 exercises, 715 19 additional applications, 717 19.1 introduction, 717 19.2 maximum weight closure of a graph, 719 19.3 data scaling, 725 19.4 science applications, 728 19.5 project management, 732 19.6 dynamic flows, 737 19.7 arc routing problems, 740 19.8 facility layout and location, 744 19.9 production and inventory planning, 748 19.10 summary, 755 reference notes, 759 exercises, 760 appendix a data structures, 765 a.1 introduction, 765 a.2 elementary data structures, 766 a.3 d-heaps, 773 a.4 fibonacci heaps, 779 reference notes, 787 appendix b n9-completeness, 788 b.1 introduction, 788 b.2 problem reductions and transformations, 790 b.3 problem classes 9,n9, n9-complete, and n9-hard, 792 b.4 proving n9-completeness results, 796 b.5 concluding remarks, 800 reference notes, 801 appendix c linear programming, 802 c.1 introduction, 802 c.2 graphical solution procedure, 804 c.3 basic feasible solutions, 805 c.4 simplex method, 810 c.5 bounded variable simplex method, 814 c.6 linear programming duality, 816 reference notes, 820 references, 821 index, 84o |
内容加载中，请稍后...
商品评论（0条）