传输理论（、），又称为运输理论，是数学、经济学等学科中研究最优运输和资源配置的理论。该问题最早由法国数学家加斯帕尔·蒙日于1781年提出。

1920年代，A·N·托尔斯泰是最早运用数学方法研究传输问题的学者之一。1930年，他在苏联国家交通部编纂的《运输规划》第一卷中发表了题为《寻找太空货物运输的最小千公里方法》的论文。

第二次世界大战期间，苏联数学家、经济学家列昂尼德·坎托罗维奇在该领域取得了重要进展。因此，这一问题有时也被称为蒙日-坎托罗维奇运输问题（）。 该问题的线性规划形式也被称为-库普曼斯运输问题。

背景
矿山与工厂
假设有m个开采铁矿石的矿山以及n个工厂使用这些矿山生产的铁矿石，且这些矿山和工厂构成欧几里得平面\mathbb{R}^2中两个不相交的子集M和F。同时假设存在一个成本函数c : \mathbb{R}^2 \times \mathbb{R}^2 \to [0, \infty)， 其中c(x, y)表示将一批矿石从x运送到y的成本。为简化起见，此处忽略运输所需的时间。我们还假定每个矿山只能供应一家工厂（不能拆分运输），并且每家工厂需要恰好一批货物才能运营（工厂不能半负荷或双倍负荷运转）。基于上述条件，一个传输计划可以看作是一个双射T: M \to F 。换句话说，每个矿井m \in M仅供应一个目标工厂T(m) \in F，而每个工厂也只由一个矿山供货。我们希望找到最优传输计划T，使得总成本

:c(T) := \sum_{m \in M} c(m, T(m))

在所有M到F的传输计划中是最小的。该问题是传输问题的一个特例，可看成一个任务分配问题。更具体地说，它等价于在二分图中寻找最小权重匹配。

书籍移动：成本函数的重要性
下面这个简单的例子说明了成本函数在确定最优传输计划中的重要性。假设我们有n本宽度相等的书摆放在书架上（可以看成具像化的实数线），形成连续一排书。我们希望将它们重新排列，在保持其连续性的同时将整体向右移动一本书的宽度。针对这个问题，有两个显而易见的最优传输候选方案：

将所有n本书全都向右移动一本书的宽度（许多小步）；

将最左侧的书向右移动n书本的宽度，其他书则保持不动（一大步）。

如果成本函数与欧几里得距离成正比（即 c(x, y) = \alpha \|x - y\|，其中\alpha > 0 ），那么这两种候选方案都是最优的。而如果我们选择与欧几里得距离的平方成比例的严格凸成本函数（即 c(x, y) = \alpha \|x - y\|^2，其中\alpha > 0 ），则“许多小步”的方案则是唯一的最优解。

需要注意的是，上述成本函数仅考虑书籍本身移动的水平距离，而没有考虑拿起每本书并将其移动到位的设备所行进的水平距离。如果考虑后者，那么在两种传输计划中，第二种方案对于欧几里得距离始终是最优的，而第一种方案则对于平方欧几里得距离是最优的（至少有三本书的情况下）。

希区柯克问题
以下传输问题的表述由弗兰克·劳伦·希区柯克提出：

:假设有m个供应源x_1, \ldots, x_m为某一商品供货，且每个供应源x_i处有a(x_i)个单位的供应量。同时有n个需求点y_1, \ldots, y_n需要该商品，每个需求点y_j处有b(y_j)个单位的需求。若c(x_i,\ y_j)表示从x_i到y_j的单位运输成本，任务是找到一个流量分配方案，在满足供应需求的同时最小化运输成本。这一物流问题由德尔伯特·雷·富尔克森提出，并在他与小莱斯特·伦道夫·福特合著的《网络流》（Flows in Networks）（1962年）一书中得到了阐述。

佳林·库普曼斯也为运输经济学与资源分配问题的表述作出了贡献。

问题的抽象表述
蒙日和坎托罗维奇形式
由于黎曼几何和测度论的发展，在现代或更加技术性的文献中传输问题的表述有所不同。不过，上述矿山与工厂的简单例子还是可以作为考虑抽象形式时一个有用的参照。此时我们可以考虑并非所有矿山和工厂都营业的情况，并允许一个矿山向多家工厂供货，而一家工厂也可以从多个矿山接受矿石。

假设X和Y为两个可分度量空间，使得X（或者Y ) 上的每个概率测度都是拉东测度，并假设c : X \times Y \to [0, \infty)是一个博雷尔可测函数。给定X上的概率测度\mu和Y上的概率测度\nu，最优传输问题的蒙日形式是指寻找一个传输映射T : X \to Y，使得下式中的下确界成立：

:\inf \left\{ \left. \int_X c(x, T(x)) \, \mathrm{d} \mu (x) \right| T_* (\mu) = \nu \right\},

其中T_*(\mu)由T推进\mu的向前推进算子。如果一个映射T达到这个下确界，则该映射被称为“最优传输映射”。

最优传输问题的蒙日形式有其局限性，因为有时可能不存在满足T_*(\mu) = \nu 的映射T。例如，当\mu是狄拉克测度而\nu不是时，就会出现这种情况。

此时可以通过采用最优传输问题的坎托罗维奇形式来克服这一局限，即寻找X \times Y上的一个概率测度\gamma，使得下式中的下确界成立：

:\inf \left\{ \left. \int_{X \times Y} c(x, y) \, \mathrm{d} \gamma (x, y) \right| \gamma \in \Gamma (\mu, \nu) \right\},

其中 \Gamma (\mu, \nu) 表示X \times Y上所有概率测度的集合并满足边缘分布\mu和\nu。可以证明，当成本函数c是下半连续并且\Gamma(\mu, \nu)是紧测度集合（拉东空间X和Y蕴含该条件）时，该问题总是存在最小值（另见沃瑟斯坦度量）。、史蒂文·哈克尔（Steven Haker）与提出了蒙日–坎托罗维奇问题解的梯度下降表述。

对偶形式
坎托罗维奇问题的最小值等于

:\sup \left( \int_X \varphi (x) \, \mathrm{d} \mu (x) + \int_Y \psi (y) \, \mathrm{d} \nu (y) \right),

其中上确界遍历所有有界且连续、满足

:\varphi (x) + \psi (y) \leq c(x, y)

的函数对。

经济学解释
将以上表述中的符号翻转更利于从经济学角度解释这一问题。假设x \in X表示工人特征的向量， y \in Y表示企业特征的向量，\Phi(x,y) =-c(x,y)则表示工人x与企业y配对所创造的经济产出。令u(x) = -\varphi(x)、v(y) =-\psi(y)，蒙日–坎托罗维奇问题可以重新表述为：

:\sup \left\{ \int_{X\times Y}\Phi(x,y) d\gamma(x,y) ,\gamma \in \Gamma(\mu,\nu) \right\}

它的对偶形式为：

:\inf \left\{ \int_X u(x) \,d\mu(x) +\int_Y v(y) \, d\nu (y) :u(x) +v(y) \geq \Phi(x,y) \right\}

其中下确界遍历所有有界且连续的函数u:X\to \mathbb{R}和v:Y\to \mathbb{R}。如果对偶问题有解，则有：

:v(y) =\sup_x \left\{ \Phi(x,y) - u(x)\right\}

可以将u(x)解释为x类型工人的均衡工资 ，并将v(y)解释为y类型企业的均衡利润。

问题求解
一维连续情形
对于1 \leq p ， 假设\mathcal{P}_p(\mathbb{R})表示\mathbb{R}上所有p阶矩有限的概率测度的集合。设\mu, \nu \in \mathcal{P}_p(\mathbb{R})且c(x, y) = h(x-y)，其中h:\mathbb{R} \to [0,\infty)是一个凸函数。

如果\mu没有，即\mu的累积分布函数F_\mu : \mathbb{R}\to[0,1]是一个连续函数，则F_{\nu}^{-1} \circ F_{\mu} : \mathbb{R} \to \mathbb{R}是一个最优传输映射。如果h是严格凸的，则它是唯一的最优映射。

可以得到

:\min_{\gamma \in \Gamma(\mu, \nu)} \int_{\mathbb{R}^2} c(x, y) \, \mathrm{d} \gamma (x, y) = \int_0^1 c \left( F_{\mu}^{-1} (s), F_{\nu}^{-1} (s) \right) \, \mathrm{d} s.

拉切夫（Rachev）与吕申多夫（Rüschendorf）于1998年给出了对此的证明。

离散情形与线性规划
在边缘分布\mu和\nu是离散的情形下，令\mu_x和\nu_y分别是分配给x\in \mathbf{X}和y\in \mathbf{Y}的概率质量，而\gamma_{xy}则是xy的分配概率。原始坎托罗维奇问题中的目标函数为

: \sum_{x\in \mathbf{X},y\in \mathbf{Y}} \gamma_{xy}c_{xy}

并满足约束条件

:
\sum_{y\in \mathbf{Y}}\gamma_{xy}=\mu_x,\forall x\in \mathbf{X}

:
\sum_{x\in \mathbf{X}} \gamma_{xy}=\nu_y,\forall y\in \mathbf{Y}.

为了将这一问题作为线性规划问题处理，我们需要将矩阵\gamma_{xy}向量化，可以通过堆叠其行或列来完成，我们用\operatorname{vec}来表示这一操作。在的情况下，上述约束条件可改写为

: \left( 1_{1\times |\mathbf{Y}| }\otimes I_\right) \operatorname{vec}(\gamma)=\mu
: \left( I_\otimes 1_{1\times |\mathbf{X}|}\right) \operatorname{vec}(\gamma)=\nu

其中\otimes是克罗内克积，1_{n\times m}是一个大小为n\times m、所有元素为1的矩阵，而I_{n}是大小为n的单位矩阵。设z=\operatorname{vec}(\gamma)，该问题的线性规划形式为

:
\begin{align}
& \text{Minimize } &&\operatorname{vec}(c)^\top z \\[4pt]
& \text{subject to:} && z \ge 0, \\[4pt]
& && \begin{pmatrix}
1_{1\times |\mathbf{Y}|}\otimes I_ \\
I_\otimes 1_{1\times |\mathbf{X}|}
\end{pmatrix} z=\binom{\mu}{\nu}
\end{align}

这一问题可以很容易地通过大规模线性规划求解器计算。

半离散情形
在半离散情况下，令X=Y=\mathbb{R}^d，且\mu是\mathbb{R}^d上的连续分布，\nu =\sum_{j=1}^J \nu_j\delta_{y_i}则是分配概率质量\nu_j到y_j \in \mathbb{R}^d的离散分布。此时，坎托罗维奇问题的原始形式为：

: \inf \left\{ \int_X \sum_{j=1}^J c(x,y_j) \, d\gamma_j(x) ,\gamma \in \Gamma(\mu,\nu)\right\}

其中\gamma \in \Gamma(\mu ,\nu)满足\int_X d\gamma_j(x)=\nu_j和\sum_j d\gamma_j(x) =d\mu(x) 。

而其对偶形式则为

: \sup \left\{ \int_X\varphi(x)d\mu (x)+\sum_{j=1}^J\psi_j\nu_j:\psi_j+\varphi (x)\leq c(x,y_j) \right\}

还可以写为：

: \sup_{\psi \in \mathbb{R}^J}\left\{ \int_X\inf_j\left\{ c(x,y_j)-\psi_j\right\} d\mu (x)+\sum_{j=1}^J\psi_j\nu_j\right\}

这是一个有限维凸优化问题，可以通过梯度下降等方法求解。

当c(x,y)=|x-y|^2/2时，可以证明分配给特定j的x\in \mathbf{X}集合是一个凸多面体，而得到的配置称为。

二次正态情形
假设一个特殊情形\mu =\mathcal{N}(0,\Sigma_X)、\nu =\mathcal{N}(0,\Sigma _{Y}) 且c(x,y) =|y-Ax|^2/2，其中A是可逆矩阵。此时有

: \varphi(x) =-x^\top \Sigma_X^{-1/2}\left( \Sigma_X^{1/2}A^\top \Sigma_Y A\Sigma_X^{1/2}\right) ^{1/2}\Sigma_{X}^{-1/2}x/2

:\psi(y) =-y^\top A\Sigma_X^{1/2}\left( \Sigma_X^{1/2}A^\top \Sigma_Y A\Sigma_{X}^{1/2}\right)^{-1/2} \Sigma_X^{1/2}Ay/2

: T(x) = (A^\top)^{-1}\Sigma_X^{-1/2} \left(\Sigma_X^{1/2}A^\top \Sigma_Y A\Sigma_X^{1/2} \right)^{1/2} \Sigma_X^{-1/2}x

加利雄（Galichon）于2016年证明了该情况下的解。

可分希尔伯特空间
令X是一个可分希尔伯特空间，定义\mathcal{P}_p(X)为X上所有p阶矩有限的概率测度的集合，\mathcal{P}_p^r(X)则表示其中高斯正则的测度集合，即如果g是X上任何严格正的且满足g(N) = 0 ，则\mu(N) = 0也成立。

假设\mu \in \mathcal{P}_p^r (X)、\nu \in \mathcal{P}_p(X)，并且c (x, y) = | x - y |^p/p，其中p\in(1,\infty), p^{-1} + q^{-1} = 1 。则坎托罗维奇问题存在一个唯一解\kappa ，并且该解对应一个最优传输映射：即存在一个博雷尔映射r\in L^p(X, \mu; X)，使得

:\kappa = (\mathrm{id}_X \times r)_{*} (\mu) \in \Gamma (\mu, \nu).

此外，如果\nu具有有界支撑，那么对于\mu-几乎所有的x\in X，存在局部利普希茨、 c-凹和最大坎托罗维奇势\varphi，使得

:r(x) = x - | \nabla \varphi (x) |^{q - 2} \, \nabla \varphi (x)

其中\nabla \varphi表示\varphi的加托导数。

熵正则化
考虑上述离散问题的一个变体：在原始问题的目标函数中添加一个熵正则化项

:
\begin{align}
& \text{Minimize } \sum_{x\in \mathbf{X}, y\in \mathbf{Y}}\gamma_{xy}c_{xy}+\varepsilon \gamma_{xy} \ln \gamma_{xy} \\[4pt]
& \text{subject to: } \\[4pt]
& \gamma\ge0 \\[4pt]
& \sum_{y\in \mathbf{Y}}\gamma_{xy} = \mu_x, \forall x\in \mathbf{X} \\[4pt]
& \sum_{x\in \mathbf{X}}\gamma_{xy} = \nu_y, \forall y\in \mathbf{Y}
\end{align}

相应的对偶问题为

:
\max_{\varphi ,\psi} \sum_{x\in \mathbf{X}} \varphi_x \mu_x + \sum_{y\in \mathbf{Y}} \psi_y v_y - \varepsilon \sum_{x\in \mathbf{X},y\in \mathbf{Y}} \exp \left( \frac{\varphi_x + \psi_y - c_{xy}}{\varepsilon }\right)

相较于不含正则化项的问题，原先对偶问题中的硬约束（ \varphi_x + \psi_y - c_{xy}\geq 0 ）被替换为了软约束，即惩罚项\varepsilon \exp \left( (\varphi _x + \psi_y - c_{xy})/\varepsilon \right)。对偶问题的最优条件可以表示为

:
\mu_x = \sum_{y\in \mathbf{Y}} \exp \left( \frac{\varphi_x + \psi_y - c_{xy}}{\varepsilon} \right) ~\forall x\in \mathbf{X}

:
\nu_y = \sum_{x\in \mathbf{X}} \exp \left( \frac{\varphi_x + \psi_y - c_{xy}}{\varepsilon }\right) ~\forall y\in \mathbf{Y}

令A为|\mathbf{X}| \times |\mathbf{Y}|的矩阵，其中元素A_{xy}=\exp \left(-c_{xy} / \varepsilon \right)。此时对偶问题的求解等价于寻找两个对角正矩阵D_1和D_2，它们的大小分别为|\mathbf{X}|和|\mathbf{Y}| ，使得D_1AD_2 1_=\mu、(D_1AD_2)^\top 1_=\nu 。矩阵D_1和D_2的存在性是辛克宏定理的推广，可以使用辛克宏-诺普算法进行求解。该算法通过迭代求解中的\varphi_x和中的\psi_y实现。因此，辛克宏-诺普算法相当于对偶正则问题的坐标下降法。

应用
蒙日-坎托罗维奇运输问题已广泛运用于许多领域，例如：

• 图像配准与变形
• 反射面设计
• 从阴影照相与质子射线成像中提取信息
• 地震层析成像和反射地震学
• 涉及总替代性质的经济模型

参见

• 沃瑟斯坦度量
• 匈牙利算法
• 交通规划
• 推土机距离
• 齐次蒙日-安培方程

参考文献