page 5 9/14/2020
School of Management
运筹学教程
第二章习题解答
minW b1y1 b2y2 bmym
m
aijyi
cj
( j 1,2,,n1)
对偶问题： stim1 aijyi cj
( j n1 1,n1 2,,n)
i1 yi 0
(i 1,,m1)
yi无约束（ j m1 1,,m）
maxW 2y1 3y2 5y3
y1 2y2 y3 2
对偶问题: st34yy11
y2 4y3 2 3y2 3y3 4
y1 0, y2 0, y3无限制
School of Management
运筹学教程
page 3 9/14/2020
第二章习题解答
max Z 5x1 6x2 3x3
0 X3 20 2 (c) 1 0 0 1
Cj－Zj
32 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 0 1 (f) 0 (h) 1/2
Cj－Zj
ቤተ መጻሕፍቲ ባይዱ
0 (k) (g) 0 -5/4 (j)
page 13 9/14/2020
School of Management
运筹学教程
第二章习题解答
minW 2y1 y2 2y3
page 8 9/14/2020
School of Management
运筹学教程
第二章习题解答
2.3 已知某求极大化线性规划问题用单纯形 法求解时的初始单纯形表及最终单纯形表如下表 所示，求表中各括弧内未知数的值。
解：
l=1, k=0 , h=-1/2, a=2,
c=3, b=10, e=5/4, f=-1/2,
page 4 9/14/2020
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）
d=1/4, g=-3/4, i=-1/4, j=-1/4
page 9 9/14/2020
School of Management
运筹学教程
Cj→ CB 基 b
32 2 0 0 0 X1 X2 X3 X4 X5 X6
0 X1 (b) 1 1 1 1 0 0
0 X2 15 (a) 1 2 0 1 0
page 11 9/14/2020
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。 (3)由于 y1=-8/5,y2=1/5都不等于零，原问题中的约 束取等号。又上面第4个约束不等号成立，故x4=0，令 x3=0就可以得到最优解： x1=8/5,x2=1/5。
page 10 9/14/2020
School of Management
运筹学教程
第二章习题解答
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 2 9/14/2020
2.1 写出下列线性规划问题的对偶问题。
min Z 2 x1 2 x2 4 x3
x1 3 x2 4 x3 2
(1)
st
2 x1 x1 4
x x
2 2
3x3 3x3
3 5
x1 , x2 , 0, x3无约束
答：不对！道理同上。
page 7 9/14/2020
School of Management
运筹学教程
第二章习题解答
(3)在互为对偶的一对原问题与对偶问题中，不管 原问题是求极大或极小，原问题可行解的目标函数值 一定不超过其对偶问题可行解的目标函数值；
答：不对！如果原问题是求极小，结论相反。
(4)任何线性规划问题具有惟一的对偶问题。 答：结论正确！
page 12 9/14/2020
School of Management
运筹学教程
第二章习题解答
2.5 给出线性规划问题
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。
运筹学教程
第二章习题解答
mn
min Z
cij xij
i 1 j 1
n
xij ai
(i 1, , m )
(3)
j1
st
n
xij b j
( 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(, i， 1,1n, m ,m,j1, ,n)
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
5y2 3y2
7y3 3y3
6 3
y1无约束, y2 0, y3 0
School of Management
page 6 9/14/2020
School of Management
运筹学教程
第二章习题解答
2.2 判断下列说法是否正确，为什么?
(1)如果线性规划的原问题存在可行解，则其对偶 问题也一定存在可行解；
答：不对！如原问题是无界解，对偶问题无可行 解。
(2)如果线性规划的对偶问题无可行解，则原问题 也一定无可行解；