天津大学管理运筹学课件第一章管理运筹学——线性规划.ppt

管理运筹学 Operational Research,天津大学管理学院 郭均鹏,教师简介：,郭均鹏：博士，副教授， 硕士生导师。 主要研究领域： 运筹决策技术； 信息管理与企业信息化； 绩效考核与薪酬体系设计 联系方式：天津大学管理学院，300072 ,授课内容：,线性规划 图论与网络分析 网络计划 风险型决策 排队论 博弈论,课程教材：,吴育华,杜纲. 管理科学基础，天津大学出版社。,绪 论,产生于二战时期，运筹学（Operational Research) 直译为“运作研究”。 60年代，在工业、农业、社会等各领域得到广泛应用 在我国，50年代中期由钱学森等引入,运用数学方法，为决策者进行最优决策提供科学依据的一门应用科学。,一、运筹学的产生与发展,二、学科性质,三、运筹学的分支,线性规划 非线性规划 图论与网络分析 存储论 决策论 排队论 对策论（博弈论）,四、管理运筹学的工作程序,明确问题,问题分类,建立数学模型,求解数学模型,结果分析,实施,注意计算机软件的应用 Lindo、WinQSB等,第一章 线性规划 （Linear Programming，简称LP）,1 线性规划的模型与图解法,一、LP问题及其数学模型,例1 某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源，有关单耗数据如表，试拟定使总收入最大的生产计划。,产品,资源,线性规划模型三要素： （1）决策变量 设甲产品生产x1，乙产品生产x2 （2）目标函数 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两种饲料中选择，试决定总花费最小的购买方案。（列出模型）,养分,饲料,课堂练习,某蓄场每日要为每头牲畜购买饲料，以使其获取所需的A、B、C、D四种养分。有关数据如下表，现饲料可从市场上出售的M、N两种饲料中选择，试决定总花费最小的购买方案。（列出模型）,养分,饲料,答案：设购买M饲料x1，N饲料x2,0.5 x1 +0.1x210 0.2x1 +0.3x2 5 0.3x1 +0.4x2 8 0.2x2 7 x1 , x20,s.t.,Min Z=300 x1 +200x2,二、线性规划的图解法,1. 步骤,（1）作约束的图形可行域,可行解的集合,先作非负约束 再作资源约束,9x1+4x2=360,4x1+5x2=200,3x1+10x2=300,（2）作目标函数的等值线,给z不同的值，作相应直线，判断出z增大时，直线的移动方向,将直线向增大方向移动，直至可行域边界，交点X*即为最优解。,7x1+12x2=84,7x1+12x2=168,如：令7 x1 +12x2=84 7 x1 +12x2=168,X*=（20，24）， Z*=428,最优解： x1 = 0， x2 = 1 最优目标值 z = 3,课堂练习 图解法求解线性规划,2. LP 解的几种情况,注：出现（3）、（4）情况时，建模有问题,图解法的结论：,线性规划的可行域是凸集,线性规划的最优解若存在，必在可行域的在极点获得 若在两个极点同时获得，则有无穷多最优解,极点,三、 线性规划应用举例与软件求解,例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 = 100 2x2 + x3 + 3x5 + 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=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 + + a1n 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有唯一解，,，,结论：基本解的个数,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. 最优性检验,把目标函数用非基变量表示：,检验数向量，记为。当 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,-0.2,84,0,0,1,-3.12,1.16,0,0,0,-1.36,-0.52,X*=(20,24,84,0,0)T Z*=428,例：,用单纯形法求解,X*=(6,0,8,0)T Z*= -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为充分大正数）。,于是原问题化为：,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型单纯形表与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、问题的提出,煤电油例,今有另厂要购买三种资源，在原厂可接受的条件下，单价多少可是另厂付费最低？,设煤电油价格分别为y1, y2, y3,Min W=360y1+200y2+300y3,s.t.,9y1+4y2+3y37,4y1+5y2+10y312,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）对偶最优解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）影子价格反映了资源的稀缺性， 影子价格越高，则越稀缺,例如：煤的影子价格为0，则表明有剩余,4 灵敏度分析,任务：当LP的系数A、b、c变化时，是否影响最优解或最优基？ 或：若不影响最优解或最优基， A、b、c的变化范围？,可行性：B-1b0,最优性：,一、b变,（只影响解的可行性）,问题：br在何范围变化时，不影响最优基？,例：煤电油例，讨论b2的变化,解得-5027或150b2227,问题： cj在何范围变化时，不影响最优基（解）？,方法：,（讨论检验数）,（1） cj为非基价格系数,，解出,（2） cj为基价格系数,此时需考虑所有非基变量的检验数：,解出,例：煤电油例，为使最优解不变，求c1的变化范围。,解：考虑所有非基检验数,同理，,令,基变量的检验数仍全为0，故无需考虑。,三、A 变,（1） 增加新变量xn+1,例如，煤电油例又增加产品丙或丁，相关数据如右表。,问题：增加后是否影响最优基（解），从而判断是否 有利？（使目标改善）,方法：是否有利取决于是否进基。,故只需计算,，则有利,，则不利,例:,丙不应投产。,同理可得,丁应投产。,（2） 某列Pj Pj（只考虑非基向量情形）,问题：改变后是否影响最优基（解）、有利？,方法：,只需计算,，则有利,，则不利,5 整数规划 Integer Programming(简称IP),一、 整数规划的一般模型,LP: max z=CX AX=b X0,IP: max z=CX AX=b X0 X为整数,整数规划的解法：分枝定界法或割平面法,基本思想是把一个整数规划问题化为一系列的线性规划问题来求解,整数规划的分类： 纯整数规划：所有变量都限制为整数 混合整数规划：仅部分变量限制为整数 0-1整数规划：变量的取值仅限于0或1,例 人力资源分配的问题 某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：,设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?,解：设 xi 表示第i班次时开始上班的司机和乘务人员数,于是LP模型为:,x1 + x6 60 x1 + x2 70 x2 + x3 60 x3 + x4 50 x4 + x5 20 x5 + x6 30 x1,x2,x3,x4,x5,x6 0且为整数,min z=x1 + x2 + x3 + x4 + x5 + x6,最优解：X* =(60 ，10，50 ，0 ，30 ，0）， Z*=150,二、 0-1整数规划,投资场所的选址问题 指派问题 背包问题 消防队问题,1. 投资场所的选址问题 某城市拟在东、西、南三区设立商业网点，备选位置有A1A7共7个，如果选Ai，估计投资为bi元，利润为ci元，要求总投资不超过B元，规定 东区：A1、A2、A3中至多选2个 西区：A4、A5中至少选一个 南区：A6、A7中至少选一个 问如何设点使总利润最大？,max z=,xi=0或 1，i=1, ,7,x1+x2+x32,x4+x51,x6+x71,s.t.,课堂练习1: 某钻井队要从S1S10共10个井位中确定五个钻井探油，如果选Si，估计钻探费用为ci元，并且井位选择上要满足下列条件： （1）或选择S1和S7，或选择S8 ;,（2）选择了S3或S4就不能选择S5，反 过来也一样; （3）在S5，S6 ，S7，S8中最多只能选两个。 问如何选择井位使总费用最小？,课堂练习1: 某钻井队要从S1S10共10个井位中确定五个钻井探油，如果选Si，估计钻探费用为ci元，并且井位选择上要满足下列条件： （1）或选择S1和S7，或选择S8 （2）选择了S3或S4就不能选择S5，反过来也一样 （3）在S5，S6 ，S7，S8中最多只能选两个 问如何选择井位使总费用最小？,min z=,s.t.,或 1，i=1, ,10,某篮球队有8名队员，其身高和专长如下表，现要选拔5名球员上场参赛，要求： （1）中锋只有1人上场 （2）后卫至少有一人上场 （3）只有2号上场，6号才上场 要求平均身高最高，应如何选拔队员？,课堂练习2:,max z=,或 1，i=1, ,8,s.t.,某篮球队有8名队员，其身高和专长如下表，现要选拔5名球员上场参赛，要求： （1）中锋只有1人上场 （2）后卫至少有一人上场 （3）只有2号上场，6号才上场 要求平均身高最高，应如何选拔队员？,2. 指派问题,例： 有一份中文说明书，需译成英、日、德、俄四种文字，分别记作任务E、J、G、R，现有甲、乙、丙、丁四人，他们将中文说明书翻译成不同语种说明书所需的时间如下表所示，问应指派何人去完成何项任务，使所需总时间最少？,问题描述：n项任务可由n个人完成，由于专长不同，各人完成各任务的时间也不同，求最优安排。 要求：每人只能完成一项任务，每项任务只能由一人完成。,x11+ x12+ x13+ x14= 1 (甲只能干一项工作) x21+ x22+ x23+ x24= 1 (乙只能干一项工作) x31+ x32+ x33+ x34= 1 (丙只能干一项工作) x41+ x42+ x43+ x44= 1 (丁只能干一项工作) x11+ x21+ x31+ x41= 1 ( E任务只能一人干) x12+ x22+ x32+ x42= 1 ( J任务只能一人干) x13+ x23+ x33+ x43= 1 ( G任务只能一人干) x14+ x24+ x34+ x44= 1 ( R任务只能一人干) xij = 0 或 1，i,j = 1,2,3,4,min z=2x11+15x12+13x13+4x14+10x21+4x22+14x23+15x24 +9x31+14x32+16x33+13x34+7x41 +8x42+11x43+9x44,课堂练习:P57例2.23,例：甲、乙、丙、丁是四名游泳运动员，他们各种姿势的100m游泳成绩如表。为组成一个4100m混合泳接力队，怎样选派运动员，方使接力队的游泳成绩最好？,3. 背包问题,问题描述,已知：一个背包最大容量为b公斤；有m件物品供选择，每件物品重ai公斤，价值为ci（i=1,m）。,问题：携带哪些物品可使总价值最大？,一般模型,s.t.,1， 物品i被选中 0，物品i没被选中,xi=,例：一个徒步旅行者要在背包中选择一些最有价值的物品携带。他最多能带115kg的物品，现有5件物品，分别重54、35、57、46、19kg，其价值依次为7、5、9、6、3。问携带哪些物品可使总价值最大？,解：,模型为：,s.t.,4. 消防队问题,某城市的消防总部将全市划分为11个防火区，设有4个消防救火站。下图表示消防站，111表示防火区域，图中连线表示各地区由哪个消防站负责。问题：可否减少消防站的数目，仍能同样负责各地区的防火任务？如果可以，应关闭哪个消防站？,则模型为,课堂练习: 某市为方便学生上学，拟在新建的居民小区增设若干所小学。已知备选校址代号及其能覆盖的居民小区编号如表所示，问为覆盖所有小区至少应建多少所小学？,备选校址代号,覆盖的居民小区编号,ABCDEF,1、5、7,1、2、5,1、3、5,2、4、5,3、6,4、6,6 运输问题,一、运输问题的提出 生产某种产品，