2016年河北工业大学理学院913运筹学复试笔试最后押题五套卷
● 摘要
一、计算题
1． 某工程公司在未来l~4月份内需完成三项工程:第一项工程的工期为1~3月份，总计需劳动 力80人月; 第二项工程的工期为1~4月份，总计需劳动力100人月; 第三项工程的工期为3~4月份，总计需劳动力120人月。该公司每月可用劳力为80人，但任一项工程上投入的劳动力任一月内不准超过60人。问该工 程公司能否按期完成上述三项工程任务，应如何安排劳力? （请将该问题归结为网络最大流问题求解）
【答案】可以构建网络图（弧上数字为最大流量），如下图所示。
图
通过标号 与调整，得到的最大流如下图所示。
其中，结点1、2、3、4分别代表1、2、3、4月份，结点5、6、7分别代表第一、二、三项工程。
图
该最大流问题有多重最优解，上图仅给出一种。
第 2 页，共 59 页
所以该公司能按期完成上述三项工程任务，安排劳力的方案可以为:1月份，安排60人做第一项任务、20 人做第二项任务; 2月份，安排60人做第二项任务; 3月份，安排60人做第三项任务、20人做第一项任务; 4 月份，安排60人做第四项任务、20人做第三项任务。
2． 举例说明，当运输问题的最优解中所有的基变量均大于零时，该运输问题有无穷多最优解;
【答案】举例如下:
表
对非基变量求检验数，如表所示:
表
如表中空格（1，l ）的检验数是0，其他检验数都大于0，表明有无穷多最优解。
3． 设某工厂自国外进口一部精密机器，由机器制造厂至出口港有三个港口可供选择，而进口港又有三个可供选择，进口后可经由两个城市到达目的地，其间的运输成本如图中所标的数字，试求运费最低的路线。
图
【答案】设阶段变量k=1，2，3，4，依次表示4个阶段选择路线的过程; 状态变量s k 表示第k 阶段初可能处的位置; 决策变量x k 表示第k 阶段初可能选择的路线; 最优值函数
第 3 页，共 59 页 表示从第k
阶段点s k 开始至终点E 的最少运费， 则有
同理，
由此，可得出三条最优的运输路线:
4． 求解运输问题:
表
【答案】首先判断发量和收量相等;
第一步，用伏格尔法寻找得到初始基可行解
表
第二步，用位势法计算各空格处的检验数为:
表
第 4 页，共 59 页