Задача о потоке наименьшей стоимости. Симплексный алгоритм.

Для того, чтобы можно было применить симплекс-алгоритм:

Симплексный алгоритм для данного типа задач содержит те же шаги, что и обычный симплекс-метод.

Особенности задачи учитываются в процессе вычисления.

Симплексный алгоритм строится на:

(Сумма всех потоков узла равна 0)

для небазисных дуг вычисляем:

для базисных:

30.Сетевое планирование. Построение сети.

Сетевое планирование предназначено для составления и оптимизации комплекса работ, входящих в проект, каждая выполненная работа характеризуется:

1) Временем выполнения

2) Привлеченными для ее выполнения ресурсами

В процессе оптимизации может оптимизироваться по времени выполнения, по объему используемых ресурсов, по равномерности использования ресурсов.

Наиболее известные методы анализа и оптимизации времени выполнения:

1) метод критического пути

2) PERT (program evaluation and review technique)

Проект представляет собой совокупность отдельных работ для каждой из которых известна длительность выполнения и отношение предшествования (последовательность выполнения работ)

Построение сети проекта

Исходно такой проект дается в виде таблицы:

Наименование работы | длительность | предшествующие работы.

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

Построение сети проекта основано на следующих правилах:

1) Каждая работа в проекте представляется одной и только одной

2) каждая работа идентифицируется двумя концевыми узлами.

Возможно 4 варианта структуры, конкретный вариант выбирают из удобства построения сети

3) Для поддержания правильных отношений предшествования перед включением в четь любого процесса необходимо ответить на следующие вопросы:

а) какая работа непосредственно предшествует текущей

б) какая работа должна выполняться после завершения текущей

в) какая работа конкурирует, т.е. выполняется совместно

31.Сетевое планирование. Метод критического пути.

Конечным результатом МКП является построение временного графика выполнения проекта. Для этого проводятся специальные вычисления:

1) Общая длительность выполнения проекта

2) Разделение множества работ, составляющих проект на критические и не критические

Работа называется критической, если она не обладает резервами времени начала и завершения.

Длительность проекта определяется суммарной длительностью критических работ.

У некритических работ есть резервы времени.

Определим событие как точку во временной оси, в которой завершается одна работа и начинается другая.

Dij – длительность процесса

TFi – раннее время наступления события i

TLi – позднее время наступления события i

При проходе вперед вычисляем самое раннее наступление, при проходе назад – самое позднее.

1->n

начальный шаг TF1≡0, проект начинается в нулевой момент времени.

Основонй шаг j.

Для узла j определяем узлы p,q,…,υ, непосредственно связанные с узлом j работами, для которых уже вычислены самые ранние времена наступления соответствующих событий.

Самое раннее время наступления j определяем как:

TFj = max{TFp + Dpj;TFq + Dqj;…TFυ + Dυj}

TFj по определению равна самому длинному пути от начала выполнения проекта до узла j

n->1:

Начальный шаг: TLn ≡ TFn, т.е.раннее и позднее время окончания проекта совпадают.

Основной шаг j: p,q,…,υ

Определяем такие узлы, которые непосредственно связаны с узлом j.

(j,p), (j,q)…(j, υ), для которых уже вычислены поздние времена наступления событий.

TLj = min{TLp + Djp;TLq + Djq;…TLυ + Djυ}

Работа считается критической ксли выполняются следующие условия:

1) TLi = TFi

2) TLj = TFj

3) TLj – Tli = TFj – Tfi = Dij

32.Сетевое планирование. Резервы времени. Временная диаграмма.

(Сначала надо построить таблицу времени выполнения работ)

Построение графика начинается с построения предварительного графика.

Для некритических работ необходимо рассмотреть резервы времени.

Различают общий и свободный резерв времени работ.

Общий запас времени работы (i,j) определяется как превышение над длительностью выполнения работы, интервала времени от самого раннего момента до наступления события i до самого позднего наступления события j.

Свободный запас времени работы (i,j) определяется как превышение длительности выполнения этой работы от самого раннего момента наступления события i до самого раннего момента наступления j.

Правило «красного флажка»

Для некритической работы (i,j):

а) Если FFij = TFij, то данная работа может выполняться в любое время внутри макс интервала (TFij, TLij) без нарушения отношения следования.

б) Если FFij < TFij, то без нарушения отношения следования работа может начинаться со сдвигом, не превышающим FFij относительно момента самого раннего наступления событий i.