y1 2 y2 y3 2
对偶问题
:
st
3 4
y1 y1

y2 4 y3 2 3y2 3y3 4
y1 0, y2 0, y3无限制
page 3 9 September 2019
3
School of Management
运筹学教程
第二章习题解答
18
School of Management
运筹学教程
第二章习题解答
minW 8 y1 6 y2 6 y3 9 y4
y1 2 y2 y4 2
(1)对偶问题：3 y1
y2 y3 y4 y3 y4 1
1

y1 y3 1
y j 0, ( j 1,,4)
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 3 2 2 0 0 0
┆┆ ┆
┆┆┆┆
┆
┆
0 X4 5/4 0
3 X 25/ 1 page 11
9 September 2019
1
0 (d) (l) - -
1/ 1/
page 13 9 September 2019
13
School of Management
运筹学教程
第二章习题解答
2.5 给出线性规划问题
max Z x1 2x2 x3
x1 x2 x3 2
st 2x1x1x2x2x3x31 2
.
x1 0, x2 0, x3无约束
运筹学教程
第二章习题解答
2.8 已知线性规划问题A和B如下：
问题A
n
min Z c j x j
影子价格
j 1
n
a1 j x j b1
y1
j 1
st.
n j 1
a2
j
x
j
b2
y2
n
a3 j x j b3
y3
j 1
x j 0, ( j 1,, n)
解：
l=1, k=0 , h=-1/2, a=2,
c=3, b=10, e=5/4, f=-1/2,
d=1/4, g=-3/4, i=-1/4, j=-1/4
page 10 9 September 2019
10
School of Management
运筹学教程
Cj→
32 2 0 0 0
CB 基 b X1 X2 X3 X4 X5 X6
page 20 9 September 2019
20
School of Management
运筹学教程
第二章习题解答
问题B
n
min Z c j x j
j 1


n
5a1 j x j
5b1
j1
st.
n j 1
1 5
a2 j x j

1 5 b2
n
(a3 j 3a1 j )x j b3 3b1
n
xij ai
(i 1,, m)
(3) j1
st

n
xij bj
( j 1,, n)
.
i1
xij 0 (i 1,, m, j 1,, n)

m
n
maxW ai yi bj y jm
对偶问题：
st.
i 1
44
0 (e) 0
3/ (i) 11
School of Management
运筹学教程
第二章习题解答
2.4 给出线性规划问题
min Z 2x1 3x2 5x3 6x4
st.
x1 2 x1
2
x2 x2
3x3 x4 x3 3x4

2 3

x j 0, ( j 1,,4)
运筹学教程
第二章习题解答
minW b1 y1 b2 y2 bm ym


m
aij yi
cj
( j 1,2,, n1)
对偶问题：
st

i 1 m
aij
yi

cj
( j n1 1, n1 2,, n)
i1 yi 0
(i 1,, m1)
(i 1,, m1 m)
(4)
j1
st

n
aij x j
bi
(i m1 1, m1 2,, m)
j1

x
j

0
( j 1,, n1, n), x j无约束（j n1 1,, n）
page 6 9 September 2019
6
School of Management
(2)如果线性规划的对偶问题无可行解， 则原问题也一定无可行解；
答：不对！道理同上。
page 8 9 September 2019
8
School of Management
运筹学教程
第二章习题解答
(3)在互为对偶的一对原问题与对偶问题 中，不管原问题是求极大或极小，原问题可行 解的目标函数值一定不超过其对偶问题可行解 的目标函数值；
st.
2x1 x2 6 x2 x3 x4 6

x1 x2 x3 9
x j 0, ( j 1,,4)
要求：(1)写出其对偶问题；(2)已知原问 题最优解为X*=(2，2，4，0)，试根据对偶理 论，直接求出对偶问题的最优解。
page 18 9 September 2019
(2)已知原问题最优解为X*=(2，2，4，
0)，代入原问题，第4个约束不等式成立，故
y4=0。有由于x1,x2,x3大于0，上面对偶问题前 3个约束取等号，故得到最优解： y1=4/5,
page 19y2,=3/5, y3=1, y4=0
19
9 September 2019
School of Management
运筹学教程
第二章习题解答
2.6 已知线性规划问题
max Z x1 x2 5x3 6x4
st
.
x1 x2 x3 2 2x1 x2 x3 1

x
j

0, (
j
1,,3)
试根据对偶问题性质证明上述线性规划 问题目标函数值无界。
page 16 9 September 2019
(1)写出其对偶问题；(2)利用对偶问题性质证明 原问题目标函数值z≤1。
page 14 9 September 2019
14
School of Management
运筹学教程
第二章习题解答
min W 2 y1 y2 2 y3
y1 y2 y3 1
(1)对偶问题：st
y1y1
max Z 5x1 6x2 3x3
x1 2x2 2x3 5
(2)
st
4 xx1175xx22
3x3 3x3
3 8
x1无约束, x2 , 0, x3 0
maxW 5 y1 3y2 8 y3
y1 y2 4 y3 5
运筹学教程
第二章习题解答
2.1 写出下列线性规划问题的对偶问题。
min Z 2x1 2x2 4x3
x1 3x2 4x3 2
(1)
st
2x1x1 4
x2 x2
3x3 3x3

3 5
x1, x2 , 0, x3无约束
maxW 2 y1 3y2 5 y3
(4)
由于(1)和(4)是矛盾约束，故对偶问题 无可行解。所以原问题目标函数值无界。
page 17 9 September 2019
17
School of Management
运筹学教程
第二章习题解答
2.7 给出线性规划问题
min Z 2x1 4x2 x3 x4
x1 3x2 x4 8
(1)对偶问
题： st
.32
y1 y1

y2 y2

3 5

y1
3y2

6
y1 0, y2 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。
y2 y2
y3 y3
2
1
y1 0, y2无约束, y3 0
(2)y1=y3=0,y2=1 时 对 偶 问 题 的 一 个 可 行 解 ， 目 标 函数值为1，故原问题的目标函数值小于等于1。
page 15 9 September 2019
15
School of Management
运筹学教程
同样适合第三版黄皮版
page 1 9 September 2019
1
School of Management
运筹学教程
运筹学教程（第二版） 习题解答
安徽大学管理学院
电话：5108157(H)， 5107443(O)
page 2