2016年军事交通学院军事后勤学801运筹学考研内部复习题及答案
● 摘要
一、简答题
1． 简述求解最小费用最大流的赋权网络设置方法。
，有可行流f ，保持原网络各点， 【答案】解:对网络G=（ V ，E ，C ，d ）
每条边用两条方向相反的有向边代替，各边的权
②当边（vj 名）为原来G 中边（vi ，vj ）的反向边，令
2． 试写出标准指派问题的线性规划问题。 【答案】
A ij 表示工作人员i 做工作j 时的工作效益
则得线性规划模型为:
按如下规则:
3． 试说明C 一W 节约算法的基本思想，你认为还可用它解决哪些方面的问题? 举例加以说明。
【答案】（1）C 一W 节约算法的基本思想（以旅行商问题为例）:优先考虑将节约值最大的弧插入到旅行线路中， 这样在满足访问若干城市各一次且仅一次的条件下，最大限度地缩短了路程。 （2）举例。运用C 一W 节约算法:设n 个不同用户为n 个点，维修点为基点，n 个用户点中从点i 到点j 的 长度为工人骑摩托车的交通时间加上点i 与点j 维修时间总和的一半。优先考虑将节约值最大的长度加入工作线路中去进行迭代。
4． 对在多台设备上加工多个工件的工件排序问题来说，应如何衡量不同排序方案的优劣? 你认为应有哪 些准则? 这些准则的适用条件是什么? 请举出两个实例加以详细说明。
【答案】（l ）应根据工期最短、成本最低、质量最优等优劣标准来衡量不同排序方案的优劣。 （2）设备充分利用、总加工时间最短等某一或某几种目标函数最优。
（3）每个工件在m 台设备加工都有一定的先后顺序，工件在不同设备的加工顺序不同的情况不作考虑以及 信息掌握情况和资源约束等适用条件。
（4）举例。建筑施工流水作业问题:在不同的施工段上按一定的施工工艺进行施工，而施工工艺又由不同 的施工工序组成，每道施工工序都要消耗一定的人工费用，机械台班和材料费用，并且某些施工工序之间有一定的先后约束关系，如支起模板后才能浇注混凝土，而此问题关注不同施
使整个施工按照最短施工时间保持一定施工节拍进行流工工序如何搭接排序组成一定施工工艺，
水作业，同时消耗人、机、材等资源也合理。
二、计算题
5． 某产品从仓库A i （i=1， 2, 3）运往市场B j （j=1， 2, 3，4） 销售，已知各仓库的可供应量、各市场的需求量及从A 1仓库到B 1市场路径上的容量如表所示（表中数字0表示两点之
，请制定一个调运方案使从各仓库调运产品总量最多。 间无直接通路）
表
【答案】该问题是求最大流问题，由题得网络图，其中S 、D 是虚拟开始和结束点，各路径最大容量如图所示，初始流量为0:
图
（1）标号过程
①首先给S 标号（0,
，同理，）, 检查S , 在弧（S , A1）上，F SA1< CSA1，则给A 1标号（S , 20）
，A 3 （S , 100） 标号A 2（S , 20）
②任选一点A 1进行检查，在弧（A 1 , B1）上，F A1B1< CA1B1，则给B 1标号（A 1, 20）
F B1D < CB1D ，S- A1- ，③检查B 1 ，在弧（B l , D ）上，则给D 标号（B l , 20）这样找到了一条增广链，
B 1-D
（2）调整过程，由（1）知，=20, 得新的可行流量图，如下图所示。
图
依据上述方法，重复标号及调整过程，直到不存在增广链为止，最终得最大流量图，如下图所示。
图
调运方案如表所示.
表
6． 某工厂的生产任务最近波动很大，为降低成本宜雇佣临时工，但熟练的生产工人临时难以雇到，培训新 手的费用又高，今后四个月需要工人数量如下表所示:
表
相关内容
相关标签