自由変数連続化による離散評点

自由変数連続化による離散評点

BCC

モデル計算の高速化

日大生産工

(

院

)

    ○吉村  彩    日大生産工

(

院

)

   

   

 茂木  渉

  

 

  

  日大生産工        篠原  正明

   

 

1．はじめに

  離散評点BCCモデルによる効率性計算においては，存在性 項目として追加された出力項目 に対する評価値 が自由 変数であり，正値，零値，負値のあらゆる値をとることができ

る

[1]．従って，例えば

y0 u₀

} 3 , 2 , 1 , 0 { }, 2 , 1 , 0 { }, 1 , 0

0 ={ ± ± ± ± ± ±

u

などと正負値を許容した離散評点に，それ以外の評価値

,

については，例えば あるいは などと正値あるいは非負値のみを 許容した離散評点に限定し，それらの離散評点組合せを列挙し て，評価組合せパタン毎に絶対効率値，相対効率値を計算し，

DMU別にすべての組合せパタンの中での最大相対効率値を

計算する[2]．

) ,..., 1

(i s

u_i = v_i(i=1,...,m) {0,1,2} }

3 , 2 , 1 , 0

{ {1,2,3}

文献[2]の離散評点

BCCモデルにもとづく計算効率値と，従

来のBCCモデルである連続評点

BCCモデルとの計算効率値と

を比較した結果，

BCCモデルの2

つの計算効率値はCCRモデル

の

2つの計算効率値と比較すると誤差が大きいことが判明した．

この原因としては，ⅰ

)BCCモデルにおいてはCCRモデルに自

由変数 が付加された，ⅱ

)自由変数

の変動域が広い，ⅲ

)

自由変数 による包絡の幾何学的形状

[3]などの理由により，

自由変数 の離散化が不十分であることが考えられる．そこ で，出力項目の1 つである存在性項目に対する評価値，自由変 数 のみを離散変数でなく連続変数として扱う． を連続変 数として扱うことは，離散評点値候補数を無限大にすることを 意味する．これにより自由変数 の不十分な離散化に対処す るアプローチを提案する．

u0 u₀

u0

u0

u0 u₀

u0

2．

変化による相対効率値最大化問題の

2変数LP

問題への帰着

u0

  と

v

^{を固定した下で， の相対効率値を とし，}

変化時最大値 を求める数理計画問題を以下に考察

する．

u DMU_k R_k

u0 _k

u R

0

max

u

^と

v

^{を固定した下で， の絶対効率値}

は

(1)式で与えられる．

) ,..., 1 (

DMU_j j= n

Aj

) ,..., 1

T (

0 0 T

n y j

A u

j j j

j + =

=

  

x v y

u (1)

但し，

y_0j =1 (j=1,...,n)^,

は固定された評価列ベクトル，

は可変の自由変数である．

v u, u0

) ,..., 1

T (

0 T

T

n u j

A

j j j

j = +

  

=

x v x v

y

u (2)

DMUk

^{の相対効率値 は}

(3)式で与えられる．

Rk

} { max _j

j k

k A

R = A (3)

u0

b a

A_j = _j + _j

^{とすると， は次式で与えられ} る．

0 , 0 >

> _j

j b

a

j j

aj

x v

y u

T T

= (4)

j

bj

x v^T

= 1 (5)

ここで， だが，

 

が成立すると仮定している． 変化時 最大化問 題は次式となる．

0 x 0 y 0 v 0

u≥(>) , ≥(>) , _j≥ , _j ≥ u^Ty_j >0,

Tx_j >0

v u₀ R_k

} {

maxmax

0 0

0 a bu

u b a

j j j

k k

u +

+ (6)

分母と分子に

t>0

を乗じ，

tu₀ =s

と置くと，

s

^{も自由変数} である．

Discrete-scoring BCC Model with Free Variable u0

Aya YOSHIMURA , Wataru MOGI and Masaaki SHINOHARA

 

} {

maxmax

0 0

0 a t btu

tu b t a

j j j

k k

u +

+ (7)

} {

max max

,

0 a t b s

s b t a

j j j

k k s

t +

+

> 自由

(8)

問題(8)は次の問題(9)〜

(12)と等価である．

目的関数：

z_k =a_kt+b_ks→max         (9)

制約条件：

max{a_jt+b_js}=1            

j

   (10)

s

：自由変数 (11)

>0

t (12)

>0

t

^{を で置換すれば，問題}

(9)〜(12)は次の問題(13)〜

(15)の2変数LP問題となる．

≥0 t

目的関数：

z_k =a_kt+b_ks→max          ⁽¹³⁾

制約条件：

a_jt+b_js≤1

 

(j=1,...,n)       (14)

≥0

t (15) (14)式のj

^{番目の制約式「}

a_jt+b_js≤1

^」を図

¹

^{に示すが，以} 下の切片，勾配を持つ．

t

^切片

j j

aj u y x v

T

1 T

=

= (16)

s

^切片

_j

b1j =v^Tx

= (17)

勾配

j

j j

b

a =−u^Ty

−

= (18)

又，図

2

には の場合のすべての制約条件式による 実行可能域例を示す．

5 ,

5 =

= k

n

s

t s

^切片

=v^Tx_j

t

^切片

j j

y u

x v

T T

=

勾配

=−u^Tyj

0

図

2.1

．

2

変数

LP

問題の第 制約条件式

s

t

0

① ②

③

④ max

5 5 5

→ +

=

   

s b t a z

⑤

a b

c

d

図

2.2．2変数LP問題の実行可能域例

図

2において，k=5

としているため目的関数

z₅=a₅t+b₅s

の等高線は第5 制約式(等号

)⑤と平行である．

3．2変数LP問題の解法アルゴリズム

2変数LP問題(13)〜(15)は単体法などで解くことが可能であ

るが，ここでは(表計算に直接組込むため

)陽な形で求解するア

ルゴリズムを与える．基本的な考え方は単体法と同じである．

初期点は原点

O

で，次に凸な実行可能域の外辺

s

^{軸に沿って，}

最初の制約式との交点(図

2

の

a)まで進む．次に，その制約式

の辺に沿って最初の制約式との交点

(図2のb)まで進む…．制

約式の勾配と目的関数の勾配の値の大小関係から目的関数が 最大と判断できた交点でアルゴリズムは停止する．以下に

2変

数

LP問題(13)〜(15)(目的関数 )を解くアルゴリズムを記述

する．

zk

1. s

軸上(

t=0)のs

^切片値 の最小値を与える制約式 番号を とする．

xj

v^T

} ,...,N N

) 1 (

p ={1,2

^．

N j

p(1) argminj v^Tx

= ∈

k

p u y

y

u^T ₍₁₎ ≥ ^T

) 1 ( p N N

(19)

イ

)

 

                (20) 

ならば，

                (21)

として停止．

0

),

1 (

T =

= t

s v x_p

2. ← −

N

^{個の連立方程式}

j

 

 

,       (22)

) 1

1 ( ) 1

( t+b s=

a_{p p} a_jt+b_js=1 (j∈N)

の交点の

t

座標は次式で与えられる． 

) 1 ( )

1 (

) 1

) (

), 1 ( (

p j j p

p j

b a b a

b j b

p

t −

= −   (j∈N)      (23)

N

^{個の交点の中で でかつ} を選ぶ． 

0 ) ), 1 ( (p j ≥ t

) ), 1 ( ( mint p j

) ), 1 ( ( min arg ) 2

( t p j

p = j∈N   (≥0)          (24)

ロ) 

                     (25)

 

ならば， 

k

p u y

y

u^T ₍₂₎ ≥ ^T

) 1 ( ) 2 ( ) 2 ( ) 1 (

) 2 ( ) 1 (

p p p p

p p

b a b a

a s a

−

= − ^,

) 1 ( ) 2 ( ) 2 ( ) 1 (

) 1 ( ) 2 (

p p p p

p p

b a b a

b t b

−

= − ⁽²⁶⁾

として停止． 

3. N←N−p(2) 4. N

^{個の連立方程式}

 

,       (27)

) 1

2 ( ) 2

( t+b s=

a_{p p} a_jt+b_js=1 (j∈N)

の交点の

t

座標は次式で与えられる．

) 2 ( )

2 (

) 2

) (

), 2 ( (

p j j p

p j

b a b a

b j b

p

t −

= −   (j∈N)      (28)

N

^{個の交点の中で でかつ}

を選ぶ．

)) 2 ( ), 1 ( ( ) ), 2 (

(p j t p p

t ≥

) ), 2 ( ( mint p j

) ), 2 ( ( min arg ) 3

( t p j

p = j∈N   (≥t(p(1),p(2)))   (29)

ハ

)

 

                     (30)

ならば，

k

p u y

y

u^T ₍₃₎≥ ^T

) 2 ( ) 3 ( ) 3 ( ) 2 (

) 3 ( ) 2 (

p p p p

p p

b a b a

a s a

−

= − ^,

) 2 ( ) 3 ( ) 3 ( ) 2 (

) 2 ( ) 3 (

p p p p

p p

b a b a

b t b

−

= − ⁽³¹⁾

として停止．

) 3 ( ) 2 ( ), 2 ( ) 1 ( ), 3

( p p p p

p N

N← − ← ←

^と

して4.へ．

〔アルゴリズム記述終了〕

(

コメント

1)  s

^軸 も制約式の中に入れれば，より統一 的なアルゴリズムの記述が可能と思う．

) 0 (t=

(コメント2) (20),(25),(30)の判定において，等号が成立する場

合は，注目交点から次の交点の辺に対する領域で与えら れる．

(コメント3) s

^と

t

^{が求まれば， により自由変数}

の値が定まる．

2

つの交点

(

^と

(

^{の辺が最適解}

の時は

(コメント2)，「

t s

u₀ = / u₀

) ,₁

1 t

s s₂,t₂)

2 2 1 1

0 t

s t

s ≤u ≤ ₀

DMUデータ

」の形で

u

^は上限，

下限制約下の区間で与えられる．

4．表計算による例題

以下の表4.1．2 入力2出力のDMU データを，表計算によっ て解いた結果を示す．なお，今回用いたデータは参考文献[4]

(表1.5

病院の例)で用いられていたものである．

表

4.1．2入力2

出力のDMUデータ

DMU x₁ x₂ y₁ y₂

1 38 284 250 120

2 53 306 260 147

3 50 268 250 100

4 30 244 190 100

5 31 206 152 80

ここでは，評価ベクトル

u

^，

v

^を

u=(1，1)，v=(1，1)とし，

目的関数を

z₁=a₁t+b₁k→max

Tx

j j,b

yj T

xj

T j,bj

DMU v^Tx

とする．

1．

はじめに，各々の ，

_v

，

a

を求める．

yj

u^T _j

表4.2．

u

，

v

，

a

の結果

j u^Tyj aj bj

1 322 370 1.149068323 0.00310559

2 359 407 1.133704735 0.002785515

3 360 420 1.166666667 0.002777778

4 274 190 0.693430657 0.003649635

5 237 152 0.641350211 0.004219409

 

表4.2より

s

^切片値

v

の最小値を与える制約式番号を求

め、第

1端点とする．

xj T

t座標 t_p(1)= 0

表4.3．第1端点

s切片の 最小値 を与える 制約式番号

p(1)= 5

s座標 min(v^Tx_j)=s_p(1)= 237 ap(1)= 0.641350211 b_p(1)= 0.004219409

表4.3より，

v

の最小値を与える制約式番号 が

DMU 5

となり， となる．

xj

T p(1)

237 min

arg ) 1

( = ^T =

∈ j

N j

x v p

 

ここで， なので，次のステップ

に進む．

152

T 370

) 1 (

Ty_p ≥u y_k≠ ≥ u

2． DMU 5

以外のDMUと，目的関数の交点の 座標を求め

る．

t

表

4.4．DMUと目的関数の 座標t

DMU t_k t_k>t_pi 1 0.389908 0.389908257

2 0.478431 0.478431373

3 0.458955 0.458955224

4 0.973684 0.973684211

5 #DIV/0! -

表

4.4より，

交点の中で かつ を選

ぶ．

 

0 ) ), 1 ( (p j ≥

t mint(p(1),j) s

^切片値 の最小値を与える制約式番号を求め、

第

2

端点とする．

xj v^T

表

4.5．第2端点

t座標 min(t_k)= 0.389908257

s切片の 最小値 を与える 制約式番号

p(2)= 1

s座標 min(v^Tx_j)=s_p(2)= 177.733945 a_p(2)= 1.149068323 b_p(2)= 0.00310559

表

4.5より

が

DMU 1となり， =322

となる．ここで， なので，

) 2 (

p _j

N j

p(2) argminv^Tx

= ∈

370

T 370

) 2 (

Ty_p ≥u y_k= ≥ u

) 2 ( ) 3 ( ) 3 ( ) 2 (

) 3 ( ) 2 (

p p p p

p p

b a b a

a s a

−

= − ，

) 2 ( ) 3 ( ) 3 ( ) 2 (

) 2 ( ) 3 (

p p p p

p p

b a b a

b t b

−

= −

として停止する。

表

4.6

．第

2

端点の

s

座標，

t

座標，

u₀

の値

s= 177.733945 t= 0.3899082569 u₀= 455.8352941

  表4.6より，s=177.733945 ，

t=0.3899082569となり，

より，

=455.8352941となる．ここで，(コ

メント

2)の等号が成立しており，この

は上限を与えて

いる．

t s

u₀= / u₀

u0

同様に，目的関数を

z₂ =a₂t+b₂k→max

，…

5 max

5

5=at+bk→

z

とした時の全てのパターンを計算 し，各々の

u₀

を求める．

図

4.1は今回用いたDMU

データの線形計画問題をグラフ化

したものである．

-100 0 100 200 300 400

0 0.2 0.4 0.6 0.8 1

DMU1 DMU2 DMU3 DMU4 DMU5

図

4.1．2変数LP問題のグラフ

5．おわりに

自由変数 を連続変数として扱うアプローチ法を提案した．

u0

今回は評価ベクトルを

_u=(1，1)，v=(1，1)としたが，違う

値を用いた時とではどの程度結果が変わってくるかを考察し たい．また，交点が3 本以上の直線で決まる場合は退化で，各々 の傾きを調べ，その傾きが一番小さいものを選ぶようにしなけ ればならない．この場合を考慮して作り直す必要がある．

DMUデータを増やし，そのBCCモデルの効率値と，本論文

のアルゴリズムで求めた を用いた

BCC

モデルの効率値が 一致するかの検証が今後の課題である．

u0

参考文献

[1]

篠原正明・大澤慶吉・鈴木洋臣：BCC モデルのCCRモデ ルに基づく解釈，第

35回日本大学生産工学部

学術講演会 数理情報部会 講演概要，pp121-122 (2002.12)

[2]

金子隆史・大久保智弘・大澤慶吉・篠原正明：離散評点

BCC

モデルの試み，第

39回日本大学生産工学部 学術講演会 数

理情報部会 講演概要，pp41-44 (2006.12)

[3]

大久保智弘・大澤慶吉・篠原正明：性能低下傾向にある生 産活動群の効率性評価についての考察，第

40回日本大学生

産工学部 学術講演会 数理情報部会 講演概要，

pp91-94 (2007.12)

[4] 刀根薫：経営効率性の測定と改善〜包絡分析法DEAによる

〜、日科技連

(1993)