線形計画法とは？目的関数・制約条件と利益最大化の考え方【基本情報技術者試験】

まず結論

線形計画法とは、限られた資源の中で、利益を最大にしたり、費用を最小にしたりする組合せを求める方法です。

基本情報技術者試験では、次の言葉が出てきたら線形計画法を考えます。

利益を最大にする
費用を最小にする
使える時間に上限がある
材料に上限がある
最適な生産量を求める

覚える一文はこれです。

限られた資源の中で、利益最大・費用最小を求めるのが線形計画法。

計算問題では、次の順番を基本にします。

制約式を書く
↓
実行可能領域の頂点を求める
↓
各頂点で目的関数を計算する
↓
最大・最小を選ぶ

直感的な説明

工場では、作りたい製品が複数あっても、使える時間や材料には限りがあります。

製品Aは利益が高い
でも材料を多く使う

製品Bは利益は少し低い
でも短時間で作れる

製品Cは材料を多く使う
でも時間はあまりかからない

このとき、

Aを何個作るか
Bを何個作るか
Cを何個作るか

を決めて、全体の利益が最大になる組合せを探します。

つまり、線形計画法は、

限られた時間・材料・人員を、どこへどれだけ配分すると一番よいか

を考える方法です。

ここで大切なのは、1個当たりの利益が最も高い製品だけを作ればよいとは限らないことです。

単価が高い
≠
全体の利益が最大

材料の使い方を組み合わせることで、全体の利益がより大きくなる場合があります。

定義・仕組み

線形計画法では、主に次の3つを決めます。

変数
目的関数
制約条件

変数

変数は、決めたい数量です。

例えば、製品A・B・Cの生産量を次のように置きます。

x：製品Aの生産量
y：製品Bの生産量
z：製品Cの生産量

目的関数

目的関数は、最大化または最小化したいものです。

例えば、1個当たりの利益が次のとおりだとします。

製品A：8千円
製品B：5千円
製品C：5千円

全体の利益は、

8x + 5y + 5z

です。

したがって、目的は次のようになります。

8x + 5y + 5z を最大化する

制約条件

制約条件は、守らなければならない上限や下限です。

製造時間が次のように必要だとします。

製品A：2時間
製品B：3時間
製品C：1時間

月に使える製造時間が240時間なら、

2x + 3y + z ≤ 240

です。

原料使用量が次のとおりだとします。

製品A：2kg
製品B：1kg
製品C：2kg

使える原料が150kgなら、

2x + y + 2z ≤ 150

です。

また、生産量が負になることはないため、

x ≥ 0
y ≥ 0
z ≥ 0

という条件も必要です。

線形であるとは

目的関数と制約条件が、変数の1次式で表されることがポイントです。

8x + 5y
2x + 3y ≤ 240

のように、変数同士の掛け算や2乗が含まれません。

xy
x²

のような項がある場合は、通常の線形計画法とは異なります。

このテーマは、基本情報技術者試験の経営工学やORに関係する内容です。公式の出題範囲やシラバスは、IPA：基本情報技術者試験から確認できます。

科目Aでどう出る？

科目Aでは、問題文の内容から適切な手法を選ぶ形や、与えられた条件から最大利益を求める形で出題されます。

線形計画法を選ぶ手掛かり

限られた資源
最適な組合せ
利益最大
費用最小
生産量
配分

これらがそろっていれば、線形計画法を考えます。

似た手法との切り分け

手法	主な目的
移動平均法	時系列データを平滑化して傾向を見る
最小二乗法	データに最も合う直線や曲線を求める
線形計画法	制約の中で最適な組合せを求める
定量発注法	在庫が減ったときに一定量を発注する

試験では、次のように判断できます。

売上や需要の変動を滑らかにする
→ 移動平均法

点の集まりから回帰直線を求める
→ 最小二乗法

時間や材料に上限があり、利益を最大化
→ 線形計画法

在庫を一定量ずつ補充する
→ 定量発注法

問題文を式にする

線形計画法の問題では、次の順番で整理します。

何を決めるか
何を最大・最小にするか
何に上限・下限があるか

例えば、

何を決めるか
→ 各製品の生産量

何を最大化するか
→ 利益

何に上限があるか
→ 製造時間と原料

と読めれば、式へ変換しやすくなります。

2製品なら「Xだけ・Yだけ・交点」をまず見る

2製品の利益最大化問題では、解き方に迷ったら次の3候補を確認すると整理しやすくなります。

Xだけ作る
Yだけ作る
XとYを組み合わせる境界線の交点

ただし、この3つだけで十分とは限りません。最終的には、実行可能領域を作るすべての頂点を比較するのが基本です。

例えば、制約が

2x + y ≤ 100
x + 2y ≤ 80
x ≥ 0
y ≥ 0

で、利益が

100x + 150y

なら、候補を次のように調べます。

Xだけ → (50, 0) → 5,000円
Yだけ → (0, 40) → 6,000円
交点   → (40, 20) → 7,000円

この場合は、組み合わせた (40, 20) が最大利益になります。

高利益の製品を優先するのではなく、候補となる頂点で全体利益を比較する。

これが科目Aで安定して解くための判断軸です。

どんな場面で使う？

線形計画法は、資源配分を決める場面で使われます。

代表例は次のとおりです。

製品ごとの生産量を決める
人員の配置を決める
輸送量を決める
広告予算の配分を決める
原材料の配合を決める
費用を最小にする購入計画を立てる

生産計画

工場では、限られた機械時間や材料を、どの製品へ配分するかを決めます。

利益最大
→ どの製品を何個作るか

輸送計画

複数の倉庫から複数の店舗へ商品を送る場合に、輸送費が最小になる配送量を求めます。

費用最小
→ どこからどこへ何個送るか

人員配置

必要人数や勤務時間の条件を満たしながら、人件費が最小になる配置を求めます。

必要人数を確保
かつ
人件費を最小化

グラフで考える基本

変数が2つの場合は、グラフで考えられます。

例えば、

2x + 3y ≤ 240
2x + y ≤ 150
x ≥ 0
y ≥ 0

という制約があるとします。

各不等式を満たす範囲を重ねると、すべての条件を満たす領域ができます。

この範囲を 実行可能領域 といいます。

制約条件をすべて満たす範囲
→ 実行可能領域

線形計画法では、目的関数の最大値や最小値は、通常、この実行可能領域の頂点で求まります。

そのため、2変数の問題では、頂点を調べる方法がよく使われます。

計算問題は「頂点を比較する」

2変数の線形計画法では、次の4ステップで考えると整理しやすくなります。

制約条件を式にする
実行可能領域の頂点を求める
各頂点を目的関数に代入する
最大値または最小値を選ぶ

例えば、製品MとNの生産量をそれぞれ x、y とし、次の制約があるとします。

6x + 3y ≤ 360
2x + 4y ≤ 240
x ≥ 0
y ≥ 0

境界線は、次の等式で表せます。

6x + 3y = 360
2x + 4y = 240

簡単にすると、

2x + y = 120
x + 2y = 120

です。

この2本の境界線が交わる点は、連立方程式で求めます。

2x + y = 120
x + 2y = 120

2つ目の式から、

x = 120 - 2y

これを1つ目の式へ代入します。

2(120 - 2y) + y = 120
240 - 4y + y = 120
-3y = -120
y = 40

したがって、

x = 40
y = 40

となります。

ただし、交点を求めただけでは最大利益とは決まりません。

実行可能領域のほかの頂点も含め、目的関数へ代入して比較します。

例えば、1個当たりの利益が次のとおりなら、

製品M：600円
製品N：400円

目的関数は、

600x + 400y

です。

交点 (40, 40) では、

600 × 40 + 400 × 40
= 40,000円

となります。

試験では、連立方程式を解くこと自体が目的ではありません。

制約式を書く
↓
頂点を求める
↓
目的関数へ代入する
↓
ほかの頂点と比較する

この流れで、最も大きい利益や最も小さい費用を選びます。

微分して最大値を求めるのではないの？

利益を関数にして微分する方法を思い浮かべるかもしれません。

しかし、基本情報技術者試験で扱う線形計画法では、目的関数も制約条件も1次式です。

例えば、

利益 P = 100x + 150y
制約 2x + y = 100

なら、制約から

y = 100 - 2x

として利益に代入すると、

P(x) = 100x + 150(100 - 2x)
     = 15000 - 200x

となります。

これは1次関数なので、微分しても

P'(x) = -200

と一定です。

二次関数など
→ 山や谷がある
→ 微分して極大・極小を探せる

線形計画法
→ 目的関数は直線
→ 傾きは一定
→ 実行可能領域の境界・頂点で最大最小を調べる

したがって、FE試験では

線形計画法 → 微分ではなく、実行可能領域の頂点を比較する

と判断すると解き方が定まりやすくなります。

科目Bでどう使う？

科目Bでは、変数、条件式、最大値探索の考え方につながります。

例えば、複数の生産量候補を調べる場合は、次のように考えます。

すべての候補について
    制約条件を満たすか確認する
    満たすなら利益を計算する
    最大利益を更新する

Pythonで単純に探索すると、次のようになります。

best_profit = -1
best_plan = None

for x in range(121):
    for y in range(81):
        for z in range(241):
            time_used = 2 * x + 3 * y + z
            material_used = 2 * x + y + 2 * z

            if time_used <= 240 and material_used <= 150:
                profit = 8 * x + 5 * y + 5 * z

                if profit > best_profit:
                    best_profit = profit
                    best_plan = (x, y, z)

print(best_profit, best_plan)

本来の線形計画法では、すべての組合せを総当たりしなくても効率よく解けます。

ただし、科目Bでは、

制約条件を満たすか
目的値を計算する
最大値を更新する

という流れを理解しておくと役立ちます。

よくある誤解・混同

最大値を求める問題ならすべて線形計画法

違います。

最大化・最小化に加えて、制約条件の中で複数の変数の組合せを決めることがポイントです。

単に最大値を探す
→ 必ずしも線形計画法ではない

資源制約の中で最適配分を求める
→ 線形計画法

利益が最も高い製品だけを作ればよい

違います。

1個当たりの利益が高くても、多くの資源を消費する場合があります。

単価だけを見る
→ 誤り

制約を満たす各頂点で全体利益を比較する
→ 正しい

微分して最大値を求めればよい

通常のFEの線形計画法では、その考え方は使いません。

目的関数は1次式なので、微分しても傾きは一定です。

線形計画法
→ 頂点を比較

二次関数などの極大・極小
→ 微分が有効な場合がある

移動平均法と同じ

移動平均法は、時系列データの変動を滑らかにする方法です。

需要予測や傾向把握
→ 移動平均法

生産量の最適化
→ 線形計画法

最小二乗法と同じ

最小二乗法は、観測データに最もよく合う直線や曲線を求める方法です。

回帰直線を求める
→ 最小二乗法

制約の中で利益最大
→ 線形計画法

定量発注法と同じ

定量発注法は、在庫が一定水準まで減ったときに、毎回決まった量を発注する方式です。

発注タイミングと発注量
→ 定量発注法

複数製品の最適な生産量
→ 線形計画法

3つ以上の製品はグラフで解けない

2変数なら平面グラフで表せますが、3変数以上では図示が難しくなります。

それでも、考え方は同じです。

目的関数
制約条件
非負条件

を整理して最適解を求めます。

制約条件は等式でなければならない

上限や下限は、不等式で表します。

最大240時間
→ ≤ 240

最低100個
→ ≥ 100

2本の制約式の交点だけ調べればよい

違います。

交点は有力な候補ですが、軸との交点など、実行可能領域を作るほかの頂点も候補です。

交点を求める
→ 候補の1つ

各頂点で目的関数を計算する
→ 最大・最小を決める

まとめ（試験直前用）

線形計画法は、制約の中で最適な組合せを求める方法
利益最大化や費用最小化に使う
決めたい数量を変数にする
最大・最小にしたい式が目的関数
時間・材料・人員などの上限が制約条件
変数は通常0以上
目的関数と制約条件は1次式で表す
2変数なら実行可能領域をグラフで考えられる
計算問題は「制約式 → 頂点 → 目的関数へ代入 → 比較」
2製品なら、まず「Xだけ・Yだけ・交点」を候補として確認する
線形計画法は、微分より頂点比較で考える
移動平均法は平滑化、最小二乗法は回帰、定量発注法は在庫補充
「限られた資源をどう配分するか」が判断の決め手

目的関数を決め、制約条件の中で最もよい組合せを頂点で比較する。

🔗 関連記事

🏠 基本情報技術者トップに戻る