第3章線形計画法（最適化） | Lemma

この章の目標

線形計画問題を標準形に直し、基底解・頂点・被約費用の言葉で書き表せる

実行可能基底解と頂点が同じものであることを証明し、最適解が（存在すれば）頂点から選べることを説明できる

単体法のピボットを計算でき、退化と巡回・ブランドの規則・計算量について正確に述べられる

ファルカスの補題から双対定理を証明し、相補性条件を使って最適性を確かめられる

双対変数をシャドウプライスとして解釈し、その有効範囲と退化したときの注意を説明できる

前提：第2章、02-linear-algebra 第2章。定式化の例は第1章で見た。3.6 節では第2章の点と閉凸集合の分離定理（定理 2.6）を使う。

工場で何をいくつ作るか、倉庫から店へ何をどれだけ運ぶか、誰をどの仕事に割り当てるか。こうした計画の多くは、「一次式で表される費用（利益）を、一次式の等式・不等式の制約のもとで最小化（最大化）する」という形に書ける。これが線形計画問題 (linear programming problem, LP) である。変数が数百万ある問題も日常的に解かれており、最適化の中でもっとも広く使われている問題の一つである。

線形計画問題には著しい性質が二つある。一つは、最適解が（存在すれば）実行可能領域である多面体の頂点から選べることで、これが頂点から頂点へ移って最適解を探す単体法 (simplex method) の基礎になる。もう一つは双対性で、どの線形計画問題にも最適値の一致する双対問題が対応する。双対問題の解は主問題の解が最適であることの証明書であり（第1章例 1.2 の生産計画で、制約を $9/5$ 倍と $2/5$ 倍して足したのがその例）、「資源を 1 単位増やすと最適値がどれだけ改善するか」（シャドウプライス）を表す。双対性は第4章で非線形の問題に拡張される。

ベクトル $x, y$ について $x \geq y$ は各成分で $x_j \geq y_j$ となることを表す。 $A^{\top}$ は転置（02-linear-algebra 第1章の ${}^tA$ と同じもの）、 $\mathbf{1}$ は成分がすべて $1$ のベクトルである。

3.1 線形計画問題と標準形

例 3.1（生産計画）製品 P, Q の 1 単位あたりの利益は 40 千円、30 千円である。P を 1 単位作るには機械 2 時間・作業 1 時間・原料 1 単位、Q には機械 1 時間・作業 1 時間が必要で（原料は使わない）、1 週間に使えるのは機械 100 時間、作業 80 時間、原料 40 単位までとする。生産量を $x_1, x_2$ とすると、問題は

\begin{aligned} \text{maximize} \quad & 40x_1 + 30x_2 \\ \text{subject to} \quad & 2x_1 + x_2 \leq 100, \quad x_1 + x_2 \leq 80, \quad x_1 \leq 40, \quad x_1, x_2 \geq 0 \end{aligned}

である。実行可能領域は頂点 $(0, 0)$ , $(40, 0)$ , $(40, 20)$ , $(20, 60)$ , $(0, 80)$ の五角形で、利益はそれぞれ $0, 1600, 2200, 2600, 2400$ である。最適解が頂点から選べること（定理 3.11）を認めれば、最適解は $(20, 60)$ 、最大利益は $2600$ 千円である。この例は本章を通して使う。

定義 3.2（線形計画問題）一次関数 $c^{\top}x$ を有限個の一次の等式・不等式のもとで最小化または最大化する問題を線形計画問題という。制約を満たす $x$ を実行可能解 (feasible solution)、その全体を実行可能領域 (feasible region) という。実行可能解がないとき実行不能 (infeasible)、最小化問題で目的関数がいくらでも小さくなる（最大化問題なら大きくなる）とき非有界 (unbounded) という。

等式は 2 つの不等式とみなせるので、実行可能領域は第2章の意味の多面体（閉凸集合）である。理論は次の形にそろえて述べる。

定義 3.3（標準形, standard form） $A \in \mathbb{R}^{m \times n}$ , $b \in \mathbb{R}^m$ , $c \in \mathbb{R}^n$ に対する次の問題を標準形の線形計画問題という。
$\text{(P)} \qquad \text{minimize} \quad c^{\top}x \qquad \text{subject to} \quad Ax = b, \quad x \geq 0$

命題 3.4（標準形への変換）任意の線形計画問題は次の書き換えで標準形になる。書き換えの前後で実行可能解は目的関数の値を保って対応する（一方の実行可能解から他方の実行可能解が作れる）ので、最適解の有無と最適値（最大化を最小化に直した符号を除く）は変わらない。

最大化 $c^{\top}x$ は最小化 $(-c)^{\top}x$ に直す。

不等式 $a^{\top}x \leq \beta$ は、新しい変数 $s \geq 0$ （スラック変数, slack variable）を加えて $a^{\top}x + s = \beta$ とする。 $a^{\top}x \geq \beta$ は $a^{\top}x - s = \beta$ , $s \geq 0$ とする。

符号の制約のない変数（自由変数） $x_j$ は $x_j = x_j^{+} - x_j^{-}$ , $x_j^{\pm} \geq 0$ と置き換える。

証明. 2： $a^{\top}x \leq \beta$ なら $s = \beta - a^{\top}x \geq 0$ とおけばよく、逆に $(x, s)$ が新しい制約を満たせば $a^{\top}x = \beta - s \leq \beta$ 。目的関数は $s$ を含まない（ $\geq$ も同様）。3： $x_j^{\pm} = \max(\pm x_j, 0)$ とおけばよく、逆に $x_j^{\pm} \geq 0$ からは $x_j = x_j^{+} - x_j^{-}$ を作る。目的関数と制約は $x_j^{+} - x_j^{-}$ を通してしか新しい変数によらない。1 は明らか。 $\square$

例 3.5 例 3.1 は、最大化を $-40x_1 - 30x_2$ の最小化に直し、スラック変数 $s_1, s_2, s_3$ （それぞれ機械・作業・原料の余り）を加えると、変数 $(x_1, x_2, s_1, s_2, s_3)$ の標準形

\text{minimize} \quad -40x_1 - 30x_2 \qquad \text{subject to} \quad \begin{pmatrix} 2 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 \end{pmatrix}\begin{pmatrix} x_1 \\ x_2 \\ s_1 \\ s_2 \\ s_3 \end{pmatrix} = \begin{pmatrix} 100 \\ 80 \\ 40 \end{pmatrix}, \quad x_1, x_2, s_1, s_2, s_3 \geq 0

になる。

注意 3.6（行の階数）標準形で $\operatorname{rank} A < m$ とする。 $Ax = b$ が解をもたなければ問題は実行不能である。解 $x$ をもてば、 $A$ の第 $i$ 行 $\alpha_i$ が他の行の一次結合 $\alpha_i = \sum_{k \neq i} t_k\alpha_k$ となっているとき $b_i = \alpha_ix = \sum_{k \neq i} t_kb_k$ なので、第 $i$ の等式は他の等式から従い、取り除いても実行可能領域は変わらない。そこで基底を使う議論（基底解・単体法・定理 3.30 の 2）では $\operatorname{rank} A = m$ （特に $m \leq n$ ）を仮定する。定理 3.8 の 1〜3 の同値性、補題 3.10、定理 3.11、3.6 節以降の双対性の理論にはこの仮定は要らない。

3.2 基底解と頂点

例 3.1 の最適解は五角形の「角」にあった。この角を代数的にとらえるのが基底解である。以下、標準形の実行可能領域を $P = \lbrace x \in \mathbb{R}^n \mid Ax = b,\ x \geq 0 \rbrace$ 、 $A$ の第 $j$ 列を $a_j$ と書き、 $x$ の台 (support) を $\operatorname{supp} x = \lbrace j \mid x_j \neq 0 \rbrace$ とする。

定義 3.7（基底解）（ $\operatorname{rank} A = m$ とする） $\lbrace 1, \dots, n \rbrace$ の $m$ 元部分集合 $B$ で、列 $a_j$ （ $j \in B$ ）が一次独立であるもの、すなわち $m$ 次正方行列 $A_B = (a_j)_{j \in B}$ が正則であるものを基底 (basis) といい、残りの添字の集合を $N$ とする。 $x_N = 0$ , $x_B = A_B^{-1}b$ で定まる $x$ を $B$ の基底解 (basic solution)、 $x_j$ （ $j \in B$ ）を基底変数、 $x_j$ （ $j \in N$ ）を非基底変数という。基底解が $x \geq 0$ を満たすとき実行可能基底解 (basic feasible solution) といい、さらに $x_B$ の成分に $0$ があるとき退化している (degenerate) という。

多面体の端点（第2章 2.1 節：凸集合の 2 点を結ぶ線分の内部の点にならない点）を頂点 (vertex) とよぶ。

定理 3.8（基底解と頂点） $x \in P$ について、次は同値である。

$x$ は $P$ の頂点である。

列 $a_j$ （ $j \in \operatorname{supp} x$ ）は一次独立である。

ある $c \in \mathbb{R}^n$ について、 $x$ は $P$ 上で $c^{\top}x$ を最小にするただ一つの点である。

特に $P$ の頂点は有限個である。さらに $\operatorname{rank} A = m$ ならば、これらは「 $x$ はある基底の実行可能基底解である」とも同値で、頂点は $\binom{n}{m}$ 個以下である。

証明. (3 ⇒ 1) $x = (1 - t)y + tz$ （ $y, z \in P$ , $0 < t < 1$ ）とすると、 $c^{\top}x = (1 - t)c^{\top}y + tc^{\top}z$ と $c^{\top}y, c^{\top}z \geq c^{\top}x$ より $c^{\top}y = c^{\top}z = c^{\top}x$ で、一意性から $y = z = x$ 。

(1 ⇒ 2) 対偶を示す。 $S = \operatorname{supp} x$ の列が一次従属なら、 $\sum_{j \in S} d_ja_j = 0$ となる $0$ でない $(d_j)_{j \in S}$ があり、 $j \notin S$ では $d_j = 0$ とおくと $Ad = 0$ , $d \neq 0$ 。 $\varepsilon = \min\lbrace x_j/\lvert d_j \rvert \mid d_j \neq 0 \rbrace > 0$ とすると $x \pm \varepsilon d \geq 0$ , $A(x \pm \varepsilon d) = b$ で、 $x = \frac{1}{2}(x + \varepsilon d) + \frac{1}{2}(x - \varepsilon d)$ は $P$ の相異なる 2 点の中点だから頂点でない。

(2 ⇒ 3) $c_j = 0$ （ $j \in S$ ）、 $c_j = 1$ （ $j \notin S$ ）とおく。 $y \in P$ なら $c^{\top}y = \sum_{j \notin S} y_j \geq 0 = c^{\top}x$ で、等号は $y_j = 0$ （ $j \notin S$ ）のときに限る。そのとき $\sum_{j \in S} y_ja_j = b = \sum_{j \in S} x_ja_j$ で、列の一次独立性から $y = x$ 。同じ理由で、頂点 $x$ は台 $S$ から（ $\sum_{j \in S} x_ja_j = b$ の唯一の解として）決まるので、頂点は $2^n$ 個以下で有限個である。

（基底解との同値） $x$ が基底 $B$ の実行可能基底解なら $\operatorname{supp} x \subset B$ で、 $A_B$ の列の一部として 2 が成り立つ。逆に 2 を仮定する。 $\operatorname{rank} A = m$ より $A$ の列は $\mathbb{R}^m$ を張るので、 $\lbrace a_j \rbrace_{j \in \operatorname{supp} x}$ が $\mathbb{R}^m$ を張らない限り、その張る空間に入らない列 $a_k$ があり、 $a_k$ を加えても一次独立である（02-linear-algebra 第2章命題 2.21 の 2）。これを繰り返して $m$ 本の一次独立な列に延長し、その添字集合を $B$ とすれば、 $x_N = 0$ と $A_Bx_B = b$ より $x_B = A_B^{-1}b$ で、 $x$ は $B$ の実行可能基底解である。基底は $\binom{n}{m}$ 個以下で、基底解は基底で決まるから、頂点の個数も $\binom{n}{m}$ 以下である。 $\square$

退化した頂点では、 $\operatorname{supp} x$ を基底に延長する方法が複数あるので、一つの頂点に複数の基底が対応する。

例 3.9 例 3.5 で、5 列から 3 列を選ぶ $\binom{5}{3} = 10$ 通りのうち、 $\lbrace x_2, s_1, s_2 \rbrace$ の 3 列は第 3 成分がすべて $0$ で一次従属なので基底にならない。残る 9 個の基底解のうち実行可能なのは 5 個で、例 3.1 の 5 つの頂点に一対一に対応する（どれも非退化。計算機で列挙して確かめた）。たとえば基底 $\lbrace x_1, x_2, s_3 \rbrace$ の基底解 $(x_1, x_2, s_1, s_2, s_3) = (20, 60, 0, 0, 20)$ は頂点 $(20, 60)$ で、機械と作業を使い切り原料が 20 余る。基底 $\lbrace x_1, x_2, s_1 \rbrace$ の基底解 $(40, 40, -20, 0, 0)$ は利益 $2800$ を与えるが、機械が 20 時間足りず実行不能である。頂点の数は変数と制約が増えると急速に増えるので、すべてを列挙できるのは小さな問題に限られる。

3.3 最適解の存在と頂点

補題 3.10（台を減らす） $x \in P$ で、列 $a_j$ （ $j \in \operatorname{supp} x$ ）が一次従属であるとする。このとき $Ad = 0$ , $d \neq 0$ , $\operatorname{supp} d \subset \operatorname{supp} x$ となる $d$ が存在する。 $d$ が負の成分をもてば、 $t^{\ast} = \min\lbrace x_j/(-d_j) \mid d_j < 0 \rbrace > 0$ について $x + t^{\ast}d \in P$ かつ $\operatorname{supp}(x + t^{\ast}d) \subsetneq \operatorname{supp} x$ である。

証明. $d$ の存在は定理 3.8 の証明（1 ⇒ 2）と同じである。 $d_j < 0$ なら $j \in \operatorname{supp} x$ なので $x_j > 0$ で、 $t^{\ast} > 0$ 。 $0 \leq t \leq t^{\ast}$ なら、 $d_j \geq 0$ の成分は $x_j + td_j \geq 0$ 、 $d_j < 0$ の成分も $t \leq x_j/(-d_j)$ より非負で、 $A(x + td) = b$ 。 $t = t^{\ast}$ では最小値を与える $j$ で成分が $0$ になり、 $\operatorname{supp} d \subset \operatorname{supp} x$ より台の外の成分は $0$ のままである。 $\square$

定理 3.11（線形計画法の基本定理）標準形 (P) が実行可能（ $P \neq \emptyset$ ）であるとする。

$P$ は頂点をもつ。

次のちょうど一方が成り立つ。(a) $d \geq 0$ , $Ad = 0$ , $c^{\top}d < 0$ を満たす $d$ が存在する。このとき $x \in P$ について $x + td \in P$ （ $t \geq 0$ ）で $c^{\top}(x + td) \to -\infty$ となり、(P) は非有界である。(b) (P) は最適解をもち、 $P$ の頂点の中に最適解がある。

特に $P$ が有界ならば、(P) は頂点で最適解をもつ。

証明. まず次を示す：(a) の $d$ が存在しなければ、任意の $x \in P$ に対し $c^{\top}v \leq c^{\top}x$ となる頂点 $v$ がある。 $\lvert \operatorname{supp} x \rvert$ に関する帰納法による。台の列が一次独立なら $x$ 自身が頂点である（定理 3.8）。そうでなければ補題 3.10 の $d$ をとる。 $-d$ も同じ条件を満たすので、符号を選んで $c^{\top}d \leq 0$ としてよい。このとき $d$ が負の成分をもたなければ、 $d \geq 0$ , $Ad = 0$ と (a) が成り立たないことから $c^{\top}d = 0$ で、 $d$ を $-d$ に取り替えれば負の成分をもつ（ $d \neq 0$ だから）。こうして $d$ は負の成分をもち $c^{\top}d \leq 0$ とできる。補題 3.10 の $x' = x + t^{\ast}d \in P$ は台が真に小さく、 $c^{\top}x' = c^{\top}x + t^{\ast}c^{\top}d \leq c^{\top}x$ なので、帰納法の仮定から $c^{\top}v \leq c^{\top}x'$ となる頂点 $v$ がある。

1： $c = 0$ とすれば (a) は起こらないので、 $P$ の点から頂点が得られる。2：(a) なら非有界なので (b) と両立しない。(a) が成り立たないとする。頂点は有限個（定理 3.8）で、1 より空でないので、 $c^{\top}v$ が最小の頂点 $v^{\ast}$ をとる。任意の $x \in P$ について $c^{\top}x \geq c^{\top}v \geq c^{\top}v^{\ast}$ となる頂点 $v$ があるので、 $v^{\ast}$ は最適解である。3： $d \neq 0$ , $d \geq 0$ , $Ad = 0$ なら $\lbrace x + td \mid t \geq 0 \rbrace \subset P$ は有界でないので、 $P$ が有界なら (a) は起こらない。 $\square$

したがって標準形の問題は、実行不能・非有界・頂点で最適解をもつのちょうど一つに当てはまる。一般の最適化問題と違い、「目的関数は下に有界なのに最小値に達しない」（ $\mathbb{R}$ 上の $e^{x}$ のような）ことは起こらない。

例 3.12 実行可能領域が非有界でも最適解をもつことはある。 $x_1 + 2x_2 \geq 2$ , $x \geq 0$ の領域は非有界だが、 $x_1 + x_2$ の最小値は頂点 $(0, 1)$ での $1$ である（頂点 $(2, 0)$ では $2$ ）。一方、 $x_1 - x_2 \leq 1$ , $x \geq 0$ のもとで $x_1 + x_2$ を最大化する問題は非有界である。標準形ではスラック変数の成分を $0$ とした $d = (1, 1, 0)$ が (a) の $d$ になる。

注意

「最適解は頂点にある」の正しい意味は「（最適解があれば）最適解の中に頂点がある」である。(1) 目的関数の等高線が辺と平行なら辺全体が最適解になり、頂点以外の最適解もある。(2) 一般の形の多面体は頂点をもたないことがある。半平面 $x_1 + x_2 \geq 1$ 上で $x_1 + x_2$ を最小化すると、直線 $x_1 + x_2 = 1$ 全体が最適解で、頂点はない。標準形では $x \geq 0$ のおかげで、実行可能なら必ず頂点がある（定理 3.11 の 1）。(3) 内点法（3.5 節）は、最適解が一意でないとき頂点でない最適解を返すことがある。

3.4 単体法

単体法は、実行可能基底解から出発し、目的関数の値が下がる「隣の」基底解へ移ることを繰り返す。基底 $B$ を固定し、 $Ax = b$ を $A_Bx_B + A_Nx_N = b$ と分けて $x_B$ について解き、目的関数 $c^{\top}x = c_B^{\top}x_B + c_N^{\top}x_N$ に代入すると、 $Ax = b$ を満たすすべての $x$ について

x_B = A_B^{-1}b - A_B^{-1}A_Nx_N, \qquad c^{\top}x = c_B^{\top}A_B^{-1}b + \sum_{j \in N}\bar{c}_jx_j

が成り立つ。ここで

\bar{c}_j = c_j - y^{\top}a_j \quad (j = 1, \dots, n), \qquad y = (A_B^{\top})^{-1}c_B

を基底 $B$ に関する被約費用 (reduced cost)、 $y$ を単体乗数 (simplex multiplier) という（ $j \in B$ では $\bar{c}_j = 0$ ）。非基底変数 $x_N$ を決めると基底変数と目的関数の値が決まる、という形のこの式を辞書 (dictionary) とよぶ。

命題 3.13（最適性の判定）基底 $B$ の実行可能基底解 $x$ について $\bar{c} \geq 0$ ならば、 $x$ は (P) の最適解である。

証明. $x' \in P$ なら、上の式より $c^{\top}x' = c_B^{\top}A_B^{-1}b + \sum_{j \in N}\bar{c}_jx'_j \geq c_B^{\top}A_B^{-1}b = c^{\top}x$ （ $x' \geq 0$ , $\bar{c} \geq 0$ ）。 $\square$

命題 3.14（ピボット） $x$ を基底 $B = \lbrace B(1), \dots, B(m) \rbrace$ の実行可能基底解とし、 $\bar{c}_q < 0$ となる $q \in N$ をとって $u = A_B^{-1}a_q$ とおく。 $d_q = 1$ , $d_{B(i)} = -u_i$ （ $i = 1, \dots, m$ ）、他の成分を $0$ とした $d$ は $Ad = 0$ , $c^{\top}d = \bar{c}_q$ を満たす。

$u \leq 0$ ならば $d \geq 0$ で、(P) は非有界である。

$u_i > 0$ となる $i$ があれば、次の最小値（比の判定, ratio test）を与える $i = \ell$ をとる。

$t^{\ast} = \min\left\lbrace \frac{x_{B(i)}}{u_i} \;\middle|\; u_i > 0 \right\rbrace$
このとき $B' = (B \setminus \lbrace B(\ell) \rbrace) \cup \lbrace q \rbrace$ は基底であり、 $x' = x + t^{\ast}d$ は $B'$ の実行可能基底解で、 $c^{\top}x' = c^{\top}x + t^{\ast}\bar{c}_q \leq c^{\top}x$ である。 $t^{\ast} > 0$ （たとえば $x$ が非退化）なら目的関数は真に減少する。

証明. $Ad = a_q - A_Bu = 0$ 、 $c^{\top}d = c_q - c_B^{\top}A_B^{-1}a_q = \bar{c}_q$ 。1 は定理 3.11 の (a) の場合である。2： $0 \leq t \leq t^{\ast}$ なら $x + td \geq 0$ （ $u_i \leq 0$ の成分は減らず、 $u_i > 0$ の成分は $t \leq x_{B(i)}/u_i$ の範囲で非負）で、 $A(x + td) = b$ 。 $x'$ の第 $B(\ell)$ 成分は $x_{B(\ell)} - t^{\ast}u_\ell = 0$ で、 $B'$ の外の成分はすべて $0$ である。 $a_q = A_Bu = \sum_i u_ia_{B(i)}$ で $u_\ell \neq 0$ なので、 $a_{B(\ell)}$ は $a_q$ と $a_{B(i)}$ （ $i \neq \ell$ ）の一次結合であり、これら $m$ 本の列は $\mathbb{R}^m$ を張る。よって一次独立で、 $B'$ は基底、 $x'$ はその基底解である。 $\square$

単体法は、実行可能基底解とその基底から始めて次を繰り返す。(i) $\bar{c}$ を計算し、 $\bar{c} \geq 0$ なら最適（命題 3.13）として終了する。(ii) $\bar{c}_q < 0$ となる $q$ を選ぶ（ $x_q$ を入る変数という）。(iii) $u = A_B^{-1}a_q$ を計算し、 $u \leq 0$ なら非有界として終了する。(iv) 比の判定で $\ell$ を選び（ $x_{B(\ell)}$ を出る変数という）、基底を $B'$ に替えて (i) に戻る。この基底の交換をピボット (pivot) という。

定理 3.15（有限終了）すべての実行可能基底解が非退化ならば、単体法は（(ii)・(iv) の選び方によらず）有限回の反復で、最適な実行可能基底解を見つけるか非有界であることを検出して終了する。

証明. 非退化なら $t^{\ast} > 0$ なので、各反復で目的関数の値は真に減少する。基底解は基底で決まるから、同じ基底が二度現れることはない。基底は有限個なので、反復は有限回で終わる。 $\square$

例 3.16（例 3.1 を単体法で解く）最大化問題のまま辞書を書くと、目的関数 $z$ の行で係数が正の非基底変数を入れればよい（最小化に直したときの $\bar{c}_j < 0$ にあたる）。最初の基底はスラック変数で、実行可能基底解は原点である。

\begin{aligned} s_1 &= 100 - 2x_1 - x_2 \\ s_2 &= 80 - x_1 - x_2 \\ s_3 &= 40 - x_1 \\ z &= 0 + 40x_1 + 30x_2 \end{aligned}

係数の大きい $x_1$ を入れる。 $x_1$ を増やすと $s_1, s_2, s_3$ はそれぞれ $x_1 = 50, 80, 40$ で $0$ になるので（比の判定）、最小の $40$ を与える $s_3$ が出る。 $s_3$ の式を $x_1 = 40 - s_3$ と解いて他の式に代入すると

\begin{aligned} x_1 &= 40 - s_3 \\ s_1 &= 20 - x_2 + 2s_3 \\ s_2 &= 40 - x_2 + s_3 \\ z &= 1600 + 30x_2 - 40s_3 \end{aligned}

次に $x_2$ が入り、比は $s_1$ で $20$ 、 $s_2$ で $40$ なので $s_1$ が出る。

\begin{aligned} x_1 &= 40 - s_3 \\ x_2 &= 20 - s_1 + 2s_3 \\ s_2 &= 20 + s_1 - s_3 \\ z &= 2200 - 30s_1 + 20s_3 \end{aligned}

ここで $s_3$ を入れることは、P を 1 単位減らして原料の余りを作り、空いた機械 2 時間で Q を 2 単位増やすことにあたる（利益は $-40 + 60 = 20$ 増える）。 $x_2$ の行は $s_3$ の係数が正なので制限にならず、比は $x_1$ で $40$ 、 $s_2$ で $20$ なので $s_2$ が出る。

\begin{aligned} x_1 &= 20 - s_1 + s_2 \\ x_2 &= 60 + s_1 - 2s_2 \\ s_3 &= 20 + s_1 - s_2 \\ z &= 2600 - 10s_1 - 20s_2 \end{aligned}

$z$ の行の係数がすべて負になったので最適であり、最適解 $(x_1, x_2) = (20, 60)$ 、最大利益 $2600$ を得る。たどった頂点は $(0, 0) \to (40, 0) \to (40, 20) \to (20, 60)$ である（各辞書は計算機で厳密に検算した）。最後の行の係数 $-10, -20$ の意味は 3.7・3.8 節で明らかになる。

注意 3.17（最初の実行可能基底解）制約が $Ax \leq b$ , $b \geq 0$ の形なら、スラック変数が最初の基底になる。一般には、 $b \geq 0$ となるよう行に $-1$ を掛けてから人工変数 $r \in \mathbb{R}^m$ を加えた補助問題「minimize $\mathbf{1}^{\top}r$ subject to $Ax + r = b$ , $x, r \geq 0$ 」を、 $r = b$ から始めて解く。元の問題が実行可能であることと、補助問題の最適値が $0$ であることは同値である（実行可能解 $x$ があれば $(x, 0)$ が値 $0$ を与え、逆に値 $0$ なら $r = 0$ ）。最適値が $0$ なら補助問題の解から元の問題の実行可能基底解が得られる（基底に人工変数が値 $0$ で残る場合の処理などの詳細は Chvátal, Linear Programming を参照）。これを 2 段階法 (two-phase method) という。

3.5 退化・巡回と計算量

実行可能基底解が退化していると、比の判定で $t^{\ast} = 0$ となることがある。このとき基底は替わるが点は動かず、目的関数も減らない。こうしたピボットが続いて同じ基底に戻ってくることを巡回 (cycling) という。

例 3.18（巡回する例）次の問題を、「 $z$ の行で係数が最大の変数を入れ、比の判定で最小値を与える行が複数あれば添字が最小の変数を出す」という規則で解く。スラック変数を $x_5, x_6, x_7$ とする。

\begin{aligned} \text{maximize} \quad & 10x_1 - 57x_2 - 9x_3 - 24x_4 \\ \text{subject to} \quad & \tfrac{1}{2}x_1 - \tfrac{11}{2}x_2 - \tfrac{5}{2}x_3 + 9x_4 \leq 0, \quad \tfrac{1}{2}x_1 - \tfrac{3}{2}x_2 - \tfrac{1}{2}x_3 + x_4 \leq 0, \\ & x_1 \leq 1, \quad x_1, x_2, x_3, x_4 \geq 0 \end{aligned}

基底は $\lbrace x_5, x_6, x_7 \rbrace \to \lbrace x_1, x_6, x_7 \rbrace \to \lbrace x_1, x_2, x_7 \rbrace \to \lbrace x_2, x_3, x_7 \rbrace \to \lbrace x_3, x_4, x_7 \rbrace \to \lbrace x_4, x_5, x_7 \rbrace \to \lbrace x_5, x_6, x_7 \rbrace$ と替わり、6 回のピボットの後に最初の辞書にそのまま戻る。その間、点は原点から動かず $z = 0$ のままである（各辞書の計算は省略する。計算機で確かめられる）。最適値は $1$ （ $x_1 = x_3 = 1$ , $x_2 = x_4 = 0$ ）なのに、この規則では永遠に到達しない。

定理 3.19（ブランドの規則, Bland's rule）単体法で、入る変数として $\bar{c}_j < 0$ となる $j$ のうち添字が最小のものを選び、出る変数として比の判定の最小値を与える $i$ のうち添字 $B(i)$ が最小のものを選ぶと、巡回は起こらない（ブランド, 1977 年）。したがって単体法は有限回で終了する。

証明は Chvátal, Linear Programming または Schrijver, Theory of Linear and Integer Programming を参照（本書では主張のみ）。例 3.18 をブランドの規則で解くと、7 回のピボットで最適解に達する（計算機で確かめた）。ブランドの規則が保証するのは有限回で終わることであって、ピボットの回数が少ないことではない。巡回を防ぐ方法としては、ほかに右辺 $b$ をわずかにずらして退化を解消する摂動法（辞書式規則）が知られている。

単体法のピボットの回数については、次のことが知られている。

定理 3.20（クレー–ミンティ, Klee–Minty, 1972 年）各 $n$ について、 $n$ 変数・ $n$ 本の不等式制約（と非負制約）の問題で、原点から始めて「 $z$ の行で係数が最大の変数を入れる」規則（ダンツィクの規則）の単体法が $2^n - 1$ 回のピボットを要するものが存在する。

（主張のみ。Chvátal の教科書を参照。）たとえば

\text{maximize} \quad \sum_{j=1}^{n}10^{n-j}x_j \qquad \text{subject to} \quad 2\sum_{j=1}^{i-1}10^{i-j}x_j + x_i \leq 100^{i-1} \quad (i = 1, \dots, n), \quad x \geq 0

がそのような例で、実行可能領域は立方体をゆがめた形で $2^n$ 個の頂点をもつ。 $n = 1, \dots, 7$ でピボットの回数が $2^n - 1$ になることを計算機で確かめた。 $n = 3$ では $(0, 0, 0) \to (1, 0, 0) \to (1, 80, 0) \to (0, 100, 0) \to (0, 100, 8000) \to (1, 80, 8200) \to (1, 0, 9800) \to (0, 0, 10000)$ と、8 個の頂点をすべてたどる。つまり単体法は、最悪の場合に変数の数について指数回のピボットを要しうる。

一方、線形計画問題そのものは多項式時間で解ける。入力（有理数の $A, b, c$ ）のビット数を $L$ とするとき、ハチヤン（1979 年）は楕円体法が $L$ の多項式時間で線形計画問題を解くことを示し（変数や制約の数は $L$ 以下なので、問題の規模についても多項式時間である）、カーマーカー（1984 年）は実用的にも速い多項式時間の内点法 (interior point method) を提案した。内点法は実行可能領域の内部を通って最適解に近づく方法で、その考え方（対数バリアと中心パス）は第6章で扱う。単体法も実際の問題では多くの場合に高速であることが経験的に知られており、実用的なソルバーの多くは単体法と内点法の両方を備えている。

3.6 ファルカスの補題

連立一次方程式が解をもたないことは、式の一次結合で「 $0 = 1$ 」を作れば示せる。では非負の解をもたないことはどう示せばよいか。 $x_1 + x_2 = 2$ , $x_1 + 3x_2 = 1$ は解 $(5/2, -1/2)$ をもつが、非負の解はもたない。実際、第 1 式に $-1$ 、第 2 式に $1$ を掛けて足すと $2x_2 = -1$ となり、 $x_2 \geq 0$ に反する。乗数 $y = (-1, 1)$ は $A^{\top}y = (0, 2) \geq 0$ , $b^{\top}y = -1 < 0$ を満たす。このような $y$ が常に見つかることを示すのがファルカスの補題である。

補題 3.21（有限生成錐は閉） $A \in \mathbb{R}^{m \times n}$ に対し、 $\operatorname{cone}(A) = \lbrace Ax \mid x \in \mathbb{R}^n,\ x \geq 0 \rbrace$ は $\mathbb{R}^m$ の閉凸錐である。

証明. 凸錐であることは $Ax + Ax' = A(x + x')$ , $tAx = A(tx)$ から明らか。 $w = Ax$ （ $x \geq 0$ ）とする。台の列が一次従属なら、補題 3.10（ $P = \lbrace x \geq 0 \mid Ax = w \rbrace$ に適用する。 $d$ と $-d$ の一方は負の成分をもつ）で台を減らせるので、 $w$ は一次独立な列の非負結合として書ける。そこで、列が一次独立となる添字集合 $S$ ごとに $C_S = \lbrace A_Sz \mid z \geq 0 \rbrace$ とおけば、 $\operatorname{cone}(A)$ は有限個の $C_S$ の和集合である。各 $C_S$ は閉集合である：列が一次独立なので、 $A_S^{\top}A_Sv = 0$ なら $\lVert A_Sv \rVert^2 = v^{\top}A_S^{\top}A_Sv = 0$ より $v = 0$ となり $A_S^{\top}A_S$ は正則である。 $A_Sz_k \to w$ （ $z_k \geq 0$ ）なら $z_k = (A_S^{\top}A_S)^{-1}A_S^{\top}(A_Sz_k) \to (A_S^{\top}A_S)^{-1}A_S^{\top}w =: z$ で、 $z \geq 0$ , $A_Sz = w$ だから $w \in C_S$ 。有限個の閉集合の和集合は閉である。 $\square$

定理 3.22（ファルカスの補題, Farkas' lemma） $A \in \mathbb{R}^{m \times n}$ , $b \in \mathbb{R}^m$ について、次のちょうど一方が成り立つ。

$Ax = b$ , $x \geq 0$ を満たす $x \in \mathbb{R}^n$ が存在する。

$A^{\top}y \geq 0$ , $b^{\top}y < 0$ を満たす $y \in \mathbb{R}^m$ が存在する。

証明. 両方が成り立つと $0 \leq x^{\top}(A^{\top}y) = (Ax)^{\top}y = b^{\top}y < 0$ となり矛盾する。1 が成り立たない、すなわち $b \notin C := \operatorname{cone}(A)$ とする。 $C$ は空でない閉凸集合（補題 3.21）なので、第2章の点と閉凸集合の分離定理（定理 2.6）により、 $\sup_{w \in C}p^{\top}w < p^{\top}b$ となる $p \in \mathbb{R}^m$ がある。 $0 \in C$ より $p^{\top}b > 0$ 。ある $w \in C$ で $p^{\top}w > 0$ なら、 $tw \in C$ （ $t > 0$ ）について $p^{\top}(tw) \to \infty$ となり矛盾するので、すべての $w \in C$ で $p^{\top}w \leq 0$ 、特に $p^{\top}a_j \leq 0$ （ $j = 1, \dots, n$ ）。 $y = -p$ とおけば $A^{\top}y \geq 0$ , $b^{\top}y < 0$ 。 $\square$

幾何学的には、1 は「 $b$ が列ベクトルの生成する錐に入る」こと、2 は「 $b$ と錐を超平面 $\lbrace w \mid y^{\top}w = 0 \rbrace$ で分けられる」ことである。2 の $y$ は 1 が解をもたないことの証明書であり、検証は $A^{\top}y$ と $b^{\top}y$ を計算するだけで済む。

系 3.23（ファルカスの補題の変形）

次のちょうど一方が成り立つ：(i) $Ax \leq b$ , $x \geq 0$ を満たす $x$ がある。(ii) $y \geq 0$ , $A^{\top}y \geq 0$ , $b^{\top}y < 0$ を満たす $y$ がある。

次のちょうど一方が成り立つ：(i) $A^{\top}y \leq c$ を満たす $y \in \mathbb{R}^m$ がある。(ii) $x \geq 0$ , $Ax = 0$ , $c^{\top}x < 0$ を満たす $x \in \mathbb{R}^n$ がある。

証明. 1：(i) はスラック変数を加えた $[A, I](x, s) = b$ , $(x, s) \geq 0$ の可解性と同値で、定理 3.22 をこれに使うと、もう一方は $A^{\top}y \geq 0$ , $y \geq 0$ , $b^{\top}y < 0$ となる。2：(i) は $y = y^{+} - y^{-}$ と分けスラック $s$ を加えた $A^{\top}y^{+} - A^{\top}y^{-} + s = c$ , $(y^{+}, y^{-}, s) \geq 0$ の可解性と同値である。定理 3.22 を行列 $[A^{\top}, -A^{\top}, I]$ に使うと、もう一方は「 $Ax \geq 0$ , $-Ax \geq 0$ , $x \geq 0$ , $c^{\top}x < 0$ を満たす $x$ がある」、すなわち (ii) である。 $\square$

ヒント

実務では 大きなモデルを組むと、ソルバーから「実行不能」と返ってくることがよくある。データの入力ミスや、両立しない業務ルール（「P を 50 単位以上作る」と「原料は 40 単位まで」など）が原因である。多くのソルバーは、実行不能性の証明書としてファルカスの補題の $y$ （どの制約をどんな重みで足すと矛盾が出るか）や、互いに矛盾する制約の極小な組を出力できる。 $y_i \neq 0$ の制約だけを調べればよいので、数万本の制約から原因を絞り込める。

3.7 双対問題と双対定理

例 3.1 で、最大利益の上界を作ってみる。機械・作業・原料の制約にそれぞれ $y_1, y_2, y_3 \geq 0$ を掛けて足すと

(2y_1 + y_2 + y_3)x_1 + (y_1 + y_2)x_2 \leq 100y_1 + 80y_2 + 40y_3

で、 $2y_1 + y_2 + y_3 \geq 40$ , $y_1 + y_2 \geq 30$ なら、 $x \geq 0$ より左辺は利益 $40x_1 + 30x_2$ 以上である。したがって右辺は利益の上界であり、 $y = (10, 20, 0)$ とすると上界 $2600$ が得られる。これは $(20, 60)$ での利益に等しいので、 $(20, 60)$ の最適性が証明された。最良の上界を求める問題がまた線形計画問題になる。これが双対問題である。

定義 3.24（双対問題, dual problem）標準形 (P) に対し、次の問題 (D) を (P) の双対問題、(P) を主問題 (primal problem) という。 $y \in \mathbb{R}^m$ に符号の制約はない。
$\text{(D)} \qquad \text{maximize} \quad b^{\top}y \qquad \text{subject to} \quad A^{\top}y \leq c$

定理 3.25（弱双対定理, weak duality） $x$ が (P) の、 $y$ が (D) の実行可能解ならば $b^{\top}y \leq c^{\top}x$ である。特に $b^{\top}y = c^{\top}x$ ならば、 $x, y$ はそれぞれ (P), (D) の最適解である。

証明. $b^{\top}y = (Ax)^{\top}y = x^{\top}(A^{\top}y) \leq x^{\top}c$ （ $x \geq 0$ , $A^{\top}y \leq c$ ）。等号のとき、(P) の任意の実行可能解 $x'$ について $c^{\top}x' \geq b^{\top}y = c^{\top}x$ なので $x$ は最適で、 $y$ も同様。 $\square$

定理 3.26（強双対定理, strong duality）(P) が最適解をもてば (D) も最適解をもち、両者の最適値は等しい。

証明. (P) の最適解を $x^{\ast}$ 、最適値を $z^{\ast} = c^{\top}x^{\ast}$ とする。 $A^{\top}y \leq c$ かつ $b^{\top}y \geq z^{\ast}$ を満たす $y$ が存在することを示せば、弱双対定理より $b^{\top}y = z^{\ast}$ で $y$ は (D) の最適解になる。この条件は $y$ についての連立不等式

\begin{pmatrix} A^{\top} \\ -b^{\top} \end{pmatrix}y \leq \begin{pmatrix} c \\ -z^{\ast} \end{pmatrix}

である。解がないとすると、系 3.23 の 2 より、 $(w, t) \geq 0$ （ $w \in \mathbb{R}^n$ , $t \in \mathbb{R}$ ）で $Aw - tb = 0$ かつ $c^{\top}w - tz^{\ast} < 0$ となるものがある。 $t > 0$ なら $x = w/t$ は $x \geq 0$ , $Ax = b$ , $c^{\top}x < z^{\ast}$ を満たし、 $z^{\ast}$ の最適性に反する。 $t = 0$ なら $w \geq 0$ , $Aw = 0$ , $c^{\top}w < 0$ で、 $x^{\ast} + sw$ （ $s \geq 0$ ）は実行可能かつ $c^{\top}(x^{\ast} + sw) \to -\infty$ となり、やはり矛盾する。 $\square$

系 3.27（双対定理）

(P) と (D) がともに実行可能ならば、ともに最適解をもち、最適値は等しい。

(P) が実行可能で (D) が実行不能ならば (P) は非有界である。(D) が実行可能で (P) が実行不能ならば (D) は非有界である。

(P) と (D) がともに実行不能なこともある。

証明. 1：弱双対定理より (P) の目的関数は下に有界なので、定理 3.11 より (P) は最適解をもち、定理 3.26 が使える。2：(D) が実行不能なら、系 3.23 の 2 より $w \geq 0$ , $Aw = 0$ , $c^{\top}w < 0$ となる $w$ があり、(P) の実行可能解 $x$ について $x + sw$ （ $s \geq 0$ ）で目的関数は $-\infty$ に発散する。(P) が実行不能なら、定理 3.22 より $A^{\top}y' \geq 0$ , $b^{\top}y' < 0$ となる $y'$ があり、(D) の実行可能解 $y$ について $y - sy'$ （ $s \geq 0$ ）は $A^{\top}(y - sy') \leq c$ を満たし、 $b^{\top}(y - sy') \to +\infty$ 。3： $A$ の行を $(1, -1)$ と $(-1, 1)$ 、 $b = (1, 1)$ , $c = (-1, -1)$ とすると、(P) の 2 式を足すと $0 = 2$ 、(D) の 2 式 $y_1 - y_2 \leq -1$ , $-y_1 + y_2 \leq -1$ を足すと $0 \leq -2$ となり、どちらも実行不能である。 $\square$

逆に、弱双対定理より、一方が非有界ならば他方は実行不能である。したがって (P) と (D) の組は、「ともに最適解をもち、最適値が等しい」「(P) が非有界で (D) が実行不能」「(D) が非有界で (P) が実行不能」「ともに実行不能」の 4 通りのどれかになる。

双対問題の作り方. 一般の形の問題の双対問題は、命題 3.4 で標準形に直して定義 3.24 を当てはめれば得られる。よく使う対称な形

\text{(P}'\text{)} \quad \text{maximize} \ c^{\top}x \ \ \text{s.t.} \ Ax \leq b, \ x \geq 0 \qquad \text{(D}'\text{)} \quad \text{minimize} \ b^{\top}y \ \ \text{s.t.} \ A^{\top}y \geq c, \ y \geq 0

もこうして得られ（問題 3.5）、(P′) か (D′) の一方が最適解をもてば他方も最適解をもち、最適値は等しい。一般に、最大化問題とその双対（最小化問題）の間には次の対応がある。いずれも標準形に直して確かめられる。

最大化問題	最小化問題
第 $i$ 制約が $\leq$	$y_i \geq 0$
第 $i$ 制約が $=$	$y_i$ は自由
第 $i$ 制約が $\geq$	$y_i \leq 0$
$x_j \geq 0$	第 $j$ 制約が $\geq$
$x_j$ は自由	第 $j$ 制約が $=$
$x_j \leq 0$	第 $j$ 制約が $\leq$

定理 3.28（相補性条件, complementary slackness） $x$ を (P) の、 $y$ を (D) の実行可能解とする。 $x, y$ がともに最適解であるための必要十分条件は、
$x_j(c_j - a_j^{\top}y) = 0 \qquad (j = 1, \dots, n)$
である。対称な形 (P′), (D′) では、条件は $y_i(b_i - (Ax)_i) = 0$ （ $i = 1, \dots, m$ ）かつ $x_j((A^{\top}y)_j - c_j) = 0$ （ $j = 1, \dots, n$ ）である。

証明. $c^{\top}x - b^{\top}y = x^{\top}(c - A^{\top}y) = \sum_j x_j(c_j - a_j^{\top}y)$ で、各項は非負である。両方が最適なら強双対定理より左辺は $0$ なので各項が $0$ 。逆に各項が $0$ なら $c^{\top}x = b^{\top}y$ で、弱双対定理より両方とも最適。対称な形でも、 $b^{\top}y - c^{\top}x = y^{\top}(b - Ax) + x^{\top}(A^{\top}y - c)$ の各項が非負であることから同様である。 $\square$

言葉でいえば、「主問題で正の値をとる変数に対応する双対の制約は等号で成り立ち、正の双対変数に対応する主問題の制約は等号で成り立つ（資源を使い切っている）」。最適性を確かめるには、相補性条件から双対の候補を連立一次方程式で求め、それが双対実行可能かを調べればよい。

例 3.29（例 3.1 の双対）例 3.1 の双対問題は、この節の初めに作った「 $2y_1 + y_2 + y_3 \geq 40$ , $y_1 + y_2 \geq 30$ , $y \geq 0$ のもとで $100y_1 + 80y_2 + 40y_3$ を最小化する」問題である。 $x = (20, 60)$ では原料が余るので $y_3 = 0$ 、 $x_1, x_2 > 0$ なので双対の 2 本の制約は等号で、 $2y_1 + y_2 = 40$ , $y_1 + y_2 = 30$ から $y = (10, 20, 0)$ が求まる。この $y$ は例 3.16 の最後の辞書 $z = 2600 - 10s_1 - 20s_2$ に現れていた。一般に、単体法が $\bar{c} \geq 0$ で終了したときの単体乗数 $y = (A_B^{\top})^{-1}c_B$ は、 $A^{\top}y \leq c$ （ $\bar{c} \geq 0$ と同値）と $b^{\top}y = c_B^{\top}A_B^{-1}b = c^{\top}x$ を満たすので (D) の最適解である。単体法は双対問題も同時に解いている。

3.8 シャドウプライスと感度分析

例 3.1 で機械を 1 時間増やすと、最大利益はどれだけ増えるだろうか。右辺 $b$ を変えたときの最適値の変化は、双対の最適解で表せる。

定理 3.30（シャドウプライス, shadow price）標準形 (P) で右辺を $b'$ に替えた問題の最適値を $v(b')$ とし（実行不能なら $v(b') = +\infty$ ）、(P)（右辺 $b$ ）は最適解をもつとする。

(D) の任意の最適解 $y^{\ast}$ と任意の $b'$ について、 $v(b') \geq v(b) + y^{\ast\top}(b' - b)$ 。

$\operatorname{rank} A = m$ で、(P) が非退化な最適基底解 $x^{\ast}$ （基底 $B$ ）をもつとする。このとき (D) の最適解は $y^{\ast} = (A_B^{\top})^{-1}c_B$ ただ一つであり、 $A_B^{-1}b' \geq 0$ を満たすすべての $b'$ について $v(b') = v(b) + y^{\ast\top}(b' - b)$ が成り立つ。この範囲は $b$ の近傍を含み、特に $\partial v/\partial b_i = y_i^{\ast}$ である。

証明. 1：(D) の実行可能領域 $\lbrace y \mid A^{\top}y \leq c \rbrace$ は $b$ によらないので、 $y^{\ast}$ は右辺 $b'$ の問題の双対問題でも実行可能であり、弱双対定理と強双対定理より $v(b') \geq b'^{\top}y^{\ast} = b^{\top}y^{\ast} + y^{\ast\top}(b' - b) = v(b) + y^{\ast\top}(b' - b)$ 。

2：まず $\bar{c} \geq 0$ である。実際、 $\bar{c}_q < 0$ となる $q$ があれば、命題 3.14 の 1 なら非有界、2 なら非退化より $t^{\ast} > 0$ で目的関数が真に減り、どちらも $x^{\ast}$ の最適性に反する。よって $y^{\ast} = (A_B^{\top})^{-1}c_B$ は $A^{\top}y^{\ast} \leq c$ を満たし、 $b^{\top}y^{\ast} = c_B^{\top}A_B^{-1}b = c^{\top}x^{\ast}$ だから (D) の最適解である。(D) の最適解 $y$ は相補性条件を満たし、 $x_j^{\ast} > 0$ （ $j \in B$ ）なので $a_j^{\top}y = c_j$ （ $j \in B$ ）、すなわち $A_B^{\top}y = c_B$ で $y = y^{\ast}$ 。最後に、 $A_B^{-1}b' \geq 0$ なら $x'_B = A_B^{-1}b'$ , $x'_N = 0$ は右辺 $b'$ の問題の実行可能解で、 $c^{\top}x' = c_B^{\top}A_B^{-1}b' = b'^{\top}y^{\ast}$ だから、弱双対定理より $v(b') = b'^{\top}y^{\ast} = v(b) + y^{\ast\top}(b' - b)$ 。 $A_B^{-1}b > 0$ なので、連続性から $b$ の近くの $b'$ では $A_B^{-1}b' \geq 0$ である。 $\square$

$y_i^{\ast}$ を制約 $i$ のシャドウプライス（潜在価格）という。最大化問題 (P′) では不等号の向きが逆になり、 $v(b') \leq v(b) + y^{\ast\top}(b' - b)$ である（ $v$ は凹関数）。右辺や目的関数の係数を動かしたとき、最適基底がどの範囲で変わらないかを調べることを感度分析 (sensitivity analysis) という。

例 3.31（例 3.1 のシャドウプライス）最適解は非退化で（基底変数 $x_1 = 20$ , $x_2 = 60$ , $s_3 = 20$ がすべて正）、 $y^{\ast} = (10, 20, 0)$ 。機械を 1 時間増やすと最大利益は 10 千円、作業なら 20 千円増え、余っている原料を増やしても利益は増えない。最適基底 $\lbrace x_1, x_2, s_3 \rbrace$ の基底解は、右辺 $(b_1, b_2, b_3)$ に対して $x_1 = b_1 - b_2$ , $x_2 = 2b_2 - b_1$ , $s_3 = b_3 - b_1 + b_2$ なので、作業 80・原料 40 のまま機械 $b_1$ を動かすとき、この基底が実行可能なのは $80 \leq b_1 \leq 120$ である。この範囲で機械 1 時間の価値は 10 千円であり、 $b_1 > 120$ では原料が尽きて P を増やせず、利益は $2800$ から増えない（計算機で確かめた）。目的関数の係数についても、 $\bar{c} \geq 0$ が保たれる限り最適基底は変わらない。たとえば Q の利益 30 を固定すると、P の利益 $c_1$ が $30 \leq c_1 \leq 60$ なら $(20, 60)$ が最適のままである（ $(c_1, 30) = y_1(2, 1) + y_2(1, 1)$ の $y_1 = c_1 - 30$ , $y_2 = 60 - c_1$ が非負の範囲）。

注意

シャドウプライスは「その範囲でだけ有効な限界的な値」である。(1) 範囲を超えて外挿してはいけない（問題 3.6）。(2) 退化していると双対の最適解は一意とは限らず、増やす方向と減らす方向で限界的な値が異なりうる。例 3.1 に制約 $x_1 + 2x_2 \leq 140$ を加えると、頂点 $(20, 60)$ で 3 本の制約が等号になって退化する。最適値は $2600$ のままだが、機械を増やすときの利益の増え方は 1 時間あたり $10$ 、減らすときの減り方は $50/3$ で、双対の最適解は $(y_1, 50 - 3y_1, 0, y_1 - 10)$ （ $10 \leq y_1 \leq 50/3$ ）の全体になる（計算機で確かめた。右微分 $10$ と左微分 $50/3$ が $y_1$ の範囲の両端になっていることは、定理 3.30 の 1 と整合する）。ソルバーはこの中の一つしか報告せず、同じソルバーでも解法の設定によって $(10, 20, 0, 0)$ が返ることも $(50/3, 0, 0, 20/3)$ が返ることもある。

ヒント

実務では 多くのソルバーは、最適解と一緒に双対変数（シャドウプライス、dual value）と被約費用（reduced cost）を返し、右辺や目的関数の係数を最適基底が変わらずに動かせる範囲も出力できる。「どの資源の追加にいくらまで払う価値があるか」「採算に合わない製品の利益がいくら上がれば作る価値が出るか」（被約費用）を判断する材料になる。ただし符号の約束（最大化か最小化か、 $\leq$ か $\geq$ か）はソルバーによって異なるので、小さな例で確かめてから読むこと。

3.9 輸送問題と割当問題

第1章例 1.3 の輸送問題では、倉庫 $i$ の在庫 $s_i$ 、店舗 $j$ の需要 $d_j$ 、単位輸送費 $c_{ij}$ について、 $\sum_j x_{ij} \leq s_i$ , $\sum_i x_{ij} = d_j$ , $x \geq 0$ のもとで $\sum_{i,j}c_{ij}x_{ij}$ を最小化する。上の対応表によれば、双対問題は、在庫の制約に $u_i \leq 0$ 、需要の制約に自由な $v_j$ を対応させた

\text{maximize} \quad \sum_i s_iu_i + \sum_j d_jv_j \qquad \text{subject to} \quad u_i + v_j \leq c_{ij}, \quad u_i \leq 0

である。相補性条件は、「使う経路（ $x_{ij} > 0$ ）では $u_i + v_j = c_{ij}$ 」「在庫が余る倉庫（ $\sum_j x_{ij} < s_i$ ）では $u_i = 0$ 」である。

例 3.32（輸送問題）2 つの倉庫 A, B（在庫 50, 60）から 3 つの店舗 1, 2, 3（需要 30, 40, 25）へ製品を運ぶ。単位輸送費は次の表のとおりである。

	店舗 1	店舗 2	店舗 3
倉庫 A	4	6	9
倉庫 B	5	3	7

B は店舗 2・3 へは安いが、在庫 60 では両方の需要 65 をまかなえない。そこで A→1 に 30、A→3 に 5、B→2 に 40、B→3 に 20 運ぶ計画（費用 $120 + 45 + 120 + 140 = 425$ ）を考える。A の在庫は 15 余るので $u_A = 0$ 、使う経路で $u_i + v_j = c_{ij}$ とすると、 $v_1 = 4$ , $v_3 = 9$ , $u_B = 7 - 9 = -2$ , $v_2 = 3 - (-2) = 5$ 。使わない経路でも $u_A + v_2 = 5 \leq 6$ , $u_B + v_1 = 2 \leq 5$ が成り立ち、 $u \leq 0$ なので双対実行可能で、双対の目的関数値は $60 \cdot (-2) + 30 \cdot 4 + 40 \cdot 5 + 25 \cdot 9 = 425$ 。よってこの計画は最適である（計算機でも確かめた）。

基底変数 $x_{A1}, x_{A3}, x_{B2}, x_{B3}$ と A の余りはすべて正で非退化なので、定理 3.30 により双対変数は限界費用を表す。店舗 2 の需要が 1 増えたときの費用の増加は $v_2 = 5$ で、最安の経路の費用 3 ではない。B は在庫を使い切っているので、B→2 を 1 増やし（ $+3$ ）、B→3 を 1 減らし（ $-7$ ）、A→3 を 1 増やす（ $+9$ ）ことになるからである。同様に、B の在庫が 1 増えると費用は $2$ 減る（ $u_B = -2$ 。B の在庫が 45 から 65 の範囲で正しい）。店舗 3 の需要の変化は問題 3.7 で扱う。

輸送問題・割当問題では、最適解が整数になることが重要である。

命題 3.33（輸送問題の整数性）在庫と需要がつり合った輸送問題 $\sum_j x_{ij} = s_i$ （ $i = 1, \dots, m$ ）、 $\sum_i x_{ij} = d_j$ （ $j = 1, \dots, n$ ）、 $x \geq 0$ で、 $s_i, d_j$ がすべて整数ならば、実行可能領域の頂点はすべて整数ベクトルである。したがって最適解をもてば、整数の最適解がある。

証明. 倉庫 $i$ と店舗 $j$ を頂点とし、 $x_{ij} > 0$ となる $(i, j)$ を辺とする 2 部グラフ $G(x)$ を考える。変数 $x_{ij}$ の係数の列は $e_i + e_{m+j}$ （ $e_k$ は $\mathbb{R}^{m+n}$ の単位ベクトル）である。

(i) $x$ が頂点なら $G(x)$ は閉路をもたない。閉路 $i_1j_1i_2j_2\cdots i_kj_ki_1$ があるとすると、辺 $(i_1, j_1), (i_2, j_2), \dots, (i_k, j_k)$ の列に $+1$ 、辺 $(i_2, j_1), (i_3, j_2), \dots, (i_1, j_k)$ の列に $-1$ を掛けて足せば、各頂点で $+1$ と $-1$ が打ち消し合って $0$ になる。これは台の列が一次従属であることを意味し、定理 3.8 に反する。

(ii) $G(x)$ が閉路をもたない実行可能解 $x$ は整数ベクトルである。辺の本数についての帰納法で示す。辺がなければ $x = 0$ 。辺があれば、閉路のないグラフには次数 1 の頂点がある（最長の道の端点は、他の頂点とつながれば道が延びるか閉路ができるので、次数 1 である）。それが倉庫 $i$ で、唯一の辺が $(i, j)$ なら、 $\sum_{j'}x_{ij'} = s_i$ より $x_{ij} = s_i$ は整数である。 $x_{ij}$ と $s_i$ を $0$ に、 $d_j$ を $d_j - s_i$ に替えると、整数データの同じ形の系の、辺が 1 本少なく閉路のない解が得られるので、帰納法の仮定から残りの成分も整数である。店舗の場合も同様。最後の主張は定理 3.11 による。 $\square$

在庫が需要を上回る場合も、余りを受け取る費用 $0$ の仮想の店舗を加えれば、つり合った問題に帰着する。

割当問題 (assignment problem) は、 $n$ 人を $n$ 個の仕事に一人一つずつ割り当て、費用 $c_{ij}$ の和を最小にする問題である。 $x_{ij} \in \lbrace 0, 1 \rbrace$ という整数の制約を $x_{ij} \geq 0$ にゆるめると、 $s_i = d_j = 1$ の輸送問題になる。命題 3.33 より、その頂点は各行・各列の和が 1 の $0$ - $1$ 行列、すなわち置換行列である。したがって、ゆるめた線形計画問題を単体法で解けば、元の割当問題の最適解が得られる。

例 3.34（割当問題）3 人の担当者に 3 つの仕事を割り当てる。所要時間は次のとおりである。

	仕事 1	仕事 2	仕事 3
担当者 1	2	3	6
担当者 2	1	7	8
担当者 3	5	4	9

時間の短い組から順に決める貪欲な方法では、担当者 2→仕事 1（1）、担当者 1→仕事 2（3）、担当者 3→仕事 3（9）で合計 13 になる。6 通りの割り当てをすべて調べると、最小は担当者 1→仕事 3、担当者 2→仕事 1、担当者 3→仕事 2 の $6 + 1 + 4 = 11$ である。ゆるめた線形計画問題を解いても、この割り当てを表す置換行列が最適解として得られる（計算機で確かめた）。人数が増えると割り当ての数 $n!$ は爆発的に増えるが、線形計画（あるいは専用のハンガリー法）なら効率よく解ける。整数の制約をゆるめても整数解が得られるのは特別な構造のおかげで、一般の整数計画問題では成り立たない（第7章）。

まとめ

線形計画問題は、スラック変数と自由変数の分解により標準形 $\min c^{\top}x$ , $Ax = b$ , $x \geq 0$ に直せる。
実行可能基底解・頂点・「台の列が一次独立な実行可能解」は同じものであり、頂点は有限個である。
標準形の問題は、実行不能・非有界（ $d \geq 0$ , $Ad = 0$ , $c^{\top}d < 0$ がある）・頂点で最適解をもつ、のちょうど一つに当てはまる。
単体法は被約費用 $\bar{c}$ を見て隣の頂点へ移る。 $\bar{c} \geq 0$ なら最適。非退化なら有限回で終わるが、退化すると巡回しうる。ブランドの規則を使えば巡回は起こらない。
ダンツィクの規則の単体法は最悪の場合 $2^n - 1$ 回のピボットを要する（クレー–ミンティ）。楕円体法・内点法は多項式時間で解く。
ファルカスの補題： $Ax = b$ , $x \geq 0$ が解をもたないことと、 $A^{\top}y \geq 0$ , $b^{\top}y < 0$ となる $y$ （実行不能性の証明書）が存在することは同値である。有限生成錐が閉であることと分離定理から従う。
弱双対定理・強双対定理：主問題が最適解をもてば双対問題も最適解をもち、最適値は等しい。相補性条件で最適性を確かめられる。
双対の最適解はシャドウプライスであり、非退化なら最適値の右辺についての偏微分に等しい。有効範囲の外への外挿と、退化による非一意性に注意する。
輸送問題・割当問題では、整数データなら頂点が整数になり、ゆるめた線形計画問題から整数の最適解が得られる。

演習問題

問題 3.1 ★ 次の問題を標準形に直せ。また、実行可能領域の頂点を調べて最適解を求めよ（ $x_2$ は符号の制約のない変数である）。

\text{maximize} \quad x_1 - 2x_2 \qquad \text{subject to} \quad x_1 + x_2 \geq 1, \quad 2x_1 - x_2 \leq 4, \quad x_1 \geq 0

解答

$x_2 = x_2^{+} - x_2^{-}$ とし、余剰変数 $s_1$ とスラック変数 $s_2$ を加えると、標準形は

\text{minimize} \quad -x_1 + 2x_2^{+} - 2x_2^{-} \qquad \text{subject to} \quad x_1 + x_2^{+} - x_2^{-} - s_1 = 1, \quad 2x_1 - x_2^{+} + x_2^{-} + s_2 = 4, \quad x_1, x_2^{+}, x_2^{-}, s_1, s_2 \geq 0

である（元の最大値はこの最小値の $-1$ 倍）。元の実行可能領域 $x_1 \geq 0$ , $x_2 \geq 1 - x_1$ , $x_2 \geq 2x_1 - 4$ の頂点は $(0, 1)$ と $(5/3, -2/3)$ （ $x_1 + x_2 = 1$ と $2x_1 - x_2 = 4$ の交点）で、目的関数の値は $-2$ と $3$ である。領域は非有界（ $x_2$ はいくらでも大きくできる）なので、頂点の比較だけでは最大値とは言えない。そこで制約の一次結合で上界を作ると、任意の実行可能解について $x_1 - 2x_2 = (2x_1 - x_2) - (x_1 + x_2) \leq 4 - 1 = 3$ であり、等号は 2 つの制約がともに等号のとき、すなわち $(5/3, -2/3)$ でだけ成り立つ（第 1・第 2 制約に掛けた係数 $-1$ , $1$ は、双対問題の最適解になっている）。よって最適解は $(5/3, -2/3)$ 、最大値は $3$ である（標準形では $x_1 = 5/3$ , $x_2^{+} = 0$ , $x_2^{-} = 2/3$ , $s_1 = s_2 = 0$ ）。

問題 3.2 ★ 連立方程式 $x_1 + x_2 + x_3 = 2$ , $x_1 - x_2 = 3$ が非負の解をもたないことを、ファルカスの補題の $y$ を具体的に与えて示せ。また、非負の制約がなければ解があることを確かめよ。

解答

係数行列 $A$ の行は $(1, 1, 1)$ と $(1, -1, 0)$ 、 $b = (2, 3)$ である。 $y = (1, -1)$ とすると $A^{\top}y = (0, 2, 1) \geq 0$ , $b^{\top}y = -1 < 0$ 。実際、第 1 式から第 2 式を引くと $2x_2 + x_3 = -1$ となり、 $x \geq 0$ なら左辺は非負なので矛盾する。非負の制約がなければ、たとえば $x = (3, 0, -1)$ が解である。

問題 3.3 ★ 次の問題で $x = (7/2, 3/2)$ が最適解であることを、相補性条件を使って双対問題の解を作ることで示せ。また各制約のシャドウプライスを答えよ。

\text{maximize} \quad 5x_1 + 4x_2 \qquad \text{subject to} \quad x_1 + x_2 \leq 5, \quad 3x_1 + x_2 \leq 12, \quad x_1 + 2x_2 \leq 8, \quad x \geq 0

解答

$x$ は実行可能で、第 1・2 制約は等号、第 3 制約は $7/2 + 3 = 13/2 < 8$ で余る。双対問題は minimize $5y_1 + 12y_2 + 8y_3$ subject to $y_1 + 3y_2 + y_3 \geq 5$ , $y_1 + y_2 + 2y_3 \geq 4$ , $y \geq 0$ である。相補性条件より $y_3 = 0$ で、 $x_1, x_2 > 0$ より双対の 2 本の制約は等号： $y_1 + 3y_2 = 5$ , $y_1 + y_2 = 4$ 。これを解くと $y = (7/2, 1/2, 0) \geq 0$ で双対実行可能。目的関数値は主問題が $5 \cdot \frac{7}{2} + 4 \cdot \frac{3}{2} = \frac{47}{2}$ 、双対問題が $5 \cdot \frac{7}{2} + 12 \cdot \frac{1}{2} = \frac{47}{2}$ で一致するので、弱双対定理より両方とも最適である。基底変数 $x_1, x_2$ と第 3 制約のスラック（ $3/2$ ）はすべて正で非退化なので、シャドウプライスは第 1 制約が $7/2$ 、第 2 制約が $1/2$ 、第 3 制約が $0$ である（計算機で確かめた）。

問題 3.4 ★★ 標準形の実行可能領域 $P = \lbrace x \mid Ax = b,\ x \geq 0 \rbrace$ が空でなく有界ならば、 $P$ の任意の点は $P$ の頂点の凸結合であることを示せ。これを使って、 $P$ 上で $c^{\top}x$ を最小にする頂点があることを（定理 3.11 とは別の方法で）示せ。

解答

$x \in P$ について $\lvert \operatorname{supp} x \rvert$ に関する帰納法で示す。台の列が一次独立なら $x$ は頂点である（定理 3.8）。そうでなければ補題 3.10 の $d$ （ $Ad = 0$ , $d \neq 0$ , $\operatorname{supp} d \subset \operatorname{supp} x$ ）をとる。 $d$ が負の成分をもたなければ $x + td \in P$ （ $t \geq 0$ ）となり $P$ の有界性に反するので、 $d$ は負の成分をもち、同様に $-d$ も負の成分をもつ。補題 3.10 を $d$ と $-d$ に使い、 $t_1 = \min\lbrace x_j/(-d_j) \mid d_j < 0 \rbrace$ , $t_2 = \min\lbrace x_j/d_j \mid d_j > 0 \rbrace$ とすると、 $y = x + t_1d$ , $z = x - t_2d$ は $P$ の点で、台は $x$ より真に小さい。

\frac{t_2}{t_1 + t_2}y + \frac{t_1}{t_1 + t_2}z = x + \frac{t_1t_2 - t_1t_2}{t_1 + t_2}d = x

なので $x$ は $y, z$ の凸結合であり、帰納法の仮定より $y, z$ は頂点の凸結合だから、 $x$ もそうである。頂点を $v_1, \dots, v_k$ 、 $x = \sum_i \lambda_iv_i$ （ $\lambda_i \geq 0$ , $\sum_i \lambda_i = 1$ ）とすると $c^{\top}x = \sum_i \lambda_ic^{\top}v_i \geq \min_i c^{\top}v_i$ なので、 $c^{\top}v_i$ が最小の頂点が最適解である。これは、第2章 2.1 節で紹介した「有界な多面体は頂点の凸包に等しい」ことの、標準形の場合の証明にもなっている。

問題 3.5 ★★ (1) 双対問題 (D) を命題 3.4 で標準形に直し、その双対問題を作ると (P) と同値な問題になること（双対の双対は主問題であること）を示せ。(2) (P′) の双対問題が (D′) であることを、標準形に直して確かめよ。

解答

(1) (D) は $y = y^{+} - y^{-}$ とスラック $s$ により、minimize $-b^{\top}y^{+} + b^{\top}y^{-}$ subject to $A^{\top}y^{+} - A^{\top}y^{-} + s = c$ , $(y^{+}, y^{-}, s) \geq 0$ となる（最適値は (D) の最適値の $-1$ 倍）。係数行列は $[A^{\top}, -A^{\top}, I]$ なので、定義 3.24 による双対は maximize $c^{\top}w$ subject to $Aw \leq -b$ , $-Aw \leq b$ , $w \leq 0$ 、すなわち $Aw = -b$ , $w \leq 0$ である。 $x = -w$ とおくと、これは $Ax = b$ , $x \geq 0$ のもとで $-c^{\top}x$ を最大化する問題、つまり (P) と同値である（最適値は (P) の最適値の $-1$ 倍で、符号の付け替えが打ち消し合う）。

(2) (P′) はスラック $s$ を加え、minimize $-c^{\top}x$ subject to $Ax + s = b$ , $(x, s) \geq 0$ となる。係数行列は $[A, I]$ なので、双対は maximize $b^{\top}z$ subject to $A^{\top}z \leq -c$ , $z \leq 0$ 。 $y = -z$ とおくと minimize $b^{\top}y$ subject to $A^{\top}y \geq c$ , $y \geq 0$ で、これが (D′) である。最適値については $\max c^{\top}x = -\min(-c^{\top}x) = -\max b^{\top}z = \min b^{\top}y$ となる。

問題 3.6 ★★ 例 3.1 で、作業時間のシャドウプライスは 20 千円である。担当者は「作業時間を 50 時間増やせば、利益は $20 \times 50 = 1000$ 千円増える」と報告した。この結論は正しいか。シャドウプライス 20 が正しい作業時間の範囲を求め、実際の利益の増加を計算せよ。

解答

正しくない。最適基底 $\lbrace x_1, x_2, s_3 \rbrace$ の基底解は $x_1 = b_1 - b_2$ , $x_2 = 2b_2 - b_1$ , $s_3 = b_3 - b_1 + b_2$ なので、 $b_1 = 100$ , $b_3 = 40$ のまま作業時間 $b_2$ を動かすと、非負である条件は $100 - b_2 \geq 0$ , $2b_2 - 100 \geq 0$ , $b_2 - 60 \geq 0$ 、すなわち $60 \leq b_2 \leq 100$ である。この範囲では利益は $2600 + 20(b_2 - 80)$ で、 $b_2 = 100$ で $(x_1, x_2) = (0, 100)$ 、利益 $3000$ になる。 $b_2 > 100$ では作業時間は余り、機械の制約 $2x_1 + x_2 \leq 100$ と原料の制約だけが効く。そのときの頂点 $(0, 100)$ , $(40, 20)$ での利益は $3000$ , $2200$ なので、最大利益は $3000$ のままである。したがって 50 時間増やして 130 時間にしたときの増加は $3000 - 2600 = 400$ 千円で、1000 千円ではない（後半の 30 時間は機械がボトルネックになって価値がない）。定理 3.30 の 1（最大化では不等号が逆）から、増加は常に $20 \times 50$ 以下であることも言える（計算機で確かめた）。

問題 3.7 ★★ 例 3.32 で、店舗 3 の需要が 25 から 35 に増えた。双対変数を使って費用の増加を予測し、その予測が正しい需要の範囲を求めよ。

解答

$v_3 = 9$ なので、予測は $9 \times 10 = 90$ の増加、費用 $515$ である。最適基底 $\lbrace x_{A1}, x_{A3}, x_{B2}, x_{B3}, s_A \rbrace$ （ $s_A$ は A の余り）のもとで、 $x_{A2} = x_{B1} = 0$ と B の余り $0$ を保ったまま店舗 3 の需要を $d_3$ にすると、 $x_{A1} = 30$ , $x_{B2} = 40$ , $x_{B3} = 60 - 40 = 20$ , $x_{A3} = d_3 - 20$ , $s_A = 50 - 30 - x_{A3} = 40 - d_3$ である。これが非負なのは $20 \leq d_3 \leq 40$ のときで、この範囲では定理 3.30 より費用は $425 + 9(d_3 - 25)$ 。 $d_3 = 35$ では $x_{A3} = 15$ , $s_A = 5$ で費用 $515$ となり、予測どおりである（計算機で確かめた）。 $d_3 > 40$ では総需要が総在庫 110 を超えて実行不能になる。

問題 3.8 ★★ ある単体法の実装は、比の判定で $u_i \neq 0$ となるすべての行について $x_{B(i)}/\lvert u_i \rvert$ の最小値をとっている。例 3.16 の 3 番目の辞書（ $z = 2200 - 30s_1 + 20s_3$ ）でこの実装が $s_3$ を入れると何が起こるか。この実装のどこが危ないかを説明せよ。

解答

辞書 $x_1 = 40 - s_3$ , $x_2 = 20 - s_1 + 2s_3$ , $s_2 = 20 + s_1 - s_3$ で $s_3$ を入れると、 $u$ は $s_3$ の係数の符号を変えたものなので、 $x_1$ の行で $u = 1$ 、 $x_2$ の行で $u = -2$ 、 $s_2$ の行で $u = 1$ である。誤った実装は $40/1$ , $20/2$ , $20/1$ を比べて $x_2$ を出す。 $x_2 = 0$ , $s_1 = 0$ とすると $s_3 = -10$ となり、 $x_1 = 50$ , $s_2 = 30$ , $z = 2000$ 。原料の制約 $x_1 \leq 40$ が破れた（ $s_3 < 0$ ）実行不能な点に移り、目的関数も悪くなっている。 $u_i < 0$ の行は、入る変数を増やすとかえって基底変数が増えるので制限にならない。比の判定は $u_i > 0$ の行だけで行わなければならない。浮動小数点で計算するときは、 $u_i > 0$ の判定にも許容誤差が必要で（ごく小さな正の $u_i$ で割ると誤差が拡大する）、実用的な実装はこの点に注意を払っている。