相補性条件

主問題の最適解 $x^{*}$ が与えられたとき、相補性条件「 $x_{j}^{*} > 0$ なら双対の第 $j$ 制約は等号」「主の第 $i$ 制約に余裕があれば $y_{i} = 0$ 」から連立方程式を立て、双対問題の最適解 $(y_{1}, y_{2}, y_{3})$ を求められる

前提

双対問題と双対定理（大学数学最適化・線形計画法）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

三角形の角の大きさ（算数平面図形）
対頂角と平行線の同位角・錯角（中学数学平面図形）
三角形の外角と角の組み合わせ（中学数学平面図形）
小数の四則計算（算数計算と数のきまり）
分数のたし算・ひき算（算数計算と数のきまり）
分数のかけ算・わり算（算数計算と数のきまり）
小数と分数のまじった計算（算数計算と数のきまり）
逆算（□ を求める）（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
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^{*}$ がわかっていれば、双対問題を一から解かなくても、その最適解 $y^{*}$ を連立一次方程式で求められます。そのとき使うのが「相補性条件」で、主と双対の最適解どうしが満たす関係です。双対変数は各制約の資源の「価値」（潜在価格）を表します。そのため、資源を増やしたときの効果を調べたり、与えられた $x^{*}$ が本当に最適かを確かめたりする場面でも役に立ちます。

なぜそうしてよいのか

主問題 $max c^{⊤} x$ , $A x \leq b$ , $x \geq 0$ と、双対問題 $min b^{⊤} y$ , $A^{⊤} y \geq c$ , $y \geq 0$ を考えます。 $x$ と $y$ がどちらも実行可能なら、弱双対性は次の 2 段の不等式からできています。 $c^{⊤} x \leq (A^{⊤} y)^{⊤} x = y^{⊤} A x \leq y^{⊤} b$ 1 つ目の $\leq$ は $x \geq 0$ と $A^{⊤} y \geq c$ から、2 つ目の $\leq$ は $y \geq 0$ と $A x \leq b$ から出ます。

強双対定理より、最適解の組 $x^{*}, y^{*}$ では $c^{⊤} x^{*} = b^{⊤} y^{*}$ です。したがって 2 つの $\leq$ はどちらも等号になります。1 つ目の差は $\sum_{j} x_{j}^{*} ((A^{⊤} y^{*})_{j} - c_{j}) = 0$ と書けます。各項は（0 以上）×（0 以上）なので、和が 0 ならどの項も 0 です。よって $x_{j}^{*} > 0$ なら $(A^{⊤} y^{*})_{j} = c_{j}$ 、つまり双対の第 $j$ 制約は等号です。同じように 2 つ目の差 $\sum_{i} y_{i}^{*} (b_{i} - (A x^{*})_{i}) = 0$ から、 $(A x^{*})_{i} < b_{i}$ （主の第 $i$ 制約に余裕がある）なら $y_{i}^{*} = 0$ となります。

直観的には、次のように理解できます。使い切っていない資源を 1 単位増やしても利益は増えないので、その資源の価値 $y_{i}$ は 0 です。また、実際に作っている製品 $j$ では、使う資源の価値の合計が利益 $c_{j}$ とちょうど釣り合います。逆向きも成り立ちます。実行可能な $x$ , $y$ がこの 2 つの条件を満たせば、両方の不等式が等号になって $c^{⊤} x = b^{⊤} y$ となります。すると弱双対性により、 $x$ も $y$ も最適だとわかります。

手順

主問題から双対問題 $min b^{⊤} y$ , $A^{⊤} y \geq c$ , $y \geq 0$ を書き下す。
$x_{j}^{*} > 0$ となる各 $j$ について、双対の第 $j$ 制約を等号にした式 $(A^{⊤} y)_{j} = c_{j}$ を立てる。
$x^{*}$ を主の各制約に代入する。 $(A x^{*})_{i} < b_{i}$ （余裕がある）となる $i$ について $y_{i} = 0$ とおく。
手順 2・3 の式を連立して $y$ を求める。解がただ 1 つに決まらない場合（退化などで式が足りないとき）は、解の全体を文字を使って表す。その中から $y \geq 0$ と双対の残りの制約をすべて満たすものを探す。
求めた $y$ が $y \geq 0$ と双対の全制約を満たすか確かめる。さらに $b^{⊤} y = c^{⊤} x^{*}$ が成り立つことを確かめ、最適性を確認する。

例題

主問題 $max 3 x_{1} + 2 x_{2}$ , 制約 $x_{1} + x_{2} \leq 4$ , $x_{1} + 2 x_{2} \leq 6$ , $2 x_{1} + x_{2} \leq 7$ , $x_{1}, x_{2} \geq 0$ の最適解は $x^{*} = (3, 1)$ である。相補性条件を用いて、双対問題の最適解 $(y_{1}, y_{2}, y_{3})$ を求めよ。

例題の解答

手順 1: 双対問題は $min 4 y_{1} + 6 y_{2} + 7 y_{3}$ です。制約は $y_{1} + y_{2} + 2 y_{3} \geq 3$ , $y_{1} + 2 y_{2} + y_{3} \geq 2$ , $y_{1}, y_{2}, y_{3} \geq 0$ です。
手順 2: $x_{1}^{*} = 3 > 0$ より $y_{1} + y_{2} + 2 y_{3} = 3$ です。 $x_{2}^{*} = 1 > 0$ より $y_{1} + 2 y_{2} + y_{3} = 2$ です。
手順 3: $x^{*}$ を主の制約に代入します。第 1 制約は $3 + 1 = 4$ （等号）、第 2 制約は $3 + 2 = 5 < 6$ （余裕あり）、第 3 制約は $6 + 1 = 7$ （等号）です。よって $y_{2} = 0$ です。
手順 4: $y_{2} = 0$ を代入すると $y_{1} + 2 y_{3} = 3$ , $y_{1} + y_{3} = 2$ です。辺々引いて $y_{3} = 1$ 、したがって $y_{1} = 1$ です。未知数 3 個に対して独立な式が 3 本あるので、解はこの 1 つに決まります。
手順 5: $(1, 0, 1)$ の成分はすべて 0 以上です。双対の 2 つの制約も等号で満たすので、実行可能です。双対の目的関数値は $4 \cdot 1 + 6 \cdot 0 + 7 \cdot 1 = 11$ 、主の値は $3 \cdot 3 + 2 \cdot 1 = 11$ で一致します。弱双対性より、両方とも最適です。

答え: $(1, 0, 1)$

よくある誤り

主の制約が等号で成り立っていれば $y_{i} > 0$ だと決めてしまう誤り。正しくは、相補性条件が言うのは「余裕あり $\Rightarrow$ $y_{i} = 0$ 」だけです。 $(A x^{*})_{i} = b_{i}$ のときに $y_{i} = 0$ となることもあります（退化した最適解など）。
$x_{j}^{*} = 0$ なら双対の第 $j$ 制約に余裕がある（ $(A^{⊤} y)_{j} > c_{j}$ ）と決めてしまう誤り。正しくは、 $x_{j}^{*} = 0$ からは何も言えず、等号 $(A^{⊤} y)_{j} = c_{j}$ になることもあります。等号の式を立てるのは $x_{j}^{*} > 0$ となる $j$ だけです。
条件の向きを取り違えて、「 $y_{i} > 0$ ならば主の第 $i$ 制約は等号」を $y$ を求める式として使う誤り。この命題自体は正しいものの、 $y$ が未知なので、 $y$ を決める式にはなりません。正しくは、既知の $x^{*}$ から判定できる 2 つの条件「 $x_{j}^{*} > 0 \Rightarrow (A^{⊤} y)_{j} = c_{j}$ 」と「 $(A x^{*})_{i} < b_{i} \Rightarrow y_{i} = 0$ 」を使います。
連立方程式の解をそのまま答えにして、確認を省く誤り。 $x^{*}$ が最適なら、双対の最適解 $y^{*}$ は手順 2・3 の連立方程式を必ず満たします。しかし逆に、連立方程式の解がそのまま双対の実行可能解になるとは限りません。得られた $y$ が $y \geq 0$ と双対の全制約を満たし、 $b^{⊤} y = c^{⊤} x^{*}$ となることを確かめて初めて最適と言えます。なお、連立方程式の解がただ 1 つに決まり、それが $y \geq 0$ または双対の制約を破るなら、与えられた $x^{*}$ は最適ではありません。

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

入口の問題

この技能を使う問題

この技能の次に学べること

最適性が保たれる係数の範囲（感度分析）（大学数学最適化・線形計画法）