最新单纯形法(表格形式)ppt课件.ppt

《最新单纯形法(表格形式)ppt课件.ppt》由会员分享，可在线阅读，更多相关《最新单纯形法(表格形式)ppt课件.ppt（139页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五章 单纯形法n5.1 单纯形法的基本思路和原理单纯形法的基本思路和原理n5.2 单纯形法的表格形式单纯形法的表格形式n从可行域中某一个顶点开始，判断此顶点是否是最从可行域中某一个顶点开始，判断此顶点是否是最优解，优解，n如不是则再找另一个使得其目标函数值更优的顶点，如不是则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。称之为迭代，再判断此点是否是最优解。n直到找到一个顶点为其最优解，就是使得其目标函直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优数值最优的解，或者能判断出线性规划问题无最优解为止。解为止。5.2单纯形法的表

2、格形式迭代迭代次数次数基基C CB Bx x1 1x x2 2x x3 3x x4 4x x5 5b b比值比值2 21 10 00 00 00 0 x x3 30 00 05 51 10 00 01515- -x x4 40 06 62 20 01 10 0242424/624/6x x5 50 01 11 10 00 01 15 55 5z zj j0 00 00 00 00 0Z=0Z=0 j j= = c cj j - -z zj j2 21 10 00 00 0miijijacz1?01060003152141131acacacz01020503252241232acacacz5.2

3、单纯形法的表格形式迭代迭代次数次数基基C CB Bx x1 1x x2 2x x3 3x x4 4x x5 5b b比值比值2 21 10 00 00 00 0 x x3 30 00 05 51 10 00 01515- -x x4 40 06 62 20 01 10 0242424/624/6x x5 50 01 11 10 00 01 15 55 5z zj j0 00 00 00 00 0Z=0Z=0 j j= = c cj j - -z zj j2 21 10 00 00 0050240150352413bcbcbcz5.2单纯形法的表格形式迭代迭代次数次数基基C CB Bx x1 1

4、x x2 2x x3 3x x4 4x x5 5b b比值比值2 21 10 00 00 00 0 x x3 30 00 05 51 10 00 01515- -x x4 40 06 62 20 01 10 0242424/624/6x x5 50 01 11 10 00 01 15 55 5z zj j0 00 00 00 00 0Z=0Z=0 j j= = c cj j - -z zj j2 21 10 00 00 0050240150352413bcbcbcz第五章 单纯形法n5.1 单纯形法的基本思路和原理单纯形法的基本思路和原理n5.2 单纯形法的表格形式单纯形法的表格形式n第第1

5、1步步: :求初始基可行解求初始基可行解, ,列出初始单纯形表。列出初始单纯形表。n第第2 2步步: :最优性检验最优性检验n第第2步步:最优性检验最优性检验5.2单纯形法的表格形式最优解判别定理最优解判别定理 对于求最大目标函数的问题中，对于某对于求最大目标函数的问题中，对于某个基本可行解，如果所有检验数个基本可行解，如果所有检验数 j j 0 0，则，则这个基可行解是最优解。这个基可行解是最优解。5.2单纯形法的表格形式迭代迭代次数次数基基C CB Bx x1 1x x2 2x x3 3x x4 4x x5 5b b比值比值2 21 10 00 00 00 0 x x3 30 00 05

6、51 10 00 01515- -x x4 40 06 62 20 01 10 0242424/624/6x x5 50 01 11 10 00 01 15 55 5z zj j0 00 00 00 00 0Z=0Z=0 j j= = c cj j - -z zj j2 21 10 00 00 0n第第2步步:最优性检验最优性检验5.2单纯形法的表格形式如果表中所有检验数如果表中所有检验数 j j 0 0，且基变量中不含有，且基变量中不含有人工变量时，表中的基可行解，即为最优解人工变量时，表中的基可行解，即为最优解, ,计计算结束。算结束。当表中存在当表中存在 j j0 0，如果有，如果有P

7、Pj j 0 0则问题为无界则问题为无界解，解，计算结束计算结束；否则转入下一步。否则转入下一步。5.2单纯形法的表格形式迭代迭代次数次数基基C CB Bx x1 1x x2 2x x3 3x x4 4x x5 5b b比值比值2 21 10 00 00 00 0 x x3 30 00 05 51 10 00 01515- -x x4 40 06 62 20 01 10 0242424/624/6x x5 50 01 11 10 00 01 15 55 5z zj j0 00 00 00 00 0Z=0Z=0 j j= = c cj j - -z zj j2 21 10 00 00 0第五章

8、单纯形法n5.1 单纯形法的基本思路和原理单纯形法的基本思路和原理n5.2 单纯形法的表格形式单纯形法的表格形式n第第1 1步步: :求初始基可行解求初始基可行解, ,列出初始单纯形表。列出初始单纯形表。n第第2 2步步: :最优性检验最优性检验n第第3 3步步: :从一个基可行解转换到相邻的目标函数更大从一个基可行解转换到相邻的目标函数更大的基可行解，列出新的单纯形表的基可行解，列出新的单纯形表( (简称简称 迭代迭代 ) )。n第第3步步:迭代迭代。n1.确定入基变量确定入基变量5.2单纯形法的表格形式由最优判别定理可知，当某个由最优判别定理可知，当某个 j j 00时，非基时，非基变量变

9、量 x xj j 变为基变量变为基变量, ,不取零值可以使目标函数不取零值可以使目标函数值增大。故值增大。故要选基检验数大于要选基检验数大于0的非基变量换到的非基变量换到基变量中去。基变量中去。若有两个以上的若有两个以上的j 0，则为了使目标函数增则为了使目标函数增加得更大些，一般选其中的加得更大些，一般选其中的j 最大者的非基变最大者的非基变量为入基变量量为入基变量. .5.2单纯形法的表格形式迭代迭代次数次数基基C CB Bx x1 1x x2 2x x3 3x x4 4x x5 5b b比值比值2 21 10 00 00 00 0 x x3 30 00 05 51 10 00 01515

10、- -x x4 40 06 62 20 01 10 0242424/624/6x x5 50 01 11 10 00 01 15 55 5z zj j0 00 00 00 00 0Z=0Z=0 j j= = c cj j - -z zj j2 21 10 00 00 0n第第3步步:迭代迭代。n1.确定入基变量确定入基变量n2.确定出基变量确定出基变量5.2单纯形法的表格形式把已确定的入基变量在各约束方程中的把已确定的入基变量在各约束方程中的正的系正的系数数除以其所在约束方程中的常数项的值，除以其所在约束方程中的常数项的值，把其中最小比值所在的约束方程中的原基变量把其中最小比值所在的约束方程中

11、的原基变量确定为出基变量。确定为出基变量。这样在下一步迭代的矩阵变换中可以确保新得这样在下一步迭代的矩阵变换中可以确保新得到的到的 b bj j 值都大于等于零。值都大于等于零。5.2单纯形法的表格形式迭代迭代次数次数基基C CB Bx x1 1x x2 2x x3 3x x4 4x x5 5b b比值比值2 21 10 00 00 00 0 x x3 30 00 05 51 10 00 01515- -x x4 40 06 62 20 01 10 0242424/624/6x x5 50 01 11 10 00 01 15 55 5z zj j0 00 00 00 00 0Z=0Z=0 j

12、j= = c cj j - -z zj j2 21 10 00 00 0元数元数a a2121决定了从一个基可行解到相邻基可行解决定了从一个基可行解到相邻基可行解的转移去向，取名的转移去向，取名主元主元n第第3步步:迭代迭代。n1.确定入基变量确定入基变量n2.确定出基变量确定出基变量n3.用入基变量替换出基变量，得到一个新的基；用入基变量替换出基变量，得到一个新的基； 对应这个基可以找到一个新的基可行解；对应这个基可以找到一个新的基可行解； 并画出一个新的单纯形表。并画出一个新的单纯形表。5.2单纯形法的表格形式5.2单纯形法的表格形式52415100010001125160bPPPPP54

13、321524150054321xxxxx5.2单纯形法的表格形式52415100010001125160bPPPPP54321541510000001151106/131/bPPPPP543211415100000150106/16/13/231/bPPPPP5432110150454321xxxxx62r23rrn第第3步步:迭代迭代。n3.用入基变量替换出基变量，得到一个新的基；用入基变量替换出基变量，得到一个新的基； 对应这个基可以找到一个新的基可行解；对应这个基可以找到一个新的基可行解； 并画出一个新的单纯形表。并画出一个新的单纯形表。5.2单纯形法的表格形式新表中的基仍应是单位矩阵，

14、为此在表中做新表中的基仍应是单位矩阵，为此在表中做行的初等变换行的初等变换设主元为设主元为a alklk 将主元所在第将主元所在第i i行的数字除以主元行的数字除以主元a alklk ； 将计算得到的第将计算得到的第i i行的数字乘上（行的数字乘上（- - a aikik ），加到第），加到第i i行行数字上数字上a.a. 重新计算各变量的检验系数重新计算各变量的检验系数迭代迭代次数次数基基C CB Bx x1 1x x2 2x x3 3x x4 4x x5 5b b比值比值2 21 10 00 00 00 0 x x3 30 00 05 51 10 00 01515- -x x4 40 06

15、 62 20 01 10 0242424/624/6x x5 50 01 11 10 00 01 15 55 5z zj j0 00 00 00 00 0Z=0Z=0 j j= = c cj j - -z zj j2 21 10 00 00 0迭代迭代次数次数基基C CB Bx x1 1x x2 2x x3 3x x4 4x x5 5b b比值比值2 21 10 00 00 01 1x x3 30 00 05 51 10 00 015153 3x x1 12 21 11/31/30 01/61/60 04 41212x x5 50 00 02/32/30 0-1/6-1/61 11 13/23

16、/2z zj j2 22/32/30 01/31/30 0Z=8Z=8 j j= = c cj j - -z zj j0 01/31/30 0-1/3-1/30 0新表中的基仍应是单位矩阵，为此在表中做新表中的基仍应是单位矩阵，为此在表中做行的初行的初等变换等变换设主元为设主元为a alklk 将主元所在第将主元所在第i i行的数字除以主元行的数字除以主元a alklk ；迭代迭代次数次数基基C CB Bx x1 1x x2 2x x3 3x x4 4x x5 5b b比值比值2 21 10 00 00 00 0 x x3 30 00 05 51 10 00 01515- -x x4 40 0

17、6 62 20 01 10 0242424/624/6x x5 50 01 11 10 00 01 15 55 5z zj j0 00 00 00 00 0Z=0Z=0 j j= = c cj j - -z zj j2 21 10 00 00 0迭代迭代次数次数基基C CB Bx x1 1x x2 2x x3 3x x4 4x x5 5b b比值比值2 21 10 00 00 01 1x x3 30 00 05 51 10 00 015153 3x x1 12 21 11/31/30 01/61/60 04 41212x x5 50 00 02/32/30 0-1/6-1/61 11 13/2

18、3/2z zj j2 22/32/30 01/31/30 0Z=8Z=8 j j= = c cj j - -z zj j0 01/31/30 0-1/3-1/30 0新表中的基仍应是单位矩阵，为此在表中做新表中的基仍应是单位矩阵，为此在表中做行的初行的初等变换等变换设主元为设主元为a alklk 将主元所在第将主元所在第i i行的数字除以主元行的数字除以主元a alklk ； 将计算得到的第将计算得到的第i i行的数字乘上（行的数字乘上（- a- aikik ），加），加到第到第i i行数字上行数字上迭代迭代次数次数基基C CB Bx x1 1x x2 2x x3 3x x4 4x x5 5b

19、 b比值比值2 21 10 00 00 00 0 x x3 30 00 05 51 10 00 01515- -x x4 40 06 62 20 01 10 0242424/624/6x x5 50 01 11 10 00 01 15 55 5z zj j0 00 00 00 00 0Z=0Z=0 j j= = c cj j - -z zj j2 21 10 00 00 0迭代迭代次数次数基基C CB Bx x1 1x x2 2x x3 3x x4 4x x5 5b b比值比值2 21 10 00 00 01 1x x3 30 00 05 51 10 00 015153 3x x1 12 21

20、 11/31/30 01/61/60 04 41212x x5 50 00 02/32/30 0-1/6-1/61 11 13/23/2z zj j2 22/32/30 01/31/30 0Z=8Z=8 j j= = c cj j - -z zj j0 01/31/30 0-1/3-1/30 0n第第3步步:迭代迭代。n1.确定入基变量确定入基变量n2.确定出基变量确定出基变量n3.用入基变量替换出基变量，得到一个新的基；用入基变量替换出基变量，得到一个新的基； 对应这个基可以找到一个新的基可行解；对应这个基可以找到一个新的基可行解； 并画出一个新的单纯形表。并画出一个新的单纯形表。5.2单纯

21、形法的表格形式第五章 单纯形法n5.1 单纯形法的基本思路和原理单纯形法的基本思路和原理n5.2 单纯形法的表格形式单纯形法的表格形式n第第1 1步步: :求初始基可行解求初始基可行解, ,列出初始单纯形表。列出初始单纯形表。n第第2 2步步: :最优性检验最优性检验n第第3 3步步: :从一个基可行解转换到相邻的目标函数更大从一个基可行解转换到相邻的目标函数更大的基可行解，列出新的单纯形表的基可行解，列出新的单纯形表( (简称简称 迭代迭代 ) )。n第第4 4步：重复步：重复2 2，3 3两步直到计算结束为止两步直到计算结束为止迭代迭代次数次数基基C CB Bx x1 1x x2 2x x

22、3 3x x4 4x x5 5b b比值比值2 21 10 00 00 00 0 x x3 30 00 05 51 10 00 01515- -x x4 40 06 62 20 01 10 0242424/624/6x x5 50 01 11 10 00 01 15 55 5z zj j0 00 00 00 00 0Z=0Z=0 j j= = c cj j - -z zj j2 21 10 00 00 0迭代迭代次数次数基基C CB Bx x1 1x x2 2x x3 3x x4 4x x5 5b b比值比值2 21 10 00 00 01 1x x3 30 00 05 51 10 00 01

23、5153 3x x1 12 21 11/31/30 01/61/60 04 41212x x5 50 00 02/32/30 0-1/6-1/61 11 13/23/2z zj j2 22/32/30 01/31/30 0Z=8Z=8 j j= = c cj j - -z zj j0 01/31/30 0-1/3-1/30 0n第第2步步:最优性检验最优性检验5.2单纯形法的表格形式如果表中所有检验数如果表中所有检验数 j j 0 0，且基变量中不含有，且基变量中不含有人工变量时，表中的基可行解，即为最优解人工变量时，表中的基可行解，即为最优解, ,计计算结束。算结束。当表中存在当表中存在 j

24、 j0 0，如果有，如果有P Pj j 0 0则问题为无界则问题为无界解，解，计算结束计算结束；否则转入下一步。否则转入下一步。n第第3步步:迭代迭代。n1.确定入基变量确定入基变量n2.确定出基变量确定出基变量n3.用入基变量替换出基变量，得到一个新的基；用入基变量替换出基变量，得到一个新的基； 对应这个基可以找到一个新的基可行解；对应这个基可以找到一个新的基可行解； 并画出一个新的单纯形表。并画出一个新的单纯形表。5.2单纯形法的表格形式迭代迭代次数次数基基C CB Bx x1 1x x2 2x x3 3x x4 4x x5 5b b比值比值2 21 10 00 00 00 0 x x3

25、30 00 05 51 10 00 01515- -x x4 40 06 62 20 01 10 0242424/624/6x x5 50 01 11 10 00 01 15 55 5z zj j0 00 00 00 00 0Z=0Z=0 j j= = c cj j - -z zj j2 21 10 00 00 0迭代迭代次数次数基基C CB Bx x1 1x x2 2x x3 3x x4 4x x5 5b b比值比值2 21 10 00 00 01 1x x3 30 00 05 51 10 00 015153 3x x1 12 21 11/31/30 01/61/60 04 41212x x

26、5 50 00 02/32/30 0-1/6-1/61 11 13/23/2z zj j2 22/32/30 01/31/30 0Z=8Z=8 j j= = c cj j - -z zj j0 01/31/30 0-1/3-1/30 0迭代迭代次数次数基基C CB Bx x1 1x x2 2x x3 3x x4 4x x5 5b b比值比值2 21 10 00 00 01 1x x3 30 00 05 51 10 00 015153 3x x1 12 21 11/31/30 01/61/60 04 41212x x5 50 00 02/32/30 0-1/6-1/61 11 13/23/2z

27、zj j2 22/32/30 01/31/30 0Z=8Z=8 j j= = c cj j - -z zj j0 01/31/30 0-1/3-1/30 0n第第3步步:迭代迭代。n1.确定入基变量确定入基变量n2.确定出基变量确定出基变量n3.用入基变量替换出基变量，得到一个新的基；用入基变量替换出基变量，得到一个新的基； 对应这个基可以找到一个新的基可行解；对应这个基可以找到一个新的基可行解； 并画出一个新的单纯形表。并画出一个新的单纯形表。5.2单纯形法的表格形式迭代迭代次数次数基基C CB Bx x1 1x x2 2x x3 3x x4 4x x5 5b b比值比值2 21 10 00

28、 00 01 1x x3 30 00 05 51 10 00 015153 3x x1 12 21 11/31/30 01/61/60 04 41212x x5 50 00 02/32/30 0-1/6-1/61 11 13/23/2z zj j2 22/32/30 01/31/30 0Z=8Z=8 j j= = c cj j - -z zj j0 01/31/30 0-1/3-1/30 0迭代迭代次数次数基基C CB Bx x1 1x x2 2x x3 3x x4 4x x5 5b b比值比值2 21 10 00 00 01 1x x3 30 00 05 51 10 00 015153 3x

29、 x1 12 21 11/31/30 01/61/60 04 41212x x5 50 00 02/32/30 0-1/6-1/61 11 13/23/2z zj j2 22/32/30 01/31/30 0Z=8Z=8 j j= = c cj j - -z zj j0 01/31/30 0-1/3-1/30 0迭代迭代次数次数基基C CB Bx x1 1x x2 2x x3 3x x4 4x x5 5b b比值比值2 21 10 00 00 01 1x x3 30 00 05 51 10 00 015153 3x x1 12 21 11/31/30 01/61/60 04 41212x x5

30、 50 00 02/32/30 0-1/6-1/61 11 13/23/2z zj j2 22/32/30 01/31/30 0Z=8Z=8 j j= = c cj j - -z zj j0 01/31/30 0-1/3-1/30 0迭代迭代次数次数基基C CB Bx x1 1x x2 2x x3 3x x4 4x x5 5b b比值比值2 21 10 00 00 02 2x x3 30 00 00 01 15/45/4-15/2-15/215/215/2x x1 12 21 10 00 01/41/4-1/2-1/27/27/2x x2 21 10 01 10 0-1/4-1/43/23/2

31、3/23/2z zj j2 20 00 01/41/41/21/2Z=Z=17/217/2 j j= = c cj j - -z zj j0 00 00 0-1/4-1/4-1/2-1/2迭代迭代次数次数基基C CB Bx x1 1x x2 2x x3 3x x4 4x x5 5b b比值比值2 21 10 00 00 02 2x x3 30 00 00 01 15/45/4-15/2-15/215/215/2x x1 12 21 10 00 01/41/4-1/2-1/27/27/2x x2 21 10 01 10 0-1/4-1/43/23/23/23/2z zj j2 20 00 01/

32、41/41/21/2Z=Z=17/217/2 j j= = c cj j - -z zj j0 00 00 0-1/4-1/4-1/2-1/25.2单纯形法的表格形式表中所有检验数表中所有检验数 j j 0 0，且基变量中不含有人工变，且基变量中不含有人工变量时，表中的基可行解，即为最优解量时，表中的基可行解，即为最优解, ,计算结束。计算结束。TX0 , 0 ,215,23,27217Z基基C CB Bx x1 1x x2 2x x3 3x x4 4x x5 5b b2 21 10 00 00 0 x x3 30 00 05 51 10 00 01515x x4 40 06 62 20 01

33、 10 02424x x5 50 01 11 10 00 01 15 5 j j= = c cj j - -z zj j2 21 10 00 00 0 x x3 30 00 05 51 10 00 01515x x1 12 21 11/31/30 01/61/60 04 4x x5 50 00 02/32/30 0-1/6-1/61 11 1 j j= = c cj j - -z zj j0 01/31/30 0-1/3-1/30 0 x x3 30 00 00 01 15/45/4-15/2-15/215/215/2x x1 12 21 10 00 01/41/4-1/2-1/27/27/2

34、x x2 21 10 01 10 0-1/4-1/43/23/23/23/2 j j= = c cj j - -z zj j0 00 00 0-1/4-1/4-1/2-1/20,.250,4002,300.00010050max321213222112132121sssxxsxsxxsxxsssxx基基C CB Bx x1 1x x2 2s s1 1s s2 2s s3 3b b50501001000 00 00 01 11 11 10 00 03003002 21 10 01 10 04004000 01 10 00 01 1250250 j j= = c cj j - -z zj j0,.

35、250,4002,300.00010050max321213222112132121sssxxsxsxxsxxsssxx基基C CB Bx x1 1x x2 2s s1 1s s2 2s s3 3b b50501001000 00 00 0s s1 10 01 11 11 10 00 0300300s s2 20 02 21 10 01 10 0400400s s3 30 00 01 10 00 01 1250250 j j= = c cj j - -z zj j0,.250,4002,300.00010050max321213222112132121sssxxsxsxxsxxsssxx基基C

36、 CB Bx x1 1x x2 2s s1 1s s2 2s s3 3b b50501001000 00 00 0s s1 10 01 11 11 10 00 0300300s s2 20 02 21 10 01 10 0400400s s3 30 00 01 10 00 01 1250250 j j= = c cj j - -z zj j50501001000 00 00 0基基C CB Bx x1 1x x2 2s s1 1s s2 2s s3 3b b50501001000 00 00 0s s1 10 01 11 11 10 00 0300300s s2 20 02 21 10 01

37、10 0400400s s3 30 00 01 10 00 01 1250250 j j= = c cj j - -z zj j50501001000 00 00 0 j j= = c cj j - -z zj j基基C CB Bx x1 1x x2 2s s1 1s s2 2s s3 3b b50501001000 00 00 0s s1 10 01 11 11 10 00 0300300s s2 20 02 21 10 01 10 0400400s s3 30 00 01 10 00 01 1250250 j j= = c cj j - -z zj j50501001000 00 00 0

38、s s1 10 0s s2 20 0 x x2 2100100 j j= = c cj j - -z zj j基基C CB Bx x1 1x x2 2s s1 1s s2 2s s3 3b b50501001000 00 00 0s s1 10 01 11 11 10 00 0300300s s2 20 02 21 10 01 10 0400400s s3 30 00 01 10 00 01 1250250 j j= = c cj j - -z zj j50501001000 00 00 0s s1 10 0s s2 20 0 x x2 21001000 01 10 00 01 1250250

39、 j j= = c cj j - -z zj j基基C CB Bx x1 1x x2 2s s1 1s s2 2s s3 3b b50501001000 00 00 0s s1 10 01 11 11 10 00 0300300s s2 20 02 21 10 01 10 0400400s s3 30 00 01 10 00 01 1250250 j j= = c cj j - -z zj j50501001000 00 00 0s s1 10 01 10 01 10 0-1-15050s s2 20 02 20 00 01 1-1-1150150 x x2 21001000 01 10 00

40、 01 1250250 j j= = c cj j - -z zj j基基C CB Bx x1 1x x2 2s s1 1s s2 2s s3 3b b50501001000 00 00 0s s1 10 01 11 11 10 00 0300300s s2 20 02 21 10 01 10 0400400s s3 30 00 01 10 00 01 1250250 j j= = c cj j - -z zj j50501001000 00 00 0s s1 10 01 10 01 10 0-1-15050s s2 20 02 20 00 01 1-1-1150150 x x2 210010

41、00 01 10 00 01 1250250 j j= = c cj j - -z zj j50500 00 00 0-100-100基基C CB Bx x1 1x x2 2s s1 1s s2 2s s3 3b b50501001000 00 00 0s s1 10 01 11 11 10 00 0300300s s2 20 02 21 10 01 10 0400400s s3 30 00 01 10 00 01 1250250 j j= = c cj j - -z zj j50501001000 00 00 0s s1 10 01 10 01 10 0-1-15050s s2 20 02

42、20 00 01 1-1-1150150 x x2 21001000 01 10 00 01 1250250 j j= = c cj j - -z zj j50500 00 00 0-100-100基基C CB Bx x1 1x x2 2s s1 1s s2 2s s3 3b b50501001000 00 00 0s s1 10 01 11 11 10 00 0300300s s2 20 02 21 10 01 10 0400400s s3 30 00 01 10 00 01 1250250 j j= = c cj j - -z zj j50501001000 00 00 0s s1 10

43、01 10 01 10 0-1-15050s s2 20 02 20 00 01 1-1-1150150 x x2 21001000 01 10 00 01 1250250 j j= = c cj j - -z zj j50500 00 00 0-100-100 j j= = c cj j - -z zj j基基C CB Bx x1 1x x2 2s s1 1s s2 2s s3 3b b50501001000 00 00 0s s1 10 01 11 11 10 00 0300300s s2 20 02 21 10 01 10 0400400s s3 30 00 01 10 00 01 12

44、50250 j j= = c cj j - -z zj j50501001000 00 00 0s s1 10 01 10 01 10 0-1-15050s s2 20 02 20 00 01 1-1-1150150 x x2 21001000 01 10 00 01 1250250 j j= = c cj j - -z zj j50500 00 00 0-100-100 x x1 15050s s2 20 0 x x2 2100100 j j= = c cj j - -z zj j基基C CB Bx x1 1x x2 2s s1 1s s2 2s s3 3b b50501001000 00

45、00 0s s1 10 01 11 11 10 00 0300300s s2 20 02 21 10 01 10 0400400s s3 30 00 01 10 00 01 1250250 j j= = c cj j - -z zj j50501001000 00 00 0s s1 10 01 10 01 10 0-1-15050s s2 20 02 20 00 01 1-1-1150150 x x2 21001000 01 10 00 01 1250250 j j= = c cj j - -z zj j50500 00 00 0-100-100 x x1 150501 10 01 10 0-

46、1-15050s s2 20 00 00 0-2-21 11 15050 x x2 21001000 01 10 00 01 1250250 j j= = c cj j - -z zj j基基C CB Bx x1 1x x2 2s s1 1s s2 2s s3 3b b50501001000 00 00 0s s1 10 01 11 11 10 00 0300300s s2 20 02 21 10 01 10 0400400s s3 30 00 01 10 00 01 1250250 j j= = c cj j - -z zj j50501001000 00 00 0s s1 10 01 10

47、 01 10 0-1-15050s s2 20 02 20 00 01 1-1-1150150 x x2 21001000 01 10 00 01 1250250 j j= = c cj j - -z zj j50500 00 00 0-100-100 x x1 150501 10 01 10 0-1-15050s s2 20 00 00 0-2-21 11 15050 x x2 21001000 01 10 00 01 1250250 j j= = c cj j - -z zj j00-500-50基基C CB Bx x1 1x x2 2s s1 1s s2 2s s3 3b b505010

48、01000 00 00 0 x x1 150501 10 01 10 0-1-15050s s2 20 00 00 0-2-21 11 15050 x x2 21001000 01 10 00 01 1250250 j j= = c cj j - -z zj j00-500-505.2单纯形法的表格形式表中所有检验数表中所有检验数 j j 0 0，且基变量中不含有人工变，且基变量中不含有人工变量时，表中的基可行解，即为最优解量时，表中的基可行解，即为最优解, ,计算结束。计算结束。TX0 ,50, 0 ,250,50275002501005005050Z第五章 单纯形法n5.1 单纯形法的基本

49、思路和原理单纯形法的基本思路和原理n5.2 单纯形法的表格形式单纯形法的表格形式n5.3 单纯形法的进一步讨论单纯形法的进一步讨论n一、人工变量法一、人工变量法5.3 单纯形法的进一步讨论一、人工变量法一、人工变量法 在上述线性规划问题中，化为标准形式后在上述线性规划问题中，化为标准形式后约束条件的系数矩阵中含有单位矩阵，以此作约束条件的系数矩阵中含有单位矩阵，以此作初始基，使得求初始解和建立初始单纯形表都初始基，使得求初始解和建立初始单纯形表都十分方便。十分方便。 但是如果在化为标准形后，约束条件的系但是如果在化为标准形后，约束条件的系数矩阵中不存在单位矩阵怎么办？数矩阵中不存在单位矩阵怎么

50、办？5.3 单纯形法的进一步讨论一、人工变量法一、人工变量法例：例：0,6002,125,350.32min212112121xxxxxxxxxf0,.6002,125,3503212132121121sssxxsxxsxsxx.32max21xxz5.3 单纯形法的进一步讨论一、人工变量法一、人工变量法例：例：0,.6002,125,3503212132121121sssxxsxxsxsxx.32max21xxz600125350100010001101211bPPPPP543210,.6002,125,3503212132121121sssxxsxxsxsxx600125350100010