先日， 0x-seminar - [0x03] 最適輸送の情報科学における進展 というセミナーがあり，最適輸送について熱い2日があったらしいです．私はセミナーの存在を知らず，後からスライドを見ました．
1日目の資料は横井さんの資料で，そもそも最適輸送ってなんなの？とかNLPと絡めてこんな研究あるよ！っと色々とリンクが貼られていて勉強になりました．
2日目の佐藤さんの資料では，直感的な理解を重要視しつつ，最適輸送の問題をきっちりと定式化していて非常に勉強になりました．270ページぐらいあるのですが，すべて見る価値アリです．
その中でNetwork Simplexという最適輸送における主問題（輸送量のマトリックスを求める）を解く方法を最初に説明しています．Network Simplex法の解き方を誤解を恐れず簡単に言うと，適当な解から初めて違反的な辺がなくなるまで反復的に修正していく手法です．この修正により目的関数は広義単調減少（ゼロ改善もある）です．
なんとなくイメージはできたものの，具体的にどう解けていくのか確かめていくべく自分で問いてみました． 実例と解き方に関しては，Transportation Problem: Balancing | by Rodion Chachura | Medium の事例を参考にしました．この記事はpythonコード付きで分かりやすいです． この記事をざっと眺めた後，以下のスライドを1枚ずつめくっていくとあら不思議，なんとなくわかると思います．
