全文

(1)

双対定理の応用

1. 双対シンプレックス法と相補性定理

2. 感度分析

3. 内点法のアルゴリズム(後日)

(2)

標準形の双対問題と双対定理

c w

A w b

x b Ax

x c

 

T

T T

s.t.

max 0

, s.t.

min (D)

(P)

双対定理

(P)または(D)のいずれか一方が最適解を持 てば,もう一方も最適解を持ち,(P)の最小値と

(D)の最大値は一致する.

( P ),( D )どちらを解いてもよい!?

(3)

双対シンプレックス法

 双対問題をシンプレックス法で解く 主問題よりも速くなることがある

 シンプレックス法の反復回数

=通常,制約条件の 1.5 ~ 3 倍程度

 双対問題はスラック変数が多い

→ 初期実行可能解を見つけやすい

(4)

標準形の双対問題

c w

A w b

x b Ax

x c

T T T

s.t.

max

0 ,

s.t.

min

(D)

(P)

0 s.t.

min

T T

 

v

c v

w A

w b

) D

(5)

双対シンプレックス法(再掲)

 双対問題をシンプレックス法で解く 主問題よりも速くなることがある

 シンプレックス法の反復回数

通常,制約条件の 1.5 ~ 3 倍程度

 双対問題はスラック変数が多い

→ 初期実行可能解を見つけやすい

双対問題の解 → 主問題の解 ?

(6)

相補性定理 (Complementarity)

 

 

 

 

 

 

 

0 : 0

, ,

0 ,

s.t.

max 0

, s.t.

min

T T

T

T T T

c w

A x

b x

A w w

x

w x

w c w

A w b x

b Ax

x c

最適解

実行可能解とする

(D)

(P)

または

または

(7)

   

 

 

と(2)より最適解 双対定理からわかるこ

最適解

が成立 弱双対定理より

 

 

w b x

A w x

c c w

A x

b x

A w

c w

A x

b x

A w

w b x

A w x

c w

x

w b x

A w x

c

T T

T T

T T

T T

T

T T

T

T T

T

0 0

0 ,

0 :

,

証明

(8)

双対問題の解 → 主問題の解

 

 

b Bx

B w

b x

A w

b x

A w

w

B i

i i

: 0

0 0

0

: T

に対応 は

非退化の仮定

(D)の最適解

相補性定理の証明より

(実は,タブローの一番上の行に双対問題の解がある)

(9)

感度分析

0 ,

s.t.

min T

 b x Ax

x c

において, A,b,c, の変化に対する,最適解や 最適値の振る舞いを調べることを,感度分析 という.

ここでは b→b+Δb の場合を考える

(10)

0 ,

s.t.

min T

 b b x Ax

x c

0

0 0

1 T

T

1

N B

c c

b B

x b

B N

B

最適性の条件

のときの最適解

  ならば最適解

を動かしたとき

1    0

 b b

B x

b

B

変化しない

(11)

b B

c z

b B

c

z B T 1B T 1  最適値は

の潜在価格 資源

ている 最適値の変化量を表し

単位変化させたときの を

i b

w i i

 1

  T は双対問題の最適解

1

T B   w 

c B

(12)

例題

2種類の原料 A , B を加工して2種類の製品Ⅰ,Ⅱを作 る.製品をそれぞれ1単位作るのに,

製品Ⅰ: A 1 単位, B 1 単位

製品Ⅱ: A 1 単位, B 5 単位必要である.

A , B の在庫はそれぞれ100単位, 400 単位である.

製品Ⅰ,Ⅱの純益がそれぞれ4,7であるとき,純益を

最大とするようなⅠ,Ⅱの生産量を求めよ.

(13)

) 製品Ⅱ

に定式化(製品Ⅰ : 1 , : 2

LP x x

0 ,

0

400 5

100 s.t.

7 4

max

2 1

2 1

2 1

2 1

x x

x x

x x

x x

0 ,

, ,

400 5

100 s.t.

7 4

min

4 3

2 1

4 2

1

3 2

1

2 1

x x

x x

x x

x

x x

x

x x

標準形(主問題( P ))

(14)

625 :

75 ,

25 :

75 4

1 4

1 1

0

25 4

1 4

5 0

1

625 4

3 4

13 0

0 300

1 1 4

0

100 0

1 1

1

400 0

4 3

0

400 1

0 5

1

100 0

1 1

1

0 0

0 7

4

2 1

2 1 4

1 4 3

最大値 最適解  

x x

x x x

x x x

シンプレックス法で解く

(15)

 

100 300

400 0 100 5

1

1

1 1

1

 

 

 

 

 

より

範囲 最適基底が変化しない

b b

B

と変化

原料 B : 400  400  

(16)

   

 

 

 

 

 

4 625 3

400 100 5

1

1 7 1

4

1 1 T

T B b b

c B

とき最適値は がこの範囲にある

75 4

1 4

1 1

0

25 4

1 4

5 0

1

625 4

3 4

13 0

0

2 1

 x

x

最適タブロー

(17)

図で見ると

原料

B

原料

A

小 最適解

(18)

図で見ると

の最適解

の最適解

(19)

線形計画法のまとめ

 シンプレックス法

 二段階法

 双対定理と相補性定理

 感度分析

(20)

補足

シンプレックス法は有限回で収束 実用的に速い

ただし理論的には指数オーダーの計算量(多 項式かどうかは未解決)

多項式時間のアルゴリズム

楕円体法 ( ハチヤン,1979):遅い

内点法:実用的で速い → 後日説明

(21)

ソフトウェア(線形・整数線形など)

 Gurobi (昔は CPLEX )

 Matlab の最適化ツールボックス

 Excel の最適化ソルバー( 200 変数くらいま で)

 SCIP ( http://scip/zib.de )

 GLPK , lp_solve, R, python ほか多数

フリー

商用

(22)

演習課題

以下の生産計画問題について

3種類の原料

A,B,C,

を加工して2種類の製品Ⅰ,Ⅱを作る.

Ⅰを1単位作るには, A

0.1

単位,

B 1.2

単位,

C 0.4

単位必要である.

Ⅱを1単位作るには, A 0.3

単位,

B 0.5

単位,

C 0.3

単位必要である.

原料

A,B,C

の在庫はそれぞれ,

1.5

6

2.4

である.

Ⅰ,Ⅱの純益がそれぞれ 3, 6

であるとき,純益を最大とするようなⅠ,Ⅱの 生産量を求めよ.

1.

それぞれの原料の潜在価格を求めよ

2.

製品Ⅱの純益を と変化させたとき,最適解と利潤がどう変化 するか,議論せよ.

5 24 ( )16 00

Updating...

参照

Updating...

関連した話題 :