最適化問題はいくつかの種類があり、それに対する解法が存在します。
はじめに線形計画法が発案され、それを応用して整数計画法と非線形計画法へと発展しました。

線形計画問題	←	線形計画法 （Linear Programming, LP）
整数計画問題	←	整数計画法 （Integer Programming, IP）
非線形計画問題	←	非線形計画法 （Nonlinear Programming, NLP）

今回は“線形計画問題”について紹介します。

“線形計画問題”は一次式や一次不等式で表される制約条件の中で、一次式の目的関数を最大化または最小化する問題です。イメージしやすいように例題をご用意しました。

---

CCC動物園ではコアラを飼育していますが、近頃ぐうたらし過ぎて太ってしまいました。そこで、ダイエットのために糖質制限をかけて餌を与えることにします。主食のユーカリには糖質の他にも食物繊維、ミネラル、毒素が含まれていますが、ミネラル以外のものは取りすぎるとよくないので、こちらも摂取制限をかけます。
成分構成の異なる二つのユーカリをうまく食べ合わせて、なるべく多くのミネラルを摂取するにはどうすればいいでしょうか。

ユーカリ1gあたりの成分表（成分の単位：mg）

---

今回の目的はミネラル摂取量の最大化でした。
ユーカリAの質量をx、ユーカリBの質量をyとすると、

これを最大化することになります。
次に、今回の制約条件を一次不等式で表してみましょう。

これらの条件式から目的関数を求め、グラフ化すると以下の図のようになります。
横線で塗りつぶされた領域が制約条件を満たす範囲（実行可能領域）となり、この中から最も良い解を探索することになります。

最適化問題の中では最も簡単な問題であり、高速に解を得られる解法が存在します。
その中でも代表的なものとして、以下の２つの方法があります。

・単体法	（Simplex Method）
・内点法	（Internal Point Method）

数理最適ソルバでは単体法と内点法を組み合わせて最適解を導出しています。

さて、コアラにはユーカリをそれぞれ何gずつ与えれば良いのでしょうか。
答えは下図の黄色点部分となり、
　　ユーカリA：240g
　　ユーカリB：240g
を与えたときにミネラルの摂取が最大値（216mg）となります。