Вопросы — Теория игр

1. Общая задача линейного программирования. Прямая и двойственная задачи. Свойства допустимых значений
   Задача линейного программирования заключается в поиске минимума или максимума линейной функции при линейных ограничениях.

   Обозначения:

   1. $x = (\xi_1, \dots, \xi_m) \in \mathbb{R}^m$;
   2. $y = (\eta_1, \dots, \eta_n) \in \mathbb{R}^n$;
   3. $c = (\gamma_1, \dots, \gamma_m) \in \mathbb{R}^m$;
   4. $b = (\beta_1, \dots, \beta_n) \in \mathbb{R}^n$;
   5. $A = \set{\alpha_{ij}}_{m \times n}$.

   Прямая задача ЛП: \[ \begin{gathered} \max \dp{c}{x}, \\ xA \leqslant b, \\ x \geqslant 0. \end{gathered} \]

   Двойственная задача ЛП: \[ \begin{gathered} \min \dp{b}{y}, \\ Ay \geqslant c, \\ y \geqslant 0. \end{gathered} \]

   Вектор $x$, удовлетворяющий всем ограничениям ЗЛП, называют допустимым решением. Множество всех допустимых значений ЗЛП — $M \subset \mathbb{R}^m$.

   Допустимое решение $x^*$, на котором целевая функция достигает максимального (минимального) значения, называют оптимальным решением.

   Двойственная задача к двойственной — прямая.

   Пусть $x, y$ — допустимые решения ПЗ и ДвЗ соответственно. Тогда \[ cx \leqslant by. \]

   $x$ — допустимое решение ПЗ. поэтому \[ xA \leqslant b. \] Домножим на $y$ справа. Так как $y$ — допустимое решение ДвЗ, то $y \geqslant 0$, и знак неравенства не изменится: \[ xAy \leqslant by. \] Так как $Ay \geqslant c$, окончательно получаем \[ xc \leqslant xAy \leqslant by. \]
2. Следствие теоремы о ранге матрицы
   \[ A = \set{\alpha_{ij}}_{n \times m} = \overbrace{(a^1, \dots, a^m)}^{\text{столбцы}} = \overbrace{ \paren{ \begin{array}{c} a_1 \\ \vdots \\ a_n \end{array} } }^{\text{строки}}. \]

   (о ранге матрицы). Количество линейно независимых строк равно количеству линейно независимых столбцов.

   Рассмотрим систему линейно независимых строк $a_1, \dots, a_r \in \mathbb{R}^n$. Тогда \[ \forall \alpha_1, \dots, \alpha_r \quad \exists y = (\eta_1, \dots, \eta_n): \quad \dp{a_i}{y} = \alpha_i, \quad i = \overline{1,r}. \]

   Рассмотрим матрицу \[ A = \paren{ \begin{array}{c} a_1 \\ \vdots \\ a_r \end{array} }, \quad \dim A = r \times n, \quad \rank A = r. \] По теореме о ранге матрицы у этой матрицы $r$ линейно независимых столбцов. Пусть для определённости это первые $r$ столбцов.

   Рассмотрим вектор $m = (\alpha_1, \dots, \alpha_r)$. Его можно разложить по столбцовому базису матрицы $A$: \[ m = \sum_{j=1}^r \eta_j a^j = \sum_{j=1}^r \eta_j a^j + \sum_{j=r+1}^n 0 \cdot a^j. \] Таким образом, можно построить $y = (\eta_1, \dots, \eta_r, 0, \dots, 0) \in \mathbb{R}^n$.

   Множество $M$ называется выпуклым, если \[ \forall x,y \in M \implies \lambda x + (1 - \lambda) y \in M \quad \forall \lambda \in [0;1]. \]

   Точка $x$ выпуклого множества $M$ называется крайней, если она не может быть серединой отрезка, концы которого лежат в этом множестве, то есть \[ \nexists x_1, x_2 \in M: \quad x = \frac{x_1 + x_2}{2}. \]

   Пусть в $\mathbb{R}^n$ задано конечное число точек $M_1, \dots, M_m$. Тогда наименьшее выпуклое множество, содержащие эти точки, называется выпуклым многогранником.
3. Базисные решения систем линейных уравнений. Теорема о существовании неотрицательного базисного решения

   Рассмотрим равенство \[ \sum_{i=1}^m \xi_i a_i = b, \] где $a_i$ — строки матрицы $A$.

   Пусть существует решение системы $x = (\xi_1, \dots, \xi_m)$. Рассмотрим набор индексов \[ S \subset N = \set{1, \dots, m}. \]

   Говорят, что решение $x$ зависит от $S$, если \[ \forall i \in N \quad i \not\in S \implies \xi_i = 0. \]

   В $S$ могут входить индексы нулевых координат — это не принципиально.

   Решение $x$ называется базисным решением системы \[ \sum_{i=1}^m \xi_i a_i = b, \] если оно зависит от такого $S$: набор строк $\set{a_i: i \in S}$ — линейно независимый.

   Иными словами, решение базисное, если оно разлагает вектор $b$ по линейно независимым строкам.

   Решение $x$ называют неотрицательным, если все его компоненты неотрицательны: $\forall i = \overline{1, m} \quad \xi_i \geqslant 0$.

   Если система \[ \sum_{i=1}^m \xi_i a_i = b \] имеет решение, то она имеет базисное решение.

   Если система \[ \sum_{i=1}^m \xi_i a_i = b \] имеет неотрицательное решение, то оно имеет базисное неотрицательное решение.

   Индукция по количеству строк матрицы $A$.

   • Случай $m = 1$. Система имеет неотрицательное решение: \[ \xi_1 a_1 = b, \quad \xi_1 \geqslant 0, \] тогда $\xi_1$ — базисное решение.
   • Пусть утверждение верно для $m - 1$, то есть любая система вида \[ \sum_{i=1}^{m-1} \xi_i a_i = b \] с неотрицательным решением имеет неотрицательное базисное решение.
   • Рассмотрим систему \[ \sum_{i=1}^m \xi_i a_i = b \] с неотрицательным решением $x$. Возможны следующие варианты:
     1. Если хотя бы одна из компонент вектора $x$ равна нулю, то задача сводится к случаю $m - 1$, поэтому дальше считаем $\xi_i \gt 0$.
     2. Если $a_i$ — линейно независимые, то данное решение $x$ уже базисное.

     3. Пусть $a_i$ линейно зависимы, тогда \[ \exists \vec{\lambda} \neq \vec{0}: \quad \sum_{i=1}^m \lambda_i a_i = 0. \] Для определённости будем считать, что $\lambda_1 \gt 0$.

        Если что, можем перенумеровать и/или домножить на $(-1)$.

        Обозначим $\Theta = \max\limits_i \dfrac{\lambda_i}{\xi_i} \gt 0$. Опять для определённости $\Theta := \dfrac{\lambda_1}{\xi_1}$.

        Проведём следующие преобразования: \[ \begin{aligned} \sum_{i=1}^m \xi_i a_i &= \sum_{i=1}^m \xi_i a_i - \sum_{i=1}^m \lambda_i a_i \\ &= \frac{1}{\Theta} \sum_{i=1}^m \Theta \xi_i a_i - \sum_{i=1}^m \frac{\lambda_i}{\xi_i} \xi_i a_i \\ &= \frac{1}{\Theta} \sum_{i=1}^m \paren{\Theta - \frac{\lambda_i}{\xi_i}} \xi_i a_i \\ &= \frac{1}{\Theta} \sum_{i=2}^m \paren{\Theta - \frac{\lambda_i}{\xi_i}} \xi_i a_i \\ &= b. \end{aligned} \] Таким образом, существует неотрицательное решение \[ \xi_i' := \frac{1}{\Theta} \paren{\Theta - \frac{\lambda_i}{\xi_i}} \xi_i, \quad i = \overline{2,m} \] для системы \[ \sum_{i=2}^m \xi_i' a_i = b, \] то есть существует неотрицательное базисное решение $(\bar\xi_2', \dots, \bar\xi_m')$, откуда следует, что $(0, \bar\xi_2', \dots, \bar\xi_m')$ также является базисным неотрицательным решением.

4. Критерий оптимальности в задаче линейного программирования
   Рассмотрим \[ \overset{\text{ПЗ}}{ \begin{gathered} \max \dp{c}{x} \\ xA \leqslant b \\ x \geqslant 0 \end{gathered} } \quad \text{и} \quad \overset{\text{ДЗ}}{ \begin{gathered} \min \dp{b}{y} \\ Ay \geqslant c \\ y \geqslant 0 \end{gathered} } \]

   (критерий оптимальности). Если существуют допустимые решения $\bar x$ и $\bar y$ для ПЗ и ДЗ соответственно такие, что \[ c \bar x = b \bar y, \] то $\bar x$ и $\bar y$ — оптимальные для ПЗ и ДЗ соответственно.

   Воспользуемся свойством допустимых решений: для любых допустимых решений $x$ и $y$ ПЗ и ДЗ соответственно справедливо неравенство \[ cx \leqslant by. \]

   Тогда \[ cx \leqslant b \bar y = c \bar x, \] то есть для любого допустимого решения $x$ ПЗ выполнено \[ cx \leqslant c \bar x, \] поэтому $\bar x$ — оптимальное решение.

   Аналогично доказывается оптимальность решения $\bar y$.

5. Теорема двойственности
   Рассмотрим \[ \overset{\text{ПЗ}}{ \begin{gathered} \max \dp{c}{x} \\ xA \leqslant b \\ x \geqslant 0 \end{gathered} } \quad \text{и} \quad \overset{\text{ДЗ}}{ \begin{gathered} \min \dp{b}{y} \\ Ay \geqslant c \\ y \geqslant 0 \end{gathered} } \]

   (об альтернативах). Либо $xA = b$ имеет неотрицательное решение, либо существует решение неравенств \[ \left\{ \begin{gathered} Ay \geqslant 0 \\ by \lt 0. \end{gathered} \right. \]

   Одновременное выполнение исключено: \[ x \overbrace{Ay}^{\geqslant 0} = \overbrace{by}^{\lt 0}. \]

   (о решении систем линейных неравенств). Либо $xA \leqslant 0$ имеет неотрицательное решение, либо система \[ \left\{ \begin{gathered} Ay \geqslant 0 \\ by \lt 0 \end{gathered} \right. \] имеет неотрицательное решение.

   (двойственности).

   1. Если существуют решения ПЗ и ДЗ, то существует оптимальные решения ПЗ и ДЗ, причём их значения совпадают.
   2. Если одна из задач не имеет допустимых решений, то двойственная к ней не имеет оптимального.

   расписать
6. Каноническая теорема равновесия
   Найти численный метод решения ЗЛП.

   Каноническая форма записи: \[ \overset{\text{Стандартная форма ПЗ}}{ \begin{gathered} \max \dp{c}{x} \\ xA \leqslant b \\ x \geqslant 0 \end{gathered} } \iff \overset{\text{Каноническая форма ПЗ}}{ \begin{gathered} \max \dp{c'}{x'} \\ x'A' = b \\ x' \geqslant 0 \end{gathered} } \]

   • Из стандартной формы в каноническую: \[ xA \leqslant b \implies xA + z = b, \quad z \in \mathbb{R}^n, \; z \gt 0. \] Замена: \[ \begin{gathered} x' := (x, z) \\ A' := \paren{ \begin{matrix} A \\ E \end{matrix} } \quad C' := (C, 0) \end{gathered} \] Приходим к канонической форме: \[ \begin{gathered} \max \dp{c'}{x'} \\ x' A' = b \\ x' \geqslant 0. \end{gathered} \]
   • Из канонической формы в стандартную: \[ xA = b \iff \left\{ \begin{gathered} xA \geqslant b \\ xA \leqslant b. \end{gathered} \right. \] Домножим первое неравенство на $(-1)$: \[ \left\{ \begin{gathered} x(-A) \leqslant -b \\ xA \leqslant b. \end{gathered} \right. \] Замена: \[ A' := (A, -A), \quad b' := (b, -b). \] Приходим к стандартной форме: \[ \begin{gathered} \max \dp{c}{x} \\ xA' \leqslant b' \\ x \geqslant 0. \end{gathered} \]

   \[ \overset{\text{Стандартная форма ДЗ}}{ \begin{gathered} \min \dp{b}{y} \\ Ay \geqslant c \\ y \geqslant 0 \end{gathered} } \iff \overset{\text{Каноническая форма ДЗ}}{ \begin{gathered} \min \dp{b}{y} \\ Ay \geqslant c \\ \forall y \end{gathered} } \]

   • Из стандартной формы в каноническую.

     Рассмотрим ПЗ: \[ \begin{gathered} \max \dp{c}{x} \\ xA' \leqslant b' \\ x \geqslant 0, \end{gathered} \quad \text{где} \quad \begin{aligned} A' &:= (A, -A), \\ b' &:= (b, -b). \end{aligned} \] Составим для неё ДЗ: \[ \begin{gathered} \min \dp{b'}{y'} \\ A'y' \geqslant c \\ y' \geqslant 0. \end{gathered} \]

     Пусть \[ y' = ( \underbrace{\eta_1, \dots, \eta_n}_{\eta}, \underbrace{\eta_1', \dots, \eta_n'}_{\eta'} ), \] тогда ДЗ примет вид \[ \begin{gathered} \min (\dp{b}{\eta} - \dp{b}{\eta'}) \\ A \eta - A \eta' \geqslant c \\ \eta \geqslant 0, \; \eta' \geqslant 0, \end{gathered} \implies \begin{gathered} \min \dp{b}{(\eta - \eta')} \\ A (\eta - \eta') \geqslant c \\ \eta \geqslant 0, \; \eta' \geqslant 0. \end{gathered} \] Проведём замену переменных: \[ y := \eta - \eta'. \] Заметим, что $y$ может принимать любые значения.

     Итак, приходим к канонической форме: \[ \begin{gathered} \min \dp{b}{y} \\ A y \geqslant c \\ \forall y \end{gathered} \]

   • Из канонической формы в стандартную
     Расписать

   (каноническая теорема равновесия).

   Допустимые решения $x = (\xi_1, \dots, \xi_m)$ и $y = (\eta_1, \dots, \eta_n)$ ПЗ и ДЗ в канонической форме будут оптимальными тогда и только тогда, когда \[ \xi_i = 0, \quad \text{если} \quad a_i y \gt \gamma_i. \]

   Рассмотрим \[ \overset{\text{ПЗ}}{ \begin{gathered} \max \dp{c}{x} \\ xA = b \\ x \geqslant 0 \end{gathered} } \quad \text{и} \quad \overset{\text{ДЗ}}{ \begin{gathered} \max \dp{b}{y} \\ Ay \geqslant c \\ \forall y \end{gathered} } \]

   Пусть $x$ и $y$ — оптимальные решения. Тогда \[ \begin{aligned} cx = \sum_{i=1}^m \xi_i \gamma_i &\leqslant \sum_{i=1}^m \xi_i (a_i y) \\ &= \underbrace{\sum_{i=1}^m (\xi_i a_i)}_{=xA =b} y = by. \end{aligned} \] Равенство выполнено тогда, когда в сумме отсутствуют слагаемые, для которых \[ \gamma_i \lt a_i y, \] то есть \[ \gamma_i \lt a_i y \implies \xi_i = 0. \]

   Пусть выполнено условие \[ \gamma_i \lt a_i y \implies \xi_i = 0. \] Рассмотрим разность \[ \begin{aligned} cx - by &= cx - xAy \\ &= \sum_{i=1}^m \xi_i \gamma_i - \sum_{i=1}^m \xi_i a_i y \\ &= \sum_{i=1}^m \xi_i \paren{\gamma_i - a_i y}. \end{aligned} \] Рассмотрим каждое слагаемое:

   • Если $\gamma_i - a_i y = 0$, то слагаемое равно нулю.
   • Если $\gamma_i - a_i y \gt 0$, то по условию теоремы $\xi_i = 0$, и слагаемое равно нулю.

   Таким образом, \[ cx - by = 0 \implies cx = by, \] значит, по критерию оптимальности, $x$ и $y$ — оптимальные решения.
7. Теорема о существовании оптимального базисного решения
   Рассмотрим \[ \overset{\text{ПЗ}}{ \begin{gathered} \max \dp{c}{x} \\ xA = b \\ x \geqslant 0 \end{gathered} } \quad \text{и} \quad \overset{\text{ДЗ}}{ \begin{gathered} \max \dp{b}{y} \\ Ay \geqslant c \\ \forall y \end{gathered} } \]

   (о существовании оптимального базисного решения).

   Если ПЗ имеет оптимальное решение, то она имеет оптимальное базисное решение.

   Расписать.
8. Теорема о преобразовании симплексной таблицы
   • $a_1, \dots, a_m$ — некоторая система линейно независимых векторов из $\mathbb{R}^n$;
   • $b_1, \dots, b_n$ — произвольная система векторов из $\mathbb{R}^n$, выражающихся через $a_1, \dots, a_m$.

   Построим таблицу из коэффициентов $b_j = \sum\limits_{i=1}^m \tau_{ij} a_i$: \[ \begin{array}{c|ccccc} & b_1 & \dots & b_j & \dots & b_n \\ \hline a_1 & \tau_{11} & \dots & \tau_{1j} & \dots & \tau_{1n} \\ \vdots & \vdots & \ddots & \vdots & \ddots & \vdots \\ a_i & \tau_{i1} & \dots & \tau_{ij} & \dots & \tau_{in} \\ \vdots & \vdots & \ddots & \vdots & \ddots & \vdots \\ a_m & \tau_{m1} & \dots & \tau_{mj} & \dots & \tau_{mn} \end{array} \]

   Допустим, хотим исключить $a_r$, а на его место поставить $b_s$: \[ \begin{array}{c|ccccc} & b_1 & \dots & b_s & \dots & b_n \\ \hline a_1 & \tau_{11} & \dots & 0 & \dots & \tau_{1n} \\ \vdots & \vdots & \ddots & \vdots & \ddots & \vdots \\ {\color{green}b_s} & \tau_{s1}' & \dots & 1 & \dots & \tau_{sn}' \\ \vdots & \vdots & \ddots & \vdots & \ddots & \vdots \\ a_m & \tau_{m1} & \dots & 0 & \dots & \tau_{mn} \end{array} \]

   Если в первоначальной строке $T$ коэффициент $\tau_{rs} \neq 0$, то

   1. вектора $(a_1, \dots, a_{r-1}, b_s, a_{r+1}, \dots, a_m)$ — линейно независимы;
   2. элементы таблицы $T'$ вычисляются по формулам: \[ \begin{cases} \tau_{ij}' = \tau_{ij} - \dfrac{\tau_{is}}{\tau_{rs}} \tau_{rj}, & i \neq r, \\ \tau_{rj}' = \dfrac{\tau_{rj}}{\tau_{rs}}, & i = r. \end{cases} \]

   1. От противного: пусть $\tau_{rs} \neq 0$, но вектора $(a_1, \dots, a_{r-1}, b_s, a_{r+1}, \dots, a_m)$ линейно зависимы. Тогда \[ \exists \lambda, \mu_s \neq 0: \quad \sum_{i \neq r} \lambda_i a_i + \mu_s b_s = 0, \] но \[ b_s = \sum_{i=1}^m \tau_{is} a_i, \] поэтому \[ \sum_{i \neq r} \paren{\lambda_i + \mu_s \tau_{is}} a_i + \mu_s \tau_{rs} a_r = 0, \] то есть $(a_1, \dots, a_m)$ линейно зависимы — противоречие.
   2. Проверим формулы: \[ \begin{aligned} b_j &= \sum_{i \neq r} \tau_{ij}' a_i + \tau_{sj}' b_s \\ &= \sum_{i \neq r} \paren{\tau_{ij} - \frac{\tau_{is}}{\tau_{rs}} \tau_{rj}} a_i + \frac{\tau_{rj}}{\tau_{rs}} b_s \\ &= \sum_{i \neq r} \paren{\tau_{ij} - \frac{\tau_{is}}{\tau_{rs}} \tau_{rj}} a_i + \frac{\tau_{rj}}{\tau_{rs}} \sum_{i=1}^m \tau_{is} a_i \\ &= \sum_{i \neq r} \tau_{ij} a_i + \tau_{rj} a_r \\ &= b_j. \end{aligned} \]
9. Алгоритм симплексного метода
   Рассмотрим ДЗ: \[ \begin{gathered} \min \dp{b}{y} \\ Ay = c \\ y \geqslant 0, \end{gathered} \] где

   • $b = (\beta_1, \dots, \beta_n)$;
   • $c = (\gamma_1, \dots, \gamma_m)$;
   • $A = (\alpha_{ij})_{m \times n}$.

   Допустим, известно первое базисное решение $y = (\eta_1, \dots, \eta_m, 0, \dots, 0)$.

   Запишем симплексную таблицу: \[ \begin{array}{c|ccccccccc|c} & a^1 & \dots & a^r & \dots & a^m & \dots & a^s & \dots & a^n & c \\ \hline a^1 & 1 & \dots & 0 & \dots & 0 & \dots & \tau_{1s} & \dots & \tau_{1n} & \eta_1 \\ \vdots & \vdots & \ddots & \vdots & \ddots & \vdots & \ddots & \vdots & \ddots & \vdots & \vdots \\ a^r & 0 & \dots & 1 & \dots & 0 & \dots & \tau_{rs} & \dots & \tau_{rn} & \eta_r \\ \vdots & \vdots & \ddots & \vdots & \ddots & \vdots & \ddots & \vdots & \ddots & \vdots & \vdots \\ a^m & 0 & \dots & 0 & \dots & 1 & \dots & \tau_{ms} & \dots & \tau_{mn} & \eta_m \\ \hline z - b & 0 & \dots & 0 & \dots & 0 & \dots & \xi_s - \beta_s & \dots & \xi_n - \beta_m & \xi_0 \end{array} \]

   • Первый ряд $(a^1, \dots, a^m)$ — текущий базис.
   • Коэффициенты в таблице — коэффициенты разложения векторов $(a^1, \dots, a^n)$ по базису: \[ a^s = \sum_{i=1}^m \tau_{is} a^i, \quad s = \overline{1,n}. \]
   • $z = (\xi_1, \dots, \xi_n)$, причём $\xi_k = 0$ для всех $k = \overline{1,p}$.
   • $\xi_s = \sum\limits_{i=1}^m \tau_{is} \beta_i$ — скалярное произведение вектора $\vec{b}$ на соответствующий столбец.
   • $\xi_0 = \sum\limits_{i=1}^m \beta_i \eta_i$ — значение целевой функции при заданном базисном решении.

   1. Что вводим в базис?
      Ищем любой столбец такой, что $\beta_s \lt \xi_s$. Тогда $a^s$ — кандидат на введение.
   2. Что выводим из базиса?
      Строим отношение $\dfrac{\eta_i}{\tau_{is}}$ для всех $\tau_{is} \gt 0$, ищем $\min\limits_i \dfrac{\eta_i}{\tau_{is}} = \dfrac{\eta_r}{\tau_{rs}}$, заменяем $a^r$ на $a^s$.

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

   Когда останавливаться?

   • Если на первом шагу все $\beta_s \gt \xi_s$, то получено оптимальное решение.
   • Если на втором шагу все $\tau_{is} \lt 0$, то оптимального решения не существует.
10. Обоснование симплексного метода. Теорема об оптимальном решении
    Рассмотрим ДЗ: \[ \begin{gathered} \min \dp{b}{y} \\ Ay = c \\ y \geqslant 0, \end{gathered} \] где

    • $b = (\beta_1, \dots, \beta_n)$;
    • $c = (\gamma_1, \dots, \gamma_m)$;
    • $A = (\alpha_{ij})_{m \times n}$.

    Допустим, известно первое базисное решение $y = (\eta_1, \dots, \eta_m, 0, \dots, 0)$.

    Запишем симплексную таблицу: \[ \begin{array}{c|ccccccccc|c} & a^1 & \dots & a^r & \dots & a^m & \dots & a^s & \dots & a^n & c \\ \hline a^1 & 1 & \dots & 0 & \dots & 0 & \dots & \tau_{1s} & \dots & \tau_{1n} & \eta_1 \\ \vdots & \vdots & \ddots & \vdots & \ddots & \vdots & \ddots & \vdots & \ddots & \vdots & \vdots \\ a^r & 0 & \dots & 1 & \dots & 0 & \dots & \tau_{rs} & \dots & \tau_{rn} & \eta_r \\ \vdots & \vdots & \ddots & \vdots & \ddots & \vdots & \ddots & \vdots & \ddots & \vdots & \vdots \\ a^m & 0 & \dots & 0 & \dots & 1 & \dots & \tau_{ms} & \dots & \tau_{mn} & \eta_m \\ \hline z - b & 0 & \dots & 0 & \dots & 0 & \dots & \xi_s - \beta_s & \dots & \xi_n - \beta_m & \xi_0 \end{array} \]

    (об оптимальности). Если в последней строке симплекс-таблицы нет положительных элементов (кроме $\xi_0$), то полученное базисное решение является оптимальным.

    По следствию из теоремы о ранге матрицы \[ \exists x: \quad a^i x = \beta_i, \quad i = \overline{i,m}. \] Посчитаем, чему равно выражение $a^i x$ для векторов, не входящих в базис: \[ \begin{aligned} a^s x &= \sum_{i=1}^m \tau_{is} a^i x \\ &= \sum_{i=1}^m \tau_{is} \beta_i \bydef = \xi_s \leqslant \beta_s, \quad s = \overline{1,n}. \end{aligned} \]
11. Обоснование симплексного метода. Лемма о преобразовании последней строки симплексной таблицы
12. Обоснование симплексного метода. Теорема о неограниченном решении
13. Матричная игра. Максиминные и минимаксные стратегии. Равновесия
    Система вида $\Gamma = \angset{X, Y, K}$, где

    • $X \neq \varnothing$ — множество стратегий игрока $I$;
    • $Y \neq \varnothing$ — множество стратегий игрока $II$;
    • $K: X \times Y \to \mathbb{R}$, причём
      • $\phantom{(-}K\phantom{)}$ — выигрыш $I$-го игрока,
      • $(-K)$ — выигрыш $II$-го игрока,

    называется антагонистической игрой в нормальной форме.

    Матричная игра — антагонистическая игра, в которой множества стратегий игроков конечны.

    Пусть $X$ и $Y$ — конечные множества: \[ \begin{aligned} \abs{X} &= m, & X \leftrightarrow M &= \set{1, \dots, m} \\ \abs{Y} &= n, & Y \leftrightarrow N &= \set{1, \dots, n} \end{aligned} \] Обозначим:

    • $\phantom{-}K(x_i, y_i) = \phantom{-} \alpha_{ij}$ — выигрыш игрока $I$ в ситуации $(i, j)$;
    • $-K(x_i, y_i) = -\alpha_{ij}$ — выигрыш игрока $II$ в ситуации $(i, j)$.

    Сумма выигрышей равна нулю.

    Игроки независимо друг от друга и одновременно выбирают стратегии.

    Рассмотрим матрицу выигрышей \[ A = \paren{ \begin{matrix} \alpha_{11} & \dots & \alpha_{1n} \\ \vdots & \ddots & \vdots \\ \alpha_{m1} & \dots & \alpha_{mn} \end{matrix} } \]

    $\underline{V} \bydef = \sup\limits_x \inf\limits_y K(x,y)$ называют нижним значением игры.

    Если экстремум достигается, то $\underline{V}$ называют максимином игры.

    Максиминная стратегия — номер строки, в которой минимальный элемент принимает максимальное значение.

    $\overline{V} \bydef = \inf\limits_y \sup\limits_x K(x,y)$ называют верхним значением игры.

    Если инфимум достигается, то $\overline{V}$ называют минимаксом игры.

    Минимаксная стратегия — номер столбца, в котором максимальный элемент принимает минимальное значение.

    В антагонистической игре $\underline{V} \leqslant \overline{V}$.

    Так как \[ K(x,y) \leqslant \sup_x K(x,y) \quad \forall x \in X, \; \forall y \in Y, \] верно для любого $y$, то \[ \inf_y K(x,y) \leqslant \underbrace{\inf_y \sup_x K(x,y)}_{\const} \quad \forall x \in X. \] Неравенство верно для любого $x$, поэтому \[ \underline{V} \bydef = \sup_x \inf_y K(x,y) \leqslant \inf_y \sup_x K(x,y) \bydef = \overline{V}. \]

    Ситуация $(x^*, y^*) \in X \times Y$ называется ситуацией равновесия (седловой точкой) в игре $\Gamma$, если \[ \forall x \in X, \; \forall y \in Y \quad K(x, y^*) \leqslant K(x^*, y^*) \leqslant K(x^*, y). \] В этом случае $K(x^*, y^*) = V$ называют значением игры.

    Множество всех ситуаций равновесия в игре $\Gamma$ обозначим через $Z(\Gamma) \subset X \times Y$.

14. Необходимое и достаточное условие существования оптимальных стратегий в матричной игре
    (о существовании ситуации равновесия). В матричной игре ситуация равновесия существует тогда и только тогда, когда существуют минимакс $\overline{V}$ и максимин $\underline{V}$ и выполняется равенство \[ \underline{V} = \overline{V} = V. \]

    Пусть $(i_0, j_0)$ — ситуация равновесия, тогда по определению \[ \alpha_{ij_0} \leqslant \alpha_{i_0 j_i} \leqslant \alpha_{i_0j} \quad \forall i \in X, j \in Y, \] поэтому \[ \max_{i \in X} \alpha_{i j_0} \leqslant \alpha_{i_0 j_0} \leqslant \min_{j \in Y} \alpha_{i_0 j}. \] Так как \[ \overline{V} \bydef = \min_{j \in Y} \max_{i \in X} \alpha_{ij} \leqslant \max_{i \in X} \alpha_{i j_0} \] и \[ \min_{j \in Y} \alpha_{i_0 j} \leqslant \max_{i \in X} \min_{j \in Y} \alpha_{ij} \bydef = \underline{V}, \] то \[ \overline{V} \leqslant V \leqslant \underline{V}, \] но по лемме $\underline{V} \leqslant \overline{V}$, поэтому $\overline{V} = \underline{V} = V$.

    Пусть $\underline{V} = \overline{V} = V$. Тогда \[ \underline{V} \bydef = \min_{j \in Y} \alpha_{i_0 j} = V = \max_{i \in X} \alpha_{i j_0} \bydef = \overline{V}, \] а, следовательно, \[ \alpha_{i_0 j} \geqslant V \geqslant \alpha_{i j_0} \quad \forall i \in X, j \in Y. \] Рассмотрим $i = i_0$ и $j = j_0$: \[ \alpha_{i_0 j_0} \geqslant V \geqslant \alpha_{i_0 j_0}, \implies V = \alpha_{i_0 j_0}. \] Таким образом, \[ \alpha_{i j_0} \leqslant \alpha_{i_0 j_0} \leqslant \alpha_{i_0 j} \quad \forall i \in X, j \in Y, \] поэтому $(i_0, j_0)$ является ситуацией равновесия.
15. Смешанное расширение матричной игры
    Случайная величина, значениями которой являются стратегии игрока, называется смешанной стратегией.

    Рассмотрим игру $\Gamma = \angset{M, N, A}$.

    • Смешанная стратегия $I$-го игрока: $\vec x = (\xi_1, \dots, \xi_m)$, где $\xi_i$ — вероятность розыгрыша $i$-ой чистой стратегии $I$ игрока; \[ \xi_i \geqslant 0, \quad \sum_{i=1}^m \xi_i = 1. \]
    • Смешанная стратегия $II$-го игрока: $\vec y = (\eta_1, \dots, \eta_m)$, где $\eta_i$ — вероятность розыгрыша $i$-ой чистой стратегии $II$ игрока; \[ \eta_i \geqslant 0, \quad \sum_{i=1}^m \eta_i = 1. \]

    Обозначим:

    • $\overline{X}$ или $\Sigma_I$ — множество смешанных стратегий $I$-го игрока;
    • $\overline{Y}$ или $\Sigma_{II}$ — множество смешанных стратегий $II$-го игрока.

    $\overline{X}$ и $\overline{Y}$ — выпуклые компакты.

    Выигрышем $I$-го игрока называется мат. ожидание выигрыша при использовании стратегии \[ \overline K(\bar x, \bar y) = \sum_{i=1}^m \sum_{j=1}^n \xi_i a_{ij} \eta_j = \bar x A \bar y. \]

    Для игры $\Gamma = \angset{X, Y, K}$ игра $\overline \Gamma = \angset{\overline X, \overline Y, \overline K}$ называется смешанным расширением.

    Ситуация $(\bar x, \bar y)$ называется ситуацией равновесия в $\overline \Gamma$, а число $V = \overline K(\bar x, \bar y)$ — значением игры, если \[ \overline K(x, \bar y) \leqslant \overline K(\bar x, \bar y) \leqslant \overline K(\bar x, y) \qquad \forall x \in \overline X, y \in \overline Y. \]
16. Свойства оптимальных смешанных стратегий

    Пусть $Z(\Gamma)$ — множество ситуаций равновесия в игре $\Gamma = \angset{X, Y, K}$.

    Свойства:

    1. Единственность в смысле выигрыша: для любых двух ситуаций равновесия $(x_1^*, y_1^*), (x_2^*, y_2^*) \in Z(\Gamma)$ выполнено: \[ K(x_1^*, y_1^*) = K(x_2^*, y_2^*) = K(x_1^*, y_2^*) = K(x_2^*, y_1^*) = v. \]

       расписать.
    2. Для любых двух ситуаций равновесия $(x_1^*, y_1^*), (x_2^*, y_2^*) \in Z(\Gamma)$ справедливо \[ (x_1^*, y_2^*), (x_2^*, y_1^*) \in Z(\Gamma). \]

       расписать.
    3. (о масштабе). Пусть $\Gamma = \angset{X, Y, K}$ и $\Gamma' = \angset{X, Y, K'}$, причём $K' = \alpha K + \beta$, где $\alpha \gt 0, \beta \in \mathbb{R}$. Тогда \[ Z(\Gamma) = Z(\Gamma') \quad \text{и} \quad V' = \alpha V + \beta. \]
    4. \[ (x^*, y^*) \in Z(\Gamma) \iff K(i, y^*) \leqslant K(x^*, y^*) \leqslant K(x^*, j) \] для любых $i \in X, j \in Y$.

       Расписать.
    5. Пусть $(x^*, y^*) \in Z(\Gamma)$, где $x^* = (\xi_1^*, \dots, \xi_m^*)$ и $y^* = (\eta_1^*, \dots, \eta_n^*)$. Тогда:

       1. если $K(i, y^*) \lt K(x^*, y^*)$, то $\xi_i^* = 0$;
       2. если $K(x^*, j) \gt K(x^*, y^*)$, то $\eta_j^* = 0$;
    6. Пусть $(x^*, y^*) \in Z(\Gamma)$. Тогда:

       1. $\max\limits_i K(i, y^*) = K(x^*, y^*) = V$;
       2. $\min\limits_j K(x^*, j) = K(x^*, y^*) = V$.
17. Теорема о существовании ситуации равновесия в смешанных стратегиях
    (фон Неймана о существовании ситуации равновесия в матричной игре). Всякая матричная игра имеет ситуацию равновесия в смешанных стратегиях.
18. Теорема о доминировании для матричных игр
    Рассмотрим матричную игру $\Gamma = \angset{X, Y, K}$.

    Говорят, что чистая стратегия $i$ доминирует чистую стратегию $k$ для $I$-го игрока, если $a_{ij} \gt a_{kj}$ для любого $j \in Y$. Аналогично для $II$-го игрока.

    Если $a_{ij} \geqslant a_{kj}$ для любого $j \in Y$, то говорят о нестрогом доминировании.

    Говорят, что смешанная стратегия $\xi'$ доминирует смешанную стратегию $\xi''$ для игрока $I$, если \[ \xi' a^j \geqslant \xi'' a^j \quad \forall j \in Y. \]

    Говорят, что стратегия доминируемая, если существует хотя бы одна доминирующая её стратегия.

    Говорят, что стратегия $k$ доминируема выпуклой комбинацией стратегий $i$ и $j$ для игрока $I$, если \[ \exists \lambda \in (0,1): \quad \lambda a_{ip} + (1 - \lambda) a_{jp} \gt a_{kp} \quad \forall p \in Y. \]

    Пусть $x = (\xi_1, \dots, \xi_{i-1}, \xi_i, \xi_{i+1}, \dots, \xi_m) \in \mathbb{R}^m$ — смешанная стратегия. Тогда вектор $x' = (\xi_1, \dots, \xi_{i-1}, 0, \xi_i, \xi_{i+1}, \dots, \xi_m) \in \mathbb{R}^{m+1}$ называют $i$-местным расширением стратегии $x$.

    (о доминировании). Рассмотрим матричную игру $\Gamma = \angset{X,Y,K}$. Пусть чистая стратегия $i$ доминируема выпуклой линейной комбинацией других строк: \[ \alpha_{ij} \geqslant \sum_{k=1,k\neq i}^m \lambda_k \alpha_{kj}, \] где \[ \lambda_k \geqslant 0, \quad \sum_{k=1,k\neq i}^m \lambda_k = 1. \] Рассмотрим игру $\Gamma'$ с матрицей $A'$, которая получилась вычёркиванием из $A$ стратегии $i$. Тогда если $x^*$ и $y^*$ — оптимальные стратегии в $\Gamma'$, то $\bar x_i^*$ и $y^*$ — оптимальные стратегии в $\Gamma$, а также $V' = V$.

    $\bar x_i^*$ — $i$-местное расширение стратегии $x^*$.

    Если стратегия $i$ строго доминируема, то любая оптимальная стратегия $\bar x_i^*$ в $\Gamma$ может быть получена расширением оптимальной стратегии в $\Gamma'$ на $i$-ом месте.
19. Понятие игры в нормальной форме. Равновесие по Нэшу. Примеры. Парадокс Брайеса
    Система $\Gamma = \angset{N, \set{X_i}_{i \in N}, \set{K_i}_{i \in N}}$ называется бескоалиционной игрой $n$ лиц, или игрой в нормальной форме.

    Ситуация $x^*$ называется ситуацией равновесия по Нэшу (NE), если для любого игрока односторонее отклонение невыгодно, то есть для любого $i \in N$ \[ K_i(x^*) \geqslant K_i(x^* \Vert x_i) \quad \forall x_i \in X_i, \] где $(x^* \Vert x_i) \bydef = (x_1^*, \dots, x_{i-1}^*, x_i, x_{i+1}^*, \dots, x_n^*)$.

    Множество ситуаций равновесия по Нэшу обозначают $X^{NE}$.

    1. Выигрыши в разных NE, вообще говоря, разные.
    2. Из того, что $x_i$ и $y_j$ — стратегии из NE, не следует, что $(x_i, y_j)$ — NE.
    3. В игре могут встречаться решения, по всем компонентам превосходящие NE.
    4. NE может не существовать в чистых стратегиях.
    5. Ситуация равновесия по Нэшу не является устойчивой относительно двух игроков.

    В случае матричной игры ($n = 2$ и $K_1 = -K_2$) NE эквивалентна ситуации равновесия.

    По определению NE \[ \begin{aligned} K_1(x_1^*, x_2^*) &\geqslant K_1(x_1, x_2^*) \\ K_2(x_1^*, x_2^*) &\geqslant K_2(x_1^*, x_2), \end{aligned} \implies \begin{aligned} K_1(x_1^*, x_2^*) &\geqslant \phantom{-} K_1(x_1, x_2^*) \\ -K_2(x_1^*, x_2^*) &\leqslant -K_2(x_1^*, x_2), \end{aligned} \] но $K_1 = -K_2$, поэтому \[ K_1(x_1, x_2^*) \leqslant K(x_1^*, x_2^*) \leqslant K_1(x_1^*, x_2), \] откуда по определению $(x_1^*, x_2^*)$ — ситуация равновесия.

    Ситуация $\bar x$ называется оптимальной по Парето (PO) в неантагонистической игре $\Gamma$, если не существует такой ситуации $x$, которая давала бы всем игрокам не меньший выигрыш, а хотя бы одному больший, то есть \[ \nexists x \in X: \quad K_i(x) \geqslant K_i(\bar x) \quad \text{и} \quad \exists i_0 \in N: \quad K_{i_0}(x) \gt K_i(\bar x). \]

    (семейный спор). Муж и жена могут выбрать одно из двух вечерних развлечений: футбольный матч $(\alpha_1, \beta_1)$ или театр $(\alpha_2, \beta_2)$. Если они имеют разные желания $(\alpha_1, \beta_2)$ или $(\alpha_2, \beta_1)$, то остаются дома.

    Игра биматричная: \[ (A,B) = \begin{matrix} & \beta_1 & \beta_2 \\ \begin{matrix} \alpha_1 \\ \alpha_2 \end{matrix} & \left[ \begin{matrix} {\color{green}(4,1)} \\ (0,0) \end{matrix} \right. & \left. \begin{matrix} (0,0) \\ {\color{green}(1,4)} \end{matrix} \right] \\ & & \end{matrix}. \]

    Возможные ситуации:

    • $(\alpha_1, \beta_1)$ — NE и PO;
    • $(\alpha_2, \beta_2)$ — NE и PO.

    (дилемма заключённого). Обозначения:

    • $\text{С}_1, \text{НС}_1$ — стратегии первого игрока (сказать/не сказать)
    • $\text{С}_2, \text{НС}_2$ — стратегии второго игрока (сказать/не сказать)

    Игра биматричная: \[ (A,B) = \begin{matrix} & \text{С}_2 & \text{НС}_2 \\ \begin{matrix} \text{С}_1 \\ \text{НС}_1 \end{matrix} & \left[ \begin{matrix} {\color{#47c7f0}(-7,-7)} \\ {\color{orange}(-10,0)} \end{matrix} \right. & \left. \begin{matrix} {\color{orange}(0,-10)} \\ {\color{orange}(-1,-1)} \end{matrix} \right] \\ & & \end{matrix}. \]

    Возможные ситуации:

    • $(\alpha_1, \beta_1)$ — NE;
    • $(\alpha_1, \beta_2)$ — PO;
    • $(\alpha_2, \beta_1)$ — PO;
    • $(\alpha_2, \beta_2)$ — PO (неустойчивое).

    (парадокс Брайеса) .

    Расписать.

    
20. Кооперативные игры. Характеристическая функция. Дележи. Доминирование дележей
    Подмножество множества игроков $S \subseteq N$ называется коалицией.

    Пара $(N, v)$ называется кооперативной игрой, если

    1. $N \subset \mathbb{N}$ — конечное множество игроков;
    2. $v: 2^N \to \mathbb{R}$, — характеристическая функция, сопоставляющая каждому подмножеству множества игроков $S \subseteq N$ вещественное число и обладающая свойствами:
       1. $v(\varnothing) = 0$;
       2. Для любых двух непересекающихся коалиций $S_1,S_2 \subset N$ справедливо неравенство: \[ v(S_1 \cup S_2) \geqslant v(S_1) + v(S_2) \]
       3. $v(N) = \sum\limits_{i=1}^n K_i(\bar x_1, \dots, \bar x_n)$ — максимальный суммарный выигрыш.

    Вектор $\alpha = (\alpha_1, \dots, \alpha_n)$ называется дележом кооперативной игры, если

    1. $\sum\limits_{i \in N} \alpha_i = v(N)$ — все дележи PO;
    2. $\alpha_i \geqslant v(\{i\}) \quad \forall i \in N$, — каждый игрок получает по крайней мере столько, как если бы он действовал один.

    Из условий следует, что \[ v(N) \geqslant \sum_{i \in N} v(\{i\}), \] то есть вместе играть выгоднее.

    Кооперативная игра называется существенной, если \[ v(N) \gt \sum_{i\in N} v(\{i\}). \]

    Говорят, что делёж $\alpha$ доминирует делёж $\beta$ по коалиции $S \subset N$, если выполнены два условия:

    1. Предпочтительность. Делёж $\alpha$ лучше дележа $\beta$ для всех членов коалиции $S$: \[ \alpha_i \gt \beta_i \quad \forall i \in S. \]
    2. Реализуемость. Коалиция действительно может предложить каждому игроку $i$ величину $\alpha_i$: \[ \alpha(S) = \sum_{i \in S} \alpha_i \leqslant v(S). \]

    Иными словами, для коалиции $S$ делёж $\alpha$ выгоднее дележа $\beta$.

    Обозначение: $\alpha \overset{S}{\succ} \beta$.

    Говорят, что делёж $\alpha$ доминирует делёж $\beta$, если существует коалиция $S$, для которой $\alpha \overset{S}{\succ} \beta$.

    Обозначение: $\alpha \succ \beta$.

    • Доминирование по одноэлементной коалиции невозможно.
      Пусть $\beta$ — некоторый делёж. Предположим, что существует делёж $\alpha \overset{\{i\}}{\succ} \beta$. Тогда по определению доминирования по коалиции \[ \beta_i \lt \alpha_i, \quad \text{и} \quad \alpha_i \leqslant v(\{i\}) \] но по определению дележа \[ \beta_i \geqslant v(\{i\}), \] то есть $\beta$ дележом не является.
    • Нельзя доминировать, когда $S = N$
      Пусть $\beta$ — некоторый делёж. Предположим, что существует делёж $\alpha \overset{N}{\succ} \beta$. Тогда по определению доминирования по коалиции \[ \beta_i \lt \alpha_i \quad \forall i \in N \] но по определению дележа \[ \sum_{i\in N} \beta_i = v(N), \] тогда \[ \sum_{i\in N} \alpha_i \gt v(N), \] то есть $\alpha$ дележом не является.
    • Отношение доминирования некоммутативно: \[ \alpha \succ \beta \quad \cancel\Longrightarrow \quad \beta \succ \alpha. \]
21. $C$-ядро игры. Необходимое и достаточное условие непустоты $C$-ядра. $HM$-решение
    Множество недоминируемых дележей кооперативной игры $(N, v)$ называется $C$-ядром.

    $C$-ядро может быть пустым.

    (Необходимое и достаточное условие недоминируемости дележа) \[ \alpha \in C(N, v) \iff \sum_{i \in S} \alpha_i \geqslant v(S) \quad \forall S \subset N. \]

    Рассмотрим $\alpha \in C(N, v)$. Предположим, что \[ \exists T \subset N: \quad \alpha(T) \lt v(T). \] Тогда рассмотрим вектор $\beta \in \mathbb{R}^n$, коэффициенты которого имеют вид: \[ \left\{ \begin{aligned} \beta_i &= \alpha_i + \frac{v(T) - \alpha(T)}{\abs{T}}, & i \in T \\ \beta_i &= v(\{i\}) + \frac{v(N) - v(T) - \sum_{i \not\in T} v(\{i\})} {\abs{N} - \abs{T}}, & i \not\in T. \end{aligned} \right. \] Проверим, является ли он дележом:

    1. Должно выполняться $\beta_i \geqslant v(\{i\}), i \in N$. Проверяем: \[ \begin{aligned} \forall i \in T && \beta_i &= \alpha_i + \frac{v(T) - \alpha(T)}{\abs{T}} \gt \alpha_i \geqslant v(\{i\}) \\ \forall i \not\in T && \beta_i &= v(\{i\}) + \frac{V(N) - V(T) - \sum_{i \not\in T} v(\{i\})} {\abs{N} - \abs{T}} \geqslant v(\{i\}). \end{aligned} \]
    2. Должно выполняться $\sum_{i \in N} \beta_i = v(N)$. Проверяем: \[ \begin{aligned} \sum_{i \in N} \beta_i &= \sum_{i \in T} \beta_i + \sum_{i \not\in T} \beta_i \\ &= {\color{red}\sum_{i \in T} \alpha_i} + {\color{#47c7f0}v(T)} - {\color{red}\alpha(T)} + {\color{green}\sum_{i \not\in T} v(\{i\})} + v(N) - {\color{#47c7f0}v(T)} - {\color{green}\sum_{i \not\in T} v(\{i\})} \\ &= v(N). \end{aligned} \]

    Таким образом, $\beta$ является дележом.

    Проверим, доминирует ли он делёж $\alpha$:

    1. Предпочтительность: \[ \beta_i \gt \alpha_i \quad \forall i \in T. \]
    2. Реализуемость: \[ \sum\limits_{i \in T} \beta_i = {\color{red}\alpha(T)} + v(t) - {\color{red}\alpha(T)} = v(t) \leqslant v(t). \]

    Таким образом, делёж $\beta$ доминирует делёж $\alpha$, что противоречит тому, что $\alpha \in C(N,v)$.

    Пусть \[ \alpha(S) \geqslant v(S) \quad \forall S \subset N. \] Предположим, что $\alpha \not\in C$, то есть существует делёж $\beta$, доминирующий $\alpha$ по некоторой коалиции $T \subset N$, то есть выполнены свойства:

    1. Предпочтительность: \[ \beta_i \gt \alpha_i \quad \forall i \in T; \]
    2. Реализуемость: \[ \sum\limits_{i \in T} \beta_i \leqslant v(T). \]

    Из предпочтительности следует, что \[ \beta(T) \gt \alpha(T), \] но \[ \alpha(S) \geqslant v(S) \quad \forall S \subset N, \] поэтому \[ \beta(T) \gt v(T), \] что противоречит реализуемости дележа $\beta$.

    Подмножество $L$ дележей называется $NM$-решением, если выполняются условия:

    1. Внутренняя устойчивость. \[ \alpha \succ \beta \implies \alpha \not\in L \quad \text{или} \quad \beta \not\in L. \]
    2. Внешняя устойчивость. \[ \forall \alpha \not\in L \quad \exists \beta \in L: \quad \beta \succ \alpha. \]

    $NM$-решение может быть пустым.

    $C$-ядро — подмножество $NM$-решения.

    От противного: пусть $C \not\subset NM$, тогда существует по крайней мере один элемент $C$-ядра $\alpha$, не принадлежащий $NM$. Тогда \[ \exists \alpha \not\in NM: \quad \forall \beta \in NM \quad \beta \not\succ \alpha, \] что противоречит определению $NM$-решения.
22. Вектор Шепли
    Рассмотрим кооперативную игру $(N, v)$ с $n$ игроками.

    Рассмотрим $v(S) - v(S \setminus \{i\})$. Это вклад игрока $i$ в коалицию $S$, которая создаётся случайным образом:

    • С вероятностью $1/n$ выбирается размер коалиции;
    • Коалиция с игроком $i$ данного размера выбирается равновероятно.

    Таким образом, коалицию размера $\abs{S}$ с игроком $i$ можно построить $C_{n-1}^{\abs{S} - 1}$ количеством способов. Найдём мат. ожидание его вклада в коалицию: \[ \begin{aligned} \Sh_i &= \sum_{S \subset N, i \in S} \frac{1}{n} \cdot \frac{1}{C_{n-1}^{\abs{S}-1}} \left[v(S) - v(S \setminus \{i\})\right] \\ &= \sum_{S \subset N, i \in S} \frac{1}{n} \cdot \frac{(\abs{S}-1)! (n - \abs{S})!}{(n-1)!} \left[v(S) - v(S \setminus \{i\})\right] \\ &= \sum_{S \subset N, i \in S} \frac{(\abs{S}-1)! (n - \abs{S})!}{n!} \left[v(S) - v(S \setminus \{i\})\right] \\ \end{aligned} \]

    Вектор Шепли — принцип оптимальности распределения выигрыша между игроками.

    1. Вектор Шепли является дележом.
    2. Для каждой кооперативной игры существует единственный вектор Шепли.

    Вектор Шепли не всегда принадлежит $C$-ядру.
23. Примеры задач динамического программирования
    (Задача о загрузке самолёта).

    • $W$ — допустимый вес;
    • $V$ — допустимый объём;
    • $n$ видов грузов:
      • $v_i$ — объём груза типа $i$;
      • $w_i$ — вес единицы груза типа $i$;
      • $c_i$ — стоимость единицы груза типа $i$.

    Обозначим вектор загрузки как $x = (\xi_1, \dots, \xi_n)$, где $\xi_i$ — количество единиц груза $i$-го вида, загруженного в самолёт, причём $\xi_i \in \mathbb{Z}$.

    ЗЛП не требует целочисленного ограничения, но по смыслу задачи он необходим, т.к. грузы неделимы.

    Получаем ЗЛП: \[ \begin{gathered} xc \to \max \\ xv \leqslant V \\ xw \leqslant W \\ x \geqslant 0, \; x \in \mathbb{Z}^n \end{gathered} \]

    Рассмотрим функцию Беллмана $\mathcal{F}_n(W, V)$, означающую максимальную ценность грузов, которая может быть перевезена самолётом с грузоподъёмностью $W$ и полезным объёмом $V$, при условии, что мы используем данные $n$ типов грузов.

    Пусть мы загрузили в самолёт $\xi_n$ единиц груза $n$-го типа, тогда получили «новый» самолёт с новыми параметрами: \[ \mathcal{F}_{n-1} (W - \xi_n w_n, V - \xi_n v_n). \] Предположим, что остатком распорядились оптимально, тогда суммарная ценность перевозимого груза составит \[ \xi_n c_n + \mathcal{F}_{n-1} (W - \xi_n w_n, V - \xi_n v_n). \] Она зависит только от $\xi_n$, поэтому \[ \mathcal{F}_n(W, V) = \max_{\xi_n} \paren{\xi_n c_n + \mathcal{F}_{n-1} (W - \xi_n w_n, V - \xi_n v_n)}, \quad \text{где} \quad 0 \leqslant \xi_n \leqslant \min \left\{ \floor{\frac{W}{w_n}}, \floor{\frac{V}{v_n}} \right\}. \] Рассмотрим максимальную ценность при полной загрузке грузом первого типа: \[ \mathcal{F}_1(W, V) = c_1 \cdot \min \left\{ \floor{\frac{W}{w_1}}, \floor{\frac{V}{v_1}} \right\}. \] Таким образом, чтобы решить задачу, надо найти все $\mathcal{F}_k$ для $k = \overline{1, n}$.

    (Задача о добыче золота).

    Дано два прииска $A$ и $B$ с запасами золота $a$ и $b$ соответственно. При установке добывающего устройства на прииск $A$ добыча составит $xa$ в год, где $x \in (0,1)$. Аналогично с прииском $B$ — $yb$ в год, где $y \in (0,1)$.

    Вероятность поломки устройства на прииске $A$ — $p$, а на прииске $B$ — $q$. Если устройство за год не сломалось, то снова решаем, куда его поместить на следующий год.

    Математическое ожидание добычи золота в год

    • на прииске $A$ равняется $(1-p)xa$;
    • на прииске $B$ равняется $(1-q)yb$.

    Введём в рассмотрение функцию Беллмана $F_n(a,b)$, означающую максимальное ожидаемое количество золота, которое может быть добыто за $n$ лет, если начальные запасы приисков равны $a$ и $b$ соответственно.

    Рассмотрим случай $n=1$: максимальное количество добытого за год золота составит \[ \mathcal{F}_1 (a, b) = \max \left[ (1-p)ax, (1-q)by \right]. \]

    Рассмотрим случай произвольного $n$: \[ \mathcal{F}_n(a,b) = \max \left\{ \begin{gathered} (1-p) ax + (1-p) \mathcal{F}_{n-1}(a - ax, b) \\ (1-q) by + (1-q) \mathcal{F}_{n-1}(a, b - by) \\ \end{gathered} \right\} \]

24. Уравнение Беллмана для детерминированного многошагового процесса принятия решений

    Рассмотрим марковский процесс принятия решения:

    • $P$ — множество состояний;
    • $Q$ — множество управлений.

    Для начального состояния $p_0$ выбираем управление $q_0$. Любой паре $(p_0, q_0)$ ставим в соответствие новое состояние $p_1$ при помощи преобразования $T: P \times Q \to P$:

    • $p_1 = T(p_0, q_0)$, выбираем $q_1 \in Q$;
    • $p_2 = T(p_1, q_1)$, выбираем $q_2 \in Q$;
    • $\dots$
    • $p_n = T(p_{n-1}, q_{n-1})$.

    Получаем последовательность состояний $\vec{p} = (p_0, \dots, p_n)$, которую называют траекторией процесса, а также последовательность управлений $\vec q = (q_1, \dots, q_n)$, которую называют программным управлением.

    Предположим, что задана вещественная функция $H(\vec p, \vec q)$, характеризующая выигрыш (доход).

    Так как $p_1, \dots, p_n$ определяются программным управлением, то \[ H(\vec p, \vec q) = K(p_0, \vec q). \] Поставим задачу о максимизации дохода, то есть \[ \max_{\vec q \in Q^n} K(p_0, \vec q). \] Нетрудно видеть, что максимальное значение зависит от начального состояния $p_0$, поэтому можно ввести функцию \[ V(p_0) = \max_{\vec q \in Q^n} K(p_0, \vec q). \] Если функция выигрыша имеет вид \[ K(p_0, \vec q) = \sum_{i=0}^{n-1} f(p_i, q_i) + g(p_n), \] то можно записать функцию Беллмана: \[ \begin{aligned} V_n(p_0) &= \max_{\vec q \in Q^n} K(p_0, \vec q) \\ &= \max_{\vec q \in Q^n} \paren{\sum_{i=0}^{n-1} f(p_i, q_i) + g(p_n)} \\ &= \max_{q_0 \in Q} \left[ f(p_0, q_0) + \underbrace{\max_{q_1 \in Q} \dots \max_{q_{n-1} \in Q} \paren{\sum_{i=0}^{n-1} f(p_i, q_i) + g(p_n)}}_{V_{n-1}(p_1)} \right] \\ &= \max_{q_0 \in Q} \left[ f(p_0, q_0) + V_{n-1}(p_1) \right] \\ &= \max_{q_0 \in Q} \left[ f(p_0, q_0) + V_{n-1}(T(p_0, q_0)) \right]. \end{aligned} \]

    Рекурсивная формула \[ \begin{aligned} V_n(p) &= \max_{q \in Q} \left[ f(p, q) + V_{n-1}(T(p, q)) \right] \\ V_1(p) &= \max_{q \in Q} \left[ f(p, q) + g(T(p, q)) \right] \\ \end{aligned} \] называется уравнением Беллмана для детерминированного многошагового процесса принятия решений.

    Рекурсивно решая уравнение Беллмана, получаем оптимальную траекторию $p^* = (p_0^*, \dots, p_n^*)$ и оптимальное управление $q^* = (q_0^*, \dots, q_{n-1}^*)$.

25. Принцип оптимальности Беллмана. Решение задачи об оптимальном быстродействии
    Принцип оптимальности Беллмана: каковы бы ни были первоначальное состояние и управление, последующие решения должны составлять оптимальное поведение относительно состояния, получающегося в результате первого решения.

    (оптимального быстродействия, дискретная).

    Пусть имеется некоторая конечная сеть $N$ из $m$ узлов, а $(x,y) \in N \times N$ — её ребро. Считаем, что сеть полная, то есть все рёбра возможны.

    Обозначим за $t(x,y) \geqslant 0$ время перехода из узла $x$ в узел $y$, причём $t(x, x) = 0, x \in N$.

    Задача заключается в том, чтобы перейти из начальной вершины $x_0 \in N$ в конечную $M \in N$ наискорейшим способом.

    Рассмотрим произвольную последовательность рёбер \[ \pi = \set{ (x_0, x_1), (x_1, x_2), \dots, (x_k, M)}, \] тогда задача заключается в поиске последовательности, доставляющей минимум функции \[ T(\pi) = \sum_{i=0}^{k} t(x_i, x_{i+1}). \]

    Введём в рассмотрение функцию Беллмана $T(x)$, означающую минимальное время перехода из точки $x$ в $M$.

    Предположим, что первый шаг совершаем произвольно и переходим в точку $x_1$ за время $t(x, x_1)$, а дальнейшую последовательность рёбер строим оптимально. Тогда суммарное время составит $t(x, x_1) + T(x_1)$.

    Функция Беллмана для данной задачи: \[ \begin{aligned} T(x_0) &= \min_{x_1 \in N} \left[ t(x_0, x_1) + T(x_1) \right] \\ T(M) &= 0. \end{aligned} \]

    До сих пор не ясно, как искать $T(x_1)$. Для решения этой проблемы воспользуемся методом последовательных приближений:

    • Пусть $T_0(x) = t(x, M)$ — минимальное время перехода из $x$ в $M$ без промежуточных точек,
    • $T_1(x) = \min\limits_{x_1 \in N} \left[ t(x, x_1) + T_0(x_1) \right]$ — минимальное время перехода из $x$ в $M$ с не более чем одной промежуточной точкой.
    • $\dots$
    • $T_k(x) = \min\limits_{y \in N} \left[t(x, y) + T_{k-1}(y)\right]$ — минимальное время перехода из $x$ в $M$ с не более чем $k$ промежуточными точками.

    Последовательность функций $T_0(x), \dots, T_k(x), \dots$ монотонно невозрастает, так как $t(x, y) \geqslant 0$, поэтому, по теореме Вейерштрасса, данная последовательность сходится за конечное число шагов к своему пределу, то есть \[ \exists n \in \mathbb{N}: \quad T_{n-1}(x) = T_n(x) = T_{n+1}(x) = \dots \]

    Вообще у нас количество узлов конечно ($m$), поэтому можно получить оптимальное решение уже через $m$ итераций.
26. Непрерывные задачи динамического программирования

    Рассмотрим управляемую систему \[ \dv{x^i}{t} = f^i(x^1, \dots, x^n, u^1, \dots, u^r) = f^i(x, u), \quad i = \overline{1,n}, \] или, в векторной форме: \[ \pd{x}{t} = f(x, u). \] Считаем, что:

    • $u \in U \subset \mathbb{R}^r$, причём $U$ — компакт;
    • $f$ дважды непрерывно дифференцируема по всем аргументам.
27. Связь динамического программирования с принципом максимума Л.С.Понтрягина
28. Пример решения задачи оптимального управления с использованием принципа максимума
29. Потоки в сетях. Понятия и свойства
    Рассмотрим сеть $\Gamma = \angset{N, u}$, где

    • $N = \{ x \}$ — конечное множество узлов, $\abs{N} = n$;
    • $u: N \times N \to \mathbb{R}$ — функция пропускной способности сети.

    Говорят, что сеть $\Gamma$ порождает граф \[ \overline \Gamma = \angset{N, G}, \quad \text где \quad G = \set{ (x,y): \; u(x,y) \gt 0}. \]

    Если $u(x,y) = u(y, x) \gt 0$, то $(x,y)$ — неориентированное ребро.

    Функцию \[ f: N \times N \to \mathbb{Z} \] называют потоком в сети $\Gamma$, если она обладает свойствами:

    1. Кососимметричность потока: \[ f(x,y) = -f(y,x) \quad \forall x,y \in N. \] Другими словами, рассматриваем чистые потоки.
    2. Допустимость: \[ f(x,y) \leqslant u(x,y) \quad \forall x,y \in N. \]

    $f(A,B) = \sum\limits_{x \in A} \sum\limits_{y \in B} f(x,y) \quad \forall A,B \subset N$.

    потока в сети $\Gamma$:

    1. Поток из $A$ в $A$ равен нулю (в силу кососимметричности): \[ f(A, A) = \sum_{x \in A} \sum_{y \in A} f(x,y) = 0 \quad \forall A \subset N. \]
    2. Поток из $A$ в $B$ допустим (следует из свойства допустимости — duh): \[ f(A, B) \leqslant u(A,B) \quad \forall A,B \subset N. \]

    Поток, для которого \[ f(x,y) = 0 \quad \forall x,y \in N, \] называется тривиальным.

    Если существует узел $s$ такой, что для любого нетривиального потока \[ f(s, N) \gt 0, \] называется истоком сети $\Gamma$.

    Если существует узел $s'$ такой, что для любого нетривиального потока \[ f(s', N) = -f(N, s') \lt 0, \] называется стоком сети $\Gamma$.

    Будем считать, что в сети существуют единственные исток и сток.

    Узел $x \in N$, не являющийся истоком и стоком, называется промежуточным.

    В силу кососимметричности потока для любого промежуточного узла \[ f(x, N) = 0. \]

    Мощностью потока $f$ называется число $f(s, N)$, то есть сумма потоков, вытекающих из истока.

    Поток $\overline f$ максимальной мощности называют максимальным потоком в сети.

    (прямая). В сети $\Gamma$ найти максимальный поток $\overline f$.
30. Теорема о максимальном потоке и минимальном сечении
    Рассмотрим сеть $\Gamma = \angset{N, u}$.

    Пара множеств $(S, S'), \; S, S' \subset N$ называется сечением сети $\Gamma$, если она обладает свойствами:

    1. $S \cup S' = N, \; S \cap S' = \varnothing$;
    2. $s \in S, \; s' \in S'$

    Пусть $(S, S')$ — некоторое сечение сети, тогда \[ u(S, S') = \sum_{x \in S} \sum_{y \in S'} u(x,y) \] называется пропускной способностью сечения $(S, S')$.

    Сечение $(S, S')$ с минимальной пропускной способностью называется минимальным сечением сети $\Gamma$.

    (двойственная). В сети $\Gamma$ найти сечение $(S, S')$ с минимальной пропускной способностью.

    В любой сети $\Gamma$ с единственными истоком $s$ и стоком $s'$ мощность любого потока не превосходит пропускной способности любого сечения: \[ f(s, N) \leqslant u(S, S') \quad \forall f, \forall (S, S'). \]

    Так как $s \in S$, но $s' \not\in S$, то $S \setminus \{s\}$ — множество, состоящее из промежуточных узлов: \[ \sum_{x \in S \setminus \{s\}} f(x, N) = 0, \] поэтому \[ \begin{aligned} f(s, N) &= f({\color{green}s}, N) + f({\color{green}S \setminus \{s\}}, N) \\ &= f({\color{green}S}, N) \\ &= \cancel{f(S, S)} + f(S, S') \\ &\leqslant u(S, S'). \end{aligned} \]

    Если для какого-то потока $\overline f$ и для какого-то сечения $(\overline S, \overline S')$ справедливо равенство \[ \overline f(s, N) = u(\overline S, \overline S'), \] то $\overline f$ — максимальный поток, а $(\overline S, \overline S')$ — минимальное сечение.

    • По предыдущей лемме известно, что \[ f(s, N) \leqslant u(\overline S, \overline S') \quad \forall f, \] но по условию леммы \[ \overline f(s, N) = u(\overline S, \overline S'), \] поэтому \[ f(s, N) \leqslant \overline f(s, N) \quad \forall f, \] откуда следует, что $\overline f$ — максимальный поток.
    • По предыдущей лемме известно, что \[ \overline f(s, N) \leqslant u(S, S') \quad \forall (S, S'), \] но по условию леммы \[ \overline f(s, N) = u(\overline S, \overline S'), \] поэтому \[ u(\overline S, \overline S') \leqslant u(S, S') \quad \forall (S, S') \] откуда следует, что $(\overline S, \overline S')$ — минимальное сечение.

    (о максимальном потоке и минимальном сечении в сети).

    В любой сети $\Gamma$ существует максимальный поток $\overline f$ и минимальное сечение $(\overline S, \overline S')$m, и при этом \[ \overline f(s, N) = u(\overline S, \overline S'). \]

    Из первой леммы следует, что:

    • $f(s, N)$ ограничена сверху пропускной способностью любого сечения, но у множества пропускных способностей любых сечений существует точное нижнее значение (пропускная способность минимального сечения), откуда, в силу целочисленности задачи, следует, что существует максимальный поток $\overline f$.
    • $u(S, S')$ ограничена снизу мощностью любого потока, но у мощностей любых потоков существует точное верхнее значение, откуда, в силу целочисленности задачи, следует, что существует минимальное сечение.

    Недостаточно обоснованное доказательство: как $\leqslant$ превратился в $=$?

    Эта теорема является аналогом теоремы двойственной.

    Говорят, что ребро $(x, y)$ не насыщенно потоком $f$, если $f(x,y) \lt u(x,y)$.

    Путь $P(s, s')$ — последовательность рёбер вида \[ P(s, s') = \set{ (s, x_1), (x_1, x_2), \dots, (x_n, s') }. \]

    Построим множество $\overline S$ точек $x$, которые можно достичь из $s$ по пути, ненасыщенному относительно потока $\overline f$, и $\overline S' = N \setminus \overline S$.

    Возможны два случая:

    1. $s' \not\in \overline S$ (тогда $(\overline S, \overline S')$ — сечение).
       В этом случае $\overline f(s, N) = u(\overline S, \overline S')$.

       От противного: пусть $\overline f(s,N) \lt u(\overline S, \overline S')$. Из леммы 1 известно, что \[ \overline f(\overline S, \overline S') \lt u(\overline S, \overline S'), \] то есть существует ребро $(x, y)$, где $x \in \overline S, \; y \in \overline S'$, такое, что \[ \overline f(x,y) \lt u(x,y), \] то есть $y$ можно достичь по ненасыщенном пути из $S$ — противоречие.

    2. $s' \in \overline S$, тогда существует ненасыщенный путь $\overline P(s, s')$ относительно потока $\overline f$.

       Рассмотрим \[ \bar \delta = \min_{(x, y) \in \overline P} \left[ u(x,y) - f(x,y) \right] \gt 0. \] Построим функцию $f'(x,y)$ по следующему правилу: \[ f'(x,y) = \begin{cases} \overline f(x,y) + \bar \delta, & (x,y) \in \overline P, \\ \overline f(x,y) - \bar \delta, & (y,x) \in \overline P, \\ \overline f(x,y), & \text{в остальных случаях}. \end{cases} \]

       $f'(x,y)$ — поток.

       • $f'(x,y) \leqslant u(x, y)$;
       • $f'(x,y) = -f(y, x)$.

       Тогда переходим на новую итерацию при $f'(s, N) = \overline f(s,N) + \bar\delta \gt \overline f(s, N)$.

31. Теорема о простых назначениях
    • $I = \set{ I_1, \dots, I_m }$ — конечное множество работников;
    • $J = \set{ J_1, \dots, J_m }$ — конечное множество работ;
    • Матрица возможностей $A = \set{\alpha_{ij}}_{m \times n}$: \[ \alpha_{ij} = \begin{cases} 1, & I_i \to J_j \\ 0, & I_i \not\to J_j \end{cases} \]
      • $\alpha_{ij} = 1$ — работник $i$ может выполнять работу $j$;
      • $\alpha_{ij} = 0$ — работник $i$ не может выполнять работу $j$;
    • Матрица назначений $X = \set{\xi_{ij}}$: \[ \xi_{ij} = \begin{cases} 1, & I_i \to J_j \\ 0, & I_i \not\to J_j \end{cases} \]
      • $\xi_{ij} = 1$ — работник $i$ назначен на работу $j$;
      • $\xi_{ij} = 0$ — работник $i$ не назначен на работу $j$;

    (простая о назначении). Требуется полное назначение:

    • каждый работник назначен ровно на 1 работу;
    • на каждую работу назначено не более одного работника;

    то есть \[ \left\{ \begin{aligned} \sum_{j=1}^n \xi_{ij} &= 1, & & i = \overline{1,m}, \\ \sum_{i=1}^n \xi_{ij} &\leqslant 1, & & j = \overline{1,n}, \\ \xi_{ij} &\geqslant 0 && \xi_{ij} \in \mathbb{Z}. \end{aligned} \right. \]

    (о простых назначениях). Полное назначение $X$ возможно тогда и только тогда, когда \[ \forall S \subset I \quad \abs{S} \leqslant \abs{J(S)}, \] где $J(S)$ — множество работ, которое могут выполнять работники из $S$.
32. Теорема об оптимальных назначениях
33. Задача нелинейного программирования. Возможные направления. Свойства
    Задача нелинейного программирования (ЗНЛП) — задача нахождения наибольшего (наименьшего) значения нелинейной функции многих переменных в случае ограничений типа равенства, неравенства или отсутствия ограничений.

    Стандартная ЗНЛП: \[ \begin{cases} \max f(x) \\ g_i(x) \geqslant 0, \quad i = \overline{1,m}, \end{cases} \] где \[ f: \mathbb{R}^n \to \mathbb{R}, \quad g: \mathbb{R}^n \to \mathbb{R}, \] — непрерывно дифференцируемые функции.

    Множество $F = \set{ x: g_i(x) \geqslant 0, \; i = \overline{1,m}}$ называют множеством допустимых решений.

    Рассмотрим $x \in F$. Тогда $d \in \mathbb{R}^n$ называют возможным направлением в точке $x$, если \[ \exists \delta \gt 0: \quad (x + \tau d) \in F \quad \forall \tau \in [0;\delta]. \] Множество всех возможных направлений в точке $x$ обозначают $D(x)$.

    Если $F = \mathbb{R}^n$, то $D(x) = \mathbb{R}^n, x \in F$.

    Производная по направлению $d$ в точке $x$: \[ \dp{\nabla f(x)}{d} = \lim\limits_{\tau \to +0} \dfrac{f(x + \tau d) - f(x)}{\tau}, \] если $\abs{d} = 1$.

    Если $\dp{\nabla f(x)}{d} \gt 0$, для $x \in F$ и $d \in D(x)$, то \[ \exists \delta \gt 0 \quad f(x + \tau d) \gt f(x) \quad \forall \tau \in (0, \delta), \] причём $x + \tau d \in F$.

    \[ \dp{\nabla f(x)}{d} \gt 0 \implies \lim\limits_{\tau \to +0} \dfrac{f(x + \tau d) - f(x)}{\tau} \gt 0, \] следовательно, \[ \exists \delta' \gt 0 \quad \dfrac{f(x + \tau d) - f(x)}{\tau} \gt 0 \quad g\forall \tau \in (0, \delta'). \] Так как $x \in F$, то \[ \exists \delta'' \gt 0: \quad x + \tau d \in F \quad \tau \in (0, \delta''). \] Тогда для выполнения леммы положим $\delta = \min \set{\delta', \delta''}$.

    (необходимое условие оптимальности). Если $x^* \in F$ — оптимальное решение стандартной ЗНЛП, то \[ \forall d \in D(x^*) \quad \dp{\nabla f(x^*)}{d} \leqslant 0. \]

    Если $D(x^*) = \varnothing$, то доказывать нечего.

    От противного: пусть $x^*$ — оптимальное решение, но \[ \exists d \in D(x^*) \quad \dp{\nabla f(x)}{d} \gt 0. \] Тогда по предыдущей лемме следует, что \[ \exists d \gt 0 \quad f(x^* + \tau d) \gt f(x^*) \] и при этом $x^* + \tau d \in F$ для любого $\tau \in (0, \delta)$, что противоречит предположению о том, что $f(x^*)$ — оптимальное решение.

    Если $F = \mathbb{R}^n$, а $x^* \in F$ — оптимальное решение ЗНЛП, то $\nabla f(x^*) = 0$.

    Если $F = \mathbb{R}^n$, то $D(x^*) = \mathbb{R}^n$, откуда по необходимому условию оптимальности \[ \forall d \in D(x^*) \quad \begin{cases} \dp{\nabla f(x^*)}{d} \leqslant 0 \\ \dp{\nabla f(x^*)}{(-d)} \leqslant 0, \end{cases} \] откуда $\nabla f(x^*) = 0$.

    Если $x^* \in F$ — оптимальное решение, то \[ \forall d \in \overline D(x^*) \quad \dp{\nabla f(x^*)}{d} \leqslant 0. \]

    Рассмотрим сходящуюся последовательность направлений \[ \set{ d^k }_{k=1}^\infty \quad d^k \in D(x^*), \] причём \[ \lim_{k \to \infty} d^k = d \in \overline{D}. \] Так как $x^*$ — оптимальное решение, то \[ \dp{\nabla f(x^*)}{d^k} \leqslant 0 \quad \forall k \in \mathbb{N}, \] откуда из непрерывности следует, что \[ \dp{\nabla f(x^*)}{d} \leqslant 0 \quad \forall d \in \overline D. \]

    Пусть $x \in F$. Говорят, что ограничение $i$ — активное в точке $x$, если \[ g_i(x) = 0. \] Множество активных ограничений в точке $x$ обозначим за $A(x)$.

    Если $x \in F$, то \[ \overline D(x) \subset \widetilde D(x), \] где \[ \widetilde D(x) = \set{d: \nabla g_i(x) d \geqslant 0 \quad i \in A(x)}. \]

    1. Проверим, что $D(x) \subset \widetilde D(x)$.

       От противного: пусть найдётся $d \in \mathbb{R}^n$ такой, что \[ d \in D(x), \quad \text{но} \quad d \not\in \widetilde{D}(x). \] Тогда $\exists i \in A(x)$ такой, что $\nabla g_i(x) d \geqslant 0$, значит, по первой теореме \[ g_i(x + \tau d) \lt \overbrace{g_i(x) = 0}^{\text{т.к. } i \in A(x)} \quad \forall \tau \in (0, \delta). \] Получается, что \[ \begin{cases} g_i(x + \tau d) \lt 0, \\ g_i(x) \geqslant 0, \end{cases} \] то есть, двигаясь по направлению $d$, мы выходим из множества допустимых решений, что противоречит тому, что $d \in D(x)$.

    2. $D(x) \subset \widetilde D(x)$, следовательно, $\overline D(x) \subset \overline{\widetilde{D}}(x) = \widetilde D(x)$, т.к. $\widetilde D(x)$ — замкнутое множество.
       Показать замкнутость множества $\widetilde D(x)$.

    Условие регулярности ЗНЛП: \[ \overline D(x) = \widetilde D(x) \quad \forall x \in F. \]
34. Теорема Куна-Таккера. Достаточность условий оптимальности Куна-Таккера
    Рассмотрим стандартную ЗНЛП: \[ \begin{cases} \max f(x) \\ g_i(x) \geqslant 0, \quad i = \overline{1,m}, \end{cases} \] где \[ f: \mathbb{R}^n \to \mathbb{R}, \quad g: \mathbb{R}^n \to \mathbb{R}, \] — непрерывно дифференцируемые функции.

    Пусть выполнено условие регулярности: \[ \overline D(x) = \widetilde D(x) \quad \forall x \in F. \]

    (Фаркаша).

    Система \[ \begin{cases} qx \leqslant 0, \\ Ax \geqslant 0, \end{cases} \qquad q \in \mathbb{R}^n, \; A \in \mathbb{R}^{m \times n} \] разрешима тогда и только тогда, когда \[ \exists \vec l \in \mathbb{R}^m \geqslant 0: \quad q + lA = 0. \]

    Система разрешима $\iff$ ЗЛП \[ \begin{cases} \max (qx) = 0 \\ -Ax \leqslant 0 \end{cases} \] имеет решение $\iff$ двойственная задача \[ \left\{ \begin{aligned} \min l &\cdot 0 \\ -l A &= q \\ l &\geqslant 0. \end{aligned} \right. \] имеет оптимальное решение, то есть \[ \exists \vec l \in \mathbb{R}^m \geqslant 0: \quad q + lA = 0. \]

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

    Если $x^*$ — оптимальное решение, то существует вектор $l = (\lambda_1, \dots, \lambda_m) \geqslant 0$ такой, что выполнены условия Куна-Таккера:

    1. условие допустимости: \[ g_i(x^*) \geqslant 0 \quad i = \overline{1,m}; \]
    2. условие оптимальности: \[ \nabla f(x^*) + \sum_{i=1}^m \lambda_i \nabla g_i(x^*) = 0; \]
    3. условие трансверсальности: \[ \lambda_i g_i(x^*) = 0 \quad i = \overline{1,m}. \]

    Пусть $x^*$ — оптимальное решение.

    1. $x^*$ удовлетворяет условию 1, т.к. он должен быть допустимым;
    2. Для оптимального решения справедливо \[ \dp{\nabla f(x^*)}{d} \leqslant 0 \quad \forall d \in \overline D(x^*) = \widetilde D(x), \] поэтому \[ \begin{cases} \dp{\nabla f(x^*)}{d} \leqslant 0 \\ \dp{\nabla g_i(x^*)}{d} \geqslant 0, & i \in A(x^*). \end{cases} \] Тогда по теореме Фаркаша \[ \exists \lambda_i \geqslant 0: \quad \nabla f(x^*) + \sum_{i \in A(x^*)} \lambda_i \nabla g_i(x^*) = 0. \]
    Дальше что-то странное, надо разобраться.
    3. Пусть выполнено \[ \lambda_i g_i (x^*) = 0, \quad i = \overline{1,m}. \] Тогда, в частности, справедливо \[ i \not\in A(x^*) \implies g_i(x^*) \gt 0 \implies \lambda_i = 0, \] поэтому, предполагая, что 3 условие выполнено, 2 условие можно переписать в виде \[ \nabla f(x^*) + \sum_{i=1}^m \lambda_i \nabla g_i(x^*) = 0. \]

    Говорят, что функция $f$ выпукла вверх (вогнута), если \[ \forall x_1, x_2 \in F \quad \forall \lambda \in [0;1]: \quad f(\lambda x_1 + (1 - \lambda) x_2) \geqslant \lambda f(x_1) + (1 - \lambda) f(x_2). \]

    Говорят, что функция $f$ выпукла вниз (выгнута), если $-f(x)$ — вогнута.

    (достаточное условие Куна-Таккера).

    Если $x^*$ удовлетворяет необходимым условиям Куна-Таккера, а $f_i$ и $g_i$ — вогнутые на $F$, то $x^*$ — оптимальное решение ЗНЛП.

    1. Рассмотрим множество \[ F_i = \set{x: \quad g_i(x) \geqslant 0}. \] Выберем произвольные $x_1, x_2 \in F_i$. Так как $g_i$ — вогнута, то \[ \forall \lambda \in [0;1] \quad g_i(\lambda x_1 + (1 - \lambda) x_2) \geqslant \lambda g_i(x_1) + (1 - \lambda) g(x_2) \geqslant 0, \] то есть \[ g_i(\lambda x_1 + (1 - \lambda) x_2) \geqslant 0, \] откуда следует, что $\lambda x_1 + (1 - \lambda) x_2 \in F_i$, то есть $F_i$ — выпуклое множество.

       Таким образом, \[ F = \bigcap_{i=1}^m F_i \] также является выпуклым как пересечение выпуклых множеств.

    2. Пусть $x^*$ удовлетворяет необходимым условиям Куна-Таккера, тогда $x^* \in F$.

       Рассмотрим $x \in F$, тогда $d = x - x^* \in D(x^*)$ из-за выпуклости $F$. По условию $f$ вогнута, поэтому \[ \begin{aligned} f(\lambda x + (1 - \lambda) x^*) &\geqslant \lambda f(x) + (1 - \lambda) f(x^*) \\ f(x^* + \lambda (x - x^*)) &\geqslant f(x^*) + \lambda (f(x) - f(x^*)) \\ f(x^* + \lambda d) &\geqslant f(x^*) + \lambda (f(x) - f(x^*)) & \vert :\lambda \in (0; 1] \\ \frac{f(x^* + \lambda d) - f(x^*)}{\lambda} &\geqslant f(x) - f(x^*). \end{aligned} \] Устремим $\lambda \to +0$, получим \[ \nabla f(x^* + \lambda d) \geqslant f(x) - f(x^*). \] Из 2-го необходимого условия Куна-Таккера следует, что \[ 0 \geqslant - \sum_{i=1}^m \lambda_i \nabla g_i(x^*) \geqslant f(x) - f(x^*), \] значит, $f(x) \leqslant f(x^*)$, то есть $x^*$ — оптимальное решение.