Сетевые модели

Материал из Systems analysis wiki
Перейти к навигации Перейти к поиску

Сетевые модели (в исследовании операций; англ. Network models) — это класс математических моделей, представляющих задачу в форме графа (сети), где вершины (узлы) обозначают объекты или состояния, а рёбра (дуги) — связи или процессы между ними[1]. В контексте оптимизации под сетью часто понимается ориентированный граф, который в операционном анализе напрямую называют «сетью»; вершины такой сети называются узлами, а рёбра — дугами[2].

Сетевые модели являются мощным инструментом для анализа и оптимизации сложных систем в таких областях, как логистика, телекоммуникации, управление проектами и финансы. Их сила заключается в высоком уровне абстракции: узел может представлять город, компьютерный маршрутизатор или этап проекта, а дуга — дорогу, канал связи или технологическую операцию.

Определение и терминология

Основой для сетевых моделей служит теория графов. Ключевыми понятиями являются:

  • Сеть потоков (англ. flow network): ориентированный граф, в котором каждое ребро имеет пропускную способность (capacity) и поток (flow). В графе выделяются две особые вершины: исток (source), из которого поток исходит, и сток (sink), в который он входит[1].
  • Закон сохранения потока: Для любой вершины, не являющейся истоком или стоком, суммарный входящий поток должен быть равен суммарному исходящему потоку. Это условие является дискретным аналогом физических законов сохранения[3].
  • Сетевое планирование: Модель, представляющая проект как комплекс взаимосвязанных операций (дуг) и событий (узлов). Такие сети являются ориентированными ациклическими графами, что отражает порядок выполнения работ[4].

Ключевые свойства и теоремы

Сетевые модели обладают рядом особых свойств, которые позволяют применять для их решения высокоэффективные алгоритмы.

  • Целочисленность решений: Многие задачи сетевой оптимизации (например, о максимальном потоке или кратчайшем пути) обладают свойством полной унимодулярности матрицы ограничений. Благодаря этому, если параметры задачи (пропускные способности, длины) целочисленные, то оптимальное решение, найденное методами линейного программирования, также будет целочисленным без необходимости введения дополнительных ограничений[5][6].
  • Теорема о максимальном потоке и минимальном разрезе: Центральный результат теории потоков. Утверждает, что максимальная величина потока из истока в сток равна минимальной пропускной способности среди всех разрезов, разделяющих исток и сток. Эта теорема устанавливает критерий оптимальности для потока и лежит в основе многих алгоритмов[6][7].
  • Принцип оптимальности для кратчайших путей: Если путь из точки А в точку С является кратчайшим, то любой его участок (например, от промежуточной точки В до С) также является кратчайшим путём между соответствующими вершинами. Это свойство, лежащее в основе динамического программирования, обуславливает корректность таких алгоритмов, как алгоритм Дейкстры[8].
  • Свойства минимального остовного дерева (МОД):
  • Свойство разреза: Для любого разреза графа ребро с минимальным весом, пересекающее разрез, принадлежит хотя бы одному МОД.
  • Свойство цикла: В любом цикле графа ребро с максимальным весом не принадлежит ни одному МОД.

На этих свойствах основана корректность «жадных» алгоритмов Прима и Краскала[9].

Основные задачи сетевой оптимизации

  • Задача о кратчайшем пути: Найти путь минимальной суммарной длины (веса) между двумя заданными узлами. Решается алгоритмом Дейкстры (для неотрицательных весов) или алгоритмом Беллмана-Форда (для произвольных весов)[8].
  • Задача о максимальном потоке: Определить максимально возможный поток от истока к стоку при заданных пропускных способностях дуг. Классический метод решения — алгоритм Форда — Фалкерсона[6].
  • Задача о минимальном остовном дереве: Найти подграф, который соединяет все вершины сети и имеет минимальную суммарную стоимость рёбер.
  • Метод критического пути (CPM): В сетевых моделях планирования определить самую длинную последовательность работ, которая устанавливает минимально возможное время выполнения всего проекта. Работы на этом пути имеют нулевой резерв времени[10].

Примеры

  • Кратчайший путь: Поиск оптимального маршрута навигационной системой между двумя точками на карте города, где города — узлы, а дороги — дуги с весами, равными длине или времени проезда.
  • Максимальный поток: Определение максимальной пропускной способности сети трубопроводов, где насосные станции — узлы, а трубы — дуги с ограниченной пропускной способностью.
  • Минимальное остовное дерево: Проектирование сети связи (например, прокладка оптоволоконного кабеля) для соединения нескольких городов с минимальной общей длиной кабеля.
  • Критический путь: В проекте строительства дома, где работы (закладка фундамента, возведение стен, монтаж крыши) имеют заданную длительность и технологические зависимости, критический путь определяет минимальный срок завершения строительства. Любая задержка работы на этом пути приведёт к задержке всего проекта[10].

См. также

Примечания

  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]
Источник — https://systems-analysis.ru/wiki/index.php?title=Сетевые_модели&oldid=2146