管理运筹学试题
五邑大学试卷答案及评分标准试卷分类(A卷或B卷) A
学期: 2009 至2010 学年度第 2 学期课程: 管理运筹学专业: 信管、电子商务、市场营销班级学号: 姓名:
一、求解下述线性规划问题(共30分,每小题10分)
1.
12
max58
z x x
=+
12
12
12
2312
318
,0
x x
x x
x x
+≤
⎧
⎪
+≤
⎨
⎪≥
⎩
解: (1) 画直角坐标系……………………………………1分
(2) 画约束条件,决定可行域………………………5分
(3) 画目标函数线……………………………………7分
(4) 移动目标函数线,得到最优解…………………10分
**
(0,4),32
X z
==
得分
2、 123max 45z x x x =++
12312
1231233218245,,0
x x x x x x x x x x x ++≤⎧⎪+≤⎪⎨
+-=⎪⎪≥⎩ 解:引入松弛变量与人工变量,化标准形为
1236min 45w x x x Mx =---+
1234
12
5123
632182455,1,2,,6
i x x x x x x x x x x x x i +++=⎧⎪++=⎪⎨+-+=⎪⎪≥=⎩L
因为全体检验数非负,但基变量中存在人工变量,故原问题无可行解。 评分标准:
化标准形 3分 给出初始单纯形表 3分 迭代 3分 判断无可行解 1分
3、 1234min 3w x x x x =+++
123
12
41234
22436,,,0x x x x x x x x x x -++=⎧⎪
++=⎨⎪≥⎩ 解:
*(0,2,0,4)X '=,*6w =
因存在非基变量的检验数为0,故本题具有无穷多解。 评分标准:初始单纯形表 4分;
得到最优解 5分;
判断存在无穷多最优解1分。
得分
二、已知如下产销量及运价表,求解此运输问题(20分)
产销量及运价表
解:(1)由伏格尔法求初始调运方案
产销平衡表
单位运价表
(2)用位势法求检验数
检验数表
(3)因为全体检验数非负,所以初始调运方案即为最优解。
评分标准:
求初始调运方案9分
求检验数9分
判断最优解2分
三、
用隐枚举法求解下述0-1规划问题(15分)
12345max 82475z x x x x x =+---
123451234512345
332345324,,,,01x x x x x x x x x x x x x x x ++++≤⎧⎪
+≤⎨⎪=⎩--+或 解:第一步,将上述线性规划问题转换成规范形式 (1)目标函数求极小化,约束条件为“≥”形式
12345min 82475w x x x x x =--+++ 123451234512345332345324,,,,01x x x x x x x x x x x x x x x -----≥-⎧⎪
--≥-⎨⎪=⎩++-或 ……………………………、
、2分 (2)令1
11x x '=-,221x x '=- 1
2345min 8247510w x x x x x ''=++++- 1
23451
2345332325324()01,1,2,,5
j
j x x x x x x x x x x x x j ''⎧+---≥⎪
''+≥⎨⎪'==⎩L ++-或或 ……………………………、、4分 (3)按目标函数变量系数的大小从小到大排列变量,约束条件也作相应的调整
2
3541min 2457810w x x x x x ''=++++- 235412
3541332323254()01,1,2,,5
j
j x x x x x x x x x x x x j ''⎧---+≥⎪
''+≥⎨⎪'==⎩L +-+或或 ……………………………、、6分 第二步,检验全零解,不就是可行解。 ……………………………、、8分
第三步,依次分枝,直到得到最优解。
本问题的最优解为*
(1,0,1,0,0)X
'=,*
4z = ……………………………、
、15分 得分
四、求解下述标准指派问题(10分)
四人完成四项工作,她们完成各项任务的时间(小时)如下表所示,如何安排四人的工作,才能使完成这四项工作总的时间消耗最少。
解:
指派方案为:人员1→工作4;人员2→工作1;人员3→工作3;人员4→工作2
消耗的最小时间为:43
评分标准:
第一个矩阵3分;
第二个矩阵5分;
给出最优解2分。
得分
五、
用动态规划求解下述非线性问题(15分)
123max z x x x =⨯⨯
1231239
,,0
x x x x x x ++=⎧⎨
≥⎩ 解:阶段变量1,2,3k =;
决策变量k x ;
状态变量k S ,表示从k x 到3x 所占有的份额; 状态转移率:1k k k S S x +=-; 允许决策集合:0k k x S ≤≤;
边界条件:19S =,44()1f S =,40S =; 递推关系式:(){}110()max k k
k k k
k k x S f S x
f S ++≤≤=⨯; (5)
当3k =时,
()
{}
33
333440()max x S f S x f S ≤≤=⨯3S =
*
33x S = (8)
当2k =时,
()
{}
22
222330()max x S f S x f S ≤≤=⨯{}22
2222201max ()4
x S x S x S ≤≤=⨯-=
*
2
22
S x =
…………………………、10分 当1k =时,
()
{}
11
111220()max x S f S x f S ≤≤=⨯1123
11110()1max 27427x S S x x S ≤≤⎧⎫-=⨯==⎨⎬⎩⎭
*
1
13S x =
…………………………、12分 综上:19S =,*
13x =
26S =,*
23x = 33S =,*
3
3x = * (15)
六、 用Dijkstra 标号算法求图中开始结点V S 到其她各结点的最短路(10分)
得分
得分
