СЕТЕВОЕ ПЛАНИРОВАНИЕ И УПРАВЛЕНИЕ

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

Построение минимального остовного дерева сети

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

Рассмотрим процедуру построения минимального остовного дерева.

Введем обозначения:

X={ x₁, x₂, …, x_n } - множество узлов сети;

C_k - связное множество узлов сети, соединенных алгоритмом после выполнения k-й итерации;

- множество узлов сети, не соединенных с узлами множества C_k после выполнения k-й итерации;

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

1. Взять произвольный узел сети x_i, C₁={x_i}, = X\{x_i};

2. Выбрать из оставшихся узлов узел x_j, ближайший к множеству узлов C₁, C₂={ x_i, x_j }, = X\{ x_i, x_j };

3. Выбрать из множества узел, ближайший к узлам множества C₂, включить его в множество C₂ и исключить из множества .

За конечное число шагов будут обработаны все узлы сети и построено минимальное остовное дерево. C_n=X, =f.

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

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

Введем следующие обозначения:

x₁ - исходный узел;

x_n - узел назначения;

d_ij - расстояние на сети между смежными узлами x_i и x_j;

U_j - кратчайшее расстояние от узла x₁ до узла x_j, U₁=0.

Алгоритм нахождения кратчайшего пути состоит в последовательном нахождении значений U_j для каждого узла от исходного узла до узла назначения. Значение U_j для каждого узла рассчитывается по формуле

={ U_i + d_ij }.

Процедура заканчивается, когда получено значение U_n для узла назначения.

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

Сетевое планирование

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

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

Фиктивная работа - это связь между результатами работ (событиями), не требующая затрат времени и ресурсов.

Событие - это результат (промежуточный или конечный) выполнения одной или нескольких предшествующих работ.

Путь - это любая непрерывная последовательность (цепь) работ и событий.

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

При построении сетевых моделей необходимо соблюдать следующие правила:

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

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

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

4. В сети не должно быть промежуточных событий, которым не предшествует хотя бы одна работа.

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

Из исходного события 1 вычеркивают все исходящие из него работы, на оставшейся сети вновь находят событие, в которое не входит ни одна работа. Этому событию дается номер 2. Затем вычерчивают работы, выходящие из события 2, и вновь находят на оставшейся части сети событие, в которое не входит ни одна работа, ему присваивается номер 3, и так продолжается до завершающего события.

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

Рассмотрим прямой проход.

t_i ^р.н - ранний срок начала всех операций, выходящих из события i.

Если i = 0, то t₀ ^{p. н} = 0.

t_j ^р.н - ранний срок начала всех операций, входящих в j.

t_j ^р.н = max { t_i ^p.н + t_ij } для всех (i, j),

где t_ij - продолжительность операции (i, j).

Различают два вида резервов времени: полный резерв (r_п) и свободный резерв (r_св).

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

r _п = t_ij ^п.н - t_i ^p.н.

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

r_{св ij} = t_j ^p.н - t_i ^р.н - t_ij.

Используя результаты вычислений при прямом и обратном проходах, можно определить операции критического пути. Операция (i, j) принадлежит критическому пути, если она удовлетворяет условиям:

t_i ^р.н = t_i ^п.о,

t_j ^р.н = t_j ^п.о,

t_j ^р.н - t_i ^р.н = t_j ^п.о - t_i ^п.о = t_{i j}.

Стоимостные факторы при реализации сетевого графика учитываются путем определения зависимости "затраты - продолжительность" для каждой операции. При этом рассматриваются прямые затраты, а косвенные типа административных или управленческих расходов не принимаются во внимание.

Определив зависимость "затраты - продолжительность", для всех операций сети принимают нормальную продолжительность. Далее рассчитывается сумма затрат на все операции сети при этой продолжительности работ. На следующем этапе рассматривается возможность сокращения продолжительности работ. Этого можно достичь за счет уменьшения продолжительности какой-либо критической операции, только критические операции и следует подвергать анализу.

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