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.
230
｜
第
8
章
8.9 线性规划
本章描述的各种问题都可以使用线性规划（
LP
）解决。线性规划是最优化问题中一种
非常重要的处理方法，它能够在满足线性等式和不等式约束的情况下优化线性目标函数
（
Bazaraa and Jarvis, 1977
）。
为了展示线性规划如何工作，我们将图
8-8
的运输问题转换成一系列的线性等式。我们
使用了一个通用的商业数学软件包
Maple
来执行这些计算。回忆一下，我们的目标是在
最小化费用的同时最大化网络上的流。我们用变量来表示每条边上的流量，变量
e13
表
示流量
f
(1, 3
）。我们需要最小化费用函数，这个函数是在网络上四条边的运输费用总和。
费用等式的限制条件如下：
流量守恒
从源顶点发出的流量总和必须等于其供应量。流入汇点的流量总和必须等于其需求
量。
容量限制
边的流量
f
(
i,j
)
必须大于等于
0
。同样，流量
f
(
i, j
)
≤
容量
c
(
i, j
)
。
Maple
计算的结果是
{e13 = 100
，
e24 = 100
，
e23 = 200
，
e14 = 200}
，恰好等于之前计
算出来的最小总费用
3300
（见例
8-7
）。
例
8-7
：在转运问题中应用最小化的
Maple
命令
Constraints := [
#
每个顶点的单位限制
e13+e14 = 300, # CHI
e23+e24 = 300, # DC
e13+e23 = 300, # HOU
e14+e24 = 300, # BOS
#
每条边上的最大流
0 <= e13, e13 <= 200,
0 <= e14, e14 <= 200,
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.