線形計画法の双対定理の意味と嬉しさ

更新 2021/03/07

線形計画法の主問題・双対問題・双対定理について解説します。弱双対定理のみ証明します。最後に双対定理の嬉しさ（の一つ）を述べます。

線形計画法の等式標準形

全ての線形計画は以下の等式標準形と呼ばれる形で表現できます。

問題P

$\displaystyle\min_x\: c^{\top}x$

$\mathrm{s.t.}\:\:Ax=b, x\geq 0$

変数 $x$ を動かして目的関数 $c^{\top}x$ を最小にしたいという問題です。 $A$ は $m\times n$ 行列， $x,c$ は $n$ 次元縦ベクトル， $b$ は $m$ 次元縦ベクトルです。 $x\geq 0$ というのは $x$ の各成分が非負という意味です。

例1

$x_1+2x_2+x_3=3,x_2-x_3=1$ および $x_1,x_2,x_3\geq 0$ のもとで $x_2$ を最小化する問題は線形計画である。

実際， $c^{\top}=(0,1,0)$

$A=\begin{pmatrix}1&2&1\\0&1&-1\end{pmatrix}$ ， $b=\begin{pmatrix}3\\1\end{pmatrix}$ とすれば上記の形になる（ $m=2,n=3$ ）。

ちなみに，線形計画法は大学入試でもときどき登場します。→領域における最大・最小問題（線形計画法）

以下の問題Dを問題Pの双対問題と言います（元の問題Pを主問題と言います）。

問題D

$\displaystyle\max_{y}\: b^{\top}y$

$\mathrm{s.t.}\:\:A^{\top}y\leq c$

例2

さきほどの例1の双対問題は， $A^{\top}=\begin{pmatrix}1&0\\2&1\\1&-1\end{pmatrix}$ より，

$y_1\leq 0,2y_1+y_2\leq 1,y_1-y_2\leq 0$ のもとで $3y_1+y_2$ を最大化する問題である。これも線形計画。

主問題Pと双対問題Dの間には深い関係があります！

弱双対定理

Pの任意の実行可能解 $x$ と，Dの任意の実行可能解 $y$ に対して $b^{\top} y\leq c^{\top} x$

つまり，最大化問題Dの最適値は最小化問題Pの最適値以下というわけです！

弱双対定理の証明

$x$ がPの実行可能解のとき， $Ax=b,x \geq 0$

$y$ がDの実行可能解のとき， $A^{\top}y\leq c$

以上の式より，

$b^{\top}y= x^{\top} A^{\top}y\leq x^{\top} c=c^{\top} x$

問題P，問題Dがどちらも実行可能解を持つならば，どちらにも最適解が存在して，二つの問題の最適値は等しい。

つまり，両方の問題の最適解 $x^{*},y^{*}$ を取ってくれば弱双対定理の不等式の等号を満たす（ $c^{\top}x^{*}=b^{\top}y^{*}$ ）というわけです。

注：「問題P，問題Dがどちらも実行可能解を持つならば」を「問題Pまたは問題Dに最適解が存在するならば」に変えても成立します。

双対問題を考えるメリットの一つとして最適性の簡単な証拠を提示できるというのがあります。

強双対定理のおかげで，求めた答えが正しいことを簡単に他人に納得させることができます（どうやって答えを求めたかという複雑な手順を説明する必要がない）。

例題

さきほどの例1で $x_1=1,x_2=1,x_3=0$ が最適解であることを簡単に説明せよ。

解答

以下のことが簡単に確認できます。

上の二つの目的関数値は等しいので，強双対定理によりどちらも最適値が $1$ であり，上の解がそれぞれの問題の最適解であることが分かる！

未だに双対と共役の違いがいまいち分かりません。

この記事の監修者

マスオ

高校数学の美しい物語の管理人。「わかりやすいこと」と「ごまかさないこと」の両立を意識している。著書に『高校数学の美しい物語』『超ディープな算数の教科書』。記事の誤植やわかりにくい等のご指摘はお気軽にメールください！