線形計画法は「頂点」を調べよう！基本情報技術者試験の速い解き方
基本情報技術者試験では、「線形計画法」が出題されることがあります。
教科書では、目的関数の直線を平行移動させながら最適解を求める方法が説明されています。
もちろん、この方法は線形計画法の考え方を理解するにはとても大切です。
しかし、試験で短時間に正解するという目的で考えると、もっとシンプルな解き方があります。
今回は、基本情報技術者試験向けの実践的な解法を紹介します。
過去問
ある工場では、製品Xと製品Yを生産しています。
原料A、原料Bの在庫は限られており、製品1個を作るのに必要な原料は次のとおりです。
| 原料 | 製品X 1個 | 製品Y 1個 | 在庫 |
|---|---|---|---|
| A | 2 | 1 | 100 |
| B | 1 | 2 | 80 |
製品1個当たりの利益は、
- 製品X：100円
- 製品Y：150円
とします。
利益が最大になる生産数を求めなさい。
一見すると難しそうですが、試験では次の4ステップで解くことができます。
教科書の解き方
教科書では、
目的関数
Z＝100X＋150Y
を、
Y＝−（100÷150）×X＋Z÷150
へ変形します。
そして、Zに3000、6000、9000…と値を入れ、何本もの直線を描いて平行移動します。
最後に、
実行可能領域に最後に接する場所
を探します。
これは、
「なぜそこが最大になるのか」
を理解するための方法です。
試験では頂点だけ調べればよい
基本情報技術者試験では、
目的関数を何本も描く必要はありません。
線形計画法では、
最大値・最小値は実行可能領域の頂点で発生する
という性質があります。
つまり、
実行可能領域の頂点だけを調べれば答えが分かります。
覚え方はこれだけです。
グラフを書いたら、頂点へ代入！
試験では4ステップで解こう
① 制約条件を書く
製品XをX個、
製品YをY個作るとすると、
原料Aより
2X＋Y≦100
原料Bより
X＋2Y≦80
さらに、
生産数はマイナスにならないので
X≧0
Y≧0
となります。
② 制約条件をグラフにする
まず、不等式を等号にします。
2X＋Y＝100
この直線を描くには、
X軸との交点
Y軸との交点
を求めます。
Y軸との交点
Y軸上では、
X＝0
です。
式に代入すると、
2×0＋Y＝100したがって、
Y＝100となります。
つまり、
（0，100）
です。
X軸との交点
今度は、
Y＝0
を代入します。
2X＋0＝1002X＝100X＝50となります。
つまり、
（50，0）
です。
したがって、
（0，100）と（50，0）を結ぶ直線
になります。
次に、
X＋2Y＝80
についても同じように求めます。
Y軸との交点
Y軸上では、
X＝0
です。
0＋2Y＝80Y＝40したがって、
（0，40）
です。
X軸との交点
今度は、
Y＝0
を代入します。
X＋0＝80X＝80したがって、
（80，0）
です。
この2点を結ぶと、
X＋2Y＝80
の直線になります。
ワンポイント
なぜ、
X＝0
や
Y＝0
を代入するのでしょうか。
それは、
- Y軸上の点は、すべて X＝0
- X軸上の点は、すべて Y＝0
だからです。
このルールを覚えておけば、
一次方程式のグラフは簡単に描けます。
③ 実行可能領域の頂点を求める
条件をすべて満たす範囲を
実行可能領域
といいます。
今回の頂点は、
- （0，0）
- （0，40）
- （50，0）
- 2本の直線の交点
です。
交点は連立方程式で求めます。
2X＋Y＝100
X＋2Y＝801本目を2倍すると、
4X＋2Y＝200ここから2本目を引きます。
4X＋2Y＝200
−）X＋2Y＝ 80
──────────
3X ＝ 120したがって、
X＝40これを
2X＋Y＝100
へ代入すると、
2×40＋Y＝100
80＋Y＝100
Y＝20したがって、
交点は
（40，20）
になります。
④ 各頂点の利益を計算する
目的関数は、
Z＝100X＋150Y
です。
各頂点を代入します。
| 頂点 | 計算 | 利益 |
|---|---|---|
| （0，0） | 100×0＋150×0 | 0円 |
| （0，40） | 100×0＋150×40 | 6,000円 |
| （50，0） | 100×50＋150×0 | 5,000円 |
| （40，20） | 100×40＋150×20 | 7,000円 |
最も利益が大きいのは、
7,000円
です。
したがって、
製品Xを40個、製品Yを20個生産する
のが最適解になります。
なぜ頂点だけ調べればいいの？
「途中の点の方が利益が大きくなることはないの？」
と思うかもしれません。
教科書では、
目的関数の直線を平行移動する方法で説明されています。
利益が大きくなる方向へ直線を動かしていくと、
最後に実行可能領域へ接する場所は、
必ず頂点
になります。
つまり、
教科書の説明があるからこそ、
頂点だけ調べればよい
という試験向けの解法が成り立っています。
教科書の方法と試験向けの方法
教科書の方法は、
- なぜ最大になるのか理解できる
- 数学的な考え方が身に付く
というメリットがあります。
一方、試験向けの方法は、
- 手順が少ない
- 計算ミスが少ない
- 短時間で解ける
というメリットがあります。
どちらが正しいというわけではありません。
教科書は
「理解するための方法」
試験では
「得点するための方法」
として使い分けるのがおすすめです。
試験中の確認ポイント
問題が出たら、次の順番で確認しましょう。
- XとYが何を表しているか確認する
- 制約条件を書く
- グラフを書く
- 実行可能領域の頂点を探す
- 交点を連立方程式で求める
- 各頂点を目的関数へ代入する
- 最大値（または最小値）を選ぶ
まとめ
線形計画法では、教科書のように目的関数の直線を平行移動する方法で考えることもできます。
しかし、基本情報技術者試験では、次の4ステップを覚えておけば十分です。
- 制約条件を書く
- グラフを書く
- 実行可能領域の頂点を求める
- 頂点を目的関数へ代入する
まずは試験で解けるようになり、その後に教科書へ戻って、
「なぜ頂点だけ調べればよいのか」
を理解すると、知識がより深まります。
最後に、覚えておきたい合言葉です。
線形計画法は、グラフを書いたら頂点へ代入！