cj
0
0
0
0 −1 −1 −1
θi
CB
XB
b
x1
x2
x3
x4
x5
x6
x7
−1 x5
2 （1） −1
2
−1 1
0
0
2
−1 x6
6
2
1
−3
1
0
1
0
3
−1 x7
7
1
1
1
1
0
0
1
7
σj
4
1
0
1
0
0
0
0
x1
2
1 −1
2
−1 1
0
0 -----
−1 x6
2
0 （3） − 7
3 −2 1
0
2/3
−1 x7
5
0
2
−1
s.t.⎪⎪⎪⎨−4xx11
+ x2 − x2
+ 6x3 ≥ 6 + x3 + x4
=
−4
⇒
⎪⎩x1 ≥ 1, x2 ≥ 0
P49 1—5
解：把x1 ≥ 1看作一函数约束
令自由变量x3 = x3/ − x3// , x4 = x4/ − x4//
max z = −3x1 − 4x2 − 2x3/ + 2x3// − x4/ + x4//
则 x2 为进基变量
⎧
⎪x3 = 15 − 5x2 ≥ 0
⎪
⎪ ⎨
x1
⎪
=
4
−
1 3
x2
≥
0
⎪ ⎪⎩
x5
=1−
2 3
x2
≥
0
⎧ ⎪
x
2
≤
15 5
⇒
⎪ ⎨
x
2
≤
4 1/ 3
⎪
⎪⎩x2
≤
1 2/3
⎧
⎪5x2 + x3 = 15
⎪
⎪ ⎨
x1
⎪
+
1 3
x2
+
1 6
x4
=
4
⎪ ⎪⎩
x2
−
1 4
x4
+
3 2
x5
=
3 2
⎧ ⎪
x3
⎪
+
5 4
x4
− 15 2
x5
=
15 2
⇒
⎪ ⎨
x1
⎪
+
1 4
x4
−
1 2
x5
=
7 2
⎪ ⎪⎩
x
2
−
1 4
x4
+
3 2
x5
=
3 2
则
x5
为进基变量，
2 3
为主元
-5-
运筹学作业答案
z
=
8+
1 3
x2
−
1 3
x4
=8+
1⎛3 ⎜
3⎝2
+
1 4
x4
−
3 2
x5
⎞ ⎟
−
⎠
1 3
x4
=
17 2
解：化标准形为：
⎧− s.t.⎪⎨−
x1 + x2 0.5x1 +
+ x3 x2 +
=1 x4 =
2
⎪⎩x1, x2 , x3 , x4 ≥ 0
cj
CB
XB
b
2
2
0
0
θi
x1
x2
x3
x4
ቤተ መጻሕፍቲ ባይዱ
0
x3
1
−1
1
1
0
0
x4
2
− 0.5
1
0
1
σj
2
2
0
0
∵σ1 = 2 > 0, 而它所对应的系数列向量α1 = (−1,−0.5)T < (0,0)T
0
x2
3
0
1
0
1 -5/11 -1/11 7/11
0
x3
1
0
0
1
0 1/11 -2/11 3/11
σj
0
0
0
0 −1 −1 −1
- 10 -
运筹学作业答案
由第一阶段最终单纯形表可得 z / * = 0 ，故原 LP 问题存在可行基，转入第二阶段继续求解。
第二阶段：求解原 LP 问题。
cj
−2
−1
1
3m 3
σj
− 24 0
1 −m
− 24
−m
−+ 24
0
2
9
− 3 x2 5
0
4
− 2 x1 5
1
− 3 /10
1 （3/5）
1/10
− 1 / 10
3/10
0
− 2 / 5 1/5 − 2 / 5 −1/ 5
2/5
σj
0
−1 x3 3
0
− 2 x1 2
1
σj
0
0
0 − 1/ 2 −1/2
5/3
1 − 1/ 2 1/6
⎧3x1 + x2 + x3/ − x3// + x5 = 7
⎪ ⎪4x1
+
x2
+ 6x3/
− 6x3//
−
x6
=
6
s.t.⎪⎨x1 + x2 − x3/ + x3// − x4/ + x4// = 4
⎪⎪x1 − x7 = 1
⎪⎩x1, x2 , x3/ , x3// , x4/ , x4// , x5, x6 , x7 ≥ 0
min ω = x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 ⎧x1 + x2 + x3 + 2x4 ≥ 100
s.t.⎪⎪⎪⎨2x1x1++23xx2 3++xx5 4++24xx7 5++36x8x6≥+1020x7 ≥ 100
⎪⎩x j ≥ 0( j = 1,2,⋯,8)
i=1 j =1
⎧x11 + x12 + x13 = 200
⎪ ⎪
x21
+
x22
+
x23
=
250
s.t.⎪⎪⎨ ⎪
x11 x12
+ +
x21 x22
= 100 = 150
⎪ ⎪
x13
⎪⎩xij
+ ≥
x23
0(i
= 200 = 1,2; j
=
1,2,3)
P48 1—2（2）
max z = x1 + x2
-3-
运筹学作业答案
解：可行域的极点与基本可行解是一一对应的。
（ 1 ） 对 于 X 2 = (9,7,0,0,8)T ， 不 满 足 约 束 条 件 4x1 + 7x2 − x3 − 2x4 − x5 = 85 ， 即
X 2 = (9,7,0,0,8)T 不是可行解，也就不是基本可行解，故不是该可行域的极点。 （2）对于 X1 = (5,15,0,20,0)T ，是可行解。此时基变量为 x1, x2 , x4 ，由此得到的基矩阵为
则该 LP 问题无最优解（无界解）。
-6-
运筹学作业答案
补充作业：
max z = 6x1 − 3x2 + 3x3
⎧3x1 + x2 + x3 ≤ 60
求解下列
LP
问题：
s.t.⎪⎪⎪⎨32xx11
− +
2x2 3x2
+ −
4x3 3x3
≤ ≤
20 60
⎪⎩x1, x2 , x3 ≥ 0
解：标准化后求解过程如下：
x1
（1）
（2）
解：由图可知
Q
点为最优点。∵
⎧3x1 ⎩⎨5x1
+ +
4x2 2x2
= 10 =8
⇒
⎧ ⎪
x1
⎨
⎪⎩x2
= 67 = 137
则
X
*
=
⎛ ⎜
6
,
13
⎞ ⎟
T
, z*
=
−29
⎝7 7 ⎠
P48 1—3（2）
min z = 3x1 + 4x2 + 2x3 + x4
⎧3x1 + x2 + x3 ≤ 7
21 0
1 3 −1 = 0 ，所以 X1 = (5,15,0,20,0)T 不是基本解，也就不是基本可行解，故不是该
4 7 −2
可行域的极点。
（3）对于 X 3 = (15,5,10,0,0)T ，是可行解。此时基变量为 x1, x2 , x3 ，由此得到的基矩阵为
2 1 −1
1 3 0 = 0 ，所以 X 3 = (15,5,10,0,0)T 不是基本解，也就不是基本可行解，故不是该可
⎧x1 − x2 ≥ 0(1) s.t.⎪⎨3x1 − x2 ≤ −3(2)
⎪ ⎩
x1
,
x2
≥
0
x2
（2）
R2
（1）
3 -1
0
解：∵ R1 ∩ R2 = Φ ，则该 LP 问题无可行解。