运筹学2-4.ppt

例：用单纯形法求解 x1 x2 x3 x4 4 6 -2 2 1 0 3 1 0 1 X3 X4 0 -3 -1 -1 -1 z RHS x1 x2 x3 x4 4 6 -2 2 1 0 3 1 0 1 X3 X4 10 -2 2 0 0 z RHS 2 4 -1 1 1/2 0 4 0 -1/2 1 X2 X4 6 0 0 -1 0 z 最优解X=（0，2，0，4），最优值是6。 T §2.4 初始解（两阶段法） 问题：线性规划 问题化为标准型时， 若约束条件的系数 矩阵中不存在单位 矩阵，如何构造 初始可行基？ §2.4 初始解（两阶段法） 第一阶段：加入人工变量,构造初始可行基. 用单纯形法求解,若g=0, 进入第二阶段,否则,原问 题无可行解。 第二阶段：去掉人工变量，还原目标函数系数，做 出初始单纯形表。 例：求解下列线性规划问题 将原问题化成标准型： 解: 化标准型 用两阶段方法来求解。 第一阶段的线性规划问题为 x1 x2 x3 x4 x5 x6 x7 4 1 9 1 1 1 1 0 0 0 -2 1 -1 0 -1 1 0 0 3 1 0 0 0 1 X4 X6 X7 0 0 0 0 0 0 -1 -1 g RHS x1 x2 x3 x4 x5 x6 x7 RHS 4 1 9 1 1 1 1 0 0 0 -2 1 -1 0 -1 1 0 0 3 1 0 0 0 1 X4 X6 X7 10 -2 4 0 0 -1 0 0 g 3 1 6 3 0 2 1 1 -1 0 -2 1 -1 0 -1 1 0 6 0 4 0 3 -3 1 X4 X2 X7 6 6 0 4 0 3 -4 0 g 0 3 1 0 0 0 1 -1/2 1/2 -1/2 0 1 1/3 0 0 0 1/3 1 0 2/3 0 1/2 -1/2 1/6 X4 X2 X1 0 0 0 0 0 0 -1 -1 g x1 x2 x3 x4 x5 x6 x7 RHS 得原问题的基可行解X=(1,3,0,0,0,)T。 第二阶段：将上表中的人工变量去除，目标函数换成原问题的目标函数从上表的最后一个单纯形表出发，继续计算。 0 3 1 0 0 0 1 -1/2 0 1 1/3 0 0 1 0 2