《北邮运筹学ch4-3_目标规划单纯形法》由会员分享，可在线阅读，更多相关《北邮运筹学ch4-3_目标规划单纯形法（6页珍藏版）》请在金锄头文库上搜索。
1、北京邮电大学 运筹学 4.3 单纯形法单纯形法 Simplex Method Ch4 Goal Programming 2013-5-17Page 1 of 6 目标规划的数学模型与线性规划基本相同，所以用单纯 形法求解时的方法步骤也基本相同。但由于目标规划中目标 函数分不同的优先级，因此应首先寻求使最高优先级的目标 优化，然后转向下一级，当下一级目标优化后再转更低一 级，等等。下面用例子具体说明。 【例例1】用单纯形法求解下述目标规划问题： 32211 )(mindPddPz )3 , 2 , 1(0, 10023 402 10 21 3321 2221 111 iddxx ddxx ddx
2、x ddx ii 北京邮电大学 运筹学 4.3 单纯形法单纯形法 Simplex Method Ch4 Goal Programming 2013-5-17Page 2 of 6 【解】用单纯形法求解目标规划问题的具体步骤如下： 第步第步：列出初始单纯形表。由于目标规划中的目标函数一定是求极小， 为方便起见不转换成求极大。又由于各目标约束中的负偏差变量其系数均为 单位向量，全部负偏差变量的系数列向量构成一个基。因此本例中以d1、d2 、d 3 作为基变量，列出初始单纯形表见表41。 因为目标函数中各偏差变量分别乘以不同的优先因子，因此表中检验 数（cjzj）按优先因子1、2分成两行，分别计算。
3、 第步第步：确定换入变量。在表4中按优先级顺序依次检查1,P2, 3,，k行的（cjzj）值是否有负的。因表中1行存在负检验数，说明目 标函数中第一优先级可进一步优化，选取1行中最小检验数，其对应变量 x1即为换入变量。 第步第步：确定换出变量，将表4中b列数字同x1列中的正数相比， 其最小比值对应的变量d1即为换出变量。 第步第步：用换入变量替换基变量中的换出变量，进行迭代运算，得表4 。 北京邮电大学 运筹学 4.3 单纯形法单纯形法 Simplex Method Ch4 Goal Programming 2013-5-17Page 3 of 6 23P2 111P1 CjZj 10011
4、23d3P2 401112d20 101101d1P1 d3+d3d2+d2d1+d1x2x1 基变量 CB b 0 P2P100P100Cj 332P2 11P1 CjZj 7011332d3P2 2011221d20 101101x10 表 1 表 2 北京邮电大学 运筹学 4.3 单纯形法单纯形法 Simplex Method Ch4 Goal Programming 2013-5-17Page 4 of 6 13/2P2 11P1 CjZj 40113/23/21/2d3P2 101/21/211 1/2d1+0 201/21/21x10 d3+d3d2+d2d1+d1x2x1 基变量
5、 CB b 0 P2P100P100Cj 12211P2 11P1 CjZj 30112211d3P2 2011221x20 10111x10 表 3 表 4 北京邮电大学 运筹学 4.3 单纯形法单纯形法 Simplex Method Ch4 Goal Programming 2013-5-17Page 5 of 6 这里需要说明两点： 1对目标函数的优化是先按优先顺序逐步进行的。当P1行的 所有检验数均为非负时，说明第一级已得到优化，可转入下一 级，再考察P2行的检验数是否存在负值，依此类推。 2从考察P2行以下的检验数时，注意应包括更高级别的优先 因子在内，例如表3最下面P2行有两个负值
6、，其对应的变量d1 的检验数为（P1P2）0，变量d2的检验数为(P12P2) 0。 因此判断迭代算应否停止的准则为： 即从2行起，虽然在某一行存在负检验数，而该负检验数同 列较高优先级的行中存在有正检验数时，计算就应停止。 (1)检验数P1,P2，k行的所有值均为非负； (2)P1，Pi行所有检验数，第Pi+1行存在负检验数， 但在负检验数所在列的上面行中有正检验数。 北京邮电大学 运筹学 4.3 单纯形法单纯形法 Simplex Method Ch4 Goal Programming 2013-5-17Page 6 of 6 作业：作业：1.教材教材P113 T4.3 Exit第五章 整数规划第五章 整数规划 The End of Chapter 4
