Alokacne ulohy

ALOKAČNÉ ÚLOHY

ALOKÁCIA VÝROBNÝCH PROCESOV

1. Alokácia výrobných procesov (AVP) -> do jedného miesta

Metóda: - pomerovo-indexová metóda
Kedy:

- ak sú známe lokality a treba vybra

ť

najvhodnejšiu

- ak je

ť

ažké vy

č

ísli

ť

presné náklady

- ak nie sú presne známi dodávatelia ani odberatelia
- ak existuje ve

ľ

a faktorov, ktoré je

ť

ažko ohodnoti

ť

, ale je možné vyjadri

ť

ich

závažnos

ť

vo

č

i ostatným faktorom a porovna

ť

ich hodnoty pre jednotlivé lokality

Postup:

a) Pre vybrané lokality (L = 1 ... n) a daný výrobný proces vyberáme rozhodujúce faktory

(F1 ... Fn). Každému faktoru Fi prisúdime váhu wi najlepšie tak, aby suma bola 1.

Fi (i = 1 ... m): wi =>

1

1

=

∑

=

m

i

i

w

b) Pre hodnotenie jednotlivých faktorov Fi zvolíme interval hodnotenia (tzv. kardinálnu mieru)

HFi, ktorý bude ma

ť

hornú hranicu KHi a dolnú hranicu KDi, t.j.

i

i

i

KH

KD

HF

,

∈

.

c) Experti stanovia hodnotenie

L

i

HF (L = 1 ... n, i = 1 ... m) pre všetky lokality L a pre všetky

a faktory Fi.

d) Výsledné hodnotenie danej lokality L je dané váženým sú

č

tom:

∑

=

=

m

i

L

i

i

L

HF

w

C

1

e) Ako najlepšia bude vybraná tá lokalita, pre ktorú je hodnota C

L maximálna, t.j.

L

C

L

max

=

Príklad:
Úlohou je vybra

ť

najvhodnejšiu lokalitu pre umiestnenie výroby drevených hra

č

iek z troch

vytipovaných lokalít (Spišská Nová Ves – SNV, Rož

ň

ava – RV, Svidník – Sk).

2. Alokácia výrobných procesov (AVP) -> do jedného miesta - Optimálne umiestenie distribu

č

ného

centra

Definícia úlohy:

V rovine existuje m-objektov (odberate

ľ

ov) (P1 ... Pm) so súradnicami (a1, b1), … (an, bn). Treba

nájs

ť

súradnice pre umiestnenie nového objektu (distribu

č

ného centra) x = (x, y) tak, aby

celkové náklady na realizáciu väzieb medzi existujúcimi objektmi a novým objektom boli

minimálne. Intenzitu väzby medzi objektmi Pi a novým objektom x vyjadrujú koeficienty
wi (i = 1 ... n).

Kriteriálna funkcia:

( )

( )

∑

=

=

m

i

i

i

P

x

d

w

x

f

1

,

Kde vzdialenos

ť

(

)

i

P

x

d ,

môže by

ť

:

a) Euklidovská

(

) (

)2

2

i

i

b

y

a

x

−

+

−

b) Kvadrát Euklidovskej

(

) (

)2

2

i

i

b

y

a

x

−

+

−

c) Rektilineárna

(

)

[

]

i

i

i

y

x

b

y

a

x

w

−

+

−

,

min

d) Minimalizácia najvzdialenejšieho bodu

(

) (

)









−

+

−

2

2

max

min

i

i

b

y

a

x

Pre každý typ vzdialenosti je iný postup výpo

č

tu optimálneho umiestnenia nového objektu

(distribu

č

ného centra).

a) Euklidovská vzdialenosť – používa sa numerické riešenie (tzv. hyperbolická aproximácia).

H

ľ

adáme extrém funkcie dvoch premenných (súradnica x a súradnica y pre umiestnenie nového

objektu – distribu

č

ného centra), preto derivujeme funkciu nákladov

( )

(

) (

)

∑

=

−

+

−

=

m

i

i

i

i

b

y

a

x

w

x

f

1

2

2

parciálne a jednotlivé parciálne derivácie položíme rovné

nule:

Po úprave a zavedení substitúcie gi(x,y) dostávame postupne:

pre x-ovú súradnicu:

pre y-ovú súradnicu:

Dostávame iteračné vzorce pre výpočet súradníc optimálneho umiestnenia distribučného centra

x

(k) a y(k). Na začiatku stanovíme hodnoty pre ťažisko (x(0) a y(0)) a postupne v každej ďalšej iterácii

konverguje riešenie k optimu. Po dosiahnutí požadovanej presnosti (napríklad že hodnota
kriteriálnej funkcie na druhom ráde za desatinnou čiarkou sa už nemení) výpočet ukončíme
a aktuálne hodnoty x

(k) a y(k) určujú doporučené umiestnenie distribučného centra.

( )

(

)

(

) (

)

0

!

1

2

2

=

−

+

−

−

=

∂

∂

∑

=

m

i

i

i

i

i

b

y

a

x

a

x

w

x

x

f

(

) (

)

(

) (

)

( )

(

) (

)

( )

(

)

(

)

(

)

(

)

(

)

(

)

( )

∑

∑

∑

∑

∑

∑

=

=

−

−

−

−

=

=

=

=

=

=

=

+

−

+

−

=

−

+

−

=

−

+

−

m

i

i

i

i

m

i

k

k

i

k

k

i

i

k

m

i

m

i

i

i

i

i

i

i

i

m

i

m

i

i

i

i

i

i

i

i

w

w

a

x

y

x

g

y

x

g

a

x

g

a

g

x

b

y

a

x

w

y

x

g

b

y

a

x

a

w

b

y

a

x

w

x

1

0

1

1

1

1

1

1

1

2

2

1

1

2

2

2

2

,

,

,

ξ

(

) (

)

(

) (

)

( )

(

) (

)

( )

(

)

(

)

(

)

(

)

(

)

(

)

( )

∑

∑

∑

∑

∑

∑

=

=

−

−

−

−

=

=

=

=

=

=

=

+

−

+

−

=

−

+

−

=

−

+

−

m

i

i

i

i

m

i

k

k

i

k

k

i

i

k

m

i

m

i

i

i

i

i

i

i

i

m

i

m

i

i

i

i

i

i

i

i

w

w

b

y

y

x

g

y

x

g

b

y

g

b

g

y

b

y

a

x

w

y

x

g

b

y

a

x

b

w

b

y

a

x

w

x

1

0

1

1

1

1

1

1

1

2

2

1

1

2

2

2

2

,

,

,

ξ

( )

(

)

(

) (

)

0

!

1

2

2

=

−

+

−

−

=

∂

∂

∑

=

m

i

i

i

i

i

b

y

a

x

b

y

w

y

x

f

Príklad:
Je potrebné nájsť optimálne umiestnenie trafostanice pre 4 stanice s danými súradnicami: A[2,6],
B[6,7], C[7,4], D[5,2], káblom s mernými ročnými nákladmi 3 PJ/km. Nová stanica bude napájaná
káblom s ročnými nákladmi 5 PJ/km z existujúcej trafostanice E[1,1].

Vyjdeme z počiatočných hodnôt súradníc x

(0) a y(0) pre ťažisko a vypočítame zodpovedajúcu

hodnotu kriteriálnej funkcie f(x

(0), y(0)). Potom vypočítame substitučné koeficienty g

i(x

(0), y(0))

a dosadíme ich do iteračných vzorcov pre výpočet x

(1) a y(1).

( )

(

)

( )

(

)

( )

( )

(

)

(

) (

)

(

) (

)

( )

( )

(

)

(

) (

)

( )

( )

(

)

(

) (

)

.

2

2

0

0

1

.

2

2

0

0

1

2

2

2

2

0

0

.

0

.

0

1

65

,

3

1

82

,

3

.

5

,

...

0092

,

1

001

,

0

6

65

,

3

2

82

,

3

.

3

,

935

,

55

1

65

,

3

1

82

,

3

.

5

...

6

65

,

3

2

82

,

3

.

3

,

65

,

3

17

62

5

3

3

3

3

1

.

5

2

4

7

6

.

3

82

,

3

17

65

5

3

3

3

3

1

.

5

5

7

6

2

.

3

=

+

−

+

−

=

=

+

−

+

−

=

=

−

+

−

+

+

−

+

−

=

=

=

+

+

+

+

+

+

+

+

=

=

=

+

+

+

+

+

+

+

+

=

ξ

y

x

g

y

x

g

y

x

f

y

x

Opäť vypočítame hodnotu kriteriálnej funkcie pre nové umiestnenie distribučného centra

f(x

(1), y(1)) a celý postup iteratívne opakujeme až do chvíle, kým zmena hodnoty kriteriálnej funkcie

v dvoch po sebe nasledujúcich iteráciách klesne pod jednu stotinu PJ (viď. obrázok vyššie).

b) Ak sa vzdialenosť meria ako kvadrát Euklidovskej vzdialenosti, t.j. (

) (

)2

2

i

i

b

y

a

x

−

+

−

,

potom je optimálnym umiestnením distribučného centra jeho ťažisko (viď. vyššie).

c) V prípade

rektilineárnej vzdialenosti sa používa na výpočet optimálneho umiestnenia

distribučného centra tzv. mediánové umiestenie. Optimálneho hodnoty pre súradnicu x aj y totiž
musia ležať v v x-ovej, resp. y-ovej súradnici niektorého zo vstupných objektov (pre každú
súradnicu to samozrejme môže byť iný objekt).

V tomto prípade je potrebné najprv jednotlivé objekty usporiadať vzostupne podľa ich

súradnice x (resp. y), a potom vypočítať jednotlivé čiastkové súčty váh wi príslušných týmto
objektom, t.j.:

pre x-ovú súradnicu:

pre y-ovú súradnicu:

k

m

k

m

k

i

i

m

k

i

i

k

m

s

s

s

s

s

s

w

s

w

s

a

a

a

≤

≤

≤

≤

≤

=

=

≤

≤

≤

−

=

=

∑

∑

1

2

1

1

1

2

1

...

2

1

...

k

m

k

m

k

i

i

m

k

i

i

k

m

s

s

s

s

s

s

w

s

w

s

b

b

b

≤

≤

≤

≤

≤

=

=

≤

≤

≤

−

=

=

∑

∑

1

2

1

1

1

2

1

...

2

1

...

Príklad:
Použijeme tie isté vstupné údaje ako v príklade pre prípad Euklidovskej vzdialenosti vyššie.

Pre x-ovú súradnicu:

pre y-ovú súradnicu:

a5 ≤ a1 ≤ a4 ≤ a2 ≤ a3

b5 ≤ b4 ≤ b3 ≤ b1 ≤ b2

s5 = 5

s5 = 5

s1 = 5 + 3 = 8

s4 = 5 + 3 = 8

s4 = 5 + 3 + 3 = 11 -> optimálna súradnica

s3 = 5 + 3 + 3 = 11 ->optimálna súradnica

s2 = 5 + 3 + 3 + 3 = 14

s1 = 5 + 3 + 3 + 3 = 14

s3 = 5 + 3 + 3 + 3 + 3 = 17 5

s2 = 5 + 3 + 3 + 3 + 3 = 17 4

sm = ˝ 17 = 8,5

sm = ˝ 17 = 8,5

x = (5, 4)

d) V prípade

minimalizácie

vzdialenosti

najvzdialenejšieho

objektu

je

optimálnym

umiestnením distribučného centra stred kružnice s minimálnym polomerom opísanej tak, že
v nej ležia všetky vstupné objekty.