8.3 最大流问题Maximal Flow ProblemCh8 网络模型 Network Model8.3 最大流问题Maximal Flow Problem8.3.1 基本概念8145633810763图8184图618所示的网络图中定义了一个发点v1，称为源(source，supply node)，定义了一个收点v7，称为汇(sink，demand node)，其余点v2，v3，v6为中间点，称为转运点(transshipment nodes)。如果有多个发点和收点，则虚设发点和收点转化成一个发点和收点。图中的权是该弧在单位时间内的最大通过能力，称为弧的容量(capacity)。最大流问题是在单位时间内安排一个运送方案，将发点的物质沿着弧的方向运送到收点，使总运输量最大。 Ch8 网络模型 Network Model设cij为弧(i，j)的容量，fij为弧(i，j)的流量。容量是弧(i，j)单位时间内的最大通过能力，流量是弧(i，j)单位时间内的实际通过量，流量的集合f=fij称为网络的流。发点到收点的总流量记为v=val(f)，v也是网络的流量。 图618最大流问题的线性规划数
