最適性が保たれる係数の範囲（感度分析）

与えられた解に対応する双対解 $y$ を求め、すべての $j$ で被約費用 $c_{j} - A_{j}^{⊤} y \leq 0$ となる条件を不等式として解いて、目的関数の係数 $c$ をどこまで変えても同じ点が最適解であり続けるか（例: $c$ の最大値）を求められる

前提

相補性条件（大学数学最適化・線形計画法）

この技能までの道筋（50 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

三角形の角の大きさ（算数平面図形）
対頂角と平行線の同位角・錯角（中学数学平面図形）
三角形の外角と角の組み合わせ（中学数学平面図形）
小数の四則計算（算数計算と数のきまり）
分数のたし算・ひき算（算数計算と数のきまり）
分数のかけ算・わり算（算数計算と数のきまり）
小数と分数のまじった計算（算数計算と数のきまり）
逆算（□ を求める）（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
1 次方程式の解き方（中学数学方程式）
二等辺三角形の角（中学数学平面図形）
平行四辺形と特別な四角形の性質（中学数学平面図形）
三角形・四角形の面積（算数平面図形）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
三平方の定理（中学数学相似と三平方の定理）
乗法公式による展開（中学数学数と式）
折り返した図形の角と長さ（中学数学平面図形）
三平方の定理と平面図形（中学数学相似と三平方の定理）
最大公約数と最小公倍数（算数整数の性質）
比の性質と簡単な比（算数割合と比）
相似な三角形と長さの比（算数平面図形）
三角形の相似条件と対応する辺の長さ（中学数学相似と三平方の定理）
平行線と線分の比（中学数学相似と三平方の定理）
2点間の距離と内分点・外分点（数学II 図形と方程式）
比例・反比例の式とグラフ（中学数学関数）
関数 $y = a x^{2}$ の式と変域（中学数学関数）
因数分解（中学数学数と式）
平方完成と 2 次関数のグラフ（数学I 2次関数）
円の方程式（数学II 図形と方程式）
連立方程式の解き方（加減法・代入法）（中学数学方程式）
1 次関数の式の求め方（中学数学関数）
直線の方程式（数学II 図形と方程式）
不等式の表す領域（数学II 図形と方程式）
点と直線の距離（数学II 図形と方程式）
2 次不等式（数学I 2次関数）
円と直線の位置関係と弦の長さ（数学II 図形と方程式）
2直線の平行・垂直（数学II 図形と方程式）
円の接線（数学II 図形と方程式）
領域における最大・最小（数学II 図形と方程式）
ベクトルの演算と成分（数学C ベクトル）
行列の和・積と 2 次の逆行列（大学数学線形代数）
線形計画問題の定式化と標準形（大学数学最適化・線形計画法）
双対問題と双対定理（大学数学最適化・線形計画法）
相補性条件（大学数学最適化・線形計画法）

説明

線形計画問題で最適解 $x^{*}$ がすでに分かっているとき、目的関数の係数 $c_{j}$ の 1 つを変えても $x^{*}$ が最適解のままでいられる範囲を求めます。これを感度分析といいます。利益や費用の見積もりが変わったとき、生産計画などを立て直す必要があるかどうかを、問題を解き直さずに判断できます。道具は、相補性条件で求める双対解 $y$ と、被約費用 $c_{j} - A_{j}^{⊤} y$ の符号だけです。

なぜそうしてよいのか

主問題を「 $max c^{⊤} x$ 、 $A x \leq b$ 、 $x \geq 0$ 」、双対問題を「 $min b^{⊤} y$ 、 $A^{⊤} y \geq c$ 、 $y \geq 0$ 」とします。 $A_{j}$ は $A$ の第 $j$ 列です。実行可能な $x^{*}$ と $y$ が次の 2 つを満たすとします。(i) 双対の実行可能性： $y \geq 0$ であり、すべての $j$ で $A_{j}^{⊤} y \geq c_{j}$ 、つまり被約費用 $c_{j} - A_{j}^{⊤} y \leq 0$ 。(ii) 相補性条件。このとき (ii) から $c^{⊤} x^{*} = y^{⊤} A x^{*} = b^{⊤} y$ が成り立ちます。弱双対性から、どの実行可能解 $x$ についても $c^{⊤} x \leq b^{⊤} y$ なので、 $x^{*}$ は最適解です。逆に $x^{*}$ が最適なら、双対定理により (i)(ii) を満たす $y$ が必ず存在します。

そこで、変える係数を文字 $t$ とおきます。 $t$ を変えても、 $x^{*}$ が実行可能であることや、どの制約に余裕があるかは変わりません。変わるのは双対解 $y$ だけで、 $y$ は相補性条件の連立方程式から $t$ の式として求まります。この $y (t)$ について (i) の不等式を解けば、それが $x^{*}$ が最適であり続ける $t$ の条件です。相補性条件で $y$ がただ 1 つに決まる場合（よくある非退化の場合）は、この条件が必要かつ十分になります。

$y \geq 0$ も被約費用の条件の一部と考えられます。第 $i$ 制約のスラック変数は、列が単位ベクトル $e_{i}$ 、係数が $0$ なので、その被約費用は $0 - e_{i}^{⊤} y = - y_{i}$ です。これが $\leq 0$ であることが $y_{i} \geq 0$ にあたります。

手順

変えたい係数を文字 $t$ とおく。 $x_{j}^{*} > 0$ となる $j$ と、 $x^{*}$ を代入して余裕（不等号が等号にならない）がある制約 $i$ を調べる。
相補性条件で連立方程式を立てる。余裕のある制約では $y_{i} = 0$ 、 $x_{j}^{*} > 0$ の $j$ では $A_{j}^{⊤} y = c_{j}$ とし、 $y$ を $t$ の式として解く。
$x_{j}^{*} = 0$ の各変数について、被約費用の条件 $c_{j} - A_{j}^{⊤} y (t) \leq 0$ を書く。
すべての $i$ について $y_{i} (t) \geq 0$ （スラック変数の被約費用 $\leq 0$ ）を書く。
3・4 の不等式をすべて解き、共通部分をとる。これが求める $t$ の範囲になる。

例題

線形計画問題「最大化 $z = c x_{1} + 3 x_{2} + 2 x_{3}$ 、制約 $x_{1} + x_{2} + x_{3} \leq 4$ 、 $x_{1} + 2 x_{2} \leq 6$ 、 $x_{1} \leq 3$ 、 $x_{1}, x_{2}, x_{3} \geq 0$ 」を考える。 $x^{*} = (2, 2, 0)$ がこの問題の最適解となるような $c$ の範囲を求めよ。

例題の解答

【手順1】係数 $c$ を変数として扱う。 $x^{*}$ では $x_{1}^{*} = 2 > 0$ 、 $x_{2}^{*} = 2 > 0$ 、 $x_{3}^{*} = 0$ である。制約に代入すると $2 + 2 + 0 = 4$ （等号）、 $2 + 4 = 6$ （等号）、 $2 < 3$ （余裕あり）となる。

【手順2】第 3 制約に余裕があるので $y_{3} = 0$ 。 $x_{1}^{*} > 0$ から $y_{1} + y_{2} + y_{3} = c$ 、 $x_{2}^{*} > 0$ から $y_{1} + 2 y_{2} = 3$ 。これを解くと $y_{2} = 3 - c$ 、 $y_{1} = 2 c - 3$ となる。

【手順3】 $x_{3}^{*} = 0$ である。 $x_{3}$ の列は $(1, 0, 0)^{⊤}$ なので、被約費用の条件は $2 - y_{1} \leq 0$ 、つまり $2 - (2 c - 3) \leq 0$ となり、 $c \geq \frac{5}{2}$ 。

【手順4】 $y_{1} = 2 c - 3 \geq 0$ より $c \geq \frac{3}{2}$ 。 $y_{2} = 3 - c \geq 0$ より $c \leq 3$ 。 $y_{3} = 0 \geq 0$ は常に成り立つ。

【手順5】共通部分は $\frac{5}{2} \leq c \leq 3$ である。この範囲では $y = (2 c - 3, 3 - c, 0)$ が双対実行可能で、相補性条件も満たすので、 $x^{*}$ は最適解になる。範囲の外では、相補性条件から $y$ がただ 1 つに決まり、それが双対実行可能でないので、 $x^{*}$ は最適解でない。

（確認） $c = 3$ のとき目的関数は $3 x_{1} + 3 x_{2} + 2 x_{3}$ で、 $x_{1}$ と $x_{2}$ の係数が第 1 制約と同じ比 $1 : 1$ になる。この $c$ を超えると、最適解は $x_{1}$ を増やす方向の頂点へ移る。

答え: $[\frac{5}{2}, 3]$

よくある誤り

$x_{j}^{*} = 0$ の変数の被約費用だけを調べ、 $y_{i} \geq 0$ を忘れてしまう誤り。例題では $c \geq \frac{5}{2}$ だけが残り、上限を見落とす。正しくは $y_{2} = 3 - c \geq 0$ も課して $c \leq 3$ を得る。
もとの係数で求めた双対解 $y$ の数値を固定したまま使ってしまう誤り。例えば $c = \frac{11}{4}$ で求めた $y = (\frac{5}{2}, \frac{1}{4}, 0)$ を使うと、 $x_{1}$ の被約費用は $c - \frac{11}{4} \leq 0$ となり、範囲を取り違える。正しくは、係数を $t$ とおいて相補性条件を解き直し、 $y$ を $t$ の式で表す。
最小化問題でも不等号の向きをそのまま使ってしまう誤り。「 $min c^{⊤} x$ 、 $A x \geq b$ 、 $x \geq 0$ 」では双対制約が $A^{⊤} y \leq c$ になるので、正しくは被約費用 $c_{j} - A_{j}^{⊤} y \geq 0$ を課す。
端点を除いて開区間 $(\frac{5}{2}, 3)$ と答えてしまう誤り。端点では被約費用が $0$ または $y_{i} = 0$ となり、最適解が複数になる。それでも $x^{*}$ は最適解の 1 つなので、「最適解であり続ける範囲」には端点を含めて $[\frac{5}{2}, 3]$ とする。「ただ 1 つの最適解であり続ける範囲」を問われたときに限り、端点を除いて考える。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能を使う問題

難易度 4（大学院入試の標準レベル）
$c$ を実数の定数とし、次の線形計画問題 $(P_{c})$ を考える。
$(P_{c}) maximize subject to 4 x_{1} + 5 x_{2} + c x_{3} x_{1} + 2 x_{2} + x_{3} \leq 10, 3 x_{1} + x_{2} + 2 x_{3} \leq 15, x_{1}, x_{2}, x_{3} \geq 0.$
点 $x^{*} = (x_{1}, x_{2}, x_{3}) = (4, 3, 0)$ が $(P_{c})$ の最適解となるような $c$ の最大値を求めよ。