武汉科技大学本科历年运筹学试题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