神经网络的最优权重怎么计算（优化基于网络单纯形法求解的最小流费用问题）

『运筹OR帷幄』转载

文章作者：休语

编者按：本文整理自休语的知乎文章，文章主要围绕最小流问题进行阐述，结构主要为问题描述，模型建立，解的性质，特殊案例及网络单纯形法的求解。

问题描述

（1）网络：有向且连通。

（2）边：根据边上的流量，我们可以分为

• 最大流问题：容量限制
• 最短路径问题：费用作为边的权重

（3）节点：至少有一个（可以有多个）节点是供应点（supply node）或者需求点（demand node）

（4）其他：

• 弧的容量充分，支持供应点到需求点的所有流
• 每条弧上的费用与流量成正比。

（5）目标：给定需求，通过网络发送的总成本最小。

输入整个网络的流量是不变的，但是中间节点可以看成是处理设施，处理的费用累加在边的运输费用上。

模型建立

解的性质

因为cost

不在约束里面，所以所有BF解都是整数解只要求约束中出现的两类量为整数，即

和

为整数。

特殊案例

以下四个问题是特殊的最小费用流问题

• 运输问题：没有中间节点，边的流量没有上界约束。
• 指派问题：每个节点的 为 1或-1
• 转运问题（Transshipment Problem）：没有上界约束
• 最短路径问题：
• 除了起点（source）出发和汇入目的地（target）的边，其它边变成双向边
• 距离是cost ，没有容量（capacity）限制

• 最大流问题
• 不考虑费用，
• 选一个网络最大流量的上界 ，设Supply node为 ，demand node为
• 从supply node到demand node画一条“分流线”，分走多出来的流量 。“分流线”的 ，容量无穷大。

具体案例

前面我们已经对最小流费用问题做了简单的叙述，对于这类问题到底如何解，下面我们对一种经典解法进行描述，即网络单纯性法。

基础：上界法（Upper Bound Technique）

在运筹学建模中，我们经常有约束

。通常地，把该约束当做非负约束（nonnegative constraints）处理，会比当成函数式约束（functional constraints）处理节省计算量。我们可以做如下替换：

经过上述处理后，单纯形法中出基条件则变为了超出上界或者下界。当入基变量不断增大以至于某个

达到上界

时，用

替换。

那么上界法和最小费用流问题有什么联系呢？最小费用流问题中的约束通常分有两种：节点约束和边约束。节点约束是函数式约束，通常可以表示为

，边约束表示为

。我们可以用上界法对约束进行转换，提高计算效率。

网络单纯形法——上界法转换

网络单纯形状法和上界法的思路类似。对于

这样的增补决策变量（complementary decision variables）有一个很好的解释，如下图所示。

如下公式所示，

和

的变化其实就是上界法中把

代入到

，导致等式右侧

的变化。

最终网络流如下图所示：

是从i到j能够减少的流量，

是表示每减少单位流量，就能节省

的成本，

的上界

，是因为最多只能减少10（

流量分配了10）。

如上所述，只适用于有上界约束的情况，对于边上的流量没有上界约束的情况来说没有必要。

网络单纯形法——求解

对一个网络图来说，找到一个生成树就是找到了一组基解。

将非基变量置为0，可以解出每条弧上的流量，满足

和

的生成树就是可行生成树，对应基可行解。

网络单纯形法计算示例：

入基变量的选择

那么在求解中，哪个非基变量从0开始增加，会使得目标函数Z增加得最快？且在网络单纯形法中，每增加一个非基变量（一个arc），会形成一个环。环中同向arc增大，反向arc减小。如下图所示：

对这个变化，求一个整体的变化量

。对于每个可以加入的arc，找到这样的一个环，假设入基arc增加的流量为

，看整体的

是多少。其中能够增加单位流量，

下降最大的非基变量（arc）是我们需要选择的。

迭代选择出基变量和下一个可行解。注意，根据上界法，当某一条arc达到上界时，通过

代换得到反向arc，这样

，正常出基。

原文链接

https://zhuanlan.zhihu.com/p/73401547

https://zhuanlan.zhihu.com/p/73527137

,