运筹学作业2（清华版第二章部分习题）答案
解：根据原一对偶关系表，可得原问题的对偶规划问题为:
m n
maxw
a i U
i i 1
j 1
b j V j
U i V j C
ij
i 1,111 |,m; j 1,川 ,n
2. 2判断下列说法是否正确，为什么？
（1）如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解; 答：错。

运筹学作业2 （第二章部分习题）答案
2. 1题（P. 77）写出下列线性规划问题的对偶问题：
maxz 2x 1 2x 2 4x 3
s.t x 1 3x 2 4x 3 2
(1)
2x 1 x 2 3x 3 3
x 1 4x 2 3x 3 5
x 1 0, x 2
0,x 3无约束
解：根据原一对偶关系表，可得原问题的对偶规划问题为:
maxw 2y 3y 2 5y 3 s.t y i 2y 2 y 3 2
3y i 讨2 4y3 2
4y i
3y 2 3y 3 4
y i 0
，y 2 °』3 0
(2)
min z
qX j
i 1 j 1
qX j a i ,i 1,|| ,m
1 CM b j , j 1,|| ,n
1
0,i 1,|||,m;j 1」||
m n
n
j 1 n
j 1 ,n X j U i 无约束，v j 无约
束
因为：若线性规划的原问题存在可行解，且其对偶问题有可行解，则原问题和可行问题都将有最优解。

但，现实中肯定有一些问题是无最优解的，故本题说法不对。

max z 3 X i X2
例如原问题X i X2 1有可行解，但其对偶问题
s.t. x2 3
X i 0, X2 0
min w y i 3 y 2
y i 3无可行解。

s.t. y i y2 i
y i 0, y2 0
（2）如果线性规划的对偶问题无可行解，则原问题也一定无可行解；
答：错，如（i）中的例子。

（3）在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或求极
小,原问题可行解的目标函数值一定不超过其对偶问题可行解的目标函
数值。

答：错。

正确说法是：在互为对偶的一对原问题与对偶问题中，求极大的问题可行解的目标函数值一定不超过求极小的问题可行解的目标函数值。

（4）任何线性规划问题具有唯一的对偶问题。

答：正确。

2. 5给出线性规划问题
max z X i 2 X2X3
X i X2 X3 2
X i X2 X3 i
s.t.
2 X i X2 X
3 2
X i 0, X2 0, X3 0
写出其对偶问题；（2）禾I」用对偶问题性质证明原问题目标函数值z i
解：（
1）原问题的对偶问题为:
min w 2 y 1 y 2
2 y 3
y 1 y 2 y 3 1 s.t.
y 1 y 2 y 3
2 y 1 y 2 y
3 1
y 1
0,讨2无约
束，
y 3 0
(2) 取 y 0 1 1 T , 既y 0, y 2 1,y 3 0,经验证，y 0 1 1T 是对偶 问题的一个可行解，并且 W 1。

由对偶问题的性质可得z w 1
2. 9用对偶单纯形法求解下列线性规划问题:
min z 5x i 2 x 2 4 x 3
解：先将原问题进行标准形化:
max( z) 5x 1 2 x 2 4x 3
3x 1 X 2 2x 3 X 4 4
X 2, X 3, X 4, X 5
max( z) 5x 1 2x 2 4 x 3
X 1 , X 2 , X 3 , X 4 , X 5
列
表
计
算
如
下
:
C j
-5
-2
-4
b C B X B X 1
X 2
X 3
X 4
X 5
0 X 4 -3 -1 -2 1 0 -4 0
X 5
-6 [-3] -5 0 1 -10
C j
-5 -2 -4 0 0
X 4 [-1]
-1/3
1
-1/3
-2/3
(2)
s.t.
3x i X 2 2x 3
4 6 x 1 3x 2 5x 3 10
s.t.
6x 1 3x 2 5x 3 X 5
10
选X 4, X 5为基变量, 并将问题化为:
s.t.
3x 1 X 2 2x 3 X 4
6x 1 3x 2 5x 3 X 5
10
因所有检验数小于等于且右边常数大于,故此基可行解为最优解，即x (2/3,2,0), z 22/2。