Congested network笔记(2)

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

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

transport-2

对于它的均衡解,我们有

$$\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}$$

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

声明: 本文为0xBBC原创, 转载注明出处喵~

《Congested network笔记(2)》有2个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注