88. Матричные игры. Цена. Седловая точка. Нахождение цены и Седловой точки.

Опр. Игрой в нормальной форме наз. совокупность Г={I, {x₀}_iI, {u_i} _iI} где iI – игроки, I – мн-во игроков.

X_i = {x_ij} _jI – мн-во стратегий i-го игрока

– мно-во исходов игры.

u_i : X→R – ф-я выигрыша i-го игрока.

Схема игры в нормальной форме: игрок i выбирает стратегию x_iX_i. После выбора каждым игроком своей стратегии определяется исход игры x = (x_i) _iI и выигрыш каждого игрока u_i(x).

Пусть A, B – игроки

X_A = {x₁,…,x_n} – стратегии A.

Y_B = {y₁,…,y_m} – стратегии B.

u_A:X_AxY_B→R и U_B: X_AxY_B→R – ф-ции выигрыша

u_A(x_i, y_j)=a_ij u_B(x_i, y_j)=b_ij

Игра наз игрой с нулевой суммой, если u_A(x_i, y_j)= - u_B(x_i, y_j).

α <= β

Если α = β, то α наз ценой игры и игра наз разрешимой в чистых стратегиях. Пара (x_i, y_j) такая, что u_A(x_i, y_j)= α наз седловой точкой. Если α < β, то строим расширение игры

P=(p₁,…,p_n):

Q=(q₁,…,q_m):

- ф-я выигрыша

По т-ме Неймана.

Не ограничивая общности можно считать что a_ij>0, тогда нахождениесводится к задаче оптимизации:

89. Теорема Куна-Таккера.

Выпуклая задача оптимизации.

- выпуклые, т.е. , , , .

- выпуклое множество в .

Задачей выпуклого программирования называют задачу оптимизации

- выпуклое, т.к. и - выпуклые.

Теорема (необходимое условие оптимальности).

- допустимое является оптимальным в задаче выпуклого программирования, то :

1) – условие неотрицательности

2) , – условие дополняющей нежесткости

3), - условие минимальности

Теорема (достаточное условие оптимальности)

- является оптимальным в задаче выпуклого программирования, если :

1) (i)

2) , (ii)

3), для (iii)

Доказательство. По условию .

Т.к. для , то получаем, что т.к. , то для

Определение. Говорят, что задача выпуклого программирования удовлетворяет условию регулярности Слейтера, если .

Теорема (Куна-Таккера)

Для того, чтобы допустимое решение было оптимальным в задаче выпуклого программирования, удовлетворяло условию регулярности Слейтера, необходимо и достаточно, чтобы в пространстве , удовлетворяющее условиям (i), (ii), (iii).

Доказательство.

По предыдущей теореме.

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

Если , , то , т.к. .

Пусть , . По условию Слейтера , при .

По условиям (ii) и (iii)

90. Необходимое условие экстремума в классической вариационной задаче (уравнение Эйлера-Лагранжа)



x: T→ - кусочно-дифференцируема, т.е. непрерывна на Т, дифференцируема на Т, за исключением конечного числа точек .

PD(T,) – множество кусочно-дифференцируемых ф-ций

J : PD(T,) → , J : x, Ω = {x PD(T,): }

- Простейшая вариационная задача

Опр - сильный (слабый) лок. min, если ().

Lm (Дюбуа-Раймона) p, q: T→- кусочно-непрерывные

(T,)  Th f : →  - непрерывно дифференцируема по всем переменным доставляет лок. min ПВЗ : .

Д-во. - доставляет лок. min (T,)

(по Lm Дюбуа-Раймона) : - Интегральное ур. Эйлера-Лагранжа.◄

Для инт. ур-е Эйлера-Лагранжа равносильно дифференциальному ур-ю Эйлера-Лагранжа: .