390 391

390 Programowanie sieciowe

Obliczamy koszty związane z połączeniami (tablica 8.6).

Tablica 8.6

Krawędź	Koszt	Krawędź	Koszt
1-2	120	3-4	120
1-3	120+ 70-3 = 330	3-5	120+ 52-3 = 276
1-4	120+ 87-3 = 381	3-6	120+ 94-3=402
1-5	120+139-3 = 537	3-7	120+ 114-3 = 462
1-6	120+181 -3 = 663
1-7	120 + 201 -3 = 723	4-5	120
		4-6	120+ 42-3 = 246
2-3	120	4-7	120+ 62-3 = 306
2-4	120+ 17-3=171
2-5	120+ 69-3 = 327	5-6	120
2-6	120+111 -3 = 453	5-7	120+ 20-3=180
2-7	120+ 131 -3 = 513	6-7	120

Rozwiązanie optymalne

Rozwiązanie zadania otrzymujemy za pomocą programu NDS1.EXE lub NDS2.EXE. Najkrótsza droga od wierzchołka początkowego do wierzchołka końcowego przechodzi przez wierzchołki I -2-4-5—7. Koszt przejścia tej drogi wynosi 591.

Interpretacja rozwiązania

Zgodnie z optymalnym planem zakupów przewiduje sic dokonanie zakupu 35 jednostek w pierwszym miesiącu (krawędź 1 —2: 35), następnie po upływie tego miesiąca — 87 jednostek na dwa kolejne miesiące (krawędź 2-4: 70+17). Po upływie tych miesięcy przewiduje się zakup 52 jednostek (krawędź. 4-5: 52), a następnie po 62 jednostki na ostatnie dwa miesiące (krawędź 5-7: 42 + 20).

8.5.2. Optymalizacja transportu gorącej wody z ciepłowni do terminala wysyłkowego

Przykład 8.5

Elektrociepłownia zbudowała system rurociągów do transportu gorącej wody z ciepłowni do terminalu wysyłkowego. Rysunek 8.26 ilustruje plan rurociągów, stacji pomp oraz przepustowość poszczególnych połączeń (w tys. m^J dziennie). Przepływ przez rurociąg może odbywać się w dowolnym (ale tylko jednym) kierunku, a jego wielkość nie może przekroczyć przepustowości danego odcinka. Należy znaleźć wielkość maksymalnego przepływu od ciepłowni do terminalu.

Ponadto należy podać, jakie ilości gorącej wody będą płynęły przez poszczególne odcinki. Jeżeli nastąpi awaria odcinka 2-3, to czy będzie miała ona wpływ na przepływ przez sieć?

Rozwiązanie

Konstrukcja sieci

7,adanie można rozwiązać, korzystając z algorytmu maksymalnego przepływu. Możemy bezpośrednio wykorzystać sieć przedstawioną na rys. 8.26.

Rysunek 8.26

Rozwiązanie optymalne

Zadanie rozwiązujemy, wykorzystując program MPS1.EXE lub MPS2.EXE. Maksymalny przepływ wynosi 120 tys. m³ gorącej wody i zapisano go w tablicy 8.7.

Tablica 8.7

Droga	Wielkość przepływu
1-2—3—4-7-8	20
1-2-3-5-8	10
1-2-5-8	20
I-3-2-5-8	10
1-3-2-5-6-8	20
I-3-5-6-8	10
I-4-3-6-8	10
1-4-3-7-8	10
1-4-7-8	10