Optymalizacja w logistyce

Wykorzystanie wybranych metod optymalizacyjnych

Opracowali:

Ada Marszałkiewicz

Michał Witaszczyk

2 |

S t r o n a

SPIS TREŚCI

1.

PROGRAMOWANIE SIECIOWE ....................................................................................................... 3

1.1.

M

INIMALNE DRZEWO ROZPINAJĄCE

................................................................................................. 3

1.2.

N

AJKRÓTSZA DROGA

.................................................................................................................... 4

1.3.

MAKSYMALNY PRZEPŁYW

............................................................................................................... 5

2.

OPTYMALIZACJA ZADAŃ BAZY TRANSPORTOWEJ ......................................................................... 6

1.1.

A

LGORYTM DROGA DO NAJBLIŻSZEGO SĄSIADA

................................................................................... 6

1.2.

ALGORYTM SUKCESYWNE DOŁĄCZANIE WĘZŁÓW

................................................................................. 7

1.3.

A

LGORYTM OSZCZĘDNOŚCIOWE ŁĄCZENIE TRAS

................................................................................ 10

1.4.

A

L

G

ORYTM WĘGIERSKI

............................................................................................................... 12

3.

LOKALIZACJA MIEJSC PRODUKCJI I MAGAZYNÓW ....................................................................... 13

3 |

S t r o n a

1. PROGRAMOWANIE SIECIOWE

1.1.

MINIMALNE DRZEWO ROZPINAJĄCE

PROBLEM:

W ramach umowy międzynarodowej postanowiono zbudować rurociąg europejski

między stronami umowy. Przyłącze europejskie ma się znajdować w Grecji (punkt 1) i ma

połączyć ją z 9 innymi państwami. Aby zminimalizować koszt budowy opracowano plan

połączenia krajowych stacji przy pomocy metody minimalnego drzewa rozpinającego.

ROZWIĄZANIE GRAFICZNE:

4 |

S t r o n a

1.2.

NAJKRÓTSZA DROGA

PROBLEM:

Metoda najkrótsze drogi dokonano wyboru tras dostarczenia zamówień z magazynu

centralnego do odbiorców. Magazyn centralny znajduje się w Helsinkach (punkt 1), zaś

punktu odbiory oznaczono numerami 2-10.

ROZWIĄZANIE GRAFICZNE:

5 |

S t r o n a

Węzeł Droga

Odległość

2

1-2

789

3

1-3

1757

4

1-3-4

2005

5

1-2-5

1961

6

1-3-4-6

3580

7

1-2-7

1985

8

1-2-8

2879

9

1-2-7-9

3248

10

1-2-7-10 3788

1.3.

MAKSYMALNY PRZEPŁYW

PROBLEM:

Przedsiębiorstwo charterowe planuje przeloty z Helsinek (punkt 1) do Lizbony (punkt

10) z międzylądowaniami w wybranych stolicach państw europejskich. Niestety liczba

możliwych przelotów na poszczególnych drogach powietrznych jest ograniczona.

Przedsiębiorca planuje ustalić liczbę lotów poszczególnymi trasami tak, aby

zmaksymalizować ich liczbę.

ROZWIĄZANIE GRAFICZNE:

Droga

Przepływ

1-2-5-10

1

1-2-7-9-5-10

1

1-3-7-9-5-10

1

1-3-7-9-10

2

1-4-8-9-10

3

1-4-6-8-9-10

1

6 |

S t r o n a

2. OPTYMALIZACJA ZADAŃ BAZY TRANSPORTOWEJ

1.1.

ALGORYTM DROGA DO NAJBLIŻSZEGO SĄSIADA

PROBLEM:

Japoński turysta zaplanował podróż po wybranych stolicach państw europejskich w

taki sposób, aby zminimalizować odległość podróży między kolejnymi miastami. Miejscem

przylotu i odlotu jego samolotu z Japonii są Ateny. Trasę zwiedzania opracowano

z wykorzystaniem algorytmu droga do najbliższego sąsiada.

7 |

S t r o n a

Ateny Budapeszt Helsinki Kopenhaga Lizbona Londyn Madryt Paryż Rzym Wiedeń

0 Ateny

M

1575

3996

2877

4501

3213

3815

3069

2519

1823

1 Budapeszt

1575

M

2421

1302

3276

1732

2590

1511

1294

248

2 Helsinki

3996

2421

M

789

3886

1960

3347

1984

2878

1757

3 Kopenhaga

2877

1302

789

M

3098

1172

2259

1196

2090

1054

4 Lizbona

4501

3276

3886

3098

M

2166

645

1802

2667

2996

5 Londyn

3213

1732

1960

1172

2166

M

1627

391

1782

1422

6 Madryt

3815

2590

3347

2259

645

1627

M

1263

2022

2400

7 Paryż

3069

1511

1984

1196

1802

391

1263

M

1433

1263

8 Rzym

2519

1294

2878

2090

2667

1782

2022

1433

M

1145

9 Wiedeń

1823

248

1757

1054

2996

1422

2400

1263

1145

M

ROZWIĄZANIE:

Zgodnie z przyjętym algorytmem wyznaczono trasę H = [0,1,9,3,2,5,7,6,4,8,0], o łącznej

długości 13111 km.

1.2.

ALGORYTM SUKCESYWNE DOŁĄCZANIE WĘZŁÓW

Fabryka w Atenach wysyła produkty do innych stolic w Europie. Musimy znaleźć jak najkrótszą trasę

przez wszystkie wymienione stolice.

Ateny Budapeszt Helsinki Kopenhaga Lizbona Londyn Madryt Paryż Rzym Wiedeń

0 Ateny

M

1575

3996

2877

4501

3213

3815

3069

2519

1823

1 Budapeszt

1575

M

2421

1302

3276

1732

2590

1511

1294

248

2 Helsinki

3996

2421

M

789

3886

1960

3347

1984

2878

1757

3 Kopenhaga

2877

1302

789

M

3098

1172

2259

1196

2090

1054

4 Lizbona

4501

3276

3886

3098

M

2166

645

1802

2667

2996

5 Londyn

3213

1732

1960

1172

2166

M

1627

391

1782

1422

6 Madryt

3815

2590

3347

2259

645

1627

M

1263

2022

2400

7 Paryż

3069

1511

1984

1196

1802

391

1263

M

1433

1263

8 Rzym

2519

1294

2878

2090

2667

1782

2022

1433

M

1145

9 Wiedeń

1823

248

1757

1054

2996

1422

2400

1263

1145

M

H1={0,4,0}

1min [1575,3276]=1575

2min [3996,3886]=3886

3min [2877,3098]=2877

5min [3213,2166]=2166

6min [3815,645]=645

7min [3069,1802]=1802

8min [2519,2667]=2519

9min [1823,2996]=1823

S0 = 3996+3886-4501=3381

S4 = 3886+3996-4501=3381

H2={0,2,4,0}

1min [1575,2421,3276]=1575

3min [2877,789,3098]=789

5min [3213,1960,2166]=1960

6min [3815,3347,645]=645

7min [3069,1984,1802]=1802

8min [2519,2878,2667]=2667

9min [1823,1757,2996]=1757

S0=2519+2878-3996=1401

S2=2878+2667-2886=2659

S4=2667+2519-4501=385

H3={0,2,4,8,0}

1min [1575,2421,3276,1294]=1294

3min [2877,789,3098,2090]=789

5min [3213,1960,2166,1782]=1782

6min [3815,3347,645,2022]=645

7min [3069,1984,1802,1433]=1433

9min [1823,1757,2996,1145]=1145

S0=3213+1960-3996=1177

S2=1960+2166-2886=1240

S4=2166+1782-2667=1281

S8=1782+3213-2519=2476

H4={0,2,5,4,8,0}

1min [1575,2421,1732,3276,1294]=1294

3min [2877,789,1172,3098,2090]=789

6min [3815,3347,1627,645,2022]=645

7min [3069,1984,391,1802,1433]=391

9min [1823,1757,1422,2996,1145]=1145

S0=1575+2421-3996=0

S2=2421+1732-1960=2193

S5=1732+3276-2166=2838

S4=3276+1294-2667=1903

S8=1294+1575-2519=350

9 |

S t r o n a

H5={0,1,2,5,4,8,0}

3min [2877,1302,789,1172,3098,2090]=789

6min [3815,2590,3347,1627,645,2022]=645

7min [3069,1511,1984,391,1802,1433]=391

9min [1823,248,1757,1422,2996,1145]=248

S0=2877+1302-1575=2604

S1=1302+789-2421=-330

S2=789+1172-1960=1

S5=1172+3098-2166=2104

S4=3098+2090-2667=2521

S8=2090+2877-2519=2448

H6={0,1,3,2,5,4,8,0}

6min

[3815,2590,2259,3347,1627,645,2022]=645

7min

[3069,1511,1196,1984,391,1802,1433]=391

9min

[1823,248,1054,1757,1422,2996,1145]=248

S0=3815+2590-1575=4830

S1=2590+2259-1302=3547

S3=2259+3347-789=4817

S2=3347+1627-1960=3014

S5=1627+645-2166=106

S4=645+2022-2667=0

S8=2022+3815-2519=3318

H7={0,1,3,2,5,4,6,8,0}

7min

[3069,1511,1196,1984,391,1802,1263,1433]=391

9min

[1823,248,1054,1757,1422,2996,2400,1145]=248

S0=3069+1511-1575=3005

S1=1511+1196-1302=1405

S3=1196+1984-789=2391

S2=1984+391-1960=415

S5=391+1802-2166=27

S4=1802+1263-2667=398

S6=1263+1443-2022=684

S8=1433+3069-2519=1983

H8={0,1,3,2,5,7,4,6,8,0}

9min

[1823,248,1054,1757,1422,1263,2996,2400,1145]=

248

S0=1823+248-1575=496

S1=248+1054-1302=0

S3=1054+1757-2391=420

S2=1757+1422-1960=1219

S5=1422+1263-2166=519

S7=1263+2996-1802=2457

S4=2996+2400-2667=2729

S6=2400+1145-2022=1523

S8=1145+1823-2519=44

H9={0,1,9,3,2,5,7,4,6,8,0}

1.3.

ALGORYTM OSZCZĘDNOŚCIOWE ŁĄCZENIE TRAS

PROBLEM:

Firma spedycyjna otrzymała zlecenie przewiezienia zamówień z magazynu centralnego

(0) do odbiorców(1-9). Maksymalna trasa, jaką może pokonać jeden samochód to 10000 km,

natomiast jego maksymalna ładowność to 200 kartonów (o standardowej wielkości). Zgodnie

z przedstawionymi danymi oraz ograniczeniami zaplanowano ilość pojazdów potrzebnych do

wykonania zlecenia, ich trasę, łączną długość trasy oraz wielkość ładunku.

OGRANICZENIA:

Q

max

= 200 kartonów

T

max

= 10000 km

DANE:

0

1

2

3

4

5

6

7

8

9 b

i

0

x

1575 3996 2877 4501 3213 3815 3069 2519 1823

0

1

x

2421 1302 3276 1732 2590 1511 1294

248

46

2

x

789

3886 1960 3347 1984 2878 1757

56

3

x

3098 1172 2259 1196 2090 1054

17

4

x

2166

645

1802 2667 2996

98

5

x

1627

391

1782 1422

43

6

x

1263 2022 2400

24

7

x

1433 1263

59

8

x

1145

61

9

x

19

11 |

S t r o n a

MACIERZ WSPÓŁCZYNNIKÓW:

3150 3150 2800 3056 2800 3133 2800 3150

6084 4611 5249 4464 5081 3637 4062

4280 4918 4433 4750 3306 3646

5548 7671 5768 4353 3328

5401 5891 3950 3614

5621 4312 3238

4155 3629

3197

S

46

=7671 > S

23

=6084 > S

57

=5891 > S

47

=5768 > S

67

=5621 > S

45

=5548 > S

56

=5401 > S

25

=5249 > S

27

=5081 >

S

35

=4918 > S

37

=4750 > S

24

=4611 > S

26

=4464 > S

36

=4433 > S

48

=4353 > S

68

=4312 > S

34

=4280 > S

78

=4155 > S

29

=4062

> S

58

=3950 > S

39

=3646 > S

28

=3637 > S

79

=3629 > S

59

=3614 > S

49

=3328 > S

38

=3306 > S

69

=3238 > S

89

=3197 >

S

12

=S

13

=S

19

=3150 > S

17

=3133 > S

15

=3056 > S

14

=S

16

=S

18

=2800

OBLICZENIA:

1. Pojazd

S

i

H

i

Q

i

(kartony)

T

i

(km)

Dopuszczalna

S

46

[0,4,6,0]

122

8961

D

S

57

[0,5,7,4,6,0]

224

9866

N

S

47

[0,7,4,6,0]

181

9331

D

S

27

[0,7,4,6,0]

237

9331

N

S

37

[0,3,7,4,6,0]

198

10335

N

S

26

[0,7,4,6,2,0]

237

12859

N

S

36

[0,7,4,6,3,0]

198

11590

N

S

68

[0,7,4,6,8,0]

242

10057

N

S

78

[0,8,7,4,6,0]

242

10214

N

S

79

[0,9,7,4,6,0]

200

9348

D

2. Pojazd

S

i

H

i

Q

i

(kartony)

T

i

(km)

Dopuszczalna

S

23

[0,2,3,0]

73

7662

D

S

25

[0,5,2,3,0]

116

8839

D

S

58

[0,8,5,2,3,0]

177

9927

D

S

13

[0,8,5,2,3,1,0]

223

9927

N

S

18

[0,1,8,5,2,3,0]

223

10277

N

12 |

S t r o n a

3. Pojazd

S

i

H

i

Q

i

(kartony)

T

i

(km)

Dopuszczalna

[0,1,0]

46

3150

D

ROZWIĄZANIE:

Do wykonania zlecenia potrzebne są 3 samochody. Trasy wraz z ich łącznymi

długościami oraz wielkość ładunku kształtują się następująco:

Pojazd

Trasa

Ładunek
(kartony)

Łączna długość
trasy (km)

Samochód 1

[0,9,7,4,6,0]

200

9348

Samochód 2

[0,8,5,2,3,0]

177

9927

Samochód 3

[0,1,0]

46

3150

1.4.

ALGORYTM WĘGIERSKI

Cztery firmy złożyły oferty na wykonanie 4 poszczególnych zadań. Dane przedstawione zostały w

tabeli poniżej (w tyś. zł). Należy wybrać tak, koszt łączny był najmniejszy.

i\j

1

2

3

4

1

20

40

10

50

2

100

80

30

40

3

10

5

60

20

4

70

30

10

25

i\j

1

2

3

4

1

20-10

40-10

10-10

50-10

2

100-30

80-30

30-30

40-30

3

10-5

5-5

60-5

20-5

4

70-10

30-10

10-10

25-10

i\j

1

2

3

4

1

10-5

30-0

0-0

40-10

2

70-5

50-0

0-0

10-10

3

5-5

0-0

55-0

15-10

4

60-5

20-0

0-0

15-10

13 |

S t r o n a

20+5+10+40=75

Odpowiedź: Minimalny łączny koszt wykonania usług wynosi 75 tyś. zł.

3. LOKALIZACJA MIEJSC PRODUKCJI I MAGAZYNÓW

PROBLEM:

Amerykańska firma produkcyjna zdecydowała utworzyć swój oddział na terenie Europy.

Po zebraniu informacji na temat potencjalnych odbiorców postanowiła zlokalizować zakład

produkcyjny w możliwie korzystny sposób w stosunku do lokalizacji przyszłych kontrahentów.

Obliczeń dokonano według współrzędnych geograficznych, przy czym ponieważ punkty

te są położono zarówno na półkuli wschodniej, jak i zachodniej, przyjęto, że odległości

mierzone są od następujących współrzędnych: x

0

=0°N, y

0

=10°W

DANE:

Miasto

Szerokość

geograficzna

Długość
geograficzna

Odległość
od x

0

(°)

Odległość
od y

0

(°)

Zamówione
dostawy (t)

Ateny

38:00:00 °N

23:44:00 °E

38,0000

33,7333

63000

Budapeszt

47:30:00 °N

19:00:00 °E

47,5000

29,0000

133000

Helsinki

60:08:00 °N

25:00:00 °E

60,1333

35,0000

31500

Kopenhaga 55:43:00 °N

12:34:00 °E

55,7167

22,5667

115500

Lizbona

38:44:00 °N

09:08:00 °W

38,7333

0,8667

62300

Londyn

51:30:00 °N

00:10:00 °W

51,5000

9,8333

14700

Madryt

40:25:00 °N

03:43:00 °W

40,4167

6,2833

84000

i\j

1

2

3

4

1

5

30

0

30

2

65

50

0

0

3

0

0

55

5

4

55

20

0

5

i\j

1

2

3

4

1

5-5

30-5

0

30-5

2

65

50

0+5

0

3

0

0

55+5

5

4

55-5

20-5

0

5-5

i\j

1

2

3

4

1

0

25

0

25

2

65

50

5

0

3

0

0

65

5

4

45

15

0

0

i\j

1

2

3

4

1

1

0

0

0

2

0

0

0

1

3

0

1

0

0

4

0

0

1

0

14 |

S t r o n a

Paryż

48:52:00 °N

02:20:00 °E

48,8667

12,3333

40600

Rzym

41:53:00 °N

12:30:00 °E

41,8833

22,5000

150500

Wiedeń

48:13:00 °N

16:22:00 °E

48,2167

26,3667

121100

OBLICZENIA:

Filia

x

y

a

k

v

V

d(Mo)

K

0

38,0000 33,7333

63000

1,9

119700

119700

55,7333

6671280

1

47,5000 29,0000

133000

1,9

252700

372400

60,5

15288350

2

60,1333 35,0000

31500

1,9

59850

432250

79,1333

4736130

3

55,7167 22,5667

115500

1,9

219450

651700

62,2833

13668077,5

4

38,7333

0,8667

62300

1,9

118370

770070

33,8667

4008797,333

5

51,5000

9,8333

14700

1,9

27930

798000

45,3333

1266160

6

40,4167

6,2833

84000

1,9

159600

957600

30,7

4899720

7

48,8667 12,3333

40600

1,9

77140

1034740

45,2

3486728

8

41,8833 22,5000

150500

1,9

285950

1320690

48,3833

13835214,17

9

48,2167 26,3667

121100

1,9

230090

1264830

58,5833

13479439,17

81339896,17

V

0

= 632415

v*x

v*y

d(M2)

(v*x)/d

(v*y)/d

v/d

Ateny

4548600,00

4037880,00

36,79

123623,85

109743,28

3253,26

Budapeszt

12003250,00

7328300,00

41,76

287450,94

175496,37

6051,60

Helsinki

3598980,00

2094750,00

55,72

64587,04

37592,24

1074,06

Kopenhaga

12227022,50

4952255,00

46,83

261119,80

105760,16

4686,57

Lizbona

4584864,67

102587,33

28,87

158830,85

3553,87

4100,62

Londyn

1438395,00

274645,00

40,54

35477,43

6774,01

688,88

Madryt

6450500,00

1002820,00

29,55

218280,13

33934,68

5400,75

Paryż

3769574,67

951393,33

38,06

99033,00

24994,69

2026,60

Rzym

11976539,17

6433875,00

33,83

354071,04

190209,28

8453,75

Wiedeń

11094172,83

6066706,33

41,19

269314,37

147271,11

5585,50

71691898,83

33245212,00

1871788,46

835329,68

41321,58

15 |

S t r o n a

ROZWIĄZANIE:

x

y

M

0

40,4167°N 2,3333°E

M

1

38,6324°N 11,1996°E

M

2

46,2296°N 11,4377°E

M

3

45,2981°N 10,2153°E

M średnie

42,6442°N 8,7965°E

Zgodnie z przeprowadzaną analizą najdogodniejsza lokalizacja zakładu produkcyjnego

to punkt o współrzędnych: 42,6442°N 8,7965°E.

ROZWIĄZANIE GRAFICZNE:

0.0030

0.0035

0.0040

0.0045

0.0050

0.0055

0.0060

0.0065

0.0000 0.0005 0.0010 0.0015 0.0020 0.0025 0.0030

Filie

Możliwe lokalizacje centrum
dystrybucyjnego

Optymalna lokalizacja
centrum dystrybucyjnego

Nazwa pliku:

Marszałkiewicz,Witaszczyk

Katalog:

C:\Users\user\Desktop\optymalizacja\OwL dla Ady

Szablon:

C:\Users\user\AppData\Roaming\Microsoft\Szablony\Normal.dotm

Tytuł:

Optymalizacja w logistyce

Temat:

Wykorzystanie wybranych metod optymalizacyjnych

Autor:

DELL

Słowa kluczowe:

Komentarze:

Data utworzenia:

2012-06-07 23:23:00

Numer edycji:

92

Ostatnio zapisany:

2012-06-10 16:46:00

Ostatnio zapisany przez: Ada Marszałkiewicz
Całkowity czas edycji:

1 432 minut

Ostatnio drukowany:

2012-06-10 17:14:00

Po ostatnim całkowitym wydruku

Liczba stron:

15

Liczba wyrazów:

1 878 (około)

Liczba znaków:

11 269 (około)