基本情報技術者試験対策として、線形計画法の計算問題についてまとめました。
午前試験で出題されます。「計算方法がわからない」悪夢を避けるためがんばって覚えましょう。
線形計画法の出題パターン
線形計画法とは、一次式で現わされる制約条件の下での最大値(最小値)、もしくは最大値(最小値)になる条件を求める手法です。
情報処理技術者試験では下記の2パターンで出題されます。
- 与えられた表をもとに計算した場合の最大利益はいくらか？
- 与えられた説明をもとに線形計画法で式をつくるとどうなるか？
線形計画法の計算方法
直接解くことのできる公式はありません、そのため解法に従って順番に計算して正解を目指します。
具体的な手順は以下の通りです。
- 目的関数を特定する
- 制約条件を定式化する(一次方程式に書き換える)
- 実行可能領域の頂点を計算する(連立方程式にして解く)
- 頂点の座標を目的関数に代入する
例題をもとにした解き方の解説
今回は以下の例題をもとに、実際にどのように解いていくかを解説します。
【例題】
表は、製品A, Bを生産するのに必要な製品1単位当たりの原料使用量及び設備使用時間と、それぞれの制約条件を示している。製品1単位当たりの利益が、製品Aが5万円、製品Bが4万円であるとき、1日の最大利益は何万円か。
※基本情報技術者 平成25年 春期 問76
目的関数を特定する
質問文のこの部分が目的関数となります。
製品1単位当たりの利益が、製品Aが5万円、製品Bが4万円であるとき、1日の最大利益は何万円か。
= 製品A(5万円)と製品B(4万円)をそれぞれ何個生産したら利益が最大化されるか？
これを式に書き起こすと目的関数となり、以下となります。
- 目的関数 = 5A + 4B
制約条件を定式化し実行可能領域を特定する
続いて制約条件を定式化します。本問では与えられた表に「制約条件」と書かれているためこれを数式に書き起こします。 すると、以下2つの一次方程式を書くことができます。
- 原料：2A + 4B <= 16
- 設備：3A + 2B <= 12
この一次方程式をグラフ化した時に囲まれる部分が「実行可能領域」と呼ばれます。
単位が違うものを機械的に式にすることに抵抗があると思いますが、問題ありません。ここで求めるべきは製品A/製品Bの個数です。
目的関数、制約条件ともに変数A/変数Bが個数であることで一致していますため、このまま計算することができます。
違和感は忘れてください。
実行可能領域の頂点を計算する
実行可能領域の頂点部分が、つまり最大利益を導き出すための変数A/変数Bとなります。
頂点を求める方法として、「山勘の数値を手作業で代入して計算」「グラフを目視で読み解く」「運命力で正解を引き当てる」などの方法がありますが、いずれも正解できる可能性が低いです。
確実に正解するためには、実行可能領域を示す2つの一次方程式を連立方程式として解きます。
まず、以下の不等式から不等号を削除して一次方程式に変換します。
- 原料：2A + 4B <= 16
- 設備：3A + 2B <= 12
不等号を削除。
- 原料：2A + 4B = 16
- 設備：3A + 2B = 12
AもしくはBを消すため数式を変形する。今回はBを消すため設備の方の式を変形しました。
- 原料：2A + 4B = 16
- 設備(*2して変形)：6A + 4B = 24
変数をAのみにしてAの値を特定するため、設備の式 - 原料の式 の計算を行う。
- 設備の式 - 原料の式：(6A - 2A) + (4B - 4B) = 24 - 16
- 途中の式：2A = 8
- 計算結果：A = 4
Aの値が特定できました。実行可能領域の一次方程式どちらかを使いBの値を特定します。
今回は原料の式で計算します。
- 原料：2A + 4B = 16
- A = 4を代入：2*4 + 4B = 16
- 途中の式：8 + 4B = 16
- 途中の式：4B = 16 - 8
- 途中の式：4B = 8
- 計算結果：B = 2
結果として、実行可能領域の頂点の座標は以下であるとわかりました。
- A = 4
- B = 2
頂点の座標を目的関数に代入する
最後に目的関数に実行可能領域の頂点の座標を代入して計算します。
- 目的関数 = 5A + 4B
- 代入した：目的関数 = 54 + 42
- 途中の式：目的関数 = 20 + 8
- 計算結果：目的関数 = 28
式の意味合いとしては、A製品4個利益5万円 + B製品2個利益4万円 = 利益28万円 となります。
よって1日の最大利益は 28万円 であると言えます。
解答のポイント
手順を覚える
この問題を回答するポイントは2つ、①以下4ステップの計算の手順を覚えること、②各手順の計算方法を覚えること、です。
- 目的関数を特定する
- 制約条件を一次方程式に書き換える
- 制約条件の一次方程式を連立方程式にして解く
- 目的関数に連立方程式の答えを代入する
そして覚えるためには手計算で練習あるのみです。毎週3日は過去問の計算問題を解く、計算ドリルを全部やり切る、など反復的継続的に取り組むことをお勧めします。 2ヶ月くらいがんばるとすらすら解けるようになります。
備考
これは典型的な「練習して身に着ける」問題です。練習量が足りないと普通に忘れます(実体験)。 試験会場で解法を思い出すのはまず不可能、問題を読んだら手が勝手に動き出すくらいまで繰り返してできるようになりましょう！！！
