respectively. By possibly multiplying both sides of some of the coupling constraints by -1 , we can assume that

D_{1} x_{1}^{1} + D_{2} x_{2}^{1} \leq b

. Let

y

be a vector of auxiliary variables of dimension

m_{0}

. We form the auxiliary master problem
分别为通过将某些耦合约束条件的两边乘以-1，我们可以假设

D_{1} x_{1}^{1} + D_{2} x_{2}^{1} \leq b

。让

y

成为维数为

m_{0}

的辅助变量向量。我们形成辅助主问题

\begin{aligned} minimize & \sum_{t = 1}^{m_{0}} y_{t} \\ subject to & \sum_{i = 1, 2} (\sum_{j \in J_{i}} λ_{i}^{j} D_{i} x_{i}^{j} + \sum_{k \in K_{i}} θ_{i}^{k} D_{i} w_{i}^{k}) + y = b_{0} \\ \sum_{j \in J_{1}} λ_{1}^{j} = 1 \\ \sum_{j \in J_{2}} λ_{2}^{j} = 1 \\ λ_{i}^{j} \geq 0, θ_{i}^{k} \geq 0, y_{t} \geq 0, \forall i, j, k, t . \end{aligned}

A basic feasible solution to the auxiliary problem is obtained by letting

λ_{1}^{1} = λ_{2}^{1} = 1, λ_{i}^{j} = 0

for

j \neq 1, θ_{i}^{k} = 0

for all

k

, and

y = b_{0} - D_{1} x_{1}^{1} - D_{2} x_{2}^{1}

. Starting from here, we can use the decomposition algorithm to solve the auxiliary master problem. If the optimal cost is positive, then the master problem is infeasible. If the optimal cost is zero, an optimal solution to the auxiliary problem provides us with a basic feasible solution to the master problem.
在所有

k

和

y = b_{0} - D_{1} x_{1}^{1} - D_{2} x_{2}^{1}

的情况下，让

λ_{1}^{1} = λ_{2}^{1} = 1, λ_{i}^{j} = 0

对于

j \neq 1, θ_{i}^{k} = 0

得到辅助问题的基本可行解。从这里开始，我们可以使用分解算法来解决辅助主问题。如果最优成本为正，则主问题不可行。如果最优成本为零，则辅助问题的最优解为我们提供了主问题的基本可行解。

Termination and computational experience
终止和计算经验

The decomposition algorithm is a special case of the revised simplex method and, therefore, inherits its termination properties. In particular, in the absence of degeneracy, it is guaranteed to terminate in a finite number of steps. In the presence of degeneracy, finite termination is ensured if an anticycling rule is used, although this is rarely done in practice. Note that Bland’s rule cannot be applied in this context, because it is incompatible with the way that the decomposition algorithm chooses the entering variable. There is no such difficulty, in principle, with the lexicographic pivoting rule, provided that the inverse basis matrix is explicitly computed.
分解算法是修正单纯形法的特例，因此继承了其终止特性。特别是，在没有退化的情况下，它能保证在有限步数内终止。在存在退化的情况下，如果使用反循环规则，就能保证有限终止，不过在实际应用中很少这样做。需要注意的是，布兰德规则不能用于这种情况，因为它与分解算法选择进入变量的方式不兼容。原则上，只要逆基矩阵是明确计算出来的，使用词典枢轴规则就不会有这种困难。

A practical way of speeding up the solution of the subproblems is to start the simplex method on a subproblem using the optimal solution obtained the previous time that the subproblem was solved. As long as the objective function of the subproblem does not change too drastically between successive master iterations, one expects that this could lead to an optimal solution for the subproblem after a relatively small number of iterations.
加快子问题求解速度的一个实用方法是，使用上一次求解子问题时获得的最优解来启动子问题的单纯形法。只要子问题的目标函数在连续的主迭代之间变化不太剧烈，我们就有望在相对较少的迭代次数后得到子问题的最优解。

Practical experience suggests that the algorithm makes substantial progress in the beginning, but the cost improvement can become very slow
实际经验表明，该算法在开始阶段会取得实质性进展，但成本的提高会变得非常缓慢
later on. For this reason, the algorithm is sometimes terminated prematurely, yielding a suboptimal solution.
的算法。因此，算法有时会过早终止，从而产生一个次优解。

The available experience also suggests that the algorithm is usually no faster than the revised simplex method applied to the original problem. The true advantage of the decomposition algorithm lies in its storage requirements. Suppose that we have

t

subproblems, each one having the same number

m_{1}

of equality constraints. The storage requirements of the revised simplex method for the original problem are

O ({(m_{0} + t m_{1})}^{2})

, which is the size of the revised simplex tableau. In contrast, the storage requirements of the decomposition algorithm are

O ({(m_{0} + t)}^{2})

for the tableau of the master problem, and

t

times

O (m_{1}^{2})

for the revised simplex tableaux of the subproblems. Furthermore, the decomposition algorithm needs to have only one tableau stored in main memory at any given time. For example, if

t = 10

and if

m_{0} = m_{1}

is much larger than

t

, the main memory requirements of the decomposition algorithm are about 100 times smaller than those of the revised simplex method. With memory being a key bottleneck in handling very large linear programming problems, the decomposition approach can substantially enlarge the range of problems that can be practically solved.
现有经验还表明，该算法的速度通常并不比应用于原始问题的修正单纯形法快。分解算法的真正优势在于其存储要求。假设我们有

t

个子问题，每个子问题都有相同数量的

m_{1}

个相等约束。修正单纯形法对原始问题的存储需求为

O ({(m_{0} + t m_{1})}^{2})

，即修正单纯形表的大小。相比之下，分解算法对主问题表象的存储需求为

O ({(m_{0} + t)}^{2})

，对子问题的修正单纯形表象的存储需求为

t

乘以

O (m_{1}^{2})

。此外，分解算法在任何时候都只需在主内存中存储一个表元。例如，如果

t = 10

和

m_{0} = m_{1}

远大于

t

，分解算法所需的主内存大约是修正单纯形法的 100 倍。在处理超大线性规划问题时，内存是一个关键瓶颈，因此分解方法可以大大扩展实际求解问题的范围。

Bounds on the optimal cost
最佳成本的界限

As already discussed, the decomposition algorithm may take a long time to terminate, especially for very large problems. We will now show how to obtain upper and lower bounds for the optimal cost. Such bounds can be used to stop the algorithm once the cost gets acceptably close to the optimum.
正如前面已经讨论过的，分解算法可能需要很长时间才能结束，特别是对于非常大的问题。现在，我们将展示如何获得最佳成本的上下限。一旦成本接近最优值，就可以利用这些界限来停止算法。

Theorem 6.1 Suppose that the master problem is feasible and its optimal cost

z^{*}

is finite. Let

z

be the cost of the feasible solution obtained at some intermediate stage of the decomposition algorithm. Also, let

r_{i}

be the value of the dual variable associated with the convexity constraint for the ith subproblem. Finally, let

z_{i}

be the optimal cost in the ith subproblem, assumed finite. Then,
定理 6.1 假设主问题是可行的，且其最优成本

z^{*}

是有限的。设

z

是在分解算法的某个中间阶段得到的可行解的成本。同时，设

r_{i}

为第 i 个子问题中与凸性约束相关的对偶变量的值。最后，设

z_{i}

为第 i 个子问题的最优成本，假定为有限成本。那么

z + \sum_{i} (z_{i} - r_{i}) \leq z^{*} \leq z

Proof. The inequality

z^{*} \leq z

is obvious, since

z

is the cost associated with a feasible solution to the original problem. It remains to prove the left-hand side inequality in the statement of the theorem.
证明。不等式

z^{*} \leq z

是显而易见的，因为

z

是与原问题的可行解相关的成本。剩下的就是证明定理说明中左侧的不等式。

We provide the proof for the case of two subproblems. The proof for
我们提供了两个子问题的证明。证明
the general case is similar. The dual of the master problem is
一般情况也类似。主问题的对偶关系为

\begin{aligned} maximize & q^{'} b_{0} + r_{1} + r_{2} \\ subject to & q^{'} D_{1} x_{1}^{j} + r_{1} & \leq c_{1}^{'} x_{1}^{j}, & \forall j \in J_{1}, \\ q^{'} D_{1} w_{1}^{k} & \leq c_{1}^{'} w_{1}^{k}, & \forall k \in K_{1}, \\ q^{'} D_{2} x_{2}^{j} + r_{2} \leq c_{2}^{'} x_{2}^{j}, & \forall j \in J_{2}, \\ q^{'} D_{2} w_{2}^{k} & \leq c_{2}^{'} w_{2}^{k}, & \forall k \in K_{2} . \end{aligned}

Suppose that we have a basic feasible solution to the master problem, with

cost z

, and let (

q, r_{1}, r_{2}

) be the associated vector of simplex multipliers. This is a (generally infeasible) basic solution to the dual problem, with the same cost, that is,
假设我们有一个主问题的基本可行解，其值为

cost z

，并让 (

q, r_{1}, r_{2}

) 作为相关的单倍乘数向量。这是对偶问题的基本解（一般不可行），其代价相同，即

q^{'} b_{0} + r_{1} + r_{2} = z

Since the optimal cost

z_{1}

in the first subproblem is finite, we have
由于第一个子问题中的最优成本

z_{1}

是有限的，所以我们有

\begin{aligned} min_{j \in J_{1}} (c_{1}^{'} x_{1}^{j} - q^{'} D_{1} x_{1}^{j}) & = z_{1} \\ min_{k \in K_{1}} (c_{1}^{'} w_{1}^{k} - q^{'} D_{1} w_{1}^{k}) & \geq 0 \end{aligned}

Thus,

q

together with

z_{1}

in the place of

r_{1}

, satisfy the first two dual constraints. By a similar argument,

q

together with

z_{2}

in the place of

r_{2}

, satisfy the last two dual constraints. Therefore,

(q, z_{1}, z_{2})

is a feasible solution to the dual problem (6.14). Its cost is

q^{'} b_{0} + z_{1} + z_{2}

and, by weak duality, is no larger than the optimal cost

z^{*}

. Hence,
因此，

q

连同代替

r_{1}

的

z_{1}

满足前两个对偶约束条件。根据类似的论证，

q

和代替

r_{2}

的

z_{2}

满足后两个对偶约束条件。因此，

(q, z_{1}, z_{2})

是对偶问题 (6.14) 的可行解。其成本为

q^{'} b_{0} + z_{1} + z_{2}

，根据弱对偶性，不大于最优成本

z^{*}

。因此

\begin{aligned} z^{*} & \geq q^{'} b_{0} + z_{1} + z_{2} \\ = q^{'} b_{0} + r_{1} + r_{2} + (z_{1} - r_{1}) + (z_{2} - r_{2}) \\ = z + (z_{1} - r_{1}) + (z_{2} - r_{2}) \end{aligned}

where the last equality follows from Eq. (6.15).
其中最后一个等式来自公式 (6.15)。
Note that if the optimal cost in one of the subproblems is

- \infty

, then Theorem 6.1 does not provide any useful bounds.
请注意，如果其中一个子问题的最优成本是

- \infty

，那么定理 6.1 不会提供任何有用的约束条件。

The proof of Theorem 6.1 is an instance of a general method for obtaining lower bounds on the optimal cost of linear programming problems, which is the following. Given a nonoptimal basic feasible solution to the primal, we consider the corresponding (infeasible) basic solution to the dual problem. If we can somehow modify this dual solution, to make it feasible, the weak duality theorem readily yields a lower bound. This was the approach taken in the proof of Theorem 6.1, where we started from the generally infeasible dual solution (

q, r_{1}, r_{2}

), moved to the dual feasible solution

(q, z_{1}, z_{2}

), and then invoked weak duality.
定理 6.1 的证明是获取线性规划问题最优成本下限的一般方法的一个实例，具体如下。给定一个非最优的基本可行解，我们考虑对偶问题的相应（不可行）基本解。如果我们能以某种方式修改这个对偶解，使其变得可行，那么弱对偶定理就能轻易得出一个下限。这就是定理 6.1 的证明方法，我们从一般不可行的对偶解 (

q, r_{1}, r_{2}

) 开始，移到对偶可行解

(q, z_{1}, z_{2}

)，然后引用弱对偶性。

Example 6.4 Let us revisit Example 6.2 and consider the situation just before the first change of basis. We are at a basic feasible solution determined by
例 6.4 让我们重温例 6.2，看看第一次改变基础之前的情况。我们的基本可行解由以下条件决定

(λ^{1}, λ^{2}) = (0.8, 0.2)

. Since

c_{B} = (- 22, - 17)

, we have

z = (- 22, - 17)^{'} (0.8, 0.2) =

-21 . We also have

r = - 4

. Finally, the optimal cost in the subproblem is

(- 1, 1, - 2)^{'} (2, 1, 2) = - 5

. It follows that

- 21 \geq z^{*} \geq - 21 + (- 5) - (- 4) = - 22

. Indeed, the true value of

z^{*}

is -21.5 .

(λ^{1}, λ^{2}) = (0.8, 0.2)

。由于

c_{B} = (- 22, - 17)

，我们有

z = (- 22, - 17)^{'} (0.8, 0.2) =

-21 。我们还有

r = - 4

。最后，子问题中的最优成本为

(- 1, 1, - 2)^{'} (2, 1, 2) = - 5

。由此可知，

- 21 \geq z^{*} \geq - 21 + (- 5) - (- 4) = - 22

。事实上，

z^{*}

的真实值是 -21.5 。

6.5 Stochastic programming and Benders decomposition
6.5 随机程序设计和本德斯分解

In this section, we introduce and study two-stage stochastic linear programming problems. In this important class of problems, there are two sets of decisions that are made in consecutive stages. Furthermore, there are some exogenous parameters that influence the second stage of decision making, but whose values are uncertain, and only become known after the first set of decisions has been fixed. In order to address problems of this type, we develop a new decomposition algorithm, called Benders decomposition, which is based on delayed constraint generation (as opposed to delayed column generation).
在本节中，我们将介绍并研究两阶段随机线性规划问题。在这一类重要问题中，有两组决策是在连续的阶段中做出的。此外，还有一些影响第二阶段决策的外生参数，但这些参数的值是不确定的，只有在第一组决策确定后才能知道。为了解决这类问题，我们开发了一种新的分解算法，称为本德斯分解法，它基于延迟约束生成（而不是延迟列生成）。

Problem formulation 问题的提出

Consider a decision maker who has to act in two consecutive stages. The first stage involves the choice of a decision vector

x

. Subsequently, some new information is obtained, and then, at the second stage, a new vector

y

of decisions is to be chosen. Regarding the nature of the obtained information, we assume that there are

K

possible scenarios, and that the true scenario is only revealed after

x

is chosen. We use

ω

to index the different scenarios, and we let

α_{ω}

stand for the probability of any particular scenario

ω

, which we assume to be positive. Since the second stage decisions are made after the true scenario

ω

becomes known, we allow the decision vector

y

to depend on

ω

, and we use the notation

y_{ω}

to make this dependence explicit.
考虑一个必须在两个连续阶段采取行动的决策者。第一阶段涉及选择一个决策向量

x

。随后，会获得一些新信息，然后在第二阶段，需要选择一个新的决策向量

y

。关于所获信息的性质，我们假设有

K

种可能的情况，而真实情况只有在选择

x

之后才会揭示。我们用

ω

来表示不同的情况，用

α_{ω}

表示任何特定情况的概率

ω

，我们假设该概率为正值。由于第二阶段的决策是在已知真实情况

ω

之后做出的，因此我们允许决策向量

y

取决于

ω

，我们使用符号

y_{ω}

来明确表示这种依赖关系。

We now make more specific assumptions on the problem objectives and constraints. We are given cost vectors

c

and

f

, associated with the decisions

x

and

y_{ω}

, respectively. The first stage decisions must satisfy the constraints
现在，我们对问题的目标和约束条件做出更具体的假设。我们给定了成本向量

c

和

f

，分别与决策

x

和

y_{ω}

相关联。第一阶段的决策必须满足以下约束条件

\begin{aligned} A x & = b \\ x & \geq 0 \end{aligned}

In addition, the first and second stage decisions need to satisfy constraints of the form
此外，第一和第二阶段的决策需要满足以下形式的约束条件

\begin{aligned} B_{ω} x + D y_{ω} & = d_{ω} \\ y_{ω} & \geq 0 \end{aligned}

for all

ω

; in particular, every scenario may involve a different set of constraints. The objective is to choose

x

and

y_{1}, \dots, y_{K}

so that the “expected cost”
对于所有

ω

；特别是，每个方案都可能涉及一组不同的约束条件。我们的目标是选择

x

和

y_{1}, \dots, y_{K}

，从而使 "预期成本"

c^{'} x + α_{1} f^{'} y_{1} + \dots + α_{K} f^{'} y_{K}

is minimized. We thus arrive at the problem
最小。因此，我们得出以下问题

which will be referred to as the master problem. Notice that even if the number of possible scenarios

K

is moderate, this formulation can be a large linear programming problem. For this reason, a decomposition method is in order.
将被称为主问题。请注意，即使可能出现的情况

K

数量适中，这一表述也可能是一个庞大的线性规划问题。因此，需要采用分解方法。

Example 6.5 (Electric power capacity expansion) An electric utility is installing two generators (indexed by

j = 1, 2

) with different fixed and operating costs, in order to meet the demand within its service region. Each day is divided into three parts of equal duration, indexed by

i = 1, 2, 3

. These correspond to parts of the day during which demand takes a base, medium, or peak value, respectively. The fixed cost per unit capacity of generator

j

is amortized over its lifetime and amounts to

c_{j}

per day. The operating cost of generator

j

during the

i

th part of the day is

f_{i j}

. If the demand during the

i

th part of the day cannot be served due to lack of capacity, additional capacity must be purchased at a cost of

g_{i}

. Finally, the capacity of each generator

j

is required to be at least

b_{j}

.
例 6.5（电力容量扩展）某电力公司正在安装两台固定成本和运营成本不同的发电机（以

j = 1, 2

为指标），以满足其服务区域内的需求。每天被划分为持续时间相同的三个部分，以

i = 1, 2, 3

为索引。这三个部分分别对应一天中需求量为基本值、中等值或高峰值的时段。发电机

j

的单位容量固定成本在其使用期内摊销，每天为

c_{j}

。发电机

j

在

i

日期间的运行成本为

f_{i j}

。如果

i

日间的需求因发电能力不足而无法满足，则必须购买额外的发电能力，费用为

g_{i}

。最后，要求每台发电机

j

的容量至少为

b_{j}

。

There are two sources of uncertainty, namely, the exact value of the demand

d_{i}

during each part of the day, and the availability

a_{j}

of generator

j

. The demand

d_{i}

can take one of four values

d_{i, 1}, \dots, d_{i, 4}

, with probability

p_{i, 1}, \dots, p_{i, 4}

, respectively. The availability of generator 1 is

a_{1, 1}, \dots, a_{1, 4}

, with probability

q_{1, 1}, \dots, q_{1, 4}

, respectively. Similarly, the availability of generator 2 is

a_{2, 1}, \dots, a_{2, 5}

, with probability

q_{2, 1}, \dots, q_{2, 5}

, respectively. If we enumerate all the possible events, we see that there is a total of

4^{3} \times 4 \times 5 = 1280

scenarios

ω

. Let us use

d_{i}^{ω}

and

a_{j}^{ω}

to denote the demands and availabilities, respectively, under scenario

ω

.
不确定因素有两个，即一天中每个时段的需求量

d_{i}

的准确值，以及发电机

j

的可用性

a_{j}

。需求量

d_{i}

可以取四个值之一

d_{i, 1}, \dots, d_{i, 4}

，概率分别为

p_{i, 1}, \dots, p_{i, 4}

。发电机 1 的可用性为

a_{1, 1}, \dots, a_{1, 4}

，概率分别为

q_{1, 1}, \dots, q_{1, 4}

。同样，发电机 2 的可用性分别为

a_{2, 1}, \dots, a_{2, 5}

，概率为

q_{2, 1}, \dots, q_{2, 5}

。如果我们列举所有可能发生的事件，就会发现共有

4^{3} \times 4 \times 5 = 1280

种情况

ω

。让我们用

d_{i}^{ω}

和

a_{j}^{ω}

分别表示

ω

情况下的需求和可用性。

We introduce the first stage variables

x_{j}, j = 1, 2

, that represent the installed capacity of generator

j

. We also introduce the second stage variables

y_{i j}^{ω}

that denote the operating levels of generator

j

during the

i

th part of the day and under scenario

ω

. Finally

y_{i}^{ω}

is the capacity that needs to be purchased under scenario

ω

, in order to satisfy unmet demand during the

i

th part of the day. We interpret availability to mean that the operating level of generator

j

, at any given time, is at most

a_{j} x_{j}

. We then arrive at the following formulation:
我们引入第一阶段变量

x_{j}, j = 1, 2

，表示发电机

j

的装机容量。我们还引入了第二阶段变量

y_{i j}^{ω}

，表示发电机

j

在一天中

i

的第 3 个时段和情景

ω

下的运行水平。最后，

y_{i}^{ω}

是在情景

ω

下需要购买的容量，以满足一天中

i

第 3 个时段未满足的需求。我们将可用性解释为，在任何给定时间内，发电机

j

的运行水平最多为

a_{j} x_{j}

。因此，我们得出以下公式：

\begin{aligned} minimize & \sum_{j = 1}^{2} c_{j} x_{j} + E [\sum_{i = 1}^{3} (\sum_{j = 1}^{2} f_{i j} y_{i j}^{ω} + g_{i} y_{i}^{ω})] \\ subject to & x_{j} \geq b_{j}, & \forall j, \\ y_{i j}^{ω} \leq a_{j}^{ω} x_{j}, & \forall i, j, ω, \\ \sum_{j = 1}^{2} y_{i j}^{ω} + y_{i}^{ω} \geq d_{i}^{ω}, & \forall i, ω, \\ x_{j}, y_{i j}^{ω}, y_{i}^{ω} \geq 0, & \forall i, j, ω . \end{aligned}

(Here,

E [\cdot]

stands for mathematical expectation, that is the average over all scenarios

ω

, weighted according to their probabilities.) The full model involves 11522 variables and 11522 constraints (not counting nonnegativity constraints).
(这里，

E [\cdot]

代表数学期望，即所有情况

ω

的平均值，根据其概率加权）。整个模型涉及 11522 个变量和 11522 个约束条件（不包括非负性约束条件）。

Reformulation of the problem
问题的重新表述

Consider a vector

x

such that

A x = b

and

x \geq 0

, and suppose that this is our choice for the first stage decisions. Once

x

is fixed, the optimal second stage decisions

y_{ω}

can be determined separately from each other, by solving for each

ω

the problem
考虑一个向量

x

，即

A x = b

和

x \geq 0

，并假设这是我们对第一阶段决策的选择。一旦

x

固定下来，就可以通过求解每个

ω

的问题，分别确定最佳的第二阶段决策

y_{ω}

。

\begin{aligned} minimize & f^{'} y_{ω} \\ subject to & B_{ω} x + {D y}_{ω} = d_{ω} \\ y_{ω} \geq 0 \end{aligned}

Let

z_{ω} (x)

be the optimal cost of the problem (6.16), together with the convention

z_{ω} (x) = \infty

if the problem is infeasible. If we now go back to the optimization of

x

, we are faced with the problem
让

z_{ω} (x)

成为问题 (6.16) 的最优成本，如果问题不可行，则加上约定

z_{ω} (x) = \infty

。如果我们现在回到

x

的优化，我们将面临以下问题

\begin{aligned} minimize & c^{'} x + \sum_{ω = 1}^{K} α_{ω} z_{ω} (x) \\ subject to & A x = b \\ x \geq 0 \end{aligned}

Of course, in solving this problem, we should only consider those

x

for which none of the

z_{ω} (x)

are equal to infinity.
当然，在解决这个问题时，我们只应考虑那些

x

中的

z_{ω} (x)

都不等于无穷大的情况。

We will approach problem (6.16) by forming its dual, which is
我们将通过形成其对偶来处理问题 (6.16)，即

\begin{aligned} maximize & p_{ω}^{'} (d_{ω} - B_{ω} x) \\ subject to & p_{ω}^{'} D \leq f^{'} \end{aligned}

Let 让

P = {p ∣ p^{'} D \leq f^{'}}

We assume that

P

is nonempty and has at least one extreme point. Let

p^{i}

i = 1, \dots, I

, be the extreme points, and let

w^{j}, j = 1, \dots, J

, be a complete set of extreme rays of

P

.
我们假设

P

是非空且至少有一个极值点。设

p^{i}

i = 1, \dots, I

, 为极值点，设

w^{j}, j = 1, \dots, J

, 为

P

的极值射线的完整集合。

Under our assumption that the set

P

is nonempty, either the dual problem (6.18) has an optimal solution and

z_{ω} (x)

is finite, or the optimal dual cost is infinite, the primal problem (6.16) is infeasible, and

z_{ω} (x) = \infty

. In particular,

z_{ω} (x) < \infty

if and only if
在我们假设集合

P

是非空的情况下，要么对偶问题 (6.18) 有最优解，且

z_{ω} (x)

有限；要么最优对偶成本无限，原始问题 (6.16) 不可行，且

z_{ω} (x) = \infty

有限。特别是，

z_{ω} (x) < \infty

当且仅当

{(w^{j})}^{'} (d_{ω} - B_{ω} x) \leq 0, \forall j

Whenever

z_{ω} (x)

is finite, it is the optimal cost of the problem (6.18), and the optimum must be attained at an extreme point of the set

P

; in particular,
只要

z_{ω} (x)

是有限的，它就是问题 (6.18) 的最优代价，而且最优代价必须在集合

P

的一个极值点上达到；具体而言，

z_{ω} (x)

是问题 (6.18) 的最优代价，而且最优代价必须在集合

P

的一个极值点上达到、

z_{ω} (x) = max_{i = 1, \dots, I} {(p^{i})}^{'} (d_{ω} - B_{ω} x)

Alternatively,

z_{ω} (x)

is the smallest number

z_{ω}

such that
或者，

z_{ω} (x)

是最小的数

z_{ω}

，使得

{(p^{i})}^{'} (d_{ω} - B_{ω} x) \leq z_{ω}, \forall i

We use this characterization of

z_{ω} (x)

in the original problem (6.17), and also take into account the condition (6.19), which is required for

z_{ω} (x)

to be finite, and we conclude that the master problem (6.17) can be put in the form
我们在原问题 (6.17) 中使用

z_{ω} (x)

的这一特性，并考虑

z_{ω} (x)

必须为有限的条件 (6.19)，得出主问题 (6.17) 的形式为

\begin{aligned} minimize & c^{'} x + \sum_{ω = 1}^{K} α_{ω} z_{ω} \\ subject to & A x = b \\ {(p^{i})}^{'} (d_{ω} - B_{ω} x) \leq z_{ω}, & \forall i, ω, \\ {(w^{j})}^{'} (d_{ω} - B_{ω} x) \leq 0, & \forall j, ω, \\ x \geq 0 . \end{aligned}

With this reformulation, the number of variables has been reduced substantially. The number of constraints can be extremely large, but this obstacle can be overcome using the cutting plane method. In particular, we will only generate constraints that we find to be violated by the current solution.
通过这种重新表述，变量的数量大大减少。约束条件的数量可能极其庞大，但这一障碍可以通过切割平面法来克服。特别是，我们将只生成我们发现当前解法违反的约束条件。

Delayed constraint generation
延迟生成制约因素

At a typical iteration of the algorithm, we consider the relaxed master problem, which has the same objective as the problem (6.20), but involves only a subset of the constraints. We assume that we have an optimal solution to the relaxed master problem, consisting of a vector

x^{*}

and a vector

z^{*} = (z_{1}^{*}, \dots, z_{K}^{*})

. In the spirit of the cutting plane method, we need to check whether (

x^{*}, z^{*}

) is also a feasible solution to the full master problem. However, instead of individually checking all of the constraints, we proceed by solving some auxiliary subproblems.
在算法的典型迭代中，我们考虑的是松弛主问题，其目标与问题 (6.20) 相同，但只涉及约束条件的子集。我们假设松弛主问题有一个最优解，它由一个向量

x^{*}

和一个向量

z^{*} = (z_{1}^{*}, \dots, z_{K}^{*})

组成。根据切割面法的精神，我们需要检查 (

x^{*}, z^{*}

) 是否也是完整主问题的可行解。不过，我们不用逐个检查所有约束条件，而是通过求解一些辅助子问题来进行。

For

ω = 1, \dots, K

, we consider the subproblem
对于

ω = 1, \dots, K

，我们考虑子问题

\begin{aligned} minimize & f^{'} y_{ω} \\ subject to & D y_{ω} = d_{ω} - B_{ω} x^{*} \\ y_{ω} \geq 0 \end{aligned}

which we solve to optimality. Notice that the subproblems encountered at different iterations, or for different values of

ω

, differ only in the right-hand side vector

d_{ω} - B_{ω} x^{*}

. In particular, the corresponding dual problems always have the same feasible set, namely,

P

. For this reason, it is natural to assume that the subproblems are solved by means of the dual simplex method.
我们对其进行优化求解。请注意，不同迭代或

ω

的不同值所遇到的子问题仅在右侧向量

d_{ω} - B_{ω} x^{*}

上有所不同。特别是，相应的对偶问题总是具有相同的可行集，即

P

。因此，可以很自然地假定这些子问题是通过对偶单纯形法求解的。

There are a few different possibilities to consider:
有几种不同的可能性可以考虑：
(a) If the dual simplex method indicates that a (primal) subproblem is infeasible, it provides us with an extreme ray

w^{j (ω)}

of the dual feasible set

P

, such that
(a) 如果对偶单纯形法表明某个（初等）子问题不可行，它就会为我们提供对偶可行集

P

的极端射线

w^{j (ω)}

，使得

{(w^{j (ω)})}^{'} (d_{ω} - B_{ω} x^{*}) > 0

We have then identified a violated constraint, which can be added to the relaxed master problem.
这样，我们就确定了一个被违反的约束条件，可以将其添加到放松的主问题中。
(b) If a primal subproblem is feasible, then the dual simplex method terminates, and provides us with a dual optimal basic feasible solution

p^{i (ω)}

. If we have
(b) 如果初等子问题可行，则对偶单纯形法终止，并为我们提供一个对偶最优基本可行解

p^{i (ω)}

。如果我们有

{(p^{i (ω)})}^{'} (d_{ω} - B_{ω} x^{*}) > z_{ω}^{*}

we have again identified a violated constraint, which can be added to the relaxed master problem.
我们再次发现了一个被违反的约束条件，可以将其添加到放宽的主问题中。
© Finally, if the primal subproblems are all feasible and we have
最后，如果基本子问题都是可行的，并且我们有

{(p^{i (ω)})}^{'} (d_{ω} - B_{ω} x^{*}) \leq z_{ω}^{*}

for all

ω

, then, by the optimality of

p^{i (ω)}

, we obtain
对于所有

ω

，根据

p^{i (ω)}

的最优性，我们可以得到

{(p^{i})}^{'} (d_{ω} - B_{ω} x^{*}) \leq z_{ω}^{*}

for all extreme points

p^{i}

. In addition,
的所有极值点

p^{i}

。此外还有

{(w^{j})}^{'} (d_{ω} - B_{ω} x^{*}) \leq 0

for all extreme rays

w^{j}

, and no constraint is violated. We then have an optimal solution to the master problem (6.20), and the algorithm terminates.
对于所有极端射线

w^{j}

，没有违反任何约束条件。这样我们就得到了主问题 (6.20) 的最优解，算法结束。

The resulting algorithm is summarized below.
由此产生的算法概述如下。

Benders decomposition for two-stage problems
两阶段问题的本德尔分解

A typical iteration starts with a relaxed master problem, in which only some of the constraints of the master problem (6.20) are included. An optimal solution ( $x^{*}, z^{*}$ ) to the relaxed master problem is calculated.
典型的迭代是从松弛主问题开始的，其中只包含主问题 (6.20) 的部分约束条件。计算出松弛主问题的最优解 ( $x^{*}, z^{*}$ )。
For every $ω$ , we solve the subproblem
对于每个 $ω$ ，我们要解决的子问题是

\begin{aligned} minimize & f^{'} y_{ω} \\ subject to & {D y}_{ω} = d_{ω} - B_{ω} x^{*} \\ y_{ω} \geq 0, \end{aligned}

using the dual simplex method.
使用对偶单纯形法。
3. If for every

ω

, the corresponding subproblem is feasible and the optimal cost is less than or equal to

z_{ω}^{*}

, all constraints are satisfied, we have an optimal solution to the master problem, and the algorithm terminates.
3.如果对每个

ω

而言，相应的子问题都是可行的，且最优成本小于或等于

z_{ω}^{*}

，所有约束条件都得到满足，我们就有了主问题的最优解，算法终止。
4. If the subproblem corresponding to some

ω

has an optimal solution whose cost is greater than

z_{ω}^{*}

, an optimal basic feasible solution

p^{i (ω)}

to the dual of the subproblem is identified, and the constraint
4.如果与某个

ω

相对应的子问题有一个成本大于

z_{ω}^{*}

的最优解，那么子问题对偶的最优基本可行解

p^{i (ω)}

就确定了，并且约束条件

{(p^{i (ω)})}^{'} (d_{ω} - B_{ω} x) \leq z_{ω}^{*}

is added to the relaxed master problem.
被添加到放宽的主问题中。
5. If the subproblem corresponding to some

ω

is infeasible, its dual has infinite cost, and a positive cost extreme ray

w^{j (ω)}

is identified. Then, the constraint
5.如果与某个

ω

相对应的子问题不可行，则其对偶问题的代价是无限的，并且会出现一条正代价的极端射线

w^{j (ω)}

。那么，约束条件

{(w^{j (ω)})}^{'} (d_{ω} - B_{ω} x) \leq 0

is added to the relaxed master problem.
被添加到放宽的主问题中。

Benders decomposition uses delayed constraint generation and the cutting plane method, and should be contrasted with Dantzig-Wolfe decomposition, which is based on column generation. Nevertheless, the two methods are almost identical, with Benders decomposition being essentially the same as Dantzig-Wolfe decomposition applied to the dual. Let us also note, consistently with our discussion in Section 6.3, that we have the option of discarding all or some of the constraints in the relaxed primal that have become inactive.
本德斯分解法采用延迟约束生成和切割面法，应与基于列生成的丹齐格-沃尔夫分解法相比较。尽管如此，这两种方法几乎是相同的，本德斯分解法本质上等同于应用于对偶的 Dantzig-Wolfe 分解法。我们还要注意的是，与第 6.3 节中的讨论一致，我们可以选择丢弃松弛初等数中所有或部分已失效的约束条件。

One of the principal practical difficulties with stochastic programming, is that the number

K

of possible scenarios is often large, leading to a large number of subproblems. This is even more so for stochastic programming problems involving more than two stages, where similar methods can be in principle applied. A number of remedies have been proposed, in-
随机程序设计的一个主要实际困难是，可能出现的情况

K

往往很多，从而导致大量子问题。对于涉及两个以上阶段的随机编程问题，情况更是如此，原则上可以采用类似的方法。已经提出了一些补救措施，包括
cluding the use of random sampling to generate only a representative set of scenarios. With the use of parallel computers and sophisticated sampling methods, the solution of some extremely large problems may become possible.
其中包括使用随机抽样来生成一组有代表性的方案。随着并行计算机和复杂抽样方法的使用，一些极其庞大的问题也有可能得到解决。

6.6 Summary 6.6 小结

The main ideas developed in this chapter are the following:
本章提出的主要观点如下：
(a) In a problem with an excessive number of columns, we need to generate a column only if its reduced cost is negative, and that column is to enter the basis (delayed column generation). A method of this type requires an efficient subroutine for identifying a variable with negative reduced cost.
(a) 在一个列数过多的问题中，我们只需要在列的还原成本为负数时生成一列，该列将进入基数（延迟生成列）。这种方法需要一个有效的子程序来识别还原成本为负的变量。
(b) In a problem with an excessive number of constraints, a constraint needs to be taken into account only if it is violated by the current solution (delayed constraint generation). A method of this type (cutting plane method) requires an efficient subroutine for identifying violated constraints.
(b) 在约束条件过多的问题中，只有在当前解法违反某一约束条件时，才需要考虑该约束条件（延迟约束条件生成）。这种方法（切割面法）需要一个高效的子程序来识别违反的约束条件。
We have noted that delayed column generation methods applied to the primal coincide with cutting plane methods applied to the dual. Furthermore, we noted that there are several variants depending on whether we retain or discard from memory previously generated columns or constraints.
我们注意到，应用于主线的延迟列生成方法与应用于对偶线的切割面方法不谋而合。此外，我们还注意到，根据我们是保留还是从内存中摒弃先前生成的列或约束条件，有几种变体。

For a problem consisting of a number of subproblems linked by coupling constraints, the delayed column generation method applied to a suitably reformulated problem, results in the Dantzig-Wolfe decomposition method. Loosely speaking, Benders decomposition is the “dual” of DantzigWolfe decomposition, and is based on delayed constraint generation. Stochastic programming is an important class of problems where Benders decomposition can be applied.
对于由耦合约束联系起来的若干子问题组成的问题，将延迟列生成方法应用于适当重新表述的问题，可以得到 Dantzig-Wolfe 分解法。宽泛地说，Benders 分解法是 Dantzig-Wolfe 分解法的 "对偶"，它以延迟约束生成为基础。随机程序设计是可以应用本德斯分解法的一类重要问题。

6.7 Exercises 6.7 练习

Exercise 6.1 Consider the cutting stock problem. Use an optimal solution to the linear programming problem (6.4) to construct a feasible solution for the corresponding integer programming problem, whose cost differs from the optimal cost by no more than

m

.
练习 6.1 考虑切割库存问题。使用线性规划问题 (6.4) 的最优解，为相应的整数规划问题构建一个可行解，其成本与最优成本的差异不超过

m

。

Exercise 6.2 This problem is a variation of the diet problem. There are

n

foods and

m

nutrients. We are given an

m \times n

matrix

A

, with

a_{i j}

specifying the amount of nutrient

i

per unit of the

j

th food. Consider a parent with two children. Let

b^{1}

and

b^{2}

be the minimal nutritional requirements of the two children, respectively. Finally, let

c

be the cost vector with the prices of the different foods. Assume that

a_{i j} \geq 0

and

c_{i} > 0

for all

i

and

j

.
练习 6.2 这个问题是饮食问题的一个变式。有

n

种食物和

m

种营养素。给我们一个

m \times n

矩阵

A

，其中

a_{i j}

指定了每单位

j

食物中营养素

i

的含量。考虑有两个孩子的父母。设

b^{1}

和

b^{2}

分别为两个孩子的最低营养需求量。最后，让

c

成为包含不同食物价格的成本向量。假设

a_{i j} \geq 0

和

c_{i} > 0

适用于所有

i

和

j

。

The parent has to buy food to satisfy the children’s needs, at minimum cost. To avoid jealousy, there is the additional constraint that the amount to be spent for each child is the same.
父母必须以最低的成本购买食物来满足孩子们的需求。为了避免嫉妒，还有一个额外的约束条件，即每个孩子的花费相同。
(a) Provide a standard form formulation of this problem. What are the dimensions of the constraint matrix?
(a) 提供该问题的标准形式表述。约束矩阵的维数是多少？
(b) If the Dantzig-Wolfe method is used to solve the problem in part (a), construct the subproblems solved during a typical iteration of the master problem.
(b) 如果使用 Dantzig-Wolfe 方法来解决 (a) 部分中的问题，请构建主问题典型迭代过程中解决的子问题。
© Suggest a direct approach for solving this problem based on the solution of two single-child diet problems.
在解决两个独生子女饮食问题的基础上，提出解决这一问题的直接方法。

Exercise 6.3 Consider the following linear programming problem:
练习 6.3 考虑下面的线性规划问题：

We wish to solve this problem using Dantzig-Wolfe decomposition, where the constraint

x_{11} + x_{23} \leq 15

is the only “coupling” constraint and the remaining constraints define a single subproblem.
我们希望使用 Dantzig-Wolfe 分解法来解决这个问题，其中

x_{11} + x_{23} \leq 15

约束是唯一的 "耦合 "约束，其余约束定义了一个子问题。
(a) Consider the following two feasible solutions for the subproblem:
(a) 考虑子问题的以下两个可行解：

x^{1} = (x_{11}, x_{12}, x_{13}, x_{21}, x_{22}, x_{23}) = (20, 0, 0, 0, 10, 10)

and 和

x^{2} = (x_{11}, x_{12}, x_{13}, x_{21}, x_{22}, x_{23}) = (0, 10, 10, 20, 0, 0)

Construct a restricted master problem in which

x

is constrained to be a convex combination of

x^{1}

and

x^{2}

. Find the optimal solution and the optimal simplex multipliers for the restricted master problem.
构建一个受限主问题，其中

x

受限为

x^{1}

和

x^{2}

的凸组合。求限制性主问题的最优解和最优单倍乘数。
(b) Using the simplex multipliers calculated in part (a), formulate the subproblem and solve it by inspection.
(b) 利用在第(a)部分中计算出的单倍乘数，提出子问题并通过检验求解。
© What is the reduced cost of the variable

λ_{i}

associated with the optimal extreme point

x^{i}

obtained from the subproblem solved in part (b)?
(b)部分求解的子问题得到的最佳极值点

x^{i}

6.8 Notes and sources 6.8 说明和资料来源

6.2. The delayed column generation approach to the cutting stock problem was put forth by Gilmore and Gomory (1961, 1963).
6.2.Gilmore 和 Gomory（1961 年，1963 年）提出了切削库存问题的延迟柱生成方法。
6.3. Cutting plane methods are often employed in linear programming approaches to integer programming problems, and will be discussed
6.3.切分面方法通常用于线性规划中的整数规划问题，下面将对其进行讨论
in Section 11.1. The same idea can also be applied to more general convex optimization problems; see, e.g., Bertsekas (1995b).
见第 11.1 节。同样的思路也可应用于更一般的凸优化问题；参见 Bertsekas (1995b)。
6.4. Dantzig-Wolfe decomposition was developed by Dantzig and Wolfe (1960). Example 6.2 is adapted from Bradley, Hax, and Magnanti (1977).
6.4.Dantzig-Wolfe 分解法由 Dantzig 和 Wolfe (1960) 提出。例 6.2 改编自 Bradley、Hax 和 Magnanti (1977)。
6.5. Stochastic programming began with work by Dantzig in the 1950 's and has been extensively studied since then. Some books on this subject are Kall and Wallace (1994), and Infanger (1993); Example 6.5 is adapted from the latter reference. The Benders decomposition method was developed by Benders (1962). It finds applications in other contexts as well, such as discrete optimization; see, e.g., Schrijver (1986), and Nemhauser and Wolsey (1988).
6.5.随机程序设计始于 20 世纪 50 年代 Dantzig 的研究，此后得到了广泛的研究。有关这方面的书籍有 Kall and Wallace (1994) 和 Infanger (1993)；例 6.5 改编自后者的参考文献。本德斯分解法由本德斯（1962 年）提出。该方法还可应用于其他领域，如离散优化；参见 Schrijver (1986) 和 Nemhauser and Wolsey (1988)。

Chapter 7 第 7 章

Network flow problems 网络流量问题

Contents 目录

7.1. Graphs 7.1.图表

7.2. Formulation of the network flow problem
7.2.网络流量问题的表述
7.3. The network simplex algorithm
7.3.网络单纯形算法
7.4. The negative cost cycle algorithm
7.4.负成本循环算法
7.5. The maximum flow problem
7.5.最大流量问题
7.6. Duality in network flow problems
7.6.网络流问题中的对偶性
7.7. Dual ascent methods*
7.7.双上升法*
7.8. The assignment problem and the auction algorithm
7.8.分配问题和拍卖算法
7.9. The shortest path problem
7.9.最短路径问题
7.10. The minimum spanning tree problem
7.10.最小生成树问题
7.11. Summary 7.11.摘要
7.12. Exercises 7.12.练习
7.13. Notes and sources 7.13.说明和资料来源

Network flow problems (also known as transshipment problems) are the most frequently solved linear programming problems. They include as special cases, the assignment, transportation, maximum flow, and shortest path problems, and they arise naturally in the analysis and design of communication, transportation, and logistics networks, as well as in many other contexts.
网络流动问题（也称转运问题）是最常解决的线性规划问题。它们包括分配问题、运输问题、最大流量问题和最短路径问题等特例，自然出现在通信、运输和物流网络的分析和设计以及许多其他场合。

The network flow problem is a special case of linear programming, and any algorithm for linear programming can be directly applied. On the other hand, network flow problems have a special structure which results in substantial simplification of general methods (e.g., of the simplex method), as well as in new, special purpose, methods.
网络流问题是线性规划的一个特例，任何线性规划算法都可以直接应用。另一方面，网络流量问题具有特殊的结构，这导致一般方法（如单纯形法）的大量简化，以及新的特殊目的方法的产生。

From a high level point of view, most of the available algorithms for network flow problems fall into one of three categories:
从高层次的角度来看，现有的大多数网络流量问题算法可分为三类：
(a) Primal methods. These methods maintain and keep improving a primal feasible solution. The primal simplex method, presented in Section 7.3, is an important representative. An alternative algorithm is derived from first principles in Section 7.4.
(a) 原始方法。这些方法保持并不断改进原始可行解。第 7.3 节中介绍的原始单纯形法就是一个重要的代表。在第 7.4 节中，我们将根据第一原理推导出另一种算法。
(b) Dual ascent methods. These methods, which are discussed in Section 7.7, maintain a dual feasible solution and an auxiliary primal (usually infeasible) solution that satisfy complementary slackness. The dual variables are updated so as to increase the value of the dual objective and reduce the infeasibility of the complementary primal solution. The Hungarian, primal-dual, relaxation, and dual simplex methods fall in this general category.
(b) 对偶上升法。这些方法将在第 7.7 节中讨论，它们维持一个对偶可行解和一个满足互补松弛性的辅助初等解（通常为不可行解）。对偶变量的更新是为了增加对偶目标值，减少互补初等解的不可行性。匈牙利法、初等-对偶法、松弛法和对偶单纯形法都属于这一类。
© Approximate dual ascent methods. These methods are similar in spirit to the dual ascent methods, except that small decreases in the dual objective are allowed to occur and the complementary slackness conditions are only approximately enforced. The auction algorithm, which is discussed in Section 7.8, as well as the

ϵ

-relaxation and preflow-push methods, are of this type.
近似双上升法。这些方法在精神上与对偶上升法相似，只是允许对偶目标出现微小的下降，并且只近似地执行互补松弛条件。第 7.8 节中讨论的拍卖算法以及

ϵ

松弛法和预流推动法都属于这种类型。

In this chapter, all three of the above mentioned algorithm types will be encountered. The chapter begins with a brief introduction to graphs (Section 7.1), that provides us with the language for studying network flow problems, and with a problem formulation (Section 7.2). We develop a number of general methods, but we also pay attention to special cases whose structure can be further exploited, such as the maximum flow problem (Section 7.5), the assignment problem (Section 7.8), and the shortest path problem (Section 7.9). We also discuss the minimum spanning tree problem (Section 7.10), which is not a network flow problem, but has a similar underlying graph structure. Throughout this chapter, our focus is on major algorithmic ideas, rather than on the refinements that can lead to better complexity estimates.
在本章中，我们将遇到上述所有三种算法类型。本章首先简要介绍了图（第 7.1 节），为我们提供了研究网络流量问题的语言，以及问题的表述（第 7.2 节）。我们开发了一些通用方法，但也关注了其结构可进一步利用的特殊情况，如最大流量问题（第 7.5 节）、赋值问题（第 7.8 节）和最短路径问题（第 7.9 节）。我们还讨论了最小生成树问题（第 7.10 节），它不是一个网络流量问题，但具有类似的底层图结构。在本章中，我们的重点是主要算法思想，而不是能带来更好复杂度估计的改进。

7.1 Graphs 7.1 图表

Network flow problems are defined on graphs. In this section, we introduce graphs formally and provide a number of elementary definitions and properties.
网络流问题是在图上定义的。在本节中，我们将正式介绍图，并提供一些基本定义和属性。

Undirected graphs 无向图

An undirected graph

G = (N, E)

consists of a set

N

of nodes and a set

E

of (undirected) arcs or edges, where an edge

e

is an unordered pair of distinct nodes, that is, a two-element subset

{i, j}

N

; see Figure 7.1. Note that
无向图

G = (N, E)

由节点集

N

和（无向）弧或边集

E

组成，其中边

e

是不同节点的无序对，即

N

的双元素子集

{i, j}

；见图 7.1。请注意

Figure 7.1: An undirected graph

G = (N, E)

with

N =

{1, 2, 3, 4, 5}

and

E = {{1, 2}, {1, 3}, {2, 3}, {1, 4}, {3, 4}, {3, 5}}

.
图 7.1：带有

N =

{1, 2, 3, 4, 5}

和

E = {{1, 2}, {1, 3}, {2, 3}, {1, 4}, {3, 4}, {3, 5}}

的无向图

G = (N, E)

。
an undirected arc

{i, j}

is one and the same object as the undirected arc

{j, i}

. Furthermore, “self-arcs” like

{i, i}

are not allowed. We say that the arc

{i, j}

is incident to nodes

i

and

j

, and these nodes are called the endpoints of the arc.
无向弧

{i, j}

与无向弧

{j, i}

是同一个对象。此外，像

{i, i}

这样的 "自弧 "是不允许的。我们说弧

{i, j}

与节点

i

和

j

相连，这些节点称为弧的端点。

The degree of a node in an undirected graph is the number of arcs incident to that node. The degree of an undirected graph is defined as the maximum of the degrees of its nodes.
无向图中节点的度数是该节点所连弧线的数目。无向图的度定义为节点度的最大值。

A walk from node

i_{1}

to node

i_{t}

in an undirected graph is defined as a finite sequence of nodes

i_{1}, i_{2}, \dots, i_{t}

such that

{i_{k}, i_{k + 1}} \in E, k =

1, 2, \dots, t - 1

. A walk is called a path if it has no repeated nodes. A cycle is defined as a walk

i_{1}, i_{2}, \dots, i_{t}

such that the nodes

i_{1}, \dots, i_{t - 1}

are distinct (and hence form a path) and

i_{t} = i_{1}

. In addition, we require the number

t - 1

of distinct nodes to be at least 3 . This is in order to exclude a walk of the form

i, j, i

, where the same arc

{i, j}

is traversed back and forth. An undirected graph is said to be connected if for every two distinct nodes

i, j \in N

, there exists a path from

i

j

.
在无向图中，从节点

i_{1}

到节点

i_{t}

的行走定义为节点

i_{1}, i_{2}, \dots, i_{t}

的有限序列，使得

{i_{k}, i_{k + 1}} \in E, k =

1, 2, \dots, t - 1

。如果行走没有重复节点，则称为路径。循环的定义是：当节点

i_{1}, \dots, i_{t - 1}

和

i_{t} = i_{1}

是不同的（因此构成一条路径）时，

i_{1}, i_{2}, \dots, i_{t}

就是一条行走路径。此外，我们要求不同节点的数量

t - 1

至少为 3。这是为了排除

i, j, i

这种形式的行走，在这种行走中，相同的弧

{i, j}

被来回穿越。如果每两个不同的节点

i, j \in N

都存在一条从

i

到

j

的路径，则称该无向图为连通图。

As an example, the graph in Figure 7.1 is connected. The sequence

1, 2, 3, 1, 4

is a walk but not a path. The sequence

1, 2, 3, 1

is a cycle, and the sequence

1, 3, 5

is a path.
例如，图 7.1 中的图形是连通的。序列

1, 2, 3, 1, 4

是行走，但不是路径。序列

1, 2, 3, 1

是一个循环，序列

1, 3, 5

是一条路径。

For undirected graphs, we will often denote the number of nodes by

| N |

n

, and the number of edges by

| E |

m

.
对于无向图，我们通常用

| N |

或

n

表示节点数，用

| E |

或

m

表示边数。

Directed graphs 有向图

A directed graph

G = (N, A)

consists of a set

N

of nodes and a set

A

of (directed) arcs, where a directed arc is an ordered pair (

i, j

) of distinct nodes; see Figure 7.2. Our definition allows for both

(i, j)

and

(j, i)

to be
有向图

G = (N, A)

由一组节点

N

和一组（有向）弧

A

组成，其中有向弧是不同节点的有序对 (

i, j

)；见图 7.2。我们的定义允许

(i, j)

和

(j, i)

都是

Figure 7.2: A directed graph

G = (N, A)

with

N = {1, 2, 3, 4, 5}

图 7.2：带有

N = {1, 2, 3, 4, 5}

的有向图

G = (N, A)

and

A = {(1, 2), (2, 1), (1, 3), (3, 2), (1, 4), (4, 3), (3, 5)}

. 和

A = {(1, 2), (2, 1), (1, 3), (3, 2), (1, 4), (4, 3), (3, 5)}

。
elements of the arc set

A

, but self-arcs like

(i, i)

are not allowed.
弧集

A

中的元素，但不允许

(i, i)

这样的自弧。
For any arc

(i, j)

, we say that

i

is the start node and

j

is the end node. The arc

(i, j)

is said to be outgoing from node

i

, incoming to node

j

, and incident to both

i

and

j

. We define

I (i)

and

O (i)

as the set of start nodes (respectively, end nodes) of arcs that are incoming to (respectively, outgoing from) node

i

. That is,
对于任何弧

(i, j)

，我们说

i

是起点节点，而

j

是终点节点。我们说弧

(i, j)

从节点

i

出发，进入节点

j

，并同时与

i

和

j

相连。我们将

I (i)

和

O (i)

定义为进入（分别从）节点

i

的弧的起点节点（分别为终点节点）的集合。也就是说

I (i) = {j \in N ∣ (j, i) \in A}

and 和

O (i) = {j \in N ∣ (i, j) \in A} .

Starting from a directed graph, we can construct a corresponding undirected graph by ignoring the direction of the arcs and by deleting repeated arcs; for example, the directed graph in Figure 7.2 leads to the undirected graph in Figure 7.1. Under one possible interpretation, flow or movement in a directed arc is permitted only from the start node to the end node, whereas in an undirected arc, flow or movement is permitted in both directions. We say that a directed graph is connected if the resulting undirected graph is connected.
从有向图开始，我们可以通过忽略弧的方向和删除重复弧来构建相应的无向图；例如，图 7.2 中的有向图可以导出图 7.1 中的无向图。根据一种可能的解释，有向弧只允许从起点节点向终点节点流动或移动，而在无向弧中，两个方向都允许流动或移动。如果得到的无向图是连通的，我们就说有向图是连通的。

We now present a definition of walks in directed graphs; it is important to note that this definition allows us to traverse an arc in either direction, irrespective of the arc’s direction. More specifically, a walk is
我们现在介绍有向图中行走的定义；需要注意的是，这个定义允许我们沿任一方向遍历弧，而与弧的方向无关。更具体地说，行走就是
defined as a sequence

i_{1}, \dots, i_{t}

of nodes, together with an associated sequence

a_{1}, \dots, a_{t - 1}

of arcs such that for

k = 1, \dots, t - 1

, we have either

a_{k} = (i_{k}, i_{k + 1})

(in which case we say that

a_{k}

is a forward arc) or

a_{k} = (i_{k + 1}, i_{k})

(in which case we say that

a_{k}

is a backward arc). Note that if

i_{k}

and

i_{k + 1}

are consecutive nodes in a walk and if

(i_{k}, i_{k + 1})

and

(i_{k + 1}, i_{k})

are both arcs of the underlying directed graph, then either arc can be used in the walk. The reason for including the arcs

a_{k}

in the definition of a walk is precisely to avoid such ambiguities.
定义为一个节点序列

i_{1}, \dots, i_{t}

，以及一个相关的弧序列

a_{1}, \dots, a_{t - 1}

，对于

k = 1, \dots, t - 1

，我们要么有

a_{k} = (i_{k}, i_{k + 1})

（在这种情况下，我们说

a_{k}

是一个向前的弧），要么有

a_{k} = (i_{k + 1}, i_{k})

（在这种情况下，我们说

a_{k}

是一个向后的弧）。请注意，如果

i_{k}

和

i_{k + 1}

是行走中的连续节点，如果

(i_{k}, i_{k + 1})

和

(i_{k + 1}, i_{k})

都是底层有向图的弧，那么行走中可以使用任意一个弧。在行走的定义中包含弧

a_{k}

的原因正是为了避免这种歧义。

A walk is said to be a path if all of its nodes

i_{1}, \dots, i_{t}

are distinct, and a cycle if the nodes

i_{1}, \dots, i_{t - 1}

are distinct and

i_{t} = i_{1}

. Note that we allow a cycle to consist of only two distinct nodes (in contrast to our definition for the case of undirected graphs). Thus, a sequence

i, (i, j), j, (j, i), i

is a bona fide cycle. Finally, a walk, path, or cycle is said to be directed if it only contains forward arcs.
如果漫步的所有节点

i_{1}, \dots, i_{t}

都是不同的，则称该漫步为路径；如果节点

i_{1}, \dots, i_{t - 1}

和

i_{t} = i_{1}

都是不同的，则称该漫步为循环。请注意，我们允许循环只由两个不同的节点组成（这与我们对无向图的定义不同）。因此，序列

i, (i, j), j, (j, i), i

是一个真正的循环。最后，如果一个行走、路径或循环只包含向前的弧，那么这个行走、路径或循环就是有向的。

For the graph shown in Figure 7.2, the sequence 1, (1,3), 3, (3,2), 2,

(1, 2), 1, (1, 4), 4

is a walk, but not a directed walk, because ( 1,2 ) is a backward arc. The sequence

1, (1, 3), 3, (3, 2), 2, (2, 1), 1

is a directed cycle. The sequence

1, (1, 2), 2, (2, 1), 1

is also a directed cycle. The sequence

4, (4, 3), 3, (1, 3), 1, (1, 2), 2

is a path, but not a directed path, because

(1, 3)

is a backward arc.
对于图 7.2 所示的图形，序列 1, (1,3), 3, (3,2), 2,

(1, 2), 1, (1, 4), 4

是一个行走，但不是有向行走，因为 ( 1,2 ) 是一个向后的弧。序列

1, (1, 3), 3, (3, 2), 2, (2, 1), 1

是有向循环。序列

1, (1, 2), 2, (2, 1), 1

也是一个有向循环。序列

4, (4, 3), 3, (1, 3), 1, (1, 2), 2

是一条路径，但不是一条有向路径，因为

(1, 3)

是一条向后的弧。

For directed graphs, we will often denote the number of nodes by

| N |

n

, and the number of arcs by

| A |

m

.
对于有向图，我们通常用

| N |

或

n

表示节点数，用

| A |

或

m

表示弧数。

Trees 树木

An undirected graph

G = (N, E)

is called a tree if it is connected and has no cycles. If a node of a tree has degree equal to 1 , it is called a leaf. See Figure 7.3 for an illustration.
如果一个无向图

G = (N, E)

是连通的，并且没有循环，那么它就叫做树。如果树的节点度等于 1，则称为树叶。请参见图 7.3。

Figure 7.3: A tree with 8 nodes, 7 arcs, and 5 leaves. Note that if we were to add the arc

{2, 7}

, a single cycle would be created, namely, 2,3,5,7,2.
图 7.3：一棵有 8 个节点、7 条弧和 5 片叶的树。请注意，如果我们添加弧

{2, 7}

，就会产生一个循环，即 2,3,5,7,2。

We now present some important properties of trees that will be of use later on (e.g., in the development of the simplex method, in Section 7.3).
现在，我们将介绍树的一些重要特性，这些特性将在以后（例如，在第 7.3 节中开发单纯形法时）派上用场。

Theorem 7.1 定理 7.1

(a) Every tree with more than one node has at least one leaf.
(a) 每棵有一个以上节点的树至少有一片叶子。
(b) An undirected graph is a tree if and only if it is connected and has

| N | - 1

arcs.
(b) 当且仅当一个无向图是连通的且有

| N | - 1

个弧时，它是一棵树。
© For any two distinct nodes

i

and

j

in a tree, there exists a unique path from

i

j

.
对于树中任何两个不同的节点

i

和

j

，都存在一条从

i

到

j

的唯一路径。
(d) If we start with a tree and add a new arc, the resulting graph contains exactly one cycle (as long as we do not distinguish between cycles involving the same set of nodes).
(d) 如果我们从一棵树开始，并添加一条新弧，那么得到的图恰好包含一个循环（只要我们不区分涉及同一组节点的循环）。

Proof. 证明。

(a) Consider a tree with more than one node and suppose that there are no leaves. Then, every node has degree greater than 1. (If the degree of a node were 1 , that node would be a leaf, and if it were 0 , the graph would not be connected.) Therefore, given a node and an arc through which we enter the node, we can find a different arc through which we can exit. By repeating such a process, we must eventually visit the same node twice, which implies that there exists a cycle, contradicting the definition of a tree.
(a) 考虑一棵有多个节点的树，假设没有树叶。那么，每个节点的阶数都大于 1（如果节点的阶数为 1，则该节点是树叶；如果节点的阶数为 0，则该图不相连）。因此，给定一个节点和一条进入该节点的弧，我们就可以找到另一条可以离开该节点的弧。通过重复这样的过程，我们最终必须访问同一个节点两次，这意味着存在一个循环，这与树的定义相矛盾。
(b) We first prove that every tree has

| N | - 1

arcs. This is trivially true if the tree has a single node. Consider now a tree that has more than one node. Such a tree must have at least one leaf, by part (a). We delete that leaf together with the single arc incident to that node. The resulting graph is again a tree, because the deletion of a leaf cannot create a cycle or cause a graph to become disconnected. This process can be carried out

| N | - 1

times, until we are left with a single node and, therefore, no arcs. Since at each stage there was exactly one arc deletion, we conclude that the original tree had

| N | - 1

arcs.
(b) 我们首先证明每棵树都有

| N | - 1

个弧。如果这棵树只有一个节点，那么这一点显然是正确的。现在考虑一棵有多个节点的树。根据 (a) 部分，这样一棵树必须至少有一片叶子。我们删除该树叶以及与该节点相关的一条弧。这样得到的图又是一棵树，因为叶子的删除不会产生循环，也不会导致图断开。这个过程可以重复

| N | - 1

次，直到只剩下一个节点，因此也就没有弧。由于每个阶段都恰好删除了一个弧，因此我们可以得出结论：最初的树有

| N | - 1

个弧。
In order to prove the converse statement, let us consider a connected graph with

| N | - 1

arcs. If this graph contains a cycle, we can delete one of the arcs in the cycle and still maintain connectivity. We repeat this process as many times as needed, until we are left with a connected graph without any cycles, that is, a tree. We have already proved that a tree with

| N |

nodes must have

| N | - 1

arcs, and this shows that the final tree has as many arcs as the original graph. It follows that no arc was deleted and the original graph was a tree to start with.
为了证明相反的说法，让我们考虑一个具有

| N | - 1

个弧的连通图。如果该图包含一个循环，我们可以删除循环中的一条弧，但仍能保持连通性。我们可以根据需要多次重复这个过程，直到我们得到一个没有任何循环的连通图，也就是一棵树。我们已经证明，具有

| N |

节点的树一定有

| N | - 1

个弧，这表明最终树的弧数与原始图一样多。由此可见，没有弧被删除，原始图一开始就是一棵树。
© Suppose that there exist two different paths joining the same nodes

i

and

j

. By joining these two paths and by deleting any arcs that are
假设存在两条不同的路径，分别连接相同的节点

i

和

j

。将这两条路径连接起来，并删除其中的任何弧。

(a)

(b)

Figure 7.4: (a) An undirected graph. The thicker arcs form a spanning tree. (b) Another undirected graph. The arcs

{1, 2}

{2, 3}, {4, 6}

do not form any cycle. They can be augmented to form a spanning tree, e.g., by adding arcs

{3, 6}

and

{5, 6}

.
图 7.4： (a) 一个无向图。较粗的弧构成一棵生成树。 (b) 另一个无向图。弧

{1, 2}

、

{2, 3}, {4, 6}

不构成任何循环。可以通过添加弧

{3, 6}

和

{5, 6}

等方式对它们进行扩展，以形成生成树。
common to both, we are left with one or more cycles, contradicting the definition of a tree.
那么我们就只剩下一个或多个循环，这与树的定义相矛盾。
(d) Consider a tree, and let us add an undirected arc

{i, j}

. Using part (b), the resulting graph must have

| N |

arcs. Therefore, it cannot be a tree, and must have a cycle. Any cycle created by this addition consists of the arc

{i, j}

and a path from

i

j

. Since there exists a unique path from

i

j

[part ©], it follows that a unique cycle has been created.
(d) 考虑一棵树，让我们添加一条无向弧

{i, j}

。根据 (b) 部分，得到的图必须有

| N |

条弧。因此，它不可能是一棵树，而必须有一个循环。通过这种添加创建的任何循环都由弧

{i, j}

和一条从

i

到

j

的路径组成。由于存在一条从

i

到

j

的唯一路径 [©部分]，因此我们创建了一个唯一的循环。

Spanning trees 跨接树

Given a connected undirected graph

G = (N, E)

, let

E_{1}

be a subset of

E

such that

T = (N, E_{1})

is a tree. Such a tree is called a spanning tree. The following result will be used later on (in Sections 7.3 and 7.10) and is illustrated in Figure 7.4.
给定一个连通无向图

G = (N, E)

，设

E_{1}

是

E

的一个子集，使得

T = (N, E_{1})

是一棵树。这样的树称为生成树。下面的结果将在后面（第 7.3 节和第 7.10 节）使用，如图 7.4 所示。

Theorem 7.2 Let

G = (N, E)

be a connected undirected graph and let

E_{0}

be some subset of the set

E

of arcs. Suppose that the arcs in

E_{0}

do not form any cycles. Then, the set

E_{0}

can be augmented to a set

E_{1} \supset E_{0}

so that

(N, E_{1})

is a spanning tree.
定理 7.2 假设

G = (N, E)

是连通的无向图，假设

E_{0}

是弧集

E

的某个子集。假设

E_{0}

中的弧不构成任何循环。那么，可以将集合

E_{0}

扩展为集合

E_{1} \supset E_{0}

，从而使

(N, E_{1})

成为一棵生成树。

Proof. Let

G = (N, E)

be a connected undirected graph. Suppose that

E_{0} \subset E

, and that the arcs in

E_{0}

do not form any cycles. If

G

is a tree, we may let

E_{1} = E

and we are done. Otherwise,

G

contains at least one cycle. A cycle cannot consist exclusively of arcs in

E_{0}

, because of our assumption on

E_{0}

. Let us choose and delete an arc that lies on a cycle and that does
证明假设

G = (N, E)

是一个连通的无向图。假设

E_{0} \subset E

，并且

E_{0}

中的弧不构成任何循环。如果

G

是一棵树，我们可以让

E_{1} = E

这样做。否则，

G

至少包含一个循环。一个循环不可能完全由

E_{0}

中的弧组成，因为我们对

E_{0}

做了假设。让我们选择并删除一个位于循环上的弧，该弧应符合以下条件
not belong to

E_{0}

. The resulting graph is still connected. By repeating this process as many times as needed, we end up with a connected graph

(N, E_{1})

without any cycles, hence a tree. In addition, since the arcs in

E_{0}

are never deleted, we have

E_{0} \subset E_{1}

.
不属于

E_{0}

。这样得到的图仍然是连通的。通过多次重复这一过程，我们最终得到了一个没有任何循环的连通图

(N, E_{1})

，也就是一棵树。此外，由于

E_{0}

中的弧从未被删除，我们得到了

E_{0} \subset E_{1}

。

7.2 Formulation of the network flow problem
7.2 网络流量问题的提出

A network is a directed graph

G = (N, A)

together with some additional numerical information, such as numbers

b_{i}

representing the external supply to each node

i \in N

, nonnegative (possibly infinite) numbers

u_{i j}

representing the capacity of each

arc (i, j) \in A

, and numbers

c_{i j}

representing the cost per unit of flow along arc

(i, j)

.
网络是一个有向图

G = (N, A)

，以及一些附加的数字信息，例如代表每个节点

i \in N

外部供应的数字

b_{i}

、代表每个

arc (i, j) \in A

容量的非负数（可能是无限的）数字

u_{i j}

，以及代表弧

(i, j)

每单位流量成本的数字

c_{i j}

。

We visualize a network by thinking of some material that flows on each arc. We use

f_{i j}

to denote the amount of flow through arc

(i, j)

. The supply

b_{i}

is interpreted as the amount of flow that enters the network from the outside, at node

i

. In particular, node

i

is called a source if

b_{i} > 0

, and a sink if

b_{i} < 0

. If node

i

is a sink, the quantity

| b_{i} |

is sometimes called the demand at node

i

. We impose the following conditions on the flow variables

f_{i j}, (i, j) \in A

:
我们可以通过考虑在每个弧上流动的材料来直观地显示网络。我们用

f_{i j}

表示流经弧

(i, j)

的流量。供应量

b_{i}

被解释为从外部进入网络的流量，即节点

i

。其中，如果节点

b_{i} > 0

被称为源，如果

b_{i} < 0

被称为汇，则节点

i

被称为源。如果节点

i

是汇，则

| b_{i} |

的数量有时称为节点

i

的需求量。我们对流量变量

f_{i j}, (i, j) \in A

施加以下条件：

\begin{array}{ll} b_{i} + \sum_{j \in I (i)} f_{j i} = \sum_{j \in O (i)} f_{i j}, & \forall i \in N, \\ 0 \leq f_{i j} \leq u_{i j}, & \forall (i, j) \in A . \end{array}

Equation (7.1) is a flow conservation law: it states that the amount of flow into a node

i

must be equal to the total flow out of that node. Equation (7.2) simply requires that the flow through an arc must be nonnegative and cannot exceed the capacity of the arc. Any vector with components

f_{i j}

(i, j) \in A

, will be called a flow. If it also satisfies the constraints (7.1)-(7.2), it will be called a feasible flow.
等式 (7.1) 是流量守恒定律：它规定流入节点

i

的流量必须等于流出该节点的总流量。等式 (7.2) 简单地要求通过弧的流量必须是非负值，并且不能超过弧的容量。任何包含分量

f_{i j}

、

(i, j) \in A

的向量都称为流量。如果它也满足 (7.1)-(7.2) 约束条件，则称为可行流。

By summing both sides of Eq. (7.1) over all

i \in N

, we obtain
通过对所有

i \in N

公式 (7.1) 两边求和，我们得到

\sum_{i \in N} b_{i} = 0

which means that the total flow from the environment into the network (at the sources) must be equal to the total flow from the network (at the sinks) to the environment. From now on, we will always assume that the condition

\sum_{i \in N} b_{i} = 0

holds, because otherwise no flow vector could satisfy the flow conservation constraints, and we would have an infeasible problem.
这意味着从环境（源）流入网络的总流量必须等于从网络（汇）流向环境的总流量。从现在起，我们将始终假设

\sum_{i \in N} b_{i} = 0

条件成立，否则，任何流量矢量都无法满足流量守恒约束条件，我们就会遇到一个不可行的问题。

The general minimum cost network flow problem deals with the minimization of a linear cost function of the form
一般的最小成本网络流量问题涉及到最小化线性成本函数，其形式为

\sum_{(i, j) \in A} c_{i j} f_{i j}

over all feasible flows. We observe that this is a linear programming problem. If

u_{i j} = \infty

for all

(i, j) \in A

, we say that the problem is uncapacitated; otherwise, we say that it is capacitated. Note that in the uncapacitated case, we only have equality and nonnegativity constraints, and the problem is in standard form.
遍及所有可行的流量。我们注意到这是一个线性规划问题。如果

u_{i j} = \infty

适用于所有

(i, j) \in A

，我们就说这是一个无容量问题；否则，我们就说这是一个有容量问题。请注意，在无容量的情况下，我们只有相等和非负约束，而且问题是标准形式的。

We now provide an overview of important special cases of the network flow problem; most of them will be studied later in this chapter.
现在，我们对网络流问题的重要特例进行概述；本章稍后将对其中大部分特例进行研究。

The shortest path problem
最短路径问题

For any directed path in a network, we define its length as the sum of the costs of all arcs on the path. We wish to find a shortest path, that is, a directed path from a given origin node to a given destination node whose length is smallest. This problem is studied in Section 7.9, where we show that it can be formulated as a network flow problem, under a certain assumption on the arc lengths.
对于网络中的任何有向路径，我们将其长度定义为路径上所有弧的成本之和。我们希望找到一条最短路径，即从给定起点节点到给定终点节点的长度最小的有向路径。我们将在第 7.9 节中研究这个问题，我们将在该节中说明，在对弧长有一定假设的情况下，这个问题可以表述为网络流问题。

The maximum flow problem 最大流量问题

In the maximum flow problem, we wish to determine the largest possible amount of flow that can be sent from a given source node to a given sink node, without exceeding the arc capacities. This problem is studied in Section 7.5.
在最大流量问题中，我们希望确定在不超过弧容量的情况下，从给定源节点发送到给定汇节点的最大流量。第 7.5 节将研究这一问题。

The transportation problem
交通问题

Let there be

m

suppliers and

n

consumers. The

i

th supplier can provide

s_{i}

units of a certain good and the

j

th consumer has a demand for

d_{j}

units. We assume that the total supply

\sum_{i = 1}^{m} s_{i}

is equal to the total demand

\sum_{j = 1}^{n} d_{j}

. Finally, we assume that the transportation of goods from the

i

th supplier to the

j

th consumer carries a cost of

c_{i j}

per unit of goods transported. The problem is to transport the goods from the suppliers to the consumers at minimum cost. Let

f_{i j}

be the amount of goods transported from the

i

th supplier to the

j

th consumer. We then have the following problem:
假设有

m

个供应商和

n

个消费者。第

i

个供应商可以提供

s_{i}

件某种商品，第

j

个消费者对

d_{j}

件商品有需求。我们假设总供给

\sum_{i = 1}^{m} s_{i}

等于总需求

\sum_{j = 1}^{n} d_{j}

。最后，我们假设从第

i

个供应商向第

j

个消费者运输货物的单位成本为

c_{i j}

。问题是如何以最低成本将货物从供应商运到消费者手中。设

f_{i j}

为从第

i

个供应商向第

j

个消费者运输的货物数量。我们就会遇到以下问题：

\begin{array}{lll} minimize & \sum_{i = 1}^{m} \sum_{j = 1}^{n} c_{i j} f_{i j} \\ subject to & \sum_{i = 1}^{m} f_{i j} = d_{j}, & j = 1, \dots, n, \\ \sum_{j = 1}^{n} f_{i j} = s_{i}, & i = 1, \dots, m \\ f_{i j} \geq 0, & \forall i, j . \end{array}

The first equality constraint specifies that the demand

d_{j}

of each consumer must be met; the second equality constraint requires that the entire supply

s_{i}

of each supplier must be shipped. This is a special case of the uncapacitated network flow problem, where the underlying graph has a special structure; see Figure 7.5. It turns out that every network flow problem can
第一个相等约束规定必须满足每个消费者的需求

d_{j}

；第二个相等约束要求必须装运每个供应商的全部供应

s_{i}

。这是无容限网络流动问题的一个特例，其底层图具有特殊结构；见图 7.5。事实证明，每个网络流动问题都可以

Figure 7.5: A network corresponding to a transportation problem with three suppliers and two consumers.
图 7.5：与三个供应商和两个消费者的运输问题相对应的网络。
be transformed into an equivalent transportation problem (Exercises 7.5 and 7.6). Consequently, any algorithm for the transportation problem can be adapted and can be used to solve general network flow problems. For this reason, the initial development and testing of new algorithms is often carried out for the special case of transportation problems.
可以转化为等价的运输问题（练习 7.5 和 7.6）。因此，运输问题的任何算法都可以进行调整，并可用于解决一般的网络流问题。因此，新算法的初步开发和测试通常是针对运输问题的特殊情况进行的。

The assignment problem 分配问题

The assignment problem is a special case of the transportation problem, where the number of suppliers is equal to the number of consumers, each supplier has unit supply, and each consumer has unit demand. As will be proved later in this chapter, one can always find an optimal solution in which every

f_{i j}

is either 0 or 1 . This means that for each

i

there will be a unique and distinct

j

for which

f_{i j} = 1

, and we can say that the

i

th supplier is assigned to the

j

th consumer; this justifies the name of this problem.
分配问题是运输问题的一个特例，其中供应商的数量等于消费者的数量，每个供应商都有单位供给，每个消费者都有单位需求。正如本章后面将要证明的，我们总能找到一个最优解，其中每个

f_{i j}

要么为 0，要么为 1。这意味着，对于每个

i

来说，都会有一个唯一且独特的

j

，而对于

f_{i j} = 1

来说，我们可以说，第

i

个供应商被分配给了第

j

个消费者；这也是这个问题名称的由来。

Variants of the network flow problem
网络流量问题的变体

There are several variants of the network flow problem all of which can be shown to be equivalent to each other. For example, we have already mentioned that every network flow problem is equivalent to a transportation problem. We now discuss some more examples.
网络流问题有多种变体，所有这些变体都可以证明彼此等价。例如，我们已经提到，每个网络流量问题都等价于运输问题。现在我们再讨论一些例子。
(a) Every network flow problem can be reduced to one with exactly one source and exactly one sink node. This is illustrated in Figure 7.6.
(a) 每个网络流问题都可以简化为一个源节点和一个汇节点的问题。如图 7.6 所示。

Figure 7.6: (a) A network with three source nodes. (b) A network with only one source node. The costs of the new arcs are zero. Because of the way that the arc capacities

u_{0 i}

are chosen (

u_{0 i} = b_{i}

i = 1, 2, 3

), exactly

b_{i}

units must flow on each arc (

0, i), i = 1, 2, 3

. The reduction to a network with a single sink node is similar.
图 7.6： (a) 有三个源节点的网络。(b) 只有一个源节点的网络。新弧线的成本为零。由于弧容量

u_{0 i}

的选择方式（

u_{0 i} = b_{i}

i = 1, 2, 3

），每条弧上必须有

b_{i}

个单位的流量（

0, i), i = 1, 2, 3

。类似的情况也可以简化为只有一个汇节点的网络。
(b) Every network flow problem can be reduced to one without sources or sinks. (Problems in which all of the supplies are zero are called circulation problems.) Consider, without loss of generality, a network with a single source

s

and a single sink

t

. We introduce a new

arc (t, s)

whose capacity

u_{t s}

is equal to

b_{s}

and whose unit cost is

c_{t s} = - M

, where

M

is a large number; see Figure 7.7. Since

M

is large, an optimal solution to the circulation problem will try to set

f_{t s}

b_{s}

, which has the same effect as having a supply of

b_{s}

at node

s

. If an optimal solution to the circulation problem does not succeed in setting

f_{t s}

b_{s}

, this means that there is no way of shipping

b_{s}

units of flow from

s

t

, and the original problem is infeasible.
(b) 每个网络流动问题都可以简化为一个没有源或汇的问题。(所有供应均为零的问题称为流通问题）。在不失一般性的前提下，考虑一个具有单一源

s

和单一汇

t

的网络。我们引入一个新的

arc (t, s)

，其容量

u_{t s}

等于

b_{s}

，单位成本为

c_{t s} = - M

，其中

M

是一个大数；见图 7.7。由于

M

较大，流通问题的最优解将尝试将

f_{t s}

设为

b_{s}

，这与节点

s

的供应量为

b_{s}

的效果相同。如果流通问题的最优解不能成功地将

f_{t s}

设置为

b_{s}

，这就意味着无法将

b_{s}

单位流量从

s

运输到

t

，原始问题不可行。
© Node capacities. Suppose that we have an upper bound of

g_{i}

on the total flow that can enter a given node

i

; for example, if

i

is a source
节点容量。假设我们对可进入给定节点

i

的总流量设定了

g_{i}

的上限；例如，如果

i

是一个源节点，那么

i

的流量上限为

g_{i}

。

Figure 7.7: (a) A network. (b) An equivalent circulation problem.
图 7.7： (a) 一个网络。(b) 等效循环问题。
node, we may have a constraint
节点，我们可能有一个约束条件

b_{i} + \sum_{j \in I (i)} f_{j i} \leq g_{i}

By splitting node

i

into two nodes

i

and

i^{'}

, and by letting

g_{i}

be the capacity of

arc (i, i^{'})

, we are back to the case where we only have arc capacities; see Figure 7.8.
将节点

i

拆分为两个节点

i

和

i^{'}

，并让

g_{i}

成为

arc (i, i^{'})

的容量，我们就回到了只有弧容量的情况；见图 7.8。

Figure 7.8: Transformation of a node capacity into an arc capacity.
图 7.8：将节点容量转换为弧容量。
(d) Lower bounds on the arc flows. Suppose that we add constraints of the form

f_{i j} \geq d_{i j}

, where

d_{i j}

are given scalars. The resulting problem can be reduced to an equivalent problem in which every

d_{i j}

is equal to zero. Exercise 7.7 provides some guidance as to how this can be accomplished.
(d) 弧流的下限。假设我们添加了

f_{i j} \geq d_{i j}

形式的约束条件，其中

d_{i j}

是给定的标量。由此产生的问题可以简化为每个

d_{i j}

都等于零的等价问题。练习 7.7 为如何实现这一目标提供了一些指导。

A concise formulation 简明表述

We now discuss how to rewrite the network flow problem, and especially the flow conservation constraint, in more economical matrix-vector notation. We assume that

N = {1, \dots, n}

and we let

m

be the number of arcs. Let us fix a particular ordering of the arcs, and let

f

be the vector of flows that results when the components

f_{i j}

are ordered accordingly. We define the node-arc incidence matrix

A

as follows: its dimensions are

n \times m

(each row corresponds to a node and each column to an arc) and its (

i, k

)th entry

a_{i k}

is associated with the

i

th node and the

k

th arc. We let
现在我们讨论如何用更经济的矩阵向量符号重写网络流量问题，尤其是流量守恒约束。我们假设

N = {1, \dots, n}

，并让

m

为弧的数量。让我们对弧线进行特定排序，并让

f

成为流量向量，当分量

f_{i j}

相应排序时，流量向量就会产生。我们定义节点-弧入射矩阵

A

如下：其维数为

n \times m

（每行对应一个节点，每列对应一个弧），其 (

i, k

)条目

a_{i k}

与第

i

个节点和第

k

个弧相关联。我们让

a_{i k} = {\begin{aligned} 1, & if i is the start node of the k th arc, \\ - 1, & if i is the end node of the k th arc \\ 0, & otherwise. \end{aligned}

Thus, every column of

A

has exactly two nonzero entries, one equal to +1 , and one equal to -1 , indicating the start and the end node of the corresponding arc.
因此，

A

的每一列都有两个非零条目，一个等于 +1 ，一个等于 -1 ，表示相应弧的起点和终点节点。

Example 7.1 Consider the directed graph of Figure 7.2 and let us use the following ordering of the arcs:

(1, 2), (2, 1), (3, 2), (4, 3), (1, 4), (1, 3), (3, 5)

. The corresponding node-arc incidence matrix is
例 7.1 考虑图 7.2 中的有向图，弧的顺序如下：

(1, 2), (2, 1), (3, 2), (4, 3), (1, 4), (1, 3), (3, 5)

。相应的节点-弧入射矩阵为

A = [\begin{array}{rrrrrrr} 1 & - 1 & 0 & 0 & 1 & 1 & 0 \\ - 1 & 1 & - 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & - 1 & 0 & - 1 & 1 \\ 0 & 0 & 0 & 1 & - 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & - 1 \end{array}]

Let us now focus on the

i

th row of

A

, denoted by

a_{i}^{'}

(this is the row associated with node

i

). Nonzero entries indicate the arcs that are incident to node

i

; such entries are +1 or -1 depending on whether the arc is outgoing or incoming, respectively. Thus,
现在，让我们关注

A

的

i

第三行，用

a_{i}^{'}

表示（这是与节点

i

相关的一行）。非零条目表示与节点

i

相关的弧线；根据弧线是传出还是传入，这些条目分别为 +1或 -1。因此

a_{i}^{'} f = \sum_{j \in O (i)} f_{i j} - \sum_{j \in I (i)} f_{j i}

and the flow conservation constraint at node

i

[cf. Eq. (7.1)] can be written as
节点

i

处的流量守恒约束 [参见公式 (7.1)]可写成

a_{i}^{'} f = b_{i}

or, in matrix notation, 或用矩阵符号表示

A f = b

where

b

is the vector

(b_{1}, \dots, b_{n})

.
其中，

b

是向量

(b_{1}, \dots, b_{n})

。
We observe that the sum of the rows of

A

is equal to the zero vector; in particular, the rows of

A

are linearly dependent. Thus, the matrix A violates one of the basic assumptions underlying our development of the
我们注意到，

A

行的总和等于零向量；特别是，

A

行是线性相关的。因此，矩阵 A 违反了我们建立
simplex method. As discussed in Chapter 2 (cf. Theorem 2.5 in Section 2.3), either the problem is infeasible or we can remove some of the equality constraints, without affecting the feasible set, so that the remaining constraints are linearly independent. We revisit this issue in the next section.
单纯形法正如第 2 章所讨论的（参见第 2.3 节中的定理 2.5），要么问题不可行，要么我们可以在不影响可行集的情况下删除部分相等约束，从而使剩余的约束线性独立。我们将在下一节重新讨论这个问题。

Circulations 流通

We close by introducing some elementary concepts that are central to many network flow algorithms.
最后，我们将介绍一些基本概念，它们是许多网络流算法的核心。

Any flow vector

f

(feasible or infeasible) that satisfies
任何流量矢量

f

（可行或不可行），只要满足

A f = 0

is called a circulation. Intuitively, we have flow conservation within the network and zero external supply or demand, which means that the flow “circulates” inside the network.
称为循环。直观地说，我们的网络内部流量保持不变，外部供求为零，这意味着流量在网络内部 "循环"。

Let us now consider a cycle

C

. We let

F

and

B

be the set of forward and backward arcs of the cycle, respectively. The flow vector

h^{C}

with components
现在让我们考虑一个循环

C

。我们设

F

和

B

分别为循环的前弧和后弧集合。流量向量

h^{C}

的分量为

h_{i j}^{C} = {\begin{aligned} 1, & if (i, j) \in F \\ - 1, & if (i, j) \in B \\ 0, & otherwise \end{aligned}

is called the simple circulation associated with the cycle

C

. It is easily seen that

h^{C}

satisfies
称为与循环

C

7.3 The network simplex algorithm
7.3 网络单纯形算法

In this section, we develop the details of the simplex method, as applied to the uncapacitated network flow problem
在本节中，我们将详细介绍应用于无容限网络流量问题的单纯形法

\begin{aligned} minimize & c^{'} f \\ subject to & A f = b \\ f \geq 0 \end{aligned}

Figure 7.9: A cycle and the corresponding simple circulation. Arcs

(4, 3)

and

(1, 5)

are backward arcs and carry a flow of -1 . Note that flow is conserved at each node.
图 7.9：一个循环和相应的简单循环。弧

(4, 3)

和

(1, 5)

是后向弧，流量为 -1 。请注意，每个节点上的流量都是守恒的。
where

A

is the node-arc incidence matrix of a directed graph

G = (N, A)

. (Capacitated problems are briefly discussed at the end of this section.) The network simplex algorithm is widely used in practice, and is included in many commercial optimization codes, due to its simplicity and efficiency. In particular, it tends to run an order of magnitude faster than a general purpose simplex code applied to a network flow problem.
其中

A

是有向图

G = (N, A)

的节点-圆弧入射矩阵。(网络单纯形算法因其简单高效而在实践中得到广泛应用，并被纳入许多商业优化代码中。特别是，它的运行速度往往比应用于网络流问题的通用单纯形法代码快一个数量级。

Due to our restriction to uncapacitated problems, we are dealing with a linear programming problem in standard form. We let

m

and

n

be the number of arcs and nodes, respectively. We therefore have

m

flow variables and

n

equality constraints which, unfortunately, is the exact opposite of the notational conventions used in earlier chapters.
由于我们仅限于处理无容限问题，因此我们要处理的是标准形式的线性规划问题。我们假设

m

和

n

分别为弧和节点的数量。因此，我们有

m

流变量和

n

平等约束，不幸的是，这与前面章节中使用的符号习惯完全相反。

There are two different ways of developing the network simplex method. The first is to go through the mechanics of the general simplex method and specialize each step to the present context. The second is to develop the algorithm from first principles and then to point out that it is a special case of the simplex method. We take a middle ground that proceeds along two parallel tracks; each step is justified from first principles, but its relation to the simplex method is also explained. The end result is an algorithm with a fairly intuitive structure.
开发网络单纯形法有两种不同的方法。第一种是通过一般单纯形法的力学原理，并根据当前情况对每一步进行专门化。第二种是从第一原理出发来开发算法，然后指出它是单纯形法的一个特例。我们采取了中间路线，沿着两条平行的轨道前进；每一步都从第一原理出发，但也解释了它与单纯形法的关系。最终得出的算法具有相当直观的结构。

Throughout this section, the following assumption will be in effect.
在本节中，将采用以下假设。

Assumption 7.1 假设 7.1

(a) We have

\sum_{i \in N} b_{i} = 0

. (a) 我们有

\sum_{i \in N} b_{i} = 0

.
(b) The graph

G

is connected.
(b) 图形

G

是连通的。

Part (a) of this assumption is natural, because otherwise the problem is infeasible. Part (b) is also natural, because if the graph is not connected,
这一假设的(a)部分是自然的，因为否则问题就不可行。(b)部分也很自然，因为如果图形不相连、
then the problem can be decomposed into subproblems that can be treated independently.
那么问题就可以分解成可以独立处理的子问题。

As noted in Section 7.2, the rows of the matrix

A

sum to the zero vector and are therefore linearly dependent. In fact, the last constraint (flow conservation at node

n

) is a consequence of the flow conservation constraints at the other nodes, and can be omitted without affecting the feasible set. Let us define the truncated node-arc incidence matrix

\tilde{A}

to be the matrix of dimensions

(n - 1) \times m

, which consists of the first

n - 1

rows of the matrix

A

. Any column of

\tilde{A}

that corresponds to an arc of the form

(i, n)

has a single nonzero entry, equal to 1 , at the

i

th row. Similarly, any column of

\tilde{A}

that corresponds to an arc of the form

(n, i)

has a single nonzero entry, equal to -1 , at the

i

th row. All other columns of

\tilde{A}

have two nonzero entries. Let

\tilde{b} = (b_{1}, \dots, b_{n - 1})

. We replace the original equality constraint

A f = b

by the constraint

\tilde{A} f = \tilde{b}

. We will see shortly that under Assumption 7.1, the matrix

\tilde{A}

has linearly independent rows.
如第 7.2 节所述，矩阵

A

的各行和为零向量，因此是线性相关的。事实上，最后一个约束条件（节点

n

的流量保持）是其他节点流量保持约束条件的结果，可以省略而不影响可行集。让我们定义截断的节点-圆弧入射矩阵

\tilde{A}

为维数为

(n - 1) \times m

的矩阵，它由矩阵

A

的前

n - 1

行组成。与形式为

(i, n)

的弧相对应的

\tilde{A}

的任何一列在

i

第 1 行都有一个非零条目，等于 1。同样，

\tilde{A}

中的任何一列，如果对应于形式为

(n, i)

的弧，则在

i

第 1 行有一个非零条目，等于-1。

\tilde{A}

的所有其他列都有两个非零条目。让

\tilde{b} = (b_{1}, \dots, b_{n - 1})

.我们用约束

\tilde{A} f = \tilde{b}

代替原来的相等约束

A f = b

。我们很快就会看到，根据假设 7.1，矩阵

\tilde{A}

具有线性独立行。

Example 7.2 Consider the node-arc incidence matrix

A

in Example 7.1. The associated matrix

\tilde{A}

is given by
例 7.2 考虑例 7.1 中的节点-圆弧入射矩阵

A

。相关矩阵

\tilde{A}

由以下公式给出

\tilde{A} = [\begin{array}{rrrrrrr} 1 & - 1 & 0 & 0 & 1 & 1 & 0 \\ - 1 & 1 & - 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & - 1 & 0 & - 1 & 1 \\ 0 & 0 & 0 & 1 & - 1 & 0 & 0 \end{array}]

It can be verified that the matrix

\tilde{A}

has full rank. For example, the third, fourth, sixth, and seventh columns are linearly independent.
可以验证矩阵

\tilde{A}

具有全秩。例如，第三列、第四列、第六列和第七列是线性独立的。

Trees and basic feasible solutions
树和基本可行方案

We now introduce an important definition.
我们现在介绍一个重要的定义。

Definition 7.1 A flow vector f is called a tree solution if it can be constructed by the following procedure.
定义 7.1 如果一个流矢量 f 可以通过以下步骤构建，则称其为树状解。

(a) Pick a set

T \subset A

n - 1

arcs that form a tree when their direction is ignored.
(a) 挑选一组

T \subset A

的

n - 1

弧线，当忽略它们的方向时，它们会形成一棵树。
(b) Let

f_{i j} = 0

for every

(i, j) \notin T

.
(b) 让

f_{i j} = 0

适用于每一个

(i, j) \notin T

。
© Use the flow conservation equation

\tilde{A} f = \overset{―}{b}

to determine the flow variables

f_{i j}

, for

(i, j) \in T

.
使用流量守恒方程

\tilde{A} f = \overset{―}{b}

确定

f_{i j}

和

(i, j) \in T

的流量变量。
A tree solution that also satisfies

f \geq 0

, is called a feasible tree solution.
同时满足

f \geq 0

的树形解称为可行树形解。

Step © in the above definition can be carried out using the following systematic procedure, illustrated in Figure 7.10:
上述定义中的步骤 © 可以通过以下系统程序进行，如图 7.10 所示：
(a) Call node

n

the root of the tree.
(a) 将节点

n

称为树根。

Figure 7.10: A network and a set of

n - 1

arcs (indicated by hatched lines) that form a tree. By setting the arc flows outside the tree to zero, we obtain

f_{12} = 2, f_{23} = 2

and

f_{43} = 2

. We then use conservation of flow at node 3 , to obtain

f_{38} = 2

. We also have

f_{56} = 1

and

f_{67} = 0

. Using conservation of flow at node 6 , we obtain

f_{86} = 1

. Note that this is a feasible tree solution.
图 7.10：一个网络和一组

n - 1

弧（用阴影线表示）组成了一棵树。通过将树外的弧流量设为零，我们可以得到

f_{12} = 2, f_{23} = 2

和

f_{43} = 2

。然后，我们利用节点 3 的流量守恒得到

f_{38} = 2

。我们还可以得到

f_{56} = 1

和

f_{67} = 0

。利用节点 6 的流量守恒，我们得到

f_{86} = 1

。请注意，这是一个可行的树形解决方案。
(b) Use the flow conservation equations to determine the flows on the arcs incident to the leaves, and continue by proceeding from the leaves towards the root.
(b) 利用流量守恒方程确定叶片上弧线的流量，并继续从叶片向根部推进。

It should be pretty obvious from Figure 7.10 that once a tree is fixed, a corresponding tree solution is uniquely determined. Nevertheless, we provide a rigorous proof.
从图 7.10 中可以很明显地看出，一旦固定了一棵树，相应的树解就是唯一确定的。尽管如此，我们还是要提供一个严格的证明。

Theorem 7.3 Let

T \subset A

be a set of

n - 1

arcs that form a tree when their direction is ignored. Then, the system of linear equations

\overset{―}{A} f = \tilde{b}

, and

f_{i j} = 0

for all

(i, j) \notin T

, has a unique solution.
定理 7.3 设

T \subset A

是一组

n - 1

弧，当忽略它们的方向时，这些弧组成一棵树。那么，线性方程组

\overset{―}{A} f = \tilde{b}

和

f_{i j} = 0

对于所有

(i, j) \notin T

都有唯一的解。

Proof. Let B be the

(n - 1) \times (n - 1)

matrix that results if we only keep those

n - 1

columns of

\tilde{A}

that correspond to the arcs in

T

. Let

f_{T}

be the subvector of

f

, of dimension

n - 1

, whose entries are the flow variables

f_{i j}

(i, j) \in T

. We need to show that the linear system

{B f}_{T} = \tilde{b}

has a unique solution. For this, it suffices to show that the matrix

B

is nonsingular.
证明。假设 B 是

(n - 1) \times (n - 1)

矩阵，如果我们只保留

\tilde{A}

中与

T

中弧线相对应的

n - 1

列，那么 B 就是

(n - 1) \times (n - 1)

矩阵。让

f_{T}

成为

f

的子向量，维数为

n - 1

，其条目为流量变量

f_{i j}

、

(i, j) \in T

。我们需要证明线性系统

{B f}_{T} = \tilde{b}

有唯一的解。为此，只需证明矩阵

B

是非奇数即可。

Let us assume that the nodes have been renumbered so that numbers increase along any path from a leaf to the root node

n

. Let us also assign
假设节点已重新编号，因此从叶节点到根节点

n

的任何路径上的数字都会增加。我们还可以指定

[\begin{array}{rrrrrrr} 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & - 1 & 0 & 0 & 0 \\ - 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & - 1 & 0 & 0 & - 1 & 1 & 0 \\ 0 & 0 & - 1 & 1 & 0 & 0 & - 1 \end{array}]

Figure 7.11: A numbering of the nodes and arcs of a tree, and the corresponding

B

matrix.
图 7.11：树节点和弧的编号，以及相应的

B

矩阵。
to every

arc (i, j) \in T

, the number

min {i, j}

; see Figure 7.11. Such a renumbering of nodes and arcs amounts to a reordering of the rows and columns of

B

but does not affect whether

B

is singular or not.
对每个

arc (i, j) \in T

都重新编号为

min {i, j}

；见图 7.11。这种节点和弧的重新编号相当于对

B

的行和列重新排序，但并不影响

B

是否为奇数。

With the above numbering, the

i

th column of

B

corresponds to the

i

th arc, which is an arc of the form

(i, j)

(j, i)

, with

j > i

. Thus, any nonzero entries in the

i

th column will be in row

i

j

. Since

j > i

, no nonzero entry can be found above the diagonal. We conclude that

B

is lower triangular and has nonzero diagonal entries. This implies that

B

has nonzero determinant and is nonsingular, which completes the proof.
根据上述编号，

B

的第

i

列对应于第

i

个弧，即形式为

(i, j)

或

(j, i)

的弧，其中有

j > i

个弧。因此，第

i

列中的任何非零条目都将位于第

i

行或第

j

行。由于

j > i

，对角线上方找不到非零条目。我们得出结论，

B

是下三角，并且对角线上有非零条目。这意味着

B

具有非零行列式，并且是非正方形，从而完成了证明。

We note an important corollary of the proof of the previous theorem.
我们注意到前面定理证明的一个重要推论。

Corollary 7.1 If the graph

G

is connected, then the matrix

\overset{―}{A}

has linearly independent rows.
推论 7.1 如果图

G

是连通的，那么矩阵

\overset{―}{A}

具有线性独立行。

Proof. If the graph

G

is connected, then there exists a set of arcs

T \subset A

that form a tree, when their orientation is ignored (cf. Theorem 7.2). Let us pick such a set

T

and form the corresponding matrix

B

, as in the proof of Theorem 7.3. Since the

(n - 1) \times (n - 1)

matrix

\underset{A}{A}

is nonsingular, it has linearly independent columns. Hence, the matrix

\tilde{A}

has

n - 1

linearly independent columns and, therefore, has

n - 1

linearly independent rows.

◻

证明如果图

G

是连通的，那么存在一组弧

T \subset A

，当忽略它们的方向时，它们构成一棵树（参见定理 7.2）。让我们选取这样一个集合

T

并形成相应的矩阵

B

如同定理 7.3 的证明。由于

(n - 1) \times (n - 1)

矩阵

\underset{A}{A}

是非奇数，因此它具有线性独立列。因此，矩阵

\tilde{A}

具有

n - 1

线性独立列，并因此具有

n - 1

线性独立行。

◻

With our construction of a tree solution, the columns of

B

are the columns of

\tilde{A}

corresponding to the variables

f_{i j}

, for

(i, j) \in T

, and are linearly independent. In general linear programming terminology,

B

is a
在我们构建的树形解决方案中，

B

的列是

\tilde{A}

中与变量

f_{i j}

相对应的列，对于

(i, j) \in T

，它们是线性独立的。在一般线性规划术语中，

B

是一个
basis matrix. Since the remaining variables

f_{i j}, (i, j) \notin T

, are set to zero, the resulting flow vector

f

is the basic solution corresponding to this basis. Thus, a tree solution is a basic solution, and a feasible tree solution is a basic feasible solution. In fact, the converse is also true.
基矩阵。由于其余变量

f_{i j}, (i, j) \notin T

设为零，因此得到的流量向量

f

就是与此基础相对应的基本解。因此，树解就是基本解，可行树解就是基本可行解。事实上，反之亦然。

Theorem 7.4 A flow vector is a basic solution if and only if it is a tree solution.
定理 7.4 当且仅当一个流矢是一个树解时，它才是一个基本解。

Proof. We have already argued that a tree solution is a basic solution. Suppose now that a flow vector

f

is not a tree solution. We will show that it is not a basic solution. Note that if

A f \neq b

, then

f

is not a basic solution, by definition. Thus, we only need to consider the case where

A f = b

.
证明。我们已经论证了树解是基本解。现在假设流向量

f

不是树解。我们将证明它不是基本解。请注意，如果

A f \neq b

，那么根据定义，

f

也不是基本解。因此，我们只需考虑

A f = b

的情况。

Let

S = {(i, j) \in A ∣ f_{i j} \neq 0}

. If the arcs in the set

S

do not form a cycle, then there exists a set

T

n - 1

arcs such that

S \subset T

, and such that the

arcs

T

form a tree [cf. Assumption 7.1(b) and Theorem 7.2]. Since

f_{i j} = 0

for all

(i, j) \notin T

, the flow vector

f

is the tree solution associated with

T

, which is a contradiction.
设

S = {(i, j) \in A ∣ f_{i j} \neq 0}

。如果集合

S

中的弧不构成循环，则存在一个

n - 1

弧的集合

T

，使得

S \subset T

和

T

中的

arcs

构成一棵树 [参见假设 7.1(b) 和定理 7.2]。由于

f_{i j} = 0

适用于所有

(i, j) \notin T

，因此流矢量

f

是与

T

相关联的树解，这是一个矛盾。

Let us now assume that the set

S

contains a cycle

C

and let

h^{C}

be the simple circulation associated with

C

. Consider the flow vector

f + h^{C}

. We have

A f = b

and

A h^{C} = 0

, which implies that

A (f + h^{C}) = b

. Furthermore, whenever

f_{i j} = 0

, the arc

(i, j)

does not belong to the cycle

C

, and we have

h_{i j}^{C} = 0

. We see that all constraints that are active at the vector

f

are also active at the vector

f + h^{C}

. Thus, the constraints that are active at

f

do not have a unique solution, and

f

is not a basic solution (cf. Theorem 2.2 and Definition 2.9 in Section 2.2). See Figure 7.12 for an illustration.
现在，让我们假设集合

S

包含一个循环

C

，并让

h^{C}

成为与

C

相关联的简单循环。考虑流动矢量

f + h^{C}

。我们有

A f = b

和

A h^{C} = 0

，这意味着

A (f + h^{C}) = b

。此外，只要有

f_{i j} = 0

，弧

(i, j)

就不属于循环

C

，我们就有

h_{i j}^{C} = 0

。我们可以看到，在向量

f

上处于活动状态的所有约束条件在向量

f + h^{C}

上也处于活动状态。因此，在

f

处有效的约束没有唯一解，而

f

也不是基本解（参见第 2.2 节中的定理 2.2 和定义 2.9）。请参见图 7.12。

Figure 7.12: (a) Part of a flow vector that satisfies

A f = b

. This flow vector is not a tree solution because the arcs

(2, 1), (3, 1)

, and

(3, 2)

form a cycle

C

and carry nonzero flow. (b) The flow vector

f + h^{C}

. Active constraints (arcs that carry zero flow) under

f

remain active under

f + h^{C}

.
图 7.12：(a) 满足

A f = b

的流量向量的一部分。由于弧

(2, 1), (3, 1)

和

(3, 2)

形成循环

C

并携带非零流量，因此该流量向量不是树形解。(b) 流量向量

f + h^{C}

。

f

下的有效约束（流量为零的弧线）在

f + h^{C}

下保持有效。

To summarize our conclusions so far, we have established the following:
综上所述，我们得出了以下结论：
(a) Basic (feasible) solutions are (feasible) tree solutions and vice versa.
(a) 基本（可行）解就是（可行）树解，反之亦然。
(b) Every basis matrix is triangular when its rows and columns are suitably reordered.
(b) 如果对每个基矩阵的行和列进行适当的重新排序，它们都是三角形的。
© Given a basis matrix

B

, the vector of basic variables

B^{- 1} \tilde{b}

can be easily computed, without the need to maintain

B^{- 1}

in a tableau.
给定一个基矩阵

B

，就可以轻松计算出基本变量向量

B^{- 1} \tilde{b}

，而无需在表格中维护

B^{- 1}

。
As in the case of general linear programming problems, a basic feasible solution can be degenerate. This happens if the flow on some arc

(i, j) \in

T

turns out to be 0 . In this case, the same basic feasible solution may correspond to several trees. For example, the tree shown in Figure 7.10 leads to a degenerate basic feasible solution, because

f_{67} = 0

. A different tree that would yield the same basic feasible solution is obtained by replacing

arc (6, 7)

by arc

(5, 7)

.
与一般线性规划问题一样，基本可行解也可能是退化解。如果某些弧

(i, j) \in

T

上的流量为 0，就会出现这种情况。在这种情况下，同一个基本可行解可能对应多个树。例如，图 7.10 中的树会导致一个退化的基本可行解，因为

f_{67} = 0

。将弧

arc (6, 7)

替换为弧

(5, 7)

就可以得到另一棵树，而这棵树也会产生相同的基本可行解。

Change of basis 更改依据

We will now develop the mechanics of a change of basis. Recall that in a general linear programming problem, we first choose a nonbasic variable that enters the basis, find how to adjust the basic variables in order to maintain the equality constraints, and increase the value of the entering variable until one of the old basic variables is about to become negative. We specialize this procedure to the network case. Picking a nonbasic variable is the same as choosing an arc

(i, j)

that does not belong to

T

. Then, the

arc (i, j)

together with some of the arcs in

T

form a cycle. Let us choose the orientation of the cycle so that

(i, j)

is a forward arc. Let

F

and

B

be the sets of forward and backward arcs in the cycle, respectively. If we are to increase the value of the nonbasic variable

f_{i j}

to some

θ

, the old basic variables need to be adjusted in order not to violate the flow conservation constraints. This can be accomplished by pushing

θ

units of flow around the cycle. More precisely,

f_{k ℓ}

is increased (decreased) by

θ

for all forward (backward) arcs of the cycle. The new flow variables

{\hat{f}}_{k ℓ}

are given by
现在，我们将介绍基础变化的机制。回想一下，在一般的线性规划问题中，我们首先要选择一个进入基础的非基本变量，找到如何调整基本变量以保持相等约束条件的方法，并增加进入基础的变量值，直到其中一个旧的基本变量即将变为负值。我们将这一过程专门用于网络情况。选择一个非基本变量与选择一个不属于

T

的弧

(i, j)

是一样的。然后，

arc (i, j)

与

T

中的一些弧组成一个循环。让我们选择循环的方向，使

(i, j)

是一条向前的弧。让

F

和

B

分别成为循环中向前和向后弧的集合。如果我们要将非基本变量

f_{i j}

的值增加到某个

θ

，则需要调整原有的基本变量，以免违反流量守恒约束。这可以通过在循环中推动

θ

单位流量来实现。更确切地说，在循环的所有前进（后退）弧上，

f_{k ℓ}

都会增加（减少）

θ

。新的流量变量

{\hat{f}}_{k ℓ}

由以下公式给出

{\hat{f}}_{k ℓ} = {\begin{cases} f_{k ℓ} + θ, & if (k, ℓ) \in F \\ f_{k ℓ} - θ, & if (k, ℓ) \in B \\ f_{k ℓ}, & otherwise \end{cases}

We set

θ

as large as possible, provided that all arc flows remain nonnegative. It is clear that the largest possible value of

θ

is equal to
我们将

θ

设置得尽可能大，前提是所有弧流量保持非负。显然，

θ

的最大可能值等于

θ^{*} = min_{(k, ℓ) \in B} f_{k ℓ}

except if

B

is empty, in which case we let

θ^{*} = \infty

. A variable

f_{k ℓ}

that attains the minimum in Eq. (7.5) is set to zero and exits the basis. If

f_{k ℓ} = 0

for some

arc (k, ℓ) \in B

(which can happen if we start with a
除非

B

为空，在这种情况下，我们让

θ^{*} = \infty

为空。变量

f_{k ℓ}

如果达到公式 (7.5) 中的最小值，则设为零并退出基础。如果

f_{k ℓ} = 0

对于某个

arc (k, ℓ) \in B

（如果我们从一个
degenerate basic feasible solution), then the change of basis occurs without any change of the arc flows. (For the example shown in Figure 7.10, if

f_{57}

enters the basis,

f_{67}

exits the basis and

θ^{*} = 0

.)
如果

f_{57}

进入基点，

f_{67}

退出基点，

θ^{*} = 0

退出基点。(在图 7.10 所示的例子中，如果

f_{57}

进入基础，

f_{67}

退出基础，

θ^{*} = 0

退出基础）。

Calculation of the cost change
费用变化的计算

The cost change resulting from the above described change of basis, is equal to
上述基础变化引起的成本变化等于

θ^{*} \cdot (\sum_{(k, ℓ) \in F} c_{k ℓ} - \sum_{(k, ℓ) \in B} c_{k ℓ})

Naturally, the variable

f_{i j}

should enter the basis only if the value of the expression (7.6) is negative.
当然，只有当表达式 (7.6) 的值为负数时，变量

f_{i j}

才能进入基础。

From the development of the simplex method for general linear programming problems, we know that if the variable that enters the basis takes the value

θ^{*}

, then the cost changes by

θ^{*}

times the reduced cost of the entering variable. Comparing with Eq. (7.6), we see that the reduced cost

{\bar{c}}_{i j}

of a nonbasic variable

f_{i j}

is given by
根据一般线性规划问题的单纯形法的发展，我们知道，如果进入基础的变量取值为

θ^{*}

，则成本变化为

θ^{*}

乘以进入变量的降低成本。对比公式 (7.6)，我们可以看出，非基本变量

f_{i j}

的降低成本

{\bar{c}}_{i j}

由以下公式给出

{\bar{c}}_{i j} = \sum_{(k, ℓ) \in F} c_{k ℓ} - \sum_{(k, ℓ) \in B} c_{k ℓ}

which is simply the cost of the cycle around which flow is being pushed.
这仅仅是推动流量循环的成本。
We will now derive an alternative formula for the reduced costs that allows for more efficient computation. Recall the general formula

{\overset{―}{c}}^{'} =

c^{'} - p^{'} \tilde{A}

for determining the reduced costs, where

p

is the dual vector given by

p^{'} = c_{B}^{'} B^{- 1}, B

is the current basis matrix, and

c_{B}

is the vector with the costs of the basic variables. The dimension of

p

is equal to the number of rows of

\tilde{A}

, which is

n - 1

, and we have one dual variable

p_{i}

associated with each node

i \neq n

. Suppose that

(i, j)

is the

k

th arc of the graph. Then, the

k

th entry of the vectors

\overset{―}{c}

and

c

is equal to

{\bar{c}}_{i j}

and

c_{i j}

, respectively. The

k

th entry of

p^{'} \tilde{A}

is equal to the inner product of

p

with the

k

th column of

\tilde{A}

. From the definition of the node-arc incidence matrix, the

k

th column of

\tilde{A}

has an entry equal to 1 at the

i

th row (if

i < n

), and an entry equal to -1 at the

j

th row (if

j < n

). We conclude that
现在，我们将推导出另一个降低成本的公式，从而提高计算效率。回顾一下确定还原成本的一般公式

{\overset{―}{c}}^{'} =

c^{'} - p^{'} \tilde{A}

，其中

p

是由

p^{'} = c_{B}^{'} B^{- 1}, B

给出的对偶向量，

p^{'} = c_{B}^{'} B^{- 1}, B

是当前的基础矩阵，

c_{B}

是包含基本变量成本的向量。

p

的维数等于

\tilde{A}

的行数，即

n - 1

，我们有一个与每个节点

i \neq n

Overview of the algorithm
算法概述

We start with a summary of the network simplex algorithm and then proceed to discuss some issues related to initialization and termination.
我们首先总结了网络单纯形算法，然后讨论与初始化和终止相关的一些问题。

The simplex method for uncapacitated network flow problems
无容限网络流问题的单纯形法

A typical iteration starts with a basic feasible solution $f$ associated with a tree $T$ .
典型的迭代是从与树 $T$ 相关联的基本可行解 $f$ 开始的。
To compute the dual vector $p$ , solve the system of equations (7.10), by proceeding from the root towards the leaves.
要计算对偶向量 $p$ ，请从根部向叶部求解方程组 (7.10)。
Compute the reduced costs ${\bar{c}}_{i j} = c_{i j} - (p_{i} - p_{j})$ of all arcs $(i, j) \notin$ $T$ . If they are all nonnegative, the current basic feasible solution is optimal and the algorithm terminates; else, choose some ( $i, j$ ) with ${\bar{c}}_{i j} < 0$ to be brought into the basis.
计算所有弧 $(i, j) \notin$ $T$ 的还原成本 ${\bar{c}}_{i j} = c_{i j} - (p_{i} - p_{j})$ 。如果它们都是非负值，则说明当前的基本可行解是最优解，算法终止；否则，选择一些具有 ${\bar{c}}_{i j} < 0$ 的 ( $i, j$ ) 加入基础。
The entering $arc (i, j)$ and the $arcs$ in $T$ form a unique cycle. If all arcs in the cycle are oriented the same way as $(i, j)$ , then the optimal cost is $- \infty$ and the algorithm terminates.
进入 $arc (i, j)$ 的弧和 $T$ 中的 $arcs$ 形成一个唯一的循环。如果循环中的所有弧的方向都与 $(i, j)$ 相同，则最佳成本为 $- \infty$ ，算法终止。
Let $B$ be the set of arcs in the cycle that are oriented in the opposite direction from $(i, j)$ . Let $θ^{*} = min_{(k, ℓ) \in B} f_{k ℓ}$ , and push $θ^{*}$ units of flow around the cycle. A new flow vector is determined according to Eq. (7.4). Remove from the basis one of the old basic variables whose new value is equal to zero.
让 $B$ 成为循环中方向与 $(i, j)$ 相反的弧的集合。让 $θ^{*} = min_{(k, ℓ) \in B} f_{k ℓ}$ ，并将 $θ^{*}$ 单位流量推向循环周围。根据公式 (7.4) 确定新的流量矢量。从基础中删除一个新值等于零的旧基本变量。

In the case where finding an initial basic feasible solution is difficult, we may need to form and solve an auxiliary problem. For example, for each pair of source and sink nodes, we may introduce an auxiliary arc; finding a basic feasible solution in the presence of these arcs is straightforward. Furthermore, if the unit costs

c_{i j}

of the auxiliary arcs are chosen large enough, solving the auxiliary problem is equivalent to solving the original problem.
在难以找到初始基本可行解的情况下，我们可能需要形成并解决一个辅助问题。例如，对于每一对源节点和汇节点，我们可以引入一条辅助弧；在存在这些弧的情况下，找到基本可行解是很简单的。此外，如果辅助弧的单位成本

c_{i j}

选得足够大，那么解决辅助问题就等同于解决原始问题。

The network simplex algorithm is similar to the naive implementation described in Section 3.3. Because of the special structure of the basis matrix B, the system

c_{B}^{'} = p^{'} B

can be solved on the fly, without the need to maintain a simplex tableau or the inverse basis matrix

B^{- 1}

. For a rough
网络单纯形算法与第 3.3 节中描述的天真算法类似。由于基矩阵 B 的特殊结构，系统

c_{B}^{'} = p^{'} B

可以即时求解，而无需维护单纯形表或逆基矩阵

B^{- 1}

。对于粗略的

Figure 7.13: Once

p_{i}

is computed,

p_{j}

and

p_{k}

can also be computed, because we have

p_{i} - p_{j} = c_{i j}

and

p_{k} - p_{i} = c_{k i}

. Starting from the root and continuing in this fashion, all dual variables can be computed.
图 7.13：计算出

p_{i}

之后，还可以计算

p_{j}

和

p_{k}

，因为我们有

p_{i} - p_{j} = c_{i j}

和

p_{k} - p_{i} = c_{k i}

。从根开始，以这种方式继续下去，所有对偶变量都可以计算出来。
count of the computational requirements of each iteration, we need

O (n)

computations to evaluate the dual vector

p, O (m)

computations to evaluate all of the reduced costs, and another

O (n)

computations to effect the change of basis. Given that

m \geq n - 1

, the total is

O (m)

, which compares favorably with the

O (m n)

computational requirements of an iteration of the simplex method for general linear programming problems. In practice, the running time of the network simplex algorithm is improved further by using a somewhat more clever way of updating the dual variables, and by using suitable data structures to organize the computation.
计算每次迭代所需的计算量时，我们需要

O (n)

次计算来评估对偶向量

p, O (m)

次计算来评估所有降低的成本，还需要

O (n)

次计算来实现基础的改变。考虑到

m \geq n - 1

，总计算量为

O (m)

，这与一般线性规划问题的单纯形法迭代所需的

O (m n)

计算量相比毫不逊色。在实践中，通过使用更巧妙的方法更新对偶变量，以及使用合适的数据结构组织计算，网络单纯形算法的运行时间会得到进一步改善。

All of the theory in Chapters 3 and 4 applies to the network simplex method. In particular, in the absence of degeneracy, the algorithm is guaranteed to terminate after a finite number of steps. In the presence of degeneracy, the algorithm may cycle. Cycling can be avoided by using either a general purpose anticycling rule or special methods. If the optimal cost is

- \infty

, the algorithm terminates with a negative cost directed cycle. (The simple circulation

h^{C}

associated with that cycle is an extreme ray of the feasible set, and

c^{'} h^{C} < 0

.) If the optimal cost is finite, the algorithm terminates with an optimal flow vector

f

and an optimal dual vector

p

. In practice, the number of iterations is often

O (m)

, but there exist examples involving an exponential number of basis changes.
第 3 章和第 4 章中的所有理论都适用于网络单纯形法。特别是，在没有退化的情况下，算法保证在有限步数后终止。在存在退化的情况下，算法可能会循环。可以通过使用通用的反循环规则或特殊方法来避免循环。如果最优代价为

- \infty

，算法会以负代价定向循环结束。(与该循环相关的简单循环

h^{C}

是可行集的极射线，而

c^{'} h^{C} < 0

是可行集的极射线）。如果最优成本是有限的，算法将以最优流向量

f

和最优对偶向量

p

结束。在实践中，迭代次数通常为

O (m)

，但也有涉及指数级基础变化的例子。

Example 7.3 Consider the uncapacitated network problem shown in Figure 7.14(a); the numbers next to each arc are the corresponding costs. Figure 7.14(b) shows a tree and a corresponding feasible tree solution. Arc

(4, 3)

forms a cycle consisting of nodes 4,3 , and 5 . The reduced cost

{\bar{c}}_{43}

f_{43}

is equal to the cost of
例 7.3 考虑图 7.14(a) 所示的无容错网络问题；每个弧旁边的数字是相应的成本。图 7.14(b) 显示了一棵树和相应的可行树解。弧

(4, 3)

构成了一个由节点 4、3 和 5 组成的循环。

f_{43}

的降低成本

{\bar{c}}_{43}

等于

Figure 7.14: (a) An uncapacitated network flow problem. Arc costs are indicated next to each arc. (b) An initial feasible tree solution. The arc flows are indicated next to each arc. ©-(d) Feasible tree solutions obtained after the first and the second change of basis, respectively.
图 7.14：(a) 无容错网络流问题。每条弧旁边都标有弧成本。(b) 初始可行树解决方案。每个弧旁边都标有弧流。(c)-(d)分别是第一次和第二次改变基础后得到的可行树形解。
that cycle, which is

c_{43} + c_{35} - c_{45} = - 1

. We let arc

(4, 3)

enter the tree. Pushing flow along the cycle attempts to reduce the flow along the arc ( 4,5 ). Since this was zero to start with (degeneracy), we have

θ^{*} = 0

; the arc

(4, 5)

arc (1, 2)

c_{12} + c_{24} + c_{43} - c_{13} = - 1

, and we let that arc enter the tree. We can push up to one unit of flow along the cycle

1, 2, 4, 3, 1

, that is, until the flow along arc

(1, 3)

is set to zero. Thus,

θ^{*} = 1

, the

arc (1, 3)

leaves the tree, and we obtain the feasible tree solution indicated in Figure 7.14(d). It is not hard to verify that all reduced costs are nonnegative and we have an optimal solution.
即

c_{43} + c_{35} - c_{45} = - 1

。我们让弧

(4, 3)

进入树中。沿循环推动流量，试图减少沿弧 ( 4,5 ) 的流量。由于开始时流量为零（退化），我们得到

θ^{*} = 0

；弧

(4, 5)

arc (1, 2)

Integrality of optimal solutions
最优解的整体性

An important feature of network flow problems is that when the problem data are integer, most quantities of interest are also integer and the simplex method can be implemented using integer (as opposed to floating point) arithmetic. This allows for faster computation and, equally important, the issues of finite precision and truncation error disappear. The theorem that follows provides a summary of integrality properties.
网络流问题的一个重要特点是，当问题数据是整数时，大多数相关量也是整数，因此可以使用整数（而非浮点）算术来实现单纯形法。这样可以加快计算速度，同样重要的是，有限精度和截断误差的问题也不复存在。下面的定理提供了整数特性的总结。

Theorem 7.5 Consider an uncapacitated network flow problem and assume that the underlying graph is connected.
定理 7.5 考虑无容错网络流量问题，假设底层图是连通的。

(a) For every basis matrix B, the matrix

B^{- 1}

has integer entries.
(a) 对于每个基矩阵 B，矩阵

B^{- 1}

都有整数条目。
(b) If the supplies

b_{i}

are integer, then every basic solution has integer coordinates.
(b) 如果供给

b_{i}

c_{i j}

are integer, then every dual basic solution has integer coordinates.
如果费用系数

c_{i j}

是整数，那么每个对偶基本解都有整数坐标。

Proof. 证明。

(a) As shown in the proof of Theorem 7.3, we can reorder the rows and columns of a basis matrix

B

so that it becomes lower triangular and its diagonal entries are either 1 or -1 . Therefore, the determinant of

B

is equal to 1 or -1 . By Cramer’s rule,

B^{- 1}

has integer entries.
(a) 如定理 7.3 的证明所示，我们可以对基矩阵

B

的行和列重新排序，使其成为下三角矩阵，其对角线项要么为 1，要么为-1。因此，

B

的行列式等于 1 或 -1 。根据克拉默法则，

B^{- 1}

具有整数条目。
(b) This follows by inspecting the nature of the algorithm that determines the values of the basic variables (see the proof of Theorem 7.3), or from the formula

f_{T} = B^{- 1} \tilde{b}

.
(b) 通过观察决定基本变量值的算法的性质（见定理 7.3 的证明），或从公式

f_{T} = B^{- 1} \tilde{b}

中可以得出结论。
© This follows by inspecting the nature of the algorithm that determines the values of the dual variables, or from the formula

p^{'} = c_{B}^{'} B^{- 1}

.
通过观察决定对偶变量值的算法的性质，或根据公式

p^{'} = c_{B}^{'} B^{- 1}

得出。

We now have the following important corollary of Theorem 7.5.
现在我们有了定理 7.5 的如下重要推论。

Corollary 7.2 Consider an uncapacitated network flow problem, and assume that the optimal cost is finite.
推论 7.2 考虑一个无容限网络流量问题，假设最优成本是有限的。

(a) If all supplies

b_{i}

are integer, there exists an integer optimal flow vector.
(a) 如果所有供应量

b_{i}

都是整数，则存在一个整数最佳流量矢量。
(b) If all cost coefficients

c_{i j}

are integer, there exists an integer optimal solution to the dual problem.
(b) 如果所有成本系数

c_{i j}

都是整数，则对偶问题存在一个整数最优解。

The simplex method for capacitated problems
容量问题的单纯形法

We will now generalize the simplex method to the case where some of the arc capacities are finite and we have constraints of the form
现在，我们将把单纯形法推广到某些弧的容量是有限的情况，并且我们有如下形式的约束条件

d_{i j} \leq f_{i j} \leq u_{i j}, (i, j) \in A

There are only some minor differences from the discussion earlier in this section. For this reason, our development will be less formal.
与本节前面的讨论仅有细微差别。因此，我们的论述将不那么正式。

Consider a set

T \subset A

n - 1

arcs that form a tree when their direction is ignored. We partition the remaining arcs into two disjoint subsets

D

and

U

. We let

f_{i j} = d_{i j}

for every

(i, j) \in D, f_{i j} = u_{i j}

for every

(i, j) \in U

, and then solve the flow conservation equations for the remaining variables

f_{i j}

(i, j) \in T

. The resulting flow vector is easily shown to be a basic solution, and all basic solutions can be obtained in this manner; the argument is similar to the proofs of Theorems 7.3 and 7.4.
考虑一组

T \subset A

的

n - 1

弧，当忽略其方向时，这些弧组成一棵树。我们将剩余的弧划分为两个互不相交的子集

D

和

U

。我们让

f_{i j} = d_{i j}

代表每个

(i, j) \in D, f_{i j} = u_{i j}

代表每个

(i, j) \in U

，然后求解其余变量

f_{i j}

(i, j) \in T

的流量守恒方程。由此得到的流量矢量很容易证明是基本解，而且所有基本解都可以通过这种方法得到；其论证与定理 7.3 和 7.4 的证明类似。

Given a basic feasible solution associated with the sets

T, D

, and

U

, we evaluate the vector of reduced costs using the same formulae as before, and then examine the arcs outside

T

. If we find an

arc (i, j) \in D

whose reduced cost is negative, we push as much flow as possible around the cycle created by that arc. (This is the same as in our previous development.) Alternatively, if we can find an

arc (i, j) \in U

with positive reduced cost, we push as much flow as possible around the cycle created by that arc, but in the opposite direction. In either case, we are dealing with a direction of cost decrease. Determining how much flow can be pushed is done as follows. Let

F

be the set of arcs whose flow is to increase due to the contemplated flow push; let

B

be the set of arcs whose flow is to decrease. Then, the flow increment is limited by

θ^{*}

, defined as follows:
给定一个与集合

T, D

和

U

相关联的基本可行解，我们使用与之前相同的公式评估降低成本向量，然后检查

T

以外的弧。如果我们发现

arc (i, j) \in D

的降低成本为负值，我们就会在该弧所形成的循环周围推动尽可能多的流量。(或者，如果我们能找到一个降低成本为正的

arc (i, j) \in U

，我们就会在该弧所形成的循环周围推动尽可能多的流量，但方向相反。无论哪种情况，我们都是在处理成本降低的方向。确定可以推动多少流量的方法如下。假设

F

是弧的集合，其流量会因考虑的流量推动而增加；假设

B

是弧的集合，其流量会减少。然后，流量增量受

θ^{*}

的限制，其定义如下：

θ^{*} = min {min_{(k, ℓ) \in B} {f_{k ℓ} - d_{k ℓ}}, min_{(k, ℓ) \in F} {u_{k ℓ} - f_{k ℓ}}} .

By pushing

θ^{*}

units of flow around the cycle, there will be at least one arc

(k, ℓ)

whose flow is set to either

d_{k ℓ}

u_{k ℓ}

. If the

arc (k, ℓ)

belongs to

T

, it is removed from the tree and is replaced by

(i, j)

. The other possibility is that

(k, ℓ) = (i, j)

. (For example, pushing flow around the cycle may result in

f_{i j}

being reduced from

u_{i j}

d_{i j}

.) In that case, the set

T

remains the
将

θ^{*}

个单位的流量推到循环周围，至少会有一条弧

(k, ℓ)

的流量被设置为

d_{k ℓ}

或

u_{k ℓ}

。如果

arc (k, ℓ)

属于

T

，则会从树中删除，由

(i, j)

代替。另一种可能是

(k, ℓ) = (i, j)

。(例如，围绕循环推动流量可能会导致

f_{i j}

从

u_{i j}

缩减到

d_{i j}

）。在这种情况下，集合

T

仍然是
same, but

(i, j)

is moved from

U

D

, or vice versa. In any case, we obtain a new basic feasible solution. (In the presence of degeneracy, it is possible that the new basic feasible solution coincides with the old one, and only the sets

T, D

, or

U

change.) To summarize, the network simplex algorithm for capacitated problems is as follows.
相同，但

(i, j)

会从

U

移动到

D

，反之亦然。无论如何，我们都会得到一个新的基本可行解。(在存在退化的情况下，新的基本可行解有可能与旧解重合，只有集合

T, D

或

U

发生变化）。总之，容错问题的网络单纯形算法如下。

The simplex method for capacitated network flow problems
容量网络流问题的单纯形法

A typical iteration starts with a basic feasible solution $f$ associated with a tree $T$ , and a partition of the remaining arcs into two sets $D, U$ , such that $f_{i j} = d_{i j}$ for $(i, j) \in D$ , and $f_{i j} = u_{i j}$ for $(i, j) \in U$ .
典型的迭代开始于与树 $T$ 相关的基本可行解 $f$ ，以及将剩余弧划分为两个集合 $D, U$ ，这样 $f_{i j} = d_{i j}$ 代表 $(i, j) \in D$ ，而 $f_{i j} = u_{i j}$ 代表 $(i, j) \in U$ 。
Solve the system of equations (7.10) for $p_{1}, \dots, p_{n}$ , by proceeding from the root towards the leaves.
从根向叶求解 $p_{1}, \dots, p_{n}$ 的方程组 (7.10)。
Compute the reduced costs ${\bar{c}}_{i j} = c_{i j} - (p_{i} - p_{j})$ of all arcs $(i, j) \notin$ $T$ . If ${\bar{c}}_{i j} \geq 0$ for all $(i, j) \in D$ , and ${\bar{c}}_{i j} \leq 0$ for all $(i, j) \in U$ , the current basic feasible solution is optimal and the algorithm terminates.
计算所有弧 $(i, j) \notin$ $T$ 的降低成本 ${\bar{c}}_{i j} = c_{i j} - (p_{i} - p_{j})$ 。如果所有 $(i, j) \in D$ 都是 ${\bar{c}}_{i j} \geq 0$ ，所有 $(i, j) \in U$ 都是 ${\bar{c}}_{i j} \leq 0$ ，则当前的基本可行解是最优解，算法终止。
Let $(i, j)$ be an arc such that ${\bar{c}}_{i j} < 0$ and $(i, j) \in D$ , or such that ${\bar{c}}_{i j} > 0$ and $(i, j) \in U$ . This arc $(i, j)$ together with the tree $T$ forms a unique cycle. Choose the orientation of the cycle as follows. If $(i, j) \in D$ , then $(i, j)$ should be a forward arc. If $(i, j) \in U$ , then ( $i, j$ ) should be a backward arc.
假设 $(i, j)$ 是一条弧，使得 ${\bar{c}}_{i j} < 0$ 和 $(i, j) \in D$ 相交，或者使得 ${\bar{c}}_{i j} > 0$ 和 $(i, j) \in U$ 相交。这条弧 $(i, j)$ 与树 $T$ 构成一个唯一的循环。选择循环的方向如下。如果是 $(i, j) \in D$ ，那么 $(i, j)$ 应该是一条向前的弧。如果是 $(i, j) \in U$ ，则 ( $i, j$ ) 应为向后弧。
Let $F$ and $B$ be the forward and backward arcs, respectively, in the cycle. Determine $θ^{*}$ according to Eq. (7.11). Compute a new flow vector, with components ${\hat{f}}_{k ℓ}$ , by letting
设 $F$ 和 $B$ 分别为循环中的前弧和后弧。根据公式 (7.11) 确定 $θ^{*}$ 。计算一个新的流量向量，其分量为 ${\hat{f}}_{k ℓ}$ ，让

{\hat{f}}_{k ℓ} = {\begin{cases} f_{k ℓ} + θ^{*}, & if (k, ℓ) \in F, \\ f_{k ℓ} - θ^{*}, & if (k, ℓ) \in B, \\ f_{k l}, & otherwise. \end{cases}

Finally, update the sets

T, D, U

.
最后，更新

T, D, U

集。

7.4 The negative cost cycle algorithm
7.4 负成本循环算法

The network simplex algorithm incorporates a basic idea, which is present in practically every primal method for network flow problems: given a current primal feasible solution, find an improved one by identifying a negative cost cycle along which flow can be pushed. One advantage of the simplex method is that it searches for negative cost cycles using a streamlined and efficient mechanism. A potential disadvantage is that a change of basis can be degenerate, with no flow being pushed, and without any cost improvement.
网络单纯形算法包含了一个基本思想，几乎存在于每一种网络流量问题的基本方法中：给定一个当前的基本可行解，通过确定一个负成本循环来找到一个改进的解，沿着这个循环可以推动流量。单纯形法的一个优点是，它使用一种精简高效的机制来搜索负成本循环。一个潜在的缺点是，基础的改变可能是退化的，没有流量推动，也没有任何成本改善。

In this section, we present a related, but different, algorithm, where every iteration aims at a nonzero cost improvement. In particular, at every
在本节中，我们将介绍一种相关但不同的算法，在这种算法中，每次迭代都以非零成本改进为目标。特别是，在每次

Figure 7.15: (a) A portion of a network, together with the values of some of the flow variables. (b) The new arc flows after pushing

δ

units of flow around the cycle

C

.
图 7.15： (a) 网络的一部分，以及一些流量变量的值。(b) 在循环

C

周围推动

δ

单位流量后的新弧流量。
iteration we push some flow around a negative cost cycle. The algorithm terminates when no profitable cycle can be identified. The method is justified by a key result that relates the absence of profitable cycles with optimality.
迭代时，我们会在负成本循环周围推动一些流量。如果找不到有利可图的循环，算法就会终止。该方法的一个关键结果证明了其合理性，该结果将无盈利循环与最优性联系了起来。

Motivation 动机

Consider the portion of a network shown in Figure 7.15(a). Could the flow vector

f

given in the figure be optimal? The answer is no, for the following reason. Suppose that we push

δ

units of flow along the indicated cycle, where

δ

is a positive scalar. Taking into account the direction of the arcs, the new flow variables take the values indicated in Figure 7.15(b). In particular, the flow on every forward arc is increased by

δ

and the flow on every backward arc is reduced by

δ

. Flow conservation is preserved, and as long as

δ \leq 2

, the constraints

0 \leq f_{i j} \leq u_{i j}

are respected, and the new
考虑图 7.15(a) 中所示的网络部分。图中给出的流量矢量

f

是最优的吗？答案是否定的，原因如下。假设我们沿所示循环推送

δ

单位流量，其中

δ

为正标量。考虑到弧的方向，新的流量变量的值如图 7.15(b) 所示。特别是，每个向前弧上的流量增加了

δ

，每个向后弧上的流量减少了

δ

。流量保持不变，只要

δ \leq 2

、约束条件

0 \leq f_{i j} \leq u_{i j}

得到遵守，新的
flow is feasible. The change in costs is
流量是可行的。成本变化为

c_{12} δ + c_{32} (- δ) + c_{34} δ + c_{14} (- δ) = - δ

which is negative, and

f

cannot be optimal. As this example illustrates, a flow

f

can be improved if we can identify a cycle along which flow can be profitably pushed.
是负值，因此

f

不可能是最优的。正如本例所示，如果我们能确定一个周期，沿着这个周期推动流量可以带来利润，那么流量

f

就可以得到改善。

Description of the algorithm
算法说明

In this subsection, we present the algorithm of interest after developing some of its elements. We assume that we have a network described by a directed graph

G = (N, A)

, supplies

b_{i}

, arc capacities

u_{i j}

, and cost coefficients

c_{i j}

. Let

C

be a cycle, and let

F

and

B

be the sets of forward and backward arcs of the cycle, respectively. Let

h^{C}

be the simple circulation associated with this cycle; that is,
在本小节中，我们将在阐述算法的部分要素后，介绍我们感兴趣的算法。我们假设有一个由有向图

G = (N, A)

、供给

b_{i}

、弧容量

u_{i j}

和成本系数

c_{i j}

描述的网络。假设

C

是一个循环，假设

F

和

B

分别是循环的前向弧集和后向弧集。让

h^{C}

成为与此循环相关的简单循环；即

h_{i j}^{C} = {\begin{aligned} 1, & if (i, j) \in F \\ - 1, & if (i, j) \in B \\ 0, & otherwise \end{aligned}

Let

f

be a feasible flow vector and let

δ

be a nonnegative scalar. If we change

f

f + δ h^{C}

, we say that we are pushing

δ

units of flow along the cycle

C

. Since

f

is feasible, we have

A f = b

; since

A h^{C} = 0

, we obtain

A (f + δ h^{C}) = b

, and the flow conservation constraint is still satisfied. In order to maintain feasibility, we also need
假设

f

是一个可行的流量向量，假设

δ

是一个非负标量。如果我们将

f

改为

f + δ h^{C}

，我们就可以说，我们正沿着循环

C

推动

δ

单位流量。由于

f

是可行的，我们得到

A f = b

；由于

A h^{C} = 0

，我们得到

A (f + δ h^{C}) = b

，流量守恒约束仍然满足。为了保持可行性，我们还需要

0 \leq f_{i j} + δ h_{i j}^{C} \leq u_{i j}

that is, 也就是说

\begin{array}{ll} 0 \leq f_{i j} + δ \leq u_{i j}, & if (i, j) \in F \\ 0 \leq f_{i j} - δ \leq u_{i j}, & if (i, j) \in B \end{array}

Since

δ \geq 0

and

0 \leq f_{i j} \leq u_{i j}

, this is equivalent to
由于

δ \geq 0

和

0 \leq f_{i j} \leq u_{i j}

，这相当于

\begin{array}{ll} δ \leq u_{i j} - f_{i j}, & if (i, j) \in F \\ δ \leq f_{i j}, & if (i, j) \in B \end{array}

Thus, the maximum amount of flow that can be pushed along the cycle, which we denote by

δ (C)

, is given by
因此，我们用

δ (C)

表示沿循环推动的最大流量，其值为

δ (C) = min {min_{(i, j) \in F} (u_{i j} - f_{i j}), min_{(i, j) \in B} f_{i j}}

If the set

B

is empty and if

u_{i j} = \infty

for every arc in the cycle, then there are no restrictions on

δ

, and we set

δ (C) = \infty

. If

f_{i j} < u_{i j}

for all forward arcs and

f_{i j} > 0

for all backward arcs, then

δ (C) > 0

, and we say that the
如果集合

B

为空，且循环中的每条弧都是

u_{i j} = \infty

，则

δ

没有限制，我们设置

δ (C) = \infty

。如果

f_{i j} < u_{i j}

表示所有向前的弧，

f_{i j} > 0

表示所有向后的弧，那么

δ (C) > 0

，我们就说
cycle is unsaturated. For the cycle considered in Figure 7.15(a), we have

δ (C) = 2

.
循环是不饱和的。对于图 7.15(a) 中的循环，我们有

δ (C) = 2

。

We now calculate the cost change when we push a unit of flow along a cycle

C

. Using the definition of

h^{C}

, the cost change is
现在，我们来计算一下当我们沿着

C

循环推动一个单位流量时的成本变化。根据

h^{C}

的定义，成本变化为

c^{'} h^{C} = \sum_{(i, j) \in F} c_{i j} - \sum_{(i, j) \in B} c_{i j}

the cost of cycle

C

C

周期的成本。
We can now propose an algorithm which at each iteration looks for a negative cost unsaturated cycle and pushes as much flow as possible along that cycle.
现在，我们可以提出一种算法，在每次迭代时寻找一个负成本的非饱和循环，并将尽可能多的流量推向该循环。

Negative cost cycle algorithm
负成本循环算法

Start with a feasible flow $f$ .
从可行的流程 $f$ 开始。
Search for an unsaturated cycle with negative cost.
寻找负成本的不饱和循环。
If no unsaturated cycle with negative cost can be found, the algorithm terminates.
如果找不到成本为负的不饱和循环，算法就会终止。
If a negative cost unsaturated cycle $C$ is found, then:
如果找到负成本的不饱和循环 $C$ ，那么：
(a) If $δ (C) < \infty$ , construct the new feasible flow $f + δ (C) h^{C}$ , and go to Step 2.
(a) 如果 $δ (C) < \infty$ ，则构建新的可行流 $f + δ (C) h^{C}$ ，并转到步骤 2。
(b) If $δ (C) = \infty$ , the algorithm terminates and the optimal cost is $- \infty$ .
(b) 如果 $δ (C) = \infty$ ，算法终止，最佳成本为 $- \infty$ 。

There are a few different issues that need to be discussed:
有几个不同的问题需要讨论：
(a) How do we start the algorithm?
(a) 如何启动算法？
(b) How do we search for an unsaturated cycle with negative cost?
(b) 如何寻找成本为负的不饱和循环？
© If the algorithm terminates, does it provide us with an optimal solution?
如果算法终止，它是否为我们提供了最优解？
(d) Is the algorithm guaranteed to terminate?
(d) 算法是否保证终止？

These issues are addressed, one at a time, in the subsections that follow.
下文各小节将逐一讨论这些问题。

Starting the algorithm 启动算法

As discussed in Section 7.2, every network flow problem can be converted into an equivalent problem with no sources or sinks. For the latter problem, the zero flow is a feasible solution that provides a starting point. As an alternative, a feasible flow (if one exists) can be constructed by solving a suitable maximum flow problem (Exercise 7.21).
如第 7.2 节所述，每个网络流量问题都可以转换成一个没有源或汇的等价问题。对于后一种问题，零流量是一个可行解，它提供了一个起点。另外，还可以通过求解合适的最大流量问题（练习 7.21）来构建可行的流量（如果存在的话）。

The residual network 残差网络

Suppose that we have a network

G = (N, A)

and a feasible flow

f

. The residual network is an auxiliary network

\tilde{G} = (N, \tilde{A})

with the same set of nodes, but with different arcs and arc capacities. It is a convenient device to keep track of the amount of flow that can be pushed along the arcs of the original network.
假设我们有一个网络

G = (N, A)

和一个可行流量

f

。残余网络是一个辅助网络

\tilde{G} = (N, \tilde{A})

，其节点集相同，但弧和弧容量不同。它是一种方便的工具，可用于跟踪可沿原始网络的弧推动的流量。

Consider an arc

(i, j)

, with capacity

u_{i j}

, and let

f_{i j}

be the current flow through that arc. Then,

f_{i j}

can be increased by up to

u_{i j} - f_{i j}

, or can be decreased by up to

f_{i j}

. We represent these options in the residual network by introducing an arc

(i, j)

with capacity

u_{i j} - f_{i j}

, and an arc

(j, i)

, with capacity

f_{i j}

. Any flow on the

arc (j, i)

in the residual network is to be interpreted as a corresponding reduction of the flow on the arc

(i, j)

of the original network.
考虑一个容量为

u_{i j}

的电弧

(i, j)

，让

f_{i j}

成为通过该电弧的电流。那么，

f_{i j}

最多可增加

u_{i j} - f_{i j}

，或最多可减少

f_{i j}

。我们在残差网络中引入容量为

u_{i j} - f_{i j}

的弧

(i, j)

和容量为

f_{i j}

的弧

(j, i)

来表示这些选项。残差网络中

arc (j, i)

上的任何流量都将被解释为原始网络中

(i, j)

弧上流量的相应减少。

We assign costs to the arcs of the residual network in a way that reflects the cost changes in the original network. In particular, we associate a cost of

c_{i j}

with the

arc (i, j)

of the residual network, and a cost of

- c_{i j}

with the arc

(j, i)

of the residual network. [This is because a unit of flow on the

arc (j, i)

corresponds to a unit reduction of the flow on the

arc (i, j)

of the original network, and a cost change of

- c_{i j}

.] All supplies in the residual network are set to zero, which implies that every feasible flow is a circulation. Finally, we delete those arcs of the residual network that have zero capacity.
我们为残差网络中的弧分配成本的方式反映了原始网络中的成本变化。具体而言，我们将

c_{i j}

的成本与残差网络的

arc (i, j)

Optimality conditions 优化条件

We now investigate what happens at termination of the negative cost cycle algorithm. If the algorithm terminates because it discovered a negative cost cycle with

δ (C) = \infty

, then the optimal cost is

- \infty

. In particular, the flow

f + δ h^{C}

is feasible for every

δ > 0

, and by letting

δ

become arbitrarily large, the cost of such feasible solutions is unbounded below.
现在，我们来研究一下负成本循环算法终止时的情况。如果算法终止的原因是发现了一个具有

δ (C) = \infty

的负成本循环，那么最优成本就是

- \infty

。特别是，对于每一个

δ > 0

流量，

f + δ h^{C}

都是可行的，而且只要让

δ

变得任意大，这种可行解的成本就会在下方无界。

The algorithm may also terminate because no unsaturated negative cost cycle can be found. In that case, we have an optimal solution, as shown by the next result.
算法也可能因为找不到不饱和负成本循环而终止。在这种情况下，我们就有了一个最优解，如下面的结果所示。

Theorem 7.6 A feasible flow f is optimal if and only if there is no unsaturated cycle with negative cost.
定理 7.6 当且仅当不存在成本为负的不饱和循环时，可行流 f 才是最优的。

Proof. One direction is easy. If

C

is an unsaturated cycle with negative cost, then

f + δ (C) h^{C}

is a feasible flow whose cost is less than the cost of

f

, and so

f

is not optimal.
证明。一个方向很容易。如果

C

是成本为负的不饱和循环，那么

f + δ (C) h^{C}

是可行流，其成本小于

f

的成本，因此

f

不是最优流。

For the converse, we argue by contradiction. Suppose that

f

is a feasible flow that is not optimal. Then, there exists another feasible flow

f + \overset{―}{f}

whose cost is less, and in particular,

c^{'} \overset{―}{f} < 0

. As discussed in the preceding subsection, it follows that there exists a feasible (in particular, nonnegative) circulation

\tilde{f}

in the residual network whose cost is negative. To prove that this circulation implies the existence of a negative cost directed cycle in the residual network, we need the following important result.
反过来，我们用矛盾论证。假设

f

是一个并非最优的可行流量。那么，存在另一个成本更低的可行流量

f + \overset{―}{f}

，尤其是

c^{'} \overset{―}{f} < 0

。如上一小节所述，剩余网络中存在一个可行的（尤其是非负的）流通量

\tilde{f}

，其成本为负。为了证明这一循环意味着残差网络中存在负成本的有向循环，我们需要以下重要结果。

Lemma 7.1 (Flow decomposition theorem) Let

f \geq 0

be a nonzero circulation. Then, there exist simple circulations

f^{1}, \dots, f^{k}

, involving only forward arcs, and positive scalars

a_{1}, \dots, a_{k}

, such that
定理 7.1（流动分解定理）设

f \geq 0

是一个非零循环。那么，存在只涉及正向弧的简单环流

f^{1}, \dots, f^{k}

和正标量

a_{1}, \dots, a_{k}

，使得

f = \sum_{i = 1}^{k} a_{i} f^{i}

Furthermore, if

f

is an integer vector, then each

a_{i}

can be chosen to be an integer.
此外，如果

f

是一个整数向量，那么每个

a_{i}

都可以选择为整数。

Proof. (See Figure 7.18 for an illustration.) If

f

is the zero vector, the result is trivially true, with

k = 0

. Suppose that

f

is nonzero. Then, there exists some

arc (i, j)

for which

f_{i j} > 0

. Let us traverse

arc (i, j)

. Because of flow conservation at node

j

, there exists some

arc (j, k)

for which

f_{j k} > 0

. We then traverse arc

(j, k)

and keep repeating the same process. Since there are finitely many nodes, some node will be eventually visited for a second time. At that point, we have found a directed cycle with each arc in the cycle carrying a positive amount of flow. Let

f^{1}

be the simple circulation
证明。(见图 7.18。）如果

f

是零向量，结果与

k = 0

完全正确。假设

f

是非零向量。那么，存在某个

arc (i, j)

，其中

f_{i j} > 0

.让我们穿越

arc (i, j)

。由于节点

j

处的流量守恒，存在某个

arc (j, k)

，对其而言

f_{j k} > 0

。然后，我们穿越弧

(j, k)

并不断重复同样的过程。由于节点的数量是有限的，某些节点最终会被第二次访问。这时，我们就找到了一个有向循环，循环中的每个弧都携带正流量。让

f^{1}

成为简单循环

Figure 7.18: Illustration of the flow decomposition theorem. The numbers next to each arc indicate the value of the corresponding arc flows. Arcs with zero flow are not shown. (a) A nonnegative circulation

f

. (b) The circulation

a_{1} f^{1}

f - a_{1} f^{1}

. (d) The circulation

a_{2} f^{2}

. (e) The remaining flow

f - a_{1} f^{1} - a_{2} f^{2}

is a simple circulation and we let

a_{3} f^{3}

be equal to it.
图 7.18：流量分解定理图解。每个弧旁边的数字表示相应弧的流量值。流量为零的弧未显示。(a) 非负循环

f

。(b) 循环

a_{1} f^{1}

。(c) 剩余流量

f - a_{1} f^{1}

。(d) 循环

a_{2} f^{2}

。(e) 剩余流

f - a_{1} f^{1} - a_{2} f^{2}

是简单环流，我们让

a_{3} f^{3}

与之相等。
corresponding to that cycle. Let

a_{1}

be the minimum value of

f_{i j}

, where the minimum is taken over all arcs in the cycle, and consider the vector

\hat{f} = f - a_{1} f^{1}

. This vector is nonnegative because of the way that

a_{1}

was chosen. In addition, we have

A f = 0

and

A f^{1} = 0

, which implies that

A \hat{f} = 0

and

\hat{f}

is a circulation. By the definition of

a_{1}

, there exists some arc

(k, ℓ)

on the cycle for which

f_{k ℓ} = a_{1}

and

{\hat{f}}_{k ℓ} = 0

. Therefore, the number of positive components of

\hat{f}

is smaller than the number of positive components of

f

. We can now apply the same procedure to

\hat{f}

, to obtain a new simple circulation

f^{2}

, and continue similarly. Each time, the number of arcs that carry positive flow is reduced by at least one. Thus, after repeating this procedure a finite number of times, we end up with the zero flow. When this happens, we have succeeded in decomposing

f

as a nonnegative linear combination of simple circulations. Furthermore, since all of the cycles constructed were directed, these simple circulations involve only forward arcs.
对应于该循环。假设

a_{1}

是

f_{i j}

的最小值，最小值取自循环中的所有弧，并考虑向量

\hat{f} = f - a_{1} f^{1}

。由于选择

a_{1}

的方式，该向量是非负的。此外，我们还有

A f = 0

和

A f^{1} = 0

，这意味着

A \hat{f} = 0

和

\hat{f}

是一个循环。根据

a_{1}

的定义，在循环上存在某个弧

(k, ℓ)

，对其而言，

f_{k ℓ} = a_{1}

和

{\hat{f}}_{k ℓ} = 0

.因此，

\hat{f}

的正分量数小于

f

的正分量数。现在，我们可以对

\hat{f}

应用相同的程序，得到新的简单循环

f^{2}

，并继续类似的操作。每次，携带正向流的弧的数量都会减少至少一条。因此，在重复这一过程一定次数后，我们最终会得到零流量。当这种情况发生时，我们就成功地将

f

分解为简单循环的非负线性组合。此外，由于构建的所有循环都是有向的，因此这些简单循环只涉及前向弧线。

f

is integer, then

a_{1}

is integer, and

\hat{f}

is also an integer vector. It follows, by induction, that if we start with an integer flow vector

f

, all flows produced in the course of the above procedure are integer, and all coefficients

a_{i}

are also integer. This concludes the proof of Lemma 7.1.

◻

如果

f

是整数，那么

a_{1}

也是整数，而

\hat{f}

也是整数向量。根据归纳法，如果我们从一个整数流量向量

f

开始，那么在上述过程中产生的所有流量都是整数，所有系数

a_{i}

也都是整数。定理 7.1 的证明到此为止。

◻

We now apply Lemma 7.1 to the residual network. The circulation

\tilde{f}

can be decomposed in the form
现在，我们将定理 7.1 应用于残差网络。循环

\tilde{f}

可以分解为以下形式

\tilde{f} = \sum_{i} a_{i} {\tilde{f}}^{i}

where each

{\tilde{f}}^{i}

is a simple circulation involving only forward arcs, and each

a_{i}

is positive. Since

\tilde{f}

has negative cost, at least one of the circulations

{\tilde{f}}^{i}

must also have negative cost; hence, the residual network has a negative cost directed cycle. As discussed in the preceding subsection, this implies that the original network contains a negative cost unsaturated cycle, and the proof of Theorem 7.6 is now complete.
其中每个

{\tilde{f}}^{i}

都是只涉及正向弧的简单循环，而每个

a_{i}

都是正循环。由于

\tilde{f}

的成本为负，因此至少有一个循环

{\tilde{f}}^{i}

的成本也必须为负；因此，残差网络有一个负成本有向循环。如上一小节所述，这意味着原始网络包含一个负成本的不饱和循环，定理 7.6 的证明至此完成。

Termination of the algorithm
终止算法

Before concluding that the algorithm is correct, we need a guarantee that it will eventually terminate. This is the subject of our next theorem.
在断定算法正确之前，我们需要保证算法最终会终止。这就是我们下一个定理的主题。

Theorem 7.7 Suppose that all arc capacities

u_{i j}

are integer or infinite, and that the negative cost cycle algorithm is initialized with an integer feasible flow. Then, the arc flow variables remain integer throughout the algorithm and, if the optimal cost is finite, the algorithm terminates with an integer optimal solution.
定理 7.7 假设所有弧流量

u_{i j}

都是整数或无限的，负成本循环算法以整数可行流量初始化。那么，在整个算法过程中，弧流变量保持整数；如果最优成本是有限的，算法将以整数最优解结束。

Termination and computational experience 终止和计算经验

Bounds on the optimal cost最佳成本的界限

6.5 Stochastic programming and Benders decomposition6.5 随机程序设计和本德斯分解

Problem formulation 问题的提出

Reformulation of the problem问题的重新表述

Delayed constraint generation延迟生成制约因素

Benders decomposition for two-stage problems两阶段问题的本德尔分解

6.6 Summary 6.6 小结

6.7 Exercises 6.7 练习

6.8 Notes and sources 6.8 说明和资料来源

Chapter 7 第 7 章

Network flow problems 网络流量问题

Contents 目录

7.1. Graphs 7.1.图表

7.1 Graphs 7.1 图表

Undirected graphs 无向图

Directed graphs 有向图

Trees 树木

Theorem 7.1 定理 7.1

Proof. 证明。

Spanning trees 跨接树

7.2 Formulation of the network flow problem7.2 网络流量问题的提出

The shortest path problem最短路径问题

The maximum flow problem 最大流量问题

The transportation problem交通问题

The assignment problem 分配问题

Variants of the network flow problem网络流量问题的变体

A concise formulation 简明表述

Circulations 流通

7.3 The network simplex algorithm7.3 网络单纯形算法

Assumption 7.1 假设 7.1

Trees and basic feasible solutions树和基本可行方案

Definition 7.1 A flow vector f is called a tree solution if it can be constructed by the following procedure.定义 7.1 如果一个流矢量 f 可以通过以下步骤构建，则称其为树状解。

Theorem 7.4 A flow vector is a basic solution if and only if it is a tree solution.定理 7.4 当且仅当一个流矢是一个树解时，它才是一个基本解。

Change of basis 更改依据

Calculation of the cost change费用变化的计算

Overview of the algorithm算法概述

The simplex method for uncapacitated network flow problems无容限网络流问题的单纯形法

Integrality of optimal solutions最优解的整体性

Theorem 7.5 Consider an uncapacitated network flow problem and assume that the underlying graph is connected.定理 7.5 考虑无容错网络流量问题，假设底层图是连通的。

Proof. 证明。

Corollary 7.2 Consider an uncapacitated network flow problem, and assume that the optimal cost is finite.推论 7.2 考虑一个无容限网络流量问题，假设最优成本是有限的。

The simplex method for capacitated problems容量问题的单纯形法

The simplex method for capacitated network flow problems容量网络流问题的单纯形法

7.4 The negative cost cycle algorithm7.4 负成本循环算法

Motivation 动机

Description of the algorithm算法说明

Negative cost cycle algorithm负成本循环算法

Starting the algorithm 启动算法

The residual network 残差网络

Optimality conditions 优化条件

Theorem 7.6 A feasible flow f is optimal if and only if there is no unsaturated cycle with negative cost.定理 7.6 当且仅当不存在成本为负的不饱和循环时，可行流 f 才是最优的。

Termination of the algorithm终止算法

Termination and computational experience
终止和计算经验

Bounds on the optimal cost
最佳成本的界限

6.5 Stochastic programming and Benders decomposition
6.5 随机程序设计和本德斯分解

Reformulation of the problem
问题的重新表述

Delayed constraint generation
延迟生成制约因素

Benders decomposition for two-stage problems
两阶段问题的本德尔分解

7.2 Formulation of the network flow problem
7.2 网络流量问题的提出

The shortest path problem
最短路径问题

The transportation problem
交通问题

Variants of the network flow problem
网络流量问题的变体

7.3 The network simplex algorithm
7.3 网络单纯形算法

Trees and basic feasible solutions
树和基本可行方案

Definition 7.1 A flow vector f is called a tree solution if it can be constructed by the following procedure.
定义 7.1 如果一个流矢量 f 可以通过以下步骤构建，则称其为树状解。

Theorem 7.4 A flow vector is a basic solution if and only if it is a tree solution.
定理 7.4 当且仅当一个流矢是一个树解时，它才是一个基本解。

Calculation of the cost change
费用变化的计算

Overview of the algorithm
算法概述

The simplex method for uncapacitated network flow problems
无容限网络流问题的单纯形法

Integrality of optimal solutions
最优解的整体性

Theorem 7.5 Consider an uncapacitated network flow problem and assume that the underlying graph is connected.
定理 7.5 考虑无容错网络流量问题，假设底层图是连通的。

Corollary 7.2 Consider an uncapacitated network flow problem, and assume that the optimal cost is finite.
推论 7.2 考虑一个无容限网络流量问题，假设最优成本是有限的。

The simplex method for capacitated problems
容量问题的单纯形法

The simplex method for capacitated network flow problems
容量网络流问题的单纯形法

7.4 The negative cost cycle algorithm
7.4 负成本循环算法

Description of the algorithm
算法说明

Negative cost cycle algorithm
负成本循环算法

Theorem 7.6 A feasible flow f is optimal if and only if there is no unsaturated cycle with negative cost.
定理 7.6 当且仅当不存在成本为负的不饱和循环时，可行流 f 才是最优的。

Termination of the algorithm
终止算法