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

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

ОГЛАВЛЕНИЕ

Следующая >>

сначала при втором уровне ресурса (w2 = 5) в течение одного дня, а
затем при первом (w1 = 3), то операция, как легко проверить,
завершится за 41/3 дня, что больше 4. Ошибки в определении времени
завершения операции объясняются тем, что скорость завершения
операции является средней величиной. Для уменьшения ошибки
следует соответствующим образом выбрать объемы частей операции.
Так, если взять объем первой части x1 = 7,5, и объем второй части x2 =
7,5, то ошибки не возникнет. Действительно, при выполнении первой
7,5
части со скоростью w1 = 3, она будет завершена за /3 = 2,5 дня.
Вторая часть при скорости w2 = 5 будет завершена за 7,5/5 = 1,5 дня, что
в сумме даст 4 дня.
Рассмотренный пример показывает, насколько важно выбрать
объемы частей операции при ее выполнении с переменной
интенсивностью.
Рассмотрим задачу выбора объемов частей операции в общем
случае. Пусть операция состоит из n частей, каждая из которых может
выполняться при m различных уровнях ресурсов. Обозначим ?ij -

10
продолжительность i-ой части при j-ом уровне ресурсов, уi - объем i-ой
части операции, Qj - продолжительность операции при j-м уровне
ресурсов. Обозначим далее xij = 1, если i-ая операция выполняется j-м
уровнем ресурсов, xij = 0 в другом случае. Тогда продолжительность
операции определяется на основе ее описания (то есть на основе
объемов частей {уi} и продолжительностей {Qj}) и будет равна
Q = ? y i Q jx i , (1.2.1)
i, j

а истинная продолжительность
T = ? x ij ? ij . (1.2.2)
i, j

Относительная ошибка описания операции составит
Q
? = 1? . (1.2.3)
T
Поставим задачу определить объемы частей и
{уi}
продолжительности {Qj} так, чтобы ошибка ? была минимальной.
Очевидно, что если существуют числа {уi} такие, что ?ij = уiTj, где
Tj = ? ? ij , то ошибка ? = 0. Запишем условие (1.2.3) в виде
i

Q
? ? ? 1? ??
T
(1.2.4)
(1 ? ?)T ? Q ? (1 + ?)T .
Условия (1.2.4) можно представить в виде двух неравенств:

? min ((1 + ?)?ij ? yi Q j ) ? 0 ,
j
i


? min (yiQ j ? (1 ? ?)?ij ) ? 0 .
j
i

Наконец, введя новые переменные:


11
( )
u i = min (1 + ? )? ij ? y i Q j ,
j

( )
v i = min y i Q j ? (1 ? ? )? ij ,
j

приведем задачу к следующему виду:
? > min ,

? ui ? 0 , (1.2.5)
i

? vi ? 0 ,
i

u i = (1 + ? )? ij ? y i Q j , i = 1, n, j = 1, m ,
v i = y i Q j ? (1 ? ? )? ij i = 1, n, j = 1, m .
(1.2.5)
Это задача нелинейного программирования. Если зафиксировать {уш}
или {Qj}, то она становится задачей линейного программирования.
Поэтому задачу (1.2.5) можно решать как последовательность задач
линейного программирования, фиксируя сначала значения {Qj}

(например, взяв Q j = ? ?ij , j = 1, m ), а затем {уi} и т.д.
i


Заметим, что в ряде случаев величины {Qj} выбираются из
других соображений. Так, например, мы хотим получить описание
операции с линейной зависимостью скорости операции от количества
W
ресурсов, то есть f(w) = u = /Q. В этом случае Q = W u j , где uj -

количество ресурсов, соответствующее j-му уровню. Если принять
W = 1, то Q j = становится известным и задача (1.2.5) является
1
uj

задачей линейного программирования.
Рассмотрим приближенный метод построения описания
операции. В его основе лежит идея приближенного представления




12
чисел ?ij в виде yiQj. Относительная ошибка такого представления
составит

y iQ j
? = max 1 ? (1.2.6)
.
? ij
i, j


Представим (1.2.6) в виде
? ij ? ij
(1 ? ?i ) max ? y i ? (1 + ?i ) min (1.2.7)
Qj Qj
j
j


или
? ij ? ij
? min
max
Qj Qj
j
j
?i = (1.2.8)
,
? ij ? ij
+ min
max
Qj Qj
j
j


? = max ?i .
i

Легко показать, что задача минимизации ? сводится к задаче
минимизации ? = max ?i , где
i

max ? ij w j
1
j
?i = , wj = (1.2.9)
.
min ? ij w j Qj
j

Условие (1.2.9) легко сводится к виду

?
wj 1 1
? max ik = q kj . (1.2.10)
? i ? ij ?
wk

Обозначим ln wj = ?j, ln ? = ?, ln qkj = lkj. Тогда система (1.2.10)
сведется к виду

?j - ?k ? lkj - ? , (1.2.11)
j, k = 1, m .

Необходимо определить минимальную ? ? 0, при которой система
(1.2.11) имеет решение.

13
Определим полный граф с m вершинами и длинами дуг (lkj- ?).
Как известно, система (1.2.11) имеет решение, если в графе
отсутствуют контуры положительной длины.

Алгоритм решения задачи.
1 шаг. Положим ?0 = 0. Определим контур µ1 положительной
длины. Если таких контуров нет, то задача решена (? = ?0 = 0). Если
L(µ1) > 0, то полагаем длины дуг равными lij- ?1, где

L(µ1 )
?1 =
n (µ1 )
(?(µ) - число дуг контура µ).
k-й шаг. Определяем контур µk положительной длины, при
длинах дуг lij- ?k-1. LkЕсли Lk = L(µk) ? 0, то ? = ?k-1. Если L(µk) > 0, то
определяем


1
?k = Lk ,
nk

где nk = n(µk), и переходим к следующему шагу.
За конечное число шагов будет получена величина ? такая, что в
графе отсутствуют контуры положительной длины при длинах дуг
lij - ?. Соответствующие потенциалы вершин {?i} и величина ?
определяют оптимальное решение задачи (1.2.11), а значит (1.2.10) и
(1.2.7). Определив ?i, мы можем найти уi и, следовательно, получить
полное описание операции.

Пример 1.2. Возьмем ?11 = 2, ?21 = 3, ?12 = 1, ?22 = 2. Имеем

?? ? ? ?2 3?
q12 = max ? 11 ; 21 ? = max ? ; ? = 2 ,
? ?12 ? 22 ? ?1 2?

14
?? ? ? ?1 2? 2
q 21 = max ? 12 ; 22 ? = max ? ; ? = .
? ?11 ? 21 ? ?2 3? 3
В данном случае задачу можно решить не переходя к логарифмам,
определяя вместо длины контура его усиление. Усиление контура

(1,2,1) равно 4/3 > 1. Следовательно, ? = 3 . Имеем
2 , w1 = 1, w2 =
3

1
Q1 = 1, Q2 = ,
3


?Q Q ? ?Q Q ?
max ? 1 ; 2 ? ? min? 1 ; 2 ?
?? ? ? ?? ? ?
? 11 12 ? ? 11 12 ? ? 0,09
?1 =
?Q Q ? ?Q Q ?
max ? 1 ; 2 ? + min? 1 ; 2 ?
?? ? ? ?? ? ?
? 11 12 ? ? 11 12 ?

?Q Q ? ?Q Q ?
max ? 1 ; 2 ? ? min? 1 ; 2 ?
?? ? ? ?? ? ?
? 21 22 ? ? 21 22 ? ? 0,06 .
?2 =
?Q Q ? ?Q Q ?
max ? 1 ; 2 ? + min? 1 ; 2 ?
?? ? ? ?? ? ?
? 21 22 ? ? 21 22 ?
Соответственно получаем

?Q Q ? 0,92
y1 = (1 ? ?1 ) ? max ? 1 ; 2 ?=
?? ? ?
? 11 12 ? 3
?Q Q ? 0,94
y 2 = (1 ? ?2 ) ? max ? 1 ; 2 ?= .
?? ? ?
? 21 22 ? 3


1.3. Идеальное агрегирование

Агрегирование, то есть представление сложной модели
большим числом параметров) в упрощенном
(описываемой
(агрегированном) виде (описываемой небольшим числом параметров)
не только эффективный метод решения задач большой размерности,

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

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

ОГЛАВЛЕНИЕ

Следующая >>