スタートページWeb教材一覧オペレーションズリサーチ

動的計画法による最大化問題

参照:JavaScriptの計算プログラム


最適配分問題の説明

動的計画法により、
   目的関数: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 は、次の手順で知ることができます。

  1. i=3、Q=4、x3=2のときで最大になったのですから、投資3に2を配分します。残りの資金2(=Qmax-x3)が、投資1と投資2に配分されたことがわかります。
  2. i=2、Q=2のときは、x2=1のときに最大になったのだから、投資2に1を配分したときだとわかり、
  3. その残り1(2-1)を投資1に配分すればよいことがわかります。

計算プログラム

投資数N= 全投資資金Qmax= 1投資への最大投資額=

各投資に資金を配分したときの各投資で得られる利益を入力
配分資金投資1投資2投資3
 1 
 2 
 3