武汉科技大学本科历年运筹学试题Word格式.doc
《武汉科技大学本科历年运筹学试题Word格式.doc》由会员分享，可在线阅读，更多相关《武汉科技大学本科历年运筹学试题Word格式.doc（71页珍藏版）》请在冰点文库上搜索。
-5
x2
015/14-3/14
10-1/72/7
3/2
1
005/1425/14
35/2
T0
T1
T2
T0表对应O点；
T1表对应B点；
T2表对应A点，也是最优点。
3.求解：
（10分）
用对偶单纯形法求解为：
52400
x1x2x3x4x5
x5
-3-1-210
-6-3*-501
-4
52400
2
-1*0-1/31-1/3
215/30-1/3
-2/3
10/3
102/302/3
20/3
101/3-11/3
0112-1
2/3
001/311/3
22/3
∴X*=（2/3，2，0）T；
Z*=22/3
（注：
用大M法、两阶段法求解均可）
4.写出线性规划问题：
的对偶规划。
（10分）
原问题的对偶规划为：
5.有一最小化指派问题的系数矩阵如下，试求其最优解。
（10分）
用匈牙利算法求解为：
变换后：
再变换为：
再变换：
∴Z*=28
6.写出函数的梯度和海赛矩阵，并判断其凹凸性。
（10分）
的梯度矩阵为：
的海赛矩阵为：
这里H矩阵的各阶主子式均大于0，所以为严格凸函数。
7.某厂有4台设备，拟分给3个用户（工厂）使用，各用户利用设备提供的盈利如下表。
问如何分配设备才能使总盈利最大？
试建立其动态规划求解模型（可不求解）。
（10分）
用户
设备台数
3
4
6
7
5
根据题意，原问题用动态规划求解模型为：
（1）按用户分为3阶段，K=（1，2，3，4），k=4为终了阶段；
（2）xk：
第k阶段初拥有待分配设备台数；
x1=4，0≤x2≤4，0≤x3≤4，x4=0；
（3）uk：
第k阶段分配给第k用户的设备数，
有：
U1={0,1,2,3,4}，U2={0,1,2,…,x2}，U3={x3};
（4）状态转移方程：
；
（5）阶段指标：
见表，如：
；
（6）递推方程：
（7）边界条件：
。
v6
v5
v4
v3
2,2
5,3
3,0
1,0
5,2
4,3
3,3
v1
v2
8.证明下图所示v1至v6流为最大流。
弧边数字为。
（10分）
证明：
对原流图用标号法找可扩充路有：
（-，∞）
（v1,3）
标号过程进行不下去，即不存在v1-v6的可扩充路，根据可扩充路定理，图示流即为最大流,maxQ=5。
9.下图为求至的最小费用最大流时得到的某一流图，弧边数字为，试构造其费用有向图（流增量图）。
（10分）
v14,4,1v37,4,6v5
8,5,43,0,22,0,35,5,2
v2v4
6,5,1
由原流图可作出其费用有向图为：
v1-1v36v5
-6
-4423-2
-1
v21v4
10.某商行夏季订购一批西瓜，根据以往的经验，西瓜销售量可能为10000、15000、20000、25000kg。
假定西瓜售价为0.35元/kg，商行支出成本为0.25元/kg。
（1）建立益损矩阵；
（3分）
（2）分别用悲观法、乐观法、等可能法和后悔值法确定西瓜订购数量。
（7分）
解:
（1）原问题的益损矩阵为；
αi Sj
10000150002000025000
10000
15000
20000
25000
1000100010001000
-250150015001500
-150025020002000
-2750-10007502500
（2）悲观准则：
∴
乐观准则：
∴
等可能准则：
∴
后悔值准则：
后悔值矩阵为：
则
∴
（答题毕）
2002级（B）
参考答案
1.求解线性规划问题：
的最优解。
（15分）
图解过程如下：
2.写出下述线性规划的对偶规划。
（15分）
；
无限制。
对偶规划为MaxZd=-7w1+14w2+3w3
s.t.w1+6w2+28w3≤5
2w1-3w2+17w3≤-6
-w1+w2-4w3=7
-w1-7w2-2w3=4
w1无限制，w2，w3≥0。
3.某一求目标函数极小值的线性规划问题，用单纯形法求解时得到某一步的单纯形表如下。
问a1、a2、a3、c、d各为何值以及变量x属哪一类性质变量时，
（1）现有的解为唯一最优解；
（2）现有解为最优，但最优解有无穷多个；
（3）存在可行解，但目标函数无界；
（4）此线性规划问题无可行解。
（15分）
基变量
x1x2x3x4x5
-13100
a14010
a2a3001
d
cj-zj
c2000
（1）d≥0，c＞0，x3，x4，x5为非人工变量；
（2）d≥0，c=0，a1，a2中至少一个大于零，x3，x4，x5为非人工变量；
（3）d≥0，c＜0，a1≤0，a2≤0，x3，x4，x5均为非人工变量；
（4）d＞0，c＞0，a1＞0，a2≤0，a3=0，x5为人工变量。
4.用黄金分割法求解单变量函数寻优问题时，每迭代一次，寻优区间缩小多少倍？
若要将区间缩小至原区间的10%以下，则至少要多少次迭代？
（10分）
用黄金分割法求解单变量函数寻优问题时，每迭代一次，寻优区间是原区间的0.618倍。
经n次迭代后，区间长度为：
sn=0.618ns0。
若要将区间缩小至原区间的10%以下，即sn/s0≤0.1，则迭代次数≥ln0.1/ln0.618=4.78。
所以若要将区间缩小至原区间的10%以下，则至少要5次迭代。
5.某人外出旅行，需将五件物品装入包裹，但包裹总重量不超过13kg。
物品重量及价值如表。
问如何装这些物品使整个包裹价值最大？
（15分）
（只建模，可不求解）
物品
重量（kg）
价值（元）
A
B
C
D
E
0.5
用动态规划求解时，其模型为：
1.按物品类别分为5阶段，K=（1,2,3,4,5,6），k=6为终了阶段；
2.xk：
k阶段的状态变量，即装第k项物品前剩余重量；
有X1={13}；
X2={6,13}；
X3={1,3,6,8,13}；
X4={0,1,2,3,4,5,6,8,9,13}；
X5={0,1,2,3,4,5,6,7,8,9,10,134}；
X6={0}
3.uk：
k阶段的决策变量，即装第k类物品的数量；
U1={0,1…,[x1/7]}；
U2={0,1,2…,[x2/5]}；
U3={0,1,2,…,[x3/4]}；
U4={0,1…,[x4/3]}；
U5={0,1,2…,[x5/1]}
4.状态转移方程：
5.阶段指标见表，；
6.递推方程（逆推）：
7.边界条件：
6.证明下图所示s-t流为最大流。
弧边数字为（）（15分）
21,21
24,24
36,0
27,0
30，30
54，30
78，57
12，12
60，54
45，33
75，45
33，0
42，30
69，57
①
③
②
⑥
④
⑦
⑤
t
s
对原流图用标号法找增广链有
30，3054，30
（+vs，12）①③⑤
42，3060，54
（-，∞）s（+v4，12）⑥t
75，45
69，57 33，045，33
（+vs，12）②④⑦
78，57（+v2，12）12，12
标号过程进行不下去，即不存在s-t增广链，根据增广链定理，图示s-t流即为最大流。
7.已知某决策问题的收益矩阵D为：
D=
分别用乐观法、悲观法、等可能法和后悔值法确定其最优决策。
（15分）
∴
悲观准则：
∴
∴
则∴
解题毕。
2003级（A）
1.某昼夜服务的公交线路每天各时间所需司机和乘务人员数如下表。
设司机和乘务人员分别在各时间段一开始时上班，并连续工作8小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又使司机和乘务人员配备最少？
试建立求解该问题的模型（可不求解）。
（10分）
班次
时间
6:
00~10:
00
10:
00~14:
14:
00~18:
18:
00~22:
22:
00~2:
2:
00~6:
所需人数
60
70
50
20
30
设表示第班次开始上班的司机和乘务人员数（），则有：
（1）用单纯形法求解；
（10分）
（2）写出其对偶问题；
（5分）
（3）求解对偶问题。
（5分）
（1）用单纯形法求解：
-3
-2
-1
12
1*
5*
-1/5
8/5*
32/5
1/5
-3/5
3/5
2/5
18/5
5/8
-1/8
3/8
1/8
-1/4
1/4
∴该问题有无穷多最优解；
Z*=12
（2）其对偶问题为：
（3）用对偶单纯形法求解对偶问题有：
YB
y1
y2
y3
y4
y5
-1*
-5*
-9
-8/5
-2/5
-12
∴对偶问题最优解为Y*=（0,1,0）T；
W*=12
3.线性规划的目标函数是，在用标准的单纯形法迭代过程中，得到下表，其中a，b是常数，部分数据有缺损。
Cj
-8
x6
a
1/2
（1）在所有的空格中填上适当的数（其中可含参数a、b）。
（5分）
（2）判断在什么情况下此解为最优解？
（5分）
（1）如下表
-2+5a
5/2
（2）当时，表中解为最优解。
4.某房地产公司计划在一住宅小区建设5栋不同类型的楼房B1、B2、B3、B4、B5。
由3家建筑公司A1、A2、A3进行投标，允许每家建筑公司可承建1~2栋楼，通过投标得出建筑公司Ai对新楼Bj的预算费用Cij如下表，求使总费用最少的分配方案。
（10分）
B1
B2
B3
B4
B5
A1
15
11
A2
10
14
A3
13
设每家建筑公司承建2栋楼，虚设一栋楼B6，则有：
矩阵变换有：
-1
矩阵再变换有：
所以有：
或
即：
A1承建B1和B3楼；
A2承建B2楼；
A3承建B4和B5楼。
总费用为38。
5.用最速下降法求，取初始点为。
（迭代一次即可）（15分）
∴
令
∵
因此得
∴此时精度为：
6.某企业新来8名工人，拟分给3个作业班组，每个作业班组最多只分5名工人。
各作业班组得到新工人后产量增加量如下表。
问如何分配新工人才能使总产量增加最大？
（10分）
增加人数
作业班组
第一班组
第二班组
第三班组
25
17
21
32
22
33
17.5
22.5
（1）按作业班组分为3阶段，K=（1，2，3，4），k=4为终了阶段；
（2）xk：
第k阶段初拥有待分配新工人数；
X1={8}，X2={8,7,6,5,4
升级会员 