August 2017
Intermediate to advanced
360 pages
8h 35m
Chinese
Content preview from 算法技术手册（原书第2 版）
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
228
｜
第
8
章
简单来讲，人工加入的源顶点会连向
m
个供应顶点，所连接的边费用为
0
，容量等同
于供应容量
sup
(
s
i
)
。
m
个供应顶点中的每个顶点都连接到
n
个需求顶点，所连接边的
费用为
d
(
i,j
)
，容量为无穷大。
n
个需求顶点中的每个顶点会连接到人工加入的新汇点
target
，所连接边的费用为
0
，容量等同于需求容量
dem
(
t
j
)
。
w
个仓库结点中的每个顶点
都会连接到
m
个供应节顶点，所连接边的费用为
ts
(
i,k
)
，容量等于供应容量
sup
(
s
i
)
；同样，
这些仓库结点也会连接到
n
个需求顶点，所连接边的费用为
ts
(
k,j
)
，容量等于需求容量
(
t
j
)
。
最后，仓库之间边的容量和费用会根据每个仓库的限制和费用进行相应设置。
如果对应的最小费用流问题能够得到解，那么转运问题也能够得到解，结果可以通过找
出所有
f
(
u, v
) > 0
的边
(
u, v
)
∈
E
进行构造。总费用等于这些边的
f
(
u, v
)*
d
(
u, v
)
之和。
8.7 运输问题
因为没有中继仓库结点，运输问题要比转运问题简单得多。它的输入包括：
•
有
m
个供应站
s
i
，每个供应站能够生产
sup
(
s
i
)
个单位的商品。
•
有
n
个需求站
t
j
，每个需求站需要
dem
(
t
j
)
个单位的商品。
边
(
u, v
)
上运输货物的固定单位
费用为
d
(
i, j
)
≥
0
。我们的目标是计算出从供应站
s
i
到需
求站
t
j
的流
f
(
i, j
)
，并最小化总运输费用
TSC
。
TSC
的简单定义为
总运输费用（
TSC
）
= ∑
i
∑
j
d
(
i,j
)*
f
(
i,j
)
解决方案还必须同时满足每个需求站
t
j
总的需求以及每个供应站 ...
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.