运筹学作业题.doc

( 密封线内不答题)

教学中心: 专业层次: 姓名: 学号: 座号:
华南理工大学网络教育学院

教学中心: 专业层次: 姓名: 学号: 座号:
2013–2014学年度第一学期
《运筹学》作业

1. 某工厂用ABCD四种原料生产甲乙两种产品,生产甲和乙所需的各种原料的数量及在一个计划期内各种原料的现有数量见下表。又知每单位产品甲乙分别可获利400元和600元,设一个计划期内生产甲种产品个单位,乙种产品个单位,试写出以总利润为目标的线性规划模型,并化为标准型。
产品
所需原料
A
B
C
D
甲
乙
4
4
4
2
1
0
2
4
现有原料数量
28
20
32
24
答案: ,
Ⅰ、Ⅱ两种产品,已知生产单位产品所需的设备台时及A、B两种原材料的消耗,如下表所示:
I
II
总量
设备
1台时/件
2台时/件
8台时
原材料A
4 kg/件
0 kg/件
16kg
原材料B
0 kg/件
4 kg/件
12kg
每生产一件产品I可获利1元,每生产一件产品II可获利3元,如何安排生产计划使获利最大?(有多种方法选择您熟悉的一种)(10分)
解,由图解法求出可行域各顶点的值比较,得安排生产Ⅰ产品2件,、Ⅱ产品3件,获利最大为11元。或加松弛变量用单纯形表计算。
3、用单纯形法求解
解先化为标准形式,再列单纯形表计算如下
1
2
1
0
0
CB
基XB
常数
0
15
2
-3
2
1
0
0
20→
1/3
1
5
0
1
,检
0
1
2↑
1
0
0
0
75→
3
0
17
1
3
0
20
1/3
1
5
0
1
,检验数
-40
1/3↑
0
-9
0
-2
0
25
1
0
17/3
1/3
1
0
35/3
0
1
28/9
-1/9
2/3
最优了,检验数
-145/3
0
0
-98/9
-1/9
-7/3
得到最优解为
4、写出线性规划问题的对偶问题
解对偶问题为
5、已知线性规划问题
用单纯形法求解,得到最终单纯形表如下。试求出各待定常数的值。
0
0
CB
基XB
常数
3/2
1
0
1
1/2
-1/2
2
1/2
1
0
-1
2
检验数
-3
0
0
0
-4
解

从而
再由,从而
,解得
6、已知线性规划问题,其对偶问题的最优解为,试用对偶问题的性质,求原问题的最优解。
解原问题的对偶问题为,将代入第一、二个约束成为严格等式,由互补松弛性质得。又因,由互补松弛性质,进而可得,解之。原问题的最优解为,最优值为44。
7、已知世界6大城市:Pe,Pa,T,M,N,L。试在下表所示交通网络的数据中确定最小树。
Pe
T
Pa
M
N
L
Pe
13
51
77
68
50
T
13
60
70
67
59
Pa
51
60
57
36
2
M
77
70
57
20
55
N
68
67
36
2