Управление и оптимизация / Novikov - Teoriya upravleniya organizatsionnimi sistemami 2005

цию). Анализ данного конкурсного механизма в существенной степени зависит от соотношения числа операций и числа агентов.

Можно показать, что ситуации равновесия Нэша соответствует назначение операций, минимизирующее сумму объективных затрат

	C = åxij Ai j .	(2)
	i, j
Доказательство. Пусть {Sij} – ситуация равновесия.
Пусть x	= 1. Обозначим i = S – Aij = qj = Aij. Заметим,
ij	ij

что если Sik – Aik > i, то агент будет уменьшать Sik, надеясь получить операцию k и обеспечить больший выигрыш. Это уменьшение будет продолжаться до Sik = Aik + i. Если же

Sik < Aik + i, то увеличение Sik до величины Aik + i, очевидно, не изменит назначения операций. Поэтому решение

задачи (1) со значениями {Sij} эквивалентно решению такой

же задачи со значениями Sij = Aij + i, i, j =1, n . Наконец, естественно принять, что все агенты, не получившие операций, будут сообщать минимальные оценки Sij = Aij, надеясь получить какую-либо операцию. Отсюда следует, что на-

значение операций, минимизирующее å(Aij + i )xij ,	ми-
i, j
нимизирует и å Aij xij . Однако отсюда не следует,	что
i, j

операции будут назначены по минимальным ценам Aij, поскольку значения i могут быть весьма высокими. Утверждение доказано.

Рассмотрим сначала случай, когда число агентов равно числу операций.

Пусть S = {Sij} – некоторая ситуация (совокупность цен, предлагаемых агентами), а xij (S) соответствует решению задачи назначения. Заметим, что если агент увеличит

270

цены всех операций на одну и ту же величину Sij′ = Sij +			i,
j =		, то решение задачи назначения не изменится	и
	1, n

агент получит ту же операцию, но по более высокой цене. Поэтому, естественно, возникает тенденция роста цен. До каких пор? Ограничим цену каждой операции некоторой величиной Lj (лимитная цена операции). Ясно, что хотя бы по одной операции каждый агент предложит лимитную цену.

Пусть агенты перенумерованы таким образом, что в оптимальном решении задачи назначения операций при Sij = Aij операцию i получает агент с номером i, и поэтому qi = Sii. Примем начальные цены qi0 = Li, а начальные оцен-

ки Sij0 = Lj, i =1, n , j =1, n . Далее проводим корректировку оценок и цен по формулам:

Sij = min {Li , qi + Aij − Aii}, j ¹ i,	(3)
Sii = qi = min {Li, min Sji}.	(4)
j¹i

Можно показать, что эта процедура конечна и в результате будут получены равновесные оценки {Sij } и, соот-

ветственно, равновесные цены qi* = Sii* , i =1, n . Для нас

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

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

271

Пример 4.1. Пусть	Li = L; Aii = a < L;	Aij = L, j ¹ i.
Очевидно, что ситуация	равновесия Sij = L	для всех i, j.

Соответствующее равновесное решение задачи назначения

операций: x	= 1;	x	= 0, j ¹ i;			. Эффектив-
				q* = L, i =1, n
ii		ij		i

ность конкурсного механизма, оцениваемая по отношению

минимальной стоимости всех									операций Smin = n a к их
стоимости			в			ситуации		равновесия S = L n, будет равна:
K =	Smin	=	a		<< 1, если a << L.
			L
	S
	Пример 4.2. Пусть имеются две операции и два аген-
та. Значения Aij приведены в таблице 4.5.
										Таблица 4.5
					Параметры операций и агентов
						i \ j		1	2
						1		15	10
						2		25	15

Лимитные цены операций L1 = 120, L2 = 100. Определим равновесные оценки Sij и цены qj . Имеем:

S0 = S0		= L =120,			S0		= S	0 =100
21	11	1				12		22				.
	q0 =120,			q0	=100
		1		2
Вычислим:	S1	= min [L ; q			0	+ A − A			]= 100 ,
	12		2	1			12	11
	S1	= min [L ; q0				+ A		− A		]= 110 ,
	21		1	2			21	22
	S1	= q1	= min [L ; S1 ]					= 110 ,
	11	1			1		21
	S1	= q2	= min [L ; S1					]=100 .
	22	1				2	12
Получили равновесную ситуацию:
S*	= S* = 110,			S*		= S*		= 100
11		21		22			12				.
		q* = 110,		q*		= 100
		1		2

272

Эффективность конкурсного механизма в данном случае K = 17 , то есть весьма мала.

Ситуация в корне меняется при появлении еще одного агента. Самое главное, что при этом договорные цены в ситуации равновесия определяются уже не лимитными ценами {Lj}, а минимальными ценами {Aij}. Чтобы показать это, примем, что лимитные цены достаточно велики, и покажем, что они никак не влияют на равновесные. Пусть агенты перенумерованы таким образом, что агент с номером i получает операцию i, а агент с номером (m + 1) во-

обще не получает операции. В этом случае Ф0 = åAii

i

определяет оптимальное решение задачи минимизации

å Aij xij . i, j

Как уже отмечалось выше, агент (m + 1) сообщает в равновесии минимальные цены Sm+1,j = Am+1,j, а остальные агенты –

Sij = Aij + Di , i =1, m .

Для определения Di решим m задач следующего вида:

m	é		ù	® min	(5)
åêAm+1, j xm+1, j + å Aij xij ú
j =1	ë	i¹k	û

при ограничениях

åxij =1, i =1, m +1, i ¹ k,

j			(6)
åxij + xm+1, j =1, j =		.
	1, m
i¹k

Фактически мы заменили агента k на агента (m + 1) в задаче назначения операций. Обозначим Фk значение целевой функции в оптимальном решении этой задачи. Заметим, что Фk ³ Ф0 для всех k.

273

Пусть теперь	k > Фk – Ф0. В этом случае решение за-
дачи минимизации	å(Aij + i )xij не будет совпадать с
	i , j

решением задачи минимизации å Aij xij . Поэтому в ситуа-

i, j
ции равновесия должно иметь место	k ≤ Фk – Ф0, а так как
агенты заинтересованы в увеличении	k, то в равновесии

k = Фk – Ф0 и Sij = Aij + Фi – Ф0, Фm+1 = Ф0. Эффективность конкурсного механизма в случае n = m + 1 определя-

ется выражением:		Ф
K =					.
	m
	åФi − (m −1)Ф0
	i=1
Поскольку все Фi, i =1, n				определяются на основе

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

Пример 4.3. Возьмем задачу из примера 4.1 и добавим одного агента, который может взяться и за первую, и за вторую операции, которые для него одинаково выгодны,

то есть A31 = A32 = β. Пусть α < β < L.

В этом случае Ф0 = 2 α, Ф1 = Ф2 = α + β, 1 = 2 = β – α и эффективность конкурсного механизма

K = 22αβ = αβ ,

а цены обеих операций равны q1* = q2* = β.

Пример 4.4. Добавим теперь одного агента в задаче примера 4.2 со следующими данными: A31 = 40, A32 = 20.

274

	æ15 10		ö
Имеем: A =	ç	25 15	÷	, Ф0 = 30, Ф1 = 45, Ф2 = 35, D1 = 15,
	ç		÷
	ç	40 20	÷
	è		ø
D2 = 5.
Ситуация равновесия:
				S	= 30, S	=25,
				11	12
				S21	= 30, S22	=20,
				S31	= 40, S32	= 20.
Назначение операций x = x = 1, остальные xij = 0.
					11	22

Итак, первый агент получает первую операцию по цене q1* = 30, а второй – вторую по цене q2* = 20. Эффек-

тивность конкурсного механизма стала K = 3050 = 0,6, то есть повысилась по сравнению с предыдущим случаем

K = 17 примерно в 4,2 раза.

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

Эффективность конкурсного механизма максимальна, если в конкурсе участвуют равные соперники, то есть Aij = Aj

для всех i =1, n и, следовательно, Фk = Ф0, Dk = 0, то есть все

операции назначаются по минимальным ценам Aj, i =1, m .

Таким образом, с увеличением числа участников конкурса эффективность конкурсного механизма, как правило, увеличивается (во всяком случае не уменьшается).

Если n > m + 1, то анализ конкурсного механизма проводится аналогично предыдущему случаю. Однако объем вычислений быстро растет с ростом n. Так, при

n = m + 2 необходимо рассмотреть Cm2 задач, получаемых

275

заменой любых двух агентов i, j, получивших операции, на двух агентов, не получивших операций в равновесии.

Обозначим

Фij = min å åxks Aks s k ¹i , j

при условиях

ìï åxks =1, s =1, m

ïk ¹i , j

í m

ïïåxks =1, k ¹ i, j.

îs=1

В этом случае любое оптимальное по Парето решение системы неравенств

ìD		+ D		£ Ф -Ф , i, j =
	i		j			1, m,
ï				ij 0
í
ï	£ Di		£ Фi -Ф0 , i =1, m,
î0

определяет ситуацию равновесия. Эффективность кон-

	курсного	механизма можно		оценить, определив:
	Dmax = max åDi . Она равна K =			Ф0	.
			Ф0	+ Dmax
	i

Пример 4.5. К трем агентам из примера 4.4 добавим четвертого:

æ15 10 ö

ç ÷

A = ç25 15 ÷ .

çç40 20÷÷ çè20 40÷ø

Имеем: Ф1 = 35, Ф2 = 30, Ф12 = 40, Ф0 = 30, D1 £ 35 – 30 = 5, D2 £ 30 – 30 = 0.

В данном случае, ситуация равновесия:

S11 = 20, S21 = 25, S31 = 40, S41 = 20; S21 = 15, S22 = 15, S32 = 20, S42 = 40.

276

Существуют два варианта назначения операций. В первом варианте первую операцию получает первый агент, а во втором – четвертый агент. Вторую операцию в первом варианте получает второй агент, а во втором – первый агент.

Эффективность конкурсного механизма при увеличении участников конкурса до четырех увеличивается до

K = 0,84 > 0,6.

Таким образом, рассмотренные в настоящем разделе механизмы назначения позволяют эффективно решать задачи определения оптимального состава участников ОС (например, исполнителей проекта).

277

Глава 5

МЕХАНИЗМЫ КОНТРОЛЯ

Настоящая глава содержит описание механизмов контроля, среди которых можно выделить механизмы получения и обработки информации об управляемой системе: механизмы комплексного оценивания (раздел 5.1), механизмы согласия (раздел 5.2) и многоканальные механизмы (раздел 5.3); а также механизмы оперативного управления, позволяющие центру своевременно корректировать управляющие воздействия в зависимости от состояния управляемой системы и внешних возмущений: механизмы дополнительных соглашений (раздел 5.4).

5.1. Механизмы комплексного оценивания

Для выработки эффективных управляющих воздействий, начиная с этапа целеполагания и заканчивая этапом оперативного управления, управляющему органу необходимо обладать достаточной информацией о поведении управляемых субъектов, в частности – относительно результатов их деятельности. В сложных системах (многоэлементных, многоуровневых, деятельность которых описывается многими критериями) в силу ограниченности возможностей управляющего органа по переработке информации или в силу отсутствия детальной информации целесообразно использование механиз-

мов комплексного оценивания, которые позволяют осу-

278

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

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

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

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

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

279