第二章+线性规划课件

*第二章线性规划2.1 2.1 线性规划模型线性规划模型2.2 2.2 线性规划理论线性规划理论2.3 2.3 线性规划的单纯形法线性规划的单纯形法2.4 2.4 单纯形法的进一步讨论单纯形法的进一步讨论2.5 2.5 改进的单纯形法改进的单纯形法*2.1 2.1 线性规划模型线性规划模型 例例:某某工工厂厂拥拥有有A A、B B、C C 三三种种类类型型的的设设备备，生生产产甲甲、乙乙两两种种产产品品。每每件件产产品品在在生生产产中中需需要要占占用用的的设设备备机机时时数数，每每件件产产品品可可以以获获得得的的利润以及三种设备可利用的时数如下表所示：利润以及三种设备可利用的时数如下表所示：产品甲产品乙设备能力（h）设备A3 32 26565设备B2 21 14040设备C0 03 37575利润（元/件）1500150025002500*问题：工厂应如何安排生产可获得最大的总利润？解：设变量xi为第i种（甲、乙）产品的生产件数（i1，2）。根据题意，我们知道两种产品的生产受到设备能力（机时数）的限制。对设备A，两种产品生产所占用的机时数不能超过65，于是我们可以得到不等式：3 x1+2 x2 65；对设备B，两种产品生产所占用的机时数不能超过40，于是我们可以得到不等式：2 x1+x2 40；2.1 2.1 线性规划模型线性规划模型*对对设设备备C C，两两种种产产品品生生产产所所占占用用的的机机时时数数不不能能超超过过7575，于于是是我我们们可可以以得得到到不不等等式式：3 3x x2 2 75 75；另另外外，产产品品数数不不可可能能为为负负，即即 x x1 1,x,x2 2 00。同同时时，我我们们有有一一个个追追求求目目标标，即即获获取取最最大大利利润润。于于是是可可写写出出目目标标函函数数z z为为相相应应的的生生 产产 计计 划划 可可 以以 获获 得得 的的 总总 利利 润润：z z=1500=1500 x x1 1+2500+2500 x x2 2 。综综合合上上述述讨讨论论，在在加加工工时时间间以以及及利利润润与与产产品品产产量量成成线线性性关关系系的的假假设设下下，把把目目标标函函数数和和约约束束条条件件放放在在一一起起，可可以以建建立立如下的线性规划模型：如下的线性规划模型：2.1 2.1 线性规划模型线性规划模型*目标函数 Max z=1500 x1+2500 x2约束条件 s.t.3x1+2x2 65 2x1+x2 40 3x2 75 x1,x2 0 2.1 2.1 线性规划模型线性规划模型*这是一个典型的利润最大化的生产计划问题。其中，“Max”是英文单词“Maximize”的缩写，含义为“最大化”；“s.t.”是“subject to”的缩写，表示“满足于”。因此，上述模型的含义是：在给定条件限制下，求使目标函数z达到最大的x1,x2 的取值。它是一个目标函数、约束函数都是线性函数的最优化问题，即线性规划问题。2.1 2.1 线性规划模型线性规划模型*一般形式 目标函数：Min(Max)z=c1x1+c2x2+cnxn 约束条件：a11x1+a12x2+a1nxn(=,)b1a21x1+a22x2+a2nxn(=,)b2 .am1x1+am2x2+amnxn(=,)bm x1，x2，xn 02.1 2.1 线性规划模型线性规划模型*标准形式目标函数：Min z=c1x1+c2x2+cnxn 约束条件：a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2 .am1x1+am2x2+amnxn=bm x1，x2，xn 02.1 2.1 线性规划模型线性规划模型*可以看出，线性规划的标准形式有如下四个特点：目标最小化、约束为等式、决策变量均非负、右端项非负。对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:2.1 2.1 线性规划模型线性规划模型*1.极大化目标函数的问题：设目标函数为 Max f=c1x1+c2x2+cnxn 则可以令z -f，该极大化问 题与下面的极小化问题有相同的最优 解，即 Max z=-c1x1-c2x2-cnxn 但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即 Min z -Max f2.1 2.1 线性规划模型线性规划模型*2、约束条件不是等式的问题：设约束条件为 ai1 x1+ai2 x2+ain xn bi 可以引进一个新的变量s，使它等于约束右边与左边之差 s=bi(ai1 x1+ai2 x2+ain xn)显然，s 也具有非负约束，即s0，这时新的约束条件成为 ai1 x1+ai2 x2+ain xn+s=bi2.1 2.1 线性规划模型线性规划模型*当约束条件为 ai1 x1+ai2 x2+ain xn bi 时，类似地令 s=(ai1 x1+ai2 x2+ain xn)-bi 显然，s 也具有非负约束，即s0，这时新的约束条件成为 ai1 x1+ai2 x2+ain xn-s=bi 2.1 2.1 线性规划模型线性规划模型*为了使约束由不等式成为等式而引进的变量s称为“松弛变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。2.1 2.1 线性规划模型线性规划模型*例2.2：将以下线性规划问题转化为标准形式 Max f =3.6 x1-5.2 x2+1.8 x3 s.t.2.3 x1 +5.2 x2-6.1 x3 15.7 4.1 x1 +3.3 x3 8.9 x1+x2+x3 =38 x1,x2,x3 0 2.1 2.1 线性规划模型线性规划模型解：首先,将目标函数转换成极小化：令 z=-f=-3.6x1+5.2x2-1.8x3*其次考虑约束，有2个不等式约束，引进松弛变量x4，x5 0。于是，我们可以得到以下标准形式的线性规划问题：Min z=-3.6 x1+5.2 x2-1.8 x3s.t.2.3x1+5.2x2-6.1x3+x4=15.7 4.1x1+3.3x3-x5=8.9 x1+x2+x3=38 x1,x2,x3,x4,x5 02.1 2.1 线性规划模型线性规划模型*3.变量无符号限制的问题：在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令 xj=xj-xj”其中 xj0，xj”0即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj和xj”的大小。2.1 2.1 线性规划模型线性规划模型*4.右端项有负值的问题：在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如 bi0,且且B-1pj0,则则(LP)无有无有限最优解限最优解.二、最优解的判断二、最优解的判断*三、单纯形法的计算步骤三、单纯形法的计算步骤初始基本可行解初始基本可行解是否最优解或是否最优解或无限最优解无限最优解?结束结束沿边界找新沿边界找新的基本可行解的基本可行解NY*（1）确定一个初始基本可行解）确定一个初始基本可行解:A=B,N，xT=xBT,xNT,cT=cBT,cNT,f=cBT xB.这里这里xB=B-1b0,xN=0.（2）计算非基变量检验数）计算非基变量检验数=cNT-cBTB-1N,根据最优解判别定根据最优解判别定理，判断理，判断 x是否为最优解是否为最优解.若是，则停止，否则转下一步若是，则停止，否则转下一步.（3）求一改进的基本可行解）求一改进的基本可行解1)确定换入变量确定换入变量:k=max j|jNI,相应的相应的xk为换入变量为换入变量.2)确定换出变量确定换出变量:按按规则计算算=mini/aik|aik0=r/ark以以xr为换出出变量量.这里里=B-1b,ak=B-1pk3)用用pk代替代替pBr,得到新的基矩阵得到新的基矩阵B,并将并将B变换为单位矩阵变换为单位矩阵:以以ark为主元素进行迭代为主元素进行迭代(即用高斯消去法即用高斯消去法)把把pk=(a1k ark amk)T变为变为(01 0)T.（4）重复（）重复（2）、（）、（3）直到得到最优解）直到得到最优解.三、单纯形法的计算步骤（续）三、单纯形法的计算步骤（续）*四、单纯形表：四、单纯形表：设设x为初始基本可行解为初始基本可行解,相应分解相应分解A=B,Nminfs.t.f-cBTxB-cNTxN=0BxB+NxN=bxB,xN 0minfs.t.f-0 xB+(cBTB-1N-cNT)xN=cBTB-1b xB+B-1NxN=B-1bxB,xN 0检验数检验数*检验数检验数fxBTxNTRHS目标行目标行10TcBTB-1N-cNTcBTB-1 b1行行xB0IB-1NB-1bM行行1列列m列列n-m列列1列列作变换，使前作变换，使前m+1列对应的列对应的m+1阶矩阵变为单位矩阵阶矩阵变为单位矩阵,得：得：fxBTxNTRHS目标行目标行1-cBT-cNT01行行约束行约束行0BNbM行行1列列m列列n-m列列1列列*fx1x2x3x4x5RHSf1250000 x30121008x40100104x50010013引例的单纯型表：引例的单纯型表：换入变量：换入变量：x2，因，因为为max2,5=5换出变量：换出变量：x5,因因为为min8/2,3/1=3*fx1x2x3x4x5RHSf12000-5-15x301010-22x40100104x20010013fx1x2x3x4x5RHSf100-20-1-19x101010-22x4000-1122x20010013最优解最优解x*=(2,3,0,2,0)T,f*=-19*2.4 2.4 单纯形法的进一步讨论单纯形法的进一步讨论初始基本可行解的确定退化情形的处理*初始基本可行解的确定当初始基本可行解不能通过观察法很容易得到时，如何确定初始基本可行解？*初始基本可行解的确定带来的问题：人工变量的引入，改变了原问题的约束条件，得到的是与原问题不同的新问题，而新问题的最优解不一定是原问题的最优解（除非新问题的最优解正好人工变量都为零）.（人工变量是“非法”的变量，松弛变量是“合法”的变量）解决方法：大M法两阶段法*大M法若(x,0)T是DMLP的有限最优解，则x是LP的最优解若(x,xa)T(xa0)是DMLP的有限最优解，则LP无可行解若DMLP无有限最优解，则LP或者无有限最优解或者无可行解*二阶段法若(x,xa)T(xa0)是FPLP的有限最优解，则SPLP无可行解若(x,xa)T(xa=0)是FPLP的有限最优解，且xa 的分量都是非基变量，则x是SPLP的一个基本可行解若(x,xa)T(xa=0)是FPLP的有限最优解，且xa 的某些分量是基变量，则可通过主元素消去法，用原变量的非基变量，替换出基变量中的人工变量，得到SPLP的一个基本可行解*退化情形的处理循环现象：当线性规划问题存在最优解时，在非退化情形(基变量都大于0)下，单纯形法经有限次迭代必可达到最优解；在退化情形(存在基变量等于0)下，有可能经过有限次迭代求不出最优解，出现循环现象。*例子*第第一一次次迭迭代代x1x2x3x4x5x6x7RHSf0003/4-201/2-60 x11001/4-8-190 x20101/2-12-1/2 30 x300100101x1x2x3x4x5x6x7RHSf0003/4-201/2-60 x11001/4-8-190 x20101/2-12-1/2 30 x300100101第第六六次次迭迭代代*解决方法：摄动法解决方法：摄动法，具体请看陈宝林的“最优化理论与算法（第2版）”退化情形不用摄动法也不一定出现循环，事实上，退化情形是常见的，但在迭代中发生循环现象的概率很小，因此关于退化和循环的研究，主要是理论上的意义，实际计算中并不那么重要*改进的单纯形法*改进的单纯形法（续）启示：启示：优点：主要是节省了存储空间优点：主要是节省了存储空间