計算問題の解き方・5/20
線形計画法で最大利益を求める解き方
製品ごとの原料や機械時間の使用量と上限が表で与えられ、利益が最大になる生産量の組合せと、そのときの最大利益を求めます。用語問題として「1 次式の制約条件の下で 1 次式の効果を最大にする手法＝線形計画法」も出題されます。
公開過去問での出題：本試験系 8 回・免除試験 33 回（観測値）
覚える式
- 制約条件: (製品Xの使用量)×x ＋ (製品Yの使用量)×y ≦ 上限（資源ごとに 1 本）、x≧0、y≧0
- 目的関数: (Xの1個当たり利益)×x ＋ (Yの1個当たり利益)×y → 最大化
- 最大値は、制約の直線どうしの交点か、軸との交点（片方だけ作る場合）のどれかで出ます
解き方の手順
- 製品の生産量を x、y と置き、表の行と列を取り違えないように、資源（原料・機械など）ごとに「使用量×生産量の合計 ≦ 上限」の式を 1 本ずつ書きます。
- 単位をそろえます。時間が「時間」と「分」で混ざっていたら、上限を分に直してから式を立てます。
- 2 本の制約式を連立方程式として解き、交点（x, y）を求めます。
- 片方の製品だけを作る場合の最大量も求めます。各軸について、すべての制約を満たす中でいちばん小さい値が上限です。
- 候補の点（交点・各軸の上限）ごとに利益を計算し、いちばん大きい値を答えにします。
- 使える資源が 1 種類だけで、製品ごとに需要の上限がある場合は、資源 1 単位当たりの利益が高い製品から上限まで割り当て、余った資源を次の製品に回します。
例題
製品 X 及び Y を生産するために 2 種類の原料 A，B が必要である。製品 1 個の生産に必要となる原料の量と調達可能量は表に示すとおりである。製品 X と Y の 1 個当たりの販売利益が，それぞれ 100 円，150 円であるとき，最大利益は何円か。
| 原料 | 製品 X の 1 個当たりの必要量 | 製品 Y の 1 個当たりの必要量 | 調達可能量 |
|---|---|---|---|
| A | 2 | 1 | 100 |
| B | 1 | 2 | 80 |
ア 5,000
イ 6,000
ウ 7,000
エ 8,000
出典：令和元年度 秋期 基本情報技術者試験 午前 問76（解き方は当サイト作成）
解き方と答えを見る
- X を x 個、Y を y 個作るとします。
- 原料A: 2x ＋ y ≦ 100、原料B: x ＋ 2y ≦ 80
- 交点: 1 本目から y ＝ 100 − 2x。2 本目に代入して x ＋ 2(100 − 2x) ＝ 80 → −3x ＝ −120 → x ＝ 40、y ＝ 100 − 80 ＝ 20
- X だけ作る場合: A から x ≦ 50、B から x ≦ 80 → x ＝ 50、利益 100×50 ＝ 5,000円
- Y だけ作る場合: A から y ≦ 100、B から y ≦ 40 → y ＝ 40、利益 150×40 ＝ 6,000円
- 交点の利益: 100×40 ＋ 150×20 ＝ 4,000 ＋ 3,000 ＝ 7,000円
- 3 つの候補のうち最大は 7,000円です。
答え：7,000円（ウ）
ひっかけ
- 1 個当たりの利益が高い製品だけを作ればよいと考えると、例題では Y だけの 6,000円（イ）を選んでしまいます。交点の利益と必ず比べてください。
- 軸の上限を 1 本の制約だけで決めると、ほかの資源の上限を超えた生産量になります。例題で原料A だけを見ると y ＝ 100 まで作れそうですが、原料B で y ≦ 40 に抑えられます。候補の点は、すべての制約に代入して確かめてください。
- 上限が「時間」、使用量が「分」のように単位がそろっていないまま式を立てると、桁違いの答えになります。式を書く前に単位をそろえてください。
- 資源が 1 種類だけの問題で、1 個当たりの利益の大きさで優先順位を決めると誤ります。比べるのは「資源 1 単位（例: 1 分）当たりの利益」です。
類題（手順を使って解く）
類題 1
資源が工場の時間 1 種類だけで需要の上限がある形のため、時間単位をそろえ、1 分当たりの利益の高い順に割り当てる手順（手順 2・6）が試されます。
ある工場では表に示す 3 製品を製造している。実現可能な最大利益は何円か。ここで，各製品の月間需要量には上限があり，また，製造工程に使える工場の時間は月間 200 時間までで，複数種類の製品を同時に並行して製造することはできないものとする。
| 製品 X | 製品 Y | 製品 Z | |
|---|---|---|---|
| 1 個当たりの利益（円） | 1,800 | 2,500 | 3,000 |
| 1 個当たりの製造所要時間（分） | 6 | 10 | 15 |
| 月間需要量上限（個） | 1,000 | 900 | 500 |
出典：平成28年度 秋期 基本情報技術者試験 午前 問71（問題文は IPA の公開問題。答えと解説はリンク先）
類題 2
所要時間が分、稼働可能時間が時間で与えられるため、単位をそろえてから制約式を立て、連立方程式で交点を求める手順（手順 2・3）が試されます。
製品 M，N を，機械 P，Q による2工程で生産している。表は，各製品を1単位生産するために要する各機械の所要時間，及び各製品の1単位当たりの販売利益を示す。機械 P，Q の月間稼働可能時間はいずれも 200 時間である。販売利益が最大となるように製品 M，N を生産し，すべてを販売したときの販売利益は何万円か。ここで，製品 M，N ともに生産工程の順番に制約はなく，どちらの機械を先に使用しても製品は生産できるものとする。
| 機械P | 機械Q | 単位当たり販売利益 | |
|---|---|---|---|
| 製品M | 30分 | 20分 | 2,500円 |
| 製品N | 15分 | 30分 | 3,000円 |
出典：基本情報技術者試験 科目A免除 修了試験 20140622 実施分 問77（問題文は IPA の公開問題。答えと解説はリンク先）
類題 3
表の縦横から原料と設備の制約式を正しく 2 本立て、交点と各軸の上限の利益を比べる手順（手順 1・3〜5）が試されます。
表は，製品 A，B を生産するのに必要な製品 1 単位当たりの原料使用量及び設備使用時間と，それぞれの制約条件を示している。製品 1 単位当たりの利益が，製品 A が 5 万円，製品 B が 4 万円であるとき，1 日の最大利益は何万円か。
| 製品 A | 製品 B | 制約条件 | |
|---|---|---|---|
| 原料（kg／製品） | 2 | 4 | 1 日当たり合計 16 kg まで使用可能 |
| 設備（時間／製品） | 3 | 2 | 1 日当たり延べ 12 時間まで使用可能 |
出典：平成25年度 春期 基本情報技術者試験 午前 問76（問題文は IPA の公開問題。答えと解説はリンク先）