「分かりそう」で「分からない」でも「分かった」気になれるIT用語辞典

別にIT用語というわけでも ないですけどね。
某・資格試験の過去問に「線形計画法」という形で出てきたので取り上げておきます。

順番に見ていきましょう。
まずは予備知識として「一次式」について簡単に説明します。
「そんなの説明されなくても知ってるよ！」な人は適当に読み飛ばしてください。

一次式は「グラフを描くと直線になるような式」です。
例えば

Y=aX+b

みたいなのが一次式です。
横軸にXを、縦軸にYをとってグラフを描くと、斜めの直線になりますよね。



以上を踏まえて

一次式で表現されるいくつかの条件（制約条件）を踏まえて、一次式で表現される「求めたいもの（目的関数）」が最大（最小）になるように頑張ることで、最適な値の組み合わせを探すやり方

が「リニアプログラミング」です。
日本語では「線形計画法」と表現されます。



……と言われてもピンと来ませんよね。

大丈夫です。
例を挙げて説明します。

例えば、そうですね。

ピヨ太君が1kg（1,000g）の小麦粉を買ってきました。
これでケーキを作ります。



苺ショートを1個作るには小麦粉が100g必要です。



ブッシュ・ド・ノエルを1個作るには小麦粉が50g必要です。



ここで問題です。
1kg（1,000g）の小麦粉を使ってケーキは全部で何個作れるでしょうか？



せっかくなので、数学っぽく考えてみましょう。

作れる苺ショートの数を「X」とします。



作れるブッシュ・ド・ノエルの数は「Y」です。



作れるケーキの数は

X＋Y

で表現できます。



ここで、先ほどの小麦粉の話を思い出してください。
苺ショートを1個作るには小麦粉が100g必要です。
ブッシュ・ド・ノエルを1個作るには小麦粉が50g必要です。
ピヨ太君が買ってきた小麦粉は1kg（1,000g）でした。

ということは

1,000≧100X＋50Y

の条件を満たす必要があります。
1個作るのに小麦粉が100g必要な苺ショートをX個作って、1個作るのに小麦粉が50g必要なブッシュ・ド・ノエルをY個作るとして、使える小麦粉は全部で1kg（1,000g）までだからです。



あと、XとYは個数です。
個数はマイナスには、なりませんよね。
最小でも「0」です。
よって

X≧0
Y≧0

の条件も満たす必要があります。

ここまでをまとめると

■求めたいもの
【作れるケーキの数】＝X＋Y

■条件
1,000≧100X＋50Y
X≧0
Y≧0

となります。



なお「求めたいもの」で登場するXとYは

■条件
1,000≧100X＋50Y
X≧0
Y≧0

を満たす必要があります。
そのため、XとYの組み合わせは、以下のグラフの色塗り部分のどこかになります。
色塗り部分から外れたところは、条件を満たさないからです。



おっと、大変です。
ピヨ子さんが突然やってきて言いました。
「できるだけ、たくさんケーキが食べたいわ」と。



ピヨ子さんの言うことはー、ぜったーい！
ピヨ太君は

■求めたいもの
【作れるケーキの数】＝X＋Y

■条件
1,000≧100X＋50Y
X≧0
Y≧0

において【作れるケーキの数】が最大になるXとYの組み合わせを探すことになりました。

取り得るXとYの値の組み合わせは、先ほどのグラフの色塗り部分のどこかですからね。
ピヨ太君は一生懸命グラフを眺めます。



この話における「求めたいもの」は一次式です。
「条件」も、すべて一次式です。
ピヨ太君は「条件」を踏まえて「求めたいもの」が最大になる「X」と「Y」の組み合わせを探しました。

このような

一次式で表現される条件がいくつかある状態で、一次式で表現される「求めたいもの」が最大（最小）になるように頑張ることで、最適な値の組み合わせを探すやり方

がリニアプログラミングです。

なお、リニアプログラミングの話で出てくる「求めたいもの」を「目的関数」と言います。
「条件」は「制約条件」と言います。

■目的関数
【作れるケーキの数】＝X＋Y

■制約条件
1,000≧100X＋50Y
X≧0
Y≧0

気が向いたら、併せて覚えてあげてください。