管理学管理运筹学线性规划.ppt

运筹学OperationalResearch,天津大学管理学院郭均鹏,教师简介：,郭均鹏：博士，副教授，硕士生导师。主要研究领域：运筹决策技术；信息管理与企业信息化；绩效考核与薪酬体系设计联系方式：天津大学管理学院，30007213602053107；guojp,课程教材：,吴育华,杜纲.管理科学基础，天津大学出版社。,绪论,运筹学（OperationalResearch)直译为“运作研究”。产生于二战时期60年代，在工业、农业、社会等各领域得到广泛应用在我国，50年代中期由钱学森等引入,运用数学方法，为决策者进行最优决策提供科学依据的一门应用科学。,一、运筹学的产生与发展,二、运筹学的性质,三、运筹学的分支,线性规划非线性规划图论与网络分析存储论决策论动态规划排队论,四、运筹学在管理中的应用,生产计划：生产作业的计划、日程表的编排、合理下料等，追求利润最大化和成本最小化库存管理运输问题：确定最小成本的运输线路、物资的调拨以及建厂地址的选择等人力资源管理：对人员的需求和使用的预测，确定人员编制、人员合理分配，建立人才评价体系等工程网络计划：确定工期、关键工序等,明确问题,问题分类,建立数学模型,求解数学模型,结果分析,实施,五、运用运筹学方法解决实际问题的工作流程,注意计算机软件的应用Lindo、Exel等,第一章线性规划（LinearProgramming，简称LP）,1线性规划的模型与图解法2线性规划的举例与软件求解3整数规划4运输问题,第一章线性规划（LinearProgramming，简称LP）,1线性规划的模型与图解法,一、LP问题及其数学模型二、线性规划的标准型三、线性规划的图解法,一、LP问题及其数学模型,例1某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源，有关单耗数据如表，试拟定使总收入最大的生产计划。,产品,资源,线性规划模型三要素：（1）决策变量设甲产品生产x1，乙产品生产x2（2）目标函数MaxZ=7x1+12x2（3）约束条件,9x1+4x23604x1+5x22003x1+10 x2300 x1,x20,s.t.,返回,SubjectTo，意为“使其满足”,目标函数：Max（Min）Z=c1x1+c2x2+cnxn,a11x1+a12x2+a1nxn（=,）b1a21x1+a22x2+a2nxn（=,）b2am1x1+am2x2+amnxn（=,）bmx1，x2，xn0,约束条件：,s.t.,LP模型的一般形式,课堂练习,某蓄场每日要为每头牲畜购买饲料，以使其获取所需的A、B、C、D四种养分。有关数据如下表，现饲料可从市场上出售的M、N两种饲料中选择，试决定总花费最小的购买方案。（列出模型）,养分,饲料,课堂练习,某蓄场每日要为每头牲畜购买饲料，以使其获取所需的A、B、C、D四种养分。有关数据如下表，现饲料可从市场上出售的M、N两种饲料中选择，试决定总花费最小的购买方案。（列出模型）,养分,饲料,答案：设购买M饲料x1，N饲料x2,0.5x1+0.1x2100.2x1+0.3x250.3x1+0.4x280.2x27x1,x20,s.t.,MinZ=300 x1+200 x2,二、线性规划的标准型,MaxZ=c1x1+c2x2+cnxn,a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2am1x1+am2x2+amnxn=bmx1，x2，xn0,s.t.,1、标准形式,矩阵表示,MaxZ=CX,AX=bX0,s.t.,其中：C=(c1,c2,cn)称为价格系数A=(aij)mn称为技术系数b=(b1,b2,bm)称为资源系数,（1）MinZ=CX,MaxZ=-CX,（2）约束条件,例如：9x1+4x2360,9x1+4x2+x3=360,松弛变量,“”型约束，加松弛变量；,“”型约束，减松弛变量；,例、将如下问题化为标准型,三、线性规划的图解法,1.步骤,（1）作约束的图形可行域,可行解的集合,先作非负约束再作资源约束,9x1+4x2=360,4x1+5x2=200,3x1+10 x2=300,（2）作目标函数的等值线,给z不同的值，作相应直线，判断出z增大时，直线的移动方向,将直线向增大方向移动，直至可行域边界，交点X*即为最优解。,7x1+12x2=84,7x1+12x2=168,如：令7x1+12x2=847x1+12x2=168,X*=（20，24），Z*=428,最优解：x1=0，x2=1最优目标值z=6,课堂练习图解法求解线性规划,2.LP解的几种情况,注：出现（3）、（4）情况时，建模有问题,图解法的结论：,线性规划的可行域是凸集,线性规划的最优解若存在，必在可行域的在极点获得若在两个极点同时获得，则有无穷多最优解,极点,2线性规划应用举例与软件求解,例1（下料问题）某工厂要做100套钢架，每套用长为2.9m,2.1m,1.5m的圆钢各一根。已知原料每根长7.4m，问：应如何下料，可使所用原料最省？,例1（下料问题）某工厂要做100套钢架，每套用长为2.9m,2.1m,1.5m的圆钢各一根。已知原料每根长7.4m，问：应如何下料，可使所用原料最省？,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+x7=100 x1+x3+3x4+2x6+3x7+4x8=100 x1,x2,x3,x4,x5,x6,x7,x80,设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,minZ=x1+x2+x3+x4+x5+x6+x7+x8,s.t.,线性规划求解软件lindo,3整数规划IntegerProgramming(简称IP),一、整数规划的一般模型,LP:maxz=CXAX=bX0,IP:maxz=CXAX=bX0X为整数,整数规划的解法：分枝定界法或割平面法,基本思想是把一个整数规划问题化为一系列的线性规划问题来求解,整数规划的分类：纯整数规划：所有变量都限制为整数混合整数规划：仅部分变量限制为整数0-1整数规划：变量的取值仅限于0或1,例人力资源分配的问题某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：,设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?,解：设xi表示第i班次时开始上班的司机和乘务人员数,于是LP模型为:,x1+x660 x1+x270 x2+x360 x3+x450 x4+x520 x5+x630 x1,x2,x3,x4,x5,x60且为整数,minz=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中至少选一个问如何设点使总利润最大？,maxz=,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中最多只能选两个问如何选择井位使总费用最小？,minz=,s.t.,或1，i=1,10,某篮球队有8名队员，其身高和专长如下表，现要选拔5名球员上场参赛，要求：（1）中锋只有1人上场（2）后卫至少有一人上场（3）只有2号上场，6号才上场要求平均身高最高，应如何选拔队员？,课堂练习2:,maxz=,或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,minz=2x11+15x12+13x13+4x14+10 x21+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,4运输问题,一、运输问题的提出生产某种产品，m个产地：A1,，Am,产量：a1,，amn个销地：B1,，Bn,销量：b1,，bn已知：Ai至Bj的运输单价为cij问题：确定Ai运往Bj的数量xij，使总运费最低？,二、运输问题的表示网络图运输表线性规划模型,A2,A3,B2,A1,B3,B4,B1,运输问题网络图,a2=4,a3=9,b1=3,b2=6,b3=5,b4=6,a1=7,供应量,供应地,运价,需求量,需求地,3,11,3,10,1,9,2,8,7,4,10,5,运输问题的表格表示,运输问题线性规划模型,三、运输问题的分类,产销平衡问题：ai=bj产销不平衡问题：,供大于求：aibj,供不应求：aibj,四、运输问题的求解表上作业法,确定初始可行调运方案最小元素法判别当前可行方案是否最优闭回路法对现有方案进行调整闭回路法,用最小元素法确定初始可行调运方案最小元素法的基本思想：就近尽量满足供应,3,1,3,4,6,3,0,1,0,4,0,3,0,3,0,3,0,0,例：最小元素法求解下面运输问题的初始解,用闭回路法进行最优性检验1、找空格的闭回路：以某空格为起点，用水平线或垂直线向前划，只能在碰到某一数字格时才能转弯，按照这一规则继续前进，直到回到起始的空格为止。,2、根据闭回路计算空格的检验数：检验数=奇数顶点的单位运价之和偶数顶点的单位运价之和,1,2,1,-1,10,12,检验数的经济含义：当由产地Ai往销地Bj增运一个单位货物时所引起的总运输成本的变化数,结论：若所有检验数都大于等于0，则当前方案最优,对现有方案进行调整在负的检验数中选择绝对值最大的空格，在方案表中从该空格出发，沿着其闭回路依次标上“+q”、“-