ТОП 10:

Метод множителей Лагранжа для функций n переменных



Допустим, мы имеем функцию n переменных z=f(x1,x2,…,xn) и m уравнений связи (n>m):

φ1(x1,x2,…,xn)=0;φ2(x1,x2,…,xn)=0,…,φm(x1,x2,…,xn)=0.

Обозначив множители Лагранжа как λ1,λ2,…,λm, составим функцию Лагранжа:

F(x1,x2,…,xn,λ1,λ2,…,λm)=f+λ1φ1+λ2φ2+…+λmφm

Необходимые условия наличия условного экстремума задаются системой уравнений, из которой находятся координаты стационарных точек и значения множителей Лагранжа:

⎧⎩⎨⎪⎪∂F∂xi=0;(i=1,n¯¯¯¯¯¯¯)φj=0;(j=1,m¯¯¯¯¯¯¯¯)

Выяснить, условный минимум или условный максимум имеет функция в найденной точке, можно, как и ранее, посредством знака d2F. Если в найденной точке d2F>0, то функция имеет условный минимум, если же d2F<0, – то условный максимум. Можно пойти иным путем, рассмотрев следующую матрицу:

Определитель матрицы ∣∣∣∣∣∣∣∣∣∣∣∣∂2F∂x21∂2F∂x2∂x1∂2F∂x3∂x1…∂2F∂xn∂x1∂2F∂x1∂x2∂2F∂x22∂2F∂x3∂x2…∂2F∂xn∂x2∂2F∂x1∂x3∂2F∂x2∂x3∂2F∂x23…∂2F∂xn∂x3……………∂2F∂x1∂xn∂2F∂x2∂xn∂2F∂x3∂xn…∂2F∂x2n∣∣∣∣∣∣∣∣∣∣∣∣, выделенной в матрице L красным цветом, есть гессиан функции Лагранжа. Используем следующее правило:

· Если знаки угловых миноров H2m+1,H2m+2,…,Hm+n матрицы L совпадают с знаком (−1)m, то исследуемая стационарная точка является точкой условного минимума функции z=f(x1,x2,x3,…,xn).

· Если знаки угловых миноров H2m+1,H2m+2,…,Hm+n чередуются, причём знак минора H2m+1 совпадает с знаком числа (−1)m+1, то исследуемая стационарная точка является точкой условного максимума функции z=f(x1,x2,x3,…,xn).

 

2. Чистые и смешанные стратегии.

3. Решение простейших игр.(учебник)

4. Сведение игры к ЗЛП.

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

Пусть игра задана платежной мат­рицей .ИгрокАобладает стра­тегиями ,игрокВ –стратегиями . Необ­ходимо определить оптимальные стратегии и , где – вероятности применения соот­ветствующих чистых стратегий ,

, .

Оптимальная стратегия удовлетворяет следующему требо­ванию. Она обеспечивает игрокуАсредний выигрыш, не мень­ший, чем цена игрыv, при любой стратегии игрокаВи выиг­рыш, равный цене игрыv, при оптимальной стратегии игрокаВ. Без ограничения общности полагаемv > 0; этого можно добиться, сделав все элементы . Если игрокАприменяет смешанную стратегию против любой чистой стратегии игрокаВ,то он получаетсредний выигрыш,илиматематическое ожидание выигрыша (т.е. элементыj-гoстолбца платежной матрицы почленно умножаются на соответствующие вероятности стратегий и резуль­таты складываются).

Для оптимальной стратегии все средние выигрыши не меньше цены игры v, поэтому получаем систему неравенств:

Каждое из неравенств можно разделить на число . Введем новые переменные: . Тогда система принимает вид

(1*)

Цель игрока А –максимизировать свой гарантированный вы­игрыш, т.е. цену игрыv.

Разделив на равенство , получаем, что переменные удовлетворяют условию: . Максимизация цены игрыvэквивалентна мини­мизации величины ,поэтому задача может быть сформулиро­вана следующим образом:определить значения переменных ,maк, чтобы они удовлетворяли линейным ограничени­ям(*) ипри этом линейная функция (2*)обращалась в минимум.

Это задача линейного программирования. Решая задачу (1*)–(2*), получаем оптимальное решение и оптимальную стратегию.

Для определения оптимальной стратегии следует учесть, что игрокВстремится минимизировать гаранти­рованный выигрыш, т.е. найтиmax . Переменные удовлетворяют неравенствам

(3*)

которые следуют из того, что средний проигрыш игрока Вне пре­восходит цены игры, какую бы чистую стратегию не применял игрокА.

Если обозначить (4*) , то получим систему неравенств:

(5*)

Переменные удовлетворяют условию .

Игра свелась к следующей задаче.

Определить значения переменных , которые удовлетворяют системе неравенств(5*)и максимизируют линей­ную функцию

(6*)

Решение задачи линейного программирования (5*), (6*) определяет оптимальную стратегию . При этом цена игры . (7*)

Составив расширенные матрицы для задач (1*), (2*) и (5*), (6*), убеждаемся, что одна матрица получилась из другой транспонированием:

Таким образом, задачи линейного программирования (1*), (2*) и (5*), (6*), являются взаимно-двойственными. Очевид­но, при определении оптимальных стратегий в конкретных зада­чах следует выбрать ту из взаимно-двойственных задач, решение которой менее трудоемко, а решение другой задачи найти с по­мощью теорем двойственности.

При решении произвольной конечной игры размера ре­комендуется придерживаться следующей схемы:

1.Исключить из платежной матрицы заведомо невыгодные стратегии по сравнению с другими стратегиями. Такими страте­гиями для игрокаА(игрокаВ)являются те, которым соответству­ют строки (столбцы) с элементами, заведомо меньшими (боль­шими) по сравнению с элементами других строк (столбцов).

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

3.Если седловая точка отсутствует, то решение следует искать в смешанных стратегиях. Для игр размератхпрекомендуется симплексный метод, для игр размера 2х2,2хn,mх2 возможно геометрическое решение.

 

 







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

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