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

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

線形計画法の等式標準形

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

問題P

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

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

変数 xx を動かして目的関数 cxc^{\top}x を最小にしたいという問題です。AAm×nm\times n 行列,x,cx,cnn 次元縦ベクトル,bbmm 次元縦ベクトルです。 x0x\geq 0 というのは xx の各成分が非負という意味です。

例1

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

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

A=(121011)A=\begin{pmatrix}1&2&1\\0&1&-1\end{pmatrix}b=(31)b=\begin{pmatrix}3\\1\end{pmatrix} とすれば上記の形になる(m=2,n=3m=2,n=3)。

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

双対問題

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

問題D

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

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

例2

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

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

弱双対定理とその証明

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

弱双対定理

Pの任意の実行可能解 xx と,Dの任意の実行可能解 yy に対して bycxb^{\top} y\leq c^{\top} x

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

弱双対定理の証明

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

yy がDの実行可能解のとき,AycA^{\top}y\leq c

以上の式より,

by=xAyxc=cxb^{\top}y= x^{\top} A^{\top}y\leq x^{\top} c=c^{\top} x

強双対定理

強双対定理

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

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

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

双対定理の嬉しさ:最適性の証拠

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

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

例題

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

解答

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

  • x1=1,x2=1,x3=0x_1=1,x_2=1,x_3=0 は主問題P(例1)の実行可能解であり,目的関数値は 11 である。
  • y1=0,y2=1y_1=0,y_2=1 は双対問題D(例2)の実行可能解であり,目的関数値は 11 である。

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

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