線形計画法4（5/16）

双対定理の応用
1.
2.
双対シンプレックス法と相補性定理
感度分析
2014/5/16
1
双対シンプレックス法
双対問題をシンプレックス法で解く
主問題よりも早くなることがある
シンプレックス法の反復回数
通常，制約条件の1.5～3倍程度
双対問題はスラック変数が多い
→初期実行可能解を見つけやすい
2014/5/16
2
標準形の双対問題
T
（Ｐ） min c x
s.t. Ax b, x 0
T
（Ｄ） max b w
T
s.t. A w c
T
（Ｄ） min b w
T
s.t. A w v
c
v 0
2014/5/16
初期基底解の候補になりやすい
3
双対シンプレックス法
双対問題をシンプレックス法で解く
主問題よりも早くなることがある
シンプレックス法の反復回数
通常，制約条件の1.5～3倍程度
双対問題はスラック変数が多い
→初期実行可能解を見つけやすい
双対問題の解→主問題の解？
2014/5/16
4
相補性定理(Complementarity)
min c T x
（Ｐ）
s.t. Ax b, x 0
max b T w
（Ｄ）
s.t.
A T w c, w 0
x , w 実行可能解とする
wi
x , w : 最適解
i
0
0 または A w b i
0
w T Ax b 0
x T AT w c 0
xi
2014/5/16
0 または Ax b
T
5
証明
弱双対定理より c T x
w T Ax
b T w が成立
cT x
w T Ax
bT w
x , w : 最適解
w T Ax b
w T Ax b
x T AT w c
0
0
cT x
w T Ax
0, x T AT w c
0
bT w
双対定理からわかること（２）より最適解
2014/5/16
6
双対問題の解→主問題の解
相補性定理の証明より
w :（Ｄ）の最適解
非退化の仮定
2014/5/16
T
w Ax b
0
wi
0
Ax b i
0
wi
0 は B に対応 : BxB
b
7
感度分析
T
min c x
s.t.
Ax b, x 0
において，A,b,c,の変化に対する，最適解や
最適値の振る舞いを調べることを，感度分析
という．
b→b+Δbの場合を考える．
2014/5/16
8
T
min c x
s.t.
Ax b
b
b, x 0
1
0 のときの最適解 xB
最適性の条件 c
T
N
T
B
1
B b 0
c B N
0
変化しない
b を動かしたとき
xB
2014/5/16
1
B b
b
0 ならば最適解
9
最適値は
T
B
z
1
c B b
T
B
c B
1
w
T
z
T
B
c B
1
b
は双対問題の最適解
wi は bi を1単位変化させたときの
最適値の変化量を表している
資源iの潜在価格
2014/5/16
10
例題
２種類の原料A，Bを加工して２種類の製品Ⅰ，Ⅱを作
る．製品をそれぞれ１単位作るのに，
製品Ⅰ：A 1単位，B 1単位
製品Ⅱ：A 1単位，B 5単位必要である．
A，Bの在庫はそれぞれ１００単位，400単位である．
製品Ⅰ，Ⅱの純益がそれぞれ４，７であるとき，純益を
最大とするようなⅠ，Ⅱの生産量を求めよ．
2014/5/16
11
LPに定式化（製品Ⅰ: x1 , 製品Ⅱ: x2）
max 4 x1 7 x2
min 4 x1 7 x2
s.t. x1
s.t. x1
x2 100
x1 5 x2
x1
0, x2
400
0
x2
x3
100
x1 5 x2
x4
x1 , x2 , x3 , x4
0
400
標準形（主問題（P））
2014/5/16
12
シンプレックス法で解く
x3
4
1
7 0 0 0
1 1 0 100
x4
1
5
0
3
x1
1
1
x4
0
4
0 1 400
4
0 400
0 0 13 4
1
0 100
x1
1 0
54
1 1 300
x2
0 1
14
最適解 : x1
2014/5/16
25, x2
34
625
14
25
14
75
75 最大値 : 625
13
原料B : 400
400
と変化
最適基底が変化しない範囲
b
1 1
1 5
より 300
100
1
B b
2014/5/16
1
100
400
0
14
がこの範囲にあるとき最適値は
T
B
1
c B b
b
4 7
T
1 1
1 5
1
100
400
3
625
4
最適タブロー
x1
x2
2014/5/16
0 0 13 4
34
625
1 0
0 1
14
14
25
75
54
14
15
線形計画法のまとめ
シンプレックス法
二段階法
双対定理と相補性定理
感度分析
2014/5/16
16
補足
シンプレックス法は有限回で収束
実用的に早い
ただし理論的には指数オーダーの計算量
多項式時間のアルゴリズム
楕円体法(ハチヤン，１９７９）：遅い
内点法：実用的で早い →後日説明
2014/5/16
17
ソフトウェア
商用
Gurobi（昔はCPLEX）
Matlabのlpsolve(最適化ツールボックス)
Excel の最適化ソルバー（200変数くらいまで，
以外と使える）
GLPK
lp_solve ほか多数
2014/5/16
フリー
18
演習課題
次の例題について
max 4 x1 7 x2
s.t. x1
x2 100
x1 5 x2
x1
1.
2.
0, x2
400
0
双対問題を作れ
双対問題を解いて，双対定理と相補性定理
を確かめよ
（締切：5月22日（木）16時，Ⅳ系事務室）
2014/5/16
19

Download Report