4x1+2x3≥10 x1,x2,x3≥0
解：先将问题化为标准式
maxz'=?10x1?5x2?4x3+0x4+0x5st. -3x1?2x2+3x3+x4 =?3 -4x1?2x3 +x5 =?10 xi(i=1,2,3,4,5)≥0
则原问题已化为关于基B 的典式， C CB0 0
XBX4X5
2 X1
3 X2
1 0 X3
X4
0 X50 1 0
-3 -100 B
取初始正则基 B = （p4 p5） = I
-3 -2 -4 0
3 1 -2 0 -4 0 0 1 1 0 0 0
检验数 -10 -5 0
X4
-9 -2 2
0
3/2 -18-1/25 -2
20
-4 X3
检验数 -2 -5 -10 X1-4 X3
1 0
2/9
0 -1/9 -1/62
-4/9 1 2/9 -1/61 -41/9 0 -2/9 -7/324
检验数 0
可得原问题的最优解为：
Tx*=（2,0,1,0,0）,Z*=?24,Z=24,y*=(2/9,7/3),w*=24.
(2) minz=2x1+3x2+4x3 s.t. x1+2x2+x3≥3 2x1?x2+3x3≥4
x1,x2,x3≥0
将问题化为：
11
maxz'=?2x1?3x2?4x3
st. ?x1?2x2?x3+x4 =?3 -2x1+x2?3x3 +x5 =?4 xi(i=1,2,3,4,5)≥0C CB
XB
3 2 X1
X2
1 X3-1 -3 -4
0 X41 0 0 1 0 0
0 X50 1 0
-3 -4 B
0 X40 X5
-1 -2 -21
检验数 -2 -3 0 X43 X1
0 -5/21/2 1 -1/2 3/2
-1
-1/2 -1 -1/2 2 -1
250 2/5
检验数 0 -4 2 X23 X1
0 1 1 0
-1/5 -2/5 1/5
14/10 -1/5 -4/1011/5 -9/5 -8/5 -1/5 -28/5
检验数 0 0
x*=(11/5,2/5,0)T； Z'*=?28/5; Z*=28/5
(3) minz=2x1+x2 s.t. 3x1+x2≥3
4x1+3x2≥6 x1+2x2≤3 x1,x2≥0
解：
(3)maxz'=?2x1?x2
st. -3x1?x2+x4 =?3 -4x1?3x3 +x5 =?6 x1+2x2 +x6 =3 xi(i=1,2,3,4,5,6)≥0
12
C CB0 0 0
XBX4X5X6
3 X1
5 X2
0 0 X3
X4
0 X50 1 0 0 0
0X600100
B
-3 -1 -4 0 1
2
0 1 -30 0 0 0 0 0 1 1 0 0 0 0 0
-3 -6 3 -3 2 3 1 2/32 2
检验数 -2 -1 0 0 0
X4X3X6
-3
-1
4/3 0 1
2
-1/300 0
100
检验数 -2 -1 -2 X10 0
X3X6
1 0 0
1/3 0 -1/3 0
-4/9 1 4/9 -1/305/3 0 1/3 0 -1/3 0 -2/3 0
10
检验数 0
(4) minz=3x1+2x2+x3 s.t. x1+x2+x3≤6
x1+x3≥4 x2?x3≥3
xj≥0(j=1,2,3)
解：化为：
maxz'=?3x1?2x2?x3
st. x1+x2+x3+x4 =6 -x1?x3 +x5 =?4=?3 ?x2+x3 +x6 xi(i=1,2,3,4,5,6)≥0
13
C CB
XB
-3 -2 -10 0 0 b X1
X2
X3
X4X5
X6
0 X40 X50 X6
1 1 1 1 0 0 6 -1 0 -10 1 0 -40 -1 1 0 0 1 -3
检验数 -3 -2 -10 0 0 0 X4-1 X30 X6
0 1 0 1 1 0 2 1 0 1 0 -1 0 4 -1-1 0 0 1 1 -7
检验数 -2 -2 0 0 -1 0 0 X4-1 X3-3 X1
0 1 0 1 1 0 2 0 -11 0 0 1 -31 1 0 0 -1 -1 7
检验数 0 0 0 0 -3 -2 0 X4-2 X2-3 X1
0 0 1 1 1 1 -10 1 -10 0 -1 3 1 0 1 0 -1 0 4
检验数 0 0 0 0 -3 -2 由表知，此题无可行解。
13、已知线性规划问题
maxz=3x1+8x2 s.t.
cj cBxB3 x10 x4x28
检验数 3
8
表2-3 0
0 0 1 0 0
0 -2 10 1
x11 0 0 0
x20 0 1 0
x31/2-3 0 -3/2
x4 x5
b
100 500 350
2x1+4x2≤1600 6x1+2x2≤1800 x2≤350 x1,x2≥0
-2 -3100
用单纯形法求解时得最终单纯形表如表2-3所示.
14
（1）要保持现有最优解不变，分别求c1,c2的变化范围； （2）要保持现有最优解不变，分别求b1,b2，b3的变化范围； （3）当b3变为500时，求新的最优解. 解：
（1）由表知，C1C2为基变量的系数
??3/2?
∴ΔC1?=max?+?=?3
?1/2???2?
ΔC1+=min?+?=1
??2?∴C1∈[0,4]
??2?
ΔC2?=max?+?=?2
?1??3/2?
ΔC2+=min?+?=∞
0??
∴C2∈[6,+∞)
（2）参见教材P67的方法求之 (3) ∵b3=500?[300,400] ∴最优解将发生变化；
Δb=(0,0,150)
T
?1/20?2??0???300????=?1500? 0∴Δb'=B-1Δb=??3110??????
?001??150??150???????
C CB
XB
3 X11 0 0
8 0 X2X3
0 0 b X4X5
3 X10 X48 X2
0 1/2 0 -2-200 0 -3 1 0
1 10 2000 0 1 500
检验数 0 0 X50 X4
0 -3/2 0 -2
-1/2 0 -1/4 0 1 100 5
0 -1/2 1 0 1000
15
运筹学 线性规划的对偶理论复习题
