运筹学线性规划和单纯形法.ppt

1,运筹学 第一章线性规划及单纯形法Linear Programming and Simplex Method,2,本章内容提要,线性规划问题及其数学模型线性规划解的概念单纯形法原理及算法步骤线性规划应用建模,3,如何合理地利用有限的人、财、物等资源，得到最好的经济效果?,1.1 问题的提出,线性规划是以数学为工具，研究在一定的人、财、物等资源条件下，用最少的资源耗费，取得最大的经济效果。,1.线性规划问题及数学模型,4,例1.1：某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：问题：工厂应如何安排生产可获得最大的总利润？,5,解：设变量xi为第i种（甲、乙）产品的生产件数（i1，2）。根据题意，我们知道两种产品的生产受到设备能力（机时数）的限制。对设备A，两种产品生产所占用的机时数不能超过65，于是我们可以得到不等式：3 x1+2 x2 65；对设备B，两种产品生产所占用的机时数不能超过40，于是我们可以得到不等式：2 x1+x2 40；,6,对设备C，两种产品生产所占用的机时数不能超过75，于是我们可以得到不等式：3x2 75；另外，产品数不可能为负，即 x1,x2 0。同时，我们有一个追求目标，即获取最大利润。于是可写出目标函数z为相应的生产计划可以获得的总利润：z=1500 x1+2500 x2。综合上述讨论，在加工时间以及利润与产品产量成线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下的线性规划模型：,7,目标函数 max z=1500 x1+2500 x2约束条件 s.t.3x1+2x265 2x1+x240 3x275 x1,x2 0,这是一个典型的利润最大化的生产计划问题。其中，“max”是英文单词“maximize”的缩写，含义为“最大化”；“s.t.”是“subject to”的缩写，表示“满足于”。因此，上述模型的含义是：在给定条件限制下，求使目标函数z达到最大的x1,x2 的取值。,8,营养配餐问题 假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？,9,各种食物的营养成分表,10,解：设xj为第j种食品每天的购入量，则配餐问题的线性规划模型为：min S=14x1+6x2+3x3+2x4 s.t.1000 x1+800 x2+900 x3+200 x4 3000 50 x1+60 x2+20 x3+10 x4 55 400 x1+200 x2+300 x3+500 x4 800 x1，x2，x3，x4 0,11,线性规划数学模型的构成三要素,决策变量表示某种重要的可变因素，变量的一组数据代表一个解决的方案或措施，用x1,x2,xn表示目标函数决策变量的函数，目标可以是最大化或最小化约束条件对决策变量取值的限制条件，由决策变量 x1,x2,xn 的不等式组或方程组构成,12,一般形式 max(min)z=c1x1+c2x2+cnxn,Subject to a11 x1+a12 x2+a1n xn(=,)b1a21 x1+a22 x2+a2n xn(=,)b2.am1 x1+am2 x2+amn xn(=,)bm x1,x2,xn 0,13,14,标准形式max z=c1x1+c2x2+cnxn,Subject toa11 x1+a12 x2+a1n xn=b1a21 x1+a22 x2+a2n xn=b2 am1 x1+am2 x2+amn xn=bm x1,x2,xn 0其中bi 0，i=1,2,m,15,标准形式,16,标准形式：用向量和矩阵表述,17,可以看出，线性规划的标准形式有如下四个特点：目标最大化、约束为等式、决策变量均非负、右端项非负。对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式。,18,1.极小化目标函数的问题：设目标函数为 min f=c1x1+c2x2+cnxn则可以令z-f，该极小化问题与下面的极大化问题有相同的最优解，即 max z=-c1x1-c2x2-cnxn 但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即 min f-max z,19,2、约束条件不是等式的问题：设约束条件为 ai1 x1+ai2 x2+ain xn bi可以引进一个新的变量xn+1，使它等于约束右边与左边之差 xn+1=bi(ai1 x1+ai2 x2+ain xn)显然，xn+1也具有非负约束(xn+1 0)，这时新的约束条件成为 ai1 x1+ai2 x2+ain xn+xn+1=bi,20,当约束条件为 ai1 x1+ai2 x2+ain xn bi 时，类似地令 xn+1=(ai1 x1+ai2 x2+ain xn)-bi 显然有 xn+1 0，这时新的约束条件成为 ai1 x1+ai2 x2+ain xn-xn+1=bi,为了使约束由不等式成为等式而引进的变量 xn+1 称为“松弛变量”，后一种情况也称为“剩余变量”。,21,3.变量无符号限制的问题：在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令 xj=xj-xj”其中 xj 0，xj”0即用两个非负变量之差来表示一个无符号限制的变量。当然xj的符号取决于xj和xj”的大小。,22,4.右端项有负值的问题：在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如 bi 0，则把该等式约束两端同时乘以-1，得到：-ai1 x1-ai2 x2-ain xn=-bi。,5.xj 0问题：令 xj=-xj 即可。,23,例1.2：将以下线性规划问题转化为标准形式 min f=-3 x1+5 x2+8 x3-7 x4 s.t.2 x1-3 x2+5 x3+6 x4 28 4 x1+2 x2+3 x3-9 x4 39 6 x2+2 x3+3 x4-58 x1,x3 0,x4 0,24,解：首先，将目标函数转换成极大化,令 z=-f=3x15x28x3+7x4；其次考虑约束，有3个不等式约束，引进松弛变量x5,x6,x7 0；由于x2无非负限制，可令 x2=x2-x2”,其中 x20，x2”0；由于第3个约束右端项系数为-58，于是把该式两端乘以-1。因x4 0，令x4=-x4,则x4 0。,于是得以下标准形式的线性规划问题：,25,max z=3x15x2+5x2”8x3-7x4 s.t.2x13x2+3x2”+5x3-6x4+x5=28 4x1+2x2-2x2”+3x3+9x4-x6=39-6x2+6x2”-2x3+3x4-x7=58 x1,x2,x2”,x3,x4,x5,x6,x7 0,min f=-3 x1+5 x2+8 x3-7 x4s.t.2 x1-3 x2+5 x3+6 x4 28 4 x1+2 x2+3 x3-9 x4 39 6 x2+2 x3+3 x4-58 x1,x3 0,x4 0（原问题）,(标准型),26,2.线性规划的求解,(1)图解法只适用两个变量（2）单纯型法适用多个变量,27,解的定义：,称x=(x1,x2,xn)为线性规划的一个可行解，如果 x1,x2,xn 满足该线性规划的所有约束条件。一个线性规划的全体可行解构成的集合，称为该线性规划的可行域（集）。在一个线性规划的可行域中，使得目标函数达到最大（最小）的可行解x*=(x1*,x2*,xn*)称为该线性规划的最优解（即该线性规划的解）。一个线性规划的最优解所对应的目标函数的值z*=c1x1*+c2x2*+cnxn*称为该线型规划的最优值。,28,线性规划的图解法,对于只有两个变量的线性规划问题，可以二维直角坐标平面上作图表示线性规划问题的有关概念，并求解。图解法求解线性规划问题的步骤如下：(1)分别取决策变量x1，x2为坐标向量建立直角坐标系。,29,（2）找可行域。对每个约束条件（包括非负约束），先取其等式在坐标系中作出直线，并判断确定不等式所决定的半平面。各约束半平面交集形成一个区域(也有可能是空集），就是线性规划的可行集（可行域）；其中的点就是线性规划的可行解。如果可行集是空集，则该线性规划问题无可行解。,30,（3）确定最优解。任意给定目标函数一个值作一条目标函数的等值线，并确定该等值线平行移动后值增加的方向。平移此目标函数的等值线，使其达到既与可行域有交点又不可能使值再增加的位置(有时交于无穷远处，此时称无有限最优解）。若有交点时，此目标函数等值线与可行域的交点即最优解（一个或多个），此目标函数的值即最优值。,31,例1.3（续例1.1）：某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：,32,问题：工厂应如何安排生产可获得最大的总利润？用图解法求解。解：设变量xi为第i种（甲、乙）产品的生产件数（i1,2）。根据前面分析，可以建立如下的线性规划模型：max z=1500 x1+2500 x2 s.t.3x1+2x2 65(A)2x1+x2 40(B)3x2 75(C)x1,x2 0(D,E),33,按照图解法的步骤在以决策变量x1,x2为坐标向量的平面直角坐标系上对每个约束（包括非负约束）条件作出直线，并通过判断确定不等式所决定的半平面。各约束半平面交出来的区域即可行集或可行域如下图阴影所示。,34,图解法求解线性规划,z=1500 x1+2500 x2,35,任意给定目标函数一个值作一条目标函数的等值线，并确定该等值线平移后值增加的方向，平移此目标函数的等值线，使其达到既与可行域有交点又不可能使值再增加的位置，得到交点(5,25)T，此目标函数的值为70000。于是，我们得到这个线性规划的最优解x1=5,x2=25，最优值 z=70000。即最优方案为生产甲产品5件、乙产品25件，可获得最大利润为70000元。,36,例1.4：在例1.3的线性规划模型中，如果目标函数变为：max z=1500 x1+1000 x2 那么，最优情况下目标函数的等值线与直线（A）重合。这时，最优解有无穷多个，是从点(5,25)T到点(15,10)T 线段上的所有点，最优值为32500。如下图所示：,37,无穷多解的情况,z=1500 x1+1000 x2,z=1500 x1+2500 x2,38,例1.5：在例2.1的线性规划模型中,如果约束条件（A）、（C）变为：3 x1+2 x2 65(A）3 x2 75(C）并且去掉（D、E）的非负限制。那么，可行域成为一个上无界的区域。这时，没有有限最优解，如下图所示：,39,无有限解的情况,40,例1.6：在例1.3的线性规划模型中，如果增加约束条件（F）为：x1+x2 40（F）那么，可行域成为空的区域。这时，没有可行解，显然线性规划问题无解。如下图所示：,41,无可行解的情况,x1+x240,42,线性规划的可行域和最优解有以下几种可能的情况 1.可行域为封闭的有界区域(a)有唯一的最优解；(b)有无穷多个最优解；2.可行域为无界区域(c)有唯一的最优解；,43,(d)有无穷多个最优解；(e)目标函数无界(即虽有可行解，但在可行域中，目标函数可以无 限增大或无限减少)，因而没有 有限最优解。3.可行域为空集(f)没有可行解，原问题无最优解,44,以上几种情况的图示如下：,可行域有界唯一最优解,可行域有界多个最优解,45,可行域无界唯一最优解,可行域无界无穷多最优解,46,可行域无界目标函数无界,可行域为空集无可行解,47,3.单纯形法原理,解:满足所有约束条件的解 x=(x1，x2，.，xn)称为线性规划问题的可行解。所有可行解的集合称为可行域。使目标函数达到最优值的可行解称为最优解。,3.1.线性规划解的概念,48,基：设A是约束方程组的mn 阶系数矩阵（设nm），秩为m。B=(P1,P2,Pm)是A中m阶非奇异子矩阵，则称B是线性规划问题的一个基矩阵，简称基。B中的列向量Pj 称为基向量，与基向量Pj对应的变量xj称为基变量，其它变量称为非基变量。令非基变量为0，则由Ax=b可求出一个解，这个解x称为基解。满足非负条件的基解称为基可行解。,49,max z=1500 x1+2500 x2s.t.3x1+2x2+x3=65 2x1+x2+x4=40 3x2+x5=75 x1,x2,x3,x4,x5 0,例1.7：把例1.1化为标准型：,50,3 2 1 0 0 A=P1,P2,P3,P4,P5=2 1 0 1 0 0 3 0 0 1 A 矩阵包含以下10个33的子矩阵：B1=P1,P2,P3 B2=P1,P2,P4 B3=P1,P2,P5 B4=P1,P3,P4 B5=P1,P3,P5 B6=P1,P4,P5 B7=P2,P3,P4 B8=P2,P3,P5 B9=P2,P4,P5 B10=P3,P4,P5,51,其中B4=0，因而B4不是该线性规划问题的基。其余均为非奇异方阵，因此该问题共有9个基。对于基B3=P1,P2,P5，在等式约束中令非基变量 x3=0,x4=0，解线性方程组：3 x1+2 x2+0 x5=65 2 x1+x2+0 x5=40 0 x1+3 x2+x5=75 得到x1=15,x2=10,x5=45，对应的基解为基可行解：x3=(x1,x2,x3,x4,x5)T=(15,10,0,0,45)T，对应的目标函数值z3=47500。故基B3是一个可行基。,52,类似可得到 x2=(5,25,0,5,0)T（对应B2,z2=70000）x5=(20,0,5,0,75)T（对应B5,z5=30000）x7=(0,25,15,15,0)T（对应B7,z7=62500）x10=(0,0,65,40,75)T（对应B10,z10=0）是基可行解，x2是最优解；而 x1=(7.5,25,-7.5,0,0)T（对应B1）x6=(65/3,0,0,-10/3,75)T（对应B6）x8=(0,40,-15,0,-45)T（对应B8）x9=(0,32.5,0,7.5,-22.5)T（对应B9）是基解但不可行。,53,可行解，基可行解，基解的关系,54,3.2.凸集与顶点,凸集：如果在集合C中任意取两个点x1,x2，其连线上的所有点也都在集合C中，则称集合C为凸集。用数学解析式表达为：对n维欧式空间中的一个集合C,任意x1,x2 C，和实数a，均有 ax1+(1-a)x2 C(0a1)，则称C是凸集。,55,凸组合：如果x1,x2，xn是欧式空间中的点，若存在n个系数，u1,u2,un，,56,顶点：凸集C中的点x如果满足：对任意不同的x1,x2C和任意的a(0,1),x=ax1+(1-a)x2 恒不成立，则称x为凸集C的顶点,57,3.3.线性规划基本性质（单纯形法理论基础）,定理1.1：若线性规划问题有可行解，则其可行域x|Ax=b,x 0 是凸集（凸多面体）。,引理1.1：线性规划的可行解x=(x1,x2,.,xn)为基可行解的充分必要条件是x的正分量所对应的系数列向量是线性无关的。,58,定理1.2：线性规划问题的基可行解对应于可行域的顶点,定理1.3：若线性规划有最优解，则最优解必在可行域的顶点达到。,59,小结,线性规划可行解的全体构成一个凸集，每个可行解都对应这个凸集中的一点每个基可行解对应于可行域的一个顶点。若可行域非空则必有顶点存在，从而基可行解一定存在。一个基可行解对应着约束方程组系数矩阵中一组线性无关的向量，基解的个数不超过,若最优解存在，目标函数的最优值必在可行域的某个顶点上达到,60,基本思路是从可行域的一个顶点出发，沿着可行域的边界移到另一个相邻的顶点，使得新顶点的目标函数值比原目标函数值有改善；如此反复，直到找到目标函数值最大的顶点。,4.单纯形法,61,单纯形法的基本过程（有解情况下）,62,例1.8：用单纯形法的基本思路解例1.7的线性规划问题 max z=1500 x1+2500 x2 s.t.3 x1+2 x2+x3=65 2 x1+x2+x4=40 3 x2+x5=75 x1,x2,x3,x4,x5 0,63,第一次迭代：（1）取初始可行基 B10=(P3,P4,P5)，那么x3,x4,x5为基变量，x1,x2为非基变量。将基变量和目标函数用非基变量表示：z=1500 x1+2500 x2 x3=65-3 x1-2 x2 x4=40-2 x1-x2 x5=75-3 x2当非基变量x1,x2=0时，相应的基变量和目标函数值为x3=65,x4=40,x5=75;z=0，得到当前的基本可行解：x=(0,0,65,40,75)T;z=0。,64,（2）选择进基变量。在目标函数z=1500 x1+2500 x2中，非基变量x1,x2的系数都是正数，因此 x1,x2进基都可以使目标函数z增大。但x2的系数为2500，绝对值比x1的系数1500大，因此把x2作为进基变量可以使目标函数z增加更快。选择x2为进基变量，使x2的值从0开始增加，另一个非基变量x1保持零值不变。,65,（3）确定出基变量。在约束条件 x3=65-3 x1-2 x2 x4=40-2 x1-x2 x5=75-3 x2中，由于进基变量x2在3个约束条件中的系数都是负数，当x2的值从0开始增加时，基变量x3,x4,x5的值分别从当前的值65,40和75开始减少，当x2增加到25时，x5首先下降为0，成为非基变量。,66,这时，新的基变量为x3、x4、x2，新的非基变量为x1、x5，当前的基本可行解和目标函数值为：x=(0,25,15,15,0)T，z=62500。,67,第二次迭代：（1）当前的可行基为B7=(P2,P3,P4)，那么x2,x3,x4为基变量，x1,x5为非基变量。将基变量和目标函数用非基变量表示：z=62500+1500 x1(2500/3)x5 x2=25(1/3)x5 x3=15-3 x1+(2/3)x5 x4=15-2 x1+(1/3)x5,68,（2）选择进基变量。在目标函数z=62500+1500 x1(2500/3)x5 中，非基变量x1的系数是正数，因此x1进基可以使目标函数z增大，于是选择x1进基，使x1的值从0开始增加，另一个非基变量x5保持零值不变。,69,(3)确定出基变量。在约束条件 x2=25(1/3)x5 x3=15-3 x1+(2/3)x5 x4=15-2 x1+(1/3)x5 中，由于进基变量x1在两个约束条件中的系数都是负数，当x1的值从0开始增加时，基变量x3,x4的值分别从当前的值15,15开始减少，当x1增加到5时，x3首先下降为0成为非基变量。,70,这时，新的基变量为x1,x2,x4，新的非基变量为x3,x5，当前的基本可行解和目标函数值为：x=(5,25,0,5,0)T，z=70000。,71,第三次迭代：（1）当前的可行基为B2=(P1,P2,P4)，那么x1,x2,x4为基变量，x3,x5为非基变量。将基变量和目标函数用非基变量表示：z=70000 500 x3 500 x5 x1=5(1/3)x3+(2/9)x5 x2=25(1/3)x5 x4=5+(2/3)x3(1/9)x5,72,（2）选择进基变量。在目标函数z=70000 500 x3 500 x5 中，非基变量x3,x5的系数均不是正数，因此进基都不可能使目标函数z增大，于是得到最优解，x*=(5,25,0,5,0)T，最优目标值为 z*=70000。我们也称相应的基B2=(P1,P2,P4)为最优基。计算结束。,73,三次迭代：原点（D,E交点）,（D,C交点）,（A,C交点）,74,单纯形法的基本步骤描述如下：（1）找出初始基可行解寻找一个初始的可行基和相应基本可行解（顶点），确定基变量、非基变量（全部等于0）和目标函数的值，并将目标函数和基变量分别用非基变量表示；,75,考虑标准形式的线性规划问题：max z=c1x1+c2x2+cnxn s.t.a11 x1+a12 x2+a1n xn=b1 a21 x1+a22 x2+a2n xn=b2.am1 x1+am2 x2+amn xn=bm x1,x2,xn 0 x1 c1 b1 a11 a12.a1n x2 c2 b2 a21 a22.a2nx=.C=.b=.A=.xn cn bn am1 am2.amn,76,这里，矩阵A表示为：A=(P1,P2,Pn)，其中 Pj=(a1j,a2j,amj)T Rm。若找到一个可行基，无防设B=(P1,P2,Pm)，则m个基变量为 x1,x2,xm，n-m个非基变量为xm+1,xm+2,xn。通过运算，所有的基变量都可以用非基变量来表示：,77,x1=b1-(a1m+1xm+1+a1m+2xm+2+a1nxn)x2=b2-(a2m+1xm+1+a2m+2xm+2+a2nxn)xm=bm-(amm+1xm+1+amm+2xm+2+amnxn)把它们代入目标函数，得z=z+m+1xm+1+m+2xm+2+nxn(1-1)其中j=cj-(c1a1j+c2a2j+cm amj),78,（2）最优解的判别在用非基变量表示的目标函数表达式（1-1）中，我们称非基变量xj的系数为检验数记为 j。若某个检验数 s=maxj 0，那么相应的非基变量xs，它的值从当前值0开始增加时，目标函数值随之增加。这个选定的非基变量xs称为进基变量，转（3）。如果任何一个非基变量的值增加都不能使目标函数值增加，即所有 j 非正，则当前的基本可行解就是最优解，计算结束；,79,（3）基可行解的转换在用非基变量表示的基变量的表达式（1-1）中，观察进基变量增加时各基变量变化情况，确定基变量的值在进基变量增加过程中首先减少到0的变量xr，满足，=min bi/ais ais 0=br/ars（1-2）这个基变量xr称为出基变量。当进基变量的值增加到 时，出基变量xr的值降为0时，可行解就移动到了相邻的基本可行解（顶点），转（4）。(1-2)即所谓的最小检验比规则。,80,如果进基变量的值增加时，所有基变量的值都不减少，即所有ais 非正，则表示可行域是无界的，且目标函数值随进基变量的增加可以无限增加，此时，不存在有限最优解，计算结束；（4）将进基变量作为新的基变量，出基变量作为新的非基变量，确定新的基、新的基本可行解和新的目标函数值。在新的基变量、非基变量的基础上重复（2）。,81,表格单纯形法 设定：bi 0 i=1,2,m max z=c1 x1+c2 x2+cn xn s.t.a11 x1+a12 x2+a1n xn b1 a21 x1+a22 x2+a2n xn b2 am1 x1+am2 x2+amn xn bm x1,x2,xn 0,82,加入松弛变量：max z=c1 x1+c2 x2+cn xn s.t.a11 x1+a12 x2+a1n xn+xn+1=b1 a21 x1+a22 x2+a2n xn+xn+2=b2 am1 x1+am2 x2+amn xn+xn+m=bm x1,x2,xn,xn+1,xn+m 0,83,显然，xj=0,j=1,n;xn+i=bi,i=1,m 是基本可行解 对应的基是单位矩阵。以下是初始单纯形表：其中：z=i=1,m cn+i bi,j=cj-i=1,m cn+i aij 为检验数，cn+i=0,an+i,i=1,an+i,j=0(ji),i,j=1,m,84,xB(1)=b1-(a1,N(1)xN(1)+a1,N(2)xN(2)+a1,N(n)xN(n)xB(2)=b2-(a2,N(1)xN(1)+a2,N(2)xN(2)+a2,N(n)xN(n)xB(m)=bm-(am,N(1)xN(1)+am,N(2)xN(2)+am,N(n)xN(n)z=z+N(1)xN(1)+N(2)xN(2)+N(n)xN(n),对任一可行基B=(PB(1),PB(2),PB(m)，则m个基变量为 xB(1),xB(2),xB(m)，n-m个非基变量为xN(1),xN(2),xN(n-m)。所有的基变量都用非基变量来表示：,85,对应的单纯形表：其中：aB(i),B(i)=1,aB(i),B(j)=0(ji),i,j=1,m,86,max,min,高斯迭代运算：,87,例1.9 化标准形式：max z=1500 x1+2500 x2 s.t.3 x1+2 x2+x3=65 2 x1+x2+x4=40 3 x2+x5=75 x1,x2,x3,x4,x5 0,88,例1.9 化标准形式：max z=1500 x1+2500 x2 s.t.3 x1+2 x2+x3=65 2 x1+x2+x4=40 3 x2+x5=75 x1,x2,x3,x4,x5 0 最优解:x1*=5,x2*=25,x4*=5（松弛标量，表示B设备有5个机时的剩余）最优值：z*=70000,89,一般情况下初始基本可行解不明显。通常用以下两种方法求初始可行解:大M方法；两阶段法。,初始可行解的获取,90,max z=c1x1+c2x2+cnxn s.t.a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2.am1x1+am2x2+amnxn=bm x1,x2,xn 0,考虑标准问题：,91,大M法：引入人工变量 xn+i 0（i=1,m）及充分大正数 M（也称惩罚因子）：max z=c1x1+c2x2+cnxn-Mxn+1-Mxn+m s.t.a11 x1+a12 x2+a1n xn+xn+1=b1 a21 x1+a22 x2+a2n xn+xn+2=b2.am1 x1+am2 x2+amn xn+xn+m=bm x1,x2,xn,xn+1,xn+m 0,92,显然,xj=0,j=1,n;xn+i=bi,i=1,m是基本可行解，对应的基是单位矩阵。结论：若得到的最优解(x1,xn,xn+1,xn+m)满足 xn+i=0,i=1,m，则(x1,xn)是原问题的最优解；否则，原问题无可行解。,93,例1.10：（LP）max z=5x1+2x2+3x3-x4 s.t.x1+2x2+3x3=15 2x1+x2+5x3=20 x1+2x2+4x3+x4=26 x1,x2,x3,x4 0,94,max z=5x1+2x2+3x3-x4-Mx5-Mx6 s.t.x1+2x2+3x3+x5=15 2x1+x2+5x3+x6=20 x1+2x2+4x3+x4=26 x1,x2,x3,x4,x5,x6 0,大M 法：,95,max z=5x1+2x2+3x3-x4-Mx5-Mx6 s.t.x1+2x2+3x3+x5=15 2x1+x2+5x3+x6=20 x1+2x2+4x3+x4=26 x1,x2,x3,x4,x5,x6 0,96,97,98,最优解：(25/3,10/3,0,11)T 最优目标值：112/3,99,两阶段法：大M法不适合计算机求解，因此进一步产生两阶段法。第一阶段：引入人工变量 xn+i 0，i=1,m 构造一个新的目标函数:max z=-xn+1-xn+2-xn+m s.t.a11x1+a12x2+a1nxn+xn+1=b1 a21x1+a22x2+a2nxn+xn+2=b2.am1x1+am2x2+amnxn+xn+m=bm x1,x2.xn,xn+1,xn+m 0,100,第一阶段求解上述问题，将人工变量从基变量中换出，以求出原问题的初始基本可行解,结论：若得到的最优解满足 xn+i=0,i=1,m 则是原问题的基本可行解;否则，原问题无可行解。第二阶段以得到的初始基本可行解为基础对原目标函数求最优解。,101,第一阶段问题 max z=-x5-x6 s.t.x1+2x2+3x3+x5=15 2x1+x2+5x3+x6=20 x1+2x2+4x3+x4=26 x1,x2,x3,x4,x5,x6 0,两阶段法：,102,第一阶段,原问题的基本可行解：(0,15/7,25/7,52/7)T,103,第二阶段:划去人工变量，把基本可行解填入表中,原问题的最优解：(25/3,10/3,0,11)T；最优目标值：112/3,104,单纯形法解的几种情况讨论（1）有唯一最优解（2）有无穷多最优解（最优解不唯一）（3）有无界解(有可行解但无最优解)（4）无可行解（无解）（5）退化,105,（1）唯一最优解 最优表中所有非基变量的检验数非零大于零,则线性规划具有唯一最优解（2）无穷多解 当最优单纯形表中存在非基变量对应的检验数为零时，存在无穷多解。,106,求解线性规划,【解】:化为标准型后用单纯形法计算如下表所示,无穷多解的例子,107,108,表(3)中j全部非正,则最优解为:,表(3)表明,非基变量x3的检验数3=0,x3若增加,目标函数值不变,即当x3进基时Z仍 等于20。使x3进基 x5出基继续迭代,得到表(4)的另一 基本最优解,X(1),X(2)是线性规划的两个最优解，它的凸组合,仍是最优解，从而原线性规划有多重最优解。,109,（3）有无界解,某个检验数k0且对应的Pk（i=1，2,m）则线性规划具有无界解,110,求解线性规划,【解】化为标准型,111,初始单纯形表为,2=10,x2进基，而a120，a220，没有比值，从而线性规划的最优解无界。由模型可以看出，当固定x1使x2+且满足约束条件，还可以用图解法看出具有无界解。,112,(1)当用大M单纯形法计算得到最优解并且人工变量存在于基变量中，表明原线性规划无可行解。(2)两阶段法中，当第一阶段的最优值w0时，则原问题无可行解。,（4）无可行解,113,求解线性规划,【解】加入松驰变量x3、x4化为标准型,在第二个方程中加入人工变量x5，目标函数中加上M x5一项，得到,无可行解的例子,114,用单纯形法计算如下表所示。,表中 j0，j=1，2，5，从而得到最优解X=（2，0，0，0，2），Z=10+2M。但最优解中含有人工变量x50说明这个解是伪最优解，是不可行的，因此原问题无可行解。,115,（5）退化如果在一个基本可行解的基变量中至少有一个分量 xi=0(i=1,2,m)，则称此基本可行解是退化的基本可行解。最小比值原则决定换出变量的时候，如果出现两个或以上的相同比值，那么在下一步迭代后会出现一个或多个基变量等于零的退化解。退化情况下可能会出现循环,116,可能出现以下情况：进行进基、出基变换后，虽然改变了基，但没有改变基本可行解（顶点），目标函数当然也不会改进。进行若干次基变换后，才脱离退化基本可行解（顶点），进入其他基本可行解（顶点）。这种情况会增加迭代次数，使单纯形法收敛的速度减慢。在特殊情况下，退化会出现基的循环，一旦出现这样的情况，单纯形迭代将永远停留在同一顶点上，因而无法求得最优解。,117,在单纯形法求解线性规划问题时，一旦出现这种因退化而导致的基的循环，单纯形法就无法求得最优解。人们对如何防止出现循环作了大量研究。1952年Charnes提出了“摄动法”，1954年Dantzig、Orden和Wolfe又提出了“字典序法”，这些方法都比较复杂，同时也降低了迭代的速度。,118,1955年Beale提出了一个用单纯形法计算失效的模型,加入松弛变量后用单纯形法计算并且按字典序方法（按变量下标顺序）选进基变量，迭代6次后又回到初始表，继续迭代出现了无穷的循环，永远得不到最优解但该模型的最优解为 X(1，0，1，0)T，Z5/4,119,1976年，Bland提出了一个避免循环的新方法：在选择进基变量时，在所有 j 0的非基变量中选取下标最小的进基；当有多个变量同时可作为出基变量时，选择下标最小的那个变量出基。,120,求解线性规划,解 用大M单纯形法，加入人工变量x4、x5，构造数学模型,退化的例子,121,122,一般线性规划化为标准型,小结,123,续表,124,单纯形法计算步骤小结,125,练习：,126,练习：,A=3,b=2,c=4,d=-2,e=2,f=3,g=1,h=0,i=5,j=5,k=-1.5,l=0,127,线性规划可以应用在管理、经济、金融、战争、通讯、工程设计等各个领域。很多决策问题可以抽象为线性规划模型。线性规划方法的应用为社会带来了无法估量的巨大效益。合理利用线材问题混合配料问题产品计划问题连续投资人员安排问题,5.线性规划应用选讲,128,合理利用线材问题,现要做100 套钢架,每套用长为2.9m,2.Im 和1.5m的元钢各一根制成.已知原料长7.4米，问应如何下料，使用的原材料最省？,129,130,生产存储问题,电扇厂每月最多可生产3000台电扇，每台成本100元。如果当月销售不了，那么每台每月要支付10元的存储费。设4、5、6月的销售量预计为1000台、2500台和4000台。已知4月初没留有存货，也不要求6月底留下存货。问如何安排4、5、6月的生产计划，可使得总的生产、存储费最低？,131,假设4、5、6月份分别生产x1、x2、x3台,目标函数 min z=100（x1+x2+x3)+10(x1-1000)+10(2500-x1-x2)约束条件 s.t.x11000 x1-1000+x22500 x1+x2-1000-2500+x3=4000 x13000 x23000 x33000 x1,x2,x3 0,132,动态投资问题,133,动态投资问题,134,某商场决定：营业员每周连续工作5天后连续休息2天，轮流休息。根据统计，商场每天需要的营业员如表1.2所示。,表1.2 营业员需要量统计表,商场人力资源部应如何安排每天的上班人数，使商场总的营业员最少。,人力资源分配的问题,135,【解】设xj(j=1，2，7)为休息2天后星期一到星期日开始上班的营业员，则这个问题的线性规划模型为,136,混合配料问题,137,混合配料问题,138,混合配料问题,139,The End,140,选择题,线性规划问题的标准型最本质的特点是A目标要求是极小化 B变量可以取任意值C变量和右端常数要求非负 D约束条件一定是不等式形式线性规划可行域的顶点一定是可行解非基本解非可行最优解,141,X是线性规划的基本可行解，则有X中的基变量非负，非基变量为零X中的基变量非零，非基变量为零X不是基本解X不一定满足约束条件,142,判断题,是一个线性规划数学模型,143,判断题,可行解一定是基解基解可能是可行解线性规划的可行域无界则具有无界解可行解集有界非空时,则在顶点上至少有一点达到最优值 可行解集不一定是凸集,