《运筹学》考试题及其答案.docx
- 文档编号:16453912
- 上传时间:2023-07-13
- 格式:DOCX
- 页数:21
- 大小:346.35KB
《运筹学》考试题及其答案.docx
《《运筹学》考试题及其答案.docx》由会员分享,可在线阅读,更多相关《《运筹学》考试题及其答案.docx(21页珍藏版)》请在冰点文库上搜索。
《运筹学》考试题及其答案
4x1z是斜率为4的一族平行直线,由线性规划的
X2沿其法线方向逐渐向上平移,直至A
2012-2013学年第1学期《运筹学》考试题答案
要求:
第一题必做(50分),二三四题任选两题(每题各25分)一、考虑下面线性规划问题
(1)用图解法求解该问题;
(2)写出该问题的标准形式;
(3)求出该问题的松弛变量和剩余变量的值;
(4)用单纯形法求解。
【解答】⑴图中阴影部分为此线性规划问题的
可行域,目标函数z4x1x2,即x2
性质知,其最值在可行域的顶点取得,将直线z4x1
点,A点的坐标为(3,6),所以minz43618
55555
此线性规划问题有唯一解X13,X26。
55
⑵给等式
(2)左端添加剩余变量X3,给等式
3)左端添加松弛变量X4,则得到该问题的标
准型为:
(3)在上面标准型中令X1
-,X26,得到剩余变量X3=0,松弛变量X4=0。
55
(4)先在上面标准型中约束条件
(1)、
(2)中分别加入人工变量X5,x6,得到如下数学模型,
由此列出单纯形表逐步迭代,用大M法求解计算结果如下表所示
-4
-1
0
0
-M
-M
X1
X2
X3
X4
X5
X6
b
i
-M
X5
【3】
1
0
0
1
0
3
1
-M
X6
4
3
-1
0
0
1
6
3/2
0
X4
1
2
0
1
0
0
3
3
rj
7M—4
4M—1
-M
0
0
0
—9M
-4
X1
1
1/3
0
0
1/3
0
1
3
-M
X6
0
【5/3】
-1
0
-4/3
1
2
6/5
0
X4
0
5/3
0
1
-1/3
0
2
6/5
rj(-z)
0
(5M+1)/3
-M
0
(-7M+4)/3
0
—4-2M
-4
X1
1
0
1/5
0
3/5
-1/5
3/5
1/3
-1
X2
0
1
-3/5
0
-4/5
3/5
6/5
—
0
X4
0
0
【1】
1
1
1
0
0
rj(-z)
0
0
1/5
0
—M+8/5
-M-1/5
-18/5
-4
X1
1
0
0
-1/5
2/5
0
3/5
-1
X2
0
1
0
3/5
-1/5
0
6/5
0
X3
0
0
1
1
1
-1
0
rj(-z)
0
0
0
-1/5
—M+7/5
-M
-18/5
表中所有检验数rj0,根据最优解定理,冋题存在唯一的最优解X(—,—,0,0,0,0)T,目标函
55
数的最优值maxz43—18。
555
试用表上作业法求解下列运输问题的最优解
'产销地
B1
B2
B3
B4
产量
A1
4
8
8
4
6
A2
9
5
6
3
4
A3
3
11
4
2
12
销量1
6
2
7
7
【解答】:
显然该问题是一个供需平衡问题,利用伏格法求出初始方案,如下表所示。
Bi
B2
B3
B4
产量
Ai
6
4
8
8
4
6
A2
9
2
5
6
2
3
4
A3
0
3
ii
7
4
5
2
i2
销量
6
2
7
7
用位势法求出各非基变量(即空格)的检验数,如下表所示。
Bi
B2
B3
B4
Ui
Ai
6
4
(3)
8
(3)
8
(i)
4
ui=0
A2
(5)
9
2
5
(i)
6
2
3
u2=0
A3
0
3
(7)
ii
7
4
5
2
U3=—i
Vj
vi=4
v2=5
V3=5
V43
因为所有非基变量的检验数均为非负的,故表中的解为最优解。
按照此种方案调运,最小费用为:
6X4+2X5+2X3+0X3+7X4+5X2=78
用标号算法求解下图中从Vi到各点的最短路
vio
【解答】:
此为最短路问题,权数为正,用Dijksta算法的计算步骤如下:
ViV2V3V4VV6V7V8VVioVii
初始值
T()
{0}
00
00
00
00
00
00
00
00
00
00
i
P()+Wij
0+2
0+8
0+0
0+0
0+0
0+0
0+0
0+0
0+0
0+0
T()
{2}
8
00
00
00
oo
0
0
0
0
2
P()+Wij
2+6
2+o
2+1
2+0
2+0
2+0
2+0
2+0
2+0
T()
8
00
:
{3}
oo
OO
0
0
0
0
3
P()+Wij
3+5
3+o
3+0
3+0
3+0
3+1
3+0
3+0
T()
8
00
OO
0
0
{4}
0
0
4
P()+Wij
4+g
4+o
4+6
4+0
4+7
4+0
4+0
T()
{8}
00
10
0
11
0
0
5
P()+Wij
8+7
8+0
8+0
8+0
8+0
8+0
T()
15
{10}
0
11
0
0
6
P()+Wij
10+o
10+4
10+0
10+0
10+0
T()
15
14
{11}
0
0
7
P()+Wij
11+0
11+0
11+0
11+9
T()
15
{14}
0
20
8
P()+Wij
14+o
14+1
14+0
T()
{15}
{15}
11
9
P()+Wij
15+4
T()
{19}
由上表的迭代过程可得:
Sq{Vi,V2,V,V9,V3,V6,V8,V7,V4,V10,V11}
d(Vi,V2)=2,最短路:
(Vi,V2);d(Vi,V5)=3,最短路:
(ViWs);
d(Vi,V9)=4,最短路:
(Vi,V2,V5,V9);d(Vi,V6)=10,最短路:
(Vi,V2,V5,V9,V6);
d(Vi,V3)=8,最短路:
(Vi,V3)或(Vi,V2,V3)或(Vi,V2,V5,V3);
d(Vi,V8)=ii最短路:
(Vi,V2,V5,V9,V8);d(Vi,V7)=14最短路:
(Vi,v?
V5,V9,V6,V7);
d(Vi,V4)=15,最短路:
(Vi,V3,V4)或(Vi,V2,V3,V4)或(Vi,V2,V5,V3,V4);
d(Vi,Vio)=i5,最短路:
(Vi,V2,V5,V9,V6,V7,Vi0);
d(Vi,Vii)=i9,最短路:
(Vi,V2,V5,V9,V6,V7,Vio,Vii);
四、某公司面对四种自然状态的三种备选行动方案收益表如下,假定状态概率未知,
试分别用悲观准则、等可能性准则、后悔值准则和乐观系数准则(0=0.6)进行决策
收、状态
Of'
9i
92
93
94
Ai
15
8
0
-6
A2
4
14
8
3
A3
1
4
10
12
【解答】:
(1)应用悲观准则:
min{15,8,0,-6}
tmaxmin{4,14,8,3}max-6,3,13/.S2为最佳方案。
min{1,4,10,12}
117
E(A1)-(15806),
44
291
83),E(A3)(141012)
⑷应用乐观系数准则(0=0.6):
先计算各个方案的折中益损值:
44
E(AJ
0.6
15
0.4
(
6)
6.6,
Ef)
0.6
14
0.4
3
9.6
E(A3)
0.6
12
0.4
1
7.6
max{6.6,9.6,7.6}
9.6
E(Q
--S2为最佳方案
已知下表为求解某目标函数为极大化线性规划问题的最终单纯形表,表中X4,X5
为松弛变量,问题的约束为形式(共8分)
X2
X3
X4
X5
X3
5/2
0
1/2
1
1/2
0
x
5/2
1
—1/2
0
—1/6
1/3
CjZj
0
-4
0
—4
—2
(1)写出原线性规划问题;(4分)
(2)写出原问题的对偶问题;(3分)
(3)直接由上表写出对偶问题的最优解。
(1分)
四、用单纯形法解下列线性规划问题(16分)
maxZ2x1x2x3
s.t.
3xi
+X2+X3
60
xi-
x2+2x3
I0
xi+
x2-x3
20
xi,
x2,x3
0
五、求解下面运输问题。
(18分)
某公司从三个产地Ai、A2、A3将物品运往四个销地Bi、B2、B3、B4,各产地的产量、各销地的销量
和各产地运往各销地每件物品的运费如表所示:
问:
应如何调运,可使得总运输费最小?
产地
销地
Bi
B2
B3
B4
产量
A
I0
5
6
7
25
A
8
2
7
6
25
A3
9
3
4
8
50
销
量
i5
20
30
35
I00
六、灵敏度分析(共8分)
线性规划maxz=10xi+6x2+4x3
s.t.
xi+x2+
X3
I00
IOxi+4x2+
5x3
600
2xi+2x2+
6x3
300
xi,X2,
X3
0
的最优单纯形表如下:
6
X2
200/3
0
5/6
i
5/3
-I/6
0
I0
xi
I00/3
i
I/6
0
-2/3
I/6
0
0
X6
i00
0
4
0
-2
0
i
j
0
-8/3
0
-I0/3
-2/3
0
(1)Ci在何范围内变化,最优计划不变?
(4分)
(2)bi在什么范围内变化,最优基不变?
(4分)
七、试建立一个动态规划模型。
(共8分)
某工厂购进I00台机器,准备生产pi,p2两种产品。
若生产产品pi,每台机器每年可收入45万元,损坏率为65%;若生产产品p2,每台机器每年可收入35万元,损坏率为35%;估计三年后
将有新的机器出现,旧的机器将全部淘汰。
试问每年应如何安排生产,使在三年内收入最多?
八、求解对策问题。
(共I0分)
某种子商店希望订购一批种子。
据已往经验,种子的销售量可能为500,I000,I500或2000公斤。
假
定每公斤种子的订购价为6元,销售价为9元,剩余种子的处理价为每公斤3元。
要求:
(1)建立损益矩阵;(3分)
(2)用悲观法决定该商店应订购的种子数。
(2分)
(3)建立后悔矩阵,并用后悔值法决定商店应订购的种子数。
(5分)
九、求下列网络计划图的各时间参数并找出关键问题和关键路径。
(8分)
解:
用X1,X2,X3分别表示大豆、玉米、麦子的种植公顷数;X4,X5分别表示奶牛和鸡的饲养数;X6,X7
分别表示秋冬季和春夏季的劳动力(人日)数,则有
maxZ3000x14100x24600x3900x420x520x625x7
x1
xX3
1.5x4
100
(土地限制)
400x43x5
15000
(资金限制)
20x1
35x2
10x3100x4
0.6X5
x63500
(劳动力限制)
50x1
175x2
40x350x4
0.3x5
x74000
(劳动力限制)
x4
200
(牛栏限制)
x5
1500
(鸡舍限制)
Xj
0(j
1,2,,7)
三、对偶问题。
共计
-8分
X2
2X2
5
3x1x2
X3
10
X1,X2
0
;4分
(2)原问题的对偶规划问题为:
minw5y110y2
3y26
y1y22
2y1y210
*^20;
3分
(3)对偶规划问题的最优解为:
Y
(4,2)
T
o
1分
四、单纯形表求解线性规划。
共计16分
解:
引入松弛变量X4、
X5、
X6,标准化得,
maxZ
2x1
X2X3
s.t.
3X1
+X2+X3+X4
=60
X1-
X2+2X3+X5
=10
Xl+x2-X3+X6=0
X1,x2,X3,X4、X5、X6,>03分
建初始单纯形表,进行迭代运算:
…分
Cb
Xb
b'
2
-1
1
0
0
0
0
X1
X2
X3
X4
X5
X6
0
X4
60
3
1
1
1
0
0
20
0
X5
10
[1]
-1
2
0
1
0
10*
0
X6
20
1
1
-1
0
0
1
20
1
0
2*
-1
1
0
0
0
0
X4
30
0
4
-5
1
-3
0
7.5
2
X1
10
1
-1
2
0
1
0
—
0
X6
10
0
[2]
-3
0
-1
1
5*
2
20
0
1*
-3
0
-2
0
0
X4
10
0
0
1
1
-1
-2
2
X1
15
1
0
0.5
0
0.5
0.5
-1
X2
5
0
1
-1.5
0
-0.5
0.5
3
25
0
0
-1.5
0
-1.5
-0.5
由最优单纯形表可知,原线性规划的最优解为:
(15,5,0)T•…分
所以,基本的初始可行解为:
X14=25;X22=20;X24=5;
七、建动态规划模型。
共计8分
解:
(1)设阶段变量k表示年度,因此,阶段总数n=3。
(2)状态变量sk表示第k年度初拥有的完好机床台数,同时也是第k
(3)决策变量uk,表示第k年度中分配于生产产品p1的机器台数。
于
年度末时的完好机床数量。
sk-uk便为该年度中分配
于生产产品p1的机器台数.
(4)状态转移方程为
(5)允许决策集合i,在第35ku段为).65視<6屮){山0uksk}
(6)目标函数。
设gk(sk,uk)为第k年度的产量,则kk
gk(sk,uk)=45uk+35(sk-uk),
因此,目标函数为
(7)条件最优目标函数递推方程。
fk(Sk)kmax(uk(Sk))
令fk(sk)表示由第k年的状态sk出发,采取最优分配方案到第3年度结束这段时间的产品产量,
根据最优化
原理有以下递推关系:
(8).边界条件为356uk)]fki[0.35uk0.65(Skuk)]}
八、解决对策问题。
共10分f31(s31)0
(1)益损矩阵如下表所示:
……3分
销售
S1
S2
S3
S4
订购
500
1000
1500
2000
A1500
1500
1500
1500
1500
A21000
0
3000
3000
3000
A31500
—1500
1500
4500
4500
A42000
—3000
0
3000
6000
(2)悲观法:
A1,订购500公斤。
……2分
(3)后悔矩阵如下表所示:
3分
S1
S2
S3
S4
最大后悔值1
A1
0
1500
3000
4500
4500
A2
1500
0
1500
3000
3000
A3
3000
1500
0
1500
3000
A4
4500
3000
1500
0
4500
按后悔值法商店应取决策为A2或A3,即订购1000公斤或1500公斤。
九、求网络计划图的各时间参数。
(8分)•
工序
代号
工序
时间
最早开
工时间
时间
1-2
1-3
1-4
2-4
2-5
最晚完
工时间”
3、
8
0
3
6
8
28
8
713
14
9
11
7
H0I
0
I..
11
3
0
4
2
6
8
14
0/
3-4
二61/\
0218
3-6
10
15
18
4-5
11
14
11
14
4-6
11
18
11
18
4-7
11
15
22
26
11
5-7
14
23
17
26
关键问题是:
①
关键线路是:
评分标准:
①能正确给各顶点标号并填表
②正确写出关键问题
③正确画出关键线路
2分
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 考试题 及其 答案