Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Задача о максимальном потоке в сети, алгоритм Форда-Фалкерсона.

Задача о максимальном потоке в сети. Исследуется оптимальное значение функции потока, который протекает в заданной ориентированной сети от источника S к стоку T. Рассмотрим простейшую задачу, которая называется однопродуктовый поток, по сети протекает поток, однородный (вода, информация, электричество и т.д.).

Пусть множество {bi} – множество всех узлов, связанных с узлом i дугами, направленными к узлу i.

Множество {ai} – множество узлов, связанных с i дугами к узлу i.

Также задана функция{fij} – целочисленная, определенная на множестве дуг сети, и называется потоком в сети. В том случае, если выполнены следующие условия:

fij³0 "(I,j)ÎA

S_j£|ai| fij - S _j£|bi| fij = 0 "iÎN, i¹S, i¹T

fij£uij "(i,j)ÎA, uij- пропускная способность дуги (i,j)

fij – объем продукта который протекает по дуге (i,j).

Поскольку пропускная способность дуги конечна, то и всей сети тоже конечна. Надо найти такой маршрут, что поток от истока к стоку будет максимален.

Алгоритм Форда-Фалкерсона.

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

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

Пропускная способность разреза – это сумма пропускной способности дуг входящих в разрез.

Согласно этой теореме мы можем построить и рассмотреть все разрезы и найти минимум – это максимум пропускной способности данной сети. Но по этой теореме мы не можем найти все потоки проходящие по дугам сети. Используются пометки для указания величины потока и его источник.

Например, если из вершины i в j передается qj единиц потока и эта добавка вызывает увеличение потока по дуге, то узлу j приписывается пометка [qj,i], если же величина потока qj вызывает уменьшение потока по этой дуге, то узлу j присваивается пометка [-qij,i].

[qj,i] – прямая дуга; [-qj,i] – обратная дуга.

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

Алгоритм:

На первом этапе источнику присваивается пометка бесконечность. На этом этапе все остальные узлы не помечены. Постараемся расставить пометки дойдя до стока T®S.

1. Дойдя до стока ему приписываем пометку [qij,k].

2. Путь потока от источника будет найден и поток для каждой дуги этого пути увеличится на величину qt.

3. Дойдя до стока мы начнем расставлять пометки сначала, при этом необходимо следить, чтобы остаточная пропускная способность всех дуг не была превышена.

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

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

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

1. Планировать работы над проектом, предвидеть возможные задержки и затруднения.

2. Планировать завершение работ в поставленные сроки

3. Координировать и контролировать выполнение работ с целью соблюдения графика.

Данные задачи могут решаться при имеющихся ограничениях на используемые ресурсы. В этом случае, к проектам добавляется следующее:

1. Необходимо устанавливать последовательность и сроки использования ресурсов в течении всего периода осуществления проекта.
2. Проведение динамического регулирования сроков начала каждой работы.
3. Осуществлять оптимальное распределение средств на выполнение проектов.
4. Достигать компромисса между затратами и сроками.

Рассмотрим задачу расчета графика работ, при отсутствии ресурсных ограничений. Будем рассматривать сетевую модель в терминах работы, где для каждой работы b_j задана ее продолжительность t_j, а также множество дуг D(I,j), которые связывают с ней предшевтсующие ей работы. Т.е. узлы в сети – это собтие, которое представляет собой моменты начала одной или нескольких работ(дуги – сами работы). Причем, в данном случае, желательно строить граф(сеть) таким образом, чтобы длина дуги в некотром маштабе, соотвтетвовала времени соотв. работы

Продолжительность работ должна соответствовать чему-то. Что-то, обозначающий продолжительность работы. Событие i, событие j.
Пусть все работы начинаются в момент времени t=0. Требуется для каждой работы определить моменты ее начала и окончания. Алгоритм решения следующий:

1. Присваеваем Ti^N=0

2. Вычислем окончание каждой работы. T_t^o=T_i^N+t_i

3. S=false

4. Просматриваем весь список работ

a. Для каждой работы, рассчитываем начало ее работы, как максимум двух величин
T_i^N=max(T_i^N, T_k^O)
T_i^N= T_k^O s=true

b. T_i^O = T_i^N +t_i

5. Если s=true =>п.3, иначе конец.

Смысл алгоритма в следующем: На всех итерациях получаем начало и окончание тех работ, которые не имеют предшествующих. На следующей итерации, вычисляется значение моментов начала и окончания работ, которые связаны только с начальными работами.
На всех следующих итерациях, происходит расчет моментов начала и окончания работ, связанных с найденными предыдущими – это и есть длина критического пути. Т.е. сумма всех длин работ – сумма всех видов работ, лежащих на максимальном пути в сети от начала до конца. Найденный путь называется критическим, поскольку он вычисляет минимальную продолжительность всего проекта,и все работы, лежащие на этом крит. Пути являются также критическими. Любое увеличение этих работ или любая задержка в их выполнении увеличивает общее время выполнения проекта. У этих критических работ полностью отсутствует какой либо резерв времени. Для остальных работ, не лежащих на критическом пути может существовать данный резерв времени.
Пробуем их найти.
Сроки начала и окончания работ – вычисленное предположение, что они начинаются в наиболее ранний возможный момент времени называется ранними сроками начала и окончания работ. Их будем обозначать T_i^RN - раннее начало T_i^RО – раннее окончание. Сроки работ, вычисленные из предположения, что они начинаются в наиболее поздний допустимый момент времени – поздние сроки начала и окончания работ T_i^PN –позднее начало, T_i^PO – позднее окончание. Разность между наиболее ранними и наиболее поздним началом/окончанием – называется полный резерв времени. R_i. Наличие резерва времени для некоторых работ, позволяет их откладывать в пределах этого резерва, без изменения сроков выполнения этого проекта.

Время выполнения каждой работы – ось проекции.

(отдельное фото)

Для того, чтобы показать посл. Работ, ставят дефективные дуги. Например, 4 работа только после окончания 3-й. последовательно вычисляются все временные работы. Раннее начало работы.

T₁^RN=0; T₂^{RN =} T₁^RN +5=5; T₃^{RN =} T₁^RN +3=3;

T₄^RN =10; T₅^RN = 13; T₆^RN =19; T₇^RN = T₈^RN +2=25.

Расчет происходит от конца к началу. В этом случае, наиболее позднее допустимое событие, непоследственно предшествующий этому событию вычисляется по этой формуле: T_i^PN = T_k^PN –mint_i
T_n^PN ,i=n

T_i^PN = min_j>i(T_j^PN-b_i),1<=i<=n-1.

Можно записать резерв времени для каждой из работ:

1. R1 = T₁^PN - T₁^RN = 0

2. R2 = 7-5=2

3. R3 = 4-3=1

4. R4 = 10-10 = 0

5. R5 = 14-13 = 1

6. R6 = 19-19=0

7. R7 = 0

8. R8 = 0