华中科技大学自动化运筹学答案2017
来源：美国移民 发布时间：2020-08-28 点击：
2017 7 年- - 2018 8 学 年 度 第 一 学期
华中科技大学本科生课程考试试卷(A 卷)
课程名称：
运筹学（一）
课程类别
□公共课
■专业课
考试形式
□开卷
■闭卷
所在院系：
自动化学院
专业及班级：
考试日期：
2017 7 .11. 18
学
号：
姓名：
任课教师：
题号
一
二
三
四
五
六
总分
分数
一、（20 分）
试求解如下线性规划问题 1 2 31 2 31 2 31 31 2 3max 2 372 3 5 8. .2 1, , 0z x x xx x xx x xstx xx x x
解：将模型化为如下：
1 2 31 2 3 41 2 3 51 3 6 7max 2 3= 72 3 5 + 8. .2 10, 1,2, ,8iz x x xx x x xx x x xstx x x xx i 列出初始单纯形表
得分 评卷人
2 1 3 0 0 0 -M
b
1x
2x
3x
4x
5x
6x
7x
0 4x
7 1 1 1 1 0 0 0 7 0 5x
8 2 -3 5 0 1 0 0 4 -M 7x
1 [1] 0 -2 0 0 -1 1 1
j jc z
2+M 1 3-2M 0 0 -M 0
选择1x 为换入变量，7x 为换出变量，进行迭代得到：
2 1 3 0 0 0 -M
b
1x
2x
3x
4x
5x
6x
7x
0 4x
6 0 1 3 1 0 1 -1 2 0 5x
6 0 -3 [9] 0 1 2 -2 6/9 2 1x
1 1 0 -2 0 0 -1 1
j jc z
0 1 7 0 0 2 -M-2
选择3x 为换入变量，5x 为换出变量，进行迭代得到：
2 1 3 0 0 0 -M
b
1x
2x
3x
4x
5x
6x
7x
0 4x
4 0 [2] 0 1 -1/3 1/3 -1/3
3 3x
2/3 0 -1/3 1 0 1/9 2/9 -2/9
2 1x
7/3 1 -2/3 0 0 2/9 -5/9 5/9
j jc z
0 10/3 0 0 -7/9 4/9 -M-4/9
选择2x 为换入变量，4x 为换出变量，进行迭代得到：
2 1 3 0 0 0 -M
b
1x
2x
3x
4x
5x
6x
7x
1 2x
2 0 1 0 1/2 -1/6 1/6 -1/6
3 3x
4/3 0 0 1 1/6 1/18 5/18 -5/18
2 1x
11/3 1 0 0 1/3 1/9 -4/9 4/9
j jc z
0 0 0 -5/3 -2/9 -5/9 -M+5/9
所有检验数都为复数，得到最优解为：1 2 3=11/3 2, 4/3 x x x ，
最优值为 ：
40/3 z
二、 （ （15 分）
已知线性规划问题如下：
221 21 211 2max
35 10
501
s.t.
4
0, 0xz x xx xx xx x 已知该问题的最优解为 (2,4) ，利用对偶性质写出对偶问题的最优解。
解：该问题的对偶问题为：
得分 评卷人
321 21 21231 31min
50 45s.t.
100, 0, 03w y y yy yy y yy y y 将*(2,4) x 代入原问题可知：1 21 x x 为严格不等式，所以2*0 y 。
由对偶问题性质可知：
1 31** *51013yy y（或者311** *550 4114yy y，或者1133****1050 4314y yy y ）
解之得：1*1/5 y ，3*1 y 。
。
所以，对偶问题的最优解是*(1/5,0,1) y ，最优值 min
14 w 。
。
三 、（15 分）已知线性规划问题及其最优单纯形表（见表1）
332 321 21 2111 2 33max
+4
2
+
s.t.
+
0,92+ 4 0, 0z x x xx x xx x xx xx x xx 表 表 1 jC
－1 －1 4 0 0 0 BC
Bx
b
1x
2x
3x
4x
5x
6x
－1 1x
1/3 1 －1/3 0 1/3 0 －2/3 0 5x
6 0 2 0 0 1 1 得分 评卷人
4 3x
13/3 0 2/3 1 1/3 0 1/3 j
0 －4 0 －1 0 －2 若约束的右端列向量924b 变成列向量323 ，在上述最优单纯形表的基础上求新问题的最优解。
解：先求解最优单纯形表中列向量 b 所对应的解变为 11/3 0 2/3 3 1( ) 0 1 1 2 51/3 0 1/3 3 2BX B b b 因为－1 小于 0，用对偶单纯形法继续迭代：
jC
－1 －1 4 0 0 0 BC
Bx
b
1x
2x
3x
4x
5x
6x
－1 1x
－1 1 －1/3 0 1/3 0 [－2/3] 0 5x
5 0 2 0 0 1 1 4 3x
2 0 2/3 1 1/3 0 1/3 j
0 －4 0 －1 0 －2
经过一次迭代得到最优单纯形表
jC
－1 －1 4 0 0 0 BC
Bx
b
1x
2x
3x
4x
5x
6x
0 6x
3/2 －3/2 1/2 0 －1/2 0 1 0 5x
7/2 3/2 3/2 0 1/2 1 0 4 3x
3/2 1/2 1/2 1 1/2 0 0 j
－3 －3 0 －2 0 0
因此，新问题的最优解为*(0,0,3/ 2) x ，最优值*max
6 z 。
四 ． （0 20 分）已知某运输问题的产销平衡表和单位运价表如表 2 所示，试求最优的运输调拨方案。
表 2
销地产地 B1 B2 B3 B4 B5 产量 A1 10 2 3 15 9 25 A2 5 10 15 2 4 30 A3 15 5 14 7 15 22 A4 20 15 13 M 8 28 销量 20 18 30 12 25
解：
vogel 法确定初始解
销地 产地 B1 B2 B3 B4 B5 行差 A1 10 2 3 15 9 1 A2 5 10 15 2 4 2 A3 15 5 14 7 15 2 A4 20 15 13 M 8 5 得分 评卷人
列差 5 3 10 5 4
第一步
销地 产地 B1 B2 B3 B4 B5 产量 A1
25
25 A2
30 A3
22 A4
28 销量 20 18 30 12 25
调整行差、列差
销地 产地 B1 B2 B3 B4 B5 行差 A1 10 2 3 15 9
A2 5 10 15 2 4 2 A3 15 5 14 7 15 2 A4 20 15 13 M 8 5 列差 10 5 1 5 4
第二步：
销地 产地 B1 B2 B3 B4 B5 产量 A1
25
25 A2 20
30 A3
22 A4
28 销量 20 18 30 12 25
调整行差、列差
销地 产地 B1 B2 B3 B4 B5 行差 A1 10 2 3 15 9
A2 5 10 15 2 4 2 A3 15 5 14 7 15 2 A4 20 15 13 M 8 5 列差
5 1 5 4
第三步：
销地 产地 B1 B2 B3 B4 B5 产量 A1
25
25 A2 20
10
30 A3
22 A4
30 销量 20 20 30 12 25
调整行差、列差
销地 产地 B1 B2 B3 B4 B5 行差 A1 10 2 3 15 9 1 A2 5 10 15 2 4
A3 15 5 14 7 15 2 A4 20 15 13 M 8 5 列差 10 10 1 M 7
第三步：
销地 产地 B1 B2 B3 B4 B5 产量 A1
25
25 A2 20
10
30 A3
2
22 A4
28 销量 20 18 30 12 25
调整行差、列差
销地 产地 B1 B2 B3 B4 B5 行差 A1 10 2 3 15 9 1 A2 5 10 15 2 4 2 A3 15 5 14 7 15 9 A4 20 15 13 M 8 5 列差 10 10 1
7
第四步：
销地 产地 B1 B2 B3 B4 B5 产量 A1
25
25 A2 20
10
30 A3
18
2
22 A4
28 销量 20 18 30 12 25
调整行差、列差
销地 产地 B1 B2 B3 B4 B5 行差 A1 10 2 3 15 9 1 A2 5 10 15 2 4 2 A3 15 5 14 7 15 1 A4 20 15 13 M 8 5 列差
1
7
第五步，即为初始解：
销地 产地 B1 B2 B3 B4 B5 产量 A1
25
25 A2 20
10
30 A3
18 2 2
22 A4
3
25 28 销量 20 18 30 12 25
判断解是不是最优解，用位势法。
销地 产地 B1 B2 B3 B4 B5 位势 A1 10，11
2， 8 3 15， 19 9， 11 0 A2 5 10， 10 15， 6 2 4， 0 6 A3 15， 5 14 7 15， 11
5 6 A4 20， 11 15， 11 13 M， M 8 10 位势 -1 -6 3 -4 -2
该解已是最优解。
最优值为：z=3*25+5*20+2*10+5*18+14*2+7*2+13*3+8*25=566
五、（5 15 分）
试建立如下问题的目标规划模型 （只建模不求解）
。
产 某工厂生产 I,II 两种产品，已知相关数据见表 3 ，在工厂决策时，依次考虑如下的条件：
1) 根据市场信息，产品 I 的销售量有下降的趋势，故考虑产品 I 的产量不品 大于产品 II ； 2) 超过计划供应的原材料时，需用高价采购，会使成本大幅度增加； 3) 应尽可能充分利用设备台时，但不希望加班； 4) 应尽可能达到并超过计划利润指标 56 元。
表 表 3
I II 拥有量 原材料（kg ）
2 1 11 设备（hr ）
1 2 13 利润（元/ 件）
8 10
解：设1 2, x x
分别表示产品 I, II 的产量，其目标规划模型如下：
1 1 2 2 3 3 3 4 41 2 1 11 2 2 21 2 3 31 2 4 41 2min +02 11. . 2 138 10 56, , , 0, 1,2,3,4i iz Pd Pd P d d Pdx x d dx x d dst x x d dx x d dx x d d i
得分 评卷人
六、（15 分）
有甲乙丙丁 4 个工人，要分别指派他们完成 ABCD 不同的 4 项工作，每人做各项工作所消耗的时间如表 4 所示。应如何指派工作，才能使总的消耗时间最少？ 表 4
工作 工人 A B C D 甲 甲 4 10 6 7 乙 乙 2 7 6 3 丙 丙 3 3 4 4 丁 丁 4 6 6 3
解：