Задачи формирования состава

Для имеющегося множества N принять решение о включении или невключении в систему нового агента a {a - additional) с функцией затрат ca(ya) = c°a + ea(ya)

не изменяя функций стимулирования прочих агентов;

изменяя функции стимулирования прочих агентов.

Для заданного множества претендентов N0 определить оптимальный состав агентов N.

Задача I относится к случаю уже функционирующей системы, а задача II - к случаю формирования начального состава системы.

Задача 1.1

С учетом пришедшего агента целевая функция центра принимает вид

фАуа) = Н(Г+уа)-С0-с°а-Е(Г)-еа(уа) (d - distorted).

целевая функция центра от этого увеличивается, то есть если выполнено условие

тахФДуа) > Фтах = Ф(7*).

Уа'^О

Тогда условие выгодности привлечения нового агента принимает вид:

тах[Н(Г+уа)-Н(Г)-еа(уа)] = тах[АН(уа)-еа(уа)]>с°а,

Уа^О Уа>О

или, иначе,

тах.[АН(уа)-са(уа)]>0.

У а? О

Рис. 4 показывает, как графически можно найти оптимальный план нового агента. Начиная от точки Y* от функции дохода центра отнимается функция затрат дополнительного агента. Если максимум получившейся функции достигается правее точки 7* - добавление дополнительного агента целесообразно.

А Н(ГЛуа)-са(уа) > Г Т+уа Y

Я(Г)

Рис. 4. Графическое построение оптимального плана нового агента

Задача 1.2

В отличие от предыдущей модели, при введении нового агента центр имеет возможность пересчитать планы и стимулирование всех агентов. Тогда равновесные значения исходной целевой функции центра и «новой» целевой функции будут иметь вид:

(84) Фтах=Ф(7*) = тах[Я(7)- mm !>,(>> )]

7 y-Lyi=riGN

ieN

Ф^х = Фй(Y'*) = тах[Я(7') - min {^(у,) + са(уа)}].

Y У,Уd- 2^У'+У«=Т ieN

ieN

Лемма 10.

Ф^х = тах[Я(Г) - min {C(Y) + ca(ya)}].

Г' Г,уа:Г+уа=Г'

Доказательство. Необходимо показать, что

min [$>,.(yi) + ca(ya)]= min [ min [ 1>г (z,)] + са(ja)].

_ у-уa- ieN

ieN

/,Уа- ~z''Hzi=Y ieN Y+ya=Y' ieN

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

Лемма 10 позволяет свести задачу нахождения максимального значения «новой» целевой функции центра к задаче

81

стимулирования для двух игроков - нового агента а, и «агента», затраты которого описываются функцией С(7), представляющего собой совокупность имеющихся агентов.

Тем не менее, задачу можно еще упростить, если число агентов п в системе велико. В этом случае для нахождения приближенного решения задачи функции дохода H(Y) и затрат C(Y) можно линеаризовать в окрестности точки У*. Так как У* - точка максимума «старой целевой функции центра», то

Н'(Y*) =-С'(Y*), поэтому линеаризация выглядит следующим

образом:

H(Y) = H(Y*) + a{Y - Y*), C(Y) = C(Y*)-a(Y-Y*), где a- предельные затраты (или, что то же самое, предельная доходность в «старой» точке равновесия). Тогда

Ф^ах =H{Y*)-C{Y*) + mm\a{Y<-Y*)~ min {a{Y-Y*) +

Г Г,уа.Г+уа=Г'

+ са(уа)}1 = Фmax+max[a7'- min JaY + cJyJ}],

Г' Г,уа:Г+уа=Г'

поэтому условие выгодности добавления нового агента -

Ф1х-Фтах=тах[а7'- min JaY+ са(уа)}]> 0.

Можно вычислить внутренний минимум выражения (86). Условие Лагранжа (равновесные значения Y и уа обозначены знаком **, в отличие от «старого» равновесия Y*) дает условие на

производную затрат нового агента: а = с'а (у**) . Отсюда можно выразить оптимальный план нового агента у** = [с'а \ 1 (а). Тогда Y** = Г'-у** и условие (86) преобразуется к выражению

max[aY'-a(Y'-y**) - cfl (уГ)}] = а • уГ - cfl (уГ) > 0 .

Сведение к линейному случаю привело к исчезновению Г' из максимизируемого выражения.

выигрыш центра. Если выбрать Y** = Y*, то результат решения линеаризованной задачи 1.2 совпадает с решением линеаризованной задачи 1.1 (получаемой из условия (83) линеаризацией функций дохода и затрат аналогично (85)).

Отсюда можно сделать вывод о том, что наличие у центра возможности изменения планов «старых» агентов в задаче 1.2 дает прибавку второго порядка малости к результату центра в задаче 1.1. Таким образом, большие системы (для которых линеаризация в окрестности равновесной точки корректна) достаточно сложны, чтобы неизбежные накладные расходы по изменению стимулирования всех агентов системы перекрывали выигрыш от оптимизации планов, связанной с появлением нового агента.

В то же время, последовательное добавление большого количества агентов все больше сдвигает вектор планов «старых» агентов (рассчитанный для исходного состава N) от вектора оптимальных планов, то есть, в активно развивающихся ОС центр время от времени все же должен корректировать планы для нового состава агентов, даже если изменение существующих планов связано с организационными сложностями.

С технической точки зрения, пересчет оптимальных планов при введении нового агента сводится к вычислению новой функции совокупных затрат CN+a(YN+a) = min \СХ{YN) + са(уа)] и

YN+ya=YN+a

последующей оптимизации целевой функции центра Ф\ А )- Эта задача при известных функциях затрат CN(.) и са(.) является задачей выпуклого программирования.

В то же время, для минимизации времени «перенастройки» системы при изменении ее состава или изменении функции дохода центра полезно для имеющегося состава агентов иметь рассчитанные оптимальные планы у* (Y) в некоторой окрестности оптимального совокупного плана Y*.

Задача II

«Прямолинейный» подход к задаче первоначального формирования состава N агентов из множества претендентов N,, (каждый из претендентов полностью описывается своей функцией затрат с {у,)), состоит в рассмотрении 2Л° -1 задач стимулирования для каждого непустого подмножества N0 и последующего выбора подмножества, доставляющего максимум целевой функции центра. Несмотря на то, что никаких теоретических трудностей эта процедура не вызывает, однако вычислительно

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

Решение задачи стимулирования (с учетом упрощения (78)) для каждого состава N с N0 состоит из следующих этапов:

Вычисление совокупной функции затрат (задача выпуклой оптимизации с \N\ переменными и одним ограничением):

CN(Y) = min ЕсДя).

У'- 2.У-=Г ieN

ieN

Решение одномерной задачи выпуклой оптимизации

ФМТАХ (У; ) = maх[Я(7) - CN (7)].

Затем производится определение оптимального состава

N* е Arg max0Nmax.

NОдин из возможных подходов к упрощению задачи состоит в поиске условий, позволяющих сократить множество рассматриваемых составов. Примеры таких условий рассматриваются ниже.

Мы не будем рассматривать случай, когда сг° = 0 для всех /' е N0. В этом случае, очевидно, N* = N0. Однако если условие с- = 0 выполняется только для некоторых агентов (множество таких агентов обозначим М). этот факт позволяет сократить количество рассматриваемых составов только составами, в которые входят все агенты множествам.

Рассмотрим агентов с линейными затратами вида

Сг(Уг) = Сг +7гУг-

Выражение (88) для произвольного состава N CI NTL принимает вид

Cn(Y)=Zc°+Ymm7l ,

iGN iGN

то есть для любого состава работает только самый «дешевый» агент, остальные получают нулевой план и минимальную ставку

сг°. Поэтому очевидно, что в линейном случае кандидатами на оптимальный состав могут быть только составы, состоящие только из одного агента.

Решая таким образом N0 задач стимулирования (для системы с одним агентом), определяем для каждой системы значение целевой функции центра и выбираем агента, при котором выигрыш центра максимален:

(92) Г =аг§шах[я(7;)-Гг7; -с,0], где Y* =[Я'Г1(у1).

Как видно из этого выражения, даже рассмотрение линейных функций затрат, хоть и упрощает задачу, все же не позволяет ввести априорное ранжирование агентов на основании только знания функций их затрат, что позволило бы, не решая задачу стимулирования, определить оптимальный состав системы.

Другой возможный подход состоит в модификации самой задачи: определим функции затрат претендентов следующим образом:

ч k (J, ),>-,> о

ci (Уг) = 1 и решим /v'rмерную задачу максимизации

О, Уг = О

Если оп

разрывной функции у = arg max

у

#(!>,)- (Уг)

ieN„ zeW„

тимальный план некоторого агента равен нулю, значит, этот агент не входит в оптимальный состав исполнителей. Этот прием позволяет свести 2( 2Л° -1) задач оптимизации к двум, но с разрывными функциями.

Пример 6. «Задача первоначального формирования состава».

Рассмотрим задачу выбора состава исполнителей из двух претендентов с функциями затрат

С1 (Jl ) = 2 + У]2 , с2 {у 2 ) = 1 + 2у2 .

Как следует из вида функций затрат, первый кандидат отличается относительно большей производительностью (его функция затрат возрастает более полого), но и более высокими начальными затратами, чем второй.

Пусть доход центра возрастает линейно, Я (7) = aY .

Построим функцию затрат C(Y) = min (Cj ) + с2(у2)).

yl+y2=Y

В случае двух претендентов нужно рассмотреть лишь три возможных состава - функции затрат для каждого из них можно построить непосредственно:

Q(7) = 2 + 72, C2(Y) = 1 + 2Y2, Cn(Y) = 3 + ^Y2,

функции затрат системы, состоящей из первого агента, второго агента и обоих агентов соответственно.

Очевидно, что С (7) = min[Cj (7), С2 (7), Сп (7)], то есть

1 + 272 npuY< 1 С(7) = Ь + 72 при 1 < 7 < 1.5 3 + 572 /9 иры7>1.5.

Оптимальный план 7 находится из условия равенства производных функции дохода центра и функции минимальных затрат С(7). Это условие имеет вид: H'(Y) = а = С'(7). Таким образом, в зависимости от значения доходности а, оптимальным составом будет:

При 0 < а < 3 - система из единственного первого агента,

при 3 < а < 4.25 - система из единственного второго агента,

при а > 4.25 - система из обоих агентов (при этом план второго агента в два раза меньше плана первого агента). •