高中二年级数学选修：最小费用最大流与网络分析应用教学设计

高中二年级数学选修：最小费用最大流与网络分析应用教学设计【教学设计概述】本节内容属于高中数学选修课程“图论初步”或“运筹学初步”中的核心专题，旨在引导学生从实际生活中的网络问题出发，抽象出图论模型，掌握最小费用最大流问题的基本概念、算法思想及其在现实中的应用，同时拓展网络分析的多元应用场景。通过本课学习，学生不仅能深化对图论与线性规划的理解，更能培养数学建模、逻辑推理与优化决策的数学核心素养。本设计以“问题驱动—模型建构—算法探究—应用迁移”为主线，突出学生主体地位，强调数学与工程、经济、管理等领域的交叉融合。一、教学目标【核心素养导向】1.知识与技能：理解网络流的基本要素（源点、汇点、容量、费用、可行流、最大流），掌握最小费用最大流问题的数学模型与连续最短路算法（亦称“最小费用路算法”或“增广路算法”）；能够运用算法思想求解简单的最小费用最大流问题；了解网络分析的典型应用（如运输问题、指派问题、关键路径、网络可靠性等）。2.过程与方法：通过“情境—抽象—求解—解释”的探究过程，体会图论建模的方法；在算法步骤的分解与手工模拟中，培养逻辑思维与计算思维；通过小组合作分析实际案例，提升问题解决能力。3.情感态度价值观：感受数学优化在资源调配、成本控制中的巨大价值，树立科学决策意识；感悟数学与现实世界的深刻联系，激发学习数学的兴趣。二、教学重难点【重点】最小费用最大流的概念界定；连续最短路算法的原理与步骤；网络分析中典型模型的转化。【难点】算法中“费用”与“距离”的耦合理解；负费用边与对偶势函数的处理；将实际问题抽象为网络流模型时的变量设定与约束构建。三、教学方法与手段【多元融合】采用启发式讲授、案例教学、小组协作探究、GeoGebra或网络流模拟软件演示相结合的方式。利用多媒体课件展示网络图动态增广过程，辅助学生直观理解算法。穿插课堂即时练习与变式训练，强化核心技能。四、教学准备【资源与工具】教师准备：教学设计方案、多媒体课件（含动态演示）、导学案、课后拓展阅读材料。学生准备：预习教材相关章节，复习最大流问题与最短路径问题，每人准备好铅笔、直尺、草稿纸。五、教学过程（一）导入新课教师呈现实际情境：某快递公司需从配送中心（源点）将货物运往客户点（汇点），运输网络中各条线路有运输容量限制（如每小时的包裹上限）和单位运输成本（如每公里运费）。公司希望在达到最大运输量的前提下，使总运输成本最小。如何设计最优运输方案？此问题正是“最小费用最大流问题”的核心。引导学生回顾已学的最大流问题（只求最大流量，不计成本），自然过渡到“流量最大”与“费用最小”的双重目标。揭示课题，明确学习任务。（二）新知探究——55最小费用最大流问题【基础概念建立】教师首先系统讲解网络流的基本要素：有向图D=(V,A)，指定源点s和汇点t；每条弧(i,j)有容量c(i,j)（非负）和单位费用w(i,j)（可为负，但需避免负环）；一个可行流f需满足容量限制（0≤f(i,j)≤c(i,j)）和流量守恒（除s,t外，流入等于流出）；流量值v(f)等于源点净流出量。在此基础上，定义“最小费用最大流”：在所有流量值达到最大的可行流中，使总费用∑w(i,j)·f(i,j)最小的流。【重要】强调最小费用最大流不是简单先求最大流再优化费用，因为不同最大流对应的费用可能差异很大。必须同步考虑流量与费用的耦合。【数学模型呈现】给出线性规划形式：目标函数min∑w(i,j)·f(i,j)；约束条件：0≤f(i,j)≤c(i,j)；∑{j:(s,j)}f(s,j)∑{j:(j,s)}f(j,s)=v；∑{j:(i,j)}f(i,j)∑{j:(j,i)}f(j,i)=0（i≠s,t）；v为最大流值（需预先或同时确定）。说明这是带参数v的优化问题，通常先求最大流值v_max，再在流量为v_max的可行域中优化费用。【算法引入】连续最短路算法（SuccessiveShortestPathAlgorithm）思想：从零流开始，每次在残余网络中寻找从s到t的“最小费用路”（即单位费用之和最小的增广路），沿该路增广尽可能大的流量（受路径上最小残余容量限制），直至不存在增广路（即达到最大流）。关键在于如何定义残余网络中的“费用”以及如何处理反向弧的费用。【难点剖析】残余网络构建规则：对于原图中的弧(i,j)，若f(i,j)<c(i,j)，则保留正向弧，费用为w(i,j)，容量为剩余容量；若f(i,j)>0，则添加反向弧(j,i)，费用为w(i,j)，容量为f(i,j)。反向弧费用为负，使得寻找最小费用路时可借助负费用弧“退回”之前的流量以调整路径。算法需处理负权边，但若原网络无负费用圈，则残余网络也不会出现负环（可证明），因此可用BellmanFord或Dijkstra（若费用非负）求最短路。实际中常用Dijkstra配合势函数（potentials）处理负权，保证高效。【算法步骤详细分解】第一步：初始化零流f=0，设置势函数π(v)=0（所有顶点）。第二步：在残余网络上，以“修正费用”w'(i,j)=w(i,j)+π(i)π(j)作为边权，利用Dijkstra求从s到t的最短路（修正费用非负）。若不存在路径，则当前流已是最大流，结束；否则得到最短路径P。第三步：计算路径P上的可增广量δ=min_{(i,j)∈P}r(i,j)（r为残余容量）。第四步：沿路径P增广δ：对每条弧(i,j)∈P，若为正向弧则f(i,j)+=δ，若为反向弧则f(j,i)=δ。第五步：更新势函数π(v)=π(v)+d(v)，其中d(v)为修正费用意义下从s到v的最短距离。第六步：重复第二步至第五步，直到不存在增广路。最后输出流f及其总费用。【关键算法】势函数的作用是保持修正费用非负，从而可以使用Dijkstra，大幅提升效率。同时势函数的更新等价于对偶变量的调整，体现了线性规划的对偶思想。【手工模拟案例】给出一个简单网络：s→A（容量5，费用2），s→B（容量3，费用3），A→t（容量4，费用1），B→t（容量2，费用4），A→B（容量2，费用1）。引导学生逐步演算：初始零流，残余网络与原图相同，修正费用即原费用（势均为0）。Dijkstra求s→t最短路：s→A→t费用2+1=3，s→B→t费用3+4=7，s→A→B→t费用2+1+4=7，故选择s→A→t，增广量min(5,4)=4，流值4，总费用4×3=12。更新势：d(s)=0，d(A)=2，d(t)=3，新势π=原势+d。第二次迭代：残余网络更新（正向弧s→A剩余容量1，费用2；A→t正向容量0，反向弧t→A容量4，费用1；其他不变）。修正费用计算：以新势π(s)=0，π(A)=2，π(t)=3，则w'(s,A)=2+02=0，w'(s,B)=3+00=3（需重新计算π(B)？B的势尚未更新？注意：π(B)仍为0，因为d(B)在第一次最短路中未达到，因此d(B)=∞？实际上Dijkstra只更新了可达点的距离，B的d应记为∞，但势函数通常只对可达点更新，不可达点保持原势？严格做法是只对可达点更新，不可达点π不变。这里B的d未被更新，故π(B)=0。则w'(s,B)=3+00=3；w'(A,B)=1+20=3；w'(B,t)=4+03=1；反向弧t→A修正费用：w'(t,A)=1+32=0。用修正费用跑Dijkstra：s可达A(0)，A可达B(0+3=3)，B可达t(3+1=4)；s直接到B(3)，s到A再到t？A到t的正向弧已无，反向弧t→A不考虑方向。实际上s到t的路径：s→A→B→t费用0+3+1=4；s→B→t费用3+1=4；s→A→t？无法走。故最短路径费用4，两条可选。任选s→A→B→t，增广量min(剩余s→A容量1，A→B容量2，B→t容量2)=1，增广后流值5，总费用增加1×(2+1+4)=7，累计19。更新势：新d(s)=0，d(A)=0，d(B)=3，d(t)=4，新势π=原势+d：π(s)=0+0=0，π(A)=2+0=2，π(B)=0+3=3，π(t)=3+4=7。第三次迭代：残余网络更新（s→A满流，反向弧A→s容量1费用2；A→B正向剩余容量1费用1，反向B→A容量1费用1；B→t正向剩余容量1费用4，反向t→B容量2费用4；A→t反向弧仍存在容量4费用1）。计算修正费用：w'(A,s)=2+20=0；w'(s,B)=3+03=0；w'(A,B)=1+23=0；w'(B,A)=1+32=0；w'(B,t)=4+37=0；w'(t,A)=1+72=4；w'(t,B)=4+73=0。所有正向弧修正费用几乎为0，Dijkstra从s出发：s可达A？需经过反向弧？从s出发只能沿正向弧，s有出弧吗？s→A已无正向，但有反向A→s，但方向不对，不能从s走反向。s→B正向存在，费用0，故s→B(0)；B可达t(0)，故s→B→t费用0，增广量min(s→B容量3？注意s→B原来容量3，第一次流没用它，但第二次增广用了A→B→t，未影响s→B，所以s→B剩余容量仍为3？第二次增广用了s→A(1)和A→B(1)和B→t(1)，所以s→B未变，仍为3。路径s→B→t上，s→B残余容量3，B→t残余容量1（因为第二次用了1），所以δ=1。增广后流值6，总费用增加1×(3+4)=7，累计26。此时已达最大流？检查：s出弧总容量5+3=8，t入弧总容量4+2=6，最大流应为6。流值6已达最大，算法结束（后续找不到增广路）。最终流：s→A流4（第一次），s→A流1（第二次？实际上第二次s→A用了1，所以s→A总流5，满流；s→B流1（第三次），共6；A→t流4（第一次），A→B流1（第二次），B→t流1（第三次）和第一次？第一次没走B→t，所以B→t流1；检查平衡：A流入s→A5，流出A→t4+A→B1，平衡；B流入s→B1+A→B1，流出B→t2？A→B1加上s→B1共2，B→t只有1，不平衡？发现问题：B的流出只有B→t1，但流入有s→B1和A→B1，共2，所以B节点流量不平衡。错误出在第二次增广后B→t剩余容量应为21=1，第三次增广选择s→B→t用了1，则B→t变为0，B总流出1，流入s→B1和A→B1共2，B净流入1，违反了流量守恒？仔细检查：第一次增广后，s→A=4，A→t=4，其余为0。第二次增广路径s→A→B→t，增广1单位，更新后s→A=5，A→B=1，B→t=1。此时s→A=5，s→B=0，A→B=1，B→t=1，A→t=4。计算各点：s流出5，t流入A→t4+B→t1=5？A→t4，B→t1，t总流入5，但s总流出5，所以总流值应为5，不是6。因为最大流是5？之前算s出弧总容量5+3=8，t入弧4+2=6，最大流应为min(8,6)=6，但这里只得到5，说明还有增广可能。第三次增广s→B→t后，s→B=1，B→t=2？第三次增广时B→t剩余容量是1，增广1后变为0，所以B→t=1+1=2？不对，第二次后B→t=1，剩余容量=21=1，第三次增广1，则B→t变为2，剩余0。更新后s→B=1，B→t=2。此时s流出s→A5+s→B1=6，t流入A→t4+B→t2=6，最大流6。但B的流入：s→B1+A→B1=2，流出B→t2，平衡。之前计算错误，B→t第二次后应为1，第三次后应为2，正确。所以最终流值为6，总费用：第一次4×3=12，第二次1×(2+1+4)=7，第三次1×(3+4)=7，合计26。检查是否有更优？比如若第一次不走s→A→t而走其他，可能会得到更小费用。这正是最小费用最大流要解决的问题。通过此例，学生可体会算法的迭代过程。【算法收敛性说明】连续最短路算法在每次增广中都选择当前费用最小的增广路，由于每次增广后势函数更新保证了后续修正费用非负，算法至多进行O(V·E)次增广（每次至少增加一个饱和弧或删除一个零流弧），可证明最终得到的流是最大流且总费用最小。（三）新知探究——56网络分析的其它应用【热点】网络流模型是运筹学与图论的重要工具，其思想可迁移至诸多领域。教师逐一介绍以下典型应用：（1）运输问题（TransportationProblem）：有m个供应点（仓库）和n个需求点（客户），各供应点有供应量a_i，各需求点有需求量b_j，且∑a_i=∑b_j（产销平衡）。从i到j的单位运输成本为c_{ij}，求总运费最小的调运方案。这本质上是二分图上的最小费用流问题：构造源点s连接各供应点，弧容量为a_i，费用0；供应点i到需求点j弧容量无穷大（或适当上界），费用c_{ij}；需求点j连接汇点t，容量b_j，费用0。求s到t的最小费用最大流（最大流值即为总运量），即得最优调运方案。若产销不平衡，可通过虚拟节点处理。【重要】此模型也可用表上作业法求解，但网络流视角更统一，且可处理中间转运（中转运输问题）。（2）指派问题（AssignmentProblem）：有n项任务和n个人，每人完成每项任务的效率（或成本）已知，要求每人分配一项任务，每项任务只由一人完成，使总成本最小（或总效率最大）。可视为完全二分图上的最小费用最大流：源点s到每个人弧容量1，费用0；每个人到每项任务弧容量1，费用为成本（若求最大效率则取负或转化为最小）；每项任务到汇点t弧容量1，费用0。求s到t的最小费用最大流，流值为n，即得最优指派。此即著名的匈牙利算法所解决的问题，而网络流算法可处理非平衡指派（人数与任务数不等）及带约束指派。（3）关键路径法（CriticalPathMethod,CPM）与项目网络图：在项目管理中，用有向图表示工序间的先后关系，弧权表示工期。求项目的最短完工时间（即最长路径，亦称关键路径），这本质上是最长路问题，可通过将权取负转化为最短路问题，或直接使用拓扑序动态规划。网络流视角下，可转化为最小费用流？实际上，关键路径可视为“时间资源”的优化，若考虑赶工成本（压缩工期需额外费用），则变为“时间—费用权衡”问题，可用最小费用流模型求解最优赶工方案。【难点】将项目网络转化为流网络时，需引入“事件节点”和“工序弧”，并考虑资源约束，属于进阶应用，可作为拓展。（4）最大流与最小割的应用：最大流等价于最小割，这一对偶关系可用于分析网络脆弱性。例如通信网络中，要破坏s与t之间的连通所需切断的最少边（或最小容量和）即为最小割。在网络可靠性分析中，可通过计算所有节点对间的最大流来评估网络连通强度。另外，图像分割中常将像素视为节点，相邻像素间连边权表示相似度，通过最小割将图像分为前景背景（GraphCut算法）。（5）二分图匹配与覆盖：最大流模型可求二分图的最大匹配（将人、任务分别置于两侧，容量1，源汇连接），进一步可求最小点覆盖、最大独立集等，通过König定理关联。这在任务分配、资源调度中应用广泛。（6）物流与供应链中的库存路径问题：多级库存系统中，如何安排运输使总成本（运输+库存）最小，可构建动态网络流模型，时间维度展开为时空网络，每个节点表示某时刻某地点，弧表示运输或库存，费用含运输费和持有成本，求最小费用流。（7）城市交通流分配：将道路网络抽象为图，路段有容量（通行能力）和阻抗（时间），用户均衡或系统最优分配问题可转化为凸费用流问题，是交通规划的核心。【热点】大数据时代，网络流模型与机器学习、深度学习结合，如神经网络中的信息传递可视为流，正则化路径与最小费用流有深层联系。教师可简要提及，激发学生探索欲望。（四）典例剖析例1（最小费用最大流综合题）：给定下图（弧上标注(容量,费用)），求s到t的最小费用最大流。图：s→1(4,2)，s→2(3,3)，1→2(2,1)，1→3(3,4)，2→4(3,2)，3→t(5,1)，4→t(4,3)，3→4(2,2)。要求学生分组用连续最短路算法手工演算，并交流结果。教师巡视指导，最后点评并给出最优流（流量最大为？计算最大流：s出弧4+3=7，t入弧5+4=9，但中间节点有限，实际最大流需通过计算，可能为6或7。通过算法可得最小费用）。例2（运输问题转化）：某建材公司有A、B两个采石场，日产石子分别为40吨、60吨；有C、D、E三个建筑工地，日需求分别为30吨、50吨、20吨。从各采石场到工地的吨运费如下表（单位：元/吨）：A→C:10，A→D:15，A→E:20；B→C:12，B→D:9，B→E:14。求总运费最小的调运方案。引导学生构建网络流模型，并用软件或手工求解（可用最小费用流算法，也可用表上作业法对比）。强调产销平衡（40+60=100，30+50+20=100），直接建模求解。例3（指派问题变形）：某车间有4名工人可安排完成4项任务，但工人甲不能做任务2，工人乙不能做任务3，其他均可，每人每项任务的耗时已知，如何指派使总耗时最小？引入禁止弧（容量0或极大费用）来处理约束，转化为最小费用流求解。（五）课堂练习发放导学案，包含以下练习题：1.判断下列说法是否正确：最小费用最大流一定是最大流中费用最小的；连续最短路算法每次增广都使总费用增加量最小。（讨论算法局部最优与全局最优的关系）2.给定一个只有三条边的简单网络：s→A(2,5)，A→t(2,1)，s→t(1,10)，求最小费用最大流，并思考若将s→t费用改为3，结果如何？3.将下列实际问题抽象为网络流模型：某工厂生产两种产品，需经过三个车间加工，各车间加工能力有限，产品利润已知，如何安排生产使利润最大？（提示：可转化为最大费用最大流，或取负费用）4.利用网络流概念解释“木桶效应”或“瓶颈”。学生独立完成后，小组内互评，教师选取典型答案投影讲解。（六）课堂小结师生共同回顾本节课核心内容：【核心概念】最小费用最大流的定义、数学模型、残余网络、势函数。【关键算法】连续最短路算法的步骤与思想。【重要应用】运输问题、指派问题、关键路径、最大流与最小割等。强调数学建模的一般步骤：实际问题→网络抽象→变量设定→算法求解→结果解释。鼓励学生在生活中寻找可用网络流分析的案例，培养数学眼光。（七）布置作业1.必做题：教材习题55第2、3题；56第1、2题。