「限られた条件のもとで利益を最大にするには？」── 線形計画法は、連立不等式が定める領域内で一次式（目的関数）の最大値・最小値を求める方法です。
直線の平行移動という幾何学的なアイデアが、最適化問題を鮮やかに解決します。
日常生活やビジネスでは、「限られた資源のもとで利益を最大にする」「コストを最小にする」といった問題が数多く現れます。こうした最適化問題のうち、条件も目的もすべて「一次式」で表されるものを扱うのが線形計画法（Linear Programming, LP）です。
線形計画法は、次の3つの要素で構成されます。
制約条件を満たす点 $(x, y)$ の集合が実行可能領域（feasible region）であり、この領域内で目的関数 $k$ の値が最大（または最小）になる点を見つけるのが目標です。
たとえば、あるパン屋が食パンとクロワッサンを作るとします。小麦粉と時間に限りがあるとき、利益を最大にするにはそれぞれ何個ずつ作ればよいか、という問題は典型的な線形計画法の問題です。
目的関数：$k = ax + by$ を最大化（または最小化）
制約条件：
$$\begin{cases} a_1 x + b_1 y \leq c_1 \\ a_2 x + b_2 y \leq c_2 \\ \quad \vdots \\ x \geq 0, \quad y \geq 0 \end{cases}$$
制約条件が定める領域内で、目的関数の最大値・最小値を求めます。
線形計画法の最も重要な定理は、目的関数の最大値・最小値は、実行可能領域の頂点（角の点）で達成されるということです。
実行可能領域が有界な凸多角形であるとき、一次式の最大・最小は必ずいずれかの頂点で実現します。したがって、すべての頂点で目的関数の値を計算し、比較すればよいのです。
目的関数 $k = ax + by$ を変形すると、
$$y = -\frac{a}{b}x + \frac{k}{b} \quad (b \neq 0)$$
これは傾き $-\dfrac{a}{b}$、$y$ 切片 $\dfrac{k}{b}$ の直線の方程式です。$k$ の値を変えると、傾きが同じで $y$ 切片だけが変わるので、平行な直線の族が得られます。
$k$ を大きくすると $y$ 切片 $\dfrac{k}{b}$ が大きくなり、直線は上に平行移動します（$b > 0$ の場合）。逆に $k$ を小さくすると直線は下に移動します。
したがって、$k$ の最大値を求めるには、直線 $ax + by = k$ を実行可能領域と共有点をもつ範囲で、できるだけ上に（$b > 0$ なら）移動させればよいのです。
Step 1. 制約条件の連立不等式から実行可能領域を図示する。
Step 2. 目的関数 $ax + by = k$ を直線として描く（例えば $k = 0$ のとき）。
Step 3. この直線を平行移動させ、実行可能領域と共有点をもつ最後の位置を見つける。
Step 4. その位置での接点（頂点）の座標から $k$ の最大値（最小値）を求める。
例題：次の条件のもとで $k = x + 2y$ の最大値を求めよ。
$$x + y \leq 6, \quad x + 3y \leq 12, \quad x \geq 0, \quad y \geq 0$$
解：
実行可能領域の頂点は、連立不等式の境界線の交点を求めることで得られます。
直線 $x + 2y = k$ は傾き $-\dfrac{1}{2}$ の直線です。$k$ を大きくすると直線は右上に移動します。この直線が実行可能領域と共有点をもつ限界が、点 $\mathrm{B}(3, 3)$ を通るときです。
$$k = 3 + 2 \times 3 = 9$$
よって、$k$ の最大値は $9$（$x = 3$, $y = 3$ のとき）。
目的関数 $k = ax + by$ の最大値・最小値は、直線 $ax + by = k$ を平行移動して実行可能領域と最後に接する位置で得られる。
直線の傾きと領域の形状から、どの頂点で最大・最小が実現するかが幾何学的にわかります。
実行可能領域が有界（閉じた多角形）でない場合、目的関数に最大値や最小値が存在しないことがあります。
✗ 誤り：「領域内で最大値は必ず存在する」と思い込む
✓ 正しい：領域が非有界の場合、直線を際限なく移動できるため最大値（または最小値）が存在しないことがある
たとえば制約条件が $x \geq 0$, $y \geq 0$, $x + y \geq 2$ のとき、領域は右上に無限に広がるので $k = x + y$ の最大値は存在しません。
実行可能領域が凸多角形であるとき、一次関数は凸多角形の辺の上や内部では「端（頂点）よりも大きい（小さい）値をとることはない」という性質があります。これは一次関数が直線的に変化し、途中で折り返すことがないからです。
一次関数 $k = ax + by$ は平面上で「一定の方向に値が増加する」関数です。凸多角形の辺の上では $k$ は単調に変化するので、辺の両端の頂点でのどちらかが辺上の最大（最小）です。
多角形全体で考えても、最大・最小はいずれかの辺の端点、すなわち頂点で達成されます。
例題：次の条件のもとで $k = 2x + 3y$ の最大値と最小値を求めよ。
$$x + y \leq 5, \quad 2x + y \leq 8, \quad x \geq 0, \quad y \geq 0$$
解：頂点を求めます。
| 頂点 | $(x, y)$ | $k = 2x + 3y$ |
|---|---|---|
| $\mathrm{O}$ | $(0, 0)$ | $0$ |
| $\mathrm{A}$ | $(4, 0)$ | $8$ |
| $\mathrm{B}$ | $(3, 2)$ | $12$ |
| $\mathrm{C}$ | $(0, 5)$ | $15$ |
よって、最大値は $15$（点 $\mathrm{C}(0, 5)$ のとき）、最小値は $0$（原点 $\mathrm{O}(0, 0)$ のとき）。
頂点を1つでも見落とすと、最大値・最小値を間違える可能性があります。特に注意すべきケースは以下の通りです。
✗ 誤り：境界線の交点だけを求め、領域内にあるかどうかを確認しない
✓ 正しい：境界線の交点を求めたら、すべての制約条件を満たすかどうかを確認する
また、座標軸との交点（$x = 0$ や $y = 0$ との交点）を頂点として数え忘れることもよくあるミスです。必ず領域を図示して頂点を確認しましょう。
実行可能領域が有界な凸多角形のとき、一次式 $k = ax + by$ の最大値・最小値は頂点で達成される。
$$k_{\max} = \max\{k(\text{頂点}_1),\, k(\text{頂点}_2),\, \ldots,\, k(\text{頂点}_n)\}$$
$$k_{\min} = \min\{k(\text{頂点}_1),\, k(\text{頂点}_2),\, \ldots,\, k(\text{頂点}_n)\}$$
頂点の個数は有限なので、すべて調べ上げることが可能です。
目的関数が $k = x + y$ の場合、直線 $x + y = k$ は傾き $-1$ の直線です。$k$ を大きくすると直線は右上に平行移動します。
例：$x \geq 0$, $y \geq 0$, $x + 2y \leq 8$, $2x + y \leq 10$ のもとで $x + y$ の最大値を求めよ。
頂点 $(0,0)$, $(5,0)$, $(4,2)$, $(0,4)$ を求め、各頂点で $x+y$ を計算すると、点 $(4,2)$ で $x + y = 6$ が最大です。
目的関数の係数によって、直線の傾きが変わるので、最適解の頂点も変わります。領域は同じでも、目的関数が異なれば最適解は異なり得ることに注意しましょう。
例：同じ領域で $k = 2x + 3y$ の最大値を求めると、直線の傾きは $-\dfrac{2}{3}$ となり、最適解が変わる場合があります。
$k = \dfrac{y}{x}$（ただし $x > 0$）の最大・最小を求める問題は、$k$ が原点と点 $(x, y)$ を結ぶ直線の傾きであることに着目します。
$y = kx$ は原点を通る傾き $k$ の直線なので、この直線を原点を中心に回転させて、実行可能領域と接する限界の傾きを求めます。
$k = \dfrac{y - q}{x - p}$ の最大・最小は、点 $(p, q)$ と領域内の点 $(x, y)$ を結ぶ直線の傾きの最大・最小に対応する。
特に $k = \dfrac{y}{x}$ は原点からの傾きです。直線 $y = kx$ を回転させて、領域と最後に共有点をもつ位置を見つけます。
目的関数が $\dfrac{y - q}{x - p}$ の形のとき、定点 $(p, q)$ が領域の外にあることが多いです。定点から領域への接線の傾きが最大値・最小値に対応します。
例：$k = \dfrac{y + 1}{x - 2}$ の最大値を求めるには、点 $(2, -1)$ から領域への見通しを考えます。
| パターン | 目的関数 | 幾何学的解釈 |
|---|---|---|
| 一次式型 | $k = ax + by$ | 直線 $ax + by = k$ の平行移動 |
| 傾き型 | $k = \dfrac{y}{x}$ | 原点を通る直線 $y = kx$ の回転 |
| 定点傾き型 | $k = \dfrac{y - q}{x - p}$ | 定点 $(p,q)$ を通る直線の回転 |
線形計画法の問題を解く鍵は、目的関数を直線の方程式として解釈し、その幾何学的な動き（平行移動・回転）で最適解を見つけることです。
「$k$ を動かすと何が起こるか」を常に図形的に考える習慣をつけましょう。
実際の線形計画法の問題は、文章から条件を読み取って数式に翻訳する力が求められます。
例題：ある工場で製品 A と製品 B を生産する。製品 A は1個あたり利益 $3$ 万円、製品 B は1個あたり利益 $5$ 万円である。原料の制約として $2x + y \leq 14$、労働時間の制約として $x + 3y \leq 12$ がある。$x \geq 0$, $y \geq 0$ のとき、利益 $k = 3x + 5y$ を最大にせよ。
解：頂点を求めます。
よって、$x = 6$, $y = 2$ のとき利益は最大 $28$ 万円です。
$k = \dfrac{y}{x}$ のような分数型の問題では、「傾き」として解釈して解きます。
例題：$x + y \leq 6$, $x \geq 1$, $y \geq 0$ のもとで $k = \dfrac{y}{x}$ の最大値を求めよ。
解：$k = \dfrac{y}{x}$ は原点と点 $(x, y)$ を結ぶ直線の傾きです。直線 $y = kx$ を原点を中心に反時計回りに回転させると、領域との最後の共有点で $k$ が最大になります。
$x + y = 6$ と $x = 1$ の交点 $(1, 5)$ で $k = \dfrac{5}{1} = 5$ が最大です。
入試では「$x$, $y$ が整数のとき」という制約がつく場合があります。この場合、最適解は必ずしも頂点ではなく、頂点付近の格子点（整数座標の点）を調べる必要があります。
例題：$x + y \leq 5$, $x \geq 0$, $y \geq 0$, $x, y$ は整数のとき、$k = 3x + 2y$ の最大値を求めよ。
解：整数制約がない場合、頂点 $(5, 0)$ で $k = 15$ が最大です。この場合 $(5, 0)$ は整数点なのでそのまま最大値 $15$ が答えです。しかし、頂点が整数点でないときは、頂点付近の格子点をすべて調べる必要があります。
整数制約のある線形計画法では、「連続の最適解に最も近い整数点」が必ずしも最適であるとは限りません。
✗ 誤り：頂点 $(3.5, 2.5)$ に近い $(4, 2)$ や $(3, 3)$ だけを調べる
✓ 正しい：直線を少しずらしながら、制約を満たすすべての整数点の候補を調べる
高校では2変数の線形計画法を図形的に解きますが、実際のビジネスや工学では変数が数百〜数万にもなります。このような大規模な線形計画法を効率的に解くアルゴリズムが、1947年にダンツィグが考案したシンプレックス法（単体法）です。
シンプレックス法は「頂点から隣の頂点へ移動しながら目的関数を改善していく」方法で、高校で学ぶ「頂点で最適解が得られる」という事実を基礎としています。
線形計画法はオペレーションズ・リサーチ（OR）と呼ばれる分野の中核であり、物流の最適化、金融ポートフォリオの設計、航空便のスケジューリングなど、幅広い分野で活用されています。
Q1. 線形計画法において、目的関数の最大・最小が達成される位置はどこか。
Q2. 制約条件 $x + y \leq 4$, $x \geq 0$, $y \geq 0$ のもとで $k = x + 3y$ の最大値を求めよ。
Q3. 目的関数 $k = 2x + y$ を $k$ の値を変えて図示すると、どのような直線の族になるか。
Q4. $k = \dfrac{y}{x}$（$x > 0$）の最大・最小を求めるとき、$k$ は幾何学的に何を表すか。
Q5. 実行可能領域が非有界のとき、目的関数の最大値について何がいえるか。
次の連立不等式の表す領域において、$k = x + 2y$ の最大値と最小値を求めよ。
$$x + y \leq 6, \quad x - y \leq 2, \quad x \geq 0, \quad y \geq 0$$
実行可能領域の頂点を求める。
$x + y = 6$ と $x - y = 2$ の交点：$2x = 8$ より $x = 4$, $y = 2$ → $(4, 2)$
$x - y = 2$ と $y = 0$ の交点：$(2, 0)$
$x + y = 6$ と $x = 0$ の交点：$(0, 6)$
原点 $(0, 0)$
各頂点で $k = x + 2y$ を計算：
$(0, 0)$：$k = 0$、$(2, 0)$：$k = 2$、$(4, 2)$：$k = 8$、$(0, 6)$：$k = 12$
よって、最大値 $12$（$(0, 6)$ のとき）、最小値 $0$（$(0, 0)$ のとき）。
方針：問題の条件を整理し、段階的に計算を進める。
方針：問題の条件を整理し、段階的に計算を進める。