第5回 双対問題 テキストp.42-56 内容 •双対問題の導出 式を足しあわせる方法 Lagrange緩和 •相補性条件 •双対辞書 •主問題と双対問題（一般論） 2000年12月 第4回 双対問題 1 問題 引き続き，あなたは丼チェーン店の店長だ．今日，丼チェ ーンの本社から，自社農場で飼育している豚，鶏，牛の肉 の価値を算出するよう指令が届いた．さて，トンコケ丼， コケトン丼，ミックス丼の販売価格から考えたとき，豚肉 ，鶏肉，牛肉の百グラムあたりの価値は何円と考えればよ いのだろうか？ こういうときは双対問題が便利 双対問題 ＝ もとの問題（主問題）と表裏一体を成す線形計画問題 2000年12月 第4回 双対問題 2 式を足し合わせることによる導出 上界：主問題の最適解以上であることが保証されている値 基本的アイディア： 式を足し合わせることによって上界を計算 2000年12月 第4回 双対問題 3 式を足し合わせることによる導出 目的関数は 15x1+18x2+30x3 の最大化 2 x1 x2 x3 60 x1 2 x2 x3 60 ) x3 30 3x1 3x2 3x3 150 30 x1 30 x2 30 x3 1500 15x1 18x2 30 x3 30 x1 30 x2 30 x3 1500 15x1+18x2+30x3 の上界は1500 最適値は1230であったので270のギャップ 2000年12月 第4回 双対問題 4 式を足し合わせることによる導出 目的関数は 15x1+18x2+30x3 の最大化 12 x1 6 x2 6 x3 360 6 x1 12 x2 6 x3 360 ) 20 x3 600 18x1 18x2 32 x3 1320 15x1 18x2 30 x3 18x1 18x2 32 x3 1320 最適値は1230であったので90のギャップ 2000年12月 第4回 双対問題 5 式を足し合わせることによる導出 目的関数は 15x1+18x2+30x3 の最大化 2 y1 x1 y1 x2 y1 x3 y1 60 y2 x1 2 y2 x2 y2 x3 y2 60 ) y3 x3 y3 30 ??? 2 y1 y2 x1 y1 2 y2 x2 y1 y2 y3 x3 60 y1 60 y2 30 y3 2000年12月 第4回 双対問題 6 式を足し合わせることによる導出 2 y1 y2 x1 y1 2 y2 x2 y1 y2 y3 x3 60 y1 60 y2 30 y3 これが15x1+18x2+30x3以上になるためには 15 2 y1 y2 18 y1 2 y2 30 y1 y2 y3 の必要あり，このとき上界は 60 y1 60 y2 30 y3 最もよい（小さい）上界を与えるy1 ，y2， y3を求める問題は？ 2000年12月 第4回 双対問題 7 双対問題 仕入れ価格の最小化 最小化 60 y1 60 y2 30 y3 条件 2 y1 y2 15 y1 2 y2 18 豚肉と鶏肉の価値 トンコケ丼の価値 y1 y2 y3 30 y1 , y2 , y3 0 それぞれの肉の百グラムあたりの価値（単位は百円） 2000年12月 第4回 双対問題 8 Lagrange緩和による方法 最大化 15x1+18x2+30x3 条件 2 x1 x2 x3 60 x1 2 x2 x3 60 x3 30 x1 , x2 , x3 0 最大化 15x1+18x2+30x3 +(60－2x1－x2－x3)y1 +(60－x1－2x2－x3)y2 +(30－x3)y3 条件 2 x1 x2 x3 60 x1 2 x2 x3 60 x3 30 非負 x1 , x2 , x3 , y1 , y2 , y3 0 主問題 最適値は主問題の上界 2000年12月 第4回 双対問題 9 Lagrange緩和による方法 最大化 15x1+18x2+30x3 +(60－2x1－x2－x3)y1 +(60－x1－2x2－x3)y2 +(30－x3)y3 条件 2 x1 x2 x3 60 最大化 (15－2y1－y2)x1 +(18－y1－2y2)x2 +(30－y1－y2－y3)x3 +60y1+60y2+30y3 条件 2 x1 x2 x3 60 x1 2 x2 x3 60 x1 2 x2 x3 60 x3 30 x1 , x2 , x3 , y1 , y2 , y3 0 x3 30 x1 , x2 , x3 , y1 , y2 , y3 0 目的関数をx1,x2,x3についてまとめる 2000年12月 第4回 双対問題 10 Lagrange緩和による方法 最大化 (15－2y1－y2)x1 +(18－y1－2y2)x2 +(30－y1－y2－y3)x3 +60y1+60y2+30y3 最大化 (15－2y1－y2)x1 +(18－y1－2y2)x2 +(30－y1－y2－y3)x3 +60y1+60y2+30y3 条件 2 x1 x2 x3 60 条件 x1 , x2 , x3 , y1 , y2 , y3 0 x1 2 x2 x3 60 x3 30 いくつかの条件を省く（緩和） x1 , x2 , x3 , y1 , y2 , y3 0 線形計画問題だけでなく， 一般的な最適化問題に対する フレームワーク 2000年12月 Lagrange緩和問題 第4回 双対問題 11 Lagrange緩和による方法 なるべくよい（なるべく小さい）上界を得ることを考える 最大化 (15－2y1－y2)x1 +(18－y1－2y2)x2 +(30－y1－y2－y3)x3 +60y1+60y2+30y3 ここが正だといくらでも大きくできる 非正でなければならない 条件 x1 , x2 , x3 , y1 , y2 , y3 0 他の係数についても同様 この条件のもとで目的関数のxに依存しない部分を最小化 2000年12月 第4回 双対問題 12 Lagrange緩和による方法 双対問題 最小化 60y1+60y2+30y3 条件 2 y1 y2 15 y1 2 y2 18 y1 y2 y3 30 y1 , y2 , y3 0 2000年12月 第4回 双対問題 13 弱双対性 定理（弱双対性（week duality）） 主問題の実行可能解の目的関数値は，双対問題の実行可能解の 目的関数値以下である． 主問題の最適値が∞なら 双対問題には実行可能解が存在しない 双対問題の最適値が－∞なら 主問題には実行可能解が存在しない 2000年12月 第4回 双対問題 19 強双対性 より強いことも言える 定理（強双対性（strong duality）） 主問題が最適解をもつなら，その双対問題も最適解をもち，そのと き両者の目的関数は一致する． 2000年12月 第4回 双対問題 20 相補性条件 Lagrange緩和問題の目的関数に注目 15x1+18x2+30x3+(60－2x1－x2－x3)y1+(60－x1－2x2－x3)y2+(30－x3)y3 主問題の目的関数 （最大化） =0 (15－2y1－y2)x1+(18－y1－2y2)x2+(30－y1－y2－y3)x3+60y1+60y2+30y3 =0 双対問題の目的関数 （最小化） さらに．．． 2000年12月 第4回 双対問題 21 相補性条件 xiは主問題の実行可能解なので yiは双対問題の実行可能解なので 60 2 x1 x2 x3 0 15 2 y1 y2 0 60 x1 2 x2 x3 0 18 y1 2 y2 0 30 x3 0 30 y1 y2 y3 0 y1 , y2 , y3 0 が成り立つ x1 , x2 , x3 0 が成り立つ (60－2x1－x2－x3)y1+(60－x1－2x2－x3)y2+(30－x3)y3=0 各項は0以上，すなわち0 2000年12月 第4回 双対問題 22 相補性条件 xiは主問題の実行可能解なので yiは双対問題の実行可能解なので 60 2 x1 x2 x3 0 15 2 y1 y2 0 60 x1 2 x2 x3 0 18 y1 2 y2 0 30 x3 0 30 y1 y2 y3 0 y1 , y2 , y3 0 が成り立つ x1 , x2 , x3 0 が成り立つ (15－2y1－y2)x1+(18－y1－2y2)x2+(30－y1－y2－y3)x3=0 各項は0以下，すなわち0 2000年12月 第4回 双対問題 つまり．．． 23 相補性条件 主問題の最適解xiと主問題の最適解yiは (60－2x1－x2－x3)y1=0 (60－x1－2x2－x3)y2=0 (30－x3)y3=0 (15－2y1－y2)x1=0 (18－y1－2y2)x2=0 (30－y1－y2－y3)x3=0 を満たさなければならない． 原料の価格 ＞ 余った肉の価値は0で 丼の価格 なければならない ならば丼を作らない xiとyiが最適解であることの必要十分条件 2000年12月 第4回 双対問題 24 双対辞書 双対問題の辞書を作る 最小化 60 y1 60 y2 30 y3 条件 2 y1 y2 15 y1 2 y2 18 y1 y2 y3 30 y1 , y2 , y3 0 余裕変数の導入 2000年12月 最小化 60y1+60y2+30y3 =z 条件 2y1+ y2 -w1 =15 y1+ 2y2 -w2 =18 y1 + y2 + y3 -w3=30 y1 , y2 , y3 , w1 , w2 , w3 0 第4回 双対問題 25 双対辞書 最小化 60y1+60y2+30y3 =z 条件 2y1+ y2 -w1 =15 y1+ 2y2 -w2 =18 y1 + y2 + y 3 -w3=30 最小化問題を 最大化問題に変換 y1 , y2 , y3 , w1 , w2 , w3 0 最大化 -60y1-60y2-30y3 =-z 条件 2y1+ y2 -w1 =15 y1+ 2y2 -w2 =18 y1 + y2 + y3 -w3=30 y1 , y2 , y3 , w1 , w2 , w3 0 2000年12月 第4回 双対問題 26 双対辞書 最大化 -60y1-60y2-30y3 =-z 条件 2y1+ y2 -w1 =15 y1+ 2y2 -w2 =18 y1 + y2 + y3 -w3=30 y1 , y2 , y3 , w1 , w2 , w3 0 辞書により表現 初期双対辞書 -z = 0 -60y1-60y2-30y3 w1=-15+ 2y1+ y2 w2=-18+ y1+ 2y2 w3=-30+ y1+ y2+ y3 2000年12月 第4回 双対問題 27 双対辞書 初期双対辞書 -z = 0 -60y1-60y2-30y3 w1=-15+ 2y1+ y2 w2=-18+ y1+ 2y2 w3=-30+ y1+ y2+ y3 双対辞書に対応する基底解は 必ずしも実行可能になっていない (y1,y2,y3,w1,w2,w3)=(0,0,0,-15,-18,-30) 非負条件を満たしていない 2000年12月 第4回 双対問題 28 双対辞書 主問題の初期辞書と見比べると 初期辞書 z = 0+15x1+18x2+30x3 s1=60- 2x1- x2- x3 s2=60- x1- 2x2- x3 s3=30 - x3 初期双対辞書 -z = 0 -60y1-60y2-30y3 w1=-15+ 2y1+ y2 w2=-18+ y1+ 2y2 w3=-30+ y1+ y2+ y3 係数を行列表現すると 0 15 18 30 60 –2 –1 –1 60 –1 –2 –1 30 0 0 –1 2000年12月 転置反転の関係 第4回 双対問題 0 –60 –60 –30 –15 2 1 0 –18 1 2 0 –30 1 1 1 29 双対辞書 初期辞書 z = 0+15x1+18x2+30x3 s1=60- 2x1- x2- x3 s2=60- x1- 2x2- x3 s3=30 - x3 (x1,x2,x3,s1,s2,s3)=(0,0,0,60,60,30) 初期双対辞書 -z = 0 -60y1-60y2-30y3 w1=-15+ 2y1+ y2 w2=-18+ y1+ 2y2 w3=-30+ y1+ y2+ y3 (y1,y2,y3,w1,w2,w3)=(0,0,0,-15,-18,-30) 相補性条件 siyi=0 i=1,2,3 wjxj=0 j=1,2,3 を満たしている 2000年12月 第4回 双対問題 30 双対辞書 初期辞書 z = 0+15x1+18x2+30x3 s1=60- 2x1- x2- x3 s2=60- x1- 2x2- x3 s3=30 - x3 1反復後の辞書 z =900+15x1+18x2-30s3 s1=30 - 2x1- x2+ s3 s2=30 - x1- 2x2+ s3 x3=30 - s3 初期双対辞書 -z = 0 -60y1-60y2-30y3 w1=-15+ 2y1+ y2 w2=-18+ y1+ 2y2 w3=-30+ y1+ y2+ y3 相補性条件 siyi=0 i=1,2,3 wjxj=0 j=1,2,3 1反復後の双対辞書 -z =-900-30y1-30y2-30w3 w1=- 15+ 2y1+ y2 w2=- 18+ y1+ 2y2 y3= 30- y1- y2+ w3 実行可能解でなければ 多面集合の端点でもない 基底解 (y1,y2,y3,w1,w2,w3)=(0,0,30,-15,-18,0) 2000年12月 第4回 双対問題 31 双対辞書 1反復後の辞書 z =900+15x1+18x2-30s3 s1=30 - 2x1- x2+ s3 s2=30 - x1- 2x2+ s3 x3=30 - s3 1反復後の双対辞書 -z =-900-30y1-30y2-30w3 w1=- 15+ 2y1+ y2 w2=- 18+ y1+ 2y2 y3= 30- y1- y2+ w3 相補性条件 siyi=0 i=1,2,3 wjxj=0 j=1,2,3 2反復後の双対辞書 2反復後の辞書 -z =-1170- 15y1- 15w2-30w3 z =1170+ 6x1- 9s2- 21s3 w1=- 6+3/2y1+1/2w2 s1=15 -3/2x1-1/2s2+1/2s3 y2 = 9- 1/2y1+1/2w2 x2=15 -1/2x1-1/2s2+1/2s3 y3= 21- 1/2y1- 1/2w2+ w3 x3=30 - s3 まだ 実行可能解でなければ 2000年12月 多面集合の端点でもない 基底解 (y1,y2,y3,w1,w2,w3)=(0,9,21,-6,0,0) 第4回 双対問題 32 双対辞書 2反復後の辞書 z =1170+ 6x1- 9s2- 21s3 s1=15 -3/2x1-1/2s2+1/2s3 x2=15 -1/2x1-1/2s2+1/2s3 x3=30 - s3 2反復後の双対辞書 -z =-1170- 15y1- 15w2-30w3 w1=- 6+3/2y1+1/2w2 y2 = 9- 1/2y1+1/2w2 y3= 21- 1/2y1- 1/2w2+ w3 相補性条件 siyi=0 i=1,2,3 wjxj=0 j=1,2,3 最終双対辞書 最終辞書 -z =-1230- 10w1- 10w2-30w3 z =1230- 4s1 - 7s2- 19s3 y1 = 4+2/3w1-1/3w2 x1=10 - 2/3s1+1/3s2+1/3s3 y2 = 7- 1/3w1+2/3w2 x2=10 +1/3s1- 2/3s2+1/3s3 y3 = 19- 1/3w1- 1/3w2+ w3 x3=30 - s3 基底解 やっと (y1,y2,y3,w1,w2,w3)=(4,7,19,0,0,0) 実行可能解になった 2000年12月 第4回 双対問題 33 双対辞書 最終双対辞書 -z =-1230- 10w1- 10w2-30w3 y1 = 4+2/3w1-1/3w2 y2 = 7- 1/3w1+2/3w2 y3 = 19- 1/3w1- 1/3w2+ w3 じつは わざわざ双対辞書を作らなくても 主問題の最終辞書の目的関数式 z =1230- 4s1 - 7s2- 19s3 における係数符号を反転したもの が最適な双対変数になっている 基底解 (y1,y2,y3,w1,w2,w3)=(4,7,19,0,0,0) 豚肉は百グラム400円 鶏肉は百グラム700円 牛肉は百グラム1900円 とするのが最適な価格付け 2000年12月 第4回 双対問題 34 双対辞書 双対問題の実行可能領域と双対辞書に対応する基底解の動き y3 y2 y3 30 30 y2 30 30 y1 30 2000年12月 y1 第4回 双対問題 30 35 2種類の運賃クラスを考え， 高い方の運賃クラスを Y，安い方 の運賃クラスを Q とする． 残席数（図中の数字） を利益最大になるように 顧客に割り振る． 2000年12月 第4回 双対問題 36 推定需要量 発地-着地（運賃クラス） 略称 需要量の推定値 収益 成田-ホノルル（クラスQ） NaHoQ 成田-ハワイ（クラスQ） NaHaQ 成田-マウイ（クラスQ） NaMaQ 成田-ホノルル（クラスY） NaHoY 成田-ハワイ（クラスY） NaHaY 成田-マウイ（クラスY） NaMaY 80 70 50 10 20 20 70000 85000 79000 115000 140000 130000 Ｑ１．各運賃クラスを何人まで受け付けるか？ Ｑ２．就航していないホノルル-ハワイ，ホノルル-マウイの価格は 幾らに設定すれば良いか？何円以上なら受け付けるべきか？ 2000年12月 第4回 双対問題 37 Excel Solver Yクラスはすべて受け入れ．Qクラスは20,20,10を上限に受け入れ． 2000年12月 第4回 双対問題 38 感度レポート（最適双対変数） NaHoの価値=70000 HoHaの価値=15000 （料金未設定の便） HoMaの価値=9000 （料金未設定の便） 2000年12月 第4回 双対問題 39
© Copyright 2024 ExpyDoc
