12018/5/18

双対定理の応用

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

2. 感度分析

3. 内点法のアルゴリズム（後日）

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

c w

A w b

x b Ax

x c

 

 ^T

T T

s.t.

max 0

, s.t.

min （Ｄ）

（Ｐ）

双対定理

（Ｐ）または（Ｄ）のいずれか一方が最適解を持 てば，もう一方も最適解を持ち，（Ｐ）の最小値と

（Ｄ）の最大値は一致する．

（ P ），（ D ）どちらを解いてもよい！？

双対シンプレックス法

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

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

＝通常，制約条件の 1.5 ～ 3 倍程度

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

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

標準形の双対問題

c w

A w b

x b Ax

x c







T T T

s.t.

max

0 ,

s.t.

min

（Ｄ）

（Ｐ）

0 s.t.

min

T T







 

v

c v

w A

w b

） Ｄ

（

双対シンプレックス法（再掲）

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

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

通常，制約条件の 1.5 ～ 3 倍程度

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

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

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

相補性定理 (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

最適解

実行可能解とする

（Ｄ）

（Ｐ）

または

または

   

 

 

と（２）より最適解 双対定理からわかるこ

最適解

が成立 弱双対定理より







 

 





























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 :

,

証明

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

 

 

b Bx

B w

b x

A w

b x

A w

w

B i

i i





















: 0

0 0

0

: ^T

に対応 は

非退化の仮定

（Ｄ）の最適解

相補性定理の証明より

（実は，タブローの一番上の行に双対問題の解がある）

感度分析

0 ,

s.t.

min ^T



 b x Ax

x c

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

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

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

変化しない

b B

c z

b B

c

z ^  _B ^{T  1}  ^  _B ^{T  1}  最適値は

の潜在価格 資源

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

単位変化させたときの を

は

i b

w _{i i}



 1

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

1

T B   w 

c _B

例題

２種類の原料 A ， B を加工して２種類の製品Ⅰ，Ⅱを作 る．製品をそれぞれ１単位作るのに，

製品Ⅰ： A 1 単位， B 1 単位

製品Ⅱ： A 1 単位， B 5 単位必要である．

A ， B の在庫はそれぞれ１００単位， 400 単位である．

製品Ⅰ，Ⅱの純益がそれぞれ４，７であるとき，純益を

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

） 製品Ⅱ

に定式化（製品Ⅰ : ₁ , : ₂

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 ））

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

シンプレックス法で解く

 

100 300

400 0 100 5

1

1

1 ¹

1









 



 







 



 



 









より

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

b b

B

と変化

原料 B : 400  400  

   







 

 







 



 



 











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

最適タブロー

図で見ると

原料

B

A

大

小 最適解

図で見ると

の最適解

の最適解

線形計画法のまとめ

 シンプレックス法

 二段階法

 双対定理と相補性定理

 感度分析

補足

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

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

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

楕円体法 ( ハチヤン，１９７９）：遅い

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

ソフトウェア（線形・整数線形など）

 Gurobi （昔は CPLEX ）

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

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

 SCIP （ http://scip/zib.de ）

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

フリー

商用

演習課題

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

３種類の原料

A,B,C,

Ⅰを１単位作るには， A

0.1

B 1.2

C 0.4

Ⅱを１単位作るには， 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