第一章
线性规划及单纯形法
1.1 用图解法求解下列线性规划问题。并指出问题具有唯一最优解、无穷多最优解、无界解还是无可行解。 (a) min z=2x1+3x2 s.t. 4x1+6x2≥6
4x1+2x2≥4 x1, x2≥0
(b) max z=3x1+2x2 3x1+4x2≥12
x1,x2≥0
s.t. 2x1+x2≤2
(c) max z=x1+x2
5≤x1≤10 3≤x2≤8
(d) max z=5x1+6x2
s.t. 2x1-x2≥2
-2x1+3x2≤2
x1,x2≥0
s.t. 6x1+10x2≥120
解：
x2 3 (a) 2 L1 Lz 1 L2 1 2 x1 1 2 3 4 L1 Lz L2 x2 3 (b) x1
x2 x2 2 Lz x1 -1 x1 10 20 -2 1 2 (d) (c) 15 10 Lz 5
如图所示：(a) 有无穷多最优解；(b) 无可行解；(c) 有唯一最优解; (d) 无界解
1.3 用单纯形法求解下述线性规划问题
max z=10x1+5x2 s.t. 3x1+4x2≤9
5x1+2x2≤8 x1, x2≥0
解：
将此问题化成标准形式，
max z=10x1+5x2+0x3+0x4 s.t. 3x1+4x2+x3 =9
5x1+2x2
+x4=8
x1, x2, x3, x4≥0
P1P2P3P4?3410? ?5201???其约束系数矩阵：
单纯形法求解的过程见表如下 CB 0 0
由于10>5, 选择x1作为换入基的变量。对于P1有：
θ=min{ b1/a11, b2/a21 | a11,a21>0 }=min{9/3, 8/5 }=8/5. 确定x4为换出基变量。5为主元素 CB 0 10
Cj→ 基 X3 X1 Cj-zj 单纯形法的求解过程 b 21/5 8/5 10 X1 0 1 0 5 X2 14/5 2/5 1 0 X3 1 0 0 0 X4 -3/5 1/5 -2 Cj→ 基 X3 X4 Cj-zj 单纯形法的求解过程 b 9 8 10 X1 3 5 10 5 X2 4 2 5 0 X3 1 0 0 0 X4 0 1 0 由于1>0, 选择x2作为换入基的变量。对于P2有：
θ=min{ b1/a12, b2/a22 | a12,a22>0 }=min{(21/5)/(14/5),(8/5)/(2/5) }=21/14. 确定x3为换出基变量。2/5为主元素 CB 5 10
至此，所有检验数σj≤0，表明已找到最优解x1=1, x2=1.5, x3=0, x4=0 max z=10x1+5x2=17.5
x2 Lz 3 2 L2 Cj→ 基 X2 X1 Cj-zj 单纯形法的求解过程 b 3/2 1 10 X1 0 1 0 5 X2 1 0 0 0 X3 5/14 -1/7 -5/14 0 X4 -3/14 10/35 -25/14 (c) 1 L1 x1 2 4
1.8 已知某线性规划问题的初始单纯性表(1-23)和用单纯形法迭代后得到的表(1-24)如下，试求括弧中未知数q~l的值。 x4 x5 cj-zj x1 x5 cj-zj 解：
表1-24 (f) 4 x1 (g) (h) 0 x2 2 (i) -7 x3 -1 1 (j) x4 1/2 1/2 (k) x5 0 1 (l) 表1-23 6 1 x1 (b) -1 (a) x2 (c) 3 -1 x3 (d) (e) 2 x4 1 0 0 x5 0 1 0