|
|
目录
1.图的基本定义
2.双边匹配问题
2.1 二分图基本概念
2.2 二分图最大匹配求解
2.3 二分图最优匹配求解
2.4 二分图最优匹配建模实例
2.4.1 二分图最优匹配在师生匹配中的应用
2.4.2 二分图最优匹配在多对多拼车算法中的应用
3.网络最大流
3.1 网络流基本定义
3.2 最大流的问题线性规划形式
3.3 最大流的问题图算法求解(暂无)
4.网络最小费用最大流
4.1 最小费用最大流问题的线性规划形式
4.2 最小费用最大流问题的图算法求解
4.3 最小费用最大流的应用
4.3.1 最小费用最大流模型在运输网络优化中的应用
4.3.2 最小费用最大流模型在指派(分配)问题中的应用
4.3.3 最小费用最大流模型在资源分配中的应用
4.3.4 最小费用最大流模型在资源调度中的应用
1.图基本定义
参考这里:图与网络的基本概念 - 百度文库
参考资料:
1.运筹学-图与网络模型以及最小费用最大流分解
https://doc.mbalib.com/view/f5c778a020411dc3d57c51d70419ee57.html
2.双边最优匹配问题
在经济管理生活中，经常面临双边匹配的问题，比如出行场景中乘客与司机的匹配、物流领域中货物与车辆的匹配、教学领域学生与教师的匹配、营销领域奖励与用户的匹配等。在现实世界稀缺资源约束下(比如人力、物力、财力等)，我们希望最终做出的决策达到某种效率的最优，这里的效率可以是时间最少、行驶路程最短、双方满意度等，可以是多种单一指标的综合。
以滴滴2018年所发表的论文 《Large-Scale Order Dispatch in On-Demand Ride-Hailing Platforms: A Learning and Planning Approach》中所提及的司乘匹配问题为例，将最优匹配问题建模如下形式:
最优匹配问题形式化定义
其中， 表示将乘客 分配给司机 ； 表示将乘客 分配给司机的价值(比如GMV、距离等)；约束 部分的含义为"一个乘客只能分配给至少且最多一个司机"；约束 部分的含义为"一个司机只能服务至少且最多一个乘客"。
显然上述问题是一个典型的0-1整数规划问题。忽略具体的业务场景，很大部分的指派问题都可以建模成如上形式，只是将不同业务诉求隐藏在 中。0-1整数规划是组合优化问题，NP难！通常可以采用爬山法(Climbing Hill)等启发式方法求得最优问题的近似解。
其实在问题规模适中时可以利用图优化方法(这里指二分图最优匹配)求的问题的精确最优解，本小节接下来将介绍二分图相关的内容。
参考资料:
1.基于 “ 滴滴 KDD 2018 论文：基于强化学习技术的智能派单模型 ” 再演绎
https://www.infoq.cn/article/1x-QigwOCSqtTFl8RKps?utm_source=rss&utm_medium=article
2.Large-Scale Order Dispatch in On-Demand Ride-Sharing Platforms: A Learning and Planning Approach
2.1 二分图基本概念
1). 二分图：简单来说，如果无向图G=(V,E)中点可以被分为两组，并且使得所有边都跨越组的边界，则这就是一个二分图。准确地说：把一个图的顶点划分为两个不相交集 和 ，使得每一条边都分别连接 、 中的顶点。如果存在这样的划分，则此图为一个二分图。如下图:
二分图
用二分图表示司乘匹配问题如下图，其中左侧节点表示乘客，右侧节点表示司机，中间的连线表示司乘匹配的价值:
2). 匹配：在图论中，一个匹配(matching)是一个边的集合，其中任意两条边都没有公共顶点。如下图，图 2、图 3 中红色的边就是图1的匹配。相关定义还有: 匹配点、匹配边、未匹配点、非匹配边。
事实上，匹配定义中的"其中任意两条边都没有公共顶点"对应了前文最优化问题形式化中的约束条件， 和 。所以双边匹配最优化问题的本质是从二分图中寻找一个匹配使得目标函数最大。
3). 最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。上图中图 3 是一个最大匹配，它包含 4 条匹配边。
4). 完美匹配：如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。完美匹配一定是最大匹配。
5). 最优匹配：最优匹配又称为带权最大匹配，是指在带有权值边的二分图中，求一个匹配使得匹配边上的权值和最大。一般求最优匹配时，所求二分图的划分  的顶点数相同，使得每一个顶点都需要被匹配，这样也就等同求出了完美匹配。如果 和 的顶点数不同，可以通过补点加权值0边实现转化。
注意最大匹配与最优匹配的区别:
最大匹配不考虑边的权值，即
最优匹配则考虑了边的权值 ,即
2.2 二分图最大匹配求解
求最大匹配的一种显而易见的算法是:先找出全部的匹配，然后保留匹配数最多的。但是这个算法的时间复杂度是边数的指数级函数。通常更高效的求解二分图最大匹配的算法是匈牙利算法。在介绍匈牙利算法前先了解下交替路和增光路径的概念。
1).交替路:从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边...形成的路径叫交替路。
2).增广路:从一个未匹配点出发，走交替路，如果途径另一个未匹配点(出发的点不算)，则这条交替路称为增广路(agumenting path)。如下图(红色边表示已匹配边):
增广路示意图
从增广路的定义以及示例图中可以看出其性质:1.增广路经历的节点一定为奇数 2.增广路中未匹配边比匹配边多"一"。因此我们将增广路取反，也就是"匹配边->未匹配边"，同时"未匹配边->匹配边"，如此以来匹配边就会增加1。进一步，如果可以不断的找到增广路，则匹配数就会不断递增直到达到最大匹配。
下面举一个网上广为流传的例子，给定二分图:
匈牙利算法的步骤如下:
Step1:添加一条边  ，粗线表示已匹配边
Step2:添加一条边 ，粗线表示已匹配边
至此已匹配边集合  中已经包含两条边。
Step3:尝试添加边 ，发现  已经被占。于是以  为起点构造增广路径:  ,将增广路径取反  并添加到二分图中：
同理加入  、  .
int M, N; //M, N分别表示左、右侧集合的元素数量
int Map[MAXM][MAXN]; //邻接矩阵存图
int p[MAXN]; //记录当前右侧元素所对应的左侧元素
bool vis[MAXN]; //记录右侧元素是否已被访问过
bool match(int i)
{
for (int j = 1; j <= N; ++j)
if (Map[j] && !vis[j]) //有边且未访问
{
vis[j] = true; //记录状态为访问过
if (p[j] == 0 || match(p[j])) //如果暂无匹配，或者原来匹配的左侧元素可以找到新的匹配
{
p[j] = i; //当前左侧元素成为当前右侧元素的新匹配
return true; //返回匹配成功
}
}
return false; //循环结束，仍未找到匹配，返回匹配失败
}
int Hungarian()
{
int cnt = 0;
for (int i = 1; i <= M; ++i)
{
memset(vis, 0, sizeof(vis)); //重置vis数组
if (match(i))
cnt++;
}
return cnt;
}Note:对于图来说，最大匹配不是唯一的，但是最大匹配的大小是唯一的。
2.3 二分图最优匹配问题求解
相对于单纯求最大匹配，二分图最优匹配的实际意义更高些。一种求解最优匹配的方式是:用匈牙利算法先求出所有的最大匹配，然后从这些最大匹配(边权重累加)中选出最优匹配。但是这种方法的时间复杂度较高，目前求解二分图最优匹配的算法是大名鼎鼎的KM(Kuhn-Munkres Algorithm)算法。
同样以一个广为流传的例子介绍下KM算法，下图表格中是带权二分图边的权重:
Step1:将边权值转化为顶标(或称标杆)，通常初始化时，X集合的元素&#34;贪心的&#34;取对应边权重最大值，Y集合的元素取0。取出满足以下条件的边: 。以下称之为二分子图。
Step2:从 开始寻找增广路径  ；接着从 寻找增广路径，发现 已经被占。此时需要往二分图中添加边，并使得权重和最大。有两种选择:1.让 放弃 ，并选择新的边 2.为 选择新的边。KM的选择策略如下:
对于当前已经搜索过的路径(当前为 )上的XY点，设该路径上X顶点集为 (当前为  )，Y顶点集为 (当前为 )。对于所有在 中的点  以及不在 中的点  ，计算 ，并从 集中的 标杆中减去 ,将 集中的  标杆加 。
按照上述策略选择  加入到二分子图中。
1).怎么理解 准则?
找一个使得&#34;标杆值下降最小&#34;且&#34;使得原来非法的匹配变成合理的匹配&#34;的边加入，从而使得新二分子图中的边权重和最大。
比如，对于不合法的匹配(上图) &#34;权值和 = 的最大权值边(  )权值 + 的最大权值边(  )权值&#34;，由于这个匹配是不合法的(终点冲突)，因此必须让 或 某一个退而求其次，使得整体&#34;权值和&#34;减少最小的边加入。
2). 的含义是什么?
表示能添加到二分图中的  边权的上限。
玩一个数字游戏:
一个递减的序列:  则 
比如9,8,6,4,3 则:9-(9-8)>6.
Step3: 对 寻找增广路，搜索范围如下图蓝色路径所示，同样找不到增广路，需要扩大相等子图。按照Step2同一规则，会将边  、  加入，d=1.
Step4: 在新的二分子图上，对 重新寻找增广路。如果是深度优先，得到的路线是  ，此时将匹配结果取反，则得到  三个匹配；如果是宽度优先，得到的匹配结果是  ，如下图：
整体来看，KM算法就是一个从最理想状态(添加最大边权)不断妥协的过程，每次找不到合理匹配的时候，就添加一条边权和最大且能完成匹配的边。所以KM是一个贪心的过程，不过其特殊性质使得可以达到全局最优。
import numpy as np
# 声明数据结构
adj_matrix = build_graph() # np array with dimension N*N
# 初始化顶标
label_left = np.max(adj_matrix, axis=1) # init label for the left set
label_right = np.zeros(N) # init label for the right set
# 初始化匹配结果
match_right = np.empty(N) * np.nan
# 初始化辅助变量
visit_left = np.empty(N) * False
visit_right = np.empty(N) * False
slack_right = np.empty(N) * np.inf
# 寻找增广路，深度优先
def find_path(i):
visit_left = True
for j, match_weight in enumerate(adj_matrix):
if visit_right[j]: continue # 已被匹配（解决递归中的冲突）
gap = label_left + label_right[j] - match_weight
if gap == 0:
# 找到可行匹配
visit_right[j] = True
if np.isnan(match_right[j]) or find_path(match_right[j]): ## j未被匹配，或虽然j已被匹配，但是j的已匹配对象有其他可选备胎
match_right[j] = i
return True
else:
# 计算变为可行匹配需要的顶标改变量
if slack_right[j] < gap: slack_right[j] = gap
return False
# KM主函数
def KM():
for i in range(N):
# 重置辅助变量
slack_right = np.empty(N) * np.inf
while True:
# 重置辅助变量
visit_left = np.empty(N) * False
visit_right = np.empty(N) * False
# 能找到可行匹配
if find_path(i): break
# 不能找到可行匹配，修改顶标
# (1)将所有在增广路中的X方点的label全部减去一个常数d
# (2)将所有在增广路中的Y方点的label全部加上一个常数d
d = np.inf
for j, slack in enumerate(slack_right):
if not visit_right[j] and slack < d:
d = slack
for k in range(N):
if visit_left[k]: label_left[k] -= d
for n in range(N):
if visit_right[n]: label_right[n] += d
res = 0
for j in range(N):
if match_right[j] >=0 and match_right[j] < N:
res += adj_matrix[match[j]][j]
return resNote:KM算法要求左右两边的节点数相等，可以通过添加虚拟节点的方法实现.
2.4 二分图最优匹配建模实例
2.4.1 二分图最优匹配在师生匹配中的应用
相对完整的数学建模设计应当包含:1.问题背景 2.基本假设 3.基本定义 4.数学模型 5.算例分析 几部分。下面以此为顺序详述下二分图最优匹配在研究生录取问题中的应用。
1).问题背景
硕士研究生的录取目前普遍采用&#34;初试+复试&#34;的方案。一般是根据初试的成绩，在达到国家和学校分数线的学生中从高到低分排序，按1:1.5的比例选择进入复试的名单。复试一般采用由专家组面试考核的办法，主要面试考核学生的专业知识面、思维的创造性、灵活的应变能力、文字和口头的表达能力和外语水平等综合素质。专家组一般由多名专家组成，每位专家根据自己看法和偏好对所有参加复试学生的各个方面都给出相应的评价，可以认为专家组的面试整体评价都是客观的，最后由主管部门综合所有专家的意见和学生的初试成绩等因素确定录取名单。将问题抽象如下:
考虑学生的综合评价择优录用，包括初试成绩和面试评价。考虑导师和学生意愿，导师对学生的要求和学生自己的意愿。最优双向选择，一方面每一名导师只带一名学生，同时一名导师可以初选多个学生。
显然，这是一个多目标的最优匹配问题。
2).基本假设
专业方向可以互相调剂.研究生复试专家面试评价及导师学术水平指标的量化。分别把A、B、C、D量化为95,80,70,65；将8个专家的评分取算术平均做为专家对考生的综合评价指标 ；导师学术水平中，每一项所占比例相同，通过标准化处理，令每一项中数值最大者为25分，其余按比例折合。
3).基本定义
 代表10名导师 代表参加复试的15名学生
4).数学模型
整个策略分为两部分，首先根据初试成绩和专家评价确定录取同学，其次将录取同学分配给导师。
Part1:确定录取名单
这里采取层次分析法对参加复试的同学打分，最终确定录取的同学。假设结果为: 
Part2:双边满意度矩阵
同样参考前面的层次分析法，可以分别建立:
10名导师综合水平打分每位学生对每位老师的满意程度，记为  ，学生 对导师 的满意程度每位老师对每位学生的满意程度，记为  ，导师 对学生 的满意程度
Part3:最优匹配模型
这里的核心是 的设计。在双边匹配问题中，如果只考虑单边的利益最大化可能会带来很多问题。比如，令  则忽略了学生的诉求，可能会带来严重的师生矛盾，反之亦然。这里令  ，则同时考虑了导师与学生双边的诉求。
说到这里顺便提下在双边匹配中存在的不稳定匹配问题。以婚恋匹配场景为例，一个不稳定的匹配对  指的是一对不稳定的男 女 ，他们没有结合，但是 喜欢 的程度胜过他喜欢目前的配偶，并且 喜欢 的程度也胜过目前配偶。同样的对于一个匹配方案来讲，如果存在这么一对男女，这个系统就成为不稳定的，之所以不稳定是因为 和 最有可能放弃目前配偶，双双私奔，造成社会不安定。因此在双边匹配机制设计中一定要综合考虑双方的诉求。
5).算例分析
这里只给出一个可能的匹配结果:
以上参考论文<<研究生录取问题的数学建模>>.
题外:如果只有5个导师，每个导师带2个学生，该如何处理? 此时可以通过添加虚拟节点的方法解决，也就是将5个导师重复添加。更一般的情况，导师和考生的数目不相等，即当  时问题的处理。
当  时，可以增加  位虚拟导师(虚拟结点)，虚拟导师对所有考生的满意度均为0, 反之亦然；在匹配方案中，当考生对应的导师为虚拟导师时，该考生即落榜。当  时，可以增加  位虚拟考生，任意虚拟考生对导师的满意度为0，反之亦然。
参考资料:
1.二分图的最大匹配、完美匹配和匈牙利算法
http://www.renfei.org/blog/bipartite-matching.html
2.二分匹配——匈牙利算法和KM算法
https://blog.csdn.net/D5__J9/article/details/80754657
3.匈牙利算法（二分图）
https://www.cnblogs.com/shenben/p/5573788.html
4.带你入门多目标跟踪（三）匈牙利算法&KM算法
https://blog.csdn.net/NIeson2012/article/details/94472313
5.匈牙利算法(Kuhn-Munkres)算法
https://www.cnblogs.com/xingnie/p/10395788.html
6.匈牙利算法-看这篇绝对就够了！
https://blog.csdn.net/u013384984/article/details/90718287?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task
7.算法学习笔记(5)：匈牙利算法
https://zhuanlan.zhihu.com/p/96229700
8.KM算法学习笔记
https://segmentfault.com/a/1190000017781300
9.研究生录取中的最佳匹配问题
https://wenku.baidu.com/view/60d275ebc8d376eeaeaa31f8.html
10.研究生录取问题的数学建模
https://wenku.baidu.com/view/60d275ebc8d376eeaeaa31f8.html
11.网络与市场中的计算思维-6.网络流量博弈
https://zhuanlan.zhihu.com/p/89956348
12.研究生录取中的最佳匹配问题
https://wenku.baidu.com/view/a8b9f2ab9a89680203d8ce2f0066f5335a81673d.html
2.4.2 二分图最优匹配在多对多拼车算法中的应用
论文:一种高效的大规模多对多拼车匹配算法_曹斌
1).问题定义
随着经济不断的发展，城市中私家车数量的增加，交通环境变得日益拥堵，并伴随着严重的环境污染问题。在O2O技术不断发展的今天，越来越多的人选择拼车出行。参与拼车离不开拼车系统，拼车系统的设计好坏对拼车效率以及司乘两端的体验至关重要。
下图是一次拼车的业务流程，这里的拼车类似于顺风车的概念:
图中相关符号定义:
 :司机 的出发位置
 :司机 的目的地位置
 :乘客 的出发位置
 :乘客 的目的位置
 :接驾距离
 :送驾距离
:司机原来的行驶路径。比如，开始司机车上有一个乘客  ，此时的行驶路径是;由于接到了新的乘客  而更新了路径。
 :司机返回原始的目的地的距离
:由于接送新乘客 而产生的绕路距离。 
 :乘客 需要支付给司机 的车费。 
另外还有与时间相关的定义:
:司机 的出发时间。
 :司机 的最晚到达时间。
 :乘客 最早出发时间。
:乘客 最晚出发时间。
 :拼车匹配结果反馈给乘客与司机的时间。
在实际系统中，一个合理的匹配结果要满足各方(这里指司机、乘客、平台)的基本体验，比如:
1).司机要在乘客的出发时间范围内到达乘客的出发位置以方便乘客能够合理规划自己的行程。 
2).司机在完成乘客的拼车订单后，还能在自己的最晚到达时间之前到达司机自身的目的地，保证了司机的行程不被耽误。 
3).乘客支付的车费必须小于他提出的最大拼车费用。
4).司机和乘客出发之前获得拼车反馈信息
5).平台视角希望所有司机产生的绕路距离最小
2).数据结构
司机信息列表:
ID(唯一标识),Origin(当前出发位置),Destination(目的地信息),DriverTrip(出发到目的地的最短路径),DepartureTime(出发时间),ArrivalTIme(最晚到达时间)
网格索引(grid index):
在O2O应用场景中，如果将全城的司机乘客做匹配时间复杂度会很高，因此通常会对空间划分成小的分片。这里将整个城市划分成  的相同大小的正方形网格。
网格索引(time index):
1.司机出发时间索引
2.乘客最晚出发时间索引
如下示意图(主要是便于后续的快速查找):
3).匹配策略
整个策略分为两个阶段，首先是单乘客对多司机的匹配，其次是多乘客与多司机的最优组合匹配。
步骤一:单乘客对多司机的匹配
对于特定乘客 , 选取  个合适的司机。
所谓合适，首先司机的出发时间 必定要早于乘客的最晚出发时间 。为了加速，可以借助上文的数据索引。
其次, 的距离尽量小。在线上路径规划是非常耗时的操作，为了加快速度，可以用启发式的方法快速排除掉一些劣质解。这里可以用基于欧式距离的方法。
司机终点与乘客终点距离分布
例如，现在时间是  ， 道路平均速度  ，费用  。乘客 的最早出发时间  ,  。根据乘客最晚出发时间与当前时间的差确定乘客 搜索司机的最大半径，如下公式: 
依据 筛选出来的司机集合有  ，在此基础上根据 再做筛选得到  。在  的基础上再根据乘客的费用约束、司机的最晚到达约束过滤掉部分司机得  。
上面的过滤是基于欧几里得距离，在得到  后司机集合比较小，此时可以基于路网距离在此筛选。最终得到乘客 的候选司机集合  。
步骤二:多乘客对多司机的最优匹配
在为每位乘客 初筛出符合拼车要求的司机集合后，为了达到所有司机拼车绕路距离最小的目标，需要从全局角度做统筹规划，本质是一个从局部最优到全局最优的过程。到这里可以想到对于这样的双边最优匹配问题可以用前文所述的KM算法。如下图，边的权重为 ,也就是绕路距离。
司乘最优匹配
司乘绕路距离矩阵
对  的稀疏矩阵直接做KM算法比较耗时，文中提出了将完整矩阵拆分成多个子矩阵并分别做KM匹配的方法。
子矩阵1
子矩阵2
详细算法可以参考:http://www.doc88.com/p-3498467603633.html ，并证明了两种方法的结果是等价的。
3.网络最大流
如何制定一个运输计划使生产地到销售地的的产品输送量最大。这就是网络最大流问题。
3.1 网络流基本定义
1). 容量网络: 对网络上的每条弧 都给出一个最大的通过能力，称为该弧的容量，记为  。容量网络中通常规定一个发点(也称源点，记为  ) 和一个收点(也称汇点，记为  ),网络中其他点称为中间点。
2). 网络最大流: 是指网络中从发点到收点之间允许通过的最大流量。
3). 流与可行流: 流是指加在网络各条弧上的实际流量，对加在弧 上的负载量记为  。 若  ,称为零流。满足以下条件的一组流称为可行流:
容量限制条件。容量网络上的所有弧满足:  中间点平衡条件。  若以  表示网络中从  的流量，则有: 
3.2 最大流的问题线性规划形式
如下网络，如何求解  的最大流量?
建立线性规划模型:
求解上述模型即可得到结果。同时也可以利用or-tools(运筹工具包).
参考:Minimum Cost Flows | OR-Tools | Google Developers
&#34;&#34;&#34;From Taha &#39;Introduction to Operations Research&#39;, example 6.4-2.&#34;&#34;&#34;
from ortools.graph import pywrapgraph
def main():
# 定义从 start->end 的弧的容量
# 即 start_node -> end_node = capacities
start_nodes = [1, 1, 2, 2, 3, 3, 4, 4, 4,5,6]
end_nodes = [2, 4, 5, 3, 5, 6, 3, 6, 7,7,7]
capacities = [6, 6, 3, 2, 2, 2, 3, 1, 2,5,4]
# Instantiate a SimpleMaxFlow solver.
# 创建简单流
max_flow = pywrapgraph.SimpleMaxFlow()
# Add each arc.
# 添加节点和弧
for i in range(0, len(start_nodes)):
max_flow.AddArcWithCapacity(start_nodes, end_nodes, capacities)
# Find the maximum flow between node 0 and node 4.
# 最后就是求解了
if max_flow.Solve(1, 7) == max_flow.OPTIMAL:
print(&#39;Max flow:&#39;, max_flow.OptimalFlow())
print(&#39;&#39;)
print(&#39; Arc Flow / Capacity&#39;)
for i in range(max_flow.NumArcs()):
print(&#39;%1s -> %1s %3s / %3s&#39; % (
max_flow.Tail(i),
max_flow.Head(i),
max_flow.Flow(i),
max_flow.Capacity(i)))
print(&#39;Source side min-cut:&#39;, max_flow.GetSourceSideMinCut())
print(&#39;Sink side min-cut:&#39;, max_flow.GetSinkSideMinCut())
else:
print(&#39;There was an issue with the max flow input.&#39;)
if __name__ == &#39;__main__&#39;:
main()
--------------------Result--------------------
Max flow: 10
Arc Flow / Capacity
1 -> 2 4 / 6
1 -> 4 6 / 6
2 -> 5 3 / 3
2 -> 3 1 / 2
3 -> 5 2 / 2
3 -> 6 2 / 2
4 -> 3 3 / 3
4 -> 6 1 / 1
4 -> 7 2 / 2
5 -> 7 5 / 5
6 -> 7 3 / 4
Source side min-cut: [1, 2, 3, 4]
Sink side min-cut: [7, 6]
求解最大流还有图类算法，EK算法、SAP算法、DINIC算法、HLPP算法等，感兴趣的可以查找下资料。
Note:最大流的值是唯一的，但最大流的边集是不唯一的。
4.网络最小费用最大流
最小费用最大流问题: 给了一个带收发点的网络，每一对弧 ,除了给出容量 外，还给出了这条弧的单位流量的费用  , 要求一个最大流  ,并使得总运费最小。
如下图网络，每条边不仅包括容量限制还有单位流量费用。求解如何运输才能使得运送最多的石油并使得总的运送费用最小?
4.1 最小费用最大流问题的线性规划形式
基本思路:先求出最大流F，在F的所有解中找一个费用最小的(最大流的值是唯一的,但最大流的边集是不唯一的).
用求解器(or-tools等)求解即可。
这里思考一个问题，前文讲解的网络流中的节点是没有容量限制的，而实际问题中节点也会有容量约束，比如交通网中的收费站，其服务能力是有限制的。此时该如何做? 一种解决方案是用边代替顶点，具体做法是对每个有容量顶点v，都添加一个新的顶点v’，连接vv’，使c(v→v’)=c(v)，并将v的流出边转移到v’上。
有上下界的算法优化?
4.2 最小费用最大流问题的图算法求解
本文暂时不对具体算法做讲解，可以参考:
最小费用最大流问题与算法实现（Bellman-Ford、SPFA、Dijkstra）_网络_不积跬步无以至千里-CSDN博客
参考资料:
1.用网络单纯形法(network simplex)解最小费用最大流(mincost)问题
https://zhuanlan.zhihu.com/p/80443584
4.3 最小费用最大流的应用
1).最小费用最大流模型在运输网络优化中的应用
运输作为现代物流过程的主要职能之一，是物流各项业务的中心活动。同时，运输产生的费用也是供应链和整个物流系统成本结构的重要组成部分。可以说，一个高效率、低成本和高反应能力的运输网络对一个成功的物流配送体系至关重要，这就使得运输网络的优化成为配送体系中一项重要的运营决策，关系到物流设计体系的成功与否。运输网络的优化主要是对运输路线的安排，即选择合理的配送路线，既能保证配送效率的最大化，又能同时使运输成本最低。
某公司链接产地到销地的物流运输体系为例进行说明。其中，产品运输网络如下图所示,图中各弧表示运输道路。由于道路实际地质情况不同，使得每条道路上的运输费用也不同，因此优化该运输系统除考虑货物的最大流外，还需要考虑道路运输的最小费用，即可基于本文所提的最小费用最大流模型予以求解。
弧上括号内的数字分别表示对应运输道路的容量限制和单位运费。
上例是标准的最小费用最大流问题，主要是感受下在实践中如何应用。
首先，求解最大流:
接着，求解最小费用:
参考论文:<<最小费用最大流模型在运输网络优化中的应用>>_郭京生
2).最小费用最大流模型在指派(分配)问题中的应用
设有5位工程师，5项任务 ， 他们各自能胜任任务的情况下图所示(边权重代表成本)，设计一种任务分配方案，使得尽可能多的工程师分配到任务，并且成本尽可能小的方案。其中，  表示工人，  表示任务。
我们可以转化为最小费用最大流问题求解。 在二分图中增加两个新点分别作为发点、收点。并用有向边把它们与原二分图中顶点相连，令全部边上的容量均为1 。最终如下图:
相比于二分图，最小费用最大流更加灵活，没有结点的限制。
参考论文:<<网络最大流问题的应用>>_朱淑芹
3).最小费用最大流模型在资源分配中的应用
某市政工程公司在未来5～8月份内需完成4项工程:修建一条地下通道修建一座人行天桥;修建 一条道路及道路维修。工期和所需劳动力如表所示, 公司共有120人，任 一 项工程在一个月内 的劳动力不能超过80人，则公司如何分配劳动力完成所有工程。
将工程计划用如下网络图表示，其中标号 5、6 、7 、8 分别表示月份，  、  、 、  表示工程在第i个月内 的完成部分， 用弧表示某月完成某项工程的状态, 弧的流量为劳动力限制。合理安排每 个月个工程的劳动力，在不超过现有人力的条件下，尽可能保证工程按期完成，就是求上图 从发点到收点的最大流问题。
求得分配结果:
4).最小费用最大流模型在资源调度中的应用
并行作业是大规模集群资源调度的热点，现有的研究工作多基于队列模型，仅能满足局部最优解且调度目标不变，灵活性不够。基于最小费用最大流的资源调度方法将任务的资源需求和物理资源供给问题转换成最小费用最大流的构造和求解问题，满足公平性、优先级和放置约束条件。
假设给定图  ,其中 是结点集，表示资源供需实体，包括任务需求方和资源供给方；  是边集，表示任务与资源的可满足性，即任务能否映射到相应资源； 是边上容量，表示资源供给能力；  是费用，表示任务与资源的映射效果。
基于最小费用最大流调度元素含义
最小费用最大流求解模型
1). 公平性
公平性指作业能够公平共享资源份额(资源份额通过特定公平算法)。例如，对于 其包含的任务数为 ，通过公平算法计算其公平份额为 ，如果调度算法分配给 的资源份额为 ，则该调度算法满足公平性。公平性通过图的边容量构造来表达，如下图:
设置 容量的上下界为:  。由于 的上下界均为 ，则通过 的流量  (最小费用最大流网络模型的约束条件)。即 中需要等待的任务为 个。 的任务 或流向 处于等待状态，或流向资源调度结点。因此， 通过资源结点的流量:
即 分配到 份额资源，满足最大最小公平性。
例如，给定 和 , 分别包含3个任务  和 4个任务  。4台机器  ，每个机器可运行一个任务，每个  资源需求为2。在对图进行构造时，  容量上下界赋值为  ,  容量上下界赋值为 [2,2]，即 有一个任务等待， 有两个任务等待，对应 有两个任务占用两台机器， 有两个任务占用两台机器运行，满足公平性。
2). 放置约束
在深度学习任务中，我们倾向于将任务部署到GPU中，这称之为放置约束。
表示任务， 表示任务约束的资源，  放置到 上所获得的效益。采用效益函数描述放置约束，即:
放置约束可映射到图的边有无构造问题。在 和 之间建立一条边  ，并赋予一个与效益值相反的费用，即:  。最大效益函数对应最小费用:
通过最小费用最大流网络表述的放置约束等价于放置约束的定义。举例，任务 图像处理程序，两台机器  。 带有GPU， 无GPU。 对 有放置约束，获得的收益为1；对 无放置约束，即收益为0.通过最小费用最大流求解，可以获得最小费用，即最大收益， 会在 执行。
放置约束定义
3). 优先级
所谓优先级是指优先级高的任务会先获取资源。最小费用最大流网络能够通过构造费用来支持优先级调度。参照Brog(Google大规模资源调度框架)带有优先级调度的费用计算公式定义为:
优先级调度费用计算公式
其中，  代表每一维度(CPU利用率维度、磁盘利用率维度等)的权重，每一维度的取值范围为  ,  是一个常数值。为了满足严格优先级约束，则优先级较高的任务费用一定最小。
如下示例，3个任务  优先级为1,2,5 ，即: 优先级最高，  次之，  优先级最低。计算得出所需费用分别为  且  。假设只有一台机器 ，构造最小费用最大流图时，根据最小费用最大流算法最小费用约束， 会获得资源，  等待。
综合看下前面的网络图:
Note:建模的关键是如何把业务语义映射到模型。
参考资料:
1.运筹学-图与网络模型以及最小费用最大流分解
https://wenku.baidu.com/view/c458f5777275a417866fb84ae45c3b3567ecdd99.html
2.网络流(4)——带有容量的顶点和二部匹配
https://wenku.baidu.com/view/c458f5777275a417866fb84ae45c3b3567ecdd99.html
3.最大流问题的应用_朱叔芹
4.运输网络转运结点有容量限制的最大流分配算法
http://www.doc88.com/p-9139305144431.html
5.【应用数学】最大流及最小费用的算法研究
http://www.doc88.com/p-4435802148736.html
6.基于最小费用最大流的大规模资源调度方法 |
本帖子中包含更多资源
您需要 登录 才可以下载或查看，没有账号？立即注册
×
|
窥视卡
雷达卡
发表于 2021-11-19 20:04
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
显身卡