阅读 ‧ 电子书库

线性编程

本章描述的各种问题都可以用线性编程解决，如果能够在服从各种限制条件的情况下，优化好线性目标函数，那么这种解决方案将会非常高效和实用。

我们来看看实践中线性编程的表现吧，我们将图8-7的转运问题转换成一系列的线性等式，然后用线性编程来解决。我们使用了一个通用商业数学软件包Maple（http://www.maplesoft.com）来执行这些计算。回忆一下，这个目标是在最小化开销的同时最大化网络上的流。我们用变量来表示每条边上的流，变量e13表示f(1,3）。我们需要最小化开销函数，这个函数是在每条边上的运输开销的总和。开销等式的限制条件和之前描述的网络流问题的限制条件一样。

流量守恒

广告：个人专属 VPN，独立 IP，无限流量，多机房切换，还可以屏蔽广告和恶意软件，每月最低仅 5 美元

从源点发出的流总和必须等于其供应量。汇入到汇点的流的总和必须等于其需求。

容量限制

一条边的流f(i,j)必须大于等于0。同样f(i,j)≤c(i,j)。

Maple计算的结果是{e13=100，e24=100，e23=200，e14=200}，恰好等于之前计算出来的最小总开销（见例8-7）。

例8-7：求转运问题的最小化开销的Maple命令

George Dantzig在1947年提出的单纯形算法也能够解决例8-7中的问题，不过需要成百上千个变量（McCall，1982）。虽然在特定情况下，单纯形法也会导致指数级的计算，但是很多人证明这个方法在实践中非常高效。我们不推荐你自己实现单纯形法，因为它的复杂度较高，你可以借助商业软件库做这个工作。