Задача о нахождении кратчайших путей в графе

Задача о нахождении кратчайших путей в графе

Сетевые модели (СМ) или методы сетевого планирования и управления (СПУ) – способ исследования и проектирования сложных систем, анализа и оптимизации процессов, состоящих из связанных подсистем или совокупности последовательных и взаимосвязанных работ и событий.

СМ позволяют дать ответы на следующие вопросы, стоящие перед руководителями разработок:

1. как наилучшим образом распределить исполнителей, чтобы выполнить разработку в срок;

2. как определить вероятное время выполнения разработки и выделить те работы, которые наиболее сильно влияют на срок завершения;

3. откуда взять ресурсы, если некоторые работы срываются;

4. как распределить ресурсы (рабочую силу, материалы, финансы), чтобы не было простоев

Математическое представление СПУ – это сетевая модель, базирующаяся на теории ориентированных графов. Орграф – множество вершин, соединенных направленными линиями (дугами).

Сетевой график – это отображение СМ в виде орграфа.

Рассмотрим СМ, основными элементами которой является событие, работа и путь.

9

3

12

8

15

0

4

6

15

7

2

6

5

3

4

1

0

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

Фиктивная работа – отображает логическую связь работ, не требует расхода времени и ресурсов; она констатирует, что событие 3 не может произойти, пока не свершится событие 1.

Ресурсы – материалы, сырье, оборудование, контингент исполнителей, необходимый для производства работы, финансовые средства.

Событие – факт завершения всех предшествующих работ и готовность к выполнению всех последующих.

Путь – последовательность работ в сети, в которой конечное событие любой работы совпадает с начальным событием следующей за ней работы. Путь кодируется в событиях, через которые он проходит (по рисунку: путь (3, 5, 6) иногда обозначается начальным и конечным событиями пути – L(3, 6)).

Могут быть определены следующие типы путей:

1. частичные: (1, 3, 5); (0, 1, 3); (0, 3); (3, 5, 6)

2. полные:

Продолжительность любого пути T(L) можно определить по формуле:

В нашем примере:

Путь, имеющий наибольшую продолжительность, называется критическим:

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

Факт обнаружения на сложной СМ критического пути и критических работ является достаточно важным результатом, позволяющим выявить узкие места проекта и сосредоточить на них максимальное внимание. Время выполнения проекта в целом не может быть меньше T_кр., поэтому первая задача при анализе СМ – выявление L_кр. и критических работ и поиск возможностей по сокращению их длительности. На этом базируется и в этом состоит сущность первого из сетевых методов – метода критического пути.

Рассмотрим сетевую модель на примере выполнения какой-нибудь работы.

Чтобы составить модель задачи, необходимо ответить на следующие вопросы:

1. наиболее раннее время начала работы;

2. наиболее раннее время окончания работы;

3. наиболее позднее время начала работы;

4. наиболее позднее время окончания работы;

5. критический путь;

6. длина критического пути;

7. запас времени на выполнение работы.

Существует два способа описания работы: табличный и графический.

Табличный способ:

Графический способ:

A

D

C

B

Пример.

Некоторая организация проводит строительные работы, в которых запланированы следующие виды работ:

Ответить на следующие вопросы:

1. сколько работ на критическом пути;

2. какова длина критического пути;

3. на сколько можно отложить работы E, чтобы это не повлияло на срок выполнения проекта;

4. на сколько можно отложить начало работы B, чтобы это не повлияло на срок выполнения проекта;

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