德州学院期末考试试卷(a卷)评分标准。
2007 至 2008 学年第 1 学期）
课程名称： 运筹学考试时间： 120 分钟。
一、名词解释：（每小题2分，共10分）
1．欧拉道路：连通图g中，若存在一条道路，经过每边一次且仅一次，则称这条路为欧拉道路。
2．排队长：排队长是指系统中正在排队等待服务的顾客数。
3．总时差：工作的总时差是指在不影响任务总工期的条件下，某工作可以延迟其开工时间的最大幅度。工作的总时差等于它的最迟完工时间与最早完工时间之差。
4．对策论：亦称博弈论或竞赛论，是研究具有对抗或竞争性质现象的数学理论和方法。
5．存储策略：所谓存储策略，是指决定什么情况下对存储进行补充，以及补充数量的多少。常见的存储策略有：t-循环策略、（t，s）策略、（s，s）策略。
评分标准：1. 不要求学生死记教材上的定义，只要答对意思，就可以得满分。
2. “存储策略”答对句号前面的部分即可得满分，仅答后面的部分可得1 分。3.
“欧拉回路”无连通图减1分。4. “工作的总时差” 答对前面的部分和后面的部分都可得满分，答机动时间也得满分。
5. 其他情况酌情给分。
二、（24分）
解：将线性规划问题化为：max
st2分）因此，可得如下初始单纯形表：（5分）
因3≥2≥1，所以选x2进基，因3/(4/3)≤1/(1/3)，故选x5出基，则得。
因5/4≥0，所以选x1进基，因(1/4)/(1/4)≤(9/4)/(1/4)，故选x4出基，则得。
最优解为：（1，2，0）。（10分）
1）目标函数中变量x3的系数变为6 时，得如下单纯形表，并用单纯形法求解步骤进行计算，其过程如下：
因2≥0，所以选x3进基，因2≥0，故选x2出基，则得。
得最优解为：（2，0，1），代入目标函数得z = 10 。（14分）
2）设目标函数中变量x1和x2的系数为c1、c2 ，则由原单纯形表得如下单纯形表：
若要保持原问题最优解不变，则应有所有检验数均小于等于0；即。
和即和 （18分）
3）约束右端项由变为；有＝ =
将上述结果反映到单纯形表中得：
此时，上表中的解仍为可行解，故最优解为：（5，1，0），代入目标函数得z = 13 。（21分）
4）增加一个新的变量x6，, c6 = 7 ；
检验数 c6- z6 = 7 - 3*2 = 1 ，将上述结果反映到单纯形表中得：
因x6的检验数1≥0，所以原最优解已经不是新问题的最优解；选x6进基，因3≥0，故选x1出基，则得。
故最优解为：（0，2，0，0，0，1/3），代入目标函数得z = 6 + 7/3 = 25/3 。（24分）
评分标准：1. 单纯形法求最优解10分，若结果不正确，但步骤正确可得8分。2.（1）、（2）小题4分，（3）（4）小题3分。3. 其他情况酌情给分。
三、（12分）解：由题意知：该问题为产量大于需量的不平衡问题，可以假想一个虚拟的面食加工厂4，其需量为（20+30+20）-（15+25+20）= 10 ，从而变为平衡问题。
又该题求总效益最大的面粉分配方案，可以转化为下面运输问题，运往虚拟的面食加工厂4的运费为 0 ，如下表。
则容易得知，其总效益就是总运费的相反数。（4分）
由最小元素法求得上述运输问题的初始基可行解，并使用位势法计算非基变量的检验数（括号内），得下表。（10分）
在表中，由于所有检验数均大于等于 0 ，所以表中的解就是最优解，其最小运费为 425 。即面粉分配计划为：面粉厂ⅰ的面粉20单位运往面食加工厂3，面粉厂ⅱ的面粉15单位运往面食加工厂1，面粉厂ⅱ的面粉15单位运往面食加工厂2，面粉厂ⅲ的面粉10单位运往面食加工厂2，面粉厂ⅲ的面粉10单位不向外运输，其总效益最大，为425元 。
（12分）
评分标准：1. 变为平衡问题2分。2. 变为总效益是总运费的相反数的运输问题2分。3. 运输问题求解6分，得出结论2分。4. 其他情况酌情给分。
四、（12分）将原问题化成标准形式得：
max st.
用单纯形法节其松弛问题，得最终单纯形表：
因为5/3和8/3的分数部分相同，对第一行产生割平面约束为：
引入松弛变量，得割平面方程：
并入上表并用对偶单纯形法求解，得下表：
类似对第三行产生个平面约束为：
引入松弛变量，得割平面方程：
并入上表并用对偶单纯形法求解，得下表：
最优解为x=（0，4，2，0，1，0）
评分标准：1. 本题主要考察学生对偶单纯形方法和整数规划概念的理解。
2.使用单纯形方法求得松弛问题正确的最优解得6分。求出整数规划的最优解得6分。
3. 若结果不正确，但步骤正确可得6分。4.
其他情况酌情给分。
五、（12分）解：设第i种产品装载的件数为xi(i=1,2,3) 。则问题可表示为：
max 建立动态规划模型，由于决策变量取离散值，所以可用列表法求解。
当k=1时，
计算结果见下表：
当k=2时，
计算结果见下表。
当k=3时， =max=500
此时x3*=0，递推可得全部策略为：x1*= 5 ，x2*= 0 ， x3*= 0 。
评分标准：1. 列出动态规划模型4分，求解8分。
2. 结果正确，有简单步骤说明即可得满分。3.
若结果不正确，但步骤正确可得6分。4. 其他情况酌情给分。
六、（10分）
解：第一步：标号，找到一条可增广链；第二步：调整流量；第三步：重复第。
一、第二步直至找不到可增广链为止。
本题共可以找到三条可增广链，分别为：s,a,c,d,t，调整量为2；s,c,d,e,t，调整量为1；s,b,e,t，调整量为3。或者为：
s,c,d,t，调整量为2；s,c,d,e,t，调整量为1；s,b,e,t，调整量为3。
最后调整结果如图，其中虚线为切割线。
其最大流为13 。
或。评分标准：1. 若结果不正确，但步骤正确可得5分。2. 若结果正确，但无步骤可得9分。3.其他情况酌情给分。
七、解：用图上计算法计算的事项时间参数和工作时间参数如下图。
关键路径为a-c-e-h-i
评分标准：1. 结果正确，有简单步骤说明即可得满分。2. 若结果不正确，但步骤正确可得5分。3. 其他情况酌情给分。
八、解：本题可以看成一个m/m/1/∞排队问题，其中。
1）店内空闲的概率：
2）有4个顾客的概率： =0.03125
3）至少有一个顾客的概率：p=1-p0= 0.5
4）店内顾客的平均数： =1
5）等待服务的顾客的平均数： =1-0.5=0.5
6）平均等待修理时间：
评分标准：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分 二 将下列模型...