Re:ゼロから学ぶ最適化計算 with Python(前編）～最適化問題の難しさ～
この記事の概要
プログラムを使って、最適化問題（数理計画問題とも言う）を解く
その前段階というか、どうしてプログラミング言語を使うのかという話。
勉強意識の高い高校生から卒業研究のネタに困ってる大学3年生まで
幅広く有益な情報になってると思うのでよかったら読んでほしい。
注・
ゲームの話とか一切ない、ちょっと真面目な記事です。
あと、あくまで学生のメモ書きなので知識や専門用語など
おかしい部分があってもご容赦願いたい。
最適化問題（数理計画問題）って何？
簡単に言うと
- 最大化（最小化）する目的関数がある
- 目的関数を構成する変数（決定変数）がある
- 等式及び不等式で示された決定変数の制約条件がある
問題の総称である。
（すげーざっくり言ってるので厳密には違うかも）
具体例として、以下の例題を見てみよう
例題1の場合
決定変数：2個（x,y)
目的関数：4x+5y
制約条件：4個（上の不等式）
になる。
高校数学の範囲なのでご存知の方も多いと思うが、
下図のように領域を書いて
直線：k=f(x) ⇔ y＝-4/5 x+k/5 が領域内を通過する
kの最大値を求めるのが一般的な解法である。
求める最大値は(x,y)=(2,1)のときk=13となる。
（参考：領域における最大・最小問題（線形計画法） | 高校数学の美しい物語）
最適化問題の難しさ
例題1のように、決定変数及び制約条件が2個程度なら
簡単な手計算で求めることが可能だ。
では、次のような例題2はどうだろうか
例題2
あなたの鎮守府もとい軍隊の資材庫には
燃料10000弾薬10000鉄鋼10000ボーキサイト10000があります。
あなたは資材を使って以下の4種類の軍事ユニットを作ることができます
戦車：燃料50弾薬40鉄鋼50ボーキ10
自走砲：燃料10弾薬15鉄鋼10ボーキ0
戦艦：燃料400弾薬500鉄鋼600ボーキ300
戦闘機：燃料30弾薬30鉄鋼10ボーキ60戦闘力は戦車：自走砲：戦艦：戦闘機＝8：2：100：15
兵士は全部で1000人、戦車5（人/台）自走砲3(人/台)戦艦40(人/台)戦闘機1(人/台)の人手が必要です
さて、どれを何機作るのが一番戦闘力が高くなるでしょうか?
この問題を数式に直すとこうなる
決定変数が4個に増えたので、例題1での解法は使えなくなってしまった。
やるには4次元の図が必要である。3次元世界の我々には手が届かない。
まあ、これくらいなら他の方法で解ける気がするけど。
（そもそも問題設定とか数値が適当だしね）
このように、
決定変数の数が増えたり
（あるいはバイナリ値のような離散変数など面倒な変数が入ってたり）
目的関数や制約条件が複雑になってくると
段々と最適化問題を数学的に解くことは難しくなる。
ちなみに筆者が去年くらいまでやってた
年間シミュレーションでの内部計算はこんな感じだった
例題３
（個人情報保護のため変数の名前はわざと適当にしてある）
例題2までの書き方で式を全部書こうとしたら大変なことになる。
こうなってしまうと手計算ではできないので
コンピューターに計算をやってもらうことになる。
コンピューターの問題の解き方とソルバー
最適化問題では、一発で解が求まらない複雑な問題に対して
「今いる位置の近くでよさそうな方向にちょっと進む。これを繰り返す」
という作業を反復して、理論上の最適値に限りなく近くなる近似解を求める。
こういった決まった作業の繰り返しはコンピューターの十八番である。
気になる人は最急降下法やニュートンラプソン法などで調べてみてほしい。
以下の記事でも非常にわかりやすくまとめられている。
ここまで書いといて恐縮だが…
筆者がここで伝えたいのは、こういった仕組みや理論を理解する必要は
ない
ということだ。
素晴らしいことに、PythonやMATLAB等のプログラミング言語には
「ソルバー」という便利なツールが存在する。
これは上述のめんどくさい理論をブラックボックス化してくれるものだ。
我々は下図のようにこの黒い箱に決定変数などの入力データを入れるだけ。
あとは数行のコードで目的の最適解が得られる。ありがてえ。
これの凄い所は、試算の際の入力データの量に
（常識的な範囲なら）制限が無いこと
例題3のような問題だって繰り返し構文でまとめて書いて
ブラックボックスに投げ入れるだけ。らくちんだね。v(￣Д￣)v ｲｴｲ
まとめと次回予告
Python等を使えば、難しそうに見える最適化問題も割とあっさり解けちゃうよ。
という話
後編と併せて読んでもらうと分かるのだが、そこまで難しいことはしていない。
高校2年生くらいでも十分理解・習得できる知識と技術である。
ただ侮ることなかれ、「数理モデルの最適解を求める」という技術は
研究という行為において中々に便利で汎用性が高い。
具体的には、いい感じの題材を見つけられさえすれば、
現実の問題を数式に置き換えてこれを応用するだけで
適当な卒論くらいなら1本書けてしまう。（筆者は書いた）
（それどころか修論すらもこれで書こうとしている）
長くなってしまったが、
以上が実際にPythonのソースコードを書くまでの前段階のお話である。
後編でいよいよ具体的なサンプルプログラムを書くのでお楽しみに。
