394 395

394 Programowanie sieciowe

numeracji budynków w tablicy 8.10. Wartości przy odpowiednich krawędziach, wynikające z kosztów połączeń, podane są w tablicy 8.11.

Tablica 8.1 I

Krawędź	Koszt	Krawędź	Koszt
1-2	8	4-5	18
1-3	7	4-9	9
1-4	9	5-6	15
1-6	18	5-7	9
2-3	7	5-9	15
2-4	8	6-7	6
2-9	5	6-8	14
3-4	8	7-8	12
3-5	7	7-9	14
3-6	12	7-10	20
3-7	10	8-9	5
3-8	16	9-10	5

Rozwiązanie optymalne

Zadanie rozwiązujemy za pomocą programu MDR2.RXE. Optymalną sieć powiązań przedstawiono w tablicy 8.12.

Tablica 8.12

Połączenie	Koszt
1-2	7
2-3	7
2-4	8
2-9	5
3-5	7
5-7	9
6-7	6
8-9	5
9-10	5
Suma	59

Interpretacja rozwiązania

Optymalną sieć połączeń należy zbudować wyłącznie między budynkami, których numery wymieniono w tablicy 8.12, wykorzystując połączenia wyszczególnione w tej tablicy. Gwarantuje to przesyłanie informacji między dwoma dowolnymi budynkami, a jednocześnie mamy zapewniony minimalny koszt budowy sieci.

Pr^gramciwsitie dftmmlczme.

9.1. Wprowadzenie

W poprzednich rozdziałach rozpatrywaliśmy zadania, w których decyzje podejmowane hyły jednorazowo na początku rozważanego odcinka czasu (wyjątek stanowi tu zagadnienie wieloetapowych drzew decyzyjnych omawiane w rozdziale 5). Zadania takie można określić mianem zadań statycznych. Istnieje jednak wiele zagadnień, w których decyzji nie podejmujemy jednorazowo, lecz wielokrotnie. Ze względu na powyższą własność nazwiemy je wieloetapowymi procesami decyzyjnymi.

Na ocenę interesującego nas procesu mają wpływ wszystkie decyzje podejmowane w trakcie jego trwania. Dlatego też, chcąc zmaksymalizować (lub zminimalizować) wieloetapową funkcję celu. obejmującą wszystkie etapy, nie wystarczy rozwiązać ciągu zadań jednoetapowych, lecz trzeba na rozwiązanie popatrzeć kompleksowo. Wynika to stąd, że skutki decyzji podjętych w etapach wcześniejszych mogą w istotny sposób zmniejszać (lub przeciwnie — zwiększać) możliwości decyzyjne w następnych etapach.

Opisując problemy programowania dynamicznego, wykorzystamy terminologię zaczerpniętą z teorii sterowania automatycznego. Na początku każdego etapu proces scharakteryzowany jest wielkościami nazwanymi zmiennymi stanu. Decydent na początku każdego etapu ma możliwość obserwowania tych wielkości. W kolejnych etapach istnieje możliwość sterowania przebiegiem takiego procesu przez wybór dopuszczalnych wartości zmiennych decyzyjnych, zwanych też wartościami sterującymi. Zbiór tych wartości uzależniony jest od stanu, w jakim znajduje się proces. Podjęcie decyzji etapowej powoduje, że na początku następnego etapu proces znajdzie się w kolejnym stanie.

Funkcję opisującą zależność między stanem procesu na początku następnego etapu a stanem procesu na początku etapu bieżącego i podjętą decyzją (czyli dynamikę procesu) nazywamy funkcją przejścia. Jednocześnie z przejściem takim związana jest etapowa korzyść lub strata. Zajmiemy się najczęściej występującą sytuacją, w której globalna korzyść (lub strata) charakteryzująca sterowanie procesem jest sumą korzyści (lub strat) etapowych. Będziemy starali się podejmować