以 LP 问题形式对网络流问题求解

说明网络流模型与传统 LP 模型之间的转换。

网络流模型是具有特殊结构的 LP 模型。 CPLEX 网络优化器是主单纯形法技术的高效实现，它已修改为能够利用这种特殊结构。需要特别说明的是，不会执行基底因式分解。但是，如果首先将网络数据结构转换为 LP 模型的数据结构，那么可使用任何 CPLEX LP 优化器来求解网络模型。要将网络数据结构转换为 LP 数据结构，在 Interactive Optimizer 中请使用 change problem lp 命令，从 Callable Library 中请使用 CPXcopynettolp 例程。

图 1 中示例的 LP 阐述如下所示：

最小化

3a1 + 3a2 + 4a3 + 3a4 + 5a5 + 6a6 + 7a7 + 4a8 + 2a9 + 6a10 + 5a11 + 4a12 + 3a13 + 6a14

約束

a1 = 20

-a1 + a2 - a8 - a9 + a14 = 0

- a2 + a3 + a9 = 0

- a3 + a4 + a10 + a11 - a12 = -15

a7 + a8 - a10 - a13 = 5

- a5 + a6 - a11 + a12 + a13 - a14 = 0

- a4 + a5 = 0

- a6 - a7 = -10

使用这些边界

18 ≤ a1 ≤ 24 0 ≤ a2 ≤ 25 a3 = 12

0 ≤ a4 ≤ 10 0 ≤ a5 ≤ 9 a6 free

0 ≤ a7 ≤ 20 0 ≤ a8 ≤ 10 0 ≤ a9 ≤ 5

0 ≤ a10 ≤ 15 0 ≤ a11 ≤ 10 0 ≤ a12 ≤ 11

0 ≤ a13 ≤ 6 0 ≤ a14

在该阐述中，每一列都正好有一个等于 1 的系数，正好有一个等于 -1 的系数，并且所有其他系数均为 0。

因为网络流问题以此方式对应于 LP 问题，实际上还可通过 CPLEX LP 优化器来求解网络流问题。如果将网络流问题读取到 Interactive Optimizer 中，那么可使用 change problem lp 命令将其转换为 LP 阐述。进行此更改后，可以将任何 LP 优化器应用于此问题。

将网络流问题更改为 LP 问题时，该网络流问题中的基础信息将转递到 LP 阐述。实际上，如果已求解该网络流问题获得最优解，并且调用主或对偶单纯形法优化器（例如，使用 Interactive Optimizer 命令 primopt 或 tranopt 进行此调用），那么该单纯形法优化器将不执行迭代。

通常，还可将基底文件中的基底用于 LP 和网络优化器。但是，有一种例外情况：为了将 LP 基底与网络优化器配合使用，必须至少有一个松弛变量或一个人工变量是基本变量。从高级基启动在 LP 优化器的上下文中提供更多有关此主题的说明。

如果已将问题的 LP 阐述读取到 Interactive Optimizer 中，那么可使用 change problem network 命令将其转换为网络。给定任何 LP 问题和此命令，CPLEX 将尝试寻找 LP 问题中嵌入的最大网络，并将其转换为网络流问题。但是，执行此操作时，将废弃所有并非属于该嵌入式网络的行和列。同时，CPLEX 会将尽量多的基础信息传递到网络优化器。