Расчет временных параметров сетевого графика.

Путь в сети от исходного события до завершающего наз. полным путем, обознач. L. Продолжительность пути – время, необходимое для выполнения всех работ, лежащих на этом пути, обо­знач. t(L). Путь, имеющий наиб. продолжительность, наз. критическим. Работы, лежащие на критическом пути называют критическими работами. Время критического пути определяет время выполнения проекта, т.е. время, необходимое для завершения работ.

Расчет критического пути включ. в себя два этапа: 1) прямой проход – вычисления начинают с исходного события и про­должают до тех пор, пока не будет достигнуто завершающее событие. Для каждого соб-я определяется одно число, представляющее ранний срок его наступления. t_j=max{t_i+t_ij}. 2) обратный проход – вычисление начинают с завершающего события и продолжают пока не будет дос­тигнуто исходное событие. Для каждого события вычисл-ся поздний срок его наступления. Обратный проход выделяет критический путь.

Задача о максимальном потоке. Потоком сети наз.ф-цию m, которая каждому ребру данного графа ставит в соответствие неотриц. число m: E®R⁺È {0}.

Для " еÎ E m(e) определяет поток по ребру. Проблема максимального потока состоит в том, чтб. для задан­ной сети найти поток, кот. имеет максимальные из числа возможных цен. Ценой потока называется полный поток, приходящийся на сток.

Задача о кратчайшем пути. Пример (классический пример – задача коммивояжера).Найти кратчайший путь, проходящий через заданные пункты и возвращающийся в исходный пункт (все расстояния известны). Торговец, живущий в городе А, намерен посетить города В, С и D, расстояния между кот. известны. AB=11; AC=13; AD=17; BC=6; BD=9; CD=10.

Требуется указать кратчайший маршрут (циклический) из А через три других города.

ABDCA d=43

ACDBA d=43

ABCDA d=44

ACBDA d=45

ADCBA d=44

ADBCA d=45

ABDCA (ACDBA)

Гамильтонов цикл (проходит через каждую вершину ровно по одному разу) имеет всегда кратчайший путь. Любой подпуть кратчайшего пути явл. кратчайшим путем. Это свойство названо принципом оптимальности. Оно лежит в основе общего метода решения оптимизационных задач метода динамического программирования.

Алгоритм Дейкстры - алгоритм решения зад. о кратчайшем пути. Перед началом работы алгоритма все вершины считаются не маркированными, а в процессе работы алгоритма каждой вершине присваивается некоторое число.1) m(s)=0 m(x)=¥, " x¹ s 2) Пусть x – последняя маркированная вершина. Для нее рассмотрим все смешные с ней вершины. (x, y) – y – смешн. верш. 3)Для каждой смешной с x верш. находится М=m(x)+ m(x, y). Если m(y)> M, то m(y)=M 4)Если m(y)=¥, для всех немаркированных вершин, то заканчиваем работу, т.е. нет пути, ведущего из s в t. В прот. Случае маркируется та вершина, для кот. m(y) наименьшая (если их несколько, то произвольно выбираем одну из них). 5)Если y=t, то закончить работу, т.е. кратчайший путь из s в t найден.