Ю. Ю. Горюнов, Т. Ю. Горюнова, Д. В. Дружинин Теория и методы принятия решений Учебное пособие пенза 2010


НазваниеЮ. Ю. Горюнов, Т. Ю. Горюнова, Д. В. Дружинин Теория и методы принятия решений Учебное пособие пенза 2010
страница9/12
Дата публикации16.03.2013
Размер0.54 Mb.
ТипУчебное пособие
userdocs.ru > Математика > Учебное пособие
1   ...   4   5   6   7   8   9   10   11   12
^

4. Потоки в сетях


В этом разделе рассматриваются задача максимизации потока некоторого продукта по сети. Подобного рода задачи возникают при организации перекачки нефти или газа по трубопроводам, железнодорожного или автомобильного движения, передачи информации по сетям и т.д.

Приведём необходимые определения, формализующие соответствующие предметные области.

^ Сетью называется орграф без циклов с помеченными вершинами и дугами. Числа, которыми помечаются дуги сети, называются пропускными способностями дуг.

Примеры вершин сети: перекрёстки дорог, телефонные узлы, железнодорожные узлы, аэропорты, склады и т.д.

Примеры дуг сети: дороги, трубы, телефонные и железнодорожные линии и т.д.

Сеть, у которой существует ровно один исток3 и один сток4, называется транспортной сетью.

Пример транспортной сети:



Потоком в транспортной сети называется неотрицательная функция, определённая на множестве дуг сети, удовлетворяющая двум условиям:

  1. величина потока по каждой дуге не превосходит её пропускной способности;

  2. сумма потоков, входящих в каждую вершину сети, за исключением истока и стока, равна сумме потоков, выходящих из вершины.

^ Величина потока есть сумма потоков, выходящих из истока, или сумма потоков, входящих в сток сети.

Пример потока в транспортной сети:



Для любой транспортной сети величина потока имеет максимальное значение, которое определяется теоремой Форда – Фалкерсона, которая утверждает, что величина максимального потока в сети равна величине минимального разреза, где

разрезом транспортной сети называется такое множество дуг, удаление которых отделяет исток от стока.

минимальным разрезом транспортной сети называется разрез с минимальной пропускной способностью.

Пример. Транспортная сеть



имеет два разреза и . Пропускная способность первого разреза равна 11 (7+4), а второго – 9 (4+5), поэтому максимальный поток в этой транспортной сети равен 9 = min(11, 9). Этот максимальный поток указан в круглых скобках.
^

4.1. Алгоритм построения максимального потока в транспортной сети


Цепью, соединяющей исток A0 со стоком An, (или просто цепью) в транспортной сети называется последовательность дуг A0A1, …, An 1 An, в которой вершина Ai является началом i-ой дуги, а вершина Ai+1 – её концом (или, наоборот, Ai является концом i-ой дуги, а вершина Ai+1 – её началом).

Например, в следующей сети с заданным в скобках потоком



цепями являются последовательности AB, BC, CD и AC, CB, BD, причём в первой цепи направление дуги BC совпадает с направлением потока, а во второй цепи направление дуги CB противоположно направлению потока.

Определение. Дуга цепи называется допустимой дугой, если:

  1. направление дуги совпадает с направлением потока и поток по этой дуге меньше её пропускной способности;

  2. направление дуги противоположно направлению потока и поток по этой дуге больше нуля.

Цепь, соединяющая исток сети со стоком, называется увеличивающей, если все её дуги являются допустимыми.

Алгоритм построения максимального потока в сети

1. Если поток в сети не задан,

то считать поток нулевым.

2. Пока в сети есть увеличивающие цепи повторять:

  • взять любую увеличивающую цепь,

  • вычислить наименьшую разность  между пропускными способностями дуг этой цепи и потоками по этим дугам,

  • потоки по дугам, направление которых совпадает с направлением потока, увеличить на ,

  • потоки по дугам, направление которых противоположно направлению потока, уменьшить на ,

3. Если в сети нет увеличивающих цепей,

то максимальный поток построен,

Пример 1 (Поток в сети не задан). Построить максимальный поток для заданной транспортной цепи.

Данная сеть:

Сеть с нулевым потоком:





Решение.

1. Поток в сети не задан, считаем его нулевым.

2. Пока в сети есть увеличивающие цепи, повторяем:

Увеличивающая цепь: AB, BD, DF;

направление дуг совпадает с направлением потока,

 = min(9 – 0, 6 – 0, 10 – 0) = 6.

Новые потоки по дугам цепи:

AB: 0+6=6, BD: 0+6 = 6,

DF: 0+6=6:








Увеличивающая цепь: AB, BE, EF;

направление дуг совпадает с направлением потока,

 = min(9 – 6, 3 – 0, 7 – 0) = 3.

Новые потоки по дугам цепи:

AB: 6 + 3 = 9, BE: 0 + 3 = 3,

EF: 0 + 3 = 3:








Увеличивающая цепь: AC, CE, ED, DF;

направление дуг совпадает с направлением потока,

 = min(8 – 0, 4 – 0, 4 – 0, 10 – 6) = 4.

Новые потоки по дугам цепи:

AC: 0 + 4 = 4, CE: 0 + 4 = 4,

ED: 0 + 4 = 4, DF: 6 +4 = 10:





Увеличивающих цепей в сети нет, поэтому максимальный поток построен и он равен 13 = 9 + 4 = 10 + 3.

Пример 2 (Поток в сети задан). Построить максимальный поток для заданной транспортной цепи.

Сеть с заданным потоком:



Решение.

1. Поток в сети задан.

2. Пока в сети есть увеличивающие цепи, повторяем:

Увеличивающая цепь: AB, BD, DE, EF;

направление дуги DE противоположно потоку, направление остальных дуг совпадает с направлением потока,

 = min(9 – 6, 6 – 3, 4 – 2, 7 – 4) = 2.

Новые потоки по дугам цепи:

AB: 6 + 2 = 8, BD: 3 + 2 = 5,

DE: 2 – 2 = 0, EF: 4 + 2 = 6:








Увеличивающая цепь: AB, BD, DF;

направление дуг совпадает с направлением потока,

 = min(9 – 8, 6 – 5, 10 – 5) = 1.

^ Новые потоки по дугам цепи:

AB: 8 + 1 = 9, BD: 5 + 1 = 6,

DF: 5 + 1 = 6:








^ Увеличивающая цепь: AC, CE, EF;

направление дуг совпадает с направлением потока,

 = min(8 – 3, 4 – 3, 7 – 6) = 1.

Новые потоки по дугам цепи:

AC: 3+ 1 = 4, CE 3+ 1 = 4,

EF: 6 + 1 = 7:





Увеличивающих цепей в сети нет, поэтому максимальный поток построен и он равен 13 = 9 + 4 = 10 + 3.

Примечание. Обратите внимание на то, что сети в примерах 1 и 2 и максимальные потоки по ним совпадают, а потоки по некоторым дугам различаются, например, в примере 1 поток по дуге DF равен 10, а в примере 2 по этой же дуге равен 6.
1   ...   4   5   6   7   8   9   10   11   12

Похожие:

Ю. Ю. Горюнов, Т. Ю. Горюнова, Д. В. Дружинин Теория и методы принятия решений Учебное пособие пенза 2010 iconСписок вопросов к экзамену по дисциплине Системы принятия решений для групп ук-41, стс-41
Основные понятия теории принятия решений(теория принятия решений, сппр, манипулирование, альтернатива, критерии)
Ю. Ю. Горюнов, Т. Ю. Горюнова, Д. В. Дружинин Теория и методы принятия решений Учебное пособие пенза 2010 iconМетоды прогнозирования и принятия решений
Учебное пособие предназначено для студентов вузов, аспирантов, а также специалистов по прикладной экономике и прогнозированию
Ю. Ю. Горюнов, Т. Ю. Горюнова, Д. В. Дружинин Теория и методы принятия решений Учебное пособие пенза 2010 iconВопросы к экзамену по дисциплине «методы принятия управленческих решений»
Поведение человека в процессе принятия решений. Феномены поведения человека в процессе принятия решений
Ю. Ю. Горюнов, Т. Ю. Горюнова, Д. В. Дружинин Теория и методы принятия решений Учебное пособие пенза 2010 icon1. Предмет и задачи курса «Теория принятия решений»
В простейших случаях трудностей может и не быть, но в таких алгоритмически сложных областях, как принятие решений, управление, системное...
Ю. Ю. Горюнов, Т. Ю. Горюнова, Д. В. Дружинин Теория и методы принятия решений Учебное пособие пенза 2010 iconУчебное пособие Челябинск д анилова Ирина Валентиновна, Моцаренко...
Данилова Ирина Валентиновна, Моцаренко Наталья Васильевна. Общая экономическая теория: Учебное пособие. – Челябинск: Издательство...
Ю. Ю. Горюнов, Т. Ю. Горюнова, Д. В. Дружинин Теория и методы принятия решений Учебное пособие пенза 2010 iconВычислительная математика Учебное пособие
Мастяева И. Н., Семенихина О. Н. Численные методы: Учебное пособие / Московский международный институт эконометрики, информатики,...
Ю. Ю. Горюнов, Т. Ю. Горюнова, Д. В. Дружинин Теория и методы принятия решений Учебное пособие пенза 2010 iconУчебное пособие Челябинск
Законодательство России обязывает каждое предприятие вести бухгалтерский учет. Но для принятия управленческих решений существует...
Ю. Ю. Горюнов, Т. Ю. Горюнова, Д. В. Дружинин Теория и методы принятия решений Учебное пособие пенза 2010 iconЗадачи теории игр в экономике, финансах и бизнесе. Теория игр
Теория игр – раздел современной математики, изучающий математические модели принятия решений в т н конфликтных ситуациях
Ю. Ю. Горюнов, Т. Ю. Горюнова, Д. В. Дружинин Теория и методы принятия решений Учебное пособие пенза 2010 iconЗадачи теории игр в экономике, финансах и бизнесе. Теория игр
Теория игр – раздел современной математики, изучающий математические модели принятия решений в т н конфликтных ситуациях
Ю. Ю. Горюнов, Т. Ю. Горюнова, Д. В. Дружинин Теория и методы принятия решений Учебное пособие пенза 2010 iconЗадачи теории игр в экономике, финансах и бизнесе. Теория игр
Теория игр – раздел современной математики, изучающий математические модели принятия решений в т н конфликтных ситуациях
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2020
контакты
userdocs.ru
Главная страница