单纯形法表格形式

第五章单纯形法SinglexMethod第五章单纯形法5.1单纯形法的基本思路和原理5.2单纯形法的表格形式从可行域中某一个顶点开始，判断此顶点是否是最优解，如不是则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。第五章单纯形法5.1单纯形法的基本思路和原理5.2单纯形法的表格形式一、找出一个初始基本可行解(单位矩阵)二、最优性检验(检验数j)三、基变换(换入变量与换出变量)第五章单纯形法5.1单纯形法的基本思路和原理5.2单纯形法的表格形式第1步:求初始基可行解,列出初始单纯形表。第五章单纯形法5.1单纯形法的基本思路和原理5.2单纯形法的表格形式第1步:求初始基可行解,列出初始单纯形表。第1步:求初始基可行解,列出初始单纯形表。例§5.2单纯形法的表格形式0524261552max212121221,xxxxxxxxxz0,,,,524261550002max543215214213254321xxxxxxxxxxxxxxxxxxz§5.2单纯形法的表格形式第1步:求初始基可行解,列出初始单纯形表。例0,,,,524261550002max543215214213254321xxxxxxxxxxxxxxxxxxz52415100010001125160bPPPPP54321P3,P4,P5是单位矩阵,构成一个基,对应变量x3,x4,x5是基变量.令非基变量x1,x2等于零,即找到一个初始基可行解TX5,24,15,0,0§5.2单纯形法的表格形式0,,,,524261550002max543215214213254321xxxxxxxxxxxxxxxxxxz迭代次数基CBx1x2x3x4x5b比值210000x300510015-x40620102424/6x501100155zj00000Z=0j=cj-zj21000§5.2单纯形法的表格形式迭代次数基CBx1x2x3x4x5b比值210000x300510015-x40620102424/6x501100155zj00000Z=0j=cj-zj21000miijijacz1?01060003152141131acacacz01020503252241232acacacz§5.2单纯形法的表格形式迭代次数基CBx1x2x3x4x5b比值210000x300510015-x40620102424/6x501100155zj00000Z=0j=cj-zj21000050240150352413bcbcbcz§5.2单纯形法的表格形式迭代次数基CBx1x2x3x4x5b比值210000x300510015-x40620102424/6x501100155zj00000Z=0j=cj-zj21000050240150352413bcbcbcz第五章单纯形法5.1单纯形法的基本思路和原理5.2单纯形法的表格形式第1步:求初始基可行解,列出初始单纯形表。第2步:最优性检验第2步:最优性检验§5.2单纯形法的表格形式最优解判别定理对于求最大目标函数的问题中，对于某个基本可行解，如果所有检验数j0，则这个基可行解是最优解。§5.2单纯形法的表格形式迭代次数基CBx1x2x3x4x5b比值210000x300510015-x40620102424/6x501100155zj00000Z=0j=cj-zj21000第2步:最优性检验§5.2单纯形法的表格形式如果表中所有检验数j0，且基变量中不含有人工变量时，表中的基可行解，即为最优解,计算结束。当表中存在j＞0，如果有Pj0则问题为无界解，计算结束；否则转入下一步。§5.2单纯形法的表格形式迭代次数基CBx1x2x3x4x5b比值210000x300510015-x40620102424/6x501100155zj00000Z=0j=cj-zj21000第五章单纯形法5.1单纯形法的基本思路和原理5.2单纯形法的表格形式第1步:求初始基可行解,列出初始单纯形表。第2步:最优性检验第3步:从一个基可行解转换到相邻的目标函数更大的基可行解，列出新的单纯形表(简称迭代)。第3步:迭代。1.确定入基变量§5.2单纯形法的表格形式由最优判别定理可知，当某个j0时，非基变量xj变为基变量,不取零值可以使目标函数值增大。故要选基检验数大于0的非基变量换到基变量中去。若有两个以上的j0，则为了使目标函数增加得更大些，一般选其中的j最大者的非基变量为入基变量.§5.2单纯形法的表格形式迭代次数基CBx1x2x3x4x5b比值210000x300510015-x40620102424/6x501100155zj00000Z=0j=cj-zj21000第3步:迭代。1.确定入基变量2.确定出基变量§5.2单纯形法的表格形式把已确定的入基变量在各约束方程中的正的系数除以其所在约束方程中的常数项的值，把其中最小比值所在的约束方程中的原基变量确定为出基变量。这样在下一步迭代的矩阵变换中可以确保新得到的bj值都大于等于零。§5.2单纯形法的表格形式迭代次数基CBx1x2x3x4x5b比值210000x300510015-x40620102424/6x501100155zj00000Z=0j=cj-zj21000元数a21决定了从一个基可行解到相邻基可行解的转移去向，取名主元第3步:迭代。1.确定入基变量2.确定出基变量3.用入基变量替换出基变量，得到一个新的基；对应这个基可以找到一个新的基可行解；并画出一个新的单纯形表。§5.2单纯形法的表格形式§5.2单纯形法的表格形式52415100010001125160bPPPPP54321524150054321xxxxx§5.2单纯形法的表格形式52415100010001125160bPPPPP54321541510000001151106/131/bPPPPP543211415100000150106/16/13/231/bPPPPP5432110150454321xxxxx62r23rr第3步:迭代。3.用入基变量替换出基变量，得到一个新的基；对应这个基可以找到一个新的基可行解；并画出一个新的单纯形表。§5.2单纯形法的表格形式新表中的基仍应是单位矩阵，为此在表中做行的初等变换设主元为alka.将主元所在第i行的数字除以主元alk；b.将计算得到的第i行的数字乘上（-aik），加到第i行数字上c.重新计算各变量的检验系数迭代次数基CBx1x2x3x4x5b比值210000x300510015-x40620102424/6x501100155zj00000Z=0j=cj-zj21000迭代次数基CBx1x2x3x4x5b比值210001x3005100153x1211/301/60412x5002/30-1/6113/2zj22/301/30Z=8j=cj-zj01/30-1/30新表中的基仍应是单位矩阵，为此在表中做行的初等变换设主元为alka.将主元所在第i行的数字除以主元alk；迭代次数基CBx1x2x3x4x5b比值210000x300510015-x40620102424/6x501100155zj00000Z=0j=cj-zj21000迭代次数基CBx1x2x3x4x5b比值210001x3005100153x1211/301/60412x5002/30-1/6113/2zj22/301/30Z=8j=cj-zj01/30-1/30新表中的基仍应是单位矩阵，为此在表中做行的初等变换设主元为alka.将主元所在第i行的数字除以主元alk；b.将计算得到的第i行的数字乘上（-aik），加到第i行数字上迭代次数基CBx1x2x3x4x5b比值210000x300510015-x40620102424/6x501100155zj00000Z=0j=cj-zj21000迭代次数基CBx1x2x3x4x5b比值210001x3005100153x1211/301/60412x5002/30-1/6113/2zj22/301/30Z=8j=cj-zj01/30-1/30第3步:迭代。1.确定入基变量2.确定出基变量3.用入基变量替换出基变量，得到一个新的基；对应这个基可以找到一个新的基可行解；并画出一个新的单纯形表。§5.2单纯形法的表格形式第五章单纯形法5.1单纯形法的基本思路和原理5.2单纯形法的表格形式第1步:求初始基可行解,列出初始单纯形表。第2步:最优性检验第3步:从一个基可行解转换到相邻的目标函数更大的基可行解，列出新的单纯形表(简称迭代)。第4步：重复2，3两步直到计算结束为止迭代次数基CBx1x2x3x4x5b比值210000x300510015-x40620102424/6x501100155zj00000Z=0j=cj-zj21000迭代次数基CBx1x2x3x4x5b比值210001x3005100153x1211/301/60412x5002/30-1/6113/2zj22/301/30Z=8j=cj-zj01/30-1/30第2步:最优性检验§5.2单纯形法的表格形式如果表中所有检验数j0，且基变量中不含有人工变量时，表中的基可行解，即为最优解,计算结束。当表中存在j＞0，如果有Pj0则问题为无界解，计算结束；否则转入下一步。第3步:迭代。1.确定入基变量2.确定出基变量3.用入基变量替换出基变量，得到一个新的基；对应这个基可以找到一个新的基可行解；并画出一个新的单纯形表。§5.2单纯形法的表格形式迭代次数基CBx1x2x3x4x5b比值210000x300510015-x40620102424/6x501100155zj00000Z=0j=cj-zj21000迭代次数基CBx1x2x3x4x5b比值210001x3005100153x1211/301/60412x5002/30-1/6113/2zj22/301/30Z=8j=cj-zj01/30-1/30迭代次数基CBx1x2x3x4x5b比值210001x3005100153x1211/301/60412x5002/30-1/6113/2zj22/301/30Z=8j=cj-zj01/30-1/30第3步:迭代。1.确定入基变量2.确定出基变量3.用入基变量替换出基变量，得到一个新的基；对应这个基可以找到一个新的基可行解；并画出一个新的单纯形表。§5.2单纯形法的表格形式迭代次数基CBx1x2x3x4x5b比值210001x3005100153x1211/301/60412x5002/30-1/6113/2zj22/301/30Z=8j=cj-zj01/30-1/30迭代次数基CBx1x2x3x4x5b比值210001x3005100153x1211/301/60412x5002/30-1/6113/2zj22/301/30Z=8j=cj-zj01/30-1/30迭代次数基CBx1x2x3x4x5b比值210001x3005100153x1211/301/60412x5002/30-1/6113/2zj22/301/30Z=8j=cj-zj01/30-1/30迭代次数基CBx1x2x3x4x5b比值210