輸送問題

輸送問題とは

輸送問題とは、複数の供給地と需要地があり、それぞれの供給量と需要量、供給地から需要地までの１個あたりの輸送費用が与えられているときに、総輸送費用を最小にするには、どの供給地からどの需要地へ、いくつ輸送すればよいかを求める問題です。線形計画法の特殊な問題です。

　　ｍ　　　　供給地の数
　　ｎ　　　　需要地の数
　　ａ(ｉ)　　供給地ｉの供給量
　　ｂ(ｊ)　　需要地ｊの需要量
　　ｃ(ｉ,ｊ) 供給地ｉから需要地ｊに１個輸送する費用
　　ｘ(ｉ,ｊ) 供給地ｉから需要地ｊに輸送する量
とすると、次のように定式化されます。
　　目的関数
　　　ｃ(1,1)ｘ(1,1) + ｃ(1,2)ｘ(1,2) +・・・
　　　　　　　　　　 + ｃ(i,j)ｘ(i,j) +・・・+ ｃ(m,n)ｘ(m,n) →最小
　　制約条件
　　（供給量条件）
　　　ｘ(1,1) + ｘ(1,2) +・・・+ ｘ(1,n) ＝ ａ(1)
　　　ｘ(2,1) + ｘ(2,2) +・・・+ ｘ(2,n) ＝ ａ(2)
　　　　　：　　　　　　　　　　　　　　　　　：
　　　ｘ(m,1) + ｘ(m,2) +・・・+ ｘ(m,n) ＝ ａ(m)
　　（需要量条件）
　　　ｘ(1,1) + ｘ(2,1) +・・・+ ｘ(m,1) ＝ ｂ(1)
　　　ｘ(1,2) + ｘ(2,2) +・・・+ ｘ(m,2) ＝ ｂ(2)
　　　　　：　　　　　　　　　　　　　　　　　：
　　　ｘ(1,n) + ｘ(2,n) +・・・+ ｘ(m,n) ＝ ｂ(n)

これは、線形計画法を用いて解くことができますが、制約条件での係数がすべて１であるという特徴があります。その特徴に着眼して、計算を容易にする方法が輸送問題なのです。

輸送問題の解法

輸送問題を解く手順は、次のようになります。

初期可能解の設定

費用のことは考えずに、制約条件を満足する ｘ(i,j) を設定します。その方法には、
　　北西隅の方法
　　ハウザッカー法
などがあります。

最適解への改善

割り付けた ｘ(i,j) と ｃ(i,j) を吟味して、総費用を下げるように ｘ(i,j) を変更します。これ以上総費用を下げることができなくなったときが最適解になります。その判定と改善をする方法には、
　　飛び石法
　　ＵＶ法（ポテンシャル法）
などがあります。

数値例と解法の解説

数値例を用いて、北西隅の方法とＵＶ法（ポテンシャル法）について解説します。

数値例

供給地の個数=3，　需要地の個数=4

北西隅の方法

北西（左上）から右へ下へと順に輸送量を決めていく方法です。

• 供給地１の供給量１８と需要地１の需要量１２を比較すると、需要量のほうが小さいので、需要量１２を割り付けます。→ ｘ(1,1)＝１２
  その結果、需要地１での需要残は０、供給地１での供給残は１８－１２＝６になります。
• 供給地１に供給残があるので、需要地２の需要量２０と比較します。こんどは供給量のほうが小さいので、供給量６を割り付けます。→ｘ(1,2)＝６
  その結果、供給地１での供給残は０、需要地２での需要残は２０－６＝１４になります。
• 供給地１の供給残が０になったので、供給地２について考えます。供給地２の供給量２２よりも需要地２の需要残１４のほうが小さいので、ｘ(2,2)＝１４とします。
• このように、繰り返すことにより、初期可能解が得られます。

このときの総費用は、
　　　ｃ(1,1)ｘ(1,1) + ｃ(1,2)ｘ(1,2) + ｃ(2,2)ｘ(2,2)
　　+ ｃ(2,3)ｘ(2,3) + ｃ(3,3)ｘ(3,3) + ｃ(3,4)ｘ(3,4)
　　＝７×１２ ＋ ３×６ ＋ ３×１４ ＋ ６×８ ＋ ８×８ ＋ ６×１８
　　＝３６４
　　 となります。

解の改善

この解は改善の余地があります。例えば
　　　　　　　　　需要地２　　需要地３
　　　供給地１　　c(1,2)=3　　c(1,3)=2
　　　　　　　　　x(1,2)=6 　 x(1,3)=0
　　　供給地２　　c(2,2)=3　　c(2,3)=6
　　　　　　　　　x(2,2)=14 　x(2,3)=8
になっています。ここで、
　　（１,３）に１個割り付けると、　２円増加
　　（１,２）が１個減り、　　　　　３円減少
　　（２,３）が１個減り、　　　　　６円減少
　　（２,２）が１個増える　　　　　３円増加
ので、総費用は、２－３－６＋３＝－４円だけ変化します。
　そして、（１,３）に割り付けることができる最大値は、ｘ(1,2)とｘ(2,3)の小さいほうになります。

このようなループと最大値を、目視ではなく、数学的に求めることが必要になります。

ＵＶ法（ポテンシャル法）

新しい概念、
　　ｕ(ｉ) ：供給地ｉの供給量 ａ(ｉ) を１個増大したときの費用減
　　ｖ(ｊ) ：需要地ｊの供給量 ｂ(ｉ) を１個増大したときの費用減
を導入します。 　すると、目的関数や制約条件を次のように書き換えることができます。

　目的関数
　　　ａ(1)ｕ(1) + ａ(2)ｕ(2) +・・・+ ａ(m)ｕ(m)
　　+ ｂ(1)ｖ(1) + ｂ(2)ｖ(2) +・・・+ ｂ(m)ｖ(m) →最大 　制約条件
　　　ｕ(i) + ｖ(j) ＝ ｃ(i,j)

これを理解するには、線形計画法の双対問題の知識が必要ですが、ここでは省略して、数値例で説明します。

ｕ(i) と ｖ(j) の設定

既にが割りつけられる（ｘ(i,j) ＞０）要素について、ｕ(i) + ｖ(j) ＝ ｃ(i,j) が成立するようにｕ(i) + ｖ(j) を設定します。その手順を示します。

1. まず、ｕ(1) ＝０とします。
2. 行１のなかで、輸送している（ｘ(i,j) ＞０）要素を探します。
   ｃ(1,1)＝７とｃ(1,2)＝３がそれにあたります。
3. ｕ(i) + ｖ(j) ＝ ｃ(i,j) が成立するように ｖ(j) を設定します。
   ｖ(1)＝ｃ(1,1)－ｕ(1)＝７－０＝７、ｖ(2)＝ｃ(1,2)－ｕ(1)＝３－０＝３になります。
4. ｖ(j) が設定された列について、既に ｕ(i) が設定されている行の要素以外で費用が最小の要素を探します。
   列１については、対象となる要素はありません。
   列２については、ｃ(2,2)＝３ がそれにあたります。
   
5. ｕ(i) + ｖ(j) ＝ ｃ(i,j) が成立するように ｕ(i) を設定します。
   ｕ(2) ＝ ｃ(2,2) － ｖ(2) ＝３－３＝０
6. ｕ(i) が更新された行について、「２」以降を行います。
   ｕ(2) が設定されたので、ｃ(2,3)＝６ が対象になり、ｖ(3)＝ ｃ(2,3) － ｕ(2) ＝６－０＝６になります。
7. 「４」と同様に、ｃ(3,3) ＝８ が対象になり、ｕ(3) ＝ ｃ(3,3) － ｖ(3) ＝８－６＝２ になります。
8. 行３に関しては、ｃ(3,4)＝６ が対象になり、ｖ(4)＝ ｃ(3,4) － ｕ(3) ＝６－２＝４になります。
9. これで、すべてのｕとｖが設定されました。
   この結果は次のようになります。

　　ｕ(1) ＝０，　ｕ(2) ＝０，　ｕ(3) ＝２
　　ｕ(1) ＝７，　ｕ(2) ＝３，　ｕ(3) ＝６，　ｕ(4) ＝４

未割付要素での ｃ(i,j) － ｕ(i) － ｖ(j) の計算

未割付要素（ｘ(i,j) ＝ ０ の要素）について、ｃ(i,j) － ｕ(i) － ｖ(j) を計算します。
要素 (1,3) については、ｃ(1,3) － ｕ(1) － ｖ(3) ＝２－０－６＝－４になります。
各要素については、次のように計算できます。

• ｃ(1,3) － ｕ(1) － ｖ(3) ＝　２－０－６＝－４
• ｃ(1,4) － ｕ(1) － ｖ(4) ＝１０－０－４＝　６
• ｃ(2,1) － ｕ(2) － ｖ(1) ＝　９－０－７＝　２
• ｃ(2,4) － ｕ(2) － ｖ(4) ＝　８－０－４＝　４
• ｃ(3,1) － ｕ(3) － ｖ(1) ＝　８－２－７＝－１
• ｃ(3,2) － ｕ(3) － ｖ(2) ＝　７－２－３＝　２

以上から次の表が得られます。
　　　　　　　　　　　　　需要地１　需要地２　需要地３　需要地４
　　　　　　↓ｕ(i)ｖ(j)→　　７　　　　３　　　　６　　　　４
　　供給地１　　　０　　　　　　　　　　　　　　－４　　　　６
　　供給地２　　　０　　　　　２　　　　　　　　　　　　　　４
　　供給地３　　　２　　　　－１　　　　２

解の吟味と改善

ここで、
　　ｐ(i,j) ＝ｃ(i,j) － ｕ(i) － ｖ(j)
　　　　　　＝　ｃ(i,j)
　　　　　　　－ｃ(s,j)　　[＝ - ｕ(s) - ｖ(j)]
　　　　　　　－ｃ(i,t)　　[＝ - ｕ(i) - ｖ(t)]
　　　　　　　＋ｃ(s,t)　　[＝ + ｕ(s) + ｖ(t)]
と変形できます。
　そして、ｘ(i,j) を１個増加することは、供給量と需要量を変えないという条件から、ｘ(s,j) と ｘ(i,t) を１個減らして、ｘ(s,t) を１個増やすことになります。そのときの総費用の変化は、ｃ(i,j) - ｃ(s,j) - ｃ(i,t) + ｃ(s,t) です。すなわち、
　　ｐ(i,j) は、ｘ(i,j) の値を１個増大したときの総費用の変化
を示しています。

それで、
　　すべての要素で ｐ(i,j) ≧０ になれば、最適解である。
といえます。

ｐ(i,j) ＜０ の要素があれば、ｘ(i,j) を増加させれば総費用を下げることができます。
　全要素のうち、ｐ(i,j) が最小（負で絶対値が最大）の要素を (ipvt, jpvt) としましょう。数値例では ｐ(1,2)＝－４がそれにあたります。
　ｘ(ipvt,jpvt) の最大値は、行ipvtの要素 ｘ(ipvt, j) （ｘ(ipvt,jpvt) を除く）のなかで正の最小値 ｘ(ipvt, jmin) と、列jpvtの要素 ｘ(i, jpvt) （ｘ(ipvt,jpvt) を除く）のなかで正の最小値 ｘ(imin, jpvt) の小さいほうになります。
　数値例では、行１のなかでの最小値は ｘ(1,1)＝１２、列３のなかでの最小値は ｘ(2,3)＝８ですから、ｘ(1,2) ＝６にすればよいことがわかります。

最小値になる要素が複数ある場合は、それぞれのｃ(ipvt,jpvt) - ｃ(imin,jpvt) - ｃ(ipvt,jmin) + ｃ(imin,jmin) を計算して、その最大のものを選択します。

これにより、
　　ｘ(1,3) →　０＋６＝　６
　　ｘ(2,3) →　８－６＝　２
　　ｘ(1,2) →　６－６＝　０
　　ｘ(2,2) →１４＋６＝２０
となります。その結果、次のようになります。

総費用=340

そのときの、ｕ(i)，ｖ(j)，ｐ(i,j) を計算すると、次のようになります。

これから、p[3][1]＝-5＜０なので改善が必要になり、
　　x[3][1]＋8 → 8
　　x[3][3]－8 → 0
　　x[1][1]＋8 → 4
　　x[1][3]－8 → 14
を行います。

このように繰り返していくうちに、すべての要素で ｐ(i,j) ≧０になり、最適解に到達します。

総費用=296

輸送問題の計算プログラム

練習用に作成したものなので、「素直な」問題にしか対応していません。