線形計画問題

与えられた線形な等式および不等式制約のもとで, 線形目的関数を最大化あるいは最小化する問題

工場において一定の原料やエネルギー消費量の制約 のもとで利益を最大化するための生産計画を立てる問題などが挙げられる。 実用的な線形計画問題では, 変数および制約条件の数は極めて大きくなる。

シンプレックス法と内点法の２つの解法がよく知られている

高校数学でやった記憶がある問題

例:

パソコンショップの店主であるAさんは, ある顧客から「PC/AT互換機のシス テムを組んで欲しい」という依頼を受けた。顧客の要望はメモリ100MB以上, ディスク 5GB 以上, 予算はディスクとメモリを合わせて 10万円以下, 予算の範囲でメモリもディスクも可能な限りたくさん載せたいというものであった。

話を簡単にするため, (非現実的な仮定だが)メモリおよびディスクの大きさは 任意の正の実数値を取るものとする。メモリの価格は1MBあたり100円, ディス クの価格は1GBあたり2,500円とする。また, 顧客の依頼したパソコンは, メ モリは最大800MBまで,ディスクは無限に増設できるものとする。Aさんの店で は, メモリは1MBあたり10円, ディスクは1GBあたり200円の利益があるものとする。 Aさんとしては, 顧客の予算を目一杯使って, なるべく多くの利益をあげたい。 さて, どのような意思決定をするのが良いだろうか?

https://gyazo.com/6b8c4ae07b0143aef33c91261b256f54

参考文献