意思決定科学

意思決定科学

DEA （包絡分析法）

堀田敬介

2015

年

1

月

16

日（金）

考えよう



あなたは６つの店舗をもつ社長だ．今年１年間の業績が最もよい 店舗を表彰して他店舗の模範とし，次年度も切磋琢磨させたい．

さて，あなたはどの店舗を表彰するのか？

9 , 1

4 , 4 7 , 4

5 , 6

7 , 8 2 , 10

0 1 2 3 4 5 6 7 8 9 10

0 1 2 3 4 5 6 7 8 9 10

A店 B店 C店 D店 E店 F店 営業費 56 100 86 100 57 250 人員数 500 100 150 83 50 50 売上 500 400 600 500 400 500

A店 B店 C店 D店 E店 F店

売上/費 9 4 7 5 7 2

売上/人 1 4 4 6 8 10

包絡線

A B C

D

E F

Contents



DEA とは？

 DMU

（意思決定主体）



効率性：

DMU

の入力・出力と効率値



DEA の基本的モデル

 CCR

モデル



生産可能集合とその他のモデル



凸包モデル

 BCC

モデル

 IRS

モデル

 DRS

モデル

 GRS

モデル

最も変換効率の良いDMUを 基準として，他の

DMU

の非効 率性を算出し，比較する．

ただし，変換効率はDMU毎に 最も有利になるように計算．

DEA とは？



DEA (Data Envelopment Analysis)

DMU

Decision Making Unit

… …

入力

(m

個

)

出力

(s

個

)

Decision Making Unit

DMU

仮想的入力 仮想的出力

DMU

の変換効率＝ 仮想的出力 仮想的入力

比率尺度を効率性と 見なして相対比較

envelop=

包む

envelopment=

包むこと

c.f.) envelope=

封筒

DEA とは？



2 入力・ 1 出力



例）店舗売上

入力 出力

店舗

(DMU) A B C D E F G H I

従業員数

4 9 6 3 4 6 3 6 4

売場面積

3 4 1 2.1 9 2 6 6 8

売上高

12 36 12 21 36 12 24 36 24

従業員数

売上高 入力１

入力２

売場面積 出力

DMU

Decision Making Unit

DEA とは？

店舗

(DMU) A B C D E F G H I

売上高

/

従業員数

3 4 2 7 9 2 8 6 6

売上高

/

売場面積

4 9 12 10 4 6 4 6 3

効率的

DMU

非効率的

DMU

0 1 2 3 4 5 6 7 8 9 10 11 12 13

0 1 2 3 4 5 6 7 8 9 10 11 12

出力

/

入力

1

出力

/

入力

2

生産可能集合

効率的フロンティア

D

A E

B C

F

G H

I

DEA とは？

店舗

(DMU) A B C D E F G H I

売上高

/

従業員数

3 4 2 7 9 2 8 6 6

売上高

/

売場面積

4 9 12 10 4 6 4 6 3

効率的

DMU

非効率的

DMU

0 1 2 3 4 5 6 7 8 9 10 11 12 13

0 1 2 3 4 5 6 7 8 9 10 11 12

出力

/

入力

1

出力

/

入力

2

D

A E

B C

F

G H

I

非効率的

DMU H

の 非効率値は

OH/OP

であり

H

の有位（参照）集合 は

D

と

E

効率的DMU C,D,E の 効率値は

1.0

P

DEA ： CCR モデル



多入力・多出力

Decision Making Unit

DMU

出力（

s

個）

入力（

m

個）

仮想的入力 ：＝

v₁

×

x₁

＋

v₂

×

x₂

＋

…

＋

v_m

×

x_m

仮想的出力 ：＝

u₁

×

y₁

＋

u₂

×

y₂

＋

…

＋

u_s

×

y_s

効率性（生産性） ：＝

入力・出力のウェイトは可変

⇔

固定ウェイト

x₁ x₂ x_m

…

y₁ y₂ y_s

…

v₁ v₂ v_m

…

u₁ u₂ u_m

…

v₁

×

x₁

＋

v₂

×

x₂

＋

…

＋

v_m

×

x_m u₁

×

y₁

＋

u₂

×

y₂

＋

…

＋

u_s

×

y_s

入力の

ウェイト

出力の

ウェイト

DEA ： CCR モデル



多入力・多出力

DMU

_k

Decision Making Unit

…

入力

(m

個

) n

個（

k=1,2,…,n

）

…

出力

(s

個

)















 

mn m

n

x x

x x

X   

1

1 11















 

sn s

n

y y

y y

Y   

1

1 11

DMU

数（

n

個）

DMU

数（

n

個）

入力データ行列 出力データ行列

入 力 数

(m)

出 力 数

(s)



^v_{1 } ^v_m



^T



v ^{u }



^u_{1 } ^u_s



^T

入力データ用ウェイトベクトル 出力データ用ウェイトベクトル

) , ,

1 (

:

1

n k

x v

q ^m

i

ik i

k 



 



) , ,

1 (

:

1

n k

y u

r ^s

j

jk j

k 



 



DMU_k

の仮想入力

DMU_k

の仮想出力

x_1k

x… _2k x_mk

y_1k y… _2k y_sk

DEA ： CCR モデル



多入力・多出力



測定対象

DMU_o(o=1,…,n)

のウェイトを計算する

0 ,

,

, , 0

) , , 1 (

1

.

.

: . max

1 1 1

1 1 1

1 1

1 1





 





 





 

s m mk m k

sk s k

mo m o

so s o

o

u

u v

v

n x k

v x

v

y u y

t u s

x v x

v

y u y

u



 



 

全ての

DMU

の 効率性は

1

以下 対象の

DMU

の

効率性を最大化

<FP_o>

分数計画問題

入出力用可変ウェ イトの変数は非負

0 ,

,

, , 0

( 1, , )

. . . : 1 max

1 1

1 1 1

1 1 1

1 1

   





  

 



s m

mk m k

sk s k

mo m o

so s o

o

u

uv u yv v x k v x n y

uv x v x t

s u y u y

  





線形計画問題

<LP_o>

同 値

([1]) <FP_o>

の目的関数について

分母を

1

にし，分子を最大化

<FP_o>

の制約の分母を払う

注）全部で

n

個の

LP

を解く！

Def： DMU_o

の優位集合（or 参照集合）



k s sk k m mk



o k n u y u y v x v x

E : {1,, } ₁^* ₁  ^*  ₁^* ₁  ^*

Lem

：

DMU_o

が

D

非効率的，即ち

_o^* 1

なら

mk m k

sk s

k u y v x v x

y u n

k {1, , }, ₁^* ₁   ^*  ₁^* ₁   ^*

   

DEA ： CCR モデル



多入力・多出力



効率性について

0 ,

,

, , 0

( 1, , )

. . . : 1 max

1 1

1 1 1

1 1 1

1 1

   





  

 



s m

mk m k

sk s k

mo m o

so s o

o

u

u v

v u y v x v x k n

y

uv x v x t

s u y u y

  



<LP_o> 

* 1

o

Def

：

DMU_o

が

D

効率的

⇔ DMU_o

が

D

非効率的

⇔

* 1

o

* 1

o

この等号を満たす

k

の集合を

DMU_o

の優位集合（

or

参照集合

)

という

E_o

に属する

DMU

は

D

効率的 注）

D効率的だからといっ

て効率的とは言えない

効率的フロンティア

の一部を形成

DEA ： CCR モデル



多入力・多出力

 <LP_o>

の双対問題と最適解について

0 ,

,

, , 0

( 1, , )

. . . : 1 max

1 1

1 1 1

1 1 1

1 1

   





  

 



s m

mk m k

sk s k

mo m o

so s o

o

u

u v

v u y v x v x k n

y

uv x v x t

s u y u y

  



<LP_o> 

0

, ,

) , ,

1 (

0 )

(

. . . ( ) 0 ( 1, , ) min

1 1 1

1 1

 





   





n

io n

jn j

n in i

io yx xy y ij ms

x t

s



 

 





 

 





       

) , , 1 (

)

( :

) , , 1 (

) (

:

1 1

1

1 y y j s

y d

m i

x x

x d

io n

jn j

y j

n in i

io x

i   



  



双対問題

入力

i

の重み和

DMU_o

の入力

i

出力

j

の重み和

DMU_o

の出力

j

入力の余剰 出力の不足

CCR モデル

<D_o>

DEA ： CCR モデル



多入力・多出力



入力の余剰と出力の不足を求める

0 ,

,

0 ,

,

0 ,

,

) , , 1 (

)

(

) , , 1 (

) (

. .

) (

) .(

max

1 1 1 1

1

1 1

* 1

1



  





    

    

y s y

x m

x n

io n

jn j

y j

n in i

io x

i

y s y

x m x

d d

d d

s j

y y

y d

m i

x x

x d

t s

d d

d d



 

  





 

  



<LP_o>

の最適値

出力の不足の和 入力の余剰の和

<D_o>

を解いて最適解 を得た後，

この

LP

を解いて最適解 を得る．

) ,

, ,

(^* ^*_{1 } ^*_n

) ,

, ,

, ,

(d₁^x*  d_m^x* d₁^y*  d_s^y*

Def： DEA効率性の定義

 0

1,( ₁ ^*, , ^*, ₁ ^*, , ^*)

* y

s y

x m

x d d d

d  



となるDMUはDEA効率的

それ以外の

DMU

は

DEA

非効率的

DEA

の実行手順

DEA ： CCR モデル



例題



「意思決定科学」受講学生の効率性

学生（DMU） A B C D E F

勉強時間 x₁ 40 20 15 30 20 16 v₁ 授業集中度 x₂ 0.8 0.2 1 0.5 0.9 1 v₂ 出席率 x₃ 1 0.9 0.8 0.9 1 1 v₃ 中間試験 y₁ 40 60 30 20 70 50 u₁ 期末試験 y₂ 30 90 55 70 24 60 u₂

DMU ^（学生）

出力（

2

個）

入力（

3

個）

x₁ x₂ x₃

y₁ y₂ v₁

v₂ v₃

u₁ u₂

入力の

ウェイト

出力の ウェイト

効率性（生産性） ：＝

v₁

×

x₁

＋

v₂

×

x₂

＋

v₃

×

x₃ u₁

×

y₁

＋

u₂

×

y₂

DEA ： CCR モデル



学生

A

（

DMU_A

）の効率性を求める

0 ,

, 0 ,

,

16 1

60 50

9 1 . 0 20

24 70

9 1 . 0 5

. 0 30

70 20

8 1 . 0 15

55 30

9 1 . 0 2

. 0 20

90 60

8 1 . 0 40

30 40

. .

8 . 0 40

30 : 40

. max

2 1 3

2 1

3 2

1

2 1

3 2

1

2 1

3 2

1

2 1

3 2

1

2 1

3 2

1

2 1

3 2

1

2 1

3 2

1

2 1





 





 





 





 





 





 



 

 

u u v

v v

v v

v

u u

v v

v

u u

v v

v

u u

v v

v

u u

v v

v

u u

v v

v

u t u

s

v v

v

u

 u

<FP_A>

学生（DMU） A B C D E F

勉強時間 x₁ 40 20 15 30 20 16 v₁ 授業集中度 x₂ 0.8 0.2 1 0.5 0.9 1 v₂ 出席率x₃ 1 0.9 0.8 0.9 1 1 v₃ 中間試験 y₁ 40 60 30 20 70 50 u₁ 期末試験 y₂ 30 90 55 70 24 60 u₂

分数計画問題

0 ,

, 0 ,

,

16 60

50

9 . 0 20

24 70

9 . 0 5

. 0 30

70 20

8 . 0 15

55 30

9 . 0 2

. 0 20

90 60

8 . 0 40

30 40

1 8

. 0 40

. .

30 40

. max

2 1 3

2 1

3 2

1 2

1

3 2

1 2

1

3 2

1 2

1

3 2

1 2

1

3 2

1 2

1

3 2 1

2 1

3 2

1 2

1











    

   







   

u u v

v v

v v

v u

u

v v

v u

u

v v

v u

u

v v

v u

u

v v

v u

u

v v

v u

u

v v

v t

s

u u

線形計画問題

<LP_A>

0 ,

, , , ,

0 30 )

60 24

70 55

90 30

(

0 40 )

50 70

20 30

60 40

(

0 )

9 . 0 8

. 0 9

. 0

(

0 ) 9

. 0 5

. 0

2 . 0 8

. 0 ( 0.8

0 ) 16 20

30 15

20 40

( 40

. .

. min

6 5 4 3 2 1

6 5

4 3

2 1

6 5

4 3

2 1

6 5

4 3

2 1

6 5

4 3

2 1

6 5

4 3

2 1

    





      



      



























     



      

      

t s

（

P

）主問題

（

D

）双対問題

DEA ： CCR モデル



学生

A

（

DMU_A

）の効率性を求める

学生（DMU） A B C D E F

勉強時間 x₁ 40 20 15 30 20 16 v₁ 授業集中度 x₂ 0.8 0.2 1 0.5 0.9 1 v₂ 出席率x₃ 1 0.9 0.8 0.9 1 1 v₃ 中間試験 y₁ 40 60 30 20 70 50 u₁ 期末試験 y₂ 30 90 55 70 24 60 u₂

線形計画問題

<LP_A>

0 ,

, , , ,

0 30 )

60 24

70 55

90 30

(

0 40 )

50 70

20 30

60 40

(

0 )

9 . 0 8

. 0 9

. 0

(

0 ) 9

. 0 5

. 0

2 . 0 8

. 0 ( 0.8

0 ) 16 20

30 15

20 40

( 40

. .

. min

6 5 4 3 2 1

6 5

4 3

2 1

6 5

4 3

2 1

6 5

4 3

2 1

6 5

4 3

2 1

6 5

4 3

2 1

    





      



      



























     



      

      

t s

<LP_A>

の最適値

θ*=1

なら

次の

LP

も解く

0 ,

, , , , , , , , ,

30 )

60 24

70 55

90 30

(

40 )

50 70

20 30

60 40

(

)

9 . 0 8

. 0 9

. 0

(

) 9

. 0 5

. 0

2 . 0 8

. 0 ( 0.8

) 16 20

30 15

20 40

( 40

. .

) (

) (

. max

6 5 4 3 2 1 2 1 3 2 1

6 5

4 3

2 1

2

6 5

4 3

2 1

1

6 5

4 3

2 1

* 3

6 5

4 3

2 1

* 2

6 5

4 3

2 1

* 1

2 1

3 2

1



































































































































































y y x x x y y x x x

y y

x x

x

d d d d d d d d d d t s

d d

d d

d

DEA ： CCR モデル



例題 2 （

_{[3] p.15}

）

DMU A B C D E F

入力

1 x₁ 4 4 4 3 2 6

入力

2 x₂ 2 3 1 2 4 1

出力

y 1 1 1 1 1 1

0 ,

, ,

, ,

( ) 1 0

2 (2 3 2 4 ) 0

. . .4 (4 4 4 3 2 6 ) 0 min

6 5

4 3

2 1

6 5

4 3

2 1

6 5

4 3

2 1

6 5

4 3

2 1

 











     

      











   





     

      

t  s

入力）

0.83

×

A = 0.33

×

C + 0.67

×

D

出力）

A = 0.33

×

C + 0.67

×

D

DMU A

は

DEA

非効率的で，優位集合は

C

と

D

D E

A B

C F

1 2 3 4 5

1 2 3 4

o _x

1/y x₂/y

6

0.83

最適解：

θ*=0.83, (λ₁*,λ₂*,λ₃*,λ₄*,λ₅*,λ₆*)=(0,0,0.33,0.67,0,0) DMU A

についての問題

0.83 4

2 0.33 4

1 0.67 3

2 1 0.33 1 0.67 1