[PR]当サイトはアフィリエイト広告を利用しています。
エクセルソルバーと聞いて「難しい」と感じたことはありませんか？
エクセルのソルバーは目的を設定すれば条件に合うパラメーターを求めてくれる便利な機能です。
しかしその基礎となっているのはOR（オペレーションズ・リサーチ）という分野の数理最適化理論です。
少し勉強した方なら線形計画法という名前を聞いたことがあるかもしれません。これも数理最適化の一分野です。
一般に数理最適化理論をまともに理解するのは非常に大変です。
そうは言ってもソルバーの基礎だけ学んで、とりあえず使えるようになりたい、という需要もあるかと思います。
今回は数理最適化の導入的な話題から、ソルバーの実際の使い方まで網羅的に解説していきます。
ソルバーはなぜ難しいのかという疑問が解消し、ソルバーのなんとなくの全体像が描けるようになりましたら幸いです。
そもそも数理最適化を理解するのに必要となる学力レベル
私はOR系の大学の研究室に所属していたので、基礎を学ぶのにどの程度の学力が必要かというのがある程度わかります。
簡単に言うと、数理最適化理論の全体像のイメージをそれなりに描けて、適切にソルバーに反映できるくらいになるには、理系大学院の修士レベルが必要です。
目的関数、制約条件、変数。基本はこの3つを理解すればよいのですが、これのパターンが膨大で、与えられた目の前の現象から、何が目的関数なのか、という数式やアルゴリズムを見つけるのがまず大きな壁です。熟練の研究者でも正直難しい作業です。
これをエクセルのセルの動きを適切に把握し、数式なり、アルゴリズムなりに表現するというのがまともにできるためには、大学院で専門教育を受けたくらいの技量を要します。
一般的な解説ではいきなりなんらかの例題（在庫管理とか線形計画法など）があって、ソルバーを設定する方法がいきなり始まります。
ここでよくわからないのは当然なのです。数理最適化の基礎がわかっていないと、どういう枠組みからソルバーを設定しているのか理解できないので、やり方はわかったけど何をやっているかわからないという状態になります。
数理最適化とは
数理最適化の全体像を完全に把握するには相当の時間と努力を要しますが、ソルバーを設定するために最低限の知識を知っているというレベルなら、ある程度到達できる可能性があります。
今回は基礎の基礎を解説します。
数理最適化の定義
まず数理最適化というのは何なのかというのを一言で言うと
与えられた制約を満たしつつ、目的に合致する、変数の解を求めること
となります。
先ほどの記述で目的関数、制約条件、変数、基本はこの3つを理解すればよいと述べました。これらを言葉で並べると上のような定義となります。また得られた解を最適解と言います。
何かのプロジェクトで発生した検討課題から「これがベストだ」となったときに「これが最適解だ」と言うことがありますよね。その最適解というのは数理最適化の最適解が由来だと思われます。
ただし抽象的な言葉でその概念が捉えらないというのは、物事の基本です。抽象概念は具体的な事例を知り、それを抽象の概念に当てはめてみて理解を蓄積してようやくわかるようになっていきます。上の定義だけではピンとこないでしょう。
ところで上で熟練の研究者でも最適化の問題設定は難しいと述べました。しかしこれは世の中に最適化問題がほとんどないという意味ではありません。
むしろ意思決定する場面にはかなりの頻度で現れます。
例えば、朝コーヒーを飲むかどうかという問題を最適化問題で表してみると
- 目的関数：ホットコーヒーを飲むかどうかという人間の感覚。出力は飲むか飲まないか
- 制約条件：気温は0度から40度
- 変数：気温
多少強引ですが、このように表すこともできます。上のような問題は機械学習の基本的な手法で解決する場合が多いですが、人間の感覚を100%シミュレーションできるようなAIが開発され、超高速計算ができる量子コンピューターやそれに準ずる新たなテクノロジーが一般化されれば数理最適化で厳密解を求めるという段階が見えてくるでしょう。
他にはスケジュールや工程表を決める時にも表れますし、数式を解くときも数理最適化が現れます。
難しいのは問題設定と数式化やアルゴリズムの構築なのです。
目的関数・制約条件・変数
具体的な例題で数理最適化の重要概念である、目的関数・制約条件・変数を考えてみましょう。
中学校で連立方程式を解きますよね。解の公式を使って求解するはずです。これも立派な数理最適化問題です。
どういうことなのか最適化問題として表してみましょう。
\[y=x^{2}+2x+1\]
という関数があったとします。\(x=-1\)が\(y=0\)となるときの\(x\)の値ですね。
これを数理最適化問題として記述すると次のようになります。
- 目的関数：\(y=x^{2}+2x+1\)→最小化
- 制約条件：\(-10 \leq x \leq 10\)
- 変数：\(x\)
制約条件は適当に問題の範囲に解が入るように決めました。普通は解がどの範囲に入っているかは未知である場合が多いので、解の公式だけで二次関数の問題すべてが解けるとは限りません。
解の範囲として制約条件を定めたのには理由があります。基本的に数理最適化の手法では有限範囲の中での最適解を求める手法も存在し、解の範囲を無限に広げると求解が難しくなる場合があるからです。もちろん無限範囲でも限定的な目的関数なら求解できる手法も存在します。
何らかの手法で求解すると\(x=-1\)が求まります。
基本的に数理最適化では目的関数を最小化（最大化）する変数の値（最適解）を求めることになります。
上でyの二次関数の最小化の最適解が\(y=0\)のときの\(x\)の値にちょうどよくなりました。
これはyの関数が\(y=(x+1)^{2}\)と書けるので、たまたま\((x+1)^{2}\geq 0\)と表せるからです。
最適化手法と最適化問題の分類
上で制約条件と変数がありました。数理最適化では制約条件の範囲で変数の値を何らかの手法で移動しながら探索します。目的関数を数値微分して微分係数の情報で変数を移動しながら最適解に向かっていくこともありますし、ランダム的に発生させた解の候補を特定の手順にしたがって更新することで最適解を得る手法もあります。
こうした探索手法を最適化手法と呼びます。線型計画法なども最適化手法の一つです。
ランダム的に探索する手法で有名なのが遺伝的アルゴリズム（GA）です。GAの概要は次の記事で解説しています。
なぜたくさんの手法が存在するのでしょうか？
それはそれぞれの最適化手法で解ける問題が違うからです。
最適化問題の種類
詳細は後述します。
簡単な分類では最適化問題は次の2つに分けられます。
- 連続変数問題
- 離散変数問題
また次のようにも分類できます。
- 線形最適化問題
- 非線形最適化問題
さらに次のようにも分類できます。
- 関数がなめらか
- 関数がなめらかでない
上の6つはそれぞれ独立しているわけではありません。離散変数の線形最適化問題もありますし、連続変数の線形最適化問題や、連続変数の非線形最適化問題もあります。さらにはある区間では変数が連続で違う区間では変数が離散変数という線形問題も非線形問題も存在します。そしてそれぞれに目的関数がなめらかかどうかという条件も付きます。
その他にも最適化問題のバリエーションは存在しますが、まず上の6つを押さえましょう。とはいえまだそれぞれの分類の中身を解説していないので、上の6つの分類をこれより解説していきます。
また上の分類でわかるように最適化問題は非常にややこしいです。
連続変数の線形最適化問題を解くだけでも線型計画法という手法の理解が必要で、大学院の専門課程で1年解説してできるようになるかどうか、という世界です。基本情報技術者試験レベルの問題なら、手計算でも求まりますが、まともに「変数が多数の最適化問題を汎用的に解く」ことを考えると上のような大学院レベルの話になってきます。
限定的な分類でようやくその範囲内でなら最適解が求まるという世界なのです。とはいえ分類の大枠がわかっていれば、あとは専門家が作ってくれたソルバーを使えばいいだけです。原理を理解するなら何十年もかかってしまいますが、分類さえわかっていればソルバーは使えます。まずはそこを目指しましょう。
連続変数と離散変数
連続変数というのは、変数が連続していてある範囲なら自由に動き回って良い変数の制約条件が存在する状態をいいます。
たとえば\[0 \leq x \leq 5\]なら0から5の範囲で最適化手法は自由に動き回ってよいし、基本的に微分もできます。
ところが\[0 \leq x \leq 5\]かつ
「変数は整数」
という制約がつくと、変数は0, 1, 2, 3, 4, 5のいずれかしか移動できません。連続変数ではないということです。
一般的に連続変数より離散変数のほうが解を求める難度は高いです。これは連続変数の最適化問題を解く手法は連続変数の空間から小数を含めた最適解を出力するので、離散変数の条件が付いたとき、小数の解の近くのどの離散値を選ぶのか、そもそも近くの離散値を選んでよいのかという問題にはっきりとした決め手がないからです。
線形最適化問題と非線形最適化問題【線形最適化問題編】
次の分類は線形か非線形かというものです。
線形というのは、変数が1次ということです。例えば\(3x\)は線形です。\(3x^{2}\)は2次なので非線形です。
\(4x_{1}+6x_{2}\)は線形ですが、\(4x_{1}+6x_{2}^{2}\)は非線形です。
要するに変数の1乗なら線形です。
線形計画問題（線形最適化問題）というのは、線形の不等式か等式を満たす（つまり線形の制約条件）変数の組で線形の目的関数を最小化あるいは最大化する問題です。例えば次のような問題です。
- 目的関数：\(y=200x_{1}+320x_{2}\)→最大化
- 制約条件1：\(80x_{1}+130x_{2}\leq 7800\)
- 制約条件2：\(6x_{1}+4x_{2}\leq 350\)
- 制約条件3：\(x_{1}, x_{2}\geq 0\)
目的関数、制約条件ともに変数\(x_{1}, x_{2}\)の一次式となっています。
こういう問題なら線形計画法（LP：Linear Programming）で求解できます。ソルバーのモードで言うと「シンプレックスLP」を使うことになります。
線形最適化問題と非線形最適化問題【非線形最適化問題編】
続いては非線形最適化問題です。非線形とは線形でない、ということです。例えば上で二次関数を最小化する問題を書きました。それを再掲すると次のようになります。
- 目的関数：\(y=x^{2}+2x+1\)→最小化
- 制約条件：\(-10 \leq x \leq 10\)
- 変数：\(x\)
変数は一つだけ、しかも制約条件も線形ですが、目的関数が線形ではないので非線形最適化問題となります。
このように中学校の問題でさえ非線形になってしまいます。世の中の最適化問題は線形ばかりではないので、線形ではない非線形の最適化問題を判別できるようになっておきましょう。考慮すべき視点は「線形でない」なら「非線形」だということです。
また制約条件が二次式の次のような問題も存在します。
\[x^{2}+4x+4 \leq 0\]
こういう制約条件が付くと、目的関数が線形でも、制約条件が線形ではないので非線形最適化問題になります。
目的関数がなめらかか、なめらかでないか
最後の分類が目的関数が「なめらか」か「なめらかでない」かです。
なめらかというのは何回偏微分しても連続な偏導関数が得られることをいいます。直感的には次のようなイラストで説明できます。まずはなめらかな関数。
\(y=x+2\cos x\)
続いてなめらかでない関数。
どこかに非連続な点があるとなめらかでなくなります。
例えばx=1を境に勾配がいきなり変わるとか、関数値がx=1の左側では3、右側では7に飛ぶなどの場合です。
なめらかでないと導関数が得られないので微分できなくなり、微分を利用した最適化手法は計算不能となります。
逆に言うと関数がなめらかな離散変数なら、目的関数を連続変数として扱って微分を利用して、その解の近くの離散値を最適解に採用するということができる場合もありますが、連続変数と考えて最適化した結果から離散変数のどれを最適解にするかという選択が容易ではないのです。
関数がなめらかかどうかというのは、簡単に言うと、関数が滑らかにつながっているということです。関数がある変数の値を境に非連続に変化するとき関数はなめらかではないとされます。
最適化手法と解決できる最適化問題の関係
最適化手法によって解決できる最適化問題が限定されます。ここからはエクセルソルバーのどの最適化手法がどの最適化問題を解決できるのかという内容を扱います。
線形最適化問題ならシンプレックスLP
線形最適化問題なら線形計画法が最も適した解法です。エクセルソルバーではシンプレックスLPが線形計画法に相当します。
シンプレックスLPなら離散変数でも連続変数でも線形最適化問題なら解決できます。かなり性能が良いです。
上の線形最適化問題を再掲します。
- 目的関数：\(y=200x_{1}+320x_{2}\)→最大化
- 制約条件1：\(80x_{1}+130x_{2}\leq 7800\)
- 制約条件2：\(6x_{1}+4x_{2}\leq 350\)
- 制約条件3：\(x_{1}, x_{2}\geq 0\)
これを実際にエクセルのソルバーで解いてみます。なおソルバーアドインを使えるようにする方法は後述します。
まず次のようにセルに入力します。
ここで各セルの数式は次のようになります。
- C3：0
- D3：0
- E3：=200*C3+320*D3
- F3：=80*C3+130*D3
- G3：=6*C3+4*D3
次に目的セルや変数セル、制約条件などを以下のように入力します。解決方法は「シンプレックスLP」を選択します。複数セルを入力するときは、複数セルをドラッグすると入力できます。
入力したら解決をクリックします。うまくいけば次のような画面が出るので「OK」をクリックします。
解が次のように出力されていれば成功です。
非線形最適化問題で関数がなめらかならGRG非線形
非線形最適化問題で関数がなめらかならGRG非線形が使えます。連続変数はもちろん解けますが、離散変数でも関数がなめらか、つまり微分可能なら解ける場合があります。
GRG非線形に似たような基礎的な手法としてニュートン法があります。当ブログでは過去にニュートン法で三次方程式を解いてみました。
またGRG非線形は「勾配法」の一つなので、同じ勾配法の最急降下法の流れを知ればより理解が深まります。
変数の連続性ですが、例えば上で挙げた制約条件である\(x^{2}+4x+4 \leq 0\)といった制約条件は連続変数かどうかの判定に使いません。あくまで\(x_{1}, x_{2}\geq 0\)といった、変数そのものの範囲が連続かどうか、というのが連続変数かどうかを決定します。
中学校の二次関数の最小化問題を再掲します。
- 目的関数：\(y=x^{2}+2x+1\)→最小化
- 制約条件：\(-10 \leq x \leq 10\)
- 変数：\(x\)
目的関数はなめらかで非線形です。こういうときにGRG非線形を使います。GRG非線形の中身はどうなっているのか、と疑問を持たれるかもしれません。詳細は難しいですが、簡単に言うと初期点から数値的に目的関数を微分してその勾配から探索方向を決定して最適解に到達する方法です。
微分を使うので滑らかな目的関数で利用します。
上の最適化問題をソルバーで解いてみましょう。セルに次のように入力します。
各セルの数式は次の通りです。
- C3：0
- D3：=C3+2*C3+1
次にソルバーの設定ダイアログで以下のように入力します。
解決すると次のようにx=-1が求まります。
エボリューショナリー【線形でも非線形でも連続でも非連続でも解けるが時間がかかる】
非線形最適化問題で目的関数がなめらかでないときは解決方法にエボリューショナリーを選択します。中身は遺伝的アルゴリズムっぽい手法です。
数値微分を使わずに解を探索するので、離散変数でもなめらかでない目的関数でも使えますし、連続変数でも使えます。また線形最適化問題でも非線形最適化問題でも使えます。
とりあえずどの手法を使えばよいか迷うときや、非線形のなめらかでない目的関数のときはエボリューショナリーを使います。上で挙げた例題はすべてエボリューショナリーで解けます。解決方法をエボリューショナリーに変えるだけです。
エボリューショナリーは例えば過去に当ブログで取り扱った作物の輪作問題を解いたときに使用しました。
注意点としては、シンプレックスLPやGRG非線形よりも解が求まるまで時間がかかるという点です。問題が複雑になると数十分かかるときもあり、エボリューショナリー以外の手法で解けそうならなるべくそちらを使ったほうがよいでしょう。
ただし時間が多少かかってもよいならとりあえずエボリューショナリーにしておけば解決できる最適化問題も多いので、結構重宝する手法です。
解決方法のオプションでエボリューショナリーのパラメータを細かく制御できますが、基本的にデフォルトでOKです。
エボリューショナリーで解くときの注意点【微分の利用との関係】
エボリューショナリーの弱点は求解に時間がかかるという点です。問題を見極めて適切な最適化手法を選択するのが大事です。
なぜエボリューショナリーで時間がかかるか、という点ですが、最適解かどうかの判定がエボリューショナリーではできないからです。
遺伝的アルゴリズムの概要がわかるとイメージできるのですが、こうした進化計算では微分を使っていないので、どこで探索を終了すればいいのかという明確な指針がありません。何千回か計算して解が更新されない、くらいしか最適解の判定方法がないのです。
それに比べてGRG非線形は微分係数を探索に利用するので、最適解かどうかの判定指針があります。高校数学の数学Ⅲの知識で言うと、微分係数が0になれば極大値か極小値ですよね。これと似たような判定方法でこうした微分を利用した手法は止まることができます。
シンプレックスLPではシンプレックス表やピボット演算と呼ばれる道具を使って解の候補を移動していきます。これも移動していくうちにそれ以上移動しても意味がないという点の条件が存在して、自分で止まれます。
とはいえこうした微分を利用した手法にも弱点があって、極大値と極小値は関数の底を判定することはできますが、複数の底があるとどこかの底で止まってしまいます。微分係数が0であっても、複数の極値があればその中のすべてのうちで最も小さいか大きい極値が最大値か最小値になります。
微分を利用した手法ではとにかく底なら止まるので、最小値や最大値ではない底で止まることがあるのです。一般にこうした微分を利用した手法がとりあえず止まる解を局所解と言います。
一方ですべての局所解のうち、最大か最小になる解を大域解と呼びます。
エボリューショナリーの利点は局所解で止まりにくいという点です。必ず大域解で止まるかは保証できませんが、大域解にも止まるので、割と大域解が求まります。
もちろんGRG非線形にもこの問題の対処法があって、初期点をランダムにたくさん設定して、それぞれの初期点から探索を始めて、それぞれの初期点で求めた最適解のうち最も小さい・大きい点を出力するオプションも存在します。こうしたオプションを利用することで大域解が確実ではないにしろ求まるという設定にもできます。
なお線形計画法は最適解が得られたらそれが大域解となります。目的関数が線形という点と解の領域が凸という性質によるのですが、ここでは詳細は割愛します。
ソルバーアドインのインストール方法と使い方
ここからはソルバーアドインをインストールしてダイアログを表示するまでを解説します。
まず「ファイル」タブの「オプション」をクリックします。
次に「アドイン」の下の方にある「設定」をクリックします。
そして「ソルバーアドイン」にチェックを入れてOKをクリックして終了です。
ソルバー設定ダイアログの表示方法は、「データ」タブの「ソルバー」をクリックすればよいです。
まとめ【ソルバーを使うなら最適化問題の見極めの経験を積もう】
ソルバーを使えるようになるには、数理最適化とは何なのかという理解と、最適化問題の種類を見極めて、それに適した最適化手法を選択する必要があります。
特に最適化問題の見極めは経験を積むことでわかるようになっていくので、何らかのテキストの問題をソルバーで解いてみるといった練習が必要かもしれません。
最適化問題は地味ですが生産計画などの分野では頻出の問題ですので、ご自身が担当になった場合は上のように最適化問題の種類を見極めて適切な手法を選択しましょう。
問題の種類の見極めが第一歩です
当ブログ（シルルスのコードおきば）ではエクセルソルバー関係の記事を他にも執筆しています。参考になりましたら幸いです。
Office最新版が常に使えます。楽天なら購入するとポイントも
●ソルバーをVBAで繰り返す【初期値を変えて複数解を自動探索】
●エクセルソルバーで複数解を求める方法【初期値を変えるしかないです】
●エクセルソルバーと組み合わせ最適化問題【解法例と基礎知識】
●Support Vector Regressionをエクセルのソルバーで作ってみた
USBメモリ 128GB USB2.0 日本製【翌日配達送料無料】 KIOXIA（旧東芝メモリー）TransMemory U202 キャップ式 ホワイト 海外パッケージ LU202W128GG4
