12018/5/11

(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











x x

0 ,

, ,

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

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

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

x b

x_B 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

















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

標準形へ変換する

【例題】

ー１に注意

(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

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

人為変数

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

→

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

(6)

2018/5/11 6

二段階法のアルゴリズム

1. 補助問題を作成

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

3. 最適値＝０

→

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

→

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

4. 最適値＞０

→

元の問題は実行不能，終了．

(7)

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

6 0

0 1

0 0

2 1

0 0

1 0

1 1

2 0

1 0

0 1

2 1

0 1

1 0

0 0

5 7 6

x x x



ー補助問題の初期タブロ

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

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

を作る

(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

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

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



第二段階

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

との列

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

(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

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

双対問題（Ｄ）

主問題（Ｐ）

双対変数主変数

, :

: w

x

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

(15)

標準形の双対問題

c w

A w b

x b Ax

x c







T T T

s.t.

max

0 ,

s.t.

min

（Ｄ）

（Ｐ）

~ 0 , s.t. ~

max ~

0 ,

s.t.

min

T T

T

























w w

c w

A w

A

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

:

:  

（Ｄ）の実行可能解

（Ｐ）の実行可能解

b w

Ax w

x c

w b

b w

Ax w

x c

T T

T

T T









（標準形の場合）

証明：

0

T

w  c , x 

A Ax  b , w  0

(17)

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

がない

（Ｐ）には実行可能解

がない

（Ｄ）には実行可能解

は（Ｄ）の最適解は（Ｐ）の最適解

（Ｄ）の実行可能解

（Ｐ）の実行可能解

（Ｐ）の最適値

（Ｄ）の実行可能解

（Ｄ）の最適値

（Ｐ）の実行可能解













 

 

 

 













w b

x c

w x w

b x

c w

x

w b

w

x c x

T T

) 3 (

: : )

2 (

: : )

1 (

(18)

2018/5/11 18

双対定理（強双対定理）

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

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

【系】

（Ｐ），（Ｄ）ともに実行可能解を持てば，ともに最適解を持ち，最適値は一致する．