管理运筹学课件第一章管理运筹学——线性规划(共74页).doc

《管理运筹学课件第一章管理运筹学——线性规划(共74页).doc》由会员分享，可在线阅读，更多相关《管理运筹学课件第一章管理运筹学——线性规划(共74页).doc（74页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、精选优质文档-倾情为你奉上管理运筹学课件第一章_管理运筹学线性规划管理运筹学Operational Research天津大学管理学院郭均鹏管理运筹学教师简介：郭均鹏：博士，副教授， 硕士生导师。主要研究领域： 运筹决策技术；信息管理与8企业信息3化；绩效考核与薪酬体系设计 联系方式：天津大学管理学院， guojptju.edu管理运筹学授课内容： 线性规划 图论与网络分析 网络计划 风险型决策排队论 博弈论课程教材：吴育华,杜纲. 管理科学基础，天津大学出版社。管理运筹学绪 论 产生于二战时期，运筹学（Operational Research) 直译为“运作研究”。 60年代，在工业、农业、社

2、会等各领域得到广泛应用 在我国，50年代中期由钱学森等引入 运用数学方法，为决策者进行最优决策提供科学依据的一门应用科学。一、运筹学的产生与发展二、学科性质管理运筹学三、运筹学的分支线性规划非线性规划图论与网络分析存储论决策论排队论对策论（博弈论）管理运筹学四、管理运筹学的工作程序明确问题问题分类建立数学模型求解数学模型结果分析实施 注意计算机软件的应用 Lindo、WinQSB等管理运筹学第一章 线性规划（Linear Programming，简称LP）1 线性规划的模型与图解法一、LP问题及其数学模型例1 某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源，有关单耗数据如表，试拟定使总收

3、入最大的生产计划。127单价300103油20054电36049煤资源限制乙甲产品资源管理运筹学127单价300103油20054电36049煤资源限制乙甲产品资源线性规划模型三要素：（1）决策变量 设甲产品生产x1，乙产品生产x2（2）目标函数 Max Z=7 x1 +12x2（3）约束条件9 x1 +4x23604x1 +5x2 2003 x1 +10x2 300x1 , x20s.t.返回Subject To， 意为“使其满足”管理运筹学Max （Min） Z = c1 x1 + c2 x2 + + cn xn a11 x1 + a12 x2 + + a1n xn （ =, ）b1 am

4、1 x1 + am2 x2 + + amn xn （ =, ）bmx1 ，x2 ， ，xn 0s.t. LP模型的一般形式矩阵表示Max Z = CXAX bX 0s.t.其中: X= (x1,x2, , xn) T 为决策变量 C=(c1,c2, , cn) 称为价格系数A=(aij)mn 称为技术系数b= (b1,b2, , bm) T 称为资源系数管理运筹学课堂练习 某蓄场每日要为每头牲畜购买饲料，以使其获取所需的A、B、C、D四种养分。有关数据如下表，现饲料可从市场上出售的M、N两种饲料中选择，试决定总花费最小的购买方案。（列出模型）78510每头日需2000.20.40.30.1N3

5、0000.30.20.5M价格DCBA养分饲料管理运筹学课堂练习 某蓄场每日要为每头牲畜购买饲料，以使其获取所需的A、B、C、D四种养分。有关数据如下表，现饲料可从市场上出售的M、N两种饲料中选择，试决定总花费最小的购买方案。（列出模型）78510每头日需2000.20.40.30.1N30000.30.20.5M价格DCBA养分饲料答案：设购买M饲料x1，N饲料x20.5 x1 +0.1x2100.2x1 +0.3x2 50.3x1 +0.4x2 8 0.2x2 7x1 , x20s.t.Min Z=300 x1 +200x2管理运筹学二、线性规划的图解法1. 步骤（1）作约束的图形可行域可

6、行解的集合先作非负约束再作资源约束9x1+4x2=3604x1+5x2=2003x1+10x2=300公共部分，即为可行域例：煤电油例Max Z=7 x1 +12x29 x1 +4x23604x1 +5x2 2003 x1 +10x2 300x1 , x20s.t.x1x240206080100204060801000管理运筹学（2）作目标函数的等值线给z不同的值，作相应直线，判断出z增大时，直线的移动方向将直线向增大方向移动，直至可行域边界，交点X*即为最优解。7x1+12x2=847x1+12x2=168如：令7 x1 +12x2=84 7 x1 +12x2=1689x1+4x2=3604

7、x1+5x2=2003x1+10x2=300x1x240206080100204060801000X*=（20，24），Z*=428管理运筹学最优解： x1 = 0， x2 = 1 最优目标值 z = 3课堂练习图解法求解线性规划012341234x1x2O-1-2(1)(2)(3)管理运筹学2. LP 解的几种情况（1）唯一解（2）多重最优解（3）无可行解注：出现（3）、（4）情况时，建模有问题（4）无有限最优解管理运筹学图解法的结论：线性规划的可行域是凸集 线性规划的最优解若存在，必在可行域的在极点获得 若在两个极点同时获得，则有无穷多最优解凸集不是凸集极点管理运筹学三、 线性规划应用举例

8、与软件求解 例1 （下料问题） 某工厂要做100套钢架，每套用长为2.9 m,2.1 m,1.5 m的圆钢各一根。已知原料每根长7.4 m，问：应如何下料，可使所用原料最省？管理运筹学 例1 （下料问题） 某工厂要做100套钢架，每套用长为2.9 m,2.1 m,1.5 m的圆钢各一根。已知原料每根长7.4 m，问：应如何下料，可使所用原料最省？余料1.52.12.9方案7.4 m2.9m2.1m1.5 m2010.11200.31110.910300301.10220.20130.80041.4管理运筹学501030 2x1 + x2 + x3 + x4 = 100 2x2 + x3 + 3

9、x5 + 2x6 + x7 = 100 x1 + x3+ 3x4 + 2x6 + 3x7 + 4x8 = 100 x1, x2, x3, x4, x5, x6, x7, x8 0设 x1,x2,x3,x4,x5,x6,x7,x8 分别为上述8种方案下料的原材料根数，建立如下的LP模型：最优解为： x1=10,x2=50,x3=0,x4=30,x5=0,x6=0,x7=0,x8=0min Z =x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8s.t.余料1.52.12.9方案2010.11200.31110.910300301.10220.20130.80041.4管理

10、运筹学一、线性规划的标准型Max Z = c1 x1 + c2 x2 + + cn xn a11 x1 + a12 x2 + + a1n xn =b1 am1 x1 + am2 x2 + + amn xn =bmx1 ，x2 ， ，xn 0s.t.1、标准形式Max Z = CXAX=bX 0s.t.注：标准型中要求bi 02 单纯形法矩阵表示管理运筹学2、非标准型标准型（1）Min Z = CXMax Z' = -CX（2）约束条件例如： 9 x1 +4x23609 x1 +4x2+ x3=360松弛变量 “”型约束，加松弛变量； “”型约束，减松弛变量；（3）自由变量xj进行变量

11、替换： xj= xj ' - xj ' ' ，其中xj ' 、 xj ' ' 0管理运筹学二、LP解的基本概念考虑标准型：Max Z = CXAX=bX 0s.t.（1）（2）1. 可行解满足（1）、（2）的解2. 基本解设r(A)=m，则BX=b有唯一解，称为基本解，简称基解。且不妨设非奇异，。设为，结论：基本解的个数管理运筹学3. 基可行解若基解X0，则称为基可行解。可行解基解基可行解结论：LP的基可行解对应于可行域的顶点。基：A中m阶可逆子阵，记为B。基向量：B中的列。基变量：和基向量相对应的决策变量。其余部分称为非基子阵，记为

12、N。管理运筹学例、研究约束集合基本解的个数令x2=x3=0，得基本解X1=(1/2, 0, 0)T,对应于A点；1/211/3ABCx2x3x1令x1=x3=0，得基本解X2=(0, 1, 0)T,对应于B点；令x1=x2=0，得基本解X3=(0, 0, 1/3)T,对应于C点；管理运筹学基可行解例、研究约束集合基本解的个数令x1=0，得基本解X1=(0, 3, 2, -1)T,对应于A点；令x2=0，得基本解X2=(3, 0, 1, -8)T,对应于B点；令x3=0，得基本解X3=(2, 1, 0, 5)T,对应于F点；画出可行域12341234ABCDEF0x1x2标准化令x4=0，得基本

13、解X4=(1/3, 8/3, 5/3, 0)T,对应于D点；管理运筹学三、单纯形法的基本方法基本方法：确定初始基可行解检验是否最优？转到另一更好的基可行解停YN方法前提：模型化为标准型管理运筹学1. 初始可行基B0的确定若A中含有I：B0=I若A中不含I：人工变量法管理运筹学2. 最优性检验矩阵分块把目标函数用非基变量表示：检验数向量，记为。当 0时，当前解为最优解。方法：（1）计算每个xj的检验数（2）若所有j 0 ，则当前解为最优；否则，至少有k >0 ，转3。管理运筹学3. 换基迭代（基变换）（1）进基：取对应的Pk进基。（2）出基：取对应的Pl进基。得新基，转2。管理运筹学的计算

14、:x5x4x3x2x1B-1bCBXB四、单纯形法的实现单纯形表例：煤电油例Max Z=7 x1 +12x29 x1 +4x23604x1 +5x2 2003 x1 +10x2 300x1 , x20s.t.Max Z=7 x1 +12x29 x1 +4x2 +x3 =3604x1 +5x2 +x4 = 2003 x1 +10x2 +x5 = 300x1 ,x50s.t.化为标准型x3x4x5000360200300943451010001000112000单纯形表:7管理运筹学x5x4x3x2x1B-1bCBXB四、单纯形法的实现单纯形表例：煤电油例Max Z=7 x1 +12x29 x1

15、+4x23604x1 +5x2 2003 x1 +10x2 300x1 , x20s.t.Max Z=7 x1 +12x29 x1 +4x2 +x3 =3604x1 +5x2 +x4 = 2003 x1 +10x2 +x5 = 300x1 ,x50s.t.化为标准型x3x4x5000360200300943451010001000112000单纯形表:790的计算:4030管理运筹学x5x4x3x2x1B-1bCBXB四、单纯形法的实现单纯形表例：煤电油例Max Z=7 x1 +12x29 x1 +4x23604x1 +5x2 2003 x1 +10x2 300x1 , x20s.t.Max

16、Z=7 x1 +12x29 x1 +4x2 +x3 =3604x1 +5x2 +x4 = 2003 x1 +10x2 +x5 = 300x1 ,x50s.t.化为标准型x3x4x5000360200300943451010001000112000单纯形表:7904030 枢纽元素管理运筹学x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000单纯形表:7904030 x3x4x20012300.31000.1以10为主元进行初等行变换502.5001-0.52407.8010-0.43.4000-1.2即:管理运筹学x5x4x3x2x

17、1B-1bCBXBx3x4x5000360200300943451010001000112000单纯形表:7904030 x3x4x20012300.31000.1以10为主元进行初等行变换502.5001-0.52407.8010-0.43.4000-1.2即:30.820100管理运筹学x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000单纯形表:7904030 x3x4x20012300.31000.1以10为主元进行初等行变换502.5001-0.52407.8010-0.43.4000-1.230.820100 管理运筹学

18、x3x1x2071224010-0.120.16201000.4-0.284001-3.121.16000-1.36-0.52x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000单纯形表:7904030 x3x4x20012300.31000.1502.5001-0.52407.8010-0.43.4000-1.230.820100 以 为主元进行初等行变换2.5管理运筹学x3x1x2071224010-0.120.16201000.4-0.284001-3.121.16000-1.36-0.52x5x4x3x2x1B-1bCBXB

19、x3x4x5000360200300943451010001000112000单纯形表:7904030 x3x4x20012300.31000.1502.5001-0.52407.8010-0.43.4000-1.230.820100 X*=(20,24,84,0,0)T Z*=428管理运筹学例：用单纯形法求解Min S= - x1 +2x2x1 - x2 - 2x1 +2x2 6x1 , x20s.t.化为标准型Max S?= x1 -2x2-x1 + x2 +x3 = 2x1 +2x2 +x4= 6x1 , ,x40s.t.-216102160x4不考虑011-120x3x4x3x2x1

20、B-1bCBXB-10-40102161x1113080x3X*=(6,0,8,0)T Z*= -6管理运筹学x3x1x2071224010-0.120.16201000.4-0.284001-3.121.16000-1.36-0.52x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000单纯形表:7904030x3x4x20012300.31000.1502.5001-0.52407.8010-0.43.4000-1.230.820100注：单纯形表中的信息每一列的含义：B-1(b A)=(B-1b, B-1 P1,， B-1 Pn

21、)每个表中的B和B-1的查找： B从初表中找； B-1从当前表中找，对应于初表中的I的位置。 以第2个表为例：管理运筹学终表分析最优基B* 和(B*)-1的查找x3x1x2071224010-0.120.16201000.4-0.284001-3.121.16000-1.36-0.52x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000单纯形表:7904030x3x4x20012300.31000.1502.5001-0.52407.8010-0.43.4000-1.230.820100注：单纯形表中的信息管理运筹学1五、人工变量法

22、（大M法）1 问题:例：用单纯形法求解Max Z = 5x1+3x2+2x3+4x45x1+ x2+ x3+8x4=102x1+4x2+3x3+2x4=10x1,x2,x3,x4 0s.t.Max Z = CXAX=bX 0s.t.设问题：，A中不含I()管理运筹学增加人工变量 X人=（xn+1，xn+m）T，X人在目标函数中的系数为 -M（M为充分大正数）。于是原问题化为：2 方法:单纯形法求解() ,若最优基变量中不含X人，则所得解的前n个分量即为X*否则， ()无解。3 结论:Max Z = CX- M X人AX +IX人=bX , X人 0s.t.()管理运筹学例：用单纯形法求解Max

23、 Z = 5x1+3x2+2x3+4x45x1+ x2+ x3+8x4=102x1+4x2+3x3+2x4=10x1,x2,x3,x4 0s.t.解：增加人工变量x5、x6，则模型化为：Max Z = 5x1+3x2+2x3+4x4-Mx5-Mx65x1+ x2+ x3+8x4+x5 =102x1+4x2+3x3+2x4 +x6=10x1,x6 0s.t.管理运筹学Max Z = 5x1+3x2+2x3+4x4-Mx5-Mx65x1+ x2+ x3+8x4+x5 =102x1+4x2+3x3+2x4 +x6=10x1,x6 0s.t.01x51234208115x6x4x3x2x1B-1bCB

24、XBx5x6-M-M10105+7M3+5M2+4M4+10M005/45管理运筹学01x51234208115x6x4x3x2x1B-1bCBXBx5x6-M-M10105+7M3+5M2+4M4+10M005/45x4x64-M5/45/81/81/81015/23/415/411/4015/2+3/4M005/2+15/4M3/2+11/4M102管理运筹学01x51234208115x6x4x3x2x1B-1bCBXBx5x6-M-M10105+7M3+5M2+4M4+10M005/45x4x64-M5/45/81/81/81015/23/415/411/4015/2+3/4M005/

25、2+15/4M3/2+11/4M102x4x24313/501/30121/5111/150200-1/35/310管理运筹学01x51234208115x6x4x3x2x1B-1bCBXBx5x6-M-M10105+7M3+5M2+4M4+10M005/45x4x64-M5/45/81/81/81015/23/415/411/4015/2+3/4M005/2+15/4M3/2+11/4M102x4x24313/501/30121/5111/150200-1/35/310x1x2535/3101/185/35/30113/18-1/30-10/30-4/9X*=(5/3, 5/3, 0, 0)

26、T, Z*=40/3管理运筹学六、单纯形法总结1、Min型单纯形表与Max型的区别仅在于： 令 k=minj 0的xk进基，当 0时最优。2、解的几种情况及其在单纯形表上的体现（讨论Max型）唯一最优解j 0,非基<0多重最优解j 0有非基k=0无界解有k >0但B-1Pk 0无可行解用大M法求解，最优基中含有X人退化解最优解中某基变量为0管理运筹学3 线性规划的对偶问题（Dual Programming，简称DP）一、对偶问题的提出和模型1、问题的提出煤电油例 今有另厂要购买三种资源，在原厂可接受的条件下，单价多少可是另厂付费最低？Max Z=7 x1 +12x29 x1 +4x

27、23604x1 +5x2 2003 x1 +10x2 300x1 , x20s.t.设煤电油价格分别为y1, y2, y3Min W=360y1+200y2+300y3s.t.9y1+4y2+3y374y1+5y2+10y312y1, y2, y3 0DUAL管理运筹学2、模型Max Z = CXAXbX 0s.t.原问题（P）：对偶问题（D）：Min W = bTYATY CTY 0s.t.特点：（1）P为max型，D为min型（2）P的变量个数=D的约束个数（3）P的约束个数=D的变量个数Max Z=7 x1 +12x29 x1 +4x23604x1 +5x2 2003 x1 +10x2

28、300x1 , x20s.t.Min W=360y1+200y2+300y3s.t.9y1+4y2+3y374y1+5y2+10y312y1, y2, y3 0管理运筹学1、对称性（P）与（D）互为对偶二、对偶性质与定理2、弱对偶性设X、Y 分别为（P）、（D）的任一可行解，则管理运筹学3、解的最优性设 、 分别为（P）与（D）的可行解，且则4、无界性若（P）为无界解，则（D）无可行解若（D）为无界解，则（P）无可行解管理运筹学5、对偶定理若（P）有最优解，则（D）也有最优解，且二者最优值相等.管理运筹学小结：（1）对偶最优解Y*= CB B-1，其中B为原问题的最优基；（2）如何从（P）的终

29、表中确定Y* ? Y*即为（P）终表的XS的检验数的负值； 若无XS，则用Y*= CB* (B*)-1计算。- CB B-1C - CB B-1AB-1B-1A CB B-1b0XSCX6、检验数管理运筹学x3x1x2071224010-0.120.16201000.4-0.284001-3.121.16000-1.36-0.52x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000例：煤电油的单纯形表:7904030（初表）（终表）由终表：Y*=(0 ,1.36 , 0.52)T管理运筹学三、对偶问题最优解的经济解释影子价格 设DP

30、其最优值为Z *(注：与LP最优值同），则根据Z * = bT y* = b1y1* + b2y2* + ? + bmym*?Z / ?bi = yi* 简单推导： Y*=(y1* , y2* ,， ym* ）为DP的最优解，则yi* 表示 LP某资源bi 变化1个单位对目标 产生的影响，称 yi* 为 bi的影子价格。例、煤电油例的对偶问题的最优解为Y* =(0 1.36 0.52), 则煤电油三种资源的影子价格分别为0 、 1.36 、 0.52管理运筹学影子价格在管理决策中的作用：（1）影子价格市场价格 若影子价格市场价格，则应影子价格市场价格，则应买进该资源卖出该资源（2）影子价格反映

31、了资源的稀缺性， 影子价格越高，则越稀缺例如：煤的影子价格为0，则表明有剩余管理运筹学4 灵敏度分析任务：当LP的系数A、b、c变化时，是否影响最优解或最优基？ 或：若不影响最优解或最优基， A、b、c的变化范围？对解的影响可行性：B-1b0最优性：管理运筹学一、b变（只影响解的可行性）问题：br在何范围变化时，不影响最优基？设第 r 种资源brbr+ （b）方法：（保证可行性）即，解出即可例：煤电油例，讨论b2的变化解得-5027或150b2227管理运筹学二、C 变（只影响解的最优性）问题： cj在何范围变化时，不影响最优基（解）？设第 j 种资源cjcj+ （c ）方法：（讨论检验数）（

32、1） cj为非基价格系数，解出管理运筹学（2） cj为基价格系数此时需考虑所有非基变量的检验数：解出例：煤电油例，为使最优解不变，求c1的变化范围。解：考虑所有非基检验数同理，令基变量的检验数仍全为0，故无需考虑。管理运筹学三、A 变（1） 增加新变量xn+1810单价48油36电123煤丁丙例如，煤电油例又增加产品丙或丁，相关数据如右表。问题：增加后是否影响最优基（解），从而判断是否 有利？（使目标改善）方法：是否有利取决于是否进基。故只需计算，则有利，则不利例:丙不应投产。同理可得丁应投产。管理运筹学（2） 某列Pj Pj?（只考虑非基向量情形）问题：改变后是否影响最优基（解）、有利？方法：只需计算，则有利，则不利管理运筹学5 整数规划Integer Programming(简称IP)一、整数规划的一般模型LP: max z=CX AX=b X0IP: max z=CX AX=b X0 X为整数管理运筹学整数规划的解法：分枝定界法或割平面法 基本思想是把一个整数规划问题化为一系列的线性规划问题来求解整数规划的分类： 纯整数规划：所有变量都限制为整数 混合整数规划：仅部分变量限制为整数 0-