广东海洋大学运筹学习题解答

要求： （1）写出其对偶问题； （2）已知原问题最优解为 X 论，直接写出对偶问题的最优解。 解： （1）对偶规划为： min w 8 y1 6 y 2 6 y 3 9 y 4

(2, 2, 4, 0) T , 试根据对偶理
y4 2 y1 2 y 2 3 y y y y 4 1 2 3 4 st. y3 y 4 1 y y3 1 1 y i 0, (i 1, 2, 3, 4)
要求确定既满足动物生长的营养需要，又使费用最省的选用饲料的方案。 （仅建模型） 解：设 x i (i
1,2,3,4,5) 分别代表 5 种饲料的采购数，则模型为：
min z 0.2 x1 0.7 x 2 0.4 x3 0.3 x 4 0.8 x5
st.
3 x1 2 x 2 x3 6 x 4 18 x5 700 x 0.5 x 0.2 x 2 x 0.5 x 30 1 2 3 4 5 0.5 x1 x 2 0.2 x3 2 x 4 0.8 x5 100 xi 0, i 1, 2, 3, 4, 5.
C( X X 0 ) C( X X 0 ) 0 (C C )( X X 0 ) 0.
1.13 某饲养场饲养动物出售，设每头动物每天至少需要 700 克蛋白质、30 克矿物质、100 毫克维
生素。现有五种饲料可供选用，各种饲料每 kg 营养成分含量及单价如表所示： 饲料 1 2 3 4 5 蛋白质(g) 3 2 1 6 18 矿物质(g) 1 0．5 0．2 2 0．5 维生素(mg) 0．5 1．0 0．2 2 0．8 价格(元/kg) 0．2 0．7 0．4 0．3 0．8

3 14 2 7 25 14
故所求惟一最优解为： x1
3 1 1, x2 , max z 17 . 2 2
1.10
设
若目标函数中用 C 代替 C X 0 是线性规划问题 max z CX , AX b, X 0 的最优解。
后，问题的最优解变为
X 。求证： (C C )( X X 0 ) 0 。
x6
[2]
1 -2

故最优计划为 A, B, C , D 的产量各为 0，0，5，
5 5 1 , 最大利润为 z 4 5 3 27 元。 2 2 2 3 （4） 解法一 从（1）中的最终表知道，材料的影子价格为 0.6 0.4 （已知的市 5
场价格） 。故应再购进原材料，设再购 单位（ 0) 。
习题答案（2）
2.5 给出线性规划问题 max z x1 2 x 2 x3 x1 x 2 x3 2 x x x 1 1 2 3 st. 2 x1 x 2 x3 2 x1 0, x 2 0
（1） 写出其对偶问题； （2）利用对偶问题证明原问题目标函数值 z 1. 解： （1）对偶规划为：
3 x3 3 x1 2 x 2 2 x3 5 x 0,(i 1, 2, 3) i
解：原规划化为标准规划为： max w max( z ) 4 x1 12 x 2 18 x3
3 x3 x 4 3 x1 st. 2 x 2 2 x3 x 5 5 x 0,(i 1, 2, 3, 4, 5) i
解：令 x1
则所求规划的标准形式为：
' " max z ' 2 x1' 2 x2 3 x3 3 x3 M x4 0 x5
st.

' " x1' x2 x3 x3 x4 ' 1 ' 3 " 3 " 3
4
2 x x2 x x x5 6 x ' 0, x 0, x ' 0, x 0, x 0, x 0 2 3 4 5 1
min w 2 y1 y 2 2 y 3 y1 y 2 2 y 3 1 st. y1 y 2 y 3 2 y1 y 2 y 3 1 y1 0, y 3 0
（2） 由（1）易知 y 0, 1, 1 是对偶规划的一个可行解，且 w 1 ，
又X

(2, 2, 4, 0) T 代入原规划中，第 4 个约束成为严格不等式，即
左边= x1 x 2 x3 8 9 右边

由互补松弛性质知： y 4 0 故对偶规划的最优解为： Y ( ,


4 3 , 1, 0). 5 5
2 .9
用对偶单纯形法求解线性规划问题 min z 4 x1 12 x 2 18 x3
1.4 用单纯形法求解线性规划问题：
max z 10 x1 5 x2
st.
3 x1 4 x2 9 5 x1 2 x2 8 x 0, x 0 2 1 max z 2 x1 x2
解：将其化为标准形式为：
st.
9 3 x1 5 x2 x3 x4 8 5 x1 2 x2 x 0, x 0, x 0, x 0 2 3 4 1 b x1
（3） 设新产品 D 的产量为 x 6 。
1 因为 c 6 z 6 3 C B B 2 3 ( 5 , 5 ) 2 3 5 5 0, 1 故应生产 D ，最终表中应增加一列，即 B 2 4
用对偶单纯形法列表计算如下：
cj CB
0 0 基
4 b 3 5 x1 1
0
12 x2
0
18 x3 3 2 18 [ 3]
1
0
0
x4
1 0 0 1 0 0
x5
0 1 0 0
x4 x5 cj zj
[ 2] 12
0 1 0 0
4 3 5 2 1
0
0
x4 x2 cj zj
P4
P5 ) P4 P5 )
(1, 0, 0) (3 , 4) B 1 ( P2
1 1 1 3= (1, 0, 0) (3 , 4) 3 3 1 2 1 5 5 1 1 1 3 1 （1 , 0, 0) -（ 3 , , ) 3 5 3 5 3 1 1 1 3 1 （-2+ , , ) 3 5 3 5 3 1 2 3 0 3 9 1 1 解 0 得 ， 5 5 5 3 3 1 0 5 3 3 9 12 24 ] 上变动是，上述最优计划不变。 即知 A 的利润在 [3 , 3 ] [ , 5 5 5 5
12

1 2
4
1
6
1
6
0
18
x3
1 3

1 3
12
x2 cj zj
3 2

1 3
1 0
0 0
1 3 2

1 2
2 3 T , 1) , 2
6
故最优解为： X

(0,
z min z 36.
2.14 某厂生产 A, B, C 三种产品，其所需劳动力、材料等有关数据见下表。要求：
（2）记 Y ( y1 , y 2 , y 3 , y 4 ) 为对偶规划的最优解，由互补松弛性质知， 在 X 中，因 x1 2 0,
x2 2 0, x3 4 0,
从而 Y 使得对偶规划的前三个约束成为等式，即
y1 2 y 2 y4 2 3 y1 y 2 y 3 y 4 4 y3 y4 1
证明：
X 0 、 X 在目标函数的系数变化之前之后都是问题的可行解，故有 CX 0 CX ，即 C ( X 0 X ) 0, C( X X 0 ) 0
即 （1） （2）
同理
C X C X 0,
（1）+（2） 即
C( X X 0 ) 0
T
根据对偶理论
max z w ，可以推知原目标函数值 z 1.
2.7 给出线性规划问题 max z 2 x1 4 x 2 x3 x 4 x4 8 x1 3 x 2 2 x x 6 1 2 x 2 x3 x 4 6 st. x x x 9 2 3 1 x j 0, ( j 1,2,3,4)
15 45 30 6
x2
3 4 1 -1
x3
5 [5] 4 0
x4
1 0 0 1
x5
0 1 0 -1
3
3 [3]
x3 cj zj x1 x3 cj zj
6
3 5 3 5
1 0 0
5 3
4 5 11 5 1 3
1 -2
1
0 0
0
0 1 0
1 3 1 5 1 5
1 5 4 5 1 3 2 5 3 5
A
B
C
可用单位
B, C 各生产 x1 , x 2 , x3 件。有 min z 3 x1 x 2 4 x3 6 x1 3 x 2 5 x3 45 st. 3 x1 4 x 2 5 x3 30 x 0, ( j 1, 2, 3) j
列表计算
x1 x4 x5 cj zj x4
习题解答（1） 1.2 将线性规划问题化为标准形式
min z 2 x1 2 x2 3 x3
st.
x1 x2 x3 4 2 x1 x2 x3 6 x 0, x 0 2 1
' " x3 , z z' x1' , x3 x3
（1）确定获利最大的产品生产计划； （2）产品 A 的利润在什么范围内变动时，上述最 优计划不变； （ 3）如果设计一种新产品 D ，单位劳动力消耗为 8 单位，材料消耗为 2 单位，每件可获利 3 元，问该种产品是否值得生产？（4）如果劳动力数量不增，材料 不足时可以从市场购买，每单位 0。4 元。问该厂要不要购进原材料扩大生产，以购多 少为宜。 消耗定额 资源 劳动力 材料 产品利润（元/件） 解： （1）设 A, 6 3 3 3 4 1 5 5 4 45 30 产品
3 [5] 10 0 1 0
用单纯形法求解的过程见下表 基
x2
4 2 5
x3
1 0 0 1 0 0
x4
0 1 0
x3 x4
9 8
cj zj] 5 2 5
-
3 5 1 5
cj zj
1
-2
x2 x1
3 2
1
0 1 0
1 0 0
cj zj
5 14 1 7 5 14
1 2 2 5 1 10
1 6 13 15 59 30
8
1 3 8
14
1
8
2 5
最终表变为
x1 x1 x3 cj zj x6 x3 5 2
5 5 3 1 0 0
x2 1 3
x3
0 1 0 0 1 0
x4 1 3 1 5 1 5 1 6 1 15 7 30
x5 1 3 2 5 3 5 1 6 4 15 17 30
获利最大的生产计划是 A, B, C 各生产 5 件、 0 件、 3 件， 最大利润为 z 3 5 4 3 27 元。 （2） c1 , 则 c1 3 时，最终表中非基变量 x 2 , x 4 , x5 的检验数为
( 2 , 4 , 5 ) (1, 0, 0) C B B 1 ( P2