Chapter 7. Network Optimization Problems 第七章. 网络最优化问题

获奖实例 法国国家铁路网每年运载约5000万乘客 通过网络最优化问题来适应乘客的喜好，并且调整日运行量来满足需求 每年增加收入1500万美元，降低成本的同时提高了服务质量 获得了1997年度弗兰茨.厄德曼一等奖

Table of Contents (主要内容) Minimum-Cost Flow Problems (Section 7.1)(最小费用流问题) A Case Study: The BMZ Maximum Flow Problem (Section 7.2)(案例研究：BMZ公司的最大流问题) Maximum Flow Problems (Section 7.3)(最大流问题)

Table of Contents (主要内容) Shortest Path Problems: Littletown Fire Department (Section 7.4)(最短路问题：里特城的消防队问题) Shortest Path Problems: General Characteristics (Section 7.4)(最短路问题：一般特征) Shortest Path Problems: Minimizing Sarah’s Total Cost (Section 7.4)(最短路问题：最小化莎拉的总成本问题)

Table of Contents (主要内容) Shortest Path Problems: Minimizing Quick’s Total Time (Section 7.4)(最短路问题：最小化奎克公司总时间问题) Minimum Spanning Trees: The Modern Corp. Problem (Section 7.5)(最小支撑树问题：摩登公司问题)

Distribution Unlimited Co. Problem The Distribution Unlimited Co. has two factories producing a product that needs to be shipped to two warehouses (无限配送公司有两个工厂生产产品，这些产品需要运到两个仓库里) Factory 1 produces 80 units. (工厂1生产80个单位) Factory 2 produces 70 units. (工厂2生产70个单位) 最小费用流问题

Distribution Unlimited Co. Problem Warehouse 1 needs 60 units. (仓库1需要60个单位) Warehouse 2 needs 90 units. (仓库2需要90个单位) There are rail links directly from Factory 1 to Warehouse 1 and Factory 2 to Warehouse 2. (在工厂1和仓库1之间以及工厂2和仓库2之间各有一条铁路运输轨道)

Distribution Unlimited Co. Problem Independent truckers are available to ship up to 50 units from each factory to the distribution center, and then 50 units from the distribution center to each warehouse. (卡车司机至多可以从工厂运输50个单位到配送中心，然后可以从配送中心运输50个单位到仓库)

The Distribution Network

Data for Distribution Network

A Network Model

Distribution Unlimited Co. Problem How many units (truckloads) should be shipped along each shipping lane? 每条路线应该运送多少单位的产品？

The Optimal Solution

Terminology for Minimum-Cost Flow Problems The model for any minimum-cost flow problem is represented by a network with flow passing through it. (所有最小费用流问题都是用带有通过其中的流的网络表示的) The circles in the network are called nodes. (网络中的圆圈被称为节点)

Terminology for Minimum-Cost Flow Problems Each node where the net amount of flow generated (outflow minus inflow) is a fixed positive number is a supply node. (如果节点产生的净流量[流出减去流入]是一个确定的正数的话，这个节点就是供应点) Each node where the net amount of flow generated is a fixed negative number is a demand node. (如果节点产生的净流量是一个确定的负数的话，那么这个节点就称为需求点)

Terminology for Minimum-Cost Flow Problems Any node where the net amount of flow generated is fixed at zero is a transshipment node. Having the amount of flow out of the node equal the amount of flow into the node is referred to as conservation of flow. (如果节点产生的净流量恒为零，那么这个节点就称为转运点，我们把流出节点的量等于流入节点的量称为流量守恒)

Terminology for Minimum-Cost Flow Problems The arrows in the network are called arcs. (网络中的箭头称为弧) The maximum amount of flow allowed through an arc is referred to as the capacity of that arc. (允许通过某一条弧的最大流量称为该弧的容量)

Assumptions of a Minimum-Cost Flow Problem At least one of the nodes is a supply node. (至少有一个节点是供应点) At least one of the other nodes is a demand node. (至少有一个节点是需求点) All the remaining nodes are transshipment nodes. (所有剩下的节点都是转运点)

Assumptions of a Minimum-Cost Flow Problem Flow through an arc is only allowed in the direction indicated by the arrowhead, where the maximum amount of flow is given by the capacity of that arc. (If flow can occur in both directions, this would be represented by a pair of arcs pointing in opposite directions.) (通过弧的流只允许沿着箭头的方向流动，通过弧的最大流量取决于该弧的容量[如果流是双向的话，则需要用一对箭头指向相反的弧来表示])

Assumptions of a Minimum-Cost Flow Problem The network has enough arcs with sufficient capacity to enable all the flow generated at the supply nodes to reach all the demand nodes. (网络中有足够的弧提供足够的容量，使得所有在供应点中产生的流都能够达到需求点)

Assumptions of a Minimum-Cost Flow Problem The cost of the flow through each arc is proportional to the amount of that flow, where the cost per unit flow is known. (在流的单位成本已知的前提下，通过每一条弧的流的成本和流量成正比)

Assumptions of a Minimum-Cost Flow Problem The objective is to minimize the total cost of sending the available supply through the network to satisfy the given demand. (An alternative objective is to maximize the total profit from doing this.) (最小费用流问题的目标是在满足给定需求的条件下，使得通过网络供应的总成本最小[或通过这样做使得总利润最大化])

Properties of Minimum-Cost Flow Problems The Feasible Solutions Property: Under the previous assumptions, a minimum-cost flow problem will have feasible solutions if and only if the sum of the supplies from its supply nodes equals the sum of the demands at its demand nodes. (具有可行解的特征：在以上假设下，当且仅当供应点所提供的流量总和等于需求点所需要的流量总和时，最小费用流问题有可行解)

Properties of Minimum-Cost Flow Problems The Integer Solutions Property: As long as all the supplies, demands, and arc capacities have integer values, any minimum-cost flow problem with feasible solutions is guaranteed to have an optimal solution with integer values for all its flow quantities. (具有整数解的特征：只要其所有的供应、需求和弧的容量都是整数值，那么任何最小费用流问题的可行解就一定有所有流量都是整数的最优解)

Spreadsheet Model

The SUMIF Function The SUMIF formula can be used to simplify the node flow constraints. (SUMIF公式可以简化节点流约束) SUMIF(Range A, x, Range B) For each quantity in (Range A) that equals x, SUMIF sums the corresponding entries in (Range B). (区域A中的每一个量满足条件x时，SUMIF函数就会计算区域B中相应内容之和) The net outflow (flow out – flow in) from node x is then (节点x的净流出[流出-流入]就等于) SUMIF(“From labels”, x, “Flow”) – SUMIF(“To labels”, x, “Flow”)

Typical Applications of Minimum-Cost Flow Problems

The BMZ Maximum Flow Problem The BMZ Company is a European manufacturer of luxury automobiles. Its exports to the United States are particularly important. (BMZ公司是欧洲一家生产豪华汽车的制造商，其产品出口到美国尤为重要) 最大流问题

The BMZ Maximum Flow Problem BMZ cars are becoming especially popular in California, so it is particularly important to keep the Los Angeles center well supplied with replacement parts for repairing these cars. (BMZ公司的汽车尤其在加利福尼亚大受欢迎，因此保持洛杉矶中心零部件的充足供给，以便及时维修这些汽车就显得特别重要了)

The BMZ Maximum Flow Problem BMZ needs to execute a plan quickly for shipping as much as possible from the main factory in Stuttgart, Germany to the distribution center in Los Angeles over the next month. (BMZ公司需要迅速执行一项计划，下个月要从位于斯图加特和德国的主要工厂运送尽可能多的配件到洛杉矶的配送中心)

The BMZ Maximum Flow Problem The limiting factor on how much can be shipped is the limited capacity of the company’s distribution network. (配件运送数量的限制因素就是公司配送网络的容量)

The BMZ Distribution Network

A Network Model for BMZ

The BMZ Maximum Flow Problem How many units should be sent through each shipping lane to maximize the total units flowing from Stuttgart to Los Angeles? 通过每一条运送路线应该运送多少配件，才能使从斯图加特到洛杉矶的总流量最大？

Spreadsheet Model for BMZ

Assumptions of Maximum Flow Problems All flow through the network originates at one node, called the source, and terminates at one other node, called the sink. (The source and sink in the BMZ problem are the factory and the distribution center, respectively.) (网络中所有流起源于一个节点，这个节点叫作源[起点]，所有的流终止于另一个节点，这个节点叫作收点[终点]。BMZ问题中的源和收点分别代表工厂和配送中心)

Assumptions of Maximum Flow Problems All the remaining nodes are transshipment nodes. (其余所有的节点叫作转运点) Flow through an arc is only allowed in the direction indicated by the arrowhead, where the maximum amount of flow is given by the capacity of that arc. At the source, all arcs point away from the node. At the sink, all arcs point into the node. (通过每一个弧的流只允许沿着弧的箭头所指方向流动。由源发出的所有的弧背向源，而所有终结于收点的弧都指向收点)

Assumptions of Maximum Flow Problems The objective is to maximize the total amount of flow from the source to the sink. This amount is measured in either of two equivalent ways, namely, either the amount leaving the source or the amount entering the sink. (最大流问题的目标是使得从源到收点的总流量最大。这个流量的大小可以用两种等价的方法来衡量，分别叫作从源点出发的流量和进入收点的流量)

最大流问题和最小费用流问题区别 最小费用流问题：供应点、需求点 最大流问题：源、收点 最小费用流问题的供应量和需求量都是固定的，而最大流问题的源和收点却不是 最小费用流问题的供应点和需求点可能有多个，但最大流问题的源和收点只有一个

BMZ with Multiple Supply and Demand Points BMZ has a second, smaller factory in Berlin. (BMZ公司在柏林还有一家更小的工厂) The distribution center in Seattle has the capability of supplying parts to the customers of the distribution center in Los Angeles when shortages occur at the latter center. (一旦洛杉矶配送中心出现缺货，位于西雅图的配送中心就可以给有关的客户供应配件)

Network Model for The Expanded BMZ Problem

BMZ with Multiple Supply and Demand Points How many units should be sent through each shipping lane to maximize the total units flowing from Stuttgart and Berlin to Los Angeles and Seattle? 通过每一条运送路线应该运送多少配件，才能使从斯图加特和柏林到洛杉矶和西雅图的总流量最大？

Spreadsheet Model

Some Applications of Maximum Flow Problems Maximize the flow through a distribution network, as for BMZ. (通过配送网络的流量最大，如BMZ问题) Maximize the flow through a company’s supply network from its vendors to its processing facilities. (通过从供应商到处理设施的公司供应网络的流量最大) Maximize the flow of oil through a system of pipelines. (通过管道运输系统运送的油量最大)

Some Applications of Maximum Flow Problems Maximize the flow of water through a system of aqueducts. (最大化通过输水系统的水量) Maximize the flow of vehicles through a transportation network. (通过交通网络的车流量最大)

Littletown Fire Department Littletown is a small town in a rural area. (里特城是一个农村的小镇) Its fire department serves a relatively large geographical area that includes many farming communities. (它的消防队要为包括许多农场社区在内的大片地区提供服务) 最短路问题

Littletown Fire Department Since there are numerous roads throughout the area, many possible routes may be available for traveling to any given farming community. (在这个地区有很多路，从消防站到任何一个社区都有很多条路线可供选择)

The Littletown Road System

The Network Representation

Littletown Fire Department Which route from the fire station to a certain farming community minimizes the total number of miles? 从消防站到某个特定的农场社区的最短路线是那条？

1959年，Dijkstra提出 算法步骤： 步骤1：起点是已标号点，标号为0 步骤2：从所有已标号点向未标号点扩散，得到未标号点的临时标号 最短路问题的标号法 1959年，Dijkstra提出 算法步骤： 步骤1：起点是已标号点，标号为0 步骤2：从所有已标号点向未标号点扩散，得到未标号点的临时标号

最短路问题的标号法 上述公式也用于更新临时标号点的临时标号

步骤3：某临时标号点的所有可能标号的最小值即是其最终标号，此时将该临时标号点标记为已标号点，并记录其前一节点 最短路问题的标号法 步骤3：某临时标号点的所有可能标号的最小值即是其最终标号，此时将该临时标号点标记为已标号点，并记录其前一节点

最短路问题的标号法 步骤4：重复步骤2和3直至找到最短路线，此时得到的最终标号即为其最短路线的长度

优点：Dijkstra的标号法是求解最短路问题的最优化算法，也是目前最好的算法，而且可以求得起点到各点的最短路 最短路问题的标号法 优点：Dijkstra的标号法是求解最短路问题的最优化算法，也是目前最好的算法，而且可以求得起点到各点的最短路

最短路问题的标号法 算例

Spreadsheet Model

Assumptions of a Shortest Path Problem You need to choose a path through the network that starts at a certain node, called the origin, and ends at another certain node, called the destination. (在 网络中选择一条路，这条路始于某一 节点，这节点叫作源，终于另一个节 点，这个节点叫作目标地)

Assumptions of a Shortest Path Problem The lines connecting certain pairs of nodes commonly are links (which allow travel in either direction), although arcs (which only permit travel in one direction) also are allowed. (连接两个节点的连线通常叫作边 [允许任一个方向的行进]，虽然也允许存 在弧[只允许沿着一个方向行进])

Assumptions of a Shortest Path Problem Associated with each link (or arc) is a nonnegative number called its length. (Be aware that the drawing of each link in the network typically makes no effort to show its true length other than giving the correct number next to the link.) (和每条边相关的一个非负数，叫作该边 的长度[注意：在网络中，除了在边的旁边表明 了其长度的准确数字以外，所画的每一条边的长 度并不表明其真实的长度])

Assumptions of a Shortest Path Problem The objective is to find the shortest path (the path with the minimum total length) from the origin to the destination. (目标是寻找从源点到目 标地的最短路线[总长度最小的路])

Applications of a Shortest Path Problem Minimize the total distance traveled. (行进的总距离最小) Minimize the total cost of a sequence of activities. (一系列活动的总成本最小) Minimize the total time of a sequence of activities. (一系列活动的总时间最小)

Minimizing Total Cost: Sarah’s Car Fund Sarah has just graduated from high school. (莎拉刚刚高中毕业) As a graduation present, her parents have given her a car fund of $21,000 to help purchase and maintain a three-year-old used car for college. (在毕业典礼上，她的父母给了她21000美元的汽车基金帮助她购买并保养一辆使用了三年的二手车，以供她上大学使用)

Minimizing Total Cost: Sarah’s Car Fund Since operating and maintenance costs go up rapidly as the car ages, Sarah may trade in her car on another three-year-old car one or more times during the next three summers if it will minimize her total net cost. (At the end of the four years of college, her parents will trade in the current used car on a new car for Sarah.)

Minimizing Total Cost: Sarah’s Car Fund 由于开车费用和维修费用随着汽车的老化而飞速上涨，所以，如果能够最小化总的净成本，莎拉可能在接下来的三个夏天里，一次或多次折价将她的汽车置换为其他使用了三年的二手车。四年后，莎拉的父母会把她的旧车置换成一辆新车，作为莎拉的毕业礼物。

Sarah’s Cost Data

Minimizing Total Cost: Sarah’s Car Fund When should Sarah trade in her car (if at all) during the next three summers? 在接下来的三个夏天里，莎拉应该何时折价卖掉她的汽车？如何考虑？如何转换成最短路问题？

Shortest Path Formulation 权=购买成本+总使用和维护成本-销售收入

Spreadsheet Model

Minimizing Total Time: Quick Company The Quick Company has learned that a competitor is planning to come out with a new kind of product with great sales potential. (奎克公司获悉它的一个竞争对手计划将把一种很有销售潜力的新产品投放市场) Quick has been working on a similar product that had been scheduled to come to market in 20 months. (奎克公司也一直在研制一种类似的产品，并计划在20个月后投放市场)

Minimizing Total Time: Quick Company Quick’s management wishes to rush the product out to meet the competition. (奎克公司的管理者希望迅速推出产品去参与竞争) Each of four remaining phases can be conducted at a normal pace, at a priority pace, or at crash level to expedite completion. However, the normal pace has been ruled out as too slow for the last three phases. (现在还有四个阶段没有完成，每个阶段都可以正常水平、优先水平和应急水平加速完成。正常水平由于后三个阶段的实施速度太慢而被排除了) $30 million is available for all four phases. (有3000万美元用于这四个阶段的实施过程)

Time and Cost of the Four Phases

Minimizing Total Time: Quick Company At what pace should each of the four phases be conducted? 每个阶段应该以什么样的速度进行？如何考虑？如何转换成最短路问题？

Shortest Path Formulation 虚拟节点 节点: (阶段, 剩余资金)；弧: 活动；权: 时间

Spreadsheet Model

The Optimal Solution

Minimum Spanning Trees: The Modern Corp. Problem Modern Corporation has decided to have a state-of-the-art fiber-optic network installed to provide high-speed communication (data, voice, and video) between its major centers. (摩登公司决定铺设最先进的光纤网络系统以便在其主要中心之间提供高速通信，包括数据、声音和视频等) 最小支撑树问题

Minimum Spanning Trees: The Modern Corp. Problem Any pair of centers do not need to have a cable directly connecting them in order to take advantage of the technology. All that is necessary is to have a series of cables that connect the centers. (为了充分利用光纤技术在中心之间高速通信的优势，不需要在每两个中心之间都用一条光缆把它们直接连接起来，那些需要光缆直接连接的中心有一系列的光缆连接它们)

Modern Corporation’s Major Centers

Minimum Spanning Trees: The Modern Corp. Problem Which cables should be installed to provide high-speed communications between every pair of centers. 应该铺设哪些光纤以便在每两个中心之间提供高速通信？

Assumptions of a Minimum-Spanning Tree Problem You are given the nodes of a network but not the links. Instead, you are given the potential links and the positive cost (or a similar measure) for each if it is inserted into the network. (给你网络中的节点，但没有给你边。或者，给你可供选择的边和如果把它插入到网络中后的每条边的正的成本[或者相似的度量])

Assumptions of a Minimum-Spanning Tree Problem You wish to design the network by inserting enough links to satisfy the requirement that there be a path between every pair of nodes. (在设计网络时你希望通过插入足够的边，以满足每两个节点之间都存在一条路的需要) The objective is to satisfy this requirement in a way that minimizes the total cost of doing so. (目标是寻找一种方法，使得在满足要求的同时总成本最小)

Algorithm for a Minimum-Spanning-Tree Problem Choice of the first link: Select the cheapest potential link. (选择第一条边：选择成本最低的备选边) Choice of the next link: Select the cheapest potential link between a node that already is touched by a link and a node that does not yet have such a link. (选择下一条边：在一个已经有一条边连接的节点和另一个还没有边连接的节点之间选择成本最低的备选边)

Algorithm for a Minimum-Spanning-Tree Problem Repeat step 2 over and over until every node is touched by a link (perhaps more than one). At that point, an optimal solution (a minimum spanning tree) has been obtained. (重复第二个步骤，直到所有的节点都有一条边[可能会有多于一条边]与其相连。此时就得到了最优解[最小支撑树]) Ties for the cheapest potential link at each step may be broken arbitrarily. (当有几条边同时是成本最低的边时，任意选择一条边不会影响最后的最优值)

Application of Algorithm to Modern Corp.: First Link

Application of Algorithm to Modern Corp.: Second Link

Application of Algorithm to Modern Corp.: Third Link

Application of Algorithm to Modern Corp.: Fourth Link

Application of Algorithm to Modern Corp.: Fifth Link

Application of Algorithm to Modern Corp.: Final Link

The Optimal Solution

最小支撑树问题 避圈法：开始选一条最小权的边，以后每一步中，总从未被选取的边中选一条权最小的边，并使之与已被选取的边不构成圈(如果有两条或两条以上的边都是权最小的边，则从中任选一条)

最小支撑树问题 算例

最小支撑树问题 破圈法：任取一个圈，从圈中去掉权最大的边(如果有两条或两条以上的边都是权最大的边，则任意去掉其中一条)。在余下的图中，重复这个步骤，一直到图中不含圈为止。去边的同时必须保证图的连通性

最小支撑树问题 算例

Applications of Minimum-Spanning-Tree Problems Design of telecommunication networks (computer networks, lease-line telephone networks, cable television networks, etc.) (电信网络 [计算机网络、电话专用线网络、有 线电视网络等等]的设计)

Applications of Minimum-Spanning-Tree Problems Design of a lightly-used transportation network to minimize the total cost of providing the links (rail lines, roads, etc.)(低负荷运输 网络的设计，使得网络中提供链接 的部分[如铁路、公路等]的总成本 最小)

Applications of Minimum-Spanning-Tree Problems Design of a network of high-voltage electrical power transmission lines. (高压输电线路网络的设计) Design of a network of pipelines to connect a number of locations. (连接多个场所的管道网络设计)

Applications of Minimum-Spanning-Tree Problems Design of a network of wiring on electrical equipment (e.g., a digital computer system) to minimize the total length of the wire.(电器设备线 路网络[如数字计算机系统]的设计， 使得线路总长度最短)

规划问题总结 线性规划 最小支撑树问题 资源分配问题 成本收益平衡问题 网络配送问题：运输问题，指派问题，最小费用流问题，最大流问题，最短路问题 混合问题 最小支撑树问题

规划问题总结 资源分配问题 将有限的资源分配到各种活动中去 函数约束：使用的资源数量≤可用的资源数量 需要确定三类数据：资源可用量、单位活动消耗的资源量和单位活动对绩效测度的贡献量 目标就是在满足资源限制的条件下使活动水平能够最大化所选择的绩效测度

规划问题总结 成本收益平衡问题 函数约束：完成的水平≥最低可接受水平 需要的三类数据：每种收益的最低可接受水平、每种活动对每一收益的贡献、每种活动的单位成本 通过选择各种活动水平的组合，以最小的成本来实现最低可接受的各种收益

函数约束是确定的需求：提供的数量=需要的数量 混合问题 函数约束多种多样：资源约束、收益约束、确定性需求约束 规划问题总结 配送网络问题 函数约束是确定的需求：提供的数量=需要的数量 混合问题 函数约束多种多样：资源约束、收益约束、确定性需求约束

规划问题总结 运输问题 出发地：供应量 目的地：需求量 配送成本等于单位成本乘于配送量 目标就是确定如何配送使配送总成本最小 运输问题的变形

规划问题总结 指派问题 任务和被指派者 目标就是确定怎样进行任务的指派，以最小化完成任务的总成本 指派问题的变形 是特殊的运输问题

规划问题总结 最小费用流问题 用带流的网络图表示 节点，供应点，需求点，转运点，弧，容量 至少有一个供应点一个需求点，其余是转运点 通过每一条弧的流的成本和流量成正比 目标是在满足给定需求的条件下，使得通过网络供应的总成本最小

最大流问题 最短路问题 源，收点，转运点 目标是使得从源到收点的总流量最大 源，目标地，边，边的长度 目标是寻找从源到目标地的最短路 规划问题总结 最大流问题 源，收点，转运点 目标是使得从源到收点的总流量最大 最短路问题 源，目标地，边，边的长度 目标是寻找从源到目标地的最短路

规划问题总结 最小支撑树问题 边和成本 选择或插入足够的边，使得任意两点之间都存在一条路 目标是寻找一种方法，使得在满足要求的同时总成本最小

The end of chapter 7