运筹学经典问题（三）：最大流问题
问题描述
给定一个图网络
G
=
(
V
,
E
)
G=(V, E)
G=(V,E)，网络中连边的权重代表最大容量，在这个图中找出从起点到终点流量最大的路径。
数学建模
集合：
I
I
I：点的集合；
E
E
E：边的集合。
常量：
d
e
d_e
de?：边
e
e
e上的最大容量；
变量：
x
e
x_e
xe?：
e
e
e这条边的流量；
f
f
f：最大流量。
数学模型：
m
a
x
f
s
.
t
.
∑
e
∈
o
u
t
(
i
)
x
e
?
∑
e
∈
i
n
(
i
)
x
e
=
{
f
,
i
=
s
?
f
,
i
=
t
0
,
e
l
s
e
0
≤
x
e
≤
d
e
，
?
e
∈
E
max f \\ s.t. \sum_{e\in out(i)}x_e - \sum_{e\in in(i)}x_e = \begin{cases} f, i=s\\ -f, i=t\\ 0, else \end{cases} \\ 0 \leq x_e \leq d_e，\forall e \in E
maxfs.t.e∈out(i)∑?xe??e∈in(i)∑?xe?=?
?
??f,i=s?f,i=t0,else?0≤xe?≤de?，?e∈E
问题求解
方式一：扔给求解器；
方式二：Ford-fulkerson（FFA）算法
参考资料
- 运筹优化常用算法、模型及案例实战：Python+Java 实现. 刘兴禄，熊望祺，臧永森，段宏达，曾文佳，陈伟坚.
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！