1、4.3单纯形法单纯形法 Simplex MethodCh4GoalProgramming Page 1 of 608 八月 2024 目标规划的数学模型与线性规划基本相同，所以用单纯形法求解时的方法步骤也基本相同。但由于目标规划中目标函数分不同的优先级，因此应首先寻求使最高优先级的目标优化，然后转向下一级，当下一级目标优化后再转更低一级，等等。下面用例子具体说明。【例例1】用单纯形法求解下述目标规划问题：4.3单纯形法单纯形法 Simplex MethodCh4GoalProgramming Page 2 of 608 八月 2024【解】用单纯形法求解目标规划问题的具体步骤如下：第第步步：列
2、出初始单纯形表。由于目标规划中的目标函数一定是求极小，为方便起见不转换成求极大。又由于各目标约束中的负偏差变量其系数均为单位向量，全部负偏差变量的系数列向量构成一个基。因此本例中以d1、d2、d3作为基变量，列出初始单纯形表见表41。因为目标函数中各偏差变量分别乘以不同的优先因子，因此表中检验数（cjzj）按优先因子1、2分成两行，分别计算。第第步步：确定换入变量。在表4中按优先级顺序依次检查1,P2,3,，k行的（cjzj）值是否有负的。因表中1行存在负检验数，说明目标函数中第一优先级可进一步优化，选取1行中最小检验数，其对应变量x1即为换入变量。第第步步：确定换出变量，将表4中b列数字同x
3、1列中的正数相比，其最小比值对应的变量d1 即为换出变量。第第步步：用换入变量替换基变量中的换出变量，进行迭代运算，得表4。4.3单纯形法单纯形法 Simplex MethodCh4GoalProgramming Page 3 of 608 八月 2024Cj00P100P1P20bCB基变量x1x2d1d1+d2d2+d3d3+P1d11011100d2211140P2d33211100CjZjP1111P2320 x11011100d21221120P2d32331170CjZjP111P2233表1表24.3单纯形法单纯形法 Simplex MethodCh4GoalProgrammin
4、g Page 4 of 608 八月 2024Cj00P100P1P20bCB基变量x1x2d1d1+d2d2+d3d3+0 x111/21/2200d1+1/2111/21/210P2d31/23/23/21140CjZjP111P2 3/210 x1111100 x21221120P2d311221130CjZjP111P211221表3表44.3单纯形法单纯形法 Simplex MethodCh4GoalProgramming Page 5 of 608 八月 2024这里需要说明两点：1对目标函数的优化是先按优先顺序逐步进行的。当P1行的所有检验数均为非负时，说明第一级已得到优化，可转
5、入下一级，再考察P2行的检验数是否存在负值，依此类推。2从考察P2行以下的检验数时，注意应包括更高级别的优先因子在内，例如表3最下面P2行有两个负值，其对应的变量d1的检验数为（P1P2）0，变量d2的检验数为(P12P2)0。因此判断迭代算应否停止的准则为：即从2行起，虽然在某一行存在负检验数，而该负检验数同列较高优先级的行中存在有正检验数时，计算就应停止。(1)检验数P1,P2，k行的所有值均为非负；(2)P1，Pi行所有检验数，第Pi+1行存在负检验数，但在负检验数所在列的上面行中有正检验数。4.3单纯形法单纯形法 Simplex MethodCh4GoalProgramming Page 6 of 608 八月 2024作业：作业：1.教材教材P113T4.3Exit第五章第五章整数规划整数规划TheEndofChapter4
浙ICP备2021020529号-1 | 浙B2-20240490 
