Wiele problemów zarządzania, związanych m.in. z optymalizacją systemów transportowych, projektowaniem systemów informatycznych czy pewnymi zagadnieniami logistycznymi, można przedstawić jako zagadnienia sieciowe i rozwiązać za pomocą odpowiednich metod. W niniejszym rozdziale zostaną omówione trzy takie metody programowania sieciowego: algorytm znajdowania minimalnego drzewa rozpinającego, algorytm poszukiwania najkrótszych dróg w sieci oraz algorytm maksymalnego przepływu.
Drzewo rozpinające w grafie liczącym n wierzchołków to zbiór n — 1 jego krawędzi takich, że dowolne dwa wierzchołki grafu można połączyć za pomocą krawędzi należących do tego zbioru. Minimalne drzewo rozpinające to drzewo wybrane spośród wszystkich istniejących drzew rozpinających, dla którego łączna długość krawędzi jest najmniejsza.
Najkrótsza droga między dwoma dowolnie wybranymi wierzchołkami w sieci to taki zbiór krawędzi łączących te wierzchołki, dla których suma długości jest najmniejsza. Przyjmujemy, że wierzchołek o numerze 1 jest wyróżnionym wierzchołkiem początkowym grafu i interesuje nas znalezienie najkrótszych dróg łączących wierzchołek początkowy ze wszystkimi pozostałymi wierzchołkami grafu.
W zagadnieniu maksymalnego przepływu wyróżniamy wierzchołek początkowy, zwany źródłem, oraz wierzchołek końcowy, zwany ujściem. Każda krawędź grafu opisana jest dwoma liczbami, charakteryzującymi przepustowości krawędzi. Należy zaplanować taki przepływ między źródłem i ujściem, uwzględniający przepustowość wszystkich krawędzi, aby łączna wielkość tego przepływu była największa.
W dalszej części rozdziału omówimy metody programowania sieciowego, pozwalające na rozwiązanie sformułowanych powyżej zadań Pokażemy możliwości ich zastosowania w rozwiązywaniu różnorodnych zadań praktycznych. Do poszukiwania minimalnego drzewa rozpinającego wykorzystamy programy MDR1.EXE i MDR2.EXE, najkrótsze drogi w sieci znajdziemy przy użyciu programów NDS1.EXE i NDS2.EXE, natomiast do znalezienia maksymalnego przepływu w sieciach wykorzystamy programy MPS1.EXE i MPS2.EXE.
Proste zastosowanie zagadnienia minimalnego drzewa rozpinającego do planowania sieci komputerowej ilustruje przykład 8.1
Przykład 8.1
Centrum komputerowe ma zainstalować nowy superkomputer, który zostanie połączony z pięcioma użytkownikami za pomocą linii telekomunikacyjnej. Koszty instalacji są wysokie i dlatego dopuszcza się możliwość bezpośredniego połączenia niektórych użytkowników, natomiast pozostali podłączą się za pośrednictwem użytkowników już podłączonych. W wyniku przeprowadzonej analizy możliwości połączeń uzyskano graf, przedstawiony na rys. 8.1. Węzeł 1 oznacza centrum komputerowe, natomiast węzły 2-6 to użytkownicy. Krawędzie w sieci odpowiadają tym połączeniom, które mogą być zrealizowane, natomiast wartość parametru opisującego każdą z krawędzi to koszt realizacji tego połączenia. Należy znaleźć takie połączenie, które pozwoli na uzyskanie łączności między dowolnymi dwoma użytkownikami a centrum komputerowym i zminimalizuje koszt budowy linii telekomunikacyjnej.
Opisany w tym przykładzie problem budowy sieci komputerowej może być rozwiązany za pomocą algorytmu minimalnego drzewa rozpinającego.
Rysunek 8.1