全文

(1)

2.線形計画

Linear Programming (LP)

(2)

はじめに

 例題1(生産計画問題)のような問題

 変数は全て連続値

 目的関数,等式・不等式制約が全て一次式

(線形)

 1975 ノーベル経済学賞(最適資源割り当て

の理論 Kantrovich 1939,Koopmans 1947 )

シンプレックス法( Dantzig 1947 )

(3)

(等式)標準形

0 ,

s.t.

min T

 b x Ax

x c

1.最小化問題

2.等式制約のみ

3.変数には非負制約

どのような問題も標準形で表現できるか?

(4)

補足

行 列

(5)

標準形への変換

1. →

2. 変数 に制約がない →

3. →

4. →

x c

T

max

i j

j

ij

x b

a 

i j

j

ij

x b

a 

x

i

x c )

T

(

min

1 

を掛けて

を追加 とおきかえ,

  0 ,   0

 

i

i i i

i

x x x x

x

j

i i

j ij

i

b y

x a

y を用い

スラック変数 0

ij j i i

i

a x z b

z を用い

数)

スラック変数(剰余変

0

(6)

は制約なし

2 1

2 1

2 1

2 1

, 0

6 5

4

15 8

2 s.t.

5 2

max

x x

x x

x x

x x

標準形への変換(例題)

(7)

1.最大化 → 最小化

は制約なし

2 1

2 1

2 1

2 1

, 0

6 5

4

15 8

2 s.t.

5 2

max

x x

x x

x x

x x

標準形への変換(例題)

は制約なし

2 1

2 1

2 1

2 1

, 0

6 5

4

15 8

2 s.t.

5 2

min

x x

x x

x x

x x

(8)

は制約なし

2 1

2 1

2 1

2 1

, 0

6 5

4

15 8

2 s.t.

5 2

min

x x

x x

x x

x x

0 ,

0 ,

0

6 5

5 4

15 8

8 2

s.t.

5 5

2 min

3 2

1

3 2

1

3 2

1

3 2

1

x x

x

x x

x

x x

x

x x

x

標準形への変換(例題)

2.制約なし → 非負制約

は制約なし

2 1

2 1

2 1

2 1

, 0

6 5

4

15 8

2 s.t.

5 2

min

x x

x x

x x

x x

(9)

0 ,

, ,

,

6 5

5 4

15 8

8 2

s.t.

5 5

2 min

5 4

3 2

1

5 3

2 1

4 3

2 1

3 2

1

x x

x x

x

x x

x x

x x

x x

x x

x

3.4.スラック変数,等式制約

標準形への変換(例題)

0 ,

0 ,

0

6 5

5 4

15 8

8 2

s.t.

5 5

2 min

3 2

1

3 2

1

3 2

1

3 2

1

x x

x

x x

x

x x

x

x x

x

0 ,

0 ,

0

6 5

5 4

15 8

8 2

s.t.

5 5

2 min

3 2

1

3 2

1

3 2

1

3 2

1

x x

x

x x

x

x x

x

x x

x

(10)

は制約なし

2 1

2 1

2 1

2 1

, 0

6 5

4

15 8

2 s.t.

5 2

max

x x

x x

x x

x x

標準形への変換のまとめ

標準形

0 ,

, ,

,

6 5

5 4

15 8

8 2

s.t.

5 5

2 min

5 4

3 2

1

5 3

2 1

4 3

2 1

3 2

1

x x

x x

x

x x

x x

x x

x x

x x

x

(11)

基底解と最適解

0 ,

0

6 2

6 2

s.t.

max

2 1

2 1

2 1

2 1

x x

x x

x x

x x

【例題】

x

1

x

2

6

3 6 3

実行可能集合 0

 

 

  1 c 1

最適解

(12)

0 ,

0

6 2

6 2

s.t.

2 max

2 1

2 1

2 1

2 1

x x

x x

x x

x x

目的関数を変更

x

1

x

2

6

3 6 3

0

 

 

 

2 c 1

最適解集合

両端は頂点

(13)

 

非基底変数 基底変数

非基底行列 基底行列

は実行可能基底解 とくに

凸多面体の頂点 基底解

の解

とおくと

とする

: ,

:

: ,

:

0

solution) (Basic

, 0

) (

: 0

,

1

1

N B

x x

N B

x b

B

b b Ax

x B x

x x N

B A

n m

n m

A x

b Ax

 

 

 

 

 

 

x

の要素のうち

n-m

個を

0

に固定し残りを計算

頂点

0

1

, 

N

B

B b x

x

(14)

はスラック変数

4 3

4 3

2 1

4 2

1

3 2

1

2 1

, 0

, ,

,

6 2

6 2

s.t.

min

x x

x x

x x

x x

x

x x

x

x x

例題を標準形に変換

6 , 6

1 0

2 1

0 1

1

2 b

A 

 

 

 

 

 

基底解は6個

(15)

 

T

1

2 1

0 0

2 2

2 2 6

6 2

1

1 , 2

2 1

1 2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

x

x x x

B

B

6 0 6 0

T

0 , 1

1

2   

 

  x

B

3 0 0 3

T

1 , 1

0

2  

 

  x

B

A

の1列目

A

の2列目

(非基底変数は 基底変数は

4 3

2 1

, ,

x x

x

A

の1列目

A

の3列目

x

3 1

, x

x

基底変数は

(16)

0 3 3 0

T

0 , 2

1

1  

 

  x

B

0 6 0 6

T

1 , 2

0

1   

 

  x

B

0 0 6 6

T

1 , 0

0

1  

 

  x

B

(17)

x

1

x

2

6

3 6 3

0

実行可能基底解は

①,③,④,⑥の4つ

目的関数値

① ー4,③ ー3

④ ー3,⑥ 0

2

1

x

x 

①が最適解

(18)

実行可能基底解(=凸多面体の頂点)を探索 すれば,最適解が見つかる

凸多面体:線形等式・不等式で表現される図形

 

)!

(

!

! :

m n

m

n

n m

n m

A b

Ax

 

頂点の数

とすると

(19)

実行可能基底解を効率よく探索すればよい

シンプレックス法

(20)

演習課題

前回説明した問題(例題1:生産計画問題)

最大化

制約条件

Updating...

参照

Updating...

関連した話題 :