运筹期末复习题

5.（4分）见下图，现提供一网络，并提供一初始可行流，弧旁的数字（cij,fij）分别代表（容量，流量）。请找出一条增广链，请直接在图上标号。

6．（6分）求下图到的最短路。（需要写出主要的步骤）

7．（3分）用奇偶点图上作业法求解下图所示的中国邮递员问题，并求出最优解的总权？

8．（6分）根据下面的作业明细表绘制网络图。

表19.（10分）已知如下网络计划图，计算网络的时间参数，求网络计划的关键线路（事项的时间请直接标于图中，工序的时间需列表给出）。

八、已知网络如下图，每条有向边上数组为（cij，fij）（15分）

1)向x为何值时，网路上流为可行流？（2）求网络的最大流、最大流量。（3）证明（2）中得到的结论。(题中k=考生学号最后一位，0号写成10)

1、已知网络上某条链如下图，问：x为何值时，该链不是增流链，为什么？

x＝0（1分）。此时后向边为零边，不符合增流链定义（2分）。

八、已知网络如下图，每条有向边上数组为（cij，fij）（15分）

1)向x为何值时，网路上流为可行流？（2）求网络的最大流、最大流量。（3）证明（2）中得到的结论。(题中k=考生学号最后一位。0号写成10)

1）（3分）

2）网路上增流链ⅰ：（令k=1）

调整量θ＝1，调整后，（2分）

网络上增流链ⅱ：

调整量θ＝1。调整后2分）

最终网络图如下图：

2分）最大流量＝9，。（2分）

3）由标号法求出，求出截线如图所示。

而网络上的割c=9，即。

所以网络上流为最大流。（4分）

九(10分)、下图为一网络，网络中每条弧上的数字为该条弧的（容量，流量）。

1(6分)、求该网络的最大流和最大流量；

2(4分)、若想增加网络的最大流量，首先应改善哪些瓶颈弧的容量？

例：设有某种肥料共6个单位，准备给4块粮田用，其每块粮田施肥数量与增产粮食的关系如下表所示。试求对每块田施多少单位重量的肥料，才能使总的粮食增产最多。

所以最优解为2，2，0，2，最大增产量为134。

例某工厂有100太机器，拟分四个周期使用，在每一周期中有两种生产任务，据经验，把台机器投入第一种生产任务，则在一个周期内有台机器作废；余下的机器全部投入第二种生产任务，且有机器作废。在第一种任务中，每台机器可收益10个单位，而第二种任务中每台机器可收益7个单位，问怎样分配机器，能使总收益为最大？

六、某公司打算将3千万元资金用于改造扩建所属的3个工厂，每个工厂的利润增长额与所分配的投资有关。各工厂在获得不同的投资额时所能增加的利润如下表所示，问应如何分配资金，使公司总的利润为最大（15分。

石油输送管道铺设最优方案的选择问题：如图所示，其中a为出发点，e为目的地，b、c、d分别为三个必须建立油泵加压站的地区，其中的b1、b2、b3;c1、c2、c3;d1、d2分别为可供选择的各站站点。图中的线段表示管道可铺设的位置，线段旁的数字为铺设管线所需要的费用，问如何铺设管道才使总费用最小？