Оптимизация сетевого графика
Лекция 16
Оптимизация сетевого графика
Оптимизация сетевого графика в зависимости от полноты решаемых задач может быть условно разделена на частную и комплексную. Видами частной оптимизации сетевого графика являются:
Ø Минимизация времени выполнения комплекса работ при заданной его стоимости;
Ø Минимизация стоимости комплекса работ при заданном времени выполнения проекта.
Комплексная оптимизация представляет собой нахождение оптимального соотношения величин стоимости и сроков выполнения проекта в зависимости от конкретных целей, ставящихся при его реализации.
При использовании метода «время – стоимость» предполагают, что уменьшение продолжительности работы пропорционально возрастанию ее стоимости. Каждая работа (i,j) характеризуется продолжительностью t(i ,j), которая может находиться в пределах
(1)
где 
- минимально возможная (экстренная) продолжительность работы (i,j), которую только можно осуществить в условиях разработки, 
- нормальная продолжительность выполнения работы (i,j).
Рекомендуемые материалы
При этом стоимость 
работы (i,j ) заключена в границах от 
при нормальной продолжительности работы, до 
при экстренной продолжительности работы. Используя аппроксимацию по прямой, можно найти изменение стоимости работы 
при сокращении ее продолжительности на величину
(2)
Величина 
, равная тангенсу угла α наклона аппроксимирующей прямой, показывает затраты на ускорение работы (i,j) по сравнению с нормальной продолжительностью на единицу времени:
Самый очевидный вариант частной оптимизации сетевого графика с учетом стоимости предполагает использование резервов времени работ. Продолжительность каждой работы, имеющей резерв времени, увеличивают до тех пор, пока не будет исчерпан этот резерв или пока не будет достигнуто верхнее значение продолжительности 
. При этом стоимость выполнения проекта, равная до оптимизации
,
уменьшится на величину
.
Для проведения частной оптимизации сетевого графика кроме продолжительности работ t(i ,j), необходимо знать их граничные значения и , а также показатели затрат на ускорение работ 
. Продолжительность каждой работы 
целесообразно увеличить на величину такого резерва, чтобы не изменить ранние (ожидаемые) сроки наступления всех событий сети, т.е. на величину свободного резерва времени 
.
Пример
Провести частную оптимизацию сетевого графика. Граничные значения продолжительности работ , имеющих резервы времени 
, а также граничные значения и и их стоимости , коэффициенты затрат на ускорение работ приведены в таблице.
| № | Раб | Прод | Продолжительности работ | Своб. Рез. | Стоим. раб | Коэф. затр. | Умен. Стоим. | ||||||
|
|
|
|
|
|
|
|
| ||||||
| 1 | (0,5) | 9 | 0 | 9 | 11 | 20 | 11 | 60 | 8 | 5*8=40 | |||
| 2 | (1,4) | 6 | 8 | 14 | 20 | 26 | 9 | 28 | 4 | 4*4=16 | |||
| 3 | (1,3) | 4 | 8 | 12 | 9 | 13 | 1 | 37 | 12 | 1*12=12 | |||
| 4 | (2,7) | 3 | 17 | 20 | 40 | 43 | 13 | 86 | 6 | 4*6=24 | |||
| 5 | (3,6) | 6 | 13 | 19 | 23 | 29 | 10 | 92 | 10 | 3*10=30 | |||
| 6 | (4,7) | 8 | 23 | 31 | 35 | 43 | 2 | 48 | 5 | 2*5=10 | |||
| 7 | (4,6) | 3 | 23 | 26 | 26 | 29 | 3 | 64 | 12 | 3*12=36 | |||
| 8 | (5,8) | 10 | 20 | 30 | 28 | 38 | 7 | 15 | 1 | 7*1=7 | |||
| 9 | (5,9) | 6 | 20 | 26 | 36 | 42 | 16 | 86 | 7 | 16*7=42 | |||
| 10 | (6,10) | 5 | 29 | 34 | 43 | 48 | 14 | 44 | 5 | 15*5=25 | |||
| 11 | (7,10) | 5 | 33 | 38 | 43 | 48 | 10 | 74 | 4 | 10*4=40 | |||
| 12 | (8,9) | 4 | 37 | 41 | 38 | 42 | 1 | 20 | 3 | 1*3=3 | |||
| 13 | (9,11) | 17 | 42 | 59 | 44 | 61 | 2 | 40 | 4 | 2*4=8 | |||
| Итого | 694 | - | Бесплатная лекция: "24. Почвы пустынь и полупустынь умеренного пояса." также доступна. 293 | ||||||||||
В таблице представлены параметры тех работ, которые имеют свободный резерв времени.
Подчеркнуты те работы, свободные резервы времени которых полностью использованы на увеличение их продолжительности.
В результате оптимизации сети получился сетевой график, который позволяет выполнить комплекс работ в срок 
=61 (суток) при минимальной его стоимости С=923 (усл. руб). (Сюда включены стоимости остальных работ: C(0,1)=50; C(0,3)=45; C(1,2)=82; C(3,4)=55; C(3,5)=72; C(5,6)=30; C(6,7)=26; C(6,9)=75; C(6,8)=42; C(9,10)=35; C(10,11)=10 (усл. руб)).
В реальных условиях выполнение проекта может потребоваться ускорение его выполнения, что отразится на стоимости проекта, т.е. она увеличиться. Поэтому необходимо определить оптимальное соотношение между стоимостью проекта С и продолжительностью его выполнения 
, представленное в виде функции 
.
Для оптимизации сетей и, в частности, для нахождения функции 
могут быть использованы эвристические методы, т.е. методы, учитывающие индивидуальные особенности сетевых графиков.
