线性规划及单纯形法最新新

线性规划及单纯形法线性规划及单纯形法(最新新最新新)课堂要求1.要求同学们上课不迟到，不早退，不得旷课；2.上课认真听讲，要求每位同学都做笔记；3.上课不得讲话，看书，玩手机等与课堂无关的内容；4.课后要求独自完成作业，不得抄袭或不做课后作业。2参考资料1.胡运权主编，运筹学教程（第三版），清华大学出版社；2.周华任主编，运筹学解题指导，清华大学出版社；3.运筹学习题集（修订版），清华大学出版社；4.熊伟编著，运筹学，机械工业出版社；5.运筹学数据、模型、决策，科学出版社。3教学计划教学计划 以线性规划和运输问题为讲授重点，其以线性规划和运输问题为讲授重点，其它部分作为选讲内容。它部分作为选讲内容。教学方法教学方法 以授课为主，案例分析与上机演示为辅。以授课为主，案例分析与上机演示为辅。而讲课中主要培养用最优化方法解决实际而讲课中主要培养用最优化方法解决实际问题的能力。问题的能力。教学计划与方法4前言运筹学简介运筹学是管理科学的重要理论基础和应用手段，是管理专业的重要专业基础课程之一。运筹学根据管理问题的环境条件和决策要求，建立相应的数学模型，利用数学模型对实际问题进行分析和求解，经过分析和比较，得到适合实际问题的方案。求解结果.求解结果.建立模型求解模型修改模型求解结果.修改模型实际问题数学模型5运筹学是在第二次世界大战中诞生和发展起来的。由于战争的需要，英国和美国招募了一批年轻的科学家和工程师，在军队将军的领导下研究战争中的问题，例如大规模轰炸的效果，搜索和攻击敌军潜水艇的策略，兵力和军需物质的调运等等。这些研究在战争中取得了很好的效果。当时英国把这些研究成为“作战研究”，英文是Operational Research，在美国称为Operations Research。6战后这些研究成果逐渐公开发表，这些理论和方法被应用到经济计划，生产管理领域，也产生了很好的效果。这样，Operations Research就转义成为“作业研究”。我国把Operations Research译成“运筹学”，非常贴切地涵盖了这个词作战研究和作业研究两方面的涵义。运筹学的内容十分广泛，包括线性规划、整数规划、动态规划、非线性规划、图论与网络优化、排队论、决策理论、库存理论等。在本课程中，结合管理学科的特点，主要介绍线性规划和运输问题。7线性规划线性规划数数学学规规划划非线性规划非线性规划整数规划整数规划动态规划动态规划学学科科内内容容多目标规划多目标规划双层规划双层规划组组合合优优化化最优计数问题最优计数问题网络优化网络优化排序问题排序问题统筹图统筹图随随机机优优化化对策论对策论排队论排队论库存论库存论决策分析决策分析可靠性分析可靠性分析运筹学的主要内容8目录：p第一章线性规划及单纯形法p第二章 对偶问题p第三章灵敏度分析p第四章线性规划的建模与应用p第五章 运输问题9第一章 线性规划p线性规划问题p线性规划模型p线性规划的图解p可行域的性质p线性规划的基本概念p基础解、基础可行解p单纯形表10第1节线性规划问题及其数学模型n生产计划问题n配料问题n背包问题n运输问题n指派问题1.1问题的提出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三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占有的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：求使得总利润最大的生产计划。12产品甲产品乙产品丙产品丁设备能力（小时）设备A1.51.02.41.02000设备B1.05.01.03.58000设备C1.53.03.51.05000利润（元/件）5.247.308.344.18设四种产品的产量分别为x1，x2，x3，x4，总利润为z，线性规划模型为：max z=5.24x1+7.30 x2+8.34x3+4.18x4s.t.1.5x1+1.0 x2+2.4x3+1.0 x42000 1.0 x1+5.0 x2+1.0 x3+3.5x48000 1.5x1+3.0 x2+3.5x3+1.0 x45000 x1,x2,x3,x40目标函数约束条件变量非负约束这个问题的最优解为：x1=294.12件，x2=1500件，x3=0，x4=58.82件最大利润为：z=12737.06元。132.配料问题（Material Blending）某工厂要用四种合金T1、T2、T3、T4为原料，经熔炼成为新的不锈钢G。这四种原料含铬（Cr）、锰（Mn）和镍（Ni）的含量（），这四种原料的单价以及新的不锈钢G所要求的Cr、Mn、Ni的最低含量（）如下表：T1T2T3T4GCr3.214.532.191.763.20Mn2.041.123.574.332.10Ni5.823.064.272.734.30单价（元/公斤）115978276要求配100公斤不锈钢G，并假定在配制过程中没有损耗。求使得总成本最低的配料方案。14T1T2T3T4GCr3.214.532.191.763.20Mn2.041.123.574.332.10Ni5.823.064.272.734.30单价（元/公斤）115978276min z=115x1+97x2+82x3+76x4s.t.3.21x1+4.53x2+2.19x3+1.76x4320 Cr的含量下限约束 2.04x1+1.12x2+3.57x3+4.33x4210 Mn的含量下限约束 5.82x1+3.06x2+4.27x3+2.73x4430 Ni的含量下限约束 x1+x2+x3+x4=100 物料平衡约束 x1,x2,x3,x40设四种原料分别选取x1，x2，x3，x4公斤，总成本为z。这个问题的最优解为：x1=26.58,x2=31.57,x3=41.84，x4=0（公斤）,最低成本为z=9549.87元。问题：如果某一种成分的含量既有下限，又有上限怎么办？153.背包问题（Knapsack Problem）一只背包最大装载重量为50公斤。现有三种物品，每种物品数量无限。每种物品每件的重量、价格如下表：物品1物品2物品3重量（公斤/件）104120价值（元/件）177235求背包中装入每种物品各多少件，使背包中物品总价值最高。16设三种物品的件数各为x1，x2，x3件，总价值为z。max z=17x1+72x2+35x3s.t.10 x1+41x2+20 x350 x1，x2，x30 x1，x2，x3为整数这是一个整数规划问题（Integer Programming）。这个问题的最优解为：x1=1件，x2=0件，x3=2件，最高价值z=87元物品1物品2物品3重量（公斤/件）104120价值（元/件）177235174.运输问题（Transportation）某种物资从两个供应地A1，A2运往三个需求地B1，B2，B3。各供应地的供应量、各需求地的需求量、每个供应地到每个需求地每吨物资的运输价格如下表：运价（元/吨）B1B2B3供应量（吨）A123535A247825需求量（吨）10302060求总运费最低的运输方案。18运价（元/吨）B1B2B3供应量（吨）A123535A247825需求量（吨）10302060A1A2B3B2B135吨25吨10吨30吨20吨23547819运价（元/吨）B1B2B3供应量（吨）A123535A247825需求量（吨）10302060设从两个供应地到三个需求地的运量（吨）如下表：B1B2B3A1x11x12x13A2x21x22x2320运价（元/吨）B1B2B3供应量（吨）A123535A247825需求量（吨）10302060min z=2x11+3x12+5x13+4x21+7x22+8x23s.t.x11+x12+x13 =35 供应地A1 x21+x22+x23=25 供应地A2 x11 +x21 =10 需求地B1 x12 +x22 =30 需求地B2 x13 +x23=20 需求地B3 x11,x12,x13,x21,x22,x230 21运量（吨）B1B2B3供应量（吨）A130535A2101525需求量（吨）10302060这个问题的最优解表示如下：最小总运费为：z=330+55+410+815=275元A1A2B3B2B135吨25吨10吨30吨20吨23547830吨5吨10吨15吨225.指派问题（Assignment Problem）有n项任务由n个人完成，每项任务交给一个人，每人都有一项任务。由i个人完成j项任务的成本（或效益）为cij。求使总成本最小（或总效益最大）的分配方案。设：23张、王、李、赵四位老师被分配教语文、数学、物理化学四门课程，每位老师教一门课，每门课由一位老师教。根据这四位老师以往教课的情况，他们分别教四这门课程的平均成绩如下表。要求确定哪一位老师上哪一门课，使四门课的平均总成绩最高。语文数学物理化学张92688576王82917763李83907465赵9361837524设：语文数学物理化学张x11x12x13x14王x21x22x23x24李x31x32x33x34赵x41x42x43x44max z=92x11+68x12+85x13+76x14+82x21+91x22+77x23+63x24+83x31+90 x32+74x33+65x34+93x41+61x42+83x43+75x44s.t.x11+x12+x13+x14=1 (1)x21+x22+x23+x24=1 (2)x31+x32+x33+x34=1 (3)x41+x42+x43+x44=1 (4)x11+x21+x31+x41=1 (5)x12+x22+x32+x42=1 (6)x13+x23+x33+x43=1 (7)x14+x24+x34+x44=1 (8)xij=0,125最优解为：x14=1，x23=1，x32=1，x41=1，max z=336即张老师教化学，王老师教语文，李老师教数学，赵老师教语文。语文数学物理化学张0001王0010李0100赵1000语文数学物理化学张92688576王82917763李83907465赵93618375四门课的总分可以达到336分。26线性规划模型min(max)z=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn (,)b1 a21x1+a22x2+a2nxn (,)b2 am1x1+am2x2+amnxn (,)bm x1,x2,xn 0(,Free)线性规划模型的目标函数必须是变量的线性函数，约束条件必须是变量的线性等式或不等式。如右的问题就不是线性规划问题：271.2线性规划的标准形式目标函数为极大化，约束条件全部为等号约束，右端常数项均为非负，所有变量全部是非负的，这样的线性规划模型称为标准形式maxz=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1,x2,xn 0 28线性规划模型用矩阵和向量表示max z=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1,x2,xn 0 29线性规划模型用矩阵和向量表示（续）因此，线性规划模型可以写成如下矩阵和向量的形式MaxZ =CTXs.t.AX=b X0 30线性规划模型总结线性规划模型的结构n目标函数：max，minn约束条件：,=,n变量符号：0,0,Free线性规划的标准形式n目标函数：maxn约束条件：=n右端常数项：0n变量符号：0MaxZ =CTXs.t.AX=b X0 31线性规划问题的标准化n极小化目标函数转化为极大化n小于等于约束条件转化为等号约束n大于等于约束条件转化为等号约束n右端常数项小于等于0的标准化n变量小于等于0的标准化n变量没有符号限制（Free）的标准化32非标准形式如何化为标准1)Min型化为Max型 加负号 因为，求一个函数的极小点，等价于求该函数的负函数的极大点。注意：Min型化为Max型求解后，最优解不变，但最优值差负号。33 min z=2x1-3x2+x3令 z=-z，z=-2x1+3x2-x3新的目标函数 max z=-2x1+3x2-x3取得极大化的最优解时，这个最优解同时使原目标函数值取得最小化的最优解。但两个问题最优解的目标函数值相差一个负号。极小化目标函数问题转化为极大化目标函数34例如，对于以下两个线性规划问题min z=2x1+3x2s.t.x1+x23 x21 (A)x1,x20max z=-2x1-3x2s.t.x1+x23 x21 (B)x1,x20它们的最优解都是x1=2,x2=1，但(A)的最小化的目标函数值为min z=7，(B)的最大化的目标函数值为max z=-7352)不等式约束化为等式约束分析：以下面约束为例之所以“不等”是因为左右两边有一个差额，称为“松弛量”，若在左边加上这个松弛量，则化为等式。而这个松弛量也是变量，记为 ，则有称为松弛变量。问题：它的实际意义是什么？资源的“剩余”。36 2x1+3x2-4x35引进松弛变量(Slack variable)x4=5-(2x1+3x2-4x3)，把松弛变量x4加在约束条件左边，就可以将小于等于约束变为等式。2x1+3x2-4x3+x4=5由此可以知道，松弛变量x40。如果有一个以上小于等于约束，要对于每一个约束引进不同的松弛变量。例如：2x1+3x2-4x35 3x1-2x2+5x38在两个约束中分别引进松弛变量x4，x50 2x1+3x2-4x3+x4 =5 3x1-2x2+5x3 +x5=8小于等于约束条件转化为等号约束37将不等式约束变为等式约束。例如：2x1+3x2-4x35 3x1-2x2+5x38在两个约束的左边分别减去剩余变量x4，x50 2x1+3x2-4x3-x4 =5 3x1-2x2+5x3 -x5=8大于等于约束条件转化为等号约束38练习：请将下列约束化为标准型解：增加松弛变量则约束化为易见，增加的松弛变量的系数恰构成一个单位阵I。39一般地，记松弛变量的向量为 Xs，则问题：松弛变量在目标中的系数为何？0。3)当模型中有某变量 xk 没有非负要求，称为自由变量,则可令 化为标准型。40没有符号限制的变量，用两个非负变量之差表示。例如：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)的标准化41Max z=-x1-2x2+3x3s.t.2x1+3x2-4x3+x4 =5 3x1-2x2+5x3-x5=8 x10,x2:free,x3,x4,x50然后，令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,x50424）右端常数项小于等于0的标准化当右端常数项为小于等于0时，如：2x1-3x2+4x3-4只需不等式两边同乘以-1，不等式改好就可以了-2x1+3x2-4x3443min 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,x505）变量小于等于0的的标准化44练习：min z=2x1-x2+4x3s.t.x1+x2-x33 3x1-x2+2x36 x1-3x2-4x3-4 x10,x30451.3线性规划问题解的概念设线性规划46举例：1.maxZ=8x1+10 x2 2x1+x2 11 x1+2x2 10 x1,x20确定下列向量中哪些是解？可行解？求出可行域。47基本概念（1）可行解与最优解直观上，可行解是可行域中的点，是一个可行的方案；最优解是可行域的角点，是一个最优的方案。481.4 图解法：对于模型中只有两个变量的线性规划问题，可以通过在平面上作图的方法求解。一个线性规划问题有解，是指能找出一组xj(j=1,2,n)，满足约束条件，称这组xj为问题的可行解。通常线性规划问题总是含有多个可行解，称全部可行解的集合为可行域，可行域中使目标函数为最优的可行解为最优解。图解法的目的是判别线性规划问题的求解结局和存在最优解的条件下求出最优解。49图解法的步骤1.建立具有合适刻度单位的坐标系统；2.对每一约束条件建立直线，从而确定可行域；3.确定目标函数等值线的移动方向；4.求出最优解：最优解为等值线在移动过程中与可行域的最后交点。50线性规划的图解max z=x1+3x2s.t.x1+x26-x1+2x28x1 0,x20可行域目标函数等值线最优解6543211 2 3 4 5 6-8 -7 -6 -5 -4 -3-2 -1 0 x1x2z=6z=3z=9z=12问题：1、线性规划的最优解是否可能位于可行域的内部？2、线性规划的最优解是否可能位于可行域的边界上？51举例：1.maxZ=2x1+x2 5x215 6x1+2x2 24 x1+x2 5 x1,x20唯一最优解2.maxZ=x1+x2 -2x1+x2 4 x1-x2 2 x1,x20 无界解 3.maxZ=3x1+9x2 x1+3x2 22 -x1+x2 4 x1,x20无穷多最优解 4.maxZ=x1+x2 x1+x2 1 2x1+2x24 x1,x20无解52线性规划可行域和最优解的几种情况1、可行域封闭 唯一最优解2、可行域封闭 多个最优解3、可行域开放 唯一最优解4、可行域开放 多个最优解5、可行域开放 目标函数无界6、无可行解53 标准化的线性规划问题，有n个变量，m个约束。maxz=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1,x2,xn 0 p如果m个变量的系数矩阵的行列式不等于0，这个mm的矩阵称为线性规划的一个基。其余的n-m个变量称为非基变量，m个变量称为基变量。1.5线性规划的基本概念基、基解、基可行解、极点54求解mm的线性方程组，得到基变量的一组解，连同等于0的非基变量这n个变量的值称为线性规划的一个基解。如果一个基解中的所有变量都是非负的，这个基解称为基可行解。线性规划的基可行解就是可行域的极点。55基矩阵与基变量基矩阵(简称基)：系数阵A中的m阶可逆子阵，记 为B；其余部分称为非基矩阵，记为N。基向量：基B中的列；其余称非基向量。基变量：与基向量Pj对应的决策变量xj，记其组成的 向量为XB；与非基向量对应的变量称非基变 量，记其组成的向量为XN。56 6个。一般地，mn 阶矩阵A中基的个数最多有多少个？问题：本例的A中一共有几个基？57基本解与基本可行解可见：一个基本解是由一个基决定的。注意：基本解仅是资源约束的解，并未要求其非负，因此其未必可行。称非负的基本解为基本可行解（简称基可行解）。58例4：在上例中求相应于基B1和B2的基本解，它们是否基本可行解？59上二组概念间的联系：系数阵A中可找出若干个基B每个基B都对应于一个基本解非负的基本解就是基本可行解几种解之间的关系：可行解基本解非可行解基本可行解问题：基本可行解是可行域中的哪些点？601.找出下述线性规划问题的全部基解，指出其中的基可行解，并确定最优解。maxZ=2x1+3x2 x1 +x35 x1+2x2 +x4 10 x2 +x5 4 xi 061解：x1x2x3x4x5Z是否为基可行解1005104520452017350054104055012051005 0415652.5001.517.575403 02282430019最优解为x1 2，x24，x3 3，Z19621.6 解的可行性和松弛变量符号的关系A(1,2.5)B(2,1)C(1.5,3)max z=2x1+3x2s.t.x1+x24 (1)-x1+x21 (2)x1,x20max z=2x1+3x2s.t.x1+x2+x3 =4 -x1+x2 -x4=1 x1,x2,x3,x40引进松弛变量约束条件(1)约束条件(2)D(3,2)A(1,2.5)满足所有约束条件，x3=0.5,x4=0.5B(2,1)满足(1)，不满足(2)，x3=1,x4=-2C(1.5,3)不满足(1),满足(2)，x3=-0.5,x4=0.5D(3,2)不满足(1)和(2)，x3=-1,x4=-2结论：如果一个解满足一个约束条件，相应的松弛变量大于等于0。如果一个解不满足一个约束条件，相应的松弛变量小于0。0 1 2 3 4-14321x2x163max z=x1+2x2s.t.x1+x23 x2 1 x1,x2 0max z=x1+2x2s.t.x1+x2+x3 =3 x2 +x4=1 x1,x2,x3,x40 x1=0,x2=0 x3=3,x4=1基可行解x1=0,x4=0 x2=1,x3=2基可行解x2=0,x3=0 x1=3,x4=1基可行解x3=0,x4=0 x1=2,x2=1基可行解x1=0,x3=0 x2=3,x4=-2是基解，但不是可行解OABx3=0 x4=0 x2=0 x1=0CD可行域64第2节 线性规划问题的几何意义1.凸集 如果集合C中任意两点x1，x2，其连线上的所有点也都是集合C中的点，则称C为凸集，其中x1，x2的连线可以表示为：x1（1）x2(0 1)数学解析式为：x1 C，x2 C，有x1（1）x2C (0 1)，则C为凸集。2.1基本概念652.极点 如果集合C中任意两点x1，x2，使x为这两点连线上的一个点，对任何x1 C，x2 C，不存在 x=x1（1）x2(0 1)，则称x为凸集的顶点。3.凸组合P16662.2 几个基本定理定理1：若线性规划问题存在可行解，则问题的可行域是凸集引理：线性规划问题的可行解X(x1,x2,xn)为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的（所组成的矩阵是非奇异的）。定理2：线性规划问题的基可行解X对应线性规划问题可行域的顶点。定理3：若线性规划问题有最优解，一定存在一个基可行解是最优解。67第3节 单纯形法maxZ=6x1+5x2 x1+3x290 2x1+x275 2x1+2x2 80 x1,x20maxZ=6x1+5x2 x1+3x2+x390 2x1+x2 +x4 75 2x1+2x2 +x580 xi0找一个基可行解，X（0，0，90，75，80），Z=01）Z6x1+5x2，x1的系数C16大于C2=5；选择x1为新的基变量。X3=90-(x1+3x2)当x3=0，X2=0时，x1=90 选择x4为X4=75-(2x1+x2)当x4=0，X2=0时，x1=37.5 换出变量，X5=80-(2x1+2x2)当x5=0，X2=0时，x1=40 即x4 0最小3.1举例683）Z225+2x2-3x4，x2的系数C22大于0；选择x2为新的基变量。X3=52.5-(2.5x2-0.5x4)当x3=0，x4=0时，x2=21 X1=75/2-(0.5x2+0.5x4)当x1=0，x4=0时，x2=75 X5=5-(x2-x4)当x5=0，x4=0时，x2=5 所以选择x5为换出变量,x2为换入变量 最小则X（37.5，0，52.5，0，5）T，Z2252X2-3X42）仍然用非基变量表示基变量X3=52.5-(2.5x2-0.5x4)X1=75/2-(0.5x2+0.5x4)X5=5-(x2-x4)Z225+2x2-3x4694)用非基变量表示基变量X3=40-(1.5x4-2.5x5)X1=35-(x4-0.5x5)X2=5-(x5-x4)Z235-x4-2x5 则X（35，5，40，0，0）T，Z235-x4-2x5 为最优解70（1）线性规划模型为标准形式（2）约束条件系数矩阵中至少有一个单位子矩阵（3）目标函数中不含基变量这样的线性规划模型称为规范型71线性规划基本概念练习（1）036x1x2OABCEFGHI46-2min z=-x1+2x2s.t.3x1+2x212(1)x1+2x2 6(2)-2x1+x2 4(3)x1,x2 01、约束条件（1）对应的直线是（），对应的半平面是 约束条件（2）对应的直线是（），对应的半平面是 约束条件（3）对应的直线是（），对应的半平面是2、这个线性规划的可行域是（）。3、对于z=2和4,分别画出目标函数等值线。4、这个线性规划的最优解位于（）。ACEFBCDHEGHICDGEz=2z=4CD4721.确定初始基可行解 由于基可行解是由一个可行基决定的，因此，确定初始基可行解X0相当于确定一个初始可行基B0。方法：若A中含I，则B0=I；若A中不含I，则可用人工变量法构 造一个I。问题：若B0=I，则X0=？3.2单纯形法的步骤732.最优性检验问题：用什么检验？目标。问题：非最优的特征为何？743.寻找更好的基可行解 由于基可行解与基对应，即寻找一个新的基可行解，相当于从上一个基B0变换为下一个新的基B1，因此，本步骤也称为基变换。（基变换）进基出基754.迭代76 以下面模型为例，可按上述单纯形法的步骤求出其最优解，其大致的过程如下。（1）先将模型化为标准型(2)确定初始基可行解、检验77（3）换基、计算下一个基可行解、再检验，直至最优问题：当模型规模较大时，计算量很大。事实上，单纯形法的实现是在单纯形表上完成的。78第4节单纯形法的计算步骤单纯形表 单纯形表是基于单纯形法的步骤设计的计算格式，是单纯形法的具体实现。回顾单纯形法步骤79单纯形表的主要结构：问题：第一张表的B-1=？单位阵I。检验数的公式是什么？80单纯形表求解线性规划问题maxZ=6x1+5x2 x1+3x290 2x1+x275 2x1+2x2 80 x1,x20maxZ=6x1+5x2 x1+3x2+x390 2x1+x2 +x4 75 2x1+2x2 +x580 xi081cj65000CBXBbx1x2x3x4x50 x390131000 x475210100 x58022001cj-zj6500082cj65000CBXBbx1x2x3x4x50 x390131000 x475210100 x58022001cj-zj6500083cj65000CBXBbx1x2x3x4x50 x3901310090/10 x4752101075/20 x5802200180/2cj-zj65000所以把x4换出为非基变量，x1为换入变量即新的基变量。84cj65000CBXBbx1x2x3x4x50 x3901310090/10 x4752101075/20 x5802200180/2cj-zj650006x175/211/201/2085cj65000CBXBbx1x2x3x4x50 x3901310090/10 x4752101075/20 x5802200180/2cj-zj650000 x3105/205/21-1/206x175/211/201/2086cj65000CBXBbx1x2x3x4x50 x3901310090/10 x4752101075/20 x5802200180/2cj-zj650000 x3105/205/21-1/206x175/211/201/200 x55010-1187cj65000CBXBbx1x2x3x4x50 x3901310090/10 x4752101075/20 x5802200180/2cj-zj650000 x3105/205/21-1/206x175/211/201/200 x55010-11cj-zj020-3088cj65000CBXBbx1x2x3x4x50 x3901310090/10 x4752101075/20 x5802200180/2cj-zj650000 x3105/205/21-1/20216x175/211/201/20750 x55010-115cj-zj020-30所以把x5换出为非基变量，x2为换入变量即新的基变量。89cj65000CBXBbx1x2x3x4x50 x3901310090/10 x4752101075/20 x5802200180/2cj-zj650000 x3105/205/21-1/20216x175/211/201/20750 x55010-115cj-zj020-305x25010-1190cj65000CBXBbx1x2x3x4x50 x3901310090/10 x4752101075/20 x5802200180/2cj-zj650000 x3105/205/21-1/20216x175/211/201/20750 x55010-115cj-zj020-300 x3400012-5/25x25010-1191cj65000CBXBbx1x2x3x4x50 x3901310090/10 x4752101075/20 x5802200180/2cj-zj650000 x3105/205/21-1/20216x175/211/201/20750 x55010-115cj-zj020-300 x3400012-5/26x1351001-1/25x25010-1192cj65000CBXBbx1x2x3x4x50 x3901310090/10 x4752101075/20 x5802200180/2cj-zj650000 x3105/205/21-1/20216x175/211/201/20750 x55010-115cj-zj020-300 x3400012-5/26x1351001-1/25x25010-11cj-zj000-1-2此时所有的检验数都小于等于0，所以该解为最优解。最优解为X（35，5，40，0，0）T，Z*23593练习：对于下面的线性规划（1）用图解法求解；（2）将模型化为标准型；（3）用单纯形法步骤求出其最优解，并指出求 解过程中每一个基可行解相当于可行域的 哪一个角点。94Step 0 获得一个初始的单纯形表，确定基变量和非基变量Step 1 检查基变量在目标函数中的系数是否等于0，在约束条件中的系数是否是一个单位矩阵。Step 2 如果表中非基变量在目标函数中的系数全为负数，则已得到最优解。停止。否则选择系数为正数且绝对值最大的变量进基，转step 3。Step 3 如果进基变量在约束条件中的系数全为负数或0，则可行域开放，目标函数无界。停止。否则选取右边常数和正的系数的最小比值，对应的基变量离基，转step 4。Step 4 确定进基变量的列和离基变量的行交叉的元素为“主元”，对单纯形表进行行变换，使主元变为1，主元所在列的其他元素变为0。将离基的基变量的位置用进基的非基变量代替。转Step 2。单纯形表的算法描述951.maxZ=3x1+9x2 x1+3x221 -x1+x24 x1,x20maxZ=3x1+9x2 x1+3x2+x321 -x1+x2 +x4 4 xi0举例cj3900CBXBbx1x2x3x40 x32113100 x44-1101cj-zj390096cj3900CBXBbx1x2x3x40 x321131070 x44-11014cj-zj3900所以把x4换出为非基变量，x2为换入变量即新的基变量。97cj3900CBXBbx1x2x3x40 x321131070 x44-11014cj-zj39009x24-1101498cj3900CBXBbx1x2x3x40 x321131070 x44-11014cj-zj39000 x39401-39x24-110199cj3900CBXBbx1x2x3x40 x321131070 x44-11014cj-zj39000 x39401-39x24-1101cj-zj1200-9100cj3900CBXBbx1x2x3x40 x321131070 x44-11014cj-zj39000 x39401-39/49x24-1101-cj-zj1200-9所以把x3换出为非基变量，x1为换入变量即新的基变量。101cj3900CBXBbx1x2x3x40 x321131070 x44-11014cj-zj39000 x39401-39/49x24-1101-cj-zj1200-93x19/4101/4-3/4102cj3900CBXBbx1x2x3x40 x321131070 x44-11014cj-zj39000 x39401-39/49x24-1101-cj-zj1200-93x19/4101/4-3/49x225/4 011/41/4103cj3900CBXBbx1x2x3x40 x321131070 x44-11014cj-zj39000 x39401-39/49x24-1101-cj-zj1200-93x19/4101/4-3/49x225/4011/41/4cj-zj00-30此时所有的检验数都小于等于0，所以该解为最优解。最优解为X（9/4，25/4，0，0）T，Z*63由于非基变量x4的检验数0，所以我们可以把它作为换入基变量来考虑。104cj3900CBXBbx1x2x3x40 x321131070 x44-11014cj-zj39000 x39401-39/49x24-1101-cj-zj1200-93x19/4101/4-3/4-9x225/4011/41/425cj-zj00-30105cj3900CBXBbx1x2x3x40 x321131070 x44-11014cj-zj39000 x39401-39/49x24-1101-cj-zj1200-93x19/4101/4-3/4-9x225/4011/41/425cj-zj00-300 x4250411106cj3900CBXBbx1x2x3x40 x321131070 x44-11014cj-zj39000 x39401-39/49x24-1101-cj-zj1200-93x19/4101/4-3/4-9x225/4011/41/425cj-zj00-303x12113100 x4250411107cj3900CBXBbx1x2x3x40 x321131070 x44-11014cj-zj39000 x39401-39/49x24-1101-cj-zj1200-93x19/4101/4-3/4-9x225/4011/41/425cj-zj00-303x12113100 x4250411cj-zj00-30此时所有的检验数都小于等于0，所以该解为最优解。Z*=631081.maxZ=x1+x2 -2x1+x24 x1-x22 x1,x20maxZ=x1+x2 -2x1+x2+x34 x1-x2 +x4 2 xi0举例cj1100CBXBbx1x2x3x40 x34-21100 x421-101cj-zj1100109cj1100CBXBbx1x2x3x40 x34-211040 x421-101-cj-zj1100所以把x3换出为非基变量，x2为换入变量即新的基变量。110cj1100CBXBbx1x2x3x40 x34-211040 x421-101-cj-zj11001x24-2110111cj1100CBXBbx1x2x3x40 x34-211040 x421-101-cj-zj11001x24-21100 x46-1011112cj1100CBXBbx1x2x3x40 x34-211040 x421-101-cj-zj11001x24-21100 x46-1011cj-zj30-10113cj1100CBXBbx1x2x3x40 x34-211040 x421-101-cj-zj11001x24-21100 x46-1011cj-zj30-10可以看出，的检验数为3，大于0，但是的系数列向量中的所有原数（-2,-1）T，都小于0，所以该题为无界解。114练习：用单纯形法求解问题：标准模型的A中是否含I？松弛变量系数恰好构成I。115 中表示进基列与出基行的交叉元，下一张表将实行以它为主元的初等行变换（称高斯消去）。方法是：先将主元消成1，再用此1将其所在列的其余元消成0。116 （请解释其实际意义）117第5节 单纯形法的进一步讨论5.1 人工变量法1.大M法约束条件：“”加一个剩余变量后，再加一个人工变量“”加一个人工变量目标函数：人工变量的系数为“M”，即罚因子若线性规划问题有最优解则人工变量必为0。118MaxZ=3x1-x2-x3 x1-2x2+x311 -4x1+x2+2x33 -2x1 +x3=1 xi 0MaxZ=3x1-x2-x3+0 x4+0 x5-Mx6-Mx7 x1-2x2+x3+x4=11 -4x1+x2+2x3 -x5+x6=3 -2x1 +x3 +x7=1 xi 0增加人工变量后，线性规划问题中就存在一个B为单位矩阵，后面可以根据我们前面所讲的单纯形法来进行求解。119cj3-1-100-M-MCBXBbX1X2X3X4X5X6X70X4111-211000-MX63-4120-110-MX71-2010001cj-zj3-6M-1+M-1+3M0-M00120cj3-1-100-M-MCBXBbX1X2X3X4X5X6X70X4111-21100011-MX63-4120-1103/2-MX71-20100011cj-zj3-6M-1+M-1+3M0-M00121cj3-1-100-M-MCBXBbX1X2X3X4X5X6X70X4111-21100011-MX63-4120-1103/2-MX71-20100011cj-zj3-6M-1+M-1+3M0-M00-1X31-2010001122cj3-1-100-M-MCBXBbX1X2X3X4X5X6X70X4111-21100011-MX63-4120-1103/2-MX71-20100011cj-zj3-6M-1+M-1+3M0-M000X4103-20100-1-1X31-2010001123cj3-1-100-M-MCBXBbX1X2X3X4X5X6X70X4111-21100011-MX63-4120-1103/2-MX71-20100011cj-zj3-6M-1+M-1+3M0-M000X4103-20100-1-MX610100-11-2-1X31-2010001124cj3-1-100-M-MCBXBbX1X2X3X4X5X6X70X4111-21100011-MX63-4120-1103/2-MX71-20100011cj-zj3-6M-1+M-1+3M0-M000X4103-20100-1-MX610100-11-2-1X31-2010001cj-zj1-1+M00-M01-3M125cj3-1-100-M-MCBXBbX1X2X3X4X5X6X70X4111-21100011-MX63-4120-1103/2-MX71-20100011cj-zj3-6M-1+M-1+3M0-M000X4103-20100-1-MX610100-11-21-1X31-2010001-cj-zj-1-1+M00-M01-3M126cj3-1-100-M-MCBXBbX1X2X3X4X5X6X70X4111-21100011-MX63-4120-1103/2-MX71-20100011cj-zj3-6M-1+M-1+3M0-M000X4103-20100-1-MX610100-11-21-1X31-2010001-cj-zj-1-1+M00-M01-3M-1X210100-11-2127cj3-1-100-M-MCBXBbX1X2X3X4X5X6X70X4111-21100011-MX63-4120-1103/2-MX71-20100011cj-zj3-6M-1+M-1+3M0-M000X4103-20100-1-MX610100-11-21-1X31-2010001-cj-zj-1-1+M00-M01-3M0X4123001-22-5-1X210100-11-2128cj3-1-100-M-MCBXBbX1X2X3X4X5X6X70X4111-21100011-MX63-4120-1103/2-MX71-20100011cj-zj3-6M-1+M-1+3M0-M000X4103-20100-1-MX610100-11-21-1X31-2010001-cj-zj-1-1+M00-M01-3M0X4123001-22-5-1X210100-11-2-1X31-2010001129cj3-1-100-M-MCBXBbX1X2X3X4X5X6X70X4111-21100011-MX63-4120-1103/2-MX71-20100011cj-zj3-6M-1+M-1+3M0-M000X4103-20100-1-MX610100-11-21-1X31-2010001-cj-zj-1-1+M00-M01-3M0X4123001-22-5-1X210100-11-2-1X31-2010001cj-zj1000-1-M+1-M-1130cj3-1-100-M-MCBXBbX1X2X3X4X5X6X70X4111-21100011-MX63-4120-1103/2-MX71-20100011cj-zj3-6M-1+M-1+3M0-M000X4103-20100-1-MX610100-11-21-1X31-2010001-cj-zj-1-1+M00-M01-3M0X4123001-22-54-1X210100-11-2-1X31-2010001-cj-zj1000-1-M+1-M-1131cj3-1-100-M-MCBXBbX1X2X3X4X5X6X70X4123001-22-54-1X210100-11-2-1X31-2010001-cj-zj1000-1-M+1-M-13X141001/3-2/32/3-5/3132cj3-1-100-M-MCBXBbX1X2X3X4X5X6X70X4123001-22-54-1X210100-11-2-1X31-2010001-cj-zj1000-1-M+1-M-13X141001/3-2/32/3-5/3-1X210100-11-2133cj3-1-100-M-MCBXBbX1X2X3X4X5X6X70X4123001-22-54-1X210100-11-2-1X31-2010001-cj-zj1000-1-M+1-M-13X141001/3-2/32/3-5/3-1X210100-11-2-1X390012/3-4/34/3-7/3134cj3-1-100-M-MCBXBbX1X2X3X4X5X6X70X4123001-22-54-1X210100-11-2-1X31-2010001-cj-zj1000-1-M+1-M-13X141001/3-2/32/3-5/3-1X210100-11-2-1X390012/3-4/34/3-7/3cj-zj000-1/3-1/3-M+1/3-M+2/3此时所有的检验数都小于等于0，所以该解为最优解。最优解为X（4，1，9，0，0，0，0）T，Z*21352.两阶段法第一阶段在不考虑原问题是否存在基可行解，给原问题加入人工变量，并构建一个仅含人工变量的目标函数（求极小化），人工变量的系数一般为1，约束条件和原问题的一样。当第一阶段中目标函数的最优值0，既人工变量0，则转入第二阶段；若第一阶段中目标函数的最优值不等于0，既人工变量不等于0，则判断原问题为无解。第二阶段：将第一阶段计算所得的单纯形表划去人工变量所在的列，并加目标函数换为原问题的目标函数作为第二阶段的初始单纯形表，进行进一步的求解。136MaxZ=3x1-x2-x3 x1-2x2+x311 -4x1+x2+2x33 -2x1 +x3=1 xi 0MinZ=x6+x7 x1-2x2+x3+x4=11 -4x1+x2+2x3 -x5+x6=3 -2x1 +x3 +x7=1 xi 0增加人工变量后，线性规划问题中就存在一个B为单位矩阵，后面可以根据我们前面所讲的单纯形法来进行求解。137cj0000011CBXBbX1X2X3X4X5X6X70X4111-2110001X63-4120-1101X71-2010001cj-zj6-1-30100138cj0000011CBXBbX1X2X3X4X5X6X70X4111-21100011-MX63-4120-1103/2-MX71-20100011cj-zj6-1-30100139cj0000011CBXBbX1X2X3X4X5X6X70X4111-211000111X63-4120-1103/21X71-20100011cj-zj6-1-301000X4103-20100-11X610100-11-20X31-2010001140cj0000011CBXBbX1X2X3X4X5X6X70X4111-211000111X63-4120-1103/21X71-20100011cj-zj6-1-301000X4103-20100-1-1X610100-11-210X31-2010001-cj-zj0-100103141cj0000011CBXBbX1X2X3X4X5X6X70X4111-211000111X63-4120-1103/21X71-20100011cj-zj6-1-301000X4103-20100-1-1X610100-11-210X31-2010001-cj-zj0-1001030X4123001-22-50X210100-11-20X31-2010001142cj0000011CBXBbX1X2X3X4X5X6X70X4111-211000111X63-4120-1103/21X71-20100011cj-zj6-1-301000X4103-20100-1-1X610100-11-210X31-2010001-cj-zj0-1001030X4123001-22-50X210100-11-20X31-2010001cj-zj0000011可以看到人工变量x6，x7均为0，所以构造的目标函数w=0，因此可以判断该线性规划问题有可行解，可以进行第二阶段的计算。143maxz=3x1 -x2-x3 s.t.x1-2x2+x3+x4=11 -4x1+x2+2x3-x5=3 -2x1 +x3=1 xj0cj3-1-100CBXBbX1X2X3X4X50X4123001-2-1X210100-1-1X31-20100cj-zj1000-1144cj-zj3-1-100CBXBbX1X2X3X4X50X4123001-24-1X210100-1-1X31-2010