第一章线性规划与单纯形法课件.ppt

第一章,线性规划的发展,法国数学家 J.-B.-J.傅里叶和 C.瓦莱普森分别于1832和1911年独立地提出线性规划的想法。1939年苏联数学家.康托罗维奇在生产组织与计划中的数学方法中提出线性规划问题。1947年美国数学家G.B.丹齐克提出线性规划的一般数学模型和求解线性规划问题的通用方法单纯形法。1947年美国数学家J.von诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。1951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖。,线性规划的发展,50年代后对线性规划进行大量的理论研究。例如，1954年C.莱姆基提出对偶单纯形法，1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956年A.塔克提出互补松弛定理，1960年G.B.丹齐克和P.沃尔夫提出分解算法等。线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。,线性规划的发展,1979年苏联数学家L.G.Khachian提出解线性规划问题的椭球算法，并证明它是多项式时间算法。1984年N.卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。,第一节线性规划问题及其数学模型,1、线性规划问题的提出在生产管理和经营活动中经常提出一类问题，即如何合理地利用有限的人力、物力、财力等资源，以便得到最好的经济效果。,第一节线性规划问题及其数学模型,例1：某工厂在计划期内要安排生产、两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表1-1所示：,x1,x2,第一节线性规划问题及其数学模型,问：如何安排计划使该工厂获利最多？解题思路：用以下数学模型来描述，设x1、x2分别表示在计划期内产品、的产量。因为设备的有效台时是8，这是一个限制产量的条件，所以在确定产品、的产量时，要考虑不超过设备的有效台时数，即可用不等式表示为：,第一节线性规划问题及其数学模型,第一节线性规划问题及其数学模型,综上所述，该计划问题可用数学模型表示为：,第一节线性规划问题及其数学模型,例2：靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万立方米，在两个工厂之间有一条流量为每天200万立方米的支流。第一化工厂每天排放含有某种有害物质的工业污水2万立方米，第二化工厂每天排放含有这种污水1.4万立方米，,第一节线性规划问题及其数学模型,从第一化工厂排出的工业污水流到第二化工厂以前，有20%可以自然净化。根据环保要求，河流中工业污水的含量应不大于0.2%。这两个工厂都需各自处理一部分工业污水。第一化工厂处理工业污水的成本是1000元/万立方米，第二化工厂处理工业污水的成本是800元/万立方米。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂总的处理工业污水费用最小。,第一节线性规划问题及其数学模型,解题思路：用数学模型来描述。约束条件：设第一化工厂每天处理工业污水量为x1万立方米，第二化工厂每天处理工业污水量为x2万立方米，从第一化工厂到第二化工厂之间，河流中工业污水的含量要不大于0.2%。由此可得近似关系式（2-x1）/500 0.2%。流经第二化工厂后，河流中的工业污水仍要不大于0.2%，这时有近似关系式0.8（2-x1）+（1.4-x2）/(500+200)0.2%,第一节线性规划问题及其数学模型,由于每个工厂每天处理的工业污水量不会大于每天的排放量，故有x12；x21.4目标函数：求两厂用于处理工业污水的总费用最小，即z=1000 x1+800 x2。,第一节线性规划问题及其数学模型,综上所述，数学模型为：,目标函数 minz=1000 x1+800 x2满足约束条件（2-x1）/500 0.2%0.8(2-x1)+(1.4-x2)/(500+200)0.2%x12 x21.4X1,x20,举例,例：生产计划问题假设工厂要根据拥有的资源和设备，计划生产甲、乙两种产品，其主要资源有钢材4吨、铜材3吨。专用设备能力8千台时。资源与设备能力的消耗定额及单位产品所获利润如表1-1所示：问如何安排生产，才能使该厂获得的利润最大。,举例,生产计划问题的数据表,x1,x2,使总利润f=2x1+2x2最大,解：由题意可知：在加工时间和利润与产品产量成线性关系的假设下，考虑到甲、乙两种产品的生产量不能为负数，即x1,x20，于是最优方案写成线性规划的数学模型为：,练习,生产计划问题（资源利用问题）胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子销售价格30元/个，生产桌子和椅子要求需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每个月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？,练习,某工厂生产甲、乙产品。已知生产甲种产品1吨需耗A 种矿石10吨，B种矿石5吨，煤4吨；生产乙种产品1吨需耗A 种矿石4吨，B种矿石4吨，煤9吨。每1吨甲种产品的利润是600元，每1吨乙种产品的利润是1000元。工厂在生产这两种产品的计划中要求消耗A种矿石不超过300吨,B种矿石不超过200吨，煤不超过360吨。甲，乙两种产品应各生产多少吨（精确到0.1吨），能使利润总额达到最大值？,练习,例：合理下料问题,某钢筋车间，现用的原材料是长度10米的钢筋（直径相同），需要制作一批长度为3米的钢筋90根，长度为4米的钢筋60根，问怎样下料既满足需要，又使原材料最少？解：根据题意：有如下三种下料方式：1）截成3米的3根。2）截成3米的2根，4米的1根。3）截成4米的2根。设三种下料方式B1,B2,B3分别用原材料（10米）x1,x2,x3根，列成表1-7：,例：合理下料问题,下料方式表,可转化成求下面的线性规划问题：min f=x1+x2+x3,下料方式,x1,x2,x3,OBJECTIVE FUNCTION VALUE 1)53.00000 VARIABLE VALUE REDUCED COST X1 2.000000 1.000000 X2 42.000000 1.000000 X3 9.000000 1.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 0.000000 3)0.000000 0.000000,min x1+x2+x3st3x1+2x2=90 x2+2x3=60endgin 3,第一节线性规划问题及其数学模型,从以上例子可以看出，它们都是属于一类优化问题。它们的共同特征：1、每一个问题都用一组决策变量（x1，x2，xn）表示某一方案，这组决策变量的值就代表一个具体方案，一般这些变量取值是非负且连续的。2、存在有关的数据，同决策变量构成互不矛盾的约束条件，这些约束条件可用一组线性等式或线性不等式来表示。3、都有一个要求达到的目标，它可用决策变量及其有关的价值系数构成的线性函数来表示。按问题的不同，要求目标函数实现最大化或最小化。,第一节线性规划问题及其数学模型,满足以上三个条件的数学模型称为线性规划的数学模型。其一般形式为：,价值系数,目标函数,技术系数,限额系数,约束条件,变量的非负约束条件,1.2 图解法,对例1用图解法求解。,4x1=16,4x2=12,x1+2x2=8,Q1,Q2,Q3,Q4,可行域,1.2 图解法,4x1=16,4x2=12,x1+2x2=8,Q1,Q2(4,2),Q3,Q4,可行域,可行域：阴影区域中的每一个点（包括边界点）都是这个线性规划问题的解（称可行解），此区域是线性规划问题的解的集合，称为可行域。,等值线,x1,x2,1.2 图解法,上例中求解得到问题的最优解是唯一的，但对一般线性规划问题，求解结果可能出现系以下几种情况：1、无穷多最优解（多重最优解）若将例1中的目标函数变为maxz=2x1+4x2，则表示目标函数中以参数z的这族平行直线与约束条件x1+2x28的边界线平行。当z值由小变大时，将与线段Q2Q3重合。线段Q2Q3上任意一点都使z取得相同的最大值，则这个线性规划问题有无穷多最优解（多重最优解）。,1.2 图解法,1、无穷多最优解（多重最优解）,（4,2）,（4,0）,（0,0）,（2,3）,用图解法解下面的例子Max z=2X1+4X 2 X1+2X2 8(1)4X1 16（2）4X2 12（3）X1，X2 0（4）,无穷多最优解,注意：多重解产生的原因，是因为目标函数线与第（1）条约束线的斜率相等。,(1),(2),(3),(8,0),(0,4),1.2 图解法,2、无界解Max z=x1+x2-2x1+x2 4（1）x1x2 2（2）x1,x2 0（3）,（2，0）,（0，4）,（0，0）,无界解（不等于无可行解）在这里需要注意的是，可行域无界不等于问题无界，这要看目标函数的情况。如把该问题中目标函数x1的系数由原来的1改为3/2时，该问题有最优解Z(0,4)4。,1.2 图解法,3、无可行解Max z=2x1+3x2 x1+2x2 8(1)4x1 16(2)4x2 12(3)-2x1+x2 4(4)x1,x2 0(5),（-2，0）,（0，4）,（4，0）,（4，2）,无可行解（约束条件无共同区域）,1.2 图解法,从图解法中直观地见到，当线性规划问题的可行域非空时，它是有界或无界凸多边形。若线性规划问题存在最优解，它一定在有界可行域的某个顶点得到；若在两个顶点同时得到最优解，则它们连线上的任意一点都是最优解，即有无穷多最优解。,1.3线性规划问题的标准形式,标准形式为：,在标准形式中规定各约束条件的右端项bi0，否则等式两端同乘以“-1”。,1.3线性规划问题的标准形式,用向量和矩阵符号表述：,1.3线性规划问题的标准形式,实际碰到各种线性规划问题的数学模型都应变换为标准型式后求解。,1.3线性规划问题的标准形式,如何变换为标准型的问题。标准型的特点：1、目标函数求极大 2、约束方程全为等式3、变量全为非负 4、约束条件右端常数项bi 0（I=1,2,m）,1.3线性规划问题的标准形式,化标准形式的一般步骤1、目标函数极小化“极大化”2、约束条件的右端项 bi0“bi0”3、约束条件为不等式 或“=”4、取值无约束（自由）变量“非负变量”5、取值非正变量“非负变量”,1.3线性规划问题的标准形式,（1）极小化目标函数的问题设目标函数为 Min z=CX令 z-z，得maxz=-CX但必须注意，尽管以上两个问题的最优解相同，但它们最优解的目标函数值却相差一个符号，即 Min z-Max z=CX,1.3线性规划问题的标准形式,注意：目标函数值相差一个符号,1.3线性规划问题的标准形式,(2)约束方程为不等式的问题约束方程为“”不等式，则在“”不等式的左端加入非负松弛变量。约束方程为“”不等式，则在“”不等式的左端减去一个非负剩余变量。,1.3线性规划问题的标准形式,例3：将例1的数学模型化为标准型例1的数学模型为：,加上松弛变量,所加松弛变量表示没有被利用的资源。当然也没有利润，在目标函数中其系数应为0。,1.3线性规划问题的标准形式,3、变量无符号限制的问题当某变量xk无限制时，则令xk=xk-xk，xk,xk 0,将下述线性规划问题化为标准型,1.3线性规划问题的标准形式,步骤：(1)用x3-x3替换x3，其中x3，x3 0；(2)在第一个约束不等式号的左端加入松弛变量x4；(3)在第二个约束不等式号的左端减去剩余变量x5；(4)令z=-z，把求min z 改为求max z，即可得到该问题的标准型,标准型,1.3线性规划问题的标准形式,4、若bi为负，则约束等式两边同乘(-1)。,1.3线性规划问题的标准形式,1、因x3无约束，所以令2、第一个约束条件是“”号，因此在“”号左边加入松弛变量x4。3、第二个约束条件是“”号，因此在“”号左边减去剩余变量x5。4、第三个约束条件是“”号且常数项为负数，因此在“”号左边加入松弛变量x6，同时两边乘以“-1”。5、因目标函数是最小值，令z=-z，得maxz=-CX,即当Z达到最小值时Z达到最大值。,1.3线性规划问题的标准形式,1.3线性规划问题的标准形式,5、变量为有界变量的问题如变量xja,b，即axjb，0 xj-a b-a令xj=xj-a 0则xj+xn+1=b-a 且 xj 0,1.3线性规划问题的标准形式,例：把下面问题标准化,1.3线性规划问题的标准形式,解：x2无限制，令x2=x2-x2,x2，x2 0因x30,令x3=-x3 0则标准型为：,注：解完一定要代回到原问题,1.3线性规划问题的标准形式,例4：将下述线性规划问题化为标准型,令x3=x4-x5，其中x4,x50,令z=-z，把求minz改为求maxz,1.4线性规划问题解的概念,可行解（Feasible Solution)：满足约束条件（1-5）式、（1-6）式的解。,1.4线性规划问题解的概念,基：若A中一个子矩阵B是可逆矩阵|B|0，则方阵B称为LP问题的一个基。B中的任一列成为LP问题的一个基向量(共有m个)。与基向量对应的变量为基变量。A中其他列向量叫基B的非基向量(共有n-m个)。与非基向量对应的变量为非基变量。,基向量,1.4线性规划问题解的概念,A=(P1 Pm Pm+1 Pn)=(BN)基向量 非基向量,X=(x1 xmxm+1 xn)T=(XBXN)T 基变量 非基变量 XB XN,举例,解 约束条件的系数矩阵为25矩阵,易知r(A)=2,2阶子矩阵有,其中第一列和第三列构成的2阶矩阵不是一个基，基矩阵只有9个。,举例,当确定某一子矩阵为基矩阵时。则基矩阵对应的列向量为基向量,在上例中B2的基向量是A中的第一列和第四列，其余列向量是非基向量，x1、x4是基变量，x2、x3、x5是非基变量。基变量、非基变量是针对某一确定基而言的，不同的基对应的基变量和非基变量也不同。,1.4线性规划问题解的概念,基解：对某一确定的基B，令非基变量等于0，利用（1-5）求出基变量，则这组解称为基B的基解。,1.4线性规划问题解的概念,基可行解（Feasible Solution)：满足非负条件的基解称为基可行解。可行基：对应于基可行解的基。,最优解(Optimal Solution)：使目标函数达到最大值的可行解。对应的目标函数值称为最优值。可行解：是约束方程组的解并且满足非负条件。基解是约束方程组具有特定性质的解，它至多有m个非0分量，但未必满足非负性。,显然，只要基本解中的基变量的解满足式（1-6）的非负要求，那么这个基本解就是基本可行解。,在上例中，对来说，x1,x2是基变量，x3,x4，x5是非基变量，令x3=x4=x5=0，则式（1-5）为,举例,对B2来说，x1,x4,为基变量，令非变量x2,x3,x5为零，由式（1-5）得到，x4=4，,因|B1|，由克莱姆法则知，x1、x2有唯一解x12/5,x2=1则 基解为,举例,反之，可行解不一定是基可行解例如 满足式（1-5）（1-6），但不是任何基矩阵的基解。,由于 是基解，从而它是基可行解，在 中x10,因此不是可行解，也就不是基可行解。,基解为,基本概念,可行基：基可行解对应的基称为可行基；最优基：基最优解对应的基称为最优基；如上述B3就是最优基，最优基也是可行基。,基最优解 最优解是基解称为基最优解。例如，满足式（1-4）(1-6)是最优解,又是B3的基解,因此它是基最优解。,1.4线性规划问题解的概念,基解（0，Q1,Q2,Q3,Q4以及延长各条线的交点）,基可行解（0，Q1,Q2,Q3,Q4），非0分量的数目不大于m,并且都是非负的。,1.4线性规划问题解的概念,约束方程组（1-5）具有基解的数目最多是 个。一般基可行解的数目要小于基解的数目。注：基解中的非0分量的个数小于m个时，该基解是退化解。,1.4线性规划问题解的概念,1.4线性规划问题解的概念,1.4线性规划问题解的概念,1.4线性规划问题解的概念,1.4线性规划问题解的概念,1.4线性规划问题解的概念,1.4线性规划问题解的概念,1.4线性规划问题解的概念,比较z1,z3,z4,可知z3=117/5为最大值。所以，最优解为X(3)=(34/5,0,0,7/5),1 可行解与最优解：,最优解一定是可行解，但可行解不一定是最优解。,线性规划解之间的关系,基解不一定是可行解，可行解也不一定是基解。,2 可行解与基解：,3 可行解与基可行解：,基可行解一定是可行解，但可行解不一定是基解。,4 基解与基可行解：,5 最优解与基解：,最优解不一定是基解，基解也不一定是最优解。,问题：最优解与基本可行解？,基可行解一定是基解，但基解不一定是基可行解。,线性规划问题的最优解,第2节 线性规划问题解的概念,2.1基本概念,凸集：设K是n维欧氏空间的一个点集，若对任意两点X(1),X(2)K的连线上的所有点,存在，则称集合K为凸集。（convex set）。也称X是X(1)，X(2)的凸组合。,第2节 线性规划问题解的概念,凸组合：设X(1),X(2),X(k)是n维欧氏空间En中k个点。若存在 则称X为X(1),X(2),X(k)的凸组合。（当01时，称为严格凸组合）,第2节 线性规划问题解的概念,任何两个凸集的交集是凸集。,第2节 线性规划问题解的概念,顶点：设K是n维向量组成的凸集，X K，若X不能用不同的两点X(1),X(2)K（X(1)X(2)）的线性组合表示为，则称X为凸集的顶点（极点）。（以圆球为例）,若x是集合K的顶点，则x一定不在K中任意不同于它的两点的连线内。,2.2 几个定理,定理1：若线性规划问题存在可行域，则其可行域 是凸集。,引理1：线性规划问题的可行解X=(x1,x2,xn)T为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的。,定理2：线性规划问题的基可行解X对应于可行域D的顶点。,2.2 几个定理,定理3 若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。,2.2 几个定理,证明：为了证明满足线性规划问题的约束条件 的所有点（可行解）组成的集合是凸集，只要证明D中任意两点连线上的点必然在D内即可。设,定理1：若线性规划问题存在可行域，则其可行域 是凸集。,2.2 几个定理,则有,2.2 几个定理,2.2 几个定理,2.2 几个定理,引理1：线性规划问题的可行解X=(x1,x2,xn)T为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的。,2.2 几个定理,定理2：线性规划问题的基可行解X对应于可行域D的顶点。,2.2 几个定理,2.2 几个定理,例5 设X是三角形中任意一点，X(1),X(2)和X(3)是三角形的三个顶点，试用三个顶点得坐标表示X。,解：任选一顶点X(2),做一条连线XX(2)；并延长至X(1)X(3)连线上的点X。,2.2 几个定理,因X 是连线X(1)X(3)上的点。故可用X(1)、X(3)线性组合表示为,2.2 几个定理,定理3 若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。证明：设X(1)，X(2)，X(k)是可行域的顶点，若X(0)不是顶点，且目标函数在X(0)处达到最优，z*=CX(0)(标准型是z*=maxz)因X(0)不是顶点，所以它可以用D的顶点线性表示为,2.2 几个定理,在所有的顶点中必然能找到某一个点X(m)，使CX(m)是所有CX(i)中最大者。并将X(m)代替（1-10）式中的所有X(i)，这就得到,有时目标函数可能在多个顶点处达到最大值。这时在这些顶点得凸组合上也达到最大值。称这种线性规划问题有无限多个最优解。,2.2 几个定理,假设 是目标函数达到最大值的顶点，若 是这些顶点得凸组合，即,注：若可行域为无界，则可能无最优解，若有也必定在某顶点上得到。,2.2 几个定理,结论：线性规划问题的所有可行解构成的集合是凸集，也可能为无界域，它们有有限个顶点，线性规划问题的每个基可行解对应可行域的一个顶点；若线性规划问题有最优解，必在某顶点上得到。,第三节单纯形法,单纯形法的基本思路：从可行域中某一个顶点开始，判断此顶点是否是最优解，如不是,则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。,第三节单纯形法,例6 试以例1来讨论如何用单纯形法求解。例1的标准型为,约束方程式的系数矩阵,基变量,非基变量,第一步：先把问题标准化。,第三节单纯形法,从（1-12）可以看到x3,x4,x5的系数列向量,是线性独立的，这些向量构成一个基,令非基变量为0,解出基变量得基可行解,第三节单纯形法,对应于B的变量x3,x4,x5为基变量，从（1-12）式中可以得到,将（1-13）式代入目标函数（1-11）式得到,当令非基变量x1=x2=0，便得到z=0。这时得到一个基可行解X(0)。,这个基可行解表示：工厂没有安排生产产品、；资源都没有被利用，所以工厂的利润指标z=0。,不是最优解。,第三节单纯形法,由（1-14）可以看出，非基变量x1,x2的系数都是正数，因此将非基变量变为基变量，目标函数的值就可能增大。所以只要在目标函数的表达式中还存在有正系数的非基变量，这表示目标函数值还有增加的可能，就需要将非基变量与基变量对换。,第三节单纯形法,思路：一般选择正系数最大的那个非基变量x2为换入变量，将它换入到基变量中去，同时还要确定基变量中有一个要换出来成为非基变量。,第三节单纯形法,步骤：将x2定为换入变量后，必须从x3,x4,x5中确定一个换出变量，并保证其余的都是非负的。当x1=0，由（1-13）式得到,第三节单纯形法,由这些资源中的薄弱环节，就确定了产品的产量。由原材料B的数量确定了产品的产量。X2=12/4=3件,第三节单纯形法,为了求得以x2，x3，x4为基变量的一个基可行解和进一步分析问题，将x2和x5的位置互换。得,第三节单纯形法,再将（1-17）式代入目标函数（1-11）式得：,令非基变量x1=x5=0，得z=9,得另一个基可行解X(1)。,X(1)=（0，3，2，16，0）T,系数为正,第三节单纯形法,代入目标函数,令非基变量x3=x5=0，得z=13,得另一个基可行解X(2)=（2，3，0，8，0）T,X(1)不一定是最优解。继续迭代,x1为换入变量。令x5=0，可知,x3为换出变量。将x1和x3的位置互换。,第三节单纯形法,X(2)不一定是最优解。继续迭代x5为换入变量。令x3=0，可知,x4为换出变量。将x5和x4的位置互换。,代入目标函数,第三节单纯形法,令非基变量x3=x4=0，得z=14,得最优解X(3)。X(3)=（4，2，0，0，4）T即当产品生产4件、生产2件，工厂才能得最大利润。,第三节单纯形法,举例,举例,X1为换入变量，X4为换出变量，,举例,X2为换入变量，X3为换出变量，,举例,一、单纯形表的推导,一、单纯形表的推导,一、单纯形表的推导,把式(4)、(5)写成矩阵形式：,一、单纯形表的推导,基本可行解,系数矩阵,目标含数值,检验数,xB,xN,一、单纯形表,举例：,3.2初始可行基的确定,确定初始可行基(1)直接观察,3.2初始可行基的确定,(2)化标准型(约束条件是“”的不等式)得方程组,3.2初始可行基的确定,以B作为可行基，将（1-22）每个等式移项得,3.2初始可行基的确定,3.2初始可行基的确定,(3)约束条件是“”的不等式及等式约束情况若不存在单位矩阵时，就采用人造基方法。即对不等式约束减去一个非负的剩余变量后，再加上一个非负的人工变量；对于等式约束再加上一个非负的人工变量，总能得到一个单位矩阵。,3.3最优性检验与解的判别,3.3最优性检验与解的判别,3.3最优性检验与解的判别,3.3最优性检验与解的判别,1、最优解的判别定理,检验数：,3.3最优性检验与解的判别,2、无穷多最优解的判别定理,举例,举例,3.3最优性检验与解的判别,3、无界解判别定理,4、无解：含人工变量的单纯形表解中两阶段法中第一阶段无解或只有非0解大M法中终表时人工变量没出基且不为0,3.3最优性检验与解的判别,无界解,3.3最优性检验与解的判别,3.3最优性检验与解的判别,以上讨论都是针对标准型，即目标函数极大化时的情况。当目标函数极大化时，将其化为标准型，若不化为标准型，只需在上述1、2中把j0改为j0；在上述3中把m+k0改为m+k0。,3.4基变换,基变换：从原可行基中换一个列向量，得到一个新的可行基，称为基变换。为了换基，首先要确定换出变量，让它们相应的系数列向量进行对换，就得到一个新的基可行解。1.换入变量的确定换入变量：当某些j0时，xj增加则目标函数值还可以增大，这时要将某个非基变量xj换到基变量中去，则xj称为换入变量。,3.4基变换,若有两个以上的j0，一般选j0中的大者，即,对应的xj为换入变量,2.换出变量的确定,设P1,P2,Pm是一组线性独立的向量组，它们对应的基可行解是X(0)。将它代入约束方程组（1-21）得,其它的向量Pm+1,Pm+2,Pm+t,，Pn都可以用P1,P2,Pm线性表示，若确定非基变量pm+t为换入变量,必然可找到一组不全为0的数（i=1,2,m）使得,3.4基变换,3.4基变换,xi换出变量,按最小比值确定值，称为最小比值规则。,3.4基变换,3.4基变换,3.4基变换,3.4基变换,由此可见，X(1)的m个非0分量对应的列向量Pj（j=1,2,m,jl）与Pm+l是线性独立的，即经过基变换得到的解是基可行解。从一个基可行解到另一个基可行解的变换就是进行一次基变换。几何意义：从可行域的一个顶点转向另一个顶点。,3.5迭代（旋转）运算,用向量方程描述的用基可行解的转换方法在实际计算时不太方便，因此采用系数矩阵法。系数矩阵法把约束方程化为标准形式,3.5迭代（旋转）运算,3.5迭代（旋转）运算,3.5迭代（旋转）运算,3.5迭代（旋转）运算,变换的步骤:(1)将增广矩阵中的第L行除以alk，得到,(2)将（1-34）中xk列的各元素，除alk变换为1外，其他都应变换为0，得,3.5迭代（旋转）运算,得变换后系数矩阵各元素的变换关系式：,下面是详细的推导步骤：,3.5迭代（旋转）运算,3.5迭代（旋转）运算,3.5迭代（旋转）运算,(3)经过初等变换后的新增广矩阵,3.5迭代（旋转）运算,(4)由上式可以看到x1,x2,xk,xm的系数列向量构成mm单位矩阵，它是可行基，当非基变量xm+1,xl,xm为0时，就得到一个基可行解X(1).,3.5迭代（旋转）运算,例：试用上述方法计算例6的两个基变换。解 将例6的约束方程组的系数矩阵写成增广矩阵,3.5迭代（旋转）运算,第四节单纯形法的计算步骤,4.1单纯形表,第四节单纯形法的计算步骤,第四节单纯形法的计算步骤,4.1单纯形表,根据增广矩阵设计计算表,初始单纯形表,表1-2的说明,XB列中填入基变量，这里是x1，x2,，xm；CB列中填入基变量的价值系数，这里是c1,c2,cm；它们是与基变量相对应的；b列中填入约束方程组右端的常数；cj行中填入基变量的价值系数c1,c2,cn；i列的数字是在确定换入变量后，按规则计算后填入；最后一行称为检验数行，对应各非基变量xj的检验数是,4.2计算步骤,1、找出初始可行基，确定初始可行解，建立初始单纯形表。2、检验各非基变量xj的检验数是,Pk0，则此问题是无界，停止计算。否则转入下一步。,4.2计算步骤,4.2计算步骤,1、初始单纯形表 表1-3,4.2计算步骤,4.2计算步骤,5、重复24的计算步骤地表1-5,最后一行的所有检验数都已为负或0，这表示目标函数值已不可能再增大，则的最优解,举例,举例,LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1)7.000000 VARIABLE VALUE REDUCED COST X1 0.000000 3.500000 X2 3.000000 0.000000 X3 1.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 1.000000 3)0.000000 0.500000 NO.ITERATIONS=2 RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1-1.000000 3.500000 INFINITY X2 2.000000 INFINITY 1.000000 X3 1.000000 1.000000 1.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 4.000000 INFINITY 1.000000 3 6.000000 2.000000 6.000000,举例,补充题,已知某线性规划的单纯形表，求价值系数C及目标向量Z。,习题1.8,习题1.8,(1)表中有唯一最优解d0,c10,a10(4)d0,c10 c1c2,3/a30时,举例,下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为约束形式为，x1，x2，x3为松弛变量，表中解的目标函数值为z=14,0,0,0,28,1,2,2,0,28,举例,a=7,b=-6,c=0,d=1,e=0,f=1/3,g=0,第五节单纯形法的进一步讨论,引例,第五节单纯形法的进一步讨论,第五节单纯形法的进一步讨论,第五节单纯形法的进一步讨论,5.1人工变量法设线性规划问题的约束条件是,第五节单纯形法的进一步讨论,基变量中不再含有非0的人工变量，则原问题有解。若当所有cj-zj0,而其中还有某个非0的人工变量，则原问题无可行解。,第五节单纯形法的进一步讨论,1.大M法在线性规划问题的约束条件中加入人工变量后，要求人工变量对目标函数的取值无影响，需假定人工变量在目标函数中的系数为（-M），这样目标函数要实现最大化时，必须把人工变量从基变量换出。否则目标函数不可能实现最大化。,第五节单纯形法的进一步讨论,第五节单纯形法的进一步讨论,第五节单纯形法的进一步讨论,例8 现有线性规划问题,第五节单纯形法的进一步讨论,松弛变量,剩余变量,人工变量,M是一个任意大的正数,第五节单纯形法的进一步讨论,因本例的目标函数是要求min，所以用所有cj-zj0来判别目标函数是否实现了最小化.用单纯形法进行计算时，,检验数最小,在表的最终计算结果表中，表明已得到最优解是：x1=4,x2=1,x3=9，x4=x5=x6=x7=0；目标函数z=-2,大M法,大M法,注意：若设原来的问题为，用大M法构造的新问题为，则（1）设有最优解，若人工变量为0，则问题有最优解；若人工变量不为0，则问题无解；（2）设有无界解，若人工变量为0，则问题有无界解；若人工变量不为0，则问题无解；,举例,举例,检验数0,检验数0，有最优解。但人工变量x5=50,故原问题无可行解。,2.两阶段法,用电子计算机求解含人工变量的线性规划问题时，只能用很大的数来代替M，这就可能造成计算上的错误。故介绍两阶段法求线性规划问题。,2.两阶段法,第一阶段：不考虑原问题是否存在基可行解；给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数和要求实现最小化。,2.两阶段法,然后用单纯形法求解上述模型，若得到=0，这说明原问题存在基可行解，可以进行第二段计算。否则原问题无可行解，应停止计算,2.两阶段法,第二阶段：将第一阶段计算得到的最终表，除去人工变量。将目标函数行的系数，换原问题的目标函数系数，作为第二阶段计算的初始表。各阶段的计算方法及步骤与第3节单纯形法相同。下面举例说明,2.两阶段法,例9 试用两阶段法求解线性规划问题,2.两阶段法,解：先在上述线性规划问题的约束方程中加入人工变量，给出第一阶段的数学模型为：,2.两阶段法,第一阶段用单纯形法求解，见表1-7。求得的结果是=0，得到最优解是x1=0,x2=1,x3=1,x4=12,x5=x6=x7=0因人工变量x6=x7=0，所以(0，1，1，12，0)T是这线性规划问题的基可行解。,2.两阶段法,人工变量,表 1-7,2.两阶段法,由于W=0 人工变量都不是基变量于是可以进行第二阶段运算。将第一阶段的最终表中的人工变量取消填入原问题的目标函数的系数。进行第二阶段计算，见表1-8。,W=0 人工变量都不是基变量W0 原问题无可行解W=0 人工变量部分为基变量，但它们为0，此为退化情形,2.两阶段法,第二阶段计算，见表1-8,检验数0,2.两阶段法,从表1-8中得到最优解为x1=4,x2=1,x3=9,目标函数值 z=-2.,2.两阶段法,2.两阶段法,第二阶段,2.两阶段法,求解线性规划问题,原问题无可行解,补充习题,有些原来问题中有等式约束时，若一些变量对应A中的列为单位阵的某些列,则此时的约束等式无需添加人工变量。,注意,注意：在两阶段法迭代过程中，某人工变量一旦出基，则可从表中删除此列。人工变量可以避免，只要利用初等变换凑出一个单位阵。单位阵中相应的行元素为1处所对应的b中分量非负。,5.2 退化,单纯形法计算中用规则确定换出变量时，有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这就出现退化解。这时换出变量xl=0，迭代后目标函数值不变。这时不同基表示为同一顶点。有人构造了一个特例，当出现退化时，进行多次迭代，而基从B1,B2，又返回到B1，即出现计算过程的循环，便永远达不到最优解。,5.2 退化,尽管计算过程的循环现象极少出现，但还是有可能的。如何解决这问题?先后有人提出了“摄动法”，“字典序法”。1974年由勃兰特(Bland)提出一种简便的规则，简称勃兰特规则：(1)选取cj-zj0中下标最小的非基变量xk为换入变量，即k=min(jcj-zj0)(2)当按规则计算存在两个和两个以上最小比值时，选取下标最小的基变量为换出变量。按勃兰特规则计算时，一定能避免出现循环。,5.2 退化,一个或多个基变量为0的基本可行解，成为退化的基本可行解（约束方程中b有0解）退化线性规划问题的可行基不唯一。,【例】求解线性规划,解 用大M单纯形法，加入人工变量x4、x5，构造数学模型,退化与循环,单纯形法 Simplex Method,出现退化,（2）中选x5出基便得到表（5），或在表（3）中选x3进基便得到表（5），（3）和（5）的最优解从数值上看相同，但它们是两个基可行解，对应于同一个极点。,5.3 检验数的几种表示形式,本书以max z=CX;AX=b,X0为标准型；以cj-zj0，（j=1,2,n）为最优解的判别准则。还有其他的形式。为了避免混淆，现将几种情况归纳如下。设x1,x2,xm为约束方程的基变量，于是可得,5.3 检验数的几种表示形式,将它们代入目标函数后，可有两种表达形式,判别准则的选择,要求目标函数实现最大化时，若用(1-37)式来分析，就得到cj-zj0,（j=1,2，,n）的判别准则。若用(1-38)式来分析，就得到zj-cj0,（j=1,2,n）的判别准则。要求目标函数实现最小化时，可用(1-37)式或(1-38)式来分析，这时分别用cj-zj0或zj-cj0，（j=1,2,n）来判别目标函数已达到最小。,几种判别准则的汇总，表1-9。,5.4 单纯形法小结,(1)根据实际问题给出数学模型，列出初始单纯形表。进行标准化，见表1-10。分别以每个约束条件中的松弛变量或人工变量为