82
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2012
Для уточнения постановки векторной задачи с критерием (3) вос-
пользуемся известными принципами оптимальности, изложенными в
работе [6]. Напомним, что эффективным по Парето решением много-
критериальной задачи (3) на минимум называется такой вектор
z
*,
что не существует вектора
z
,
при котором строгими являются неко-
торые неравенства в следующей системе:
T
k
(
z
)
≤
T
k
(
z*
),
k
= 1, 2, …,
K.
(4)
Каждую
k
-
ю задачу о назначениях с оптимизируемым критерием
T
k
можно решать «независимо» от других в рамках общей итераци-
онной схемы. Тогда отображение
π
получается в результате пооче-
редного выполнения проецирований
π
k
графов задач (
k
= 1, 2, …,
K
).
Распределение всех заданий по процессорам дает вектор
z
,
равный
сумме векторов
z
k
—
решений всех «скалярных» задач о назначениях
c номерами
k
= 1, 2, …,
K
.
При этом подходе на каждой итерации, на
которой происходит решение
k
-
й задачи о назначениях, в балансовых
соотношениях (2) варьируется лишь слагаемое
z
k
.
В пределе (если он существует) получаем решение векторной за-
дачи о назначениях. Принцип оптимальности, характеризующий
устойчивость решения, заключается в определении вектора
z
*,
обла-
дающего свойством
T
k
(
z
*
|| z
k
)
≤
T
k
(
z
*),
k
= 1, 2, …,
K.
(5)
Здесь через
z
*
|| z
k
обозначен вектор, получаемый из
z
*
заменой
части координат
z
*
k
,
относящихся к
k-
й задаче, на произвольные до-
пустимые значения
z
k
.
Выбор
z
*,
согласно (5), называется ситуацией
равновесия по Нэшу.
Оптимальное решение задачи о назначениях.
Пусть
z
*
отвеча-
ет такому проецированию заданий, которое уравнивает задержки
f
l
(
z
l
),
l
∈
V
h
,
на каждом ярусе графа сети. (Если все эти функции оди-
наковы, то сказанное эквивалентно равномерной загруженности всех
процессоров каждого яруса сети.) Решение
z
*
не всегда точно реали-
зуемо ввиду целочисленности вектора
z
.
Рассмотрим задачу (3) в непрерывной постановке, т. е. вектор
z
непрерывен. С помощью принципа уравнивания Гермейера [6], при-
меняемого при решении минимаксных задач, можно сформулировать
следующую теорему.
Теорема.
Уравнивающее задержки назначение
z
*
является эф-
фективным по Парето и равновесным по Нэшу решением задачи (3).
Как следует из теоремы, в векторной задаче о назначениях прин-
ципы оптимальности (4), (5) не противоречат друг другу. Кроме того,
монотонные свойства функций задержек позволяют эффективно реа-
лизовать уравнивание значений.