运筹学复习课件

1、胡晓青658205）运 筹 学（Operations Research） 第一章 线性规划及单纯形法 LP的数学模型 图解法 单纯形法 单纯形法的进一步讨论人工变量法 LP模型的应用本章主要内容：线性规划问题的数学模型某企业计划生产甲、乙两种产品。这些产品分别要在A、B、C、D、四种不同的设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台时如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？ 设 备产 品 A B C D利润（元） 甲 2 1 4 0 2 乙 2 2 0 4 3 有 效 台 时 12 8 16 12线性规划问题的数学模型解：设x1

2、、x2分别为甲、乙两种产品的产量，则数学模型为：max Z = 2x1 + 3x2 x1 0 , x2 0s.t. 2x1 + 2x2 12 x1 + 2x2 8 4x1 16 4x2 12问题分析决策变量：混合饲料中两种原料的数量，设采购玉米 斤，采购红薯 斤目标函数：成本最小，则 约束条件： 碳水化合物的营养要求： 蛋白质的营养要求： 维他命的营养要求： 非负约束：例1.3 物流网络配送问题（成本最低）某物流公司需将三个工厂（1、2、3）生产的一种新产品运送到A、B两个仓库，工厂1和工厂2的产品可以通过铁路运送到仓库A，数量不限；工厂3的产品可以通过铁路运送到仓库B，同样数量不限。由于铁路

3、运输成本较高，公司同时考虑用卡车来运送，但每个工厂要用卡车先将产品运到配送中心（每个工厂用卡车最多运送60单位），再从配送中心用卡车运到各个仓库（每个仓库最多收到用卡车送来的货物90单位）。公司管理层希望以最小的成本来运送所需的货物。产量BAT1322.32.33.03.49.23.5606060908.27.5901008070工厂单位运输成本仓库需求量120130问题分析决策变量：各条路线的运输量 表示节点 i 到节点 j 的数量BAT132目标函数：总运输成本最小 问题分析线性规划问题的求解方法一 般 有三种方法图 解 法单纯形法计算机辅助（Excel，Lingo等）两个变量、直角坐标三

4、个变量、立体坐标适用于任意变量、但必需将一般形式变成标准形式图解法max Z = 2X1 + X2 X1 + 1.9X2 3.8 X1 - 1.9X2 3.8s.t. X1 + 1.9X2 10.2 X1 - 1.9X2 -3.8 X1 ，X2 0例：用图解法求解线性规划问题图解法max Z=3X1+5.7X2x1x2oX1 - 1.9X2 = 3.8 ()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8()X1 + 1.9X2 = 10.2 ()（7.6，2）DL0： 0=3X1+5.7X2 max Z（3.8，4）34.2 = 3X1+5.7X2 蓝色线段上的所有点都

5、是最优解这种情形为有无穷多最优解，但是最优目标函数值max Z=34.2是唯一的。可行域图解法min Z=5X1+4X2x1x2oX1 - 1.9X2 = 3.8 ()X1 + 1.9X2 = 3.8()X1 + 1.9X2 = 10.2 ()DL0： 0=5X1+4X2 max Z min Z 8=5X1+4X2 43=5X1+4X2 （0，2）可行域此点是唯一最优解图解法246x1x2246无界解(无最优解)max Z=x1+2x2例1.6x1+x2=4()x1+3x2=6()3x1+x2=6() max Z min Zx1x2O10203040102030405050无可行解(即无最优解

6、)max Z=3x1+4x2例1.7图解法学习要点：1. 通过图解法了解线性规划有几种解的形式（唯一最优解；无穷多最优解；无界解；无可行解）2. 作图的关键有三点： (1) 可行解区域要画正确 (2) 目标函数增加的方向不能画错 (3) 目标函数的直线怎样平行移动线性规划问题的数学模型目标函数：约束条件：3. 线性规划数学模型的一般形式简写为：线性规划问题的数学模型（2）如何化标准形式 目标函数的转换 如果是求极小值即 ， ，则可将目标函数乘以(-1)，可化为求极大值问题。也就是：令 ，可得到上式。即 若存在取值无约束的变量 ，可令 其中： 变量的变换线性规划问题的数学模型 约束方程的转换：由

7、不等式转换为等式。称为松弛变量称为剩余变量 变量 的变换 可令 ， 显然线性规划问题的数学模型(2) 第一个约束条件是“”号，在“”左端加入松驰变量x4，x40,化为等式；(3) 第二个约束条件是“”号，在“”左端减去剩余变量x5，x50；(4) 第3个约束方程右端常数项为-5，方程两边同乘以(-1),将右端常数项化为正数； (5) 目标函数是最小值，为了化为求最大值，令z=-z,得到max z=-z，即当z达到最小值时z达到最大值，反之亦然;线性规划问题的数学模型标准形式如下：线性规划问题的数学模型4. 线性规划问题的解线性规划问题求解线性规划问题，就是从满足约束条件(2)、(3)的方程组中

8、找出一个解，使目标函数(1)达到最大值。单纯形法的计算步骤单纯形法的思路找出一个初始可行解是否最优转移到另一个基本可行解（找出更大的目标函数值）最优解是否循环核心是：变量迭代结束单纯形法的计算步骤例1.8 用单纯形法求下列线性规划的最优解解：1）将问题化为标准型，加入松驰变量x3、x4则标准型为:单纯形法的计算步骤2）求出线性规划的初始基可行解，列出初始单纯形表。cj3400icB基bx1x2x3x40 x34021100 x43013013400检验数单纯形法的计算步骤cj3400icB基变量bx1x2x3x40 x34021100 x430130134000 x34x23x14x2换入列b

9、i /ai2，ai204010换出行将3化为15/311801/301/31011/3303005/304/3乘以1/3后得到103/51/518011/52/540011单纯形法的计算步骤例1.9 用单纯形法求解解：将数学模型化为标准形式：不难看出x4、x5可作为初始基变量，列单纯形表计算。单纯形法的计算步骤cj12100icB基变量bx1x2x3x4x50 x4152-32100 x5201/31501121000 x42x220 x221/3150120753017131/309022560 x111017/31/31250128/9-1/92/335/300-98/9-1/9-7/3单

10、纯形法的计算步骤学习要点：1. 线性规划解的概念以及3个基本定理2. 熟练掌握单纯形法的解题思路及求解步骤单纯形法的进一步讨论人工变量法人工变量法：前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。单纯形法的进一步讨论人工变量法例1.10 用大M法解下列线性规划解：首先将数学模型化为标准形式系数矩阵中不存在单位矩阵，无法建立初始单纯形表。

11、单纯形法的进一步讨论人工变量法故人为添加两个单位向量，得到人工变量单纯形法数学模型：其中：M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下表。 单纯形法的进一步讨论人工变量法cj32-100-M-MCBXBbx1x2x3x4x5x6x7i0 x64-431-10104-Mx5101-1201005-Mx712-21000113-2M2+M-1+2M-M0 x63-650-1013/5-Mx58-3300108/3-1x312-210005-6M5M0-M002x23/56/5101/50-Mx531/53/5

12、003/5131/3-1x311/52/5012/505 00002x213010123x131/310015/3-1x319/300102/3000-5-25/3Chapter5 目标规划( Goal programming )目标规划问题及其数学模型目标规划的图解分析法目标规划应用举例本章主要内容：目标规划问题及其数学模型例5.1 某企业计划生产甲，乙两种产品，这些产品分别要在A,B,C,D四种不同设备上加工。按工艺文件规定，如表所示。ABCD单件利润甲11402乙22043最大负荷1281612目标规划问题及其数学模型但企业的经营目标不仅仅是利润，而且要考虑多个方面，如：力求使利润指标不

13、低于12元；考虑到市场需求，甲、乙两种产品的生产量需保持1:1的比例；C和D为贵重设备，严格禁止超时使用；设备B必要时可以加班，但加班时间要控制；设备A即要求充分利用，又尽可能不加班。要考虑上述多方面的目标，需要借助目标规划的方法。目标规划问题及其数学模型3. 目标的优先级与权系数在一个目标规划的模型中，为达到某一目标可牺牲其他一些目标，称这些目标是属于不同层次的优先级。优先级层次的高低可分别通过优先因子P1,P2,表示。对于同一层次优先级的不同目标，按其重要程度可分别乘上不同的权系数。权系数是一个个具体数字，乘上的权系数越大，表明该目标越重要。现假定： 第1优先级P1企业利润； 第2优先级P

14、2甲乙产品的产量保持1:1的比例 第3优先级P3设备A,B尽量不超负荷工作。其中设备A的重要性比设备B大三倍。目标规划问题及其数学模型上述目标规划模型可以表示为：目标规划问题及其数学模型目标规划数学模型的一般形式达成函数目标约束其中：gk为第k个目标约束的预期目标值， 和 为pl 优先因子对应各目标的权系数。目标规划的图解分析法目标规划的图解法：适用两个变量的目标规划问题，但其操作简单，原理一目了然。同时，也有助于理解一般目标规划的求解原理和过程。图解法解题步骤：1. 将所有约束条件（包括目标约束和绝对约束，暂不考虑正负偏差变量）的直线方程分别标示于坐标平面上。2. 确定系统约束的可行域。3.

15、 在目标约束所代表的边界线上，用箭头标出正、负偏差变量值增大的方向目标规划的图解分析法3. 求满足最高优先等级目标的解4. 转到下一个优先等级的目标，再不破坏所有较高优先等级目标的前提下，求出该优先等级目标的解5. 重复4，直到所有优先等级的目标都已审查完毕为止6. 确定最优解和满意解。目标规划的图解分析法例5.2 用图解法求解下列目标规划问题目标规划的图解分析法(a)(b)(c)(d )x2x1(e)(f)d1-d1+d2+d2-d3-d3+d4-d4+满意解(3,3)04683462 2目标规划的图解分析法x1x2(a)(b)d1+d1-(c)d2-d2+(d)d3-d3+GD满意解是线段

16、GD上任意点其中G点X(2,4),D点X(10/3,10/3)05.51055.6112,410/3,10/35107例5.3目标规划的图解分析法Ox1x22040605020406050abd1-d1+d2-d2+cdd3-d3+d4-d4+(24,26)满意解X=(24，26)例5.4实 例 设某公司生产两种型号的电扇，一种为普通型，装配一个需要1小时，另一种为豪华型，装配一个需要2小时。正常的装配时间每周限定为40小时。市场调查表明每周销售普通型不超过30件，豪华型不超过15件。普通型每件的净利润为8元，豪华型为每件12元。公司经理提出如下优先次序的要求： 1计划利润不少于400元2装配

17、线尽可能少加班3根据市场调研要求每周生产的产品数不能多于销售的数量，即普通型电扇为30件，豪华型电扇为15件。该问题的决策目标是：（1）总利润不少于400元；（2）尽可能少加班；（3）生产数量不能超过预销售数量。（4）绝对目标约束。所谓绝对目标约束就是必须要严格满足的约束。绝对目标约束是最高优先级，在考虑较低优先级的目标之前它们必须首先得到满足。实 例Chapter6 图与网络分析( Graph Theory and Network Analysis )图的基本概念与模型树与图的最小树最短路问题网络的最大流本章主要内容：树与图的最小树 树：无圈的连通图即为树性质1：任何树中必存在次为1的点。性

18、质2：n 个顶点的树必有n-1 条边。性质3：树中任意两个顶点之间，恰有且仅有一条链。性质4：树连通，但去掉任一条边，必变为不连通。性质5：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。v1v2v3v4v5v6树与图的最小树v1v7v4v3v2v5v620159162532817412336练习：应用破圈法求最小树树与图的最小树v1v7v4v3v2v5v620159162532817412336树与图的最小树v1v7v4v3v2v5v6201591625328174123树与图的最小树v1v7v4v3v2v5v6201591625328174123树与图的最小树v1v7v4v3v2v5

19、v61591625328174123树与图的最小树v1v7v4v3v2v5v61591625328174123树与图的最小树v1v7v4v3v2v5v691625328174123树与图的最小树v1v7v4v3v2v5v691625328174123树与图的最小树v1v7v4v3v2v5v6925328174123树与图的最小树v1v7v4v3v2v5v6925328174123树与图的最小树v1v7v4v3v2v5v69328174123树与图的最小树v1v7v4v3v2v5v69328174123树与图的最小树v1v7v4v3v2v5v693174123min=1+4+9+3+17+23=

20、57树与图的最小树练习：应用避圈法求最小树v1v7v4v3v2v5v620159162532817412336树与图的最小树v1v7v4v3v2v5v620159162532817412336树与图的最小树v1v7v4v3v2v5v620159162532817412336树与图的最小树v1v7v4v3v2v5v620159162532817412336树与图的最小树v1v7v4v3v2v5v620159162532817412336树与图的最小树v1v7v4v3v2v5v620159162532817412336树与图的最小树v1v7v4v3v2v5v62015916253281741233

21、6min=1+4+9+3+17+23=57某公司铺设光导纤维网络某公司的管理层已经决定铺设最先进的光导纤维网络，为公司的主要中心之间提供高速通信（数据、声音、图像等）。下图中的节点显示了该公司主要中心（包括公司的总部、巨型计算机、研究区、生产和配送中心等）的分布图。虚线是铺设纤维光缆的可能位置。每条虚线旁的数字表示了如果选择在这个位置铺设光缆需要花费的成本。ADCFEG43722B5445711ADCFEG43722B2445711最优解图示总成本为2+2+1+3+1+5=14树与图的最小树课堂练习：3749346321Min C(T)=12Min C(T)=15254173314475答案：

22、树与图的最小树34122323242Min C(T)=12213638534567454321Min C(T)=18最短路问题从一特殊的节点出发，找出从该节点到网络中任何其它节点的最短路径问题GPS导航系统寻找最优路径问题描述：就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路 .有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。最短路问题求最短路有两种算法: 狄克斯屈拉(Dijkstra)标号算法 逐次逼近算法最短路问题例6.5 求下图v1到v7的最短路长及最短路线86252353

23、4210570862254411147510711v7已标号，计算结束。从v1到v7的最短路长是 11,最短路线： v1 v4 v6 v7P标号T标号12最短路问题从上例知，只要某点已标号，说明已找到起点vs到该点的最短路线及最短距离，因此可以将每个点标号，求出vs到任意点的最短路线，如果某个点vj不能标号，说明vs不可达vj 。注：无向图最短路的求法只将上述步骤2将弧改成边即可。最短路问题例6.6 求下图v1到各点的最短距离及最短路线。4526178393261216180452231039612641166188122482418所有点都已标号，点上的标号就是v1到该点的最短距离，最短路线

24、就是红色的链。最短路问题课堂练习：1. 用Dijkstra算法求下图从v1到v6的最短距离及路线。v3v54v1v2v4v635222421v1到v6的最短路为：最短路问题2. 求从v1到各点的最短路径237184566134105275934682最短路问题237184566134105275934682p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10v1到v8的最短路径为v1v4v7v5v8，最短距离为10最短路问题3. 求下图中v1点到另外任意一点的最短路径v1v2v3v4v6v5322762133最短路问题v1V2V3V4 V6V5322762133024714最短路问题v1V2V3V4 V6V5322762133024714网