Сети и алгоритмы на сетях.

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

U – источник

W – конечная стадия

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

Зам. Последнее огранич-е не существенно, т.к., добавляя вершины и направл. ребра можно получить единственный источник или сток. Изображение такого графа наз. сетью планирования проекта, или сетевым графиком, или сетевой моде­лью. В основе построения сетевого графика лежат три основных понятия: работа - изображается ребром (деятельность), событие - вершина (задача), путь. Работа – любой активный процесс, требующий определенных затрат и ведущий к постижению постав­ленной цели.1) действительная – любой активный процесс, требующий затрат труда, времени и матер. ресур­сов. 2) ожидание – пассивный процесс, не требующий затрат труда и матер. ресурсов, но требующ. затрат времени. 3) фиктивная – условная зависимость между событиями, не требующими затрат времени и ре­сурсов. Событие – результат выполнения работы. 1) исходное – начало выполнения проекта; исходному событию не предшествуют никакие ра­боты. 2) завершающее – достижение конечной цели проекта; не имеет следующих за ним работ. 3) про­межуточное – результат выполнения одной или неск-х работ, позволяющих приступить к выполнению последующих работ. Промежуточ. соб. не сопровождается затратами труда, матер. ресурсов и времени. На сетевом графике событие изображаются кружком, в кот. проставляется число – шифр данного события. Любая стрелка на сетевом графике соединяет только две вершины и отражает процесс перехода от одного события к другому. Поэтому любая работа м/б зашифрована парой чисел, соответствующих предыдущему и последующему событию.Время, необх. для выполнения работы i, j, наз. продолжительностью работы t_{i, j}.

t₁₃=10; t₁₂=5.

Основные правила построения сетевого графика. 1. Сеть изображают слева направо, т.е. каждая стрелка рисуется по возможности так, чтб. ее конец находился правее начала и горизон­тально.2. Два соседних события могут объединяться лишь одной работой. Для изображения параллельных работ вводятся промежуточные события и фиктивные работы. (Фиктивная работа изображается пунктирной стрелкой, никакого весового коэф-та не пишется). 3. Следят за тем, чтб. во все вершины, кроме исходного события, входила по меньшей мере одна стрелка. 4. Следят за тем, чтб. из всех вершин сети, кроме завершающего события, выходили стрелки. 5. Следят за тем, чтб. в сетевом графике не было тупиков и не образовывалось циклов. Для правильной нумерации событий поступают следующим образом: исходному событию дают шифр – 1(или 0); вычеркиваются все выходящие из него работы; выбирается вершина, в кот-ю не входит ни одна стрелка, этой вершине присваивается следующий номер; вычеркиваются работы, выходящие из второго события и т.д.