五、(1)用逆序标号法求解下列线路网络A到G的最短路径。
（15） （6） B1 （15） （11） E1 9 C1 6 D1 9 8 （2） （15） 3 6 7 （4） 3 F1 2 （0） （17） 2 B2 8 8 E2 2 G A 4 3 9 3 （3） 3 9 7 5 7 F2 6 C2 3 D2 4 8 B3 （18）（12） （9） E3 （9） 解：用逆序标号法求图线路网络A到G的最短路径为： A→B1→C2→D2→E2→F1→G。 最短路径的距离为17。 (2)用避圈法或破圈法求出下图G的最小生成树T。
V2 10 V5 9 V7 10 V9 4 2 V4 3 7 V1 9 1 2 2 2 8 1 V3 8 V6 6 V8 3 V10
解：用避圈法求出下图G的最小生成树T如下图：
其权重为W（T）=4+2+1+3+1+2+2+3+2=20。
V2 V5 V7 V9 4 2 V4 3 V1 1 2 2 2 1 V3 V6 V8 3 V10
六、某公司有资金4万元，可向A，B，C三个项目投资，已知各项目不同投资额的相应效益值如下表所示。问如何分配资金可使总效益最大？
投 资 额 项目 0 1 2 3 4 A 0 52 68 78 80 B 0 52 65 70 86 C 0 64 70 78 89 解：设向A，B，C三个项目投资的资金分别为x1，x2，x3，g1(x1), g2(x2), g3(x3)分别为三个项目投资的效益值函数。则依题意得投资静态模型为：
第 31 页共40页
MaxZs.t?max{g(x1)?1g2(x2)?g3(x3)}
??x1?x2?x3?4???x1?0,x2?0,x3?0且为整数其动态规划的基本方程为：
?????f(s)?max{gkkk(xk)?fk?1(sk?1)}
f(s)?000其中：S0=0，S1=x1，S2=S1+x2，S3=S2+x3≤4,
f0(s0)?0,fff21(s1)?max0??{g(x1)?1fx1s10(s0)}?max0??{g(x1)},1x1s1(s2)?max0?{g(x2)?2ff1(s1)}
x2?s2{g(x3)?323(s3)?max0?(s2)}x3?s3取△=1，则x1，x2，x3只能在（0，1，2，3，4）上取值，用表格法求解如下：
X2 0 1 2 3 4 S1 X1(S1) g2(x2) 0 52 65 70 86 f1(s1) S2 0 0 0 0 0* 52* 65 70 86 1 2 3 1 2 3 52 68 78 1 2 3 52* 68 78 104* 117 120* 133* 130 122 3 78 130 4 89 89 4 4 80 4 80 X3 0 1 2 S2 X2(S2) g2(x3) 0 64 70 f2(s2) S3 0 0 0 1 2 3 4 0,1 1 1 2 52 104 120 133 4 133 184* 174 第 32 页共40页
从表中可以看出，当x3*=1，x2*=1，x1*=2时为最优解，即按向A，B，C项目分别投资2万元， 1万元和 1万元时，取得的总效益值最大为Z*=184（万元）。
七、用表上作业法求下列运输问题的最优解：
表中数字表示运费 销地 产地 B1 B2 B3 产量 A1 6 5 5 9 A2 2 10 4 8 A3 9 3 10 3 销量 6 8 6
解：用表上作业法的最小元素法求得Xij初始运输方案表如下：
Xij运输方案 销地 产地 B1 B2 B3 产量 A1 6 9－5－4 5 5 5 4 A2 A3 2 6 10 3 3 4 8－6－2 3－3 9 10 6－6 8－3－5 6－2－4 销量 由上表可知，基格个数=5=M+N-1=3+3-1。 判断运输问题是否是最优解，λij=λij－（ui+vj）,作ui,vj和λij表如下：
ui,vj和λij表 销地 ui 产地 B1 B2 B3 产量 A1 6 5| 9 0 5| |3 A2 2| 10 |6 4| 8 －1 A3 9 |8 3| 10 |7 3 －2 销量 vj
6 3 8 5 6 5 第 33 页共40页
因为所有非基格的λij≥0(i,j=1,2,3),得该运输问题的最优解：
X*?0???6?0?5034??2?， 0??最优值为Z*=5×5+5×4+2×6+4×2+3×3=74。
八、求以下网络容量图的最大流和最小割。 边上的数字（Cij，fij）=（容量，流量）
V1 (7,2) V5
(6,5) (4,3) (6,2) V2 V4 Vs (5,2) (4,0) (3,3) Vt
(8,4) (2,2) (10,6) (7,4) V3 V6 解：用标号法求得Vs→Vt的增广链为：
μ1：Vs→V1→V5→Vt δ1=1 μ2：Vs→V2→V4→V1→V5→Vt δ2=3
μ3：Vs→V3→V6→Vt δ3=3 如图
不能再找到增广链，根据最大流与最小割原理得，该网络的最大流=最小割=C(S,S)如图 6+3+9=18。 V1 (7,6) V5 (6,6) (4,0) (6,6) V2 V4 Vs (5,5) (4,3) (3,3) Vt
(8,7) (2,2) (10,9) (7,7) V3 V6 九、用分枝定界法求整数规划的最优解。
MaxZ?5x1?2x2s.t3x1?x2?12??2x1?2x2?10??x?0,x?0且为整数2?1
解：用矩形框图求解如下：（具体求解过程使用LP的图解法）
第 34 页共40页
X0*=（3.5，1.5） Z0*=20.5 X1≤3 Z?20.5Z?0X1≥4 X1*=（3，2） Z1*=19 X2*=（4，0） Z2*=20 Z?20Z?20 (3.5,1.5) -------------6分
由上图可知，该整数LP的最优解为：X*=（4，0），Z*=20。
十、用匈牙利法求解下列最优指派问题: 4项工件中由4个人分别完成，下表中为第i(i=1，2，3，4)个人从事工作Aj (j=1，
2，3，4)所需时间，试确定所需总时间最小的最优指派。 单位：小时 A1 A2 A3 A4 1 5 8 3 8 2 2 6 5 9 3 9 2 3 6 4 8 2 9 3 解：由题得，效率矩阵为：
???5W??2??9??886223539?min?2505???2???8?(3)行变换?0437??06?(2)???7014?????7?????6?(2)?6?6071???00013?(2)min540003174??6? 3??0??用圈零法圈零如下：
?2????7??6?54?0?3174??6? ?3????因为圈零个数=行数=4，
所以得所求问题的最优解为：
第 35 页共40页