SPIS TREŚCI

1. Programowanie sieciowe 3

1.1. Minimalne drzewo rozpinające 3

1.2. Najktótsza droga 4

1.3. maksymalny przepływ 5

2. Optymalizacja zadań bazy transportowej 5

1.1. Algorytm droga do najbliższego sąsiada 5

1.2. algorytm sukcesywne dołączanie węzłów 6

1.3. Algorytm oszczędnościowe łączenie tras 6

1.4. Alkorytm węgierski 8

3. Lokalizacja miejsc produkcji i magazynów 8

Programowanie sieciowe

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:

Najktó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:

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

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ę.

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

ROZWIĄZANIE GRAFICZNE:

Optymalizacja zadań bazy transportowej

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.

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

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:

Q_max = 200 kartonów

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

S₄₆=7671 > S₂₃=6084 > S₅₇=5891 > S₄₇=5768 > S₆₇=5621 > S₄₅=5548 > S₅₆=5401 > S₂₅=5249 > S₂₇=5081 > S₃₅=4918 > S₃₇=4750 > S₂₄=4611 > S₂₆=4464 > S₃₆=4433 > S₄₈=4353 > S₆₈=4312 > S₃₄=4280 > S₇₈=4155 > S₂₉=4062 > S₅₈=3950 > S₃₉=3646 > S₂₈=3637 > S₇₉=3629 > S₅₉=3614 > S₄₉=3328 > S₃₈=3306 > S₆₉=3238 > S₈₉=3197 > S₁₂=S₁₃=S₁₉=3150 > S₁₇=3133 > S₁₅=3056 > S₁₄=S₁₆=S₁₈=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

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	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	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	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 wschodniej, jak i zachodniej, przyjęto, że odległości mierzone są od następujących współrzędnych: x₀=0°N, y₀=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

V₀ = 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: