第二章运筹学各分支简介 运筹学作为一门学科,在理论和方法上取得了巨大的进展,现在我们就来介绍一下各分支研究 题的对象和基本的分析方法,使读者对它们有一个概貌的了解 作为一门学科来说,运筹学的内容可以大致表示如下: 线性 优选,统筹 数学规划 非线性,几何 组合最优化 确定性模型 图论,网络流 整数,参数,多目标 动态规划 运筹学 投入产出 决策 对策 随机性模型」排队,更新,维修,可靠性 随机控制 模拟 以下对其中的主要分支,分别介绍如下。 §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+SC<AC+BC(注意SA+SC=SD)。 当n=4时,方法仍是用一新点E代替两原顶点C,D(△ECD成一正三角形),先求△ABE的 斯点S1,连SE交外接圆于S2,则S1和S2即为所求(图4)。同样若以新点E’代替A,C,则可另 得二个斯点,如此递归进行,可以求出任意个顶点的所有斯点。 S1.S2 图4 问题是图形数目太多(当n=7,S≤5,共有62370个图形),有人( Garey等)已证明最短网络 是NP- complete问题,因此n略大时,譬如n≥100,计算机就不能胜任,目前可做10个顶点的问 题 现在研究方向有二,其一是对具有特殊性质的点集构造斯坦纳树,如对正n边形顶点集合,当 n>5时,斯坦纳最小树即是最小生成树(详见,翁家丰,应用数学学报,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＋SC<AC+BC（注意 SA＋SC＝SD）。 当 n＝4 时，方法仍是用一新点 E 代替两原顶点 C，D（△ECD 成一正三角形），先求△ABE 的 斯点 S1，连 S1E 交外接圆于 S2，则 S1 和 S2 即为所求（图 4）。同样若以新点 E 代替 A，C，则可另 得二个斯点，如此递归进行，可以求出任意个顶点的所有斯点。 A B D C E E 1 S 2 S 图 4 问题是图形数目太多（当 n S = 7, 5 ，共有 62370 个图形），有人（Garey 等）已证明最短网络 是 NP-complete 问题，因此 n 略大时，譬如 n 100 ，计算机就不能胜任，目前可做 10 个顶点的问 题。 现在研究方向有二，其一是对具有特殊性质的点集构造斯坦纳树，如对正 n 边形顶点集合，当 n>5 时，斯坦纳最小树即是最小生成树（详见，翁家丰，应用数学学报，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． 对网络进行分析可找出关键路线，这就是网络中所需时间最长的一组活动。网络的解可以