---
title: "Сетевые модели"
source: "https://systems-analysis.info/wiki/%D0%A1%D0%B5%D1%82%D0%B5%D0%B2%D1%8B%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8"
wiki: "systems-analysis.info/wiki"
article: "Сетевые_модели"
language: "ru"
categories:
  - "Категория:Russian"
  - "Категория:Исследование операций"
revision_id: 362
wiki_created_at: 2026-09-06T22:07:42Z
wiki_modified_at: 2026-09-06T22:07:42Z
downloaded_at: 2026-09-07T22:19:20Z
---

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

**Сетевые модели** (в [исследовании операций](https://systems-analysis.info/wiki/%D0%98%D1%81%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BE%D0%BF%D0%B5%D1%80%D0%B0%D1%86%D0%B8%D0%B9 "Исследование операций"); англ. *Network models*) — это класс математических моделей, представляющих задачу в форме графа (сети), где вершины (узлы) обозначают объекты или состояния, а рёбра (дуги) — связи или процессы между ними<sup>[\[1\]](https://systems-analysis.info/wiki/%D0%A1%D0%B5%D1%82%D0%B5%D0%B2%D1%8B%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8#cite_note-en-wiki-flow-network-1)</sup>. В контексте оптимизации под сетью часто понимается ориентированный граф, который в операционном анализе напрямую называют «сетью»; вершины такой сети называются узлами, а рёбра — дугами<sup>[\[2\]](https://systems-analysis.info/wiki/%D0%A1%D0%B5%D1%82%D0%B5%D0%B2%D1%8B%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8#cite_note-belgut-lec-2)</sup>.

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

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

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

- **Сеть потоков** (англ. *flow network*): ориентированный граф, в котором каждое ребро имеет **пропускную способность** (*capacity*) и **поток** (*flow*). В графе выделяются две особые вершины: **исток** (*source*), из которого поток исходит, и **сток** (*sink*), в который он входит<sup>[\[1\]](https://systems-analysis.info/wiki/%D0%A1%D0%B5%D1%82%D0%B5%D0%B2%D1%8B%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8#cite_note-en-wiki-flow-network-1)</sup>.
- **Закон сохранения потока**: Для любой вершины, не являющейся истоком или стоком, суммарный входящий поток должен быть равен суммарному исходящему потоку. Это условие является дискретным аналогом физических законов сохранения<sup>[\[3\]](https://systems-analysis.info/wiki/%D0%A1%D0%B5%D1%82%D0%B5%D0%B2%D1%8B%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8#cite_note-ru-wiki-transport-net-3)</sup>.
- **Сетевое планирование**: Модель, представляющая проект как комплекс взаимосвязанных операций (дуг) и событий (узлов). Такие сети являются ориентированными ациклическими графами, что отражает порядок выполнения работ<sup>[\[4\]](https://systems-analysis.info/wiki/%D0%A1%D0%B5%D1%82%D0%B5%D0%B2%D1%8B%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8#cite_note-ru-wiki-cpm-pert-4)</sup>.

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

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

- **Целочисленность решений**: Многие задачи сетевой оптимизации (например, о максимальном потоке или кратчайшем пути) обладают свойством полной унимодулярности матрицы ограничений. Благодаря этому, если параметры задачи (пропускные способности, длины) целочисленные, то оптимальное решение, найденное методами [линейного программирования](https://systems-analysis.info/wiki/%D0%9B%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 "Линейное программирование"), также будет целочисленным без необходимости введения дополнительных ограничений<sup>[\[5\]](https://systems-analysis.info/wiki/%D0%A1%D0%B5%D1%82%D0%B5%D0%B2%D1%8B%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8#cite_note-mit-amp-ch8-5)[\[6\]](https://systems-analysis.info/wiki/%D0%A1%D0%B5%D1%82%D0%B5%D0%B2%D1%8B%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8#cite_note-ru-wiki-max-flow-6)</sup>.
- **Теорема о максимальном потоке и минимальном разрезе**: Центральный результат теории потоков. Утверждает, что максимальная величина потока из истока в сток равна минимальной пропускной способности среди всех разрезов, разделяющих исток и сток. Эта теорема устанавливает критерий оптимальности для потока и лежит в основе многих алгоритмов<sup>[\[6\]](https://systems-analysis.info/wiki/%D0%A1%D0%B5%D1%82%D0%B5%D0%B2%D1%8B%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8#cite_note-ru-wiki-max-flow-6)[\[7\]](https://systems-analysis.info/wiki/%D0%A1%D0%B5%D1%82%D0%B5%D0%B2%D1%8B%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8#cite_note-goldberg-tarjan-1990-7)</sup>.
- **Принцип оптимальности для кратчайших путей**: Если путь из точки А в точку С является кратчайшим, то любой его участок (например, от промежуточной точки В до С) также является кратчайшим путём между соответствующими вершинами. Это свойство, лежащее в основе [динамического программирования](https://systems-analysis.info/wiki/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 "Динамическое программирование"), обуславливает корректность таких алгоритмов, как алгоритм Дейкстры<sup>[\[8\]](https://systems-analysis.info/wiki/%D0%A1%D0%B5%D1%82%D0%B5%D0%B2%D1%8B%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8#cite_note-ru-wiki-shortest-path-8)</sup>.
- **Свойства минимального остовного дерева (МОД)**:
- **Свойство разреза**: Для любого разреза графа ребро с минимальным весом, пересекающее разрез, принадлежит хотя бы одному МОД.
- **Свойство цикла**: В любом цикле графа ребро с максимальным весом не принадлежит ни одному МОД.

На этих свойствах основана корректность «жадных» алгоритмов Прима и Краскала<sup>[\[9\]](https://systems-analysis.info/wiki/%D0%A1%D0%B5%D1%82%D0%B5%D0%B2%D1%8B%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8#cite_note-ru-wiki-mst-9)</sup>.

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

- **Задача о кратчайшем пути**: Найти путь минимальной суммарной длины (веса) между двумя заданными узлами. Решается алгоритмом Дейкстры (для неотрицательных весов) или алгоритмом Беллмана-Форда (для произвольных весов)<sup>[\[8\]](https://systems-analysis.info/wiki/%D0%A1%D0%B5%D1%82%D0%B5%D0%B2%D1%8B%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8#cite_note-ru-wiki-shortest-path-8)</sup>.
- **Задача о максимальном потоке**: Определить максимально возможный поток от истока к стоку при заданных пропускных способностях дуг. Классический метод решения — алгоритм Форда — Фалкерсона<sup>[\[6\]](https://systems-analysis.info/wiki/%D0%A1%D0%B5%D1%82%D0%B5%D0%B2%D1%8B%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8#cite_note-ru-wiki-max-flow-6)</sup>.
- **Задача о минимальном остовном дереве**: Найти подграф, который соединяет все вершины сети и имеет минимальную суммарную стоимость рёбер.
- **Метод критического пути (CPM)**: В сетевых моделях планирования определить самую длинную последовательность работ, которая устанавливает минимально возможное время выполнения всего проекта. Работы на этом пути имеют нулевой резерв времени<sup>[\[10\]](https://systems-analysis.info/wiki/%D0%A1%D0%B5%D1%82%D0%B5%D0%B2%D1%8B%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8#cite_note-ru-wiki-cpm-10)</sup>.

## Примеры

- **Кратчайший путь**: Поиск оптимального маршрута навигационной системой между двумя точками на карте города, где города — узлы, а дороги — дуги с весами, равными длине или времени проезда.
- **Максимальный поток**: Определение максимальной пропускной способности сети трубопроводов, где насосные станции — узлы, а трубы — дуги с ограниченной пропускной способностью.
- **Минимальное остовное дерево**: Проектирование сети связи (например, прокладка оптоволоконного кабеля) для соединения нескольких городов с минимальной общей длиной кабеля.
- **Критический путь**: В проекте строительства дома, где работы (закладка фундамента, возведение стен, монтаж крыши) имеют заданную длительность и технологические зависимости, критический путь определяет минимальный срок завершения строительства. Любая задержка работы на этом пути приведёт к задержке всего проекта<sup>[\[10\]](https://systems-analysis.info/wiki/%D0%A1%D0%B5%D1%82%D0%B5%D0%B2%D1%8B%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8#cite_note-ru-wiki-cpm-10)</sup>.

## См. также

- [Исследование операций](https://systems-analysis.info/wiki/%D0%98%D1%81%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BE%D0%BF%D0%B5%D1%80%D0%B0%D1%86%D0%B8%D0%B9 "Исследование операций")
- [Метод критического пути (CPM)](https://systems-analysis.info/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BA%D1%80%D0%B8%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B3%D0%BE_%D0%BF%D1%83%D1%82%D0%B8_(CPM) "Метод критического пути (CPM)")
- [PERT](https://systems-analysis.info/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_PERT "Метод PERT")
- [Динамическое программирование](https://systems-analysis.info/wiki/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 "Динамическое программирование")
- [Линейное программирование](https://systems-analysis.info/wiki/%D0%9B%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 "Линейное программирование")

## Примечания

1.  <span id="cite_note-en-wiki-flow-network-1">↑ <sup>[1,0](https://systems-analysis.info/wiki/%D0%A1%D0%B5%D1%82%D0%B5%D0%B2%D1%8B%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8#cite_ref-en-wiki-flow-network_1-0)</sup> <sup>[1,1](https://systems-analysis.info/wiki/%D0%A1%D0%B5%D1%82%D0%B5%D0%B2%D1%8B%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8#cite_ref-en-wiki-flow-network_1-1)</sup> "Flow network". *Wikipedia*. <a href="https://en.wikipedia.org/wiki/Flow_network" class="external autonumber" rel="nofollow">[1]</a></span>
2.  <span id="cite_note-belgut-lec-2">[↑](https://systems-analysis.info/wiki/%D0%A1%D0%B5%D1%82%D0%B5%D0%B2%D1%8B%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8#cite_ref-belgut-lec_2-0) "Тема 10: Сетевые модели". Учебное пособие. Гомель: БелГУТ. <a href="https://elib.gsu.by/bitstream/123456789/4781/13/Тема10_Сетевые%20модели_net_lec.pdf" class="external autonumber" rel="nofollow">[2]</a></span>
3.  <span id="cite_note-ru-wiki-transport-net-3">[↑](https://systems-analysis.info/wiki/%D0%A1%D0%B5%D1%82%D0%B5%D0%B2%D1%8B%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8#cite_ref-ru-wiki-transport-net_3-0) "Транспортная сеть". *Википедия*. <a href="https://ru.wikipedia.org/wiki/Транспортная_сеть" class="external autonumber" rel="nofollow">[3]</a></span>
4.  <span id="cite_note-ru-wiki-cpm-pert-4">[↑](https://systems-analysis.info/wiki/%D0%A1%D0%B5%D1%82%D0%B5%D0%B2%D1%8B%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8#cite_ref-ru-wiki-cpm-pert_4-0) "Сетевое планирование". *Википедия*. <a href="https://ru.wikipedia.org/wiki/Сетевое_планирование" class="external autonumber" rel="nofollow">[4]</a></span>
5.  <span id="cite_note-mit-amp-ch8-5">[↑](https://systems-analysis.info/wiki/%D0%A1%D0%B5%D1%82%D0%B5%D0%B2%D1%8B%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8#cite_ref-mit-amp-ch8_5-0) Bradley S. P., Hax A. C., Magnanti T. L. (1977). *Applied Mathematical Programming*. Addison-Wesley. Ch.8: Network Models. <a href="https://web.mit.edu/15.053/www/AMP-Chapter-08.pdf" class="external autonumber" rel="nofollow">[5]</a></span>
6.  <span id="cite_note-ru-wiki-max-flow-6">↑ <sup>[6,0](https://systems-analysis.info/wiki/%D0%A1%D0%B5%D1%82%D0%B5%D0%B2%D1%8B%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8#cite_ref-ru-wiki-max-flow_6-0)</sup> <sup>[6,1](https://systems-analysis.info/wiki/%D0%A1%D0%B5%D1%82%D0%B5%D0%B2%D1%8B%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8#cite_ref-ru-wiki-max-flow_6-1)</sup> <sup>[6,2](https://systems-analysis.info/wiki/%D0%A1%D0%B5%D1%82%D0%B5%D0%B2%D1%8B%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8#cite_ref-ru-wiki-max-flow_6-2)</sup> "Задача о максимальном потоке". *Википедия*. <a href="https://ru.wikipedia.org/wiki/Задача_о_максимальном_потоке" class="external autonumber" rel="nofollow">[6]</a></span>
7.  <span id="cite_note-goldberg-tarjan-1990-7">[↑](https://systems-analysis.info/wiki/%D0%A1%D0%B5%D1%82%D0%B5%D0%B2%D1%8B%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8#cite_ref-goldberg-tarjan-1990_7-0) Goldberg A. V., Tardos É., Tarjan R. E. (1990). "Network Flow Algorithms". In: *Paths, Flows, and VLSI-Layout*. Springer. <a href="https://www.cs.cornell.edu/~eva/Network.Flow.Algorithms.pdf" class="external autonumber" rel="nofollow">[7]</a></span>
8.  <span id="cite_note-ru-wiki-shortest-path-8">↑ <sup>[8,0](https://systems-analysis.info/wiki/%D0%A1%D0%B5%D1%82%D0%B5%D0%B2%D1%8B%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8#cite_ref-ru-wiki-shortest-path_8-0)</sup> <sup>[8,1](https://systems-analysis.info/wiki/%D0%A1%D0%B5%D1%82%D0%B5%D0%B2%D1%8B%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8#cite_ref-ru-wiki-shortest-path_8-1)</sup> "Задача о кратчайшем пути". *Википедия*. <a href="https://ru.wikipedia.org/wiki/Задача_о_кратчайшем_пути" class="external autonumber" rel="nofollow">[8]</a></span>
9.  <span id="cite_note-ru-wiki-mst-9">[↑](https://systems-analysis.info/wiki/%D0%A1%D0%B5%D1%82%D0%B5%D0%B2%D1%8B%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8#cite_ref-ru-wiki-mst_9-0) "Минимальное остовное дерево". *Википедия*.</span>
10. <span id="cite_note-ru-wiki-cpm-10">↑ <sup>[10,0](https://systems-analysis.info/wiki/%D0%A1%D0%B5%D1%82%D0%B5%D0%B2%D1%8B%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8#cite_ref-ru-wiki-cpm_10-0)</sup> <sup>[10,1](https://systems-analysis.info/wiki/%D0%A1%D0%B5%D1%82%D0%B5%D0%B2%D1%8B%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8#cite_ref-ru-wiki-cpm_10-1)</sup> "Метод критического пути". *Википедия*. <a href="https://ru.wikipedia.org/wiki/Метод_критического_пути" class="external autonumber" rel="nofollow">[9]</a></span>