Marszałkiewicz,Witaszczyk, gr1

Programowanie sieciowe

Minimalne drzewo rozpinające

Najktótsza droga

maksymalny przepływ

Optymalizacja zadań bazy transportowej

Algorytm droga do najbliższego sąsiada

PROBLEM:

Amerykań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 USA są Ateny. Trasę zwiedzania wykonana z wykorzystaniem algorytmu droga do najbliższego sąsiada.

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.

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

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=449

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

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:

Qmax = 200 kartonów

Tmax = 10000 km

DANE:

0 1 2 3 4 5 6 7 8 9 bi
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

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

S46=7671 > S23=6084 > S57=5891 > S47=5768 > S67=5621 > S45=5548 > S56=5401 > S25=5249 > S27=5081 > S35=4918 > S37=4750 > S24=4611 > S26=4464 > S36=4433 > S48=4353 > S68=4312 > S34=4280 > S78=4155 > S29=4062 > S58=3950 > S39=3646 > S28=3637 > S79=3629 > S59=3614 > S49=3328 > S38=3306 > S69=3238 > S89=3197 > S12=S13=S19=3150 > S17=3133 > S15=3056 > S14=S16=S18=2800

OBLICZENIA:

  1. Pojazd

Si Hi Qi (kartony) Ti (km) Dopuszczalna
S46 [0,4,6,0] 122 8961 D
S57 [0,5,7,4,6,0] 224 9866 N
S47 [0,7,4,6,0] 181 9331 D
S27 [0,7,4,6,0] 237 9331 N
S37 [0,3,7,4,6,0] 198 10335 N
S26 [0,7,4,6,2,0] 237 12859 N
S36 [0,7,4,6,3,0] 198 11590 N
S68 [0,7,4,6,8,0] 242 10057 N
S78 [0,8,7,4,6,0] 242 10214 N
S79 [0,9,7,4,6,0] 200 9348 D

  1. Pojazd

Si Hi Qi (kartony) Ti (km) Dopuszczalna
S23 [0,2,3,0] 73 7662 D
S25 [0,5,2,3,0] 116 8839 D
S58 [0,8,5,2,3,0] 177 9927 D
S13 [0,8,5,2,3,1,0] 223 9927 N
S18 [0,1,8,5,2,3,0] 223 10277 N

  1. Pojazd

Si Hi Qi (kartony) Ti (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

Alkorytm 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
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

20+5+10+40=75

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

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 wschodnie, jak i zachodniej, przyjęto, że odległości mierzone są os następujących współrzędnych: x0=0°N, y0=10°W

DANE:

Miasto   Szerokość geograficzna Długość geograficzna Odległość od x0 (°) Odległość od y0 (°) 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
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

V0 = 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

ROZWIĄZANIE:

x y
M0 40,4167°N 2,3333°E
M1 38,6324°N 11,1996°E
M2 46,2296°N 11,4377°E
M3 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:


Wyszukiwarka

Podobne podstrony:
Marszałkiewicz,Witaszczyk
Marszałkiewicz,Witaszczyk
Marszałkiewicz,Witaszczyk
marszalek szczepienia2
Marszalek
Kataliza Monograficzny gr1 wyniki
TECHNIKa 2006 zapis i przechowywanie informaji gr1, Do szkoły, GIM TECHNIKA
Hymn Wysp Marszala, 03. Hymny państwowe - teksty
FP gr1 2009, Finanse Publiczne
pytania gr1(temat 1)
sprawozdanie gr1
Wykłady Marszałkiewicz 12
gig z sem2 gr1
Pałac jaśniepana marszałka wielkopolskiego herbu platforma
marszalek streszczenie
Wniosek koncesje do marszałka, AGH, MGR GiGG, Specjalizujące Zagadnienia Prawne, koncesja - prezenta

więcej podobnych podstron