非線形の最適化問題をExcel VBAを使って解く方法を具体例で実演！
非線形の最適化問題の事例
ある物流センターでは、物流加工で4つの工程があります。
各工程1人ずつで受け持ち、毎日合計4人必要です。
今まで延べ7人がこの作業を行ったことがあり、各人の作業生産性（個／時間）と時給は次の通りです。
センター長は、そろそろスタッフを固定したいと思っています。
全体の生産性は一番生産性の悪い工程（ボトルネック）で決まります。
この時、全体の生産性を70以上にしながら、総時給が7,000円以内に抑えられるようにするには、どの工程に誰を割り当てたら良いでしょうか？
この問題は最適化問題の一種です。
Excelには分析ツールが付いていて、ある程度の最適化問題は解くことができます。
しかし、線形問題（条件式や目的関数が一次式で表される問題）しか解くことができません。
この問題は非線形問題のため、分析ツールを使うことができません。
（全体の生産性が一番生産性の悪い工程で決まるため一次式で表せない。Min関数を使うことになるため）
ではどうするかと言うと、すべての組み合わせを虱潰しに見ていき、条件を満たすかどうかを判断します。
今回はこれをExcel VBAを使って解いてみます。
順列が840通りもあり人海戦術で解くのは難しい
例えば、工程Aを鈴木さん、工程Bを高橋さん、工程Cを渡辺さん、工程Dを田中さんに割り当てる場合を考えてみましょう。
工程Bの生産性が70で一番低いため、全体の生産性は工程Bに制約されて70になります。
一方、4人の総時給は2,000＋2,090＋1,800＋1,940＝7,830円となります。
従って、この順列では生産性は70をクリアしますが、総時給は7,000円を上回ってクリアしません。
すべての順列は7×6×5×4＝840通りありますので、これらすべてについて生産性と総時給を計算するとなると、人手ではとんでもない時間がかかってしまいます。
>> 【順列と組み合わせを学びなおす！】具体例を使ってわかりやすく解説します。
Excel VBAで非線形最適化問題を解く
「配列」に変数を読み込む
こんな時に力を発揮するのがExcel VBAです。
7個の中から4個を選ぶ順列をExcel VBAで列挙する方法については、前回の記事で解説しました。
重複のある順列／重複のない順列／組み合わせを列挙するアルゴリズムをExcelで
今回はこのVBAに少しプログラムを追加して、この問題を解いてみます。
まず、先ほどの生産性や人件費の表の数値を変数としてマクロに読み込みます。
すべての数字に変数を割り当てようとすると、35個も変数を定義しないといけなくて面倒です。
そこで、配列という考え方を使います。
普通は一つの変数は一つの数字しか取れないのですが、配列で変数を定義すると複数の数字を入れられます。
そこで、次のように5つの変数を配列で定義します。
このようにすると、PA(1)には31を、PA(2)には74、、、を入れられるようになります。
では、この表の35個の数字を5つの変数に読み込むプログラムを書いてみましょう。
次のようになります。
For I = 1 To 7
PA(I) = Range(Cells(I + 3, 3), Cells(I + 3, 3))
PB(I) = Range(Cells(I + 3, 4), Cells(I + 3, 4))
PC(I) = Range(Cells(I + 3, 5), Cells(I + 3, 5))
PD(I) = Range(Cells(I + 3, 6), Cells(I + 3, 6))
Cost(I) = Range(Cells(I + 3, 7), Cells(I + 3, 7))
Next I
たったこれだけで、35個の数字を5つの変数に読み込めます。
条件を満たす順列を探す
前回の記事で、7個から4個を選ぶすべての順列を変数a1～a4に書き出しました。
（a1～a4の組み合わせは840通り）
これは、a1～a4を工程A～Dと読み替えると、どの工程に7人のうちの誰を割り当てるかということと同じです。
例えば、a1=1、a2＝2、a3=3、a4＝4の順列だと、工程Aに佐藤さん、工程Bに鈴木さん、工程Cに高橋さん、工程Dに田中さんを割り当てることに相当します。
この場合、
PA(a1)は佐藤さんの工程Aの生産性＝31
PB(a2)は鈴木さんの工程Bの生産性＝70
PC(a3)は高橋さんの工程Cの生産性＝75
PD(a4)は田中さんの工程Dの生産性＝76
Cost(a1)は佐藤さんの時給＝1,300
Cost(a2)は鈴木さんの時給＝2,000
Cost(a3)は高橋さんの時給＝2,090
Cost(a4)は田中さんの時給＝1,800
ですので、
全体の生産性＝31（31、70、75、76の中で一番低い値）
総時給＝7,190
ということが計算できます。
マクロで書くと次のようになります。
If SS = 0 Then
CBN = a1 & a2 & a3 & a4
P = WorksheetFunction.Min(PA(a1), PB(a2), PC(a3), PD(a4))
C = WorksheetFunction.Sum(Cost(a1), Cost(a2), Cost(a3), Cost(a4))
If P > 70 And C < 7500 Then
XX = XX + 1
Range(Cells(XX + 1, 1), Cells(XX + 1, 1)) = CBN
Range(Cells(XX + 1, 2), Cells(XX + 1, 2)) = P
Range(Cells(XX + 1, 3), Cells(XX + 1, 3)) = C
Else
End If
End If
赤字の箇所で4人の生産性の最小値を、青字の箇所で4人の総時給を計算しています。
そして、緑字の箇所で全体の生産性が70以上、かつ総時給が7,000円以下のパターンだけを選んでいます。
選ばれた順列だけが、シートに順に書き込まれます。
このマクロを実行すると、次のように条件にマッチする8つの順列がシートに書き込まれます。
840通りの順列の中で、条件にマッチするのは8つだけでした。
中でも一番コスパが良さそうなのは、下から2番目の順列、工程Aが渡辺さん、工程Bが田中さん、工程Cが山本さん、工程Dが佐藤さんの時で、その時の総時給は6,690円になります。
これを人手で計算するとなると気の遠くなる作業で、普通の人は諦めるでしょう。
でも、Excel VBAを使いこなせれば不可能が可能になるのです。
まとめ
実はこの計算、Excel VBAでやらせても10分くらい時間がかかります。
もっと計算負荷が低いやり方で、うまくプログラムを組んだとしても5分以上はかかると思います。
このようなのを組み合わせ最適化問題と言いますが、nが大きくなると爆発的に計算負荷が増えます。
この例だと7個の中から4個を選ぶ順列ですが、10個の中から7個を選ぶ順列になると、実に4,000倍くらいの時間がかかります。
今後、量子コンピュータでブレークスルーが期待されている分野です。
でも、Excel VBAでやっても、人手でやるとまず不可能なことが可能なレベルにはなります。
管理人は10時間くらいかかるプログラムを走らせて、組み合わせ最適化問題を解いたことがありました。
その時は、誰も考えていなかった意外な組み合わせが最もコスト安となることが分かって、皆に驚かれました。
意外と、あなたの身の周りにもそのような未解決問題があるかもしれませんよ。