経営学・経済学・数学・オペレーションズリサーチなどの分野で頻繁に登場する「線形計画法」。
「目的関数って何？」「制約条件はどう扱うの？」「グラフ解法はどうやるの？」と疑問に感じる方も多いでしょう。
本記事では、線形計画法の意味・定式化・グラフ解法・最適解の求め方を、具体的な例題を交えてわかりやすく解説していきます。
数学が苦手な方でも理解できるよう、ステップバイステップで説明しますので、ぜひ最後までご覧ください。
線形計画法とは？基本的な意味と概要
それではまず、線形計画法の意味と基本概要について解説していきます。
線形計画法（Linear Programming, LP）とは、線形（一次式）の目的関数を、線形の制約条件のもとで最大化または最小化する手法です。
「どのように資源を配分すれば最も利益が大きくなるか」「どのようにコストを割り当てれば最も費用を抑えられるか」といった最適化問題を解くために使われます。
線形計画法の問題は次の3つの要素で構成されます。
【線形計画法の3要素】
①目的関数（objective function）：最大化または最小化したい量を表す一次式
②制約条件（constraints）：満たさなければならない条件（一次不等式・等式）
③非負条件：変数が0以上であること（x ≥ 0, y ≥ 0）
線形計画法は1940年代にジョージ・ダンツィグが「シンプレックス法」を開発したことで実用的な手法となり、以来、経営・物流・金融・エネルギー・製造業など幅広い分野で活用されています。
目的関数と制約条件の設定方法
線形計画法を解くためには、まず問題を正しく定式化することが重要です。
目的関数は「最大化したいもの（利益・生産量など）」または「最小化したいもの（コスト・時間など）」を一次式で表します。
たとえば、製品AとBを生産するとき、利益が A 1個あたり3万円、B 1個あたり4万円であれば、目的関数は z = 3x + 4y（最大化）となります。
制約条件は、原材料の量・機械の稼働時間・労働力などの上限や下限を一次不等式で表します。
問題文を丁寧に読み、変数・目的関数・制約条件を正確に整理することが問題解決の第一歩です。
グラフ解法の手順（2変数の場合）
2変数の線形計画問題は、グラフを使って解くことができます。
グラフ解法の手順は次のとおりです。
【グラフ解法の手順】
①各制約条件を等号に変えた直線を描く
②制約条件を満たす領域（実行可能領域）を特定する
③目的関数を定数 k とおいた直線（z = k）を描く
④kの値を変えながら実行可能領域内で z が最大（または最小）になる頂点を求める
最適解は必ず実行可能領域の「頂点（角）」に存在することが線形計画法の重要な定理です。
これを「頂点定理」と呼び、すべての頂点の座標で目的関数の値を計算し比較することで最適解を求められます。
実行可能領域と最適解の関係
実行可能領域とは、すべての制約条件を同時に満たす変数の集合をグラフ上に表した領域です。
この領域は「多角形（凸多角形）」の形をとることが多く、その頂点が最適解の候補になります。
目的関数の直線（等値線）を実行可能領域に沿って動かしていき、領域から出る直前の接点が最適解です。
もし実行可能領域が存在しない場合（制約条件が矛盾している場合）は「実行不可能」、領域が無限に広がる場合は「最適解なし（非有界）」となります。
実行可能領域を正確に描き、頂点を特定することがグラフ解法の要です。
線形計画法の例題を解いてみよう
続いては、具体的な例題を通して線形計画法の解き方を確認していきます。
例題：製品生産の最適化
【例題】
製品A・Bを生産する工場があります。
A 1個には原料2kg・加工時間1時間、B 1個には原料1kg・加工時間2時間が必要です。
原料は合計10kg、加工時間は合計8時間まで使用できます。
A 1個の利益は3万円、B 1個の利益は4万円のとき、利益を最大にする生産数を求めよ。
まず変数を設定します：A の生産数を x、B の生産数を y とします。
目的関数：z = 3x + 4y（最大化）
制約条件：2x + y ≦ 10（原料）、x + 2y ≦ 8（加工時間）、x ≧ 0、y ≧ 0
制約条件の直線を描き、実行可能領域を求めます。
頂点は (0, 0)、(5, 0)、(4, 2)、(0, 4) となります。
各頂点での z の値を計算すると、z(0,0) = 0、z(5,0) = 15、z(4,2) = 20、z(0,4) = 16 です。
最大値は z = 20（x = 4, y = 2）のときとなります。
交点の座標の求め方
例題の交点 (4, 2) は、2つの制約式を連立方程式として解くことで求められます。
【連立方程式による交点の計算】
2x + y = 10 ……①
x + 2y = 8 ……②
①×2：4x + 2y = 20
②：x + 2y = 8
引き算：3x = 12 → x = 4
②に代入：4 + 2y = 8 → y = 2
このように、制約条件の直線の交点を求める際には連立方程式を活用します。
実行可能領域の各頂点を漏れなく計算することが正確な解答への道です。
シンプレックス法の概要
変数が3つ以上になるとグラフ解法は使えなくなります。
そのような場合に使われるのが「シンプレックス法（単体法）」です。
シンプレックス法は、実行可能領域の頂点を効率的に移動しながら最適解を探すアルゴリズムです。
コンピュータで実装しやすく、数百・数千の変数を持つ大規模問題にも対応できます。
PythonのSciPyライブラリやExcelのソルバー機能を使えば、シンプレックス法を手軽に実行できます。
線形計画法の実際の応用例
続いては、線形計画法が実際にどのような場面で活用されているかを確認していきます。
物流・サプライチェーンでの活用
線形計画法は物流・サプライチェーン管理で広く使われています。
「複数の倉庫から複数の配送先へ、コストを最小化しながら物資を輸送する問題（輸送問題）」は線形計画法の古典的な応用例です。
宅配業者の配送ルート最適化・工場の生産計画・在庫管理なども線形計画法の枠組みで解くことができます。
物流コストの削減に線形計画法が大きく貢献しているケースは多いでしょう。
金融・投資ポートフォリオへの応用
金融分野では、「リスクを一定以下に抑えながらリターンを最大化する投資配分」を求める問題に線形計画法が使われます。
ポートフォリオ最適化では、各資産への投資割合を変数として目的関数・制約条件を設定します。
資産配分の問題は2次計画法（目的関数が2次式）に発展することもありますが、基本の考え方は線形計画法と共通しています。
線形計画法の限界と発展的手法
線形計画法は強力な手法ですが、いくつかの限界もあります。
目的関数や制約条件が非線形の場合には使えず、非線形計画法が必要になります。
変数が整数値でなければならない場合は「整数計画法（Integer Programming）」を使います。
複数の目的関数を同時に最適化したい場合は「多目的最適化」の手法が必要です。
線形計画法をマスターすることは、より高度な最適化手法を学ぶ上での重要な土台となるでしょう。
まとめ
本記事では、線形計画法の意味・定式化・グラフ解法・例題の解き方・実際の応用例について詳しく解説しました。
線形計画法とは、線形の目的関数を線形の制約条件のもとで最大化・最小化する手法です。
2変数の問題はグラフ解法で解くことができ、最適解は実行可能領域の頂点に存在します。
多変数の場合はシンプレックス法を使い、物流・金融・製造など多くの分野で活用されています。
線形計画法の考え方を身につけることで、実際のビジネス問題や数学の最適化問題を論理的に解決できる力が身につくでしょう。
ぜひ例題を繰り返し解いて、線形計画法の感覚を掴んでみてください。
