---

Overview

Zadanie
Wzor
Zadania

---

Sheet 1: Zadanie

Ćwiczenie 6. Elementy planowania sieciowego i dynamicznego.

1. Wprowadzić dane w arkusz Excel’a i wytłumaczyć ich sens.

2. Na podstawie analizy treści zadania zapisać ekonomiczno-matematyczny model zadania.

3. Narysować graf. Sprawdzić, czy jest on siecią.

4. Uporządkować graf metodą Fulkersona.

5. Metodami programowania dynamicznego znaleźć wartość funkcji celu i

optymalną ścieżkę między punktami 1 a 10, a również 2 a 10, 3 a 10, ... , 9 a 10.

6. Znajdż optymistycną, pesymistyczną, oczekiwaną wartości funkcji celu.

7. Oblicz prawdopodobieństwo że funkcja celu przyjmuje podaną wartość.

8. Zrobić wnioski.

---

Sheet 2: Wzor

Zadanie. Dla dziesięciu miast 1,2, ... 9, 10 jest znany czas przejazdu tij między odpowiednie miastami i i j.
Która droga z miasta 1 do miasta 10 będzie najkrótsza?
Rozwiązanie.
1. Narysujemy graf sieci dróg. Dla tego połączmy lukami (strzałkami) wierzchołki (miasta), między którymi istnieją drogi.
2. Uporządkujemy jego metodą Fulkerson'a. Dla tego wyznaczymy wierzchołki, z których tylko wychodzą łuki. Z wykresu widać,
że to będzie wierzchołek 1. On tworzy I-ą grupę wierzchołków. Dalej śkreślamy z grafu wierzchołek 1 i luki, które zaczynają się w
wierzchołku 1 (luki 1-2, 1-3, 1-4, onie zaznaczony na wykresie grubszymi liniami). W pozostałym grafie z wierzchołków 2 i 3
również tylko wychodzą luki. Wierzchołki 2 i 3 odniosą się do II-ej grupy. Jeżeli kontynuować ten proces przekształcenia grafu,
to będziemy mieć 9 grup wierzchołków, które narysowany na wykresie niżej.
3. Wykorzystamy metody programowania dynamicznego dla znalezienia minimalnej odległości między punktami 1 a 10, i również 2 a 10, 3 a 10, ... , 9 a 10.
Zaczynamy od ostatniego etapu XIX. Liczymy, że odległość z miasta 10 do miasta 10 równa się 0. Na przedostatnim etapie VIII (wierzchołek 9) z
wierzchołka 9 wychodzi tylko jedna luka. To oznacza, że minimalna odległość między miastami 9 i 10 równa się 2 jednostki (0+2=2).
Komórkę z optymalnym marszrutem przejazdu zaznaczamy kolorem.
Na VII etapie z wierzchołka 8 wychodzi 2 luki. Jeżeli będziemy jechać kierunkiem 8-10, to odległość będzie 0+5=5 jednostek, jeżeli trasą 8-9-10
– wtedy 0+2+6=8 jednostek. Porównując trasy 8-10 i 8-9-10 wyberamy minimalną odległość z 8 do 10: to jest 5 jednostek i odpowiada kierunku 8-10.
Dalej potrzebnie zrobić optymalizację dla pozostałych etapów.
4. Obliczymy czas optymistyczny dla ścieżki 1-2-5-8-10: topt=10 i ścieżki 1-3-7-10: topt=12. Dla ścieżki 2-5-8-10: topt=9
Obliczmy czas pesymistyczny dla ścieżki 1-2-5-8-10: tpes=24 i ścieżki 1-3-7-10: tpes=19. Dla ścieżki 2-5-8-10: tpes=20 Czas oczekiwany
dla ścieżki 1-2-5-8-10: toczekiwane = 14,33 dla ścieżki 1-3-7-10 : toczekiwane = 13,83 dla ścieżki 2-5-8-10: toczekiwane = 12,17.
5. Na podstawie optymalizacji można zrobić następujące wnioski:
5.1. Optymalny kierunek z 1 w 10: 1-2-5-8-10 lub 1-3-7-10. Czas przejazdu 13 jednostek.
5.2. Optymalne kierunki: z 2 w 10: 2-5-8-10 (11); z 3 w 10: 3-7-10 (8); z 4 w 10: 4-6-7-10 (13); z 5 w 10: 5-8-10 (10); z 6 w 10: 6-7-10 (8); z 7 w 10: 7-10 (5);
z 8 w 10: 8-10 (5); z 9 w 10: 9-10 (2).
5.3. Oczekiwany czas przejazdu od 1 do 10 wynosi 13,83 jednostek czasowych, od 2 do 10 – 12,17 jednostek.
6. Korzystając z empirycznych wzorów dla wartości oczekiwanej i wariancji i przypuszczając że dla czasu przejazdu występuję rozkład normalny,
obliczamy parametry rozkładu i badamy prawdopodobieństwa przejazdu od p.1 do p.10 w określionych granicach czasu.
	Zadanie.				1	Narysujemy graf sieci dróg.
		tpl	topt	tpes
	t12	2	1	4
	t13	5	4	7
	t14	9	7	11
	t24	4	2	8
	t25	1	1	5																			Solver
	t26	9	8	9
	t35	5	5	5
	t36	9	8	11	2	Uporządkujemy graf metodą Fulkersona.																			xij - zmienne decyzyjne binarne
	t37	3	3	4		I	II		III		IV	V		VI	VII		VIII			x12	1	t12	2		tij - obciążenia grafu
	t45	5	3	8																x13	0	t13	5		Funkcja celu
	t46	5	2	8																x14	0	t14	9		Z=	13,0000000222407
	t56	4	3	5																x24	0	t24	4		Ograniczenia
	t58	5	3	7																x25	1	t25	1
	t67	3	3	6																x26	0	t26	9		1:	1	=	1
	t68	5	4	6																x35	0	t35	5		2:	1	=	1
	t78	9	7	13																x36	0	t36	9		3:	0	=	0
	t79	8	7	15																x37	0	t37	3		4:	0	=	0
	t710	5	5	8																x45	0	t45	5		5:	1	=	1
	t89	6	5	8																x46	0	t46	5		6:	0	=	0
	t810	5	5	8																x56	0	t56	4		7:	0	=	0
	t910	2	1	6																x58	1	t58	5		8:	1	=	1
						3	Metodami programowania dynamicznego znajdziemy minimalny czas przejazdu													x67	0	t67	3		9:	0	=	0
							1	2	3	4	5	6	7	8	9	10				x68	0	t68	5		10:	1	=	1
																				x78	0	t78	9
							1_2	2_4	3_5	4_5	5_6	6_7	7_8	8_9	9_10	10_10				x79	0	t79	8
							13	17	15	15	12	8	14	8	2	0				x710	0	t710	5
							1_3	2_5	3_6	4_6	5_8	6_8	7_9	8_10						x89	0	t89	6
							13	11	17	13	10	10	10	5						x810	1	t810	5
							1_4	2_6	3_7				7_10							x910	0	t910	2
							22	17	8				5
						4, 5	Obliczamy optymistyczny, pesymistyczny, oczekiwany czas przejazdu
						trasa	1_2	2_5			5_8			8_10		10_10
						topt	10	9			8			5		0	toczekiwane=	14,33
						tpes	24	20			15			8		0
						trasa	1_3		3_7				7_10			10_10
						topt	12		8				5			0	toczekiwane=	13,83
						tpes	19		12				8			0
						trasa		2_5			5_8			8_10		10_10
						topt		9			8			5		0	toczekiwane=	12,17
						tpes		20			15			8		0
						6	Oblicz prawdopodobieństwo że czas przejazdu będzie zawierać się: a) między topt a 2topt; b) między 0,9toczek a 1,1 toczek.
						Przypuszczając, że dla badania losowości czasu przejazdu można stosować rozkład normalny,
						obliczymy parametry rozkładu
															- gęstość prawdopodobieństwa dla rozkładu normalnego
																						t	f(t)
						Korzystniejszy (minimalny czas) kierunek jest 1-3-7-10. Dla tego															1	9,16666666666667	0,000114711622084
						toczekiwane=		13,83													2	9,45833333333333	0,000302224870601
						Obliczymy wariancje s2 według wzoru:															3	9,75	0,000748013738611
																					4	10,0416666666667	0,001739184049114
																					5	10,3333333333333	0,003798727210233
						Wtedy	s2 =	1,36111111111111													6	10,625	0,007794482144221
							s =	1,16666666666667													7	10,9166666666667	0,015024257565916
						W naszym przypadku															8	11,2083333333333	0,027205415859143
																					9	11,5	0,046277971297018
						Obliczamy:															10	11,7916666666667	0,073951987565581
						a) prawdopodobieństwo że czas przejazdu będzie między t=12 a t=15;															11	12,0833333333333	0,111015081999335
						topt =	12	2topt =	15		p =	0,783303179199215	(narysowane na wykresie)								12	12,375	0,156556358904875
						b) prawdopodobieństwo że czas przejazdu będzie między 0,9toczek a 1,1toczek;															13	12,6666666666667	0,207403478159265
						0,9toczek =	12,45	2topt =	15,2166666666667		p =	0,764264849023151									14	12,9583333333333	0,258117798989831
						7. Wnioski:															15	13,25	0,301770280083684
						1. Optymalny kierunek z 1 w 10: 1-2-5-8-10 lub 1-3-7-10 . Ego długość 13.															16	13,5416666666667	0,331429814402442
						2. Optymalne kierunki: z 2 w 10: 2-5-8-10 (11); z 3 w 10: 3-7-10 (8); z 4 w 10: 4-6-7-10 (13);															17	13,8333333333333	0,341950526058371
									z 5 w 10: 5-8-10 (10); z 6 w 10: 6-7-10 (8); z 7 w 10: 7-10 (5);												18	14,125	0,331429814402443
									z 8 w 10: 8-10 (5); z 9 w 10: 9-10 (2).												19	14,4166666666667	0,301770280083687
						3. Oczekiwany czas z 1 w 10: 1-2-5-8-10 --- 14,33 , dla 1-3-7-10 --- 13,83. Kierunek 1-3-7-10 jest lepszy.															20	14,7083333333333	0,258117798989834
						Oczekiwany czas z 2 w 10: 2-5-8-10 --- 12,17.															21	15	0,207403478159268
						4.															22	15,2916666666667	0,156556358904878
						a) prawdopodobieństwo że czas przejazdu będzie między topt a 2topt;										p =	0,783				23	15,5833333333333	0,111015081999338
						b) prawdopodobieństwo że czas przejazdu będzie między 0,9toczek a 1,1toczek;											p=	0,764			24	15,875	0,073951987565583
																					25	16,1666666666667	0,046277971297019
																					26	16,4583333333333	0,027205415859144
																					27	16,75	0,015024257565916
																					28	17,0416666666667	0,007794482144221
																					29	17,3333333333333	0,003798727210233
																					30	17,625	0,001739184049114
																					31	17,9166666666667	0,000748013738611
																					32	18,2083333333333	0,000302224870601
																					33	18,5	0,000114711622084
																					34	18,7916666666667	4,09016884638904E-05

---

Sheet 3: Zadania

Zestaw 1-5. Dla dziesięciu miast 1,2, ... 9, 10 wiadomy czas przejazdu tij między odpowiednie miastami i i j . Która droga z miasta 1
do miasta 10 będzie najkrótsza?
Potrzebnie: 1. Narysować graf sieci dróg. 2. Uporządkować jego metodą Falkersona. 3. Metodami programowania dynamicznego
znaleźć minimalny czas przejazdu między punktami 1 a 10, i również 2 a 10, 3 a 10, ... , 9 a 10. 4. Oblicz oczekiwany czas
przejazdu od miasta 1 do miast 10 i od miasta 2 do miasta 10. 5. Oblicz prawdopodobieństwo że czas przejazdu będzie zawierać
się: a) między tpes a 1,5tpes; b) między 0,75toczek a 1,25 toczek. 6. Zrobić wnioski.
Zestaw 6-10. Dla dziesięciu miast 1,2, ... 9, 10 taksówkarzu wiadomy płacy za czas przyjazdu tij między odpowiednie
miastami i i j . Którą drogą z miasta 1 do miasta 10 powinien taksówkarz przewozić pasażerów, żeby otrzymać
największy zysk? Drogi przejezdne tylko w jednym kierunku.
Potrzebnie: 1. Narysować graf sieci dróg. 2. Uporządkować jego metodą Falkersona. 3. Metodami programowania
dynamicznego znaleźć maksymalny czas przejazdu (i maksymalny zysk) od przewozów między punktami 1 a 10, i również 2 a
10, 3 a 10, ... ,9 a 10. 4. Oblicz oczekiwany czas przejazdu od miasta 1 do miast 10 i od miasta 2 do miasta 10.
5. Oblicz prawdopodobieństwo że czas przejazdu będzie zawierać się: a) między topt a tpes; b) między 0,8toczek a 1,2toczek.
6. Zrobić wnioski.
W tablicach są zapisane macierzy zbieżności wierzchołków. Liczba w komórce oznacza połączenie pomiędzy i-tym a j-ym
punktem (opłatę, czas), komunikat "nie" - że połączenie nie istnieje.
Z prawej strony w macierzach zapisane, na ile procent zmniejsza się (zwiększa się) odpowiednia wartość dla czasu
optymistycznego (pesymistycznego).
Zestaw 1, 6												Zestaw 1, 6 Granice dolne												Zestaw 1, 6 Granice górne
Punkty	1	2	3	4	5	6	7	8	9	10		Punkty	1	2	3	4	5	6	7	8	9	10		Punkty	1	2	3	4	5	6	7	8	9	10
1	0	9	5	7	4	nie	nie	nie	nie	nie		1	0	6	1	3	2	nie	nie	nie	nie	nie		1	0	10	6	10	7	nie	nie	nie	nie	nie
2		0	nie	nie	7	nie	nie	2	6	nie		2		0	nie	nie	5	nie	nie	1	4	nie		2		0	nie	nie	10	nie	nie	3	9	nie
3			0	5	nie	9	nie	nie	nie	nie		3			0	2	nie	7	nie	nie	nie	nie		3			0	8	nie	12	nie	nie	nie	nie
4				0	3	6	nie	nie	nie	8		4				0	2	3	nie	nie	nie	6		4				0	4	8	nie	nie	nie	11
5					0	nie	9	nie	5	nie		5					0	nie	5	nie	2	nie		5					0	nie	12	nie	6	nie
6						0	nie	nie	nie	2		6						0	nie	nie	nie	1		6						0	nie	nie	nie	3
7							0	nie	2	6		7							0	nie	1	2		7							0	nie	3	7
8								0	4	nie		8								0	1	nie		8								0	6	nie
9									0	7		9									0	3		9									0	8
10										0		10										0		10										0
Zestaw 2, 7												Zestaw 2, 7 Granice dolne												Zestaw 2, 7 Granice górne
Punkty	1	2	3	4	5	6	7	8	9	10		Punkty	1	2	3	4	5	6	7	8	9	10		Punkty	1	2	3	4	5	6	7	8	9	10
1	0	7	4	9	nie	nie	6	nie	nie	nie		1	0	3	1	5	nie	nie	4	nie	nie	nie		1	0	8	7	11	nie	nie	8	nie	nie	nie
2		0	nie	5	4	nie	7	nie	nie	nie		2		0	nie	1	1	nie	5	nie	nie	nie		2		0	nie	8	6	nie	9	nie	nie	nie
3			0	nie	nie	8	nie	9	nie	nie		3			0	nie	nie	6	nie	5	nie	nie		3			0	nie	nie	10	nie	12	nie	nie
4				0	nie	nie	2	nie	nie	nie		4				0	nie	nie	1	nie	nie	nie		4				0	nie	nie	3	nie	nie	nie
5					0	nie	9	nie	3	nie		5					0	nie	5	nie	2	nie		5					0	nie	11	nie	4	nie
6						0	3	nie	nie	5		6						0	2	nie	nie	3		6						0	4	nie	nie	7
7							0	nie	4	6		7							0	nie	1	3		7							0	nie	7	8
8								0	nie	4		8								0	nie	2		8								0	nie	7
9									0	8		9									0	5		9									0	9
10										0		10										0		10										0
Zestaw 3, 8												Zestaw 3, 8 Granice dolne												Zestaw 3, 8 Granice górne
Punkty	1	2	3	4	5	6	7	8	9	10		Punkty	1	2	3	4	5	6	7	8	9	10		Punkty	1	2	3	4	5	6	7	8	9	10
1	0	4	5	7	3	nie	nie	nie	nie	nie		1	0	0	3	5	2	nie	nie	nie	nie	nie		1	0	6	7	10	4	nie	nie	nie	nie	nie
2		0	nie	8	nie	3	nie	nie	nie	nie		2		0	nie	6	nie	2	nie	nie	nie	nie		2		0	nie	11	nie	4	nie	nie	nie	nie
3			0	nie	8	nie	nie	nie	7	nie		3			0	nie	4	nie	nie	nie	4	nie		3			0	nie	9	nie	nie	nie	9	nie
4				0	nie	nie	nie	9	nie	nie		4				0	nie	nie	nie	6	nie	nie		4				0	nie	nie	nie	11	nie	nie
5					0	nie	nie	1	5	nie		5					0	nie	nie	1	1	nie		5					0	nie	nie	2	6	nie
6						0	5	2	nie	nie		6						0	3	1	nie	nie		6						0	7	3	nie	nie
7							0	nie	nie	9		7							0	nie	nie	7		7							0	nie	nie	11
8								0	nie	8		8								0	nie	4		8								0	nie	10
9									0	3		9									0	2		9									0	4
10										0		10										0		10										0
Zestaw 4, 9												Zestaw 4, 9 Granice dolne												Zestaw 4, 9 Granice górne
Punkty	1	2	3	4	5	6	7	8	9	10		Punkty	1	2	3	4	5	6	7	8	9	10		Punkty	1	2	3	4	5	6	7	8	9	10
1	0	7	9	nie	5	nie	nie	nie	nie	nie		1	0	4	6	nie	2	nie	nie	nie	nie	nie		1	0	10	11	nie	8	nie	nie	nie	nie	nie
2		0	nie	nie	9	6	nie	nie	nie	nie		2		0	nie	nie	5	4	nie	nie	nie	nie		2		0	nie	nie	12	7	nie	nie	nie	nie
3			0	4	3	nie	5	nie	nie	nie		3			0	1	2	nie	1	nie	nie	nie		3			0	7	4	nie	8	nie	nie	nie
4				0	nie	nie	1	nie	3	nie		4				0	nie	nie	0	nie	2	nie		4				0	nie	nie	2	nie	4	nie
5					0	nie	4	3	nie	8		5					0	nie	0	2	nie	6		5					0	nie	5	4	nie	10
6						0	nie	2	nie	4		6						0	nie	1	nie	0		6						0	nie	3	nie	6
7							0	nie	9	8		7							0	nie	5	5		7							0	nie	11	9
8								0	nie	3		8								0	nie	2		8								0	nie	4
9									0	6		9									0	2		9									0	8
10										0		10										0		10										0
Zestaw 5, 10												Zestaw 5, 10 Granice dolne												Zestaw 5, 10 Granice górne
Punkty	1	2	3	4	5	6	7	8	9	10		Punkty	1	2	3	4	5	6	7	8	9	10		Punkty	1	2	3	4	5	6	7	8	9	10
1	0	8	4	7	9	nie	nie	nie	nie	nie		1	0	5	1	5	7	nie	nie	nie	nie	nie		1	0	11	6	8	10	nie	nie	nie	nie	nie
2		0	nie	5	nie	3	nie	nie	nie	nie		2		0	nie	1	nie	2	nie	nie	nie	nie		2		0	nie	8	nie	4	nie	nie	nie	nie
3			0	nie	2	nie	6	nie	nie	nie		3			0	nie	1	nie	3	nie	nie	nie		3			0	nie	3	nie	9	nie	nie	nie
4				0	nie	2	nie	6	nie	nie		4				0	nie	1	nie	2	nie	nie		4				0	nie	3	nie	7	nie	nie
5					0	nie	4	5	8	nie		5					0	nie	1	3	4	nie		5					0	nie	7	8	11	nie
6						0	nie	9	nie	8		6						0	nie	6	nie	6		6						0	nie	10	nie	9
7							0	nie	5	nie		7							0	nie	1	nie		7							0	nie	6	nie
8								0	1	5		8								0	1	3		8								0	2	6
9									0	7		9									0	5		9									0	10
10										0		10										0		10										0
Punkty	1	2	3	4	5	6	7	8	9	10
1	0	16,2	nie	3,3	4,7	nie	1,8	5,9	nie	1
2		0	nie	nie	nie	nie	9,4	5,4	nie	3,1
3			0	2,5	16,1	nie	2,4	nie	nie	17,2
4				0	nie	nie	15,9	8,2	5,2	nie
5					0	nie	2,1	nie	nie	nie
6						0	5	17	nie	2,6
7							0	17,7	1,3	nie
8								0	nie	16,3
9									0	7
10										0