<<
>>

1.4. Методы приближенного агрегирования линейных моделей

Линейная зависимость скорости операции от количества ресурсов широко применяется на практике. Без ограничения общности линейную зависимость можно представить в виде

/ ч fu,, u, < a,

f (u, H ' ' > '. (14.1)

[a;, u, >a,

Действительно, в общем случае линейная зависимость имеет вид

/ ч fk, • u,, u, < a, f, (u, H 1 1 1 '.

[k, • a,, u, > a,

Как известно, описание операции инвариантно к умножению скорости и объема операции на любое положительное число. Поэтому, положив f, _ -k-f,, W, _ -k- W,, мы получим зависимость (1.4.1)

Метод агрегирования рассмотрим сначала для случая

независимых операций. Обозначим t, _ W^ минимальную

продолжительность ьой операции,

T _ max t,

минимальную продолжительность комплекса из n независимых операций. Положим

A _?WL _ W . T T

Величины А и Т примем за параметры агрегированной операции. Эквивалентный объем агрегированной операции определяется как сумма объемов операций, а зависимость скорости агрегированной операции от количества ресурсов N имеет вид (1.4.1), то есть

.. Ч In, n3V 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=

1.7, не имеет путей из двух дуг." />

Оптимальный вариант всего один. В этом варианте объединяются операции (2, 3, 4, 5) в одну агрегированную операцию со значением

/ Ч 2 • 4 • 5 40 4 A2 _ A(2,3,4,5) _ _ — _ 4 —

2 v / 9 9 9

Рассмотрим теперь произвольный комплекс операций. Возьмем продолжительности всех операций равными минимальным значениям tj, и определим критический путь в сети. Обозначим через Ткр длину критического пути. Поставим задачу выравнивания ресурсов, то есть определения максимально равномерного графика ресурсов, требуемых для выполнения комплекса операций за время Ткр. Эту задачу удобнее рассматривать, когда сетевой график изображен в форме «операции- дуги», то есть дуги сетевого графика соответствуют операциям, а вершины - событиям (моментам завершения одной или нескольких операций). Задача выравнивания ресурсов эффективно решается при заданном упорядочении 0, 1,2, ... , m моментов завершения событий (m+1 - число событий). Эта задача рассматривалась еще в шестидесятых годах [4]. В [5] для ее решения предлагалась гидродинамическая модель (переток жидкости между сообщающимися 30

сосудами), а в [4] задача решалась методом квадратичного программирования. Мы рассмотрим геометрический подход к решению задачи. Обозначим Ak, - общий объем операций, которые должны быть выполнены в первых k интервалах, Вк - общий объем операций, которые могут быть выполнены в первых k интервалах. Для определения Ак необходимо определить правосдвинутый график использования ресурсов, то есть график, соответствующий началу всех операций в наиболее поздние моменты времени. Для определения Вк необходимо определить левосдвинутый график использования ресурсов, то есть график, соответствующий началу всех операций в наиболее ранние моменты времени. На основе этих

графиков определяются значения Ак и Вк к = 1, m.

Построим на плоскости графики зависимости A; и Вк от соответствующих моментов совершения событий наиболее поздних

поздних Тк и наиболее ранних Т]р.

Область между двумя графиками определяет множество возможных состояний комплекса операций, определяемых как объем операций, выполненный к соответствующему моменту t. Любому процессу выполнения операций комплекса соответствует траектория, соединяющая точку 0 с точкой К на рис. 1.8. Тангенс угла наклона этой траектории определяет количество ресурсов в соответствующий момент времени. Очевидно, что решению задачи выравнивания уровня ресурсов соответствует кратчайшая траектория, соединяющая точку 0 с точкой К. Точки излома траектории определяют моменты изменения количества ресурсов. Поиск кратчайшей траектории можно осуществлять непосредственно на плоскости с помощью карандаша и линейки.

Рис.1.8.Пример 1.7. Рассмотрим комплекс из четырех операций (рис 1.9).

Рис.1.8.

Пример 1.7. Рассмотрим комплекс из четырех операций (рис 1.9).

Рис. 1.9.Числа у дуг на рис. 1.9 равны аь а числа в скобках - минимальным продолжительностям tt.

Рис. 1.9.

Числа у дуг на рис. 1.9 равны аь а числа в скобках - минимальным продолжительностям tt.

Критический путь выделен толстыми дугами. График зависимостей {Ak} и {Bk} приведены на рис. 1.10.

^w к

Рис. 1.10.Из рисунка видно, что кратчайшая траектория проходит через точку В.

Рис. 1.10.

Из рисунка видно, что кратчайшая траектория проходит через точку В.

Таким образом, мы имеем оптимальный график использования ресурсов, состоящий из двух участков. На отрезке [0, 5] 32 уровень ресурсов равен N1 = 26/5 = 5,2, а на отрезке [5, 10] - N2 = 27/5 = 5,4.
Поэтому комплекс можно представить в виде двух последовательных агрегированных операции. Первая агрегированная операция объединяет две операции - (0, 1) и (0, 2), имеет объем Wt = 26 и величину А1 = 5,2. Вторая агрегированная операция объединяет три операции - (1, 2), (1, 3) и (2, 3) имеет объем W2 = 27 и величину А2 = 5,4. Допуская относительную ошибку порядка 2% можно весь комплекс заменить одной агрегированной операцией объемом W = 53 и величиной А2 = 5,3.

Пример 1.8. Рассмотрим комплекс из шести операций, рис. 1.11.

Пример 1.8. Рассмотрим комплекс из шести операций, рис. 1.11.

45. - 40..

Рис. 1.12.T50- ¦'WГрафик {Ак}, {Вк} приведен на рис. 1.12.

о

¦||:1! 'I" ' —I—I—I—I—t-

3 4

6

Рис. 1.12.

T

50- ¦'W

График {Ак}, {Вк} приведен на рис. 1.12.

В данном случае удается уменьшить число операций за счет агрегирования только до четырех. Однако, если требование равномерной загрузки ресурсов на комплексах является существенным, можно добиться этого, увеличив минимальную продолжительность агрегированного комплекса. Пунктирная прямая OL на рис. 1.12, проходящая через точку М, соответствует агрегированию комплекса в одну операцию с параметрами Tmin= 9 9/29, A = 45/6.

<< | >>
Источник: Баркалов С.А., Бурков В.Н., Гилязов Н.М.. Методы агрегирования в управлении проектами. М.: ИПУ РАН, 1999- 55 с.. 1999

Еще по теме 1.4. Методы приближенного агрегирования линейных моделей:

  1. 1.2 Методы основанные на построении модели лица.
  2. 1.3.2. Методы классификации с предварительной обработкой сигнала
  3. 2.6. Линейная сложность
  4. 6.1. Классическая линейная модель регрессионного анализа
  5. 6.1.7. Команда построения линейной модели регрессии
  6. ГЛАВА 1. Методы построения агрегированных операций
  7. 1.4. Методы приближенного агрегирования линейных моделей
  8. 3.3. Концептуальные положения разработки модели инвестиционной деятельности естественной монополии
  9. БИБЛИОГРАФИЯ
  10. Оценка математической модели прогнозирования.
  11. § 65. Симплекс-метод решения задач линейного программирования, М-метод
  12. 2.3.2» Анализ линейной модели инноваций  
  13. 2.3. Регрессионные модели оценки ставки восстановления
  14. Матричный метод решения систем линейных уравнений.
  15. От линейной модели к круговой
  16. Линейная модель
  17. 4. Проекционные методыОбширный класс методов приближенного решения уравнений вида Аи = / использует следующий ПОДХОД: решение ищется В виде UN = = где коэффициенты а, определяются из условия равенства
  18. Исследование методов решения задач линейного программирования. Лекция, 2017
  19. Исследование методов решения задач линейного программирования. Метод северо-западного угла.
- Менеджмент предприятий - Основы менеджмента -
- Архитектура и строительство - Безопасность жизнедеятельности - Библиотечное дело - Бизнес - Биология - Военные дисциплины - География - Геология - Демография - Диссертации России - Естествознание - Журналистика и СМИ - Информатика, вычислительная техника и управление - Искусствоведение - История - Культурология - Литература - Маркетинг - Математика - Медицина - Менеджмент - Педагогика - Политология - Право России - Право України - Промышленность - Психология - Реклама - Религиоведение - Социология - Страхование - Технические науки - Учебный процесс - Физика - Философия - Финансы - Химия - Художественные науки - Экология - Экономика - Энергетика - Юриспруденция - Языкознание -