---

Overview

Zadanie
Wzór
Zestawy dla rozwiązania

---

Sheet 1: Zadanie

Ćwiczenie 6.  Zadanie o maksymalnym potoku

Zadanie

1. (1.0) Sformułować ekonomiczno - matematyczny model zadania;

2. (0.5) Narysować graf sieci;

3. (1.0) Obliczyć początkowe potoki, tabele nasyconych żeber i potoków. Zrobić wnioski;

4. (1.5) Zwiększyć moc potoku;

5. (1.0) Obliczyć maksymalny potok.

---

Sheet 2: Wzór

Zadanie.		Zorganizować maksymalny dowóz turystów mikrobusami z miasta 1 do miasta 6 w jednostce czasu, jeżeli maksymalny
		dowóz pomiędzy miastem i a j wynosi rij:								r12	r13	r14	r23	r24	r25	r35	r45	r46	r56
										7	4	2	8	4	1	2	8	4	5
1	Na podstawie danych stworzymy macierz przepustowości żeber (maksymalnych potoków) i narysujemy graf połączeń
		Macierz przepustowości
		1	2	3	4	5	6
	1	0	7	4	2	0	0
	2	7	0	8	4	1	0
	3	4	8	0	0	2	0
	4	2	4	0	0	8	4
	5	0	1	2	8	0	5
	6	0	0	0	4	5	0
2	Tworzymy początkowe potoki:
								Początkowe potoki:				1-3-5-6 2 jednostki,				(min(	4	2	5	)=	2	)
												1-2-5-6 1 jednostka,				(min(	7	1	3	)=	1	)
												1-4-6 2 jednostki.				(min(	2	4		)=	2	)	Potok w sieci:			5
									Tabela potoku:							Tabela nasyconych żeber:
									1	2	3	4	5	6			1	2	3	4	5	6
								1	0	1	2	2	0	0		1	0	6	2	0	0	0
								2	-1	0	0	0	1	0		2	8	0	8	4	0	0
								3	-2	0	0	0	2	0		3	6	8	0	0	0	0
								4	-2	0	0	0	0	2		4	4	4	0	0	8	2
								5	0	-1	-2	0	0	3		5	0	2	4	8	0	2
								6	0	0	0	-2	-3	0		6	0	0	0	6	8	0
3	Zbiór nienasyconych wierzchołków:							1|2,3		2|3,4		3|.
												4|5,6		5|6	- potok nie optymalny.
										3|.
	Tworzymy potok 1-2-4-6 i zwiększamy moc potoku w sieci na min(												6	4	2	)=	2	jednostki
	Sieć połączeń:																						Potok w sieci:			7
									Tabela potoku:							Tabela nasyconych żeber:
									1	2	3	4	5	6			1	2	3	4	5	6
								1	0	3	2	2	0	0		1	0	4	2	0	0	0
								2	-3	0	0	2	1	0		2	10	0	8	2	0	0
								3	-2	0	0	0	2	0		3	6	8	0	0	0	0
								4	-2	-2	0	0	0	4		4	4	6	0	0	8	0
								5	0	-1	-2	0	0	3		5	0	2	4	8	0	2
								6	0	0	0	-4	-3	0		6	0	0	0	8	8	0
	Zbiór nienasyconych wierzchołków:							1|2,3		2|3,4		3|.
												4|5		5|6	- potok nie optymalny.
	Tworzymy potok 1-2-4-5-6 i zwiększamy moc potoku w sieci na min(												4	2	8	2	)=	2	jednostki				Potok w sieci:			9
4	Sieć połączeń:
									Tabela potoku:							Tabela nasyconych żeber:
									1	2	3	4	5	6			1	2	3	4	5	6
								1	0	5	2	2	0	0		1	0	2	2	0	0	0
								2	-5	0	0	4	1	0		2	12	0	8	0	0	0
								3	-2	0	0	0	2	0		3	6	8	0	0	0	0
								4	-2	-4	0	0	2	4		4	4	8	0	0	6	0
								5	0	-1	-2	-2	0	5		5	0	2	4	10	0	0
								6	0	0	0	-4	-5	0		6	0	0	0	8	10	0
5	Zbiór nienasyconych wierzchołków:							1|2,3		2|.		3|.					- potok optymalny.
														Maksymalna moc potoku: 2+5+2 = 4+5 = 9.
	Czerwona linia przerywana pokazuję cięcie minimalne C(A,B)
	Zbiór A zawiera wierzchołki {1,2,3} - wynika ze zbioru nienasyconych wierzchołków na ostatnim kroku.
	Zbiór B zawiera pozostałe wierzchołki {4,5,6}. Przepustowość cięcia wynosi 2+1+4+2=9.
											Solver
	Zmienne decyzyjne:						Funkcja celu				Ograniczenia
	x12	7				Z=	8,99999999996458	---> max			1	8,99999999996458	=	8,99999999996458			r12	7
	x13	-3,54170026639622E-11									2	7	=	7,00000000005403			r13	4
	x14	2									3	2,00000000001861	=	2			r14	2
	x23	2,00000000005403									4	6	=	6			r23	8
	x24	4									5	5,0000000000373	=	5			r24	4
	x25	1									6	8,9999999999627	=	8,99999999996458			r25	1
	x35	2															r35	2
	x45	2,0000000000373															r45	8
	x46	3,9999999999627															r46	4
	x56	5															r56	5
						Tabela potoku:							Tabela nasyconych żeber:
						1	2	3	4	5	6			1	2	3	4	5	6
					1	0	7	-3,54170026639622E-11	2	0	0		1	0	0	4,00000000003542	0	0	0
					2	-7	0	2,00000000005403	4	1	0		2	14	0	5,99999999994597	0	0	0
					3	3,54170026639622E-11	-2,00000000005403	0	0	2	0		3	3,99999999996458	10,000000000054	0	0	0	0
					4	-2	-4	0	0	2,0000000000373	3,9999999999627		4	4	8	0	0	5,9999999999627	3,73039377166151E-11
					5	0	-1	-2	-2,0000000000373	0	5		5	0	2	4	10,0000000000373	0	0
					6	0	0	0	-3,9999999999627	-5	0		6	0	0	0	7,9999999999627	10	0

---

Sheet 3: Zestawy dla rozwiązania

Zorganizować maksymalny potok (turystów, samochodów, ropy, informacji, itp.) od p.1 do p.6
Dane do zestawów są zapisane w kolumnach.
Jeżeli rij = 0 wtedy połączenie pomiędzy i i j nie istnieję.
		Zadania
	Var	1	2	3	4	5	6	7	8	9	10
	r12	6	10	3	1	4	1	9	1	10	9
	r13	2	2	8	0	1	1	9	0	4	2
	r14	9	4	0	6	0	10	0	5	2	3
	r15	1	1	7	0	10	0	2	0	2	5
	r16	5	0	10	5	9	2	5	7	0	5
	r23	9	5	0	6	6	9	2	4	1	1
	r24	8	9	4	1	8	7	0	5	6	9
	r25	4	10	5	2	10	5	2	5	2	6
	r26	0	4	1	0	1	1	0	1	0	3
	r34	5	1	0	0	0	7	10	0	1	6
	r35	10	5	2	0	0	10	7	3	9	5
	r36	5	0	4	7	9	4	1	8	10	2
	r45	8	3	4	1	0	2	0	7	5	7
	r46	6	9	4	3	1	8	9	1	3	9
	r56	3	10	4	7	8	9	10	2	8	1