数理計画法
数理計画問題とは
与えられた制約条件の中で,ある一つの目的関数を最大(最小)にする最適化問題
目的関数と制約条件が線形関数か……
yes なら線形計画問題
変数の一部に整数制約があれば整数計画問題という
no なら 非線形計画問題
線形計画問題を解く方法として単体法がある.
ダンツィック(1947)
線形計画問題の例
(生産計画問題) A 社では,3 種類の原料 (原料1,2,3) を使って,2 種類の
製品 (製品1,2) を生産している.製品1を 1 トン生産するには,表 1 にあるように原
料1,2,3がそれぞれ 1 トン,4 トン,3 トン必要であり,製品2を 1 トン生産するに
は,原料1,2,3がそれぞれ 2 トン,4 トン,1 トン必要である.1 日の原料1,2,3
の使用可能量は,それぞれ 80 トン,180 トン,90 トンである.また,製品1,2を生産
したときの 1 トンあたりの利益はそれぞれ 5 万円,4 万円である.1 日あたりの利益を最
大にするには,製品1,2をそれぞれ何トンずつ生産すればよいか.
製品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