傳輸理論 （英語：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.
