数理計画法
数理計画問題とは
与えられた制約条件の中で，ある一つの目的関数を最大（最小）にする最適化問題
目的関数と制約条件が線形関数か……
yes なら線形計画問題
変数の一部に整数制約があれば整数計画問題という
no なら 非線形計画問題
線形計画問題を解く方法として単体法がある．
ダンツィック(1947)
線形計画問題の例
(生産計画問題) A 社では，3 種類の原料 (原料１，２，３) を使って，2 種類の
製品 (製品１，２) を生産している．製品１を 1 トン生産するには，表 1 にあるように原
料１，２，３がそれぞれ 1 トン，4 トン，3 トン必要であり，製品２を 1 トン生産するに
は，原料１，２，３がそれぞれ 2 トン，4 トン，1 トン必要である．1 日の原料１，２，３
の使用可能量は，それぞれ 80 トン，180 トン，90 トンである．また，製品１，２を生産
したときの 1 トンあたりの利益はそれぞれ 5 万円，4 万円である．1 日あたりの利益を最
大にするには，製品１，２をそれぞれ何トンずつ生産すればよいか．
製品1と製品2の生産量をそれぞれ$ x_1トン，$ x_2トンとすると，利益は
$ 5x_1 + 4x_2
で表される．
使用量の制限より，それぞれ
$ x_1 + 2x_2 \leq 80
$ 4x_1 + 4x_2 \leq 180
$ 3x_1 + x_2 \leq 90
という式が立つ．
また，$ x_1と$ x_2はどちらも生産量なので，負の値を取ることはない
$ x_1 \geq 0,x_2 \geq 0