第5回 双対問題 テキストp 内容 双対問題の導出 式を足しあわせる方法 Lagrange緩和 相補性条件 双対辞書

Presentation on theme: "第5回 双対問題 テキストp 内容 双対問題の導出 式を足しあわせる方法 Lagrange緩和 相補性条件 双対辞書"— Presentation transcript:

1 第5回 双対問題 テキストp.42-56 内容 双対問題の導出 式を足しあわせる方法 Lagrange緩和 相補性条件 双対辞書
主問題と双対問題（一般論） 2000年12月 第4回 双対問題

2 もとの問題（主問題）と表裏一体を成す線形計画問題
引き続き，あなたは丼チェーン店の店長だ．今日，丼チェーンの本社から，自社農場で飼育している豚，鶏，牛の肉の価値を算出するよう指令が届いた．さて，トンコケ丼，コケトン丼，ミックス丼の販売価格から考えたとき，豚肉，鶏肉，牛肉の百グラムあたりの価値は何円と考えればよいのだろうか？ こういうときは双対問題が便利 双対問題 ＝ もとの問題（主問題）と表裏一体を成す線形計画問題 2000年12月 第4回 双対問題

3 式を足し合わせることによる導出 上界：主問題の最適解以上であることが保証されている値 基本的アイディア：
式を足し合わせることによって上界を計算 2000年12月 第4回 双対問題

4 式を足し合わせることによる導出 目的関数は 15x1+18x2+30x3 の最大化 15x1+18x2+30x3 の上界は1500
最適値は1230であったので270のギャップ 2000年12月 第4回 双対問題

5 式を足し合わせることによる導出 目的関数は 15x1+18x2+30x3 の最大化 最適値は1230であったので90のギャップ
2000年12月 第4回 双対問題

6 式を足し合わせることによる導出 目的関数は 15x1+18x2+30x3 の最大化 ??? 2000年12月 第4回 双対問題

7 式を足し合わせることによる導出 これが15x1+18x2+30x3以上になるためには の必要あり，このとき上界は
最もよい（小さい）上界を与えるy1 ，y2， y3を求める問題は？ 2000年12月 第4回 双対問題

8 双対問題 仕入れ価格の最小化 トンコケ丼の価値 豚肉と鶏肉の価値 それぞれの肉の百グラムあたりの価値（単位は百円） 2000年12月
第4回 双対問題

9 Lagrange緩和による方法 最大化 15x1+18x2+30x3 最大化 15x1+18x2+30x3
+(60－2x1－x2－x3)y1 +(60－x1－2x2－x3)y2 +(30－x3)y3 非負 主問題 最適値は主問題の上界 2000年12月 第4回 双対問題

10 Lagrange緩和による方法 最大化 15x1+18x2+30x3 最大化 (15－2y1－y2)x1 +(60－2x1－x2－x3)y1
+(30－y1－y2－y3)x3 +60y1+60y2+30y3 目的関数をx1,x2,x3についてまとめる 2000年12月 第4回 双対問題

11 Lagrange緩和による方法 最大化 (15－2y1－y2)x1 最大化 (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 いくつかの条件を省く（緩和） 線形計画問題だけでなく， 一般的な最適化問題に対する フレームワーク Lagrange緩和問題 2000年12月 第4回 双対問題

12 Lagrange緩和による方法 なるべくよい（なるべく小さい）上界を得ることを考える 最大化 (15－2y1－y2)x1
+(30－y1－y2－y3)x3 +60y1+60y2+30y3 ここが正だといくらでも大きくできる 非正でなければならない 他の係数についても同様 この条件のもとで目的関数のxに依存しない部分を最小化 2000年12月 第4回 双対問題

13 Lagrange緩和による方法 双対問題 最小化 60y1+60y2+30y3 2000年12月 第4回 双対問題

14 ちょっと脱線Lagrange緩和一般論 一般の（線形制約とは限らない）最適化問題に対するフレームワーク Lagrange未定乗数法
たとえば以下の問題の場合 2000年12月 第4回 双対問題

15 ちょっと脱線Lagrange緩和一般論 明らかにこれが答え 1 -1 1 なんだけど，あえて Lagrange未定乗数法を使ってみよう -1
1 なんだけど，あえて Lagrange未定乗数法を使ってみよう -1 2000年12月 第4回 双対問題

16 Lagrange未定乗数法 Lagrange緩和問題を生成 λを未定乗数と呼ぶ とする 2000年12月 第4回 双対問題

17 Lagrange未定乗数法 なのでこれはxとyの関数 λを定数だと思ってf(x)の最大値をλで表す 最大値をλで表すのは一般的には難しい
最急降下法，共役勾配法などを用いる 今回は簡単な問題なので 解析的に最大値を求める 2000年12月 第4回 双対問題

18 Lagrange未定乗数法 の最大値は のとき これを最小にするλは このとき 2000年12月 第4回 双対問題

19 弱双対性 定理（弱双対性（week duality）） 主問題の実行可能解の目的関数値は，双対問題の実行可能解の目的関数値以下である．
主問題の最適値が∞なら 双対問題には実行可能解が存在しない 双対問題の最適値が－∞なら 主問題には実行可能解が存在しない 2000年12月 第4回 双対問題

20 強双対性 より強いことも言える 定理（強双対性（strong duality））
主問題が最適解をもつなら，その双対問題も最適解をもち，そのとき両者の目的関数は一致する． 2000年12月 第4回 双対問題

21 相補性条件 Lagrange緩和問題の目的関数に注目 主問題の目的関数 =0 （最大化） 双対問題の目的関数 =0 （最小化） さらに．．．
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回 双対問題

22 相補性条件 xiは主問題の実行可能解なので yiは双対問題の実行可能解なので が成り立つ が成り立つ 各項は0以上，すなわち0
(60－2x1－x2－x3)y1+(60－x1－2x2－x3)y2+(30－x3)y3=0 各項は0以上，すなわち0 2000年12月 第4回 双対問題

23 相補性条件 xiは主問題の実行可能解なので yiは双対問題の実行可能解なので が成り立つ が成り立つ 各項は0以下，すなわち0 つまり．．．
(15－2y1－y2)x1+(18－y1－2y2)x2+(30－y1－y2－y3)x3=0 各項は0以下，すなわち0 つまり．．． 2000年12月 第4回 双対問題

24 相補性条件 主問題の最適解xiと主問題の最適解yiは (60－2x1－x2－x3)y1=0 (15－2y1－y2)x1=0
を満たさなければならない． 原料の価格 ＞ 丼の価格 ならば丼を作らない 余った肉の価値は0でなければならない xiとyiが最適解であることの必要十分条件 2000年12月 第4回 双対問題

25 双対辞書 双対問題の辞書を作る 最小化 60y1+60y2+30y3 =z 条件 2y1+ y2 -w1 =15
y1+ y2+ y w3=30 余裕変数の導入 2000年12月 第4回 双対問題

26 双対辞書 最小化 60y1+60y2+30y3 =z 条件 2y1+ y2 -w1 =15 y1+ 2y2 -w2 =18 最小化問題を
y1+ y2+ y w3=30 最小化問題を 最大化問題に変換 最大化 -60y1-60y2-30y =-z 条件 y1+ y w =15 y1+ 2y w =18 y1+ y2+ y w3=30 2000年12月 第4回 双対問題

27 双対辞書 最大化 -60y1-60y2-30y3 =-z 条件 2y1+ y2 -w1 =15 y1+ 2y2 -w2 =18
y1+ y2+ y w3=30 辞書により表現 初期双対辞書 -z = y1-60y2-30y3 w1= y1+ y2 w2= y1+ 2y2 w3= y1+ y2+ y3 2000年12月 第4回 双対問題

28 双対辞書 初期双対辞書 -z = 0 -60y1-60y2-30y3 w1=-15+ 2y1+ y2 w2=-18+ y1+ 2y2
w3= y1+ y2+ y3 双対辞書に対応する基底解は 必ずしも実行可能になっていない (y1,y2,y3,w1,w2,w3)=(0,0,0,-15,-18,-30) 非負条件を満たしていない 2000年12月 第4回 双対問題

29 双対辞書 主問題の初期辞書と見比べると 初期辞書 z = 0+15x1+18x2+30x3 s1=60- 2x1- x2- x3
初期双対辞書 -z = y1-60y2-30y3 w1= y1+ y2 w2= y1+ 2y2 w3= y1+ y2+ y3 係数を行列表現すると 60 –2 –1 –1 60 –1 –2 –1 –1 0 –60 –60 –30 – – – 転置反転の関係 2000年12月 第4回 双対問題

30 双対辞書 初期辞書 z = 0+15x1+18x2+30x3 s1=60- 2x1- x2- x3 s2=60- x1- 2x2- x3
初期双対辞書 -z = y1-60y2-30y3 w1= y1+ y2 w2= y1+ 2y2 w3= y1+ y2+ y3 (x1,x2,x3,s1,s2,s3)=(0,0,0,60,60,30) (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回 双対問題

31 双対辞書 初期辞書 z = 0+15x1+18x2+30x3 s1=60- 2x1- x2- x3 s2=60- x1- 2x2- x3
初期双対辞書 -z = y1-60y2-30y3 w1= y1+ y2 w2= y1+ 2y2 w3= y1+ y2+ y3 相補性条件 siyi=0 i=1,2,3 wjxj=0 j=1,2,3 1反復後の辞書 z =900+15x1+18x2-30s3 s1= x x2+ s3 s2= x1- 2x2+ s3 x3= s3 1反復後の双対辞書 -z = y1-30y2-30w3 w1= y1+ y2 w2= y1+ 2y2 y3= y1- y2+ w3 実行可能解でなければ 多面集合の端点でもない 基底解 (y1,y2,y3,w1,w2,w3)=(0,0,30,-15,-18,0) 2000年12月 第4回 双対問題

32 双対辞書 1反復後の辞書 z =900+15x1+18x2-30s3 s1=30 - 2x1- x2+ s3 1反復後の双対辞書
-z = y1-30y2-30w3 w1= y1+ y2 w2= y1+ 2y2 y3= y1- y2+ w3 相補性条件 siyi=0 i=1,2,3 wjxj=0 j=1,2,3 2反復後の双対辞書 -z = y1- 15w2-30w3 w1= /2y1+1/2w2 y2= /2y1+1/2w2 y3= /2y1- 1/2w2+ w3 2反復後の辞書 z = x1- 9s2- 21s3 s1= /2x1-1/2s2+1/2s3 x2= /2x1-1/2s2+1/2s3 x3= s3 基底解 (y1,y2,y3,w1,w2,w3)=(0,9,21,-6,0,0) まだ 実行可能解でなければ 多面集合の端点でもない 2000年12月 第4回 双対問題

33 双対辞書 2反復後の辞書 z =1170+ 6x1- 9s2- 21s3 s1=15 -3/2x1-1/2s2+1/2s3
x2= /2x1-1/2s2+1/2s3 x3= s3 2反復後の双対辞書 -z = y1- 15w2-30w3 w1= /2y1+1/2w2 y2= /2y1+1/2w2 y3= /2y1- 1/2w2+ w3 相補性条件 siyi=0 i=1,2,3 wjxj=0 j=1,2,3 最終双対辞書 -z = w1- 10w2-30w3 y1 = /3w1-1/3w2 y2 = /3w1+2/3w2 y3 = /3w1- 1/3w2+ w3 最終辞書 z = s1 - 7s2- 19s3 x1= /3s1+1/3s2+1/3s3 x2= /3s1- 2/3s2+1/3s3 x3= s3 基底解 (y1,y2,y3,w1,w2,w3)=(4,7,19,0,0,0) やっと 実行可能解になった 2000年12月 第4回 双対問題

34 双対辞書 じつは 最終双対辞書 わざわざ双対辞書を作らなくても -z =-1230- 10w1- 10w2-30w3
主問題の最終辞書の目的関数式 z = s1 - 7s2- 19s3 における係数符号を反転したもの が最適な双対変数になっている 最終双対辞書 -z = w1- 10w2-30w3 y1 = /3w1-1/3w2 y2 = /3w1+2/3w2 y3 = /3w1- 1/3w2+ w3 基底解 (y1,y2,y3,w1,w2,w3)=(4,7,19,0,0,0) 豚肉は百グラム400円 鶏肉は百グラム700円 牛肉は百グラム1900円 とするのが最適な価格付け 2000年12月 第4回 双対問題

35 双対辞書 双対問題の実行可能領域と双対辞書に対応する基底解の動き 2000年12月 第4回 双対問題

36 高い方の運賃クラスを Y，安い方の運賃クラスを Q とする． 残席数（図中の数字） を利益最大になるように 顧客に割り振る．
2種類の運賃クラスを考え， 高い方の運賃クラスを Y，安い方の運賃クラスを Q とする． 残席数（図中の数字） を利益最大になるように 顧客に割り振る． 2000年12月 第4回 双対問題

37 推定需要量 発地-着地（運賃クラス） 略称 需要量の推定値 収益 成田-ホノルル（クラスQ） NaHoQ 80 70000
発地-着地（運賃クラス）　 略称 　 需要量の推定値 収益 成田-ホノルル（クラスQ） NaHoQ 成田-ハワイ（クラスQ） NaHaQ 　 成田-マウイ（クラスQ） NaMaQ 　 成田-ホノルル（クラスY） NaHoY 成田-ハワイ（クラスY）　 NaHaY 成田-マウイ（クラスY） 　NaMaY Ｑ１．各運賃クラスを何人まで受け付けるか？ Ｑ２．就航していないホノルル-ハワイ，ホノルル-マウイの価格は 幾らに設定すれば良いか？何円以上なら受け付けるべきか？ 2000年12月 第4回 双対問題

38 Excel Solver Yクラスはすべて受け入れ．Qクラスは20,20,10を上限に受け入れ． 2000年12月 第4回 双対問題

39 感度レポート（最適双対変数） NaHoの価値=70000 HoHaの価値=15000 （料金未設定の便）
HoMaの価値=9000 （料金未設定の便） 2000年12月 第4回 双対問題

40 一般論 例えば不等号の向きが逆の場合 超簡単な例 今までに扱ってきた向き 最大化 x1-x2 逆向き 2000年12月 第4回 双対問題

41 一般論 Lagrange緩和を使うと 最大化 x1-x2+(1-x1)y1+(2-x2)y2 最大化 x1-x2 今までと違うところ
2000年12月 第4回 双対問題

42 一般論 式変形 最大化 x1-x2+(1-x1)y1+(2-x2)y2 最大化 y1+2y2+(1-y1)x1+(-1-y2)x2
2000年12月 第4回 双対問題

43 一般論 制約を緩和 最大化 y1+2y2+(1-y1)x1+(-1-y2)x2 最大化 y1+2y2+(1-y1)x1+(-1-y2)x2
この問題の最適値は元の問題の最適値以上になるから 元の問題の最適値と同じ値を求める問題は 2000年12月 第4回 双対問題

44 一般論 最大化 y1+2y2+(1-y1)x1+(-1-y2)x2 最小化 y1+2y2 これが双対問題，式を変形すると 2000年12月
第4回 双対問題

45 一般論 最小化 y1+2y2 最小化 y1+2y2 これが双対問題 2000年12月 第4回 双対問題

46 一般論（その２） 例えば等号がある場合 最大化 x1+x2 最大化 x1+x2 等号は不等号が2つだと思う 2000年12月
第4回 双対問題

47 一般論（その２） あとはお決まりのコース，まず，制約を目的関数に組み込む 最大化 x1+x2
最大化 x1+x2+(1-x1)y1+(2-x2)y2+(2-x2)y3 2000年12月 第4回 双対問題

48 一般論（その２） 目的関数を整理し，制約を緩和 最大化 x1+x2+(1-x1)y1+(2-x2)y2+(2-x2)y3
最大化 y1+2y2 +2y3 +(1-y1)x1+(1-y2-y3)x2 2000年12月 第4回 双対問題

49 一般論（その２） 元の問題と同じ最適値となる問題を生成 最大化 y1+2y2 +2y3 +(1-y1)x1+(1-y2-y3)x2
2000年12月 第4回 双対問題

50 一般論（その２） ちょっと整理して 最小化 y1+2y2 +2y3 最小化 y1+2y2 +2y3 y2+y3が一つの変数だと思うと，
これはどんな値も取れる変数 2000年12月 第4回 双対問題

51 一般論（その２） さらに整理して 最小化 y1+2y2 +2y3 最小化 y1+2y4 y2+y3=y4とした 2000年12月
第4回 双対問題

52 おわりに 今日線形計画問題を解くための道具はたくさん提供されている →問題を手作業で解くための方法を覚えることは意味がない
双対性や相補性条件の意義を理解し活用できることこそ重要 2000年12月 第4回 双対問題