简介这份最优化复习提纲面向通信网络方向的学习者与备考者围绕网络设计中的优化问题展开帮助读者系统梳理最小费用流、最大流与最短路等典型模型的建模与求解思路。资源以PPT形式呈现共1个文件压缩包约820KB内容涵盖网络设计问题介绍、线性规划、整数线性规划、无约束规划、分解方法及对偶理论等章节重点讲解Link-Path与Node-Link两种建模方式、单纯型算法流程、基本可行解生成及最优性条件等核心知识点。目前已有118人学习适合用于课程复习、考前梳理或作为通信网优化入门的参考材料便于快速把握各章重点与解题框架。1. 从一份复习提纲说起通信网优化到底在算什么如果你正在准备通信网方向的考试或者刚接手一个网络规划项目大概率会遇到这样的困惑链路容量、业务需求、单位成本都摆在面前但流量到底该怎么分配才最省钱这份《最优化复习提纲 网络做优化》就是冲着这个问题来的。它把通信网中的优化问题归结为网络流问题用 Link-Path 和 Node-Link 两套建模思路把最小费用流、最大流、最短路这些经典问题串起来讲。适合通信工程、网络规划方向的在校生复习备考也适合刚入行的工程师补数学建模的底子。提纲覆盖线性规划、整数线性规划、无约束规划、分解方法和对偶理论六章重点落在前四章尤其是单纯型法和分支定界法的实操推演。2. Link-Path 与 Node-Link两套建模思路的选型与落地2.1 Link-Path 模型路径已知只做分流Link-Path 模型的核心假设是所有业务节点之间的候选路径集合 P 已经提前找出来了你只需要决定每条路径上承载多少流量。这个假设在实际工程中很常见——比如骨干网的路由规划路径往往是预先配置好的优化空间在于分流比例。提纲里给了一个三节点网络的例子。节点 1、2、3 之间有业务需求链路单位成本都为 1目标是让总成本最小。用 Link-Path 建模决策变量是特定路径承载特定流的大小。写成数学形式# Link-Path 模型的最小费用流问题 # 决策变量x[path] 表示某条路径上承载的流量 # 参数h[o,d] 是节点对 (o,d) 之间的业务需求 # c[link] 是链路单位成本 # cap[link] 是链路容量上限 import pulp # 假设路径集合已经枚举好 paths { (1,2): [[1,2], [1,3,2]], # 1到2的两条候选路径 (1,3): [[1,3], [1,2,3]], # 1到3的两条候选路径 (2,3): [[2,3], [2,1,3]], # 2到3的两条候选路径 } demand {(1,2): 5, (1,3): 7, (2,3): 8} # 业务需求矩阵 link_cost {(1,2): 1, (1,3): 1, (2,3): 1} # 链路单位成本 link_cap {(1,2): 10, (1,3): 10, (2,3): 15} # 链路容量上限 prob pulp.LpProblem(LinkPath_MinCost, pulp.LpMinimize) # 为每条路径创建决策变量 x {} for od, path_list in paths.items(): for p in path_list: x[(od, tuple(p))] pulp.LpVariable( fx_{od}_{p}, lowBound0, catContinuous ) # 目标函数所有链路上的流量乘以单位成本 prob pulp.lpSum( link_cost[link] * pulp.lpSum( x[(od, tuple(p))] for od, path_list in paths.items() for p in path_list if link in [tuple(p)[i:i2] for i in range(len(p)-1)] ) for link in link_cost ) # 约束1每条链路的流量不超过容量上限 for link in link_cap: prob pulp.lpSum( x[(od, tuple(p))] for od, path_list in paths.items() for p in path_list if link in [tuple(p)[i:i2] for i in range(len(p)-1)] ) link_cap[link] # 约束2每个业务对的需求必须被满足 for od, d in demand.items(): prob pulp.lpSum( x[(od, tuple(p))] for p in paths[od] ) d prob.solve() print(最优总成本:, pulp.value(prob.objective)) for var in prob.variables(): if var.varValue 0: print(f{var.name} {var.varValue})这段代码的逻辑很直接目标函数是所有链路上流量乘以单位成本的总和约束一是链路容量限制约束二是业务需求必须被完全满足。参数方面demand是业务需求矩阵link_cap是链路容量上限link_cost是单位成本。实际用的时候路径集合的枚举方式会直接影响求解效率——路径太多会导致变量爆炸路径太少可能找不到最优解。常见做法是先跑一遍 K 最短路把候选路径控制在合理范围内。提纲里给出的手算例子更简洁三个节点、三条链路、六个决策变量直接写出线性规划的标准形式用单纯型法迭代求解。这个例子的价值在于让你看清 Link-Path 模型的变量是怎么定义的——每个变量对应一条路径上的流量约束条件对应链路容量和业务需求。2.2 Node-Link 模型路由和分流一起优化Node-Link 模型比 Link-Path 更灵活因为它不要求路径预先确定而是把路由和分流比例都作为优化变量。提纲里的描述是“假定业务的路由和在每条路由上的分流比例都需要优化确定”。这意味着模型要同时决定流量走哪条路、每条路上走多少。Node-Link 模型的一般写法涉及流守恒约束。对于每个节点流入流量减去流出流量等于该节点产生的业务量如果是源节点或消耗的业务量如果是目的节点。提纲里给出了完整的数学表达# Node-Link 模型的最小费用流问题 # 决策变量f[link, od] 表示链路 link 上承载的来自业务对 od 的流量 # y[link] 表示链路是否被使用0-1变量用于容量约束 import pulp nodes [1, 2, 3] links [(1,2), (1,3), (2,3), (2,1), (3,1), (3,2)] # 有向链路 demand {(1,2): 5, (1,3): 7, (2,3): 8} link_cost {l: 1 for l in links} link_cap {(1,2): 10, (1,3): 10, (2,3): 15, (2,1): 10, (3,1): 10, (3,2): 15} prob pulp.LpProblem(NodeLink_MinCost, pulp.LpMinimize) # 决策变量每条链路上承载的来自每个业务对的流量 f {} for l in links: for od in demand: f[(l, od)] pulp.LpVariable(ff_{l}_{od}, lowBound0) # 目标函数 prob pulp.lpSum(link_cost[l] * f[(l, od)] for l in links for od in demand) # 流守恒约束对每个节点和每个业务对 for od in demand: o, d od for node in nodes: inflow pulp.lpSum(f[(l, od)] for l in links if l[1] node) outflow pulp.lpSum(f[(l, od)] for l in links if l[0] node) if node o: prob outflow - inflow demand[od] elif node d: prob inflow - outflow demand[od] else: prob inflow - outflow 0 # 容量约束 for l in links: prob pulp.lpSum(f[(l, od)] for od in demand) link_cap[l] prob.solve() print(最优总成本:, pulp.value(prob.objective))Node-Link 模型的优势在于它不需要预先枚举路径适合路径选择本身也是优化变量的场景。但代价是变量数量更多——链路数乘以业务对数规模大了之后求解时间会明显上升。提纲里特别强调了这个模型的一般写法中流守恒约束的构建方式这是整个模型的核心。两套模型怎么选我的经验是如果路径集合相对固定、业务需求变化频繁用 Link-Path 更省事如果网络拓扑经常调整、路径选择本身需要优化Node-Link 更合适。提纲里两个模型都给了完整例子复习的时候建议手推一遍把变量和约束的对应关系搞清楚。3. 线性规划与单纯型法从几何直觉到迭代步骤3.1 标准形式转换与基本可行解线性规划是后面所有方法的基础。提纲第二章的重点很明确掌握标准形式和一般形式的转换理解多面体、凸集、极点与最优性的关系掌握基本可行解的生成方法。标准形式的要求是目标函数最小化、约束条件全部为等式、决策变量非负。一般形式转标准形式常见操作包括最大化转最小化目标函数取负、不等式约束引入松弛变量或剩余变量、自由变量拆成两个非负变量之差。基本可行解的生成依赖于基 B 的概念。从约束矩阵 A 中选 m 个线性无关的列组成基矩阵 AB对应的变量叫基变量其余叫非基变量。令非基变量为零解出基变量的值就得到一个基本解。如果基变量的值都非负这个基本解就是基本可行解。提纲里给出了基变量的计算公式XB B^{-1}b。这个公式看着简单但手算的时候容易在矩阵求逆上翻车。我的建议是小规模问题手算练手大规模问题直接上求解器别跟自己过不去。3.2 单纯型算法的迭代逻辑与手算示例单纯型算法的核心思想是从一个基本可行解出发沿着使目标函数下降的方向移动到另一个基本可行解直到找不到下降方向为止。提纲把算法流程拆成了四步找出初始基和对应的初始可行解 X计算缩减费用reduced costcj cj - cB^T B^{-1} Aj。如果所有 cj 0当前解就是最优解终止否则选取 cj 0 的 j 作为入基变量计算方向向量 dB B^{-1} Aj。如果 dB 0问题无界停止否则计算步长 θ min{xB(i) / dB(i) | dB(i) 0}确定新的基继续迭代提纲里给了一个具体的单纯型算法例子。初始基选 B [A1, A3, A6, A7]对应的基本可行解是 X (2, 0, 2, 0, 0, 1, 4)。计算缩减费用后选取 j5 作为入基变量计算方向向量 dB确定步长获得新的解继续迭代。这个例子的价值在于让你看清每一步的计算细节。手算一遍之后你会对“缩减费用小于零意味着目标还能下降”这个判断有肌肉记忆。实际写代码的时候这些步骤都被求解器封装了但理解底层逻辑能帮你在结果异常时快速定位问题——比如无界解、退化循环这些经典坑。提示单纯型法在退化情况下可能循环。常见做法是采用 Bland 规则——选入基和出基变量时都选下标最小的可以避免循环。4. 整数规划与分支定界离散决策的求解框架4.1 整数规划的分类与枚举树整数规划要求部分或全部决策变量取整数值。提纲第三章的重点是理解整数规划是离散优化、理解枚举树的形成、掌握分支定界法。枚举树的思想很朴素把所有可能的整数解组织成一棵树从根节点开始每个分支对应一个变量的取值决策。但朴素枚举的规模是指数级的所以需要分支定界来剪枝。分支定界法的核心操作是“分支”和“定界”。分支是把可行解空间不断分割为越来越小的子集定界是为每个子集内的解的值计算一个下界或上界。分支后如果某个子集的界限超出了已知可行解的值这个子集就不再进一步分支——这就是剪枝。4.2 分支定界算法的五步流程与手算推演提纲把分支定界算法描述为五个步骤如果目标是最小化设定目前最优解的值 Z ∞根据分支法则从尚未被洞悉的节点中选择一个节点在其下一阶层中分为几个新节点计算每个新分枝出来的节点的下限值 LB对每个节点进行洞悉条件测试。满足以下任一条件即可洞悉节点的下限值大于等于 Z已找到该节点中具最小下限值的可行解若此解小于 Z 则更新 Z该节点不可能包含可行解判断是否仍有尚未被洞悉的节点。如果有回到步骤二如果没有演算停止得到最优解提纲里给了一个完整的例子最大化 z 40x1 90x2约束为 9x1 7x2 ≤ 56、7x1 20x2 ≤ 70、x1, x2 ≥ 0 且为整数。先不考虑整数条件解对应的线性规划得到最优解 x1 4.81, x2 1.82, z0 356。这个 z0 是原问题最优目标函数值 z* 的上界。x1 0, x2 0 时 z 0是 z* 的一个下界。所以 0 ≤ z* ≤ 356。接下来就是分支的过程。x1 4.81 不是整数可以分支为 x1 ≤ 4 和 x1 ≥ 5 两个子问题。对每个子问题重新求解线性规划更新上下界继续分支直到找到整数最优解。# 分支定界法求解整数线性规划 # 使用 pulp 的整数规划求解器底层自动执行分支定界 import pulp prob pulp.LpProblem(BranchAndBound_Example, pulp.LpMaximize) x1 pulp.LpVariable(x1, lowBound0, catInteger) x2 pulp.LpVariable(x2, lowBound0, catInteger) prob 40 * x1 90 * x2 # 目标函数 prob 9 * x1 7 * x2 56 # 约束1 prob 7 * x1 20 * x2 70 # 约束2 prob.solve() print(求解状态:, pulp.LpStatus[prob.status]) print(x1 , pulp.value(x1)) print(x2 , pulp.value(x2)) print(最优目标值 , pulp.value(prob.objective))这段代码用 pulp 的整数规划求解器直接求解底层自动执行分支定界。参数方面catInteger指定变量为整数lowBound0指定非负。实际用的时候如果问题规模大可以设置求解器的超时时间和间隙容忍度避免卡在某个分支上太久。手算这个例子的价值在于理解分支定界的剪枝逻辑。提纲里详细展示了每一步的上下界更新过程复习的时候建议跟着推一遍把“什么时候该剪枝、什么时候该继续分支”的判断条件搞清楚。注意分支定界法的最坏情况复杂度是指数级的。如果问题规模大且约束复杂可能需要考虑列生成、拉格朗日松弛等更高级的方法。提纲后续章节的分解方法和对偶理论就是干这个的。5. 避坑与排查复习和实操中最容易翻车的五个点5.1 现象Link-Path 模型求解结果比预期差很多原因路径集合枚举不完整最优路径不在候选集合里。Link-Path 模型的前提是路径集合 P 已经找出来如果枚举时漏掉了关键路径模型只能在剩余路径里找最优结果自然差。解决先用 K 最短路算法生成候选路径K 取 3 到 5 通常够用。如果结果仍然不理想逐步增大 K观察目标函数是否收敛。另外注意路径集合里是否包含了所有业务对的路径漏掉某个业务对的路径会导致该业务无法路由。5.2 现象Node-Link 模型求解时间过长原因变量数量随链路数和业务对数乘积增长规模大了之后求解器扛不住。另外流守恒约束的构建方式也会影响求解效率。解决先检查是否有冗余变量——比如某些链路上不可能承载某些业务对的流量这些变量可以提前剔除。另外可以尝试把连续变量和整数变量分开处理先用线性松弛求一个下界再逐步收紧。5.3 现象单纯型法迭代过程中目标函数值不下降原因可能是退化导致的循环也可能是缩减费用计算错误。退化是指基本可行解中出现了零值基变量导致步长为零迭代原地打转。解决采用 Bland 规则选择入基和出基变量可以避免循环。另外检查缩减费用的计算公式是否正确——cj cj - cB^T B^{-1} Aj注意 cB 是基变量对应的目标函数系数B^{-1} 是基矩阵的逆。5.4 现象分支定界法找不到整数最优解原因分支策略选择不当导致搜索树过大求解器在超时前没有找到最优解。另外定界过程如果下界更新不及时剪枝效果会大打折扣。解决调整分支变量的选择策略——优先选择小数部分接近 0.5 的变量进行分支通常能更快收敛。另外可以设置求解器的间隙容忍度允许在一定误差范围内接受次优解换取求解速度。5.5 现象线性规划标准形式转换后求解结果与预期不符原因不等式转等式时松弛变量的符号搞反了或者自由变量拆分时遗漏了约束。标准形式转换是手工操作容易在细节上出错。解决转换完成后把标准形式代回原问题验证一遍。特别是松弛变量的符号——小于等于约束引入松弛变量时是加号大于等于约束引入剩余变量时是减号。自由变量拆成两个非负变量之差时两个变量都要出现在所有约束中。6. 对偶理论与分解方法进阶用法与验证技巧提纲最后两章讲的是对偶理论和分解方法。这两块内容在复习时容易被跳过但实际工作中遇到大规模网络优化问题时它们往往是破局的关键。对偶理论的核心思想是每个线性规划问题都有一个对应的对偶问题原问题和对偶问题的最优目标函数值相等强对偶定理。对偶问题的变量个数等于原问题的约束个数所以当原问题约束多、变量少时转成对偶问题求解可能更高效。提纲里没有展开对偶问题的具体求解步骤但给出了一个重要的验证思路如果你求出了原问题的最优解可以构造对偶问题并验证互补松弛条件是否满足。互补松弛条件说的是原问题的最优解中如果某个约束是紧的等号成立对偶变量可以非零如果约束是松的严格不等式对偶变量必须为零。这个条件可以用来交叉验证求解结果的正确性。分解方法解决的是大规模问题的求解效率问题。核心思路是把一个大问题拆成若干个小问题分别求解后再协调。常见的分解方法包括 Benders 分解和 Dantzig-Wolfe 分解。提纲里没有给出具体的分解算法步骤但强调了分解方法在通信网优化中的应用场景——比如多区域网络规划、多层网络协同优化。我自己的习惯是每次用求解器得到结果后都会手动检查一遍互补松弛条件。具体做法是把最优解代入原问题的约束看哪些约束是紧的然后检查对应的对偶变量是否为零。如果发现紧约束对应的对偶变量为零或者松约束对应的对偶变量非零说明求解过程可能有问题需要回头检查模型构建或求解器设置。# 互补松弛条件验证示例 # 假设已经求出原问题最优解 x_opt 和对偶问题最优解 y_opt import numpy as np # 原问题约束矩阵和右端项 A np.array([[9, 7], [7, 20]]) b np.array([56, 70]) # 原问题最优解来自求解器 x_opt np.array([4.0, 2.0]) # 假设的整数最优解 # 对偶问题最优解来自求解器 y_opt np.array([0.0, 4.5]) # 假设值 # 检查互补松弛条件 for i in range(len(b)): slack b[i] - A[i] x_opt # 第i个约束的松弛量 if slack 1e-6: # 约束是松的 assert abs(y_opt[i]) 1e-6, f约束{i}是松的但对偶变量非零 else: # 约束是紧的 pass # 对偶变量可以非零 print(互补松弛条件验证通过)这段代码的逻辑是对每个约束计算松弛量如果松弛量大于零约束是松的对偶变量必须为零如果松弛量等于零约束是紧的对偶变量可以非零。参数方面1e-6是数值容差避免浮点误差导致误判。从那以后我每次做完网络优化求解都会强制走一遍互补松弛条件验证。这个习惯帮我抓出过好几次模型构建的错误——比如约束方向写反了、变量范围设错了。希望帮到你。本文还有配套的精品资源点击获取