Презентация на тему: Математические методы (Исследование операций, Методы оптимизации) Задача о

Реклама. Продолжение ниже
Математические методы (Исследование операций, Методы оптимизации) Задача о максимальном потоке
Актуальность
Постановка задачи
Постановка задачи
Основные определения
Пример
Переход к алгоритму
Идея алгоритма нахождения максимального потока
Шаги 1-3
Шаги 4-5
Шаг 5. Решение
Расчетный пример
Расчетный пример
Аналогично для пути 1-2-3-4-5
Аналогично для пути 1-2-3-4-5
Аналогично для пути 1-2-3-2-5
Аналогично для пути 1-2(-3-2)-5
Аналогично для 1-3-2-5
Аналогично для 1-3-2-5 и 1-4(-3-4)-5
Решение
Итог
1/21
Средняя оценка: 4.6/5 (всего оценок: 50)
Код скопирован в буфер обмена
Скачать (2765 Кб)
Реклама. Продолжение ниже
1

Первый слайд презентации: Математические методы (Исследование операций, Методы оптимизации) Задача о максимальном потоке

Изображение слайда
1/1
2

Слайд 2: Актуальность

Изображение слайда
1/1
3

Слайд 3: Постановка задачи

Рассмотрим сеть трубопроводов для транспортировки сырой нефти от буровых скважин до нефтеперегонных заводов. Для перекачки нефти предусмотрены магистральные насосные станции. Каждый сегмент трубопровода имеет свою пропускную способность. Сегменты трубопровода могут быть как однонаправленные (осуществляют перекачку нефти только в одном направлении), так и в двунаправленные.

Изображение слайда
1/1
4

Слайд 4: Постановка задачи

В однонаправленных сегментах положительная пропускная способность предполагается в одном направлении и нулевая - в другом. Как определить оптимальную пропускную способность (т.е. максимальный поток) между нефтяными скважинами и нефтеперегонными заводами? Для ребра (i, j), где i < j, используем запись (Cij,Cji) для представления пропускных способностей в направлениях i->j и j->i соответственно. Во избежании недоразумений на схеме сети Cij будем располагать на ребре (i, j) ближе к узлу i, а Cji ближе к узлу j, как показано на рис унке:

Изображение слайда
Изображение для работы со слайдом
1/2
5

Слайд 5: Основные определения

Разрез определяет множество ребер, при удалении которых из сети полностью прекращается поток от источника к столу. Пропускная способность разреза равна сумме пропускных способностей "разрезанных" ребер. Среди всех разрезов сети разрез с минимальной пропускной способностью определяет максимальный поток в сети.

Изображение слайда
1/1
6

Слайд 6: Пример

Рассмотрим сеть, показанную на рис. 3. На этом рисунке при обозначении пропускных способностей двунаправленных ребер придерживались соглашения, принятого ранее (рис. 2). Например, для ребра (3, 4) пропускная способность в направлении 3 -> 4 равна 10, а в направлении 4 -> 3 равна 5.

Изображение слайда
Изображение для работы со слайдом
1/2
7

Слайд 7: Переход к алгоритму

Вывод, который можно сделать из этих трех разрезов, заключается в том, что максимальный поток не может превышать 60 единиц ( минимальное число). Но мы не можем сказать, какой максимальный поток на самом деле, так как не перебрали все возможные разрезы сети. К сожалению, перебор всех разрезов является непростой задачей. Поэтому для определения максимального потока в сети не используются алгоритмы, основанные на полном переборе разрезов.

Изображение слайда
1/1
Реклама. Продолжение ниже
8

Слайд 8: Идея алгоритма нахождения максимального потока

Идея данного алгоритма состоит в нахождении сквозных путей с положительными потоками от источника к стоку. Рассмотрим ребро (i, j) с (начальной) пропускной способностью (Cij,Cji). В процессе выполнения алгоритма части этих пропускных способностей "забираются" потоками, проходящими через данное ребро, в результате каждое ребро будет иметь остаточную пропускную способность. Будем использовать запись (cij, cji) для представления остаточных пропускных способностей. Сеть, где все ребра имеют остаточную пропускную способность, назовем остаточной. Для произвольного узла j, получающего поток от узла i, определим метку [aj, i], где aj - величина потока, протекающего от узла j к узлу i. Алгоритм нахождения максимального потока предполагает выполнение следующих действий.

Изображение слайда
1/1
9

Слайд 9: Шаги 1-3

Изображение слайда
Изображение для работы со слайдом
1/2
10

Слайд 10: Шаги 4-5

Изображение слайда
Изображение для работы со слайдом
1/2
11

Слайд 11: Шаг 5. Решение

Изображение слайда
Изображение для работы со слайдом
1/2
12

Слайд 12: Расчетный пример

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
Изображение для работы со слайдом
1/4
13

Слайд 13: Расчетный пример

Изображение слайда
1/1
14

Слайд 14: Аналогично для пути 1-2-3-4-5

Изображение слайда
Изображение для работы со слайдом
1/2
Реклама. Продолжение ниже
15

Слайд 15: Аналогично для пути 1-2-3-4-5

Изображение слайда
Изображение для работы со слайдом
1/2
16

Слайд 16: Аналогично для пути 1-2-3-2-5

Изображение слайда
Изображение для работы со слайдом
1/2
17

Слайд 17: Аналогично для пути 1-2(-3-2)-5

Изображение слайда
1/1
18

Слайд 18: Аналогично для 1-3-2-5

Изображение слайда
1/1
19

Слайд 19: Аналогично для 1-3-2-5 и 1-4(-3-4)-5

Изображение слайда
Изображение для работы со слайдом
1/2
20

Слайд 20: Решение

Изображение слайда
1/1
21

Последний слайд презентации: Математические методы (Исследование операций, Методы оптимизации) Задача о: Итог

Изображение слайда
1/1
Реклама. Продолжение ниже