<<
>>

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

Случай линейных зависимостей скоростей операций от количества ресурсов широко распространен, поскольку пропорциональность объема выполненных работ количеству ресурсов довольно часто имеет место с достаточной для практики точностью.
Пусть

. 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 снова объединяем в одну и рассматриваем второй интервал аналогичным образом, и т.д.

<< | >>
Источник: Бурков В.Н., Квон О.Ф., Цитович Л.А.. МОДЕЛИ И МЕТОДЫ МУЛЬТИПРОЕКТНОГО УПРАВЛЕНИЯ -М., 1997 (Препринт / Институт проблем управления). - 62 с.. 1997

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

- Авторское право - Аграрное право - Адвокатура - Административное право - Административный процесс - Антимонопольно-конкурентное право - Арбитражный (хозяйственный) процесс - Аудит - Банковская система - Банковское право - Бизнес - Бухгалтерский учет - Вещное право - Государственное право и управление - Гражданское право и процесс - Денежное обращение, финансы и кредит - Деньги - Дипломатическое и консульское право - Договорное право - Жилищное право - Земельное право - Избирательное право - Инвестиционное право - Информационное право - Исполнительное производство - История - История государства и права - История политических и правовых учений - Конкурсное право - Конституционное право - Корпоративное право - Криминалистика - Криминология - Маркетинг - Медицинское право - Международное право - Менеджмент - Муниципальное право - Налоговое право - Наследственное право - Нотариат - Обязательственное право - Оперативно-розыскная деятельность - Права человека - Право зарубежных стран - Право социального обеспечения - Правоведение - Правоохранительная деятельность - Предпринимательское право - Семейное право - Страховое право - Судопроизводство - Таможенное право - Теория государства и права - Трудовое право - Уголовно-исполнительное право - Уголовное право - Уголовный процесс - Философия - Финансовое право - Хозяйственное право - Хозяйственный процесс - Экологическое право - Экономика - Ювенальное право - Юридическая деятельность - Юридическая техника - Юридические лица -