Alokacne ulohy pokracovanie

ALOKAČNÉ ÚLOHY

3. Alokácia výrobných procesov do viacerých miest

3.1 Priradzovací problém (základná verzia)

DEFINÍCIA

Majme n-objektov, ktoré je potrebné umiestni

ť

do n-miest s minimálnymi nákladmi. Ak

poznáme náklady cij (i = 1 ... n, j = 1 ... n) pre lokalizáciu i-teho objektu do j-teho miesta, potom je
možné zostavi

ť

jednoduchý bivalentný model.

MODEL:

{ }1

,

0

,

∈

j

i

x

->

1 ak i-ty objekt je umiestnený do j-teho miesta

->

0 ak i-ty objekt nie je umiestnený do j-teho miesta

( )

n

i

x

n

j

x

MIN

x

c

x

f

n

j

ij

n

i

ij

n

i

n

j

ij

ij

..

1

1

..

1

1

1

1

!

1

1

=

∀

=

=

∀

=

=

=

∑

∑

∑∑

=

=

=

=

3.2 Priradzovací problém (existujú väzby iba medzi novými a existujúcimi objektmi)

DEFINÍCIA

Máme p-existujúcich objektov, n-nových objektov a n-miest. V tomto prípade existujú väzby

medzi novými a existujúcimi objektmi. Je známa matica vzdialeností medzi existujúcimi objektmi

a novými miestami

[ ]P

n

ij

d

D

=

a matica prepravných sadzieb

[ ]P

n

ij

w

W

=

je intenzita väzby medzi

starými a novými objektmi. Potom maticu nákladov možno vypočítať nasledovne:

[ ]n

n

ij

c

D

W

C

=

=

.

Bivaletný model je potom rovnaký ako pri základnej verzii priradzovacieho problému.

MODEL:

{ }1

,

0

,

∈

j

i

x

->

1 i-ty objekt je umiestnený do j-teho umiestnenia

->

0 i-ty objekt nie je umiestnený do j-teho umiestnenia

( )

n

i

x

n

j

x

MIN

x

c

x

f

n

j

ij

n

i

ij

n

i

n

j

ij

ij

..

1

1

..

1

1

1

1

!

1

1

=

∀

=

=

∀

=

=

=

∑

∑

∑∑

=

=

=

=

Príklad:

V tabuľke sú uvedené vzdialenosti v [m] medzi existujúcimi strojmi P, O, R a novými strojmi

A, B, C. Z priestorových dôvodov nemožno premiestniť stroj z miesta B do miesta H. Nájdite
optimálne rozmiestnenie nových objektov do nových miest E, F, G, H.

Keďže miest je o 1 viac ako strojov, zavedieme fiktívny stroj D s nulovými počtami paliet

prepravovanými od neho, resp. k nemu, t.j.:

























=













































=

=

0

0

0

0

40

39

28

21

1000

27

17

24

50

47

34

25

2

5

3

4

4

3

2

3

6

5

4

1

.

0

0

0

2

3

4

3

4

0

2

4

5

D

W

C

Model:

{ }

1

,

0

,

∈

j

i

x

->

1 ak i-ty objekt (A,B,C,D) je umiestnený do j-teho miesta (E,F,G,H)

->

0 ak i-ty objekt nie je umiestnený do j-teho miesta

( )

4

..

1

1

4

..

1

1

4

1

4

1

!

4

1

4

1

=

∀

=

=

∀

=

=

=

∑

∑

∑∑

=

=

=

=

i

x

j

x

MIN

x

c

x

f

j

ij

i

ij

i

j

ij

ij

3.3 Kvadratický priradzovací problém

DEFINÍCIA

Máme umiestniť n-nových objektov do n-miest. Medzi novými objektmi existujú vzájomné

väzby. Je známa matica vzdialeností

[ ]n

n

ij

d

D

=

, kde dij je vzdialenosť medzi i-tym a j-tym

miestom. A matica prepravných sadzieb

[ ]n

n

ij

w

W

=

, kde wij je intenzita väzby medzi i-tym a j-tym

novým objektom. Je symetrická okolo hlavnej diagonály.













2

n

Každé prípustné riešenie možno vyjadriť ako permutáciu

( ) ( )

( )

(

)

n

p

p

p

P

,...,

2

,

1

=

, kde p(i)=k

znamená, že i-ty objekt pôjde do miesta k.

Náklady pre akúkoľvek permutáciu sú:

( )

( ) ( )

∑∑

=

=

=

n

i

n

j

j

P

i

P

ij d

w

P

f

1

1

METÓDY:

• Metóda CRAFT je heuristická a nezaručí nájdenie najlepšieho riešenia

• Metóda vetvenia a medzí zaručuje nájdenie optimálneho riešenia, ale v nepolynomiálnom

čase v závislosti od veľkosti vstupu

CRAFT:
1) Z východzej (náhodnej) permutácie sa vytvorí

nových permutácií výmenami

všetkých dvojíc objektov v o východzej

permutácii.

2) Pre každú permutáciu sa vypočíta kriteriálny funkcia a vyberie sa to najlepšie a stane sa

východzou permutáciou pre nasledujúcu iteráciu algoritmu.

3) Celý postup sa opakuje dovtedy, kým sa zlepšuje kriteriálna funkcia z jednej iterácie na druhú.

Príklad:

4 nové stroje môžu byť umiestené do miest A, B, C, D. Vzdialenosti medzi novými miestami sú

uvedené v matici D , denné počty prepravovaných paliet medzi dvojicami nových strojov sú v matici

W . Jednotkové prepravné náklady sú rovnaké.

























=

























=

0

7

0

3

7

0

2

1

0

2

0

4

3

1

4

0

0

3

6

6

3

0

3

5

6

3

0

4

6

5

4

0

W

D

Vyjdeme z náhodného rozmiestnenia objektov reprezentovaného napr. permutáciou

)

2

,

4

,

1

,

3

(

=

P

.

Pre takéto rozmiestnenie objektov je hodnota kriteriálnej funkcie:

( )

86

6

.

7

4

.

0

6

.

2

3

.

3

3

.

1

5

.

4

34

24

23

14

13

12

=

+

+

+

+

+

=

+

+

+

+

+

=

DB

AB

AD

CB

CD

CA

d

w

d

w

d

w

d

w

d

w

d

w

P

f

Všetkými možnými výmenami dvojíc objektov vytvoríme nové (susedné permutácie) a pre každú

z nich vypočítame hodnotu kriteriálnej funkcie:

Najlepšia hodnota kriteriálnej funkcie v 1. iterácii zodpovedá permutácii (2,1,4,3),

s hodnotou 64. Preto táto permutácia sa stane východzou pre nasledujúcu iteráciu:

+

-> Nie je tu lepšie riešenie ako v 1. iterácii.

Najlepšia hodnota kriteriálnej funkcie je po druhej iterácii 68, čo nie je lepšie, ako hodnota

predchádzajúcej permutácie, takže výpočet končí. Výpočet je možné opakovať podľa potreby
niekoľkokrát pre ľubovoľné východzie permutácie.


3.4 Zovšeobecnený distribučný problém

DEFINÍCIA

Výrobca dodáva tovar n-odberateľom a má k dispozícii konečný počet m-miest pre postavenie

distribučného centra. Pre každé miesto sú určené fixné náklady fi spojené so zriadením
distribučného centra a prepravné náklady cij od i-teho distribučného centra j-temu odberateľovi.
Úlohou je vybrať miesta pre zriadenie distribučných centier tak, aby celkové náklady (fixné aj
prepravné) boli minimálne.

fi

(pre všetky i = 1 ... m) fixné náklady

cij

(pre všetky i = 1 ... n, j = 1 ... m)

METÓDY:

A) Celočíselné programovanie
B) Klasický programovací prístup (heuristika)
C) CLP

A) Celočíselné programovanie
yi (i=1, 2, ..., m) ->

1 ak i-te miesto bude vybrané pre zriadenie distribučného centra

->

0 ak i-te miesto nebude vybrané pre zriadenie distribučného centra

xi,j = {0, 1} (i = 1, 2, ..., m; j = 1, 2, ..., n)

->

1 ak i-te distribučné centrum bude dodávať j-temu odberateľovi

->

0 ak i-te distribučné centrum nebude dodávať j-temu odberateľovi

( )

(

)

(

)

n

j

m

i

y

x

n

j

x

MIN

x

c

y

f

y

x

f

i

ij

m

i

ij

m

i

n

j

ij

ij

m

i

i

i

,...,

2

,

1

;

,...,

2

,

1

,...,

2

,

1

1

,

1

!

1

1

1

=

=

≤

=

=

=

+

=

∑

∑∑

∑

=

=

=

=

Čo znamená 2

n+nm=2n(1+m) ohraničení. Pre úlohu reálneho rozmeru (napr. n=80, m=20)

nezvládnuteľný rozmer.

B) Klasický programovací prístup (heuristika)
Pre každý možný výber distribučných centier (tých je 2

m) je priradenie odberateľov triviálne

(každého odberateľa preradíme najbližšiemu distribučnému centru). Vývoj programu trval ca.
2 mesiace a pre pomerne malú zmenu zadania je nutné program úplne zmeniť.

C) CLP

Naprogramovanie tej istej úlohy trvalo ca. 2 týždne a bol omnoho flexibilnejší, t.j. napr. zmena

zadania si vyžiada jednoduchú zmenu programu. Výborný prototypovací nástroj.

Príklad:

Nesledujú tri verzie riešenia zovšeobecnenej distribučnej úlohy pre tri možné distribučné centrá

a piatich odberateľov v deklaratívnom jazyku systému VisualXpress.

1) Distribučné centrá (DC) bez obmedzenia kapacity distribučného centra, každému odberateľovi dodáva

práve jedno distribučné centrum.

Program:
LET
d=3 !miesta pre distribučné centra
o=5

!odberatelia

TABLES
vzdialenosti(d,o)
fixne_naklady(d)
dodavky(o)

DATA
vzdialenosti(1,1) = 5,3,8,4,2
vzdialenosti(2,1) = 9,6,1,3,5
vzdialenosti(3,1) = 2,4,6,8,3

fixne_naklady(1) = 300, 200, 400
dodavky(1) = 50, 70, 30, 80, 60

VARIABLES
y(d) !zriadiť, alebo nezriadiť distribučné centrum
x(d,o)

!bude dané DC dodávať danému odberateľovi (áno/nie)

CONSTRAINTS
odberatelia(j=1:o): SUM(i=1:d) x(i,j) = 1 !odberateľ odoberá len od 1 DC
dodavatelia(i=1:d, j=1:o): x(i,j) < y(i)
naklady: SUM(i=1:d) fixne_naklady(i)*y(i) + SUM(i=1:d, j=1:o) dodavky(j)*

vzdialenosti(i,j)*x(i,j)$

BOUNDS
y(i=1:d) .BV.
x(i=1:d, j=1:o) .BV.

2) Distribučné centrá (DC) s obmedzenou kapacitou distribučného centra, každému odberateľovi dodáva

práve jedno distribučné centrum.

Program:

LET
d=3

!miesta pre distribučné centra

o=5

!odberatelia

TABLES
vzdialenosti(d,o)
fixne_naklady(d)
kapacity(d)
dodavky(o)

DATA
vzdialenosti(1,1) = 5,3,8,4,2
vzdialenosti(2,1) = 9,6,1,3,5
vzdialenosti(3,1) = 2,4,6,8,3

fixne_naklady(1) = 300, 200, 400
kapacity(1) = 150, 130, 170
dodavky(1) = 50, 70, 30, 80, 60

VARIABLES
y(d) !zriadiť, alebo nezriadiť distribučné centrum
x(d,o)

!bude dané DC dodávať danému odberateľovi (áno/nie)

CONSTRAINTS
odberatelia(j=1:o): SUM(i=1:d) x(i,j) = 1 !odberateľ odoberá len od 1 DC
dodavatelia(i=1:d, j=1:o): x(i,j) < y(i)
kapacita(i=1:d): SUM(j=1:o) x(i,j)* dodavky(j) < kapacity(i)
naklady: SUM(i=1:d) fixne_naklady(i)*y(i) + SUM(i=1:d, j=1:o) dodavky(j)*

vzdialenosti(i,j)*x(i,j)$

BOUNDS

y(i=1:d) .BV.
x(i=1:d, j=1:o) .BV.

3) Distribučné centrá (DC) s obmedzenou kapacitou distribučného centra, jeden odberateľ môže odoberať

z viacerých distribučných centier.

Program:
LET
d=3

!miesta pre distribučné centra

o=5

!odberatelia

TABLES
vzdialenosti(d,o)
fixne_naklady(d)
kapacity(d)
dodavky(o)

DATA
vzdialenosti(1,1) = 5,3,8,4,2
vzdialenosti(2,1) = 9,6,1,3,5
vzdialenosti(3,1) = 2,4,6,8,3

fixne_naklady(1) = 300, 200, 400
kapacity(1) = 150, 130, 170
dodavky(1) = 50, 70, 30, 80, 60

VARIABLES
y(d) !zriadiť, alebo nezriadiť distribučné centrum (binárne)

x(d,o)

!koľko bude dané DC dodávať danému odberateľovi (reálne čísla)

CONSTRAINTS
odberatelia(j=1:o): SUM(i=1:d) x(i,j) = dodavky(j)
kapacita(i=1:d): SUM(j=1:o) x(i,j) < kapacity(i)
naklady: SUM(i=1:d) fixne_naklady(i)*y(i) + SUM(i=1:d, j=1:o)

vzdialenosti(i,j)*x(i,j)$

BOUNDS
y(i=1:d) .BV.