線形計画の双対定理

線形計画問題の双対問題を書き下し、弱双対性・強双対性と相補性条件を使って、主・双対の最適解と最適値を求められる

前提

掃き出し法と連立 1 次方程式（大学数学線形代数）
領域における最大・最小（数学II 図形と方程式）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

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

説明

線形計画問題（1 次式の制約のもとで 1 次式を最大・最小にする問題）には、同じデータから作られる「双対問題」という相棒の問題がついています。双対問題の任意の実行可能解は元の問題の最適値の上界（または下界）を与え、両方に最適解があれば最適値どうしは一致します。この技能では、双対問題を書き下し、弱双対性・強双対性・相補性条件を使って、一方の最適解からもう一方の最適解と最適値を求めます。最適性の証明書を作るときや、制約の「価値」（シャドウプライス）を求めるときに使います。

なぜそうしてよいのか

次の形の問題（主問題）を考えます。 $(P) 最大化 c^{T} x 制約 A x \leq b, x \geq 0$ ここで $A$ は $m \times n$ 行列、 $b \in R^{m}$ 、 $c, x \in R^{n}$ で、ベクトルの不等式は成分ごとの不等式です。また $A^{T}$ は $A$ の行と列を入れ替えた $n \times m$ 行列（転置行列）で、 $(A^{T})_{j i} = A_{ij}$ と定めます。縦ベクトル $c$ の転置 $c^{T}$ は横ベクトルで、 $c^{T} x = \sum_{j} c_{j} x_{j}$ は内積です。

最大値を上から押さえたいので、 $i$ 番目の制約 $\sum_{j} A_{ij} x_{j} \leq b_{i}$ に重み $y_{i} \geq 0$ を掛けて足し合わせると $\sum_{i} y_{i} \sum_{j} A_{ij} x_{j} \leq \sum_{i} b_{i} y_{i}$ が得られます（ $y_{i} \geq 0$ なので不等号の向きは変わりません）。左辺を $x_{j}$ でまとめると、 $x_{j}$ の係数は $\sum_{i} A_{ij} y_{i} = (A^{T} y)_{j}$ 、つまり $A$ の $j$ 列目と $y$ の内積です。もしこの係数がどの $j$ についても $c_{j}$ 以上なら、 $x \geq 0$ より $c^{T} x \leq (A^{T} y)^{T} x = y^{T} A x \leq b^{T} y$ となり、 $b^{T} y$ が最大値の上界になります。最もよい（小さい）上界を探す問題が双対問題です。 $(D) 最小化 b^{T} y 制約 A^{T} y \geq c, y \geq 0$ 上の不等式の連鎖が、(P) の任意の実行可能解 $x$ と (D) の任意の実行可能解 $y$ について $c^{T} x \leq b^{T} y$ が成り立つという弱双対性です。特に、 $c^{T} x = b^{T} y$ となる実行可能な組が見つかれば、両方とも最適解です。

さらに強双対性という定理が成り立ちます: (P) が最適解をもてば (D) も最適解をもち、最適値は一致します（図形的には、最適な頂点で交わる制約直線の法線ベクトルを非負の重みで組み合わせると目的関数の係数ベクトル $c$ が作れる、ということに対応します）。

最適値が一致するとき、上の連鎖の 2 つの不等号はどちらも等号です。 $(A^{T} y - c)^{T} x = \sum_{j} x_{j} {(A^{T} y)_{j} - c_{j}} = 0$ で各項は $0$ 以上なので、各 $j$ で $x_{j} = 0$ または $(A^{T} y)_{j} = c_{j}$ 。同様に $y^{T} (b - A x) = 0$ から、各 $i$ で $y_{i} = 0$ または $(A x)_{i} = b_{i}$ 。これが相補性条件で、「主問題で余裕のある（等号でない）制約に対応する双対変数は 0、正の主変数に対応する双対制約は等号」と読めます。逆に、実行可能な $x, y$ が相補性条件を満たせば、上の連鎖がすべて等号になるので両方とも最適です。これにより、最適解を求める問題が連立 1 次方程式に帰着されます。

手順

主問題を「最大化 $c^{T} x$ 、 $A x \leq b$ 、 $x \geq 0$ 」の形に整え、 $A, b, c$ を読み取る。最小化 $c^{T} x$ なら $- c^{T} x$ の最大化に直す（最適値は符号を戻す）、 $\geq$ の制約は両辺に $- 1$ を掛けて $\leq$ にする、等式の制約は $\leq$ と $\geq$ の 2 本に分ける、符号に制約のない変数 $x_{j}$ は $x_{j} = x_{j}^{'} - x_{j}^{''}$ （ $x_{j}^{'}, x_{j}^{''} \geq 0$ ）と置き換える
双対問題「最小化 $b^{T} y$ 、 $A^{T} y \geq c$ 、 $y \geq 0$ 」を書き下す（主の制約 1 本ごとに双対変数 1 個、主の変数 1 個ごとに、 $A$ のその列を係数とする双対制約 1 本）
主問題の最適解 $x^{*}$ を求め（2 変数なら領域の頂点を調べる）、どの制約が等号で、どの変数が正かを調べる
相補性条件を書く: 等号でない主制約 $i$ には $y_{i} = 0$ 、 $x_{j}^{*} > 0$ の $j$ には $(A^{T} y)_{j} = c_{j}$
得られた連立 1 次方程式を解き、 $y \geq 0$ と $A^{T} y \geq c$ を満たすことを確かめる
$c^{T} x^{*} = b^{T} y^{*}$ を確認する（弱双対性より両方が最適であることの証明になる）

例題

線形計画問題 $最大化 3 x_{1} + 5 x_{2} 制約 x_{1} + x_{2} \leq 4, x_{1} + 3 x_{2} \leq 6, x_{1} \geq 0, x_{2} \geq 0$ の双対問題の最適解 $(y_{1}, y_{2})$ を求めよ。ただし $y_{1}, y_{2}$ はそれぞれ 1 本目、2 本目の制約に対応する双対変数とする。

例題の解答

手順 1: すでに標準形なので、 $A = (1113)$ , $b = (46)$ , $c = (35)$ 。

手順 2: $A$ の 1 列目 $(1, 1)$ と 2 列目 $(1, 3)$ を係数にして、双対問題は $最小化 4 y_{1} + 6 y_{2} 制約 y_{1} + y_{2} \geq 3, y_{1} + 3 y_{2} \geq 5, y_{1} \geq 0, y_{2} \geq 0.$

手順 3: 実行可能領域の頂点は $(0, 0), (4, 0), (3, 1), (0, 2)$ で、 $3 x_{1} + 5 x_{2}$ の値はそれぞれ $0, 12, 14, 10$ 。よって主問題の最適解は $x^{*} = (3, 1)$ 、最適値 $14$ 。このとき 2 本の制約はどちらも等号（ $3 + 1 = 4$ , $3 + 3 = 6$ ）で、 $x_{1}^{*} = 3 > 0$ , $x_{2}^{*} = 1 > 0$ 。

手順 4: $x_{1}^{*} > 0$ , $x_{2}^{*} > 0$ なので双対制約はどちらも等号: $y_{1} + y_{2} = 3, y_{1} + 3 y_{2} = 5.$ （主制約はどちらも等号なので、 $y_{i} = 0$ という条件は出てこない。）

手順 5: 2 式の差から $2 y_{2} = 2$ で $y_{2} = 1$ 、 $y_{1} = 2$ 。 $y_{1}, y_{2} \geq 0$ で、双対制約も（等号で）満たす。

手順 6: $4 \cdot 2 + 6 \cdot 1 = 14 = 3 \cdot 3 + 5 \cdot 1$ 。弱双対性より $y^{*} = (2, 1)$ は双対問題の最適解である。

答え: $(2, 1)$

よくある誤り

最大化問題の双対で、双対制約の不等号の向きや双対変数の符号を逆にしてしまう誤り。例題で $y_{1} + y_{2} \leq 3$ と書く、あるいは $y$ の非負条件を落とす。正しくは「最大化・ $A x \leq b$ ・ $x \geq 0$ 」の双対は「最小化・ $A^{T} y \geq c$ ・ $y \geq 0$ 」。
転置を忘れて $A y \geq c$ と書く誤り。例題の $A$ は対称（ $A^{T} = A$ ）なので結果が偶然同じになるが、 $A = (1021)$ なら $A y \geq c$ は $y_{1} + 2 y_{2} \geq c_{1}, y_{2} \geq c_{2}$ となって誤り。正しい双対制約は $A$ の列ごとに作った $y_{1} \geq c_{1}, 2 y_{1} + y_{2} \geq c_{2}$ 。
相補性条件を逆向きに使ってしまう誤り。「主制約が等号なら $y_{i} > 0$ 」「 $x_{j} = 0$ なら双対制約は等号でない」とするのは誤り。正しくは「主制約が等号でない $\Rightarrow y_{i} = 0$ 」「 $x_{j} > 0 \Rightarrow (A^{T} y)_{j} = c_{j}$ 」の向きだけが成り立つ（主制約が等号で $y_{i} = 0$ となる場合や、 $x_{j} = 0$ で双対制約も等号になる場合もある）。
相補性条件から出た連立方程式の解を、 $y \geq 0$ や残りの双対制約を確かめずに答えにしてしまう誤り。正しくは解が双対問題の実行可能解であることと、 $c^{T} x^{*} = b^{T} y^{*}$ を確かめて初めて最適と言える。

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

入口の問題

難易度 1（大学院の講義の例題レベル）
実数 $x_{1}, x_{2}$ についての線形計画問題 (P)
$maximize subject to 2 x_{1} + 3 x_{2} x_{1} + x_{2} \leq 4, x_{1} + 3 x_{2} \leq 6, x_{1} \geq 0, x_{2} \geq 0$
を考える。(P) の最適解は $(x_{1}, x_{2}) = (3, 1)$ であることがわかっている。(P) の 1 つ目の制約に対応する双対変数を $y_{1}$ 、2 つ目の制約に対応する双対変数を $y_{2}$ として双対問題 (D) を書き、相補性条件を用いて (D) の最適解 $(y_{1}, y_{2})$ を求めよ。

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

ラグランジュ双対関数と弱双対性（大学院数学凸最適化・組合せ最適化）
整数計画の線形計画緩和と整数性（大学院数学凸最適化・組合せ最適化）