線形計画問題の解法（図解法・シンプレックス法）とは？意味と試験で問われるポイント｜証券アナリスト1次・数量分析と確率・統計
ひとことで言うと
- 変数が2つなら、実行可能領域を図に描いて頂点を比べる図解法で解けます。
- 一般の問題では、頂点から頂点へ目的関数が良くなる方向にたどるシンプレックス法が代表的な解法です。
- 領域の内部を通って最適解に近づく内点法もあります。
この記事では、証券アナリスト1次「数量分析と確率・統計」の学習ポイントのひとつ「線形計画問題の代表的な解法」について、意味と試験で問われやすいポイントを解説します。
| 分野 | 1次 科目Ⅲ／数量分析と確率・統計 |
|---|---|
| 大分類 | (9) 最適化手法 |
| 協会の学習ポイント | 線形計画問題の代表的な解法について理解する。 |
線形計画問題の解法（図解法・シンプレックス法）とは
線形計画問題では、最適解があれば実行可能領域の頂点に現れます。そのため、解法の基本は「頂点を効率よく調べること」です。代表的な解法として、図解法とシンプレックス法を押さえましょう。
図解法
決定変数が2つの場合に使える方法です。各制約条件を境界線として座標平面に描き、すべてを満たす領域（実行可能領域）を求めます。次に、目的関数の値が一定となる直線（等利益線）を描き、それを目的関数が大きくなる方向へ平行移動させます。領域から離れる直前に触れる頂点が最適解です。等利益線が領域の辺と平行な場合は、その辺上のすべての点が最適解になります（最適解が無数に存在）。
シンプレックス法
変数が多いと図は描けないため、代数的に頂点をたどるシンプレックス法を使います。スラック変数を加えた標準形から出発し、原点など1つの頂点（実行可能基底解）から始めます。目的関数を改善できる変数を1つ選んで増やし（入る変数）、どの制約が最初に限界に達するかを比の計算（最小比テスト）で調べ、その制約に対応する変数を0にします（出る変数）。これで隣の頂点に移ります。この操作を、どの変数を増やしても目的関数が改善しなくなるまで繰り返せば最適解です。
内点法
シンプレックス法が領域の境界（頂点）をたどるのに対し、内点法は領域の内部を通って最適解に近づく方法です。大規模な問題で効率がよいことが知られています。
整理しておきたいポイント
| 解法 | 考え方 | 向いている場面 |
|---|---|---|
| 図解法 | 領域を図示し、等利益線を平行移動して頂点を探す | 変数が2つの問題。直感的な理解 |
| シンプレックス法 | 隣り合う頂点へ、目的関数が改善する方向に移動を繰り返す | 変数が多い一般の線形計画問題 |
| 内点法 | 実行可能領域の内部を通って最適解に近づく | 大規模な問題 |
具体例で確認
次の問題を解きます。目的関数 5x ＋ 4y を最大化、制約条件 6x ＋ 4y ≦ 24、x ＋ 2y ≦ 6、x ≧ 0、y ≧ 0。
図解法
頂点は(0, 0)、(4, 0)、(3, 1.5)、(0, 3)の4つです。(3, 1.5)は2本の制約6x＋4y＝24とx＋2y＝6の交点です。目的関数の値はそれぞれ0、20、21、12なので、最適解はx＝3、y＝1.5、最大値21です。
シンプレックス法の流れ
- 出発点は原点(0, 0)で目的関数0。係数が大きいxを増やす（入る変数）。
- 最小比テスト：24÷6＝4、6÷1＝6 → 小さい4が上限。1本目の制約が先に効き、頂点(4, 0)へ移動（目的関数20）。
- この頂点で目的関数を書き直すと、20 ＋ (2/3)y － (5/6)s1 となり、yの係数が正なのでyを増やせば改善する。
- 2本目の制約が効くのはy＝1.5のときで、頂点(3, 1.5)へ移動（目的関数21）。
- ここではどの変数を増やしても改善しないので、これが最適解。
動画で解説
この論点は、証券アナリストアカデミーのYouTubeで解説しています。テキストとあわせて確認してください（動画「線形計画問題の標準的定式化と代表的な解法について理解する」）。
試験で問われやすいポイント
- 図解法で、実行可能領域の頂点を求め、目的関数の値を比較して最適解を選ぶ計算が問われやすいです。
- シンプレックス法は頂点から隣の頂点へ移動する方法であり、領域の内部を通るのは内点法である、という対比に注意しましょう。
- シンプレックス法の入る変数・出る変数（最小比テスト）の考え方を押さえておきましょう。
- 等利益線が辺と平行なら最適解が無数、領域が空なら実行不能、どこまでも改善できれば非有界という特殊ケースも確認しておきましょう。
要点まとめ
- 変数2つなら図解法で頂点を比べる
- シンプレックス法は頂点をたどって改善を繰り返す
- 改善できる変数がなくなった頂点が最適解
- 内点法は領域の内部から最適解に近づく
証券アナリストアカデミーのYouTube（@cma-fa-academy）では、学習ポイントに沿って論点を1つずつ解説しています。
※学習ポイントは日本証券アナリスト協会「【2026年度】CMA資格の取得に求められる主要学習事項と学習ポイント」より引用しています。
