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

^ 4. Потоки в сетях В этом разделе рассматриваются задача максимизации потока некоторого продукта по сети. Подобного рода задачи возникают при организации перекачки нефти или газа по трубопроводам, железнодорожного или автомобильного движения, передачи информации по сетям и т.д. Приведём необходимые определения, формализующие соответствующие предметные области. ^ Сетью называется орграф без циклов с помеченными вершинами и дугами. Числа, которыми помечаются дуги сети, называются пропускными способностями дуг. Примеры вершин сети: перекрёстки дорог, телефонные узлы, железнодорожные узлы, аэропорты, склады и т.д. Примеры дуг сети: дороги, трубы, телефонные и железнодорожные линии и т.д. Сеть, у которой существует ровно один исток3 и один сток4, называется транспортной сетью. Пример транспортной сети: Потоком в транспортной сети называется неотрицательная функция, определённая на множестве дуг сети, удовлетворяющая двум условиям: величина потока по каждой дуге не превосходит её пропускной способности; сумма потоков, входящих в каждую вершину сети, за исключением истока и стока, равна сумме потоков, выходящих из вершины. ^ Величина потока есть сумма потоков, выходящих из истока, или сумма потоков, входящих в сток сети. Пример потока в транспортной сети: Для любой транспортной сети величина потока имеет максимальное значение, которое определяется теоремой Форда – Фалкерсона, которая утверждает, что величина максимального потока в сети равна величине минимального разреза, где разрезом транспортной сети называется такое множество дуг, удаление которых отделяет исток от стока. минимальным разрезом транспортной сети называется разрез с минимальной пропускной способностью. Пример. Транспортная сеть имеет два разреза и . Пропускная способность первого разреза равна 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. Пока в сети есть увеличивающие цепи повторять: взять любую увеличивающую цепь, вычислить наименьшую разность  между пропускными способностями дуг этой цепи и потоками по этим дугам, потоки по дугам, направление которых совпадает с направлением потока, увеличить на , потоки по дугам, направление которых противоположно направлению потока, уменьшить на , 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.

Похожие:

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