Випадок 2 - фіксовані обсяги робіт, будь-якої агент може виконувати

Припустимо, що число агентів дорівнює числу функцій: n = m. позначимо
| R1
sij = ci (R, ri) = r / ф (-). i e N, j e M. Тоді задача оптимального
r /
розподілу функцій буде описуватися виразами (10) - (12) розділу 2.1, тобто буде класичною задачею про призначення.
Згадаймо тепер, що ми досліджуємо команди, що характеризуються автономністю діяльності агентів. Остання в тому числі на увазі, що члени команди можуть самостійно приймати рішення про те, які роботи і в яких обсягах їм виконувати. Якщо інтереси всіх членів команди єдині і полягають в мінімізації сумарних витрат, то за умови, що всі параметри є загальним знанням, кожен з агентів може вирішити задачу (6) або завдання (10) - (12) розділу 2.1 і вибрати оптимальні дії.
Однак може виявитися, що кожен з членів команди переслідує власні інтереси. Як же буде функціонувати команда в цьому випадку, і як домогтися злагодженої і ефективної (в сенсі мінімуму сумарних витрат) роботи її членів? Для відповіді на це питання розглянемо наступну модель, в якій вже з'являються елементи управління, характерного для ієрархічних організаційних систем.
Перенумеруем агентів таким чином, щоб оптимальним рішенням задачі про призначення було діагональне призначення (x / i = 1, ХЦ = 0, j * i, i, j e N). 80
Нехай за виконання j-ої функції встановлено винагороду qj, j е M. Виграш i-го агента описується різницею між винагородою за виконання обраної ним функції j і витратами на виконання цієї функції: qj - sij. г, j е N. Запитується,
які повинні бути розміри винагород, щоб вибори агентів відповідали оптимальному вирішенню завдання про призначення. Для відповіді на це питання скористаємося отриманими в [75] результатами рішення задачі синтезу оптимальних нормативних рангових систем стимулювання.
Для того щоб i-му агенту було вигідно вибирати i-ю функцію (а не будь-яку іншу), необхідно і достатньо виконання наступної системи нерівностей:
qi - su> qj - -V г j е N
Запишемо (12) у вигляді
qj - qi. aj, i, j е N,
де aij = sij -. i, j е N. Позначимо сумарне винагороду агентів
J = X qi,
г = 1
де q задовольняє (13). Тоді задача полягає у виборі невід'ємних винагород, які мінімізують вираз (14) за умови (13). Введемо в розгляд «-вершина граф Ga, ваги дуг в якому визначаються || агу ||.

Завдання мінімізації (14) за умови (13) є завданням про мінімальні невід'ємних потенціалах вершин графа Ga, для існування вирішення якої необхідно і досить відсутності контурів негативною довжини [7]. Розглянемо наступну задачу про призначення:
п
X sv Xj ® min
i, j = 1
хп е, i, j е N,
X Xij = 1, j е N,
г = 1
X Xij = 1, i е N.
j = 1
Затвердження 4.2. Для того щоб в оптимальному вирішенні завдання (15) - (18) xii = 1, xij = 0, j Ф i, i, j e N, необхідно і достатньо, щоб граф Ga не мав контурів негативною довжини.
З теорії графів відомо [7], що в оптимальному вирішенні завдання (15) - (18) мінімальна не тільки сума потенціалів вершин графа Ga (сумарні витрати на винагороду членів команди), але і мінімальні все потенціали вершин (індивідуальні винагороди).
Маючи результат затвердження 4.2, ми маємо можливість запропонувати алгоритм обчислення мінімальних потенціалів. Поставимо у відповідність обмеженням (17) - (18) двоїсті змінні Uj і vi, i, j e N. Обмеження двоїстої задачі мають вигляд: (19) Uj - Vi. aij, i, j e N.
Зауважимо, що, так як xii = 1, i e N, то ut - vi = aii = 0, а значить ui = v = qi. Використовуючи цей факт, визначимо наступний алгоритм:
Крок 0. Uj = Cjj, j e N.
Крок 1. V; -: = max jeN J J
Крок 2. U-: = max, j e N.
jeN
Послідовне повторення кроків 1 і 2 алгоритму кінцеве число (очевидно, що не перевищує n) раз дасть оптимальне рішення задачі (15) - (18):
qi = ui = Vi, i e N.
Наведений вище алгоритм дозволяє вирішувати задачу пошуку мінімальних потенціалів графа Ga, які відповідають умові (13), тобто спонукають членів команди вибрати оптимальні дії.
Позначимо C2 (r, R) - значення цільової функції в оптимальному вирішенні завдання (15) - (18). Легко бачити, що
"R> 0," R> 0 C2 (r, R)> Q (r, R),
Тобто сумарні витрати команди на виконання фіксованого набору робіт в разі фіксації «ролей» членів команди не нижче, ніж у випадку, коли кожен член команди може виконувати кілька функцій одночасно. Це властивість оптимальних рішень має прозору змістовну інтерпретацію в термінах властивостей організаційних структур [72]. Зробимо невеличкий відступ, прояснює зв'язок між властивостями опти-
мінімальних рішень задач розподілу функцій і типами організаційних структур.