Network model (operations research) — 网络模型

网络模型（在运筹学中；英语：Network models）是一类将问题表示为图（网络）形式的数学模型，其中顶点（节点）表示对象或状态，而边（弧）表示它们之间的连接或过程。在优化的背景下，网络通常指有向图，在运筹分析中直接称之为“网络”；这种网络的顶点称为节点，边称为弧。

网络模型是分析和优化物流、电信、项目管理和金融等领域复杂系统的强大工具。其优势在于高度的抽象性：节点可以代表城市、计算机路由器或项目阶段，而弧则可以代表道路、通信信道或技术操作。

定义与术语

网络模型的基础是图论。关键概念包括：

• 流网络（英语：flow network）：一种有向图，其中每条边都有容量（capacity）和流量（flow）。图中指定了两个特殊顶点：源点（source），流量从此处流出；以及汇点（sink），流量向此处流入。
• 流量守恒定律：对于任何既非源点也非汇点的顶点，流入的总流量必须等于流出的总流量。这个条件是物理守恒定律的离散模拟。
• 网络规划：将项目表示为相互关联的作业（弧）和事件（节点）的复合体模型。这类网络是有向无环图，反映了工作的执行顺序。

关键属性与定理

网络模型具有一系列特殊性质，使其可以应用高效算法进行求解。

• 整数解特性：许多网络优化问题（例如，最大流或最短路径问题）的约束矩阵具有完全幺模性。因此，如果问题的参数（容量、长度）是整数，那么通过线性规划方法找到的最优解也将是整数，无需引入额外约束。
• 最大流最小割定理：流理论的核心成果。该定理指出，从源点到汇点的最大流量等于分离源点和汇点的所有割中容量最小的割的容量。这一定理为流量问题建立了最优性准则，是许多算法的基础。
• 最短路径的最优性原理：如果从点A到点C的路径是最短的，那么它的任何一段（例如，从中间点B到C）也是对应顶点之间的最短路径。这一性质是动态规划的基础，并确保了戴克斯特拉算法等算法的正确性。
• 最小生成树（MST）的性质：
• 割性质：对于图的任意一个割，横跨该割的最小权重边属于至少一个最小生成树。
• 环性质：在图的任何环中，权重最大的边不属于任何最小生成树。

普林姆算法和克鲁斯克尔算法等“贪心”算法的正确性就基于这些性质。

主要网络优化问题

• 最短路径问题：寻找两个给定节点之间总长度（权重）最小的路径。可通过戴克斯特라算法（适用于非负权重）或贝尔曼-福特算法（适用于任意权重）求解。
• 最大流问题：在给定弧容量的条件下，确定从源点到汇点的最大可能流量。经典求解方法是福特-富尔克森算法。
• 最小生成树问题：寻找一个连接网络中所有顶点且总边成本最小的子图。
• 关键路径法 (CPM)：在网络规划模型中，确定最长的一系列作业，该序列决定了整个项目的最短可能完成时间。这条路径上的作业时间储备为零。

示例

• 最短路径：导航系统在城市地图上寻找两点之间的最优路线，其中城市为节点，道路为弧，权重等于路程长度或行驶时间。
• 最大流：确定管道网络的最大输送能力，其中泵站为节点，管道为容量有限的弧。
• 最小生成树：设计通信网络（例如，铺设光纤电缆）以连接多个城市，并使电缆总长度最小。
• 关键路径：在房屋建设项目中，各项工作（如打地基、砌墙、盖屋顶）都有预定时长和技术依赖关系，关键路径决定了项目完工的最短时间。该路径上任何工作的延误都会导致整个项目的延误。

另见

• 运筹学
• 图论
• 运输问题
• 关键路径法
• PERT