三网络流与图 _网络流

经过两篇文章的篇幅，我们介绍了最小费用网络流模型以及解决的算法。今天我们介绍网络流模型的现实应用案例，并针对一些特殊的情景提出更高效的解决算法。
传送门：网络流与图（一）网络流与图（二）
1
运输与分配问题
运输问题是特殊的最小费用网络流模型，其中每个节点都是一个纯供给节点（所有弧都指出）或一个纯需求节点（所有弧都指入）.
它的标准形式可以表示为：
举个贴近现实的例子——海军调动运输问题。
【三网络流与图】美国海军兵团的军官调动计划是一个真实的大规模运输问题。非常时期，会有上千名官军从他们日常岗位被调走或留在原有位置。然而并非每名军官在职级、经验或所接受的训练上都能满足分配需求。调动选择可以表示为如下面虚拟的有向图中。供给节点代表目前位于同一位置且可能满足分配要求的一组军官。例如第一个节点代表被训练为情报官的上尉；需求节点代表非常时期内活跃地区对具有特定资格的军官需求，例如节点2表示需要一个或多个服务于当地政府联络军官。
当一个供给节点所表示的军官具有填充一个需求节点所对应职位的资格时，两个节点间就会存在一个弧。因此，民政事务官会连接到当地政府联络员。对于处在任一源节点的军官，都可能有多种可行的分配，比如事务官也可以作为第一部队通信员。
海军需要首先考虑是填充所有所需的职位，但事实上总会留下一些职位无法被填充。此时我们用一个与所有需求相连的人工供给节点来表示无法填充职位的可能性，其弧上的高费用用在目标函数中作为无法填充职位的惩罚。一旦尽可能多的需求得以满足，第二个要考虑的则是令变动最小化。即尽量将军官分配到与调动前相同的单位，或至少通过最小化总路费而将他们分配到邻近的单位。
利用下列概念，将海军调动问题简化为标准形式。
分配问题（）是另外一种特殊的最小费用网络流问题，用于获取两个不同集合中对象间的最优配对或匹配。
分配问题要用到离散决策变量进行建模：
用A表示可行的分配（i ， j）的集合，我们可以将线性分配模型表示为双向流问题:
第一组约束方程通过对所有可能的分配j求和，保证每个i都恰好被分配了一次；第二组约束方程用同样的方式来确保每个j恰好被分配一次。
该公式为一个整数线性规划（ILP）问题，决策变量仅允许取离散值0或1 。但我们会发现，计算最优解时可以忽略离散性。
举个真实的例子——CAM分配问题。
某计算机辅助制造（CAM）系统可以通过一个由电脑控制的工厂工作站来自动运行工作，而每项工作由所要求的一系列加工和装配操作构成。通过情况下，相同的操作可以在几个不同的工作站完成。因此电脑控制系统必须做出相应的运行决策。每当一项工作的某步骤已被完成，系统即必须从可实现其下步操作的几个工作站中选择一个来承接该项工作。完成这种控制决策的一种接近最优的方法即周期性的求解分配模型。为了进行说明，下表虚拟了8项工作i要么正在等待被移动到下一个工作站，要么会接下来的5min内完成当前的操作。同时，表中也列出了可能承接工作的10个工作站j 。表中的项表示：运往站的时间+等待站变空的时间+在站中的操作处理时间。即它们将工作i分配给j的最短时间。缺失的数据表示不可行分配。

三 网络流与图

三网络流与图