---

Overview

Zadanie
Wzor
Wzór_ćw
Graf
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	IX		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: Wzór_ćw

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

IX

x12

t12

2

tij - obciążenia grafu

t45

5

3

8

x13

t13

5

Funkcja celu

t46

5

2

8

x14

t14

9

Z=

t56

4

3

5

x24

t24

4

Ograniczenia

t58

5

3

7

x25

t25

1

t67

3

3

6

x26

t26

9

1:

=

t68

5

4

6

x35

t35

5

2:

=

t78

9

7

13

x36

t36

9

3:

=

t79

8

7

15

x37

t37

3

4:

=

t710

5

5

8

x45

t45

5

5:

=

t89

6

5

8

x46

t46

5

6:

=

t810

5

5

8

x56

t56

4

7:

=

t910

2

1

6

x58

t58

5

8:

=

3

Metodami programowania dynamicznego znajdziemy minimalny czas przejazdu

x67

t67

3

9:

=

1

2

3

4

5

6

7

8

9

10

x68

t68

5

10:

=

x78

t78

9

1_2

2_4

3_5

4_5

5_6

6_7

7_8

8_9

9_10

10_10

x79

t79

8

x710

t710

5

x89

t89

6

x810

t810

5

x910

t910

2

4, 5

Obliczamy optymistyczny, pesymistyczny, oczekiwany czas przejazdu

trasa

1_2

2_5

5_8

8_10

10_10

topt

toczekiwane=

tpes

trasa

1_3

3_7

7_10

10_10

topt

toczekiwane=

tpes

trasa

2_5

5_8

8_10

10_10

topt

toczekiwane=

tpes

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

Korzystniejszy (minimalny czas) kierunek jest 1-3-7-10. Dla tego

toczekiwane=

Obliczymy wariancje s2 według wzoru:

Wtedy

s2 =

s =

W naszym przypadku

Obliczamy:

a) prawdopodobieństwo że czas przejazdu będzie między t=12 a t=15;

topt =

12

2topt =

15

p =

(narysowane na wykresie)

b) prawdopodobieństwo że czas przejazdu będzie między 0,9toczek a 1,1toczek;

0,9toczek =

2topt =

p =

---

Sheet 4: Graf

---

Sheet 5: 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	15,6	10,5	nie	12,5	nie	nie	13,8	15,8	1,9
2		0	11,3	nie	18	nie	19,2	nie	nie	nie
3			0	nie	2,8	11,6	nie	nie	nie	2,5
4				0	10,2	nie	11,3	nie	nie	nie
5					0	8,9	nie	nie	14,8	4
6						0	nie	nie	nie	nie
7							0	15,3	19,9	nie
8								0	15,9	nie
9									0	14,4
10										0