3.4. Теорема Куна–Таккера для задачи выпуклого векторного программирования

Рассмотрим анализ задачи выпуклого векторного программирования на необходимые и достаточные условия существования оптимальной точки по Слейтеру. Для этого приведем аналог известной теоремы Куна – Таккера.

Теорема Куна–Таккера 2.17.Пусть множествоXудовлетворяет условию регулярностиR2. Для того, чтобы точкаyXбыла точкой оптимума по Слейтеру, необходимо и достаточно существование такихu_i, i(MI(y)), для которых справедлива система

	(2.12)
	(2.13)
ui0, i (M  I(y)),	(2.14)

Приведем пример, иллюстрирующий применение теоремы Куна – Таккера к анализу задачи (2.1), (2.2).

Пример. Для задачи

₁(x)= x₁² + x₂²  min,

₂(x)= x₁² + (x₂ –4)²  min,

₃(x)= (x₁ –4)² + x₂²  min,

₄(x)= (x₁ –4)² + (x₂ –4)² min.

проверить на оптимальность по Слейтеру точку y = (2,2)^T.

Решение.

Составим для этой задачи систему вида (2.15). Для этого, подставив в нее значения градиентов ' _i(y), получим

(2.15)

Нетрудно видеть, что составленная система разрешима и имеет следующие решения: (0.50, 0.00, 0.00, 0.50 )^T,

(0.00, 0.50, 0.50, 0.00 )^T,

(0.25, 0.25, 0.25, 0.25) ^T.

В общем случае проверить разрешимость подобных задач можно симплекс-методом. Продемонстрируем это. Введем в систему (2.15) искусственные переменные z_j, j=1,2,3 и построим задачу:

F=					z1	+ z2	+ z3		min
	4 u1	+ 4 u2	– 4 u3	– 4u4	+ z1			=	0
	4 u1	– 4 u2	+ 4 u3	– 4u4		+ z2		=	0
	u1	+   u2	+    u3	+ u4			+ z3	=	1
	u1 0	u2 0	u3 0	u4 0	z1 0	z2 0	z3 0

Если в этой задаче F=0, т.е.z₁=0 , z₂=0 , z₃=0, то система (2.15) разрешима, еслиF>0, то система (2.15) не имеет решения.

Самостоятельная работа № 4.

Для задачи

₁(x)= (x₁ – a₁)² + (x₂ – b₁)²  min,

₂(x)= (x₁ – a₂)² + (x₂ – b₂)²  min,

₃(x)= (x₁ – a₃)² + (x₂ – b₃)²  min,

₄(x)= (x₁ – a₄)² + (x₂ – b₄)²  min.

проверить на оптимальность точки: y=(y₁,y₂)^T, z=(z₁,z₂)^T.

Варианты заданий взять из лабораторной работы 3.

4. Некоторые задачи теория игр

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

Формально игру можно определить в следующем виде:

Нормальная форма игры:

G=I;   X_i, iI;   _i(x),  ,iI,

где I – множество игроков,I={1,2,3,…,N}, дляi–го игрокаX_i, – множество стратегийi–го игрока, он осуществляет выборx_iX_i,_i(x) – критерий (выигрыш), по которомуi–ый игрок оценивает свое состояние в игре. В силу того, что – прямому произведению множествX_K, KI, критерий можно записать так_i(x)=_i(x₁, x₂, x₃,…, x_i, …, x_N). Игрок с номеромiосуществляет выбор толькоi–ой переменной. Мы будем считать, что i–ый игрок максимизирут свой критерий, и записывать . Ясно, что величина выигрыша зависит от стратегий, выбранных другими игроками.

Равновесие по Нешу в игре.Точкуx^*=(x^*₁, x^*₂, x^*₃,…, x^*_i, …, x^*_N)Xбудем называть состоянием равновесия по Нешу, если для каждого игрокаiI выполняется соотношение

,

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

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

В зависимости от количества игроков N различают игры двух и более чем двух игроков. Первые из них наиболее изучены. Игры трёх и более игроков менее исследованы из-за возникающих принципиальных трудностей и технических возможностей получения решения. Чем больше игроков, тем больше проблем.

По количеству стратегий игры делятся на конечные и бесконечные.Если в игре все игроки имеют конечное число возможных стратегий, то она называетсяконечной.Если при этомN=2, тобиматричной, так как в этом случае функции выигрыша_i(x)=_i(x₁, x₂) можно представить матрицами. Если же хотя бы один из игроков имеет бесконечное количество возможных стратегий игра называется бесконечной.

По характеру взаимодействия субъектов игры делятся на:

1. бескоалиционные игры – в них игроки не имеют права вступать какие-либо объединения для выбора согласованных стратегий, т.е. не имеют права образовывать коалиции;

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

По характеру выигрышей игры делятся на: антагонистическиеилиигры с нулевой суммой(общий капитал всех игроков не меняется, а перераспределяется между игроками; сумма выигрышей всех игроков равна нулю) и игры с ненулевой суммой.

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

Непрерывнойсчитается игра, в которой функция выигрышей каждого игрока является непрерывной в зависимости от стратегий.

Если функция выигрышей является выпуклой, то такая игра называется выпуклой. Этот класс игр достаточно хорошо изучен.

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