Расчётные параметры сетевого графика

Для событий рассчитывают три характеристики: ранний и поздний срок совершения события, а также его резерв.

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

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

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

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

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

Ранний срок начала -

Ранний срок окончания -

Поздний срок окончания -

Поздний срок начала -

Полный резерв времени -

Независимый резерв -

где

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

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

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

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

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

Рассмотрим последний указанный способ для расчета СМ, которая представлена на Рис. 1; результаты расчета приведены в табл. 1

Рассчитаем среднюю продолжительность выполнения работ и полную дисперсию для критического пути. Оценим вероятность выполнения всего комплекса работ за 35 дней, за 30 дней. Оценим максимально возможный срок выполнения всего комплекса работ с надежностью 95%.

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

Решение. Результаты расчета сведены в таблице.

К_пр	(i, j)	t(i, j)	t_p_н(i, j)= tp	t_po(i, j)	t_n_н(i, j)	t_no(i, j)= t_n	R_n	R_н	К_н
				5=4+3	6=7-3
	(1, 2)
	(2, 3)								0, 67
	(2, 4)
	(2, 5)								0, 44
	(3, 7)								0, 67
	(4, 5)
	(4, 6)								0, 47
	(4, 9)								0, 67
	(5, 8)								0, 78
	(5, 10)
	(6, 9)								0, 38
	(6, 11)								0, 38
	(7, 10)								0, 67
	(8, 10)								0, 78
	(9, 10)								0, 67
	(10, 11)

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

а дня.

Вычислим коэффициент напряженности по формуле:

где продолжительность отрезка рассматриваемого пути, совпадающего с критическим путем.

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

напряженные

подкритические

резервные

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

При расчете этих показателей целесообразно пользоваться графиком СМ. Итак, для работ критического пути (1, 2), (2, 4), (4, 5), (5, 10), (10, 11) . Для других работ:

= 1 - (6: (33 - (6 + 9)) = 1- 0, 33 = 0, 67,

= 1 - (5: (33 - (6 + 3 + 9)) = 1 - 0, 33 = 0, 67,

= 1 - (2: (33 - (6 + 3 + 6 + 9)) = 1 - 0, 22 = 0, 78 и т.д.

В соответствии с результатами вычислений для остальных работ, которые представлены в последней графе табл.1, можно утверждать, что оптимизация сетевой модели возможна в основном за счет двух резервных работ: (6, 11) и (2, 5).

Рассчитаем среднюю продолжительность выполнения работ и полной дисперсии для критического пути. Имеем:

……………………………….

Работа	Продолжительность	Ожидаемая	Дисперсия
			Продолжительность
(1.2)		7.5		0.25
(2.3)		6.5		0.25
(2.4)				1.00
(2.5)		5.5		0.25
(3.7)	0.5	3.5		0.36
(4.5)		7.5		0.25
(4.6)		5.5		0.25
(4.9)				1.00
(5.8)		4.5		0.25
(5.10)				1.00
(6.9)				0.00
(6.11)				1.00
(7.10)				1.00
(8.10)				1.00
(9.10)				1.00
(10.11)		10.5		0.25

Критическим является путь: , а его продолжительность равна дня.

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

Оценим вероятность выполнения всего комплекса работ за 35 дней, за 30 дней.

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

Таким образом, вероятность того, что весь комплекс работ будет выполнен не более чем за 35 дней, составляет 88, 5%, в то время как вероятность его выполнения за 30 дней - всего 3, 5%.

Оценим максимально возможный срок выполнения всего комплекса работ с надежностью 95%.

Найдем значение аргумента , которое соответствует заданной вероятности 95%. В графе наиболее близкое значение (0, 9545 100%) к ней соответствует . В этой связи в формуле (3.61) используется именно это (не совсем точное) значение. Получаем:

дня.

Следовательно, максимальный срок выполнения всего комплекса работ при заданном уровне вероятности составляет 36, 2 дня.

Контрольное задание №6

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

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

Вариант 1.

Содержание работ Обозначение Предшествующие работы Длительность работ

Заказ на оборудование а₁ -

Разработка системы учета спроса а₂ -

Отбор товаров и выписка счетов а₃ а₁

Завоз товара а₄ а₃

Завоз оборудования а₅ а₁

Установка оборудования а₆ а₅

Выкладка товара а₇ а₄

Учет наличия товара а₈ а₄

Оформление зала а₉ а₆, а₇

Изучение документов а₁₀ а₂, а₈

Репетиция а₁₁ а₉, а₁₀

Проведение ярмарки а₁₂ а₁₁

Вариант 2.

Содержание работ Обозначение Предшествующие работы Длительность работ

Заказ на оборудование а₁ -

Разработка системы учета спроса а₂ -

Отбор товаров и выписка счетов а₃ а₁

Завоз товара а₄ а₃

Завоз оборудования а₅ а₁

Установка оборудования а₆ а₅

Выкладка товара а₇ а₄

Учет наличия товара а₈ а₄

Оформление зала а₉ а₆, а₇

Изучение документов а₁₀ а₂, а₈

Репетиция а₁₁ а₉, а₁₀

Проведение ярмарки а₁₂ а₁₁

Вариант 3.

Содержание работ Обозначение Предшествую щие работы Длительность работ

Заказ на оборудование а₁ -

Разработка системы учета спроса а₂ -

Отбор товаров и выписка счетов а₃ а₁

Завоз товара а₄ а₃

Завоз оборудования а₅ а₁

Установка оборудования а₆ а₅

Выкладка товара а₇ а₄

Учет наличия товара а₈ а₄

Оформление зала а₉ а₆, а₇

Изучение документов а₁₀ а₂, а₈

Репетиция а₁₁ а₉, а₁₀

Проведение ярмарки а₁₂ а₁₁

Вариант 4.

Содержание работ Обозначение Предшествую щие работы Длительность работ

Заказ на оборудование а₁ -

Разработка системы учета спроса а₂ -

Отбор товаров и выписка счетов а₃ а₁

Завоз товара а₄ а₃

Завоз оборудования а₅ а₁

Установка оборудования а₆ а₅

Выкладка товара а₇ а₄

Учет наличия товара а₈ а₄

Оформление зала а₉ а₆, а₇

Изучение документов а₁₀ а₂, а₈

Репетиция а₁₁ а₉, а₁₀

Проведение ярмарки а₁₂ а₁₁

Вариант 5.

Содержание работ Обозначение Предшествую щие работы Длительность работ

Заказ на оборудование а₁ -

Разработка системы учета спроса а₂ -

Отбор товаров и выписка счетов а₃ а₁

Завоз товара а₄ а₃

Завоз оборудования а₅ а₁

Установка оборудования а₆ а₅

Выкладка товара а₇ а₄

Учет наличия товара а₈ а₄

Оформление зала а₉ а₆, а₇

Изучение документов а₁₀ а₂, а₈

Репетиция а₁₁ а₉, а₁₀

Проведение ярмарки а₁₂ а₁₁

Вариант 6.

Содержание работ Обозначение Предшествую щие работы Длительность работ

Заказ на оборудование а₁ -

Разработка системы учета спроса а₂ -

Отбор товаров и выписка счетов а₃ а₁

Завоз товара а₄ а₃

Завоз оборудования а₅ а₁

Установка оборудования а₆ а₅

Выкладка товара а₇ а₄

Учет наличия товара а₈ а₄

Оформление зала а₉ а₆, а₇

Изучение документов а₁₀ а₂, а₈

Репетиция а₁₁ а₉, а₁₀

Проведение ярмарки а₁₂ а₁₁

Вариант 7.

Содержание работ Обозначение Предшествую щие работы Длительность работ

Заказ на оборудование а₁ -

Разработка системы учета спроса а₂ -

Отбор товаров и выписка счетов а₃ а₁

Завоз товара а₄ а₃

Завоз оборудования а₅ а₁

Установка оборудования а₆ а₅

Выкладка товара а₇ а₄

Учет наличия товара а₈ а₄

Оформление зала а₉ а₆, а₇

Изучение документов а₁₀ а₂, а₈

Репетиция а₁₁ а₉, а₁₀

Проведение ярмарки а₁₂ а₁₁

Вариант 8.

Содержание работ Обозначение Предшествующие работы Длительность работ

Заказ на оборудование а₁ -

Разработка системы учета спроса а₂ -

Отбор товаров и выписка счетов а₃ а₁

Завоз товара а₄ а₃

Завоз оборудования а₅ а₁

Установка оборудования а₆ а₅

Выкладка товара а₇ а₄

Учет наличия товара а₈ а₄

Оформление зала а₉ а₆, а₇

Изучение документов а₁₀ а₂, а₈

Репетиция а₁₁ а₉, а₁₀

Проведение ярмарки а₁₂ а₁₁

Вариант 9.

Содержание работ Обозначение Предшествующие работы Длительность работ

Заказ на оборудование а₁ -

Разработка системы учета спроса а₂ -

Отбор товаров и выписка счетов а₃ а₁

Завоз товара а₄ а₃

Завоз оборудования а₅ а₁

Установка оборудования а₆ а₅

Выкладка товара а₇ а₄

Учет наличия товара а₈ а₄

Оформление зала а₉ а₆, а₇

Изучение документов а₁₀ а₂, а₈

Репетиция а₁₁ а₉, а₁₀

Проведение ярмарки а₁₂ а₁₁

Вариант 10.

Содержание работ Обозначение Предшествую щие работы Длительность работ

Заказ на оборудование а₁ -

Разработка системы учета спроса а₂ -

Отбор товаров и выписка счетов а₃ а₁

Завоз товара а₄ а₃

Завоз оборудования а₅ а₁

Установка оборудования а₆ а₅

Выкладка товара а₇ а₄

Учет наличия товара а₈ а₄

Оформление зала а₉ а₆, а₇

Изучение документов а₁₀ а₂, а₈

Репетиция а₁₁ а₉, а₁₀

Проведение ярмарки а₁₂ а₁₁

Тема №7 Задача об оптимальном назначении.

Пусть имеются n работ и n кандидатов для выполнения этих работ. Назначение кандидата i на работу j связано с затратами (i, j=1, 2, …, n). Требуется найти назначения кандидатов на все работы, дающие минимальные суммарные затраты, при этом каждого кандидата можно назначать только на одну работу и каждая работа может быть занята только одним кандидатом. Исходные данные представлены в таблице:

Решение.

Введем переменные (i, j=1, 2, …, n), имеющие следующий смысл:

=1, если кандидат распределяется на работу ;

=0 — в противном случае.

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

для всех i =1, 2, …, n;

для всех j =1, 2, …, n.

Критерием оптимизации (целевой функцией) является суммарное время выполнения всех работ Y:

.

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

Для решения будем использовать венгерский метод. Основной принцип его – оптимальность решения задачи о назначении – не нарушается при уменьшении или увеличении элементов строки (столбца) на одну и ту же величину ( ). Решение считается оптимальным, если все измененные искусственно затраты (i, j=1, 2, …, n) и можно подобрать такой набор , при котором

.

На основе исходных данных создадим таблицу 1:

Таблица 1

А_i B_j a_i d_i

B₁ B₂ B₃ B₄

A₁

A₂

A₃

A₄

b_j

Алгоритм метода включает следующие основные этапы:

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

Таблица 2

А_i B_j a_i

B₁ B₂ B₃ B₄

A₁

A₂

A₃

A₄

b_j

d_j

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

Таблица 3

А_i B_j a_i

B₁ B₂ B₃ B₄

A₁

A₂

A₃

A₄

b_j

2) поиск оптимального решения. Необходимо рассмотреть сначала одну из строк таблицы 3, имеющую наименьшее число нулей. Выделим тот из нулей (тот, которому соответствуют наименьшие затраты времени по таблице 1) этой строки и зачеркнем все остальные нули этой строки и того столбца, в которых находится выделенный нуль. Аналогичные операции последовательно проводят для всех строк. Если назначения, которые получены при всех выделенных нулях, являются полными (то есть число выделенных нулей равно n), то решение оптимальное, в противном случае следует переходить к следующему этапу;

3) поиск минимального набора строк и столбцов, содержащих нули. Для этого необходимо выделить:

a) все строки, в которых не имеется ни одного выделенного нуля (строка 4 табл. 3);

b) все столбцы, содержащие перечеркнутый нуль хотя бы в одной из выделенных строк (столбец 3 табл. 3);

c) все строки, содержащие выделенные нули хотя бы в одном из выделенных столбцов (строка 3 табл. 3).

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

4) перестановка некоторых нулей. Взять наименьшее число из тех клеток, через которые не проведены прямые (это число 2 табл. 3). Вычесть его из каждого числа не вычеркнутых столбцов и прибавить к каждому числу вычеркнутых строк. Получим таблицу 4:

Таблица 4

А_i B_j a_i

B₁ B₂ B₃ B₄

A₁

A₂

A₃

A₄

b_j

Эта операция не изменяет оптимального решения, после чего весь цикл расчета начинается с этапа два и продолжается до получения оптимального решения. В нашем случае число выделенных нулей оказалось равным 4, значит, назначение является полным, а решение – оптимальным.

Оптимальное решение может быть неединственным. Для нашей задачи минимальное значение целевой функции будет равно:

(используем затраты времени тех клеток, которым в табл. 4 соответствуют выделенные нули).

Контрольное задание №7

Пусть имеются n работ и n кандидатов для выполнения этих работ. Назначение кандидата i на работу j связано с затратами (i, j=1, 2, …, n). Требуется найти назначения кандидатов на все работы, дающие минимальные суммарные затраты, при этом каждого кандидата можно назначать только на одну работу и каждая работа может быть занята только одним кандидатом. Исходные данные представлены в таблице:

Вариант 1.

Вариант 2.

Вариант 3.

Вариант 4.

Вариант 5.

Вариант 6.

Вариант 7.

⇐ Предыдущая 3 4 5 6 7 8910 11 12 Следующая ⇒