2010年(平成22年)東京大学後期-総合科目ＩＩ[2]B - [別館]球面倶楽部零八式markIISR

[2] 数学的な方法は，社会における最適な行動の選択においても重要な役割を果たす．この問題では，土地の競売，商品の輸送という，ふたつの商業活動における問題を考える．

B
平面上の $n$ 個の地点 $x_i（i=1,2,\ldots,n）$ に商品が保管されている． $i, j=1, 2,\ldots,n$ について，地点 $x_i$ と $x_j$ との間の距離を $d_{i,j}$ と書くことにする．ここで，各 $i,j$ に対して $d_{i,j}$ は負でない実数であり， $d_{i,j}=d_{j,i}$ であるとする．また，任意の互いに異なる $i,j,k$ に対して，
$d_{i,k}\lt d_{i,j}+d_{j,k}$
が成立しているものとする．同じ点どうしの距離は $0$ であるから， $d_{i,i}=0（i=1,2,\ldots,n）$ である．

それぞれの地点に保管されている商品の量を $p_1,p_2,\ldots,p_n$ ，実際に必要となる商品の量を， $q_1,q_2,\ldots,q_n$ とする．ただし， $p_i\geqq 0（i=1,2,\ldots,n）$ ， $p_1+p_2+\cdots+p_n=1$ ， $q_i\geqq 0（i=1,2,\ldots,n）$ ， $q_1+q_2+\cdots+q_n=1$ である．すべての地点で必要量を確保できるように商品を輸送するプランを立てる．輸送プランは，次のように書ける．地点 $x_i$ から地点 $x_j$ に輸送する商品の量を $w_{i,j}$ と書くことにして，それぞれの $j$ について
$q_j=p_j+\displaystyle\sum_{i=1}^n w_{i,j}$ ……(1)
が成立するようにする．ただし， $x_i$ から $x_j$ に商品が運ばれるときには $w_{i,j}\gt 0$ ， $x_j$ から $x_i$ に商品が運ばれるときには $w_{i,j}\lt 0$ となるように符号を選び，逆方向に運ばれる商品の量は符号が逆になる，つまり
$w_{i,j}=-w_{j,i}$ と決めることにする．また， $x_i$ と $x_j$ との間で商品を輸送しないときは， $w_{i,j}=0$ とする．特に， $w_{i,i}=0（i=1,2,\ldots,n）$ とする．

$w_{i,j}（i,j=1,2,\ldots,n）$ が条件(1)をみたすとき，輸送にかかる費用は，輸送量と輸送距離の積の総和
$C=\dfrac{1}{2}\displaystyle\sum_{i=1}^n\sum_{j=1}^n |w_{i,j}|d_{i,j}$
であると考えられる．費用Cができるだけ小さくなるような輸送プランを考えたい．

(B-1) $w_{i,j}（i,j=1,2,\ldots,n）$ が条件(1)をみたすとする．それぞれの $i$ について，
(i) $w_{i,j}\leqq 0（j=1,2,\ldots,n）$
あるいは
(ii) $w_{i,j}\geqq 0（j=1,2,\ldots,n）$
のどちらかが成立しなければ，この輸送プランよりも良い輸送プランが存在することを示せ．つまり， $C$ がより小さくなるような $w_{i,j}（i,j=1,2,\ldots,n）$ が存在することを示せ．

(B-2) 図2のように，平面上の6点 $x_i（i=1,2,\ldots,6）$ が，正六角形の頂点になるように配置されている．各点で保管されている商品の量は
$p_1=p_2=\cdots=p_6=\dfrac{1}{6}$
必要となる商品の量は
$q_1=q_2=\dfrac{1}{18}$ ， $q_3=q_4=\dfrac{2}{9}$ ， $q_5=\dfrac{5}{18}$ ， $q_6=\dfrac{1}{6}$
とする．このとき， $C$ を最小にするような輸送プラン
$w_{i,j}（i,j=1,2,\ldots,6）$ を求めよ．ただし，正六角形の1辺の長さはそれぞれ1，各点の間の距離は平面上の距離であるとする．

図2(略)

2021.02.15記

[解答]

(B-1) (i)(ii) の両方が成立しないと仮定する．番号をつけ換えることにより， $w_{1,2}\gt 0$ ， $w_{1,3}\lt 0$ であるとしても一般性を失わない．このとき， $w_{3,1}\gt 0$ であるから，商品は3から1に輸送され，1から2に輸送されている．

そこで， $0\lt \varepsilon\lt \min\{w_{1,2},w_{3,1}\}$ なる $\varepsilon$ だけ，商品を3から2に直接輸送することを考えると，その分の輸送コストは $\varepsilon (d_{3,1}+d_{1,2})$ から $\varepsilon d_{3,2}$ に変化するが， $d_{3,2}\lt d_{3,1}+d_{1,2}$ により輸送コストは減少しているので，題意は証明された．

(B-2) 輸送は経由せずに直接運ぶ方が良いことに注意する．

$x_1,x_2$ は $\dfrac{1}{9}$ 運び出し， $x_3,x_4$ は $\dfrac{1}{18}$ 運び込み， $x_5$ は $\dfrac{1}{9}$ 運び込み， $x_6$ は何もしなくて良い．

$x_1$ から $x_3$ ， $x_4$ ， $x_5$ への単位あたりの輸送コストは $\sqrt{3}$ ， $2$ ， $\sqrt{3}$ ，
$x_2$ から $x_3$ ， $x_4$ ， $x_5$ への単位あたりの輸送コストは $1$ ， $\sqrt{3}$ ， $2$ ，
であるから， $x_1$ からはなるべく $x_5$ に， $x_2$ からはなるべく $x_3$ ， $x_4$ に輸送すれば良い．
よって， $x_1$ の $\dfrac{1}{9}$ を $x_5$ に， $x_2$ の $\dfrac{1}{9}$ を $x_3$ ， $x_4$ に $\dfrac{1}{18}$ ずつ輸送すればコストが最小になる．

よって， $w_{1,5}=\dfrac{1}{9}$ ， $w_{5,1}=-\dfrac{1}{9}$ ， $w_{2,3}=w_{2,4}=\dfrac{1}{18}$ ， $w_{3,2}=w_{4,2}=-\dfrac{1}{18}$ であり，残りの $w_{i,j}$ は全て0である．