12018/4/27

1

標準形と基底解（復習）

標準形の問題

等式制約において（ ）

とおくと

は の解（基底解）

とくに は実行可能基底解

シンプレックス法（単体法）とは

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

ただし，最大 個（全探索は不可）

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

⇒シンプレックス法（単体法）

3

シンプレックス法の原理

 





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

,

















 



 



 





 



 



 











最適解 かつ   



¹

b 0 c

c

B

N 0

B

簡単のため フルランク

基底行列，正則

B,Nに対応して分割

 

 



 

0

1

b

x B

要素に負の ものがある

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

なる 非基底変数 と増加

目的関数値が減少

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

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 列

基底変数 非基底変数

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

















k i

i i

i k

x x

x y

b x

0 0

0 :

基底変数の入れ替え

（ピボット操作）

 0





 x y x

有界でない

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

る いくらでも大きくでき

がない となる









:

0 i

y

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











































 





min   





例題

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

   

     

 

       

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

なる を基底変数に入れる

どちらも負

とする

【反復１】

:

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



















































 



 



 













 



 



 













スラック変数を基底→基底行列は単位行列，目的関数値は０

2 1

, x x

目的関数値は－６

   

     

 

       

非基底変数になる

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

【反復２】

:

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

   

   

 

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







 



 











 



 















最適値は

は最適解，終了．

現在の

【反復３】

x

B N

B c c

B b

B b

x x x

B N

B

非負

図で見ると

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

 Δの幾何学的意味

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

x

x

6

3 6 3

0



 



  3 c 2

①

②

③

13

実行時の問題点

１．Step1において





_k

→どれを選んでもよいが， が最小の ものを選ぶと実用上有効（とされている）．





２．Step3において ^{  b}_i ^y_i となる が複数ある

i

→複数の基底変数が同時に0になる．

退化 (degenerate) している

負で絶対値最大

退化が起こると

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

 同じ基底解で循環する．

↓ 循環を防ぐ方法：

最小添字規則（Blandの規則）

x

x

6

3 6 3

0

という制約を追加 9

3x₁  x₂ 

3 つの直線が交差 → 退化

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

または，タブロー

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}

目的関数値×（－１）

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





 を求める．

を計算し，

3 /

1

y 

b

6 /

2

y 

b

反復を繰り返す へ

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













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

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

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



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

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



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



残っている問題点

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

21

演習課題

次の例題をシンプレックス法（タブロー）を用い て解け．（締め切り： 5 月 10 日（木） 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