School of Management
运筹学教程
第二章习题解答
min W 2 y1 3 y 2
(1) 对偶问题：
y1 2 y 2 2
st
.
2 3
y1 y1
y2 y2
3 5
y1
3 y2
6
y1 0, y 2 0
(2) 最优解是：y1=-8/5,y2=1/5,目标函数值-19/5。
运筹学黄皮版第二章习题答案
电话：5108157(H)，5107443(O) E-mail:
运筹学教程（第二版） 习题解答
安徽大学管理学院 洪文
运筹学教程
第二章习题解答
2.1 写出下列线性规划问题的对偶问题。
min Z 2 x1 2 x2 4 x3
x1 3 x2 4 x3 2
(1)
st
(3)由于 y1=-8/5,y2=1/5都不等于零，原问题中的约束取等号。又上面第4个约束不等 号成立，故x4=0，令x3=0就可以得到最优解： x1=8/5,x2=1/5。
page 13 November 1, 2010
School of Management
运筹学教程
第二章习题解答
2.5 给出线性规划问题
page 8 November 1, 2010
School of Management
运筹学教程
第二章习题解答
(3)在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或极小，原问题可 行解的目标函数值一定不超过其对偶问题可行解的目标函数值；
答：不对！如果原问题是求极小，结论相反。 (4)任何线性规划问题具有惟一的对偶问题。 答：结论正确！
School of Management
运筹学教程
第二章习题解答
m
maxZ cjxj
j1
n
aijxj bi
(i 1,,m1 m)
(4)
j1 st n aijxj bi
(i m1 1,m1 2,,m)
j1
xj 0 ( j 1,,n1, n),xj无约束（ j n1 1,,n）
page 6 November 1, 2010
School of Management
运筹学教程
第二章习题解答
max Z 5x1 6x2 3x3
x1 2x2 2x3 5
(2)
st
4 xx1175xx22
3x3 3x3
3 8
x1无约束, x2 , 0, x3 0
maxW 5y1 3y2 8y3
y1 y2 4y3 5
对偶
问题： st22yy11
d=1/4, g=-3/4, i=-1/4, j=-1/4
page 10 November 1, 2010
School of Management
运筹学教程
Cj→
3
2
2
0
0
0
CB
基
b
X1
X2
X3
X4
X5
X6
0
X1
(b)
1
1
1
1
0
0
0
X2
15 (a) 1
2
0
1
0
0
X3
20
2 (c)
1
0
0
1
Cj－Zj
5y2 3y2
7y3 3y3
6 3
y1无约束, y2 0, y3 0
page 4 November 1, 2010
School of Management
运筹学教程
第二章习题解答
mn
min Z
cij xij
i1 j 1
n
xij ai
(i 1, , m )
(3)
j1
st
n
xij b j
max Z x1 2 x2 x3
x1 x2 x3 2
st
x1 2 x1
x
2
x
2
x
3
x
1 3
2
.
x1 0, x2 0, x3无约束
(1)写出其对偶问题；(2)利用对偶问题性质证明原问题目标函数值z≤1。
2 x1 x1 4
x x
2 2
3x3 3x3
3 5
x1 , x2 , 0, x3无约束
maxW 2y1 3y2 5y3
y1 2y2 y3 2
对偶问题: st34yy11
y2 4y3 2 3y2 3y3 4
y1 0, y2 0, y3无限制
page 3 November 1, 2010
( j 1, , n )
.
i1 xij 0
(i 1, , m , j 1, , n )
m
n
maW x aiyi bjyjm
对偶问 s.t 题 yyii无 y： ji 限 m 1 c制 ii j 1j(,， i1,1n, m ,m,j1, ,n)
page 5 November 1, 2010
page 9 November 1, 2010
School of Management
运筹学教程
第二章习题解答
2.3 已知某求极大化线性规划问题用单纯形法求解时的初始单纯形表及最终 单纯形表如下表所示，求表中各括弧内未知数的值。
解：
l=1, k=0 , h=-1/2, a=2,
c=3, b=10, e=5/4, f=-1/2,
3
2
2
0
0
0
┆┆
┆
┆┆
┆
┆
┆
┆
0
X4
5/4
0
0
(d) (l) -1/4 -1/4
3
X1
25/4
1
0
(e)
0
3/4 (i)
2
X2
5/2
page 11 November 1, 2010
Cj－Zj
0
1
(f)
0 (k) (g)
0
(h) 1/2
0 -5/4 (j) School of Management
运筹学教程
School of Management
运筹学教程
第二章习题解答
2.2 判断下列说法是否正确，为什么? (1)如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解； 答：不对！如原问题是无界解，对偶问题无可行解。 (2)如果线性规划的对偶问题无可行解，则原问题也一定无可行解； 答：不对！道理同上。
School of Management
运筹学教程
第二章习题解答
min j 1,2,,n1)
对偶问题： stim1 aijyi cj
( j n1 1,n1 2,,n)
i1 yi 0
(i 1,,m1)
yi无约束（ j m1 1,,m）
page 7 November 1, 2010
第二章习题解答
2.4 给出线性规划问题
minZ 2x1 3x2 5x3 6x4
st.x21x1 2xx22
3x3 x4 x3 3x4
2 3
xj 0,( j 1,,4)
(1)写出其对偶问题；(2)用图解法求解对偶问题；(3)利用(2)的结果及根据对偶问题性 质写出原问题最优解。
page 12 November 1, 2010