运筹学第四版线性规划及单纯形法.pptx

线性规划及 单纯形法线性规划及单纯形法v线性规划问题及其数学模型v图解法v单纯形法原理v单纯形法的计算步骤第一节 线性规划问题及其数学模型一、问题的提出线性规划主要解决：如何利用现有有限的资源，使得预期目标达到最优的问题。例1 某工厂在计划期内要安排生产A、B两种产品（假定产品畅销）。已知生产单位产品的利润与所需的劳动力、设备台时及原材料的消耗，如表1.1所示问该厂应如何安排生产使获利最大？表1-1产品A产品B资源限量劳动力设 备原材料9434510360200300利润元/kg70120问题要求给出一个方案(产品A生产多少；产品B生产多少)设该工厂生产A、B两种产品产量分别为确定决策变量表1-1产品A产品B资源限量劳动力设 备原材料9434510360200300利润元/kg70120制定方案的目标是什么？该厂获取的利润可表示为 问题的目标：确定目标函数利润最大化表1-1产品A产品B资源限量劳动力设 备原材料9434510360200300利润元/kg70120方案的制定受到那些现实条件制约：人力资源（劳动力）的限制：设备工时的限制：原材料资源的限制：此外，决策变量的取值不应为负值即确定约束条件其中目标函数约束条件资源约束非负约束约束条件可记 s.t (subject to),意思为“以为条件“、”假定“、”满足“之意。综上所述，我们得到了这个问题的数学模型建立问题的线性规划模型步骤1 确定决策变量决策变量是模型所要决定的未知量，也是模型最重要的参数它用以表明规划中的用数量表示的方案、措施，可由决策者决定和控制2 确定目标函数就是将决策者所追求的目标表示为决策变量的函数它决定了线性规划优化的方向，是线性规划的重要组成部分3 确定约束条件这些约束条件可用含有决策变量的等式或不等式来表示例2 给海狸鼠配饲料饲料中营养要求：Va每天至少700克，Vb每天至少30克，VC每天刚好200克。现有五种饲料，搭配使用，饲料成分如下表：饲料VaVbVc价格元/KG 资源量IIIIIIIVV32161810.50.220.50.510.220.8274955060507040营养要求70030200问：应如何搭配饲料，使费用最小？v确定决策变量：设抓取饲料I x1kg;饲料II x2kg;饲料III x3kgv确定目标函数：minZ=2x1+7x2+4x3+9x4+5x5v确定约束条件：3x1+2x2+x3+6x4+18x5 700 x1+0.5x2+0.2x3+2x4+0.5x5 30 0.5x1+x2+0.2x3+2x4+0.8x5=200 x1 50,x2 60,x3 50,x4 70,x5 40 x1 0,x2 0,x3 0,x4 0,x5 0 营养要求用量要求非负约束综上所述，便得到如下的数学模型：美佳公司计划制造、两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试工序及每天可用于这两种家电的能力、各售出一件时的获利情况，如表1-2所示。问该公司应制造两种家电各多少件，使获取的利润最大？课堂练习项目每天可用能力设备A(h)设备B(h)调试工序(h)06152115245利润（元）21表1-2其数学模型为：例3：捷运公司在下一年度的14月份的4个月内拟租用仓库堆放物资。已知各月份所需仓库面积列于下表1-3。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表1-4。租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。因此该厂可根据需要，在任何一个月初办理租借合同。每次办理时可签一份合同，也可签若干份租用面积和租用期限不同的合同。试确定该公司签订租借合同的最优决策，目的是使所租借费用最少。月份 1 2 3 4所需仓库面积15 10 20 12表1-3表1-4合同租借期限 1个月 2个月 3个月 4个月合同期内的租费2800 4500 6000 7300单位：100m2单位；元/100m2月份 1 2 3 4所需仓库面积15 10 20 12表1-2表1-3合同租借期限 1个月 2个月 3个月 4个月合同期内的租费2800 4500 6000 7300单位：100m2单位；元/100m2解：设 表示捷运公司在第i(i=1,2,3,4)月初签订的租期为j (j=1,2,3,4)个月的仓库面积的合同（单位为100m2)。15102012经过上面的讨论，得到下面的LP模型：目标函数约束条件每一个问题都有一组变量-称为决策变量，一般记为下面从数学的角度来归纳上述三个例子的共同点。每个问题中都有决策变量需满足的一组约束条件-线性的等式或不等式。对决策变量每一组值：代表了一种决策方案。通常要求决策变量取值非负，即二。线性规划问题的数学模型 都有一个关于决策变量的线性函数-称为目标函数。要求这个目标函数在满足约束条件下实现最大化或最小化。我们将约束条件和目标函数都是决策变量的线性函数的规划问题称为线性规划。有时也将线性规划问题简记为LP（linear programming)其数学模型为：上述模型的简写形式为：若令线性规划问题可记为矩阵和向量的形式：用向量表示时，上述模型可写为：三。线性规划问题的标准形式：LP问题的数学模型的标准形式为：其中常数项 LP问题标准形式的特征是：求目标函数的最大值；约束条件为等式；决策变量非负。下面分析如何将LP问题标准化：若目标函数为引进新的目标函数则的最小值即为的最大值，即：从而目标函数变换为：（2）若约束条件为不等式，分为两种情况讨论：加入松弛变量加入剩余变量（3）对于决策变量非负的要求，分为两种情况讨论：非正变量：即xk 0 令xk=-xk即可自由变量：即xk无约束 令xk=xkxk例1 将LP问题化为标准形。解：引进新的目标函数于是原LP问题化为标准形式：例2 将LP问题化为标准形。松弛变量例3 将LP问题化为标准形。剩余变量例4 将LP问题化为标准形。课堂练习例4 将LP问题化为标准形。我们得到例4的标准形为：1.2 线性规划问 题的图解法1.2线性规划图解法v所谓图解法，就是在平面直角坐标上画出各个约束条件所允许变化的范围，通过图上作业法求出最优解和目标函数值。一个线性规划问题有解，是指能找出一组xj(j=1,2,n),满足所有约束条件，称这组xj为问题的可行解。通常线性规划问题总是含有多个可行解，称全部可行解的集合为可行域。在用图解法求解时，可形象的看到可行域。在可行域中使目标函数值达到最优的可行解称为最优解对不存在可行解的线性规划问题，称该问题无解图解法背景知识图解法背景知识由中学知识可知：y=ax+b是一条直线。同理(如果Z值固定)Z=70 x1+120 x2x2=-70/120 x1+Z/120也是一条直线x2=-70/120 x1+Z/120也是一组平行的等值线1.2.1图解法的步骤v1、建立直角坐标系；v2、根据约束条件描绘可行域；v3、作目标函数的等高线；v4、求解最优点和最优目标函数值。例题1生产计划问题v某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：产品A产品B资源限量劳动力设 备原材料9434510360200300利润元/kg70120问题：如何安排生产计划，使得获利最多？例1 图解法.90 80 60 40 20 0 20 40 60 80 100 x1 x29x1+4x2 3604x1+5x2 200 3x1+10 x2 300Z=70 x1+120 x2maxZ=70X1+120X2 9X1+4X2360 4X1+5X2 200 3X1+10X2 300 X10 X20最优解(20,24),Z=4280可行域课堂练习用图解法求解下述线性规划问题。1）2）3）答案：1）2）3）x1=1,x2=1.5 Z*=17.5x1=15/4,x2=3/4 Z*=33/4x1=2,x2=6 Z*=361.2.2求解的几种可能结局v1、无穷多最优解。v2、唯一最优解。v2、无界解。v3、无解或无可行解。解的可能性 v多重最优解：无穷多个最优解。若在两个顶点同时得到最优解，则它们连线上的每一点都是最优解。v唯一最优解：只有一个最优点。x1=82x2=123x1+4 x2=36x1x248123690 0A AB BC(4,6C(4,6)D D例例1的数学模型变为的数学模型变为 maxZ=3x1+4 x2 x1 8 2x2 12 3x1+4 x2 36 x1 0,x2 0S.t.Z=24Z=36Z=12解的可能性解的可能性v无界解：线性规划问题的可行域无界，使目标函数无限增大而无界。（缺乏必要的约束条件）例如例如 maxZ=3x1+2 x2 -2x1+x2 2 x1-3 x2 3 x1 0,x2 0-2x1+x2=2x1-3 x2=3x2123-1x1123-1Z=6Z=12S.t.解的可能性解的可能性v无可行解：若约束条件相互矛盾，则可行域为空集例如例如 maxZ=3x1+2 x2 -2x1+x2 2 x1-3 x2 3 x1 0,x2 0-2x1+x2=2x1-3 x2=3x2123-1x1123-1S.t.由图解法得到的启示图解法虽然只能用来求解只具有两个变量的线性规划问题，但它的求解思路和几何上直观得到的一些概念判断，对于单纯形法有很大启示1、求解线性规划问题时，解的情况有：唯一最优解；无穷多最优解；无界解；无可行解2、若线性规划问题的可行解存在，则可行域是一个凸集3、若线性规划问题的最优解存在，则最优解或最优解之一一定是可行域的凸集的某个顶点。由图解法得到的启示4、解题思路是：先找出凸集的任一顶点，计算在顶点处的目标函数值。比较周围相邻顶点的目标函数值是否比这个值大，如果为否，则该顶点就是最优解的点或最优解的点之一；否则转到比这个点的目标函数值更大的另一个顶点，重复上述过程，一直到找出使目标函数值达到最大的顶点为止。1.3 单纯形法 原 理数学试验LINDO软件包LINDO软件包介绍v初试LINDOv用LINDO求解整数规划v注意事项LINDO是一种专门用于求解数学规划问题的优化计算软件包,版权现在由美国 LINDO系统公司(Lindo System Inc.)所拥有.LINDO软件包的特点是程序执行速度很快,易于输入、修改、求解和分析一个数学规划(优化问题),因此LINDO在教育、科研和工业界得到广泛应用.有关该软件的发行版 本、发行价格和其他最新信息都可以从LINDO系统公司的INTERNET 网络站点http:/获取,该站点还提供部分LINDO软件的演示版本或测试版本学生版和演示版与发行版的主要区别在于对优化问题的规模(变量和约束数)有不同的限制.LINDO是Linear Interactive and Discrete Optimizer 字首的缩写形式,可以用来求解线性规划(LP-Linear Programming)、整数规划(IP-Integer Programming)和 二次规划(QP-Quadratic Programming)问题.LINDO学生版可求解多达 200 个变量和100个约束的规划问题.初试 LINDO如解如下LP 问题:LINDO 中己假设所有的变量都是非负的,所以非负约束条件不必再输入到计算机中;LINDO 也不区分变量中的大小写字符(实际上任何小写字符都将被转换为大写字符);约束条件中的“=”可用“”代替.上述问题用键盘输入如下:：MAX 2X+3Y?ST(说明:也可写成S.T.,SUCH THAT 或 SUBJECT TO 等）?4X+3Y10?3X+5Y12?END：注：目标函数为第1行,两个约束条件分别为第2,3行.直接键入运行命令(GO)就可得到解答,屏幕显示如下:GO LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1）7.4545450VARIABLE VALUE REDUCED COST X 1.272727 .000000Y 1.636364 .000000ROW SLACK OR SURPLUS DUAL PRICES 2).000000 .090909 3).000000 .545455 NO.ITERATIDNS=2 DO RANGE(SENSITIVITY)ANALYSIS?单纯形法在2次迭代后得到最优解。最优目标值最优解：:GO LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1）7.4545450VARIABLE VALUE REDUCED COST X 1.272727 .000000 Y 1.636364 .000000ROW SLACK OR SURPLUS DUAL PRICES 2）.000000 .090909 3）.000000 .545455 NO.ITERATIDNS=2 DO RANGE(SENSITIVITY)ANALYSIS?单纯形进行了2次迭代带有松弛变量和剩余变量的最优解：检验数减少的成本对偶价格一个问题解答之后,LINDO会询问是否需要作灵敏度分析(DO RANGE(SENSITIVITY)ANALYSIS?).如果不需要,你应回答 N(No),回到提示符:之下.如果想重新看到刚才输入的模型,可键入 LOOK命令,LINDO 会询问具体的行号范围(也可直接将行号范围写在LOOK后).典型的行号范围可以是3,或1-2,或ALL,而结果相应地会显示出第3行、第1-2行,或问题的所有行.如:LOOK ROW:3 (等价于直接命令“LOOK3”)3)3X+5Y=12:如果想修改问题,可键入ALTER命令,LINDO会询问行号,变量名及新的系数,例如:若想将上述问题中约束条件4x+3y 10,修改为6x+3y10,然后再全部看一下,并求解新问题,那么键入ALTER命令后相应要键入2,X,6然后再键入:“LOOK ALL”.在相应位置再键入“GO”，就会给出解答.以下是屏幕上演示过程:：ALTER ROW：2 VAR：XNEW COEFFICIENT：6 (等价于直接命令“ALTER2X6”）:LOOK ALLMAX 2X+3YSUBJECT TO2)6X+3Y=103）3X+5Y=12END:GOLP OPTIMUM FOUND AT STEP O OBJECTIVE FUNCTION VALUE 1)7.333333VARIABLE VALUE REDUCED COSTX .666667 .000000Y 2.0000 .000000ROWSLACK OR SURPLUS DUAL PRICES 2).000000 .047619 3).000000 .571429NO.ITERATIONS=0DO RANGE(SENSITIVITY)ANALYSIS?N:QUIT改动约束条件的右端项,可以将RHS(即right-hand side)作为变量名.改变约束条件中的不等号方向(如,可以将DIR作为变量名.修改问题还可用EXT命令(增加新的约行),DEL命令(去掉一行)和APPC 命令(增加一个新的变量),也可用EDIT全屏幕编辑器.灵 敏 度 分 析下面用一个具体例子来说明 LINDO 软件求对偶变量及进行灵敏度分析.例 有一家具制造车间,制造书桌(DESK)、桌子(TABLE)、椅子(CHAIR),所用原料及木工、漆工的数据如表1所示.每个书桌每个桌子每个椅子资源总数术料8单位6单位1单位48单位漆工4单位2单位1.5单位20单位木工2单位1.5单位0.5单位8单位成品单价 60单位30单位20单位表 1若要求桌子的生产量不超过 5 件,问如何安排三种产品的产量可使收入最大?用 分别表示书桌、桌子、椅子的生产量.建立LP 模型:将上述模型输入LINDO并求解:：MAX 6OX1+3OX2+2OX3?S.T?2)8X1+6X2+x348?3)4XI+2X2+1.5X3 20?4)2XI+1.5X2+0.5X3 8?5)X2 5?END:GOLP OPTIMUM FOUND AT STEP 2OBJECTIVE FUNCTION VALUE1)280.00000VARIABLE VALUE REDUCED COSTXI 2.000000 .000000X2 .000000 5.000000X3 8.000000 .000000 ROW SLACK OR SURPLUS DUAL PRICES 2)24.000000 .000000 3).000000 10.000000 4).000000 10.000000 5)5.000000 .000000LINDO在2次迭代后得到最优解。最优目标值最优解带有松弛变量的最优解检验数NO.ITERATIONS=2 DO RANGE(SENSITIVITY)ANALYSIS?YRANGES IN WHICH THE BASIS IS UNCHANGED.OBJ COEFFICIENT RANGESVARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE Xl 60.000000 20.000000 4.000000 X2 30.000000 5.000000 INFINITY X3 20.000000 2.500000 5.000000价值系数ciC1在区间60-4,60+20=56,80的范围内变化时，最优基保持不变（最优解的值也不变，但最优值可能要改变）。30-，30+5=（-，35是否需要作灵敏度分析？RIGHT HAND SIDE RANGESROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 48.000000 INFINITY 24.000000 3 20.000000 4.000000 4.000000 4 8.000000 2.000000 1.333333 5 5.000000 INFINITY 5.000000约束行的右端项值在什么范围内变化，最优基保持不变。右端项值第5行约束（即第4个约束方程），右端项当前值为5，允许增加为，允许减少值为5，即当其右端项旨在5-5，5+=0，）内变化时，最优基不变（最优值及最优解的值可能要变）若需要显示单纯形表,可执行TABLEAU命令.:TABLEAU THE TABLEAUROW(BASIS)x1 x2 x3 SLK2 SLK3 SLK4 SLK5 1 ART 0 5.0 0 0 10.0 10.0 0 280.02 SLK2 0 -2.0 0 1.0 2.0 -8.0 0 24.0 3x3 0 -2.0 1.0 0 2.0 -4.0 0 8.04 x1 1.0 1.25 0 0 -5.0 1.5 0 2.0 5 SLK5 0 1.0 0 0 0 0 1.0 5.0检验行右端项值基向量Z最优解：含有所有变量的最优解：注意LINDO软件在使用单纯形法时,目标函数行使用的公式是:而我们第2章中使用的公式是:因此它的检验数值与我们第2章中介绍的差一个符号。线性规划及单纯形法v线性规划问题及其数学模型v图解法v单纯形法迭代原理v单纯形法的计算步骤单纯形法原理预备例1 某工厂在计划期内要安排生产A、B两种产品（假定产品畅销）。已知生产单位产品的利润与所需的劳动力、设备台时及原材料的消耗，如表1.1所示问该厂应如何安排生产使获利最大？由于单纯形法是基于代数演算的方法，所以在对例1进行讨论时，应将其转换为标准形。可行解:(20,20)、(40,0)非可行解：（50，0）可行解：（20,20,100,20,40）(40,0,0,40,180)非可行解:(50,0,-90,0,150)单纯形法原理预备转化为矩阵形式2.3 单纯形法原理一、线性规划问题的解的概念二、凸集及其顶点三、几个基本定理的证明四、单纯形法迭代原理一、线性规划问题的解的概念可行解可行解：满足约束条件AX=b,X0的解。举例：标准式可行解：（20,20,100,20,40）(40,0,0,40,180)非标准式可行解:(20,20)、(40,0)最优解最优解：使目标函数最优的可行解，称为最优解。举例：非标准式最优解：(20,24)标准式最优解：(20,24,84,0,0)基的概念基的概念：(重点)如前所述LP标准型:约束方程的mn阶系数矩阵A的秩为m，且m 0，则与之相应的非基变量Xj若取非零，将使Z增加。取 相应之非基变量Xk若取非零，将使Z增加最快。故Xk为进基变量进基变量（由非基变量变为基变量）。令其余非基变量保持为零，XK 由0逐渐增大直到某个原基变量为0。则该基变量称为出基变量出基变量（由基变量变为非基变量）；若继续XK增大将破坏该出基变量的非负约束。如何确定那个基变量为出基？，这时XL由基变量变为非基变量由于处在变量转换的交叉点上，称之为枢轴元素 90 80 60 40 20 x29x1+4x2 3604x1+5x2 200(0 0 360 200 300)9x1+4 x2+x3 =360 4x1+5 x2 +x4 =200 3x1+10 x2 +x5 =300 70 x1+120 x2+0 x3+0 x4+0 x5=Z120 70 x2为进基x3=360 4x2 0 x4=200 5x2 0 x5=300 10 x2 0 x2 90 x2 40 x2 30(0 30 240 50 0)X5为出基基变换的图形意义枢轴元素线性规划及单纯形法v线性规划问题及其数学模型v图解法v单纯形法迭代原理v单纯形法的计算步骤v单纯形法的进一步讨论2.4 单纯形法计算步骤一、代数解法二、表格单纯形法2.4 单纯形法计算步骤一、代数解法二、表格单纯形法例：用代数解法求解下面LP问题解：由于该LP问题不是标准形式，故应先将其转换为标准式1、确定初始基可行解x1x2x3x4x5x3x4x5非奇异子阵，做为一个基基变量基变量x3,x4,x5非基变量非基变量x1,x2在确定基变量后，可立即求得基可行解：令x1,x2等于0，x3,x4,x5的值可立即从上式读出初始基可行解为：一个可行解就是一个生产方案，在上述方案中两种产品都不生产，利润Z=0。因为每个等式只有一个系数为1的基变量，并且这个基变量只出现在这个等式。Notice:为什么基变量的值能如此方便的读出？在后面的过程中，当基变量成员发生变化时，我们将对其系数矩阵做初等变换（高斯消元法Gaussian elimination），将其转化为这种方便的形式。这种形式被称为 proper form from Gaussian elimination2、检验其最优性从目标函数-Z+3x1+5 x2+0 x3+0 x4+0 x5=0可知：非基变量x1和x2的检验数均为正数，生产哪种产品都会增加利润。故该初始基可行解不是最优解。3、确定进基变量（迭代的第一步）确定进基变量对应于图解法的确定运动方向从目标函数-Z+3x1+5 x2+0 x3+0 x4+0 x5=0可知：因为x2的系数大于x1的系数，即生产单位乙产品比甲产品利润更高一些，故应优先多生产乙产品。即x2为进基进基进基变量的标识4、确定出基变量（迭代的第二步）确定出基变量对应于图解法的确定在那里停下来基变量由非基变量线性表示：保持原非基变量x1=0,x2逐渐增大时应保证：x2 12/2x2 36/4X4为出基变量出基变量的标识5、对新基可行解的求解（迭代的第三步）枢轴元素下面是初等变换（高斯消元法）的具体步骤：1/245由于x1,x4是非基变量，令x1,x4等于0。x2,x3,x5的值能够直接从上式读出，于是得到新的基可行解：目标函数值Z=30重复上述步骤，直到获得最优解小结小结初始化最优性检验迭代（Iteration）最优？yesSTOPno初始基可行解的确定当前的基可行解是否最优？包括三个步骤：1、确定进基变量（进基）2、确定出基变量（出基）3、对新基可行解的求解（高斯消元）最优性检验：由于目标函数中x1的检验数为正数（1=3 0），故不是最优解,开始第二次迭代确定出基变量（迭代的第二步）：确定进基变量（迭代的第一步）：x1为进基变量保持原非基变量x4=0,x1逐渐增大并保证x3、x2、x5非负。x1 8/1x1 12/3X5为出基变量 对新基可行解的求解（迭代的第三步）：使用高斯消元法1/3-3由于x4、x5为非基变量，令x4=0,x5=0 x1,x2,x3的值能从上式直接读出，于是得到新的基可行解：最优性检验：在目标函数中所有检验数非正（j 0），可以判定该解为最优解。即单纯形法的几何意义单纯形法的几何意义x1=82x2=123x1+4 x2=36x1x248123690 0A AB BC(4,6C(4,6)D DX0=(0,0,8,12,36)TX1=(0,6,8,0,12)TX1=(4,6,4,0,0)T课堂练习第一次迭代 x1为入基，x4为出基第二次迭代 x2为入基，x3为出基2.4 单纯形法计算步骤一、代数解法二、表格单纯形法二、表格单纯形法上节介绍的单纯形法的代数形式也许是了解单纯形法最好的形式。但是，它不是最方便的计算形式，特别是需要手工求解问题的时候。表格形式的单纯形法仅记录本质的信息：l 决策变量的系数（包括约束条件和目标函数）l 等式右边的常数l 基变量（每次迭代时）表格单纯形法强调了运算涉及的数字并且将计算紧凑的记录下来1、单纯形表的格式：CjC1 C2 Cn i CBXBbx1 x2 .xn C1 C2Cmx1x2xmb 1b2bma11 a12 a1na21 a22 a2n am1 am2 amn 1 2 m j 1 2 n 迭代计算中每找出一个新的基可行解时，就重画一张单纯形表。含初始基可行解的单纯形表称初始单纯形表，含最优解的单纯形表称最终单纯形表。2、表格单纯形法的计算步骤：将线性规划问题化成标准型。找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯形表。计算各非基变量xj的检验数j=Cj-CBPj，若所有j0，则问题已得到最优解，停止计算，否则转入下步。在大于0的检验数中，若某个k所对应的系数列向量Pk0，则此问题是无界解，停止计算，否则转入下步。根据maxjj0=k原则，确定xk为换入变量(进基变量)（进基）（进基）再按规则计算：确定xL为换出变量。建立新的单纯形表，此时基变量中xk取代了xL的位置。(出基出基)以aLk为枢轴元素进行迭代，把xk所对应的列向量变为单位列向量，即aLk变为1，同列中其它元素为0，（高（高斯消元），斯消元），转第 步。小结小结初始化最优性检验迭代（Iteration）最优？yesSTOPno初始基可行解的确定当前的基可行解是否最优？包括三个步骤：1、确定进基变量（进基）2、确定出基变量（出基）3、对新基可行解的求解（高斯消元）3、表格单纯形法举例：Cj比值CBXBb检验数jx1x2x3x4x53500081010012020103634001x3x4x5000-12/2=636/4=903500 0单纯形表对应的代数式子：检验行说明检验行说明检验数检验数 j81010060101/2012300-21x3x2x5050-30300-5/208-4Cj比比值值CBXBb检验数检验数 jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9Cj比值CBXBb检验数jx1x2x3x4x53500081010060101/2012300-21x3x2x5050-30300-5/208-4检验数j 40012/3-1/360101/204100-2/31/3x3x2x1053-42000-1/2-1最优解最优解:X*=(4,6,4,0,0)T，Z*=42分别用图解法和表格单纯形法求解下列线性规划问题，并对照指出单纯形法迭代的每一步相当于图解法可行域中的那一个顶点。课堂练习Cj比值CBXBb检验数jx1x2x3x4x53500041010012020101832001x3x4x5000-12/2=618/2=903500 0Cj比比值值CBXBb检验数检验数 jx1x2x3x4x53500041010012020101832001x3x4x5000035000-12/2=618/2=9检验数检验数 j41010060101/206300-11x3x2x5050-30300-5/204/1-6/3检验数检验数 j41010060101/206300-11x3x2x5050-30300-5/204/1-6/3检验数检验数 jx3x2x10532100-1/31/360101/2020011/3-1/3-36000-3/2-1最优解最优解:X*=(2,6,2,0,0)T，Z*=36课堂练习用表格单纯形法解例1Cj比值CBXBb检验数jx1x2x3x4x5701200003609410020045010300310001x3x4x500007012000 0360/4=90200/5=40300/10=30Cj比值CBXBb检验数jx1x2x3x4x5701200003609410020045010300310001x3x4x500007012000 0360/4=90200/5=40300/10=30检验数检验数 jx3x4x200120300.310 0 0.1502.5001-0.52407.8010-0.4-360034000-1230.7620100检验数检验数 jx3x4x200120300.310 0 0.1502.5001-0.52407.8010-0.4-360034000-12检验数检验数 jx3x1x2070120201000.4-0.284001-3.121.1624010-0.120.16-4280000-13.6-5.2最优解最优解:X*=(20,24,84,0,0)T，Z*=4280 CjC1 C2 CnCBXBbX1 X2 X3 X4 X5j 0 0 0X3X4X5360200300 9 4 1 0 0 4 5 0 1 0 3 10 0 0 1 904030j0 70 120 0 0 0 0 0 120X3X4X224050 30 7.8 0 1 0 -0.4 2.5 0 0 1 -0.5 0.3 1 0 0 0.130.7620100j3600 34 0 0 0 -12701200X3X1X2842024 0 0 1 -3.12 1.16 1 0 0 0.4 -0.2 0 1 0 -0.12 0.16j4280 0 0 0 -13.6 -5.2Complete set of simplex tableaux for the problem:4、最优基和最优基的逆：Cj比值CBXBb检验数j035000 x1x2x3x4x53500081010012020103634001x3x4x5000检验数j 40012/3-1/360101/204100-2/31/3x3x2x1053-42000-1/2-1Cj比值CBXBb检验数j035000 x1x2x3x4x53500081010012020103634001x3x4x5000 x3x2x1最优基最优基x3x2x1一定存在B-1使得如何求得B-1?单位单位矩阵矩阵Cj比值CBXBb检验数j035000 x1x2x3x4x53500081010012020103634001x3x4x5000检验数j 40012/3-1/360101/204100-2/31/3x3x2x1053-42000-1/2-1B-1B-1被称为最优基的逆矩阵5、表格单纯形法下的解的情况说明：当所有j0时，表明现有顶点（基可行解）的目标函数值比起相邻各顶点（基可行解）的目标函数值都大，根据线性规划问题的可行域是凸集的证明以及凸集的性质，可以判定现有顶点对应的基可行解即为最优解。最优解存在两种情况：（1）唯一最优解在最终单纯形表中所有非基变量j0,又Pj0,可以看出不存在，无出基变量，Z的取值无限增大，该线性规划问题无界解例 解LP问题解：由于上式不是标准式，将其标准化得：Cj比比值值CBXBb检验数检验数jx1x2x3x432002-211031-301x3x40003200-3检验数j80-512x3x103-31-301-90110-3此时，检验数2=11 0，还没有得到最优解。确定x2进基，但x2所在列的系数向量元素非正，无界值不存在，有进基变量但无离基变量。检验数j80-512x3x103-31-301-90110-3Cj比比值值CBXBb3200 x1x2x3x4线性规划及单纯形法v线性规划问题及其数学模型v图解法v单纯形法迭代原理v单纯形法的计算步骤v单纯形法的进一步讨论2.5 单纯形法进一步讨论一、人工变量法(大M法)二、两阶段法三、单纯形法计算中的几个问题2.5 单纯形法进一步讨论一、人工变量法(大M法)二、两阶段法三、单纯形法计算中的几个问题一、人工变量法(大M法)针对标准形约束条件的系数矩阵中不含单位矩阵的处理方法。在上面例子中，化为标准形式后约束条件的系数矩阵中含有单位矩阵，以此作初始基，使求初始基和建立初始单纯形表都十分方便。但在下面例子中，化为标准形后的约束条件的系数矩阵中不存在单位矩阵强行加上人工变量，使其出现单位矩阵：但这样处理后：不易接受。因为 是强行引进，称为 人工变量。它们与 不一样。称为松弛变量和剩余变量，是为了将不等式改写为等式而引进的，而改写前后两个约束是等价的。人工变量的引入一般来说是前后不等价的。只有当最优解中，人工变量都取值零时（此时人工变量实质上就不存在了）才可认为它们是等价的。处理办法：把人工变量从基变量中赶出来使其变为非基变量。为此，发明者建议把目标函数作如下处理：其中M为任意大的实数，“-M”称为“罚因子”。用意：只要人工变量取值大于零，目标函数就不可能实现最优。填入单纯形表，有：Cj比值CBXBb检验数jx1 x2 x3 x4 x5 x6 x7-3 0 1 0 0 -M -M4 1 1 1 1 0 0 01 -2 1 -1 0 -1 1 09 0 3 1 0 0 0 1x4x6x70-M-M0 -3 0 1 0 0 -M -MCj比值CBXBb检验数jx1 x2 x3 x4 x5 x6 x7-3 0 1 0 0 -M -M4 1 1 1 1 0 0 01 -2 1 -1 0 -1 1 09 0 3 1 0 0 0 1x4x6x70-M-M 10M -2M-3 4M 1 0 -M 0 0Cj比值CBXBb检验数jx1 x2 x3 x4 x5 x6 x7-3 0 1 0 0 -M -M4 1 1 1 1 0 0 01 -2 1 -1 0 -1 1 09 0 3 1 0 0 0 1x4x6x70-M-M 10M -2M-3 4M 1 0 -M 0 04/11/19/1Cj比值CBXBb检验数jx1 x2 x3 x4 x5 x6 x7-3 0 1 0 0 -M -M3 3 0 2 1 1 -1 01 -2 1 -1 0 -1 1 06 6 0 4 0 3 -3 1x4x2x700-M 6M 6M-3 0 4M+1 0 3M -4M 03/3-6/6Cj比值CBXBb检验数jx1 x2 x3 x4 x5 x6 x7-3 0 1 0 0 -M -M3 3 0 2 1 1 -1 01 -2 1 -1 0 -1 1 06 6 0 4 0 3 -3 1x4x2x700-M 6M 6M-3 0 4M+1 0 3M -4M 03/3-6/6Cj比值CBXBb检验数jx1 x2 x3 x4 x5 x6 x7-3 0 1 0 0 -M -M0 0 0 0 1 -1/2 1/2 -1/23 0 1 1/3 0 0 0 1/31 1 0 2/3 0 1/2 -1/2 1/6x4x2x100-3 3 0 0 3 0 3/2 -M-3/2 -M+1/2-93/2Cj比值CBXBb检验数jx1 x2 x3 x4 x5 x6 x7-3 0 1 0 0 -M -M0 0 0 0 1