运筹学答案

发布 2022-09-15 11:13:28 阅读 7946

德州学院期末考试试卷(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.对策论:亦称博弈论或竞赛论,是研究具有竞争或对抗性质现象的数学理论和方法。

评分标准:1. 不要求学生死记教材上的定义,只要答对意思,就可以得满分。

2. “欧拉道路”无连通图减1分。3.

“工作的单时差” 答对前面的部分和后面的部分都可得满分,答机动时间也得满分。4. 其他情况酌情给分。

二、(24分)解:先将问题改写为:

max st.(2分)

列出单纯形表,并用单纯形法求解步骤进行计算,其过程如下:

6分)因2≥1≥0,所以选x1进基,因0≤1,故选x4出基,则得(8分)

得最优解为:(6,0,0),代入目标函数得z = 12。(10分)

1)目标函数变为 max 时,直接反映到最终单纯形表中得:

因x2的检验数1≥0,所以原最优解已经不是新问题的最优解;选x2进基,因10/3≤6/1,故选x5出基,则得。

得最优解为:(8/3,10/3,0),代入目标函数得z = 16 。(15分)

2)约束右端项由变为时;有=

将上述结果反映到单纯形表中得:

此时,上表中的解仍为可行解,故最优解为:(3,0,0),代入目标函数得z = 6 。(19分)

3)增添一个新的约束条件。

将原最优解(6,0,0)代入新的约束条件。 ,得知:原最优解不满足新的约束条件,所以原最优解不是此时的最优解。

在新的约束条件。中,加松弛变量x6 ,得;即,反映到单纯形表中得:

因为x1列不是单位向量,故需进行变换,得下面单纯形表。下表中④⑤行同上表中的①②行,下表中⑥行由以下初等变换得到:⑥=

因-8≤0,使用对偶单纯形法求解,选x6出基,因1/3≤2≤3,故选x3进基,则得。

故最优解为:(10/3,0,8/3),代入目标函数得z = 28/3 。(24分)

评分标准:1. 单纯形法求最优解10分,若结果不正确,但步骤正确可得8分。2.(1)、(3)小题5分,(2)小题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分)解:使用匈牙利方法求上述指派问题的最优解。

第一步:变换系数矩阵。(4分)

第二步:确定独立零元素。(10分)

已经找到4个独立的零元素,故可以确定指派问题的最优指派方案。即甲去加工c工件, 乙去加工a工件, 丙去加工d工件, 丁去加工b工件;其总的加工时间最少,为:4 + 11 + 5 + 9 = 29 。

(12分)

评分标准:1. 本题主要考察学生指派问题的应用。

2.变换系数矩阵得4分,求最优解给6分,得出结论给2分,若结果不正确,但步骤正确可得6分。3.

其他情况酌情给分。

五、(12分)解:4个时期分为4个阶段,sk为状态变量,表示第k阶段开始时的库存量,xk为决策变量,表示第k阶段的生产量,gk表示第k阶段对产品的需求量。

建立动态规划模型:(4分)

其中,由于决策变量取离散值,所以可用列表法求解。

当k=4时,,计算结果见下表:

当k=3时,,计算结果见下表:

当k=2时,,计算结果见下表:

当k=1时, =min=67

此时x1*=5,递推可得全部策略为:x1*= 5 ,x2*= 6 ,x3*= 0 ,x4*= 0。(12分)

评分标准:1. 列出动态规划模型4分,求解9分。

2. 结果正确,有简单步骤说明即可得满分。3.

若结果不正确,但步骤正确可得6分。4. 其他情况酌情给分。

六、(10分)解:第一步:确定初始可行方案。

第二步:调整可行方案,使重复边最多为一次。

第三步:检查图中每个初等圈是否满足定理条件,如不满足则进行调整,直至满足为止。

解为下图:评分标准:1. 结果正确,有简单步骤说明即可得满分。2. 若结果不正确,但步骤正确可得5分。3. 其他情况酌情给分。

七、(10分)解:用图上计算法计算的事项时间参数和工作时间参数如下图:

评分标准:1. 结果正确,有简单步骤说明即可得满分。2. 若结果不正确,但步骤正确可得5分。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分 二 将下列模型...