《天津大学管理运筹学课件第一章_管理运筹学——线性规划》由会员分享，可在线阅读，更多相关《天津大学管理运筹学课件第一章_管理运筹学——线性规划（92页珍藏版）》请在金锄头文库上搜索。
1、管理运筹学 Operational Research,天津大学管理学院 郭均鹏,教师简介：,郭均鹏：博士，副教授，硕士生导师。 主要研究领域： 运筹决策技术；信息管理与企业信息化；绩效考核与薪酬体系设计联系方式：天津大学管理学院，,授课内容：,线性规划图论与网络分析网络计划风险型决策 排队论博弈论,课程教材：,吴育华,杜纲. 管理科学基础，天津大学出版社。,绪 论,产生于二战时期，运筹学（Operational Research) 直译为“运作研究”。60年代，在工业、农业、社会等各领域得到广泛应用在我国，50年代中期由钱学森等引入,运用数学方法，为决策者进行最优决策提供科学依据的一门应用科学
2、。,一、运筹学的产生与发展,二、学科性质,三、运筹学的分支,线性规划 非线性规划 图论与网络分析 存储论 决策论 排队论 对策论（博弈论）,四、管理运筹学的工作程序,明确问题,问题分类,建立数学模型,求解数学模型,结果分析,实施,注意计算机软件的应用 Lindo、WinQSB等,第一章 线性规划 （Linear Programming，简称LP）,1 线性规划的模型与图解法,一、LP问题及其数学模型,例1 某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源，有关单耗数据如表，试拟定使总收入最大的生产计划。,产品,资源,线性规划模型三要素： （1）决策变量设甲产品生产x1，乙产品生产x2 （2
3、）目标函数Max Z=7 x1 +12x2 （3）约束条件,9 x1 +4x2360 4x1 +5x2 200 3 x1 +10x2 300 x1 , x20,s.t.,返回,Subject To， 意为“使其满足”,LP模型的一般形式,其中: X= (x1,x2, , xn) T 为决策变量 C=(c1,c2, , cn) 称为价格系数 A=(aij)mn 称为技术系数 b= (b1,b2, , bm) T 称为资源系数,课堂练习,某蓄场每日要为每头牲畜购买饲料，以使其获取所需的A、B、C、D四种养分。有关数据如下表，现饲料可从市场上出售的M、N两种饲料中选择，试决定总花费最小的购买方案。（
4、列出模型）,养分,饲料,课堂练习,某蓄场每日要为每头牲畜购买饲料，以使其获取所需的A、B、C、D四种养分。有关数据如下表，现饲料可从市场上出售的M、N两种饲料中选择，试决定总花费最小的购买方案。（列出模型）,养分,饲料,答案：设购买M饲料x1，N饲料x2,0.5 x1 +0.1x210 0.2x1 +0.3x2 5 0.3x1 +0.4x2 80.2x2 7 x1 , x20,s.t.,Min Z=300 x1 +200x2,二、线性规划的图解法,1. 步骤,（1）作约束的图形可行域,可行解的集合,先作非负约束 再作资源约束,9x1+4x2=360,4x1+5x2=200,3x1+10x2=3
5、00,（2）作目标函数的等值线,给z不同的值，作相应直线，判断出z增大时，直线的移动方向,将直线向增大方向移动，直至可行域边界，交点X*即为最优解。,7x1+12x2=84,7x1+12x2=168,如：令7 x1 +12x2=847 x1 +12x2=168,X*=（20，24）， Z*=428,最优解： x1 = 0， x2 = 1 最优目标值 z = 3,课堂练习 图解法求解线性规划,2. LP 解的几种情况,注：出现（3）、（4）情况时，建模有问题,图解法的结论：,线性规划的可行域是凸集,线性规划的最优解若存在，必在可行域的在极点获得若在两个极点同时获得，则有无穷多最优解,极点,三、
6、线性规划应用举例与软件求解,例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，问：应如何下料，可使所用原料最省？,2,0,1,0.1,1,2,0,0.3,1,1,1,0.9,1,0,3,0,0,3,0,1.1,0,2,2,0.2,0,1,3,0.8,0,0,4,1.4,2x1 + x2 + x3 + x4 = 1002x2 + x3 + 3x5 + 2x6
7、 + x7 = 100x1 + x3+ 3x4 + 2x6 + 3x7 + 4x8 = 100x1, 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=0,min Z =x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8,s.t.,一、线性规划的标准型,Max Z = c1 x1 + c2 x2 + + cn xn,a11 x1 + a12 x2 + + a1
8、n xn =b1 am1 x1 + am2 x2 + + amn xn =bm x1 ，x2 ， ，xn 0,s.t.,1、标准形式,注：标准型中要求bi 0,2 单纯形法,（1）Min Z = CX,Max Z = -CX,（2）约束条件,例如： 9 x1 +4x2360,9 x1 +4x2+ x3=360,松弛变量,“”型约束，加松弛变量；,“”型约束，减松弛变量；,（3）自由变量xj,进行变量替换： xj= xj - xj ，其中xj 、 xj 0,二、LP解的基本概念,考虑标准型：,1. 可行解,满足（1）、（2）的解,2. 基本解,设r(A)=m，,则BX=b有唯一解，,，,结论：基
9、本解的个数,3. 基可行解,若基解X0，则称为基可行解。,结论：LP的基可行解对应于可行域的顶点。,基：A中m阶可逆子阵，记为B。,基向量：B中的列。,基变量：和基向量相对应的决策变量。,其余部分称为非基子阵，记为N。,例、研究约束集合,基本解的个数,令x2=x3=0，得基本解,X1=(1/2, 0, 0)T,对应于A点；,例、研究约束集合,基本解的个数,三、单纯形法的基本方法,基本方法：,确定初始基可行解,检验是否最优？,转到另一更好的 基可行解,停,Y,N,方法前提：模型化为标准型,1. 初始可行基B0的确定,若A中含有I：B0=I 若A中不含I：人工变量法,2. 最优性检验,把目标函数用
10、非基变量表示：,检验数向量，记为。当 0时，当前解为最优解。,方法：,（1）计算每个xj的检验数,（2）若所有j 0 ，则当前解为最优；,否则，至少有k 0 ，转3。,3. 换基迭代（基变换）,得新基，转2。,的计算:,四、单纯形法的实现单纯形表,12,0,0,0,单纯形表:,7,90,的计算:,40,30, ,枢纽元素,x3,x4,x2,30,0.3,1,0,0,0.1,50,2.5,0,0,1,-0.5,240,7.8,0,1,0,-0.4,3.4,0,0,0,-1.2,即:,即:,30.8,20,100,x3,x1,x2,24,0,1,0,-0.12,0.16,20,1,0,0,0.4,
11、-0.2,84,0,0,1,-3.12,1.16,0,0,0,-1.36,-0.52,X*=(20,24,84,0,0)TZ*=428,例：,用单纯形法求解,X*=(6,0,8,0)TZ*= -6,注：单纯形表中的信息 每一列的含义： B-1(b A)=(B-1b, B-1 P1,， B-1 Pn) 每个表中的B和B-1的查找：B从初表中找；B-1从当前表中找，对应于初表中的I的位置。,以第2个表为例：,终表分析最优基B* 和(B*)-1的查找,五、人工变量法（大M法）,1 问题:,增加人工变量 X人=（xn+1，xn+m）T， X人在目标函数中的系数为 -M（M为充分大正数）。,于是原问题化
12、为：,2 方法:,单纯形法求解() ,若,最优基变量中不含X人，则所得解的前n个分量即为X*,否则， ()无解。,3 结论:,例：用单纯形法求解,解：增加人工变量x5、x6，则模型化为：,Max Z = 5x1+3x2+2x3+4x4-Mx5-Mx6,5x1+ x2+ x3+8x4+x5 =10 2x1+4x2+3x3+2x4 +x6=10 x1,x6 0,s.t.,x5,x6,-M,-M,10,10,5/4,5,x4,x6,4,-M,10,2,x4,x2,4,3,5/3,10,x1,x2,5,3,X*=(5/3, 5/3, 0, 0)T, Z*=40/3,六、单纯形法总结,1、Min型单纯形
13、表与Max型的区别仅在于：令 k=minj 0的xk进基，当 0时最优。,2、解的几种情况及其在单纯形表上的体现（讨论Max型）,唯一 最优解,j 0, 非基0 但B-1Pk 0,无可行解,用大M法求解，最优基中含有X人,退化解,最优解中某基变量为0,3 线性规划的对偶问题 （Dual Programming，简称DP）,一、对偶问题的提出和模型,1、问题的提出,煤电油例,今有另厂要购买三种资源，在原厂可接受的条件下，单价多少可是另厂付费最低？,设煤电油价格分别为y1, y2, y3,Min W=360y1+200y2+300y3,s.t.,9y1+4y2+3y37,4y1+5y2+10y31
14、2,y1, y2, y3 0,DUAL,2、模型,原问题（P）：,对偶问题（D）：,Min W = bTY,ATY CT Y 0,s.t.,特点：,（1）P为max型，D为min型,（2）P的变量个数=D的约束个数,（3）P的约束个数=D的变量个数,1、对称性,（P）与（D）互为对偶,二、对偶性质与定理,2、弱对偶性,设X、Y 分别为（P）、（D）的任一可行解，则,3、解的最优性,设 、 分别为（P）与（D）的可行解，且,则,4、无界性,若（P）为无界解，则（D）无可行解,若（D）为无界解，则（P）无可行解,5、对偶定理,若（P）有最优解，则（D）也有最优解，且二者最优值相等.,小结：,（1）
15、对偶最优解Y*= CB B-1，其中B为原问题的最优基； （2）如何从（P）的终表中确定Y* ?,Y*即为（P）终表的XS的检验数的负值；若无XS，则用Y*= CB* (B*)-1计算。,6、检验数,（初表）,（终表）,由终表：Y*=(0 ,1.36 , 0.52)T,三、对偶问题最优解的经济解释影子价格,Y*=(y1* , y2* ,， ym* ）为DP的最优解，则yi* 表示 LP某资源bi 变化1个单位对目标 产生的影响，称 yi* 为 bi的影子价格。,例、煤电油例的对偶问题的最优解为Y* =(0 1.36 0.52),则煤电油三种资源的影子价格分别为0 、 1.36 、 0.52,影子价格在管理决策中的作用： （1）影子价格市场价格,若,影子价格市场价格，则应,影子价格市场价格，则应,买进该资源,卖出该资源,（2）影子价格反映了资源的稀缺性，影子价格越高，则越稀缺,
