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

线性规划及 单纯形法,线性规划及单纯形法,线性规划问题及其数学模型图解法单纯形法原理单纯形法的计算步骤,第一节 线性规划问题及其数学模型,一、问题的提出,线性规划主要解决：如何利用现有有限的资源，使得预期目标达到最优的问题。,例1 某工厂在计划期内要安排生产A、B两种产品（假定产品畅销）。已知生产单位产品的利润与所需的劳动力、设备台时及原材料的消耗，如表1.1所示问该厂应如何安排生产使获利最大？,表1-1,问题要求给出一个方案(产品A生产多少；产品B生产多少),设该工厂生产A、B两种产品产量分别为,确定决策变量,表1-1,制定方案的目标是什么？,该厂获取的利润可表示为,问题的目标：,确定目标函数,利润最大化,表1-1,方案的制定受到那些现实条件制约：,人力资源（劳动力）的限制：,设备工时的限制：,原材料资源的限制：,此外，决策变量的取值不应为负值即,确定约束条件,其中,目标函数,约束条件,资源约束,非负约束,约束条件可记 s.t(subject to),意思为“以,为条件“、”假定“、”满足“之意。,综上所述，我们得到了这个问题的数学模型,建立问题的线性规划模型步骤,1 确定决策变量决策变量是模型所要决定的未知量，也是模型最重要的参数它用以表明规划中的用数量表示的方案、措施，可由决策者决定和控制,2 确定目标函数就是将决策者所追求的目标表示为决策变量的函数它决定了线性规划优化的方向，是线性规划的重要组成部分,3 确定约束条件这些约束条件可用含有决策变量的等式或不等式来表示,例2 给海狸鼠配饲料饲料中营养要求：Va每天至少700克，Vb每天至少30克，VC每天刚好200克。现有五种饲料，搭配使用，饲料成分如下表：,问：应如何搭配饲料，使费用最小？,确定决策变量：设抓取饲料I x1kg;饲料II x2kg;饲料III x3kg确定目标函数：minZ=2x1+7x2+4x3+9x4+5x5确定约束条件：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所示。问该公司应制造两种家电各多少件，使获取的利润最大？,课堂练习,表1-2,其数学模型为：,例3：捷运公司在下一年度的14月份的4个月内拟租用仓库堆放物资。已知各月份所需仓库面积列于下表1-3。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表1-4。租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。因此该厂可根据需要，在任何一个月初办理租借合同。每次办理时可签一份合同，也可签若干份租用面积和租用期限不同的合同。试确定该公司签订租借合同的最优决策，目的是使所租借费用最少。,表1-3,表1-4,单位：100m2,单位；元/100m2,表1-2,表1-3,单位：100m2,单位；元/100m2,解：设 表示捷运公司在第i(i=1,2,3,4)月初签订的租期为j(j=1,2,3,4)个月的仓库面积的合同（单位为100m2)。,15,10,20,12,经过上面的讨论，得到下面的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线性规划图解法,所谓图解法，就是在平面直角坐标上画出各个约束条件所允许变化的范围，通过图上作业法求出最优解和目标函数值。,一个线性规划问题有解，是指能找出一组xj(j=1,2,n),满足所有约束条件，称这组xj为问题的可行解。,通常线性规划问题总是含有多个可行解，称全部可行解的集合为可行域。在用图解法求解时，可形象的看到可行域。在可行域中使目标函数值达到最优的可行解称为最优解,对不存在可行解的线性规划问题，称该问题无解,图解法背景知识,图解法背景知识,由中学知识可知：y=ax+b是一条直线。同理(如果Z值固定)Z=70 x1+120 x2,x2=-70/120 x1+Z/120也是一条直线,x2=-70/120 x1+Z/120也是一组平行的等值线,1.2.1图解法的步骤,1、建立直角坐标系；2、根据约束条件描绘可行域；3、作目标函数的等高线；4、求解最优点和最优目标函数值。,例题1生产计划问题,某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：,问题：如何安排生产计划，使得获利最多？,例1 图解法,.,90 80 60 40 20,0 20 40 60 80 100,x1,x2,9x1+4x2 360,4x1+5x2 200,3x1+10 x2 300,Z=70 x1+120 x2,maxZ=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.5,x1=15/4,x2=3/4 Z*=33/4,x1=2,x2=6 Z*=36,1.2.2求解的几种可能结局,1、无穷多最优解。2、唯一最优解。2、无界解。3、无解或无可行解。,解的可能性,多重最优解：无穷多个最优解。若在两个顶点同时得到最优解，则它们连线上的每一点都是最优解。唯一最优解：只有一个最优点。,解的可能性,无界解：线性规划问题的可行域无界，使目标函数无限增大而无界。（缺乏必要的约束条件）,解的可能性,无可行解：若约束条件相互矛盾，则可行域为空集,由图解法得到的启示,图解法虽然只能用来求解只具有两个变量的线性规划问题，但它的求解思路和几何上直观得到的一些概念判断，对于单纯形法有很大启示,1、求解线性规划问题时，解的情况有：唯一最优解；无穷多最优解；无界解；无可行解,2、若线性规划问题的可行解存在，则可行域是一个凸集,3、若线性规划问题的最优解存在，则最优解或最优解之一一定是可行域的凸集的某个顶点。,由图解法得到的启示,4、解题思路是：先找出凸集的任一顶点，计算在顶点处的目标函数值。比较周围相邻顶点的目标函数值是否比这个值大，如果为否，则该顶点就是最优解的点或最优解的点之一；否则转到比这个点的目标函数值更大的另一个顶点，重复上述过程，一直到找出使目标函数值达到最大的顶点为止。,1.3 单纯形法 原 理,数学试验,LINDO软件包,LINDO软件包介绍,初试LINDO用LINDO求解整数规划注意事项,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.000000.090909.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=12,END:GOLP OPTIMUM FOUND AT STEP O OBJECTIVE FUNCTION VALUE 1)7.333333VARIABLE VALUE REDUCED COSTX.666667.000000Y 2.0000.000000ROWSLACK OR SURPLUS DUAL PRICES.000000.047619.000000.571429,NO.ITERATIONS=0DO RANGE(SENSITIVITY)ANALYSIS?N:QUIT,改动约束条件的右端项,可以将RHS(即right-hand side)作为变量名.改变约束条件中的不等号方向(如,可以将DIR作为变量名.修改问题还可用EXT命令(增加新的约行),DEL命令(去掉一行)和APPC 命令(增加一个新的变量),也可用EDIT全屏幕编辑器.,灵 敏 度 分 析,下面用一个具体例子来说明 LINDO 软件求对偶变量及进行灵敏度分析.,例 有一家具制造车间,制造书桌(DESK)、桌子(TABLE)、椅子(CHAIR),所用原料及木工、漆工的数据如表1所示.,表 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:GO,LP 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.000000,LINDO在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,价值系数ci,C1在区间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 x3 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章中介绍的差一个符号。,线性规划及单纯形法,线性规划问题及其数学模型图解法单纯形法迭代原理单纯形法的计算步骤,单纯形法原理预备,例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，且mn。若B是A中mm阶的满秩子矩阵，则称B是LP的一个基，即：B是A中m个线性无关（列）向量组成的矩阵。,基的概念举例：,线性方程组系数A的矩阵：,其中，最容易看出的线性无关向量组（列）：,单位矩阵,基的数目不超过,B,p1 p2 p3 p4 p5,基的概念举例：,由基的概念，我们可用定义下面两个概念：,1 基变量：与基向量Pj相对应的m个变量xj称为基变量，其余的m-n个变量为非基变量。,2 基解：令所有非基变量等于零，对m个基变量所求的 解，对应一个特定的基矩阵能求得一组唯一 解，这个解加上非基变量取0称为基解。,结合图解来看，基解是各约束方程及坐标轴之间交点的坐标。,提问：基解的数目不超过：,单位矩阵,基变量、基解举例：,基变量是x3,x4,x5,非基变量是x1,x2,令非基变量x1=x2=0，求得基变量 x3=360，x4=200，x5=300于是得到基解（0,0,360,200,300）,由于基解的求解没有考虑非负约束，因此所得到的基解有可能不满足非负约束，因而不是可行解。由此，我们得到下面的定义：,基可行解：基解可正可负，负则不可行（违背非负性约束条件），称满足所有约束条件的基解为基可行解。即所有变量大于等于0的基解称为基可行解。,退化的基可行解：若某个基变量取值为零，则称之为退化的基可行解。,基可行解举例：,线性方程组系数A的矩阵：,例1 的标准型,p1 p2 p3 p4 p5,基可行解举例：,基可行解举例：,基与解的对应关系：,非可行解,可行 基可行解解,基解,解与解之间的关系为：,基解,基,可行基,基可行解,最优基,基最优解,小结,基解的几何意义,结合图解来看，基解是各约束方程及坐标轴之间交点的坐标。,我们继续对例1进行讨论，下面是例1的标准型：,下表是对前面得到的表进行重新排列，基可行解排在前面（用红色表示），基非可行解排在后面（用蓝色表示）,.,90 80 60 40 20,0 20 40 60 80 100,x1,x2,9x1+4x2 360,4x1+5x2 200,3x1+10 x2 300,Z=70 x1+120 x2,基解V.S.图形,基解的几何意义,由此我们得到基解非常重要的性质：基解是各约束方程及坐标轴之间的交点基可行解对应于可行域上的交点（顶点）基非可行解对于于非可行域上的交点,非可行解,可行 基可行解解,基解,进一步深入讨论解与解之间的关系为：,其中，可行解对应可行域；基可行解对应可行域上的顶点,课堂练习,对下述线性规划问题找出所有基解，指出那些是基可行解,并指出得到的基可行解对应那个顶点,课堂练习Solution:,先将其转换为标准形式：,p1 p2 p3 p4 p5,p1 p2 p3 p4 p5,2.3 单纯形法原理,一、线性规划问题的解的概念,二、凸集及其顶点,三、几个基本定理的证明,四、单纯形法迭代原理,对简单的几何形体可以直观地判断其凹凸性，但在高维空间，只能给出点集的解析表达式，因此只能用数学解析式判断。,二、凸集及其顶点,凸集的概念：如果集合C中任意两个点X1,X2，其连线上的所有点也都是集合C的点，则称C为凸集。由于X1,X2的连线可表示为：,凸集的概念,因此凸集定义用数学解析式可表示为：对任何,则称C为凸集。,凸集举例:,凸集举例:,顶点凸集C中满足下述条件的点X称为顶点：如果C中不存在任何两个不同的点X1,X2，使X成为这两个点连线上的一个点。或者这样叙述：对任何,不存在,则称X是凸集C的顶点,由凸集和顶点的概念，可以证明以下定理：,定理1 若线性规划问题存在最优解，则问题的可行域是凸集。,定理2 线性规划问题的基可行解对应线性规划问题可行域（凸集）的顶点。,定理3 若线性规划问题最优解存在，则一定存在一个是基可行解,由此可看出，最优解要在基可行解（可行域顶点）中找。,三、几个基本定理的证明,线性规划的解题思路,线性规划问题可以有无数个可行解，最优解只可能在顶点上达到，而顶点对应的是有限个基可行解，故只要在有限个基可行解中寻求最优解即可。找出一个可行基，得到一个基可行解（对应一个顶点），判别它是否最优（对应比较相邻的顶点）。如若不是，换一个基再行求解（对应向邻近的顶点转移）、检验，如此迭代循环目标值逐步改善，直至求得最优解。,线性规划的解题思路,.,90 80 60 40 20,0 20 40 60 80 100,x1,x2,9x1+4x2 360,4x1+5x2 200,3x1+10 x2 300,Z=70 x1+120 x2,得到最优解,2.3 单纯形法原理,一、线性规划问题的解的概念,二、凸集及其顶点,三、几个基本定理的证明,四、单纯形法迭代原理,四、单纯形法迭代原理,初始基可行解的确定 最优性检验基变换,四、单纯形法迭代原理,初始基可行解的确定 最优性检验基变换,初始基可行解的确定,从系数矩阵中找到一个可行基B，不妨设B由A的前m列组成，即B=(P1,P2,Pm)。进行等价变换即约束方程两端分别左乘B1 得,令非基变量为0，得基可行解,例1 的标准型 maxZ=70 x1+120 x2+0 x3+0 x4+0 x5 9x1+4x2+x3=360 4x1+5x2+x4=200 3x1+10 x2+x5=300 x1,x2,x3,x4,x5 0线性方程组的系数矩阵A,S.T,可行基B,初始基可行解的确定(举例),例1的标准型 maxZ=70 x1+120 x2+0 x3+0 x4+0 x5 9x1+4x2+x3=360 4x1+5x2+x4=200 3x1+10 x2+x5=300 x1,x2,x3,x4,x5 0,S.T,maxZ=70 x1+120 x2+0 x3+0 x4+0 x5 39/5x1+0 x2+x3-2/5x5=240 2/5 x1+0 x2+x4-1/2x5=50 3/10 x1+1x2 1/10 x5=30 x1,x2,x3,x4,x5 0,p3 p4 p2 1 0 0 0 1 0 0 0 1,初始基可行解的确定(举例),初始基可行解的确定(举例),B-1A=,=39/5 0 1 0-4/10 240 5/2 0 0 1-5/10 50 3/10 1 0 0 1/10 30,为方便计算初始基可行解一般设为原点,可行基B,90 80 60 40 20,x2,9x1+4x2 360,4x1+5x2 200,Z=70 x1+120 x2,初始基可行解的确定(举例),四、单纯形法迭代原理,初始基可行解的确定 最优性检验基变换,最优性检验,LP经过若干步迭代，成为如下形式：,一般性表示：,将xi代入目标函数得：,maxZ=70 x1+120 x2+0 x3+0 x4+0 x5 39/5x1+0 x2+x3-2/5x5=240 2/5 x1+0 x2+x4-1/2x5=50 3/10 x1+1x2 1/10 x5=30 x1,x2,x3,x4,x5 0,x3=240-39/5x1+2/5x5x4=50-2/5 x1+1/2x5x2=30-3/10 x1-1/10 x5,Z=c3x3+c4x4+c2x2+c1x1+c5x5=240c3-39/5c3x1+2/5c3x5+50c4-2/5 c4x1+1/2c4x5+30c2-3/10c2x1-1/10c2x5+c1x1+c5x5=(240c3+50c4+30c2)+(c1 39/5c3-2/5c4-3/10c2)x1+(c5-2/5c3-1/2c4-1/10c2)x5,ci（bi-aijxj）,i=m,i=1,cjxj,j=m+1,j=n,j=m+1,j=n,j=cj-ciaij,i=m,i=1,最优性检验(举例),检验数的求解（1）,将目标函数中含有基变量的项消去。,检验数的求解（2）,四、单纯形法迭代原理,初始基可行解的确定 最优性检验基变换,基变换,若存在j 0，则与之相应的非基变量Xj若取非零，将使Z增加。取 相应之非基变量Xk若取非零，将使Z增加最快。故Xk为进基变量（由非基变量变为基变量）。,令其余非基变量保持为零，XK 由0逐渐增大直到某个原基变量为0。则该基变量称为出基变量（由基变量变为非基变量）；若继续XK增大将破坏该出基变量的非负约束。,如何确定那个基变量为出基？,，这时XL由基变量变为非基变量,由于,处在变量转换的交叉点上，称之为枢轴元素,90 80 60 40 20,x2,9x1+4x2 360,4x1+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=Z,120 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为出基,基变换的图形意义,枢轴元素,线性规划及单纯形法,线性规划问题及其数学模型图解法单纯形法迭代原理单纯形法的计算步骤单纯形法的进一步讨论,2.4 单纯形法计算步骤,一、代数解法,二、表格单纯形法,2.4 单纯形法计算步骤,一、代数解法,二、表格单纯形法,例：用代数解法求解下面LP问题,解：由于该LP问题不是标准形式，故应先将其转换为标准式,1、确定初始基可行解,非奇异子阵，做为一个基,基变量x3,x4,x5非基变量x1,x2,在确定基变量后，可立即求得基可行解：,令x1,x2等于0，x3,x4,x5的值可立即从上式读出,初始基可行解为：,一个可行解就是一个生产方案，在上述方案中两种产品都不生产，利润Z=0。,因为每个等式只有一个系数为1的基变量，并且这个基变量只出现在这个等式。,Notice:,为什么基变量的值能如此方便的读出？,在后面的过程中，当基变量成员发生变化时，我们将对其系数矩阵做初等变换（高斯消元法Gaussian elimination），将其转化为这种方便的形式。这种形式被称为 proper form from Gaussian elimination,2、检验其最优性,从目标函数-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/2,x2 36/4,X4为出基变量,出基变量的标识,5、对新基可行解的求解（迭代的第三步）,枢轴元素,下面是初等变换（高斯消元法）的具体步骤：,1/2,4,5,由于x1,x4是非基变量，令x1,x4等于0。,x2,x3,x5的值能够直接从上式读出，于是得到新的基可行解：,目标函数值Z=30,重复上述步骤，直到获得最优解,小结,初始化,最优性检验,迭代（Iteration）,最优？,yes,STOP,no,初始基可行解的确定,当前的基可行解是否最优？,包括三个步骤：1、确定进基变量（进基）2、确定出基变量（出基）3、对新基可行解的求解（高斯消元）,最优性检验：由于目标函数中x1的检验数为正数（1=3 0），故,不是最优解,开始第二次迭代,确定出基变量（迭代的第二步）：,确定进基变量（迭代的第一步）：x1为进基变量,保持原非基变量x4=0,x1逐渐增大并保证x3、x2、x5非负。,x1 8/1,x1 12/3,X5为出基变量,对新基可行解的求解（迭代的第三步）：使用高斯消元法,1/3,-3,由于x4、x5为非基变量，令x4=0,x5=0 x1,x2,x3的值能从上式直接读出，于是得到新的基可行解：,最优性检验：在目标函数中所有检验数非正（j 0），可以判定该解为最优解。即,单纯形法的几何意义,X0=(0,0,8,12,36)T,X1=(0,6,8,0,12)T,X1=(4,6,4,0,0)T,课堂练习,第一次迭代 x1为入基，x4为出基,第二次迭代 x2为入基，x3为出基,2.4 单纯形法计算步骤,一、代数解法,二、表格单纯形法,二、表格单纯形法,上节介绍的单纯形法的代数形式也许是了解单纯形法最好的形式。但是，它不是最方便的计算形式，特别是需要手工求解问题的时候。,表格形式的单纯形法仅记录本质的信息：决策变量的系数（包括约束条件和目标函数）等式右边的常数 基变量（每次迭代时）,表格单纯形法强调了运算涉及的数字并且将计算紧凑的记录下来,1、单纯形表的格式：,迭代计算中每找出一个新的基可行解时，就重画一张单纯形表。含初始基可行解的单纯形表称初始单纯形表，含最优解的单纯形表称最终单纯形表。,2、表格单纯形法的计算步骤：,将线性规划问题化成标准型。,找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯形表。,计算各非基变量xj的检验数j=Cj-CBPj，若所有j0，则问题已得到最优解，停止计算，否则转入下步。,在大于0的检验数中，若某个k所对应的系数列向量Pk0，则此问题是无界解，停止计算，否则转入下步。,根据maxjj0=k原则，确定xk为换入变量(进基变量)（进基）再按规则计算：,确定xL为换出变量。建立新的单纯形表，此时基变量中xk取代了xL的位置。(出基),以aLk为枢轴元素进行迭代，把xk所对应的列向量变为单位列向量，即aLk变为1，同列中其它元素为0，（高斯消元），转第 步。,小结,初始化,最优性检验,迭代（Iteration）,最优？,yes,STOP,no,初始基可行解的确定,当前的基可行解是否最优？,包括三个步骤：1、确定进基变量（进基）2、确定出基变量（出基）3、对新基可行解的求解（高斯消元）,3、表格单纯形法举例：,03500 0,单纯形表对应的代数式子：,检验行说明,最优解:X*=(4,6,4,0,0)T，Z*=42,分别用图解法和表格单纯形法求解下列线性规划问题，并对照指出单纯形法迭代的每一步相当于图解法可行域中的那一个顶点。,课堂练习,03500 0,最优解:X*=(2,6,2,0,0)T，Z*=36,课堂练习,用表格单纯形法解例1,07012000 0,07012000 0,最优解:X*=(20,24,84,0,0)T，Z*=4280,Complete set of simplex tableaux for the problem:,4、最优基和最优基的逆：,最优基,一定存在B-1使得,如何求得B-1?,单位矩阵,B-1,B-1被称为最优基的逆矩阵,5、表格单纯形法下的解的情况说明：,当所有j0时，表明现有顶点（基可行解）的目标函数值比起相邻各顶点（基可行解）的目标函数值都大，根据线性规划问题的可行域是凸集的证明以及凸集的性质，可以判定现有顶点对应的基可行解即为最优解。最优解存在两种情况：,（1）唯一最优解,在最终单纯形表中所有非基变量j0时，该线性规划问题具有唯一解。,（2）无穷多最优解,在最终单纯形表中，存在非基变量的检验数j=0，则表明可以找到另一个顶点（基可行解）目标函数值也达到最大。（让这个非基变量进基，继续迭代，得另一个最优解）由于该两点连线上的点也属于可行域内的点，且目标函数值相等，即该线性规划问题有无穷多最优解。,例 解LP问题,1/16/1,1/16/1,x1x5,10,所有j0，故已得最优解X1=（1,0,0,0,5）T,Z*=1,x1x5,10,非基变量x2对应的20，令其为进基变量,-5/3,x1x2,1-2,所有j0，故已得最优解X2=(13/3,5/3,0,0,0)T,Z*=1,以 与 的连线段：,即,为全部解的一般形式。,无最优解也存在两种情况：,（1）无可行解（将在下一节讨论）,（2）无界解,如果存在某个j0,又Pj0,可以看出,不存在，无出基变量，Z的取值无限增大，该线性规划问题无界解,例 解LP问题,解：由于上式不是标准式，将其标准化得：,此时，检验数2=11 0，还没有得到最优解。确定x2进基，但x2所在列的系数向量元素非正，无界值不存在，有进基变量但无离基变量。,线性规划及单纯形法,线性规划问题及其数学模型图解法单纯形法迭代原理单纯形法的计算步骤单纯形法的进一步讨论,2.5 单纯形法进一步讨论,一、人工变量法(大M法),二、两阶段法,三、单纯形法计算中的几个问题,2.5 单纯形法进一步讨论,一、人工变量法(大M法),二、两阶段法,三、单纯形法计算中的几个问题,一、人工变量法(大M法),针对标准形约束条件的系数矩阵中不含单位矩阵的处理方法。,在上面例子中，化为标准形式后约束条件的系数矩阵中含有单位矩阵，以此作初始基，使求初始基和建立初始单纯形表都十分方便。,但在下面例子中，化为标准形后的约束条件的系数矩阵中不存在单位矩阵,强行加上人工变量，使其出现单位矩阵：,但这样处理后：不易接受。因为 是强行引进，称为,人工变量。它们与 不一样。称为松弛变量和剩,余变量，是为了将不等式改写为等式而引进的，而改写前后,两个约束是等价的。人工变量的引入一般来说是前后不等,价的。只有当最优解中，人工变量都取值零时（此时人工,变量实质上就不