1、第二节第二节 单纯形法单纯形法 单纯形法是求解线性规划的主要算法，单纯形法是求解线性规划的主要算法，19471947年由美国斯坦福大学教授丹捷格（年由美国斯坦福大学教授丹捷格（G.B.DanzigG.B.Danzig）提出。提出。尽管在其后的几十年中，又有一些算法问世，尽管在其后的几十年中，又有一些算法问世，但单纯形法以其简单实用的特色始终保持着绝对但单纯形法以其简单实用的特色始终保持着绝对的的“市场市场”占有率。占有率。1.1.线性规划的标准型线性规划的标准型 用单纯形法求解线性规划的前提是先将模用单纯形法求解线性规划的前提是先将模型化为标准型：型化为标准型：标准型的特征：标准型的特征：Ma
2、xMax型、等式约束、非负约束型、等式约束、非负约束一、单纯形法的预备知识一、单纯形法的预备知识nnxcxcxcMaxz2211njxbxaxaxabxaxaxabxaxaxatsjmnmnmmnnnn,2,1,0.22112222212111212111标准型的矩阵表示：标准型的矩阵表示：0.XbAXtsCXMaxz。）（的秩为的秩为0,bnmmAnmTmnTnbbbccCxxX),(),(,),(111 称为称为决策变量向量决策变量向量，称为称为价格系数向量价格系数向量,称为称为技技术系数矩阵术系数矩阵,称为称为资源限制向量资源限制向量。XCAb其中其中 mnmmnnaaaaaaaaaA2
3、12222111211非标准形式如何化为标准型？非标准形式如何化为标准型？1)1)MinMin型化为型化为MaxMax型型 CXMinzCXMaxz/加负号加负号 因为，求一个函数因为，求一个函数的极小点，等价于求该的极小点，等价于求该函数的负函数的极大点。函数的负函数的极大点。)(xf)(xf*x注意：注意：MinMin型化为型化为MaxMax型求解后，最优解不变，但最优值差负号。型求解后，最优解不变，但最优值差负号。2142minxxz2142maxxxz如原问题如原问题可化为可化为2)对对约束，可添加约束，可添加松弛变量松弛变量构成等式约束构成等式约束分析：分析：以例以例1中煤的约束为例
4、中煤的约束为例3604921 xx之所以之所以“不等不等”是因为左右两边有一个差额，称为是因为左右两边有一个差额，称为“松松弛量弛量”，若在左边加上这个松弛量，则化为等式。而这，若在左边加上这个松弛量，则化为等式。而这个松弛量也是变量，记为个松弛量也是变量，记为X X3 3 ，则有，则有36049321 xxx问题：问题：它的实际意义是什么？它的实际意义是什么？X X3 3称为松弛变量，它的价格系数称为松弛变量，它的价格系数c c3 3=0=0。煤资源的煤资源的“剩余剩余”。3)对对约束，可添加约束，可添加剩余变量剩余变量构成等式约束构成等式约束例如，对约束例如，对约束22521 xx2254
5、21xxx减去剩余变量减去剩余变量x40，构成等式约束，构成等式约束同样，剩余变量的价格系数同样，剩余变量的价格系数c c4 4=0=0。4)4)当模型中有某变量当模型中有某变量 xk 没有非负要求，称为没有非负要求，称为 自由自由 变量变量,则可令则可令 0,/kkkkkxxxxx5 5）若某一常数项若某一常数项 b i0这时只要在这时只要在b i相对应的约相对应的约 束方程两边乘上束方程两边乘上-1。6)6)若若x0,则令则令x=-x练习练习1：请将例：请将例1的约束化为标准型的约束化为标准型0,3001032005436049.21212121解：增加松弛变量解：增加松弛变量则约束化为则
6、约束化为,543xxx0,300 10320054360 49.54321521421321易见，增加的松弛变量的系数恰构成一个单位阵易见，增加的松弛变量的系数恰构成一个单位阵I I。一般地，记松弛变量的向量为一般地，记松弛变量的向量为 Xs，则，则0.XbAXts0,.ssXXbIXAXts0.XbAXts0,.ssXXbIXAXts问题：松弛变量在目标中的系数为何？问题：松弛变量在目标中的系数为何？0 0。练习练习2：将下面非标准线性规划化为等价的标准型：将下面非标准线性规划化为等价的标准型将目标函数转化为求极大型，即将目标函数转化为求极大型，即得得对第一个约束添加松弛变量对第一个约束添加
7、松弛变量x40，得，得对第二个约束减去剩余变量对第二个约束减去剩余变量x50，得，得对自由变量对自由变量 x3，令，令min z=-x1+3x2-7x3max z=x1-3x2+7x3x1-2x2+3x3+x4=72x1-x2+x3 x5=4x3=x3-x3，x30，x30 为自由变量为自由变量321321321321,0,64542732xxxxxxxxxxxx原规划化为标准型：原规划化为标准型：max z=x1-3x2+7x3-7x3 0,644542733254332133215332143321xxxxxxxxxxxxxxxxxxxx练习练习2：将下面非标准线性规划化为等价的标准型：将
8、下面非标准线性规划化为等价的标准型min z=-x1+3x2-7x3 为自由变量为自由变量321321321321,0,64542732xxxxxxxxxxxx练习练习3：minZ=x1+2x2-3x3 x1+x2+x3 9 -x1-2x2+x3 2 3x1+x2-3x3=5 x10，x20，x3无约束无约束令令x1=-x1，x3=x3-x3 Z=-Z。maxZ=x1-2x23(x3-x3)-x1+x2+x3-x3x4 =9 x1-2x2+x3-x3 -x5=2-3 x1+x2-3(x3-x3)=5 x1 x2 x3 x3 x4 x5 0标准型为标准型为:2.基本概念基本概念（1）可行解与最优
9、解）可行解与最优解；的解，记为可行解：满足全体约束X。，有解则对任可行的，记为最优解：可行解中最优*,CXCXXX 直观上，可行解是可行域中的点，是一个直观上，可行解是可行域中的点，是一个可行的方案；可行的方案；最优解是可行域的角点，是一个最优的方最优解是可行域的角点，是一个最优的方案。案。mnmmnnaaaaaaaaaA212222111211假设假设nm，且系数矩阵，且系数矩阵的秩为的秩为m，用，用Pj表示表示A中第中第j列的列向量，即列的列向量，即由此，矩阵由此，矩阵A可表示为可表示为A=P1 P2 Pn mjjjjaaaP21（2）基矩阵与基变量）基矩阵与基变量基向量基向量：基：基B中
10、的列；其余称非基向量。中的列；其余称非基向量。基变量基变量：与基向量：与基向量Pj对应的决策变量对应的决策变量xj，记其组成的，记其组成的 向量为向量为XB；非基变量非基变量：与非基向量对应的变量称非基变量，记其：与非基向量对应的变量称非基变量，记其 组成的向量为组成的向量为XN。基矩阵基矩阵(基基)：设设A A是是m mn n阶约束系数矩阵（阶约束系数矩阵（mnmn）,秩秩为为m m。A=A=（P P1 1,P,P2 2,P,Pn n ）,则则A A中中m m阶可逆子阵阶可逆子阵 B B=（P P1 1,P,P2 2,P,Pm m ）为线性规划的一个）为线性规划的一个基基。其余部其余部分称为
11、分称为非基矩阵非基矩阵，记为，记为N N 1231241432123,0 xxxxxxxx例：下面为某线性规划的约束请例举出其基矩阵和相应的基向量、基变量。阶可逆子阵有中的，解：本例中，210011221AA 6 6个。个。一般地，一般地，m mn n 阶矩阵阶矩阵A A中基的个数最多有多少个？中基的个数最多有多少个？个。mnC;,100143434311xxXxxPPBB，基变量为，其相应的基向量为。基变量为其相应的基向量为21212122,1221xxXxxPPBB问题：本例的问题：本例的A A中一共有几个基？中一共有几个基？p16（3）基本解与基本可行解）基本解与基本可行解当当A中的基中
12、的基B取定后，不妨设取定后，不妨设B表示中的前表示中的前m列，则可记列，则可记A=（B N）,相应地相应地 X=(XB XN)T.0,11 bBXbBXBNBNXBbBX11 ,bXXNBNB 约束中的约束中的 AX=b 可表示为可表示为即即bNXBXNB 解解为线性规划的一个基本为线性规划的一个基本的解的解称称 01bBXbAX当取当取XN=0时，有时，有可见：一个基本解是由一个基决定的。可见：一个基本解是由一个基决定的。注意：基本解仅是资源约束的解，并未要求其非负，因此其未必可行。注意：基本解仅是资源约束的解，并未要求其非负，因此其未必可行。称非负的基本解为称非负的基本解为基本可行解基本可
13、行解（简称基可行解），（简称基可行解），对应于基可行解的基称为对应于基可行解的基称为可行基可行基。例例4：在上例中：在上例中0,321241421321xxxxxxxx 求相应于基求相应于基B1和和B2的基本解，它们是否基本可行解？的基本解，它们是否基本可行解？,31311001,1001,1001111 bBBB11解：解：是是基基本本可可行行解解。的的基基本本解解为为相相应应于于基基,)3,1,0,0(1TXB,51-573151-525251,51-525251,1-221112 bBBB22不是基本可行解。不是基本可行解。的基本解为的基本解为相应于基相应于基,0,0)51,-57(2T
14、XB 上二组概念间的联系：上二组概念间的联系：系数阵系数阵A中可找出若干个基中可找出若干个基B每个基每个基B都对应于一个基本解都对应于一个基本解非负的基本解就是基本可行解非负的基本解就是基本可行解几种解之间的关系：几种解之间的关系：可行解可行解基本解基本解非可行解非可行解基本可行解基本可行解问题：基本可行解是可行域中的哪些点？问题：基本可行解是可行域中的哪些点？3.基本定理基本定理（1 1）线性规划的可行域是一个）线性规划的可行域是一个凸凸多面体。多面体。（2 2）线性规划的最优解（若存在的话）必能在可行）线性规划的最优解（若存在的话）必能在可行 域的域的角点角点获得。获得。（3 3）线性规划
15、可行域的）线性规划可行域的角点角点与与基本可行解基本可行解一一对应。一一对应。因此，在角点中寻找最优点即可转化为在所有基因此，在角点中寻找最优点即可转化为在所有基本可行解中寻找最优解。因此，只需考虑所有基本可本可行解中寻找最优解。因此，只需考虑所有基本可行解就够了行解就够了二、单纯形法的步骤二、单纯形法的步骤 单纯形法是一单纯形法是一种迭代的算法，它种迭代的算法，它的思想是在可行域的思想是在可行域的角点的角点基本可基本可行解中寻优。由于行解中寻优。由于角点是有限个角点是有限个（为（为什么？什么？），因此，），因此，算法经有限步可终算法经有限步可终止。止。1.确定初始基可行解确定初始基可行解 由
16、于基可行解是由一个可行基决定的，因此，由于基可行解是由一个可行基决定的，因此，确定初始基可行解确定初始基可行解X X0 0相当于确定一个初始可行基相当于确定一个初始可行基B B0 0。问题：若问题：若B0=I，则，则X0=？可行。可行。,000100 bbBXXXNB方法：方法：若若A中含中含I，则，则B0=I，由此可得初始基本可行解由此可得初始基本可行解 若若A中不含中不含I，则可用人工变量法构造一个，则可用人工变量法构造一个I。2.最优性检验最优性检验问题：用什么检验？问题：用什么检验？把目标函数用把目标函数用非基变量非基变量表示。表示。优。优。时，当前基可行解为最时，当前基可行解为最，则
17、当，则当记记 01 NBCCBN 因此，对给定的一个可行基因此，对给定的一个可行基B(即给定一个基即给定一个基本可行解本可行解XB=B-1b,XN=0)，判别它是否最优，判别它是否最优，（2）若所有）若所有j j0时，这个基本可行解为优；反时，这个基本可行解为优；反之，若有某一检验数之，若有某一检验数 k 0，则此解一定不是最，则此解一定不是最优优,转转3。2.最优性检验（续）最优性检验（续）jBjjPBCc1 （1）只需计算每一非基变量）只需计算每一非基变量 x j 的检验数的检验数NBCCBN1 z3.寻找更好的基可行解寻找更好的基可行解 由于基可行解与基对应，即寻找一个新的基可行由于基可
18、行解与基对应，即寻找一个新的基可行解，相当于从上一个基解，相当于从上一个基B0变换为下一个新的基变换为下一个新的基B1，因，因此，本步骤也称为基变换。此，本步骤也称为基变换。（基变换）（基变换）0NNMNbBzz可行：改善：基变换的原则称作检验比。i）变换的方法：（nklPPPP,N进基进基出基出基 以例以例1 1为例，可按上述单纯形法的步骤求出其最为例，可按上述单纯形法的步骤求出其最优解，其大致的过程如下。优解，其大致的过程如下。（1 1）先将模型化为标准型）先将模型化为标准型0,3001032005436049.54321521421321xxxxxxxxxxxxxxts 21127xxM
19、axz(2)(2)确定初始基可行解、检验确定初始基可行解、检验;00,300)(0,0,360,2,00)(360,200,3,0100TTXbBB111;,52PP向量为再计算检验比确定出基量为计算检验数确定进基向 以例以例1 1为例，可按上述单纯形法的步骤求出其最为例，可按上述单纯形法的步骤求出其最优解，其大致的过程如下。优解，其大致的过程如下。（1 1）先将模型化为标准型）先将模型化为标准型0,3001032005436049.54321521421321xxxxxxxxxxxxxxts 21127xxMaxz(2)(2)确定初始基可行解、检验确定初始基可行解、检验;00,300)(0,
20、0,360,2,00)(360,200,3,0100TTXbBB111;,52PP向量为再计算检验比确定出基量为计算检验数确定进基向7349111)0,0,0(71111 pBCcB 122 （3 3）换基、计算下一个基可行解、再检验，直至最）换基、计算下一个基可行解、再检验，直至最优优;50,0)(0,24,240,)(240,50,30,1051411111TTXbBB;0,0)(20,24,84,(84,20,24),103544912122TTXbBB00;,41PP向量为再计算检验比确定出基量为计算检验数确定进基向前解为最优。计算检验数均非正，当问题：当模型规模较大时，计算量很大。问
21、题：当模型规模较大时，计算量很大。事实上，单纯形法的实现是在单纯形表上完成的。事实上，单纯形法的实现是在单纯形表上完成的。练习：对于下面的线性规划练习：对于下面的线性规划0,6222min2N2N2N2Nxxxxxxxxz（1）用图解法求解；）用图解法求解；（2）将模型化为标准型；）将模型化为标准型；（3）用单纯形法步骤求出其最优解，并指出求）用单纯形法步骤求出其最优解，并指出求 解过程中每一个基可行解相当于可行域的解过程中每一个基可行解相当于可行域的 哪一个角点。哪一个角点。三、单纯形表三、单纯形表 单纯形表是基于单纯形法的步骤设计的计算格单纯形表是基于单纯形法的步骤设计的计算格式，是单纯形
22、法的具体实现。式，是单纯形法的具体实现。110101100)()(000BPBbBPBCcbBXBikiiljBjj min0 回顾单纯形法步骤回顾单纯形法步骤bBN需计算ABN需计算单纯形表的主要结构：单纯形表的主要结构：X CABNbBN问题：第一张表的问题：第一张表的B-1=？单位阵单位阵I。检验数的公式是什么？检验数的公式是什么？jBjjPBCcNAIAABbIbbB 11,按上式计算基变量检验数为按上式计算基变量检验数为0B-1Pj 在哪里？在哪里？-B-1A 中的中的 j 列列例例5：用单纯形法求解例：用单纯形法求解例10,3001032005436049.21212121xxxx
23、xxxxts21127xxMaxz将模型化为标准型：解：增加松弛变量,543xxx 0,3001032005436049.54321521421321xxxxxxxxxxxxxxts 21127xxMaxz问题：标准模型的问题：标准模型的A中是否含中是否含I？松弛变量系数恰好构成松弛变量系数恰好构成I。例例5：用单纯形法求解例：用单纯形法求解例10300103200543604921212121xxxxxxxxts,.21127xxMaxz 0,3001032005436049.54321521421321xxxxxxxxxxxxxxts 21127xxMaxz54321 xxxxxbBNBX
24、BC 0 0 0 12 71001030105400149300200360543xxx000初始单纯型表：初始单纯型表：化为标准型化为标准型松弛变量系数恰好构成松弛变量系数恰好构成I。54321 xxxxxbB1 BXBC0 0 0 12 71001030105400149300200360543xxx000 0 0 0 12 77;3490)0 (071111 pBCcB 其中检验数其中检验数;110540)0 (01212222 pBCcB 304090下一张表将通过实行初等行变换（称高斯消去）得到。下一张表将通过实行初等行变换（称高斯消去）得到。方法是：先将主元消成方法是：先将主元消成
25、1 1，再用此，再用此1 1将其所在列的其余元消将其所在列的其余元消成成0 0。主元主元54321 xxxxxbBNBXBC 0 0 0 12 71001030105400149300200360543xxx000 0 0 0 12 7 3040900.1 0 0 1 0.3 300.4-0 1 0 7.8 2400.5-1 0 0 2.5 50243xxx1200 1.2-0 0 0 3.41002030.8 以以10为为i主元进行初等行变换主元进行初等行变换54321 xxxxxbBNBXBC 0 0 0 12 71001030105400149300200360543xxx000 0 0
26、 0 12 7 3040900.1 0 0 1 0.3 300.4-0 1 0 7.8 2400.5-1 0 0 2.5 50243xxx1200 1.2-0 0 0 3.41002030.8 0.2-0.4 0 0 1 201.16 0.32-1 0 0 840.16 0.12-0 1 0 24213xxx1270428.,0,0)(20,24,84,*zXT（请解释其实际意义）（请解释其实际意义）以以 为主元进行初等行变换为主元进行初等行变换0 0 0 -1.36 -0.52 2.5练习：用单纯形法求解下面的线性规划练习：用单纯形法求解下面的线性规划将将模模型型化化为为标标准准型型：解解：
27、增增加加松松弛弛变变量量,43xx212xxMaxz 0,622 -.4342132121xxxxxxxxxxts 0,62-2-.2121 21xxxxxxts 212xxMins 4321xxxx 0 0 2-1bBNBXBC10 2 101 1 1-6243xx006 0 0 2-1 1 0 2 1 6 1 1 3 0 813xx10 1-0 4-0TX)0,8,0,6(6s单纯形表：单纯形表：212xxMaxz 0,622 -.4342132121xxxxxxxxxxts410105001010 -0.40 1 -0.50 0 0.130.810-1.2【】【】410105001010
28、 -0.40 1 -0.50 0 0.130.810-1.2【】【】Min型单纯形表：型单纯形表：Min型单纯形表与型单纯形表与Max型的区别仅在于：检验数反型的区别仅在于：检验数反号，即号，即 -当检验数均大于等于零时为最优；当检验数均大于等于零时为最优；-令负检验数中最小的对应的变量进基。令负检验数中最小的对应的变量进基。四、大四、大M法法1 问题问题设问题：设问题：0.XbAXtsCXMaxzA中不含中不含 I例如，例如，用单纯形法求解线性规划用单纯形法求解线性规划例如，例如，用单纯形法求解线性规划用单纯形法求解线性规划 解：解：首先增加松弛变量与剩余变量首先增加松弛变量与剩余变量x4、
29、x5，将模型约，将模型约束化为标准型束化为标准型2 方法方法 在第二、第三个约束方程左边分别添加人工变在第二、第三个约束方程左边分别添加人工变量量x60、x70。在求极大型在求极大型M问题中，人工变量在目标函数中问题中，人工变量在目标函数中系数均为系数均为-M；在求极小型；在求极小型min问题中，系数均为问题中，系数均为M，其中其中M是很大很大的正数是很大很大的正数。7654321 xxxxxxxbB1 BXBC M M 0 0 2 3 4-248764xxxMM0 2441 -2 2 1 0 0 0-2 1 1 0 -1 1 0-1 0 1 0 0 1 1-4+3M 3-M 2-2M 0 -
30、M 0 07654321 xxxxxxxbB1 BXBC M M 0 0 2 3 4-248764xxxMM0 244364xxx2M0 324xxx2301 -2 2 1 0 0 0-2 1 1 0 -1 1 0-1 0 1 0 0 1 1-4+3M 3-M 2-2M 0 -M 0 04 3 -2 0 1 0 0 -22 -1 1 0 0 -1 1 -12 -1 0 1 0 0 0 1-2+M 3-M 0 0 M 0 2M-228 1 0 0 1 -2 2 -42 -1 1 0 0 -1 1 -12 -1 0 1 0 0 0 11 0 0 0 3 M-3 M+1最优解的基变量中含有人工变量，
31、可以证明此最优解的基变量中含有人工变量，可以证明此情况下，原问题无可行解；情况下，原问题无可行解；最优解的基变量中不含人工变量，即人工变量最优解的基变量中不含人工变量，即人工变量均为零，可以证明在此情况下，从最优解中去掉均为零，可以证明在此情况下，从最优解中去掉人工变量即为原问题的最优解人工变量即为原问题的最优解 使用大使用大M法会出现下列两种情况：法会出现下列两种情况：p26解的几种情况在单纯形表上的体现（解的几种情况在单纯形表上的体现（Max型）：型）：-唯一最优解唯一最优解：终表非基变量检验数均小于零；：终表非基变量检验数均小于零；-多重最优解多重最优解：终表非基变量检验数中有等于零的；
32、：终表非基变量检验数中有等于零的；(书书例例2.12)练习：用单纯形法求解下面的线性规划练习：用单纯形法求解下面的线性规划0,25.2121 21xxxxxxts105153212.5xxMaxz将模型化为标准型：将模型化为标准型：解：增加松弛变量解：增加松弛变量,43xx21xxMaxz5.20,102515 53.4342132121xxxxxxxxxxts10 2 501 5 3101543xx00 0 0 1 2.525 4321xxxx 0 0 1 2.5bBNBXBC51 0 52 153-1 519 02913xx2.50 0.5-0 0 0TX)09,0,2,(5z问题：本题的
33、单纯形终表检验数有何特点？问题：本题的单纯形终表检验数有何特点？非基变量非基变量x2 的检验数等于零。的检验数等于零。解的几种情况在单纯形表上的体现（解的几种情况在单纯形表上的体现（Max型）：型）：-唯一最优解唯一最优解：终表非基变量检验数均小于零；：终表非基变量检验数均小于零；-多重最优解多重最优解：终表非基变量检验数中有等于零的；：终表非基变量检验数中有等于零的；(书书例例2.12)-无界解无界解：任意表有正检验数相应的系数列均非正。：任意表有正检验数相应的系数列均非正。(书书例例2.13)-无解无解：用人工变量法求解，人工变量模型的最优解基：用人工变量法求解，人工变量模型的最优解基中含有人工变量中含有人工变量-退化解退化解：在单纯形终表中，最优解为：在单纯形终表中，最优解为 若其中某分量若其中某分量b k=0，则称此解为一个退化解，则称此解为一个退化解
