スタートページ> Web教材一覧> オペレーションズリサーチ> 線形計画法
線形計画法、輸送問題、北西隅の方法、UV法(ポテンシャル法)
輸送問題とは、複数の供給地と需要地があり、それぞれの供給量と需要量、供給地から需要地までの1個あたりの輸送費用が与えられているときに、総輸送費用を最小にするには、どの供給地からどの需要地へ、いくつ輸送すればよいかを求める問題です。線形計画法の特殊な問題です。
m 供給地の数
n 需要地の数
a(i) 供給地iの供給量
b(j) 需要地jの需要量
c(i,j) 供給地iから需要地jに1個輸送する費用
x(i,j) 供給地iから需要地jに輸送する量
とすると、次のように定式化されます。
目的関数
c(1,1)x(1,1) + c(1,2)x(1,2) +・・・
+ c(i,j)x(i,j) +・・・+ c(m,n)x(m,n) →最小
制約条件
(供給量条件)
x(1,1) + x(1,2) +・・・+ x(1,n) = a(1)
x(2,1) + x(2,2) +・・・+ x(2,n) = a(2)
: :
x(m,1) + x(m,2) +・・・+ x(m,n) = a(m)
(需要量条件)
x(1,1) + x(2,1) +・・・+ x(m,1) = b(1)
x(1,2) + x(2,2) +・・・+ x(m,2) = b(2)
: :
x(1,n) + x(2,n) +・・・+ x(m,n) = b(n)
これは、線形計画法を用いて解くことができますが、制約条件での係数がすべて1であるという特徴があります。その特徴に着眼して、計算を容易にする方法が輸送問題なのです。
輸送問題を解く手順は、次のようになります。
数値例を用いて、北西隅の方法とUV法(ポテンシャル法)について解説します。
供給地の個数=3, 需要地の個数=4
需要地1 | 需要地2 | 需要地3 | 需要地4 | ||
需要量→ ↓供給量 | 12 | 20 | 16 | 18 | |
供給地1 | 18 | 7 | 3 | 2 | 10 |
供給地2 | 22 | 9 | 3 | 6 | 8 |
供給地3 | 26 | 8 | 7 | 8 | 6 |
北西(左上)から右へ下へと順に輸送量を決めていく方法です。
需要地1 | 需要地2 | 需要地3 | 需要地4 | ||
需要量→ ↓供給量 | 12 | 20 | 16 | 18 | |
供給地1 | 18 | 12 | 6 | ||
供給地2 | 22 | 14 | 8 | ||
供給地3 | 26 | 8 | 18 |
このときの総費用は、
c(1,1)x(1,1) + c(1,2)x(1,2) + c(2,2)x(2,2)
+ c(2,3)x(2,3) + c(3,3)x(3,3) + c(3,4)x(3,4)
=7×12 + 3×6 + 3×14 + 6×8 + 8×8 + 6×18
=364
となります。
この解は改善の余地があります。例えば
需要地2 需要地3
供給地1 c(1,2)=3 c(1,3)=2
x(1,2)=6 x(1,3)=0
供給地2 c(2,2)=3 c(2,3)=6
x(2,2)=14 x(2,3)=8
になっています。ここで、
(1,3)に1個割り付けると、 2円増加
(1,2)が1個減り、 3円減少
(2,3)が1個減り、 6円減少
(2,2)が1個増える 3円増加
ので、総費用は、2-3-6+3=-4円だけ変化します。
そして、(1,3)に割り付けることができる最大値は、x(1,2)とx(2,3)の小さいほうになります。
このようなループと最大値を、目視ではなく、数学的に求めることが必要になります。
新しい概念、
u(i) :供給地iの供給量 a(i) を1個増大したときの費用減
v(j) :需要地jの供給量 b(i) を1個増大したときの費用減
を導入します。
すると、目的関数や制約条件を次のように書き換えることができます。
目的関数
a(1)u(1) + a(2)u(2) +・・・+ a(m)u(m)
+ b(1)v(1) + b(2)v(2) +・・・+ b(m)v(m) →最大
制約条件
u(i) + v(j) = c(i,j)
これを理解するには、線形計画法の双対問題の知識が必要ですが、ここでは省略して、数値例で説明します。
u(1) =0, u(2) =0, u(3) =2
u(1) =7, u(2) =3, u(3) =6, u(4) =4
以上から次の表が得られます。
需要地1 需要地2 需要地3 需要地4
↓u(i)v(j)→ 7 3 6 4
供給地1 0 -4 6
供給地2 0 2 4
供給地3 2 -1 2
ここで、
p(i,j) =c(i,j) - u(i) - v(j)
= c(i,j)
-c(s,j) [= - u(s) - v(j)]
-c(i,t) [= - u(i) - v(t)]
+c(s,t) [= + u(s) + v(t)]
と変形できます。
そして、x(i,j) を1個増加することは、供給量と需要量を変えないという条件から、x(s,j) と x(i,t) を1個減らして、x(s,t) を1個増やすことになります。そのときの総費用の変化は、c(i,j) - c(s,j) - c(i,t) + c(s,t)
です。すなわち、
p(i,j) は、x(i,j) の値を1個増大したときの総費用の変化
を示しています。
それで、
すべての要素で p(i,j) ≧0 になれば、最適解である。
といえます。
p(i,j) <0 の要素があれば、x(i,j) を増加させれば総費用を下げることができます。
全要素のうち、p(i,j) が最小(負で絶対値が最大)の要素を (ipvt, jpvt) としましょう。数値例では p(1,2)=-4がそれにあたります。
x(ipvt,jpvt) の最大値は、行ipvtの要素 x(ipvt, j) (x(ipvt,jpvt) を除く)のなかで正の最小値 x(ipvt, jmin) と、列jpvtの要素 x(i, jpvt) (x(ipvt,jpvt) を除く)のなかで正の最小値 x(imin, jpvt) の小さいほうになります。
数値例では、行1のなかでの最小値は x(1,1)=12、列3のなかでの最小値は x(2,3)=8ですから、x(1,2) =6にすればよいことがわかります。
最小値になる要素が複数ある場合は、それぞれのc(ipvt,jpvt) - c(imin,jpvt) - c(ipvt,jmin) + c(imin,jmin) を計算して、その最大のものを選択します。
これにより、
x(1,3) → 0+6= 6
x(2,3) → 8-6= 2
x(1,2) → 6-6= 0
x(2,2) →14+6=20
となります。その結果、次のようになります。
需要地1 | 需要地2 | 需要地3 | 需要地4 | ||
需要地→ ↓供給地 | 12 | 20 | 16 | 18 | |
供給地1 | 18 | 12 | 6 | ||
供給地2 | 22 | 20 | 2 | ||
供給地3 | 26 | 0 | 8 | 18 |
総費用=340
そのときの、u(i),v(j),p(i,j) を計算すると、次のようになります。
需要地1 | 需要地2 | 需要地3 | 需要地4 | ||
v[j]→ ↓u[i] | 7 | -1 | 2 | 0 | |
供給地1 | 0 | 4 | 10 | ||
供給地2 | 4 | -2 | 4 | ||
供給地3 | 6 | -5 | 2 |
これから、p[3][1]=-5<0なので改善が必要になり、
x[3][1]+8 → 8
x[3][3]-8 → 0
x[1][1]+8 → 4
x[1][3]-8 → 14
を行います。
このように繰り返していくうちに、すべての要素で p(i,j) ≧0になり、最適解に到達します。
需要地1 | 需要地2 | 需要地3 | 需要地4 | ||
需要地→ ↓供給地 | 12 | 20 | 16 | 18 | |
供給地1 | 18 | 2 | 16 | ||
供給地2 | 22 | 2 | 20 | ||
供給地3 | 26 | 8 | 18 |
総費用=296
練習用に作成したものなので、「素直な」問題にしか対応していません。