この記事は前回の記事の続きです。まだ見てない方はこちらをクリック！
こんにちは！しゅんです！
いきなりですが皆さんはいま運送会社の従業員で、これからトラックにどんな荷物を積めば良いかを考えてもらいます。
積みたい荷物はたくさんあるけどトラックの容量は決まっているので全部を積むことはできません。こんなときはどの荷物を積むのがいちばん良いのでしょうか。今回の記事ではこんな問題を数学を使って解いてみたいと思います！
普段は組合せ最適化の記事を書いてたりします。
ぜひ他の記事も読んでみてください！
このブログの簡単な紹介はこちらに書いてあります。
興味があったら見てみてください。
このブログでは経営工学を勉強している現役理系大学生が、経営工学に関することを色々話していきます！
ぼくが経営工学を勉強している中で感じたことや、興味深かったことを皆さんと共有出来たら良いなと思っています。
そもそも経営工学とは何なのでしょうか。Wikipediaによると
経営工学（けいえいこうがく、英: engineering management）は、人・材料・装置・情報・エネルギーを総合したシステムの設計・改善・確立に関する活動である。そのシステムから得られる結果を明示し、予測し、評価するために、工学的な分析・設計の原理・方法とともに、数学、物理および社会科学の専門知識と経験を利用する。
引用元 : 経営工学 – Wikipedia
長々と書いてありますが、要は経営、経済の課題を理系的な観点から解決する学問です。
問題設定
それではまず今回考える問題をちゃんと設定しましょう。
問題設定
・倉庫に20個の荷物があり、それらの中からいくつかをトラックで運ぶことを考える。
・トラックに積める荷物は合計で300kgまで。
・荷物は「書籍」、「食料品」、「家電」、「家具」の4つのグループのいずれかに属す。
・それぞれの荷物は既知であり、以下の通りである。
目的
・積まれる荷物の個数が最も小さいグループ内の、積まれる荷物の個数を最大化したい
前回の記事とは違い、最小値を最大化したいという目的になっています。例えば以下の2つのケースを考えましょう。
Case.1
「書籍」: 4個
「食料品」: 1個
「家具」: 3個
「家電」: 3個
合計：11個
Case.2
「書籍」: 2個
「食料品」: 2個
「家具」: 3個
「家電」: 3個
合計：10個
Case.1では合計11個の荷物をトラックに積むことができています。一方Case.2では合計10個の荷物をトラックに積むことができています。両者を比較するとCase.1の方がたくさん荷物を積めています。
一方で最も荷物を積めていないグループを比較すると、Case.1では「食料品」の1個が最小値でCase.2では「書籍」、「食料品」の2個が最小値です。この2つを比べるとCase.2の方が最小値の値が大きいです。
このように合計で比較するのではなく、グループの最小値同士を比較したときに最も大きいものを求めたいと思います。
整数計画問題として定式化
「記号の設定」、「目的関数の設定」、「制約条件の設定」の3つに分けて説明したいと思います。
記号の設定
パラメータとして荷物の集合と、各グループに属す荷物の集合、荷物の重さを設定します。変数は0-1変数\(x_i\)を使いたいと思います。
パラメータ：
\(G\) : グループの集合
\(I\) : 荷物の集合
\(I_g\) : グループ\(g\)に属す荷物の集合
\(w_i\) : 荷物\(i\)の重さ
変数：
\(x_i \in \{0,1\}\)
なお、\(I_g\)は\(I\)の分割なので\(\bigcup\limits_{g \in G}I_g = I, p \ne q \Rightarrow I_p \cap I_q = \emptyset\)です。
目的関数の設定
トラックに積まれるグループ\(g\)中の荷物の個数は
\(\sum\limits_{i \in I_g}x_i\)
と表せます。よって目的関数は以下のように表せます。
目的関数：\(\min\limits_{g \in G} \sum\limits_{i \in I_g}x_i \)
例えば「書籍」を4個、「食料品」を1個、「家電」を3個、「家具」を3個トラックに積むとします。（「書籍」を1、「食料品」を2、「家電」を3、「家具」を4と数字でグループを表しています。）このとき目的関数値は
\(\min\limits_{g \in G}\sum\limits_{i \in I_g}x_i = \min\{4,1,3,3\} = 1\)
となります。この値はトラックに積まれた個数が最も少ないグループ、すなわち「食料品」の荷物の個数と対応していますね。今回はこれを最大化することを考えます。
\( \max\min\limits_{g \in G} \sum\limits_{i \in I_g}x_i \)
ということでマックスミニ問題として表すことができました。ここからさらにもう一工夫します。
\(t=\min\limits_{g \in G} \sum\limits_{i \in I_g}x_i\)
とします。このとき\(t\)は以下の制約を満たす必要があります。
\(\sum\limits_{i \in I_g}x_i \geq t \;\;\; (\forall g \in G)\)
\(t\)は\(\sum\limits_{i \in I_g}x_i\)の最小値なので、全ての\(g \in G\)に対して上記の式が成り立つはずです。
ということで上記のマックスミニ問題を以下のように変形することができます。
\( \max \;\;\; t\)
\( \;\text{s.t.}\;\;\;\sum\limits_{i \in I_g}x_i \geq t \;\;\; (\forall g \in G)\)
制約条件の設定
制約条件：\(\sum\limits_{i \in I}w_ix_i \leq 300 \)
制約条件は
「トラックに積める荷物の重さの合計は300kg以下」
です。これを数式で表すと上記のようになります。
例えば荷物3,8,10をトラックに積む場合を考えましょう。このとき\(x_4 = x_8 = x_{10} = 1\)となります。そして制約条件の左辺は
\(\sum\limits_{i \in I}w_i x_i = w_4 x_4 + w_8 x_8 + w_{10}x_{10} = 44\)
となり、荷物4,8,10の重さの合計を表しています。これが300以下になれば良いので上記のような制約条件になります。
整数計画問題としてまとめる
以上のことを踏まえて整数計画問題として定式化しましょう。
パラメータ：
\(G\) : グループの集合
\(I\) : 荷物の集合
\(I_g\) : グループ\(g\)に属す荷物の集合
\(w_i\) : 荷物\(i\)の重さ
変数：
\(x_i \in \{0,1\}\)
\(t\)
\(\max \;\;\; t\)
\(\;\text{s.t.}\;\;\;\sum\limits_{i \in I_g} x_i \geq t \;\;( \forall g \in G)\)
\(\;\;\;\;\;\;\;\;\; \sum\limits_{i \in I} w_ix_i \leq 300\)
\(\;\;\;\;\;\;\;\;\; x_{ij} \in \{0,1\} \;\;( \forall i \in I)\)
pythonで解いてみる
それでは実際にこの問題をpythonで解いてみましょう。結論以下のコードを実行することで問題を解くことができます。
## 事前準備
!pip install pulp # pulpをインストール
from pulp import *
## 記号の定義
I = [i for i in range(20)] # 荷物の集合
I_1 = [i for i in range(0,5)] # 書籍の集合
I_2 = [i for i in range(5,10)] # 食料品の集合
I_3 = [i for i in range(10,15)] # 家電の集合
I_4 = [i for i in range(15,20)] # 家具の集合
w = [5, 19, 25, 3, 9, 4, 16, 25, 15, 16, 46, 38, 32, 29, 41, 26, 38, 39, 45, 50] # 重さの集合
## 整数計画問題として定式化
prob = pulp.LpProblem(sense = LpMaximize) # 問題をMaximizeに設定
x = LpVariable.dict("x",I, cat = "Binary") # 0-1変数の設定
t = LpVariable("t", cat = "Continuous") # 0-1変数の設定
prob += t # 目的関数の設定
prob += lpSum(w[i] * x[i] for i in I) <= 300 # 制約条件を設定
prob += lpSum(x[i] for i in I_1) >= t # 制約条件を設定
prob += lpSum(x[i] for i in I_2) >= t # 制約条件を設定
prob += lpSum(x[i] for i in I_3) >= t # 制約条件を設定
prob += lpSum(x[i] for i in I_4) >= t # 制約条件を設定
result = prob.solve() # 問題を解く
## 結果の表示
print(LpStatus[result]) # 得られた結果の状態を表示（Optimalなら最適解が得られている）
for i in I:
if x[i].value() == 1:
print(f"x{i} =",x[i].value()) # 最適解（変数の値が1のものだけ）を表示
print("最適値 :", prob.objective.value()) # 最適値を表示
このコードを実行したら以下の結果が得られました。
コードの説明と結果の解釈の2つに分けて話したいと思います。
コードの説明
事前準備
## 事前準備
!pip install pulp # pulpをインストール
from pulp import *
問題を解くための事前準備としてpulpをインストール、インポートします。pulpはpythonで数理計画問題を解くのに便利なやつです。2行目でpulpのインストール、3行目でpulpのインポートを行っています。
記号の定義
## 記号の定義
I = [i for i in range(20)] # 荷物の集合
I_1 = [i for i in range(0,5)] # 書籍の集合
I_2 = [i for i in range(5,10)] # 食料品の集合
I_3 = [i for i in range(10,15)] # 家電の集合
I_4 = [i for i in range(15,20)] # 家具の集合
w = [5, 19, 25, 3, 9, 4, 16, 25, 15, 16, 46, 38, 32, 29, 41, 26, 38, 39, 45, 50] # 重さの集合
5～11行目では記号の定義をしています。6行目で荷物の集合\(I\)、7～10行目で各グループに属す荷物の集合、11行目で荷物\(i\)の重さ\(w_i\)をそれぞれリスト形式で設定しています。
整数計画問題として定式化
## 整数計画問題として定式化
prob = pulp.LpProblem(sense = LpMaximize) # 問題をMaximizeに設定
x = LpVariable.dict("x",I, cat = "Binary") # 0-1変数の設定
t = LpVariable("t", cat = "Continuous") # 0-1変数の設定
prob += t # 目的関数の設定
prob += lpSum(w[i] * x[i] for i in I) <= 300 # 制約条件を設定
prob += lpSum(x[i] for i in I_1) >= t # 制約条件を設定
prob += lpSum(x[i] for i in I_2) >= t # 制約条件を設定
prob += lpSum(x[i] for i in I_3) >= t # 制約条件を設定
prob += lpSum(x[i] for i in I_4) >= t # 制約条件を設定
result = prob.solve() # 問題を解く
13～24行目で整数計画問題として定式化しています。
14行目では問題を最大化(Maximize)に設定しています。
15～16行目では変数の設定をしています。
17行目では目的関数を設定しています。
18行目では制約条件\(\sum\limits_{i \in I} w_ix_i \leq 300\)を設定しています。\(\sum\)はlpSumで表現できます。
19～22行目では制約条件\(\sum\limits_{i \in I_g} x_i \geq t \;\;( \forall g \in G)\)を設定しています。
24行目で問題を解いています。
結果の表示
## 結果の表示
print(LpStatus[result]) # 得られた結果の状態を表示（Optimalなら最適解が得られている）
for i in I:
if x[i].value() == 1:
print(f"x{i} =",x[i].value()) # 最適解（変数の値が1のものだけ）を表示
print("最適値 :", prob.objective.value()) # 最適値を表示
26～31行目で計算結果を表示しています。
27行目で解の状態を表示しています。Optimalと表示されたら最適解が得られています。
28～30行目で最適解を表示しています。for文で全ての荷物のインデックスを取得して、変数の値が1のものだけ表示するようにしています。
31行目で最適値を表示しています。
結果の解釈
1行目は無視して大丈夫です。（pulpがちゃんとインストールされていることを示しています。）
2行目でOptimalと返されているのでちゃんと最適解が得られていることが分かります。
3～15行目は最適解を表しています。pythonはデフォルトだと0から数字が始まるので、x0=1.0は荷物1をトラックに積むことを表しています。
16行目は最適値が表示されています。最適値が3なので各グループ最低でも3つの荷物は積めることが分かりました。
グループ間の偏りが無くなった
ということでこっちの定式化だとグループ間の偏りがだいぶ無くなっていることが分かります。
荷物の個数をもっと大きくして計算してみる
それでは最後に荷物の個数をもっと大きくしたときに2つの定式化で解がどう変わるのかを確かめてみましょう。
パラメータ：
\(I\) : 荷物の集合
\(w_i\) : 荷物\(i\)の重さ
\(K\) : トラックの重量制限
変数：
\(x_i \in \{0,1\}\)
定式化1 :
\(\max \;\;\; \sum\limits_{i \in I}x_i\)
\(\;\text{s.t.}\;\;\;\sum\limits_{i \in I} w_ix_i \leq K\)
\(\;\;\;\;\;\;\;\;\; x_{ij} \in \{0,1\} \;\;( \forall i \in I)\)
パラメータ：
\(G\) : グループの集合
\(I\) : 荷物の集合
\(I_g\) : グループ\(g\)に属す荷物の集合
\(w_i\) : 荷物\(i\)の重さ
\(K\) : トラックの重量制限
変数：
\(x_i \in \{0,1\}\)
\(t\)
定式化2 :
\(\max \;\;\; t\)
\(\;\text{s.t.}\;\;\;\sum\limits_{i \in I_g} x_i \geq t \;\;( \forall g \in G)\)
\(\;\;\;\;\;\;\;\;\; \sum\limits_{i \in I} w_ix_i \leq K\)
\(\;\;\;\;\;\;\;\;\; x_{ij} \in \{0,1\} \;\;( \forall i \in I)\)
荷物の個数が200個、グループ数が20個、各グループ内の荷物は10個、各荷物の重さは1kg以上100kg以下、トラックの重量制限は5000kgとします。
\((|I| = 200, |G| = 20, \forall g \in G, |I_g| = 10, \forall i \in I, w_i \in [1,100], K = 5000)\)
以下が計算結果です。
定式化1ではグループ間の偏りが大きいのに対して定式化2ではグループ間の偏りが抑えられていますね。ちなみに定式化1の最適値は135で定式化2の最適値は128でした。
おわりに
いかがでしたか。
今回の記事では数学が世の中で使える例について解説していきました。
今後もこのような数理最適化に関する記事を書いていきます！
最後までこの記事を読んでくれてありがとうございました。
