CB 0 0 0 ?1 0 2 0 ?2 0 2 -1 ?3 x4 x1 x2 x4 x1 x6 x4 x5 x6 60 10 20 0 30 10 10 20 10 15 5 25 x1 3 [1] 1 2* 0 1 0 0 0 1 0 0 x2 1 -1 1 -1 4 -1 [2] 1* 0 0 1 0 x3 1 2 -1 1 -5 2 -3 -3 1 0.5 -1.5 -1.5 x4 1 0 0 0 1 0 0 0 1 0 0 0 x5 0 1 0 0 -3 1 -1 -2 -1 0.5 -0.5 -1.5 x6 0 0 1 0 0 0 1 0 -2 0.5 0.5 -0.5 20 10* 20 7.5 --- 5* 由最优单纯形表可知，原线性规划的最优解为： ( 15 , 5 , 0 )T …2分
最优值为： z*=25。………2分
五、求解运输问题。共计18分 解：
（1）最小元素法：（也可以用其他方法，酌情给分） 设xij为由Ai运往Bj的运量（i=1,2,3; j=1,2,3,4）, 列表如下：
销 地 B1 B2 B3 B4 产 量 产 地 1 2 3 销 量 15 15 20 20 30 30 25 5 5 35 25 25 50 100 ……………3分 所以，基本的初始可行解为：x14 =25； x22=20 ； x24 =5 ；
X31 =15； x33 =30； x34=5
其余的xij=0。 …………3分
（2）求最优调运方案：
1会求检验数，检验解的最优性：?11=2；?12=2；?13=3；
?21=1；?23=5；?32= - 1…………3分
2会求调整量进行调整：=5 …………2分
销 地 产 地 1 2 3 销 量 B1 15 15 B2 15 5 20 B3 30 30 B4 25 10 35 产 量 25 25 50 100 …3分
3再次检验 …………2分
4能够写出正确结论
解为：x14=25 ； x22 =15 ； x24 =10 x31 =15， x32 =5 x33=30
其余的xij=0。 ……1分
最少运费为： 535 ………1分。
六、灵敏度分析。共计8分 （1）（4分） ??8/3?2/3???10/3?max,??c?min???? 11/61/6?2/3????
?4??c1?5,6?10?4?c1??c1?10?5?15
（2）（4分） ?200/3????100/3?100?max???,, ???b1?min??5/3?2/3?2????
?40??b1?10
七、建动态规划模型。共计8分
解：(1)设阶段变量k表示年度，因此，阶段总数n=3。
(2)状态变量sk表示第k年度初拥有的完好机床台数， 同时也是第 k–1 年度末时的完好机床数量。
(3)决策变量uk，表示第k年度中分配于生产产品 p1 的机器台数。于是sk– uk便为该年度中分配于生产产品 p1的机器台数． （4） 状态转移方程为
sk?1?0.35uk?0.65(sk?uk)（5）允许决策集合,在第 k 段为 U(s)?{u0?u?s}kkkkk（6）目标函数。设gk(sk,uk)为第k年度的产量，则
gk(sk,uk) = 45uk + 35(sk–uk) ,
因此，目标函数为 3 R?g(s,u) ki?kkkk（7）条件最优目标函数递推方程。
fk(sk)?max(uk(sk))uk?Uk
令fk(sk)表示由第k年的状态sk出发，采取最优分配方案到第3年度结束这段时间的产品产量，根据最优化
原理有以下递推关系：
? {[45 uk?35(sk?uk)]?fk?1[0.35uk?0.65(sk?uk)]}（8）.边界条件为
f3?1(s3?1)?0
八、解决对策问题。共10分
（1）益损矩阵如下表所示：……3分
销 售 S1 S2 S3 S4 订 购 500 1000 1500 2000 A1 500 A2 1000 A3 1500 A4 2000 1500 0 －1500 －3000 1500 3000 1500 0 1500 3000 4500 3000 1500 3000 4500 6000 （2）悲观法：A1 ，订购500公斤。……2分 （3）后悔矩阵如下表所示：……3分
S1 S2 S3 S4 A1 A2 A3 0 1500 3000 1500 0 1500 3000 1500 0 4500 3000 1500 最大后悔值 4500 3000 3000 A4 4500 3000 1500 0 4500 按后悔值法商店应取决策为A2或A3 ，即订购1000公斤或1500公斤。……2分 九、求网络计划图的各时间参数。（8分） 14 8 14 0 5 8 2 5
8 9 3 3 11 0 26 0 0 4 6 1 4 7
26 0 7 11 7 2 8 3
3 6 7
9 18
0 18
工序 代号 1-2 1-3 1-4 2-4 2-5 3-4 工序 时间 8 7 6 3 5 2 最早开 工时间 0 0 0 8 8 7 最早完 工时间 8 7 6 11 13 9 最晚开 工时间 0 2 5 8 9 9 最晚完 工时间 8 9 11 11 14 11 机动 时间 0 2 6 0 1 2 3-6 4-5 4-6 4-7 5-7 6-7 3 3 7 4 9 8 7 11 11 11 14 18 10 14 18 15 23 26 15 11 11 22 17 18 18 14 18 26 26 26 8 0 0 11 3 0
关键问题是：①
→②；2→④；④→⑤；④→6；6→⑦
关键线路是： 1
评分标准：①能正确给各顶点标号并填表......................4分
②正确写出关键问题.............. 2分
③正确画出关键线路............. ２分
2 4 1 6 7 十、用标号法求v1 到 v6 的最短路。（6分）
(4,v1)
V2 6
4 7 (0,0) V1 2
8 3 V3 (6,v2) 7
（8,v1）
最短路为：v1,v2,v3,v4,v5,v6 长度为：12
正确标号：4分；正确写出结论：2分
V4 (9,v3) (10,v2) 5 1 V6 (12,v5) (14,v4) 2 V5 (10,v4) (11,v2) (13,v3)
《运筹学》-期末考试-试卷A-答案
