【ナップザック問題】粗利益を最大化するような商品発注を整数計画法で最適化
輸入コンテナの積載範囲内で粗利益最大になるように発注したい事例
ある日系小売業のタイ法人は、日本から毎週商品を海上コンテナ１本分輸入しています。
海上コンテナは積載荷重25t、積載容量50m3です。
本当はコンテナ１本分以上発注したいのですが、２本では多すぎるため、毎週何らかの商品の発注を諦めています。
今までは担当者が諦める商品を勘で決めていたのですが、今後は発注した商品の粗利益が最大になるように発注する商品を決めたいと考えています。
今週の発注商品の候補は次の通りです。
重量３２ｔ＞２５ｔ、容積８５.６ｍ３＞５０ｍ３なので、どちらも最大積載量を上回っています。
これを最大積載量ギリギリまで積めて、商品の粗利益合計額を最大にするには、どの商品を発注すれば良いでしょうか？
0-1整数計画法として解く場合
定式化する
商品一つひとつを見ると、随分大きいですね。
これは１個の商品ではなく、まとめているためです。
例えば、商品Aは１,０００箱分で５,０００ｋｇというイメージです。
この１,０００箱分をすべて発注するかしないかの判断になります。
従って、商品Ａ～Ｋを発注するかしないかをx1～x11の変数で表し、それぞれ１（発注する）か０（発注しない）しか値をとらないとします。
すると、発注する商品の粗利益合計は次のように計算できます。
粗利益合計＝100000x1+80000x2+90000x3+80000x4+60000x5+120000x6+90000x7
+40000x8+70000x9+100000x10+60000 x11・・・①
また積載重量と積載容積の制限から、次の制約式が成り立ちます。
重量の制約
5000x1+1000x2+8000x3+2000x4+2000x5+2000x6+4000x7+1000x8+2000x9
+4000x10+1000 x11≦25000・・・②
容積の制約
9.6x1+8x2+6.4x3+10.4x4+5.6x5+12.8x6+4.8x7+4.8x8+8x9+9.6x10+5.6x11≦50・・・③
以上から、制約条件②及び③のもとで、目的関数①を最大化するxiを求める最適化問題になります。
また変数xiは０または１ですので、整数計画法の中でも特に0-1整数計画法の問題と呼ばれます。
Excelソルバーで解く
これは前回の記事のようにExcelのソルバーで解くことができます。
まずはExcelシートに表を作ります。
続いてデータ⇒ソルバーをクリックしソルバー画面を開いて、下記のように目的関数と制約条件を入力します。
これを実行すると、次のような計算結果になりました。
商品A、B、C、E、G、J、Kを発注すると最大粗利益５８０,０００円になり、その時の重量は制限いっぱいの２５ｔ、容積は制限ギリギリの４９.６m3になります。
整数計画法として解く場合
定式化する
上記のように発注すれば、ほぼ積載率１００％近くまで積んで最大粗利益が５８万円になりますが、商品D、F、H、Iは発注することができません。
さすがに４割近くの商品が欠品してしまうと、顧客に叱られてしまいそうです。
また商品を落とされたマーチャンダイザーも怒るでしょう。
そこで、すべての商品を発注するという制約条件を付け加えます。
しかしすべての商品を１００％発注することはできませんので、マーチャンダイザーから上がってきた希望発注数量の±５０％の範囲で数量を調整可能にします。
ここでは説明を簡単にするために、すべての商品の希望発注数量が１,０００箱だったと仮定します。
すると、１箱当たりの重量、容積、粗利益は次のようになります。
そして、今度は先ほど０か１しかとらない変数として定義したx1～x11を、正の整数をとる変数として定義し直します。
すると、Excelの表は次のようになります。
Excelソルバーで解く
そしてソルバーの設定画面には次のように入力します。
ソルバーを実行すると、次のように計算結果が表示されます。
最大粗利益は１万円ほど減りましたが、すべての商品が発注され、顧客もマーチャンダイザーも満足でしょう。
物流で応用範囲の広いナップザック問題
このような整数計画法の問題はナップザック問題と言われます。
OR（オペレーションズリサーチ）の分野の中でも有名な問題の一つです。
容量が限られたナップザックの中に入れる品物の価値を最大化させる問題と同じだからです。
この場合の容量は重量でも容積でもいいのですが、物流の世界では重量と容積を同時に考慮する必要があります。
そのような場合でも、今回の例のようにナップザック問題と考えることができますので、応用範囲は広いと思います。