Сетевые задачи

из "Математические исследования операций в экономике "

Неориентированным графом называется тройка (I,D,G), в которой I — непустое множество вершин, D — множество ребер и G — отображение, которое каждому ребру deD ставит в соответствие неупорядоченную пару вершин [г, /], где /, /е/. [c.121]
Граф (/, Д G) называется конечным, если множества / и D конечны. [c.121]
Путем длины п в ориентированном графе (/, D) называется упорядоченная последовательность различных дуг (d,, 4 — i 4 ) Для которых начало каждой последующей совпадает с концом предыдущей. Конечный путь, у которого начальная вершина совпадает с конечной, называется контуром. [c.122]
Для неориентированного графа аналогом понятия путь является цепь, а контура — цикл. [c.122]
Если две любые вершины неориентированного графа могут быть соединены цепью, то он называется связным. Ориентированный граф называется связным, если ему отвечает связный неориентированный граф. [c.122]
Связный неориентированный граф, не содержащий циклов, называется деревом. [c.122]
Если Y с D, а отображение GY является сужением отображения G на множество F, то граф (/, У, GY) называют частичным графом (реберным подграфом) графа (/, Д G). [c.122]
Рассмотрим задачу имеется конечный граф (/, Д G), каждой вершине i которого сопоставлено некоторое число bt, называемое интенсивностью вершины. Граф (/, Д G), вершинам которого сопоставлены значения интенсивностей 6,, будем называть сетью. Если Ъ О, то вершина i называется источником, если Ь( О, то — стоком, а если 6. = 0, то — нейтральной вершиной. Множество источников, стоков и нейтральных вершин обозначим соответственно /+, / , /°. [c.122]
Соотношение (3.11) означает, что для любой вершины сети разность выходящего и входящего потоков равна ее интенсивности. [c.123]
Приведенные формулировки задач специально даны в столь абстрактном виде, что позволяет подчеркнуть их универсальность. К очевидной сфере их приложения относится организация грузоперевозок в транспортной сети. В таких моделях вершины i трактуются как пункты, соединенные сетью дорог, и характеризуются потребностями в некотором продукте (bt 0) или его запасами (bt 0). Задачи определения плана, минимизирующего затраты на перевозки, которые с математической точки зрения полностью идентичны (З.П)-(ЗЛЗ), (3.14), также называют транспортными задачами в сетевой постановке. [c.123]
Для решения транспортной задачи в сетевой постановке (3.15)—(3.17) также может быть применен метод потенциалов, который является обобщением описанного выше метода потенциалов для транспортной задачи в матричной постановке. [c.125]
Поскольку задача (3.15)-(3.17) является частным случаем задачи линейного программирования, ее можно привести к канонической форме. При этом достаточно просто устанавливается, что ранг матрицы задачи равен т-1, где т — количество вершин в сети. Введем дополнительно еще некоторые понятия, используемые при описании свойств сетевых задач. [c.125]
Теперь дадим краткое описание схемы метода потенциалов для транспортной задачи в сетевой постановке. [c.125]
Получив очередную группу вершин с известными потенциалами, мы имеем возможность на основе (3.22)-(3.23) вычислить потенциалы для следующей группы смежных вершин и т. д., пока не будут определены все потенциалы. Возможность сделать это единственным образом вытекает из свойства отсутствия циклов у остова сети. [c.126]
Имея полную систему потенциалов, для всех дуг следует проверить условия критерия оптимальности (3.19)-(3.21). Если они выполняются, то текущий поток X(q — оптимальный и, следовательно, алгоритм завершен в противном случае — переходим к построению следующего улучшенного потока. [c.126]
В результате мы получаем новый допустимый поток x(d+l), полагаем номер текущей итерации q+l и переходим к п. 1°. [c.127]
В описанном алгоритме, как и в случае с матричной транспортной задачей, мы не гарантированы от возникновения вырожденного потока. Как уже упоминалось выше, такому потоку будет соответствовать несвязная опора. Для преодоления вырожденности рекомендуется включить в текущий план фиктивные компоненты с нулевыми объемами так, чтобы соответствующие им дуги дополняли опору до остова сети. Построенный таким способом план позволяет выполнить все действия, входящие в стандартную итерацию метода потенциалов. [c.127]
Построенная вспомогательная задача обладает очевидным допустимым невырожденным потоком, получаемым назначением объемов, равных интенсивностям вершин, по всем добавленным дугам. Решив вспомогательную задачу, мы либо получим допустимый поток для основной задачи, либо придем к выводу об отсутствии у нее допустимых планов. [c.128]

Вернуться к основной статье