Теория двойственности в линейном программировании. Двойственный симплекс-метод (стр. 4 )

Если на критическом пути лежит конечное событие j, то

Если на критическом пути лежат начальное и конечное собы­тия i и j, но сама работа не принадлежит этому пути, то

Соотношения (14.18)—(14.20) можно использовать при провер­ке правильности расчетов резервов времени отдельных работ.

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

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

6.7. Коэффициент напряженности работы. Анализ и оптимизация сетевого графика

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

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

Анализ сетевого графика начинается с анализа топологии сети, включающего контроль построения сетевого графика, установле­ние целесообразности выбора работ, степени их расчленения.

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

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

Коэффициентом напряженности КИ работы (/, j) называется отношение продолжительности несовпадающих (заключенных между одними и теми же событиями) отрезков пути, одним из которых является путь максимальной продолжительности, проходящий через данную работу, а другим — критический путь:

где— продолжительность максимального пути, проходящего через работу (i, j);

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

Формулу (14.29) можно легко привести к виду

где— полный резерв времени работы (i, j).

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

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

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

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

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

• перераспределением всех видов ресурсов, как временных (использование резервов времени некритических путей), так и трудовых, материальных, энергетических (например, перевод час­ти исполнителей, оборудования с некритических путей на работы критического пути); при этом перераспределение ресурсов долж­но идти, как правило, из зон, менее напряженных, в зоны, объе­диняющие наиболее напряженные работы;

• сокращением трудоемкости критических работ за счет пере­дачи части работ на другие пути, имеющие резервы времени;

• параллельным выполнением работ критического пути;

• пересмотром топологии сети, изменением состава работ и структуры сети.

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

УПРАЖНЕНИЯ

В задачах 6.7, 6.8 построить сетевой график. Найти продолжи­тельность выполнения комплекса работ, временные характеристики событий и работ. В скобках указана продолжительность работ.

6.7. Сделать деревянный ящик (работу выполняет один чело­век). Разместить доски в соответствии с размерами ящика (15 мин); разрезать доски (12 мин); склеить части ящика (40 мин); прибить к крышке ящика петли (8 мин); подождать, пока ящик высохнет, и вытереть его (15 мин); петли (с крышкой) прибить к ящику (10 мин).

6.8. Заменить колесо машины (работу выполняют два чело­века). Достать из багажника домкрат и инструменты (40 с); снять диск с колеса (30 с); освободить колесо (50 с); поставить домкрат под машину (26 с); поднять машину (20 с); из багажника взять запасное колесо (25 с); снять гайки и колесо (20 с); установить запасное колесо на ось (10 с); завинтить (не сильно) гайки на оси (15 с); опустить машину и собрать домкрат (25 с); поставить дом­крат обратно в багажник (10 с); завинтить гайки на оси до конца (12 с); положить плохое колесо и инструменты в багажник (40 с); поставить на место диск колеса (10 с).

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

6 6 7

4

1

7 4

3 10

1 2

9 8

2 5

6 5 8

3

Задача 6.10. По данным таблицы заполнить таблицу событий, построить сетевой график, определить критический путь и его длину.

Работа	Работы, до завершения которых не может начаться данная работа (непосредственно предшествующие работы)	Продолжительность (сутки)
Р1		5
Р2		10
Р3	1	7
Р4	2	5
Р5	3	9
Р6	2	6
Р7	4	8

Решение

Задача 6.11. По данным таблицы построить линейную диаграмму проекта, определить критический путь и его длину.

Решение

Таблица событий

Событие	Работы, для которых данное событие является конечным	Работы, для которых данное событие является начальным
0		Р1, Р2
1	Р1=(0,1)	Р3
2	Р2=(0,2)	Р4,Р6
3	Р3=(1,4)	Р5
4	Р4=(1,4)	Р7
5	Р6=(2,5)
6	Р5=(3,6)
7	Р7=(4,7)
8	Ф1=(5,8), Ф2=(6,8), Ф3=(7,8)

25

Задача 6.12. По данным таблицы построить сетевой график, определить полные пути, определить критический путь и его длину.

Работы	Продолжительность (сутки)
(1,2)	5
(1,3)	2
(1,4)	7
(3,4)	5
(2,5)	9
(3,5)	6
(4,5)	4

Решение

Исследование операций в экономике. Под ред. . М. ЮНИТИ, 2006 г.