全文

(1)

初期実行可能基底解の求め方

シンプレックス法を実行

初期実行可能基底解・初期基底行列が必要

どう求めるか?

(2)

2018/5/11 2

 

のとき,例えば,

元々の形が

と仮定 ただし

標準形

0 0

,

0 0

,

b x

b Ax

b x

b Ax

0 ,

0

6 2

6 2

s.t.

3 2

max

2 1

2 1

2 1

2 1

x x

x x

x x

x x

0 ,

, ,

6 2

6 2

s.t.

3 2

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

標準形のスラック変数を基底変数に選べばよい.

は単位行列 初期基底行列 B

x b

xB x ,

6 6

4

3

 

 

 

 

 

(3)

一般の場合どうするか?

目の子で見つける!?

計算機でシステマティックに実行できる方法

二段階法,

Big M

(4)

2018/5/11 4

二段階法

0 ,

0

6 2

2

2 2

s.t.

max

2 1

2 1

2 1

2 1

2

x x

x x

x x

x x

x

0 ,

, ,

,

6 2

2 2 2

s.t.

min

5 4

3 2

1

5 2

1

4 2

1

3 2

1 2

x x

x x

x

x x

x

x x

x

x x

x x

標準形へ変換する

【例題】

ー1に注意

(5)

0 ,

, ,

, ,

,

6 2

2 2 2

s.t.

min

7 6

5 4

3 2

1

5 2

1

7 4

2 1

6 3

2 1

7 6

x x

x x

x x

x

x x

x

x x

x x

x x

x x

x x

補助問題を作成 標準形に対し,以下の

人為変数

最適値=0ならば元問題の実行可能基底解 人為変数

補助問題の実行可能基底解

(6)

2018/5/11 6

二段階法のアルゴリズム

1. 補助問題を作成

2. 補助問題をシンプレックス法で解く

3. 最適値=0

最適解は元の問題の実行可能基底解

初期実行可能基底解として元の問題を 解く

4. 最適値>0

元の問題は実行不能,終了.

(7)

二段階法のシンプレックス法

6 0

0 1

0 0

2 1

2 1

0 0

1 0

1 1

2 0

1 0

0 1

2 1

0 1

1 0

0 0

0 0

5 7 6

x x x

ー 補助問題の初期タブロ

最適タブローのように見えるが,最適ではない

基底変数に対応す る列に掃き出し演 算をして0にする

を作る

(8)

2018/5/11 8

4 0

1 1

0 1

0 2

1 1

2 1 0

1 2

1 0

2 3

1 0

2 1 0

0 2

1 1

2 1

1 0

2 3 0

1 2

1 0

2 3

6 0

0 1

0 0

2 1

2 1

0 0

1 0

1 1

2 0

1 0

0 1

2 1

4 0

0 0

1 1

3 0

2 7 2 5 7 6

x x x x x x

ス法を実行 ここからシンプレック

第一段階の 初期タブロー

ピボット

(9)

 

 

 

 

 

3 8

3 4

3 2 0

3 8 3

4 3

1 1

3 4 3

1 0

0

3 2 3

2 3

1 0

3 2 3

1 0

1

3 4 3

1 3

1 0

3 1 3

1 1

0

0 1

1 0

0 0

0 0

5 2 1 5

1 2

x x x x

x x x

初期実行可能基底解

B

最適値

第一段階終了

元の問題は実行可能

(10)

10

3 8 1

3 4 3

1 0

0

3 2 0

3 2 3

1 0

1

3 4 0

3 1 3

1 1

0

0 0

0 0

1 0

5 1 2

x x x

第二段階

第一段階の最適タブローから,人為変数の列を消 去し,元の目的関数の係数を記入

と の列

基底変数に対応する列に掃き出し演算をして0にする

(11)

始   ここから第二段階開

3 8 1 3

4 3

1 0

0

3 2 0

3 2 3

1 0

1

3 4 0

3 1 3

1 1

0

3 4 0

3 1 3

1 0

0

3 8 1

3 4 3

1 0

0

3 2 0 3 2 3

1 0

1

3 4 0 3

1 3

1 1

0

0 0

0 0

1 0

5 1 2 5 1 2

x x x x x x

第二段階の初期タブロー

(12)

2018/5/11 12

 終了        

      

1 2

1 1

0 0

2 1

4 1

0 1

0 2

3 2

1 0

0 1

2 1

3 2

1 0

0 0

2 1

2 1

2 0

0 1

2 0

2 1

0 3

2 0

1 0

1 1

2 0

1 0

0 1

3 8 1

3 4 3

1 0

0

3 2 0

3 2 3

1 0

1

3 4 0

3 1 3

1 1

0

3 4 0

3 1 3

1 0

0

4 3 2

5 3 2 5 1 2

x x x x

x x x x x

(13)

x

1

x

2

3

2 3 2

0

図でみると

1

第一段階終了 最適解

6

(14)

2018/5/11 14

双対性 (Duality)

0 ,

s.t.

max

0 ,

s.t.

min

T T T

w c

w A

w b

x b Ax

x c

双対問題(D)

主問題(P)

双対変数 主変数

, :

: w

x

双対問題の双対問題は主問題

(15)

標準形の双対問題

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. ~

max ~

0 ,

s.t.

min

T T

T T

T

w w

c w

A w

A

w b

w b

x b Ax

b Ax

x c

:

制約なし

w ~

w

w  

(16)

2018/5/11 16

弱双対定理

w b

x w c

x

T T

:

:  

(D)の実行可能解

(P)の実行可能解

b w

Ax w

x c

w b

b w

Ax w

x c

T T

T

T T

T T

(標準形の場合)

証明:

0

T

w  c , x 

A Ax  b , w  0

(17)

弱双対定理からわかること

がない

(P)には実行可能解

がない

(D)には実行可能解

は(D)の最適解 は(P)の最適解

(D)の実行可能解

(P)の実行可能解

(P)の最適値

(D)の実行可能解

(D)の最適値

(P)の実行可能解



 

 

 

 

w b

x c

w x w

b x

c w

x

w b

w

x c x

T T

T T

T T

) 3 (

: : )

2 (

: : )

1

(

(18)

2018/5/11 18

双対定理(強双対定理)

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

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

【系】

(P),(D)ともに実行可能解を持てば,ともに 最適解を持ち,最適値は一致する.

(19)

双対性のまとめ

双対問題(D)

実行可能 非有界 実行不能

(P)

実行可能 ○(最適解) × ×

非有界 × ×

実行不能 ×



 x

c

T

w

b

T

(20)

2018/5/11 20

ともに実行不能となる例

0 ,

1 1 s.t.

max

0 ,

1 1 s.t.

min

2 1

2 1

2 1

2 1

2 1

2 1

2 1

2 1

w w

w w

w w

w w

x x

x x

x x

x x

(D)

(P)

x1

x2

0 1

1

c

w1

w2

0 1

1

b

(21)

演習課題

次の例題を二段階法で解け.

(締め切り:

5

月1

7

(

)1

6時,Ⅳ系事務室)

0 ,

0

1 3

2 s.t.

3 min

2 1

2 1

2 1

2 1

2 1

x x

x x

x x

x x

x

x

Updating...

参照

Updating...

関連した話題 :