§ 3.3. Математический аппарат теории графов

1. Понятие графа

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

Система методов СПУ – это система методов планирования и управления разработкой крупных народнохозяйственных и военных комплексов, научными исследования, конструкторской и технологической подготовкой производства, новых видов изделий, строительством и реконструкцией, капитальным ремонтом основных фондов, боевой подготовкой войск и повседневным руководством деятельности военных объектов путём применения сетевых графов.

В России работы по сетевому планированию начались в 60- годах прошлого века. Тогда методы СПУ нашли применение в строительстве и научных разработках. В дальнейшем они стали широко применяться и в других областях народного хозяйства.

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

Система СПУ позволяет: • Формировать календарный план реализации некоторого комплекса работ;

• Выявлять и мобилизовывать ресурсы времени, трудовые материальные и денежные ресурсы;

• Осуществлять управление комплексом работ по принципу «ведущего звена» с прогнозированием и предупреждением возможных срывов в ходе работ;

• Повышать эффективность управления в целом при чётком распределении ответственности между руководителями разных уровней и исполнителями работ.

Диапазон применения СПУ весьма широк: от задач, касающихся деятельности отдельных лиц, до проектов, в которых участвуют сотни организаций и десятки тысяч людей.

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

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

Работа – любой процесс или действие, сопровождающееся затратами времени и ресурсов на её выполнение. В качестве ресурсов выступают: люди, денежные средства, ЗИП и т.д. Ресурсы могут быть: однородными и неоднородными.

Р абота на графе отображается направленной дугой

k

t(k)

Рис. 3.6. Основные понятия сетевого графа

где I,J – номера начального и конечного событий k работы;

k – номер работы;

t(k) – ресурсы (количество людей).

Тр – ранний срок наступления событий.

Тп – поздний срок наступления события. R – резерв времени.

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

Событие – это результат выполнения одной или нескольких работ, не требует затрат времени и ресурсов (факт окончания). Событие на графе обозначается:

Ранний срок наступления события – максимальная длительность пути, ведущего от исходного события к данному. Тр(ij) = max{Тр(i) + tij}, где tij – продолжительность, проводимой работы между событиями

Поздний срок наступления события – это срок позднее которого событие наступить не должно. В противном случае увеличивается время всей операции. Тп(i) = min{Тп(j) - tij}, где Тп(j) – последующее событие.

Полный резерв времени работы Rп = Тп(j) – Тр(i) – tij.

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

Однако изменяются резервы последующих и предыдущих работ. Поэтому полным резервом распоряжается руководитель всей операции.

Свободный резерв: Rс = max {0, Тр(j) – Тп(i) – tij}. То есть это максимальное из двух значений: 1)0 и 2)Тр(j) – Тп(i) – tij.

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

Частные резервы (ЧР):

Rr' = Тп (j) – Тп(i) – tij – ЧР 1 вида.

Rr'' = Тр (j) – Тр(i) – tij – ЧР 2 вида.

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

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

Вероятностный сетевой граф – это граф, у которого одна или несколько работ случайны по продолжительности (tij - непостоянна). Стохастический сетевой граф – граф, у которого и топология и длительности работ случайны.

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

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

Длительность пути – сумма продолжительности составляющих его работ.

К ритический путь – путь наибольшей длительности (наибольших затрат ресурсов).

Основная задача теории и метода сетевого планирования состоит: в выработке конкретных направлений оптимизации плана операции (сетевого графа). Цель оптимизации – сокращение длительности критического пути, или минимизация общих затрат ресурсов.

1(2) 4(3)

3(7)

2(4) 5(4)

где:

Пути: Длительность пути

1) 0,1,3 Т(0,1,3) = 5.

2) 0,1,2,3 Т(0,1,2,3) = 13.

3) 0,2,3 Т(0,2,3) = 8.

 ресурсов (длительностей работ)

Достоинства метода сетевого планирования:

1. Возможность выявления узких мест.

2. Наглядность.

3. Отображение взаимосвязей отдельных этапов операции.

4. Прогнозируемость.

5. Возможность определения общих затрат ресурсов.

6. Выявление резервов.

7. Возможность реализации на ЭВМ.

8. Простота оптимизации.

Метод применяется при анализе учебно-боевых мероприятий противника для вскрытия оперативно-тактических нормативов состояний объектов в ходе условных боевых действий.

При построении сетевого графа необходимо соблюдать ряд правил:

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

2. В сетевом графе не должно быть «хвостовых» событий (кроме исходного), которым не предшествует хотя бы одна работа.

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

Л юбые два события должны быть непосредственно связаны не более чем одной работой (дугой, стрелкой).

правильно

4. В сети рекомендуется иметь одно исходное и одно завершающее событие. Если в составленной сети это не так, то добиться желаемого можно путём введения фиктивных событий и работ (фиктивные работы обозначаются на графе пунктирной линией).

5. Сетевой граф должен быть нумерованным. При этом для каждой работы номер её начального события меньше номера её конечного события.

6. Сетевой граф должен быть наглядным. Это правило требует избегать пересечения дуг (по возможности) и вводить минимально необходимое количество фиктивных работ и дополнительных событий.

Фиктивные работы вводятся и в ряде других случаев:

• П ри отражении зависимости событий, не связанных с реальными работами;

• При неполной зависимости работ;

• Для отражения реальных отсрочек и ожидания.