スタートページ> Web教材一覧> オペレーションズリサーチ
動的計画法により、
目的関数:Rx = f1(x1) + f2(x2) + ・・・ + fn(xn) →最大
制約条件:Q=x1 + x2 + ・・・ + xn ≦ Qmax 0 ≦ xi ≦ xmaxi
を解く方法を解説します。
これは、「n個の投資があり、投資iに xi の資金を配分したときの利益が fi(xi) であるとしたとする。全投資のための資金の上限がQmaxであるとき、利益最大にする各投資への資金配分額を求めよ。ただし、投資iに配分できる資金は 0 ≦ xi ≦ xmaxi であるとする。」という意味です。
数値例では、3個の投資について、配分費用と利益が表のように与えられているとき、資金上限が4であるとすれば、各投資への配分を求めることになります(その解答は、投資1に1、投資2に1、投資3に2としたとき利益は最大値15になります)。
配分資金 上限値
0 1 2 3 (xmax)
↓ 投資1 0 2 4 6 3
i 投資2 0 5 5 6 3
投資3 0 0 8 - 2
ここで、ある投資に配分限界以上に資金を配分したときには、限界内での最大利益になるという条件をつけましょう。例えば、投資1に4の資金を配分したときの利益は6、投資3に3の資金を配分した(表の「-」の部分)ときの利益は8であるとします。
最適性の原理によって、
Pi(Q) = max{ fi(xi) + Pi-1(Q-xi) } i=2~n 0 ≦ Q ≦ Qmax 0 ≦ xi ≦ Q
P1(Q) = max{ f1(x1) x1=0~Q } = f1(Q) 0 ≦ Q ≦ Qmax
の関係があります。
上の式は、次のことを表しています。
max{ } の中は、全体の配分資金をQとしたとき、
新投資iを加えたときの利益
=「新投資iに xi を配分したときの利益」 f2(x2)
+「それまでの投資にQ-xi を投資したときの最大利益」 P1(Q-x2)
であり、
Pi(Q) とは、xi を0~Qまで変化させたときの最大利益、すなわち、資金がQで新投資iを加えたときの最大利益を示しています。
このように、「全体の配分が最適なときは、新しい投資にどのような決定をするかに関係なく、それまでの投資での最適配分は維持される」というのが最適性の原理であり、「それまでの投資での最適配分」を記録しておき、有効に活用するのが動的計画法の特徴なのです。
上の式では、Pi-1 を用いているので、最初の投資1に適用することはできません。それで、投資1(i=1)には下の式が必要になります。
投資1では、x1=Qになります。それで、f1(x1) で xi を0~Qまで変化させたときの最大利益を P1(Q) とするのですが、実務的に考えれば「配分を多くしたら利益が下がる」ような場合は、利益最大のところで打ち切るでしょうから、f1(x1) は右上がりになっているはずです。それで、
max{ f1(x1) } = f1(Q)
とすることができます。
これを用いて上の問題を解いてみましょう。この手順は、まず投資1だけの場合を計算し、次に投資2を加えたときを計算し、次に投資3を・・・というように計算していきます。そのとき、直前の結果を記録しておくことにより、計算量を少なくしています。
全投資資金の上限Qmax=4とします。
●i=1(投資1だけのとき)
上の表から、xmax1 = 3
f1(0) = 0 f1(1) = 2 f1(2) = 4 f1(3) = 6
になっています。
例えば f1(2) = 4 とは、「投資1に2の資金を配分したときの利益は4である」ことを示しています。
そして、
P1(x1) = f1(k1)
ですので、
P1(0) = f1(0) = 0
P1(1) = f1(1) = 2
P1(2) = f1(2) = 4
P1(3) = f1(3) = 6
になります。
さらに、「配分上限値以上の配分をしたときは、限界内での最大値とする」という条件により、
P1(4) = 6
とします。
結果として、i=1が完了したときには、
P1(0)=0, P1(1)=2, P1(2) = 4, P1(3) = 6, P1(4) = 6
になっています。
●i=2(投資2を加えたとき)
ここまでに、
P1(0) = 0 f2(0) = 0
P1(1) = 2 f2(1) = 5
P1(2) = 4 f2(2) = 5
P1(3) = 6 f2(3) = 6
P1(4) = 6
がわかっており、
P2(Q) = max{ f2(x2) + P1(Q-x2) } 0 ≦ Q ≦ Qmax x2 = 1~Q
を用いて計算します。
Q=0(資金が0のとき)
P2(0) = max{ f2(0) + P1(0-x2) x2=0} = 0 + 0 = 0
Q=1(資金が1のとき)
P2(1) = max{ f2(x2) + P1(1-x2) x2=0~1}
投資2に0を配分(投資1に1を配分) f2(0) + P1(1) = 0 + 1 = 2
投資2に1を配分(投資1に0を配分) f2(1) + P1(0) = 5 + 0 = 5 ←max
=5
Q=2(資金が2のとき)
P2(2) = max{ f2(x2) + P1(1-x2) x2=0~2}
投資2に0を配分(投資1に2を配分) f2(0) + P1(2) = 0 + 4 = 4
投資2に1を配分(投資1に1を配分) f2(1) + P1(1) = 5 + 2 = 7 ←max
投資2に2を配分(投資1に0を配分) f2(2) + P1(0) = 5 + 0 = 5
=7
Q=3(資金が3のとき)
P2(2) = max{ f2(x2) + P1(1-x2) x2=0~3}
投資2に0を配分(投資1に3を配分) f2(0) + P1(3) = 0 + 6 = 6
投資2に1を配分(投資1に2を配分) f2(1) + P1(2) = 5 + 4 = 9 ←max
投資2に2を配分(投資1に1を配分) f2(2) + P1(1) = 5 + 2 = 7
投資2に3を配分(投資1に0を配分) f2(3) + P1(0) = 6 + 0 = 6
=7
Q=4(資金が4のとき)
P2(2) = max{ f2(x2) + P1(1-x2) x2=0~4}
★投資2に0を配分(投資1に4を配分) f2(0) + P1(4) = 0 + 6 = 6
投資2に1を配分(投資1に3を配分) f2(1) + P1(3) = 5 + 6 = 11 ←max
投資2に2を配分(投資1に2を配分) f2(2) + P1(2) = 5 + 4 = 9
投資2に3を配分(投資1に1を配分) f2(3) + P1(1) = 6 + 2 = 8
★投資2に4を配分(投資1に0を配分) f2(4) + P1(0) = 6 + 0 = 6
=11
結果として、i=2が完了したときには、
P2(0)=0, P2(1)=5, P2(2) = 7, P2(3) = 9, P2(4) = 11
になっています。
(★は、xi>xmaxi、または、Q-xi>max{ xmaxk k=1~i-1 } のときは、各投資の配分上限以上に配分することであり、それが最大になることはないので計算する必要はありません。以下同様です。)
●i=3(投資3を加えたとき)
ここまでに、
P2(0) = 0 f3(0) = 0
P2(1) = 5 f3(1) = 0
P2(2) = 7 f3(2) = 8
P2(3) = 9 f3(3) = 8★
P2(4) = 11
がわかっており、
P3(Q) = max{ f3(x3) + P2(Q-x2) } 0 ≦ Q ≦ Qmax x3 = 1~Q
を用いて計算します。
f3(x3) は、全体の資金Qのうち、投資3に x3 を配分したときの利益であり、P2(Q-x2) は、残りの資金 Q-x3 を、これまでの投資(投資1と投資2)に配分したときの最大利益です。
Q=0(資金が0のとき)
P3(0) = max{ f3(0) + P2(0-x2) x3=0} = 0 + 0 = 0
Q=1(資金が1のとき)
P3(1) = max{ f3(x3) + P2(1-x3) x3=0~1}
投資3に0を配分(投資1・2に1を配分) f3(0) + P2(1) = 0 + 5 = 5 ←max
投資3に1を配分(投資1・2に0を配分) f3(1) + P2(0) = 0 + 0 = 0
=5
Q=2(資金が2のとき)
P3(2) = max{ f3(x3) + P2(2-x3) x3=0~2}
投資3に0を配分(投資1・2に2を配分) f3(0) + P2(2) = 0 + 7 = 7
投資3に1を配分(投資1・2に1を配分) f3(1) + P2(1) = 0 + 5 = 5
投資3に2を配分(投資1・2に0を配分) f3(2) + P2(0) = 8 + 0 = 8 ←max
=8
Q=3(資金が3のとき)
P3(3) = max{ f3(x3) + P2(3-x3) x3=0~3}
投資3に0を配分(投資1・2に3を配分) f3(0) + P2(3) = 0 + 9 = 5
投資3に1を配分(投資1・2に2を配分) f3(1) + P2(2) = 0 + 7 = 7
投資3に2を配分(投資1・2に1を配分) f3(2) + P2(1) = 8 + 5 = 13 ←max
★投資3に3を配分(投資1・2に0を配分) f3(3) + P2(0) = 8 + 0 = 5
=13
Q=4(資金が4のとき)
P3(3) = max{ f3(x3) + P2(3-x3) x3=0~4}
★投資3に0を配分(投資1・2に4を配分) f3(0) + P2(4) = 0 +13 = 13
投資3に1を配分(投資1・2に3を配分) f3(1) + P2(3) = 0 + 9 = 9
投資3に2を配分(投資1・2に2を配分) f3(2) + P2(2) = 8 + 7 = 15 ←max
★投資3に3を配分(投資1・2に1を配分) f3(3) + P2(1) = 8 + 5 = 13
★投資3に4を配分(投資1・2に0を配分) f3(4) + P2(0) = 8 + 0 = 8
=13
結果として、i=3が完了したときには、
P3(0)=0, P3(1)=5, P3(2) = 8, P3(3) = 13, P3(4) = 15
になっています。
これより、
P3(0) から、投資資金0のときは、最大利益は 0
P3(1) から、投資資金1のときは、最大利益は 5
P3(2) から、投資資金2のときは、最大利益は 8
P3(3) から、投資資金3のときは、最大利益は13
P3(4) から、投資資金4のときは、最大利益は15
であることがわかります。
最大利益15になるときの各投資への配分、x1、x2、 ・・・、xn は、次の手順で知ることができます。