- •Глава 2. Применение теории графов
- •2.2. Методы агрегирования в управлении проектами1
- •2.4. Механизмы согласованного выбора1
- •2.5. Метризованные отношения в задачах стимулирования1
- •Запишем (4) в виде
- •2.7. Задача выбора оптимального стандартного набора видов продукции1
- •2.8. Модели закупок1
- •2.10. Оптимизация обменных производственных схем1
- •2.11. Задачи оптимизации производственного
2.4. Механизмы согласованного выбора1
Рассмотрим модель активной системы (АС), состоящей из управляющего органа – центра – и одного управляемого субъекта – активного элемента (АЭ). Стратегией АЭ является выбор действия y A из конечного множества A = {y1, y2, ..., yn}, стратегией центра является выбор механизма стимулирования, то есть назначение плана x X A и выбор функций штрафов ij за отклонения выбора АЭ yj от плана xi и дохода АЭ hj, i, j I = {1, 2, ..., n}.
Целевая функция АЭ fij, определенная на множестве A X представляет собой разность между доходом hj и штрафами ij. Выбирая при заданном плане и штрафах действие, АЭ стремится максимизировать свою целевую функцию.
Пусть на функции дохода и штрафов наложены следующие ограничения:
(1) li hi bi, i I,
(2) dij ij cij, dii = cii = 0, i, j I.
Механизм стимулирования (штрафов), при котором АЭ выгодно выполнять планы, назначаемые центром, называется согласованным.
Задача согласованного выбора заключается в ответе на вопрос – существует ли механизм, согласованный на заданном подмножестве X множества A.
Выпишем условия согласованности для множества X в предположении благожелательности АЭ к центру (в случае равенства АЭ выполняет план):
(3) hi hj - ij, i J, j I,
где J I – множество индексов, соответствующих множеству X.
Преобразуя (3) к hj - hj ij, i, j I, получаем, что штрафы следует выбирать как можно большими, то есть ij = cij. Тогда (3) примет вид:
(4) hj – hi cij, i J, j I.
Пусть j J, тогда соответствующая часть условий hj – hi cij, i J, j I, приводится к виду
(5) hi hj - cij, i J, j I.
Очевидно, следует взять hj = lj. Получаем ограничение на выбор hi:
(6) hi gi = (lj – cij), i J.
Обозначим i = max {li; gi}, i J.
Итак, задача свелась к определению набора {hi}, удовлетворяющих следующим условиям:
(7) ai hi bi, i J,
(8) hj – hi cij, i, j J.
Определим полный граф G(X) с q вершинами, где q = |J| – число элементов множества X, и длинами луг cij. Задача (7)-(8) является задачей о потенциалах. Из результатов раздела 1.2 следует справедливость следующей теоремы1.
Теорема 8 [10, 19]. Для разрешимости системы неравенств (7)-(8) необходимо и достаточно отсутствия в графе G(X) контуров отрицательной длины и выполнения условий:
(9) Lij aj – bi, i, j J,
где Lij – длина минимального пути, соединяющего вершину i с вершиной j.
Если функции штрафов неотрицательны, то есть cij 0, то граф G(X) не имеет контуров отрицательной длины. Тогда (9) дает необходимые и достаточные условия существования согласованного механизма. Для поиска минимальных или максимальных {hij}, обеспечивающих согласованность, достаточно воспользоваться модификацией алгоритма Данцига: выбираем hi(0) = ai (соответственно, hi(0) = bi, где «0» – номер шага алгоритма) и вычисляем последовательно hi(q) = [hj(q-1) - Lij] (hi(q) = [hj(q-1) + Lij]). За конечное число итераций получаем { } ({ }) такие, что - Lij, i, j J.
Отметим, что не существует системы стимулирования, обеспечивающей согласованность механизма на множестве X с меньшими значениями {hi}. Интересно также отметить, что решение задачи, если оно есть всегда существует на множестве так называемых сильно согласованных механизмов [14, 30], то есть механизмов, функция штрафов в которых удовлетворяет «неравенству треугольника»: ij + jk ik, i, j, k J.
Осталось определить значения hi, ij для i, j J, а также ij для i J, j J и для i J, j J. Очевидно, что значения ij i J, j I не влияют на согласованность механизма на множестве J. Значения hi, i J можно взять минимальными: hi = li, а ij для i J, j J - максимальными: ij = cij.
В заключение настоящего раздела рассмотрим случай, когда ограничения наложены не на функции дохода и штрафов по отдельности, а непосредственно на функции fij:
(10) qij fij rij.
Тогда из условий согласованности hj – hi ij hj - qij получаем необходимые и достаточные условия: hi qij, i J, j I.
Таким образом, если bi qij, то задача имеет решение:
(11) = max [li ; qij], i J,
= li, i J,
ij’ = - qij, i J, j I
- rij ij’ - qij, i J, j I.
В работах [10, 19] рассмотрены обобщения описанной модели на случаи: L-согласованных планов (при которых назначение плана x X приводит к тому, что АЭ выбирает действие из множества L(x) A), неопределенности относительно информации о функции дохода АЭ, наличия нескольких взаимосвязанных АЭ.