《运筹学》课程教学资源（实验讲义）实验七 网络最大流

实验七网络最大流实验目的：用Exce1软件求解网络最大流问题、最小费用最大流问题。操作步骤：1)建立电子表格模型；2)使用Exce1规划求解网络最大流问题、最小费用最大流问题；3)结果分析；在Excel或Word实验报告，电子表格模型和结果分析等。1，如果图5--2中V表示仓库，V表示商店，现要从仓库从运送物资到商店，途中弧表示交通线，弧旁边括号内的数值为（交通线上运输能力限制，单位运价）。（1）求从仓库运10单位的物资到商店的最小费用是多少？（2）求网络的最大流求两络的取人讯。V(7, 1)(10,4)V.(2, 6)(5, 2)(4, 2)(8, 1)V2(10, 3)图5—2网络图RT解第（1）问是一个最小费用流问题（i）决策变量：本问题的决策变量是每条交通路线上的运输量，设f，为交通路线V到V，（节点V到节点V）的运输量（流量）。（ii）目标函数：本问题的目标是总运输费用最小，即：Minz=4f+1f2+1f,+6fi3+2f21+3f23+2f3（iii）约束条件（节点净流量、弧的容量限制、非负）：①供应点V：fs1+fs2=10

实验七 网络最大流 实验目的：用 Excel 软件求解网络最大流问题、最小费用最大流问题。 操作步骤： 1)建立电子表格模型； 2)使用 Excel 规划求解网络最大流问题、最小费用最大流问题； 3)结果分析；在 Excel 或 Word 实验报告，电子表格模型和结果分析等。 1，如果图 5-2 中 Vs 表示仓库， Vt 表示商店，现要从仓库从运送物资到商店，途 中弧表示交通线，弧旁边括号内的数值为（交通线上运输能力限制，单位运价）。 （1）求从仓库运 10 单位的物资到商店的最小费用是多少？ （2）求网络的最大流 解 第（1）问是一个最小费用流问题 （i）决策变量：本问题的决策变量是每条交通路线上的运输量，设 ij f 为交通路 线 Vi 到 Vj （节点 Vi 到节点 Vj ）的运输量（流量）。 （ii）目标函数：本问题的目标是总运输费用最小，即： s s t t Minz f f f f f f f = 4 1 +1 2 +1 1 + 6 13 + 2 21 +3 23 + 2 3 （iii）约束条件（节点净流量、弧的容量限制、非负）： ①供应点 Vs ： f s1 + f s2 =10

②转运点V：（f+fi）-（fsi+f2）=0转运点V：（f21+f23）-fs2=0转运点V：fs,-（fi3+f23)=0③需求点V：fi.+f3,=10④弧的容量限制：fsi ≤10, fs2 ≤8, fi ≤7, fi3 ≤2, f21≤5, f23 ≤10, f3t ≤4?非负：fs1fs2fit，fi3f21f23f3t≥0得数学模型为：Minz=4f,+1fs2+1f,+6fi3+2f21+3f23+2fs1 +fs2 =10(fi, + fi3)-(fs + 21)=0(f21+f23)-fs2 =0J3r-(fi3+23)=0fir+fsr=10fs1≤10,fs2≤8,fi,≤7,i3≤2,f21≤5,f23≤10,f3,≤4fs1s2firsJi3J21J23sf3,≥0习题1第（1）问的电子表格模型如图5-3所示Excel的求解结果为：从仓库10单位的物资到商店的运送方案如图5-3中的B4;D10单元格所示，此时的总运费最低，为48

②转运点 V1： (f 1t + f 13 )−(f s1 + f 21) = 0 转运点 V2： (f 21 + f 23 )− f s2 = 0 转运点 V3： f 3t −( f 13 + f 23) = 0 ③需求点 Vt : f 1t + f 3t =10 ④弧的容量限制： f s1 10, f s2  8, f 1t  7, f 13  2, f 21  5, f 23 10, f 3t  4 ⑤非负： f s1 , f s2 , f 1t , f 13, f 21, f 23, f 3t  0 得数学模型为： s s t t Minz f f f f f f f = 4 1 +1 2 +1 1 + 6 13 + 2 21 +3 23 + 2 3 f s1 + f s2 =10 (f 1t + f 13 )−(f s1 + f 21) = 0 (f 21 + f 23 )− f s2 = 0 f 3t −( f 13 + f 23) = 0 f 1t + f 3t =10 f s1 10, f s2  8, f 1t  7, f 13  2, f 21  5, f 23 10, f 3t  4 f s1 , f s2 , f 1t , f 13, f 21, f 23, f 3t  0 习题 1 第（1）问的电子表格模型如图 5-3 所示 Excel 的求解结果为：从仓库 10 单位的物资到商店的运送方案如图 5-3 中的 B4;D10 单元格所示，此时的总运费最低，为 48

ABCDE习题1（1）-23女到流量容量单位送价节点4净流量Vs供应/需求V12870533L105dVsVs1010V2-01VI6I0V10Vt72501V210二V1V36V300V2=V12Vt9-10-10V2A3310V3Vt1d1112总运费48规划求解参数规划求解选顶区域名称单元格B4:B10设置目标单元格）：总运费国国采用线性模型（）单位运价G4:G10可假定非负）王等于：○最大值）量小值C4:C10供应需求L4:L8可变单元格节点14:18$DS4:SD$10净流量J4:J8流量约束0：D4:D10容量F4:F10净流量=供应需求总运费流量仁容量D123净流量4=SUMIF（从，节点，流量）-SUNMIF（到，节点，流量）5=SUMIFC从，节点，流量）-SUMIF（到，节点，流量）=SUMIF（从，节点，流量）-SUMIF（到，节点，流量）6SUMIF（从节点，流量）-SUMIF（王，节点，流量）A=SUMIF（从，节点，流量）-SUMIF（到，节点，流量）:P12总运费=SUMPRODUCT（单位运价，流量）图5-3习题1第（1）问的电子表格格第（2）问是一个最大流问题。（i）决策变量：与第（1）问相同。（ii）目标函数：本问题你的目标是求网络的最大流，即从仓库V运送物资的最大量。Maxz=f,I+fs2（iii）约束条件（转运点净流量为0，弧的容量限制、非负）：①转运点V：（f+fi）-(f+fa)=0转运点V：（f21+23）fs2=0转运点V：3,-（fi3+f23)=0

第（2）问是一个最大流问题。 （i）决策变量：与第（1）问相同。 （ii）目标函数：本问题你的目标是求网络的最大流，即从仓库 Vs 运送物资的最 大量。 s1 s2 Maxz = f + f （iii）约束条件（转运点净流量为 0，弧的容量限制、非负）： ①转运点 V1： (f 1t + f 13 )−(f s1 + f 21) = 0 转运点 V2： (f 21 + f 23 )− f s2 = 0 转运点 V3： f 3t −( f 13 + f 23) = 0

②弧的容量限制：sl≤10,fs2≤8,fit≤7,i3≤2,21≤5,J23≤10,f3t≤4③非负：fs1,fs2,fit,fi3,f21,f23,fs,≥0得数学模型为：Maxz=fsi+fs2(fit+fi3)-(fsi+f21)= 0(f21+f23)-fs2 =0J3-(fi3+f23)=0fsl≤10, fs2 ≤8, i, ≤7,fi3≤2, f21 ≤5, f23 ≤10, f3, ≤4fs1fs2fr,fi3,21f23f3,≥0习题1第（2）问的电子表格模型如图5-4所示

②弧的容量限制： f s1 10, f s2  8, f 1t  7, f 13  2, f 21  5, f 23 10, f 3t  4 ③非负： f s1 , f s2 , f 1t , f 13, f 21, f 23, f 3t  0 得数学模型为： s1 s2 Maxz = f + f (f 1t + f 13 )−(f s1 + f 21) = 0 (f 21 + f 23 )− f s2 = 0 f 3t −( f 13 + f 23) = 0 f s1 10, f s2  8, f 1t  7, f 13  2, f 21  5, f 23 10, f 3t  4 f s1 , f s2 , f 1t , f 13, f 21, f 23, f 3t  0 习题 1 第（2）问的电子表格模型如图 5-4 所示