运筹学第二单纯形法以及进一步讨论

1、关于运筹学第二单纯形法及进一步讨论第一张，PPT共六十二页，创作于2022年6月2第二章 线性规划 单纯形法 人工变量法 退化问题 检验数的几种表现形式 单纯形法总结第二张，PPT共六十二页，创作于2022年6月军事运筹学3(一)单纯形法的基本思路3.1 单纯形法思路：首先求出一个顶点(基可行解)，并判断是否是最优解，如果是求解结束，如果不是就进行下一步；第二步转换到另一个顶点(另一个基可行解)，并判断是否是最优解，如果是求解结束，如果不是就重复进行第二步，直至目标函数达到最优。具体工作： (1) 如何求出初始基可行解？(2) 如何判断一个基可行解是否是最优？(3) 如何从一基可行解转换到另一

2、更优的基可行解？第三张，PPT共六十二页，创作于2022年6月军事运筹学4(二)单纯形法的求解方法1. 确定初始基可行解，只要找出初始可行基。(1) 直接观察法：从系数矩阵 A 中直接观察出一个初始基3.1 单纯形法第四张，PPT共六十二页，创作于2022年6月军事运筹学5（2）化标准型法 如果所有约束条件都是“”形式的不等式，则可以利用化标准型的方法，在每个约束条件的左端加上一个松弛变量。重新对 xj 及 aij 进行编号，可得下列方程组：从中可得单位矩阵第五张，PPT共六十二页，创作于2022年6月军事运筹学6（2）化标准型法以B作为可行基。将(2.3)移项得令xm+1= = xn=0 则

3、 xi = bi ( i=1，2，m)又因bi0 (标准型中规定)，则得一初始基可行解X=(b1,b2, ,bm,0,0)T第六张，PPT共六十二页，创作于2022年6月军事运筹学7（3）人工变量法 当所有约束条件都是“”形式的不等式或等式约束时，如果不存在单位矩阵，就采用人工变量法:对不等式约束左端减去一个非负的剩余变量，再加上一个非负的人工变量；对等式约束左端再加上一个非负的人工变量。 这样就可以得到一个单位矩阵，即总能得到一个初始可行基。第七张，PPT共六十二页，创作于2022年6月军事运筹学8（3）人工变量法设线性规划问题的约束条件是分别对各约束方程加人工变量 xn+1, xn+2,

4、, xn+m可得第八张，PPT共六十二页，创作于2022年6月军事运筹学9以xn+1， xn+m为基变量，可得到一个单位矩阵令 x1 = x2 = = xn = 0，可得(2.6)式的一个初始基可行解 X(0) = ( 0，0， ，0，b1，b2， ， bm )T 以此基可行解为起始点转换到(2.5)的基可行解。（3）人工变量法第九张，PPT共六十二页，创作于2022年6月军事运筹学102. 最优性检验与解的判别线性规划问题的求解结果唯一最优解无穷多最优解无界解无可行解如何判别？第十张，PPT共六十二页，创作于2022年6月军事运筹学112. 最优性检验与解的判别线性规划问题的求解结果唯一最优

5、解无穷多最优解无界解无可行解如何判别？ 由上述初始基可行解确定的讨论，可知约束方程组变成下面的形式：第十一张，PPT共六十二页，创作于2022年6月军事运筹学12 由初始基可行解开始进行从一个基可行解到另一个更优基可行解的求解过程中，每一次求基可行解时，约束方程组都化成上述形式。为了便于讨论，把它记成一般形式。转换迭代过程中的一般形式为：第十二张，PPT共六十二页，创作于2022年6月军事运筹学13 由初始基可行解开始进行从一个基可行解到另一个更优基可行解的求解过程中，每一次求基可行解时，约束方程组都化成上述形式。为了便于讨论，把它记成一般形式。把(2.7)式代入目标函数中可得第十三张，PPT

6、共六十二页，创作于2022年6月军事运筹学14令于是再令则第十四张，PPT共六十二页，创作于2022年6月军事运筹学15 假设X(0)=( b1, b2, , bm, 0, , 0)T 是一个基可行解，则有下列判断定理：1. 最优解：如果对一切 j=m+1，n 有 j0，则X(0)为最优解(注意，这里是针对目标函数求极大而言的)。2. 无穷多最优解：如果对一切 j=m+1，n 有j0，又存在 m+k=0，则线性规划问题有无穷多最优解。3. 无界解：如果有一个m+k0，且对 i=1,m 有ai,m+k0，则线性规划问题有无界解(无最优解)。第十五张，PPT共六十二页，创作于2022年6月163.

7、 基变换基变换：在单纯形法求解中，如果得到了某一个基可行解，并判断了它不是最优解，就要从该基变换成另一个更优的基并求出新的基可行解。方法：第一步确定换入非基变量；第二步确定换出基变量；第三步将所确定的一对变量对应的系数列向量对换得到新的基，求出新的基可行解。第十六张，PPT共六十二页，创作于2022年6月军事运筹学17(1) 换入变量的确定再看 (2.8)式其中 当某些j0时， xj 增加会使目标函数值增加，我们就要从中确定一个非基变量xj换到基变量中。方法： 把j值最大者所对应的变量换入。即若 则对应的变量 xk 为换入变量, 这样的迭代速度最快。第十七张，PPT共六十二页，创作于2022年

8、6月军事运筹学18(2) 换出变量的确定设B(p1,p2, ,pm) 是一个基，与之对应的基可行解为X(0)=(x1(0), x2(0), , xm(0) , 0, ,0 )T 。pm+1,pm+2, ,pm+t , ,pn为非基向量。设确定pm+t 为换入非基向量。于是其中im+t为一组不全为0的数 ( j=1，m)。第十八张，PPT共六十二页，创作于2022年6月军事运筹学19不妨设为一正数，则有恒等式 或根据(2.9)可如下确定换出变量：令确定xl为换出变量。注意： pj ( j = 1，m, j l )，pm+t 线性无关；存在基可行解。第十九张，PPT共六十二页，创作于2022年6月

9、军事运筹学20注意： pj ( j =1，m, j l )，pm+t 线性无关；存在基可行解。：假设pj ( j=1，m, jl)，pm+t 线性相关，则存在不全为0的数j使得又因所以有这说明 p1, p2, , pm 线性相关。矛盾由构成的 X(1) 是一个基可行解。第二十张，PPT共六十二页，创作于2022年6月军事运筹学214基变换的系数矩阵法以下列形式的约束方程组进行讨论。mm单位矩阵是基， x1, x2, , xm是基变量。可得基可行解X(0)=(b1,b2, ,bm,0,0)T。第二十一张，PPT共六十二页，创作于2022年6月军事运筹学22 如果X(0)不是最优，则需作基变换。设

10、 xk 为确定的换入变量，显然 为在迭代过程中 可表示为于是可确定 xl 为换出变量。 下面就要把xk，xl所对应的向量pk=(a1k,a2k, ,amk)T 和pl=(0, , 1, ,0)T 进行交换，并且要把pk变为单位向量。 我们将通过系数矩阵的增广矩阵进行初等变换来实现。第二十二张，PPT共六十二页，创作于2022年6月23(2.10)式的增广矩阵为第二十三张，PPT共六十二页，创作于2022年6月军事运筹学24交换步骤：将(2.11)式中第 l 行除以 alk ；将(2.11)式中 xk 列的各元素，除了 alk 变换为1以外，其它都应变为0 。第i 行 ( il ) 的变换是：将

11、用(第 i 行)(经过变换以后的第 l 行乘以aik)。第二十四张，PPT共六十二页，创作于2022年6月军事运筹学25经过变换以后系数矩阵各元素的变换关系式：第二十五张，PPT共六十二页，创作于2022年6月军事运筹学26经过变换后的新增广矩阵为： 1 -a1kalk 0 a1m+1 0 a1n 0 +1alk 0 alm+1 1 aln 0 -amkalk 1 amm+1 0 amn (3.12) x1 xl xm xm+1 xk xnbb1blbm新的基可行解： 由(2.12)式可知x1 ， ， xk ， ， xm的系数列向量构成mm单位矩阵，它是可行基。于是得到一个基可行解X(1)：X

12、(1)=(b1, ,bl-1 ,0, bl+1 , bm , 0, bl ,0 , 0)T把元素alk称为主元素，它所在的列称为主列，它所在的行称为主行。第二十六张，PPT共六十二页，创作于2022年6月军事运筹学27(三)单纯形法的计算步骤1. 单纯形表 将约束方程组与目标函数组成n+1个变量，m+1个方程的方程组。 x1 +a1m+1xm+1+a1nxn b1 x2 +a2m+1xm+1+a2nxn b2 xm+amm+1xm+1+amnxn bmz+ c1x1+c2x2+ cmxm + cm+1xm+1 + cnxn 0 0 1 0 0 a1m+1 a1n 0 0 1 0 a2m+1 a

13、2n 0 0 0 1 amm+1 amn z x1 x2 xm xm+1 xnbb1b2bm1 c1 c2 cm cm+1 cn 0将上述方程组写成增广矩阵第二十七张，PPT共六十二页，创作于2022年6月军事运筹学28 0 1 0 0 a1m+1 a1n 0 0 1 0 a2m+1 a2n 0 0 0 1 amm+1 amn z x1 x2 xm xm+1 xnbb1b2bm1 c1 c2 cm cm+1 cn 0将上述方程组写成增广矩阵 将 z 看作不参与基变换的基变量，它与x1，x2，xm的系数构成一个基。采用初等行变换将c1 c2 cm 变换为零，使其对应的系数矩阵为单位矩阵。可得：

14、0 1 0 0 a1m+1 a1n 0 0 1 0 a2m+1 a2n 0 0 0 1 amm+1 amn z x1 x2 xm xm+1 xnbb1b2bmcibi1 0 0 0 cm+1 ciaim+1 cn ciain m i=1m i=1m i=1根据上述增广矩阵设计计算表：非基变量检验数j 。第二十八张，PPT共六十二页，创作于2022年6月军事运筹学29cjc1cmcm+1cniCBXBbx1xmxm+1xnc1c2cmx1x2xmb1b2bm100001a1m+1a2m+1amm+1a1na2namn12mz mcibi i=100cm+1 mciaim+1 i=1cn mcia

15、in i=1计算表11：XB列中填入基变量，这里是x1，x2，xm；CB列中填入基变量的价值系数，它们与基变量对应；b列中填入约束方程组右端的常数； cj行中填入基变量的价值系数c1， c2， cn；i列中的数字是在确定换入变量后，按 规则计算后填入；最后一行称为检验数行，对应各非基变量。非基变量检验数j 。第二十九张，PPT共六十二页，创作于2022年6月军事运筹学302. 计算步骤(1) 找出初始可行基，确定初始基可行解，建立初始单纯形表。(2) 检验各非基变量 xj 的检验数 j=cj i=1 m ciaij ，如果 j0 ，j=m+1，n；则已得到最优解，可停止计算。否则转入下一步。(

16、3) 存在 j0 ，j=m+1，n 中，若存在某个 k 对应 xk 的系数向量pk0，则问题无解，停止计算。否则，转入下一步。(4) 根据max( j0)= k ，确定xk 为换入变量，按 规则计算 =min ( aik0 ) biaik = blalk可确定xl为换出变量。转下一步。(5) 以 alk 为主元素进行迭代，把 xk 所对应的列向量pk= a1ka2kalkamk0010变换为第 l 行将XB列中的 xl 换为 xk，得到新的单纯形表。在得到最优解或确定无界解之前，重复(2)(5)。第三十张，PPT共六十二页，创作于2022年6月军事运筹学313举例例 求下列线性规划问题的解 m

17、ax z2x1+3x2x1 2x284x1 16 4x212x1x2 0 max z2x1+3x2+0 x3+0 x4+0 x5x1 2x2 x3 84x1 x4 16 4x2 x512x1x2 x3 x4 x5 0化标准型(1) 确定初始基可行解：由标准型中的约束方程组可知变量x3，x4， x5 所对应的系数向量构成33单位矩阵为一基。可得初始基可行解 X(0)=(0，0，8，16，12)T据此生成单纯形表cj23000 iCBXBbx1x2x3x4x5000 x3x4x581612140204100010001z 000表11：j23430第三十一张，PPT共六十二页，创作于2022年6月

18、军事运筹学32cj23000 iCBXBbx1x2x3x4x5003x3x4x221631400011000101/201/4z 000表12：基可行解 X(1)=(0，3，2，16，0)Tj2 -3/424 -9cj23000 iCBXBbx1x2x3x4x5000 x3x4x581612140204100010001z 000表11：j23430第三十二张，PPT共六十二页，创作于2022年6月军事运筹学33cj23000 iCBXBbx1x2x3x4x5003x3x4x221631400011000101/201/424z9 20003/4基可行解 X(1)=(0，3，2，16，0)T表

19、12：jcj23000 iCBXBbx1x2x3x4x5203x1x4x22831000011400101/221/4z 000表13：基可行解 X(2)=(2，3，0，8，0)Tj21/441213第三十三张，PPT共六十二页，创作于2022年6月军事运筹学34cj23000 iCBXBbx1x2x3x4x5203x1x4x22831000011400101/221/4412z13 00201/4表13：基可行解 X(2)=(2，3，0，8，0)Tjcj23000 iCBXBbx1x2x3x4x5203x1x5x2442100001021/21/41/21/8010z 000表14：最优解

20、X(3)=(4，2，0，0，4)T ，z=14j3/21/814第三十四张，PPT共六十二页，创作于2022年6月35单纯形法小结求解过程确定初始基可行解判断是否是最优解是，求解结束；（或者无最优解）否。确定换入换出变量基变换，得到新的可行基转入第二步，重复。第三十五张，PPT共六十二页，创作于2022年6月36第二章 线性规划 单纯形法 人工变量法 退化问题 检验数的几种表现形式 单纯形法总结第三十六张，PPT共六十二页，创作于2022年6月军事运筹学373.2 人工变量法（3.13） 在前面我们讲过由人工变量法构造初始可行基，若线性规划问题的约束条件为然后人为的加上变量 xn+1，xn+2

21、，xn+m后得到(3.14) 第三十七张，PPT共六十二页，创作于2022年6月军事运筹学383.2 人工变量法 若人工变量0，(3.14)与(3.13)不等价，即对原LP问题的约束条件进行了“篡改”，不是希望的。但又需添加人工变量，得到初始可行基。 为保证它与原LP问题得到的最优解一致，需要将人工变量从基变量中逐个替换出来。 若经过基变换后，基变量中不再含有非零的人工变量，这表示原问题有解；若在最终的表中当所有的检验数 0，但在其中还有某个非零人工变量，这表示无可行解。第三十八张，PPT共六十二页，创作于2022年6月军事运筹学393.2 人工变量法 在引入人工变量的同时修改目标函数，规定人

22、工变量在目标函数中的系数为(M )(M0的大数)。即 这种方法叫大M法。作了上述变换之后，再用单纯形法把人工变量从基变量中转换出去，然后求原问题的最优解。3.2.1 大M法第三十九张，PPT共六十二页，创作于2022年6月军事运筹学403.2 人工变量法例：用大 M 法求解如下线性规划问题第四十张，PPT共六十二页，创作于2022年6月军事运筹学413.2 人工变量法解：在上述问题的约束条件中加入松弛变量、剩余变量和人工变量，得到其中M是一个任意大的正数。第四十一张，PPT共六十二页，创作于2022年6月军事运筹学423.2 人工变量法建立单纯形表：cj-31100MMiCBXBbx1x2x3

23、x4x5x6x70 x4111-211000Mx63-4120-110Mx71-2010001j000-3+6M1-M1-3MM1113/21第四十二张，PPT共六十二页，创作于2022年6月军事运筹学433.2 人工变量法单纯形表2：cj-31100MMiCBXBbx1x2x3x4x5x6x70 x4103-20100-1Mx610100-11-21x31-2010001j000-11-M3M-1M1-1-第四十三张，PPT共六十二页，创作于2022年6月军事运筹学443.2 人工变量法单纯形表3：cj-31100MMiCBXBbx1x2x3x4x5x6x70 x4123001-22-51x

24、210100-11-21x31-2010001j000-1M-1M+1134-第四十四张，PPT共六十二页，创作于2022年6月军事运筹学453.2 人工变量法单纯形表4：cj-31100MMiCBXBbx1x2x3x4x5x6x7-3x141001/3-2/32/3-5/31x210100-11-21x390012/3-4/34/3-7/3j0001/3M-1/3M-2/31/32最优解 X =(4,1,9,0,0,0,0)，Zmin = -2。第四十五张，PPT共六十二页，创作于2022年6月军事运筹学463.2 人工变量法3.2.2 两阶段法用计算机求解含有人工变量的线性规划问题时，只能

25、用很大的数代替M，这就可能造成计算上的错误。引入两阶段法求解。第四十六张，PPT共六十二页，创作于2022年6月军事运筹学473.2 人工变量法 第一阶段，不考虑原问题是否存在基可行解；给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数和要求实现最小化。即 再利用单纯形法求解上述模型，若最优值为0，则原问题有解，可进行第二阶段计算。否则原问题无可行解。第四十七张，PPT共六十二页，创作于2022年6月军事运筹学483.2 人工变量法3.2.2 两阶段法 第一阶段，不考虑原问题是否存在基可行解；给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数和要求实现最小化。即 再利用单纯形法

26、求解上述模型，若最优值为0，则原问题有解，可进行第二阶段计算。否则原问题无可行解。 第二阶段，将第一阶段计算得到的最终表，除去人工变量，将目标函数行的系数，换原问题的目标函数系数，作为第二阶段计算的初始表。 各阶段的计算方法与前面的单纯形法相同。第四十八张，PPT共六十二页，创作于2022年6月军事运筹学493.2 人工变量法3.2.2 两阶段法例：用两阶段法求解线性规划问题第四十九张，PPT共六十二页，创作于2022年6月军事运筹学503.2 人工变量法解：添加人工变量，给出第一阶段的数学模型为第五十张，PPT共六十二页，创作于2022年6月军事运筹学513.2 人工变量法用单纯形法求解得到

27、的最后结果为：此时，得到的最优解为 =0，X =（0，1，1，12，0，0，0），它是原LP问题的基可行解，因此可以进行第二阶段的计算。cj0000011iCBXBbx1x2x3x4x5x6x70 x4123001-22-50 x210100-11-20 x31-201000000000011第五十一张，PPT共六十二页，创作于2022年6月军事运筹学523.2 人工变量法第二阶段的初始单纯形表为：cj0000011iCBXBbx1x2x3x4x5x6x70 x4123001-22-50 x210100-11-20 x31-2010000-31100011第五十二张，PPT共六十二页，创作于2022年6月53第二章 线性规划 单纯形法 人工变量法 退化问题 检验数的几种表现形式 单纯形法总结第五十三张，PPT共六十二页，创作于2022年6月军事运筹学543.3 退化问题(1) 什么是退化？ 当基解基可行解最优基可行解中有基变量为0时，即出现退化。 当出现退化时，可能出现计算过程的循环，便永远达不到最优解。第五十四张，PPT共六十二页，创作于2022年6月军事运筹学553.3 退化问题(2) 勃兰特规则为了避免出现循环，勃兰特提出下面规则：选取cjzj0中下标最小的非基变量xk为换入变量，即 k=min (