这是用户在 2024-10-30 21:37 为 https://app.immersivetranslate.com/pdf-pro/209779ac-5642-4274-a18a-819770d6786e 保存的双语快照页面,由 沉浸式翻译 提供双语支持。了解如何保存?
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 b D 1 x 1 1 + D 2 x 2 1 b D_(1)x_(1)^(1)+D_(2)x_(2)^(1) <= b\mathbf{D}_{1} \mathbf{x}_{1}^{1}+\mathbf{D}_{2} \mathbf{x}_{2}^{1} \leq \mathbf{b}. Let y y y\mathbf{y} be a vector of auxiliary variables of dimension m 0 m 0 m_(0)m_{0}. We form the auxiliary master problem
分别为通过将某些耦合约束条件的两边乘以-1,我们可以假设 D 1 x 1 1 + D 2 x 2 1 b D 1 x 1 1 + D 2 x 2 1 b D_(1)x_(1)^(1)+D_(2)x_(2)^(1) <= b\mathbf{D}_{1} \mathbf{x}_{1}^{1}+\mathbf{D}_{2} \mathbf{x}_{2}^{1} \leq \mathbf{b} 。让 y y y\mathbf{y} 成为维数为 m 0 m 0 m_(0)m_{0} 的辅助变量向量。我们形成辅助主问题
minimize t = 1 m 0 y t subject to i = 1 , 2 ( j J i λ i j D i x i j + k K i θ i k D i w i k ) + y = b 0 j J 1 λ 1 j = 1 j J 2 λ 2 j = 1 λ i j 0 , θ i k 0 , y t 0 , i , j , k , t . minimize t = 1 m 0 y t  subject to  i = 1 , 2 j J i λ i j D i x i j + k K i θ i k D i w i k + y = b 0 j J 1 λ 1 j = 1 j J 2 λ 2 j = 1 λ i j 0 , θ i k 0 , y t 0 , i , j , k , t . {:[minimizesum_(t=1)^(m_(0))y_(t)],[" subject to "sum_(i=1,2)(sum_(j inJ_(i))lambda_(i)^(j)D_(i)x_(i)^(j)+sum_(k inK_(i))theta_(i)^(k)D_(i)w_(i)^(k))+y=b_(0)],[sum_(j inJ_(1))lambda_(1)^(j)=1],[sum_(j inJ_(2))lambda_(2)^(j)=1],[lambda_(i)^(j) >= 0","theta_(i)^(k) >= 0","y_(t) >= 0","quad AA i","j","k","t.]:}\begin{aligned} \operatorname{minimize} & \sum_{t=1}^{m_{0}} y_{t} \\ \text { subject to } & \sum_{i=1,2}\left(\sum_{j \in J_{i}} \lambda_{i}^{j} \mathbf{D}_{i} \mathbf{x}_{i}^{j}+\sum_{k \in K_{i}} \theta_{i}^{k} \mathbf{D}_{i} \mathbf{w}_{i}^{k}\right)+\mathbf{y}=\mathbf{b}_{0} \\ & \sum_{j \in J_{1}} \lambda_{1}^{j}=1 \\ & \sum_{j \in J_{2}} \lambda_{2}^{j}=1 \\ & \lambda_{i}^{j} \geq 0, \theta_{i}^{k} \geq 0, y_{t} \geq 0, \quad \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 λ 1 1 = λ 2 1 = 1 , λ i j = 0 lambda_(1)^(1)=lambda_(2)^(1)=1,lambda_(i)^(j)=0\lambda_{1}^{1}=\lambda_{2}^{1}=1, \lambda_{i}^{j}=0 for j 1 , θ i k = 0 j 1 , θ i k = 0 j!=1,theta_(i)^(k)=0j \neq 1, \theta_{i}^{k}=0 for all k k kk, and y = b 0 D 1 x 1 1 D 2 x 2 1 y = b 0 D 1 x 1 1 D 2 x 2 1 y=b_(0)-D_(1)x_(1)^(1)-D_(2)x_(2)^(1)\mathbf{y}=\mathbf{b}_{0}-\mathbf{D}_{1} \mathbf{x}_{1}^{1}-\mathbf{D}_{2} \mathbf{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 k kk y = b 0 D 1 x 1 1 D 2 x 2 1 y = b 0 D 1 x 1 1 D 2 x 2 1 y=b_(0)-D_(1)x_(1)^(1)-D_(2)x_(2)^(1)\mathbf{y}=\mathbf{b}_{0}-\mathbf{D}_{1} \mathbf{x}_{1}^{1}-\mathbf{D}_{2} \mathbf{x}_{2}^{1} 的情况下,让 λ 1 1 = λ 2 1 = 1 , λ i j = 0 λ 1 1 = λ 2 1 = 1 , λ i j = 0 lambda_(1)^(1)=lambda_(2)^(1)=1,lambda_(i)^(j)=0\lambda_{1}^{1}=\lambda_{2}^{1}=1, \lambda_{i}^{j}=0 对于 j 1 , θ i k = 0 j 1 , θ i k = 0 j!=1,theta_(i)^(k)=0j \neq 1, \theta_{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 t tt subproblems, each one having the same number m 1 m 1 m_(1)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 ) O m 0 + t m 1 2 O((m_(0)+tm_(1))^(2))O\left(\left(m_{0}+t m_{1}\right)^{2}\right), which is the size of the revised simplex tableau. In contrast, the storage requirements of the decomposition algorithm are O ( ( m 0 + t ) 2 ) O m 0 + t 2 O((m_(0)+t)^(2))O\left(\left(m_{0}+t\right)^{2}\right) for the tableau of the master problem, and t t tt times O ( m 1 2 ) O m 1 2 O(m_(1)^(2))O\left(m_{1}^{2}\right) 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 t = 10 t=10t=10 and if m 0 = m 1 m 0 = m 1 m_(0)=m_(1)m_{0}=m_{1} is much larger than t t tt, 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 t tt 个子问题,每个子问题都有相同数量的 m 1 m 1 m_(1)m_{1} 个相等约束。修正单纯形法对原始问题的存储需求为 O ( ( m 0 + t m 1 ) 2 ) O m 0 + t m 1 2 O((m_(0)+tm_(1))^(2))O\left(\left(m_{0}+t m_{1}\right)^{2}\right) ,即修正单纯形表的大小。相比之下,分解算法对主问题表象的存储需求为 O ( ( m 0 + t ) 2 ) O m 0 + t 2 O((m_(0)+t)^(2))O\left(\left(m_{0}+t\right)^{2}\right) ,对子问题的修正单纯形表象的存储需求为 t t tt 乘以 O ( m 1 2 ) O m 1 2 O(m_(1)^(2))O\left(m_{1}^{2}\right) 。此外,分解算法在任何时候都只需在主内存中存储一个表元。例如,如果 t = 10 t = 10 t=10t=10 m 0 = m 1 m 0 = m 1 m_(0)=m_(1)m_{0}=m_{1} 远大于 t t tt ,分解算法所需的主内存大约是修正单纯形法的 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 z z^(**)z^{*} is finite. Let z z zz be the cost of the feasible solution obtained at some intermediate stage of the decomposition algorithm. Also, let r i r i r_(i)r_{i} be the value of the dual variable associated with the convexity constraint for the ith subproblem. Finally, let z i z i z_(i)z_{i} be the optimal cost in the ith subproblem, assumed finite. Then,
定理 6.1 假设主问题是可行的,且其最优成本 z z z^(**)z^{*} 是有限的。设 z z zz 是在分解算法的某个中间阶段得到的可行解的成本。同时,设 r i r i r_(i)r_{i} 为第 i 个子问题中与凸性约束相关的对偶变量的值。最后,设 z i z i z_(i)z_{i} 为第 i 个子问题的最优成本,假定为有限成本。那么
z + i ( z i r i ) z z z + i z i r i z z z+sum_(i)(z_(i)-r_(i)) <= z^(**) <= zz+\sum_{i}\left(z_{i}-r_{i}\right) \leq z^{*} \leq z
Proof. The inequality z z z z z^(**) <= zz^{*} \leq z is obvious, since z z zz 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 z z z z^(**) <= zz^{*} \leq z 是显而易见的,因为 z z zz 是与原问题的可行解相关的成本。剩下的就是证明定理说明中左侧的不等式。
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
一般情况也类似。主问题的对偶关系为
maximize q b 0 + r 1 + r 2 subject to q D 1 x 1 j + r 1 c 1 x 1 j , j J 1 , q D 1 w 1 k c 1 w 1 k , k K 1 , q D 2 x 2 j + r 2 c 2 x 2 j , j J 2 , q D 2 w 2 k c 2 w 2 k , k K 2 . maximize q b 0 + r 1 + r 2  subject to  q D 1 x 1 j + r 1 c 1 x 1 j , j J 1 , q D 1 w 1 k c 1 w 1 k , k K 1 , q D 2 x 2 j + r 2 c 2 x 2 j , j J 2 , q D 2 w 2 k c 2 w 2 k , k K 2 . {:[maximize,q^(')b_(0)+r_(1)+r_(2),,],[" subject to ",q^(')D_(1)x_(1)^(j)+r_(1), <= c_(1)^(')x_(1)^(j)",",AA j inJ_(1)","],[,q^(')D_(1)w_(1)^(k), <= c_(1)^(')w_(1)^(k)",",AA k inK_(1)","],[,q^(')D_(2)x_(2)^(j)+r_(2) <= c_(2)^(')x_(2)^(j)",",AA j inJ_(2)","],[,q^(')D_(2)w_(2)^(k), <= c_(2)^(')w_(2)^(k)",",AA k inK_(2).]:}\begin{array}{rlrl} \operatorname{maximize} & \mathbf{q}^{\prime} \mathbf{b}_{0}+r_{1}+r_{2} & & \\ \text { subject to } & \mathbf{q}^{\prime} \mathbf{D}_{1} \mathbf{x}_{1}^{j}+r_{1} & \leq \mathbf{c}_{1}^{\prime} \mathbf{x}_{1}^{j}, & \forall j \in J_{1}, \\ & \mathbf{q}^{\prime} \mathbf{D}_{1} \mathbf{w}_{1}^{k} & \leq \mathbf{c}_{1}^{\prime} \mathbf{w}_{1}^{k}, & \forall k \in K_{1}, \\ & \mathbf{q}^{\prime} \mathbf{D}_{2} \mathbf{x}_{2}^{j}+r_{2} \leq \mathbf{c}_{2}^{\prime} \mathbf{x}_{2}^{j}, & \forall j \in J_{2}, \\ & \mathbf{q}^{\prime} \mathbf{D}_{2} \mathbf{w}_{2}^{k} & \leq \mathbf{c}_{2}^{\prime} \mathbf{w}_{2}^{k}, & \forall k \in K_{2} . \end{array}
Suppose that we have a basic feasible solution to the master problem, with cost z cost z cost z\operatorname{cost} z, and let ( q , r 1 , r 2 q , r 1 , r 2 q,r_(1),r_(2)\mathbf{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 cost z cost z\operatorname{cost} z ,并让 ( q , r 1 , r 2 q , r 1 , r 2 q,r_(1),r_(2)\mathbf{q}, r_{1}, r_{2} ) 作为相关的单倍乘数向量。这是对偶问题的基本解(一般不可行),其代价相同,即
q b 0 + r 1 + r 2 = z q b 0 + r 1 + r 2 = z q^(')b_(0)+r_(1)+r_(2)=z\mathbf{q}^{\prime} \mathbf{b}_{0}+r_{1}+r_{2}=z
Since the optimal cost z 1 z 1 z_(1)z_{1} in the first subproblem is finite, we have
由于第一个子问题中的最优成本 z 1 z 1 z_(1)z_{1} 是有限的,所以我们有
min j J 1 ( c 1 x 1 j q D 1 x 1 j ) = z 1 min k K 1 ( c 1 w 1 k q D 1 w 1 k ) 0 min j J 1 c 1 x 1 j q D 1 x 1 j = z 1 min k K 1 c 1 w 1 k q D 1 w 1 k 0 {:[min_(j inJ_(1))(c_(1)^(')x_(1)^(j)-q^(')D_(1)x_(1)^(j))=z_(1)],[min_(k inK_(1))(c_(1)^(')w_(1)^(k)-q^(')D_(1)w_(1)^(k)) >= 0]:}\begin{aligned} \min _{j \in J_{1}}\left(\mathbf{c}_{1}^{\prime} \mathbf{x}_{1}^{j}-\mathbf{q}^{\prime} \mathbf{D}_{1} \mathbf{x}_{1}^{j}\right) & =z_{1} \\ \min _{k \in K_{1}}\left(\mathbf{c}_{1}^{\prime} \mathbf{w}_{1}^{k}-\mathbf{q}^{\prime} \mathbf{D}_{1} \mathbf{w}_{1}^{k}\right) & \geq 0 \end{aligned}
Thus, q q q\mathbf{q} together with z 1 z 1 z_(1)z_{1} in the place of r 1 r 1 r_(1)r_{1}, satisfy the first two dual constraints. By a similar argument, q q q\mathbf{q} together with z 2 z 2 z_(2)z_{2} in the place of r 2 r 2 r_(2)r_{2}, satisfy the last two dual constraints. Therefore, ( q , z 1 , z 2 ) q , z 1 , z 2 (q,z_(1),z_(2))\left(\mathbf{q}, z_{1}, z_{2}\right) is a feasible solution to the dual problem (6.14). Its cost is q b 0 + z 1 + z 2 q b 0 + z 1 + z 2 q^(')b_(0)+z_(1)+z_(2)\mathbf{q}^{\prime} \mathbf{b}_{0}+z_{1}+z_{2} and, by weak duality, is no larger than the optimal cost z z z^(**)z^{*}. Hence,
因此, q q q\mathbf{q} 连同代替 r 1 r 1 r_(1)r_{1} z 1 z 1 z_(1)z_{1} 满足前两个对偶约束条件。根据类似的论证, q q q\mathbf{q} 和代替 r 2 r 2 r_(2)r_{2} z 2 z 2 z_(2)z_{2} 满足后两个对偶约束条件。因此, ( q , z 1 , z 2 ) q , z 1 , z 2 (q,z_(1),z_(2))\left(\mathbf{q}, z_{1}, z_{2}\right) 是对偶问题 (6.14) 的可行解。其成本为 q b 0 + z 1 + z 2 q b 0 + z 1 + z 2 q^(')b_(0)+z_(1)+z_(2)\mathbf{q}^{\prime} \mathbf{b}_{0}+z_{1}+z_{2} ,根据弱对偶性,不大于最优成本 z z z^(**)z^{*} 。因此
z 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 ) z 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 {:[z^(**) >= 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))]:}\begin{aligned} z^{*} & \geq \mathbf{q}^{\prime} \mathbf{b}_{0}+z_{1}+z_{2} \\ & =\mathbf{q}^{\prime} \mathbf{b}_{0}+r_{1}+r_{2}+\left(z_{1}-r_{1}\right)+\left(z_{2}-r_{2}\right) \\ & =z+\left(z_{1}-r_{1}\right)+\left(z_{2}-r_{2}\right) \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 -oo-\infty, then Theorem 6.1 does not provide any useful bounds.
请注意,如果其中一个子问题的最优成本是 -oo-\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 q , r 1 , r 2 q,r_(1),r_(2)\mathbf{q}, r_{1}, r_{2} ), moved to the dual feasible solution ( q , z 1 , z 2 q , z 1 , z 2 (q,z_(1),z_(2):}\left(\mathbf{q}, z_{1}, z_{2}\right. ), and then invoked weak duality.
定理 6.1 的证明是获取线性规划问题最优成本下限的一般方法的一个实例,具体如下。给定一个非最优的基本可行解,我们考虑对偶问题的相应(不可行)基本解。如果我们能以某种方式修改这个对偶解,使其变得可行,那么弱对偶定理就能轻易得出一个下限。这就是定理 6.1 的证明方法,我们从一般不可行的对偶解 ( q , r 1 , r 2 q , r 1 , r 2 q,r_(1),r_(2)\mathbf{q}, r_{1}, r_{2} ) 开始,移到对偶可行解 ( q , z 1 , z 2 q , z 1 , z 2 (q,z_(1),z_(2):}\left(\mathbf{q}, z_{1}, z_{2}\right. ),然后引用弱对偶性。
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 ) λ 1 , λ 2 = ( 0.8 , 0.2 ) (lambda^(1),lambda^(2))=(0.8,0.2)\left(\lambda^{1}, \lambda^{2}\right)=(0.8,0.2). Since c B = ( 22 , 17 ) c B = ( 22 , 17 ) c_(B)=(-22,-17)\mathbf{c}_{B}=(-22,-17), we have z = ( 22 , 17 ) ( 0.8 , 0.2 ) = z = ( 22 , 17 ) ( 0.8 , 0.2 ) = z=(-22,-17)^(')(0.8,0.2)=z=(-22,-17)^{\prime}(0.8,0.2)= -21 . We also have r = 4 r = 4 r=-4r=-4. Finally, the optimal cost in the subproblem is ( 1 , 1 , 2 ) ( 2 , 1 , 2 ) = 5 ( 1 , 1 , 2 ) ( 2 , 1 , 2 ) = 5 (-1,1,-2)^(')(2,1,2)=-5(-1,1,-2)^{\prime}(2,1,2)=-5. It follows that 21 z 21 + ( 5 ) ( 4 ) = 22 21 z 21 + ( 5 ) ( 4 ) = 22 -21 >= z^(**) >= -21+(-5)-(-4)=-22-21 \geq z^{*} \geq-21+(-5)-(-4)=-22. Indeed, the true value of z z z^(**)z^{*} is -21.5 .
( λ 1 , λ 2 ) = ( 0.8 , 0.2 ) λ 1 , λ 2 = ( 0.8 , 0.2 ) (lambda^(1),lambda^(2))=(0.8,0.2)\left(\lambda^{1}, \lambda^{2}\right)=(0.8,0.2) 。由于 c B = ( 22 , 17 ) c B = ( 22 , 17 ) c_(B)=(-22,-17)\mathbf{c}_{B}=(-22,-17) ,我们有 z = ( 22 , 17 ) ( 0.8 , 0.2 ) = z = ( 22 , 17 ) ( 0.8 , 0.2 ) = z=(-22,-17)^(')(0.8,0.2)=z=(-22,-17)^{\prime}(0.8,0.2)= -21 。我们还有 r = 4 r = 4 r=-4r=-4 。最后,子问题中的最优成本为 ( 1 , 1 , 2 ) ( 2 , 1 , 2 ) = 5 ( 1 , 1 , 2 ) ( 2 , 1 , 2 ) = 5 (-1,1,-2)^(')(2,1,2)=-5(-1,1,-2)^{\prime}(2,1,2)=-5 。由此可知, 21 z 21 + ( 5 ) ( 4 ) = 22 21 z 21 + ( 5 ) ( 4 ) = 22 -21 >= z^(**) >= -21+(-5)-(-4)=-22-21 \geq z^{*} \geq-21+(-5)-(-4)=-22 。事实上, z z z^(**)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 x x\mathbf{x}. Subsequently, some new information is obtained, and then, at the second stage, a new vector y y yy of decisions is to be chosen. Regarding the nature of the obtained information, we assume that there are K K KK possible scenarios, and that the true scenario is only revealed after x x x\mathbf{x} is chosen. We use ω ω omega\omega to index the different scenarios, and we let α ω α ω alpha_(omega)\alpha_{\omega} stand for the probability of any particular scenario ω ω omega\omega, which we assume to be positive. Since the second stage decisions are made after the true scenario ω ω omega\omega becomes known, we allow the decision vector y y y\mathbf{y} to depend on ω ω omega\omega, and we use the notation y ω y ω y_(omega)\mathbf{y}_{\omega} to make this dependence explicit.
考虑一个必须在两个连续阶段采取行动的决策者。第一阶段涉及选择一个决策向量 x x x\mathbf{x} 。随后,会获得一些新信息,然后在第二阶段,需要选择一个新的决策向量 y y yy 。关于所获信息的性质,我们假设有 K K KK 种可能的情况,而真实情况只有在选择 x x x\mathbf{x} 之后才会揭示。我们用 ω ω omega\omega 来表示不同的情况,用 α ω α ω alpha_(omega)\alpha_{\omega} 表示任何特定情况的概率 ω ω omega\omega ,我们假设该概率为正值。由于第二阶段的决策是在已知真实情况 ω ω omega\omega 之后做出的,因此我们允许决策向量 y y y\mathbf{y} 取决于 ω ω omega\omega ,我们使用符号 y ω y ω y_(omega)\mathbf{y}_{\omega} 来明确表示这种依赖关系。
We now make more specific assumptions on the problem objectives and constraints. We are given cost vectors c c c\mathbf{c} and f f f\mathbf{f}, associated with the decisions x x x\mathbf{x} and y ω y ω y_(omega)\mathbf{y}_{\omega}, respectively. The first stage decisions must satisfy the constraints
现在,我们对问题的目标和约束条件做出更具体的假设。我们给定了成本向量 c c c\mathbf{c} f f f\mathbf{f} ,分别与决策 x x x\mathbf{x} y ω y ω y_(omega)\mathbf{y}_{\omega} 相关联。第一阶段的决策必须满足以下约束条件
A x = b x 0 A x = b x 0 {:[Ax=b],[x >= 0]:}\begin{aligned} \mathbf{A x} & =\mathbf{b} \\ \mathbf{x} & \geq \mathbf{0} \end{aligned}
In addition, the first and second stage decisions need to satisfy constraints of the form
此外,第一和第二阶段的决策需要满足以下形式的约束条件
B ω x + D y ω = d ω y ω 0 B ω x + D y ω = d ω y ω 0 {:[B_(omega)x+Dy_(omega)=d_(omega)],[y_(omega) >= 0]:}\begin{aligned} \mathbf{B}_{\omega} \mathbf{x}+\mathbf{D} \mathbf{y}_{\omega} & =\mathbf{d}_{\omega} \\ \mathbf{y}_{\omega} & \geq \mathbf{0} \end{aligned}
for all ω ω omega\omega; in particular, every scenario may involve a different set of constraints. The objective is to choose x x x\mathbf{x} and y 1 , , y K y 1 , , y K y_(1),dots,y_(K)\mathbf{y}_{1}, \ldots, \mathbf{y}_{K} so that the “expected cost”
对于所有 ω ω omega\omega ;特别是,每个方案都可能涉及一组不同的约束条件。我们的目标是选择 x x x\mathbf{x} y 1 , , y K y 1 , , y K y_(1),dots,y_(K)\mathbf{y}_{1}, \ldots, \mathbf{y}_{K} ,从而使 "预期成本"
c x + α 1 f y 1 + + α K f y K c x + α 1 f y 1 + + α K f y K c^(')x+alpha_(1)f^(')y_(1)+cdots+alpha_(K)f^(')y_(K)\mathbf{c}^{\prime} \mathbf{x}+\alpha_{1} \mathbf{f}^{\prime} \mathbf{y}_{1}+\cdots+\alpha_{K} \mathbf{f}^{\prime} \mathbf{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 K KK is moderate, this formulation can be a large linear programming problem. For this reason, a decomposition method is in order.
将被称为主问题。请注意,即使可能出现的情况 K K KK 数量适中,这一表述也可能是一个庞大的线性规划问题。因此,需要采用分解方法。
Example 6.5 (Electric power capacity expansion) An electric utility is installing two generators (indexed by j = 1 , 2 j = 1 , 2 j=1,2j=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 i = 1 , 2 , 3 i=1,2,3i=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 j jj is amortized over its lifetime and amounts to c j c j c_(j)c_{j} per day. The operating cost of generator j j jj during the i i ii th part of the day is f i j f i j f_(ij)f_{i j}. If the demand during the i i ii th part of the day cannot be served due to lack of capacity, additional capacity must be purchased at a cost of g i g i g_(i)g_{i}. Finally, the capacity of each generator j j jj is required to be at least b j b j b_(j)b_{j}.
例 6.5(电力容量扩展)某电力公司正在安装两台固定成本和运营成本不同的发电机(以 j = 1 , 2 j = 1 , 2 j=1,2j=1,2 为指标),以满足其服务区域内的需求。每天被划分为持续时间相同的三个部分,以 i = 1 , 2 , 3 i = 1 , 2 , 3 i=1,2,3i=1,2,3 为索引。这三个部分分别对应一天中需求量为基本值、中等值或高峰值的时段。发电机 j j jj 的单位容量固定成本在其使用期内摊销,每天为 c j c j c_(j)c_{j} 。发电机 j j jj i i ii 日期间的运行成本为 f i j f i j f_(ij)f_{i j} 。如果 i i ii 日间的需求因发电能力不足而无法满足,则必须购买额外的发电能力,费用为 g i g i g_(i)g_{i} 。最后,要求每台发电机 j j jj 的容量至少为 b j b j b_(j)b_{j}
There are two sources of uncertainty, namely, the exact value of the demand d i d i d_(i)d_{i} during each part of the day, and the availability a j a j a_(j)a_{j} of generator j j jj. The demand d i d i d_(i)d_{i} can take one of four values d i , 1 , , d i , 4 d i , 1 , , d i , 4 d_(i,1),dots,d_(i,4)d_{i, 1}, \ldots, d_{i, 4}, with probability p i , 1 , , p i , 4 p i , 1 , , p i , 4 p_(i,1),dots,p_(i,4)p_{i, 1}, \ldots, p_{i, 4}, respectively. The availability of generator 1 is a 1 , 1 , , a 1 , 4 a 1 , 1 , , a 1 , 4 a_(1,1),dots,a_(1,4)a_{1,1}, \ldots, a_{1,4}, with probability q 1 , 1 , , q 1 , 4 q 1 , 1 , , q 1 , 4 q_(1,1),dots,q_(1,4)q_{1,1}, \ldots, q_{1,4}, respectively. Similarly, the availability of generator 2 is a 2 , 1 , , a 2 , 5 a 2 , 1 , , a 2 , 5 a_(2,1),dots,a_(2,5)a_{2,1}, \ldots, a_{2,5}, with probability q 2 , 1 , , q 2 , 5 q 2 , 1 , , q 2 , 5 q_(2,1),dots,q_(2,5)q_{2,1}, \ldots, q_{2,5}, respectively. If we enumerate all the possible events, we see that there is a total of 4 3 × 4 × 5 = 1280 4 3 × 4 × 5 = 1280 4^(3)xx4xx5=12804^{3} \times 4 \times 5=1280 scenarios ω ω omega\omega. Let us use d i ω d i ω d_(i)^(omega)d_{i}^{\omega} and a j ω a j ω a_(j)^(omega)a_{j}^{\omega} to denote the demands and availabilities, respectively, under scenario ω ω omega\omega.
不确定因素有两个,即一天中每个时段的需求量 d i d i d_(i)d_{i} 的准确值,以及发电机 j j jj 的可用性 a j a j a_(j)a_{j} 。需求量 d i d i d_(i)d_{i} 可以取四个值之一 d i , 1 , , d i , 4 d i , 1 , , d i , 4 d_(i,1),dots,d_(i,4)d_{i, 1}, \ldots, d_{i, 4} ,概率分别为 p i , 1 , , p i , 4 p i , 1 , , p i , 4 p_(i,1),dots,p_(i,4)p_{i, 1}, \ldots, p_{i, 4} 。发电机 1 的可用性为 a 1 , 1 , , a 1 , 4 a 1 , 1 , , a 1 , 4 a_(1,1),dots,a_(1,4)a_{1,1}, \ldots, a_{1,4} ,概率分别为 q 1 , 1 , , q 1 , 4 q 1 , 1 , , q 1 , 4 q_(1,1),dots,q_(1,4)q_{1,1}, \ldots, q_{1,4}