运筹学线性规划问题及其数学模型资料.pptx
参考资料1.钱颂迪，运筹学（第四版），清华大学2.胡运权，运筹学教程（第三版），清华大学；3.胡运权，运筹学习题集（第三版），清华大学；4.刘建永，运筹学算法与编程实践，清华大学1第1页/共29页运筹学简介运筹学属于应用数学专业，是管理科学工程的理论基础，是分析解决管理科学领域中最优化问题的方法论。运筹学根据管理问题的环境条件和决策要求，建立相应的数学模型，利用数学模型对实际问题进行分析和求解，经过分析和比较，得到适合实际问题的方案。2求解求解结果结果.求解求解结果结果.建立模型求解模型修改模型求解求解结果结果.修改模型实际实际问题问题数学数学模型模型第2页/共29页运筹学简介运筹学的工作步骤：运筹学的工作步骤：提出和形成问题建立模型求解解的检验解的控制解的实施3第3页/共29页运筹学简介模型的一般数学形式：目标的评价准则 约束条件 可控变量已知参数随机因素4第4页/共29页中国运筹学会1991年成立，挂靠中国科学院数学与系统科学研究院；运筹学与控制论专业（数学一级学科）20世纪50年代，钱学森、许国志等将运筹学引入中国，华罗庚推广统筹法和优选法管理科学与工程（管理科学与工程一级学科）管理运筹学5第5页/共29页运筹学 operational research（operations research，O.R）运筹学是在第二次世界大战中诞生和发展起来的。由于战争的需要，英国和美国招募了一批年轻的科学家和工程师，在军队将军的领导下研究战争中的问题，例如大规模轰炸的效果、搜索和攻击敌军潜水艇的策略、兵力和军需物质的调运等等。这些研究在战争中取得了很好的效果。6第6页/共29页战后这些理论和方法被应用到经济计划，生产管理领域，也产生了很好的效果。我国把O.R译成“运筹学”，非常贴切地涵盖了这个词作战研究和作业研究两方面的涵义。运筹学的内容十分广泛，包括线性规划、非线性规划、动态规划、图论与网络分析、存储论、排队论、对策论、决策论等。在本课程中，结合专业学科的特点，主要介绍线性规划及其对偶问题，运输问题、动态规划、图与网络分析。7第7页/共29页8授课主要内容目录：p第一章线性规划p第二章运输问题p第三章动态规划p第四章 图与网络分析第8页/共29页9第一章第一章 线性规划线性规划Linear programming是研究一组线性不等式或等式约束下，使得某一线性目标函数取最大（或最小）的极值问题。第9页/共29页101.1线性规划问题及其数学模型1.生产计划问题2.配料问题3.背包问题4.运输问题5.指派问题6.下料问题第10页/共29页111.生产计划问题（Production Planning）产品甲产品甲产品乙产品乙产品丙产品丙产品丁产品丁设备能力设备能力（小时）（小时）设备设备A1.51.02.41.02000设备设备B1.05.01.03.58000设备设备C1.53.03.51.05000利润（元利润（元/件）件）5.247.308.344.18某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占有的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：求使得总利润最大的生产计划。第11页/共29页122.配料问题（Material Blending）某工厂要用四种合金T1、T2、T3、T4为原料，经熔炼成为新的不锈钢G。这四种原料含铬（Cr）、锰（Mn）和镍（Ni）的含量（），这四种原料的单价以及新的不锈钢G所要求的Cr、Mn、Ni的最低含量（）如下表：要求配100公斤不锈钢G，并假定在配制过程中没有损耗。求使得总成本最低的配料方案。T1T2T3T4GCr3.214.532.191.763.20Mn2.041.123.574.332.10Ni5.823.064.272.734.30单价（元单价（元/公斤）公斤）115978276第12页/共29页133.背包问题（Knapsack Problem）一只背包最大装载重量为50公斤。现有三种物品，每种物品数量无限。每种物品每件的重量、价格如下表：求背包中装入每种物品各多少件，使背包中物品总价值最高。物品物品1物品物品2物品物品3重量（公斤重量（公斤/件）件）104120价值（元价值（元/件）件）177235第13页/共29页144.运输问题（Transportation）某种物资从两个供应地A1，A2运往三个需求地B1，B2，B3。各供应地的供应量、各需求地的需求量、每个供应地到每个需求地每吨物资的运输价格如下表：求总运费最低的运输方案。运价（元/吨）B1B2B3供应量（吨）A123535A247825需求量（吨）10302060第14页/共29页15运量（吨）B1B2B3供应量（吨）A130535A2101525需求量（吨）10302060这个问题的最优解表示如下：最小总运费为：z=330+55+410+815=275元A1A2B3B2B135吨25吨10吨30吨20吨23547830吨5吨10吨15吨第15页/共29页16张、王、李、赵四位老师被分配教语文、数学、物理化学四门课程，每位老师教一门课，每门课由一位老师教。根据这四位老师以往教课的情况，他们分别教四这门课程的平均成绩如下表。要求确定哪一位老师上哪一门课，使四门课的平均总成绩最高。语文语文 数学数学 物理物理 化学化学张张92688576王王82917763李李83907465赵赵936183755.指派问题（Assignment Problem）语文语文数学数学物理物理化学化学张张0001王王0010李李0100赵赵1000第16页/共29页176.下料问题 现将1m长的钢切成A0.4m,B=0.3m，C=0.2m长的三种钢，其中A，B，C三种钢分别需要20根，45根和50根，问如何进行切割使得剩余的钢才为最少？解：将1m的钢分别切成A，B，C三种钢的可能方案如下：方案12345678A21110000B02103210C10130235剩料000.100.100.10第17页/共29页18小结小结上述问题的优化模型，都具有以下特征：（1）每个问题都用一组未知的变量x1,xn表示所求方案，通常这些变量都是非负的，称为决策变量；（2）存在一组约束条件，这些约束条件都可以用一组线性等式或不等式表示；（3）都有一个要求的目标，这个目标可以表示为一组决策变量的线性函数，称之为目标函数，目标函数可以求最大，也可以求最小；具有以上特征的数学模型，就称为线性规划模型第18页/共29页19线性规划模型标准形式min(max)z=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn (,)b1 a21x1+a22x2+a2nxn (,)b2 am1x1+am2x2+amnxn (,)bm x1,x2,xn 0(,Free)线性规划模型的目标函数必须是变量的线性函数，约束条件必须是变量的线性等式或不等式。1.1.一般形式非线性规划问题第19页/共29页20线性规划的标准形式-目标函数为极大化，-约束条件全部为等号约束-决策变量全部是非负maxZ=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1,x2,xn 0 线性规划模型称为标准形式第20页/共29页21线性规划模型用矩阵和向量表示max z=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1,x2,xn 0 价值系数工艺（技术）系数矩阵资源约束第21页/共29页22线性规划模型用矩阵和向量表示（续）因此，线性规划模型可以写成如下矩阵和向量的形式MaxZ =CXs.t.AX=b X0 第22页/共29页23线性规划问题的标准化极小化目标函数转化为极大化小于等于约束条件转化为等号约束大于等于约束条件转化为等号约束变量没有符号限制（Free）的标准化变量小于等于0的标准化第23页/共29页24min z=2x1-3x2+x3令 z=-z，z=-2x1+3x2-x3新的目标函数max z=-2x1+3x2-x3取得极大化的最优解时，这个最优解同时使原目标函数值取得最小化的最优解。但两个问题最优解的目标函数值相差一个负号。极小化目标函数问题转化为极大化目标函数极小化目标函数问题转化为极大化目标函数极小化目标函数问题转化为极大化目标函数极小化目标函数问题转化为极大化目标函数例如，对于以下两个线性规划问题Max z=2x1+3x2s.t.x1+x23 x21 (B)x1,x20Min z=-2x1-3x2s.t.x1+x23 x21 (A)x1,x20它们的最优解都是x1=2,x2=1，但(A)的最小化的目标函数值为min z=-7，(B)的最大化的目标函数值为max z=7第24页/共29页252x1+3x2-4x35-引进松弛变量松弛变量(Slack variable)x4=5-(2x1+3x2-4x3)0:2x1+3x2-4x3+x4=5-如果有一个以上小于等于约束，要引进不同的松弛变量：2x1+3x2-4x35 3x1-2x2+5x38 分别引进松弛变量x4，x50 2x1+3x2-4x3+x4 =5 3x1-2x2+5x3 +x5=8小于等于约束条件转化为等号约束小于等于约束条件转化为等号约束小于等于约束条件转化为等号约束小于等于约束条件转化为等号约束大于等于约束条件转化为等号约束大于等于约束条件转化为等号约束大于等于约束条件转化为等号约束大于等于约束条件转化为等号约束2x1+3x2-4x353x1-2x2+5x38-约束的左边分别减去剩余变量剩余变量x4，x50 2x1+3x2-4x3-x4 =5 3x1-2x2+5x3 -x5=8第25页/共29页26没有符号限制的变量，用两个非负变量之差两个非负变量之差表示。例：min z=x1+2x2-3x3s.t.2x1+3x2-4x35 3x1-2x2+5x38 x10,x2:free,x30将目标函数转化为极小化，在约束中引入松弛变量，不等式约束变为等式：max z=-x1-2x2+3x3s.t.2x1+3x2-4x3+x4 =5 3x1-2x2+5x3 -x5=8 x10,x2:free,x3,x4,x50变量没有符号限制变量没有符号限制变量没有符号限制变量没有符号限制(Free)(Free)的标准化的标准化的标准化的标准化第26页/共29页27然后，令x2=x2-x2”，其中x2,x2”0。代入模型，消去x2Max z=-x1-2(x2-x”2)+3x3s.t.2x1+3(x2-x”2)-4x3+x4 =5 3x1-2(x2-x”2)+5x3 -x5=8 x1,x2,x”2,x3,x4,x50整理，得到标准形式：Max z=-x1-2x2+x”2+3x3s.t.2x1+3x2-3x”2-4x3+x4 =5 3x1-2x2+2x”2+5x3 -x5=8 x1,x2,x”2,x3,x4,x50第27页/共29页28min z=x1+2x2-3x3s.t.2x1+3x2-4x35 3x1-2x2+5x38 x10,x20,x30max z=-x1-2x2+3x3s.t.2x1+3x2-4x3+x4 =5 3x1-2x2+5x3 -x5=8 x10,x20,x3,x4,x50令 x2=-x2，x20,代入模型max z=-x1+2x2+3x3s.t.2x1-3x2-4x3+x4 =5 3x1+2x2+5x3 -x5=8 x10,x20,x3,x4,x50变量小于等于变量小于等于变量小于等于变量小于等于0 0的的标准化的的标准化的的标准化的的标准化第28页/共29页29感谢您的观看！第29页/共29页
