武汉科技大学本科历年运筹学试题.doc
- 文档编号:242682
- 上传时间:2023-04-28
- 格式:DOC
- 页数:71
- 大小:3.53MB
武汉科技大学本科历年运筹学试题.doc
《武汉科技大学本科历年运筹学试题.doc》由会员分享,可在线阅读,更多相关《武汉科技大学本科历年运筹学试题.doc(71页珍藏版)》请在冰点文库上搜索。
2002级(A)
参考答案
1.写出下述线性规划模型的标准型。
(10分)
解:
令
原问题标准化为:
2.有线性规划模型:
(10分)
(1)用图解法求解;
(2)用单纯形法求解;
(3)指出每个单纯形表的可行域顶点。
解:
(1)用图解法求解;
∴X*=(1,1/2)T;Z*=35/2
(2)用单纯形法求解;
原模型标准化为:
则求解过程为:
Cj
-10-500
b
CB
XB
x1x2x3x4
0
0
x3
x4
3410
5*201
9
8
σj
-10-500
0
0
-10
x3
x1
014/51-3/5
12/501/5
24/5
8/5
σj
0-102
16
-5
-10
x2
x1
015/14-3/14
10-1/72/7
3/2
1
σj
005/1425/14
35/2
T0
T1
T2
∴X*=(1,1/2)T;Z*=35/2
(3)指出每个单纯形表的可行域顶点。
T0表对应O点;T1表对应B点;T2表对应A点,也是最优点。
3.求解:
(10分)
解:
原问题标准化为:
用对偶单纯形法求解为:
Cj
52400
b
CB
XB
x1x2x3x4x5
0
0
x4
x5
-3-1-210
-6-3*-501
-4
-10
σj
52400
0
0
2
x4
x2
-1*0-1/31-1/3
215/30-1/3
-2/3
10/3
σj
102/302/3
20/3
-5
-10
x1
x2
101/3-11/3
0112-1
2/3
2
σj
001/311/3
22/3
∴X*=(2/3,2,0)T;Z*=22/3
(注:
用大M法、两阶段法求解均可)
4.写出线性规划问题:
的对偶规划。
(10分)
解:
原问题的对偶规划为:
5.有一最小化指派问题的系数矩阵如下,试求其最优解。
(10分)
解:
用匈牙利算法求解为:
变换后:
-5
再变换为:
再变换:
∴Z*=28
6.写出函数的梯度和海赛矩阵,并判断其凹凸性。
(10分)
解:
的梯度矩阵为:
的海赛矩阵为:
这里H矩阵的各阶主子式均大于0,所以为严格凸函数。
7.某厂有4台设备,拟分给3个用户(工厂)使用,各用户利用设备提供的盈利如下表。
问如何分配设备才能使总盈利最大?
试建立其动态规划求解模型(可不求解)。
(10分)
用户
设备台数
1
2
3
0
1
2
3
4
0
4
6
7
7
0
2
5
6
8
0
3
5
7
8
解:
根据题意,原问题用动态规划求解模型为:
(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
2,2
5,2
4,3
3,3
v1
v2
8.证明下图所示v1至v6流为最大流。
弧边数字为。
(10分)
证明:
对原流图用标号法找可扩充路有:
v6
v5
v4
v3
2,2
5,3
3,0
1,0
2,2
5,2
4,3
3,3
v1
v2
(-,∞)
(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分)
解:
图解过程如下:
4
3
2
1
4
3
2
1
0
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
b
x3
x4
x5
-13100
a14010
a2a3001
4
1
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
7
5
4
3
1
9
4
3
2
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
24,24
(+vs,12)①③⑤
42,3060,54
27,0
36,0
(-,∞)s(+v4,12)⑥t
21,21
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分)
班次
1
2
3
4
5
6
时间
6:
00~10:
00
10:
00~14:
00
14:
00~18:
00
18:
00~22:
00
22:
00~2:
00
2:
00~6:
00
所需人数
60
70
60
50
20
30
解:
设表示第班次开始上班的司机和乘务人员数(),则有:
2.有线性规划模型:
(1)用单纯形法求解;(10分)
(2)写出其对偶问题;(5分)
(3)求解对偶问题。
(5分)
解:
(1)用单纯形法求解:
原模型标准化为:
则求解过程为:
Cj
-3
-2
0
0
0
b
CB
XB
x1
x2
x3
x4
x5
0
x3
-1
2
1
0
0
4
0
x4
3
2
0
1
0
12
0
x5
1*
-1
0
0
1
3
σj
-3
-2
0
0
0
0
0
x3
0
1
1
0
1
7
0
x4
0
5*
0
1
-3
3
-3
x1
1
-1
0
0
1
3
σj
0
-5
0
0
3
9
0
x3
0
0
1
-1/5
8/5*
32/5
-2
x2
0
1
0
1/5
-3/5
3/5
-3
x1
1
0
0
1/5
2/5
18/5
σj
0
0
0
1
0
12
0
x5
0
0
5/8
-1/8
1
4
-2
x2
0
1
3/8
1/8
0
3
-3
x1
1
0
-1/4
1/4
0
2
σj
0
0
0
1
0
12
∴该问题有无穷多最优解;Z*=12
(2)其对偶问题为:
(3)用对偶单纯形法求解对偶问题有:
Cj
4
12
3
0
0
b
CB
YB
y1
y2
y3
y4
y5
0
y4
1
-3
-1*
1
0
-3
0
y5
-2
-2
1
0
1
-2
σj
4
12
3
0
0
0
0
y3
-1
3
1
-1
0
3
0
y5
-1
-5*
0
1
1
-5
σj
7
3
0
3
0
-9
0
y3
-8/5
0
1
-2/5
3/5
0
-2
y2
1/5
1
0
-1/5
-1/5
1
σj
32/5
0
0
18/5
3/5
-12
∴对偶问题最优解为Y*=(0,1,0)T;W*=12
3.线性规划的目标函数是,在用标准的单纯形法迭代过程中,得到下表,其中a,b是常数,部分数据有缺损。
Cj
-2
-5
-8
0
0
0
b
CB
XB
x1
x2
x3
x4
x5
x6
x6
0
3
0
20
x2
a
1/2
b
x4
-2
-1
1
8
σj
2
(1)在所有的空格中填上适当的数(其中可含参数a、b)。
(5分)
(2)判断在什么情况下此解为最优解?
(5分)
解:
(1)如下表
Cj
-2
-5
-8
0
0
0
b
CB
XB
x1
x2
x3
x4
x5
x6
0
x6
0
0
3
0
0
1
20
-5
x2
a
1
2
0
1/2
0
b
0
x4
-2
0
-1
1
1
0
8
σj
-2+5a
0
2
0
5/2
0
(2)当时,表中解为最优解。
4.某房地产公司计划在一住宅小区建设5栋不同类型的楼房B1、B2、B3、B4、B5。
由3家建筑公司A1、A2、A3进行投标,允许每家建筑公司可承建1~2栋楼,通过投标得出建筑公司Ai对新楼Bj的预算费用Cij如下表,求使总费用最少的分配方案。
(10分)
B1
B2
B3
B4
B5
A1
3
8
7
15
11
A2
7
9
10
14
12
A3
6
9
13
12
7
解:
设每家建筑公司承建2栋楼,虚设一栋楼B6,则有:
矩阵变换有:
-1
矩阵再变换有:
所以有:
或
即:
A1承建B1和B3楼;A2承建B2楼;A3承建B4和B5楼。
总费用为38。
5.用最速下降法求,取初始点为。
(迭代一次即可)(15分)
解:
∴
令
∵
令
∴
因此得
∵
∴此时精度为:
6.某企业新来8名工人,拟分给3个作业班组,每个作业班组最多只分5名工人。
各作业班组得到新工人后产量增加量如下表。
问如何分配新工人才能使总产量增加最大?
试建立其动态规划求解模型(可不求解)。
(10分)
增加人数
作业班组
0
1
2
3
4
5
第一班组
第二班组
第三班组
0
0
0
16
10
12
25
14
17
30
16
21
32
17
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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 武汉 科技大学 本科 历年 运筹学 试题