線形計画法（linear programming）

分類

テクノロジ系 基礎理論

出る試験

基本情報応用情報

重要度

★★★☆☆

もう少し詳しい説明

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

「線形」は、出てくる式がすべて一次式（直線で表せる）という意味です。「計画法」は、英語の programming を訳したもので、計算機のプログラムとは関係ありません。

3つの材料

問題には必ず3つがそろいます。

この3つを式にするところが、問題を解く作業のほとんどです。

解き方：角を調べる

製品Aと製品Bを作る例で見ます。

式にするとこうなります。

制約：2x + y ≦ 80、x + 2y ≦ 70、x ≧ 0、y ≧ 0

目的：利益 = 300x + 400y を最大にする

制約を満たす範囲をグラフに描くと、直線で囲まれた多角形になります。

塗ってある部分が、4つの条件をすべて満たす範囲です。x ≧ 0 で左側が、y ≧ 0 で下側が切られ、残りの2本の線で右上が切られています。この中なら、どの組合せを選んでもかまいません。

ここが肝心なところです。

目的関数が最大になるのは、必ず多角形の頂点のどれか。

制約式も目的関数も直線なので、範囲の内側に「頂点より良い点」が現れることはありません。すべての点を調べる必要はなく、角だけを順に計算すれば答えが出ます。

上の例では、2本の制約が交わる点が (30, 20) です。

300 × 30 ＋ 400 × 20 ＝ 9,000 ＋ 8,000 ＝ 17,000円

ほかの頂点（0,35）や（40,0）も計算して比べると、ここがいちばん大きくなります。

「必ず頂点」が効く理由

目的関数 300x + 400y = 一定 は直線です。この直線を、値を大きくしながら平行に動かしていくと、多角形から出ていく直前に触れているのが頂点になります。

辺にぴったり重なることもあり、そのときはその辺の上がすべて最適解になります。頂点も含まれるので、頂点を調べれば答えは見つかります。

変数が3つ以上のとき

グラフが描けるのは、決める値が2つまでです。3つ以上になると、シンプレックス法という手順で、頂点から頂点へ良いほうへ移っていきます。

試験で計算させられるのは2変数までです。シンプレックス法は名前だけ覚えておけば足ります。

最小二乗法との違い

どちらも「最適なものを見つける」計算ですが、目的が違います。

線形計画法は選ぶ計算、最小二乗法は当てはめる計算です。

試験ではこう出る

科目A（旧・午前）では、2変数の問題を解かせる形が出ます。制約式と利益の式が与えられ、最大の利益を答えます。頂点だけを調べればよいと知っていると、総当たりを避けられます。

制約式を立てさせる形も出ます。文章から「材料は80kgまで」を 2x + y ≦ 80 に直せるかが問われます。

「最適解は頂点にある」という性質そのものを問う選択肢も出ます。

応用情報では、待ち行列理論などと並べて、オペレーションズリサーチの手法の選択として出ることがあります。「資源配分を最適化する」なら線形計画法です。

関連する用語

最小二乗法

同じ最適化だが目的が違う。こちらは最大化・最小化、あちらは当てはめ

限界利益と限界利益率

目的の式に入れる「1個あたりいくら残るか」はこれで出す

待ち行列理論

同じオペレーションズリサーチの道具。こちらは待ち時間を求める

MRP

必要な部品量を計算する。資源の制約という点で地続き

ミニクイズ

この分野をまとめて解く → 基礎理論と情報メディアのミニテスト（全39問）

最終更新：2026-10-20