双対定理

弱双対定理と(強)双対定理

主問題の任意の実行可能解x1, . . . , xn と双対問題の任意の実行可能解y1, . . . , ym に対して、

常に

c1x1+c2x2+· · ·+cnxn ≤b1y1+b2y2+· · ·+bmym (1.44) がなりたちます．これは弱双対定理と呼ばれています．主問題が最大化問題であったとき，任意の 実行可能解で評価した主問題の目的関数値は，任意の実行可能解で評価した双対問題の目的関数値

を下回るということを主張しています．1.5.1節の例で考えると，買収総額(双対問題の目的関数 値)が少くとも工場の売上(主問題の目的関数値)以上ないと，買収はできないということです．

(1.44)は次の式によって確かめることができます．

∑n j=1

c_jx_j≤∑ⁿ

j=1

(_m

∑

i=1

a_ijy_i )

x_j=∑^m

i=1



∑ⁿ

j=1

a_ijx_j



y_i≤∑^m

i=1

b_iy_i

弱双対定理を使って，直ちに次の主張が成り立ちます．もし、主問題の実行可能解(x1, . . . ,xn) と、双対問題の実行可能解(y₁, . . . ,y_m)が、

c₁x₁+c₂x₂+· · ·+c_nx_n=b₁y₁+b₂y₂+· · ·+b_my_m であったならば、(x1, . . . ,xn)と(y1, . . . ,ym)はそれぞれ最適解です．

定理1.1 (双対定理)

主問題(1.38)が最適解(x^∗₁, . . . , x^∗_n)を持てば、双対問題(1.39)も最適解(y^∗₁, . . . , y^∗_m)をもち、

しかも ∑n

j=1

c_jx^∗_j =∑^m

i=1

b_iy^∗_i

を満たす．

[証明] (この証明は参考とします)

仮定より主問題には最適解が存在するので、単体法によって最適辞書をえることができ、最適 辞書においては目的関数は以下のように表現されている．

z=z^∗+^n+m∑

j=1

c_jx_j (1.45)

ここで、xjが基底変数であるとき，対応する係数はcj=0となり、非基底変数のときはcj≤0 であることに注意．

主問題の目的関数は、

z=

∑n j=1

cjxj (1.46)

なので、z^∗は、主問題の最適解(x^∗₁, . . . , x^∗_n)によって z^∗=∑ⁿ

j=1

cjx^∗_j (1.47)

と書くこともできる．

ここで、

y^∗_i = −c_n+i≥0, i=1, . . . , m (1.48) とおくことで，y^∗_i, i=1, . . . , m が最適双対実行可能解となることを示す．

(1.45)の左辺をスラック変数とそうでない変数にわけて表記する．

z=z^∗+

∑n j=1

cjxj+

∑m i=1

cn+ixn+i

=z^∗+∑ⁿ

j=1

c_jx_j−∑^m

i=1

y^∗_ix_n+i (1.49)

スラック変数の定義より

z=z^∗+∑ⁿ

j=1

c_jx_j−∑^m

i=1

y^∗_i(b_i−∑ⁿ

j=1

a_ijx_j)

= (z^∗−

∑m i=1

biy^∗_i) +

∑n j=1

(cj+

∑m i=1

aijy^∗_i)xj (1.50)

となる．

これらの変形は代入による等価な変型を行っているので、(1.46)と(1.50)は恒等的に等しい．

したがって、

∑n j=1

c_jx_j= (z^∗−∑^m

i=1

b_iy^∗_i) +∑ⁿ

j=1

(c_j+∑^m

i=1

a_ijy^∗_i)x_j

の両辺の係数は等しくなくてはならないので、

∑m i=1

b_iy^∗_i =z^∗

cj+

∑m i=1

aijy^∗_i =cj, j=1, . . . , n

を満たす必要がある．

cj≤0であることから、二本目の式は、双対問題(D)の制約条件にほかならない．主問題の最 適辞書から構成した(y^∗₁, . . . , y^∗_m)は、双対問題の実行可能解で、さらにその目的関数値は双対問 題の解の下限を達成しているので最適解となることがわかった．

[証明終]

主問題と双対問題の関係

双対定理より，主問題と双対問題のあいだには、表1.23の関係があることがわかります．行方 向に見て，×はその組合わせが不可能であることを表し，○は可能であることを示しています．例 えば，主問題が非有界であるとき，双対問題は必ず実行不可能です．一方，主問題が実行不可能で あるときは，双対問題は非有界であるか，実行不可能です．

図表 1.23主問題と双対問題の関係

双対問題

最適解 非有界 実行不可能 主問題

最適解 ○ × ×

非有界 × × ○

実行不可能 × ○ ○

相補スラック定理

定理1.2 (相補スラック定理)

x^∗ = (x^∗₁, . . . , x^∗_n)^>を主問題(1.38)の実行可能解、y^∗= (y^∗₁, . . . , y^∗_m)^>を双対問題(1.39)の 実行可能解とする．このとき、x^∗とy^∗がそれぞれ最適解となるための必要十分条件は、以下 の関係が成り立つことである．

すべてのj=1, . . . , nについて

∑m i=1

aijy^∗_i =cjまたはx^∗_j =0 (1.51)

すべてのi=1, . . . , mについて

∑n j=1

aijx^∗_j =bi またはy^∗_i =0 (1.52)

[証明]

x^∗とy^∗が実行可能解であることから、以下の不等式が成り立つ．

∑n j=1

c_jx^∗_j ≤∑ⁿ

j=1

(∑^m

i=1

a_ijy^∗_i)x^∗_j =∑^m

i=1

(∑ⁿ

j=1

a_ijx^∗_j)y^∗_i ≤∑^m

i=1

b_iy^∗_i (1.53)

条件(1.51)と(1.52)が成り立っていれば、(1.53))はすべて等号が成立し、主問題と双対問題の目

的関数値が一致するので、x^∗とy^∗は最適解である．

逆に、(1.53)の等号が成立するためには、条件(1.51)と(1.52)が成り立つことが必要である．

[証明終]

相補スラック定理の主張は，次のように解釈するとよいでしょう．主問題と双対問題の最適解 x^∗₁, . . . , x^∗_n, y^∗₁, . . . , y^∗_mが与えられたとします．y^∗_i > 0であるならば，主問題のi番目の制約式は かならず有効となっている(等号が成立している)はずです．また，y^∗_i =0なら主問題のi番目の 制約式は有効ではありません¹³．

潜在価格

潜在価格は，最適な生産を行っているときにシステム内で決まる資源の価格と見なすことがで きます．資源の買収金額決定問題(1.37)で得られる最小買収額が，家具工場の最適生産計画決定

13厳密には，\退化"と呼ばれる状態も考慮しなくてはなりませんが，ここでは扱いません．

問題(1.34)で得られる最適な生産による売上額と等しいこと，双対変数y1，y2，y3が，それぞれ 木材，金属，ガラスの資源ごとに設定された買収価格であること，はすでに見た通りです．

(1.34)の最適解は(x^∗₁, x^∗₂) = (4, 2)，(1.37)の最適解は(y^∗₁, y^∗₂, y^∗₃) = (1, 1, 0)でした．相補ス ラック定理より，正の潜在価格がついている木材と金属に対しては，

x^∗₁+x^∗₂=6, 2x^∗₁+x^∗₂=10

が成り立ち，生産によって資源を使いきっています．一方，資源を使いきらないガラスについては，

潜在価格は0です．

正の生産量があるテーブルとシェルフにおいては，

テーブル：y^∗₁+2y^∗₂=3 シェルフ：y^∗₁+y^∗₂+y^∗₃=2

が成り立ちます．これは，テーブル1単位の生産に必要な資源を潜在価格で評価した値が，製品価 格3に等しいことを示しています(シェルフについても同様です)．

基底形式表現における双対変数

主問題の最適解を与える基底形式表現(以下，最適辞書)が得られているなら，双対問題を解か なくても双対問題の最適解がわかります．問題(1.38)の最適辞書の目的関数の係数が，双対問題 の最適解を与えています．理論的な関係は双対定理の証明(40ページ)に書かれているので，詳し く知りたい人は目を通してください．結果のみを記すと，主問題の最適辞書における非基底変数 x_n+iの係数が−^c_n+i であるならば，y^∗_i = ^c_n+iとなります．それ以外，値は0です．

(1.34)で確認しましょう．この問題の最適辞書は(1.32) です．x3の係数が−1なのでy^∗₁=1，

x4の係数が−1なのでy^∗₂=1です．それ以外については，y^∗₃=0です．

ちなみに，線形計画問題を解くソフトウェアには，問題を解いたときに，主問題の最適解／最 適値と同時に，その双対問題の最適解を表示する機能が実装されているのが普通です．

1.5.4 感度分析２

この節では，1.4.6節に引き続き感度分析を説明します．今回は，右辺の値が変化した場合，最 適値がどのように変化するかを見てみましょう．主問題の右辺が





 b₁ b2

...

bm





 =⇒







b₁+₁ b2+2

...

bm+m







と変化したとします．右辺の値の変化は，ただちに基底変数の値に影響をおよぼします．しかし，

辞書の目的関数の係数には影響しないことを確かめてください．したがって，_i(i=1, . . . , m)が 十分小さく，その辞書の最適性が保たれるならば，双対変数の値は変化しません．この事実を利用 すると，右辺の変化が，最適値におよぼす影響を双対変数を利用して評価することができます．双 対定理より，最適値z^∗について，

z^∗=c1x^∗₁+c2x^∗₂+· · ·+cnx^∗_n =b1y^∗₁+b2y^∗₂+· · ·+bmy^∗_m

が成り立っています．右辺が(b1+1, b2+2, . . . , bn+n)に変化したあとは，新しい最適値z^† は

z^† = (b1+1)y^∗₁+ (b2+2)y^∗₂+· · ·+ (bm+m)y^∗_m となります．変化量のみを評価するのであれば，

z^†−z^∗=₁y^∗₁+₂y^∗₂+· · ·+_my^∗_m (1.54) となります．

資源の追加投入

1.4.6節の家具工場の問題を例にとります．問題(1.34)の最適辞書を再度挙げておきました．

z= 16 −x₃ −x₄ x1= 4 +x3 −x4

x₂= 2 −2x₃ +x₄ x₅= 1 +2x₃ −x₄

(1.32)

主問題の最適解は(x^∗₁, x^∗₂, x^∗₃, x^∗₄, x^∗₅) = (4, 2, 0, 0, 1)，双対問題の最適解は(y^∗₁, y^∗₂, y^∗₃) = (1, 1, 0) です．

最適な生産計画ではガラスは全てを使い切ってはいません．直感的にも，あまっている資源を 追加投入しても，最適値は変化しないことが予想されるでしょう．実際， ガラスを3だけ増やし ても，ガラスの潜在価格(y^∗₃)は0なので，(1.54)より最適値の変化量も0です．

木材を追加する場合，木材の潜在価格y^∗₁は1なので，₁の追加に対して，最適値もちょうど 1だけ増加します(ただし，^∗₁は十分小さいものとします)．1=0.2とおき，x1，x2，x5を基 底変数として計算した結果，次の基底形式表現を得ました．

z= 16.2 −x₃ −x₄ x1= 3.8 +x3 −x4

x₂= 2.4 −2x₃ +x₄ x5= 0.6 +2x3 −x4

(1.55)

実行可能でかつ，目的関数の係数も不変であることから，最適性は保たれています．最適解が (x^∗₁, x^∗₂, x^∗₃, x^∗₄, x^∗₅) = (4, 2, 0, 0, 1)から(3.8, 2.4, 0, 0, 0.6)へ変化しています．最適値が16から16.2 になっているのは，木材の変化量₁=0.2に，木材の潜在価格y^∗₁=1をかけた量に相当する分が 増加しているからです．

市場からの調達

木材を市場から調達するコストについて考えてみましょう．工場が最適な生産を行っている場 合，木材の潜在価格は1です．この場合，上で見たように木材を₁単位追加することで，最適値 を1×₁だけ増やすことができます．したがって，もし木材の市場価格が1より小さければ，市 場で調達することで利益を増加させることができます．一方，木材の市場価格が1以上であれば，

市場で調達しても利益を挙げることができません．

図表1.24木材の追加による解の変化(0≤1≤0.6)

1 0 0.1 0.2 0.3 0.4 0.5 0.6

z 16.0 16.1 16.2 16.3 16.4 16.5 16.6

x₁ 4.0 3.9 3.8 3.7 3.6 3.5 3.4

x2 2.0 2.2 2.4 2.6 2.8 3.0 3.2

x₅ 1.0 0.8 0.6 0.4 0.2 0.0 -0.2

資源の追加投入にともなう解の変化

表1.24に，1を0から増やしていったときのx1，x2，x5の値の変化をまとめました．

木材を増やしていくと最適解が変化していってます．このとき，x₂は増加しますが，x₁とx₅ は減少します1=0.5のところで，x5はちょうど0に達し，以後負の値を取ります．1≥0.5に おいては，この辞書は実行可能性を保てなくなるので，基底の入れ替えが必要になります．

x₃を基底解に，x₅を非基底解に入れ直し，₁=0.5，右辺をb= (6.5, 10, 3)として，新しい基 底形式表現を計算しました．

z= 16.5 −1.5x₄ −0.5x₅ x1= 3.5 −0.5x4 +0.5x4

x₂= 3.5 −x₄

x3= 0.0 +0.5x4 +0.5x4

(1.56)

表1.25は₁を0.5から1.0まで変化させたときの解と最適値の変化です．

図表1.25木材の追加による解の変化(₁≥0.5)

₁ 0.5 0.6 0.7 0.8 0.9 1.0

z 16.5 16.5 16.5 16.5 16.5 16.5 x₁ 3.5 3.5 3.5 3.5 3.5 3.5 x2 3.0 3.0 3.0 3.0 3.0 3.0 x₃ 0.0 0.1 0.2 0.3 0.4 0.5

1> 5の区間では，y1=0，y2=1.5，y3=0となっているので，木材をいくら追加しても最 適値は改善しません．

木材の量を0から8まで変化させたときの目的関数値の変化を図表1.26に示しました．最大化 の線形計画問題においては，右辺の値に対して目的関数の値をグラフにとると，区分的に線形な凹 関数になることが知られています．グラフの傾きが木材の潜在価格に相当することに気をつけてく ださい．

木材の保有量b₁が，0≤b₁≤5のとき木材の潜在価格は3です．5 < b₁≤6.5の区間では潜 在価格は1に低下し，b1> 6.5では0となります．資源の増加による効果が逓減していくことが 見て取れるでしょう．

新製品の価格

家具工場で，テーブルとシェルフに加えて，カップボードの生産を行うことが可能になったと します．カップボード1単位を作るのに必要な資源の量は，木材3単位，金属3単位，ガラス2単 位で，その価格は5です．この条件でカップボードが生産可能になったとして，はたして生産すべ きなのでしょうか．

ドキュメント内 ( ) () () ( ) () () () () (ページ 35-42)