Линейные зависимости скоростей от количества ресурсов

. v Гц, если ui < ai

wi = fi (ui ) = 1 > .

[ai, если ui > ai

n

X Xiq > Wi , i = 1,

q

iq

Xiq < ai ¦ Tq, i = 1, n, q = 1,k.

Обозначим, как и ранее, .iq - объем работ i-го проекта, выполняемых в q-ом интервале. Рассмотрим задачу о возможности реализации проекта в первых k интервалах. Эта задача сводится к проверке существования решений следующей системы линейных неравенств:

Необходимым условием существования решения этой системы является, очевидно, следующее:

У NqTq >У Wi = W.

q

Покажем, что если w. = ga., i = 1, n, то это условие является достаточным

Nq — —

Действительно, возьмем решение xiq = ai - Tq , i = 1, n, q = 1, k Покажем, что это решение является допустимым. Имеем:

У Xiq = NqTq

^Xiq = A = W ^NqTq > ^

так как У NqTq > W.

q

Доказанное свойство позволяет предложить эффективный алгоритм решения задачи. Сначала упорядочим все операции по убыванию величин Р. = Wi /ai. Все операции с одинаковыми Р. объединим в одну операцию с объемом, равным сумме объемов, и с величиной a, равной сумме соответствующих а.. Пусть после такого преобразования осталось m операций с различными значениями р., пронумерованными по убыванию р., то есть р1 > р2 > ... > pm.

1 шаг. Рассматриваем первый интервал и распределяем ресурс в объеме N1T1 так, чтобы максимально выровнять числа {p.}. Для этого определяем l такое, что

У ai < N1

i=1

X ai > N-

i=1

i-1

Определяем uc = N, - X ai, ti = min(pi - p 1+1)

i<1 v \'

i=1

al

p = min

u i

T-;t-; (p i -p i+i)

и полагаем

Wi - pai, i = 1,1 - 1 Wi -pu i, i = 1

xii =<

0, i = 1 +1, m

Все операции с одинаковыми pi снова объединяем в одну и рассматриваем второй интервал аналогичным образом, и т.д.