網絡流
內容簡介
本書共分4章，全面地敘述了網絡上最大流的算法、理論及其在其他組合優化問題上的應用。第1章詳述了網絡流問題的數學模型，提出了尋求可擴充路的標號法，在此基礎上得到了關於網絡上最大流的標號算法，即著名的福特—弗爾克遜算法，以及具有重大理論價值的最大流—最小截集定理。本章是全書的核心。第2章利用最大流—最小截集定理統一了一些已有的組合問題的可行性定理(即可行解的存在條件)。這些問題的解與條件存在整數依賴性，受此啟發還在本章探索了把網絡流方法應用於其他具有這類性質的組合問題。第3章介紹了網絡流算法在最小費用流問題上的應用。這是原始對偶算法(1956年由丹澤，福特，弗爾克遜合作基於線性規劃鬆弛互補定理而提出的解一般線性規劃的算法)在組合最優化問題成功得到應用的一個典型例子。敘述從運輸問題的原始對偶算法開始，再引導到一般網絡上最小費用流的算法，並附帶介紹了算法對其他一些組合問題的應用。作為網絡流概念的推廣。第4章介紹了多重端點流的問題。以高墨瑞與胡兩人的工作為基礎，本章就無向網絡的情況介紹了多重端點定理。
作者簡介
迪·瑞·弗爾克遜(Delbert Ray Fulkerson，1924—1976)，美國數學家，近代組合最優化與多面體組合理論的開創人之一。1951年進入朗特公司，歷任朗特公司研究員，康奈爾大學運籌學教授，畢生從事運籌數學研究。小萊·福特，美國數學家，曾在朗特公司與弗爾克遜合作從事運籌學研究。