3.3 動的計画法の応用
目次（第３章）へ
3.3.1 作業人員配置計画への応用
次の表のように，５人の作業員を４つの収穫作業に配分するときの最適化を考えてみよう．ただし，表中の数字は，ある作業に作業員を配分したときのその作業の利益（単位：万円）を示す．
作業員 |
収穫作業 |
|||
J1 |
J2 |
J3 |
J4 |
|
1 2 3 4 5 |
20 40 60 60 50 |
10 20 30 50 70 |
30 40 50 70 80 |
20 30 40 50 60 |
全作業員５人を４つの作業に配分する方法は，全部で５６通りあるので，各々全部計算して最大値を見いだすことはできる．これは， "brute force" 法と呼ばれる．
●ソフトウェア DP2_e_80.exe
この問題に動的計画法を適用して，作業を段階（stages），その作業に配分する作業員を状態（states）とみなし後退法を適用すると， 次表は段階４（作業４）について，各１〜５人の作業員を配分したときの利益を示し，その次の表は段階３について示す．
段階 4
次の状態 |
最大 |
最適 |
||||||
状態 |
0 |
1 |
2 |
3 |
4 |
5 |
利益 |
コース |
1 2 3 4 5 |
20 30 40 50 60 |
20 30 40 50 60 |
0 0 0 0 0 |
|||||
段階3
次の状態 |
最大 |
最適 |
||||||
状態 |
0 |
1/20 |
2/30 |
3/40 |
4/50 |
5/60 |
利益 |
コース |
1 2 3 4 5 |
30 40 50 70 80 |
20 30+20=50 40+20=60 50+20=70 70+20=90 |
30 30+30=60 40+30=70 50+30=80 |
40 30+40=70 40+40=80 |
50 30+50=80 |
60 |
30 50 60 70 90 |
0 1 1,2 0,1,2,3 1 |
段階2
次の状態 |
最大 |
最適 |
||||||
状態 |
0 |
1/30 |
2/50 |
3/60 |
4/70 |
5/90 |
利益 |
コース |
1 2 3 4 5 |
10 20 30 50 70 |
30 10+30=40 20+30=50 30+30=60 50+30=80 |
50 10+50=60 20+50=70 30+50=80 |
60 10+60=70 20+60=80 |
70 10+70=80 |
90 |
30 50 60 70 90 |
1 2 2,3 2,3,4 5 |
段階1
次の状態 |
最大 |
最適 |
||||||
状態 |
0 |
1/30 |
2/50 |
3/60 |
4/70 |
5/90 |
利益 |
コース |
1 2 3 4 5 |
20 40 60 60 50 |
30 20+30=50 40+30=70 60+30=90 60+30=90 |
50 20+50=70 40+50=90 60+50=110 |
60 20+60=80 40+60=100 |
70 20+70=90 |
90 |
30 50 70 90 110 |
1 1,2 1,2 1,2 2 |
従って，最大利益は110万円で，作業員の配置は［3,0,1,1］である．
また，数式解法では以下のとおりである．
なお，RJのあとの数字は，当該作業番号と各々配分全作業員を示す．
RJ41=20, RJ42=30, RJ43=40, RJ44=50, RJ45=60
RJ31=max（J31, RJ41） =max（30, 20）=30
RJ32=max（J32, J31+RJ41, J30+RJ42） =max（40, 30+20, 0+30）=50
RJ33=max（J33, J32+RJ41, J31+RJ42, J30+RJ43） =max（50, 40+20, 30+30, 0+40）=60
RJ34=max（J34, J33+RJ41, J32+RJ42, J31+RJ43, J30+RJ44）
=max（70, 50+20, 40+30, 30+40, 0+50）=70
RJ35=max（J35, J34+RJ41, J33+RJ42, J32+RJ43, J31+RJ44, J30+RJ45）
=max（80, 70+20, 50+30, 40+40, 30+50, 0+60）=90
RJ21=max（J21, RJ31） =max（10, 30）=30
RJ22=max（J22, J21+RJ31, J20+RJ32） =max（20,10+30,0+50）=50
RJ23=max（J23, J22+RJ31, J21+RJ32, J20+RJ33 =max（30, 20+30, 10+50, 0+RJ33）=60
RJ24=max（J24, J23+RJ31, J22+RJ32, J21+RJ33, J20+RJ34）
=max（50, 30+30, 20+50, 10+60, 0+70）=70
RJ25=max（J25, J24+RJ31, J23+RJ32, J22+RJ33, J21+RJ34 ,J20+RJ35）
=max（70, 50+30, 30+50, 20+60, 10+70, 0+90）=90
RJ11=max（J11, RJ21） =max（20, 30）=30
RJ12=max（J12, J11+RJ21, J10+RJ22） =max（40, 20+30, 0+50）=50
RJ13=max（J13, J12+RJ21, J11+RJ22, J10+RJ23） =max（60, 40+30, 20+50, 0+60）=70
RJ14=max（J14, J13+RJ21, J12+RJ22, J11+RJ23, J10+RJ24）
=max（60, 60+30, 40+50, 20+60, 0+70）=90
RJ15=max（J15, J14+RJ21, J13+RJ22, J12+RJ23, J11+RJ24, J10+RJ25）
=max（50,60+30,60+50,40+60,20+70,0+90）=110
J（3,0,1,1）=110