运筹学期末考试试题及参考答案.pdf

文档介绍：该【运筹学期末考试试题及参考答案 】是由【非学无以广才】上传分享，文档一共【11】页，该文档可以免费在线阅读，需要了解更多关于【运筹学期末考试试题及参考答案 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:.
《运筹学》试题参考答案
一、填空题(每空2分,共10分)
1、在线性规划问题中,称满足所有约束条件方程和非负限制的解为可行解。
2、在线性规划问题中,图解法适合用于处理变量为两个的线性规划问题。
3、求解不平衡的运输问题的基本思想是设立虚供地或虚需求点,化为供求平衡
的标准形式。
4、在图论中,称无圈的连通图为树。
5、运输问题中求初始基本可行解的方法通常有最小费用法、西北角法两
种方法。
二、(每小题5分,共10分)用图解法求解下列线性规划问题:
1)maxz=6x+4x
12⑴
2xx10⑵
12

xx8⑶
12

x7⑷

2
x,x0
⑸、⑹
12
解:此题在“《运筹学》”中已有,不再重复。
2)minz=-3x+2x
12⑴
2x4x22⑵
12

x4x10⑶
12

2xx7⑷
12

x3x1⑸
12
x,x0
⑹、⑺
12
解::.
可行解域为abcda,最优解为b点。
2x4x22
12
由方程组解出x=11,x=0
x012

2
x
*1T
∴X==(11,0)
x
2
∴minz=-3×11+2×0=-33
三、(15分)某厂生产甲、乙两种产品,这两种产品均需要A、B、C三种资源,
每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储
备如下表所示:
ABC
甲94370
乙4610120
360200300
1)建立使得该厂能获得最大利润的生产计划的线性规划模型;(5分):.
2)用单纯形法求该问题的最优解。(10分)
解:1)建立线性规划数学模型:
设甲、乙产品的生产数量应为x、x,则x、x≥0,设z是产品售后的总利
1212
润,则
maxz=70x+120x
12
.
9x4x360
12

4x6x200
12

3x10x300

12
x,x0

12
2)用单纯形法求最优解:
加入松弛变量x,x,x,得到等效的标准模型:
345
maxz=70x+120x+0x+0x+0x
12345
.
9x4xx360
123

4x6xx200
124

3x10xx300
125
x0,j1,2,...,5
j
列表计算如下::.
70120000
CXbθ
BBxxxxxL
12345
0x3609410090
3
0x20046010100/3
4
0x3003(10)00130
5
00000
70120↑000
0x24039/5010-2/5400/13
3
0x20(11/5)001-3/5100/11
4
120x303/101001/10100
2
361200012
34↑000-12
0x1860/11001-39/1119/11
3
70x100/111005/11-3/11
1
120x300/11010-3/222/11
2
43000701200170/1130/11
11000-170/11-30/11
*1003001860T
∴X=(,,,0,0)
111111
**********
∴maxz=70×+120×=
111111
四、(10分)用大M法或对偶单纯形法求解如下线性规划模型:
minz=5x+2x+4x
123
3xx2x4
123

6x3x5x10
123

x,x,x0

123:.
解:用大M法,先化为等效的标准模型:
maxz/=-5x-2x-4x
123
.
3xx2xx4
1234

6x3x5xx10
1235

y0,j1,2,...,5
j
增加人工变量x、x,得到:
67
maxz/=-5x-2x-4x-Mx-Mx
12367

3xx2xxx4
12346

6x3x5xxx10
12357

x0,j1,2,...,7
j
大M法单纯形表求解过程如下::.
-5-2-400-M-M
CXbθ
BBL
xxxxxxx
1234567
-Mx4(3)12-10104/3
6
-Mx106350-1015/3
7
-9M-4M-7MMM-M-M
9M-5↑4M-27M-4-M-M00
-5x4/311/32/3-1/301/30——
1
-Mx2011(2)-1-211
7
-5-M-5/3-M-10/3-2M+5/3M2M-5/3-M
0M-1/3M-2/32M-5/3↑-M-3M+5/30
-5x5/311/25/60-1/601/610/3
1
0x10(1/2)1/21-1/2-11/22
4
-5-5/2-25/605/60-5/6
01/2↑1/60-5/6-M-M+5/6
-5x2/3101/3-11/31-1/3
1
-2x20112-1-21
2
-5-2-11/311/3-1-1/3
22
-
3
00-1/3-1-1/3-M+1-M+1/3
2
∴x*=(,2,0,0,0)T
3
2222
最优目标函数值minz=-maxz/=-(-)=
33
五、(15分)给定下列运输问题:(表中数据为产地A到销地B的单位运费)
ij:.
BBBBs
1234i
A123410
1
A876580
2
A91011915
3
d8221218
j
1)用最小费用法求初始运输方案,并写出相应的总运费;(5分)
2)用1)得到的基本可行解,继续迭代求该问题的最优解。(10分)
解:用“表上作业法”求解。
1)先用最小费用法(最小元素法)求此问题的初始基本可行解:
费销
用BBBBS
地1234i
产
地
1234
A10
1
82××
8765
A20
2
××218
910119
A30
3
×2010×
60
d8221218
j
60
∴初始方案:
BBB
8220
132
AAA
1
23
21810
BBB
243
Z=1×8+2×2+6×2+5×18+10×20+11×10=424:.
2)①用闭回路法,求检验数:
费销
用BBBBS
地1234i
产
地
12304-2
A10
1
82××
8-47-265
A20
2
××218
90101191
A30
3
×2010×
60
d8221218
j
60
∵=1>0,其余≤0
34j
∴选x作为入基变量迭代调整。
34
②用表上闭回路法进行迭代调整:
费销
用BBBBS
地1234i
产
地
123-14-3
A10
1
82××
8-37-165
A20
2
××128
901011-19
A30
3
×20×10
60
d8221218
j
60
调整后,从上表可看出,所有检验数≤0,已得最优解。
j
∴最优方案为::.
BBB
81220
132
AAA
1
23
2810
BBB
244
最小运费Z=1×8+2×2+6×12+5×8+10×20+9×10=414
六、(8分)有甲、乙、丙、丁四个人,要分别指派他们完成A、B、C、D四项不同的工作,每
人做各项工作所消耗的时间如下表所示:
ABCD
甲21097
乙154148
丙13141611
丁415139
问:应该如何指派,才能使总的消耗时间为最少?
解:用“匈牙利法”求解。
效率矩阵表示为:
210970875
列约简
行约简
154148110104

131416112350
标号

41513901195
√
(0)825(0)825√


11(0)5411(0)54

23(0)0*23(0)0*

√
0*12450*1245

:.
0*6(0)3

13(0)54

430*(0)


(0)1023
0010

0100
至此已得最优解:

0001


1000
∴使总消耗时间为最少的分配任务方案为:
甲→C,乙→B,丙→D,丁→A
此时总消耗时间W=9+4+11+4=28
七、(6分)计算下图所示的网络从A点到F点的最短路线及其长度。
此题在“《运筹学参考综合****题》(我站搜集信息自编).doc”中已有。
91
BCD
1114
55
2
3
E
11
48
6
53
A4
BCDF
222
9
6
52
4E
2
147
45
7
BC2D
333
解:此为动态规划之“最短路问题”,可用逆向追踪“图上标号法”解决如下::.
1454
91
BCD
1114
551
2
3
4
E1
1481
90
6
53
A4
BCDF
222
9
6
52
117
4E
2
147
452
7
BC2D
333
1287
最佳策略为:A→B→C→D→E→F
2112
此时的最短距离为5+4+1+2+2=14