德州学院期末考试试卷(b卷)评分标准。
2007 至 2008 学年第 1 学期)
课程名称: 运筹学考试时间: 120 分钟。
一、名词解释: (每小题2分,共10分)
1.欧拉回路:连通图g中,若存在一条回路,经过每边一次且仅一次,则称这条回路为欧拉回路。
2.割集:容量网络g=(v,e,c),vs,vt为发、收点,若有边集e’为e的子集,将g分为两个子图g1,g2,其顶点集合分别记为s,s’,s∪s’=v,s∩s’=,vs,vt分属s,s’,满足:(1)g(v,e-e')不连通;(2)e“为e’的真子集,而g(v,e-e”)仍连通,则称e’为g的割集。
3.队长:队长是指系统中的顾客数,即排队等待的顾客数与正在接受服务的顾客数之和。
4.单时差:工作的单时差是指在不影响紧后工作的最早开工时间条件下,此工作可以延迟其开工时间的最大幅度。工作的单时差等于其紧后工作的最早开工时间与本工作的最早开工时间之差。
5.存储策略:所谓存储策略,是指决定什么情况下对存储进行补充,以及补充数量的多少。常见的存储策略有:t-循环策略、(t,s)策略、(s,s)策略。
评分标准:1. 不要求学生死记教材上的定义,只要答对意思,就可以得满分。
2. “欧拉路”无连通图减1分。3.
“工作的单时差” 答对前面的部分和后面的部分都可得满分,答机动时间也得满分。4. 其他情况酌情给分。
二、(24分)解:先将问题改写为: max
st.(2分)
列出单纯形表,并用单纯形法求解步骤进行计算,其过程如下:(2分)
因2≥1≥0,所以选x1进基,因0≤1,故选x4出基,则得(4分)
得最优解为:(6,0,0),代入目标函数得z = 12。(2分)
1)目标函数变为 max 时,直接反映到最终单纯形表中得:
因x2的检验数1≥0,所以原最优解已经不是新问题的最优解;选x2进基,因10/3≤6/1,故选x5出基,则得。
得最优解为:(8/3,10/3,0),代入目标函数得z = 16 。(5分)
2)约束右端项由变为时;有=
将上述结果反映到单纯形表中得:
此时,上表中的解仍为可行解,故最优解为:(3,0,0),代入目标函数得z = 6 。(5分)
3)增添一个新的约束条件。
将原最优解(6,0,0)代入新的约束条件。 ,得知:原最优解满足新的约束条件,所以原最优解还是此时的最优解。(4分)
评分标准:1. 单纯形法求最优解10分,若结果不正确,但步骤正确可得8分。2.(1)、(2)小题5分,(3)小题4分。3. 其他情况酌情给分。
三、(12分)解:由题意知:该问题为产销平衡的运输问题,其运输表如下表。(4分)
由最小元素法求得上述运输问题的初始基可行解,并使用位势法计算非基变量的检验数(括号内),得下表。(10分)
在表中,由于所有检验数均大于等于 0 ,所以表中的解就是最优解,其最小运费为 89万元 。即化肥分配计划为:化肥厂a的化肥4单位运往面产粮区乙,化肥厂a的化肥3单位运往产粮区丁,化肥厂b的化肥6单位运往产粮区甲,化肥厂b的化肥2单位运往产粮区乙,化肥厂c的化肥3单位运往产粮区丙,其总费用最小,为89万元 。
(12分)
评分标准:1. 得运输表4分。2. 运输问题求解6分。3.得出最终结论2分4. 其他情况酌情给分。
四、(12分)解:首先将求“总的得分最大”问题变为“总得分最小”问题。选择上表中最大的分数1.4,用1.4减去表中的能力评分得下表:
使用匈牙利方法求上述指派问题的最优解。
第一步:变换系数矩阵。
第二步:确定独立零元素。
第三步:继续变换系数矩阵。
第四步:确定独立零元素。
已经找到5个独立的零元素,故可以确定指派问题的最优指派方案。即a1去做b1工作, a2去做b3工作, a3去做b4工作, a4去做b5工作, a5去做b2工作;其总的得分为:1.
3 + 1.3 + 1.2 + 1.
4 + 0.9 = 6.1
评分标准:1. 本题主要考察学生指派问题的应用。
2.变换系数矩阵得4分,求最优解给6分,得出结论给2分,若结果不正确,但步骤正确可得6分。3.
其他情况酌情给分。
五、(12分)解:1. 建立模型。
令k表示今后四个月的序号。
设sk为第k月初(或第k -1月末)的库存量,xk为第k月的生产量,用dk表示第k月的需求量;则sk+1=sk+xk-dk。设fk(sk,xk)为第k月初到第四月末的生产费用(在库存sk,生产xk)fk*(sk)为第k月初到第四月末的最低生产费用。由题意知:
k = 4,3,2,1
函数基本方程为。
f5 (s5)=0
fk*(sk) =k = 4,3,2,1
xk = 且对于不同阶段,xk还会增加新的约束。
2.逆序递推求解。
1)k=4
由问题假设知,该月末无库存。故s5=0。由状态转移方程等可得如下表:
2)k=3
由状态转移方程等可得如下表:
3)k=2
由状态转移方程等可得如下表:
4)k=1
由状态转移方程等可得如下表:
3. 顺序递推,得出结论。最有解为:x*1=5,x*2=0,x*3=5,x*4=0,f*1=14.8(千元)
评分标准:1. 列出动态规划模型4分,求解9分。
2. 结果正确,有简单步骤说明即可得满分。3.
若结果不正确,但步骤正确可得6分。4. 其他情况酌情给分。
六、(10分)解: 求出任意两点间的最短路径如表所示:
由表中max一列中取最小的一个值,得小学应建在c村。
评分标准:1. 结果正确,有简单步骤说明即可得满分。2. 若结果不正确,但步骤正确可得5分。3. 其他情况酌情给分。
七、(10分)解:用图上计算法计算的事项时间参数和工作时间参数如下图:
评分标准:1. 结果正确,有简单步骤说明即可得满分。2. 若结果不正确,但步骤正确可得8分。3. 其他情况酌情给分。
八、(10分)解:由题意可知c3=10元,r=100件/天,k=5元/件,c1=0.005元/件。
由经济批量公式得:
6.32(天)
632(件)
3.16(元/天)
所以,每隔6.32天进货一次,每次进货该商品632件,能使总费用(存储费和订购费)为最少,平均约3.16元/天。若按年计划,则每年大约进货58次,每次进货630件。
评分标准:1. 公式正确,计算结果错误得8分。2. 其他情况酌情给分。
运筹学答案
1.1 讨论下列问题 1 在例1.1中,假定企业一周内工作5天,每天8小时,企业设备a有5台,利用率为0.8,设备b有7台,利用率为0.85,其它条件不变,数学模型怎样变化 2 在例1.2中,如果设xj j 1,2,7 为工作了5天后星期一到星期日开始休息的营业员,该模型如何变化 3 在例1.3中,...
运筹学答案
1 进行矩阵合成,得wfr 0.5,0.3,0.2 结论是,有50 的把握性认为该干部属于优秀,有30 的把握性认为该干部属于良好,有20 的把握性认为该干部属于一般。对矩阵a c用积累法求特征向量和最大特征根。按列正规化,1分 按行相加,得 0.7815,1.9001,0.3184 t 1分 正规...
运筹学A答案
运筹学 试卷a参 及评分标准。一 简答题。1 作为整个过程的最优策略具有这样的性质 即无论过去的状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简言之,一个最优策略的资策略总是最优的。5分 2 无可行解 有唯一可行解 有无穷多最优解 有可行解无最优解。5分 二 将下列模型...