运筹学第二单纯形法以及进一步讨论PPT课件.ppt

《运筹学第二单纯形法以及进一步讨论PPT课件.ppt》由会员分享，可在线阅读，更多相关《运筹学第二单纯形法以及进一步讨论PPT课件.ppt（62页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、另另一一个个顶点点(另另一一个个基基可可行行解解)，并并判判断断是是否否是是最最优解解，如如果果是是求求解解结束束，如如果果不不是是就就重重复复进行行第二步，直至目第二步，直至目标函数达到最函数达到最优。具体工作具体工作：(1)如何求出初始基可行解？如何求出初始基可行解？(2)如何判断一个基可行解是否是最如何判断一个基可行解是否是最优？(3)如何从一基可行解如何从一基可行解转换到另一更到另一更优的基可行解？的基可行解？第三张，PPT共六十二页，创作于2022年6月军事运筹学军事运筹学军事运筹学军事运筹学4 4(二二)单纯形法的求解方法形法的求解方法1.确定初始基可行解，只要找出初始可行基。确定

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

4、事运筹学军事运筹学军事运筹学军事运筹学6 6（2）化）化标准型法准型法以以B作作为可行基。将可行基。将(2.3)移移项得得令令xm+1=xn=0 则 xi=bi (i=1，2，m)又因又因bi0(标准型中准型中规定定)，则得一初始基可行解得一初始基可行解X=(b1,b2,bm,0,0)T第六张，PPT共六十二页，创作于2022年6月军事运筹学军事运筹学军事运筹学军事运筹学7 7（3）人工）人工变量法量法 当当所所有有约束束条条件件都都是是“”形形式式的的不不等等式式或或等等式式约束束时，如果不存在如果不存在单位矩位矩阵，就采用人工，就采用人工变量法量法:对不不等等式式约束束左左端端减减去去一一

5、个个非非负的的剩剩余余变量量，再再加加上上一一个非个非负的人工的人工变量；量；对等式等式约束左端再加上一个非束左端再加上一个非负的人工的人工变量。量。这样就就可可以以得得到到一一个个单位位矩矩阵，即即总能能得得到到一一个个初初始可行基。始可行基。第七张，PPT共六十二页，创作于2022年6月军事运筹学军事运筹学军事运筹学军事运筹学8 8（3）人工）人工变量法量法设线性性规划划问题的的约束条件是束条件是分分别对各各约束方程加人工束方程加人工变量量 xn+1,xn+2,xn+m可得可得第八张，PPT共六十二页，创作于2022年6月军事运筹学军事运筹学军事运筹学军事运筹学9 9以以xn+1，xn+m

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

7、筹学军事运筹学军事运筹学11112.最最优性性检验与解的判与解的判别线性性规划划问题的求解的求解结果果唯一最唯一最优解解无无穷多最多最优解解无界解无界解无可行解无可行解如何判如何判别？由上述初始基可行解确定的由上述初始基可行解确定的讨论，可知，可知约束方程束方程组变成成下面的形式：下面的形式：第十一张，PPT共六十二页，创作于2022年6月军事运筹学军事运筹学军事运筹学军事运筹学1212 由初始基可行解开始进行从一个基可行解到另一个更优基可行解的求解过程中，每一次求基可行解时，约束方程组都化成上述形式。为了便于讨论，把它记成一般形式。转换迭代迭代过程中的一般形式程中的一般形式为：第十二张，PP

8、T共六十二页，创作于2022年6月军事运筹学军事运筹学军事运筹学军事运筹学1313 由初始基可行解开始进行从一个基可行解到另一个更优基可行解的求解过程中，每一次求基可行解时，约束方程组都化成上述形式。为了便于讨论，把它记成一般形式。把把(2.7)式代入目式代入目标函数函数中可得中可得第十三张，PPT共六十二页，创作于2022年6月军事运筹学军事运筹学军事运筹学军事运筹学1414令令于是于是再令再令则第十四张，PPT共六十二页，创作于2022年6月军事运筹学军事运筹学军事运筹学军事运筹学1515 假假设X(0)=(b1,b2,bm,0,0)T 是一个基可行解，是一个基可行解，则有下列判断定理：有

9、下列判断定理：1.最最优解解：如果：如果对一切一切 j=m+1，n 有有 j0，则X(0)为最最优解解(注意，注意，这里是里是针对目目标函数求极大而言的函数求极大而言的)。2.无无穷多最多最优解解：如果：如果对一切一切 j=m+1，n 有有j0，又存在又存在 m+k=0，则线性性规划划问题有无有无穷多最多最优解。解。3.无界解无界解：如果有一个：如果有一个m+k 0，且，且对 i=1,m 有有ai,m+k0，则线性性规划划问题有无界解有无界解(无最无最优解解)。第十五张，PPT共六十二页，创作于2022年6月16163.基变换基变换q基基变换：在在单纯形形法法求求解解中中，如如果果得得到到了了

10、某某一一个个基基可可行行解解，并并判判断断了了它它不不是是最最优解解，就就要要从从该基基变换成成另另一一个个更更优的的基基并并求求出出新新的的基基可可行行解。解。q方方法法：第第一一步步确确定定换入入非非基基变量量；第第二二步步确确定定换出出基基变量量；第第三三步步将将所所确确定定的的一一对变量量对应的的系系数数列列向向量量对换得得到到新新的的基基，求求出出新新的的基基可可行解。行解。第十六张，PPT共六十二页，创作于2022年6月军事运筹学军事运筹学军事运筹学军事运筹学1717(1)换入入变量的确定量的确定再看再看(2.8)式式其中其中 当某些当某些j0时，xj 增加会使目增加会使目标函数函

11、数值增加，我增加，我们就要从中确定一个非基就要从中确定一个非基变量量xj换到基到基变量中。方法：量中。方法：把把j值最大者所最大者所对应的的变量量换入。即入。即若若 则对应的的变量量 xk 为换入入变量量,这样的迭代速度的迭代速度最快。最快。第十七张，PPT共六十二页，创作于2022年6月军事运筹学军事运筹学军事运筹学军事运筹学1818(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 为换入非基向量。于

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

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

14、六十二页，创作于2022年6月军事运筹学军事运筹学军事运筹学军事运筹学2222 如果如果X(0)不是最不是最优，则需作基需作基变换。设 xk 为确定的确定的换入入变量，量，显然然 为在迭代在迭代过程中程中 可表示可表示为于是可确定于是可确定 xl 为换出出变量。量。下面就要把下面就要把xk，xl所所对应的向量的向量pk=(a1k,a2k,amk)T 和和pl=(0,1,0)T 进行交行交换，并且要把，并且要把pk变为单位向量。位向量。我我们将通将通过系数矩系数矩阵的增广矩的增广矩阵进行初等行初等变换来来实现。第二十二张，PPT共六十二页，创作于2022年6月2323(2.10)式的增广矩式的增

15、广矩阵为第二十三张，PPT共六十二页，创作于2022年6月军事运筹学军事运筹学军事运筹学军事运筹学2424交交换步步骤：将将(2.11)式中第式中第 l 行除以行除以 alk ；将将(2.11)式中式中 xk 列的各列的各元素，除了元素，除了 alk 变换为1以外，其它都以外，其它都应变为0。第。第i 行行(il)的的变换是：将用是：将用(第第 i 行行)(经过变换以后的第以后的第 l 行乘以行乘以aik)。第二十四张，PPT共六十二页，创作于2022年6月军事运筹学军事运筹学军事运筹学军事运筹学2525经过变换以后系数矩阵各元素的变换关系式：经过变换以后系数矩阵各元素的变换关系式：第二十五张

16、，PPT共六十二页，创作于2022年6月军事运筹学军事运筹学军事运筹学军事运筹学2626经过变换后的新增广矩后的新增广矩阵为：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(1)=(b1,bl-1,0,bl+1 ,bm,0,bl,0,0)T把元

17、素把元素alk称称为主元素，它所在的列称主元素，它所在的列称为主列，它所在的主列，它所在的行称行称为主行。主行。第二十六张，PPT共六十二页，创作于2022年6月军事运筹学军事运筹学军事运筹学军事运筹学2727(三三)单纯形法的计算步骤单纯形法的计算步骤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

18、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将上述方程将上述方程组写成增广组写成增广矩阵矩阵第二十七张，PPT共六十二页，创作于2022年6月军事运筹学军事运筹学军事运筹学军事运筹学2828 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 看作不参

19、与基变换的基变量，它与看作不参与基变换的基变量，它与x1，x2，xm的系数构的系数构成一个基。采用初等行变换将成一个基。采用初等行变换将c1 c2 cm 变换为零，使其对应的系变换为零，使其对应的系数矩阵为单位矩阵。可得：数矩阵为单位矩阵。可得：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共六

20、十二页，创作于2022年6月军事运筹学军事运筹学军事运筹学军事运筹学2929cjc1cmcm+1cniCBXBbx1xmxm+1xnc1c2cmx1x2xmb1b2bm100001a1m+1a2m+1amm+1a1na2namn12mz mcibi i=100cm+1 mciaim+1 i=1cn mciain i=1计算表计算表11：XB列中填入基变量，这里是列中填入基变量，这里是x1，x2，xm；CB列中填入基变量的价值系数，它们与基变量对应；列中填入基变量的价值系数，它们与基变量对应；b列中填入约束方程组右端的常数；列中填入约束方程组右端的常数；cj行中填入基变量的价值系数行中填入基变量

21、的价值系数c1，c2，cn；i列中的数字是在确定换入变量后，按列中的数字是在确定换入变量后，按 规则计算后填入；规则计算后填入；最后一行称为检验数行，对应各非基变量。最后一行称为检验数行，对应各非基变量。非基变量检验数j 。第二十九张，PPT共六十二页，创作于2022年6月军事运筹学军事运筹学军事运筹学军事运筹学30302.计算步骤计算步骤(1)找出初始可行基，确定初始基可行解，建立初始单纯形表。找出初始可行基，确定初始基可行解，建立初始单纯形表。(2)检验各非基变量检验各非基变量 xj 的检验数的检验数 j=cj i=1 m ciaij ，如果如果 j0 ，j=m+1，n；则已得到最优解，可

22、停止计算。否则转入下一步。；则已得到最优解，可停止计算。否则转入下一步。(3)存在存在 j 0 ，j=m+1，n 中，若存在某个中，若存在某个 k 对应对应 xk 的系数向量的系数向量pk0，则，则问题无解，停止计算。否则，转入下一步。问题无解，停止计算。否则，转入下一步。(4)根据根据max(j 0)=k ，确定，确定xk 为换入变量，按为换入变量，按 规则计算规则计算 =min(aik 0 )biaik =blalk可确定可确定xl为换出变量。转下一步。为换出变量。转下一步。(5)以以 alk 为主元素进行迭代，把为主元素进行迭代，把 xk 所对应的列向量所对应的列向量pk=a1ka2ka

23、lkamk0010变换为变换为第第 l 行行将将XB列中的列中的 xl 换为换为 xk，得到新的单纯形表。，得到新的单纯形表。在得到最优解或确定无界解之前，重复在得到最优解或确定无界解之前，重复(2)(5)。第三十张，PPT共六十二页，创作于2022年6月军事运筹学军事运筹学军事运筹学军事运筹学31313举例举例例例 求下列线性规划问题的解求下列线性规划问题的解 max 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化标准型化标准型

24、(1)确定初始基可行解：确定初始基可行解：由标准型中的约束方程组可知变量由标准型中的约束方程组可知变量x3，x4，x5 所对应的系数向量构成所对应的系数向量构成33单位矩阵为一基。可得初始基可行解单位矩阵为一基。可得初始基可行解 X(0)=(0，0，8，16，12)T据此生成单纯形表据此生成单纯形表cj23000 iCBXBbx1x2x3x4x5000 x3x4x581612140204100010001z 000表表11：j23430第三十一张，PPT共六十二页，创作于2022年6月军事运筹学军事运筹学军事运筹学军事运筹学3232cj23000 iCBXBbx1x2x3x4x5003x3x4

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

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

27、8010z 000表表14：最优解最优解 X(3)=(4，2，0，0，4)T，z=14j3/21/814第三十四张，PPT共六十二页，创作于2022年6月3535单纯形法小结单纯形法小结q求解求解过程程确定初始基可行解确定初始基可行解判断是否是最判断是否是最优解解是，求解是，求解结束；（或者无最束；（或者无最优解）解）否。确定否。确定换入入换出出变量量基基变换，得到新的可行基，得到新的可行基转入第二步，重复。入第二步，重复。第三十五张，PPT共六十二页，创作于2022年6月3636第二章第二章 线性规划线性规划q 单纯形法形法q 人工人工变量法量法q 退化退化问题q 检验数的几种表数的几种表现

28、形式形式q 单纯形法形法总结第三十六张，PPT共六十二页，创作于2022年6月军事运筹学军事运筹学军事运筹学军事运筹学37373.2 人工人工变量法量法（3.13）在前面我在前面我们讲过由人工由人工变量法构造初始可行基，若量法构造初始可行基，若线性性规划划问题的的约束条件束条件为然后人然后人为的加上的加上变量量 xn+1，xn+2，xn+m后得到后得到(3.14)第三十七张，PPT共六十二页，创作于2022年6月军事运筹学军事运筹学军事运筹学军事运筹学38383.2 人工人工变量法量法 若若人人工工变变量量0，(3.14)与与(3.13)不不等等价价，即即对对原原LP问问题题的的约约束束条条件

29、件进进行行了了“篡篡改改”，不不是是希希望望的的。但但又又需添加人工变量，得到初始可行基。需添加人工变量，得到初始可行基。为为保保证证它它与与原原LP问问题题得得到到的的最最优优解解一一致致，需需要要将将人人工变量从基变量中逐个替换出来。工变量从基变量中逐个替换出来。若若经经过过基基变变换换后后，基基变变量量中中不不再再含含有有非非零零的的人人工工变变量量，这这表表示示原原问问题题有有解解；若若在在最最终终的的表表中中当当所所有有的的检检验验数数 0，但在其中还有某个非零人工变量，这表示无可行解。，但在其中还有某个非零人工变量，这表示无可行解。第三十八张，PPT共六十二页，创作于2022年6月

30、军事运筹学军事运筹学军事运筹学军事运筹学39393.2 人工人工变量法量法 在在引引入入人人工工变变量量的的同同时时修修改改目目标标函函数数，规规定定人人工工变变量量在在目标函数中的系数为目标函数中的系数为(M)(M 0的大数的大数)。即。即 这这种种方方法法叫叫大大M法法。作作了了上上述述变变换换之之后后，再再用用单单纯纯形形法法把把人人工工变变量量从从基基变变量量中中转转换换出出去去，然然后后求求原原问问题题的最优解。的最优解。3.2.1 大大M法法第三十九张，PPT共六十二页，创作于2022年6月军事运筹学军事运筹学军事运筹学军事运筹学40403.2 人工人工变量法量法例：用大例：用大

31、M 法求解如下线性规划问题法求解如下线性规划问题第四十张，PPT共六十二页，创作于2022年6月军事运筹学军事运筹学军事运筹学军事运筹学41413.2 人工人工变量法量法解：在上述问题的约束条件中加入松弛变量、解：在上述问题的约束条件中加入松弛变量、剩余变量和人工变量，得到剩余变量和人工变量，得到其中其中M是一个任意大的正数。是一个任意大的正数。第四十一张，PPT共六十二页，创作于2022年6月军事运筹学军事运筹学军事运筹学军事运筹学42423.2 人工人工变量法量法建立单纯形表：建立单纯形表：cj-31100MMiCBXBbx1x2x3x4x5x6x70 x4111-211000Mx63-4

32、120-110Mx71-2010001j000-3+6M1-M1-3MM1113/21第四十二张，PPT共六十二页，创作于2022年6月军事运筹学军事运筹学军事运筹学军事运筹学43433.2 人工人工变量法量法单纯形表单纯形表2：cj-31100MMiCBXBbx1x2x3x4x5x6x70 x4103-20100-1Mx610100-11-21x31-2010001j000-11-M3M-1M1-1-第四十三张，PPT共六十二页，创作于2022年6月军事运筹学军事运筹学军事运筹学军事运筹学44443.2 人工人工变量法量法单纯形表单纯形表3：cj-31100MMiCBXBbx1x2x3x4x

33、5x6x70 x4123001-22-51x210100-11-21x31-2010001j000-1M-1M+1134-第四十四张，PPT共六十二页，创作于2022年6月军事运筹学军事运筹学军事运筹学军事运筹学45453.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月军事

34、运筹学军事运筹学军事运筹学军事运筹学46463.2 人工人工变量法量法3.2.2 两阶段法两阶段法q用计算机求解含有人工变量的线性规划问题用计算机求解含有人工变量的线性规划问题时，只能用很大的数代替时，只能用很大的数代替M，这就可能造成，这就可能造成计算上的错误。计算上的错误。q引入两阶段法求解。引入两阶段法求解。第四十六张，PPT共六十二页，创作于2022年6月军事运筹学军事运筹学军事运筹学军事运筹学47473.2 人工人工变量法量法 第一阶段，不考虑原问题是否存在基可行解；给原线性规划问题第一阶段，不考虑原问题是否存在基可行解；给原线性规划问题加入人工变量，并加入人工变量，并构造仅含人工变

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

36、实现现最最小化。即小化。即 再再利利用用单单纯纯形形法法求求解解上上述述模模型型，若若最最优优值值为为0，则则原原问问题题有有解解，可进行第二阶段计算。否则原问题无可行解。可进行第二阶段计算。否则原问题无可行解。q 第第二二阶阶段段，将将第第一一阶阶段段计计算算得得到到的的最最终终表表，除除去去人人工工变变量量，将将目目标标函函数数行行的的系系数数，换换原原问问题题的的目目标标函函数数系系数数，作作为为第第二二阶阶段段计计算算的的初初始始表。表。各阶段的计算方法与前面的单纯形法相同。各阶段的计算方法与前面的单纯形法相同。第四十八张，PPT共六十二页，创作于2022年6月军事运筹学军事运筹学军事

37、运筹学军事运筹学49493.2 人工人工变量法量法3.2.2 两阶段法两阶段法例：用两阶段法求解线性规划问题例：用两阶段法求解线性规划问题第四十九张，PPT共六十二页，创作于2022年6月军事运筹学军事运筹学军事运筹学军事运筹学50503.2 人工人工变量法量法解：添加人工变量，给出第一阶段的数学模解：添加人工变量，给出第一阶段的数学模型为型为第五十张，PPT共六十二页，创作于2022年6月军事运筹学军事运筹学军事运筹学军事运筹学51513.2 人工人工变量法量法用单纯形法求解得到的最后结果为：用单纯形法求解得到的最后结果为：此时，得到的最优解为此时，得到的最优解为 =0，X=（0，1，1，1

38、2，0，0，0），它是原），它是原LP问题的基可行解，因此可以进行第二问题的基可行解，因此可以进行第二阶段的计算。阶段的计算。cj0000011iCBXBbx1x2x3x4x5x6x70 x4123001-22-50 x210100-11-20 x31-201000000000011第五十一张，PPT共六十二页，创作于2022年6月军事运筹学军事运筹学军事运筹学军事运筹学52523.2 人工人工变量法量法第二阶段的初始单纯形表为：第二阶段的初始单纯形表为：cj0000011iCBXBbx1x2x3x4x5x6x70 x4123001-22-50 x210100-11-20 x31-201000

39、0-31100011第五十二张，PPT共六十二页，创作于2022年6月5353第二章第二章 线性规划线性规划q 单纯形法形法q 人工人工变量法量法q 退化退化问题q 检验数的几种表数的几种表现形式形式q 单纯形法形法总结第五十三张，PPT共六十二页，创作于2022年6月军事运筹学军事运筹学军事运筹学军事运筹学54543.3 退化退化问题(1)什么是退化？什么是退化？当基解当基解 基可行解基可行解 最优基可行解中有基变量为最优基可行解中有基变量为0时，时，即出现退化。即出现退化。当出现退化时，可能出现计算过程的循环，便永远达当出现退化时，可能出现计算过程的循环，便永远达不到最优解。不到最优解。第

40、五十四张，PPT共六十二页，创作于2022年6月军事运筹学军事运筹学军事运筹学军事运筹学55553.3 退化退化问题(2)勃兰特规则勃兰特规则为了避免出现循环，勃兰特提出下面规则：为了避免出现循环，勃兰特提出下面规则：选取选取cjzj 0中下标最小的非基变量中下标最小的非基变量xk为换入变量，为换入变量，即即 k=min(j|cjzj 0)当按当按规则计算存在两个和两个以上最小比值时，规则计算存在两个和两个以上最小比值时，选取下标最小的基变量为换出变量。选取下标最小的基变量为换出变量。按照此原则一定可以避免出现循环。按照此原则一定可以避免出现循环。第五十五张，PPT共六十二页，创作于2022年

41、6月5656第二章第二章 线性规划线性规划q 单纯形法形法q 人工人工变量法量法q 退化退化问题q 检验数的几种表数的几种表现形式形式q 单纯形法形法总结第五十六张，PPT共六十二页，创作于2022年6月军事运筹学军事运筹学军事运筹学军事运筹学57573.4 检验数的几种表数的几种表现形式形式标准型Max z=CXMin z=CX检验数AX=b,X0AX=b,X0cj-zj00zj-cj00第五十七张，PPT共六十二页，创作于2022年6月5858第二章第二章 线性规划线性规划q 单纯形法形法q 人工人工变量法量法q 退化退化问题q 检验数的几种表数的几种表现形式形式q 单纯形法形法总结第五十

42、八张，PPT共六十二页，创作于2022年6月军事运筹学军事运筹学军事运筹学军事运筹学59593.5 单纯形法形法总结设设B是一个可行基，一般是单位矩阵，是一个可行基，一般是单位矩阵，B-1=B=Im;N是非基变量的系数是非基变量的系数矩阵。矩阵。基变量基变量XB=(xB1，xB2，xBm)T非基变量非基变量XN=(xN1，xN2，xNn)TCB=(cB1，cB2，cBm)CN=(cN1，cN2，cNn)初始基可行解初始基可行解X(0)=(b1，b2，bm，0)T第五十九张，PPT共六十二页，创作于2022年6月军事运筹学军事运筹学军事运筹学军事运筹学6060cjc1cmcm+1cn iCBXB

43、bx1xmxm+1xnc1c2cmx1x2xmb1b2bm100001a1m+1a2m+1amm+1a1na2namn 1 2mz mcibi i=100cm+1 mciaim+1 i=1cn m ciain i=1单纯形法计算表：单纯形法计算表：矩矩阵阵法法表表基变量非基变量RHSI0B-1NCN CB B-1NB-1b CB B-1b关键参数：关键参数：N，B-1j，第六十张，PPT共六十二页，创作于2022年6月军事运筹学军事运筹学军事运筹学军事运筹学61613.5 单纯形法形法总结（1）求一个基）求一个基 B 及及 B-1，构建一个初始表；，构建一个初始表；（2）两个参数）两个参数j（N），），的计算；的计算；（3）两个判断最优解，无最优解；）两个判断最优解，无最优解；（4）一次变换，产生一个新基）一次变换，产生一个新基 B1 及及 B1-1；（5）循环（）循环（2）（）（4）直至最优或终止计算。）直至最优或终止计算。求求 解解 步步 骤骤 小小 结结第六十一张，PPT共六十二页，创作于2022年6月感谢大家观看第六十二张，PPT共六十二页，创作于2022年6月