Общие сведения и понятия

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

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

Первоначальные идеи СПУ были разработаны в конце 50-х годов в США и реализованы в виде двух систем сетевого анализа – PERT (Program Evaluation and Review Technique – оценка программ и способов проверки) и CPM (Critical Path Method – метод критического пути).

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

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

С помощью следующих методов можно решить задачи сетевого планирования:

– алгоритмы построения деревьев;

– алгоритмы поиска кратчайших и оптимальных путей;

– алгоритмы поиска паросочетаний и покрытии;

– задача почтальона;

– задача коммивояжера;

– условия существования гамильтонова контура;

– задачи размещения, поиск центра и поиск медиан;

– сетевые графики, метод критического пути;

– алгоритм Форда-Фалкерсона;

– PERT – алгоритм.

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

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

Используются следующие обозначения:

N_i – для обозначения узла i;

A_ij – для обозначения ориентированной дуги, ведущей из N_i в N_j.

Сеть называется связной, если при любом разбиении множества узлов сети на подмножество найдется дуга A_ij или A_ji, где

Последовательность узлов и дуг сети называется цепью. Замкнутая цепь называется циклом.

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

В сети выделяют два специальных узла: источник – N_s, сток – N_t.

Потоком называется множество неотрицательных чисел X_ij, каждое соответствующее дуге сети и удовлетворяющее условиям:

(1)

(2)

где x_ij – поток по дуге A_ij,

неотрицательная V – величина потока.

Ограничение (1) выражает тот факт, что в каждый узел, кроме источника и стока приходит столько потока, сколько выходит (условие сохранения энергии), а условие (2) означает, что поток x_ij по дуге ограничен его пропускной способностью d_ij.

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

Например, задача нахождения величины максимального потока в сети является задачей линейного программирования с целевой функцией вида:

(3)

при ограничениях (1), (2).

Разрезом () называется множество всех дуг A_ij, для которых , либо наоборот.

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