輸送理論（数学）

コレクションがあると仮定します${\displaystyle m}$鉄鉱石を採掘する鉱山、そして${\displaystyle n}$鉱山で生産される鉄鉱石を使用する工場。議論のために、これらの鉱山と工場が互いに素な2つの部分集合を形成すると仮定します。${\displaystyle M}$そして${\displaystyle F}$ユークリッド平面の$\displaystyle \mathbb {R} ^{2}}$また、コスト関数があると仮定します。${\displaystyle c:\mathbb {R} ^{2}\times \mathbb {R} ^{2}\to [0,\infty )}$、 となることによって${\displaystyle c(x,y)}$鉄を1回輸送するコストは${\displaystyle x}$に${\displaystyle y}$簡略化のため、輸送にかかる時間は無視する。また、各鉱山は1つの工場にのみ供給でき（出荷の分割なし）、各工場は稼働するために正確に1回の出荷を必要とする（工場は半分の能力または2倍の能力で稼働できない）と仮定する。上記の仮定に基づくと、輸送計画は全単射となる。${\displaystyle T:M\to F}$つまり、各鉱山は${\displaystyle m\in M}$正確に1つの対象工場に供給する${\displaystyle T(m)\in F}$そして各工場は正確に1つの鉱山から供給されます。私たちは最適な輸送計画、つまり計画を見つけたいのです。${\displaystyle T}$総費用

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

は、考えられるすべての輸送計画の中で最も少ないものです。${\displaystyle M}$に${\displaystyle F}$この輸送問題の動機となる特殊なケースは、割り当て問題の一例である。より具体的には、二部グラフにおける最小重みマッチングを見つけることと同等である。

これは、実数直線上、あるいは一般的には任意の距離空間上に無限に多くの鉱山や工場が分布している連続的なケースに一般化できる。このケースは通常「土の山の形を変える」というイメージで捉えられ、そのため「土砂運搬問題」と呼ばれている。

以下の簡単な例は、最適な輸送計画を決定する上でコスト関数がいかに重要であるかを示しています。${\displaystyle n}$棚（実線）に同じ幅の本が1つの連続したブロックとして並べられている。これを、1冊分の幅だけ右にずらした別の連続したブロックに再配置したい。最適な輸送計画として、2つの明らかな候補が考えられる。

1. すべて移動${\displaystyle n}$本を1冊分右にずらす（「小さな動きを何度も繰り返す」）。
2. 一番左の本を移動します${\displaystyle n}$本の幅分だけ右に移動させ、他のすべての本は固定したままにする（「一度に大きく動かす」）。

コスト関数がユークリッド距離に比例する場合（${\displaystyle c(x,y)=\alpha \|x-y\|}$一部の人にとって${\displaystyle \alpha >0}$) ならば、これら 2 つの候補はどちらも最適です。一方、ユークリッド距離の 2 乗に比例する厳密に凸なコスト関数 (${\displaystyle c(x,y)=\alpha \|x-y\|^{2}}$一部の人にとって${\displaystyle \alpha >0}$) の場合、「多数の小さな移動」オプションが唯一の最小化方法になります。

上記のコスト関数は、書籍が移動する水平距離のみを考慮しており、各書籍をピックアップして所定の位置に移動させる装置が移動する水平距離は考慮していないことに注意してください。後者を考慮すると、2つの輸送計画のうち、ユークリッド距離に関しては常に2番目の計画が最適であり、書籍が3冊以上ある場合は、1番目の輸送計画がユークリッド距離の2乗に関して最適となります。

以下の輸送問題の定式化は、FL ヒッチコックによるものです。^{[ 7 ]}

仮に${\displaystyle m}$情報源${\displaystyle x_{1},\ldots ,x_{m}}$商品の場合、${\displaystyle a(x_{i})}$供給単位${\displaystyle x_{i}}$そして${\displaystyle n}$シンク${\displaystyle y_{1},\ldots ,y_{n}}$商品に対する需要は${\displaystyle b(y_{j})}$で${\displaystyle y_{j}}$。 もし${\displaystyle c(x_{i},\ y_{j})}$出荷の単位コストは${\displaystyle x_{i}}$に${\displaystyle y_{j}}$供給からの需要を満たし、フローコストを最小化するフローを見つける。ロジスティクスにおけるこの課題は、 DR Fulkerson ^{[ 8 ]}によって取り上げられ、 LR Ford Jr. ^{[ 9 ]}と共著した書籍「Flows in Networks (1962 )」で取り上げられた。

チャリング・コープマンスは、輸送経済学と資源配分に関する理論の構築にも貢献した人物として知られている。

現代の、あるいはより専門的な文献で述べられている輸送問題は、リーマン幾何学と測度論の発展により、やや異なった様相を呈している。鉱山と工場の例は、単純ではあるが、抽象的なケースを考える際の有用な参考点となる。この例では、すべての鉱山と工場を操業し続ける必要がない可能性、鉱山が複数の工場に鉄を供給できること、そして工場が複数の鉱山から鉄を受け入れることができる可能性を考慮に入れる。

させて${\displaystyle X}$そして${\displaystyle Y}$は、任意の確率測度が${\displaystyle X}$（または${\displaystyle Y}$）はラドン測度（つまり、ラドン空間）である。${\displaystyle c:X\times Y\to [0,\infty )}$ボレル可測関数である。与えられた確率測度${\displaystyle \mu }$の上${\displaystyle X}$そして${\displaystyle \nu }$の上${\displaystyle Y}$モンジュによる最適輸送問題の定式化は、輸送マップを見つけることである。${\displaystyle T:X\to Y}$最小値を実現する

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

どこ${\displaystyle T_{*}(\mu )}$前進を意味する${\displaystyle \mu }$による${\displaystyle T}$地図${\displaystyle T}$この下限値を達成する（つまり、下限値ではなく最小値にする）輸送マップは、「最適輸送マップ」と呼ばれます。

モンジュによる最適輸送問題の定式化は、場合によっては不適切である可能性がある。${\displaystyle T}$満足${\displaystyle T_{*}(\mu )=\nu }$:これは、例えば次のような場合に起こります。${\displaystyle \mu }$ディラック測度ですが${\displaystyle \nu }$そうではない。

我々は、カントロビッチの最適輸送問題の定式化を採用することでこれを改善できる。それは確率測度を見つけることである。${\displaystyle \gamma }$の上${\displaystyle X\times 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 )}$は、すべての確率測度の集合を表します。${\displaystyle X\times Y}$周辺値付き${\displaystyle \mu }$の上${\displaystyle X}$そして${\displaystyle \nu }$の上${\displaystyle Y}$。

コスト関数が与えられた場合${\displaystyle c(x,y)}$双対変換を生み出す${\displaystyle \psi \mapsto \psi ^{c}}$定義される$${\displaystyle \psi ^{c}(y):=\inf _{x}(c(x,y)-\psi (x))}$$これはルジャンドル変換を一般化したもので、${\displaystyle c(x,y)=-xy}$看板をひっくり返すことで。

${\displaystyle \leq 1}$。

関数は${\displaystyle \psi }$c凸である場合${\displaystyle \psi =\varphi ^{c}}$一部の人にとって${\displaystyle \varphi }$。注意すべき点は、${\displaystyle \varphi ^{ccc}=\varphi ^{c}}$我々は常に次のように仮定することができる${\displaystyle \varphi }$c-凸である。関数のc-凸化${\displaystyle \psi }$は${\displaystyle \psi ^{cc}}$言い換えれば、それは最小のc凸関数である。${\displaystyle \psi '}$そのため${\displaystyle \psi '\geq \psi }$点ごとに。^{[ 10 ]：命題5.8}凸変換の場合と同様に、${\displaystyle \psi }$c凸であるのは、${\displaystyle \psi =\psi ^{cc}}$。

もし${\displaystyle \psi =\varphi ^{c}:X\to \mathbb {R} }$がc凸である場合、 c劣微分集合は${\displaystyle \psi }$で${\displaystyle x\in X}$は、${\displaystyle y\in Y}$そのため${\displaystyle \psi (x)=c(x,y)-\varphi (y)}$同様に${\displaystyle Y}$。

いつ${\displaystyle X=Y}$グラフ${\displaystyle (y,\psi ^{c}(y))}$は次のように構築できます。${\displaystyle \psi }$、そしてそれを逆さまにします。各ポイントで${\displaystyle (x,-\psi (x))}$グラフを構築する${\displaystyle y\mapsto c(x,y)}$頂点に達した${\displaystyle (x,-\psi (x))}$つまり、それは${\displaystyle y\mapsto c(x,y)-\psi (x)}$我々はこのようなグラフの集合全体を得る。それらの下端包絡線は、のグラフである。${\displaystyle \psi ^{c}}$。

同じ画像で、関数の意味を確認できます。${\displaystyle \varphi (y)}$c凸であること。グラフ全体が、移動しながら形状変化する「先端ツール」によって「触れられる」ことができる場合に限り、 c凸である。先端ツールが${\displaystyle x}$形状は${\displaystyle y\mapsto c(x,y)}$そして、高さまで持ち上げられる${\displaystyle -\psi (x)}$c凸化のグラフ${\displaystyle \varphi ^{cc}(y)}$は、傾斜したツールをできるだけ下げて、グラフに接触したままにすることで構築されます。${\displaystyle \varphi (y)}$上側。傾斜した工具によって掃引される下側の包絡線は、${\displaystyle \varphi ^{cc}(y)}$[ ^{10 ]：図5.2}

例えば、${\displaystyle X=Y=\mathbb {R} ^{n}}$は距離空間であり、${\displaystyle c(x,y)=\|x-y\|}$、 それから${\displaystyle \varphi :X\to \mathbb {R} }$c-凸であるのは、1-リプシッツであるときのみである。これは1-ワッサースタイン距離の定義で使用される。${\displaystyle c(x,y)=\|x-y\|^{2}}$、 それから${\displaystyle \varphi }$グラフが放物面の形状をした先端付き工具で上から触れることができる場合に限り、c-凸である。

かなり寛容な前提条件の下では、最適な輸送計画が存在する。

もし

• ${\displaystyle (X,\mu _{X}),(Y,\mu _{Y})}$ポーランド確率空間、
• ${\displaystyle c:X\times Y\to \mathbb {R} \cup \{\infty \}}$下半連続である、
• そして、いくつかの上半連続関数が存在する${\displaystyle a\in L^{1}(\mu _{X}),b\in L^{1}(\mu _{Y})}$タイプの${\displaystyle a:X\to \mathbb {R} \cup \{-\infty \},\;b:Y\to \mathbb {R} \cup \{-\infty \}}$そのため${\displaystyle c(x,y)\geq a(x)+b(y)}$、

すると、最適な輸送計画が存在する。つまり、存在する。${\displaystyle \gamma ^{*}\in \Gamma (\mu _{X},\mu _{Y})}$下限に達するように。^{[ 10 ]：定理4.1}

すべての輸送計画が無限である場合、下限値は無限になる可能性があることに注意してください。たとえば、${\displaystyle X=Y=\mathbb {R} ,c(x,y)=|x-y|,\;\mu _{X}}$はコーシー分布であり、${\displaystyle \mu _{Y}=\delta _{0}}$。

もし

• ${\displaystyle (X,\mu _{X}),(Y,\mu _{Y})}$ポーランド確率空間であり、
• ${\displaystyle c:X\times Y\to \mathbb {R} }$下半連続であり、
• 上半連続関数が存在する${\displaystyle a\in L^{1}(\mu _{X}),b\in L^{1}(\mu _{Y})}$タイプの${\displaystyle a:X\to \mathbb {R} ,\;b:Y\to \mathbb {R} }$そのため${\displaystyle c(x,y)\geq a(x)+b(y)}$、
• 有限コストの輸送計画が存在する。
• 任意のc凸関数に対して${\displaystyle \psi :X\to \mathbb {R} \cup \{\infty \}}$、 のために${\displaystyle \mu _{X}}$ほぼすべて${\displaystyle x\in X}$、${\displaystyle \psi }$は、​${\displaystyle x}$

すると、最適な輸送マップが存在する。^{[ 10 ]：定理5.30}

最適な輸送計画の制約は依然として最適である。つまり、${\displaystyle \gamma \in \Gamma (\mu ,\nu )}$が最適であり、${\displaystyle 0<\gamma '<\gamma }$正規化された輸送計画を定義する${\displaystyle {\bar {\gamma }}':=\gamma '/\gamma '(X\times Y)}$、 それから${\displaystyle {\bar {\gamma }}'}$は、その限界値間の最適な輸送計画である。^{[ 10 ]：定理4.6}もし${\displaystyle {\bar {\gamma }}'}$最適でない場合、それを改善する方法が存在し、それが元の改善につながる。${\displaystyle \gamma }$。

カントロヴィッチの双対性は次のように述べている。^{[ 10 ] :定理5.10}

もし${\displaystyle (X,\mu _{X}),(Y,\mu _{Y})}$ポーランド確率空間、${\displaystyle c:X\times Y\to \mathbb {R} \cup \{\infty \}}$は下半連続であり、上半連続関数も存在する。${\displaystyle a\in L^{1}(\mu _{X}),b\in L^{1}(\mu _{Y})}$タイプの${\displaystyle a:X\to \mathbb {R} ,\;b:Y\to \mathbb {R} }$そのため${\displaystyle c(x,y)\geq a(x)+b(y)}$、 それから$${\displaystyle \inf _{\gamma \in \Gamma (\mu ,\nu )}\left(\int _{X\times Y}c(x,y)\,\mathrm {d} \gamma (x,y)\right)=\sup _{\varphi {\text{ is }}c{\text{-convex}}}\left(\int _{X}\varphi (x)\,\mathrm {d} \mu (x)+\int _{Y}\varphi ^{c}(y)\,\mathrm {d} \nu (y)\right)}$$さらに、${\displaystyle c}$実数値のみを取り、有限コストの輸送計画が存在し、いくつかの関数が存在する${\displaystyle a'\in L^{1}(\mu _{X}),b'\in L^{1}(\mu _{Y})}$そのため${\displaystyle c(x,y)\leq a'(x)+b'(y)}$、 それから$${\displaystyle \min _{\gamma \in \Gamma (\mu ,\nu )}\left(\int _{X\times Y}c(x,y)\,\mathrm {d} \gamma (x,y)\right)=\max _{\varphi {\text{ is }}c{\text{-convex}}}\left(\int _{X}\varphi (x)\,\mathrm {d} \mu (x)+\int _{Y}\varphi ^{c}(y)\,\mathrm {d} \nu (y)\right)}$$

2番目のケースを考えてみましょう。このケースでは、単に最適解に近づくのではなく、実際に最適な計画に到達できます。この場合、最適な輸送計画は${\displaystyle \gamma \in \Gamma (\mu ,\nu )}$最適な価格ペアの形式を制約する${\displaystyle (\varphi ,\psi )}$そしてその逆もまた然り。

このような最適な価格ペアが与えられた場合${\displaystyle (\varphi ,\psi )}$[ ^{10 ] ：注釈5.13}

• 任意の輸送計画が与えられた場合${\displaystyle \gamma \in \Gamma (\mu ,\nu )}$すべて${\displaystyle (x,y)\in \operatorname {supp} (\gamma )}$完全な等式を満たす${\displaystyle c(x,y)=\varphi (x)+\psi (y)}$、 それから${\displaystyle \gamma }$最適な計画です。
• 最適な輸送計画が与えられた場合${\displaystyle \gamma \in \Gamma (\mu ,\nu )}$、 どれでも${\displaystyle (x,y)\in \operatorname {supp} (\gamma )}$厳密な等式を満たさなければならない${\displaystyle c(x,y)=\varphi (x)+\psi (y)}$。

より簡潔に言えば、輸送計画が最適であるのは、 c-劣微分ペアの集合上でサポートされている場合に限られる。${\displaystyle (\varphi ,\psi )}$。

最適な輸送は、次の意味で安定している。 ^{[ 10 ]：定理5.20}

と仮定する${\displaystyle (X,\mu ),(Y,\nu )}$ポーランド確率空間、${\displaystyle c:X\times Y\to \mathbb {R} }$連続的で、${\displaystyle \inf c}$有限である。連続関数の列が与えられた場合${\displaystyle c:X\times Y\to \mathbb {R} }$均一に収束して${\displaystyle c}$以上${\displaystyle X\times Y}$シーケンス${\displaystyle \mu _{k}\to \mu }$弱く、シーケンス${\displaystyle \nu _{k}\to \nu }$弱く、そして一連の最適な輸送計画${\displaystyle \gamma _{k}\in \Gamma (\mu _{k},\nu _{k})}$輸送コストが${\displaystyle \int c_{k}d\pi _{k}}$満足する${\displaystyle \int c_{k}d\pi _{k}<+\infty ,\;\forall k}$そして${\displaystyle \liminf _{k}\int c_{k}d\pi _{k}<+\infty }$、 それから${\displaystyle \gamma _{k}}$弱収束して${\displaystyle \gamma }$、 そして${\displaystyle \gamma }$最適な輸送計画は${\displaystyle \mu }$に${\displaystyle \nu }$。

同様に、最適輸送マップも安定している。^{[ 10 ]： Cor. 5.23}

と仮定する${\displaystyle (X,\mu ),(Y,\nu )}$ポーランド確率空間、${\displaystyle X}$局所的にコンパクトで、${\displaystyle c:X\times Y\to \mathbb {R} }$は下半連続であり、${\displaystyle \inf c}$有限である。下半連続関数の列が与えられた場合${\displaystyle c:X\times Y\to \mathbb {R} }$均一に収束して${\displaystyle c}$以上${\displaystyle X\times Y}$シーケンス${\displaystyle \nu _{k}\to \nu }$弱々しく、

最適輸送問題には経済学的解釈がある。^{[ 11 ]}セドリック・ヴィラニはルイス・カファレッリによる以下の解釈を述べている。^{[ 12 ]}

炭鉱から石炭を出荷したいとします。${\displaystyle \mu }$工場へ、${\displaystyle \nu }$輸送のコスト関数は${\displaystyle c}$すると、運送業者がやってきて、あなたのために輸送を申し出ます。あなたは彼に料金を支払います。${\displaystyle f(x)}$石炭1個あたり、石炭の積み込み${\displaystyle x}$そして彼に支払う${\displaystyle g(y)}$石炭1個あたり、石炭の荷揚げ${\displaystyle y}$取引を受け入れるには、価格表が以下の条件を満たしている必要があります。${\displaystyle f(x)+g(y)\leq c(x,y)}$カントロヴィッチの二元性によれば、荷送人は、あなたが自分で発送する場合とほぼ同じくらいの料金を支払わせるような料金体系を作成できる。

解釈において、双対変換は負荷コスト関数を変換する。${\displaystyle \varphi (x)}$（荷送人にとって）最適な荷降ろしコスト関数に${\displaystyle \psi (y)=\varphi ^{c}(y)}$荷降ろしコスト関数が${\displaystyle \psi (y)}$もしどこかの時点でもっと高かったら、何らかのルートがあるだろう${\displaystyle x\to y}$で${\displaystyle c(x,y)<\varphi (x)+\psi (y)}$つまり、自分で輸送したいルートがあるということです。しかし、荷降ろしコスト関数がどの時点でも低ければ、荷送人はその時点で価格を上げることでより多くの利益を得ることができたでしょう。したがって、荷送人は常に選択すべきです。${\displaystyle \psi =\varphi ^{c}}$同じ議論が再び適用され、荷送人は常に選択すべきであると述べられています。${\displaystyle \varphi =\psi ^{c}}$したがって、双対性公式の下限半分が得られます。$${\displaystyle \inf _{\gamma \in \Gamma (\mu ,\nu )}\left(\int _{X\times Y}c(x,y)\,\mathrm {d} \gamma (x,y)\right)\geq \sup _{\varphi {\text{ is }}c{\text{-convex}}}\left(\int _{X}\varphi (x)\,\mathrm {d} \mu (x)+\int _{Y}\varphi ^{c}(y)\,\mathrm {d} \nu (y)\right),}$$カントロヴィッチの双対性によれば、これは実際には等式であり、つまり、荷送人はあなたが自分自身に支払うであろう金額と同じ額をあなたに支払わせることができるが、荷送人がその上限に正確に到達することはないかもしれない（そのため、最小値と最大値ではなく、下限と最大値が使用される）。

荷送人は実際には同じコスト関数を支払わなければならず、また、を使用して最大収益に正確に到達できると仮定します。${\displaystyle (\varphi ,\psi )}$彼らの価格表のように。すると、荷送人は最適なプランを使用しなければならず、その時点で荷送人は利益を出さずに損益分岐点に達する。逆に、荷送人が正確に損益分岐点に達することができる配送プランはすべて最適である。

最適な輸送マトリックス

連続最適輸送

のために${\displaystyle 1\leq p<\infty }$、 させて${\displaystyle {\mathcal {P}}_{p}(\mathbb {R} )}$確率測度の集合を表す${\displaystyle \mathbb {R} }$有限の${\displaystyle p}$番目の瞬間。${\displaystyle \mu ,\nu \in {\mathcal {P}}_{p}(\mathbb {R} )}$そして${\displaystyle c(x,y)=h(x-y)}$、 どこ${\displaystyle h:\mathbb {R} \to [0,\infty )}$は凸関数である。

1. もし${\displaystyle \mu }$原子を持たない、つまり累積分布関数が${\displaystyle F_{\mu }:\mathbb {R} \to [0,1]}$の${\displaystyle \mu }$は連続関数である。${\displaystyle F_{\nu }^{-1}\circ F_{\mu }:\mathbb {R} \to \mathbb {R} }$は最適な輸送マップです。これは、以下の条件を満たす場合、唯一の最適な輸送マップです。${\displaystyle h}$厳密に凸である。
2. 我々は持っています

${\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) に掲載されている。^{[ 13 ]}

余白が${\displaystyle \mu }$そして${\displaystyle \nu }$離散的である、${\displaystyle \mu _{x}}$ そして${\displaystyle \nu _{y}}$それぞれに割り当てられた確率質量${\displaystyle x\in \mathbf {X} }$そして${\displaystyle y\in \mathbf {Y} }$、そして${\displaystyle \gamma _{xy}}$確率は${\displaystyle xy}$割り当て。主問題であるカントロビッチ問題の目的関数は次のようになる。

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

そして制約${\displaystyle \gamma \in \Gamma (\mu ,\nu )}$表現する

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

そして

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

これを線形計画問題に入力するには、行列をベクトル化する必要があります。${\displaystyle \gamma _{xy}}$列または行を積み重ねることで、${\displaystyle \operatorname {vec} }$この操作。列優先順序では、上記の制約は次のように書き換えられます。

${\displaystyle \left(1_{1\times |\mathbf {Y} |}\otimes I_{|\mathbf {X} |}\right)\operatorname {vec} (\gamma )=\mu }$そして${\displaystyle \left(I_{|\mathbf {Y} \|}\otimes 1_{1\times |\mathbf {X} |}\right)\operatorname {vec} (\gamma )=\nu }$

どこ${\displaystyle \otimes }$はクロネッカー積です。${\displaystyle 1_{n\times m}}$サイズが の行列です${\displaystyle n\times m}$すべてのエントリが1で、${\displaystyle I_{n}}$はサイズの単位行列です${\displaystyle n}$結果として、設定${\displaystyle z=\operatorname {vec} (\gamma )}$問題の線形計画法による定式化は次のとおりである。

${\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}}}$

これは大規模線形計画ソルバーに容易に入力できます（Galichon (2016) ^{[ 11 ]}の第 3.4 章を参照）。

半離散的な場合、${\displaystyle X=Y=\mathbb {R} ^{d}}$そして${\displaystyle \mu }$連続分布${\displaystyle \mathbb {R} ^{d}}$、 その間${\displaystyle \nu =\sum _{j=1}^{J}\nu _{j}\delta _{y_{i}}}$確率質量を割り当てる離散分布${\displaystyle \nu _{j}}$サイトへ${\displaystyle y_{j}\in \mathbb {R} ^{d}}$この場合、^{[ 14 ]}に示すように、主問題と双対問題はそれぞれ以下のように帰着することがわかります。

${\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 )}$つまり${\displaystyle \int _{X}d\gamma _{j}(x)=\nu _{j}}$そして${\displaystyle \sum _{j}d\gamma _{j}(x)=d\mu (x)}$、 そして：

${\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\}}$

双対の場合、次のように書き換えることができます。

${\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\}}$

これは、勾配降下法などの標準的な手法で解くことができる有限次元凸最適化問題です。

の場合${\displaystyle c(x,y)=|x-y|^{2}/2}$集合は${\displaystyle x\in \mathbf {X} }$特定の場所に割り当てられた${\displaystyle j}$は凸多面体である。結果として得られる構成はパワーダイアグラムと呼ばれる。^{[ 15 ]}

特定のケースを想定する${\displaystyle \mu ={\mathcal {N}}(0,\Sigma _{X})}$、${\displaystyle \nu ={\mathcal {N}}(0,\Sigma _{Y})}$、 そして${\displaystyle c(x,y)=|y-Ax|^{2}/2}$どこ${\displaystyle A}$は可逆である。すると、

${\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}$

${\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}$

${\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}$

この解法の証明はガリション（2016）に掲載されている。^{[ 11 ]}

させて${\displaystyle X}$を可分ヒルベルト空間とする。${\displaystyle {\mathcal {P}}_{p}(X)}$確率測度の集合を表す${\displaystyle X}$有限の${\displaystyle p}$の瞬間;${\displaystyle {\mathcal {P}}_{p}^{r}(X)}$これらの要素を表す${\displaystyle \mu \in {\mathcal {P}}_{p}(X)}$ガウス正規分布に従う場合：${\displaystyle g}$は、​​${\displaystyle X}$そして${\displaystyle g(N)=0}$、 それから${\displaystyle \mu (N)=0}$また。

させて${\displaystyle \mu \in {\mathcal {P}}_{p}^{r}(X)}$、${\displaystyle \nu \in {\mathcal {P}}_{p}(X)}$、${\displaystyle c(x,y)=|x-y|^{p}/p}$のために${\displaystyle p\in (1,\infty ),p^{-1}+q^{-1}=1}$すると、カントロビッチ問題は一意解を持つ。${\displaystyle \kappa }$そして、この解は最適輸送写像によって誘導される。すなわち、ボレル写像が存在する。${\displaystyle r\in L^{p}(X,\mu ;X)}$そのため

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

さらに、もし${\displaystyle \nu }$境界のあるサポートを持つ場合、

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

のために${\displaystyle \mu }$ほぼすべて${\displaystyle x\in X}$地元のリプシッツでは、${\displaystyle c}$-凹型で最大カントロビッチポテンシャル${\displaystyle \varphi }$。 （ここ${\displaystyle \nabla \varphi }$は、​${\displaystyle \varphi }$）

モンジュ・カントロビッチ問題の解法として、シグルド・アンゲネント、スティーブン・ハッカー、アレン・タンネンバウムによって勾配降下法が提案された。^{[ 16 ]}