線形計画法 (Linear Programming) とは、制約式 (制約条件) であるいくつかの一次不等式を満たす領域において、一次関数で表される目的関数を最大化または最小化する変数の値を求める方法である。線形計画法の対象となる最適化問題を線形計画問題と呼び、この問題の解決法の一つとして、シンプレックス法 (単体法) が存在する。
例えば、ある店Aでは、チキンカレーと親子丼のみがメニューとして存在する。この2つのメニューのみで売り上げを最大にすることを考える。 (実際にそんな店は存在しないのだが…)
現在、前提として冷蔵庫の中には
・鶏肉50gのカタマリ:10個
・玉ねぎ50gのカタマリ:8個
があり、これら2つの具材以外の在庫は、考えなくても大丈夫なくらい十分に存在すると仮定する。
この2つの料理には、それぞれ以下のような材料及びそれらの量を使用する。
鶏肉50gのカタマリ | 玉ねぎ50gのカタマリ | |
カレー | 1個 | 2個 |
親子丼 | 2個 | 1個 |
各メニューの価格は、下記のようにした。
カレー | 親子丼 | |
価格 | 500円 | 750円 |
このとき、カレーと親子丼を何食ずつ売れば、総売り上げを最大化できるだろうか?
x1をカレーの販売数、x2を親子丼の販売数とすれば、目的関数と制約条件はそれぞれ、次のように表される。
【目的関数】500×1+750×2 (総売り上げ)
【制約条件】x1+2×2≦10 (鶏肉の在庫)
2×1+x2≦8 (玉ねぎの在庫)
x1≧0, x2≧0 (材料の個数は非負)
コメントする