Метод множителей Лагранжа для функций 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 возможно геометрическое решение.