运筹学作业2（第二章部分习题）答案
2．4 给出线性规划问题
123412341234min 2356232..
2330,1,2,3,4
j z x x x x x x x x s t x x x x x j =+++⎧+++≥⎪
-+-+≤-⎨⎪≥=⎩
（1）写出其对偶问题；（2）用图解法解对偶问题；（3）利用（2）的结果及根据对偶问
题性质写出原问题的最优解。

解：（1）原问题的对偶问题为：
12
12121212
12max 2322
23..
35
36
0,0
w y y y y y y s t y y y y y y =--≤⎧⎪+≤⎪⎪
-≤⎨⎪+≤⎪⎪≥≤⎩ 或者等价变形为：
12
12121212
12max 232223..3536
0,0
w y y y y y y s t y y y y y y =++≤⎧⎪-≤⎪⎪
+≤⎨⎪-≤⎪⎪≥≥⎩
（2）用图解法求解对偶问题
12
12121212
max 2322
23..
3536
w y y y y y y s t y y y y =++≤⎧⎪-≤⎪⎪
+≤⎨⎪-≤
如图示，可行区域为四边形OABC ，最优顶点为B 点，即(1.6,0.2)y *
=， 3.8w *
=
（3）利用互补松紧定理及（2）的结果求解原问题：
设原问题的最优解为(
)1
23
4x x x x x **
***=。

由于121.60,
0.20y y *
*
=>=>，故在最优解()12
3
4x x x x x **
*
**=处有：
1234
1234232
2330,1,2,3,4j x x x x x x x x x j ********
*
⎧+++=⎪⎪-+-+=-⎨⎪≥=⎪⎩
又因对偶问题第4个约束方程为：1.6-0.6=1<6，故40x *
=，代入上式得到：
123
123232
230,1,2,3,4j
x x x x x x x j ******
*
⎧++=⎪⎪-+-=-⎨⎪≥=⎪⎩ 原问题有无穷多个最优解。

令30x *=得到解为1 1.6x *=，20.2x *=
即()1.60.200x *
=， 3.8z *
=
2．8题解答见课堂讲解。

2．9 用对偶单纯形法求解下列线性规划问题：
（2）
123
123123123min 524324
..
63510,,0z x x x x x x s t x x x x x x =++++≥⎧⎪
++≥⎨⎪≥⎩
, 解：先将原问题进行标准形化：
1231234123512345max()524324
..
63510,,,,0
z x x x x x x x s t x x x x x x x x x -=---++-=⎧⎪
++-=⎨⎪≥⎩
选45,x x 为基变量，并将问题化为：
1231234123512345max()524324
..
63510,,,,0z x x x x x x x s t x x x x x x x x x -=------+=-⎧⎪
---+=-⎨⎪≥⎩
列表计算如下：
因所有检验数小于等于0且右边常数大于0，故此基可行解为最优解，即
(2/3,2,0),22/2x z **==。