在上一篇 Congested network笔记(1) 里，我们提到了均衡解和优化解。其中均衡解是指对每一个流量的花费最少，即user-optimal，用户最优。优化解则是站在全局的角度考虑，提出的系统最优。

这里仍以之前出现过的网络作为例子，

对于它的均衡解，我们有

$$\left\{\begin{align}\mathcal{C}_{p^*_1}&=\lambda &\text{if }p^*_1\gt0\\
&\ge\lambda &\text{if }p^*_1=0\\
\mathcal{C}_{p^*_2}&=\lambda &\text{if }p^*_2\gt0\\
&\ge\lambda &\text{if }p^*_2=0\end{align}\right.\tag{1}$$

现在我们使用向量\(\mathcal{P}^*\)，它的各分量表示均衡解时，每条路径上的流量。同时用向量\(\mathcal{P}\)来表示第i路径上的流量\(\mathcal{P}_i\)，这里的\(\mathcal{P}_i\)是变量，既可以是均衡时的流量，也可以是还未均衡时的。

$$\mathcal{C}_{p^*}=\left(\begin{array}\mathcal{C}_{p^*_1}\\
\mathcal{C}_{p^*_2}\\
\vdots\\
\mathcal{C}_{p^*_{n_w}}\end{array}\right)\quad\mathcal{P}=\left(\begin{array}\mathcal{P}_1\\
\mathcal{P}_2\\
\vdots\\
\mathcal{P}_{n_w}\end{array}\right)$$

当然，它们都必须满足最基本的条件，\(\mathcal{P}_i\ge 0\)且对于给定的源点/终点对\(w\)来说，\(\sum_i\mathcal{P}_i=d_w\)。我们把所有满足这些条件的向量\(\mathcal{P}\)的空间称为可行集，feasible set，\(\mathcal{S}\)。

结合(1)式，我们知道对于任意\(\mathcal{P}_i\)有

$$(\mathcal{C}_{p^*_i}-\lambda)\ge 0\tag{2}$$

然后我们分类讨论，当\(\mathcal{P}^*_i=0\)时

$$\left\{\begin{align}(\mathcal{C}_{p^*_i}-\lambda)&\gt 0\\
\mathcal{P}_i-\mathcal{P}^*_i&\ge 0\end{align}\right.\tag{3}$$

当\(\mathcal{P}^*_i\not=0\)时

$$(\mathcal{C}_{p^*_i}-\lambda)= 0\tag{4}$$

综合(3), (4)我们发现对可行集\(\mathcal{S}\)中的任意向量\(\mathcal{P}\)都有如下不等式

$$(\mathcal{C}_{p^*}-\lambda)\cdot(\mathcal{P}-\mathcal{P}^*)\ge 0\quad\forall{\mathcal{P}\in \mathcal{S}}\tag{5}$$

由(3), (4)我们知道\(\mathcal{C}_p{^*}\ge\lambda\gt 0\)，那么可以将(5)改写为

$$\mathcal{C}_{p^*}\cdot(\mathcal{P}-\mathcal{P}^*)\ge 0\quad\forall{\mathcal{P}\in \mathcal{S}}\tag{6}$$

那么此时我们的问题就变成了对不等式的求解了。

并且如果我们把它转换到线段上时，这个不等式仍是成立的。我们使用向量\(\mathcal{F}\)来定义各线段上的流量，使用\(\mathcal{F}^*\)来表示均衡时，各线段上的流量。

$$\mathcal{F}=\left(\begin{array}{}f_1\\
f_2\\
\vdots\\
f_{n_{\mathcal{L}}}\end{array}\right)\quad\mathcal{F}^*=\left(\begin{array}{}f^*_1\\
f^*_2\\
\vdots\\
f^*_{n_\mathcal{L}}\end{array}\right)$$

仍使用上图的例子，我们知道路径上的花费是这条路径所使用的各线段上的花费之和。

$$\left\{\begin{align}\mathcal{C}_{p^*_1}&=\mathcal{C}^*_1+\mathcal{C}^*_3\\
\mathcal{C}_{p^*_2}&=\mathcal{C}^*_2+\mathcal{C}^*_3\end{align}\right.\tag{7}$$

根据(7)式，我们有

$$\left\{\begin{align}\mathcal{C}_{p^*_1}(\mathcal{P}_1-\mathcal{P}^*_1)\ge 0\\
\mathcal{C}_{p^*_2}(\mathcal{P}_2-\mathcal{P}^*_2)\ge 0\end{align}\right.$$

即

$$\mathcal{C}_{p^*_1}(\mathcal{P}_1-\mathcal{P}^*_1) + \mathcal{C}_{p^*_2}(\mathcal{P}_2-\mathcal{P}^*_2)\ge 0\tag{8}$$

将(7)式带入(8)有

$$\begin{align}&(\mathcal{C}^*_1+\mathcal{C}^*_3)(\mathcal{P}_1-\mathcal{P}^*_1)+(\mathcal{C}^*_2+\mathcal{C}^*_3)(\mathcal{P}_2-\mathcal{P}^*_2)\\
&=(\mathcal{C}^*_1+\mathcal{C}^*_3)(\mathcal{F}_1-\mathcal{F}^*_1)+(\mathcal{C}^*_2+\mathcal{C}^*_3)(\mathcal{F}_2-\mathcal{F}^*_2)\\
&=\mathcal{C}^*_1(\mathcal{F}_1-\mathcal{F}^*_1)+\mathcal{C}^*_3(\mathcal{F}_1-\mathcal{F}^*_1)+\mathcal{C}^*_2(\mathcal{F}_2-\mathcal{F}^*_2)+\mathcal{C}^*_3(\mathcal{F}_2-\mathcal{F}^*_2)\\
&=\mathcal{C}^*_1(\mathcal{F}_1-\mathcal{F}^*_1)+\mathcal{C}^*_2(\mathcal{F}_2-\mathcal{F}^*_2)+\mathcal{C}^*_2((\mathcal{F}_1+\mathcal{F}_2)-(\mathcal{F}^*_1+\mathcal{F}^*_2))\\
&=\mathcal{C}^*_1(\mathcal{F}_1-\mathcal{F}^*_1)+\mathcal{C}^*_2(\mathcal{F}_2-\mathcal{F}^*_2)+\mathcal{C}^*_3(\mathcal{F}_3-\mathcal{F}^*_3)\\
&\ge 0\end{align}$$

可以看出，对于线段，我们也有和路径相似的不等式

$$\mathcal{C}(\mathcal{F}^*)\cdot(\mathcal{F}-\mathcal{F}^*)\ge 0\tag{9}$$

那么为什么要证明对于线段来讲，这个不等式仍然成立呢？因为这样我们在拿到一个给定的网络\(\mathcal{G}\)，一个包含\(n_\mathcal{W}\)个源点/终点对的集合\(\mathcal{W}\)时，就不再需要去找出每一个源点/终点对\(w\)的路径\(\mathcal{P}_w\)了。那么在某些时候，我们将问题简化到只需要知道每条线段上的花费函数\(\mathcal{C}(x)\)就可以计算了。

既然均衡解可以用求解变分不等式来计算，那么最优解是否也是如此呢？答案是肯定的。

还是一我们最喜欢的图作为例子，根据我们求最优解的方程

$$\left\{\begin{align}\text{min}\, \mathcal{Z}&=\sum_{i}(\mathcal{c}_i(f_i) f_i)\\
\text{s.t } \sum_i\mathcal{P}_i &= d\end{align}\right.$$

代入\(f\)和花费函数

$$\mathcal{Z}=(f^2_1+5f_1)+(2f^2_2+10f_2)+(f^2_3+15f_3)$$

接下来使用\(\mathcal{P}\)代入

$$\mathcal{Z}=(\mathcal{P}^2_1+5\mathcal{P}_1)+(2\mathcal{P}^2_2+10\mathcal{P}_2)+((\mathcal{P}_1+\mathcal{P}_2)^2+15(\mathcal{P}_1+\mathcal{P}_2))$$

最后应用Lagrange Multiplier（拉格朗日乘数法）求解

$$\left\{\begin{align}\frac{\partial{\mathcal{F}}}{\partial{\mathcal{x}}}=f_x(x,y)+\lambda\varphi_x(x,y) &= 0\\
\frac{\partial{\mathcal{F}}}{\partial{\mathcal{y}}}=f_y(x,y)+\lambda\varphi_y(x,y) &= 0\\
\varphi(x,y) &= 0\end{align}\right.$$

我们可以看出求最优解的一般方法

先是根据线段上流量\(f\)和线段的花费函数\(c(f)\)写出系统的总花费函数\(\mathcal{Z}\)，然后代入得到一个通过路径流量\(\mathcal{P}\)作为自变量的函数\(\mathcal{Z}(\mathcal{P})\)。与均衡解类似的，我们使用向量\(\underline{\mathcal{P}}\)表示系统最优时，每条路径上的流量。同时用向量\(\mathcal{P}\)来表示第i路径上的流量\(\mathcal{P}_i\)，这里的\(\mathcal{P}_i\)是变量。在系统最优时有

$$\left\{\begin{align}\frac{\partial\mathcal{Z}(\mathcal{P})}{\partial\underline{\mathcal{P}_i}}&=\lambda &\text{if }\underline{\mathcal{P}_i}&\gt 0\\
&\ge\lambda &\text{if }\underline{\mathcal{P}_i}&=0\end{align}\right.\tag{10}$$

同样，下面这个不等式也可以通过对(10)分类讨论证明成立。

$$(\frac{\partial\mathcal{Z}}{\partial\underline{\mathcal{P}_i}}-\lambda)\cdot(\mathcal{P_i}-\underline{\mathcal{P}_i})\ge 0\quad\forall \mathcal{P}_i\in\mathcal{S}\tag{11}$$

不等式(11)说明了在第i条路径上的情况，那么对于所有的路径有

$$\begin{align}&\sum_i((\frac{\partial{\mathcal{Z}}}{\partial\underline{\mathcal{P}_i}})\cdot(\mathcal{P}-\mathcal{P}_i))\ge 0\\
&=\sum_i(\frac{\partial\mathcal{Z}}{\partial\underline{\mathcal{P}_i}}(\mathcal{P}_i-\underline{\mathcal{P}_i})-\lambda(\mathcal{P}_i-\underline{\mathcal{P}_i}))\\
&=\sum_i\frac{\partial\mathcal{Z}}{\partial\underline{\mathcal{P}_i}}(\mathcal{P}_i-\underline{\mathcal{P}_i})-\lambda(\sum_i(\mathcal{P}_i-\underline{\mathcal{P}_i}))\\
&=\sum_i\frac{\partial\mathcal{Z}}{\partial\underline{\mathcal{P}_i}}(\mathcal{P}_i-\underline{\mathcal{P}_i})-\lambda((\sum_i\mathcal{P}_i)-\sum_i(\underline{\mathcal{P}_i}))\\
&=\sum_i\frac{\partial\mathcal{Z}}{\partial\underline{\mathcal{P}_i}}(\mathcal{P}_i-\underline{\mathcal{P}_i})-\lambda(d-d)\\
&=\sum_i\frac{\partial\mathcal{Z}}{\partial\underline{\mathcal{P}_i}}(\mathcal{P}_i-\underline{\mathcal{P}_i})\\
&=\ge 0\end{align}\tag{12}$$

此时可使用\(\mathcal{F}\)代替\(\mathcal{P}\)，得到

$$\sum_i\frac{\partial\mathcal{Z(F)}}{\partial\underline{\mathcal{F}}}\cdot(\mathcal{F}-\underline{\mathcal{F}})\ge 0$$

现在，我们有了两个变分不等式

$$\left\{\begin{align}\frac{\partial\mathcal{Z(F)}}{\partial\underline{\mathcal{F}}}\cdot(\mathcal{F}-\underline{\mathcal{F}})&\ge 0&\forall \mathcal{F}\in S&\text{  最优解}\\
\mathcal{C}(\mathcal{F}^*)\cdot(\mathcal{F}-\mathcal{F}^*)&\ge 0&\forall \mathcal{F}\in S&\text{ 均衡解}\end{align}\right.$$

其中

$$\begin{align}\frac{\partial\mathcal{Z}(\mathcal{F})}{\partial\mathcal{F}}=\left(\begin{array}{}\frac{\partial\mathcal{Z}}{\mathcal{F}_1}\\
\frac{\partial\mathcal{Z}}{\mathcal{F}_2}\\
\vdots\\
\frac{\partial\mathcal{Z}}{\mathcal{F}_{n_L}}\end{array}\right)&\mathcal{C}(\mathcal{F}^*)=\left(\begin{array}{}\mathcal{F}_1\\
\mathcal{F}_2\\
\vdots\\
\mathcal{F}_{n_L}\end{array}\right)\end{align}$$

于是我们把问题变成了变分不等式的求解。