线性规划习题(30)

0

V6

→5

第一次迭代 后的总流量

V3

第二次迭代： 选择路为 V1 →V2 →V5 →V6 。弧（V1 ，V2）的顺流流量为 6，决定了 pf=6，改

进的网络流量图如图所示：

V2

6 0 6 0

8 4

2

0 0 0 5

6 V5 12 6 0 6

11→

V1

6 5 5 6

0 0

V4

6 5

0

→11 V6

第二次迭代 后的总流量

0

V3 第三次迭代：选择路为 V1→V4 →V6 。弧（V1 ，V4）的顺流流量为 6， 决定了 pf=6，改进的网络流量图如图所示： V2

6 0 4 0 6 5 5 6 0 6 0 0 0 5 2 0 6

V5

6 6

17→

V4

V1

6

0 5

0

6

V6 17→

第三次迭代 后的总流量

V3 第四次迭代：选择路为 V1→V3→V4 →V2→V5→V6 。弧（V2 ，V5）的顺流流量 为 2，决定了 pf=2，改进的网络流量图如图所示： V2

6 0 0 2 2 4 0 5 3 5 7 4 6 0 6 2 0 2 5 0 5 第四次迭代 后的总流量 0 6 8 0

V5

6 4 6 8 6

V4

19→

V1

V6

19→

V3 第五次迭代：选择路为 V1→V3→V4→V5→V6 。弧（V1 ，V3）的顺流流量为 3， 决定了 pf=3，改进的网络流量图如图所示：

V2

6 0 2

0

8 3 2 5 2 0

V5

4 1 8 0 5 6 11

22→

V1

3

0 0 7 11 4 1

6 5 2 0

V4

V6

22→

第五次迭代 后的总流量

V3 在通过第五次迭代后在图中已找不到从发点到收点的一条路上的每一条弧顺流 容量都大于零，运算停止。我们已得到此网络的从 V1 到 V6 的最大流量，最大 流量为 22，也就是公路的最大流量为每小时通过 22 千辆车。 (16) 最小费用最大流问题 请求下面网路图中的最小费用最大流,图中弧(Vi , Vj)的赋权（Cij , bij） ，其中 Cij 为 从 Vi 到 Vj 的流量，bij 为 Vi 到 Vj 的单位流量的费用。 V2

（5，3） （2，4）

V4

（2，4）

V1

（4，1）

（1，1） （1，2）

（1，2）

V6

（5，2）

V3

（3，3）

V5

（17）一台机器、n 个零件的排序问题 某车间只有一台高精度的磨床， 常常出现很多零件同时要求这台磨床加工的情况， 现有六个零件同时要求加工，这六个零件加工所需要的时间如表所示： 零件 加工时间/小时 零件 加工时间/小时 1 1.8 4 0.9 2 2.0 5 1.3 3 0.5 6 1.5 我们应该按照什么样的加工顺序来加工这六个零件，才能使得这六个零件在车间 里停留的平均时间为最少？ 解：对于一台机器 n 个零件的排序问题，我们按照加工时间从少到多排出加工零 件的顺序就能使各个零件的平均停留时间为最少。 零件 加工时间/小时 停留时间 零件 加工时间/小时 停留时间 3 0.5 0.5 6 1.5 4.2 4 0.9 1.4 1 1.8 6.0 5 1.3 2.7 2 2.0 8

（18）两台机器、n 个零件 某工厂根据合同定做一些零件，这些零件要求先在车床上车削，然后再在磨床上 加工，每台机器上各零件加工时间如表所示： 零件 车床 磨床 零件 车床 磨床 1 1.5 0.5 4 1.25 2.5 2 2.0 0.25 5 0.75 1.25 3 1.0 1.75 应该如何安排这五个零件的先后加工顺序才能使完成这五个零件的总的加工时间 为最少？ 解：我们应该一方面把在车床上加工时间越短的零件，越早加工，减少磨床等待 的时间，另一方面把在磨床上加工时间越短的零件，越晚加工，也就是说把在磨 床上加工时间越长的零件，越早加工，以便充分利用前面的时间，这样我们得到 了使完成全部零件加工任务所需总时间最少的零件排序方法。