Планирование на сети

Содержание

 

Введение…………………………………………………………………………5

1. Основные понятия сетевого планирования и управления…………….…..7

0. Основные параметры сетевой модели системы планирования и управления………………………………………………………………….7

Правила построения сетевых графиков. Характеристики элементов сетевой модели…………………………………………………………......9

2. Методы сетевого планирования…………………………………………..15

0. Метод критического пути………………………………………………..15

2.2 Метод оценки и  пересмотра планов (ПЕРТ, PERT)……………………..17

2.3 Метод графической оценки и анализа (GERT)…………………………..19

3. Численная реализация задачи сетевого планирования…………………...20

Заключение…………………………………………………………………......26

Список использованной литературы………………………………………….28

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

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

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

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

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

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

При сетевом планировании производства:

- видна цепочка работ,  от которых зависит своевременное  выполнение проекта,

- есть простые математические зависимости, позволяющие делать расчёты,

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1.Основные  понятия сетевого планирования  и управления.

1. Основные параметры сетевой модели системы планирования и управления.

 

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

Графом называется совокупность двух конечных множеств:

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

Граф называется связным, если для любых двух его вершин существует путь, их соединяющий; в противном случае граф называется несвязным.

В экономике  чаще всего используются два вида графов: дерево и сеть.

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

Сеть — это ориентированный конечный связный граф, имеющий начальную вершину (источник) и конечную вершину (сток). Таким образом, сетевая модель представляет собой граф вида «сеть».

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

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

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

Основные понятия сетевой  модели:

1. событие;
2. работа;
3. путь.

Работа характеризует материальное действие, требующее использования ресурсов, или логическое, требующее лишь взаимосвязи событий. При графическом представлении работа изображается стрелкой, которая соединяет два события. Она обозначается парой заключенных в скобки чисел (i,j), где i — номер события, из которого работа выходит, а j — номер события, в которое она входит. Работа не может начаться раньше, чем свершится событие, из которого она выходит. Каждая работа имеет определенную продолжительность t (i,j)-Например, запись t (2,5) = 4 означает, что работа (2,5) имеет продолжительность 5 единиц.

На рис. 1 графически представлена сетевая модель, состоящая из 11 событий  и 16 работ, продолжительность выполнения которых указана над работами.

 

 

 

 

 

 

 

 

 

 

 

«Рисунок 1 –  Пример сетевой  модели».

Событиями называются результаты выполнения одной или нескольких  работ.  Они не  имеют протяженности во времени. Событие свершается в тот момент, когда оканчивается последняя из работ, входящая в него. События обозначаются одним  числом  и при графическом   представлении сетевая модель изображаются кружком (или иной геометрической фигурой), внутри которого проставляется его порядковый номер (i = 1, 2, ..., n).

В сетевой модели имеется начальное событие (с номером 1), из которого работы только выходят, и конечное событие (с номером N), в которое работы только входят.

Путь — это цепочка следующих друг  за другом  работ, соединяющих начальную и конечную вершины, например, в приведенной выше модели путями являются L₁ = (1, 2, 3, 7, 10, 11), L₂ = (1, 2, 4, 6, 11) и др.

Продолжительность пути определяется суммой продолжительностей составляющих его работ. Путь, имеющий максимальную длину, называют критическим и обозначают L_Kp, а его продолжительность — tкр. Работы, принадлежащие критическому пути, называются критическими. Их несвоевременное выполнение ведет к срыву сроков всего комплекса работ.

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

 

 

2.  Правила построения сетевых графиков. Характеристики элементов сетевой модели.

 

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

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

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

2) в сети не должно быть событий, в которые не входит ни одной работы, если только эти события не являются для данной сети исходными.

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

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

4) в сети не должно быть работ, имеющих одинаковые шифры, то есть работ с общими начальным и конечным событиями.

Для любого события i сетевая модель позволяет рассчитать наиболее ранний из возможных сроков его свершения tp(i) и наиболее поздний из допустимых сроков его свершения tп(i) (или для кратности: ранний и поздний сроки свершения события i).

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

Обозначив максимальный предшествующий событию i  путь через   L(I-i)max, получим

 

tp(i)=t[L(I-i)max].                                                                                               (1)

 

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

Обозначим максимальный следующий  за событием i путь через L(i-C)max, получим

 

tп(i)=tкр-t[L(i-C)max].                                                                                       (2)

 

Зная tp(i) и tп(i) для всех событий сети, можно для любой работы (i, j) определить:

1. самый ранний из возможных сроков начала работы (i,j), или, кратко, ранний срок начала tр.н(i,j);
2. самый поздний из допустимых сроков начала работы, или поздний срок начала tп.н(i,j);
3. самый ранний из возможных сроков окончания работы, или ранний срок окончания tр.о(i,j);
4. самый поздний из допустимых сроков окончания работы, или поздний срок окончания tп.о(i,j).

Ранние сроки  начала работ определяются ранними  сроками свершения их начальных  событий, а поздние сроки окончания  работ – поздними сроками свершения  их конечных событий. Поэтому, зная продолжительность  работы t(i,j), указанные выше параметры определить по следующим формулам:

 

tр.н(i,j) = tp(i),                                                                                                     (3)

tп.н(i,j) = tп(j) – t(i,j),                                                                                          (4)

tp.o(i,j) = tp(i) + t(i,j),                                                                                          (5)

tп.о(i,j) = tп(j).                                                                                                     (6)

Для всех работ  критического пути

 

tр.н(i,j) = tп.н(i,j) и tр.о(i,j) = tп.о(i,j),                                                                (7)

 

так как начальное и конечное события этих работ находятся на критическом пути, а следовательно,

 

tp(i) = tп(i) = tп(j) – t(i,j) и tп(j) = tp(j) = tp(i) + t(i,j).                                                (8)