Podręcznik

1. Modele sieciowe

W niniejszym module rozważamy modele sieci przepływowych. Niektóre z problemów programowania liniowego można przedstawić w postaci grafu i przepływów w tym grafie. Okazuje się, że takie problemy odznaczają się specjalną strukturą, dzięki której istotnie redukuje się złożoność obliczeniowa względem ogólnych klas problemów do których one należą. Przykładowo, niektóre problemy optymalizacji całkowitoliczbowej, czyli ogólnie problemy trudne do rozwiązywania, można przedstawić w postaci przepływów w sieci. Wiedza, że dany problem można przedstawić w postaci sieci przepływowej niesie ze sobą następujące konsekwencje. Po pierwsze, wiemy, że dany problem ma niższą złożoność obliczeniową. Po drugie możemy zastosować dedykowane algorytm sieciowe. Dodatkowo, dla problemów ze zmiennymi dyskretnymi i przy dodatkowych warunkach, wiemy, że uciąglenie zmiennych dyskretnych prowadzi do problemu, którego rozwiązanie zachowuje warunek całkowitoliczbowości. Dlatego w wielu praktycznych sytuacjach staramy się uzyskać model przepływowy problemu dokonując odpowiednich przeformułowań, odpowiedniego kodowania problemu w zmiennych decyzyjnych.

Modele sieci przepływowych mają szerokie pole zastosowania w praktycznych problemach. Przykładem mogą być sieci transportowo-dystrybucyjne dla towarów, ale również przepływy energii elektrycznej, zarządzanie zasobami telekomunikacyjnymi, czy sieci bardziej abstrakcyjne jak sieci społecznościowe, sieci zależności zadań w projektach, czy zależności w strukturze organizacyjnej przedsiębiorstwa.