第五章-单纯形法(2表格形式)课件

第五章 单纯形法Singlex Method第五章 单纯形法n5.1 单纯形法的基本思路和原理单纯形法的基本思路和原理n5.2 单纯形法的表格形式单纯形法的表格形式n从可行域中某一个顶点开始，判断此顶点是否是最从可行域中某一个顶点开始，判断此顶点是否是最优解，优解，n如不是则再找另一个使得其目标函数值更优的顶点，如不是则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。称之为迭代，再判断此点是否是最优解。n直到找到一个顶点为其最优解，就是使得其目标函直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优数值最优的解，或者能判断出线性规划问题无最优解为止。解为止。第五章 单纯形法n5.1 单纯形法的基本思路和原理单纯形法的基本思路和原理n5.2 单纯形法的表格形式单纯形法的表格形式n一、找出一个初始基本可行解一、找出一个初始基本可行解(单位矩阵单位矩阵)n二、最优性检验二、最优性检验(检验数检验数 j j)n三、基变换三、基变换(换入变量与换出变量换入变量与换出变量)第五章 单纯形法n5.1 单纯形法的基本思路和原理单纯形法的基本思路和原理n5.2 单纯形法的表格形式单纯形法的表格形式n第第1 1步步:求初始基可行解求初始基可行解,列出初始单纯形表。列出初始单纯形表。第五章 单纯形法n5.1 单纯形法的基本思路和原理单纯形法的基本思路和原理n5.2 单纯形法的表格形式单纯形法的表格形式n第第1 1步步:求初始基可行解求初始基可行解,列出初始单纯形表。列出初始单纯形表。n第第1步步:求初始基可行解求初始基可行解,列出初始单纯形表。列出初始单纯形表。例例5.2单纯形法的表格形式5.2单纯形法的表格形式n第第1步步:求初始基可行解求初始基可行解,列出初始单纯形表。列出初始单纯形表。例例P P3 3,P,P4 4,P,P5 5 是单位矩阵是单位矩阵,构成一个基构成一个基,对应变量对应变量x x3 3,x,x4 4,x,x5 5是基变量是基变量.令非基变量令非基变量x x1 1,x,x2 2等于零等于零,即找到一个初始基可行解即找到一个初始基可行解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 05.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?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 05.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第五章 单纯形法n5.1 单纯形法的基本思路和原理单纯形法的基本思路和原理n5.2 单纯形法的表格形式单纯形法的表格形式n第第1 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 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 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第五章 单纯形法n5.1 单纯形法的基本思路和原理单纯形法的基本思路和原理n5.2 单纯形法的表格形式单纯形法的表格形式n第第1 1步步:求初始基可行解求初始基可行解,列出初始单纯形表。列出初始单纯形表。n第第2 2步步:最优性检验最优性检验n第第3 3步步:从一个基可行解转换到相邻的目标函数更大从一个基可行解转换到相邻的目标函数更大的基可行解，列出新的单纯形表的基可行解，列出新的单纯形表(简称简称 迭代迭代 )。n第第3步步:迭代迭代。n1.确定入基变量确定入基变量5.2单纯形法的表格形式由最优判别定理可知，当某个由最优判别定理可知，当某个 j j 00时，非基时，非基变量变量 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-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单纯形法的表格形式把已确定的入基变量在各约束方程中的把已确定的入基变量在各约束方程中的正的系正的系数数除以其所在约束方程中的常数项的值，除以其所在约束方程中的常数项的值，把其中最小比值所在的约束方程中的原基变量把其中最小比值所在的约束方程中的原基变量确定为出基变量。确定为出基变量。这样在下一步迭代的矩阵变换中可以确保新得这样在下一步迭代的矩阵变换中可以确保新得到的到的 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 j=c cj j-z zj j2 21 10 00 00 0元数元数a a2121决定了从一个基可行解到相邻基可行解决定了从一个基可行解到相邻基可行解的转移去向，取名的转移去向，取名主元主元n第第3步步:迭代迭代。n1.确定入基变量确定入基变量n2.确定出基变量确定出基变量n3.用入基变量替换出基变量，得到一个新的基；用入基变量替换出基变量，得到一个新的基；对应这个基可以找到一个新的基可行解；对应这个基可以找到一个新的基可行解；并画出一个新的单纯形表。并画出一个新的单纯形表。5.2单纯形法的表格形式5.2单纯形法的表格形式5.2单纯形法的表格形式n第第3步步:迭代迭代。n3.用入基变量替换出基变量，得到一个新的基；用入基变量替换出基变量，得到一个新的基；对应这个基可以找到一个新的基可行解；对应这个基可以找到一个新的基可行解；并画出一个新的单纯形表。并画出一个新的单纯形表。5.2单纯形法的表格形式新表中的基仍应是单位矩阵，为此在表中做新表中的基仍应是单位矩阵，为此在表中做行的初等变换行的初等变换设主元为设主元为a alklka.a.将主元所在第将主元所在第i i行的数字除以主元行的数字除以主元a alklk；b.b.将计算得到的第将计算得到的第i i行的数字乘上（行的数字乘上（-a aikik），加到第），加到第i i行行数字上数字上c.c.重新计算各变量的检验系数重新计算各变量的检验系数迭代迭代次数次数基基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迭代迭代次数次数基基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 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 alklka.a.将主元所在第将主元所在第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 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 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新表中的基仍应是单位矩阵，为此在表中做新表中的基仍应是单位矩阵，为此在表中做行的初行的初等变换等变换设主元为设主元为a alklka.a.将主元所在第将主元所在第i i行的数字除以主元行的数字除以主元a alklk；b.b.将计算得到的第将计算得到的第i i行的数字乘上（行的数字乘上（-a aikik），加），加到第到第i i行数字上行数字上迭代迭代次数次数基基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迭代迭代次数次数基基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 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单纯形法的表格形式第五章 单纯形法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 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迭代迭代次数次数基基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 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 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 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 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 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单纯形法的表格形式迭代迭代次数次数基基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 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 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 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/23/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/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，且基变量中不含有人工变量，且基变量中不含有人工变量时，表中的基可行解，即为最优解时，表中的基可行解，即为最优解,计算结束。计算结束。基基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 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/2x 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/2基基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 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 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基基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 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 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 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 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 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 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基基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 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 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 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 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-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 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 b50501001000 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，且基变量中不含有人工变，且基变量中不含有人工变量时，表中的基可行解，即为最优解量时，表中的基可行解，即为最优解,计算结束。计算结束。第五章 单纯形法n5.1 单纯形法的基本思路和原理单纯形法的基本思路和原理n5.2 单纯形法的表格形式单纯形法的表格形式n5.3 单纯形法的进一步讨论单纯形法的进一步讨论n一、人工变量法一、人工变量法5.3 单纯形法的进一步讨论一、人工变量法一、人工变量法 在上述线性规划问题中，化为标准形式后在上述线性规划问题中，化为标准形式后约束条件的系数矩阵中含有单位矩阵，以此作约束条件的系数矩阵中含有单位矩阵，以此作初始基，使得求初始解和建立初始单纯形表都初始基，使得求初始解和建立初始单纯形表都十分方便。十分方便。但是如果在化为标准形后，约束条件的系但是如果在化为标准形后，约束条件的系数矩阵中不存在单位矩阵怎么办？数矩阵中不存在单位矩阵怎么办？5.3 单纯形法的进一步讨论一、人工变量法一、人工变量法例：例：5.3 单纯形法的进一步讨论一、人工变量法一、人工变量法例：例：添加两列单位向量添加两列单位向量P P6 6，P P7 7连同约束条件中的向量连同约束条件中的向量P P5 5，构成单位矩阵，构成单位矩阵添加的添加的P P6 6，P P7 7相当于在上述问题的约束条件中添加相当于在上述问题的约束条件中添加了变量了变量a a1 1，a a2 2，此即为人工变量，此即为人工变量由于约束条件在添加人工变量前已是等式，为使这些由于约束条件在添加人工变量前已是等式，为使这些等式满足，因此在最优解中人工变量取值必须为零。等式满足，因此在最优解中人工变量取值必须为零。为此，令目标函数中人工变量的系数为任意大的负值，为此，令目标函数中人工变量的系数为任意大的负值，用用“-M-M”代表。代表。“-M-M”称为罚因子，即只要人工变量大于零，目标函称为罚因子，即只要人工变量大于零，目标函数就不可能最优数就不可能最优迭迭代代次次数数基变基变量量CBx1x2s1s2s3a1a2b比值比值-2-3000-M-M11-10010350100-100112502100100600zjj=cj-zj迭迭代代次次数数基变基变量量CBx1x2s1s2s3a1a2b比值比值-2-3000-M-Ma1-M11-10010350a2-M100-10011250s302100100600zjj=cj-zj迭迭代代次次数数基变基变量量CBx1x2s1s2s3a1a2b比值比值-2-3000-M-Ma1-M11-10010350a2-M100-10011250s302100100600zj-2M-MMM0-M-Mj=cj-zj迭迭代代次次数数基变基变量量CBx1x2s1s2s3a1a2b比值比值-2-3000-M-Ma1-M11-10010350a2-M100-10011250s302100100600zj-2M-MMM0-M-M-475Mj=cj-zj-2+2M-3+M-M-M000迭迭代代次次数数基变基变量量CBx1x2s1s2s3a1a2b比值比值-2-3000-M-Ma1-M11-10010350350a2-M100-10011251250s302100100600600/2zj-2M-MMM0-M-M-475Mj=cj-zj-2+2M-3+M-M-M000迭迭代代次次数数基变基变量量CBx1x2s1s2s3a1a2b比值比值-2-3000-M-Ma1-M11-10010350350a2-M100-10011251250s302100100600600/2zj-2M-MMM0-M-M-475Mj=cj-zj-2+2M-3+M-M-M000迭迭代代次次数数基变基变量量CBx1x2s1s2s3a1a2b比值比值-2-3000-M-Ma1-M11-10010350350a2-M100-10011251250s302100100600600/2zj-2M-MMM0-M-M-475Mj=cj-zj-2+2M-3+M-M-M0001zj j=cjzj迭迭代代次次数数基变基变量量CBx1x2s1s2s3a1a2b比值比值-2-3000-M-Ma1-M11-10010350350a2-M100-10011251250s302100100600600/2zj-2M-MMM0-M-M-475Mj=cj-zj-2+2M-3+M-M-M0001a1x1s3zj j=cjzj迭迭代代次次数数基变基变量量CBx1x2s1s2s3a1a2b比值比值-2-3000-M-Ma1-M11-10010350350a2-M100-10011251250s302100100600600/2zj-2M-MMM0-M-M-475Mj=cj-zj-2+2M-3+M-M-M0001a1-Mx1-2s30zj j=cjzj迭迭代代次次数数基变基变量量CBx1x2s1s2s3a1a2b比值比值-2-3000-M-Ma1-M11-10010350350a2-M100-10011251250s302100100600600/2zj-2M-MMM0-M-M-475Mj=cj-zj-2+2M-3+M-M-M0001a1-Mx1-2100-1001125s30zj j=cjzj迭迭代代次次数数基变基变量量CBx1x2s1s2s3a1a2b比值比值-2-3000-M-Ma1-M11-10010350350a2-M100-10011251250s302100100600600/2zj-2M-MMM0-M-M-475Mj=cj-zj-2+2M-3+M-M-M0001a1-M01-1101-1225x1-2100-1001125s30010210-2350zj j=cjzj迭迭代代次次数数基变基变量量CBx1x2s1s2s3a1a2b比值比值-2-3000-M-Ma1-M11-10010350350a2-M100-10011251250s302100100600600/2zj-2M-MMM0-M-M-475Mj=cj-zj-2+2M-3+M-M-M0001a1-M01-1101-1225x1-2100-1001125s30010210-2350zj-2-MM-M+20-MM-2 j=cjzj迭迭代代次次数数基变基变量量CBx1x2s1s2s3a1a2b比值比值-2-3000-M-Ma1-M11-10010350350a2-M100-10011251250s302100100600600/2zj-2M-MMM0-M-M-475Mj=cj-zj-2+2M-3+M-M-M0001a1-M01-1101-1225x1-2100-1001125s30010210-2350zj-2-MM-M+20-MM-2 j=cjzj0-3+M-MM-2002-2M迭迭代代次次数数基变基变量量CBx1x2s1s2s3a1a2b比值比值-2-3000-M-Ma1-M11-10010350350a2-M100-10011251250s302100100600600/2zj-2M-MMM0-M-M-475Mj=cj-zj-2+2M-3+M-M-M0001a1-M01-1101-1225x1-2100-1001125s30010210-2350zj-2-MM-M+20-MM-2-225M-250 j=cjzj0-3+M-MM-2002-2M迭迭代代次次数数基变基变量量CBx1x2s1s2s3a1a2b比值比值-2-3000-M-Ma1-M11-10010350350a2-M100-10011251250s302100100600600/2zj-2M-MMM0-M-M-475Mj=cj-zj-2+2M-3+M-M-M0001a1-M01-1101-1225225x1-2100-1001125s30010210-2350350/2zj-2-MM-M+20-MM-2-225M-250 j=cjzj0-3+M-MM-2002-2M2zj j=cj-zj迭迭代代次次数数基变基变量量CBx1x2s1s2s3a1a2b比值比值-2-3000-M-Ma1-M11-10010350350a2-M100-10011251250s302100100600600/2zj-2M-MMM0-M-M-475Mj=cj-zj-2+2M-3+M-M-M0001a1-M01-1101-1225225x1-2100-1001125s30010210-2350350/2zj-2-MM-M+20-MM-2-225M-250 j=cjzj0-3+M-MM-2002-2M2a1x1s2zj j=cj-zj迭迭代代次次数数基变基变量量CBx1x2s1s2s3a1a2b比值比值-2-3000-M-Ma1-M11-10010350350a2-M100-10011251250s302100100600600/2zj-2M-MMM0-M-M-475Mj=cj-zj-2+2M-3+M-M-M0001a1-M01-1101-1225225x1-2100-1001125s30010210-2350350/2zj-2-MM-M+20-MM-2-225M-250 j=cjzj0-3+M-MM-2002-2M2a1-Mx1-2s20zj j=cj-zj迭迭代代次次数数基变基变量量CBx1x2s1s2s3a1a2b比值比值-2-3000-M-Ma1-M11-10010350350a2-M100-10011251250s302100100600600/2zj-2M-MMM0-M-M-475Mj=cj-zj-2+2M-3+M-M-M0001a1-M01-1101-1225225x1-2100-1001125s30010210-2350350/2zj-2-MM-M+20-MM-2-225M-250 j=cjzj0-3+M-MM-2002-2M2a1-Mx1-2s200010-1175zj j=cj-zj迭迭代代次次数数基变基变量量CBx1x2s1s2s3a1a2b比值比值-2-3000-M-Ma1-M11-10010350350a2-M100-10011251250s302100100600600/2zj-2M-MMM0-M-M-475Mj=cj-zj-2+2M-3+M-M-M0001a1-M01-1101-1225225x1-2100-1001125s30010210-2350350/2zj-2-MM-M+20-MM-2-225M-250 j=cjzj0-3+M-MM-2002-2M2a1-M0-10-1/21050 x1-21-0000300s200010-1175zj j=cj-zj迭迭代代次次数数基变基变量量CBx1x2s1s2s3a1a2b比值比值-2-3000-M-Ma1-M11-10010350350a2-M100-10011251250s302100100600600/2zj-2M-MMM0-M-M-475Mj=cj-zj-2+2M-3+M-M-M0001a1-M01-1101-1225225x1-2100-1001125s30010210-2350350/2zj-2-MM-M+20-MM-2-225M-250 j=cjzj0-3+M-MM-2002-2M2a1-M0-10-1/21050 x1-21-0000300s200010-1175zj-2-0.5M-1M00.5M-1-M0 j=cj-zj迭迭代代次次数数基变基变量量CBx1x2s1s2s3a1a2b比值比值-2-3000-M-Ma1-M11-10010350350a2-M100-10011251250s302100100600600/2zj-2M-MMM0-M-M-475Mj=cj-zj-2+2M-3+M-M-M0001a1-M01-1101-1225225x1-2100-1001125s30010210-2350350/2zj-2-MM-M+20-MM-2-225M-250 j=cjzj0-3+M-MM-2002-2M2a1-M0-10-1/21050 x1-21-0000300s200010-1175zj-2-0.5M-1M00.5M-1-M0 j=cj-zj00.5M-2-M0-0.5M-10-M迭迭代代次次数数基变基变量量CBx1x2s1s2s3a1a2b比值比值-2-3000-M-Ma1-M11-10010350350a2-M100-10011251250s302100100600600/2zj-2M-MMM0-M-M-475Mj=cj-zj-2+2M-3+M-M-M0001a1-M01-1101-1225225x1-2100-1001125s30010210-2350350/2zj-2-MM-M+20-MM-2-225M-250 j=cjzj0-3+M-MM-2002-2M2a1-M0-10-1/21050100 x1-21-0000300-s200010-1175350zj-2-0.5M-1M00.5M-1-M0-50M-600 j=cj-zj00.5M-2-M0-0.5M-10-M迭迭代代次次数数基变基变量量CBx1x2s1s2s3a1a2b比值比值-2-3000-M-Ma1-M11-10010350350a2-M100-10011251250s302100100600600/2zj-2M-MMM0-M-M-475Mj=cj-zj-2+2M-3+M-M-M0001a1-M01-1101-1225225x1-2100-1001125s30010210-2350350/2zj-2-MM-M+20-MM-2-225M-250 j=cjzj0-3+M-MM-2002-2M2a1-M0-10-1/21050100 x1-21-0000300-s200010-1175350zj-2-0.5M