整理线性规划及单纯形法

1、精品文档 精品文档 第一章 线性规划及单纯形法 1.1 用图解法求解下列线性规划问题。并指出问题具有唯一最优解、无穷多最优 解、无界解还是无可行解。 (b) max Z=3XI+2X2 s.t. 2XI+X2 0 (c) max Z=X1 +X2 (d) s.t. 6X1+10X2 120 5 X1 10 3 X2 6 4X什 2X24 X1,X2 0 max Z=5X1+6X2 s.t. 2X1-X2 2 -2X1+3x2 w 2 X1 ,X2 X2 精品文档 精品文档 解精品文档 精品文档 1.3 用单纯形法求解下述线性规划问题 max Z=10XI+5X2 s.t. 3XI+4X2 9

2、5XI+2X2 0 解： 将此问题化成标准形式， max z=10 xi +5X2+0X3+0X4 s.t. 3xi+4x2+x3 =9 5XI+2X2 +X4=8 Xi, X2, X3, X4 0 R p2 巳 巳 其约束系数矩阵： 3 4 10 |5 2 0 1 单纯形法求解的过程见表如下 单纯形法的求解过程 Cj - 10 5 0 0 CB 基 b X1 X2 X3 X4 0 X3 9 3 4 1 0 0 X4 8 5 2 0 1 Cj-zj 10 5 0 0 由于 105,选择 X1作为换入基的变量。对于 P1有： 0 =min b 1/an, b2/a21 | an,a210 =mi

3、n9/3, 8/5 =8/5.确定 X4为换出基变量。5 为 主元素 单纯形法的求解过程 Cj - 10 5 0 0 CB 基 b X1 X2 X3 X4 0 X3 21/5 0 14/5 1 -3/5 10 X1 8/5 1 2/5 0 1/5 Cj-zj 0 1 0 -2 精品文档 精品文档 由于 10,选择 x2 作为换入基的变量。对于 P2有： 9 =min b i/ai2, | 毗,宠20 =min(21/5”(14/5),(8/5)/(2/5) =21/14. 确定 x3 为 换出基变量。2/5 为主元素 单纯形法的求解过程 Cj - 10 5 0 0 CB 基 b X1 X2 X

4、3 X4 5 X2 3/2 0 1 5/14 -3/14 10 X1 1 1 0 -1/7 10/35 Cj-zj 0 0 -5/14 -25/14 至此，所有检验数(T j 0,表明已找到最优解 xi = 1, X2=1.5, X3=0, X4=0 max z=10 xi+5x2=17.5 1.8 已知某线性规划问题的初始单纯性表 (1-23)和用单纯形法迭代后得到的表 (1-24)如下，试求括弧中未知数 ql 的值。 表 1-23 X1 X2 X3 X4 X5 X4 6 (b) (c) (d) 1 0 X5 1 -1 3 (e) 0 1 Cj-Zj (a) -1 2 0 0 表 1-24

5、X1 X2 X3 X4 X5 X1 (f) (g) 2 -1 1/2 0 精品文档 精品文档 X5 4 (h) (i) 1 1/2 1 cj-zj 0 -7 (j) (k) (l) 解： 由表 1-23 和 1-24 可知换出变量为 x4,换入变量为 x1。又因为 a2i=-10 所以， 主元只能是 b。所以有 g=1, h=0, c/b=2, d/b=-1, 1/b=1/2. 6/b=f 于是 b=2, c=4, d=-2, f=3。将这些数值代入相应参数，表 1-23 变成 表 1-23b x1 X2 x3 X4 x5 x4 6 2 4 -2 1 0 X5 1 -1 3 (e) 0 1 c

6、j-Z (a) -1 2 0 0 主元所在行除 2 得: 表 1-23c X1 X2 X3 X4 X5 X1 3 1 2 -1 1/2 0 x5 1 -1 3 (e) 0 1 cj-Z (a) -1 2 0 0 由表 1-23c 将 a21化为 0 得 表 1-23d X1 X2 X3 X4 X5 X1 3 1 2 -1 1/2 0 X5 4 0 5 （e-1） 1/2 1 cj-Z 0 -2a-1 a+2 -a/2 0 将表 1-23d 与表 1-24 比较后有： e-1=1, e=2, i=5.由检验数关系得-2a-1=-7,a=3; j=a+2=5; k=-a/2=-3/2; 1=0 最

7、终表 2-24 结果为 表 1-24a X1 X2 X3 X4 X5 X1 3 1 2 -1 1/2 0 X5 4 0 5 1 1/2 1 cj-Z 0 -7 5 -3/2 0 精品文档 精品文档 1.12 已知线性规划问题 max Z=C1X1+C2X2+C3X3 S.t. Xl+2X2+X3 0 (j=1,2,3) 用单纯形法求解得最终单纯形表 1-25,表中 X4, X5为松弛变量 表 1-25 X1 X2 X3 X4 X5 X2 1 1/5 1 0 3/5 -1/5 X3 3 3/5 0 1 -1/5 2/5 Cj-Z -7/10 0 0 -3/5 -4/5 试计算确定 C1, C2,

8、 C3和 b 的值。 解：因为 X4, X5为松弛变量，所以 C4=C5=0. 由书中式 1-23,对应 X1,X4,X5检验数计算可有 ,m 13 7 -1 一 i xCiai1 壬 一 (C2a11 C3a21)- C2 q： 住 5 5 10 m 3 1 i 1&ai4 =C4 一(C2a14 C3a24) =0 一5C2 - 5C3 5 5 即 C1=1.5, C2=2, C3=3,下面利用矩阵初等变换使X2,X3 对应列向量构成一组基 1 2 1 1 0 b - ,1/2 1 1/2 1/2 2 1 3 0 1 2b _2 1 3 0 1 /2 1 1 /2 1/2 0 b/2亠 1 1/5 J/5 0 1 _,1/ 5 2/5 3b/5 3/5 1 0 3/5 -1/5 b/5 0 1 -1/ 5 2/5 3b/5 0 b/2 1/2 1 1/2 1/2 0 b/2 1 2b 3/2 0 5/2 -1/2 1 3b/2 二 4 二 C4 -二 辽=G -Z i