私と理論

数学の話を主に書きます

輸送問題と More-for-Less パラドックス

皆さん，パラドックスは好きですか？僕は大好きです．高校生の時の愛読書の一つがウイリアム・パウンドストーンの「パラドックス大全」だったくらいです．パラドックスが提示する思考の迷路をうろうろして途方に暮れるのはとっても楽しいですね．

最近，ネットワークフロー（輸送問題）における More-for-Less パラドックスを知ったので紹介します．

注意として，パラドックスは妥当そうな仮定から「論理的な矛盾」を導くもの（ラッセルのパラドックスなど）と「直感的でない結論」を導くもの（誕生日のパラドックス，バナッハ・タルスキのパラドックスなど）の二種類に大別することができますが，More-for-Less パラドックスは後者に分類されるものです．

輸送問題

輸送問題とは以下のような問題です．

  • n 件の工場と m 件の店舗からなる，ある商品の流通圏があるとする．
  • 各工場 i には a_i \geq 0 個の在庫がある.．
  • 各店舗 j では b_i \geq 0 個の需要がある．
  • 在庫の総和と需要の総和は等しいとする （すなわち \sum_{i \in [n] } a_i = \sum_{i \in [m]} b_i ）．
  • 工場 i から店舗 j に商品を一つ運ぶためには C_{ij} の輸送コストがかかる．
  • 各工場 i から各店舗 j への輸送量 x_{ij} を適切に決めて，各店舗の需要を満たしつつ輸送コストの総和を最小化せよ．

輸送問題は古くから研究されていながらも最新の機械学習界隈などでも盛んに取り組まれている，非常に重要な問題です．より詳しく知りたい方は以前僕が書いた 記事 などを参考にしてください．

More-for-Less パラドックス

図 1 左 のような輸送問題を考えます ( n = 3, m = 4)．辺の横に書いてある値が輸送コストです．

f:id:Theory_and_Me:20210724142859p:plain
図1 考える輸送問題（左）と最適解（右）

この問題を解いてやると，最適解は図 1 右（辺の横に書いてあるのが輸送量）のようになり，必要コストは 152 となります．

さてここで，先ほどの例においてグラフの形状やコストは変化させず， a_2 の値を +2， b_4 の値を +2 した問題（図 2 左）を考えてみます．

f:id:Theory_and_Me:20210724143635p:plain
図2 変更した輸送問題（左）と最適解（右）

この問題は先ほどの問題と比較して 輸送する必要のある量が真に増加している ので，必要なコストは大きくなることが予想されます．いったいどの程度大きくなるのでしょう？

この問題における最適化は図 2 右のようになります．そして，必要コストは 150 になります．なんと，必要コストは増えるどころか減っているのです！

輸送しなければいけない量は増えているのに必要な（最小）コストは減ってしまう，これが輸送問題における More-for-Less パラドックスです．

なぜこんなことが起こるのか？

1つ目の問題の最適解から2つ目の問題の最適解への変化を見てみると，

  • 1→4（コスト 1）の輸送量が +2
  • 2→6（コスト 1）の輸送量が +2
  • 1→6（コスト 3）の輸送量が -2

となっています．つまり，輸送しなければいけない量（ \boldsymbol{a}, \boldsymbol{b}）が増えることによって，コストが小さい辺（1→4, 2→6）のみ使ってのやりくりが可能になるために，コストの大きい辺（1→6）を使う必要がなくなり，結果として総コストが減少しているのです．

こうして解をちゃんと観察すると「それはそう」な感じもしますが，依然として非直感的でもあります．直感に頼った推測は危険なことがわかりますね！

参考文献

このパラドックスの初出は [1] のようです（文献が見つからず読めていません）．問題例は [2] を参考にしました．

  • [1] A. Charnes, D. Klingman. The "More-for-Less" Paradox in the Distribution Model. Cahiers du Centre d'Études de Recherche Opérationnelle 13, 11-22, 1971.
  • [2] R. A. Ahuja, T. L. Magnatti, J. B. Orlin. Network Flows: Theory, Algorithms, and Applications. Princeton-Hall, 1993