查看“︁传输理论”︁的源代码

'''传输理论'''（{{lang-en|tansport theory}}、{{lang|en|transportation theory}}），又称为'''运输理论'''，是数学、经济学等学科中研究最优[[运输]]和[[资源配置]]的理论。该问题最早由法国数学家[[加斯帕尔·蒙日]]于1781年提出。<ref name="Monge">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.</ref>

1920年代，A·N·托尔斯泰是最早运用数学方法研究传输问题的学者之一。1930年，他在苏联国家交通部编纂的《运输规划》第一卷中发表了题为《寻找太空货物运输的最小千公里方法》的论文。<ref>Schrijver, Alexander, [https://books.google.com/books?id=mqGeSQ6dJycC ''Combinatorial Optimization''], Berlin; New York : Springer, 2003. {{ISBN|3540443894}}. Cf. [https://books.google.com/books?id=mqGeSQ6dJycC&dq=a.n.+tolstoi+transportation+networks&pg=PA362 p. 362] {{Wayback|url=https://books.google.com/books?id=mqGeSQ6dJycC&dq=a.n.+tolstoi+transportation+networks&pg=PA362 |date=20241211071931 }}</ref><ref>Ivor Grattan-Guinness, Ivor, [https://books.google.com/books?id=2hDvzITtfdAC ''Companion encyclopedia of the history and philosophy of the mathematical sciences''], Volume 1, JHU Press, 2003. Cf. [https://books.google.com/books?id=2hDvzITtfdAC&dq=%22a.n.+tolstoy%22+mathematics&pg=PA831 p.831] {{Wayback|url=https://books.google.com/books?id=2hDvzITtfdAC&dq=%22a.n.+tolstoy%22+mathematics&pg=PA831 |date=20231005062539 }}</ref>

[[第二次世界大战]]期间，苏联数学家、经济学家[[列昂尼德·坎托罗维奇]]在该领域取得了重要进展。<ref name="Kantorovich">L. Kantorovich. ''On the translocation of masses.'' C.R. (Doklady) Acad. Sci. URSS (N.S.), 37:199–201, 1942.</ref>因此，这一问题有时也被称为'''蒙日-坎托罗维奇运输问题'''（{{lang|en|Monge–Kantorovich transportation problem}}）。 <ref name="Villani2003">{{Cite book |title=Topics in Optimal Transportation |author=Cédric Villani |publisher=American Mathematical Soc. |year=2003 |isbn=978-0-8218-3312-4 |page=66}}</ref>该问题的[[线性规划]]形式也被称为{{le|弗兰克·劳伦·希区柯克|Frank Lauren Hitchcock|希区柯克}}-[[佳林·库普曼斯|库普曼斯]]运输问题。<ref name="RaoRao2009">{{Cite book |title=Engineering Optimization: Theory and Practice |author=Singiresu S. Rao |publisher=John Wiley & Sons |year=2009 |isbn=978-0-470-18352-6 |edition=4th |pages=221}}</ref>

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

:<math>c(T) := \sum_{m \in M} c(m, T(m))</math>

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

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

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

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

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

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

:假设有<math>m</math>个供应源<math>x_1, \ldots, x_m</math>为某一商品供货，且每个供应源<math>x_i</math>处有<math>a(x_i)</math>个单位的供应量。同时有<math>n</math>个需求点<math>y_1, \ldots, y_n</math>需要该商品，每个需求点<math>y_j</math>处有<math>b(y_j)</math>个单位的需求。若<math>c(x_i,\ y_j)</math>表示从<math>x_i</math>到<math>y_j</math>的单位运输成本，任务是找到一个流量分配方案，在满足供应需求的同时最小化运输成本。这一物流问题由[[德尔伯特·雷·富尔克森]]提出<ref>D. R. Fulkerson (1956) [https://priorart.ip.com/IPCOM/000128834/ Hitchcock Transportation Problem] {{Wayback|url=https://priorart.ip.com/IPCOM/000128834/ |date=20241213124207 }}, RAND corporation.</ref>，并在他与[[小莱斯特·伦道夫·福特]]合著的《网络流》（''Flows in Networks''）（1962年）一书中得到了阐述。<ref>L. R. Ford Jr. & D. R. Fulkerson (1962) § 3.1 in ''Flows in Networks'', page 95, [[Princeton University Press]]</ref>

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

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

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

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

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

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

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

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

其中<math> \Gamma (\mu, \nu) </math>表示<math>X \times Y</math>上所有概率测度的集合并满足[[边缘分布]]<math>\mu</math>和<math>\nu</math>。可以证明<ref name="AGS">L. Ambrosio, N. Gigli & G. Savaré. ''[https://books.google.com/books?id=rCDK9JA5BAEC&q=%22optimal+transportation%22 Gradient Flows in Metric Spaces and in the Space of Probability Measures] {{Wayback|url=https://books.google.com/books?id=rCDK9JA5BAEC&q=%22optimal+transportation%22 |date=20241211064913 }}.'' Lectures in Mathematics ETH Zürich, Birkhäuser Verlag, Basel. (2005)</ref>，当成本函数<math>c</math>是下半连续并且<math>\Gamma(\mu, \nu)</math>是紧测度集合（拉东空间<math>X</math>和<math>Y</math>蕴含该条件）时，该问题总是存在最小值（另见[[沃瑟斯坦度量]]）。{{le|西古德·安格嫩特|Sigurd Angenent}}、史蒂文·哈克尔（Steven Haker）与{{le|艾伦·坦嫩鲍姆|Allen Tannenbaum}}提出了蒙日–坎托罗维奇问题解的梯度下降表述。<ref name="AHT">{{Cite journal |last=Angenent |first=S. |last2=Haker |first2=S. |last3=Tannenbaum |first3=A. |title=Minimizing flows for the Monge–Kantorovich problem |journal=SIAM J. Math. Anal. |year=2003 |volume=35 |issue=1 |page=61–97 |citeseerx=10.1.1.424.1064 |doi=10.1137/S0036141002410927}}</ref>

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

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

其中[[上确界]]遍历所有[[有界函数|有界]]且[[连续函数|连续]]、满足

:<math>\varphi (x) + \psi (y) \leq c(x, y)</math>

的函数对。

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

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

它的[[對偶性 (最佳化)|对偶]]形式为：

:<math>\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\}</math>

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

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

可以将<math>u(x)</math>解释为<math>x</math>类型工人的均衡工资 ，并将<math>v(y)</math>解释为<math>y</math>类型企业的均衡利润。<ref name="Galichon2016">Galichon, Alfred. ''Optimal Transport Methods in Economics''. Princeton University Press, 2016.</ref>

== 问题求解 ==
=== 一维连续情形 ===
{{multiple image
<!-- Layout parameters -->
 | align             = right
 | direction         = vertical
 | width             = 200
<!--image 1-->
 | image1            = Optimal transport matrix.png
 | alt1              = 最优传输矩阵
 | link1             = 
 | caption1          = 最优传输矩阵
<!--image 2-->
 | image2            = Continuous optimal transport.png
 | alt2              = 连续最优传输
 | link2             = 
 | caption2          = 连续最优传输
}}
对于<math>1 \leq p < \infty</math>， 假设<math>\mathcal{P}_p(\mathbb{R})</math>表示<math>\mathbb{R}</math>上所有<math>p</math>阶[[矩 (數學)|矩]]有限的[[概率测度]]的集合。设<math>\mu, \nu \in \mathcal{P}_p(\mathbb{R})</math>且<math>c(x, y) = h(x-y)</math>，其中<math>h:\mathbb{R} \to [0,\infty)</math>是一个[[凸函数]]。

# 如果<math>\mu</math>没有{{le|原子 (测度论)|Atom (measure theory)|原子}}，即<math>\mu</math>的[[累积分布函数]]<math>F_\mu : \mathbb{R}\to[0,1]</math>是一个连续函数，则<math>F_{\nu}^{-1} \circ F_{\mu} : \mathbb{R} \to \mathbb{R}</math>是一个最优传输映射。如果<math>h</math>是严格凸的，则它是唯一的最优映射。
# 可以得到

:<math>\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.</math>

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

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

:<math> \sum_{x\in \mathbf{X},y\in \mathbf{Y}} \gamma_{xy}c_{xy}</math>

并满足约束条件

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

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

为了将这一问题作为[[线性规划]]问题处理，我们需要将矩阵<math>\gamma_{xy}</math>向量化，可以通过堆叠其行或列来完成，我们用<math>\operatorname{vec}</math>来表示这一操作。在{{le|行主序和列主序|Row- and column-major order|列主序}}的情况下，上述约束条件可改写为

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

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

:<math>
\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_{|\mathbf{X}|} \\
I_{|\mathbf{Y}|}\otimes 1_{1\times |\mathbf{X}|}
\end{pmatrix} z=\binom{\mu}{\nu}
\end{align}
</math>

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

=== 半离散情形 ===
在半离散情况下，令<math>X=Y=\mathbb{R}^d</math>，且<math>\mu</math>是<math>\mathbb{R}^d</math>上的连续分布，<math>\nu =\sum_{j=1}^J \nu_j\delta_{y_i}</math>则是分配概率质量<math>\nu_j</math>到<math>y_j \in \mathbb{R}^d</math>的离散分布。此时，坎托罗维奇问题的原始形式为：<ref>Santambrogio, Filippo. ''Optimal Transport for Applied Mathematicians''. Birkhäuser Basel, 2016. In particular chapter 6, section 4.2.</ref>

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

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

而其对偶形式则为

:<math> \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\}</math>

还可以写为：

:<math> \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\} </math>

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

当<math>c(x,y)=|x-y|^2/2</math>时，可以证明分配给特定<math>j</math>的<math>x\in \mathbf{X}</math>集合是一个凸多面体，而得到的配置称为{{le|幂图|Power diagram}}。<ref>{{Citation|last=Aurenhammer|first=Franzdoi=10.1137/0216006|number=1|journal=SIAM Journal on Computing|mr=873251|pages=78–96|title=Power diagrams: properties, algorithms and applications|volume=16|year=1987}}.</ref>

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

:<math> \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 </math>

:<math>\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</math>

:<math> 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 </math>

加利雄（Galichon）于2016年证明了该情况下的解。<ref name="Galichon20163">Galichon, Alfred. ''Optimal Transport Methods in Economics''. Princeton University Press, 2016.</ref>

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

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

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

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

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

其中<math>\nabla \varphi</math>表示<math>\varphi</math>的[[加托导数]]。

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

:<math>
\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}
</math>

相应的对偶问题为

:<math>
\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)
</math>

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

:{{EquationRef|5.1|式5.1:}} <math>
\mu_x = \sum_{y\in \mathbf{Y}} \exp \left( \frac{\varphi_x + \psi_y - c_{xy}}{\varepsilon} \right) ~\forall x\in \mathbf{X}
</math>

:{{EquationRef|5.2|式5.2:}} <math>
\nu_y = \sum_{x\in \mathbf{X}} \exp \left( \frac{\varphi_x + \psi_y - c_{xy}}{\varepsilon }\right) ~\forall y\in \mathbf{Y}  
</math>

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

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

* [[图像配准]]与变形<ref>{{Cite journal |last=Haker |first=Steven |last2=Zhu |first2=Lei |last3=Tannenbaum |first3=Allen |last4=Angenent |first4=Sigurd |title=Optimal Mass Transport for Registration and Warping |url=https://archive.org/details/sim_international-journal-of-computer-vision_2004-12_60_3/page/n38 |journal=International Journal of Computer Vision |language=en |date=1 December 2004 |volume=60 |issue=3 |page=225–240 |citeseerx=10.1.1.59.4082 |doi=10.1023/B:VISI.0000036836.66311.97 |issn=0920-5691 |s2cid=13261370}}</ref>
* 反射面设计<ref>{{Cite journal |last=Glimm |first=T. |last2=Oliker |first2=V. |title=Optical Design of Single Reflector Systems and the Monge–Kantorovich Mass Transfer Problem |journal=Journal of Mathematical Sciences |language=en |date=1 September 2003 |volume=117 |issue=3 |page=4096–4108 |doi=10.1023/A:1024856201493 |issn=1072-3374 |s2cid=8301248}}</ref>
* 从[[阴影照相]]与质子射线成像中提取信息<ref>{{Cite journal |last=Kasim |first=Muhammad Firmansyah |last2=Ceurvorst |first2=Luke |last3=Ratan |first3=Naren |last4=Sadler |first4=James |last5=Chen |first5=Nicholas |last6=Sävert |first6=Alexander |last7=Trines |first7=Raoul |last8=Bingham |first8=Robert |last9=Burrows |first9=Philip N. |title=Quantitative shadowgraphy and proton radiography for large intensity modulations |journal=Physical Review E |date=16 February 2017 |volume=95 |issue=2 |page=023306 |arxiv=1607.04179 |bibcode=2017PhRvE..95b3306K |doi=10.1103/PhysRevE.95.023306 |pmid=28297858 |s2cid=13326345}}</ref>
* [[地震层析成像]]和[[反射地震|反射地震学]]<ref>{{Cite journal |last=Metivier |first=Ludovic |title=Measuring the misfit between seismograms using an optimal transport distance: application to full waveform inversion |url=https://academic.oup.com/gji/article-abstract/205/1/345/2594839 |journal=Geophysical Journal International |date=24 February 2016 |volume=205 |issue=1 |page=345–377 |bibcode=2016GeoJI.205..345M |doi=10.1093/gji/ggw014 |doi-access=free |access-date=2024-12-13 |archive-date=2023-10-05 |archive-url=https://web.archive.org/web/20231005062532/https://academic.oup.com/gji/article-abstract/205/1/345/2594839 |dead-url=no }}</ref>
* 涉及总替代性质的经济模型

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

== 参考文献 ==
{{reflist|30em}}

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