「限られた条件のもとで利益を最大にするには？」── 線形計画法は、連立不等式が定める領域内で一次式（目的関数）の最大値・最小値を求める方法です。
直線の平行移動という幾何学的なアイデアが、最適化問題を鮮やかに解決します。
日常生活やビジネスでは、「限られた資源のもとで利益を最大にする」「コストを最小にする」といった問題が数多く現れます。こうした最適化問題のうち、条件も目的もすべて「一次式」で表されるものを扱うのが線形計画法（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)$ のとき）。
連立不等式 $x + 2y \leq 10$, $3x + y \leq 12$, $x \geq 0$, $y \geq 0$ の表す領域を $D$ とする。点 $(x, y)$ が領域 $D$ 内を動くとき、次の値の最大値を求めよ。
(1) $k = 3x + 4y$
(2) $k = x + 5y$
頂点を求める。
$\mathrm{O}(0, 0)$、$\mathrm{A}(4, 0)$：$3x + y = 12$ と $y = 0$ の交点
$\mathrm{B}$：$x + 2y = 10$ と $3x + y = 12$ の連立。$x + 2y = 10$ より $x = 10 - 2y$。代入して $3(10-2y) + y = 12$ → $30 - 6y + y = 12$ → $y = \dfrac{18}{5}$, $x = \dfrac{14}{5}$ → $\mathrm{B}\!\left(\dfrac{14}{5}, \dfrac{18}{5}\right)$
$\mathrm{C}(0, 5)$：$x + 2y = 10$ と $x = 0$ の交点
(1) 各頂点で $k = 3x + 4y$：
$\mathrm{O}$：$0$、$\mathrm{A}$：$12$、$\mathrm{B}$：$3 \cdot \dfrac{14}{5} + 4 \cdot \dfrac{18}{5} = \dfrac{42 + 72}{5} = \dfrac{114}{5}$、$\mathrm{C}$：$20$
最大値は $\dfrac{114}{5}$（点 $\mathrm{B}$ のとき）。
(2) 各頂点で $k = x + 5y$：
$\mathrm{O}$：$0$、$\mathrm{A}$：$4$、$\mathrm{B}$：$\dfrac{14}{5} + 5 \cdot \dfrac{18}{5} = \dfrac{14 + 90}{5} = \dfrac{104}{5}$、$\mathrm{C}$：$25$
最大値は $25$（点 $\mathrm{C}$ のとき）。
同じ領域でも目的関数の係数が変わると、最適解が別の頂点に移ります。(1)では直線の傾きが $-\dfrac{3}{4}$ で頂点 $\mathrm{B}$ が最適、(2)では傾きが $-\dfrac{1}{5}$ で頂点 $\mathrm{C}$ が最適になります。
連立不等式 $y \leq 2x$, $x + y \leq 6$, $y \geq 0$ の表す領域内の点 $(x, y)$ について、$k = \dfrac{y + 2}{x + 1}$ の最大値を求めよ。
$k = \dfrac{y + 2}{x + 1}$ は、点 $(-1, -2)$ と点 $(x, y)$ を結ぶ直線の傾きを表す。
実行可能領域の頂点は $(0, 0)$, $(6, 0)$, $(2, 4)$。
$y + 2 = k(x + 1)$ すなわち $y = kx + k - 2$ が定点 $(-1, -2)$ を通る直線。
この直線を $(-1, -2)$ を中心に回転させ、領域と最後に接する位置を見つける。
各頂点での $k$ の値：
$(0, 0)$：$k = \dfrac{0+2}{0+1} = 2$
$(6, 0)$：$k = \dfrac{0+2}{6+1} = \dfrac{2}{7}$
$(2, 4)$：$k = \dfrac{4+2}{2+1} = \dfrac{6}{3} = 2$
よって最大値は $2$（$(0,0)$ または $(2,4)$ のとき）。
$k = \dfrac{y + 2}{x + 1}$ は定点 $(-1, -2)$ からの傾き型の問題です。定点が領域の外にあることを確認し、定点から各頂点への傾きを計算して最大値を求めます。この場合、$(0,0)$ と $(2,4)$ を通る直線がちょうど傾き $2$ であり、領域の辺 $y = 2x$ 上のすべての点で $k = 2$ が実現します。
連立不等式 $x + y \leq 7$, $2x + y \leq 10$, $x \geq 0$, $y \geq 0$ の表す領域内で、$x$, $y$ がともに整数であるとき、次の問いに答えよ。
(1) 制約を満たす整数点 $(x, y)$ のうち、$k = 3x + 5y$ を最大にする点を求め、最大値を答えよ。
(2) 制約を満たす整数点 $(x, y)$ のうち、$k = 4x + y$ を最大にする点を求め、最大値を答えよ。
まず連続の場合の頂点を求める。
$\mathrm{O}(0, 0)$, $\mathrm{A}(5, 0)$, $\mathrm{B}(3, 4)$：$x + y = 7$ と $2x + y = 10$ の交点, $\mathrm{C}(0, 7)$
(1) $k = 3x + 5y$ の場合
連続の頂点での値：$\mathrm{O}$：$0$, $\mathrm{A}$：$15$, $\mathrm{B}(3,4)$：$29$, $\mathrm{C}$：$35$
$\mathrm{C}(0, 7)$ は整数点であるから、最大値は $35$（$(0, 7)$ のとき）。
(2) $k = 4x + y$ の場合
連続の頂点での値：$\mathrm{O}$：$0$, $\mathrm{A}(5,0)$：$20$, $\mathrm{B}(3,4)$：$16$, $\mathrm{C}$：$7$
$\mathrm{A}(5, 0)$ は整数点であるから、最大値は $20$（$(5, 0)$ のとき）。
この問題では、連続の最適解がそのまま整数点であったため、整数制約の影響はありませんでした。しかし、もし連続の最適解が非整数（たとえば $\left(\dfrac{7}{3}, \dfrac{14}{3}\right)$ など）であった場合は、最適解付近の整数点をすべて列挙して比較する必要があります。
一般に整数計画問題（Integer Programming）は連続の線形計画法よりもはるかに難しく、大学レベルの数理最適化で詳しく学びます。