运筹学讲义范本.doc

《运筹学讲义范本.doc》由会员分享，可在线阅读，更多相关《运筹学讲义范本.doc（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、运筹学讲义引言1年轻的学科：20世纪30年代，英国，美国，加拿大等在防空作战研究上提出的一种方法。当时叫operational research,缩写为O.R. 是一门年轻的学科。我国是在56年在中科院力学研究所成立运筹小组，80年成立运筹学会。2。应用数学：包括小到日常生活，如出门买东西的线路选择，大到国民经济建设优化组合，无处不在。例如，我国北宋时代，丁渭修皇宫P1。3。讲授内容：ch1.15;ch3; ch7;ch8;ch12;ch13.第一章 线性规划及单纯型法运筹学的一大分支是数学规划，而线性规划又是数学规划的重要组成部分。线性规划（linear programming 简写LP）也

2、是运筹学最基本的内容。相对于其他运筹学分支，LP理论完善，方法简单，应用广泛，是任何运筹分支首先要阐明的基本知识。 表1-1项目每天可用能力设备A（h）设备B（h）调试工序（h）06152115245利润（元）211 LP问题及其数学模型一. 问题的提出及建模例1 美佳公司计划制造，两种家电产品。已知各制造一件事分别占用的设备A，B的台时、调试时间、调试工序及每天可用于这两种家电的能力、各出售一件时的获利情况，如表1-1所示。问该公司应各制造两种家电各多少件，使获利最大？ 解：设制造，产品数量为，.则利润 z=2+ 问题是：在现有设备、调试能力的限制下，如何确定产量，.可使利润最大？我们把它数

3、学化： 目标函数：=2+ 设备B的限制非负约束调试能力限制设备A的限制 约 束条件其中（1）（3）资源限制，（4）为非负限制。 下面从数学的角度来归纳线性规划的模型特点：（1） 每一个问题都有一组变量称之为决策变量，一般记为，。对决策变量的每一组值：代表了一种决策方案。通常要求决策变量取值非负，即（=1，2，n）.（2）每个问题都有决策变量须满足的一组约束条件线性的等式或不等式。（3）每个问题都有一个关于决策变量的线性函数称为目标函数，要求这个目标函数在满足约束条件下实现最大或最小化。我们将约束条件及目标函数都是决策变量的线性函数的规划问题称之为线性规划。其一般模型为 （1.1.1）（目标函数

4、，或实现最大化，或实现最小化）（1.1.3）(非负约束)(1.1.2) (资源约束)s.t s.t 是subject to的英文缩写，它表示“以为条件”、“假定”、“满足”之意。另外，通常称目标函数中的系数为价值系数，表示第i种资源的拥有量。用可将上述模型简化成： s.t用向量形式表示时，上述模型可写为： s.t式中，用矩阵表示为s.t其中 A=称为约束方程组的系数矩阵。2 图解法一预备知识1直线上的点把平面分成三部分：直线上的点，直线一侧的点，直线上的点，直线另一侧的点。例：+=5 用集合表示 =（，）+=5，R2二元一次不等式的解集代表一个平面域。O55xy+=5例：+5， 分两部分：+=

5、5，及+53. 梯度：对多元函数u=(X), S,有如下的定义定义：设u=(X),XS,若在点处对于自变量的各分量的偏导数（都成立，则称函数u=(X)在点处一阶可导，并称向量(X)=是u=(X)在点出的梯度或一阶导数。例：（，）=2+， =（0），（0）=（1，2），=2，=3=12， （）=。函数在点处的几何意义是：（）是过点的(X)等直线（面）在点出的法向量,沿梯度正方向为函数在该点增加最快的方向。二下面还是以例1来说明用图解法求解线性规划问题。=2+5=15+=56+2=2O2+=z=2Q(3.5,1.5)tP（1）（3）是三个平面域，加上（4）限制在象限，可行域为Z=2+的梯度为z=(

6、2,1)T,梯度方向为t,沿t的方向是增加的方向，将等直线沿t平行推进，即将离开还未离开可行域的一根等直线记为，Q（3.5，1.5）即为此线性规划的最优解。Z=8.5. 即美佳公司应每天制造家电3.5件，家电1.5件，能获利润最大。最大利润z=8.5元。三。LP问题求解的几种可能情况：唯一，上例无穷多最优解 有最优解例 =+ 无界解目标函数z=+与约束线（3）+=5平行，最优解为PQ线段上的所有点。 无解无最优解的情况 无界解例：=2+可行域无界，造成无解解=，主要原因是漏掉了一些约束。 无界例：=2+ 可行域D=，建模有错误。四。有图解法得到的启示1。若可行域非空，则可行域为凸集。图2.1定

7、义：如果集合C中任意两个点，其连线上的所有点也都在集合C中，这样的集图2.2图2.3合称之为凸集。图2.4其中图2.1，2.2，2.4是凸集，图2.3不是。关于两点之间的连线，数学上是这样描述的： +（1-） （01）让从0向1移动，则直线上的点就从顶点移动到顶点。2。若LP有最优解，则最优解一定在凸集的顶点处取得。若在两个顶点处取得最优值，则在其连线上所有点都是最优值。3 单纯型法原理 一 LP问题的标准形式及其解的概念：1 LP问题的的标准形式：（1） 一般形式 s.t (2) 记号形式 s.t（3）向量形式 s.t其中，（4）矩阵形式 s.t A=，(x)O(x)-(x)XX2. 将非标

8、准化为标准形式（1）若目标函数为求最小化：minZ=CX 令= -z,即=-CX，此时max等价于minZ. 从右图可看出，max=-CX与minZ=CX,就最优解来说，相同。（2）若约束条件是，则在该约束条件不等式的左边加上一个新变量-称为松弛变量，将不等式改为等式。例：2+382+3+=8。（3） 若约束条件是型，则在该约束条件不等式左边减去一个新变量称为剩余变量，将不等式改为等式。例：2-3-452-3-4-=5（4）若某个约束方程的右端项0，则在约束方程两端乘以（-1）,不等好改变方向。（5）若决策变量无非负要求，则可另两个新变量0，0，作=-，且在原数学模型中，均用（-）来代替，而在

9、非负约束中增加0，0。（6）对0的情况，令=-，显然0。例3/P15 将下述线性规划化为标准形 Minz=+2+3取值无约束 s.t 解：上述问题中令= -z, =-，=-，其中0，0，按上述规则，该问题的标准形式为： Max= -2-3+3+0+0 s.t 3.线性规划问题解的概念： （2.1）s.t （2.2）可行解： 满足上述约束条件（2.2）的解，称为线性规划问题的可行解。全部可行解的集合称为可行域。最优解：使目标函数（2.1）达到最大值的可行解称为最优解。基：设为约束方程组（2.2）得系数矩阵，设（nm）设其秩为m,B是矩阵A的一个mm阶的满秩子矩阵，称B是LP问题的一个基。不失一般

10、性，设 B中的每一列向量（称为基向量。与基向量对应的变量对应的变量称为基变量。LP中除基变量以外的变量称为非基变量。基解：在约束方程（2.2）中令非基变量=0的解称为LP的基解。基可行解：满足变量非负约束条件的基解称为基可行解。可行基：对应于基可行解的基称为可行基。例4/P19 找出下述LP问题的全部基解，指出其中的基可行解，并确定最优解。 Maxz=2+3+ s.t解：首先，是基，对应的基解为 =5- =10-2 =4-令=0，得=5，=10，=4。为基可行解。同理，可求出其它基解及基可行解。4。单纯形迭代原理：前面讲过，若LP问题有最优解的话，定在可行域的某顶点处达到，又，一个顶点对应一个

11、基本可行解，一个自然的想法是：找出所有的基本可行解。因基本可行解的个数，通过“枚举法”，从理论上讲总能找出所有的基本可行解。而事实上随着m，n的增大，迅速增大，致使此路行不通。我们换一种思路：若从某一基本可行解（今后称之为初始基本可行解）出发，每次总是寻找比上一个更“好”的基本可行解，逐步改善，直至最优。这需要解决以下三个问题：（1） 如何找到一个初速的基本可行解。（2） 如何判别当前的基本可行解是否已达到了最有解。（3） 若当前解不是最优解，如何去寻找一个改善了的基本可行解。此思路称为单纯型法，单纯型原理是由美国数学家丹齐格（G.B.Danzig）在1947年为研究美国空军资源的优化配置时提

12、出的一种方法。我们还是从第一章例一为例1谈单纯型法的思想。max z =2x1+x2 (4.1)将(4.1)化为标准形式： (4.2)容易看出(3.1.2)中是基变量，将基变量用非基变量表示为 (4.3)将(4.3)带入目标函数得非基变量表示式:z=0+2 + (4.4) 若令非基变量x1=0, =0带入目标函数得到一个基本可行解 这个基本可行解显然不是最优解。因为从经济意义上讲， =0， =0，表示该公司不安排生产，因此就没有利润。相应地，将 =0， =0带入目标函数得Z（）=0。从数学角度看，(4.4)中非基变量 , 前的系数为正数,故若让非基变量 (或 )的取值从零增加,相应的目标函数值

13、Z也将虽之增加,因此就有可能找到一个新的基本可行解,使目标函数值比更“好”,或者说得到了改善.由于 前的系数比大,即每增加一个单位对Z值的贡献比大.故让的取值从零变为一个正值。即我们想让从非基变量转为基变量，今后我们称之为进基。因基变量只有三个，因此必须从原有的基，中选一个离开基转为非基变量。下解决两个问题： 应取多大的值？ 进基，那一个出基？现在，还是非基变量，仍取零值。式(43)变为： (4.5)为了让Z增,须增,但须有,0,从而 =4此时, =15, =0, =1。从而得一新的基本可行解 =（4，0，15，0，1）相应的基变量为，。看来进基，赶出了所对应的变量。记住这一结果，以后在表格法

14、中我们还要用它，称它为最小比值规则。类似地，用非基表示基变量得 (4.6)再将(4.6)带入目标函数得 Z=8+1/3至此，我们就可以把以上的运算制成一张表格，称单纯型表。2 1 0 0 0 基 b 0 150 240 50 5 1 0 06 2 0 1 01 1 0 0 1 5 2 1 0 0 0 说明： 此时，最后一行为目标函数系数，也称检验数。通过以上的分析知只要它们有正数存在，目标函数就不可能达最优，所以我们想通过基变量的转换，使这些检验数一个一个地变为零或负数。 检验数中2最大，进基，谁出呢？用最小比值法则，=4最小，对应6称为主元素，所在行对应基，出基。 初始基本可行解 =（0，0

15、，15，24，5） 目标函数值Z=（）T。b+2+0+0+0下让变成基，用行初等变换把6的位置变成1，所在列的其它位置变成零。2 1 0 0 0 基 b 0 152 40 10 5 1 0 01 2/6 0 1/6 00 4/6 0 -1/6 1 15/5=3 4/（1/3）=121/（4/6）=3/2 0 1/3 0 -1/3 0此时，=1/30，其解=（4，0，15，0，5）不是最优。目标函数Z=（0，2，0）+0+1/3+0-1/3+0目标值Z=（0，2，0）+0+1/3+0-1/3+0类似地, 进基, 出基。用行的初等变换把4/6位置变成1，4/6所在列其它位置变成0，形成下表 2 1

16、 0 0 0 基 b 0 15/22 7/21 3/20 0 1 5/4 -15/21 0 0 1/4 -1/20 1 0 -1/4 3/2 0 0 0 -1/4 -1/2例（无穷多最优解）max z =x1+x2三s.t (4.1)将(4.1)化为标准形式：解：1 1 0 0 0 基 b 0 150 240 50 5 1 0 06 2 0 1 01 1 0 0 1 5 1 1 0 0 01 1 0 0 0 基 b 0 152 40 10 5 1 0 01 2/6 0 1/6 00 4/6 0 -1/6 1 15/5=3 4/（1/3）=121/（4/6）=3/2 0 2/3 0 -1/6 0

17、1 1 0 0 0 基 b 0 15/22 7/21 3/20 0 1 5/4 -15/21 0 0 1/4 -1/20 1 0 -1/4 3/2 0 0 0 0 -1LP问题单纯型表检验数0，且其中有一个非基变量的检验数=0，则该LP问题有无穷多最优解。例（无界解） Maxz=6+2+10+8s.t 5+6-4-420 3-3+2+825 4-2+310 0(j=1,4)解：此LP问题的标准形为：Maxz=6+2+10+8 s.t 5+6-4-4+ =20 3-3+2+8 + =25 4-2+3 +=10 0(j=1,7)对应的单纯型表为： 6 2 10 8 0 0 0 基 b 0 200

18、250 105 6 -4 -4 1 0 03 -3 2 8 0 1 04 -2 1 3 0 0 1 25/ 210/1 6 2 10 8 0 0 06 2 10 8 0 0 0 基 b 0 600 50 1021 -2 0 8 1 0 4-5 1 0 2 0 1 -24 -2 1 3 0 0 1 25/ 210/1 -34 22 0 -22 0 0 -106 2 10 8 0 0 0 基 b 0 700 50 2011 0 0 12 1 2 0-5 1 0 2 0 1 -2-6 0 1 7 0 2 -3 5/1 76 0 0 -66 0 -22 34注意：=340，但，即进基，但基变量，没有出

19、基元素，什么意思呢？此LP问题是无界解。5 单纯型法的进一步讨论一 人工变量法在上述例中，LP问题化为标准形后约束条件的系数矩阵中含有单位矩阵，以此作初始基，建立单纯型表求解很方便。看下面的例例6 用单纯型法求解LP问题 Maxz=-3+ s.t +4 -2+-1 (5.1) 3+=9 ,0 解：先将(5.1)化为标准形 Maxz=-3+0 +0 s.t + =4 -2+- -=1 （5.2） 3+ =9 , 0 此时，约束条件的系数矩阵中不含有单位矩阵，怎么办？将（5.2）强行加上人工变量，使（5.2）变为 Maxz=-3+0 +0 -M-M s.t + =4-2+- -+ =1 （5.3）

20、3+ +=9,，0此时的（5.3）与（5.2）一般情况下是不等价的，只有当=0时才等价。我们在目标函数中把，前面系数设成-M，称作“罚因子”，其含义是只要，0，目标函数就不可能达到最优。为此，尽快逼它=0，即把它从基中赶出来。过河拆桥，卸磨杀驴。求解时，把M看成非常大的常数来处理。见下表-3 0 1 0 0 -M -M 基 b 0 4-M 1-M 91 1 1 1 0 0 0-2 1 -1 0 -1 1 00 3 1 0 0 0 1 4 1 3 -2M-3 4M 1 0 -M 0 00 30 1-M 63 0 2 1 1 -1 0-2 1 -1 0 -1 1 06 0 4 0 3 -3 1 1

21、1 6M-3 0 4M+1 0 3M -4M 00 00 3-3 10 0 0 1 -1/2 -1/2 1/20 1 1/3 0 0 0 1/31 0 2/3 0 1/2 -1/2 1/6 93/2 0 0 3 0 3/2 -M-3/2 M+1/20 00 5/21 3/20 0 0 1 -1/2 1/2 -1/2-1/2 1 0 0 -1/4 1/4 1/43/2 0 1 0 3/4 -3/4 1/4 11 -9/2 0 0 0 -3/4 M+3/4 M-1/4注：一旦某人工变量从基变量中赶出，变为非基变量后，该变量及相应的列克从单纯型表中删除，而不影响计算结果。二 两阶段法： 用大M法处理

22、人工变量，再用手工计算是不会碰到麻烦。但用电子计算机求解时，对M就只能在计算机内输入一个极其最大字长的数字。如果LP问题中的，或等参数值与这个代表M的数相对比较接近，或远远小于这个数字，由于计算机计算时取值上的误差，有可能使计算结果发生错误。为了克服这个困难，可以对添加人工变量后的LP问题分两个阶段来计算，称两阶段法。两阶段法的第一阶段实现求解一个目标中只包含人工变量的LP问题，即令目标函数中其它变量的系数取零，人工变量的系数取某个正的常数（一般取1），在保持原问题约束不变的情况下求这个某标函数极小化的解。显然在第一阶段中，当人工变量取值为0时，目标函数值也为0。这时候的最优解就是原问题的一个

23、基可行解。如果第一阶段求解结果最优解的目标函数值不为0，也即最优解的基变量中含有非灵的人工变量，表明原LP问题无可行解。当第一阶段求解结果表明有可行解时，第二阶段是原问题中除去人工变量，并从此可行解（即第一阶段的最优解） 以下用量阶段法求例6例6 第一阶段先化为 min=+ s.t + =4-2+- -+ =1 （5.4）3+ +=9,，0把（5.4）化为标准型，令=- 有 Max =- s.t + =4-2+- -+ =1 （5.3）3+ +=9,，00 0 0 0 0 -1 -1 基 b 0 4-1 1-1 91 1 1 1 0 0 0-2 1 -1 0 -1 1 00 3 1 0 0 0

24、 1 0 0 0 0 0 -1 -1先把基，对应的列向量，化为单位向量，然后计算单纯型表,目标是尽快把人工变量，从基变量中赶出。0 0 1 0 0 -1 -1 基 b 0 4-1 1-1 91 1 1 1 0 0 0-2 1 -1 0 -1 1 00 3 1 0 0 0 1 4 1 3 -2 4 0 0 -1 0 00 30 1-1 63 0 2 1 1 -1 0-2 1 -1 0 -1 1 06 0 4 0 3 -3 1 11 6 0 4 0 3 -4 00 00 30 10 0 0 1 -1/2 -1/2 1/20 1 1/3 0 0 0 1/31 0 2/3 0 1/2 -1/2 1/6

25、 93/2 0 0 0 0 0 -1 1 准备工作做到这里，实质上就是找到了原LP问题的一组基，。把原目标函数不变，接着这组基，继续作，即第二阶段 目标函数 max z = -3+0 +0 -3 0 1 0 0 基 b 0 00 3-3 10 0 0 1 -1/2 0 1 1/3 0 0 1 0 2/3 0 1/2 -3 0 1 0 0 把基，对应的列向量，化为单位向量0 00 3-3 10 0 0 1 -1/2 0 1 1/3 0 0 1 0 2/3 0 1/2 93/2 0 0 3 0 3/2 0 00 5/21 3/20 0 0 1 -1/2 -1/2 1 0 0 -1/4 3/2 0

26、1 0 3/4 -9/2 0 0 0 -3/4 最优解为X*=（0，5/2，3/2，0，0）T,目标函数值为z*=3/2.三 单纯型法计算中的几个问题1 退化与循环问题：按最小比值来确定换出基变量时，有时出现两个以上相同的最小比值，从而使下一个表的基可行解中出现一个或多个基变量等于零的退化解。退化解出现的原因是模型中存在多余的约束，使多个基可行解对应同一个顶点。当存在退化解时，就有可能出现迭代计算的循环。即从一个可行基经有限次迭代后又回到原来的可行基。尽管可能性及其微小（直到目前为止，还没有见到一个实际应用问题产生循环的例子），但在理论上讲是存在的。有人提出用下标值最小的变量作为换出变量来防止

27、循环。 我们不管它，当出现两个相等的最小比值时，任选一个出基。盼望出现循环实例。E.Beale曾给出一个循环的例子例 用单纯型法求解 maxZ=3/4-20+1/2-6 s.t +1/4-8 - +9=0 +1/2-12-1/2+3=0 + =1显然，是初始可行基变量，经过6次迭代后，又回到了初始状态。得不到最优解。有兴趣的同学可自行用单纯型法验证本题产生的循环现象。而实际上本题有最优解： X*=（3/4，0，0，1，0，1，0）T2 无可行解的判别例7 用单纯型法求解线形规划问题 Max z =2+s.t +2 2+26 ,0解 由2图解法知此LP问题无可行解，先用单纯型法求解，化标准型且加人工变量得 max z =2+0+0-M s.t + =2 2+2 -+=6 02 1 0 0 -M 基 b 0 2-M 61 1 1 0 0 2 2 0 -1 1 2 3 2+2M 1+2M 0 -M 0 2 2-M 21 1 1 0 0 0 0