第1章线性规划与单纯形法.pptVIP

MaxZ=-3x1+x3-Mx6-Mx7 x1+ x2+ x3+x4 =4 -2x1+ x2-x3 -x5+x6 =1 3x2+x3 +x7=9 xi ≥0,j=1,…,7 MaxZ=-3x1+x3 x1+ x2+ x3≤4 -2x1+ x2- x3≥1 3x2+x3=9 xi ≥0,j=1,2,3 增加人工变量后，线性规划问题中就存在一个B为单位矩阵， 阵，后面可以根据我们前面所讲的单纯形法来进行求解。 标准化及变形 * 当前第62页\共有111页\编于星期三\7点 cj -3 0 1 0 0 -M -M CB XB bi x1 x2 x3 x4 x5 x6 x7 θ 0 x4 4 1 1 1 1 0 0 0 -M x6 1 -2 1 -1 0 -1 1 0 -M x7 9 0 3 1 0 0 0 1 σj -3-2M 4M 1 0 0 [ ] 3 x2入，x6出 -M 0 4 1 [ ] 0 x4 0 x2 -M x7 3 3 0 2 1 1 -1 0 σj 6M-3 0 4M+1 0 -4M [ ] - x1入，x7出 3M 0 1 -2 1 -1 0 -1 1 0 1 6 6 0 4 0 3 -3 1 1 [ ] 0 x4 0 x2 -3 x1 0 0 0 0 1 -1/2 1/2 -1/2 σj 0 0 3 0 -M-3/2 [ ] 9 x3入，x1出 3/2 -M+1/2 3 0 1 1/3 0 0 0 1/3 3/2 1 1 0 2/3 0 1/2 -1/2 1/6 - [ ] 0 x4 0 x2 1 x3 0 0 0 0 1 -1/2 1/2 -1/2 σj -9/2 0 0 0 -M+3/4 -3/4 -M-1/4 5/2 -1/2 1 0 0 -1/4 1/4 1/4 3/2 3/2 0 1 0 3/4 -3/4 1/4 所以：X*=(x2,x3,x4)T=(5/2,3/2,0)T Z*=3/2 * 当前第63页\共有111页\编于星期三\7点 第一阶段：暂不考虑原问题是否存在基可行解，给原问题加入人工变量，并构建一个仅含人工变量的目标函数（求极小化），人工变量的价值系数一般为1，约束条件和原问题的一样。 当第一阶段中目标函数的最优值＝0，即人工变量＝0，则转入第二阶段；若第一阶段中目标函数的最优值不等于0，即人工变量不等于0，则判断原问题为无解。 第二阶段：将第一阶段计算所得的单纯形表划去人工变量所在的列，并将目标函数换为原问题的目标函数作为第二阶段的初始单纯形表，进行进一步的求解。 两 阶 段 法 * 当前第64页\共有111页\编于星期三\7点 辅 助 问 题 * 当前第65页\共有111页\编于星期三\7点 辅 助 问 题 与 原 问 题 的 关 系 * 当前第66页\共有111页\编于星期三\7点 求 辅 助 问 题 的 三 种 情 况 * 当前第67页\共有111页\编于星期三\7点 求解辅助问题，得到辅助问题的最优解 引进人工变量x6，x7，构造辅助问题，辅助问题的目标函数为所有人工变量之和的极小化 MaxW=0? 原问题没有可行解。 把辅助问题的最优解作为原问题的初始基础可行解 用单纯形法求解原问题，得到原问题的最优解 否 是 两阶段法的算法流程图 MaxZ=-3x1+x3 x1+ x2+ x3≤4 -2x1+ x2- x3≥1 3x2+x3=9 xi ≥0,j=1,2,3 MaxW=-x6-x7 x1+ x2+ x3+x4 =4 -2x1+ x2-x3 -x5+x6 =1 3x2+x3 +x7=9 xi ≥0,j=1,…,7 * 当前第68页\共有111页\编于星期三\7点 cj 0 0 0 0 0 -1 -1 CB XB bi x1 x2 x3 x4 x5 x6 x7 θ 0 x4 4 1 1 1 1 0 0 0 -1 x6 1 -2 1 -1 0 -1 1 0 -1 x7 9 0 3 1 0 0 0 1 (第一阶段）单纯形表1 σj