교통이론(수학)

수학과 경제학에서 교통이론이나 교통이론은 최적의 교통수단과 자원배분을 연구하기 위해 붙여진 이름이다. 이 문제는 1781년 프랑스의 수학자 가스파드 몽에 의해 공식화되었다.^[1]

1920년대 A.N. 톨스토이는 교통 문제를 수학적으로 연구한 최초의 사람 중 한 명이었다. 1930년, 소비에트 연방의 국가 교통 위원회를 위한 교통 계획 제1권 콜렉션에서, 그는 "우주에서의 화물 수송에서 최소 킬로미터의 유적을 찾는 방법"이라는 논문을 발표했다.^[2][3]

제2차 세계 대전 동안 소련의 수학자 겸 경제학자 레오니드 칸토로비치에 의해 이 분야에서 주요한 진보가 이루어졌다.^[4] 결과적으로, 언급된 문제는 때때로 몽게-칸토로비치 교통 문제로 알려져 있다.^[5] 운송 문제의 선형 프로그래밍 공식은 히치콕-쿠프만 운송 문제라고도 알려져 있다.^[6]

동기

광산 및 공장

우리가 철광석을 채굴하는 m광산의 집합체, 그리고 광산이 생산하는 철광석을 사용하는 n개의 공장들을 가지고 있다고 가정해보자. 이러한 광산들과 공장들이 유클리드 평면² R의 두 개의 분리된 하위 세트 M과 F를 형성한다고 주장하기 위해 가정해보자. 또한 비용함수² c : R × R² → [0, ∞)을 가지고 있다고 가정하여 c(x, y)는 하나의 철을 x에서 y로 운송하는 비용이다. 간단히 말해서, 우리는 수송하는 데 걸리는 시간을 무시한다. 또한 각 광산은 공장 하나만 공급할 수 있으며(출하물 분할은 안 됨)각 공장에서는 정확히 한 개의 선적을 가동해야 한다고 가정한다(공장은 절반 또는 두 배의 용량으로 가동할 수 없다). 위의 가정을 한 후에, 운송계획은 T : M → F의 편향이다. 즉, 각 광산 m ∈ M은 대상 공장 T(m) f F를 정확히 1개씩 공급하고, 각 공장은 정확히 1개의 광산이 공급한다. 우리는 최적의 운송 계획인 총비용의 계획 T를 찾기를 원한다.

$[\displaystyle c(T):=\sum _{m\in M}c(m,T(m)}}$

M에서 F까지 가능한 모든 운송 계획 중에서 가장 적은 것이다. 이것은 교통 문제의 특별한 경우에 동기를 부여한다. 좀 더 구체적으로 말하면, 그것은 초당적 그래프에서 최소 무게 일치점을 찾는 것과 같다.

이동도서 : 비용함수의 중요성

다음의 간단한 예는 최적의 운송 계획을 결정하는 데 있어서 비용 함수의 중요성을 보여준다. 선반에 같은 폭의 책을 한 권씩 연속된 블록으로 배열했다고 가정합시다. 우리는 그것들을 다른 연속 블록으로 재배열하고 싶지만, 책 너비 하나를 오른쪽으로 옮겼다. 최적의 운송 계획을 위한 두 가지 분명한 후보:

1. 모든 n권의 책을 한 권의 책 너비로 오른쪽으로 이동("많은 작은 움직임");
2. 가장 왼쪽의 책 너비 n 책 너비를 오른쪽으로 옮기고 다른 모든 책들을 고치다("한 번의 큰 움직임").

비용 함수가 유클리드 거리(c(x, y) = α x - y )에 비례한다면 이 두 후보 모두 최적이다. 반면에 유클리드 거리(c(x, y) = α x - y )의 제곱에 비례하는 엄격히 볼록한 비용 함수를 선택한다면, "여러 가지 작은 움직임" 옵션이 고유한 미니마이저가 된다.

위의 비용 함수는 각 책을 집어서 제자리에 옮기기 위해 사용하는 장치에 의해 이동하는 수평 거리가 아니라 책들이 이동하는 수평 거리만을 고려한다는 점에 유의한다. 만약 후자를 대신 고려한다면, 두 번째 운송계획은 유클리드 거리에 대해 항상 최적인 반면, 최소 3권의 책이 있다면, 첫 번째 운송계획은 제곱 유클리드 거리에 대해 최적이다.

히치콕 문제

F. L. 히치콕의 운송 문제 공식은 다음과 같다.^[7]

거기 m출처 x1, 상품의 공급의 자이와 엔 싱크에서()나는){\displaystyle a(x_{나는})}단위는 상품에 대한 수요가 b'로 에스파냐 1,…, yn{\displaystyle y_{1},\ldots ,y_{n}},(jy)yj에서{\displaystyle b(y_{j})}과…,)m{\displaystyle x_{1},\ldots ,x_{m}}, 있다고 가정하자. $a{\displaystyle }$( ${\displaystyle {}_{}}$ ${\displaystyle i_{}}$, ${\displaystyle \text{y}{}_{}}$ ${\displaystyle j_{}}$) ${\displaystyle a(x_{i}},\ y_{j}}}$이(가) x에서_i y로_j 선적하는 단가라면 공급자의 수요를 만족시키는 흐름을 찾아 유량 비용을 최소화한다. 물류의 이 도전은 D가 떠안았다. R.^[9] 풀커슨과^[8] L. R. 포드 주니어와 함께 쓴 "네트워크의 흐름"(1962)에서

Tjalling Koopmans는 또한 운송 경제학의 형성 및 자원 배분의 공로를 인정받고 있다.

문제의 추상적 공식화

몽게와 칸토로비치 공식화

현대적이거나 더 많은 기술 문헌에 기술되어 있는 운송 문제는 리만 기하학과 측량 이론의 발달로 인해 다소 다르게 보인다. 지뢰-요소의 예는 간단하지만 추상적인 경우를 생각할 때 유용한 기준점이다. 이 설정에서 우리는 사업을 위해 모든 광산과 공장을 개방하지 않기를 바라며, 광산이 하나 이상의 공장을 공급할 수 있도록 허용하고, 공장들이 둘 이상의 광산에서 철을 받아들일 수 있도록 허용한다.

X(또는 Y)에 대한 확률 측정값이 라돈 측정값(즉, 라돈 공간)이 되도록 X와 Y를 두 개의 분리 가능한 메트릭 공간이 되도록 한다. c : X × Y → [0, ∞]를 Borel 측정 가능한 함수로 한다. X와 Y에 대한 확률 측정 μs를 감안할 때, Monge의 최적 교통 문제 제정은 최소치를 실현하는 교통 지도 T : X → Y를 찾는 것이다.

$\displaystyle \inf \왼쪽\{\왼쪽.\int _{X}c(x,T(x))\,\mathrm {d} \mu(x)\;\right \;;;;T_{*}(\mu )=\nu \right\}}$

여기서 T_∗(μ)는 μ의 앞으로 T를 나타낸다. 이 최소치를 획득하는 지도 T(즉, 최소값 대신 최소값으로 한다)를 "최적 전송 지도"라고 한다.

최적의 수송 문제를 몽에가 공식화한 것은, T_∗(μ) = ν을 만족하는 T가 없는 경우도 있기 때문에, 예를 들어 μ는 디락 측정치지만 ν은 그렇지 않은 경우에 이러한 현상이 발생한다.

우리는 칸토로비치의 최적 교통 문제 제정을 채택함으로써 이를 개선할 수 있는데, 이는 최저치를 달성하는 X × Y에서 확률 측정 γ을 찾는 것이다.

$\displaystyle \inf \왼쪽\{\왼쪽.\int _{X\time Y}c(x,y)\\mathrm {d} \gamma(x,y)\right \gamma \in \Mu ,\nu )\right\}$

여기서 μ(μ, μ)는 X × Y에 대한 모든 확률 측정값의 모음을 나타내며, X에는 마진 μ, Y에는 마진 μ를 나타낸다. 비용함수 c가 더 낮은 반연속성일 때, 그리고 ,(μ, measures)은 엄격한 조치 집합일 때^[10](라돈 공간 X와 Y에 대해 보장된다). (이 제형을 확률 측정 공간에 대한 와세슈타인 측정지표₁ W의 정의와 비교한다.) 몽게-칸토로비치 문제 해결을 위한 구배 강하 공식은 시구르드 안게넨트, 스티븐 헤커, 앨런 탄넨바움 등이 제공했다.^[11]

이중성 공식

칸토로비치 문제의 최소치는 다음과 같다.

${\dapplaystyle \sup \left(\int_{X}\varphi(x)\,\mathrm {d} \mu(x)+\int_{Y}\psi(y)\,\mathrm {d} \nu(y)\right),}$

여기서 supremeum은 경계 함수 및 연속 함수 $\phi {\displaystyle }$: ${\displaystyle X}$→ ${\displaystyle R\mathbf{}}$ ${\$ 및$$ ${\displaystyle \psi }$: Y${\displaystyle }$→ ${\displaystyle R\mathbf{}}$ ${\$:$Y$$\rightarrow \mathbf {R}.$

$\displaystyle \varphi (x)+\properties (y)\leq c(x,y).}$

경제해석

간판을 뒤집으면 경제 해석이 더 명확해진다. Let ${\displaystyle \textstyle x\in X}$ stand for the vector of characteristics of a worker, ${\displaystyle \textstyle y\in Y}$ for the vector of characteristics of a firm, and ${\displaystyle \textstyle \Phi \left(x,y\right)=-c\left(x,y\right)}$ for the economic output generated by worker ${\displaystyle \textstyle x}$ matched with firm ${\displaystyle \textstyle y}$. Setting ${\displaystyle \textstyle u\left(x\right)=-\varphi \left(x\right)}$ and ${\displaystyle \textstyle v\left(y\right)=-\psi \left(y\right)}$, the Monge-Kantorovich 문제 다시 쓰기:

이중: 여기서 최소값이 경계 함수 ${\displaystyle u}$: X${\displaystyle }$→ R${\$ u:$X\rightarrow$\mathbf {$R}$ 및$v$: ${\displaystyle \mathrm{Y<img\; alt="\{\backslash displaystyle\; \backslash textstyle\; u:X\backslash rightarrow\; \backslash mathbf\; \{R\}\; \}"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/b62097d5a5bec040b3eb4b639c8e7555872c9ba5"\; style="vertical-align:\; -0.338ex;\; width:10.864ex;\; height:2.176ex;"\; papago-attr-id="438">}}$→ R${\$$Y\rightarrow \mathbf {R}$}. 이중 문제에 해결책이 있다면 다음과 같은 것을 알 수 있다. $u{\displaystyle }$( ${\displaystyle x}$) ${\$$displaystyle$$u\reft(x\$wright$)$는 x $타입{\displaystyle }$ $\$ $\$$textstyle x}$ 및$$${\displaystyle v}$( y )${\displaystyle }$${\$$displaystyle v\left(y$$\wright)$의 노동자의 평형임금으로 해석하도록$$$$ 한다$.$^[12]

문제 해결

실선의 최적 교통수단

≤ <$∞{\$$displaystyle 1\leq p<\$leq p$>}$에 대해 ${\displaystyle P_{}}$($){\displaystyle {p}_{p}(\mathbf${$R$$})}}}$은는) $p{\displaystyle }$ {\$displaystyle p}$ -th$$ 모멘트를 갖는 $R$ ${\$ \mathbf$\$matbf {R}에 대한 확률 측정값의 컬렉션을 나타낸다$.$ Let ${\displaystyle \mu ,\nu \in {\mathcal {P}}_{p}(\mathbf {R} )}$ and let ${\displaystyle c(x,y)=h(x-y)}$, where ${\displaystyle h:\mathbf {R} \rightarrow [0,\infty )}$ is a convex function.

1. If ${\displaystyle \mu }$ has no atom, i.e., if the cumulative distribution function ${\displaystyle F_{\mu }=\mathbf {R} \rightarrow [0,1]}$ of ${\displaystyle \mu }$ is a continuous function, then ${\displaystyle F_{\nu }^{-1}\circ F_{\mu }:\mathbf {R} \to \m$$atsbf {R} }$은(는) 최적의 전송 맵이다. $h{\displaystyle }$ ${\displaystyle h}$이(가) 엄격히 볼록한 경우$$ 이 맵은 고유한 최적 전송 맵이다.
2. 우리는 가지고 있다.

${\displaystyle \min _{\gamma \in \Gamma (\mu ,\nu )}\int _{2}}c(x,y)\\,\mathrm {d} \d} \gamma (x,y)=\int _{0}c\{1}c\{-1}s,F_{\nu }^{-1(s)\right)\,\mathrm {d}s.}$

이 해결책의 증거는 Rachev & Rüschendorf(1998년)에 나타난다.^[13]

이산 버전 및 선형 프로그래밍 공식

여백 ${\$ \$mu }$과($와{\displaystyle }$) ${\$$displaystyle \textstyle \nu$$}$이(가) 분리된$$ 경우, ${\displaystyle {\mu }_{}}$ ${\displaystyle x_{}}$ ${\$ x$\in$}에$$$각각$ $할당$된$$확률 질량이$$ $되도록{\displaystyle }$ 한다.$\mathbf {X}$ $및$ y ${\displaystyle \in }$ ${\displaystyle Y\mathbf{}}$ ${\$ 그리고 $\gamma {\displaystyle {}_{}}$ ${\displaystyle x_{}}$ ${\displaystyle y_{}}$ ${\$ $_$${xy}}$을(를) x ${\displaystyle y}$ ${\$ 할당$$ 확률은 되도록$$ 한다. 원시 칸토로비치 문제에서 객관적 기능은 그때다.

${\displaystyle \sum _{x\in \mathbf {X},y\in \mathbf {Y}}\gamma _{xy}c_{xy}}}}}$

그리고 제약 조건 ${\displaystyle \mathrm{constraint}}$ $∈$ (μ ,$$) {\$displaystyle$ \$textstyle$ \$gamma \in$ \Gamma $\left(\mu ,\nu \right)$은 다음과 같이 표현된다$$.

${\displaystyle \sum _{y\in \mathbf {Y} }\gamma _{xy}=\mu _{x},\forall x\in \mathbf {X} }$ and ${\displaystyle \sum _{x\in \mathbf {X} }\gamma _{xy}=\nu _{y},\forall y\in \mathbf {Y.$$} }$

이것을 선형 프로그래밍 ${\displaystyle {\mathrm{문제}}_{}}$에 입력하기 위해서는 ${\displaystyle {matrix}_{}}$ x y ${\$ 행렬을 그 열이나 행을 쌓아 ${\displaystyle \mathrm{vec<img\; alt="\{\backslash displaystyle\; \backslash textstyle\; \backslash gamma\; \_\{xy\}\}"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/eb4359ca7761f1360777bf33ea1c3765a92e176f"\; style="vertical-align:\; -1.005ex;\; width:3.194ex;\; height:2.343ex;"\; papago-attr-id="216">}}$ ${\$ 이$$ 작업을 벡터링해야 한다. 열-주요 순서에서 위의 제약조건은 다음과 같이 다시 쓰여진다.

${\displaystyle \left(1_{1\times \left\vert \mathbf {Y} \right\vert }\otimes I_{\left\vert \mathbf {X} \right\vert }\right)\operatorname {vec} \left(\gamma \right)=\mu }$ and ${\displaystyle \left(I_{\left\vert$$\mathbf {Y} \right\vert }\otimes 1_{1\times \left\ret \X} \right\vert \vec} \operatorname {vec} \left(\gamma \right)=\nu }$

여기서 $⊗{\$ $\textstyle \otimes }$은(는) 크론커 $제품$이고$,$ ${\displaystyle \mathrm{1n}}$ $×$ m {\$displaystyle$ \$textstyle$ 1_${n\$$time$ m$}$은 모든 항목이 포함된 크기$$ $n{\displaystyle }$ $×$ m ${\$$displaystystyle$ $n_{n}$의 ID$$ $행렬$이다$.$$\textstyle n$ $결과적$으로 z${\displaystyle }$= ${\displaystyle \mathrm{vec}}$ ${\displaystyle (}$ ($$ )$${\$displaystyle z=\operatorname {vec} \left(\gamma \right$ 문제의 선형 프로그래밍 공식은 다음과 같다.

${\displaystyle \min _{z\geq 0}\vecname {vec} \left(c\오른쪽)^{\top }z}$

s.${\displaystyle \begin{array}{c}{t\mathrm{}}_{}\end{array}}.{\displaystyle }$ ( ${\displaystyle \begin{array}{c}1{\mathrm{}}_{}\end{array}}$ ${\displaystyle \begin{array}{c}{\times }_{}\end{array}}$ ${\displaystyle \begin{array}{c}{Y\mathbf{}}_{}\end{array}}$ ${\displaystyle \begin{array}{c}{\times }_{}\end{array}}$ I X I ${\displaystyle \begin{array}{c}{i\mathbf{}}_{}\end{array}}$ ${\displaystyle \begin{array}{c}{1\mathrm{}}_{}\end{array}}$ ${\displaystyle \begin{array}{c}{\times }_{}\end{array}}$ X${\displaystyle \begin{array}{c}{}_{}\end{array}}$) ${\$time \$vert \mathbf {X}\$vert$}\$$ret$}\ret $\cH$}\$cH$}\mathb$.$$I_{\left$\vert $\mathbf$ {$Y} \right\vert }\otimes$ 1_${1\time\vert \X}$ \right$\vert }\end{pmatrix$}}}}$z$${\displaystyle =}$ (${\displaystyle \mu \genfrac{}{}{0ex}{}{}{}}$ $μ$ ${\displaystyle \{)}$ ${\binom$ {}{\$mu{}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}"$

대규모 선형 프로그래밍 해결기에 쉽게 입력할 수 있다(Galichon (2016년)^[12] 제3.4장 참조).

반물질 케이스

In the semi-discrete case, ${\displaystyle \textstyle X=Y=\mathbf {R} ^{d}}$ and ${\displaystyle \textstyle \mu }$ is a continuous distribution over ${\displaystyle \textstyle \mathbf {R} ^{d}}$, while ${\displaystyle \textstyle \nu =\sum _{j=1}^{$$J}\nu _{j}\delta _{y_{i}}}$ is a discrete distribution which assigns probability mass ${\displaystyle \textstyle \nu _{j}}$ to site ${\displaystyle \textstyle y_{j}\in \mathbf {R} ^{d}}$. In this case, we can see^[14] that the primal and dual Kantorovich problems respectively boil down to:

for the primal, where ${\displaystyle \textstyle \gamma \in \Gamma \left(\mu ,\nu \right)}$ means that ${\displaystyle \textstyle \int _{X}d\gamma _{j}\left(x\right)=\nu _{j}}$ and ${\displaystyle \textstyle \sum _{j}d\gamma _{j}\$$왼쪽(x\오른쪽)=d\mu \left(x\오른쪽)}$및: 다음과 같이 다시 쓸 수 있는 이중의 경우: 이는 구배 강하와 같은 표준 기법으로 해결할 수 있는 유한 차원 볼록 최적화 문제다.

In the case when ${\displaystyle \textstyle c\left(x,y\right)=\left\vert x-y\right\vert ^{2}/2}$, one can show that the set of ${\displaystyle \textstyle x\in \mathbf {X} }$ assigned to a particular site ${\displaystyle \textstyle j}$ is a convex polyhedron. 결과 구성을 전원 다이어그램이라고 한다.^[15]

2차 정규 케이스

Assume the particular case ${\displaystyle \textstyle \mu ={\mathcal {N}}\left(0,\Sigma _{X}\right)}$, ${\displaystyle \textstyle \nu ={\mathcal {N}}\left(0,\Sigma _{Y}\right)}$, and ${\displaystyle \textstyle c\left(x,y\$$right)=\left\vert y-Ax\right\vert ^{2}/2}$ $여기$서 A ${\$은(는) 변환할 수 없다. 그 중 하나가 가지고 있다.

${\displaystyle \varphi \left(x\right)=-x^{\top }\Sigma _{X}^{X}^{X}}\좌측(\Sigma _{X}^{1/2}A^{\top }\Sigma _{Y}A\Sigma _{1/2}\오른쪽)^{1/2}\Sigma _{X}^{X}^{-1/2}x/2}$

${\displaystyle \psi \left(y\right)=-y^{-y^{}A\Sigma _{X}^{X}}\왼쪽(\Sigma _{X}^{1/2}A^{\top }\Sigma _{Y}A\Sigma _{1/2}\오른쪽)^{X}^{-1/2}\Sigma _{X}^{1/2}Ay/2}$

${\displaystyle T\왼쪽(x\오른쪽)=\왼쪽(A^{\top }\오른쪽)^{-1}\Sigma _{X}^{-1/2}\왼쪽(\Sigma _{X}^{1/2})A^{{\top }\Sigma _{Y}A\Sigma _{1/2}\right)^{1/2}\Sigma _{X}^{X}-{1/2}}$

이 해결책의 증거는 갈리촌(2016년)에 나타난다.^[12]

분리형 힐버트 공간

$X{\displaystyle }$ ${\displaystyle X}$을(를) 분리 가능한 Hilbert 공간으로 두십시오$$. Let ${\displaystyle {\mathcal {P}}_{p}(X)}$ denote the collection of probability measures on ${\displaystyle X}$ that have finite ${\displaystyle p}$-th moment; let ${\displaystyle {\mathcal {P}}_{p}^{r}(X)}$ denote those elements ${\displaystyle \mu \in$$$가우스 정규인 ${\mathcal{P}_{p}(X)}:$ $g{\displaystyle }$ ${\displaystyle g}$이(가) X ${\displaystyle X}$ $및{\displaystyle }$ g ${\displaystyle (N}$)${\displaystyle }$= ${\displaystyle 0}$ ${\displaysty g($$N)=0}$에 대해 가우스 측정이 엄격히 긍정적인 경우, $\mu {\displaystyle (N}$)${\displaystyle }$= ${\displaystyle 0}$ ${\displaystypaystyptyptypty \mo$.

Let ${\displaystyle \mu \in {\mathcal {P}}_{p}^{r}(X)}$, ${\displaystyle \nu \in {\mathcal {P}}_{p}(X)}$, ${\displaystyle c(x,y)= x-y ^{p}/p}$ for ${\displaystyle p\in (1,\infty ),p^{-1}+q^{-1}=1}$$$.그렇다면 칸토로비치 문제에는 독특한 해법 ${\displaystyle \kappa }$이$($가) 있는데, 이 해법은 최적의 전송 맵에 의해 유도된다. 즉$$, 보렐 지도 $r{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle {}^{}}$ ${\displaystyle p^{}}$(${\displaystyle X}$, ${\displaystyle \mu }$; $){\displaysty r\in L^{p}(X,\mu ;X)}).$

$\\displaystyle \kappa =(\mathrm {id} _{X}\time r)_{*}(\mu )\in \감마(\mu ,\nu).}$

게다가, $만약{\displaystyle }$ $\$ {\$displaystyle \nu}$이(가) 지원을 제한했다면$$,

${\displaystyle r(x)=x- \vla \varphi (x) ^{q-2}\,\vla \varphi (x)}$

for ${\displaystyle \mu }$-almost all ${\displaystyle x\in X}$ for some locally Lipschitz, c-concave and maximal Kantorovich potential ${\displaystyle \varphi }$. (Here ${\displaystyle \nabla \varphi }$ denotes the Gateaux derivative of ${\displaystyle \varphi }$.)

등방성 정규화

원시 문제의 객관적 기능에 이방성 정규화 용어를 추가한 위의 이산형 문제의 변형을 생각해 보십시오.

${\displaystyle \min _{\gamma \geq 0}\sum \x\in \mathbf {X},y\in \mathbf {Y}, \c_{xy}+\epsilon \xy}\ln \gamma _{xy}}}}}}}$

s.t. ${\displaystyle \sum _{y\in \mathbf {Y} }\gamma _{xy}=\mu _{x},\forall x\in \mathbf {X} }$ and ${\displaystyle \sum _{x\in \mathbf {X} }\gamma _{xy}=\nu _{y},\forall y\in \mathbf {Y} }$

이중 정규화된 문제가

${\displaystyle \max _{\varphi ,\psi }\sum _{x\in \mathbf {X} }\varphi _{x}\mu _{x}+\sum _{y\in \mathbf {Y} }\psi _{y}v_{y}-\epsilon \sum _{x\in \mathbf {X} ,y\in \mathbf {Y} }\exp \left({\frac {\varphi _{x}+\psi _{y}-c_{xy}}{\epsilon }}\right)+\epsilon }$

where, compared with the unregularized version, the "hard" constraint in the former dual (${\displaystyle \textstyle \varphi _{x}+\psi _{y}-c_{xy}\geq 0}$) has been replaced by a "soft" penalization of that constraint (the sum of the ${\displays$$tyle \textstyle \epsilon \exp \exp \left$(\$varphi$_{$x}+\$required $_{y}-c_{xy}/\epsilon \right})$ 용어$$ ). 이중 문제의 최적성 조건은 다음과 같이 표현할 수 있다.

Eq. 5.1: ${\displaystyle \mathbf _{x}=\sum \mathbf {Y}}}\exp \frac {\varphi _{x}+\psi _{y}-c_}}{xy}}}}{xy}}}}}}\all x\in \in \mathbf {X}$

Eq. 5.2: ${\displaystyle \nu _{y}=\sum \mathbf {X}}}\exp \frac {\varphi _{x}+\psi _{y}-c_{xy}}}}}{xy}}}}{\in \ally\in \mathbf {Y}}}}}$

Denoting ${\displaystyle \textstyle A}$ as the ${\displaystyle \textstyle \left\vert \mathbf {X} \right\vert \times \left\vert \mathbf {Y} \right\vert }$ matrix of term ${\displaystyle \textstyle A_{xy}=\exp \left(-c_{xy}/\epsilon \right)}$, solving the dual 따라서 각 크기의 대각선$$$양수{\displaystyle {}_{}}$ ${\displaystyle {D\mathrm{}}_{}}$ 1 {\$displaystyle \$$textstyle$ ${$1} 및 D 2 {\$displaystyle$ \textstyle $D_{2$}}개$$ 크기 ${\displaystyle X\mathbf{}}$ $displaystyle \revert \x}$ $\right\verthermathb {Y}$ ${\displaystyle 및\mathbf{}}$ Y$$ $displaysty$}$\right\vert$ $\},$ 예를 $들어{\displaystyle {}_{}}$ D ${\displaystyle {1\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}{\mathrm{}}_{}}$ ${\displaystyle {1\mathbf{}}_{}}$Y = ${\displaystyle \mu }$ =$${\$displaystyle \textstyle D_{$$1$}$AD_{2}1_{\left\vert \mathbf {Y} \right\vert }=\mu }$ 및 $({\displaystyle {{D1}_{}}^{}}$ A ${\displaystyle {{D2\mathrm{}}_{}}^{}}$)${\displaystyle {\mathrm{}}^{}}$⊤ ${\displaystyle {}^{}{\mathrm{}}_{}}$ ${\displaystyle {X\mathbf{}}_{}}$= ${\displaystyle \nu }$ ${\$AD_{2}\right)^{\top}1_{\left\vert \mathbf{X}\right\vert}=\nu}. 그러한 매트릭스의 존재와 매트릭스는 Sinkhorn-Knopp algorithm,[16] 있는데 이는 단순히 반복적으로φ x{\displaystyle\textstyle \varphi_{)}에}등식 5.1를 해결할 것을 기대하고 구성되어 있어를 사용하여 계산할 수 있Sinkhorn의 정리 generalizes, ψ Y$$방정식 5.2를 푸는 데 필요한$$ ${\displaystyle \psi_{y$}. 따라서 싱혼-노프의 알고리즘은 이중 정규화 문제에 대한 좌표 강하 알고리즘이다.

적용들

Monge-Kantorovich 최적의 교통수단은 다양한 분야에서 광범위한 응용분야를 찾아냈다. 그 중에는 다음과 같은 것들이 있다.

• 이미지 등록 및 반전^[17]
• 반사체 설계^[18]
• 섀도그래피 및 양성자 방사선^[19] 촬영에서 정보 검색
• 지진단층 및 반사 지진학^[20]

참고 항목

위키미디어 커먼즈에는 교통 이론과 관련된 미디어가 있다.

• 와세르슈타인 미터법
• 운송함수
• 헝가리 알고리즘
• 운송계획
• 지구 이동 거리
• 몽에-암페르 방정식

참조

추가 읽기

• Brualdi, Richard A. (2006). Combinatorial matrix classes. Encyclopedia of Mathematics and Its Applications. 108. Cambridge: Cambridge University Press. ISBN 978-0-521-86565-4. Zbl 1106.05001.