Основные сведения

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

Рассмотрим оптимизацию сетевого графика методом «время-стоимость», при использовании которого предполагают, что уменьшение продолжительности работы пропорционально возрастанию её стоимости.

Введем обозначения:

t(i, j) – заданная продолжительность работы (i, j),

a(i, j) – минимально возможная продолжительность работы (i, j),

b(i, j) – максимально возможная продолжительность работы (i, j),

t_опт(i,j) – оптимальная продолжительность работы (i, j),

c(i,j) – заданная стоимость работы (i, j).

Работа (i, j) характеризуется продолжительностью t(i, j), которая находится в пределах: a(i, j) ≤ t(i, j) ≤ b(i, j) или t_min(i, j) ≤ t(i, j) ≤ t_max(i, j).

В таблице Т3 рассчитываются данные двух столбцов: t_опт(i,j) и Δс(i,j). Остальные данные представлены в условиях примера. Так t_max(i, j) берется из условий t_p(i), t_n(i), t_p(j), t_n(j) и t(i, j).

Оптимизация сетевого графика может быть проведена, например, за счет использования R_ч2(i, j). При этом продолжительность каждой работы увеличивается до тех пор, пока не будет исчерпан этот резерв или пока не будет достигнуто значение максимально возможной продолжительности работы t(i, j).

Находим t_опт(i,j) по формулам: t_опт(i,j) = t(i,j) + R_ч2(i,j),

если сумма не превышает максимально возможной продолжительности b(i, j).

В противном случае t_опт(i,j) = t_max(i,j) = b(i,j).

● Задаем стоимость работы с(i, j) самостоятельно, исходя из условий примера. При этом учитываем, что стоимость работы увеличивается при уменьшении её продолжительности.

Стоимость работы с(i, j) заключена в границах с_min(i, j) ≤ с(i, j) ≤ с_max(i, j), где

с_min(i, j) – стоимость при нормальной продолжительности работы,

с_max(i, j) – стоимость при экстренной продолжительности работы.

График зависимости стоимости работы (i, j) от её продолжительности

Рис.1.

Δс(i,j) – изменение стоимости работы (i, j) за счет оптимизации,

tgφ – характеризует изменение затрат при изменении времени выполнения работы (i, j) и рассчитывается из соотношений в треугольнике (1 2 3),

– затраты на ускорение работы (i, j),

Δс(i,j) можно найти из Δ(1 2 3) Δс(i,j) = [ t_опт(i,j) – t(i,j) ] · k(i,j).

● Стоимость выполнения всего проекта до оптимизации находим по формуле

С = ∑ с(i,j)

(суммирование ведется по всем работам).

● ● Величину уменьшения стоимости проекта после оптимизации находим:

ΔС = ∑ Δс(i,j)

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

Для нашего примера: 1) Проведем оптимизацию по работам (1,5), (4,10), (6,9), (7,9), (10,12), имеющие резервы R_ч2.

Заполним таблицу 3, задавая из условий примера t_max(i,j), c(i,j), k(i,j),

вычисляя t_опт(i,j), Δс(i,j).

Таблица 3

№	Код работы	Время работы t(i,j)	tmax(i,j)	Rч2(i,j)	tопт(i,j)= Rч2+t(i,j)	c(i,j)	k(i,j)	Δс(i,j)= (tопт- t)k
	(0,1)
	(1,2)
	(1,5)				10 (10)		0,5	0,5(10-5)=2,5
	(1,4)
	(4,10)				18 (15)		0,3	0,3(15-7)=2,4
	(2,3)
	(3,5)
	(5,6)
	(5,7)
	(6,9)				5 (5)		2,0	2,0(5- 4)=2
	(5,8)
	(8,9)
	(7,9)				5 (5)		0,5	0,5(5- 3)=1
	(9,10)
	(10,12)				8 (8)		1,0	1(8- 3)=5
	(10,11)
	(11,12)
						∑=227		∑= 12,9

В таблице 3 представлены параметры лишь тех работ, а именно работ (1,5), (4,10), (6,9), (7,9), (10,12) которые имеют R_ч2(i,j), т.е. свободный резерв времени.

Рассмотрим на примере работы (1,5):

● ЗАДАЕМ ИЗ УСЛОВИЙ ПРИМЕРА: t_max(i,j), c(i,j), k(i,j):

t_max(1,5) = 12, так как работа (1, 5) начинается в интервале [3,16], оканчивается в интервале [0,13], а продолжительность t(1,5) = 5,

тогда максимально возможная продолжительность работы (1,5) берём равной 12.

c(1,5) = 18 (усл. ед.)- стоимость работы задаем самостоятельно, исходя из условия примера.

k(1,5) = 0,5 - коэффициент затрат на ускорение работы (1, 5) задаем самостоятельно.

● ВЫЧИСЛЯЕМ t_опт(i,j), Δс(i,j):

t_опт(1,5) = t(i,j) + R_ч2(i,j) = t(1, 5) + R_ч2(1, 5) = 5 + 5 = 10, берем значение 10, т.к. это число не превышает t_max(1,5) = 12.

Δс(1,5) = [ t_опт(1, 5) – t(1, 5) ] · k(1, 5) = (10 – 5)0,5 = 2,5.

( Вычисляем аналогично по работам (4,10), (6,9), (7,9), (10,12) и суммируем).

2) Составим оптимизированный сетевой график, в котором время выполнения работ (1,5), (4,10), (6,9), (7,9), (10,12) укажем оптимальное:

3) Стоимость выполнения проекта уменьшилась на 12,9 ден. ед. и составила

(227 – 12,9) = 214,1 ден. ед.

227 - 100 %,

12,9 - х %, тогда х = 12,9 · 100/ 227 = 5,7 %.

Таким образом стоимость проекта уменьшилась приблизительно на 5,7 %.

Вывод:

а) В новом сетевом графике количество полных путей, имеющих критический срок исполнения (32 недели) увеличилось.

Только один путь (0) → (1) → (4) → (10) → (12) остался некритическим.

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