3V 7 [A, N > AДля обоснования предложенного метода агрегирования докажем, что при N(t) < A ошибка агрегирования равна 0. Действительно, момент T окончания агрегированной операции определяется из уравнения
Tm
J N(t)dt = W3.
0
Положим
ui(t) = NW . Wl.
j AT
Заметим, что u^t) < ai для всех i. Поэтому момент завершения i-ой операции определяется из уравнения
т. т.
T Wi T
J Uj(t)dt = Wi = —T J N(t)dt.
о A • To
W /
Подставляя T = у— получаем, что Ti = Tm. Более того, если N(t) = N,
то есть количество ресурсов не меняется во времени, то ошибка агрегирования равна 0 при любом N > A. Действительно,
продолжительность агрегированной операции Tm = W//A = T, то есть
совпадает с продолжительностью комплекса операций.
Учитывая стремление к выравниванию уровня ресурсов, выполняющих каждый комплекс операций, можно утверждать, что предложенный метод агрегирования будет давать практически небольшие ошибки агрегирования.Пусть теперь комплекс операций состоит из последовательности из п операций. В данном случае идеальное агрегирование, то есть представление комплекса в виде другого комплекса с меньшим числом
операции, возможно только в случае, если несколько соседних операции имеют равные значения ai. Если несколько соседних операции имеют близкие значения а1 то возможно приближенное агрегирование с ошибкой, зависящей от степени близости а1.
Рассмотрим задачу определения относительной ошибки приближения а1 одним значением А для всех n операций. Относительная ошибка определяется выражением
(1.4.2)
e = max
i - A
a
Представляя (1.4.6) в виде
A
1 -e < 1 < e,
a1
получаем после несложных преобразований
(1 -e)maxa1 < A< (1 + e)mina1.
11
Минимальная относительная ошибка определяется выражением
e = amax amin (1 4 3)
a max + a min
а окончательное значение
A = (1 -eKax =(1 + e)amin = ^M^. (1.4.4)
a min + a max
Определим (n+1)-вершинныИ граф с вершинами 0, 1, 2, ... , n. Вершины 1, j (1 < j) графа соединим дугой (1, j), длина которой равна относительной ошибке при агрегировании (j - 1) операций (1+1), (1+2), ... , j в одну. Обозначим эту длину e1,j.
Пусть задана допустимая ошибка приближения e. Поставим задачу определить агрегированный комплекс с минимальным числом
27
операций так, чтобы относительная ошибка при замене нескольких последовательных операций одной агрегированной операцией не превышала е. Для решения этой задачи достаточно исключить из графа все дуги 1, длины которых превышают e, и в оставшемся частичном графе определить путь, соединяющий начальную вершину 0 с конечной вершиной n и имеющий минимальное число дуг. Эта задача легко решается алгоритмами поиска кратчайших путей в графе.
Пример 1.6.
Комплекс состоит из шести последовательных операций, данные о которых приведены в таблице 1. Длины дуг e, графа, определяемые на основе выражения (1.4.3), приведены в таблице 2.Пусть e = 0,2. Граф с дугами, длины которых не превышают 0,2, приведен на рис. 1.6.
Таблица 1.
i 1 2 3 4 5 6
Wi 12 16 10 15 8 12
ai 3 4 5 5 4 6
Ti 4 4 2 3 2 2
Таблица 2.
1 2 3 4 5 6
о 0 1/7 1/4 1/4 1/4 1/3
1 0 1/9 1/9 1/9 1/5
2 0 0 1/9 1/5
3 0 1/9 1/5
4 0 1/5
5 0
![Рис. 1.6.Толстыми дугами выделены пути с минимальным числом дуг.]()
Рис. 1.6.
Толстыми дугами выделены пути с минимальным числом дуг.
Как видно из рисунка, имеются два пути - (0, 2, 6) и (0, 1, 6)- из двух дуг. Они определяют два оптимальных варианта агрегирования комплекса. В первом варианте объединяются операции 1 и 2 в одну операцию с величиной А, определяемой по выражению (1.4.4):A1 = A(1,2)
2 • 3 • 4 = 24 = 33
7 = 7 = 7,
а также объединяются операции 3, 4, 5 и 6 в одну операцию с величиной
2 • 6 • 4 = 24
10 = 5
= 4,8 .
A2 = A(3,4,5,6)
Во втором варианте операция 1 остается, а объединяются операции 2, 3, 4, 5 и 6 в одну операцию с величиной
![Во втором варианте операция 1 остается, а объединяются операции 2, 3, 4, 5 и 6 в одну операцию с величиной]()
Если взять e = 0,12, то агрегирование в две операции невозможно.
Действительно, соответствующий граф, приведенный на рис. 1.7, не имеет путей из двух дуг.
![Действительно, соответствующий граф, приведенный на рис.<div class=]()
