ТОП 10:

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



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

Алгоритм.

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

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

Полагаем

xk+1=xk+lsk sk , (2. 7)

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

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

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

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

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

j i ( x) – j i ( xk – e lk sk 2,(0,1), (2. 8)

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

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

Пример.

Для задачи

j1(x)= x12 + x22 ® min,

j2(x)= x12 + (x24)2 ® min,

j3(x)=(x14)2 + x22® min,

j4(x)=(x14)2 + (x24)2 ® min.

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

Решение.

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

Задача ZS(y).

 
 
(2.9)
 

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

max s ,

4s1 + 4s2 + s £0,

4s14s2 + s £0,

4s1 + 4s2 + s £0,

4s14s2 + s £0,

s1£1,

s2£1.

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

max s ,

4s'1 + 4s'2+ s £8,

4s'14s'2+ s £0,

4s'1+ 4s'2+ s £0,

4s'14s'2+ s £8,

s'1 £ 2, s'(2) £ 2,

s'1³0, s'2³0, s ³0.

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

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

Для задачи

j1(x)=(x1– a1)2 + (x2– b1)2 ® min,

j2(x)=(x1– a2)2 + (x2– b2)2 ® min,

j3(x)=(x1– a3)2 + (x2– b3)2 ® min,

j4(x)=(x1– a4)2 + (x2– b4)2 ® min.

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

номер варианта Значения параметров
aa1 bb1 aa2 bb2 aa3 bb3 aa4 bb4 yy1 yy2 zz1 zz2

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

 

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

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

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

 

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

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

j1(x)= x12 + x22 ® min,

j2(x)= x12 + (x24)2 ® min,

j3(x)=(x14)2 + x22® min,

j4(x)=(x14)2 + (x24)2® 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) искусственные переменные zj, j=1,2,3и построим задачу:

F= z1 + z2 + z3 ® min
  4 u1 + 4 u2 4 u3 4u4 + z1 =
  4 u1 4 u2 + 4 u3 4u4 + z2 =
u1 + u2 + u3 + u4 + z3 =
u1³0 u2³0 u3³0 u4³0 z1³0 z2³0 z3³0

 

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

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

Для задачи

j1(x)=(x1– a1)2 + (x2– b1)2 ® min,

j2(x)=(x1– a2)2 + (x2– b2)2 ® min,

j3(x)=(x1– a3)2 + (x2 – b3)2 ® min,

j4(x)=(x1– a4)2 + (x2– b4)2 ® min.

 

проверить на оптимальность точки: y=(y1,y2)T, z=(z1,z2)T.

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

 


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

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

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

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

GI; Xi, iÎI; ji(x), , iÎIñ,

где I – множество игроков, I={1,2,3,…,N}, для i–го игрока Xi, – множество стратегий i–го игрока, он осуществляет выбор xiÎXi, ji(x) – критерий (выигрыш), по которому i–ый игрок оценивает свое состояние в игре. В силу того, что – прямому произведению множеств XK, KÎI, критерий можно записать так ji(x)=ji(x1, x2, x3,…, xi, …, xN). Игрок с номером i осуществляет выбор только i–ой переменной. Мы будем считать, что i–ый игрок максимизирут свой критерий, и записывать . Ясно, что величина выигрыша зависит от стратегий, выбранных другими игроками.

Равновесие по Нешу в игре. Точку x*=(x*1, x*2, x*3,…, x*i, …, x*NX будем называть состоянием равновесия по Нешу, если для каждого игрока iÎI выполняется соотношение

,

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

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

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

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

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

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

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

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

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

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

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

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

 







Последнее изменение этой страницы: 2016-06-29; Нарушение авторского права страницы

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 34.200.226.179 (0.019 с.)