运筹学网络最优化问题

实用运筹学

－运用Excel建模和求解第5章网络最优化问题本章内容要点网络最优化问题的基本概念网络最优化问题的四种主要类型：最小费用流、最大流、最短路、最小支撑树各种网络最优化问题的建模与应用本章节内容5.1网络最优化问题基本概念5.2最小费用流问题5.3最大流问题5.4最短路问题5.5最小支撑树问题5.6货郎担问题和中国邮路问题本章主要内容框架图5.1网络最优化问题基本概念网络在各种实际背景问题中以各种各样的形式存在。交通、电子和通讯网络遍及我们日常生活的各个方面，网络规划也广泛用于解决不同领域中的各种问题，如生产、分配、项目计划、厂址选择、资源管理和财务策划等等。网络规划为描述系统各组成部分之间的关系提供了非常有效的直观和概念上的帮助，广泛应用于科学、社会和经济活动的各个领域中。近些年来，运筹学（管理科学）中一个振奋人心的发展是它的网络最优化问题的方法论和应用方面都取得了不同寻常的飞速发展。5.1网络最优化问题基本概念许多研究的对象往往可以用一个图表示，研究的目的归结为图的极值问题。运筹学中研究的图具有下列特征：

(1)用点表示研究对象，用连线（不带箭头的边或带箭头的弧）表示对象之间某种关系；

(2)强调点与点之间的关联关系，不讲究图的比例大小与形状；

(3)每条边上都赋有一个权，其图称为赋权图。实际中权可以代表两点之间的距离、费用、利润、时间、容量等不同的含义；

(4)建立一个网络模型，求最大值或最小值。5.1网络最优化问题基本概念v1v3v5v2v4v68736548521对于该网络图，可以提出许多极值问题5.1网络最优化问题基本概念（1）将某个点vi的物资或信息送到另一个点vj，使得运送成本最小。这属于最小费用流问题。（2）将某个点vi的物资或信息送到另一个点vj，使得流量最大。这属于最大流问题。（3）从某个点vi出发到达另一个点vj，怎样安排路线使得总距离最短或总费用最小。这属于最短路问题。5.1网络最优化问题基本概念（4）点vi表示自来水厂及用户，vi与vj之间的边表示两点间可以铺设管道，权为vi与vj间铺设管道的距离或费用，极值问题是如何铺设管道，将自来水送到其他5个用户并且使总的费用最小。这属于最小支撑树问题。

(5)售货员从某个点vi出发走过其他所有点后回到原点vi，如何安排路线使总路程最短。这属于货郎担问题或旅行售货员问题。（6）邮递员从邮局vi出发要经过每一条边将邮件送到用户手中，最后回到邮局vi，如何安排路线使总路程最短。这属于中国邮递员问题。5.1网络最优化问题基本概念网络最优化问题类型主要包括：（1）最小费用流问题；（2）最大流问题；（3）最短路问题；（4）最小支撑树问题；（5）货郎担问题和中国邮路问题，等等5.2最小费用流问题最小费用流问题的模型在网络最优化中扮演着重要的角色，因为它的适用性很广，并且求解方法容易。通常最小费用流问题用于最优化货物从供应点到需求点的网络。目标是在通过网络配送货物时，以最小的成本满足需求，一种典型的应用就是使得配送网络的运营最优。最小费用流问题的特殊类型包括运输问题和指派问题，以及在下面将要提到的两种重要类型：最大流问题和最短路问题。5.2最小费用流问题例5.1某公司有两个工厂生产产品，这些产品需要运送到两个仓库中。其配送网络图如图5－2所示。目标是确定一个运输方案（即每条路线运送多少单位的产品），使通过配送网络的运输成本最小。（50，400）（50，200）（50，400）（50，300）F1F2DCW2W180706090（无限制，700）（无限制，900）5.2最小费用流问题最小费用流问题的三个基本概念：1、最小费用流问题的构成（网络表示）（1）节点：包括供应点、需求点和转运点；（2）弧：可行的运输线路（节点i->节点j），经常有最大流量（容量）的限制。5.2最小费用流问题2、最小费用流问题的假设（1）至少一个供应点；（2）至少一个需求点；（3）剩下都是转运点；（4）通过弧的流只允许沿着箭头方向流动，通过弧的最大流量取决于该弧的容量；（5）网络中有足够的弧提供足够容量，使得所有在供应点中产生的流都能够到达需求点；（有解）（6）在流的单位成本已知前提下，通过每一条弧的流的成本和流量成正比；（目标是线性的）（7）最小费用流问题的目标在满足给定需求条件下，使得通过网络供应的总成本最小（或总利润最大）。5.2最小费用流问题3、最小费用流问题的解的特征（1）具有可行解的特征：在以上的假设下，当且仅当供应点所提供的流量总和等于需求点所需要的流量总和时（即平衡条件），最小费用流问题有可行解；（2）具有整数解的特征：只要其所有的供应、需求和弧的容量都是整数值，那么任何最小费用流问题的可行解就一定有所有流量都是整数的最优解（与运输问题和指派问题的解一样）。因此，没有必要加上所有决策变量都是整数的约束条件。5.2最小费用流问题最小费用流问题的数学模型为：（1）决策变量：设fij为通过弧（节点i->节点j）的流量。（2）目标是通过网络供应的总成本最小。（3）约束条件

①所有供应点：净流量（总流出减总流入）为正； ②所有转运点：净流量为零； ③所有需求点：净流量为负； ④所有弧的流量fij受到弧的容量限制； ⑤所有弧的流量fij非负。5.2最小费用流问题例5.1最小费用流问题的数学模型为：（1）决策变量：设fij为通过弧(节点i->节点j)的流量。（2）目标函数本问题的目标是总运输成本最小。5.2最小费用流问题（3）约束条件(节点净流量、弧的容量限制、非负）①供应点F1:

供应点F2: ②转运点DC: ③需求点W1:

需求点W2: ④弧的容量限制：⑤非负：5.2最小费用流问题

例5.1的电子表格模型：列出了网络中的弧和各弧所对应的容量、单位成本。决策变量为通过弧的流量。目标是计算流量的总成本。每个节点的净流量为约束条件。供应点的净流量为正，需求点的净流量为负，而转运点的净流量为0。 这里用了一个窍门：用两个SUMIF函数的差来计算每个节点的净流量，这样快捷且不容易犯错。5.2最小费用流问题

大规模的最小费用流问题的求解一般采用“网络单纯法（NetworkSimplexMethod）”。现在，许多公司都使用网络单纯法来解决他们的最小费用流问题。有些问题是非常庞大的，有着数万个节点和弧。有时，弧的数量甚至可能会多得多，达到几百万条。但Excel的规划求解中没有网络单纯法，但其他的线性规划的商业软件包通常都有这种方法。5.2最小费用流问题最小费用流问题有五种重要的特殊类型：（1）运输问题：有出发地(供应点-供应量)和目的地(需求点-需求量)，没有转运点和弧的容量限制，目标是总运输成本最小（或总利润最大）。（2）指派类型：出发地(供应点-供应量为1)是人，目的地(需求点-需求量为1)是任务，没有转运点和弧的容量限制，目标是总指派成本最小（或总利润最大）。（3）转运问题：有出发地(供应点-供应量)和目的地(需求点-需求量)，有转运点，但没有弧的容量限制(或有容量限制)，目标是总流量费用最小（或总利润最大）。5.2最小费用流问题最小费用流问题有五种重要的特殊类型(续)：（4）最大流问题：有供应点、需求点、转运点、弧的容量限制，但没有供应量和需求量的限制，目标是通过网络到目的地的总流量最大。（5）最短路问题：有供应点(供应量为1)、需求点(需求量为1)、转运点、没有弧的容量限制，目标是通过网络到目的地的总距离最短。5.3最大流问题在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题等。而网络系统最大流问题是图与网络流理论中十分重要的最优化问题，它对于解决生产中的实际问题起着十分重要的作用。最大流问题也与网络中的流有关，但目标不是使得流的总成本最小，而是寻找一个流的方案，使得通过网络的流量最大。除了目标（流最大化和成本最小化）不一样外，最大流问题的特征和最小费用流问题的特征非常相似。5.3最大流问题例5.2

某公司要从起始点vs（发点）运送货物到目的地vt（收点），其网络图如图5－4（下一张幻灯片）所示。图中每条弧（节点i->节点j）旁边的权cij表示这段运输线路的最大通过能力（容量）。要求制定一个运输方案，使得从vs到vt的运货量达到最大，这个问题就是寻求网络系统的最大流问题。5.3最大流问题708060403050407050vsv1v2v3v5v4vt5.3最大流问题例5.2最大流问题的线性规划数学模型：（1）决策变量设fij为通过弧（节点i->节点j）的流量。（2）目标函数本问题的目标是从vs流出的总流量最大。（3）约束条件(转运点的净流量为0、弧的容量限制、非负）5.3最大流问题例5.2最大流问题电子表格模型5.3最大流问题最大流问题的变形主要在于：有多个发点（供应点）和多个收点（需求点）。例5.3

在例5.2的基础上，增加了一个发点ps、一个收点pt、两个转运点p1和p2、以及与之相连的7条弧，如图5－6（下一张幻灯片）所示。目标是从vs和ps两个发点运出的总流量最大。这是一个有2个发点（供应点）和2个收点（需求点）的最大流问题。5.3最大流问题70804010203050406030404070502060v1v2v3v5v4vtp1psptp2vs5.3最大流问题例5.3的数学模型5.3最大流问题例5.3的电子表格模型5.3最大流问题最大流问题的一些实际应用：（1）通过配送网络的流量最大，如例5.2和例5.3；（2）通过管道运输系统的油的流量最大；（3）通过输水系统的水的流量最大；（4）通过交通网络的车辆的流量最大；等等。5.3最大流问题例5.4计划编制问题。某市政工程公司在未来5～8月份内需完成4项工程：修建一条地下通道、修建一座人行天桥、新建一条道路及道路维修。工期和所需劳动力见表5－1。该公司共有劳动力120人，任一工程在一个月内的劳动力投入不能超过80人，问公司应如何分配劳动力完成所有工程，是否能按期完成？工程工期需要劳动力（人）A.地下通道5～7月100B.人行天桥6～7月80C.新建道路5～8月200D.道路维修8月805.3最大流问题本问题除了可以用第3章介绍的线性规划方法来求解（可设xij为工程i在j月投入的劳动力）外，还可以用最大流的方法来求解。将工程计划用网络图5－8（下一张幻灯片）表示。图中的节点5、6、7、8分别表示5～8月份，Ai、Bi、Ci、Di表示工程在第i个月内完成的部分。用弧表示某月完成某项工程的状态，弧的流量为所投入的劳动力，受到劳动力限制（弧旁边的数字表示弧的容量，从S开始的弧，其容量为该公司共有劳动力120人；从节点5、6、7、8开始的弧以及到节点A、B、C、D的弧，其容量为任一工程在一个月内的劳动力投入不能超过80人；到收点T的弧，其容量为每个工程所需劳动力）。合理安排每个月各工程的劳动力，在不超过现有人力的条件下，尽可能保证工程按期完成，就是求图5－8从发点到收点的最大流问题。5.3最大流问题S675B6A58C5A6C6A7D8C8B7C7BCADT12080801008020080注意：增加一个起点和一个终点，其容量是供应量和需求量5.3最大流问题例5.4市政工程公司劳动力分配电子表格模型P162求解结果（每个月的劳动力分配）如表5－2所示。5月份有剩余劳动力20人，4项工程恰好按期完成。月份投入劳动力项目A项目B项目C项目D51002080612040807120804081204080合计46010080200805.3最大流问题最小费用最大流问题在实际的网络应用当中，当涉及到流的问题时，有时考虑的不只是流量，还要考虑费用多少的问题。比如一个铁路运输系统的网络流，不但要考虑网络系统的货运量最大，又要考虑总费用最小。最小费用最大流就是要解决这一类的问题。所谓最小费用最大流问题就是：给定一个带收点和发点的网络，对每一条弧（节点i->节点j）,除了给出容量cij外，还给出了这条弧的单位流量的费用bij

，要求一个最大流F，并使得总运费用最小。最小费用最大流问题也是一个线性规划问题。5.3最大流问题例5.5

某公司有一个管道网络（如图5－10所示，下一张幻灯片），使用这个网络可以把石油从采地v1运送到销地v7。由于输油管道长短不一，每段管道除了有不同的流量cij限制外，还有不同的单位流量的费用bij。每段管道旁边括号内的数值意义为（cij，bij）。如果使用这个网络系统，从采地v1向销地v7运送石油，怎样运送才能运送最多的石油并使得总的运送费用最小？5.3最大流问题(3,2)(6,3)(2,8)(1,3)(4,4)(2,3)(5,7)(2,4)（2,5）(3,4)(6,6)v1v7v6v5v4v3v25.3最大流问题解：用线性规划来求解此题，分为两步走。第一步：先求出此网络系统的最大流量F。数学模型P164电子表格模型P165求得的最大流量F=10第二步：在最大流量F的所有解中，找出一个最小费用的解。数学模型P166电子表格模型P166求得的最小费用为1455.4最短路问题最短路问题是网络理论中应用最广泛的问题之一。许多优化问题可以使用这个模型，如设备更新、管道铺设、线路安排、厂区布局等最短路问题的最普遍的应用是在两个点之间寻找最短路，是最小费用流问题的一种特殊类型：源的供应量为1、目的地（需求点）的需求量为1、转运点的净流量为0、没有弧的容量限制，目标：通过网络到目的地的总距离最短。5.4最短路问题例5.6

某人每天从住处v1开车到工作地v7上班，图中各弧旁的数字表示道路的长度（公里），试问该人应选择哪条路线，从家出发到工作地，路上行驶的总距离最短。v1v2v3v4v5v6v729683.51452.535.4最短路问题解：这是一个最短路问题。其数学模型为：（1）决策变量：设xij为弧(节点i->节点j)是否走（1表示走，0表示不走）。（2）目标函数本问题的目标是总距离最短。（3）约束条件(节点净流量、非负）P1695.4最短路问题例5.6的最短路问题的电子表格模型5.4最短路问题最短路问题的应用很广，如设备更新、管道铺设、线路安排、厂区布局等。下面举两个例子：（1）设备更新问题；（2）新产品开发时间问题。5.4最短路问题例5.7设备更新问题。某工厂的某台机器可连续工作4年，决策者每年年初都要决定机器是否需要更新。若购置新机器，就要支付购置费用；若继续使用，则需要支付维修与运行费用，而且随着机器使用的年限费用逐年增多。已知计划期（4年）中每年的购置价格及维修与运行费用。试制定今后4年的机器更新计划，使总的支付费用最少。年限1234购置费（万元）2.52.62.83.1维修与运行费（万元）11.5245.4最短路问题解：把该问题看作最短路问题。设节点1和节点5表示计划期的始点和终点（节点5可以理解为第4年末）。图5－15中各弧（i，j）表示第i年初购进的机器使用到j年初（即j-1年底），弧旁的数字由表5－3中的数据计算得到。弧长＝购置价格＋使用多年的维修与运行总费用例如，考虑从节点1到节点3的弧，这条弧对应的是在第1年初购进的机器，使用到3年初（即使用了2年），所以从①到③的弧长＝2.5＋1+1.5=5（万元）5.4最短路问题例5.7设备更新问题的网络模型因此，把求最优的设备更新问题转化为求节点1到节点5的最短路问题135243.53.63.84.111575.35.17.15.4最短路问题例5.7的电子表格模型5.4最短路问题如果已知不同役龄机器年末的处理价格如表5－4所示，那么在这计划期（4年）机器的最优更新计划又会怎样？表5－4不同役龄机器年末的处理价格使用年数1234处理价（万元）21.61.31.15.4最短路问题这还是一个最短路问题，网络模型不变，还如图5－15所示，只是弧长不同。

弧长＝购置价格＋使用多年的维修与运行总费用－使用多年后处理价5.4最短路问题有处理价格的设备更新问题的电子表格模型5.4最短路问题例5.8新产品投放市场决策。已知新产品计划20个月后投放市场，但还有四个没有时间重叠的阶段没有完成，而每个阶段的实施水平可以从正常水平提高为优先水平或应急水平，使之能够加速完成；而且最后三个阶段中都可以考虑提高实施水平。第一阶段可以以正常速度，也可以加速完成。表5－5（P174）列出了在这些水平下所需的时间。管理层给这四个阶段的预算拨款为3000万元，每个阶段的费用如表5－6（P174）所示。管理层希望确定这四个阶段各自应该采取哪一种水平，从而在3000万元预算限制内，使得这种产品可以尽早地推向市场。5.4最短路问题解：这个问题可以用最短路问题来求解。图5－18（P175）是该问题的网络图，每个节点代表了那个时间点的情况。一个虚拟目的地(节点T)(下一张幻灯片)电子表格模型P176－177由于四个阶段，每个阶段都要完成且完成一次，所以可以用第6章的0-1整数规划来求解。5.4最短路问题对于有多个实际目的地或有多个实际出发地的最短路问题的处理方法：当网络中有多个实际目的地时，在每个实际目的地和虚拟目的地之间插入一条长度为0的弧，从而使得网络中仍然只有一个目的地。同样地，如果网络中有多个实际出发地，可以增加一个虚拟出发地，虚拟出发地到实际出发地的弧长也是0。5.5最小支撑树问题许多网络问题可以归结为最小支撑树问题。例如，设计长度最小的公路网把若干城市（乡村）联系起来；设计用料最省的电话线网（光纤）把有关单位联系起来，等等。这种问题的目标是设计网络。虽然节点已经给出，但必须决定在网络中要加入哪些边。特别地，向网络中插入的每一条可能的边都有成本。为了使得每两个节点之间形成路，需要提供足够的边。目标就是以某种方法完成网络设计，使得边的总成本最小。这种问题称为最小支撑树问题。5.5最小支撑树问题例5.9某公司铺设光导纤维网络问题。某公司的管理层已经决定铺设最先进的光导纤维网络，为它的主要中心之间提供高速通信（数据、声音和图像）。图5－20（下一张幻灯片）中的节点显示了该公司主要中心（包括公司的总部、巨型计算机、研究区、生产和配送中心等）的分布图。虚线是铺设纤维光缆可能的位置。每条虚线旁边的数字表示了如果选择在这个位置铺设光缆需要花费的成本。

为了充分利用光纤技术在中心之间高速通信的优势，不需要在每两个中心之间都用一条光缆把它们直接连接起来。现在的问题就是要确定需要铺设哪些光缆使得提供给每两个中心之间的高速通信的总成本最低。实际上，这就是一个最小支撑树问题。5.5最小支撑树问题425414371572ABDCEFG5.5最小支撑树问题通过“贪婪算法”来求解。求解最小支撑树问题的贪婪算法有很多。比如，Kruskal算法，其步骤如下：（1）选择第一条边：选择成本最低的备选边；（2）选择下一条边：从剩下的边中取一条边满足：（a）最小边；（b）不构成圈；（3）重复第（2）步骤，直到选取的边数为节点数-1。此时就得到了最优解（最小支撑树）。处理成本相同的边：当有几条边同时是成本最低的边时，任意选择一条边不会影响最后的最优解。利用Kruskal算法求解例5.9的最小支撑树的步骤P181－1825.6货郎担问题和中国邮路问题一个推销员从n个城市中的某个城市出发，到其他n－1个城市推销货物，每个城市都必须访问并且只访问一次，最后回到出发地，如何安排他的行走路线使总距离最短，这就是货郎担问题或旅行售货员问题。5.6货郎担问题和中国邮路问题例5.10

某电动汽车公司和学校合作，拟定在校园内开通无污染无噪音的“绿色交通”路线。图5－23是教学楼和学生宿舍楼的分布图，边上的数字为汽车通过两点间的正常时间（分钟）。电动汽车公司应如何设计一条行驶路线，使汽车通过每一处教学楼和宿舍楼一次后总时间最少。ABCDEF42.231.51.61.82.62.82.84.25.6货郎担问题和中国邮路问题对于货郎担问题，也是将边看成长度相等方向相反的两条弧，其线性规划模型P184。用Excel求解货郎担问题的想法来源于用Excel求解最短路问题，但要修改。由于在最短路问题中，有些节点可以不经过，但在货郎担问题中要求每个节点都要恰好经过一次，所以约束条件改为将每个节点的总流入和总流出分开。也就是说，每个节点有两个约束（总流入=1和总流出=1），而非最短路问题的一个净流量约束。改进后的Excel方法，有时可以得到只有一个大回路的最优解（此时求解结束），但经常会得到有几个小回路的解，此时就应该再增加去掉小回路的约束。5.6货郎担问题和中国邮路问题解：对于例子5.10，第一步：将每个节点的总流入和总流出分开，电子表格模型如图5－24所示。Excel求解结果为：A<->D、B<->C、E<->F，也就是说，分成3个小的回路。此时的总时间为13.2分钟。5.6货郎担问题和中国邮路问题第二步：去掉第一步的3个小回路。在图5－24的基础上，增加这3对节点（教学楼和学生宿舍楼）不能有回路的约束，电子表格模型如图5－25所示。Excel求解结果为：A->C->B->E->F->D->A，也就是说，求得一个大回路，此时求解结束。如果还存在有3个节点或3个节点以上的小回路，还需增加新的约束，去掉小回路。5.6货郎担问题和中国邮路问题一个邮递员从邮局出发，将邮件投递到