例8现有线性规划问题,试用大M法求解。 min z==3xtx tx 1-2x2+x3≤11 4x1+ x2+2x3≥3 2 +x2=1 x,x2,x3≥0
例8 现有线性规划问题，试用大M法求解。 − + = − + + − + = − + + , , 0 2 1 4 2 3 2 11 min 3 1 2 3 1 3 1 2 3 1 2 3 1 2 3 x x x x x x x x x x x z x x x
解在上述问题的约束条件中加入松弛变 量x,剩余变量x5,人工变量x,x7,得到 min 2=-3x+x,+xx+OxA +Oxs+Mxe+mx x1-2x2+x2+x 11 4x1+x2+2x3 Xs+x 2 +x7=1 X1 2,3,14,5X6x7≥0 这里M是一个任意大的正数
解 在上述问题的约束条件中加入松弛变 量x4，剩余变量x5，人工变量x6 ,x7，得到 − + + = − + + − + = − + + = = − + + + + + + , , , , , , 0 2 1 4 2 3 2 11 min 3 0 0 1 2 3 4 5 6 7 1 3 7 1 2 3 5 6 1 2 3 4 1 2 3 4 5 6 7 x x x x x x x x x x x x x x x x x x x z x x x x x Mx Mx 这里M是一个任意大的正数
因本例的目标函数是要求min,所以用所有 Cjzj≥0来判别目标函数是否实现了最小化.用单 纯形法进行计算时,见表1-6。 M B b X2 M 2 03/2 X 0[11000 Ci-Z +6MI-M1-3MOM0O
因本例的目标函数是要求min，所以用所有 cj-zj≥0来判别目标函数是否实现了最小化.用单 纯形法进行计算时，见表1-6。 cj→ -3 1 1 0 0 M M CB XB b x1 x2 x3 x4 x5 x6 x7 θi 0 M M x4 x6 x7 11 3 1 1 -4 -2 -2 1 0 1 2 [1] 1 0 0 0 -1 0 0 1 0 0 0 1 11 3/2 1 cj -zj -3+6M 1-M 1-3M 0 M 0 0
在表1-6的最终计算结果表中,表明已得到最优解是: 9 X2=9,ⅩA=X=X 3 0;目标涵数z=2 一 M C X X 2 0 0 Ci-Z 1-M1-3M0 M 03M-1 0 12 0 0 0 0 Ci-zi M-1 M+ X 0 1/3-2/32/3 5/3 2/3-434/3-7/3 Ci-Z 0 /31/3M-1/3M2/3
在表1-6的最终计算结果表中，表明已得到最优解是： x1 =4,x2 =1,x3 =9，x4 =x5 =x6 =x7 =0；目标函数z=-2 cj→ -3 1 1 0 0 M M CB XB b x1 x2 x3 x4 x5 x6 x7 θi 0 M 1 x4 x6 x3 10 1 1 3 0 -2 -2 [1] 0 0 0 1 1 0 0 0 -1 0 0 1 0 -1 -2 1 1 cj -zj -1 1-M 1-3M 0 M 0 3M-1 0 1 1 x4 x2 x3 12 1 1 [3] 0 -2 0 1 0 0 0 1 1 0 0 -2 -1 0 2 1 0 -5 -2 1 4 cj -zj -1 0 0 0 1 M-1 M+1 -3 1 1 x1 x2 x3 4 1 9 1 0 0 0 1 0 0 0 1 1/3 0 2/3 -2/3 -1 -4/3 2/3 1 4/3 -5/3 -2 -7/3 cj -zj 2 0 0 0 1/3 1/3 M-1/3 M-2/3
两阶段法 以下介绍求解含有人工变量线性规划问 题的两阶段法。 第一阶段:不考虑原问题是否存在基可 解;给原线性规划问题加入人工变量, 并构造仅含人工变量的目标函数和要求 实现最小化
2. 两阶段法 • 以下介绍求解含有人工变量线性规划问 题的两阶段法。 • 第一阶段：不考虑原问题是否存在基可 行解；给原线性规划问题加入人工变量， 并构造仅含人工变量的目标函数和要求 实现最小化