第二章运筹学各分支简介 运筹学作为一门学科,在理论和方法上取得了巨大的进展,现在我们就来介绍一下各分支研究 题的对象和基本的分析方法,使读者对它们有一个概貌的了解 作为一门学科来说,运筹学的内容可以大致表示如下: 线性 优选,统筹 数学规划 非线性,几何 组合最优化 确定性模型 图论,网络流 整数,参数,多目标 动态规划 运筹学 投入产出 决策 对策 随机性模型」排队,更新,维修,可靠性 随机控制 模拟 以下对其中的主要分支,分别介绍如下。 §1数学规划 数学规划所要解决的问题就是要在某种约束条件之下,决定某些可控制的因素应该取什么样的 值,使得所选定的目标达到最小(或最大),用数学的语言来表示,就是要解决下述极值问题 minf(x),x=(x1…,x),x∈S,其中S表示满足约束条件的可行解的集合。 极值问题虽然早已存在,但现在考虑的数学规划问题与古典的极值问题却有很大的差别:(i) 古典方法只能处理当f(x)和可行域S很简单的情况,而现在实际中所出现的问题,f(x)和S 般都很复杂;(ⅱ)古典方法只能处理n比较小的情形,例如n=3,4,而现在n一般都相当大,个 别问题的n甚至上百万;(ⅲi)古典方法往往满足于一个表达式,而现在则需要把所需数值具体求出 基于上述原因,要想解决数学规划问题,必须另辟新路,实际上,自从 Dantzig在1947年发表关于 解线性规划(即f(x)为x,…,xn的一次式,S由x1,…,xn的一些线性不等式组成)的单纯形 法以来,数学规划已得到非常迅速的发展,形成许多分支,成为近代应用数学的一个重要组成部分 由于它的发展,使得有关学科,如凸分析、数理经济学、应用泛函等也得到相应的发展,国际数学 规划讨论会于1970年成立,有关杂志不下10种,国际数学规划讨论会至今已召开12届,我国第十 十二届均有人参加,会议设立了 Fulkerson奖(1979年始)和 Dantzig奖(1982年始),授予那 些在数学规划方面具有开创性成绩的工作者 本书将详细介绍数学规划的若干分支,故这里不多叙述,有关参考书较多,如: 管梅谷,郑汉鼎,线性规划,1983
5 第二章 运筹学各分支简介 运筹学作为一门学科，在理论和方法上取得了巨大的进展，现在我们就来介绍一下各分支研究 问题的对象和基本的分析方法，使读者对它们有一个概貌的了解。 作为一门学科来说，运筹学的内容可以大致表示如下： 运 筹 学 确 定 性 模 型 随 机 性 模 型 优 选 ， 统 筹 数 学 规 划 组 合 最 优 化 图 论 ， 网 络 流 动 态 规 划 投 入 产 出 决 策 对 策 排 队 ， 更 新 ， 维 修 ， 可 靠 性 存 储 随 机 控 制 模 拟 线 性 非 线 性 ， 几 何 整 数 ， 参 数 ， 多 目 标 以下对其中的主要分支，分别介绍如下。 §1 数学规划 数学规划所要解决的问题就是要在某种约束条件之下，决定某些可控制的因素应该取什么样的 值，使得所选定的目标达到最小（或最大），用数学的语言来表示，就是要解决下述极值问题： min ( ), ( , , ) , 1 T n f x x x x x S = ，其中 S 表示满足约束条件的可行解的集合。 极值问题虽然早已存在，但现在考虑的数学规划问题与古典的极值问题却有很大的差别：（i） 古典方法只能处理当 f（x）和可行域 S 很简单的情况，而现在实际中所出现的问题，f（x）和 S 一 般都很复杂；（ii）古典方法只能处理 n 比较小的情形，例如 n＝3，4，而现在 n 一般都相当大，个 别问题的 n 甚至上百万；（iii）古典方法往往满足于一个表达式，而现在则需要把所需数值具体求出。 基于上述原因，要想解决数学规划问题，必须另辟新路，，实际上，自从 Dantzig 在 1947 年发表关于 解线性规划（即 f（x）为 x1，···，xn 的一次式，S 由 x1，···，xn 的一些线性不等式组成）的单纯形 法以来，数学规划已得到非常迅速的发展，形成许多分支，成为近代应用数学的一个重要组成部分， 由于它的发展，使得有关学科，如凸分析、数理经济学、应用泛函等也得到相应的发展，国际数学 规划讨论会于 1970 年成立，有关杂志不下 10 种，国际数学规划讨论会至今已召开 12 届，我国第十 一、十二届均有人参加，会议设立了 Fulkerson 奖（1979 年始）和 Dantzig 奖（1982 年始），授予那 些在数学规划方面具有开创性成绩的工作者。 本书将详细介绍数学规划的若干分支，故这里不多叙述，有关参考书较多，如： 管梅谷，郑汉鼎，线性规划，1983
俞玉森主编,数学规划的原理和方法,1985 唐焕文,实用数学规划导论,1986 魏权龄等,数学规划与优化设计,1984 §2图与网络方法 所谓图乃是指由一组给定的点(称为顶点)及一组连接这些点的线(称为边或弧)所组成的总 体(如交通图),而图论则是研究图的理论。图论的产生可以上溯到十八世纪,但它得到重视而且逐 渐成为一门学科,则是本世纪三十年代之后的事。特别是五十年代以来,由于许多具有离散性的问 题皆可以通过图来表示,使得图论的研究越来越为人们所重视,如 兰姆赛问题( Ramsey):任意六个人在一起,若不是有三个人彼此相互认识,必然有三个人互 不认识 将此问题化为图来分析:视6个人为6个顶点,认识,用实线相连接;不认识,用虚线连接。 往证至少存在一个实三角形或虚三角形。任取一点V1,它与其他五点的连线中至少有三条同为实线 或同为虚线,不妨假设为实线,而另一端点分别为V2,V3,V4 这后三个顶点形成的三角形若是虚线的则问题已经解决,不然则至少有一条边为实线,从而又与 已知实线构成一实三角形,故问题得证。 图1 可见用图来处理问题有时很有效,并且形象直观(如哥尼斯堡七桥问题)。许多有经济意义的问 题都归结为图与网络(边上有各种数据的连通图叫做网络,数据又叫权),如 (Ⅰ)、最短路问题 在给定网络中求指定两点的最短路是图论中的一个基本问题,此问题已有有效算法 用d表示连接顶点i和j的线段长(若无则视d=+∞),现在要从点1出发,走到n,问怎样 走路程最短? 6
6 俞玉森主编，数学规划的原理和方法，1985 唐焕文，实用数学规划导论，1986 魏权龄等，数学规划与优化设计，1984 §2 图与网络方法 所谓图乃是指由一组给定的点（称为顶点）及一组连接这些点的线（称为边或弧）所组成的总 体（如交通图），而图论则是研究图的理论。图论的产生可以上溯到十八世纪，但它得到重视而且逐 渐成为一门学科，则是本世纪三十年代之后的事。特别是五十年代以来，由于许多具有离散性的问 题皆可以通过图来表示，使得图论的研究越来越为人们所重视，如 兰姆赛问题（Ramsey）：任意六个人在一起，若不是有三个人彼此相互认识，必然有三个人互 不认识。 将此问题化为图来分析：视 6 个人为 6 个顶点，认识，用实线相连接；不认识，用虚线连接。 往证至少存在一个实三角形或虚三角形。任取一点 V1，它与其他五点的连线中至少有三条同为实线 或同为虚线，不妨假设为实线，而另一端点分别为 V2 ，V3 ，V4 ，这后三个顶点形成的三角形若是虚线的则问题已经解决，不然则至少有一条边为实线，从而又与 已知实线构成一实三角形，故问题得证。 1 2 3 5 4 6 图 1 可见用图来处理问题有时很有效，并且形象直观（如哥尼斯堡七桥问题）。许多有经济意义的问 题都归结为图与网络（边上有各种数据的连通图叫做网络，数据又叫权），如 （I）、最短路问题。 在给定网络中求指定两点的最短路是图论中的一个基本问题，此问题已有有效算法。 用 ij d 表示连接顶点 i 和 j 的线段长（若无则视 ij d ＝＋∞），现在要从点 1 出发，走到 n，问怎样 走路程最短？
d 图2 考虑从点1到点j的路,按中途所经过的线段数目分类,用d表示从点1到点j的且限制中途 经过的线段数目不超过m的这类路中的一条最短路之长,研究dm+,即所经线段数目为(m+1) 时的最短路长,易见它或者等于d,或者等于min{4+d4},于是有 dn += mind, mind +d,)i 而1到n的最短路即为dn-1。 分析计算量:关系式(1)中,m取1,2,…;(n-2),对每一个固定的m,j取2,3,…,n, 对于固定的m和j,一般说来,要经过(n-1)次加法运算和比较运算才能得到dm,因此计算量 是O(n3)。这实际上就是动态规划的顺推算法,按照动态规划的最优化原理:“作为整个过程的最优 策略,具有这样的性质:即无论过去的状态和决策如何,对前面的决策所形成的状态而言,余下的 诸决策必须构成最优策略。而对于无向图说来,起点到终点的最短路自然也是终点到起点的最短路”。 当所有线段的长度都是正数,还有更好的算法: Dijkstra算法(标号算法)。它的计算量为O(n2) 具体做法是:先对起点标号,每步考察已标号顶点的相邻顶点,把距起点最近的顶点标号,直到终 点被标号,按标号反向追踪即得到最短路。 例:求下图中A到B的最短路。 标号过程如下:
7 1 2 4 3 j n d12 d13 图 2 考虑从点 1 到点 j 的路，按中途所经过的线段数目分类，用 m j d 表示从点 1 到点 j 的且限制中途 经过的线段数目不超过 m 的这类路中的一条最短路之长，研究 m 1 d j + ，即所经线段数目为（m＋1） 时的最短路长，易见它或者等于 m j d ，或者等于 min{ } m k kj k j d d + ，于是有 1 min{ ,min{ }} m m m j j k kj k j d d d d + = + （1） 而 1 到 n 的最短路即为 n 1 dn − 。 分析计算量：关系式（1）中，m 取 1，2，···，（n－2），对每一个固定的 m，j 取 2，3，···，n， 对于固定的 m 和 j，一般说来，要经过（n－1）次加法运算和比较运算才能得到 m 1 d j + ，因此计算量 是 3 O n( ) 。这实际上就是动态规划的顺推算法，按照动态规划的最优化原理：“作为整个过程的最优 策略，具有这样的性质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的 诸决策必须构成最优策略。而对于无向图说来，起点到终点的最短路自然也是终点到起点的最短路”。 当所有线段的长度都是正数，还有更好的算法：Dijkstra 算法（标号算法）。它的计算量为 2 O n( ) 。 具体做法是：先对起点标号，每步考察已标号顶点的相邻顶点，把距起点最近的顶点标号，直到终 点被标号，按标号反向追踪即得到最短路。 例：求下图中 A 到 B 的最短路。 1 6 5 3 2 A 4 1 3 1 1 2 2 2 1 5 3 2 B 标号过程如下：
故最短路为A→1→2→4→6→B,最短路长为6 最短路问题可以直接应用于解决生产实际的许多问题,诸如各种管道铺设、线路安排、厂区布 局、设备更新、选址等 (I1)、最短网络。 亦称最小树。一个实际背景是:在若干城市间架设电话线,如何架设使总长最短? 先讲讲什么是树?对于图中的任二顶点V和V,如果从一个顶点出发沿着若干边或弧(有方 向的边叫做弧),可以达到另一顶点,则称所顺次经过的边和顶点为连接V1和V的链。如果所连接 的顶点重合,即V:=V,则称这样的闭链为圈。一个圈中如果任意两顶点之间至少有一条链,则称 为连通图,而连通且无圈的图叫做树 对于含圈的连通圈,去掉每个圈的一条边,便可生成一个树,去掉的边不同生成的树也不一样, 其中边权和最小的,叫做最小生成树。 求最短网络,首先容易想到的是求最小生成树,目前的方法有所谓破圈法(即任取一个圈,每 次去掉其中最长的一条边,直到无圈为止),顶点扩充法(即任取一顶点,考察以此顶点为一端点的 所有的边,取其中最短边的另一顶点为扩充顶点,依次类推,但要注意新扩充的边与已选好的边不 能构成圈,直到所有顶点均被扩充为止)等,计算量是O(n)。 继之想到在原基础上增加一些新点和连线,扩大成一个新的网络,要求在此新网络上找出一个 子网络,它是连通的,包含原图中的点,并且边权和最小,这种网络称为斯坦纳最小树(树中新增 加的点叫斯坦纳点,简称斯点),它的边权和显然小于最小树的,现已证明 任一斯点均为夹角为120的三线段交点。 、n顶点的图形最多含(n-2)个斯点 三个顶点的斯坦纳最小树很容易找出 以AC为边作正△ACD,连BD交△ACD的外接圆于S,则S即为斯点(见图3)
8 1 6 5 3 2 A 4 1 3 1 1 2 2 2 1 5 3 2 B 0 6 5 6 3 3 2 1 故最短路为 A B → → → → → 1 2 4 6 ，最短路长为 6。 最短路问题可以直接应用于解决生产实际的许多问题，诸如各种管道铺设、线路安排、厂区布 局、设备更新、选址等。 （II）、最短网络。 亦称最小树。一个实际背景是：在若干城市间架设电话线，如何架设使总长最短？ 先讲讲什么是树？对于图中的任二顶点 Vi 和 Vj，如果从一个顶点出发沿着若干边或弧（有方 向的边叫做弧），可以达到另一顶点，则称所顺次经过的边和顶点为连接 Vi 和 Vj 的链。如果所连接 的顶点重合，即 Vi ＝Vj，则称这样的闭链为圈。一个圈中如果任意两顶点之间至少有一条链，则称 为连通图，而连通且无圈的图叫做树。 对于含圈的连通圈，去掉每个圈的一条边，便可生成一个树，去掉的边不同生成的树也不一样， 其中边权和最小的，叫做最小生成树。 求最短网络，首先容易想到的是求最小生成树，目前的方法有所谓破圈法（即任取一个圈，每 次去掉其中最长的一条边，直到无圈为止），顶点扩充法（即任取一顶点，考察以此顶点为一端点的 所有的边，取其中最短边的另一顶点为扩充顶点，依次类推，但要注意新扩充的边与已选好的边不 能构成圈，直到所有顶点均被扩充为止）等，计算量是 2 O n( ) 。 继之想到在原基础上增加一些新点和连线，扩大成一个新的网络，要求在此新网络上找出一个 子网络，它是连通的，包含原图中的点，并且边权和最小，这种网络称为斯坦纳最小树（树中新增 加的点叫斯坦纳点，简称斯点），它的边权和显然小于最小树的，现已证明： 一、任一斯点均为夹角为 120o 的三线段交点。 二、n 顶点的图形最多含（n－2）个斯点。 三个顶点的斯坦纳最小树很容易找出： 以 AC 为边作正△ACD，连 BD 交△ACD 的外接圆于 S，则 S 即为斯点（见图 3） 1 2 B C A D S
图3 易证,SA+SB+SC5时,斯坦纳最小树即是最小生成树(详见,翁家丰,应用数学学报,2(1985)),其二是对一般 的集合构造次优树,即不一定最短但接近最短,通常以最小生成树为次优树,人们对点集A,定义 r(4)斯坦纳最小树长 最小生成树长 称厂=mfH为最小斯坦纳比例,猜测P=√,由正三角形的例子知p≤当2=086,曾 证得3<n<5时,p= 黄光明③证明了ρ≥0.8(1983年),钟金芳蓉和 Graham又宣布了 ρ=0.8241(计算机结果),已经很接近了。最近(2000年)我国运筹学家越民义证明了猜测为 真。替代结果,最坏情形増加13.4%的网络长,对随机情形只增加3% (II)作业时间的优化 作业时间的优化问题,象大规模工程、房屋建筑、产品开发设计、维修以及工厂的开工投产活 动等一次完成的规划项目,如果对完工时间要求很严(如附有罚款条件),那么采用网络分析,以缩 短工时,则具有特别重要的意义 运用网络来描述规划,制作进度表,可以有以下几方面的好处 1.有助于管理者系统的、全面的考虑规划,弄清程序,便于估计完成时间和找出可能的改进 方案,从而加快规划的实现。 2.能提供工程计划的简明概况,其形式便于有关部门进行评论和参考,从而便于汇集各方面 的意见,找出存在的问题和延误工程的原因。 3.对网络进行分析可找出关键路线,这就是网络中所需时间最长的一组活动。网络的解可以
9 图 3 易证，SA＋SB＋SC5 时，斯坦纳最小树即是最小生成树（详见，翁家丰，应用数学学报，2（1985）），其二是对一般 的集合构造次优树，即不一定最短但接近最短，通常以最小生成树为次优树，人们对点集 A，定义 r A( ) = 斯坦纳最小树长 最小生成树长 称 inf ( ) A ＝ r A 为最小斯坦纳比例，猜测 3 2 = ，由正三角形的例子知 3 0.866 2 ，曾 证得 3<n<5 时， 3 2 = ，黄光明[3]证明了 0.8 （1983 年），钟金芳蓉和 Graham 又宣布了 = 0.8241 （计算机结果），已经很接近了。最近（2000 年）我国运筹学家越民义[4]证明了猜测为 真。替代结果，最坏情形增加 13.4%的网络长，对随机情形只增加 3%。 （III）作业时间的优化 作业时间的优化问题，象大规模工程、房屋建筑、产品开发设计、维修以及工厂的开工投产活 动等一次完成的规划项目，如果对完工时间要求很严（如附有罚款条件），那么采用网络分析，以缩 短工时，则具有特别重要的意义。 运用网络来描述规划，制作进度表，可以有以下几方面的好处。 1． 有助于管理者系统的、全面的考虑规划，弄清程序，便于估计完成时间和找出可能的改进 方案，从而加快规划的实现。 2． 能提供工程计划的简明概况，其形式便于有关部门进行评论和参考，从而便于汇集各方面 的意见，找出存在的问题和延误工程的原因。 3． 对网络进行分析可找出关键路线，这就是网络中所需时间最长的一组活动。网络的解可以
揭示缩短哪些活动的时间,有助于缩短整个完工时间,它还可揭示在哪些活动中加班是无益的。某 些活动可延长时间而并不会延长总的完工时间,这就明确了各个工序或过程在网络中的地位 4.有助于识别有关任务及其时间顺序关系,从而可更好的分派职责,更有效地运用资源,当 出现问题时,网络可用来确定各种可能的其它解决方法。 5.网络分析可以说明各项活动的最早可能开始时间及最迟允许完工时间。 进度表法或称网络计划技术最早是在1957年,由美国杜邦公司研究出来的,最初用于计划和管 理化学工厂的筹建,其结果使该项工程比原计划缩短了两个月时间,随后又将此方法用于维修,使 原来需停工125小时的工程缩短为78小时,取得显著效果 还有其它一些典型问题,都可以用图论方法来处理,如最大流问题,最小费用流问题,以及匹 配(无公共顶点的边所成集合)问题,哈密顿回路和旅行商问题等等。 总之,图论所研究的问题主要分两类,一是给定的图中具有某种性质的点是否存在?若存在有 多少?或至多(少)有多少?二是如何构造一个具有某些性质的图或子图? 有关参考书: 李修睦著,图论导引,1982 卢开澄著,图论及其应用,1981 §3组合最优化 在运筹学的最优化问题中有一部分问题所涉及的因素的取值范围是离散的,而且在许多情况 下是有限的(例如只取0和1)。这类问题中有些不能用传统的数学式子描述,有一些可描述, 但极为复杂,以致变得不能驾驭。这类问题往往需要用某些特殊方法来处理,这样就产生了 门新兴学科一一组合最优化。它包含了许多常用的但一般很难于处理的著名问题,象在图与网 络一节中提到的最短路问题,最小树问题,匹配问题,旅行售货员问题,也都属于组合最优化 问题。下边我们针对一些典型问题介绍几种基本方法。 (Ⅰ)背包问题和 Greedy算法(贪婪算法)。 有n件东西重量为a.,i=1,……,n,价格为c,i=1,…,n,要求从中选出若干件装入背包, 既使总重量不超过M,又使总价值最大 Greedy算法:将比值亠由小到大排好队逐件考虑,不超重就装入,否则放弃之,考虑下一件。 算法的实质就是“挑好的装,装进后就不再换出”,不过一般地讲这种方法不一定能求得最优 解。其实背包问题是NP- Complete问题至今没有有效解法。 (Ⅱ)匹配问题和交错链方法 redy算法对背包问题不能保证求得最优解,但是能求得一个比较好的初始解,人们通常以 它为基础再作一些调整,如尝试用两件东西去换一件,或三件去换二件等办法来改进所求的解 交错链方法就是这种朴素思想的发展,它是组合最优化方法的核心,让我们通过匹配问题来说 明交错链方法 有n个工人和n项工作,每个人只能适应其中某几项工作。要求寻找一种分配方式,使得尽可
10 揭示缩短哪些活动的时间，有助于缩短整个完工时间，它还可揭示在哪些活动中加班是无益的。某 些活动可延长时间而并不会延长总的完工时间，这就明确了各个工序或过程在网络中的地位。 4． 有助于识别有关任务及其时间顺序关系，从而可更好的分派职责，更有效地运用资源，当 出现问题时，网络可用来确定各种可能的其它解决方法。 5． 网络分析可以说明各项活动的最早可能开始时间及最迟允许完工时间。 进度表法或称网络计划技术最早是在 1957 年，由美国杜邦公司研究出来的，最初用于计划和管 理化学工厂的筹建，其结果使该项工程比原计划缩短了两个月时间，随后又将此方法用于维修，使 原来需停工 125 小时的工程缩短为 78 小时，取得显著效果。 还有其它一些典型问题，都可以用图论方法来处理，如最大流问题，最小费用流问题，以及匹 配（无公共顶点的边所成集合）问题，哈密顿回路和旅行商问题等等。 总之，图论所研究的问题主要分两类，一是给定的图中具有某种性质的点是否存在？若存在有 多少？或至多（少）有多少？二是如何构造一个具有某些性质的图或子图？ 有关参考书： 李修睦著，图论导引，1982 卢开澄著，图论及其应用，1981 §3 组合最优化 在运筹学的最优化问题中有一部分问题所涉及的因素的取值范围是离散的，而且在许多情况 下是有限的（例如只取 0 和 1）。这类问题中有些不能用传统的数学式子描述，有一些可描述， 但极为复杂，以致变得不能驾驭。这类问题往往需要用某些特殊方法来处理，这样就产生了一 门新兴学科－－组合最优化。它包含了许多常用的但一般很难于处理的著名问题，象在图与网 络一节中提到的最短路问题，最小树问题，匹配问题，旅行售货员问题，也都属于组合最优化 问题。下边我们针对一些典型问题介绍几种基本方法。 （Ⅰ）背包问题和 Greedy 算法（贪婪算法）。 有 n 件东西重量为 i a ,i=1,……，n，价格为 i c ，i=1,……，n，要求从中选出若干件装入背包， 既使总重量不超过 M，又使总价值最大。 Greedy 算法：将比值 i i c a 由小到大排好队逐件考虑，不超重就装入，否则放弃之，考虑下一件。 算法的实质就是“挑好的装，装进后就不再换出”，不过一般地讲这种方法不一定能求得最优 解。其实背包问题是 NP-Complete 问题至今没有有效解法。 （Ⅱ）匹配问题和交错链方法 Greedy 算法对背包问题不能保证求得最优解，但是能求得一个比较好的初始解，人们通常以 它为基础再作一些调整，如尝试用两件东西去换一件，或三件去换二件等办法来改进所求的解。 交错链方法就是这种朴素思想的发展，它是组合最优化方法的核心，让我们通过匹配问题来说 明交错链方法。 有 n 个工人和 n 项工作，每个人只能适应其中某几项工作。要求寻找一种分配方式，使得尽可
能多的人分配到适应的工作岗位上。 例如有5个工人:A、B、C、D、E:5项工作1,2,3,4,5,各工人与各工作之间的适应关系 如图5所示。图中有线段相连表示适应。例如A适应于1和2,问最多能同时安排几个人的工作? 图5 图6 图7 从图上看,是要求利用线段来将图中的端点一一配对,且希望配得对数越多越好。这就是图论 中最大匹配问题。可见,所谓匹配就是无公共顶点的边所成集合。 首先,通过直觉观察,求出一个较好的初始匹配方案。在图中我们用粗线段表出,如图6所示。 这时已连上粗线段的点称为已盖点,尚未连粗线的点称为未盖点,图上的一条路,若路上的线段粗 细交错,则称其为交错链,如图7所示。称连接两个未盖点的交错链为增广链。对于增广链,细线 段比粗线段多一条。对给定的匹配方案I,假若存在一增广链S,那么只要把路S上的细线和粗线交 换一下,便可得到多安排一个人的新匹配方案I。通常用下述符号表示上述调整运算 T=lS=lUS/InS) 图论中有下列基本事实 定理1,一个匹配为最大匹配的充要条件是不存在关于它的增广链 如何寻找增广链?采用“树生长法”(或称标号法),以图6为例,开始任取一未盖点为树根, 如D,从树根沿着细线生长,接着从树梢岀发沿着粗线往外生长,这样交错的沿着细线粗线继续从 树梢往外延伸,直到不能再生长(如图8) 图8 我们称图(8)是以D为根的交错树,在树的生长过程中,一旦发现除树根外,另一未盖点被 长到树上,过程就可中止。这时树上连结两个未盖点的那条路,便是一条增广链。图8中D与⑤之 间就是一条增广链,沿着它们调整后,可得匹配如图9
11 能多的人分配到适应的工作岗位上。 例如有 5 个工人：A、B、C、D、E；5 项工作 1，2，3，4，5，各工人与各工作之间的适应关系 如图 5 所示。图中有线段相连表示适应。例如 A 适应于 1 和 2，问最多能同时安排几个人的工作？ A B C D E 1 2 3 4 5 A B C D E 1 2 3 4 5 图 5 图 6 图 7 从图上看，是要求利用线段来将图中的端点一一配对，且希望配得对数越多越好。这就是图论 中最大匹配问题。可见，所谓匹配就是无公共顶点的边所成集合。 首先，通过直觉观察，求出一个较好的初始匹配方案。在图中我们用粗线段表出，如图 6 所示。 这时已连上粗线段的点称为已盖点，尚未连粗线的点称为未盖点，图上的一条路，若路上的线段粗 细交错，则称其为交错链，如图 7 所示。称连接两个未盖点的交错链为增广链。对于增广链，细线 段比粗线段多一条。对给定的匹配方案 I，假若存在一增广链 S，那么只要把路 S 上的细线和粗线交 换一下，便可得到多安排一个人的新匹配方案 I 。通常用下述符号表示上述调整运算： I I S I S I S = = /( ) 图论中有下列基本事实： 定理 1，一个匹配为最大匹配的充要条件是不存在关于它的增广链。 如何寻找增广链？采用“树生长法”（或称标号法），以图 6 为例，开始任取一未盖点为树根， 如 D，从树根沿着细线生长，接着从树梢出发沿着粗线往外生长，这样交错的沿着细线粗线继续从 树梢往外延伸，直到不能再生长（如图 8） D 1 2 A B 3 4 C E 5 1 5 4 3 2 图 8 我们称图（8）是以 D 为根的交错树，在树的生长过程中，一旦发现除树根外，另一未盖点被 长到树上，过程就可中止。这时树上连结两个未盖点的那条路，便是一条增广链。图 8 中 D 与⑤之 间就是一条增广链，沿着它们调整后，可得匹配如图 9
图9 总结交错链方法的计算步骤如下: 1、任选初始的匹配图 2、利用树生长法寻找增广链。如找到一条增广链则转步骤3,如所有交错树上都无增广链, 则步骤终止,已找到最大匹配。 3、(调整)替换增广链上的粗线和细线,得到一个新的匹配图,然后转步骤1。 交错链方法的计算量是0(n2)。 最优匹配问题(亦称分配(派)问题) 假如我们进一步还知道了每个工人干各项工作的效率或产值,而要求找出使总的产值最大的 匹配方式,这在图论中称为最优问题,即图中每条线都有权与其相对应,要求找出使权和最大(或 最小)的匹配。 对交错链S,我们定义 (s)=∑o(e)+∑(-o(e') e为S上的粗线e'为S上的细线 其中O(e)表示线段e的权,称O(S)为S的长度,让lk表示在所有含K条线段的匹配中,使权 的和达到最大的匹配,进一步假如存在关于的增广链,则用Sx表示最短增广链,即 (S)=mn((S)S是的增广链 下面的定理是组合最优化中最基本的性质。 定理2,对l,若存在S,则有如下递推关系: k+1=14dSk,k=0,1,2, 据此定理,可知求解最优匹配的关键是寻求最短增广链S,然而求S又可化为在一个定向图 中,求两点的最短定向路问题,如求图10
12 A B C D E 1 2 3 4 5 1 5 4 3 2 图 9 总结交错链方法的计算步骤如下： 1、任选初始的匹配图。 2、利用树生长法寻找增广链。如找到一条增广链则转步骤 3，如所有交错树上都无增广链， 则步骤终止，已找到最大匹配。 3、（调整）替换增广链上的粗线和细线，得到一个新的匹配图，然后转步骤 1。 交错链方法的计算量是 O(n2 )。 最优匹配问题（亦称分配（派）问题） 假如我们进一步还知道了每个工人干各项工作的效率或产值，而要求找出使总的产值最大的 匹配方式，这在图论中称为最优问题，即图中每条线都有权与其相对应，要求找出使权和最大（或 最小）的匹配。 对交错链 S，我们定义 ( ) ( ) ( ( )) s e e = + − e 为 S 上的粗线 e 为 S 上的细线 其中 （e）表示线段 e 的权，称 （S）为 S 的长度，让 k I 表示在所有含 K 条线段的匹配中，使权 的和达到最大的匹配，进一步假如存在关于 k I 的增广链，则用 SK 表示最短增广链，即 ( ) min{ ( ) } S S S I k k = 是 的增广链 下面的定理是组合最优化中最基本的性质。 定理 2，对 k I ，若存在 SK，则有如下递推关系： k k k 1 I I S + = ， k = 0,1,2, 据此定理，可知求解最优匹配的关键是寻求最短增广链 k S ，然而求 k S 又可化为在一个定向图 中，求两点的最短定向路问题，如求图 10
图 图11 由图10的最短增广链,可对应地作出定向图11,容易求出图11S到t的最短定向路为 0D-7 ⊙8B89A80t 相应地,图10中的最短增广链为: 假如求上述最短定向路的计算量为o(n3),则求出最优匹配的计算量为o(n) 解分配问题亦可在表上进行,采用标号法求增广链和最大匹配,然后通过简单的矩阵变换, 逐步找出最优分配,这种形式的解法叫作匈牙利方法(详见管梅谷等,线性规划) 还可以用下面将介绍的分枝定界法、最小调整法求最优匹配。 还有二次分配问题。例如,对厂址和厂房要求一个总的分配(一对一),使得厂址之间的距离 各乘以相应工厂的运输量所得的和最小。 此问题很难解决,无有效算法,也几乎无有效的启发式算法可以利用。 (Ⅲ)排序问题和分枝定界法 在许多可能的顺序中找一个最优顺序,分配加上加工顺序的限制,就成排序问题,如A与B 两车床加工n件产品,加工时间分别为t:(A)和t(B),i=1,2,…,n。A先加工,然后B再加工,问 如何安排所用时间最少? 由于加工顺序是A先B后,故应尽量减少B的等待时间,因此不难理解其最优方案应是每次 从{t;(A),t;(B)}中取出一个最小值,若它属于{t:(A)},则应排在最先加工,若属于{t:(B)}, 则应排在最后加工,然后对已确定加工顺序的数据从{t(A),t1(B)}中去掉,在余集上重复上述过 程,依次排列,便得最优排序,此问题亦可用动态规划的方法求解。 上述是2×n的同顺序排序问题,对于一般的m×n(m>3)的同顺序排序问题以及不同顺序的排 序问题,要用“分枝定界法”求解,现将该方法简介如下: 分枝定界法 欲求 nIn f(X) X∈A 考虑求 min f(X) (3) X∈B 其中要求A≌B,称(3)为(2)的松弛问题,它要好解些。若(3)的最优解XB∈A,则X=XB;
13 A B C D 1 2 3 4 1 4 3 2 A B C D 1 2 3 4 1 4 3 2 8 9 6 8 8 6 7 -8 -6 9 -8 8 -6 -7 0 0 0 0 S t 图 10 图 11 由图 10 的最短增广链，可对应地作出定向图 11，容易求出图 11S 到 t 的最短定向路为： S 0 D -7 4 8 B -8 3 9 A -8 1 0 t 相应地，图 10 中的最短增广链为： D 4 B 3 A 1 假如求上述最短定向路的计算量为 3 o n( ) ,则求出最优匹配的计算量为 4 o n( )。 解分配问题亦可在表上进行，采用标号法求增广链和最大匹配，然后通过简单的矩阵变换， 逐步找出最优分配，这种形式的解法叫作匈牙利方法（详见管梅谷等[13]，线性规划） 还可以用下面将介绍的分枝定界法、最小调整法求最优匹配。 还有二次分配问题。例如，对厂址和厂房要求一个总的分配（一对一），使得厂址之间的距离 各乘以相应工厂的运输量所得的和最小。 此问题很难解决，无有效算法，也几乎无有效的启发式算法可以利用。 （Ⅲ）排序问题和分枝定界法 在许多可能的顺序中找一个最优顺序，分配加上加工顺序的限制，就成排序问题，如 A 与 B 两车床加工 n 件产品，加工时间分别为 ti(A)和 ti(B)，i＝1,2,…,n。A 先加工，然后 B 再加工，问 如何安排所用时间最少？ 由于加工顺序是 A 先 B 后，故应尽量减少 B 的等待时间，因此不难理解其最优方案应是每次 从｛ti(A)，ti(B)｝中取出一个最小值，若它属于｛ti(A)｝，则应排在最先加工，若属于｛ti(B)｝， 则应排在最后加工，然后对已确定加工顺序的数据从｛ti(A)，ti(B)｝中去掉，在余集上重复上述过 程，依次排列，便得最优排序，此问题亦可用动态规划的方法求解。 上述是 2×n 的同顺序排序问题，对于一般的 m×n(m>3)的同顺序排序问题以及不同顺序的排 序问题，要用“分枝定界法”求解，现将该方法简介如下： 分枝定界法 欲求 min ( ) f X X A （2） 考虑求 min ( ) f X X B （3） 其中要求 A B，称（3）为（2）的松弛问题，它要好解些。若（3）的最优解 o X A B ，则 o o X X A B = ；
否则分A为两个(或多个)子集:A=4A,4∩A2=④,解相应的松弛间题:mnf(x)J=2 若XB∈A,则A1问题已解决(否则,对A1重复A的过程)。同样若XB∈A2,则A2问题已解决, 从而min{f(XB),(XB)即为所求最小值。若XB∈4而BA2(但f(X)≥f(Xx)),则 A2亦不必考虑了;否则,对A2继续实行如同A的步骤,如此进行,直到求得最优值为止(∫取最 小的子集先考虑 (IV)旅行商问题和最小调整法 设有n个城市,C1,…,Cn,由C到C的路程dn为已知,一旅行商为了推销货物,从一城市 (如C1)出发,要经过所有城市,且每个城市正好经过一次,然后回到出发点。问题是如何选择 条最优路线。容易看出,旅行商有(n-1)!种方案可供选择,对于n=21这个不大的数目,就有 20!种方案,20!是个天文数字,即使用高速计算机也无法处理这一问题。这类问题至今没有有效 算法,甚至连有效的近似算法(JA)-1≤a,a>0与集合1无关)亦没有,被称为NP困难(完 fopr (n) 全)问题。 但是上述问题有着广泛的实际背景和深刻的经济含义,例如,在计算机的集成电路的设计中就 出现这一问题,还包括派车,排序,底板布线,考古学中的排号,自动钻井,工件加工顺序,邮局 到各个邮箱开箱收信,以及去各分局送邮件等其它许多方面。所有这些需要又促使我们不得不研究 它的解法。下面考虑用最小调整法来求解。 最小调整法的思想和步骤如下: 旅行商问题的关系矩阵为A A 其中元素an表示由第ⅰ个城市到第j个城市的路程 (1°)取每列的一个最小值,画圈,得一最小方案。若这些画圈元素又分属于不同行,则得到 相应分派问题的最优解,转(3°);否则转(2°)。 (2°)应把有二个以上画圈元素的行中的一个改画到同列的别处,待到某一无圈行中有一元素 画上圈,则算一次调整。如此进行,直到每行均有一个画圈元素时为止,然后转入 (3°)即可。而每次调整均以目标函数(其值为各画圈元素之和)增值最小为原则。 (3°)如果从1°或2°得到的分派问题最优解元素的任一行指标i出发,先到其列指标j,接着 从以j为行指标的元素出发,再到其列指标,如此进行下去,最后回到以i为列指标的元素止,便 形成一个圈,若圈中的元素恰为n个,则所得方案即为最优方案;否则,便会形成两个以上的子圈, 它不是最优解,需进行再调整,转(4°) (4)以增值最小的原则实行对调调整,所谓对调调整,就是于任二子圈中各取一个元素,如an
14 否则分 A 为两个（或多个）子集： 1 2 1 2 A A A A A = = , ，解相应的松弛问题： min ( ) 1,2 X Bj f X j = ； 若 1 1 o X A B ，则 A1 问题已解决（否则，对 A1 重复 A 的过程）。同样若 2 2 o X A B ，则 A2 问题已解决， 从而 1 2 0 0 min{ ( ), ( )} B B f X f X 即为所求最小值。若 1 1 o X A B 而 2 2 o X A B （但 2 1 ( ) ( ) B B f X f X ），则 A2 亦不必考虑了；否则，对 A2 继续实行如同 A 的步骤，如此进行，直到求得最优值为止（ f 取最 小的子集先考虑）。 （IV）旅行商问题和最小调整法 设有 n 个城市，C1，···，Cn，由 Ci 到 Cj 的路程 ij d 为已知，一旅行商为了推销货物，从一城市 （如 C1）出发，要经过所有城市，且每个城市正好经过一次，然后回到出发点。问题是如何选择一 条最优路线。容易看出，旅行商有（n－1）！种方案可供选择，对于 n＝21 这个不大的数目，就有 20！种方案，20！是个天文数字，即使用高速计算机也无法处理这一问题。这类问题至今没有有效 算法，甚至连有效的近似算法（ ( ) 1 , 0 ( ) A opt f I f I − 与集合 I 无关）亦没有，被称为 NP-困难（完 全）问题。 但是上述问题有着广泛的实际背景和深刻的经济含义，例如，在计算机的集成电路的设计中就 出现这一问题，还包括派车，排序，底板布线，考古学中的排号，自动钻井，工件加工顺序，邮局 到各个邮箱开箱收信，以及去各分局送邮件等其它许多方面。所有这些需要又促使我们不得不研究 它的解法。下面考虑用最小调整法来求解。 最小调整法的思想和步骤如下： 设旅行商问题的关系矩阵为 A 12 1 1 21 2 2 1 2 1 2 j n j n i i ij in n n nj a a a a a a A a a a a a a a = 其中元素 ij a 表示由第 i 个城市到第 j 个城市的路程。 （1º）取每列的一个最小值，画圈，得一最小方案。若这些画圈元素又分属于不同行，则得到 相应分派问题的最优解，转（3º）；否则转（2º）。 （2º）应把有二个以上画圈元素的行中的一个改画到同列的别处，待到某一无圈行中有一元素 画上圈，则算一次调整。如此进行，直到每行均有一个画圈元素时为止，然后转入 （3º）即可。而每次调整均以目标函数（其值为各画圈元素之和）增值最小为原则。 （3º）如果从 1º或 2º得到的分派问题最优解元素的任一行指标 i 出发，先到其列指标 j，接着 从以 j 为行指标的元素出发，再到其列指标，如此进行下去，最后回到以 i 为列指标的元素止，便 形成一个圈，若圈中的元素恰为 n 个，则所得方案即为最优方案；否则，便会形成两个以上的子圈， 它不是最优解，需进行再调整，转（4º）。 （4º）以增值最小的原则实行对调调整，所谓对调调整，就是于任二子圈中各取一个元素，如 ij a