2017年五邑大学运筹学复试仿真模拟三套题
● 摘要
一、简答题
1． 试写出求解最短径路的Dijkstra 算法的步骤。
【答案】Dijkstra 算法的步骤为:
（l ）给v s 以p 标号，P （v S ）二0，其余各点均给T 标号，T （v i ）=+∞。
（2）若v i 点为刚得到P 标号的点，考虑这样的点v i ，（v i ，vj ）属于E ，且v i 为T 标号。对v j 的T 标号进行如下修改:T （v j ）=min[T（v i ），p （v i ）+lij ]
（3）比较所有具有T 标号的点，把最小者改为P 标号，即:
当存在两个以
上最小者时，可同时改为P 标号。若全部点均为P 标号时停止，否则用代V i 转回（2）。
2． 简述对偶问题的“互补松弛性”。
【答案】互补松弛性:若当且仅当为
最优解。
分别是原问题和对偶问题的可行解。那么
，
二、计算题
3． 利用单纯型法求解上题的线性规划问题。
【答案】在上述约束条件中加入x 6, x 7, x 8，用单纯形法求解得到表1至表4。
表
1
表2
表
3
表
4
由计算得到最优下料方案是:按l 方案下料30根; 2方案下料10根:4方案下料50根。即需90根原材料, 可以制造100套刚架。
4． 某工程公司在未来L4月份内需完成三项工程:第一项工程的工期为1-3月份，总计需劳动力80人月; 第二项工程的工期为1-4月份，总计需劳动力100人月; 第三项工程的工期为3一4月份，总计需劳动力120人月。 该公司每月可用劳力为80人，但任一项工程上投入的劳动力任一月内不准超过印人。问该工程公司能否按期完 成上述三项工程任务，应如何安排劳力? （请将该问题归结为网络最大流问题求解）
【答案】可以构建图所示的网络图（弧上数字为最大流量）。
图
其中，结点1、2、3、4分别代表l 、2、3、4月份，结点5、6、7分别代表第一、二、三项工程。通过标号与调整，得到的最大流如图所示。
图
该最大流问题有多重最优解，上图仅给出一种。
所以该公司能按期完成上述三项工程任务，安排劳力的方案可以为:1月份，安排60人做第一项任务、20 人做第二项任务; 2月份，安排60人做第二项任务; 3月份，安排60人做第三项任务、20人做第一项任务; 4 月份，安排60人做第四项任务、20人做第三项任务。
5． 试用变尺法解，取初始点小点处梯度的模不大于0.5。
【答案】取初始点
显然，
，故
令
，可得
，于是
，要求近似极
相关内容
相关标签