内容发布更新时间 : 2024/12/27 4:14:40星期一 下面是文章的全部内容请认真阅读。

??fk(sk)?max?rk(sk,xk)?fk?1(sk?1)?,k?3,2,1 ???f4(s4)?0 ——3分

（1）当k＝3时，s3＝4x3 X3 S3 0 0 1 2 3 4 5 6 7 8 9 10

（2）当k＝2时，s3X2 S2 0 0 1 2 3 4 5 6 7 8 9 10

（3）当k＝1时，s20+0=0 0+0=0 0+0=0 0+0=0 0+180=180 0+180=180 0+180=180 0 0 0 0 0 0 0 0 0 0 0 r3(s3,x3) 1 — — — — 180 180 180 180 180 180 180 2 — — — — — — — — 360 360 360 f3(s3) 0 0 0 0 180 180 180 180 360 360 360 x3* 0 0 0 0 1 1 1 1 2 2 2 ——3分 ?s2?3x2

r2(s2,x2)＋f3(s3) 1 — — — 140+0=140 140+0=140 140+0=140 140+0=140 2 — — — — — — 280+0=280 280+0=280 280+0=280 280+0=280 3 — — — — — — — — 420+0=420 0 0 0 140 180 180 280 320 360 420 460 0 0 0 1 0 0 2 1 0 2 1 f2(s2) x2* 0+180=180 140+180=320 0+360=360 140+180=320 0+360=360 140+180=320 0+360=360 140+180=320 280+180=460 420+0=420 ——3分 ?s1?2x1

r1(s1,x1)＋f2(s2) f1(s1)x1 6

1 S1 10 0 0+460= 460

1 100+360=460 2 200+280=480 3 300+180=480 4 400+0= 400 5 500+0=500 * 500 5 ——3分 当x1*=5时，s2?0，x2*=0，s3?0，x3*=0，即运送第一种产品5件，最优值为500元。

——3分

(本题15分)七?如下图，从V0派车到V8中间可经过V1，V2，V3，V4，V5，V6，V7各站，若各站间道路旁的数字表示单位时间内此路上所能通过的最多车辆数，问应如何派车才能使单位时间到达V8的车辆最多?

V210351O15V0V115V410V610V7V510V84540403020V3

解：此为一个网络的最大流问题，用麦克逊标号法求解。首先需要对网络的标号进行改进。 （1）选择路为v0—v2—v5—v8

V5 0 10 V2 0

10 10 0 10 V8 v 010

（2）选择路径v0—v3—v7—v8 30 v0 20 20 0

V3

7

V8 20 25 20 V7

30

（3）选择路径v0—v3—v6—v7—v8

V8 30

V6 15 40 0 10 40 v0 10 V 7 10

30 20

V3

找不到顺流容量大于零的路了，则已经找到了最大流，最大流为40。 10 V5 V 2

10 10

V8 30 10 40 v0 V7 10 V 6 20 30

V3

——15分，选择路的先后可不同，计算出最大流可得13分，最后进行最大流量分配得2分，分配方案不唯一，正确即可得分。

8