366 367

8, Programowanie sieciowe

8.1. Wprowadzenie

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.

8.2. Minimalne

drzewo rozpinające

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

Wyszukiwarka

Podobne podstrony:
IMG98 Metody programowania sieciowego wprowadzono pod koniec lat pięćdziesiątych naszego wieku
27479 img350 (5) 5. Programowanie sieciowe Metody programowania sieciowego wprowadzono w końcu lat p
MODUŁ 1: Nazwa modułu kształcenia Wprowadzenie do problematyki zarządzania podmiotami
34630 sieci 5. Programowi! nid sieciowe Metody programowania sieciowego wprowadzono w końcu lat pięć
ZT139 (2) 276 CZĘŚĆ 3. WSPÓŁCZESNE PROBLEMY ZARZĄDZANIA TURYSTYKĄPrawodawstwo Władze mogą wprowadzać
1. Wprowadzenie do problematyki koncepcji zarządzania Zarządzanie - realizacja funkcji zarządzania:
1956 - programowanie kwadratowe Wiele problemów optymalizacyjnych jest formułowanych w postaci model
Programowanie SiecioweHarmonogram semestru O Zajęcia 1 - zajęcia wprowadzające, wymagania, harmonogr
Programowanie SiecioweHarmonogram semestru O Zajęcia 1 - zajęcia wprowadzające, wymagania, harmonogr
35008 ZT184 (2) 366 CZĘŚĆ 3. WSPÓŁCZESNE PROBLEMY ZARZĄDZANIA TURYSTYKĄ Celem tego rozdziału jest pr
Programowanie SiecioweHarmonogram semestru O Zajęcia 1 - zajęcia wprowadzające, wymagania, harmonogr
Rozdział 2 Wprowadzenie do tematyki zarządzania jakością w organizacji Podchodząc do problematyki

więcej podobnych podstron