二章二节单纯形法.ppt

第二节单纯形法,单纯形法是求解线性规划的主要算法，1947年由美国斯坦福大学教授丹捷格（G.B.Danzig）提出。尽管在其后的几十年中，又有一些算法问世，但单纯形法以其简单实用的特色始终保持着绝对的“市场”占有率。,1.线性规划的标准型用单纯形法求解线性规划的前提是先将模型化为标准型：,标准型的特征：Max型、等式约束、非负约束,一、单纯形法的预备知识,标准型的矩阵表示：,称为决策变量向量，称为价格系数向量,称为技术系数矩阵,称为资源限制向量。,其中,非标准形式如何化为标准型？,1)Min型化为Max型,加负号,因为，求一个函数的极小点，等价于求该函数的负函数的极大点。,注意：Min型化为Max型求解后，最优解不变，但最优值差负号。,如原问题,可化为,2)对约束，可添加松弛变量构成等式约束,分析：以例1中煤的约束为例,之所以“不等”是因为左右两边有一个差额，称为“松弛量”，若在左边加上这个松弛量，则化为等式。而这个松弛量也是变量，记为X3，则有,问题：它的实际意义是什么？X3称为松弛变量，它的价格系数c3=0。,煤资源的“剩余”。,3)对约束，可添加剩余变量构成等式约束,例如，对约束,减去剩余变量x40，构成等式约束,同样，剩余变量的价格系数c4=0。,4)当模型中有某变量xk没有非负要求，称为自由变量,则可令,5）若某一常数项bi0这时只要在bi相对应的约束方程两边乘上-1。,6)若x0,则令x=-x,练习1：请将例1的约束化为标准型,易见，增加的松弛变量的系数恰构成一个单位阵I。,一般地，记松弛变量的向量为Xs，则,问题：松弛变量在目标中的系数为何？,0。,练习2：将下面非标准线性规划化为等价的标准型,将目标函数转化为求极大型，即得,对第一个约束添加松弛变量x40，得,对第二个约束减去剩余变量x50，得,对自由变量x3，令,minz=-x1+3x2-7x3,maxz=x1-3x2+7x3,x1-2x2+3x3+x4=7,2x1-x2+x3x5=4,x3=x3-x3，x30，x30,原规划化为标准型：,maxz=x1-3x2+7x3-7x3,练习2：将下面非标准线性规划化为等价的标准型,minz=-x1+3x2-7x3,练习3：,minZ=x1+2x2-3x3x1+x2+x39-x1-2x2+x323x1+x2-3x3=5x10，x20，x3无约束,令x1=-x1，x3=x3-x3Z=-Z。,maxZ=x1-2x23(x3-x3)-x1+x2+x3-x3x4=9x1-2x2+x3-x3-x5=2-3x1+x2-3(x3-x3)=5x1x2x3x3x4x50,标准型为:,2.基本概念,（1）可行解与最优解,直观上，可行解是可行域中的点，是一个可行的方案；最优解是可行域的角点，是一个最优的方案。,假设nm，且系数矩阵,的秩为m，用Pj表示A中第j列的列向量，即,由此，矩阵A可表示为A=P1P2Pn,（2）基矩阵与基变量,基向量：基B中的列；其余称非基向量。,基变量：与基向量Pj对应的决策变量xj，记其组成的向量为XB；非基变量：与非基向量对应的变量称非基变量，记其组成的向量为XN。,基矩阵(基)：设A是mn阶约束系数矩阵（mn）,秩为m。A=（P1,P2,Pn）,则A中m阶可逆子阵B=（P1,P2,Pm）为线性规划的一个基。其余部分称为非基矩阵，记为N,6个。,一般地，mn阶矩阵A中基的个数最多有多少个？,问题：本例的A中一共有几个基？,p16,（3）基本解与基本可行解,当A中的基B取定后，不妨设B表示中的前m列，则可记A=（BN）,相应地X=(XBXN)T,约束中的AX=b可表示为,即,当取XN=0时，有,可见：一个基本解是由一个基决定的。注意：基本解仅是资源约束的解，并未要求其非负，因此其未必可行。,称非负的基本解为基本可行解（简称基可行解），对应于基可行解的基称为可行基。,例4：在上例中,求相应于基B1和B2的基本解，它们是否基本可行解？,上二组概念间的联系：,几种解之间的关系：,问题：基本可行解是可行域中的哪些点？,3.基本定理,（1）线性规划的可行域是一个凸多面体。,（2）线性规划的最优解（若存在的话）必能在可行域的角点获得。,（3）线性规划可行域的角点与基本可行解一一对应。,因此，在角点中寻找最优点即可转化为在所有基本可行解中寻找最优解。因此，只需考虑所有基本可行解就够了,二、单纯形法的步骤,单纯形法是一种迭代的算法，它的思想是在可行域的角点基本可行解中寻优。由于角点是有限个（为什么？），因此，算法经有限步可终止。,1.确定初始基可行解,由于基可行解是由一个可行基决定的，因此，确定初始基可行解X0相当于确定一个初始可行基B0。,问题：若B0=I，则X0=？,方法：若A中含I，则B0=I，由此可得初始基本可行解若A中不含I，则可用人工变量法构造一个I。,2.最优性检验,问题：用什么检验？,把目标函数用非基变量表示。,因此，对给定的一个可行基B(即给定一个基本可行解XB=B-1b,XN=0)，判别它是否最优，,（2）若所有j0时，这个基本可行解为优；反之，若有某一检验数k0，则此解一定不是最优,转3。,2.最优性检验（续）,（1）只需计算每一非基变量xj的检验数,z,3.寻找更好的基可行解,由于基可行解与基对应，即寻找一个新的基可行解，相当于从上一个基B0变换为下一个新的基B1，因此，本步骤也称为基变换。,（基变换）,以例1为例，可按上述单纯形法的步骤求出其最优解，其大致的过程如下。,（1）先将模型化为标准型,(2)确定初始基可行解、检验,以例1为例，可按上述单纯形法的步骤求出其最优解，其大致的过程如下。,（1）先将模型化为标准型,(2)确定初始基可行解、检验,（3）换基、计算下一个基可行解、再检验，直至最优,问题：当模型规模较大时，计算量很大。,事实上，单纯形法的实现是在单纯形表上完成的。,练习：对于下面的线性规划,（1）用图解法求解；（2）将模型化为标准型；（3）用单纯形法步骤求出其最优解，并指出求解过程中每一个基可行解相当于可行域的哪一个角点。,三、单纯形表,单纯形表是基于单纯形法的步骤设计的计算格式，是单纯形法的具体实现。,回顾单纯形法步骤,单纯形表的主要结构：,问题：第一张表的B-1=？,单位阵I。,检验数的公式是什么？,按上式计算基变量检验数为0,B-1Pj在哪里？,-B-1A中的j列,例5：用单纯形法求解例1,问题：标准模型的A中是否含I？,松弛变量系数恰好构成I。,例5：用单纯形法求解例1,初始单纯型表：,化为标准型,松弛变量系数恰好构成I。,下一张表将通过实行初等行变换（称高斯消去）得到。方法是：先将主元消成1，再用此1将其所在列的其余元消成0。,主元,以10为i主元进行初等行变换,（请解释其实际意义）,以为主元进行初等行变换,000-1.36-0.52,2.5,练习：用单纯形法求解下面的线性规划,单纯形表：,【】,【】,【】,【】,Min型单纯形表：,Min型单纯形表与Max型的区别仅在于：检验数反号，即-当检验数均大于等于零时为最优；-令负检验数中最小的对应的变量进基。,四、大M法,1问题,设问题：,A中不含I,例如，用单纯形法求解线性规划,例如，用单纯形法求解线性规划,解：首先增加松弛变量与剩余变量x4、x5，将模型约束化为标准型,2方法,在第二、第三个约束方程左边分别添加人工变量x60、x70。在求极大型M问题中，人工变量在目标函数中系数均为-M；在求极小型min问题中，系数均为M，其中M是很大很大的正数。,1-221000,-2110-110,-1010011,-4+3M3-M2-2M0-M00,1-221000,-2110-110,-1010011,-4+3M3-M2-2M0-M00,43-20100-2,2-1100-11-1,2-1010001,-2+M3-M00M02M-2,2,81001-22-4,2-1100-11-1,2-1010001,10003M-3M+1,最优解的基变量中含有人工变量，可以证明此情况下，原问题无可行解；最优解的基变量中不含人工变量，即人工变量均为零，可以证明在此情况下，从最优解中去掉人工变量即为原问题的最优解,使用大M法会出现下列两种情况：,p26,解的几种情况在单纯形表上的体现（Max型）：,唯一最优解：终表非基变量检验数均小于零；多重最优解：终表非基变量检验数中有等于零的；(书例2.12),练习：用单纯形法求解下面的线性规划,问题：本题的单纯形终表检验数有何特点？,