MBA学位课程-运筹学(一)mqh.pptx

运筹学(OperationResearch)MBA学位课程衷心希望本课程能让大家受益衷心希望本课程能让大家受益1教师介绍教师介绍 姓 名：刘满凤 职 称：副教授 博士 单 位：信息管理学院 电 话：3816922（O）3816926（H)E-mailE-mail:课程考核评分方法课程考核评分方法 平时成绩分占 40%其中 课堂讨论5%平时作业5%大作业 30%课程考试分占 60%授课计划授课计划 总总 时时 数：数：48 48 课时课时 授课时数：授课时数：46 46 课时课时 其中课堂授课其中课堂授课4242课时，上机授课课时，上机授课4 4课时课时 案例讨论：案例讨论：2 2 课时课时 2课程内容简介与学习要求课程内容简介运筹学是一门应用性学科，它主要是应用定性分析和定量分析相结合的方法，通过建立实际问题的数学模型，应用合适的优化算法对模型进行求解，从而解决实际问题。其主要内容有：线性规划、整数规划、非线性规划、动态规划、图与网络分析、排队论、存贮论、对策论、决策论、多目标规划等。本课程选取了运筹学在经济管理领域中常用的五个部分作为教学内容，即：线性规划、整数规划、动态规划、图与网络分析、对策论。学习要求本课程将通过重点讲授原理方法、上机解题、个人研究与小组讨论相结合的案例分析等环节，培养学员全局优化的思想，使学员掌握若干类常用的运筹学模型，并能用其解决经济管理中的复杂问题。因此要求学员：对布置的思考、案例讨论题进行认真准备，按进度完成平时作业和上机练习，按要求完成大作业书面报告。参考资料（1）刘满凤、付波、聂高飞编著运筹学模型与方法教程例题分析与题解，清华大学出版社，2001年。（2）运筹学教材编写组编运筹学（修订版），清华大学出版社，1996年。（3）蓝伯雄、程佳惠、陈秉正编著管理数学（下）运筹学，清华大学出版社，1998年。（4）中山、四川、西北、武汉、湘潭大学编运筹学经济管理决策方法，四川大学出版社，1995年。（5）韩大卫编著管理运筹学，大连理工大学出版社，1998年。（6）胡运权主编运筹学习题集（修订版），清华大学出版社，1985年。3本课程内容安派：本课程内容安派：第一部分第一部分 线性规划及其应用线性规划及其应用1、问题的数学模型与求解2、单纯形法与计算机求解3、对偶理论与灵敏度分析4、运输问题及其解法5、指派问题及其解法6、整数线性规划问题及其解法第二部分第二部分 动态规划动态规划1、动态规划的基本概念和最优化原理2、动态规划模型的建立和求解方法3、建模训练与求解第三部分第三部分 对策论模型对策论模型第四部分第四部分 图与网络分析图与网络分析 1、两人有限零和对策模型及其解法2、两人有限非零和对策1、图与网络的基本概念2、树与最小树3、最短路问题4、最大流问题5、最小费用最大流问题4 绪绪 论论一、运筹学的历史与发展国际上运筹学的思想可追溯到1914年，当时的兰彻斯特提出了军事运筹学的作战模型。1917年，丹麦工程师埃尔朗在研究自动电话系统中通话线路与用户呼叫的数量关系问题时，提出了埃尔朗公式，研究了随机服务系统中的系统排队与系统拥挤问题。存储论的最优批量公式是在20世纪20年代初提出的。5二次世界大战时期，德国空军对英伦三岛狂轰滥炸，为对付敌人的空袭，英国人使用了雷达，但没有科学的布局，防空系统的效率并不很高，为解决这个问题，英国军方于1939年9月从全国各地调来一批科学家，共11人，他们中有将军1人、数学家2人、理论物理学家2人、应用物理学家1人、天体物理学家1人、测量学家1人、生物学家3人，来到英国皇家空军指挥部，组成了以著名的物理学家、诺贝尔奖金获得者P.M.S.Blacket为核心的世界上第一个运筹学小组，他们的任务就是应用系统论的观点，统筹规划的方法研究作战问题，这个运筹学小组在作战中发挥了卓越的作用，受到英国政府极大的重视。6于是，英国政府逐渐在它的海陆空三军中都成立了运筹学小组，美国参战以后，也仿效英国在军队中成立了运筹学小组。在生产管理方面的应用，最早是1939年前苏联的康特洛为奇提出了生产组织与计划中的线性规划问题，并给出解乘数法的求解方法，出版了第一部关于线性规划的著作生产组织与计划中的数学方法。但当时并没有引起重视，直到1960年康特洛为奇再次出版了最佳资源利用的经济计算，才受到国内外的一致重视，为此康特洛为奇获得了诺贝尔经济学奖。线性规划提出后很快受到经济学家的重视，如二次世界大战中从事运输模型研究的美国经济学家库普曼斯（T.C.Koopmans），他很快看到了线性规划在经济中应用的意义，并呼吁年轻的经济学家要关注线性规划。其中阿罗、萨谬尔逊、西蒙、多夫曼和胡尔威茨等都获得了诺贝尔奖。750年代中期，钱学森、许国志等教授在国内全面介绍和推广运筹学知识，1956年，中国科学院成立第一个运筹学研究室，1957年运筹学运用到建筑和纺织业中，1958年提出了图上作业法，山东大学的管梅谷教授提出了“中国邮递员问题”，1970年，在华罗庚教授的直接指导下，在全国范围内推广统筹方法和优选法。1978年11月，在成都召开了全国数学年会，对运筹学的理论与应用研究进行了一次检阅，1980年4月在山东济南正式成立了“中国数学会运筹学会”，1984年在上海召开了“中国数学会运筹学会第二届代表大会暨学术交流会”，并将学会改名为“中国运筹学会”。在中国，最早的运筹学思想有战国时期的田忌赛马，它是对策论的一个典型例子，北宋时期的丁渭造皇宫，它是统筹规划的一个例子。8二、运筹学的基本内容1、线性规划（LinearProgram）是一个成熟的分支，它有效的算法单纯形法，主要解决生产计划问题，合理下料问题，最优投资问题。2、整数规划(IntegrateProgram)：在线性规划的基础上，变量加上整数约束3、非线性规划(NonlinearProgram)：目标函数和约束条件是非线性函数，如证券投资组合优化:如何合理投资使风险最小。4、动态规划(DynamicProgram):多阶段决策问题。是美国贝尔曼于1951年提出的。5、图与网络(GraphTheoryandNetwork)：中国邮递员问题、哥尼斯堡城问题、最短路、最大流问题。96、存储模型（InventoryTheory)：主要解决生产中的库存问题，订货周期和订货量等问题。7、排队论(QueueTheory)：主要研究排队系统中的系统排队和系统拥挤现象，从而评估系统的服务质量。8、对策论(GameTheory)：主要研究具有斗争性质的优化问题。9、决策分析(DecisionAnalysis)：主要研究定量化决策三、运筹学的工作步骤1、明确目标、收集资料、提出问题2、建立模型3、模型求解与检验4、结果分析与实施10第一部分第一部分 线性规划及其应用线性规划及其应用 线性规划研究的主要内容线性规划主要解决两个方面的问题：（1）对于给定的一项任务，如何统筹安排，使以最少的资源消耗去完成？（2）在给定的一定数量的资源条件下，如何合理安排，使完成的任务最多？线性规划内容框架1112第一章LP问题的数学模型与求解13解：设x1,x2分别表示在计划期内生产产品、的产量。由于资源的限制，所以有：机器设备的限制条件:x1+2x28原材料A的限制条件：4x116（称为资源约束条件）原材料B的限制条件：4x212同时，产品、的产量不能是负数，所以有x10，x20（称为变量的非负约束）显然，在满足上述约束条件下的变量取值，均能构成可行方案，且有许许多多。而工厂的目标是在不超过所有资源限量的条件下，如何确定产量x1，x2以得到最大的利润，即使目标函数Z=2x1+3x2的值达到最大。14综上所述，该生产计划安排问题可用以下数学模型表示：maxz=2x1+3x2例2.（营养配餐问题）假定一个成年人每天需要从食物中获取3000卡路里热量，55克蛋白质和800毫克钙。如果市场上只有四种食品可供选择，它们每千克所含热量和营养成份以及市场价格如下表所示。问如何选择才能使在满足营养的前提下使购买食品的总费用最小？15解:设xj(j=1,2,3,4)为第j种食品每天的购买量，则配餐问题数学模型为minz=10 x1+6x2+3x3+2x416例3运输问题（课本P6）某公司经销某种产品，三个产地和四个销地的产量、销量、单位运价如下表所示。问在保证产销平衡的条件下，如何调运可使总运费最少？销地单位运价产地B1B2B3B4产量A15610360A2419740A3423860销量3050404017解:（1）确定决策变量：设xij(i=1,2,3;j=1,2,3,4)为从产地i运到销地j的运量（2）确定目标函数：总运费最小minz=（3）确定约束条件：x11+x12+x13+x14=60产量约束：x21+x22+x23+x24=40 x31+x32+x33+x34=60 x11+x21+x31=30销量约束：x12+x22+x32=50 x13+x23+x33=40 x14+x24+x34=4018非负约束xij0由此模型总结为：19（二）LP问题的模型上述几例所提出的问题，可归结为在变量满足线性约束条件下，求使线性目标函数值最大或最小的问题。它们具有共同的特征。（1）每个问题都可用一组决策变量(x1,x2,xn)表示某一方案，其具体的值就代表一个具体方案。通常可根据决策变量所代表的事物特点，可对变量的取值加以约束，如非负约束。（2）存在一组线性等式或不等式的约束条件。（3）都有一个用决策变量的线性函数作为决策目标（即目标函数），按问题的不同，要求目标函数实现最大化或最小化。20满足以上三个条件的数学模型称为LP问题的数学模型，其一般形式为：max(或或min)z=c1x1+c2x2+cnxn（1.1)（1.2)（1.3)或紧缩形式21或矩阵形式或向量形式：max(或min)z=cx其中c=(c1,c2,cn)，称为价值系数向量；称为技术系数矩阵(也称消耗系数矩阵)22称为资源限制向量,X=(x1,x2,xn)T称为决策变量向量下面我们再来看两个实际例子。引例3课本P60例25（投资计划问题）某公司经调研分析知，在今后三年内有四种投资机会。第种方案是在三年内每年年初投资，年底可获利15%，并可将本金收回；第种是在第一年的年初投资，第二年的年底可获利45%，并将本金收回，但该项投资不得超过2万元；第种是在第二年的年初投资，第三年的年底可获利65%，并将本金收回，但该项投资不得超过1.5万元；第种是在第三年的年初投资，年底收回本金，且可获利35%，但该项投资不得超过1万元。现在本公司准备拿出3万元来投资，问如何计划可使到第三年年未本利和最大？23解：问题分析。该问题的实际投资背景如下表所示：（1）确定决策变量：设xij表示第i年对第j个方案的投资额,i=1,2,3;j=1,2,3,4年份一二三四x111.15x11x121.45x12x211.15x21x231.65x23x311.15x31x341.35x3424（2）确定目标函数：第三年年未的本利和为maxz=1.65x23+1.15x31+1.35x34（3）确定约束条件：每一年的投资额应等于当年公司拥有的资金数：x11+x12=3x21+x23=1.15x11x31+x34=1.45x12+1.15x21每个方案投资额的限制：x122x231.5非负约束：xij0,i=1,2,3;j=1,2,3,4x34125引例4（合理下料问题）要用一批长度为7.4米的园钢做100套钢架，每套钢架由2.9米、2.1米、1.5米的园钢各一根组成，问：应如何下料才能使所用的原料最省？解：问题分析：一根长度为7.4米的园钢，要裁出2.9米、2.1米、1.5米的料有多种裁法，如可裁出一根2.9米、二根2.1米，也可裁出三根2.1米的。这样我们把所有裁法列举出来，如下表所示：下料方案根数一二三四五六七八长度米2.9111200002.1201012301.503113204合计7.17.46.57.36.67.26.36料头（米）0.300.90.10.80.21.11.426（1）确定决策变量：设xj表示按第j种方案所用的园钢的数量（2）确定目标函数：问题要求所用原料最省，所用原料为：minz=x1+x2+x3+x4+x5+x6+x7+x8（3）确定约束条件：2.9米园钢的数量限制x1+x2+x3+2x41002.1米园钢的数量限制2x1+x3+x5+2x6+3x71001.5米园钢的数量限制3x2+x3+x4+3x5+2x6+4x3100非负限制xj0，且为整数，j=1,2,8建立线性规划模型的一般步骤：（1）确定决策变量；（2）确定目标函数；（3）确定约束条件。27引例引例5一个木材储运公司有很大的仓库用以储运出售木一个木材储运公司有很大的仓库用以储运出售木材。由于木材季度价格的变化，该公司于每季度初购进木材。由于木材季度价格的变化，该公司于每季度初购进木材，一部分于本季度内出售，一部分储存起来以后出售。材，一部分于本季度内出售，一部分储存起来以后出售。已知该公司仓库的最大储存量为已知该公司仓库的最大储存量为2000万米万米3，储存费用为，储存费用为（70+100u）千元）千元/万米万米3，u为存储时间（季度数）。已知为存储时间（季度数）。已知每季度的买进卖出价及预计的销售量如下表所示。每季度的买进卖出价及预计的销售量如下表所示。季度季度买进价（万元买进价（万元/万米万米3）卖出价（万元卖出价（万元/万米万米3）预计销售量（万米预计销售量（万米3）冬冬4104251000春春4304401400夏夏4604652000秋秋4504551600由于木材不宜久贮，所有库存木材应于每年秋末售完。为由于木材不宜久贮，所有库存木材应于每年秋末售完。为使售后利润最大，试建立这个问题的线性规划模型。使售后利润最大，试建立这个问题的线性规划模型。28设设yi分别表示冬、春、夏、秋四个季度采购的木材数，分别表示冬、春、夏、秋四个季度采购的木材数，xij代代表第表第i季度采购的用于第季度采购的用于第j季度销售的木材数。季度销售的木材数。季季度度买进价买进价（万元（万元/万万米米3）卖出价卖出价（万元（万元/万万米米3）预计销售预计销售量（万米量（万米3）冬冬4104251000春春4304401400夏夏4604652000秋秋450455160029引例引例6、有一艘货轮，分前、中、后三个舱位，它们的容积有一艘货轮，分前、中、后三个舱位，它们的容积与最大允许载重量如表与最大允许载重量如表1所示。现有三种货物待运，已知有所示。现有三种货物待运，已知有关数据列于表关数据列于表2。为了航运安全，要求前、中、后舱在实际。为了航运安全，要求前、中、后舱在实际载重量上大体保持各舱最大允许载重量的比例关系，具体载重量上大体保持各舱最大允许载重量的比例关系，具体要求前、后舱分别与中舱之间载重量比例上偏差不超过要求前、后舱分别与中舱之间载重量比例上偏差不超过15%，前、后舱之间不超过，前、后舱之间不超过10%。问该货轮应装载。问该货轮应装载A，B，C各多少件，运费收入为最大？试建立这个问题的线性规各多少件，运费收入为最大？试建立这个问题的线性规划模型。划模型。前舱前舱中舱中舱后舱后舱最大允许载重量（吨）最大允许载重量（吨）200030001500容积（立方米）容积（立方米）400054001500表1商品商品数量（件）数量（件）每件体积（立方米每件体积（立方米/件）件）每件重量（吨每件重量（吨/件）件）运价（元运价（元/件）件）A6001081000B100056700C8007560030设表示设表示xij装于第装于第j(j=1,2,3)舱位的第舱位的第i(i=1,2,3)种商品的数量种商品的数量舱位载重限制舱位体积限制商品数量限制平衡条件前舱前舱 中舱中舱 后舱后舱重重量量2000 3000 1500容容积积4000 5400 1500商商品品数量数量 体体积积重重量量运运价价A6001081000B100056700C8007560031（三）LP问题的标准型1.为了讨论LP问题解的概念和解的性质以及对LP问题求解方便，必须把LP问题的一般形式化为统一的标准型：或maxz=cx标准型的特点：目标函数是最大化类型约束条件均由等式组成决策变量均为非负bi(i=1,2,n)=0322.化一般形式为标准型目标函数：minzmax(-z)=-cx若约束为“”型左边+松驰变量；若约束为“”型左边“松驰变量”若变量xj0-xj0变量，若变量xj无限制令xj=xjxj若右边常数bi0等式两边同乘以(-1)。例4课本P9化下述问题为标准型minz=-x1+2x2-3x3x1+2x2+3x37s.t.-x1+x2-x3-2-3x1+x2+2x3=5x1,x30,x2无约束33解：首先考察变量：令，并加入松驰变量x4,x5化为如下标准型：练习：课本P642.2（3）34解：令则加入松驰变量s,w，得到标准型如下：35（四）LP问题解的概念1.从代数的角度看：可行解（FeasibleSolution)：满足约束条件(1.8)和(1.9)的解X=(x1,x2,xn)T称为可行解。所有可行解构成可行解集，即可行域。最优解(OptimalSolution):而使目标函数达到最大值的可行解称为最优解，对应的目标函数值称为最优值。求解LP问题就是求其最优解和最优值，但从代数的角度去求是困难的。设LP问题362.从LP角度看：基(Basis)：设A为mxn矩阵，r(A)=m，B是A中的mxn阶非奇异子矩阵（即|B|0），则称B是LP问题的一个基。若B是LP问题的一个基，则B由m个线性独立的列向量组成，即B=(Pr1,Pr2,Prm)，其中Prj=(a1rj,a2rj,amrj)T，(j=1,2,m)称为基向量。基变量(BasicVariables)与非基变量(Non-basicVariable)与基向量Prj相对应的变量xrj称为基变量，其它变量称为非基变量。显然，对应于每个基总有m个基变量，nm个非基变量。基本解(BasicSolution)：设B是LP问题的一个基，令其nm个非基变量均为零，所得方程的解称为该LP问题的一个基本解。显然，基B与基本解是一一对应的，基本解的个数Cmn。基可行解:在基本解中，称满足非负条件的基本解为基可行解，对应的基称为可行基。37退化解(DegenerateSolution)：如果基解中非零分量的个数小于m，则称此基本解为退化的，否则是非退化的。最优基解(OptimalBasicSolution)：如果对应于基B的基可行解是LP问题的最优解，则称B为LP问题的最优基，相应的解又称基本最优解。3.LP问题解之间的关系如图所示：可行解基解最优解基最优解38（五）两个变量LP问题的图解法1、LP问题图解法的步骤：（1）画出直角坐标系；（2）依次做每条约束直线，标出可行域的方向，并找出它们共同的可行域；（3）任取一目标函数值作一条目标函数线（称等值线）,根据目标函数（最大或最小）类型，平移该直线即将离开可行域处，则与目标函数线接触的最终点即表示最优解。例1：用图解法求解如下线性规划问题2x1+3x2=243x1+2x2=26Q2(6,4)Q1(26/3,0)Q3(0,8)A(12,0)B(0,13)最优解为x1=6,x2=4最优值为maxz=3639max=2x1+3x2例2：用图解法求解下列线性规划：Q3Q4Bx132101234Q2（4，2）Q1Q2（4，2）为最优解40解的几种情况：（1）此例有唯一解Q2，即x1=4,x2=2,z=14（2）有无穷多最优解（多重解），若将目标函数改为z=2x1+4x2则线段Q2，Q3上的点均为最优解。（3）无界解41(4)无可行解42结论：（1）LP问题的可行域是凸集（凸多边形，凸多面体，）。（2）LP问题最优解若存在，则必可在可行域的顶点上达到。（3）LP问题的可行域的顶点个数是有限的。（4）若LP问题若有两个最优解，则其连线上的点都是最优解。因此，求解LP问题可转化为：“如何在可行域的顶点上求出使目标函数值达到最优的点的问题：”。432.基可行解的几何意义对例1LP问题标准化为maxZ=2x1+3x2可求得它的所有的基本解：x(1)=(0,0,8,16,12)T(0点),x(2)=(4,0,4,0,12)T(Q1点)x(3)=(4,2,0,0,4)T(Q2点),x(4)=(2,3,0,8,0)T(Q3点)x(5)=(0,3,2,16,0)T(Q4点),x(6)=(4,3,-2,0,0)T(C点)x(7)=(8,0,0,-16,12)T(A点),x(8)=(0,4,0,16,-4)T(B点)但A、B、C三点是非可行域上的点，即非可行解。因此，x(1)，x(2)，x(3)，x(4)，x(5)才是基可行解，它们与可行域的顶点相对应。于是还有ACQ1Q244结论：（5）对于标准型的LP问题，X是基可行解的充要条件是X为可行域的顶点。（6）LP问题可行域顶点的个数=基可行解的个数基的个数Cmn3.图解法只适用于两个变量（最多含三个变量）的LP问题。4.求解LP问题方法的思考：完全枚举法，对m、n较大时，Cmn是一个很大的数，几乎不可能；从可行域的一个顶点（基可行解）迭代到另一个顶点（基可行解）。452 单纯形法与计算机求解46将目标函数改写为：-Z+c1x1+c2x2+cnxn=0把上述方程组和目标函数方程构成n+1个变量，m+1个方程的方程组，并写成增广矩阵的形式：2.单纯形法的计算步骤（表格形式）（1）建立初始单纯形表，假定B=I，b0设maxZ=c1x1+c2x2+cnxn47484950上述初始单纯形表可确定初始可行基和初始基可行解：B=(P1,P2,Pm)=I,x=(b1,b2,bm,00)T从初始单纯形表建立的过程可以看到以下事实：（1）凡LP模型中约束条件为“”型，在化为标准型后必有B=I，如果b0，则模型中约束方程的各数据不改变符号照抄在表中相应的位置。目标函数中非基变量的系数则以相反数填入检验数行各相应位置。（2）在单纯形表中，凡基变量所在的列向量必是单位列向量，其相应的检验数均为零。51（2）判别最优解1在T(B)中，若所有的检验数j0(j=1,2,n)则B为最优基，相应的基可行解为最优解，停止计算。2在T(B)中，若有k0(1kn)，且xk的系数列向量Pk0，则该问题无界，停止计算。否则转入（3）（3）换基迭代（基变换）1先确定进基变量Xk:k=minj|j0,20,d020,a10d=0d013/a3,a30583、设有线性规划问题：其中b1,b2是常数，且已知此规划的最终表为：cj52300CBXBbx1x2x3x4x550 x1x530101b2100c-8-11Z1500a7de确定表中所有的参数。e=0,d=5,b=5,c=-10,a=23,b1=30,b2=40593.单纯形法的进一步讨论单纯形法的进一步讨论用人工变量法求初始基可行解用人工变量法求初始基可行解（一）人工变量法若对LP模型标准化后，不具有B=I时，如何办？此时可采用人工变量法得到初始基可行解。所谓人工变量法是在原问题不含有初始可行基B=I的情况下，人为的对约束条件增加虚拟的非负变量（即人工变量），构造出含有B=I的另一个LP问题后求解。当增加的人工变量全部取值为0时，才与原问题等价。这样，新问题将有一个初始基可行解（以人工变量为基变量），可用单纯形法进行迭代。经迭代后，若人工变量全部被换成非基变量，即人工变量全部出基，则得到原问题的一个基可行解。在最终表中若人工变量不能全部被换出，则说明原问题无可行解。因此，该法的关键在于将人工变量全部换出。60人工变量法常见的有大M法和两阶段法。61注意到：分别在约束条件中增加人工变量x5,x6是为了构成“人工基”对于Min的目标函数采用(+M)，而对于Max的目标函数则采用(-M)作为人工变量的系数,是强加于人工变量的一种惩罚,其目的是为了强制人工变量由基变量转为非基变量，使之恢复原问题，或与原问题等价。对于minZ判别最优性准则应是CjZj0。大M法适合于计算机计算，不适用于手工求解。所以本题求解过程略。62（2）两阶段法第一阶段：不考虑原问题是否存在基可行解；给原LP问题的约束条件加入人工变量，构造仅含人工变量的目标函数并要求实现最小化（即使原LP问题目标函数是求最大化）的辅助问题：MinW=xn+1+xn+m然后用单纯形法求解（1）。若W0，则原问题无可行解，停止计算。若W=0，且所有的人工变量均为非基变量，则去掉人工变量后可得到原问题的基可行解；如果人工变量中含有为0的基变量时（即退化解），则可再进行初等行变换将其换出，从而获得原问题的基可行解。（1）63第二阶段：在第一阶段所得的基可行解的基础上，将最终表中的人工变量列删去，同时将人工目标函数行换为原问题的目标函数作为第二阶段计算的初始表。仍以上例为例用两阶段法求解。MinZ=x1+1.5x2+0 x3+0 x4MinW=x5+x6辅助问题：原问题：用单纯形法求解的迭代表如下：64cj000011CBXBbx1x2x3x4x5x611x5x63213-1010110-101W524-1-100cj000011CBXBbx1x2x3x4x5x601x2x6111/31-1/301/302/301/3-1-1/31W12/301/3-1-4/3065cj000011CBXBbx1x2x3x4x5x600 x2x11/23/201-1/21/21/2-1/2101/2-3/2-1/23/2W00000-1-1上述表中目标函数值W=0，且人工变量已全部出基，得到原问题的一个可行基B=（P2，P1）和一个基可行解X=（X2，X1）=（1/2，3/2）。去掉人工变量列，并将目标函数行换为原目标函数行得：cj0000CBXBbx1x2x3x41.51x2x11/23/201-1/21/2101/2-3/2Z9/400-1/4-3/466上表中最后一行所有检验数均非正（因为是求极小化问题），所以上述表已是原问题的最优表。从表中可知原问题的最优解为X1=1/2，X2=3/2，最优目标函数值为Z=9/4。注意：第二阶段在填单纯形表时，检验数行的值是将原 目 标 函 数 中 的 基 变 量 用 非 基 变 量 表 示（x1=3/2-1/2x3+3/2x4，x2=1/2+1/2x3-1/2x4）后所得结果填入，或直接通过表中数字关系计算而得。67 总总 结结一、线性规划模型的建立一、线性规划模型的建立1、确定决策变量、确定决策变量2、确定目标函数、确定目标函数3、确定约束条件、确定约束条件二、线性规划模型的求解二、线性规划模型的求解1）找到初始可行基解，建立初始单纯形表）找到初始可行基解，建立初始单纯形表2）判断最优：所有检验数大于等于）判断最优：所有检验数大于等于0时最优时最优3）换基迭代：以负检验数对应的变量进基，）换基迭代：以负检验数对应的变量进基，按最小元素法确定出基变量。按最小元素法确定出基变量。1、普通单纯形法、普通单纯形法2、人工变量法、人工变量法1）在原问题上加入人工变量化为辅助问题）在原问题上加入人工变量化为辅助问题,用用单纯形法求解辅助问题单纯形法求解辅助问题2）删去人工变量和改换目标函数）删去人工变量和改换目标函数,求解原问题求解原问题68练习：求解下列线性规划问题练习：求解下列线性规划问题其最优表为：其最优表为：cj-12100CBXBbx1x2x3x4x512x3x2133/2011-1/21/21001/2Z77/20011/269补充：矩阵形式的单纯形表补充：矩阵形式的单纯形表加入松驰变量加入松驰变量化为标准形化为标准形设设C=（CB,CN),A=(B,N),代入代入(2)得得:(2)70将基变量从目标函数中消除将基变量从目标函数中消除建立对应于基建立对应于基B的矩阵形式的单纯形表的矩阵形式的单纯形表T（B）：）：71CCBCNCSbXBXNXSXBB-1bIB-1NB-1ZCBB-1b0CBB-1N-CNCBB-1B-1ACBB-1A-CbXXBB-1bB-1AZCBB-1bCBB-1A-C化简为如下简单的表格形式化简为如下简单的表格形式:722.4 对偶理论与灵敏度分析一、一、LP的对偶问题的对偶问题1.引例引例课课本本P6的的生生产产计计划划问问题题是是一一个个在在有有限限资资源源的的条条件件下下，求求使使利润最大的生产计划安排问题，其数学模型为：利润最大的生产计划安排问题，其数学模型为：现从另一角度考虑此问题。假设有客户提出要求，租赁现从另一角度考虑此问题。假设有客户提出要求，租赁工厂的工时和购买工厂的材料，为其加工生产别的产品，工厂的工时和购买工厂的材料，为其加工生产别的产品，由客户支付工时费和材料费，此时工厂应考虑如何为每由客户支付工时费和材料费，此时工厂应考虑如何为每种资源定价，同样使其获得的利润最大？种资源定价，同样使其获得的利润最大？73解解:1)决策变量：决策变量：设设y1,y2分别表示出售单位原材料的价格分别表示出售单位原材料的价格（含附加值）和出租设备单位工时的租金（含附加值）和出租设备单位工时的租金 3)约束条件约束条件:工厂决策者考虑：工厂决策者考虑：（1）出出售售原原材材料料和和出出租租设设备备应应不不少少于于自自己己生生产产产产品品的的获利，否则不如自己生产为好。因此有获利，否则不如自己生产为好。因此有2）目标函数：）目标函数：此时工厂的总收入为此时工厂的总收入为W=24y1+26y2,这也是这也是租赁方需要付出的成本租赁方需要付出的成本.而在这个问题中而在这个问题中,是企业不生产是企业不生产,将自己的资源出售或出租将自己的资源出售或出租,因此因此,此时此时,起决定作用的是租起决定作用的是租赁方赁方,所以此时的目标函数为所以此时的目标函数为 Min W=24y1+26y2742）价价格格应应尽尽量量低低，否否则则没没有有竞竞争争力力（此此价价格格可可成成为为与与客客户户谈判的底价谈判的底价租赁者考虑：希望价格越低越好，否则另找他人。租赁者考虑：希望价格越低越好，否则另找他人。于是，能够使双方共同接受的是于是，能够使双方共同接受的是：上述两个LP问题的数学模型是在同一企业的资源状况和生产条件下产生的，且是同一个问题从不同角度考虑所产生的，因此两者密切相关。称这两个LP问题是互为对偶的两个LP问题。其中一个是另一个问题的对偶问题。75一般地对于任何一个线性规划问题都有一个与之相对应的一般地对于任何一个线性规划问题都有一个与之相对应的对偶问题。原问题与对偶问题的一般形式为：对偶问题。原问题与对偶问题的一般形式为：原问题（原问题（LP）对偶问题（对偶问题（DP）相应的矩阵形式为：76对称形式的对偶问题为：对称形式的对偶问题为：（LP）（DP）二、对偶理论二、对偶理论1.原问题与对偶问题的关系原问题与对偶问题的关系由以上两式可知由以上两式可知,原问题与对偶问题之间具有如下关系原问题与对偶问题之间具有如下关系(1)一个问题中的约束条件个数等于它的对偶问题中的变量一个问题中的约束条件个数等于它的对偶问题中的变量数数;(2)一个问题中目标函数的系数是其对偶问题中约束条件的一个问题中目标函数的系数是其对偶问题中约束条件的右端项右端项;(3)约束条件在一个问题中为约束条件在一个问题中为“”,则在其对偶问题中为则在其对偶问题中为“”;(4)目标函数在一个问题中为求最大值目标函数在一个问题中为求最大值,在其对偶问题中则在其对偶问题中则为求最小值为求最小值77例例1、写出下列线性规划问题的对偶问题（、写出下列线性规划问题的对偶问题（P27）非对称形式的对偶问题为：非对称形式的对偶问题为：（LP）（DP）78原问题Max（对偶问题）对偶问题Min（原问题）约束条件数=m变量个数=m第i个约束条件为“”第i个约束条件为“”第i个约束条件为“=”第i个变量0第i个变量0第i个变量无限制变量个数=n约束条件个数=n第i个变量0第i个变量0第i个变量无限制第i个约束条件为“”第i个约束条件为“”第i个约束条件为“=”第i个约束条件的右端项目标函第i个变量的系数目标函数第i个变量的系数第i个约束条件的右端顶归纳对称形式与非对称形式的对偶归纳对称形式与非对称形式的对偶,原问题与对偶问题之原问题与对偶问题之间的关系如下表所示间的关系如下表所示792.设对偶问题的基本定理对偶问题的基本定理MaxZ=CXMinW=Yb（1）（对称性）对偶问题的对偶是原问题；）（对称性）对偶问题的对偶是原问题；（2）（弱弱对对偶偶定定理理）若若X(0)是是原原问问题题的的可可行行解解，Y(0)是是对对偶偶问题的可行解问题的可行解,则有则有（3）（无无界界性性）若若原原问问题题（对对偶偶问问题题）为为无无界界解解，则则其其对对偶偶问题（原问题）无可行解；问题（原问题）无可行解；（4）（最最优优性性定定理理），若若X(0)、Y(0)分分别别是是互互为为对对偶偶问问题题的的可可行行解解，且且C X(0)=Y(0)b，则则X(0)、Y(0)分分别别是是它它们们的的最最优优解解（5）（强对偶定理）若互为对偶问题之一有最优解，则另一）（强对偶定理）若互为对偶问题之一有最优解，则另一问题必有最优解，且它们的目标函数值相等。问题必有最优解，且它们的目标函数值相等。8081P29思考题：已知如下线性规划问题的对偶问题的最优解为y1*=4/5,y2*=3/5,z*=5，试用对偶理论找出原问题的最优解解：其对偶问题为：应用互补松驰性定理，将y1*=4/5,y2*=3/5代入对偶问题的约束条件得：x10又由于y1*,y2*0，原问题x2=0的两个约束为紧约束，所以x3=0 x4=0 x50解得：x1=1,x5=1,x2=x3=x4=082三、对偶单纯形法三、对偶单纯形法1.单纯形法的重新解释单纯形法的重新解释X*是最大化是最大化LP问题最优解的充要条件是同时满足：问题最优解的充要条件是同时满足：（称为原始可行条件）（称为对偶可行条件）因因此此，单单纯纯形形法法是是在在保保持持原原始始可可行行下下，经经过过迭迭代代，逐逐步步实实现对偶可行，达到求出最优解的过程。现对偶可行，达到求出最优解的过程。即单纯形法的迭代是先保证现行解对原问题可行，即即单纯形法的迭代是先保证现行解对原问题可行，即，然后从然后从0 到 根根据据对对偶偶问问题题的的对对称称性性，也也可可以以在在保保持持对对偶偶可可行行下下，经经过过迭迭代代，逐逐步步实实现现原原始始可可行行，以以求求得得最最优优解解。对对偶偶单单纯纯形形法法就是根据这种思想所设计的。就是根据这种思想所设计的。因此，对偶单纯形法是先保证现行解对对偶问题可行，即因此，对偶单纯形法是先保证现行解对对偶问题可行，即，然后从然后从0 到到83例例14 用对偶单纯形法求解下列线性规划问题：用对偶单纯形法求解下列线性规划问题：解：化为标准形后，用对偶单纯形法求解过程如下表所示cj-12-8-16-1200CBXBby1y2y3y4y5y600y5y6-2-3-2-1-4010-2-20-401w01281612002.对偶单纯形法的计算步骤：对偶单纯形法的计算步骤：84cj-12-8-16-1200CBXBby1y2y3y4y5y60-12y5y4-23/4-2-1-40101/21/2010-1/4w-96216003cj-12-8-16-1200CBXBby1y2y3y4y5y600y2y42-1/42140-10-1/20-211/2-1/4w-1320802385cj-12-8-16-1200CBXBby1y2y3y4y5y6-8-16y2y33/21/811020-1/21/401-1/2-1/41/8w-14000442上表中常数列上表中常数列b所对应的系数所对应的系数均为非负，已求得问题的最优解，均为非负，已求得问题的最优解，最优解为最优解为y=(y1,y2,y3,y4)T=(0,3/2,1/8,0)；最优值为；最优值为z*=14注意：对偶单纯形法仍是求解原问题，它是适用于当原问注意：