第一篇总论(运筹学简介) 第一章运筹学的含义及其特点 §1运筹学的含义及发展概况 运筹学在欧美简称OR( Operations Research)。日本译为“运用学”,我国译为“运筹学”,除 了“运用”,又充实以“筹划”,意义更深,它是许多管理、生产、设计、科研等单位所需要的工具, 其定义,到目前为止已是数以百计,按世界上最早出现的运筹学会(1948年)一—英国运筹学会所 下的定义,运筹学是运用科学方法来解决工业、商业、政府、国防等部门里有关人力、机器、物质、 金钱等大型系统的指挥或管理中出现的复杂问题的一门科学。 般来说,运筹学所能作的事情就是:把当事人所提出的问题以及涉及的系统,以科学的态度 弄清楚,并以科学的语言表达出来,若有可能,尽量用数学语言来描述,同时又必须以严格的科学 态度搜集和分析可以得到的资料,挑选出其中与问题有关的,并看看缺少哪些有用的资料。假若这 些缺少的资料由于某种原因不能搜集到,则要考虑会产生什么结果,特别要着重研究那些可控制的 因素,注意它们的变化对整个系统可能产生的影响,研究的目的就是要对问题所涉及的系统得到确 切的了解,提出解决问题的途径,以便最优地去控制系统使之服务于当事人的最大利益。 可见,运筹学的目的,就是要帮助当事人作出决策:对情况作出客观的分析,对各种可能出现 的情况作出科学的估计,提出控制系统的途径和方法 运筹学是在第二次世界大战中孕育和发展起来的,战后,英国于1948年成立了运筹学俱乐部 (1953年改为“运筹学”学会),1950年出版了《运筹学季刊》,美国1949年成立了运筹学委员会, 同年出版了《运筹学》。运筹学被引进我国是上世纪50年代的事。1980年中国运筹学会成立,1982 年出版了《运筹学杂志》(后改为《运筹学学报》)。现在全世界已有30多个国家成立了全国运筹学 会,与运筹学有关的刊物估计在40份以上,1959年由美、英、法倡导建立了国际运筹学会( IFORS), 至今已有成员会员44个,国际或区域性会员7个,共举行十六届国际运筹学会议,我国1981年7 月第一次以会员国的身份参加了第九届国际运筹学会议,1982年正式加入,1984年8月在美国参加 了第十次会议,并在分组会上做了报告,第15届大会已于1999年8月在北京举行,这是中国运筹 学会首次承办的国际运筹学会议 总之,正如其他科学一样,运筹学的发展也是一种从小到大,从简单到复杂的过程 §2运筹学的特点一一注重算法的研究 由运筹学的含义可以看出,它除了具有多分支之外,一个最显著的特点就是以为重大实际问题 提供科学有效的解决方法为目标,因之对算法的研究始终是运筹学的首要任务,这也是运筹学具有 针对性和实用性二大特点的体现,所以对算法本身,我们必须有一个正确的认识和全面的了解 算法体系的轮廓大致描绘如下
1 第一篇 总论（运筹学简介） 第一章 运筹学的含义及其特点 §1 运筹学的含义及发展概况 运筹学在欧美简称 O.R（Operations Research）。日本译为“运用学”，我国译为“运筹学”，除 了“运用”，又充实以“筹划”，意义更深，它是许多管理、生产、设计、科研等单位所需要的工具， 其定义，到目前为止已是数以百计，按世界上最早出现的运筹学会（1948 年）——英国运筹学会所 下的定义，运筹学是运用科学方法来解决工业、商业、政府、国防等部门里有关人力、机器、物质、 金钱等大型系统的指挥或管理中出现的复杂问题的一门科学。 一般来说，运筹学所能作的事情就是：把当事人所提出的问题以及涉及的系统，以科学的态度 弄清楚，并以科学的语言表达出来，若有可能，尽量用数学语言来描述，同时又必须以严格的科学 态度搜集和分析可以得到的资料，挑选出其中与问题有关的，并看看缺少哪些有用的资料。假若这 些缺少的资料由于某种原因不能搜集到，则要考虑会产生什么结果，特别要着重研究那些可控制的 因素，注意它们的变化对整个系统可能产生的影响，研究的目的就是要对问题所涉及的系统得到确 切的了解，提出解决问题的途径，以便最优地去控制系统使之服务于当事人的最大利益。 可见，运筹学的目的，就是要帮助当事人作出决策：对情况作出客观的分析，对各种可能出现 的情况作出科学的估计，提出控制系统的途径和方法。 运筹学是在第二次世界大战中孕育和发展起来的，战后，英国于 1948 年成立了运筹学俱乐部 （1953 年改为“运筹学”学会），1950 年出版了《运筹学季刊》，美国 1949 年成立了运筹学委员会， 同年出版了《运筹学》。运筹学被引进我国是上世纪 50 年代的事。1980 年中国运筹学会成立，1982 年出版了《运筹学杂志》（后改为《运筹学学报》）。现在全世界已有 30 多个国家成立了全国运筹学 会，与运筹学有关的刊物估计在 40 份以上，1959 年由美、英、法倡导建立了国际运筹学会（IFORS）， 至今已有成员会员 44 个，国际或区域性会员 7 个，共举行十六届国际运筹学会议，我国 1981 年 7 月第一次以会员国的身份参加了第九届国际运筹学会议，1982 年正式加入，1984 年 8 月在美国参加 了第十次会议，并在分组会上做了报告，第 15 届大会已于 1999 年 8 月在北京举行，这是中国运筹 学会首次承办的国际运筹学会议。 总之，正如其他科学一样，运筹学的发展也是一种从小到大，从简单到复杂的过程。 §2 运筹学的特点——注重算法的研究 由运筹学的含义可以看出，它除了具有多分支之外，一个最显著的特点就是以为重大实际问题 提供科学有效的解决方法为目标，因之对算法的研究始终是运筹学的首要任务，这也是运筹学具有 针对性和实用性二大特点的体现，所以对算法本身，我们必须有一个正确的认识和全面的了解。 算法体系的轮廓大致描绘如下：
算法 迭代法 直接法 收敛算法 未经证明为收敛的算法(启发法) 近似算法 有限算法 路状结构算法 树状结构算法 算法是理解为“用以解决一个以数学语言叙述出来的问题的方法”,这囊括了所有的算法。 直接法:某些算法并不是以迭代方式进行的,我们称之为直接法,例如,求导数: y=(x"y=nxn1。 迭代法:大多数的算法都是以迭代方式进行的。例如某些子程序重复使用几次。求解 f(x)=0分x=0(x-1) 未经证明收敛的算法(启发法):迭代法不一定收敛于所求的解,这就是称为启发法的算法 近似算法:有些收敛算法并不保证得到精确解,得到的只是一个近似解,它们不是有限算法, 每多迭代一步,就会向精确解靠近一步,例如 Newton法 f(xn) f(x1)等等 有限算法:能保证经有限次迭代即可得到精确解的收敛算法,称之为有限算法 路状结构算法:许多有限算法皆有路状结构,即是说,一次迭代连着一次迭代而不产生分岔的 迭代序列: 例如求矩阵的逆,线性规划中的单纯形法,几种最短路算法,网络中的最大流问题等等。 树状结构算法:在其余的有限算法中,迭代序列形成一棵由几条平行的枝做成的树:
2 算 法 迭 代 法 直 接 法 收 敛 算 法 未 经 证 明 为 收 敛 的 算 法 （ 启 发 法 ） 近 似 算 法 有 限 算 法 路 状 结 构 算 法 树 状 结 构 算 法 算法是理解为“用以解决一个以数学语言叙述出来的问题的方法”，这囊括了所有的算法。 直接法：某些算法并不是以迭代方式进行的，我们称之为直接法，例如，求导数： 1 ( )n n y x nx − = = 。 迭代法：大多数的算法都是以迭代方式进行的。例如某些子程序重复使用几次。求解： 1 ( ) 0 ( ) k k f x x x = = − 未经证明收敛的算法（启发法）：迭代法不一定收敛于所求的解，这就是称为启发法的算法。 近似算法：有些收敛算法并不保证得到精确解，得到的只是一个近似解，它们不是有限算法， 每多迭代一步，就会向精确解靠近一步，例如 Newton 法： 1 ( ) ( ) k k k k f x x x f x + = − ，等等 有限算法：能保证经有限次迭代即可得到精确解的收敛算法，称之为有限算法。 路状结构算法：许多有限算法皆有路状结构，即是说，一次迭代连着一次迭代而不产生分岔的 迭代序列： 例如求矩阵的逆，线性规划中的单纯形法，几种最短路算法，网络中的最大流问题等等。 树状结构算法：在其余的有限算法中，迭代序列形成一棵由几条平行的枝做成的树：
大多数树状搜索算法属于此类,例如动态规划、分支定界法、有界列举法等等 近似算法倾向于具有路状结构,而启发法则可认为是一种简约树状结构算法,它按某种规则舍 弃一些候选者,启发法的结构可表示如下 有些问题,对于它们不存在有效的收敛算法,即不存在一种可接受的时间内收敛于所求解的算 法,这种情况下启发法是一项有力的工具。 衡量一种算法好坏的重要标准是算法的计算次数或计算时间,显然计算次数与问题的规模有关。 设问题的规模为n,如果存在n的一个多项式P(n),使得该问题的任何实例都可以在计算次数 F(n)=O(P(m)之内解出,则称该问题存在多项式的时间算法,简称多项式算法。其中P(n)称为 计算的复杂性。一个问题若存在多项式算法,就认为它可以有效地用计算机求解,该算法就称为好 算法。若算法的计算次数F(n)=O(a")(a≥2),则称算法为指数型的。一般认为指数型算法不是 好算法。 存在这样一类问题,其目前最快算法所需计算次数是n的指数函数而非多项式,因此n略大时
3 大多数树状搜索算法属于此类，例如动态规划、分支定界法、有界列举法等等。 近似算法倾向于具有路状结构，而启发法则可认为是一种简约树状结构算法，它按某种规则舍 弃一些候选者，启发法的结构可表示如下： 有些问题，对于它们不存在有效的收敛算法，即不存在一种可接受的时间内收敛于所求解的算 法，这种情况下启发法是一项有力的工具。 衡量一种算法好坏的重要标准是算法的计算次数或计算时间，显然计算次数与问题的规模有关。 设问题的规模为 n，如果存在 n 的一个多项式 P(n)，使得该问题的任何实例都可以在计算次数 F n O P n ( ) ( ( )) = 之内解出，则称该问题存在多项式的时间算法，简称多项式算法。其中 P n( ) 称为 计算的复杂性。一个问题若存在多项式算法，就认为它可以有效地用计算机求解，该算法就称为好 算法。若算法的计算次数 ( ) ( )n F n O a = ( 2) a ，则称算法为指数型的。一般认为指数型算法不是 好算法。 存在这样一类问题，其目前最快算法所需计算次数是 n 的指数函数而非多项式，因此 n 略大时
计算机就不能胜任,故以其在计算上难于对付而闻名,被称为NP- Complete问题,例如旅行售货员 问题、时间表问题等等。数学家强烈的认为(但并未证明):人们不可能找出一个有效算法这一事实 是NP- Complete问题的固有性质,他们相信,不会有有效算法存在(如其一具有有效算法,余者皆 然),因此,对这类问题,寻找近似解的有效算法便自然成为人们追求的方向。 然而对算法的认识并未到此完结,人们很快发现上述复杂性概念只涉及到算法在最坏情况下的 性态,而这种最坏情况在实际中发生的概率究竟有多大,并未予以考虑,以致出现了多项式算法反 倒不如非多项式算法在实算中有效的奇怪现象。例如,单纯形算法已被实践证明是普遍实用和非常 有效的,但人们也举例证明了它不是多项式算法,哈奇杨算法已被证明是多项式算法,但在许多实 践中,其计算速度反比单纯形算法慢得多。这说明用算法在最坏情况下的性态来区别好坏不是最科 学的,而算法的平均性态才是衡量算法好坏的最有说服力、最重要的标志。因此那种仅凭一、两个 并不具有代表性的例子来肯定或否定一种算法的思想和行为是不可取的。 对于解决同一类问题的各种算法,优劣立判的并不常见,往往是尺短寸长,各有特点。方法一 可能在解决A子类问题上更有效,方法二可能在解决B子类问题上更优越,应当实事求是地进行具 体分析,不宜简单的肯定一种而否定另一种。那种认为某类问题已有有效算法,从而对新提出的一 些算法一概采取轻视过于挑剔甚至排斥态度,这于算法的发展是有害的。对算法亦应采取“百花齐 放,推陈出新”的方针,特别是对比较成熟领域的基本算法,哪怕是稍有些微改进,也可能产生较 大的经济效益,因此更加不能忽视 算法的发展是没有穷尽的,人们对算法的认识也在逐步深入,我们期待着有更多的好算法出现, 为社会服务,为人类造福
4 计算机就不能胜任，故以其在计算上难于对付而闻名，被称为 NP-Complete 问题，例如旅行售货员 问题、时间表问题等等。数学家强烈的认为（但并未证明）：人们不可能找出一个有效算法这一事实 是 NP-Complete 问题的固有性质，他们相信，不会有有效算法存在（如其一具有有效算法，余者皆 然），因此，对这类问题，寻找近似解的有效算法便自然成为人们追求的方向。 然而对算法的认识并未到此完结，人们很快发现上述复杂性概念只涉及到算法在最坏情况下的 性态，而这种最坏情况在实际中发生的概率究竟有多大，并未予以考虑，以致出现了多项式算法反 倒不如非多项式算法在实算中有效的奇怪现象。例如，单纯形算法已被实践证明是普遍实用和非常 有效的，但人们也举例证明了它不是多项式算法，哈奇杨算法已被证明是多项式算法，但在许多实 践中，其计算速度反比单纯形算法慢得多。这说明用算法在最坏情况下的性态来区别好坏不是最科 学的，而算法的平均性态才是衡量算法好坏的最有说服力、最重要的标志。因此那种仅凭一、两个 并不具有代表性的例子来肯定或否定一种算法的思想和行为是不可取的。 对于解决同一类问题的各种算法，优劣立判的并不常见，往往是尺短寸长，各有特点。方法一 可能在解决 A 子类问题上更有效，方法二可能在解决 B 子类问题上更优越，应当实事求是地进行具 体分析，不宜简单的肯定一种而否定另一种。那种认为某类问题已有有效算法，从而对新提出的一 些算法一概采取轻视过于挑剔甚至排斥态度，这于算法的发展是有害的。对算法亦应采取“百花齐 放，推陈出新”的方针，特别是对比较成熟领域的基本算法，哪怕是稍有些微改进，也可能产生较 大的经济效益，因此更加不能忽视。 算法的发展是没有穷尽的，人们对算法的认识也在逐步深入，我们期待着有更多的好算法出现， 为社会服务，为人类造福
