Алгоритм безусловной векторной оптимизаци.

Предлагаемый ниже алгоритм является развитием градиентных методов и метода возможных направлений Зойтендейка. Так задача ZS (y)для однокритериальной задачи безусловной оптимизации в качестве направления s вырабатывает в однокритериальной задаче возможное подходящее направление.

Алгоритм.

0 –ой шаг. В качестве х ₀задаем произвольную точку из Rⁿ.

k – ый шаг (k = 0, 1, 2, …).

Полагаем

xk+ 1= xk+lsk sk ,

(2. 7)

где значения s_k , s_k получены из решения задачи ZS (x_k).

l_k выбирается следующим образом:

1. Выбираем некоторое l (одно на всех итерациях) и полагаем l_k = l.

2. Вычисляем j _i (x)= j _i (x_k + l s_k s_k), iÎ M.

3. Если для всех

j i (x) – j i (xk)£ – e lk sk ^2, eÎ (0,1),

(2. 8)

то l_k является искомым, в противном случае полагаем l_k = a l_k , где a Î (0,1)и переходим к шагу 2.

Последовательности { x_k },{ s_k },{ s_k }обрываем, если для некоторого k в точке x_k оказалось s_k =0,в этом случае при выполнении достаточных условий точка x_k являются оптимумом по Слейтеру.

Пример.

Для задачи

j ₁(x)= x ₁² + x ₂² ® min,

j ₂(x)= x ₁² + (x ₂ – 4)² ® min,

j ₃(x)=(x ₁ – 4)² + x ₂² ® min,

j ₄(x)=(x ₁ – 4)² + (x ₂ – 4)² ® min.

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

Решение.

В этой задаче множество I = Æ, поэтому задача ZS (y)примет вид:

Задача ZS (y).

	(2.9)

Подставляя в (2.9) значения градиентов j _i' (y)в точке у = (2, 2),получим

max s,

4 s ₁ + 4 s ₂ + s £0,

4 s ₁ – 4 s ₂ + s £0,

– 4 s ₁ + 4 s ₂ + s £0,

– 4 s ₁ – 4 s ₂ + s £0,

– 1£ s ₁£1,

– 1£ s ₂£1.

Проведя замену переменных s_j = s'_j – 1, j= 1,2, получим

max s,

4 s' ₁ + 4 s' ₂ + s £8,

4 s' ₁ – 4 s' ₂ + s £0,

– 4 s' ₁ + 4 s' ₂ + s £0,

– 4 s' ₁ – 4 s' ₂ + s £ – 8,

s' ₁ £ 2, s' (2) £ 2,

s' ₁³0, s' ₂³0, s ³0.

Решая эту задачу симплекс – методом, получаем, что максимальное значение s =0. Это означает, что точка y =(2,2) оптимальна по Слейтеру

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

Для задачи

j ₁(x)=(x ₁ – a ₁)² + (x ₂ – b ₁)² ® min,

j ₂(x)=(x ₁ – a ₂)² + (x ₂ – b ₂)² ® min,

j ₃(x)=(x ₁ – a ₃)² + (x ₂ – b ₃)² ® min,

j ₄(x)=(x ₁ – a ₄)² + (x ₂ – b ₄)² ® min.

проверить на оптимальность точки: y =(y ₁, y ₂) ^T, z =(z ₁, z ₂) ^T. Если точка не является оптимальной, то для нее указать подходящее направление. Варианты заданий взять в следующей таблице:

номер варианта

Значения параметров

aa 1

bb 1

aa 2

bb 2

aa 3

bb 3

aa 4

bb 4

y y 1

y y 2

z z 1

z z 2

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

 

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

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

	(2.12)
	(2.13)
ui ³0, i Î(M È I (y)),	(2.14)

 

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

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

j ₁(x)= x ₁² + x ₂² ® min,

j ₂(x)= x ₁² + (x ₂ – 4)² ® min,

j ₃(x)=(x ₁ – 4)² + x ₂² ® min,

j ₄(x)=(x ₁ – 4)² + (x ₂ – 4)² ® min.

 

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

Решение.

Составим для этой задачи систему вида (2.15). Для этого, подставив в нее значения градиентов j' _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 =					z 1	+ z 2	+ z 3	®	min
	4 u 1	+ 4 u 2	– 4 u 3	– 4 u 4	+ z 1			=
	4 u 1	– 4 u 2	+ 4 u 3	– 4 u 4		+ z 2		=
	u 1	+ u 2	+ u 3	+ u 4			+ z 3	=
	u 1³0	u 2³0	u 3³0	u 4³0	z 1³0	z 2³0	z 3³0

 

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

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

Для задачи

j ₁(x)=(x ₁ – a ₁)² + (x ₂ – b ₁)² ® min,

j ₂(x)=(x ₁ – a ₂)² + (x ₂ – b ₂)² ® min,

j ₃(x)=(x ₁ – a ₃)² + (x ₂ – b ₃)² ® min,

j ₄(x)=(x ₁ – a ₄)² + (x ₂ – b ₄)² ® min.

 

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

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

 

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

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

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

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

G =á I; X_i, i Î I; j_i (x), , i Î I ñ,

где I – множество игроков, I ={1,2,3,…, N }, для i –го игрока X_i, – множество стратегий i –го игрока, он осуществляет выбор x_i Î X_i, j_i (x) – критерий (выигрыш), по которому i –ый игрок оценивает свое состояние в игре. В силу того, что – прямому произведению множеств X_K, K Î I, критерий можно записать так j_i (x)= j_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, то биматричной, так как в этом случае функции выигрыша j_i (x)= j_i (x ₁, x ₂) можно представить матрицами. Если же хотя бы один из игроков имеет бесконечное количество возможных стратегий игра называется бесконечной.

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

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

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

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

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

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

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

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