12019/4/19

２．線形計画

Linear Programming (LP)

はじめに

 例題１（生産計画問題）のような問題

 変数は全て連続値

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

（線形）

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

の理論 Kantrovich 1939,Koopmans 1947 ）

シンプレックス法（ Dantzig 1947 ）

（等式）標準形

0 ,

s.t.

min ^T



 b x Ax

x c

１．最小化問題

２．等式制約のみ

３．変数には非負制約

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

補足

行 列

標準形への変換

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

は制約なし

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

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













は制約なし

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

, ,

,

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

３．４．スラック変数，等式制約

標準形への変換（例題）

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

は制約なし

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

基底解と最適解

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

大

小

最適解

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

大

小

最適解集合

両端は頂点

 

非基底変数 基底変数

非基底行列 基底行列

は実行可能基底解 とくに

凸多面体の頂点 基底解

の解 は

とおくと

とする 列

行

: ,

:

: ,

:

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

はスラック変数

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



 



 

 

 



 

基底解は６個

①

②

③

 

^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

の１列目

A

の２列目

）

（非基底変数は 基底変数は

4 3

2 1

, ,

x x

x

A

の１列目

A

の３列目

x

3 1

, x

x

基底変数は

④

⑤

⑥

 ^{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

x

1

x

2

6

3 6 3

0

①

③ ②

⑤

④

⑥

実行可能基底解は

①，③，④，⑥の４つ

目的関数値

① ー４，③ ー３

④ ー３，⑥ ０

2

1

x

x 



①が最適解

実行可能基底解（＝凸多面体の頂点）を探索 すれば，最適解が見つかる

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

 

)!

(

!

! :

m n

m

n

n m

n m

A b

Ax

 







頂点の数

とすると

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

シンプレックス法

演習課題

前回説明した問題（例題１：生産計画問題）

最大化

制約条件