揭示缩短哪些活动的时间,有助于缩短整个完工时间,它还可揭示在哪些活动中加班是无益的。某 些活动可延长时间而并不会延长总的完工时间,这就明确了各个工序或过程在网络中的地位 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