<< Предыдущая

стр. 8
(из 10 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

E’


A’
0’

X3
w03

F
B C
L
w23
D
w02 E

X03

0 X1
A
w01 w13

Рис. 6.2.


В [3] показано, что для случая степенных зависимостей вида (6.2)
движение по траектории происходит со скоростью N?(t). Отсюда следует,
что минимальному времени выполнения комплекса соответствует
движение по кратчайшей траектории, соединяющей точку 0 с точкой C’.
Длина этой кратчайшей траектории равна эквивалентному объему
комплекса, если расстояние между любыми двумя точками y1 и y2
определяется по формуле:
?
?r ?
?( y 1 , y 2 ) = ?? y i1 ? y i 2
1
? (6.3)
?.
? i =1 ?




49
Описанная аналогия позволяет свести задачу определения эквивалентного
объема к задаче определения кратчайшей траектории в допустимой
области состояний комплекса.
Пример 6.2. Пусть f ij ( u ij ) = u ij , W01 = 4, W02 = 3, W13 = 3, W23 = 4,

W03 = 6.
Сначала пробуем провести прямую, соединяющую т. 0 с т. C’.
Поскольку W01 + W13 = W02 + W23 = 7, то в момент завершения операции
(0, 2) будет выполнено всего 3 единицы объема операции (0, 1).
Следовательно, прямая не проходит в допустимой области. Очевидно, что
кратчайшая траектория должна проходить через отрезок EE’. Из
геометрии известно, что треугольники 0EL и LE’C’ должны быть
подобными, если 0LC’ - кратчайшая траектория. Имеем:

w2 + w2
x 03
= = 1.
01 02
w 03 ? x 03 +
2
w2
w 13 23

Поэтому x03 = 1/2w03 = 3. Эквивалентный объем (или длина кратчайшей
траектории) равен

Wэ = 0L + LC' = 2 5 2 + 3 2 = 2 34 .

Пусть количество ресурсов тогда минимальная
N = 8,5,
продолжительность комплекса

Tmin = = 4,
N
при этом операции (0; 1), (0; 2) и половина операции (0; 3) завершаются
одновременно за время t01 = t02 = 2. Отсюда сразу определяем оптимальное
распределение ресурсов




50
2 2 2
? w 01 ? ? w 02 ? ? w 03 ?
=? ? = 4; u 02 = ? ? = 2,25; u 03 = ? ? = 2,25;
u 01
? t 01 ? ? t 02 ? ? t 03 ?
2 2
?w ? ?w ?
= ? 13 ? = 2,25; u 23 = ? 23 ? = 4.
u 13
? t 13 ? ? t 23 ?

Легко убедиться, что распределение ресурсов {uij} образует поток по
сетевому графику.
Рассмотрим еще одну аналогию задачи распределения ресурсов с
задачей определения токов и напряжений в электрической цепи из
нелинейных сопротивлений. Аналогия достаточно очевидна, поскольку
поток ресурсов естественно интерпретировать как ток в цепи, а моментам
свершения событий поставить в соответствие потенциалы вершин.
Однако, чтобы получить возрастающие вольтамперные характеристики,
необходимо перейти к новым переменным:
vij = ?j - ?i - ?ij = ?ij - ?ij,
где {?i} выбираются таким образом, что ?j - ?i > ?ij для всех (i, j), где ?ij -
предполагаемое время выполнения операции (i, j). Поставим теперь в
соответствие сетевому графику двухполюсник с нелинейными
сопротивлениями, имеющими вольтамперные характеристики
w ij
v ij ( u ij ) = ? ij ? .
u?
ij


Если теперь подать на вход двухполюсника напряжение V = ?оn - Т, где Т -
заданное время выполнения комплекса, то распределение токов по ветвям
будет определять оптимальное распределение ресурсов по комплексу
операций.
Эта аналогия позволила получить новый результат в электротехнике,
а именно, опираясь на то, что для степенных зависимостей оптимальное
распределение ресурсов образует поток в сети, было показано, что для
степенных вольтамперных характеристик эквивалентное сопротивление

51
цепи уменьшается при уменьшении любого сопротивления цепи (ранее
этот факт был известен для цепей с постоянными сопротивлениями).
Заметим, что для произвольных цепей с нелинейными пассивными
сопротивлениями этот факт, вообще говоря, не верен. Таким образом,
идеальное агрегирование комплекса со степенными зависимостями
скоростей операций от количества ресурсов сводится к определению его
эквивалентного объема.
Опишем алгоритм определения эквивалентного объема комплекса.
Сначала определяем зависимость затрат Sij = uij??ij от времени выполнения
операции:
1 1
? w ij ? ?
w ij ?
S ij = ? ij ? ? ? = (6.4)
1? ?
? ? ij ? ? ij ?


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

? S ij (? ij )
S= (6.5)
( i , j)

были минимальными.
Как известно, необходимым и достаточным для оптимальности
является выполнение для любого события i сети (за исключением
начального и конечного) следующих условий:

( )= dS ki ( ? ki )
dS ij ? ij
? ? (6.6)
.
d? ij d? ki
j k

Однако, поскольку

( ) = ? 1? ? u
dS ij ? ij
ij ,
d? ij ?




52
1
(24)
(20)

(9) 3
0

(28) (15)
2


Рис. 6.3.

то условие (6.6) эквивалентно условию потоковости ресурсов в каждом
событии. А минимум стоимости при условии, что ресурсы образуют поток
в сети, эквивалентен минимуму ресурсов N.
Для решения задачи минимизации сети по стоимости известен
эффективный алгоритм Кэлли. На каждом шаге алгоритма проверяется
условие (6.6) в вершинах сети, и время свершения соответствующего
события корректируется так, чтобы эти условия выполнялись. На каждом
шаге происходит уменьшение величины (6.5). Когда в сети получено
решение, для которого (6.6) выполняется во всех вершинах, величина
стоимости (6.5) минимальна и, следовательно, минимальным является и
уровень ресурсов Nmin. Эквивалентный объем комплекса определяется
выражением
Wэ = TN? = S?min?T1-? (6.7)
Пример 6.3. Рассмотрим сетевой график, приведенный на рисунке
6.3.
Пусть f ij ( u ij ) = u ij для всех (i, j). Объемы операций указаны в

скобках у соответствующих дуг. Пусть Т = 10. Возьмем начальное
решение t1 = 5, t2 = 8. Получим общую формулу для корректировки
моментов ti. Пусть


53
? u ij > ? u ki .
j k

В этом случае ti следует увеличить на некоторую величину ?,
определяемую из уравнения
2
? w ij ?
2
? w ki ?
? ? ? + ?? = ? ? ? ? ?? . (6.8)
k ? ki ?
j ? ij ?

I шаг. Рассматриваем событие 1. Имеем
2
? w 01 ?
2 2
? 24 ? ? 9?
=? ? = 16; u 13 = ? ? ? 2,3; u 12 = ? ? = 9.
u 01
? 5? ? 3?
? t 01 ?
u 01 = 16 < u 13 + u 12 ? 32.
Решаем уравнение
2 2 2
? 20 ? ? 24 ? ?9?
? =? ? +?
? ?.
? 5 ? ?? ? 5 + ?? ? 3 + ??

Получаем ? = 0,8, t1 = 5 - 0,8 = 4,2.
Рассмотрим событие 2. Имеем
u02 = 12,25; u12 = (9/3,8)2 ? 5,7; u23 = 56,25.
Момент t2 следует уменьшить. Определяем величину уменьшения из
уравнения
2
2 2
?9?
? 28 ? ? 15 ?
+? =?
? ? ?.
?
? 8 ? ?? ? 2 + ??
? 3,8 ? ? ?

Возьмем ? = 0,6. Имеем t2 = 7,4. С новыми значениями t1 и t2 процедура
повторяется. После нескольких итераций процесс сходится к решению t10
= 4, t20 = 7, которое является оптимальным. Действительно, для этого
решения имеем
2 2 2
? 20 ? ? 28? ? 9?
= ? ? = 25; u 02 = ? ? = 16; u12 = ? ? = 9;
u 01
? 4? ? 7? ? 3?
2 2
? 24 ? ? 15?
= ? ? = 16; u 23 = ? ? = 25.
u13

<< Предыдущая

стр. 8
(из 10 стр.)

ОГЛАВЛЕНИЕ

Следующая >>