揭示缩短哪些活动的时间,有助于缩短整个完工时间,它还可揭示在哪些活动中加班是无益的。某 些活动可延长时间而并不会延长总的完工时间,这就明确了各个工序或过程在网络中的地位 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 项工作，每个人只能适应其中某几项工作。要求寻找一种分配方式，使得尽可