第1回 数理最適化～入門編～
はじめに
昨今、機械学習やディープラーニングといった技術が広く認知され、様々な場所で利用されるようになりました。
機械学習やディープラーニングの技術を用いれば、画像認識や自然言語処理、異常検知などを行うことができますが、万能なツールではありません。何かを計画したり、意思決定の支援することにおいては、"数理最適化"という技術の方が高精度な結果を得ることができます。
今回から複数回にわたって、"数理最適化"という技術に関して記事にまとめていきます。
数理最適化とは
最適化問題とは、与えられた制約条件のもとで、目的となる値を最大もしくは最小にする変数を求める問題のことです。最適化問題を数理的な手法を用いて解くことを数理最適化と呼びます。
AIと数理最適化の違い
それでは機械学習やディープラーニングやといったAIと数理最適化は何が違うのでしょうか？
AIの特徴としては以下の通りです。
ある商品が何個売れるか？といったような予測に用いられる
画像に写っている物は何か？といったような認識に用いられる
データから規則性を自動的に学習する
一方で数理最適化の特徴としては以下の通りです。
利益を最大にするためにどの商品を何個売れば良いか？といったような計画・意思決定に用いられる
規則性やルールは人間が問題として落とし込む
数理最適化の例
数理最適化の技術はどのようなところで使われているのでしょうか？身近なところでは以下のようなところで用いられています。
アルバイトのシフトスケジューリング
トラックの配送計画
広告やマーケティング施策の予算配分
上記以外にも様々なところで数理最適化は利用されています。日本オペレーションズ・リサーチ学会の「ORを探せ！」のポスターが、暮らしの中のどこに最適化技術が用いられているのか、について分かりやすくなっておりますので、是非こちらも参考にしてみてください。
数理最適化で使用する用語
数理最適化を扱う上で必要な用語について解説します。
ここでは、以下の例を参考に用語を解説します。
ある工場では2つの製品AとBを製造している。各製品を製造するのに必要な原料、各原料の在庫、各製品から得られる利益は以下の通り。利益を最大にするためには、製品AとBを何個ずつ製造すれば良いか？
決定変数
目的を達成するために操作する変数のことを決定変数（desicion variable）と呼びます。上記の例の中では、製品Aと製品Bの生産量$${x_A, x_B}$$が決定変数となります。
制約条件
目的を達成する上で実務上必要となるルールや制約のことを制約条件（constraint）と呼びます。制約条件を与えることにより、決定変数の取り得る値に制限をかけます。上記の例の中では、生産量$${x_A, x_B}$$に対して原料c,d,eが在庫を超えないようにするというものが制約条件となります。数式で表すと以下の通りです。
$$
x_A + 3 x_B \leq 80, \\
2 x_A + 2 x_B \leq 120, \\
4 x_A + x_B \leq 60, \\
x_A, x_B \geq 0
$$
$${x_A, x_B \geq 0}$$は生産量をマイナスにすることを防ぐための制約条件となります。
目的関数
達成したい目的の達成度の指標のことを目的関数（objective function）と呼びます。目的関数は決定変数の関数として表現されます。上記の例の中では、生産量$${x_A, x_B}$$のときの利益が目的関数となります。数式で表すと以下の通りです。
$$
\text{maximize} \hspace{5pt} 5 x_A + 4 x_B
$$
ここまでの目的関数、制約条件についての数式を、最適化問題ではしばしば以下のように表現します。
$$
\begin{array}{lll}
& \text{maximize} & 5 x_A + 4 x_B \\
& \text{subject} \hspace{3pt} \text{to} & x_A + 3 x_B \le 80 \\
& & 2 x_A + 2 x_B \le 120 \\
& & 4 x_A + x_B \le 60 \\
& & x_A, x_B \ge 0
\end{array}
$$
まとめ
本記事では、数理最適化とAIの違いや、数理最適化の例、用語について説明しました。機械学習やディープラーニングなどの技術が注目されておりますが、数理最適化も必要不可欠な技術となっております。
次回以降では、Pythonを用いて実問題をどのようにプログラムに落とし込むのかについて説明する予定です。是非ご覧いただければ幸いです。
この記事が気に入ったらサポートをしてみませんか？