j 1 n n
影子价格
y1 a1 j x j b1 jn1 y2 a2 j x j b2 st . j 1 n y3 a3 j x j b3 j 1 x j 0, ( j 1, , n)
第二章习题解答
问题B min Z c j x j
n (i 1, , m1 m) aij x j bi 1 jn ( 4) st aij x j bi (i m1 1, m1 2, , m) j 1 x j 0 ( j 1, , n1 , n), x j 无约束（j n1 1, , n）

* y2
* y3

y2


第二章习题解答
2.9 用对偶单纯形法求解下列线性规划问题。
(1)
min Z 4 x1 12x2 18x3 x1 3 x3 3 st . 2 x2 2 x3 5 x 0, ( j 1, ,3) j
(2)
min Z 5 x1 2 x2 4 x3 3x1 x2 2 x3 4 st.6 x1 3x2 5 x3 10 x 0, ( j 1,,3) j
最优解：x1 2 / 3, x2 2, x3 0
第二章习题解答
2.10 考虑如下线性规划问题：
min Z 60x1 40x2 80x3 3x1 2 x2 x3 2 4 x x 3x 4 2 3 st 1 . 2 x1 2 x2 2 x3 3 x1 , x2 , x3 0
第二章习题解答
min Z cij xij
i 1 j 1 m n
(3)
n (i 1, , m) xij ai 1 jn st xij b j ( j 1, , n) . i 1 (i 1, , m, j 1, , n) xij 0
第二章习题解答
(1) min Z 4 x1 12x2 18x3 x1 3 x3 3 st . 2 x2 3 x3 5 x 0, ( j 1, ,3) j
最优解：x1 0, x2 3 / 2, x3 1
( 2)
min Z 5 x1 2 x2 4 x3 3 x1 x2 2 x3 4 st .6 x1 3 x2 5 x3 10 x 0, ( j 1, ,3) j
maxW ai yi b j y j m 对偶问题： yi y j m cij (i 1,, m, j 1,, n) st. yi 无限制，i 1,, n m
i 1 j 1
m
n
第二章习题解答
max Z c j x j
j 1 m
第二章习题解答
2.3 已知某求极大化线性规划问题用单纯形 法求解时的初始单纯形表及最终单纯形表如下表 所示，求表中各括弧内未知数的值。 解： 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
(2)已知原问题最优解为X*=(2，2，4，0)，代入原 问题，第4个约束不等式成立，故y4=0。有由于x1,x2,x3 大于0，上面对偶问题前3个约束取等号，故得到最优 解： y1=4/5, y2,=3/5, y3=1, y4=0
第二章习题解答
2.8 已知线性规划问题A和B如下：
问题A min Z c j x j
第二章习题解答
2.1 写出下列线性规划问题的对偶问题。
min Z 2 x1 2 x2 4 x3 x1 3 x2 4 x3 2 2 x x 3 x 3 2 3 st 1 x1 4 x2 3 x3 5 x1 , x2 , 0, x3无约束
CB
0 0 0
┆ 0
Cj→ 基 X1 X2 X3b3 X12 X2
2 X3
0 X4
0 X5
0 X6
(b) 15 20
┆ 5/4
Cj－Zj
┆ X4
1 1 (a) 1 2 (c) 3 2
┆ ┆ 0 0
1 2 1 2
┆ (d)
1 0 0 0
0 1 0 0
0 0 1 0
┆ ┆ ┆ (l) -1/4 -1/4
由于(1)和(4)是矛盾约束，故对偶问题无可行解。 所以原问题目标函数值无界。
第二章习题解答
2.7 给出线性规划问题 min Z 2 x1 4 x2 x3 x4 x1 3 x2 x4 8 2 x1 x2 6 st . x2 x3 x4 6 x x x 9 2 3 1 x j 0, ( j 1, ,4)
要求：(1)写出其对偶问题；(2)已知原问题最优解 为X*=(2，2，4，0)，试根据对偶理论，直接求出对偶 问题的最优解。
第二章习题解答
minW 8 y1 6 y2 6 y3 9 y4 y1 2 y2 y4 2 3 y y y y 1 1 2 3 4 (1)对偶问题： y3 y 4 1 y1 y3 1 y j 0, ( j 1, ,4)
(1)写出其对偶问题；(2)用图解法求解对偶问题； (3)利用(2)的结果及根据对偶问题性质写出原问题最优 解。
第二章习题解答
m inW 2 y1 3 y 2 y1 2 y 2 2 2 y y 3 1 2 (1)对偶问题： st . 3 y1 y 2 5 y 3 y 6 2 1 y1 0, y 2 0
第二章习题解答
2.2 判断下列说法是否正确，为什么? (1)如果线性规划的原问题存在可行解，则其对偶 问题也一定存在可行解； 答：不对！如原问题是无界解，对偶问题无可行 解。 (2)如果线性规划的对偶问题无可行解，则原问题 也一定无可行解； 答：不对！道理同上。
第二章习题解答
(3)在互为对偶的一对原问题与对偶问题中，不管 原问题是求极大或极小，原问题可行解的目标函数值 一定不超过其对偶问题可行解的目标函数值； 答：不对！如果原问题是求极小，结论相反。 (4)任何线性规划问题具有惟一的对偶问题。 答：结论正确！
要求：(1)写出其对偶问题；(2)用对偶单纯形法 求解原问题；(3)用单纯形法求解其对偶问题；(4)对比 (2)与(3)中每步计算得到的结果。
第二章习题解答
(1) maxW 2 y1 4 y2 3 y3 3 y1 4 y2 2 y3 60 2 y y 2 y 40 对偶问题： 1 2 3 st y1 3 y2 2 y3 80 y1 , y2 , y3 0
第二章习题解答
minW b1 y1 b2 y2 bm ym m ( j 1,2,, n1 ) aij yi c j 1 im 对偶问题： ( j n1 1, n1 2,, n) st aij yi c j i 1 yi 0 (i 1,, m1 ) y 无约束（j m 1,, m） 1 i
(1) 写出其对偶问题； (2) 利用对偶问题性质证明 原问题目标函数值z≤1。
第二章习题解答
minW 2 y1 y2 2 y3 y1 y2 y3 1 y y y 2 (1)对偶问题： 1 2 3 st y1 y2 y3 1 y1 0, y2无约束, y3 0
j 1 n
影子价格 y *1 y*2 y *3
n 5a1 j x j 5b1 1 jn 1a x 1b 2j j 2 st . 5 5 j 1 n (a3 j 3a1 j ) x j b3 3b1 j 1 x j 0, ( j 1, , n)
试根据对偶问题性质证明上述线性规划问题目标 函数值无界。
第二章习题解答
解：x1=1,x2=x3=0是原问题的可行解。原问题的对 偶问题为：
minW 2 y1 y2 y1 2 y2 1 (1) y y 1 (2) 1 2 st. (3) y1 y2 0 (4) y1 , y2 0
(2)y1=y3=0,y2=1 时对偶问题的一个可行解，目标 函数值为1，故原问题的目标函数值小于等于1。
第二章习题解答
2.6 已知线性规划问题
max Z x1 x2 5 x3 6 x4 x1 x2 x3 2 st . 2 x1 x2 x3 1 x 0, ( j 1, ,3) j
(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。
第二章习题解答
2.5 给出线性规划问题
max Z x1 2 x2 x3 x1 x2 x3 2 x x x 1 2 3 st 1 . 2 x1 x2 x3 2 x1 0, x2 0, x3无约束
试分别写出yi同y*i(i＝1，2，3)间的关系式。
第二章习题解答
y1 y1
y2 1 0 y3 0 1 3 0 1/ 5 y3 0 3/ 5 0 1 0 0 1 / 5 0 0 * 0 0 5 0 0 1 0 y1 0 0 0 1 0 0 1 0 0 * * * 5 0 y1 y2 y3 0 0
(1)
maxW 2 y1 3 y2 5 y3 y1 2 y2 y3 2 对偶问题: 3 y1 y2 4 y3 2 st 4 y1 3 y2 3 y3 4 y1 0, y2 0, y3无限制