【入門編】数理最適化とは|例題と事例を交えてわかりやすく解説!
数理最適化とは、現実で起こる問題を数式に当てはめて最小値や最大値を求める手法です。
字面だけでみると理解しづらいかもしれませんが、私たちは日常生活において数理最適化を自然に活用しています。
たとえば、スーパーでもっともコスパの高い買い物ができる組み合わせを計算するのも数理最適化の1種です。
また、引っ越しなどで荷物を運ぶ際、1回の積み込みで出来るだけ多く載せ往復回数を少なくするように考えるのは一般的といえます。
これを数式に当てはめて計算するのが「数理最適化」なのです。
なお、数理最適化では「変数」や「目的関数」「制約条件」などの要素を定め、最大利益や最小損失を得られる条件を考えます。
分かりやすくスーパーでの買い物に当てはめて考えてみましょう。
■前提条件:夕食のおかずを1,000円以内で購入したい
● 変数:おかずの種類や品数 ● 目的関数:おかずの品数や支出の低さ、美味しさ、満足感など ● 制約条件:合計で1,000円以内に納める |
つまり、制約条件(予算1,000円)を守りつつ目的関数の値を最大化(食べられる品数、満足感の高さ)または最小化(最終的な支出の低さ)するために最適な変数(おかずの種類、品数)の数値を求めるのが数理最適化なのです。
この記事の目次
数理最適化は大きく2種類に分けられる
数理最適化は大きく以下の2種類に分けられます。
- 連続最適化
- 離散最適化(組み合わせ最適化)
両者の違いは変数が連続的に動くかどうかにあります。
たとえば、公共交通機関の乗り換えを例に考えた場合、予算や希望到着時刻といった条件を満たしつつ目的地に辿り着くためにバスに乗るか乗らないかを判断します。
乗らない場合はタクシーに乗るか乗らないかを判断するというように、両立しない選択の組み合わせを考えなければなりません。
このように、独立した選択肢の組み合わせを求める変数として捉えるのが離散最適化(組み合わせ最適化)です。
一方、連続最適化の場合は、変数が連続的に動くため選択肢が爆発的に増えます。
たとえば、前述した夕食のおかずの購入を例に考えると予算や空腹度、求める満足感といった条件に沿って、求める変数=おかずの種類や品数が変動します。
なお乗り換えのケースとは異なり、食品Aと食品Bを同時に購入するという選択肢もありえるため、膨大なパターンを検討しなければなりません。
スーパーでの買い物であればイメージしやすいですが、ビジネスや投資の場合は保有する金融商品の比率など複雑かつ連続的に動く変数を求めなければならないため、非常に複雑な数式を解く必要があります。
機械学習・深層学習との違い
数理最適化の類似技術として、機械学習や深層学習が挙げられます。
混同されがちなそれぞれの正確な意味をしっかり捉えておきましょう。
技術名 | 特徴 |
数理最適化 | ・現実で起こる問題を数式に当てはめて最小値や最大値を求める手法 |
機械学習 | ・機械がデータを元に反復学習し、予測や分類などそこに潜む可能性やパターンを発見する技術 |
深層学習
|
・深層学習は機械学習に包括される技術
・特徴値への判断を可能とした機械学習 |
機械学習や深層学習は「物事の意味や当てはまる項目」といった認識や分類「この後どうなるの?」といった予測を求めるための技術です。
一方、数理最適化は「結果的にどうするべきか」といった適切な意思決定を求めます。
つまり、機械学習・深層学習で導き出したデータを、数理最適化によって実用化するといったイメージです。
したがって、3つの技術は非常に関連性が深いのは間違いありませんが、同列ではなく延長線上にある関係といえるでしょう。
数理最適化を正しく理解するための例題
数理最適化を正しく理解するために有名な2つの例題をご紹介します。
複雑かつ抽象的な技術の具体的なイメージを捉えるためにも、ぜひ参考にしてください。
・ナップサック問題
■例題
容量(重量)に制限が設けられた袋と価値の異なる数種類の品物がある。 袋に品物を詰め込む際、もっとも価値が高くなる組み合わせを求めよ。 なお、袋の重量制限は10kg、品物の重量・価値は以下のとおり。 |
A | B | C | D | E | F | |
重量(kg) | 2.8 | 5.2 | 7.4 | 9 | 1.6 | 4.4 |
価値 | 33 | 50 | 89 | 90 | 64 | 88 |
1kgあたりの価値 | 11.7 | 9.6 | 12 | 10 | 40 | 20 |
例題の場合であれば、品物Eを6個詰め込むのが最適解となります。
実際は、目的関数(価値の最大化)や制約条件(制限重量)が複数あったり、Bを詰めたらCも詰めなければならないなどの組み合わせに関するルールが定められていたりと、これほどシンプルではありませんが、基本的な考え方は同じです。
・巡回セールスマン問題
巡回セールスマン問題とは、1人のセールスマンがある都市を出発したのち目的地となる複数の都市を経由し帰ってくる場合、どのルートが最短となるかを求める問題です。
A、B、C、Dの4都市を例に考えてみましょう。なお前提条件は以下の通りです。
- A都市を出発し、すべての都市を経由してA都市に戻る
- 1度訪れた都市を経由して別の都市に向かうのは禁止
A-B間の距離 | 6km |
A-C間の距離 | 5km |
A-D間の距離 | 5km |
B-C間の距離 | 7km |
B-D間の距離 | 4km |
C-D間の距離 | 3km |
例題の場合であれば、都市A→都市B→都市D→都市C→都市Aが合計移動距離18kmで最短ルートとなります。
実際の場合は、移動手段や交通状況・コストなどによって目的関数や制約条件が変わってくるため、さらに複雑になります。
数理最適化のビジネスにおける活用事例
数理最適化の特徴や使い方が掴めてきたところで、現状のビジネスにおける活用事例も確認しておきましょう。
より実用的な活用方法を模索するためにも、ぜひ参考にしてください。
・東京ガス株式会社
「東京ガス株式会社」では、数理最適化を活用した革新的なプログラム「オプトパス®」を開発、運用しています。
なお、オプトパスでは以下のような目的関数を満たす変数を求めるプログラムです。
- 冷暖房や各種エネルギー設備のコスト最小化
- 年間CO2排出量の最小化
- 年間エネルギー消費量の最小化 など
季節・時間帯によるエネルギーコストの変化はもちろん、活用する機器によるエネルギー効率差なども制約条件として組み込まれ毎日毎時、どの機器をどのように運転すれば年間のエネルギーコストを最小化できるかという最適解が求められます。
・ネットロック株式会社
物流3PL事業を展開する「ネットロック株式会社」では、数理最適化を活用した積付け最適化計算システム「バンニングマスター」を開発・運用しています。
バンニングマスターは、コンテナやパレットの空間を余すことなく荷積みする「積付け」という業務を最適化するシステムです。
出来るだけ少ないコンテナでの運搬を目的関数と定め、システムが導き出した解に応じて荷物のサイズや重さを揃えるために生産の順番を変えたり、輸出日をずらしたりといった対応を実施しています。
また、 積み下ろしの際の手間や荷物の重量バランスなどを制約条件と定め、条件の範囲内における最適な積付を実現することで、使用コンテナの削減や積み下ろしに関する人件費削減などの多大なメリットを獲得しています。
まとめ
非常に難しい技術というイメージも強い数理最適化。
しかし、実際は日常生活において幅広く活用されている馴染み深い手法でもあります。
なお、ビジネスにおける利益の最大化やコストの最小化に活用される際には、条件やパターンの複雑さから膨大な数式になってしまいがちです。
そのような複雑な数式を解き、最大限メリットを獲得するために先端IT技術が活用されています。
そうした背景から、数理最適化に対応可能なエンジニアの需要も増加していくことが予想されているため、関連技術の習得を目指してみるのも自身の価値を高める有効な手段といえるでしょう。
この情報は役に立ちましたか?