传输理论

传输理论（、），又称为运输理论，是数学、经济学等学科中研究最优运输和资源配置的理论。该问题最早由法国数学家加斯帕尔·蒙日于1781年提出。G. Monge. Mémoire sur la théorie des déblais et des remblais. Histoire de l’Académie Royale des Sciences de Paris, avec les Mémoires de Mathématique et de Physique pour la même année, pages 666–704, 1781.

1920年代，A·N·托尔斯泰是最早运用数学方法研究传输问题的学者之一。1930年，他在苏联国家交通部编纂的《运输规划》第一卷中发表了题为《寻找太空货物运输的最小千公里方法》的论文。Schrijver, Alexander, Combinatorial Optimization, Berlin; New York : Springer, 2003. . Cf. p. 362 Ivor Grattan-Guinness, Ivor, Companion encyclopedia of the history and philosophy of the mathematical sciences, Volume 1, JHU Press, 2003. Cf. p.831 

第二次世界大战期间，苏联数学家、经济学家列昂尼德·坎托罗维奇在该领域取得了重要进展。L. Kantorovich. On the translocation of masses. C.R. (Doklady) Acad. Sci. URSS (N.S.), 37:199–201, 1942.因此，这一问题有时也被称为蒙日-坎托罗维奇运输问题（）。 该问题的线性规划形式也被称为-库普曼斯运输问题。

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

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

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

 将所有本书全都向右移动一本书的宽度（许多小步）；
 将最左侧的书向右移动书本的宽度，其他书则保持不动（一大步）。

如果成本函数与欧几里得距离成正比（即 ，其中 ），那么这两种候选方案都是最优的。而如果我们选择与欧几里得距离的平方成比例的严格凸成本函数（即 ，其中 ），则“许多小步”的方案则是唯一的最优解。

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

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

假设有个供应源为某一商品供货，且每个供应源处有个单位的供应量。同时有个需求点需要该商品，每个需求点处有个单位的需求。若表示从到的单位运输成本，任务是找到一个流量分配方案，在满足供应需求的同时最小化运输成本。这一物流问题由德尔伯特·雷·富尔克森提出D. R. Fulkerson (1956) Hitchcock Transportation Problem , RAND corporation.，并在他与小莱斯特·伦道夫·福特合著的《网络流》（Flows in Networks）（1962年）一书中得到了阐述。L. R. Ford Jr. & D. R. Fulkerson (1962) § 3.1 in Flows in Networks, page 95, Princeton University Press

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

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

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

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

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

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

其中表示上所有概率测度的集合并满足边缘分布和。可以证明L. Ambrosio, N. Gigli & G. Savaré. Gradient Flows in Metric Spaces and in the Space of Probability Measures . Lectures in Mathematics ETH Zürich, Birkhäuser Verlag, Basel. (2005)，当成本函数是下半连续并且是紧测度集合（拉东空间和蕴含该条件）时，该问题总是存在最小值（另见沃瑟斯坦度量）。、史蒂文·哈克尔（Steven Haker）与提出了蒙日–坎托罗维奇问题解的梯度下降表述。

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

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

的函数对。

 经济学解释 
将以上表述中的符号翻转更利于从经济学角度解释这一问题。假设表示工人特征的向量，表示企业特征的向量，则表示工人与企业配对所创造的经济产出。令、，蒙日–坎托罗维奇问题可以重新表述为：

它的对偶形式为：

其中下确界遍历所有有界且连续的函数和。如果对偶问题有解，则有：

可以将解释为类型工人的均衡工资 ，并将解释为类型企业的均衡利润。Galichon, Alfred. Optimal Transport Methods in Economics. Princeton University Press, 2016.

 问题求解 
 一维连续情形 

对于， 假设表示上所有阶矩有限的概率测度的集合。设且，其中是一个凸函数。

 如果没有，即的累积分布函数是一个连续函数，则是一个最优传输映射。如果是严格凸的，则它是唯一的最优映射。
 可以得到

拉切夫（Rachev）与吕申多夫（Rüschendorf）于1998年给出了对此的证明。Rachev, Svetlozar T., and Ludger Rüschendorf. Mass Transportation Problems: Volume I: Theory. Vol. 1. Springer, 1998.

 离散情形与线性规划 
在边缘分布和是离散的情形下，令和分别是分配给和的概率质量，而则是的分配概率。原始坎托罗维奇问题中的目标函数为

并满足约束条件

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




其中是克罗内克积，是一个大小为、所有元素为1的矩阵，而是大小为的单位矩阵。设，该问题的线性规划形式为

这一问题可以很容易地通过大规模线性规划求解器计算。Galichon, Alfred. Optimal Transport Methods in Economics. Princeton University Press, 2016.

 半离散情形 
在半离散情况下，令，且是上的连续分布，则是分配概率质量到的离散分布。此时，坎托罗维奇问题的原始形式为：Santambrogio, Filippo. Optimal Transport for Applied Mathematicians. Birkhäuser Basel, 2016. In particular chapter 6, section 4.2.



其中满足和 。

而其对偶形式则为

还可以写为：

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

当时，可以证明分配给特定的集合是一个凸多面体，而得到的配置称为。.

 二次正态情形 
假设一个特殊情形、 且，其中是可逆矩阵。此时有

加利雄（Galichon）于2016年证明了该情况下的解。Galichon, Alfred. Optimal Transport Methods in Economics. Princeton University Press, 2016.

 可分希尔伯特空间 
令是一个可分希尔伯特空间，定义为上所有阶矩有限的概率测度的集合，则表示其中高斯正则的测度集合，即如果是上任何严格正的且满足 ，则也成立。

假设、，并且，其中 。则坎托罗维奇问题存在一个唯一解 ，并且该解对应一个最优传输映射：即存在一个博雷尔映射，使得

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

其中表示的加托导数。

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

相应的对偶问题为

相较于不含正则化项的问题，原先对偶问题中的硬约束（  ）被替换为了软约束，即惩罚项。对偶问题的最优条件可以表示为





令为的矩阵，其中元素。此时对偶问题的求解等价于寻找两个对角正矩阵和，它们的大小分别为和 ，使得、。矩阵和的存在性是辛克宏定理的推广，可以使用辛克宏-诺普算法进行求解。Peyré, Gabriel and Marco Cuturi (2019), "Computational Optimal Transport: With Applications to Data Science", Foundations and Trends in Machine Learning: Vol. 11: No. 5-6, pp 355–607. DOI: 10.1561/2200000073.该算法通过迭代求解中的和中的实现。因此，辛克宏-诺普算法相当于对偶正则问题的坐标下降法。

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

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

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

 参考文献 

Category:運輸經濟學
Category:數學最佳化
Category:商业数学优化
Category:测度论
Category:变分法
Category:图论