Modele sieciowe (badania operacyjne)

From Systems analysis Wiki
Jump to navigation Jump to search

Modele sieciowe (w badaniach operacyjnych; ang. Network models) — to klasa modeli matematycznych, które reprezentują zadanie w postaci grafu (sieci), gdzie wierzchołki (węzły) oznaczają obiekty lub stany, a krawędzie (łuki) — powiązania lub procesy między nimi[1]. W kontekście optymalizacji przez sieć rozumie się często graf skierowany, który w analizie operacyjnej bezpośrednio nazywany jest „siecią"; wierzchołki takiej sieci nazywane są węzłami, a krawędzie — łukami[2].

Modele sieciowe są potężnym narzędziem do analizy i optymalizacji złożonych systemów w takich dziedzinach jak logistyka, telekomunikacja, zarządzanie projektami i finanse. Ich siła tkwi w wysokim poziomie abstrakcji: węzeł może reprezentować miasto, router komputerowy lub etap projektu, a łuk — drogę, kanał komunikacyjny lub operację technologiczną.

Definicja i terminologia

Podstawą modeli sieciowych jest teoria grafów. Kluczowymi pojęciami są:

  • Sieć przepływowa (ang. flow network): graf skierowany, w którym każda krawędź posiada przepustowość (capacity) oraz przepływ (flow). W grafie wyróżniane są dwa szczególne wierzchołki: źródło (source), z którego przepływ wychodzi, oraz ujście (sink), do którego on wpływa[1].
  • Prawo zachowania przepływu: Dla każdego wierzchołka, który nie jest źródłem ani ujściem, łączny przepływ wchodzący musi być równy łącznemu przepływowi wychodzącemu. Warunek ten jest dyskretnym analogiem fizycznych praw zachowania[3].
  • Planowanie sieciowe: Model reprezentujący projekt jako zbiór wzajemnie powiązanych operacji (łuków) i zdarzeń (węzłów). Takie sieci są skierowanymi grafami acyklicznymi, co odzwierciedla kolejność wykonywania prac[4].

Kluczowe właściwości i twierdzenia

Modele sieciowe posiadają szereg szczególnych właściwości, które umożliwiają stosowanie do ich rozwiązywania wysoce efektywnych algorytmów.

  • Całkowitoliczbowość rozwiązań: Wiele zadań optymalizacji sieciowej (np. o maksymalnym przepływie lub najkrótszej ścieżce) posiada właściwość pełnej unimodularności macierzy ograniczeń. Dzięki temu, jeśli parametry zadania (przepustowości, długości) są całkowitoliczbowe, to optymalne rozwiązanie znalezione metodami programowania liniowego również będzie całkowitoliczbowe, bez potrzeby wprowadzania dodatkowych ograniczeń[5][6].
  • Twierdzenie o maksymalnym przepływie i minimalnym przekroju: Centralny wynik teorii przepływów. Stwierdza, że maksymalna wartość przepływu ze źródła do ujścia jest równa minimalnej przepustowości spośród wszystkich przekrojów rozdzielających źródło i ujście. Twierdzenie to ustanawia kryterium optymalności przepływu i stanowi podstawę wielu algorytmów[6][7].
  • Zasada optymalności dla najkrótszych ścieżek: Jeśli ścieżka z punktu A do punktu C jest najkrótszą, to każdy jej odcinek (np. od pośredniego punktu B do C) jest również najkrótszą ścieżką między odpowiednimi wierzchołkami. Ta właściwość, leżąca u podstaw programowania dynamicznego, warunkuje poprawność takich algorytmów jak algorytm Dijkstry[8].
  • Właściwości minimalnego drzewa rozpinającego (MDR):
  • Właściwość przekroju: Dla każdego przekroju grafu krawędź o minimalnej wadze przecinająca przekrój należy do co najmniej jednego MDR.
  • Właściwość cyklu: W każdym cyklu grafu krawędź o maksymalnej wadze nie należy do żadnego MDR.

Na tych właściwościach opiera się poprawność „zachłannych" algorytmów Prima i Kruskala[9].

Podstawowe zadania optymalizacji sieciowej

  • Zadanie najkrótszej ścieżki: Znaleźć ścieżkę o minimalnej łącznej długości (wadze) między dwoma zadanymi węzłami. Rozwiązywane algorytmem Dijkstry (dla nieujemnych wag) lub algorytmem Bellmana-Forda (dla dowolnych wag)[8].
  • Zadanie maksymalnego przepływu: Wyznaczyć maksymalny możliwy przepływ od źródła do ujścia przy zadanych przepustowościach łuków. Klasyczna metoda rozwiązania — algorytm Forda-Fulkersona[6].
  • Zadanie minimalnego drzewa rozpinającego: Znaleźć podgraf, który łączy wszystkie wierzchołki sieci i posiada minimalną łączną wagę krawędzi.
  • Metoda ścieżki krytycznej (CPM): W sieciowych modelach planowania wyznaczyć najdłuższą sekwencję prac, która określa minimalny możliwy czas realizacji całego projektu. Prace leżące na tej ścieżce mają zerowy zapas czasu[10].

Przykłady

  • Najkrótsza ścieżka: Wyznaczanie optymalnej trasy przez system nawigacyjny między dwoma punktami na mapie miasta, gdzie miasta są węzłami, a drogi — łukami o wagach równych długości lub czasowi przejazdu.
  • Maksymalny przepływ: Wyznaczenie maksymalnej przepustowości sieci rurociągów, gdzie stacje pompowe są węzłami, a rury — łukami o ograniczonej przepustowości.
  • Minimalne drzewo rozpinające: Projektowanie sieci telekomunikacyjnej (np. układanie kabla światłowodowego) w celu połączenia kilku miast przy minimalnej łącznej długości kabla.
  • Ścieżka krytyczna: W projekcie budowy domu, gdzie prace (wykop pod fundamenty, wznoszenie ścian, montaż dachu) mają określony czas trwania i zależności technologiczne, ścieżka krytyczna wyznacza minimalny termin zakończenia budowy. Każde opóźnienie pracy leżącej na tej ścieżce spowoduje opóźnienie całego projektu[10].

Zobacz też

  • Badania operacyjne
  • Teoria grafów
  • Zagadnienie transportowe
  • Metoda ścieżki krytycznej
  • PERT

Przypisy

  1. ↑ 1.0 1.1 "Flow network". Wikipedia. [1]
  2. ↑ "Тема 10: Сетевые модели". Учебное пособие. Гомель: БелГУТ. [2]
  3. ↑ "Транспортная сеть". Википедия. [3]
  4. ↑ "Сетевое планирование". Википедия. [4]
  5. ↑ Bradley S. P., Hax A. C., Magnanti T. L. (1977). Applied Mathematical Programming. Addison-Wesley. Ch.8: Network Models. [5]
  6. ↑ 6.0 6.1 6.2 "Задача о максимальном потоке". Википедия. [6]
  7. ↑ Goldberg A. V., Tardos É., Tarjan R. E. (1990). "Network Flow Algorithms". In: Paths, Flows, and VLSI-Layout. Springer. [7]
  8. ↑ 8.0 8.1 "Задача о кратчайшем пути". Википедия. [8]
  9. ↑ "Минимальное остовное дерево". Википедия.
  10. ↑ 10.0 10.1 "Метод критического пути". Википедия. [9]
Retrieved from "https://systems-analysis.info/int/index.php?title=Modele_sieciowe_(badania_operacyjne)&oldid=4530"