Jadczak R Badania operacyjne, Wykład 2 Optymalizacja w logistyce

background image

OPTYMALIZACJA W

LOGISTYCE

Optymalizacja zada

ń

bazy

transportowej ( cz

ęść

2 )

Opracowano na podstawie : Stanisław Krawczyk, Metody ilo

ś

ciowe w logistyce (

przedsi

ę

biorstwa ),

Wydawnictwo C. H. Beck, Warszawa 2001

background image

Problem komiwoja

ż

era

Sformułowanie problemu

Zadanie komiwoja

ż

era jest znane od kiedy kupcy zacz

ę

li dostarcza

ć

produkty

klientom.

Podstawow

ą

wersj

ę

problemu komiwoja

ż

era mo

ż

na przedstawi

ć

w dwóch

zdaniach:

1. Komiwoja

ż

er pragnie odwiedzi

ć

pewn

ą

liczb

ę

klientów w ró

ż

nych

miejscowo

ś

ciach i po zako

ń

czeniu odwiedzin wróci

ć

do domu.

2. Jak

ą

drog

ę

powinien wybra

ć

( w jakiej kolejno

ś

ci powinien odwiedza

ć

klientów) aby przebyta przez niego droga była mo

ż

liwie najkrótsza?

background image

Pierwsze reguły wyznaczania trasy zostały opracowane na podstawie do

ś

wiadcze

ń

praktycznych ju

ż

w połowie XIX wieku przez komiwoja

ż

erów w USA. Jednak

dopiero formalne uj

ę

cie matematyczne pozwoliło odkry

ć

,

ż

e to niby proste

zadanie obejmuje bardzo szerok

ą

klas

ę

przypadków, z których tylko niektóre

mo

ż

na rozwi

ą

za

ć

dokładnie.

Zało

ż

enia:

1. Ka

ż

dego klienta mo

ż

na identyfikowa

ć

przez podanie miejscowo

ś

ci (w

ę

zła w

grafie), w której zamieszkuje ( w jednej miejscowo

ś

ci znajduje si

ę

jeden klient ).

2. Mi

ę

dzy miejscowo

ś

ciami istniej

ą

poł

ą

czenia pozwalaj

ą

ce na przemieszczanie w

obu kierunkach ( kraw

ę

dzie grafu ).

3. Ka

ż

dej kraw

ę

dzi przyporz

ą

dkowana jest liczba okre

ś

laj

ą

ca uogólnion

ą

odległo

ść

.

4. Wyró

ż

nione miejscowo

ś

ci oraz potencjalne trasy przejazdu mo

ż

na przedstawi

ć

za pomoc

ą

grafu

G=[ V , E , c ]

, nieskierowanego, spójnego, o

n

w

ę

złach, w

którym liczby przyporz

ą

dkowane kraw

ę

dziom s

ą

nieujemne –

c

ij

= c

ji

0

5. Dla dowolnych trzech w

ę

złów

i,j,k

powinna by

ć

spełniona nierówno

ść

:

c

ik

c

ij

+

c

jk

6.

Dla dowolnych dwóch miejscowo

ś

ci nie mog

ą

wyst

ę

powa

ć

poł

ą

czenia przez

inne miejscowo

ś

ci.

7. Wyró

ż

niamy jeden w

ę

zeł odpowiadaj

ą

cy miejscu startu komiwoja

ż

era i

przyjmujemy,

ż

e jego trasa powinna ko

ń

czy

ć

si

ę

powrotem do tego w

ę

zła.

background image

Ka

ż

d

ą

tras

ę

spełniaj

ą

ca te warunki nazywamy tras

ą

okr

ęż

n

ą

komiwoja

ż

era,

która jest optymalna, gdy ł

ą

czna jej długo

ść

jest minimalna. Ka

ż

da z

miejscowo

ś

ci ( z wyj

ą

tkiem startowej ) musi wyst

ą

pi

ć

na niej tylko raz. W

teorii grafów tras

ę

tego typu nazywa si

ę

cyklem Hamiltona. Je

ż

eli nie

wymaga si

ę

odwiedzenia wszystkich miejscowo

ś

ci mówimy o cyklu

skróconym.

1

1

2

3

4

5

6

background image

Poszukiwany cykl Hamiltona oznaczymy krótko symbolem

H

. Aby móc

zapisa

ć

,

ż

e pewna kraw

ę

d

ź

nale

ż

y do tego cyklu, wprowadzimy zmienne

binarne

x

ij

, i,j= 1…, n

.

Poniewa

ż

ka

ż

da miejscowo

ść

mo

ż

e tylko raz wyst

ą

pi

ć

w trasie, wi

ę

c ka

ż

dy

w

ę

zeł

i

mo

ż

e tylko raz wyst

ą

pi

ć

jako w

ę

zeł pocz

ą

tkowy kraw

ę

dzi :

Ka

ż

dy w

ę

zeł mo

ż

e by

ć

równie

ż

tylko raz w

ę

złem ko

ń

cowym kraw

ę

dzi, co

prowadzi do układu ogranicze

ń

:

[ ]

=

przypadku

przeciwnym

w

0,

H

cyklu

j

i,

droga

gdy

,

1

ij

x

n.

1,...,

j

,

1

1

=

=

=

n

i

ij

x

n.

1,...,

i

,

1

1

=

=

=

n

j

ij

x

background image

Minimalizacja trasy mo

ż

e by

ć

uj

ę

ta w formie funkcji kryterium:

Wprowadzamy sztuczne zało

ż

enie, na mocy którego, gdy mi

ę

dzy dwoma

w

ę

złami

p

i

r

nie istnieje poł

ą

czenie, to przyjmujemy,

ż

e s

ą

one oddalone

niesko

ń

czenie daleko, a wi

ę

c

c

pr

=

, oraz równie

ż

c

ii

=

Próba tak sformułowanego zadania ko

ń

czy si

ę

jednak bardzo cz

ę

sto

wskazaniem cykli skróconych, których przyj

ę

te ograniczenia niestety nie

wykluczaj

ą

. Aby do tego nie dopu

ś

ci

ć

do zadania nale

ż

y wprowadzi

ć

dodatkowe ograniczenia , które czyni

ą

zadanie trudnym do praktycznego

rozwi

ą

zania. W literaturze mo

ż

na spotka

ć

ż

ne wersje ogranicze

ń

uniemo

ż

liwiaj

ą

cych powstawanie cykli skróconych. Cz

ę

sto spotykan

ą

jest

nast

ę

puj

ą

ca:

1. Rozpatrujemy wszystkie

k

elementowe permutacje w

ę

złów

[ i

1

, i

2

,…, i

k

]

,

przy czym

• Gdy liczba w

ę

złów jest parzysta:

k = 2,3,…,

min

1

1

=

∑∑

=

=

ij

n

i

n

j

ij

x

c

z

2

n

background image

Gdy liczba w

ę

złów n jest nieparzysta:

k = 2,3,…,

2. Dla ka

ż

dego

k

tworzymy układ ogranicze

ń

:

Nale

ż

y teraz wzi

ąć

pod uwag

ę

,

ż

e dla ka

ż

dego

k

otrzymujemy

ogranicze

ń

. Dla n=6 otrzymamy 55 ogranicze

ń

, ale ich liczba

ro

ś

nie bardzo szybko dla n=14 wynosi prawie 3 miliony, co czyni zadanie

niemo

ż

liwym do rozwi

ą

zania. Z tego wzgl

ę

du w praktyce najcz

ęś

ciej

wykorzystywane s

ą

algorytmy heurystyczne.

2

1

n

1

...

1

3

2

2

1

+

+

k

x

x

x

i

i

i

i

i

i

k

( )

!

1





k

k

n

background image

Algorytm droga do najbli

ż

szego s

ą

siada

Zało

ż

enia startowe

Startujemy w

ęź

le

a

. Symbolem

z

oznaczamy długo

ść

drogi okr

ęż

nej.

Przyjmujemy:

k

1

:= a, z := 0.

Iteracje
Numery iteracji b

ę

dziemy kojarzy

ć

z liczb

ą

odwiedzanych miejscowo

ś

ci,

dlatego.

rozpatrujemy iteracje j = 2,3,…,n.

Krok 1

Wskazujemy w

ę

zeł

k

j

, dla którego

Czyli wskazujemy w

ę

zeł, który nie jest zakwalifikowany do drogi i le

ż

y najbli

ż

ej

ostatniego z ju

ż

uwzgl

ę

dnionych w drodze.

Krok 2

Tworzymy ci

ą

g

[ k1 ,…, kj ].

{ }

1

1

,

,...,

czym

przy

,

min

,

1

1

=

j

k

k

k

k

k

i

c

c

i

j

j

j

background image

Krok 3

Przyjmujemy:

Po n iteracjach do ci

ą

gu

[ k

1

,…, k

n-1

, k

n

]

doł

ą

czamy w

ę

zeł startowy

k

1

, tworz

ą

c

drog

ę

okr

ęż

n

ą

H = [ k

1

,…, k

n-1

, k

n

, k

1

]

, której długo

ść

wynosi:

j

j

k

k

c

z

z

,

1

+

=

1

,k

c

z

z

n

k

+

=

background image

Przykład

Post

ę

puj

ą

c zgodnie z zasadami wyznaczania najbli

ż

szego s

ą

siada

wyznaczamy kolejno

w wierszach zaczynaj

ą

c od wiersza 1:

W wierszu 1 : w

ę

zeł 3 – czas 78

W wierszu 3 : w

ę

zeł 5 – czas 66

W wierszu 5 : w

ę

zeł 4 – czas 288 ,nie mo

ż

na wybra

ć

2 bo nie ma z niego

dojazdu do 4 , ale z 4 nie mo

ż

liwy jest tak

ż

e dojazd do 2. Nale

ż

y

post

ę

powanie zacz

ąć

od pocz

ą

tku bior

ą

c pod uwag

ę

,

ż

e najgorszy dojazd

jest do 2 i 4

W wierszu 1 : w

ę

zeł 3 – czas 78

W wierszu 3 : w

ę

zeł 2 – czas 81

1

1

2

3

4

5

Wrocław

1

83

78

198

131

Wałbrzych

2

83

81

63

Legnica

3

78

81

277

66

Pozna

ń

4

198

277

288

Jelenia
Góra

5

131

63

66

288

background image

W wierszu 2 : w

ę

zeł 5 – czas 63

W wierszu 5 : w

ę

zeł 4 - czas 288

W wierszu 4 : w

ę

zeł 1 - czas 198

Ł

ą

czny czas przejazdu 708

Drugi wariant drogi okr

ęż

nej

W wierszu 1 : w

ę

zeł 3 – czas 78

W wierszu 3 : w

ę

zeł 4 – czas 277

W wierszu 4 : w

ę

zeł 5 - czas 288

W wierszu 5 : w

ę

zeł 2 - czas 63

W wierszu 2 : w

ę

zeł 1 – czas 83

Ł

ą

czny czas przejazdu 789

Trzeci wariant drogi okr

ęż

nej:

W wierszu 1 : w

ę

zeł 2 – czas 83

W wierszu 2 : w

ę

zeł 5 – czas 63

W wierszu 5 : w

ę

zeł 3 - czas 66

W wierszu 3: w

ę

zeł 4 - czas 277

W wierszu 4 : w

ę

zeł 1 – czas 198

Ł

ą

czny czas przejazdu 687

background image

5

3

2

4

1

Pozna

ń

Wrocław

Wałbrzych

Legnica

Jelenia Góra

background image

Jak wida

ć

algorytmu nie da si

ę

zawsze zastosowa

ć

nie

odchodz

ą

c od wcze

ś

niej przedstawionych reguł

post

ę

powania. Wszystko zale

ż

y od konfiguracji

poł

ą

cze

ń

. Dlatego nale

ż

y pami

ę

ta

ć

,

ż

e stosuj

ą

c

algorytmy heurystyczne nie zawsze otrzymujemy

rozwi

ą

zanie optymalne ale jedynie dopuszczalne.

background image

Algorytm sukcesywne doł

ą

czanie w

ę

złów.

Dla z góry zadanego w

ę

zła startowego

a

nale

ż

y ju

ż

na starcie wybra

ć

inny

w

ę

zeł

b

i

utworzy

ć

pocz

ą

tkow

ą

tras

ę

z

a

do

b

i powrotem:

[a,b,a].

W trakcie

post

ę

powania

b

ę

dziemy sukcesywnie modyfikowa

ć

t

ę

drog

ę

przez doł

ą

czanie nowych

w

ę

złów.

Wybór nowego w

ę

zła nie jest jednoznacznie okre

ś

lony, ale korzystnie jest

stosowa

ć

nast

ę

puj

ą

ca reguł

ę

:

Najmniejsza z odległo

ś

ci doł

ą

czanego w

ę

zła do wcze

ś

niej okre

ś

lonej drogi

powinna.

by

ć

mo

ż

liwie najwi

ę

ksza. Przyjmujemy zatem:

a

– w

ę

zeł startowy,

b

– w

ę

zeł najbardziej oddalony od a,

z

– okre

ś

lona długo

ść

okr

ęż

nej drogi; w iteracja po

ś

rednich – drogi

cz

ęś

ciowej,

H

– cykl w

ę

złów tworz

ą

cych drog

ę

okr

ęż

n

ą

; w iteracjach po

ś

rednich jest to

droga cz

ęś

ciowa

background image

Zało

ż

enia startowe

Przyjmujemy:

Iteracje

Numery iteracji kojarzy

ć

b

ę

dziemy z liczb

ą

odwiedzonych miejscowo

ś

ci,

dlatego.

rozpatrujemy iteracje j = 3,…,n. Przyjmijmy,

ż

e w iteracji (j-1) otrzymali

ś

my

cz

ęś

ciow

ą

.

drog

ę

okr

ęż

n

ą

:

o długo

ś

ci

z

.

Ze wzgl

ę

du na stosowane dalej wzory ostatni z w

ę

złów jest oznaczony przez

k

j

, a w

rzeczywisto

ś

ci jest nim w

ę

zeł

k

1

.

[

]

1

2

2

1

k

1

2

1

2

1

c

z

,

,

,

k

H

b,

,

k

k

k

c

k

k

k

a

k

+

=

=

=

=

[

]

j

j

k

k

k

k

H

,

,...,

,

1

2

1

=

background image

W ka

ż

dej iteracji nale

ż

y wskaza

ć

, który z nie uwzgl

ę

dnionych jeszcze w

ę

złów

powinien

by

ć

doł

ą

czony i rozstrzygn

ąć

, mi

ę

dzy którymi w

ę

złami istniej

ą

cej trasy

powinien by

ć

Doł

ą

czony.

Krok 1

Dla ka

ż

dego w

ę

zła

p

k

1

, k

2

,…, k

j-1

obliczamy :

Krok 2

Jako w

ę

zeł

i

, który ma by

ć

doł

ą

czony do drogi wybieramy ten, dla którego:

(

)

p

j

k

p

k

p

k

p

c

c

c

d

1

2

1

,...,

,

min

=

p

p

i

d

d

max

=

background image

Krok 3

Maj

ą

c wybrany w

ę

zeł i musimy rozstrzygn

ąć

, mi

ę

dzy które w

ę

zły drogi H

wstawi

ć

ten.

w

ę

zeł. W nowej drodze pojawiaj

ą

si

ę

kraw

ę

dzie

[k

t

, i]

oraz

[i , k

t+1

]

natomiast

wypada z

niej kraw

ę

d

ź

[k

t

, k

t+1

]

k

k

1

k

t

K

t+1

k

1

i

C

i

k

t+1

Ck

t

i

Ck

t

k

t+1

background image

Doł

ą

czenie nowych odcinków drogi powoduje zmian

ę

jej długo

ś

ci. Wielko

ść

tej

zmiany

oznaczamy symbolem

s

t

i obliczamy nast

ę

puj

ą

co :

Jeste

ś

my zainteresowani takim rozwi

ą

zaniem, które b

ę

dzie powodowało

najmniejszy .

przyrost długo

ś

ci drogi, dlatego post

ę

pujemy zgodnie z nast

ę

puj

ą

cym

kryterium:

Krok 4

Tworzymy now

ą

cz

ęś

ciow

ą

tras

ę

1

1

+

+

+

=

t

t

t

t

k

k

ik

i

k

t

c

c

c

s

(

)

1

1

1

min

1

,...,

1

+

+

+

+

=

+

=

=

t

t

h

h

t

t

k

k

ik

i

k

j

h

ik

i

k

t

c

c

c

c

c

s

[

]

j

t

t

k

k

i

k

k

H

,...,

,

,

,...,

1

1

+

=

background image

Krok 5

Sprawdzamy czy zostały uwzgl

ę

dnione wszystkie w

ę

zły. Je

ż

eli nie to

przechodzimy

do nast

ę

pnej iteracji. Je

ż

eli tak wyznaczanie trasy komiwoja

ż

era ko

ń

czy si

ę

.

Otrzymujemy drog

ę

okr

ęż

n

ą

, która jest cyklem Hamiltona

[

]

1

1

,

,...,

k

k

k

H

n

=

background image

Przykład

Przyjmujemy jako

a

w

ę

zeł

1

, jako

b

nale

ż

y przyj

ąć

w

ę

zeł

4

, do którego czas

przejazdu . jest najdłu

ż

szy i wynosi 198 min. Otrzymujemy drog

ę

H

1

= [1,4,1]

, z=198 + 198 = 396

Iteracja 3

Wyznaczamy w

ę

zeł, który doł

ą

czymy do drogi H

1:

p=2 r

21

= min { 83 , 10000 } = 83

P=3 r

31

= min { 78 , 277 } = 78

1

1

2

3

4

5

Wrocław

1

83

78

198

131

Wałbrzyc
h

2

83

81

63

Legnica

3

78

81

277

66

Pozna

ń

4

198

277

288

Jelenia
Góra

5

131

63

66

288

background image

P=5 r

51

= min { 131, 288 } = 131

Do drogi H

1

doł

ą

czamy w

ę

zeł 5. Musimy teraz rozstrzygn

ąć

na które miejsce w

ty celu.

obliczmy wska

ź

niki s

t

:

s

1

= c

15

+ c

54

– c

14

= 131 + 288 – 198 = 221

s

4

= c

45

+ c

51

- c

41

= 288 + 131 – 198 = 221

Wybór jest dowolny, załó

ż

my,

ż

e wybieramy s

1

co oznacza,

ż

e tworzymy now

ą

okr

ęż

n

ą

.

tras

ę

H

2

= [1, 5, 4, 1 ]

Iteracja 4

P = 2 r

22

= min { c

21

, c

25

, c

24

} =min {83 , 63 , 10000 } = 63

P = 3 r

32

= min { c

31

, c

35

, c

34

} = min {78 , 66 , 277 } = 66

Do drogi H

2

doł

ą

czamy w

ę

zeł 3.

background image

Musimy teraz rozstrzygn

ąć

na które miejsce w ty celu obliczmy wska

ź

niki s

t

:

s

1

= c

13

+ c

35

– c

15

= 78 + 66 – 131 = 13

s

5

= c

53

+ c

34

- c

54

= 66 + 277 – 288 = 55

S

4

= c

43

+ c

31

– c

41

= 277 + 78 – 198 = 157

wybieramy s

1

co oznacza,

ż

e w

ę

zeł 3 doł

ą

czamy do drogi H

2

po w

ęź

le 1.

Otrzymujemy

tras

ę

H

3

= [1 , 3 , 5 , 4 , 1] z = 78 + 66 + 288 + 198 = 630

Iteracja 5

P = 2 r

23

= min {83 , 273 , 81 , 63 } = 63

Musimy teraz rozstrzygn

ąć

na które miejsce wprowadzimy w

ę

zeł 2 w ty celu

obliczmy.

wska

ź

niki s

t

:

s

1

= c

12

+ c

23

– c

13

= 83 + 81 – 78 = 86

s

3

= c

32

+ c

24

- c

34

= 81 + 63 – 66 = 78

S

4

= c

42

+ c

21

– c

41

= 10000 + 83 – 198 = 9885

S

5

= c

52

+ c

24

- c

54

= 63 + 10000 - 288 = 9777

wybieramy s

1

co oznacza,

ż

e w

ę

zeł 2 doł

ą

czamy do drogi H

3

po w

ęź

le 1.

Otrzymujemy

tras

ę

H

3

= [1 , 3 , 2 , 5 , 4 , 1] z = 78 + 81 + 63 + 288 + 198 = 708

background image

1

4

2

5

3


Wyszukiwarka

Podobne podstrony:
Jadczak R Badania operacyjne, Wykład 4 Optymalizacja w logistyce
Jadczak R Badania operacyjne, Wykład 1 Optymalizacja w logistyce
Jadczak R - Badania operacyjne Wykład 3, Optymalizacja w logistyce
Jadczak R Badania operacyjne, Wykład 3 Optymalizacja w logistyce
Jadczak R Badania operacyjne, Wykład 4 Optymalizacja w logistyce
Jadczak R Badania operacyjne, wyklad teoria podejmowania decyzji
Jadczak R, Badania operacyjne wyklad teoria podejmowania decyzji
Jadczak R - Badania operacyjne Wykład 3, programowanie całkowitoliczbowe
Jadczak R Badania operacyjne, Wykład 5 zarządzanie projektami (LESS)
Jadczak R - Badania operacyjne Wykład 5, zarządzanie projektami (LESS)
Jadczak R - Badania operacyjne Wykład 2, liniowe modele decyzyjne
Jadczak R Badania operacyjne, Wykład 2 liniowe modele decyzyjne
Jadczak R - Badania operacyjne Wykład 4, zarządzanie projektami (CPM, PERT)
Jadczak R Badania operacyjne, wyklad teoria masowej obslugi
Jadczak R Badania operacyjne, Wykład 1 teoria podejmowania decyzji
Jadczak R Badania operacyjne, wyklad zagadnienia transportowe i przydziału
Jadczak R Badania operacyjne, Wykład 3 programowanie całkowitoliczbowe
Badania operacyjne wyklad 2 id Nieznany

więcej podobnych podstron