Numerical Optimizer SIMPLE例題集 V19

2.5 ナップサック問題

　ナップサック問題は，ナップサックの中にいくつかの品物を詰め込み入れた品物の総価値を最大にするという問題です．ただし，ナップサックと品物にはそれぞれ容量やサイズが与えられていて，入れた品物のサイズの総和がナップサックの容量を超えてはいけないという条件があります．この問題は，組合せ最適化問題の代表的な例の一つとしてよく知られていて，プロジェクトの選択や物資の購入などの問題に応用されています．以下は，整数ナップサック問題と呼ばれるものです．なお，0-1ナックサック問題につきましては，本節の最後で紹介します．

　まず，変数は各品物を詰め込む個数です．よって，この変数は整数値しか取らないということになります．ただし，「-1個詰め込む」というようなありえない答えを排除する必要があります．このため，各変数は0以上の値しか取らないということを制約条件として明示しておく必要があります．なお，「0個詰め込む」は「その品物を詰め込まない」と解釈します．

　次に，最大化することになる目的関数は詰め込んだものの総価値です．これは，各品物について「1個あたりの価値」と「その品物を詰め込んだ個数」の積を求め，その総和を取ることで表現できます．

　制約条件は，先ほど述べた変数に関するものの他に，詰め込んだ品物のサイズの総和がナップサックの容量を超えないというものがあります．目的関数の時と同様に考えると，各品物に関する「1個あたりのサイズ」と「その品物を詰め込んだ個数」の積の総和をとると詰め込んだ品物のサイズの総和が得られます．よって，この総和がナップサックの容量である65を超えないということを式で表せばよいことになります．

　以上のことから，この例題は次のように定式化することが出来ました．

　定式化した結果をSIMPLEで記述すると次のようになります．

//整数変数を宣言する
IntegerVariable coffee(name= "缶コーヒーの個数");
IntegerVariable water(name="水入りペットボトルの個数");
IntegerVariable banana(name="バナナの個数");
IntegerVariable apple(name="りんごの個数");
IntegerVariable rice_ball(name="おにぎりの個数");
IntegerVariable bread(name="パンの個数");

//総価値を最大化する
Objective total_value(name="総価値",type=maximize);
total_value=120*coffee+130*water+80*banana+100*apple+
            250*rice_ball+185*bread;

//容量に関する制約
10*coffee+12*water+7*banana+9*apple+21*rice_ball+16*bread<=65;

//各品物は0個以上詰め込む
coffee>=0;
water>=0;
banana>=0;
apple>=0;
rice_ball>=0;
bread>=0;

//求解し結果を出力する
solve();
coffee.val.print();
water.val.print();
banana.val.print();
apple.val.print();
rice_ball.val.print();
bread.val.print();
total_value.val.print();

　このモデルをNumerical Optimizerで実行すると，最後に

缶コーヒーの個数=3
水入りペットボトルの個数=0
バナナの個数=2
りんごの個数=0
おにぎりの個数=1
パンの個数=0
総価値=770

という表示がされます．そして，この表示から「缶コーヒーを3個，バナナを2個，そしておにぎりを1個詰め込むと良い」というこの例題の答えを確認できます．

　

　ところで，このモデルについて品物の種類などを変更したい場合SIMPLEでの記述を修正する箇所が多く大変な手間がかかってしまいます．この対策として，ナップサックの容量，品物の価値および品物のサイズを別に用意したdatファイルから与えることにします．このようにすることで，SIMPLEでの記述が汎用的なものになり，品物の種類が変わったとしてもdatファイルの変更のみで対応できるようになります．そのために，ここでは「品物の集合」という概念を導入します．すると定式化は次のように書き直すことができます．

　この定式化をSIMPLEで記述すると，以下のような簡潔なものになります．なお，品物の集合の具体的な要素についてはNumerical Optimizerではdatファイルから自動的に認識します．

//品物の集合を宣言する
Set Object;
Element i(set=Object);

//データファイルから与えるパラメータを宣言する
Parameter capacity(name="ナップサックの容量");
Parameter value(name="品物の価値",index= i);
Parameter size(name="品物のサイズ", index=i);

//整数変数を宣言する
IntegerVariable count(name="詰め込む個数",index= i);

//総価値の最大化
Objective total_value(name="総価値",type=maximize);
total_value=sum(value[i]*count[i], i);

//容量に関する制約
sum(size[i]*count[i], i)<=capacity;

//各品物は0個以上詰め込む
count[i]>=0;

//求解し結果を出力する
solve();
count.val.print();
total_value.val.print();

　なお，今回の例題についてのdatファイルは次のようになります．

ナップサックの容量=65;
品物の価値=
[缶コーヒー]120
[水入りペットボトル]130
[バナナ]80
[りんご]100
[おにぎり]250
[パン]185;
品物のサイズ=
[缶コーヒー]10
[水入りペットボトル]12
[バナナ]7
[りんご]9
[おにぎり]21
[パン]16;

　最後に，この例題では「缶コーヒーが3個」というように容量が許す限り同じ品物を何個でも詰め込むことができました．それでは，各品物についてナップサックに詰め込むことができるのは1個だけということにするとどのようになるでしょうか．なお，この制限を加えると0-1ナップサック問題という典型的な0-1整数計画問題になります．SIMPLEでは，0-1変数であるという宣言を簡単に行うことができます．具体的には，先ほど汎用化させたSIMPLEモデル中で変数を宣言している部分を

IntegerVariable count(name="詰め込む個数",index=i, type=binary);

とするだけです．さらに，この宣言から各変数がとりうる値は0か1しかないということが明らかなため，各品物は0個以上詰め込むという制約「count[i]>=0;」を記述する必要がなくなります．以上の点についてモデルファイルを書き換えた（knapsack3.smp参照）上で，Numerical Optimizerで実行させると，

詰め込む個数["おにぎり"]=1
詰め込む個数["りんご"]=1
詰め込む個数["バナナ"]=1
詰め込む個数["パン"]=1
詰め込む個数["缶コーヒー"]=0
詰め込む個数["水入りペットボトル"]=1
,[*] = [i]
総価値=745

という結果が得られ，缶コーヒー以外の品物を詰め込むと良いという事がわかります．

---

 

 

上に戻る