传输理论 （英語：tansport theory 、transportation theory ），又称为运输理论 ，是数学、经济学等学科中研究最优运输 和资源配置 的理论。该问题最早由法国数学家加斯帕尔·蒙日 于1781年提出。[ 1]
1920年代，A·N·托尔斯泰是最早运用数学方法研究传输问题的学者之一。1930年，他在苏联国家交通部编纂的《运输规划》第一卷中发表了题为《寻找太空货物运输的最小千公里方法》的论文。[ 2] [ 3]
第二次世界大战 期间，苏联数学家、经济学家列昂尼德·坎托罗维奇 在该领域取得了重要进展。[ 4] 蒙日-坎托罗维奇运输问题 （Monge–Kantorovich transportation problem ）。 [ 5] 线性规划 形式也被称为希区柯克 库普曼斯 运输问题。[ 6]
假设有
m
{\displaystyle m}
n
{\displaystyle n}
欧几里得平面
R
2
{\displaystyle \mathbb {R} ^{2}}
不相交 的子集
M
{\displaystyle M}
F
{\displaystyle F}
c
:
R
2
×
R
2
→
[
0
,
∞
)
{\displaystyle c:\mathbb {R} ^{2}\times \mathbb {R} ^{2}\to [0,\infty )}
c
(
x
,
y
)
{\displaystyle c(x,y)}
x
{\displaystyle x}
y
{\displaystyle y}
双射
T
:
M
→
F
{\displaystyle T:M\to F}
m
∈
M
{\displaystyle m\in M}
T
(
m
)
∈
F
{\displaystyle T(m)\in F}
T
{\displaystyle T}
c
(
T
)
:=
∑
m
∈
M
c
(
m
,
T
(
m
)
)
{\displaystyle c(T):=\sum _{m\in M}c(m,T(m))}
在所有
M
{\displaystyle M}
F
{\displaystyle F}
任务分配问题 。更具体地说，它等价于在二分图 中寻找最小权重匹配。
下面这个简单的例子说明了成本函数在确定最优传输计划中的重要性。假设我们有
n
{\displaystyle n}
实数线 ），形成连续一排书。我们希望将它们重新排列，在保持其连续性的同时将整体向右移动一本书的宽度。针对这个问题，有两个显而易见的最优传输候选方案：
将所有
n
{\displaystyle n}
将最左侧的书向右移动
n
{\displaystyle n}
如果成本函数与欧几里得距离成正比（即
c
(
x
,
y
)
=
α
‖
x
−
y
‖
{\displaystyle c(x,y)=\alpha \|x-y\|}
α
>
0
{\displaystyle \alpha >0}
凸成本函数 （即
c
(
x
,
y
)
=
α
‖
x
−
y
‖
2
{\displaystyle c(x,y)=\alpha \|x-y\|^{2}}
α
>
0
{\displaystyle \alpha >0}
需要注意的是，上述成本函数仅考虑书籍本身移动的水平距离，而没有考虑拿起每本书并将其移动到位的设备所行进的水平距离。如果考虑后者，那么在两种传输计划中，第二种方案对于欧几里得距离始终是最优的，而第一种方案则对于平方欧几里得距离是最优的（至少有三本书的情况下）。
以下传输问题的表述由弗兰克·劳伦·希区柯克提出：
假设有
m
{\displaystyle m}
x
1
,
…
,
x
m
{\displaystyle x_{1},\ldots ,x_{m}}
x
i
{\displaystyle x_{i}}
a
(
x
i
)
{\displaystyle a(x_{i})}
n
{\displaystyle n}
y
1
,
…
,
y
n
{\displaystyle y_{1},\ldots ,y_{n}}
y
j
{\displaystyle y_{j}}
b
(
y
j
)
{\displaystyle b(y_{j})}
c
(
x
i
,
y
j
)
{\displaystyle c(x_{i},\ y_{j})}
x
i
{\displaystyle x_{i}}
y
j
{\displaystyle y_{j}}
德尔伯特·雷·富尔克森 提出[ 7] 小莱斯特·伦道夫·福特 合著的《网络流》（Flows in Networks ）（1962年）一书中得到了阐述。[ 8] 佳林·库普曼斯 也为运输经济学 与资源分配问题的表述作出了贡献。
由于黎曼几何 和测度论 的发展，在现代或更加技术性的文献中传输问题的表述有所不同。不过，上述矿山与工厂的简单例子还是可以作为考虑抽象形式时一个有用的参照。此时我们可以考虑并非所有矿山和工厂都营业的情况，并允许一个矿山向多家工厂供货，而一家工厂也可以从多个矿山接受矿石。
假设
X
{\displaystyle X}
Y
{\displaystyle Y}
可分 度量空间 ，使得
X
{\displaystyle X}
Y
{\displaystyle Y}
概率测度 都是拉东测度 ，并假设
c
:
X
×
Y
→
[
0
,
∞
)
{\displaystyle c:X\times Y\to [0,\infty )}
博雷尔可测函数 。给定
X
{\displaystyle X}
μ
{\displaystyle \mu }
Y
{\displaystyle Y}
ν
{\displaystyle \nu }
T
:
X
→
Y
{\displaystyle T:X\to Y}
inf
{
∫
X
c
(
x
,
T
(
x
)
)
d
μ
(
x
)
|
T
∗
(
μ
)
=
ν
}
,
{\displaystyle \inf \left\{\left.\int _{X}c(x,T(x))\,\mathrm {d} \mu (x)\right|T_{*}(\mu )=\nu \right\},}
其中
T
∗
(
μ
)
{\displaystyle T_{*}(\mu )}
T
{\displaystyle T}
μ
{\displaystyle \mu }
T
{\displaystyle T}
最优传输问题的蒙日形式有其局限性，因为有时可能不存在满足
T
∗
(
μ
)
=
ν
{\displaystyle T_{*}(\mu )=\nu }
T
{\displaystyle T}
μ
{\displaystyle \mu }
狄拉克测度 而
ν
{\displaystyle \nu }
此时可以通过采用最优传输问题的坎托罗维奇形式来克服这一局限，即寻找
X
×
Y
{\displaystyle X\times Y}
γ
{\displaystyle \gamma }
inf
{
∫
X
×
Y
c
(
x
,
y
)
d
γ
(
x
,
y
)
|
γ
∈
Γ
(
μ
,
ν
)
}
,
{\displaystyle \inf \left\{\left.\int _{X\times Y}c(x,y)\,\mathrm {d} \gamma (x,y)\right|\gamma \in \Gamma (\mu ,\nu )\right\},}
其中
Γ
(
μ
,
ν
)
{\displaystyle \Gamma (\mu ,\nu )}
X
×
Y
{\displaystyle X\times Y}
边缘分布
μ
{\displaystyle \mu }
ν
{\displaystyle \nu }
[ 9]
c
{\displaystyle c}
Γ
(
μ
,
ν
)
{\displaystyle \Gamma (\mu ,\nu )}
X
{\displaystyle X}
Y
{\displaystyle Y}
沃瑟斯坦度量 ）。西古德·安格嫩特 艾伦·坦嫩鲍姆 [ 10]
坎托罗维奇问题的最小值等于
sup
(
∫
X
φ
(
x
)
d
μ
(
x
)
+
∫
Y
ψ
(
y
)
d
ν
(
y
)
)
,
{\displaystyle \sup \left(\int _{X}\varphi (x)\,\mathrm {d} \mu (x)+\int _{Y}\psi (y)\,\mathrm {d} \nu (y)\right),}
其中上确界 遍历所有有界 且连续 、满足
φ
(
x
)
+
ψ
(
y
)
≤
c
(
x
,
y
)
{\displaystyle \varphi (x)+\psi (y)\leq c(x,y)}
的函数对。
将以上表述中的符号翻转更利于从经济学角度解释这一问题。假设
x
∈
X
{\displaystyle x\in X}
y
∈
Y
{\displaystyle y\in Y}
Φ
(
x
,
y
)
=
−
c
(
x
,
y
)
{\displaystyle \Phi (x,y)=-c(x,y)}
x
{\displaystyle x}
y
{\displaystyle y}
u
(
x
)
=
−
φ
(
x
)
{\displaystyle u(x)=-\varphi (x)}
v
(
y
)
=
−
ψ
(
y
)
{\displaystyle v(y)=-\psi (y)}
sup
{
∫
X
×
Y
Φ
(
x
,
y
)
d
γ
(
x
,
y
)
,
γ
∈
Γ
(
μ
,
ν
)
}
{\displaystyle \sup \left\{\int _{X\times Y}\Phi (x,y)d\gamma (x,y),\gamma \in \Gamma (\mu ,\nu )\right\}}
它的对偶 形式为：
inf
{
∫
X
u
(
x
)
d
μ
(
x
)
+
∫
Y
v
(
y
)
d
ν
(
y
)
:
u
(
x
)
+
v
(
y
)
≥
Φ
(
x
,
y
)
}
{\displaystyle \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
→
R
{\displaystyle u:X\to \mathbb {R} }
v
:
Y
→
R
{\displaystyle v:Y\to \mathbb {R} }
v
(
y
)
=
sup
x
{
Φ
(
x
,
y
)
−
u
(
x
)
}
{\displaystyle v(y)=\sup _{x}\left\{\Phi (x,y)-u(x)\right\}}
可以将
u
(
x
)
{\displaystyle u(x)}
x
{\displaystyle x}
v
(
y
)
{\displaystyle v(y)}
y
{\displaystyle y}
[ 11]
对于
1
≤
p
<
∞
{\displaystyle 1\leq p<\infty }
P
p
(
R
)
{\displaystyle {\mathcal {P}}_{p}(\mathbb {R} )}
R
{\displaystyle \mathbb {R} }
p
{\displaystyle p}
矩 有限的概率测度 的集合。设
μ
,
ν
∈
P
p
(
R
)
{\displaystyle \mu ,\nu \in {\mathcal {P}}_{p}(\mathbb {R} )}
c
(
x
,
y
)
=
h
(
x
−
y
)
{\displaystyle c(x,y)=h(x-y)}
h
:
R
→
[
0
,
∞
)
{\displaystyle h:\mathbb {R} \to [0,\infty )}
凸函数 。
如果
μ
{\displaystyle \mu }
原子
μ
{\displaystyle \mu }
累积分布函数
F
μ
:
R
→
[
0
,
1
]
{\displaystyle F_{\mu }:\mathbb {R} \to [0,1]}
F
ν
−
1
∘
F
μ
:
R
→
R
{\displaystyle F_{\nu }^{-1}\circ F_{\mu }:\mathbb {R} \to \mathbb {R} }
h
{\displaystyle h}
可以得到
min
γ
∈
Γ
(
μ
,
ν
)
∫
R
2
c
(
x
,
y
)
d
γ
(
x
,
y
)
=
∫
0
1
c
(
F
μ
−
1
(
s
)
,
F
ν
−
1
(
s
)
)
d
s
.
{\displaystyle \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年给出了对此的证明。[ 12]
在边缘分布
μ
{\displaystyle \mu }
ν
{\displaystyle \nu }
μ
x
{\displaystyle \mu _{x}}
ν
y
{\displaystyle \nu _{y}}
x
∈
X
{\displaystyle x\in \mathbf {X} }
y
∈
Y
{\displaystyle y\in \mathbf {Y} }
γ
x
y
{\displaystyle \gamma _{xy}}
x
y
{\displaystyle xy}
∑
x
∈
X
,
y
∈
Y
γ
x
y
c
x
y
{\displaystyle \sum _{x\in \mathbf {X} ,y\in \mathbf {Y} }\gamma _{xy}c_{xy}}
并满足约束条件
∑
y
∈
Y
γ
x
y
=
μ
x
,
∀
x
∈
X
{\displaystyle \sum _{y\in \mathbf {Y} }\gamma _{xy}=\mu _{x},\forall x\in \mathbf {X} }
∑
x
∈
X
γ
x
y
=
ν
y
,
∀
y
∈
Y
.
{\displaystyle \sum _{x\in \mathbf {X} }\gamma _{xy}=\nu _{y},\forall y\in \mathbf {Y} .}
为了将这一问题作为线性规划 问题处理，我们需要将矩阵
γ
x
y
{\displaystyle \gamma _{xy}}
vec
{\displaystyle \operatorname {vec} }
列主序
(
1
1
×
|
Y
|
⊗
I
|
X
|
)
vec
(
γ
)
=
μ
{\displaystyle \left(1_{1\times |\mathbf {Y} |}\otimes I_{|\mathbf {X} |}\right)\operatorname {vec} (\gamma )=\mu }
(
I
|
Y
‖
⊗
1
1
×
|
X
|
)
vec
(
γ
)
=
ν
{\displaystyle \left(I_{|\mathbf {Y} \|}\otimes 1_{1\times |\mathbf {X} |}\right)\operatorname {vec} (\gamma )=\nu }
其中
⊗
{\displaystyle \otimes }
克罗内克积 ，
1
n
×
m
{\displaystyle 1_{n\times m}}
n
×
m
{\displaystyle n\times m}
I
n
{\displaystyle I_{n}}
n
{\displaystyle n}
z
=
vec
(
γ
)
{\displaystyle z=\operatorname {vec} (\gamma )}
Minimize
vec
(
c
)
⊤
z
subject to:
z
≥
0
,
(
1
1
×
|
Y
|
⊗
I
|
X
|
I
|
Y
|
⊗
1
1
×
|
X
|
)
z
=
(
μ
ν
)
{\displaystyle {\begin{aligned}&{\text{Minimize }}&&\operatorname {vec} (c)^{\top }z\\[4pt]&{\text{subject to:}}&&z\geq 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{aligned}}}
这一问题可以很容易地通过大规模线性规划求解器计算。[ 13]
在半离散情况下，令
X
=
Y
=
R
d
{\displaystyle X=Y=\mathbb {R} ^{d}}
μ
{\displaystyle \mu }
R
d
{\displaystyle \mathbb {R} ^{d}}
ν
=
∑
j
=
1
J
ν
j
δ
y
i
{\displaystyle \nu =\sum _{j=1}^{J}\nu _{j}\delta _{y_{i}}}
ν
j
{\displaystyle \nu _{j}}
y
j
∈
R
d
{\displaystyle y_{j}\in \mathbb {R} ^{d}}
[ 14]
inf
{
∫
X
∑
j
=
1
J
c
(
x
,
y
j
)
d
γ
j
(
x
)
,
γ
∈
Γ
(
μ
,
ν
)
}
{\displaystyle \inf \left\{\int _{X}\sum _{j=1}^{J}c(x,y_{j})\,d\gamma _{j}(x),\gamma \in \Gamma (\mu ,\nu )\right\}}
其中
γ
∈
Γ
(
μ
,
ν
)
{\displaystyle \gamma \in \Gamma (\mu ,\nu )}
∫
X
d
γ
j
(
x
)
=
ν
j
{\displaystyle \int _{X}d\gamma _{j}(x)=\nu _{j}}
∑
j
d
γ
j
(
x
)
=
d
μ
(
x
)
{\displaystyle \sum _{j}d\gamma _{j}(x)=d\mu (x)}
而其对偶形式则为
sup
{
∫
X
φ
(
x
)
d
μ
(
x
)
+
∑
j
=
1
J
ψ
j
ν
j
:
ψ
j
+
φ
(
x
)
≤
c
(
x
,
y
j
)
}
{\displaystyle \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
ψ
∈
R
J
{
∫
X
inf
j
{
c
(
x
,
y
j
)
−
ψ
j
}
d
μ
(
x
)
+
∑
j
=
1
J
ψ
j
ν
j
}
{\displaystyle \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
{\displaystyle c(x,y)=|x-y|^{2}/2}
j
{\displaystyle j}
x
∈
X
{\displaystyle x\in \mathbf {X} }
幂图 [ 15]
假设一个特殊情形
μ
=
N
(
0
,
Σ
X
)
{\displaystyle \mu ={\mathcal {N}}(0,\Sigma _{X})}
ν
=
N
(
0
,
Σ
Y
)
{\displaystyle \nu ={\mathcal {N}}(0,\Sigma _{Y})}
c
(
x
,
y
)
=
|
y
−
A
x
|
2
/
2
{\displaystyle c(x,y)=|y-Ax|^{2}/2}
A
{\displaystyle A}
φ
(
x
)
=
−
x
⊤
Σ
X
−
1
/
2
(
Σ
X
1
/
2
A
⊤
Σ
Y
A
Σ
X
1
/
2
)
1
/
2
Σ
X
−
1
/
2
x
/
2
{\displaystyle \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}
ψ
(
y
)
=
−
y
⊤
A
Σ
X
1
/
2
(
Σ
X
1
/
2
A
⊤
Σ
Y
A
Σ
X
1
/
2
)
−
1
/
2
Σ
X
1
/
2
A
y
/
2
{\displaystyle \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
⊤
)
−
1
Σ
X
−
1
/
2
(
Σ
X
1
/
2
A
⊤
Σ
Y
A
Σ
X
1
/
2
)
1
/
2
Σ
X
−
1
/
2
x
{\displaystyle 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年证明了该情况下的解。[ 16]
令
X
{\displaystyle X}
可分 希尔伯特空间 ，定义
P
p
(
X
)
{\displaystyle {\mathcal {P}}_{p}(X)}
X
{\displaystyle X}
p
{\displaystyle p}
矩 有限的概率测度 的集合，
P
p
r
(
X
)
{\displaystyle {\mathcal {P}}_{p}^{r}(X)}
g
{\displaystyle g}
X
{\displaystyle X}
高斯测度
g
(
N
)
=
0
{\displaystyle g(N)=0}
μ
(
N
)
=
0
{\displaystyle \mu (N)=0}
假设
μ
∈
P
p
r
(
X
)
{\displaystyle \mu \in {\mathcal {P}}_{p}^{r}(X)}
ν
∈
P
p
(
X
)
{\displaystyle \nu \in {\mathcal {P}}_{p}(X)}
c
(
x
,
y
)
=
|
x
−
y
|
p
/
p
{\displaystyle c(x,y)=|x-y|^{p}/p}
p
∈
(
1
,
∞
)
,
p
−
1
+
q
−
1
=
1
{\displaystyle p\in (1,\infty ),p^{-1}+q^{-1}=1}
κ
{\displaystyle \kappa }
r
∈
L
p
(
X
,
μ
;
X
)
{\displaystyle r\in L^{p}(X,\mu ;X)}
κ
=
(
i
d
X
×
r
)
∗
(
μ
)
∈
Γ
(
μ
,
ν
)
.
{\displaystyle \kappa =(\mathrm {id} _{X}\times r)_{*}(\mu )\in \Gamma (\mu ,\nu ).}
此外，如果
ν
{\displaystyle \nu }
μ
{\displaystyle \mu }
x
∈
X
{\displaystyle x\in X}
局部利普希茨 、
c
{\displaystyle c}
φ
{\displaystyle \varphi }
r
(
x
)
=
x
−
|
∇
φ
(
x
)
|
q
−
2
∇
φ
(
x
)
{\displaystyle r(x)=x-|\nabla \varphi (x)|^{q-2}\,\nabla \varphi (x)}
其中
∇
φ
{\displaystyle \nabla \varphi }
φ
{\displaystyle \varphi }
加托导数 。
考虑上述离散问题的一个变体：在原始问题的目标函数中添加一个熵正则化项
Minimize
∑
x
∈
X
,
y
∈
Y
γ
x
y
c
x
y
+
ε
γ
x
y
ln
γ
x
y
subject to:
γ
≥
0
∑
y
∈
Y
γ
x
y
=
μ
x
,
∀
x
∈
X
∑
x
∈
X
γ
x
y
=
ν
y
,
∀
y
∈
Y
{\displaystyle {\begin{aligned}&{\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 \geq 0\\[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{aligned}}}
相应的对偶问题为
max
φ
,
ψ
∑
x
∈
X
φ
x
μ
x
+
∑
y
∈
Y
ψ
y
v
y
−
ε
∑
x
∈
X
,
y
∈
Y
exp
(
φ
x
+
ψ
y
−
c
x
y
ε
)
{\displaystyle \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)}
相较于不含正则化项的问题，原先对偶问题中的硬约束（
φ
x
+
ψ
y
−
c
x
y
≥
0
{\displaystyle \varphi _{x}+\psi _{y}-c_{xy}\geq 0}
ε
exp
(
(
φ
x
+
ψ
y
−
c
x
y
)
/
ε
)
{\displaystyle \varepsilon \exp \left((\varphi _{x}+\psi _{y}-c_{xy})/\varepsilon \right)}
式5.1:
μ
x
=
∑
y
∈
Y
exp
(
φ
x
+
ψ
y
−
c
x
y
ε
)
∀
x
∈
X
{\displaystyle \mu _{x}=\sum _{y\in \mathbf {Y} }\exp \left({\frac {\varphi _{x}+\psi _{y}-c_{xy}}{\varepsilon }}\right)~\forall x\in \mathbf {X} }
式5.2:
ν
y
=
∑
x
∈
X
exp
(
φ
x
+
ψ
y
−
c
x
y
ε
)
∀
y
∈
Y
{\displaystyle \nu _{y}=\sum _{x\in \mathbf {X} }\exp \left({\frac {\varphi _{x}+\psi _{y}-c_{xy}}{\varepsilon }}\right)~\forall y\in \mathbf {Y} }
令
A
{\displaystyle A}
|
X
|
×
|
Y
|
{\displaystyle |\mathbf {X} |\times |\mathbf {Y} |}
A
x
y
=
exp
(
−
c
x
y
/
ε
)
{\displaystyle A_{xy}=\exp \left(-c_{xy}/\varepsilon \right)}
D
1
{\displaystyle D_{1}}
D
2
{\displaystyle D_{2}}
|
X
|
{\displaystyle |\mathbf {X} |}
|
Y
|
{\displaystyle |\mathbf {Y} |}
D
1
A
D
2
1
|
Y
|
=
μ
{\displaystyle D_{1}AD_{2}1_{|\mathbf {Y} |}=\mu }
(
D
1
A
D
2
)
⊤
1
|
X
|
=
ν
{\displaystyle (D_{1}AD_{2})^{\top }1_{|\mathbf {X} |}=\nu }
D
1
{\displaystyle D_{1}}
D
2
{\displaystyle D_{2}}
辛克宏定理 的推广，可以使用辛克宏-诺普算法 进行求解。[ 17] 式5.1
φ
x
{\displaystyle \varphi _{x}}
式5.2
ψ
y
{\displaystyle \psi _{y}}
坐标下降法 。
蒙日-坎托罗维奇运输问题已广泛运用于许多领域，例如：
^ 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.
^ Schrijver, Alexander, Combinatorial Optimization ISBN 3540443894 . Cf. p. 362
^ Ivor Grattan-Guinness, Ivor, Companion encyclopedia of the history and philosophy of the mathematical sciences p.831
^ L. Kantorovich. On the translocation of masses. C.R. (Doklady) Acad. Sci. URSS (N.S.), 37:199–201, 1942.
^ Cédric Villani. Topics in Optimal Transportation. American Mathematical Soc. 2003: 66. ISBN 978-0-8218-3312-4 ^ Singiresu S. Rao. Engineering Optimization: Theory and Practice 4th. John Wiley & Sons. 2009: 221. ISBN 978-0-470-18352-6 ^ D. R. Fulkerson (1956) Hitchcock Transportation Problem , RAND corporation.
^ 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 .
^ Angenent, S.; Haker, S.; Tannenbaum, A. Minimizing flows for the Monge–Kantorovich problem. SIAM J. Math. Anal. 2003, 35 (1): 61–97. CiteSeerX 10.1.1.424.1064 doi:10.1137/S0036141002410927 ^ Galichon, Alfred. Optimal Transport Methods in Economics . Princeton University Press, 2016.
^ Rachev, Svetlozar T., and Ludger Rüschendorf. Mass Transportation Problems: Volume I: Theory . Vol. 1. Springer, 1998.
^ 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.
^ Aurenhammer, Franzdoi=10.1137/0216006, Power diagrams: properties, algorithms and applications, SIAM Journal on Computing, 1987, 16 (1): 78–96, MR 0873251 ^ 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
^ Haker, Steven; Zhu, Lei; Tannenbaum, Allen; Angenent, Sigurd. Optimal Mass Transport for Registration and Warping. International Journal of Computer Vision. 1 December 2004, 60 (3): 225–240. CiteSeerX 10.1.1.59.4082 ISSN 0920-5691 S2CID 13261370 doi:10.1023/B:VISI.0000036836.66311.97 （英语） . ^ Glimm, T.; Oliker, V. Optical Design of Single Reflector Systems and the Monge–Kantorovich Mass Transfer Problem. Journal of Mathematical Sciences. 1 September 2003, 117 (3): 4096–4108. ISSN 1072-3374 S2CID 8301248 doi:10.1023/A:1024856201493 （英语） . ^ Kasim, Muhammad Firmansyah; Ceurvorst, Luke; Ratan, Naren; Sadler, James; Chen, Nicholas; Sävert, Alexander; Trines, Raoul; Bingham, Robert; Burrows, Philip N. Quantitative shadowgraphy and proton radiography for large intensity modulations. Physical Review E. 16 February 2017, 95 (2): 023306. Bibcode:2017PhRvE..95b3306K PMID 28297858 S2CID 13326345 arXiv:1607.04179 doi:10.1103/PhysRevE.95.023306 ^ Metivier, Ludovic. Measuring the misfit between seismograms using an optimal transport distance: application to full waveform inversion . Geophysical Journal International. 24 February 2016, 205 (1): 345–377. Bibcode:2016GeoJI.205..345M doi:10.1093/gji/ggw014
![{\displaystyle F_{\mu }:\mathbb {R} \to [0,1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fc2bc98f006bf4dab01d2ca05542d450461b5e0c)
![{\displaystyle {\begin{aligned}&{\text{Minimize }}&&\operatorname {vec} (c)^{\top }z\\[4pt]&{\text{subject to:}}&&z\geq 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{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/336ccbaf6495e68607b64544c8fda5321383bc51)
![{\displaystyle {\begin{aligned}&{\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 \geq 0\\[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{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/29f9f996d5cd0607caf4283324f584bafe9d0aee)
. doi:10.1137/S0036141002410927.
