Data Envelopment Analysis (Analýza obalu dat)

Data Envelopment Analysis (Analýza obalu dat) Martin Branda Univerzita Karlova v Praze Matematicko-fyzikální fakulta Katedra pravděpodobnosti a matematické statistiky

Optimalizace s aplikací ve financích

Martin Branda (KPMS MFF UK)

DEA

1 / 24

Motivace 3 firmy:

Suroviny (vstupy) Výrobky (výstupy)

1 3 7

2 6 11

3 3 5

Která pracuje „nejlépeÿ – efektivně – eficientně? 7 11 5 > > , 3 6 3 tedy (asi) firma 1. Co když je vstupů a výstupů více? Co když zdvojnásobením vstupů nemůžu zdvojnásobit výrobu? Martin Branda (KPMS MFF UK)

DEA

2 / 24

Decision Making Units

Homogenní jednotky – Decision Making Units (DMU) j = 1, . . . , n Vstupy X = {xij }, i = 1, . . . , m (preferujeme nižší hodnoty) Výstupy Y = {yrj }, r = 1, . . . , s (preferujeme vyšší hodnoty) Předpokládáme, že data jsou kladná.


DEA

3 / 24

Příklad – bankovní pobočky

Vstupy počet zaměstnanců (dále děleno dle kvalifikace: junior, senior, vedoucí) rozloha pobočky nemzdové náklady Výstupy počet uzavřených smluv (běžný účet, hypotéka, spotřebitelská půjčka, pojištění) počet nově získaných klientů


DEA

4 / 24

Příklad – fakulty

Vstupy počet zaměstnanců (dále děleno dle kvalifikace: asistent, docent, profesor) počet studentů, kteří nastoupí do 1. ročníku Výstupy počet vědeckých publikací počet absolventů (Bc., Mgr., Ph.D.)


DEA

5 / 24

Charnes–Cooper–Rhodes (CCR) model Lineárně frakcionální formulace

Posouzení eficience jednotky 0 ∈ {1, . . . , n} Ps ur y r 0 max Prm=1 ur ,vi i=1 vi xi0 s.t. Ps u y Prm=1 r rj ≤ 1, j = 1, . . . , n, i=1 vi xij ur ≥ 0, r = 1, . . . , s, vi

≥

0, i = 1, . . . , m.

Jednotka 0 je eficientní, právě když je optimální hodnota rovna jedné. Každá jednotka dostane pro ni nejvýhodnější váhy.


DEA

6 / 24

Charnesova–Cooperova transformace

Položíme t =


1 Pm

i=1 vi xi0

u˜r

= t · ur ,

v˜i

= t · vi .

DEA

,

7 / 24

Charnes–Cooper–Rhodes (CCR) model Multiplikátorová forma

Po Charnesově–Cooperově transformaci LP: max ur ,vi

s X

ur yr 0

r =1

s.t. m X

s X

ur yrj −

r =1


vi xi0

i=1 m X

=

1,

vi xij

≤

0, j = 1, . . . , n,

ur

≥

0, r = 1, . . . , s,

vi

≥

0, i = 1, . . . , m.

i=1

DEA

8 / 24

Charnes–Cooper–Rhodes (CCR) model

Dualita v LP (na cvičení) . . .


DEA

9 / 24

Charnes–Cooper–Rhodes (CCR) model Duální (obalová) forma

min θ θ,λj

s.t. n X

λj xij

≤

θxi0 , i = 1, . . . , m,

λj yrj

≥

yr 0 , r = 1, . . . , s,

λj

≥

0, j = 1, . . . , n.

j=1 n X j=1

Model orientovaný na vstupy.


DEA

10 / 24

Charnes–Cooper–Rhodes (CCR) model Multiplikátorová forma

Infisimální ε > 0, aby byly všechny vstupy a výstupy zahrnuty max ur ,vi

s X

ur yr 0

r =1

s.t. m X

s X

ur yrj −

r =1


vi xi0

i=1 m X

=

1,

vi xij

≤

0, j = 1, . . . , n,

ur

≥

ε, r = 1, . . . , s,

vi

≥

ε, i = 1, . . . , m.

i=1

DEA

11 / 24

Charnes–Cooper–Rhodes (CCR) model Duální (obalová) forma

min

θ,λj ,si− ,sr+

θ

−

ε

m X i=1

si− +

s X

! sr+

r =1

s.t. n X j=1 n X

λj xij + si−

=

θxi0 , i = 1, . . . , m,

λj yrj − sr+

=

yr 0 , r = 1, . . . , s,

λj

≥

0, j = 1, . . . , n,

si− sr+

≥

0, i = 1, . . . , m,

≥

0, r = 1, . . . , s.

j=1


DEA

12 / 24

Klasifikace jednotek

Nechť θ∗ , si−∗ , sr+∗ je optimální řešení, potom jednotka je Neeficientní θ∗ < 1. Slabě eficientní θ∗ = 1 a existuje si−∗ > 0 nebo sr+∗ > 0. Silně eficientní θ∗ = 1 a všechny si−∗ = 0 nebo sr+∗ = 0.


DEA

13 / 24

Production possibility set

Množina možných produktů   n n   X X PPS = (x, y ) : xi = λj xij , yr = λj yrj , λj ≥ 0   j=1


j=1

DEA

14 / 24

Výnosy z rozsahu

Rostou se vstupy proporcionálně i výstupy? Tj. (x, y ) ∈ PPS, α > 0 =⇒ (αx, αy ) ∈ PPS ? Platí-li, konstantní výnosy z rozsahu (Constant Returns to Scale – CRS). Neplatí-li, variabilní výnosy z rozsahu (Variable Returns to Scale – VRS):   n n n   X X X VRS PPS = (x, y ) : xi = λj xij , yr = λj yrj , λj = 1, λj ≥ 0   j=1


j=1

DEA

j=1

15 / 24

Výnosy z rozsahu


DEA

16 / 24

Výnosy z rozsahu

Z obrázku vidíme: CRS – nejmenší konvexní kužel obsahující data VRS – „horníÿ konvexní obal dat


DEA

17 / 24

Příklad – 3 firmy


1 3 7

2 6 11

3 3 5

Položme ε = 0 CRS eficientní: firma 1 f1: θ∗ = 1 f2: θ∗ = 0.786 f3: θ∗ = 0.714

VRS eficientní: firmy 1 a 2 f1: θ∗ = 1 f2: θ∗ = 1 f3: θ∗ =? Martin Branda (KPMS MFF UK)

DEA

18 / 24

Příklad – 3 firmy


1 3 7

2 6 11

3 3 5

Položme ε = 0 CRS eficientní: firma 1 f1: θ∗ = 1 f2: θ∗ = 0.786 f3: θ∗ = 0.714

VRS eficientní: firmy 1 a 2 i 3 f1: θ∗ = 1 f2: θ∗ = 1 f3: θ∗ = 1 (vstupy už nejdou zlepšit → model orientovaný na výstupy) Martin Branda (KPMS MFF UK)

DEA

19 / 24

Banker–Charnes–Cooper (BCC) model Duální (obalová) forma – orientace na vstupy

min

θ,λj ,si− ,sr+

θ

−

ε

m X i=1

si−

+

s X

! sr+

r =1

s.t. n X j=1 n X

λj xij + si−

=

θxi0 , i = 1, . . . , m,

λj yrj − sr+

=

yr 0 , r = 1, . . . , s,

λj

=

1,

λj

≥

0, si− ≥ 0, sr+ ≥ 0.

j=1 n X j=1


DEA

20 / 24

Banker–Charnes–Cooper (BCC) model Duální (obalová) forma – orientace na výstupy

max

ϕ,λj ,si− ,sr+

ϕ

+

ε

m X i=1

si−

+

s X

! sr+

r =1

s.t. n X j=1 n X

λj xij + si−

=

xi0 , i = 1, . . . , m,

λj yrj − sr+

=

ϕyr 0 , r = 1, . . . , s,

λj

=

1,

λj

≥

0, si− ≥ 0, sr+ ≥ 0.

j=1 n X j=1


DEA

21 / 24

Tone (2001) slack-based model

P 1 − 1/m m si− /xi0 min Psi=1 + λj ,si− ,sr+ 1 + 1/s r =1 sr /yr 0 s.t. n X j=1 n X

λj xij + si−

=

xi0 , i = 1, . . . , m,

λj yrj − sr+

=

yr 0 , r = 1, . . . , s,

λj

≥

0, si− ≥ 0, sr+ ≥ 0.

j=1

Charnesova–Cooperova transformace na LP (na cvičení).


DEA

22 / 24


DEA

23 / 24

Literatura

Banker, R.D., Charnes, A., Cooper, W. (1984). Some models for estimating technical and scale inefficiencies in Data Envelopment Analysis. Management Science 30 (9), 1078–1092. Charnes, A., Cooper, W., Rhodes, E. (1978). Measuring the efficiency of decision-making units. European Journal of Operations Research 2, 429–444. Cooper, W.W., Seiford, L.M., Zhu, J. (2011). Handbook on data envelopment analysis, Springer, New York. Tone, K. (2001). A slacks-based measure of efficiency in data envelopment analysis. European Journal of Operations Research 130, 498–509.


DEA

24 / 24

Data Envelopment Analysis (Analýza obalu dat)

Recommend Documents