1.2. Построение модели операции

( ) W f ( ) W

t(v ) = ТМ или f (v ^"М, f (v) t(v)

и скорость операции определяется с точностью до параметра W (при известной зависимости t(v) объем W может выбираться произвольно). Ситуация становится сложнее, если операция выполняется с переменным уровнем ресурсов.

Пример 1.1. Пусть операция состоит из двух частей, каждая из которых может выполняться при двух уровнях ресурсов. Обозначим tj

продолжительность i-ой части при j-ом уровне ресурса, i = 1, 2; j = 1, 2;

T1 = т11 + т21 T2 = т12 + т22

продолжительности операций при выполнении обеих частей, соответственно при первом и втором уровнях ресурсов. Пусть

т11 =2, т21 =3, т12 =1, т22 =2, T1=5, T2=3.

Примем объем операции W = 15. Тогда при T1 = 5 средняя скорость операции w1 = 3, а при Т2 = 3 - w2 = 5. Пусть операция выполняется сначала при первом уровне ресурсов в течение 2 дней, а затем при втором уровне ресурсов. Тогда очевидно, что операция будет закончена за 4 дня, так как t11 + t22 = 4. Определим, однако, момент завершения операции на основе средних скоростей w1 и w2;. За два дня будет выполнено при скорости w1 = 3 х(2) = 6 ед. объема операции. Оставшиеся 15 - 6 = 9 ед. объема при скорости w2 = 5 будут выполнены за 9/5 = 1,8 дня. В целом операция будет завершена за 3,8 дня, что меньше истинного срока t = 4.

Рассмотренный пример показывает, насколько важно выбрать объемы частей операции при ее выполнении с переменной интенсивностью.

Рассмотрим задачу выбора объемов частей операции в общем случае. Пусть операция состоит из n частей, каждая из которых может выполняться при m различных уровнях ресурсов. Обозначим xij - продолжительность i-ой части при j-ом уровне ресурсов, уi - объем i-ой части операции, Qj - продолжительность операции при j-м уровне ресурсов. Обозначим далее xij = 1, если i-ая операция выполняется j-м уровнем ресурсов, xij = 0 в другом случае. Тогда продолжительность операции определяется на основе ее описания (то есть на основе объемов частей {у^ и продолжительностей {Qj}) и будет равна

Q = Х YiQjXi, (1.2.1)

i,j

а истинная продолжительность

т = Х Xijtij. (1.2.2)

У

Относительная ошибка описания операции составит

5 =

1 - Q

(1.2.3)

T

Поставим задачу определить объемы частей {уi} и продолжительности {Qj} так, чтобы ошибка 5 была минимальной. Очевидно, что если существуют числа {у^ такие, что tij = уТ где Tj = ^tiJ , то ошибка 5 = 0. Запишем условие (1.2.3) в виде

-5 < 1 - Q <5 T

(12.4)

(1 -5)Т < Q <(1 + 5)Т. Условия (1.2.4) можно представить в виде двух неравенств: ]Tmin((1 + 5)тц- YiQj )> 0,

]Tmin(yiQj-(1 -5)ТЙ)> 0.

Ui = min((1 + 5)tij - yiQj), Vi = min(yiQJ -(1 -d)tij),

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

5 ® min,

Xui > 0, (1.2.5)

^ >0,

Ui =(1 + 5)tij - yiQj, i = 1,n, j = 1,m,

vi = y Qj-(1 -5)tij i = ^nJ =1,m. (1 2 5)

Это задача нелинейного программирования. Если зафиксировать {уш} или {Qj}, то она становится задачей линейного программирования. Поэтому задачу (1.2.5) можно решать как последовательность задач линейного программирования, фиксируя сначала значения {Qj}

(например, взяв Qj = ^xij, j = 1,m), а затем {У1} и т.д.

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

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

задачей линейного программирования.

Рассмотрим приближенный метод построения описания операции. В его основе лежит идея приближенного представления чисел tj в виде yiQj. Относительная ошибка такого представления составит

yiQj

(1.2.6)

1-

tj

5 = max

i,j

Представим (1.2.6) в виде

T • T •

(1 -5i)max^L j Qj j Qj

или

Tij • Tj

max^L - min- J

5 = j Qj j Qj (1.2.8)

i Tj , • Tij j Qj j Qj

5 = max 5i.

i

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

минимизации e = max ei, где

i

max Tijwj 1

(1.2.9)

ei =—j , wj = —

min Tijwj Qj

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

wj 1 T 1

>-max^- = -qkj. (1.2.10)

wk e i Tj e Обозначим In wj = 1j, In e = h, In qkj = 1kj. Тогда система (1.2.10) сведется к виду

1j - 1k > 1kj - h , j, k = 1,m . (1.2.11)

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

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