例题讲解(最优化)分析.doc

例1 用单纯形法解下列问题： 解：将原问题化成标准形： x4与添加的松弛变量x，x在约束方程组中其系数正好构成一个3阶单位阵，它们可以作为初始基变量，初始基可行解为X=（0, 0, , 8, 4）T列出初始单纯形表，见表。表cj→ 1 -2 1 0 0 0 CB 基 b x1 x2 x3 x4 x5 x 0 x4 10 1 1 -2 1 0 0 0 x5 8 2 -1 4 0 1 0 0 x6 4 -1 [2] -4 0 0 1 cj-zj 1 -2 1 0 0 0 由于只有σ2 0，说明表中基可行解不是最优解，确定x2为换入非基变量；以x2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量作为换出的基变量。 因此确定为主元素（表中以防括号[]括起），意味着将以非基变量x2去置换基变量x，采取的做法是对约束方程组的系数增广矩阵实施初等行变换，将x2的系数列(, -1, 2)T变换成x的系数列(0, 0, 1)T，变换之后重新计算检验数。变换结果见表2。 表cj→ 1 -2 1 0 0 0 CB 基 b x1 x2 x3 x4 x5 x 0 x4 8 3/2 0 0 1 0 -1/2 0 x5 10 3/2 0 [2] 0 1 1/2 -2 x2 2 -1/2 1 -2 0 0 1/2 cj-zj 0 0 -3 0 0 1 检验数σ=-30，当前基可行解仍然不是最优解。继续“换基”，确定为主元素，即以非基变量x置换基变量x。变换结果见表。表cj→ 1 -2 1 0 0 0 CB 基 b x1 x2 x3 x4 x5 x 0 x4 8 3/2 0 0 1 0 -1/2 1 x3 5 3/4 0 1 0 1/2 1/4 -2 x2 12 1 1 0 0 1 1 cj-zj 9/4 0 0 0 3/2 7/4 此时，个非基变量的检验数都于0，σ= 9/4，σ5= /2，σ5= /4，表明已求得最优解：。去除添加的松弛变量，原问题的最优解为：法求解下列问题： 解 引进松弛变量x4、、剩余变量x5和人工变量x6、x7，解下列问题： 用单纯形法计算如下： 表cj→ 1 1 -3 0 0 M M CB 基 b x1 x2 x3 x4 x x6 x7 0 x4 11 1 -2 1 1 0 0 0 M x6 3 2 1 -4 0 -1 1 0 M x7 1 [1] 0 -2 0 0 0 1 cj-zj 4M 1-3M 1-M -3+6M 0 M 0 0 由于σ1σ2 0，说明表中基可行解不是最优解，确定x为换入非基变量；以x的系数列的正分量对应去除常数列，最小比值所在行对应的基变量作为换出的基变量。 因此确定为主元素（表中以防括号[]括起），意味着将以非基变量x去置换基变量x，采取的做法是对约束方程组的系数增广矩阵实施初等行变换，将x的系数列(, 2, 1)T变换成x的系数列(0, 0, 1)T，变换之后重新计算检验数。变换结果见表2。 表cj→ 1 1 -3 0 0 M M CB 基 b x1 x2 x3 x4 x x6 x7 0 x4 10 0 -2 3 1 0 0 -1 M x6 1 0 [1] 0 0 -1 1 -2 1 x1 1 1 0 -2 0 0 0 1 cj-zj M+1 0 1-M -1 0 M 0 3M-1 由于σ2σ3 0，说明表中基可行解不是最优解，确定x为换入非基变量；以x的系数列的正分量对应去除常数列，最小比值所在行对应的基变量作为换出的基变量。因此确定为主元素，意味着将以非基变量x去置换基变量x，采取的做法是对约束方程组的系数增广矩阵实施初等行变换，将x的系数列(, 1, 0)T变换成x的系数列(0, , 0)T，变换之后重新计算检验数。变换结果见表。表cj→ 1 1 -3 0 0 M M CB 基 b x1 x2 x3 x4 x x6 x7 0 x4 12 0 0 [3] 1 -2 2 -5 1 x2 1 0 1 0 0 -1 1 -2 1 x1 1 1 0 -2 0 0 0 1 cj-zj 2 0 0 -1 0 1 M-1 M+1 由于只有σ3 0，表中基可行解不是最优解，确定x为换入非基变量；x3的系数列的正分量确定为主元素，意味着将以非基变量x去置换基变量x，对约束方程组的系数增广矩阵实施初等行变换，将x的系数列(, 0, -2)T变换成x的系数列(, 0, 0)T，变换之后重新计算检验数。变换结果见表。表cj→ 1 1 -3 0 0 M M CB 基 b x1 x2 x3 x4 x x6 x7 -3 x3 4 0 0 1 1/3 -2/3