最適輸送
確率分布同士の比較を行える
最適輸送でKL距離を置き換える研究もあるみたい. 面白そうだな 最適輸送問題自体は, 最小費用流問題の特殊なケース 供給側から需要側に物資を移動する際に一定のコストがかかるとする.
供給側の量をベクトル $ r, 需要側をベクトル$ cとする. 次元数はそれぞれ$ n, mとする
コストの行列を$ Mとし, これは事前に与えられる.
供給側から需要側にどう移動するかを決める行列を$ Pとする. $ P_{ij}は供給地点$ iから需要地点$ jに対してどのくらい運ぶかを表す.
この時, コストが最小化される$ Pを考える.
目的変数: $ \underset{P \in \R^{n \times m}}{\text{minimize}} \sum_{i}^{n}\sum_{j}^{m}{P_{ij}M_{ij}}
なお, $ P_{ij} \ge 0: 移動する物資の量は負にならない.
制約は以下の通り:
$ \Sigma_i P_{ij} = r_i: 供給量は用意された分と一致する.
$ \Sigma_j P_{ij} = c_j: 需要量は必要分と一致する.
ここで, 双対問題を考える. 線形計画法において, 先の目的変数の最小化を主問題として, その逆の最大化を行う場合を考える.
供給側が需要側に物資を移動する代わりに運送業者が仲介する. 供給側から物資を$ r_if_iで回収し, 需要側に$ c_jg_jで売却する. この時, 回収費用が$ f_i, 売り上げが$ g_jとなる.
双対問題は変数と制約の数だけ制約と変数が生じる.
供給量の制約に対応するのが, $ r_iに対応する$ f.
需要量は$ c_jに対応する$ gが存在
$ \underset{f \in \R^{n}, g \in \R^{m}}{\text{maximize}} $ \sum^{n}_{i}r_{i}f_{i} + \sum^{m}_{j}c_{j}g_{j}
変数$ Pに対応する制約が生じる. 運送業者のコストが供給側の配送計画で生じるコスト以下であるなら, 供給側は自分で物資を自動で移動させるより, 業者を用いて行うと考えられる.
$ f_{i} + g_{j} \le M_{ij}
関連