《绪论线性规划》PPT课件.ppt

运筹学Operational Research,天津大学管理学院 郭均鹏天津大学仁爱学院 范贻昌,举例,例（线材合理下料问题）某工厂要做100套钢架，每套用长为2.9 m,2.1 m,1.5 m的圆钢各一根。已知原料每根长7.4 m，问：应如何下料，可使所用原料最省？例（机器负荷分配问题）某种机器可以在高、低两种负荷下进行生产。高负荷年产量8，年完好率0.7；低负荷年产量5，年完好率0.9。现有完好机器1000台，需制定一个5年计划，以决定每年安排多少台机器投入高、低负荷生产，使5年的总产量最大。,消防站选址问题,某城市的消防总部将全市划分为11个防火区，设有4个消防救火站。下图表示消防站，111表示防火区域，图中连线表示各地区由哪个消防站负责。问题：可否减少消防站的数目，仍能同样负责各地区的防火任务？如果可以，应关闭哪个消防站？,绪 论,产生于二战时期，运筹学（Operational Research)直译为“运作研究”。20世纪60年代，在工业、农业、社会等各领域得到广泛应用 在我国，20世纪50年代中期由钱学森等引入,运用数学方法，为决策者进行最优决策提供科学依据的一门应用科学。运筹学的特点面向管理和工程实际问题应用数学方法建立数学模型一定意义下的优化,一、运筹学的产生与发展,二、学科性质,三、运筹学的分支,线性规划（在有限的资源条件下通过合理计划实现总效益最大化）非线性规划图论与网络分析（对网络问题分析，使网络效益最大）存储论（研究库存与订货策略）决策论（不确定条件下进行比较）排队论（提高服务系统效率）对策论（对抗与竞争条件下决策问题）,四、管理运筹学的工作程序,明确问题,问题分类,建立数学模型,求解数学模型,结果分析,实施,五 运筹学与决策管理就是决策 从这个意义上说，运筹学是典型的辅助决策的学科 决策的基本问题是发现问题和解决问题发现问题需要决策者丰富的经验、广博的知识和敏锐的观察判断能力以及深入细致的调查研究。运筹学可提供某些辅助分析，但主要不针对此问题。解决问题首先要提出方案，方案的创造同样是决策者才干的体现。在解决问题中有两类问题是值得注意的：有些问题的解决方案在既定的准则下隐含在一系列限制条件中，需要一些方法“找出”这个方案；有些问题可能提出几个（有限个）方案，需要一些方法评价和优选这些方案；运筹学在以上两类问题中是很有用的。,课程教材：,吴育华,杜纲，管理科学基础（修订版），天津大学出版社。,主要参考书：1钱颂迪等，运筹学，北京：清华大学出版社，1990；2胡运权，运筹学教程，北京：清华大学出版社，1998；3（加）Peter C Bell,韩伯棠等译，管理科学（运筹学）战略角度的审视，机械工业出版社，2000；4丁以中主编，管理科学-运用Spreadsheet建模和求解，北京：清华大学出版社，2003；5 美弗雷德里克S希利尔（Frederick S Hillier）,任建标译,数据、模型与决策（原书名 Introduction to Management Science），北京：中国财政经济出版社，2004；,主要授课内容：,线性规划 图论与网络分析 网络计划 风险型决策动态规划矩阵对策,课程基本要求：掌握好基本概念、主要模型形式及其特点、必要的算法原理及简单的计算。,所需基础知识：微积分、矩阵、线性方程组、概率基础等,班级公共邮箱,密码：6个6,第一章 线性规划（Linear Programming，简称LP）,1 线性规划的模型与图解法,一、LP问题及其数学模型,例1 某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源，有关单耗数据如表，试拟定使总收入最大的生产计划。,结构约束条件,非负约束条件,目标函数,资源向量（右端项）,LP模型的一般形式,课堂练习,某蓄场每日要为每头牲畜购买饲料，以使其获取所需的A、B、C、D四种养分。有关数据如下表，现饲料可从市场上出售的M、N两种饲料中选择，试决定总花费最小的购买方案。（列出模型）,养分,饲料,课堂练习,某蓄场每日要为每头牲畜购买饲料，以使其获取所需的A、B、C、D四种养分。有关数据如下表，现饲料可从市场上出售的M、N两种饲料中选择，试决定总花费最小的购买方案。（列出模型）,养分,饲料,答案：设购买M饲料x1，N饲料x2,0.5 x1+0.1x2100.2x1+0.3x2 50.3x1+0.4x2 8 0.2x2 7x1,x20,s.t.,Min Z=300 x1+200 x2,二、线性规划的图解法,1.步骤,（1）作约束的图形可行域,可行解的集合,先作非负约束再作资源约束,9x1+4x2=360,4x1+5x2=200,3x1+10 x2=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=6,练习（自学）图解法求解线性规划,2.LP 解的几种情况,注：出现（3）、（4）情况时，建模有问题,图解法的结论：,线性规划的可行域是凸集,线性规划的最优解若存在，必在可行域的在极点获得 若在两个极点同时获得，则有无穷多最优解,三 线性规划应用举例,例1（线材合理下料问题）某工厂要做100套钢架，每套用长为2.9 m,2.1 m,1.5 m的圆钢各一根。已知原料每根长7.4 m，问：应如何下料，可使所用原料最省？,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.,解：共有下列 8 种下料方案,一、线性规划的标准型,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,（4）若右端项为负数，则先在不等式或等式两端同乘以-1。,例、将如下问题化为标准型,得标准型：,二、单纯形法的基本方法,基本方法：,确定初始基可行解,检验是否最优？,转到另一更好的基可行解,停,方法前提：模型化为标准型,并保证其他的基变量非负,基变量和非基变量,三、单纯形法的步骤,1.初始可行基B0的确定,若A中含有I：B0=I若A中不含I：人工变量法,2.最优性检验,（1）计算每个xj的检验数,（2）若所有j 0，则当前解为最优；,否则，至少有k 0，转3。,注:（1）基变量的检验数必为0；（2）非基变量的经济含义：非基变量取值由0变正，每增加一个单位，使目标值的增加量。,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,9x1+4x2=360,4x1+5x2=200,3x1+10 x2=300,(0,0),(40,0),(36.5,10.8),(20,24),(0,30),课堂练习,用单纯形法求解,X*=(6,0,8,0)T Z*=-6,联系用矩阵表示的单纯形法原理，单纯形表各部分内容可如下表示,3 线性规划的对偶问题（Dual Programming）,一、对偶问题的提出和模型,1、问题的提出,煤电油例,今有另厂要购买三种资源，在原厂可接受的条件下，单价多少可使另厂付费最低？,设煤电油“价格”分别为y1,y2,y3,DUAL,以后将特别讨论这一“价格”的含义,2、原问题与对偶问题的对应关系,原问题（P）：,对偶问题（D）：,（Y为行向量）,对称的对偶问题原问题与对偶问题形式上的对应关系原问题（P）对偶问题（D）目标max型 目标min型 有n个变量（非负）有n个约束（大于等于）有m个约束（小于等于）有m个变量（非负）价格系数 资源向量 资源向量 价格系数技术系数矩阵 技术系数矩阵的转置,1、对称性,二、对偶性质与定理,2、弱对偶性,设X、Y 分别为（P）、（D）的任一可行解，则,一个线性规划的对偶问题的对偶问题恰是原问题；即（P）与（D）互为对偶,3、无界性,若原问题（P）无上界，则对偶问题（D）无可行解；同样，若对偶问题（D）无下界，则原问题（P）无可行解；（注意：该命题的逆命题不成立。）,4、解的最优性,5、对偶定理（强对偶性）,若（P）有最优解，则（D）也有最优解，且二者最优值相等.,由该性质的证明中可以得到一个有用的结论：若原问题（P）有最优解，设最优基为B，则CBB-1是对偶问题（D）的最优解。,6、互补松弛定理,若 是原问题（P）的可行解，是对偶问题（D）的可行解，那么 和 分别是原问题（P）和对偶问题（D）的最优解的充要条件是：,对于性质5，进一步联系单纯型表的矩阵表示，,三、对偶问题最优解的经济解释影子价格,Y*=(y1*,y2*,，ym*）为对偶问题的最优解，则yi*表示在原问题LP模型最有解基础上，资源（右端项）bi 对目标函数的边际贡献。即bi变化1个单位对目标函数产生的影响，称 yi*为 bi的影子价格（shadow price)。,例如：煤电油例的对偶问题的最优解为Y*=(0 1.36 0.52),即煤电油三种资源的影子价格分别为0、1.36、0.52，它表明：在所求出的最优生产方案（甲生产20，乙生产24，资源煤剩余84，资源电和油无剩余，总收入428）基础上，资源煤增加1单位，目标函数值不变；资源电增加1单位，目标函数值相应增加1.36；资源油增加1单位，目标函数值相应增加0.52。,由原问题所做推导：,注意：对偶解（影子价格）的所有应用都是基于这一基本概念。,影子价格在管理决策中的作用：（1）影子价格市场价格在以本章引例为代表的目标函数最大化毛收入这类模型中,（2）影子价格反映了当前优化模型中资源的稀缺性，影子价格越高，则越稀缺。,例如：煤的影子价格为0，则表明有剩余；电的影子价格为1.36，是三种资源中最大的，则表明电是相对重要的。,（3）在资源不变条件下，增加新产品是否合算的评价（见灵敏性分析）,4 线性规划的灵敏性分析（sensitivity analysis）,1右端项b变化的分析（先看后两页图示）对于线性规划 在其最优解基础上，设B为最优基，则 由单纯形法,b的变化直接影响右端项（可行性）而不直接影响检验数（最优性）,右端项变化示意1，某个右端项在一定范围变化，可能不影响最优解,右端项变化示意2，某个右端项在一定范围变化，影响最优解,但可能不影响最优基。,2价格系数C变化的分析,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）T，Z*=150,二、0-1整数规划,选址问题 指派问题 固定费用问题 背包问题,1.投资场所的选址问题 某城市拟在东、西、南三区设立商业网点，备选位置有A1A7共7个，如果选Ai，估计投资为bi元，利润为ci元，要求总投资不超过B元，规定 东区：A!、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+10 x21+4x22+14x23+15x24+9x31+14x32+16x33+13x34+7x41+8x42+11x43+9x44,课堂练习:P57例2.23,指派问题可以一般化表述为有n个人n项工作，已知第i个人做第j项工作的费用为cij，现如何分派任务，使一个人只做一项工作，一项工作只由一个人完成，而且总费用最小。以4个人4项工作的指派问题为例，该问题需用4416个01变量，即设,把这些变量和已知费用系数分别排成一44矩阵，分别称为解矩阵和费用矩阵，,3.固定费用问题,最基本的带有固定费用的费用函数一般表示为：,若引入01变量,则带有固定费用的费用函数可表示为：,固体废物处理规划例（教材P52例2.20）示意图：,固定费用问题另例,例、生产三种型号的防寒服，其消耗资源及单件成本如表。此外，每种防寒服不管生产多少，都要支付一定的固定费用。,今要生产500件防寒服，确定总费用最低的生产方式。,一般描述：,已知：生产某产品有m种方式，设第j 种生产方式的固定成本为kj，可变成本为cj。问题：应选择哪几种生产方式、分别生产多少产量可使总成本最低？,分析：这是一个混合0-1规划问题：,设第j 种生产方式的产量为xj,于是该问题可表示为：,xj M yj,例、生产三种型号的防寒服，其消耗资源及单件成本如表。此外，每种防寒服不管生产多少，都要支付一定的固定费用。,今要生产500件防寒服，确定总费用最低的生产方式。,Min Z=13x1+12x2+10 x3+120y1+150y2+180y3,x1+x2+x3=5001.5x1+1.7x2+1.8x315001.3x1+1.5x2+1.6x31000 4x1+4.5x2+5x335002.8x1+3.8x2+4.2x32800 xiMyi(i=1,2,3)；xi0;yi=0或1,4.背包问题,问题描述,已知：一个背包最大容量为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.,5.消防队问题,某城市的消防总部将全市划分为11个防火区，设有4个消防救火站。下图表示消防站，111表示防火区域，图中连线表示各地区由哪个消防站负责。问题：可否减少消防站的数目，仍能同样负责各地区的防火任务？如果可以，应关闭哪个消防站？,则模型为,课堂练习:某市为方便学生上学，拟在新建的居民小区增设若干所小学。已知备选校址代号及其能覆盖的居民小区编号如表所示，问为覆盖所有小区至少应建多少所小学？,备选校址代号,覆盖的居民小区编号,ABCDEF,1、5、7,1、2、5,1、3、5,2、4、5,3、6,4、6,作业,2.1（1）2.22.52.6（2）2.72.82.92.14,