单纯形法2表格形式

《单纯形法2表格形式》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章单纯形法SinglexMethod第五章单纯形法5.1单纯形法的基本思路和原理5.2单纯形法的表格形式从可行域中某一个顶点开始，判断此顶点是否是最优解，如不是则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。第五章单纯形法5.1单纯形法的基本思路和原理5.2单纯形法的表格形式一、找出一个初始基本可行解(单位矩阵)二、最优性检验(检验数j)三、基变换(换入变量与换出变量

2、)第五章单纯形法5.1单纯形法的基本思路和原理5.2单纯形法的表格形式第1步:求初始基可行解,列出初始单纯形表。第五章单纯形法5.1单纯形法的基本思路和原理5.2单纯形法的表格形式第1步:求初始基可行解,列出初始单纯形表。第1步:求初始基可行解,列出初始单纯形表。例§5.2单纯形法的表格形式§5.2单纯形法的表格形式第1步:求初始基可行解,列出初始单纯形表。例P3,P4,P5是单位矩阵,构成一个基,对应变量x3,x4,x5是基变量.令非基变量x1,x2等于零,即找到一个初始基可行解§5.2单纯形

3、法的表格形式迭代次数基CBx1x2x3x4x5b比值210000x300510015-x40620102424/6x501100155zj00000Z=0j=cj-zj21000§5.2单纯形法的表格形式迭代次数基CBx1x2x3x4x5b比值210000x300510015-x40620102424/6x501100155zj00000Z=0j=cj-zj21000?§5.2单纯形法的表格形式迭代次数基CBx1x2x3x4x5b比值210000x300510015-x40620102424

4、/6x501100155zj00000Z=0j=cj-zj21000§5.2单纯形法的表格形式迭代次数基CBx1x2x3x4x5b比值210000x300510015-x40620102424/6x501100155zj00000Z=0j=cj-zj21000第五章单纯形法5.1单纯形法的基本思路和原理5.2单纯形法的表格形式第1步:求初始基可行解,列出初始单纯形表。第2步:最优性检验第2步:最优性检验§5.2单纯形法的表格形式最优解判别定理对于求最大目标函数的问题中，对于某个基本可行解，如

5、果所有检验数j0，则这个基可行解是最优解。§5.2单纯形法的表格形式迭代次数基CBx1x2x3x4x5b比值210000x300510015-x40620102424/6x501100155zj00000Z=0j=cj-zj21000第2步:最优性检验§5.2单纯形法的表格形式如果表中所有检验数j0，且基变量中不含有人工变量时，表中的基可行解，即为最优解,计算结束。当表中存在j＞0，如果有Pj0则问题为无界解，计算结束；否则转入下一步。§5.2单纯形法的表格形式迭代次数基CBx1x

6、2x3x4x5b比值210000x300510015-x40620102424/6x501100155zj00000Z=0j=cj-zj21000第五章单纯形法5.1单纯形法的基本思路和原理5.2单纯形法的表格形式第1步:求初始基可行解,列出初始单纯形表。第2步:最优性检验第3步:从一个基可行解转换到相邻的目标函数更大的基可行解，列出新的单纯形表(简称迭代)。第3步:迭代。1.确定入基变量§5.2单纯形法的表格形式由最优判别定理可知，当某个j>0时，非基变量xj变为基变量,不取零值可以使目标

7、函数值增大。故要选基检验数大于0的非基变量换到基变量中去。若有两个以上的j>0，则为了使目标函数增加得更大些，一般选其中的j最大者的非基变量为入基变量.§5.2单纯形法的表格形式迭代次数基CBx1x2x3x4x5b比值210000x300510015-x40620102424/6x501100155zj00000Z=0j=cj-zj21000第3步:迭代。1.确定入基变量2.确定出基变量§5.2单纯形法的表格形式把已确定的入基变量在各约束方程中的正的系数除以其所在约束方程中的常数项的值，把

8、其中最小比值所在的约束方程中的原基变量确定为出基变量。这样在下一步迭代的矩阵变换中可以确保新得到的bj值都大于等于零。§5.2单纯形法的表格形式迭代次数基CBx1x2x3x4x5b比值210000x300510015-x40620102424/6x501100155zj00000Z=0j=cj-zj21000元数a21决定了从一个基可行解到相邻基可行解的转移去向，取名主元第3步:迭代。1.确定入基变量2.确定出基变量3.用入基变量替换出基变量，得到一个新的基；对应这个基可以找到一个新的基可行解