5.5 Оптимизация плана комплексных работ

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

Предположим, что в сетевом графике продолжительность каждой работы (i,j) не фиксирована, а лишь известен интервал ее изменения [L_ij,U_ij,]. Обозначим продолжительность работы (i,j) переменной y_ij. Тогда, y_ijÎ[L_ij,U_ij,]. Изменение продолжительности работы либо требует дополнительных затрат, если имеется в виду ее более быстрое исполнение, либо приводит к уменьшению затрат, если наблюдается увеличение продолжительности. Будем считать, что зависимость затрат от продолжительности работ линейна, то есть затраты на выполнение работы (i,j) равны b_ij-a_ijy_ij, где b_ij³0, a_ij³0.

Очевидно, что затраты на выполнение всего проекта будут минимальны при y_ij=U_ij. Полагая y_ij=U_ij найдем длину критического пути T^вкр. Если нас не устраивает полученное значение времени исполнения проекта T^вкр, то можно попытаться его уменьшить. Для этого необходимо уменьшить, по меньшей мере, продолжительность критических работ, что потребует дополнительных затрат. Обозначим желаемую продолжительность исполнения проекта T₀. Пусть t_i- неизвестный нам момент наступления i-го события. При сделанных допущениях можно построить математическую модель, предназначенную для минимизации общей стоимости проекта, продолжительность исполнения которого не больше T₀. Математическая модель имеет вид

S (b_ij-a_ijy_ij)® min

(i,j)ÎS t_i,y_ij

t_i +y_ij £ t_j для всех (i,j)ÎS, (3)

t_n- t₀ £ T₀,

L_ij £ y_ij £ U_ij для всех (i,j)ÎS,

где S есть множество всех дуг сети.

Задача (3) позволяет найти оптимальные значения продолжительностей работ y_ij при заданных продолжительности проекта T₀, отношениях предшествования, верхних и нижних пределах продолжительности каждой работы.

Задача линейного программирования (3) эквивалентна задаче (4)

S a_ijy_ij® max

(i,j)ÎS t_i,y_ij

t_i -t_j+y_ij £ 0 для всех (i,j)ÎS, (4)

-t₀ +t_n £ T₀,

L_ij £ y_ij £ U_ij для всех (i,j)ÎS.

Пусть T^пкр есть длина предкритического пути (пути, ближайшего по своей длине к критическому, но меньшего его). Если T₀³T^пкр, то значение T₀ может быть получено вследствие уменьшения продолжительности только тех работ, которые принадлежат критическому пути.

Этот результат позволяет в ситуации, когда T₀>T^пкр, рассматривать вместо задачи (4) более простую задачу (5)

S a_ijy_ij® max

(i,j)ÎКр t_i,y_ij

t_i -t_j+y_ij£0 для всех (i,j)ÎКр, (5)

-t₀+t_n £T₀,

L_ij £ y_ij £ U_ij для всех (i,j)ÎКр, где Кр – множество дуг, принадлежащих критическим путям.

Если критический путь единственен, то задачу (5) можно упростить. Для этого перенумеруем работы, лежащие на критическом пути, 1,2,…,k. Обозначим продолжительности этих работ x_i для i=1,2,…,k. Величины a_ij, отвечающие критическим работам, назовем c_i.

Тогда задачу (5) можно переписать в виде непрерывной задачи о ранце с двухсторонними ограничениями на переменные.

k

S c_ix_i® max

i=1 x_i

k

S x_i £ T₀ (6)

i=1

L_i £ x_i £ U_i для i=1,2,…,k.

Здесь L_i,U_i ( i=1,2,…,k) - это значения L_ij,U_ij , соответствующие критическим работам. Для задачи (6) существует простой метод решения.

Алгоритм решения задачи (6).

1. Упорядочим критические работы в порядке убывания значений c_i: i₁,i₂,…,i_k .

2. Полагаем T₀=T₀ -å L_i , j=1 , i=1

3. Вычисляем z=min { Ui_j-Li_j,T₀ }, xi_j =Li_j +z. Присваиваем T₀=T₀-z.

4. Если j< k , то увеличиваем j на 1 и переходим к шагу 3.

5. Работа алгоритма завершена.

Пример 5.

Для сетевого графика из примера 1 найти оптимальные значения сроков наступления событий t_i и продолжительностей работ y_ij при заданных продолжительности проекта T₀ =33, отношениях предшествования, определенных в примере 1, верхних и нижних пределах продолжительности каждой работы, заданных в таблице 6.

Таблица 6

Работа	Lij	Uij	aij
(0,1)	3	4	1
(0,2)	4	6	3
(0,4)	6	9	4
(1,5)	7	8	3
(2,3)	4	7	6
(3,4)	0	0	0
(3,5)	0	0	0
(4,6)	8	10	4
(5,6)	4	6	2
(6,7)	1	4	2
(7,8)	7	9	1

Полагаем y_ij=U_ij, и при этих значениях продолжительностей работ методом критического пути проводим анализ сети (см. пример 2). Величина критического пути равна T^вкр =36. Величина предкритического пути равна T^пкр =32. Это означает, что T₀ >T^пкр , и уменьшить время исполнения проекта можно за счет сокращения продолжительности работ, лежащих на критическом пути. Для этого достаточно решить задачу (6), которая в данном случае имеет вид :

3x₁ +6x₂ +0x₃+4x₄ +2x₅ +x₆ ® max

x₁ +x₂ +x₃+x₄ +x₅ +x₆ £33,

4£x₁ £6,

4£x₂ £7,

0£x₃ £0,

8£x₄ £10,

1£x₅ £4,

7£x₆ £9.

Переменные x_i обозначают продолжительность работ, принадлежащих критическому пути. При этом переменная x₃ соответствует фиктивной работе, и поэтому x₃ =0 (далее эту переменную не рассматриваем). Упорядочим переменные в соответствии с убыванием коэффициентов целевой функции {2,4,1,5,6}.

Полагаем T₀=33-(4+4+0+8+1+7)=9.

Тогда, x₂ =4+min{7-4,9}=7, уменьшаем T₀ =9-3=6,

x₄ =8+min{10-8,6}=10, уменьшаем T₀ =6 –2=4,

x₁ =4+min{6-4,4}=6, T₀ =4-2=2,

x₅ =1+min{4-1,2}=3, T₀ =2-2=0,

x₆ =7+min{9-7,0}=7, T₀ =0.

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

Таблица 7

Работа	Переменная Xi, соответству-ющая работе	Оптимальная продолжительность работы Yij	Lij	Uij
(0,1)		4	3	4
(0,2)	X1	6*	4	6
(0,4)		9	6	9
(1,5)		8	7	8
(2,3)	X2	7*	4	7
(3,4)	X3	0*	0	0
(3,5)		0	0	0
(4,6)	X4	10*	8	10
(5,6)		6	4	6
(6,7)	X5	3*	1	4
(7,8)	X6	7*	7	9

Пример 6.

Для сетевого графика, изображенного на рис. 4, найти оптимальные значения продолжительностей работ y_ij при заданных в таблице 8 отношениях предшествования, верхних и нижних пределах продолжительности каждой работы и продолжительности проекта T₀ =15.

Сетевой график для примера 5.

Рисунок 4.

Таблица 8

Работа	Lij	Uij	aij
(0,1)	2	8	1
(0,2)	5	10	8
(1,2)	1	4	6
(1,3)	4	8	7
(2,3)	6	8	5

Полагая y_ij=L_ij, находим T^нкр. При заданных значениях продолжительностей работ T^нкр=11. Так как T₀ >T^нкр, то задача разрешима. При y_ij= U_ij, величины критического и предкритического путей равны T^вкр =20 и T^пкр =18 соответственно. Это означает, что T₀<T^пкр и нельзя уменьшить время исполнения проекта только за счет сокращения продолжительности работ, лежащих на критическом пути. Таким образом, для определения продолжительности работ необходимо решить задачу (5), которая для данного примера при t₀=0 имеет вид:

y_0,1+8y_0,2+6y_1,2+7y_1,3+5y_2,3® max

y_0,1-t₁ £0

y_0,2-t₂ £0

y_1,2+t₁-t₂£0 (7)

y_1,3+t₁-t₃£0

y_2,3+t₁-t₃£0

t₃£15

2£y_0,1£8

5£y_0,2£10

1£y_1,2£4

4£y_1,3£8

6£y_2,3£8.

Сформулированная задача имеет слишком большую для ручного счета размерность (число ограничений m=16, число переменных n=8, а после приведения задачи к каноническому виду возрастет до n=29). Поэтому для решения задачи рекомендуем воспользоваться программой SIMPLEX, разработанной на кафедре исследования операций и предназначенной для решения задач линейного программирования.

До сих пор мы рассматривали оптимизационные модели, в которых ограничивающим фактором являлась продолжительность проекта T₀. В тех случаях, когда таким фактором является стоимость выполнения проекта C₀, можно сформулировать следующую оптимизационную задачу :

Tкр=t_n-t₀ ® min

t_i,y_ij

t_i - t_j +y_ij£0 для всех (i,j)ÎS,

(8)

S (b_ij-a_ijy_ij) £ C₀

(i,j)ÎS

L_ij £ y_ij £ U_ij для всех (i,j)ÎS.

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

Пусть С^н – затраты на выполнение проекта при y_ij=U_ij. Задача (8) разрешима тогда и только тогда, когда С ₀³C^н.

Задача (8) эквивалентна задаче линейного программирования (9):

Tкр=t_n-t₀ ® min

t_i,y_ij

t_i +y_ij £t_j для всех (i,j)ÎS,

(9)

S a_ijy_ij ³ D₀, где D₀= S b_ij -C₀,

(i,j)ÎS (i,j)ÎS

L_ij £ y_ij £ U_ij для всех (i,j)ÎS.

Задачу (9) как и задачу (4) можно решить симплекс-методом. Для этого можно воспользоваться программой SIMPLEX.

Пример 6.

Для сетевого графика изображенного на рис. 2 найти оптимальные значения продолжительностей работ y_ij, минимизирующих время выполнения проекта в целом при заданных в таблице 8 отношениях предшествования, верхних и нижних пределах продолжительности каждой работы и D₀ =201.

Задача (9) для данного примера при t₀=0 имеет вид:

t₃® min

y_0,1-t₁ £0

y_0,2-t₂ £0

y_1,2+t₁-t₂£0

y_1,3+t₁-t₃£0 (10)

y_2,3+t₁-t₃£0

y_0,1+8y_0,2+6y_1,2+7y_1,3+5y_2,3³201

2£y_0,1£8

5£y_0,2£10

1£y_1,2£4

4£y_1,3£8

6£y_2,3£8.

В результате работы программы было получено следующее оптимальное решение y_0,1=6, y_0,2=10, y_1,2=4, y_1,3=8, y_2,3=7, t ₁=6, t₂=10, Tкр=t ₃=17.