Методические указания для студентов механико-математического факультета (стр. 3 )

(0,4)-(4,6)-(6,7)-(7,8).

Если увеличить продолжительность работы (5,6) на величину ее полного резерва времени, то в сети появится новый критический путь, которому принадлежит работа (5,6). Найдем его, используя данные таблицы 4:

k=5, i(5)=3, i(3)=2, i(2)=0,

l=6, i*(6)=7, i*(7)=8.

Итак, новый критический путь проходит через узлы 0-2-3-5-6-7-8, и ему принадлежат работы (0,2)-(2,3)-(3,5)-(5,6)-(6,7)-(7,8 ).

11.5. Оптимизация плана комплекса работ

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

Предположим, что в сетевом графике продолжительность каждой работы (i, j) не фиксирована, а лишь известен интервал ее изменения [Lij, Uij,]. Обозначим продолжительность работы (i, j) переменной yij. Тогда, yijÎ[Lij, Uij,]. Изменение продолжительности работы либо требует дополнительных затрат, если имеется в виду ее более быстрое исполнение, либо приводит к уменьшению затрат, если наблюдается увеличение продолжительности. Будем считать, что зависимость затрат от продолжительности работ линейна, то есть затраты на выполнение работы (i, j) равны bij-aijyij, где bij³0, aij³0.

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

S (bij-aijyij)® min

(i, j)ÎS ti, yij

ti +yij £ tj для всех (i, j)ÎS, (3)

tn - t0 £ T0,

Lij £ yij £ Uij для всех (i, j)ÎS,

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

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

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

S aijyij® max

(i, j)ÎS ti, yij

ti - tj+yij £ 0 для всех (i, j)ÎS, (4)

- t0 +tn £ T0,

Lij £ yij £ Uij для всех (i, j)ÎS.

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

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

S aijyij® max

(i, j)ÎКр ti, yij

ti - tj+yij£0 для всех (i, j)ÎКр, (5)

-t0+tn £T0,

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

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

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

k

S cixi® max

i=1 xi

k

S xi £ T0 (6)

i=1

Li £ xi £ Ui для i=1,2,…,k.

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

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

1.  Упорядочим критические работы в порядке убывания значений ci: i1,i2,…,ik.

k

2.  Полагаем T0=T0 -å Li, и j=1 .

i=1

3.  Вычисляем z=min { Uij-Lij, T0 }, xij =Lij +z. Присваиваем T0=T0-z.

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

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

Пример 4.

Для сетевого графика из примера 1 найти оптимальные значения сроков наступления событий ti и продолжительностей работ yij при заданных продолжительности проекта T0 =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

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

3x1 +6x2 +0x3+4x4 +2x5 +x6 ® max

x1 +x2 +x3+x4 +x5 +x6 £33,

4£x1 £6,

4£x2 £7,

0£x3 £0,

8£x4 £10,

1£x5 £4,

7£x6 £9.

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

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

Тогда, x2 =4+min{7-4,9}=7, уменьшаем T0 =9-3=6,

x4 =8+min{10-8,6}=10, уменьшаем T0 =6 –2=4,

x1 =4+min{6-4,4}=6, T0 =4-2=2,

x5 =1+min{4-1,2}=3, T0 =2-2=0,

x6 =7+min{9-7,0}=7, T0 =0.

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

Таблица 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

Пример 5.

Для сетевого графика, изображенного на рис. 4, найти оптимальные значения продолжительностей работ yij при заданных в таблице 8 отношениях предшествования, верхних и нижних пределах продолжительности каждой работы и продолжительности проекта T0 =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

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

y0,1+8y0,2+6y1,2+7y1,3+5y2,3® max

y0,1-t1 £0

y0,2-t2 £0

y1,2+t1-t2£0 (7)

y1,3+t1-t3£0

y2,3+t1-t3£0

t3£15

2£y0,1£8