全文

(1)

1

標準形と基底解(復習)

標準形の問題

等式制約において( )

とおくと

は の解(基底解)

とくに は実行可能基底解

(2)

シンプレックス法(単体法)とは

実行可能基底解=実行可能集合の頂点 頂点には必ず最適解がある

ただし,最大 個(全探索は不可)

効率よく頂点を探索する方法

⇒シンプレックス法(単体法)

(3)

3

シンプレックス法の原理

 

N B

N

B

N N B

B N

B

N B

N B

n m

x N B

c c

b B c

x c x

c x

c c c c

b Nx

x Bx x x

N B A

m A

n m

R A

x b Ax

1 T

T 1

T

T T

T

,

) rank

, (

: 0

,

 

 

 

 

 

 

標準形

最適解 かつ   

1

b 0 c

T

c

T

B

1

N 0

B

N B

簡単のため フルランク

基底行列,正則

B,N

に対応して分割

 

 

 

0

1

b

x B

(4)

要素に負の ものがある

現在の基底解は最適解ではない でないとき

なる 非基底変数 と増加

目的関数値が減少

をどこまで大きくできるか?

(5)

5

 

 

 

まで大きくできる.

とおくと

で,

でなければならないの 基底変数

と減少 目的関数

とすると

m i

y y

b

A B

y b

B b

x

A B

b B

x b

B x

N B

c c

b B

c x

i i

i

k B

k B

B

B k N

B k

, ,

1 0

min , 0

0 0

:

1 1

1 1

1

1 T

T 1

T

 

行列 A の第 k 列

(6)

基底変数 非基底変数

に対応する基底変数 としたとき

k i

i i

i k

x x

x y

b x

0 0

0 :

基底変数の入れ替え

(ピボット操作)

 0

 x y x B B

有界でない

小さくできる 目的関数をいくらでも

る いくらでも大きくでき

がない となる

:

0 i

y

i

(7)

7

シンプレックス法の手順

   

 

へ.

と更新し 基底変数

のまま.

そのほかの非基底変数 非基底変数

を求める.

なる を計算し,

そうでなければ,

い.

ならば終了.有界でな を計算.

を選ぶ.

なる非基底変数 そうでなければ,

は最適解.

ならば終了.

とおく.

を選ぶ.

初期実行可能基底解

Step1

0 ,

: Step4

0 :

Step3 : Step2

0 0

: Step1

0 , ,

: Step0

1

1 T T

1 T T

1 1

y b

x x

i y

b y

A B y

x N

B c c

x N

B c c

b B b

b B x

x

B k

i i k

k k B

N

B B

N

N B

 

b

i

y

i

y

i

0 i 1 , , m

min   

(8)

例題

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

標準形への変換

(9)

9

   

     

 

       

非基底変数になる 基底に入る

なる を基底変数に入れる

どちらも負

とする

【反復1】

:

3 , 0 1

, 2 3

6 , 6 ,

: 3 :

Step4

1 ,

3 6

, 3 :

Step3

0 1

, 2 :

Step2

3 , 2 2

1

1 0 2

, 0 3

, 2 :

Step1

6 , 6 1 ,

0

0 , 1

: Step0

3

T T

T 4

3 1

2 2

1 1

T 1

1

1

1 1

T T

1 T 4

3

x

y b

x x x

x

i y

b y

b y

b

A B y

x

B N

B c c

b B b

x B

x x x

B

i i B

N

B B

 

 

 

 

 

 

スラック変数を基底基底行列は単位行列,目的関数値は0

2 1 , x x

目的関数値は-6

(10)

   

     

 

       

非基底変数になる

なる を基底変数に入れる 最適解ではない

【反復2】

:

0 , 2 2

/ 3 , 2 / 1 2

3 , 3 ,

2 :

Step4

2 ,

2 2

, 6 :

Step3

0 2

/ 3 , 2 / 1 :

Step2

1 , 0 2

2

1 0 1

, 2 0

, 3 :

Step1

1 1

0 , 2

3 , 3 ,

4

T T

T 4

1 2

2 2

1 1

T 2

1

2

1 1

T T

1 T 4

1

x

y b

x x x

x

i y

b y

b y

b

A B y

x

B N

B c c

B b

B b

x x x

B

i i B

N B

 

 

 

 

 

 

3 2

, x x

目的関数値は-

10

(11)

11

   

   

 

10

3 / 4 , 3 / 1

1 0

0 3 1

, 2 0

, 0 :

Step1

2 1

1 , 2

2 , 2 ,

1 1

T T

1 T 2

1

 

 

 

 

 

 

最適値は

は最適解,終了.

現在の

【反復3】

x

B N

B c c

B b

B b

x x x

B N

B

非負

(12)

図で見ると

シンプレックス法は,反 復ごとに隣の頂点へ移 動する.

Δ

の幾何学的意味

=ある辺に沿ってどこま で進めるか

x

1

x

2

6

3 6 3

0

 

 

  3 c 2

(13)

13

実行時の問題点

1.Step1において

c

NT

c

BT

B

1

N

k

0

となる が複数ある

k

どれを選んでもよいが, が最小の ものを選ぶと実用上有効(とされている).

 c

NT

 c

BT

B

1

N 

k

2.Step3において

b

i

y

i となる が複数ある

i

複数の基底変数が同時に

0

になる.

退化 (degenerate) している

負で絶対値最大

(14)

退化が起こると

目的関数値は変化しないが 基底の入れ替えがおこる

同じ基底解で循環する.

循環を防ぐ方法:

最小添字規則(

Bland

の規則)

x

1

x

2

6

3 6 3

0

という制約を追加

9

3 x

1

 x

2

3 つの直線が交差 → 退化

(15)

15

シンプレックス・タブロー

シンプレックス法を,表を用いて計算する.

【同じ例題】

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

または,タブロー

(16)

4 3

2 1

4 3

6 1

0 2

1

6 0

1 1

2

0 0

0 3

2

x x

x x

x x

初期タブロー

A b

c T

基底変数

b B 1

目的関数値×(-1)

(17)

17

6 1

0 2

1

6 0

1 1

2

0 0

0 3

2 : Step1

4 3

1

x x

x

を選ぶ.

えば どちらも負なので,例

6 1

0 2

1

6 0

1 1

2

0 0

0 3

2 : Step2,3

4 3

x x

y b

i i

 を求める.

を計算し,

3 /

1

1

y 

b

6 /

2

2

y 

b

(18)

反復を繰り返す へ

負の要素があるので 掃き出し演算

Step1 3 1

2 / 1 2

/ 3 0

3 0

2 / 1 2

/ 1 1

6 0

1 2

0

6 1

0 2

1

6 0

1 1

2

0 0

0 3

2 : Step4

4 1 4 3

x x x x

ピボット

①この行をピボットで割る

②-

2

倍して引く

1

倍して引く

ピボット以外のピボット 列の要素を

0

にする

が基底に入る

x

1

(19)

19

終了

を選ぶ

2 3

/ 2 3

/ 1 1

0

2 3

/ 1 3

/ 2 0

1

10 3

/ 4 3

/ 1 0

0

3 1

2 / 1 2

/ 3 0

3 0

2 / 1 2

/ 1 1

6 0

1 2

0 : Step1

2 1 4 1

2

x x x

x

x ピボット

2 /

6 /

2 2

1 1

 y b

y b

すべて非負 → 最適

最適値は- 10

 

 

 

 

 

2 2

2 1

x

最適解 x

(20)

シンプレックス法のまとめ

 実行可能解の隣にある頂点を探索する方法

→ 頂点の数は有限個 → 有限回で終了

 計算機上ではタブローを用いて計算

 残っている問題点

初期実行可能解? 計算量?

(21)

21

演習課題

次の例題をシンプレックス法(タブロー)を用い て解け.(締め切り: 5 月 9 日(木) 16 時Ⅳ系事務 室)

0 ,

0

4 . 2 3

. 0 4

. 0

6 5

. 0 2

. 1

5 . 1 3

. 0 1

. 0 s.t.

6 3

max

2 1

2 1

2 1

2 1

2 1

x x

x x

x x

x x

x

x

Updating...

参照

Updating...

関連した話題 :