1-3单纯形法PPT.ppt

表格设计依据： 将目标函数表达式改写成方程的形式，和原有的m个约束方程组成一个具有n+1个变量、m+1个方程的方程组： 取出系数写成增广矩阵的形式： -Z x1 x2 … xm xm+1 xm+2 … xn b 用矩阵的初等行变换将该基变成单位阵,这时 变成0，相应的增广矩阵变成如下形式： 增广矩阵的最后一行就是用非基变量表示目标函数的表达式, 就是非基变量的检验数。 … 0 … 0 … 1 … 0 bm xm … … … … … … … … … … … 0 … 0 b2 x2 … 0 … 1 b1 x1 … … … … 根据增广矩阵设计单纯形表 表格单纯形法求解步骤 第一步：将LP化为标准型，并加以整理。 引入适当的松驰变量、剩余变量和人工变量，使约束条件化为等式，并且约束方程组的系数阵中有一个单位阵。 确定初始可行基，写出初始基本可行解 第二步：最优性检验 计算检验数，检查： ?所有检验数是否≤ 0？ 是——结束，写出最优解和目标函数最优值； ?还有正检验数——检查相应系数列≤ 0？ 是——结束，该LP无“有限最优解”！ ?不属于上述两种情况，转入下一步—基变换。 确定是停止迭代还是转入基变换？ 选择正检验数对应的系数列为主元列，主元列对应的非基变量为换入变量； 用最小比原则确定换出变量，最小比值对应的行为主元行，主元行和主元列交叉位置的元素为主元素。 第三步：基变换 确定进基变量、出基变量。 利用矩阵初等行变换把主元列变成单位向量,主元素变为1，其他位置元素变为0。此外，将基变量XB和CB换掉，得到一张新的单纯形表，返回第二步。 第四步 换基迭代（旋转运算、枢运算) 完成一次迭代，得到新的基本可行解和相应的目标函数值 该迭代过程直至下列情况之一发生时停止 ? 检验数行全部变为非正值； （得到最优解）或 ?主元列≤ 0 （没有有限的最优解） 停止迭代的标志 例 引入非负的松弛变量X3,x4,x5,将该 LP化为标准型 cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 0 x3 8 1 2 1 0 0 4 0 x4 16 4 0 0 1 0 - 0 x5 12 0 [4] 0 0 1 3 cj-zj 2 3 0 0 0 cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 0 x3 2 [1] 0 1 0 -1/2 2 0 x4 16 4 0 0 1 0 4 3 x2 3 0 1 0 0 1/4 - cj-zj 2 0 0 0 -3/4 cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2 x1 2 1 0 1 0 -1/2 - 0 x4 8 0 0 -4 1 [2] 4 3 x2 3 0 1 0 0 1/4 12 cj-zj 0 0 -2 0 1/4 cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2 x1 4 1 0 0 1/4 0 - 0 x5 4 0 0 -2 1/2 1 - 3 x2 2 0 1 1/2 -1/8 0 - cj-zj 0 0 -3/2 -1/8 0 从最优表可知: 该LP的 最优解是X*=(4, 2, 0, 0, 4)T 相应的目标函数最优值是Zmax=14 例、表格单纯形法计算过程： 例、表格单纯形法计算过程： CB XB Cj b xj 2 3 3 0 0 x1 x2 x3 x4 x5 ?j 0 0 X4 X5 3 9 1 1 1 1 0 1 4 7 0 1 3/1 9/1 -Z 0 2 3 3 0 0 2 0 X1 X5 3 6 1 1 1 1 0 0 3 6 -1 1 3/1 6/3 -Z -6 0 1 1 -2 0 2 3 X1 X2 1 2 1 0