最优质量运输概述（自用）——一、蒙日问题、Kantorovich问题

1. 蒙日问题 Monge’s Problem

如下图所示，假设有一堆沙子要从红色沙堆运送填充到蓝色沙堆。在坐标$x$处做一个切片$\Delta x$，该切片对应沙堆中的一个厚度无限趋近于0的大圆盘，该圆盘位于坐标$x$处，质量为$\mu (x)$。因此$\mu (x)$可以看作整个沙堆的质量分布规律，或者沿坐标$x$的线密度，称之为测度。

设从$x$处搬运到$y$处，二者映射关系为$y=T(x)$。搬运后大圆盘$\mu (x)$在蓝色沙堆中对应为$\nu (x)$。
最优运输问题为：如何把沙堆从$\mu$运送到$\nu (x)$，即**$\mu (x)$中的哪个位置应当放在$\nu (x)$中的哪个位置？**

运送的距离为：$D\left(x,T(x)\right)$
则运送这一个切片的做功为：$\mu (x)D\left(x,T(x)\right)$

上图中，把三个坐标$A_i$的质量运送到坐标$B$处，则测度有如下关系：
$$\mu \left(A_1\right)+\mu \left(A_2\right)+\mu \left(A_3\right)=\nu \left(B\right)$$记为
$$\mu \left(T^{-1}(B)\right)=\nu \left(B\right)$$或
$$T_{\#}\mu =\nu$$称$T$是从红色到蓝色的一个map。
而蒙日问题的关键在于，试图找出所有$T_{\#}\mu =\nu$中，使得如下做功最小的$T$：
$$\int D\left(x,T(x)\right)\mu (dx)\text{\hspace{1em}(1)}$$

2. Kantorovich问题

如上图所示，蓝色虚线表示前线位置，蓝色五角星为目标位置A,B,C，蓝色数字为目标位置所需军力；红色三角为目前军力驻扎位置，红色数字为目前驻扎位置的军力。
Kantorovich问题如下：将三个红色军团配置到前线的三个目标位置A,B,C，该如何配置？

为解决该问题可以列出运输矩阵：

可以抽象为如下表格：

其中的$p_{ij}$需要满足如下约束：
∀ i ∈ { 1 , 2 , 3 } , ∑ j ∈ { A , B , C } p i j = a i , ∀ j ∈ { A , B , C } , ∑ i ∈ { 1 , 2 , 3 } p i j = b j , p i j ≥ 0 \forall i \in \{1,2,3\}, \quad \sum_{j \in \{A,B,C\}} p_{ij} = a_i, \\ \forall j \in \{A,B,C\}, \quad \sum_{i \in \{1,2,3\}} p_{ij} = b_j, \\ p_{ij} \geq 0 ∀i∈{1,2,3},j∈{A,B,C}∑​pij​=ai​,∀j∈{A,B,C},i∈{1,2,3}∑​pij​=bj​,pij​≥0即表格中每一行之和为对应的$a_i$，每一列之和为对应的$b_j$。
同样地，可以写出如下距离矩阵：

移动军团做的功之和，可以视作损失函数：
C ( P ) = ∑ j ∈ { A , B , C } ∑ i ∈ { 1 , 2 , 3 } p i j d i j (2) C (P) = \sum_{j \in \{A,B,C\}} \sum_{i \in \{1,2,3\}} p_{ij} d_{ij} \tag{2} C(P)=j∈{A,B,C}∑​i∈{1,2,3}∑​pij​dij​(2)