\documentclass[12pt,draft,a4paper]{amsart}
\usepackage{amsmath,amsthm,array}
\usepackage[T2A]{fontenc}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsfonts}
\usepackage{latexsym}
%\usepackage[final]{hyperref}


\tolerance 4200

\renewcommand*{\proofname}{Доказательство}
\newcommand*{\ld}{L_2(\mathbb R^d)}
\newcommand*{\Rd}{\mathbb R^d}
\newcommand*{\RR}{\mathbb R}
\newcommand*{\lf}{L_2^{\varphi}(\mathbb R^d)}
\newcommand*{\cd}{(\cdot)}
\newcommand*{\Ds}{\Delta_\sigma}
\newcommand*{\lT}{L_2([0,2\pi])}
\newcommand*{\wa}{\widehat\alpha}
\newcommand*{\wb}{\widetilde b}
\newcommand*{\wix}{\widetilde x}
\newcommand*{\wiy}{\widetilde y}
\newcommand*{\wal}{\widetilde\alpha}
\newcommand*{\ws}{\widehat\sigma}
\newcommand*{\wxi}{\widehat\xi}
\newcommand*{\wm}{\widehat m}
\newcommand*{\wx}{\widehat x}
\newcommand*{\wz}{\widehat z}
\newcommand*{\wu}{\widehat u}
\newcommand*{\wL}{\widehat L}
\newcommand*{\wJ}{\widehat J}
\newcommand*{\wh}{\widehat h}
%\newcommand*{\co}{\rm co}
\newcommand*{\cone}{\rm cone}
\newcommand*{\wy}{\widehat y}
\newcommand*{\wl}{\widehat l}
\newcommand*{\ov}{\overline}
\newcommand*{\wt}{\widehat\tau}
\newcommand*{\wv}{\widehat\varphi}
\newcommand*{\wM}{\widehat M}
\newcommand*{\Wt}{W_2^2([0,2\pi])}
\newcommand*{\wf}{\widehat f}
%\newcommand*{\intt}{\rm int}
%\newcommand*{\cl}{\rm cl}
%\newcommand*{\spa}{\rm span}
\newcommand*{\la}{\langle}
\newcommand*{\ra}{\rangle}
\newcommand*{\LL}{\mathcal L}
\newcommand*{\sjn}{\sum_{j=1}^n}
\renewcommand{\labelenumi}{\theenumi.}


{\theoremstyle{remark}\newtheorem{example}{\bf Пример}[section]}

\newtheorem{lemma}{Лемма}
\newtheorem{theorem}{Теорема}
\newtheorem{corollary}{Следствие}
\newtheorem{proposition}{Предложение}

\DeclareMathOperator*{\extr}{extr}
\DeclareMathOperator*{\infp}{inf\vphantom p}
\DeclareMathOperator*{\intt}{int}
\DeclareMathOperator*{\cl}{cl}
\DeclareMathOperator*{\spa}{span}
\DeclareMathOperator*{\co}{co}
\DeclareMathOperator*{\dom}{dom}
\DeclareMathOperator*{\epi}{epi}
\DeclareMathOperator*{\IM}{Im}
\DeclareMathOperator*{\Ker}{Ker}
\DeclareMathOperator*{\const}{const}
\DeclareMathOperator*{\aff}{aff}
\DeclareMathOperator*{\sign}{sign}
\DeclareMathOperator*{\con}{cone}
\DeclareMathOperator*{\lin}{lin}
\DeclareMathOperator*{\rg}{rg}

\begin{document}


\begin{center}\large
МИНОБРНАУКИ РОССИИ\\
\vspace{15pt} \large
Федеральное государственное бюджетное образовательное учреждение высшего образования\\[3pt]
\bf ``МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ\\[3pt]
(национальный исследовательский университет)'' (МАИ)\\[28pt]
\large
Кафедра ``Высшая математика''\\[60pt]

\bf К.~Ю.~Осипенко\\[50pt]

\bf\Large ВЫПУКЛЫЙ АНАЛИЗ\\[225pt]


Москва 2016

\thispagestyle{empty}

\end{center}

\newpage

\tableofcontents

\newpage

\section{Введение}

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

\section{Выпуклые множества}

Пусть $X$ --- линейное пространство. Если $x,y\in X$, то множество
$$[x,y]=\{\,z\in X:z=(1-\alpha)x+\alpha y,\ 0\le\alpha\le1\,\}$$
называется отрезком (соединяющим точки $x$ и $y$).

Непустое множество $A$ называется выпуклым, если для любых $x,y\in A$ \ $[x,y]\in A$. Пустое множество считается выпуклым по определению.

Пусть $x_1,\ldots,x_n\in X$. Точка
\begin{equation}\label{xx}
x=\sjn\alpha_jx_j,\quad\alpha_j\ge0,\quad\sjn\alpha_j=1,
\end{equation}
называется выпуклой комбинацией точек $x_1,\ldots,x_n$.

\begin{proposition}\label{P1}
Если $A$ --- выпуклое множество, то любая выпуклая комбинация точек $x_1,\ldots,x_n\in A$ принадлежит $A$.
\end{proposition}

\begin{proof}
Доказательство проведем индукцией по числу точек. При $n=1$ утверждение очевидно. Предположим, что утверждение верно для любой выпуклой комбинации из не более, чем $n-1$ точек. Пусть имеется точка $x$ вида \eqref{xx}. Если $\alpha_1=1$, то $x=x_1\in A$. Если $\alpha_1<1$, положим
$$\wal_j=\frac{\alpha_j}{1-\alpha_1},\quad j=2,\ldots,n.$$
В силу того, что
$$\sum_{j=2}^n\wal_j=1,$$
из предположения индукции вытекает, что
$$\wix=\sum_{j=2}^n\wal_jx_j\in A.$$
Тогда из выпуклости $A$ следует, что
$$x=\sjn\alpha_jx_j=\alpha_1x_1+(1-\alpha_1)\sum_{j=2}^n
\frac{\alpha_j}{1-\alpha_1}x_j=\alpha_1x_1+(1-\alpha_1)\wix\in A.$$
\end{proof}

Выпуклой оболочкой $\co A$ множества $A\subset X$ называется множество всех выпуклых комбинаций его точек
\begin{multline*}
\co A=\biggl\{\,x\in X:x=\sjn\alpha_jx_j:x_1,\ldots,x_n\in A,\ \alpha_j\ge0,\\
\sjn\alpha_j=1,\ n\in\mathbb N\,\biggr\}.
\end{multline*}

Среди всех выпуклых множеств, содержащих данное множество $A\subset X$, существует наименьшее, т.е. то, которое содержится в любом выпуклом множестве, содержащем $A$. Действительно, семейство всех выпуклых множеств, содержащих $A$, не пусто (в него входит, например, все пространство $X$). Пересечение всех множеств этого семейства будет выпуклым (т.к. пересечение любого семейства выпуклых множеств --- выпукло), содержащим $A$ и наименьшим. Докажем, что это множество совпадает с $\co A$.

\begin{proposition}
Множество $\co A$ является наименьшим выпуклым множеством, содержащим $A$.
\end{proposition}

\begin{proof}
Из предложения~\ref{P1} вытекает, что если некоторое выпуклое множество содержит $A$, то оно содержит любую выпуклую комбинацию точек из $A$, а значит, оно содержит $\co A$. Следовательно, пересечение всех выпуклых множеств содержит $\co A$. Осталось показать что $\co A$ выпукло, в этом случае оно совпадет с пересечением всех выпуклых множеств, содержащих $A$. Рассмотрим две произвольные точки $\co A$
$$x=\sjn\alpha_jx_j,\quad\sum_{j=1}^m\beta_jy_j.$$
Для любого $\alpha\in[0,1]$ имеем
$$(1-\alpha)x+\alpha y=\sjn(1-\alpha)\alpha_jx_j+\sum_{j=1}^m\alpha\beta_jy_j.$$
Так как
$$\sjn(1-\alpha)\alpha_j+\sum_{j=1}^m\alpha\beta_j=(1-\alpha)+\alpha=1,$$
то мы получили выпуклую комбинацию точек $x_1,\ldots,x_n,y_1,\ldots,y_m$, которая принадлежит $\co A$.
\end{proof}

\begin{corollary}
Множество $A$ является выпуклым в том и только в том случае, если $A=\co A$.
\end{corollary}

\begin{proposition}\label{P3}
Если $A$ и $B$ --- выпуклые множества, то
$$\co(A\cup B)=\{\,x\in X:x=(1-\alpha)a+\alpha b:a\in A,\ b\in B,\ \alpha\in[0,1]\,\}.$$
\end{proposition}

\begin{proof}
Из определения выпуклой оболочки вытекает, что $(1-\alpha)a+\alpha b\in\co(A\cup B)$ для всех $a\in A$, $b\in B$ и $\alpha\in[0,1]$. Пусть $x\in\co(A\cup B)$. Тогда
$$x=\sjn\alpha_jx_j+\sum_{j=1}^m\beta_jy_j,$$
где $x_1,\ldots,x_n\in A$, $y_1,\ldots,y_m\in B$, $\alpha_1,\ldots,\alpha_n\ge0$, $\beta_1,\ldots,\beta_m\ge0$ и
$$\sjn\alpha_j+\sum_{j=1}^m\beta_j=1.$$
Положим
$$\alpha=\sum_{j=1}^m\beta_j.$$
Предположим, что $0<\alpha<1$. Тогда $x=(1-\alpha)a+\alpha b$, где
$$a=\sjn\frac{\alpha_j}{1-\alpha}x_j,\quad b=\sum_{j=1}^m\frac{\beta_j}\alpha y_j.$$
В силу того, что
$$\sjn\frac{\alpha_j}{1-\alpha}=\sum_{j=1}^m\frac{\beta_j}\alpha=1,$$
$a\in A$, а $b\in B$. При $\alpha=1$ или $\alpha=0$ можно непосредственно убедиться, что справедливо то же представление.
\end{proof}

Подмножество $Y\subset X$ называется аффинным подпространством $X$, если для любых $x,y\in Y$ точка $(1-\alpha)x+\alpha y\in Y$ при всех $\alpha\in\mathbb R$.


Аффинной комбинацией точек $x_1,\ldots,x_n$ называется точка
\begin{equation}\label{xx1}
x=\sjn\alpha_jx_j,\quad\sjn\alpha_j=1,\quad\alpha_1,\ldots,\alpha_n
\in\mathbb R.
\end{equation}

\begin{proposition}\label{PA}
Если $Y$ --- аффинное подпространство, то любая аффинная комбинация точек $x_1,\ldots,x_n\in Y$ принадлежит $Y$.
\end{proposition}

\begin{proof}
Доказательство проведем индукцией по числу точек. При $n=1$ утверждение очевидно. Предположим, что утверждение верно для любой выпуклой комбинации из не более, чем $n-1$ точек. Пусть имеется точка $x$ вида \eqref{xx1} и $n>1$. Среди $\alpha_1,\ldots,\alpha_n$ найдется отличное от единицы. Без ограничения общности можно считать, что $\alpha_1\ne1$. Положим
$$\wal_j=\frac{\alpha_j}{1-\alpha_1},\quad j=2,\ldots,n.$$
В силу того, что
$$\sum_{j=2}^n\wal_j=1,$$
из предположения индукции вытекает, что
$$\wix=\sum_{j=2}^n\wal_jx_j\in Y.$$
Тогда из того, что $Y$ аффинное подпространство следует, что
$$x=\sjn\alpha_jx_j=\alpha_1x_1+(1-\alpha_1)\wix\in Y.$$
\end{proof}

Множество всех аффинных комбинаций точек из множества $A$ называется аффинной оболочкой $\aff A$ множества $A$
$$\aff A=\biggl\{\,x\in X:x=\sjn\alpha_jx_j:x_1,\ldots,x_n\in A,\
\sjn\alpha_j=1,\ n\in\mathbb N\,\biggr\}.$$

Среди всех аффинных подпространств, содержащих данное множество $A\subset X$, существует наименьшее, т.е. то, которое содержится в любом аффинном подпространстве, содержащем $A$. Действительно, семейство всех аффинных подпространств, содержащих $A$, не пусто (в него входит, например, все пространство $X$). Пересечение всех множеств этого семейства будет аффинным подпространством (т.к. пересечение любого семейства аффинных подпространств --- аффинное подпространство), содержащим $A$ и наименьшим. Докажем, что это множество совпадает с $\aff A$.

\begin{proposition}
Множество $\aff A$ является наименьшим аффинным подпространством, содержащим $A$.
\end{proposition}

\begin{proof}
Из предложения~\ref{PA} вытекает, что если некоторое аффинное подпространство содержит $A$, то оно содержит любую аффинную комбинацию точек из $A$, а значит, оно содержит $\aff A$. Следовательно, пересечение всех аффинных подпространств содержит $\aff A$. Осталось показать что $\aff A$ является аффинным подпространством, в этом случае оно совпадет с пересечением всех аффинных подпространств, содержащих $A$. Рассмотрим две произвольные точки $\aff A$
$$x=\sjn\alpha_jx_j,\quad\sum_{j=1}^m\beta_jy_j.$$
Для любого $\alpha\in\mathbb R$ имеем
$$(1-\alpha)x+\alpha y=\sjn(1-\alpha)\alpha_jx_j+\sum_{j=1}^m\alpha\beta_jy_j.$$
Так как
$$\sjn(1-\alpha)\alpha_j+\sum_{j=1}^m\alpha\beta_j=(1-\alpha)+\alpha=1,$$
то мы получили аффинную комбинацию точек $x_1,\ldots,x_n,y_1,\ldots,y_m$, которая принадлежит $\aff A$.
\end{proof}

\begin{corollary}
Множество $A$ является аффинным подпространством в том и только в том случае, если $A=\aff A$.
\end{corollary}

\begin{proposition}\label{P5}
Каждое аффинное подпространство $Y\subset X$ представляется в виде $Y=a+L_Y$, где $a$ --- произвольная точка из $Y$, а $L_Y$ --- линейное подпространство из $X$, причем $L_Y$ определено однозначно (не зависит от $a$).
\end{proposition}

\begin{proof}
Пусть $a\in Y$. Положим
$$L_Y=\{\,x\in X:x=y-a,\quad y\in Y\,\}.$$
Докажем, что $L_Y$ --- линейное подпространство $X$. Пусть $x\in L_Y$. Тогда $x=y-a$, где $y\in Y$. Для любого $\lambda\in\mathbb R$ в силу того, что $\lambda y+(1-\lambda)a\in Y$, имеем
$$\lambda x=\lambda(y-a)=\lambda y+(1-\lambda)a-a\in L_Y.$$

Пусть теперь $x_1,x_2\in L_Y$ и $x_1=y_1-a$, а $x_2=y_2-a$, где $y_1,y_2\in Y$. Так как $(y_1+y_2)/2\in Y$, то
$$\frac{x_1+x_2}2=\frac{y_1+y_2}2-a\in L_Y.$$
Из доказанного выше, положив $\lambda=2$, получаем, что $x_1+x_2\in L_Y$.

Положим
$$M_Y=\{\,x\in X:x=y-b,\quad y\in Y\,\},$$
где $b\in Y$. В силу того, что $b-a\in L_Y$, имеем
$$b+L_Y=a+(b-a)+L_Y=a+L_Y=Y.$$
Следовательно, $M_Y=L_Y$.
\end{proof}

Размерностью аффинного подпространства $Y$ называется размерность соответствующего линейного подпространства $L_Y$:
$$\dim Y=\dim L_Y.$$

Размерностью произвольного множества $A$ называется размерность его аффинной оболочки $\aff A$:
$$\dim A=\dim\aff A.$$
Поскольку $\co A\subset\aff A$, то
$$\dim A=\dim\co A=\dim\aff A.$$

\section{Теорема Каратеодори}

\begin{theorem}[Каратеодори]
Если $\dim\co A=d$, то любой элемент множества $\co A$ представляется в виде выпуклой комбинации не более, чем $d+1$ элемента множества $A$.
\end{theorem}

\begin{proof}
Положим $Y=\aff A$. Тогда $\dim Y=d$. Пусть
$$x=\sjn\alpha_jx_j,\quad\alpha_j\ge0,\quad\sjn\alpha_j=1,\quad n\ge d+2.$$
Тогда элементы $x_2-x_1,\ldots,x_n-x_1$ принадлежат линейному пространству $L_Y$ (см. предложение~\ref{P5}), размерность которого $d$. Следовательно, они линейно зависимы. Тем самым существуют $\beta_2,\ldots,\beta_n$, не все равные нулю, для которых
$$\sum_{j=2}^n\beta_j(x_j-x_1)=0.$$
Положим
$$\gamma_1=-\sum_{j=2}^n\beta_j,\quad\gamma_j=\beta_j,\quad j=2,\ldots,n.$$
Тогда
$$\sjn\gamma_jx_j=0,\quad\sjn\gamma_j=0,$$
причем $\gamma_1,\ldots,\gamma_n$ не все равны нулю. Следовательно, среди чисел $\gamma_1,\ldots,\gamma_n$ существуют отрицательные числа. Пусть
$$a=\min\left\{\,-\frac{\alpha_j}{\gamma_j}:\gamma_j<0\,\right\}=
-\frac{\alpha_k}{\gamma_k}.$$
Тогда $\alpha_j+a\gamma_j\ge0$ для всех $j=1,\ldots,n$. Кроме того,
$$x=\sjn(\alpha_j+a\gamma_j)x_j,\quad\sjn(\alpha_j+a\gamma_j)=1.$$
Так как $\alpha_k+a\gamma_k=0$, то $x$ представляется в виде выпуклой комбинации из $n-1$ точки. Если $n-1>d+1$, то продолжая этот процесс придем к тому, что $x$ представляется в виде выпуклой комбинации не более, чем $d+1$ элемента множества $A$.
\end{proof}

Пусть $X$ --- линейное нормированное пространство.

\begin{theorem}
Выпуклая оболочка компакта в конечномерном
пространстве $X$ является компактом.
\end{theorem}

\begin{proof}
Пусть $\dim X=d$, $A\subset X$ --- компакт. Докажем, что $\co A$ --- компакт. Для этого достаточно доказать, что из любой последовательности $\{x_k\}\subset\co A$ можно выбрать подпоследовательность, сходящуюся к некоторой точке из $\co A$. По теореме Каратеодори
$$x_k=\sum_{j=1}^{d+1}\alpha_{kj}x_{kj},\quad x_{kj}\in A,\quad\alpha_{kj}\ge0,\quad\sum_{j=1}^{d+1}\alpha_{kj}=1.$$
Так как $A$ --- компакт, то в последовательности $\{x_{k1}\}$ существует подпоследовательность, сходящаяся к некоторой точке $y_1\in A$, а в этой подпоследовательности в $\{\alpha_{k1}\}$ существует подпоследовательность, сходящаяся к некоторому числу $\alpha_1\in[0,1]$. Не ограничивая общности, можно считать, что $x_{k1}\to y_1$ и $\alpha_{k1}\to\alpha_1$ при $k\to\infty$. Аналогично, переходя к подпоследовательностям, можно считать, что $x_{kj}\to y_j$ и $\alpha_{kj}\to\alpha_j$ при $k\to\infty$ для любого $j=2,\ldots,d+1$. При этом
$$x_k\to\sum_{j=1}^{d+1}\alpha_jy_j,\quad\alpha_j\ge0,\quad
\sum_{j=1}^{d+1}\alpha_j=1.$$
Это означает, что предельная точка принадлежит $\co A$.
\end{proof}

Конической комбинацией точек $x_1,\ldots,x_n$ называется точка
$$x=\sjn\alpha_jx_j,\quad\alpha_1,\ldots,\alpha_n\ge0.$$
Множество всех конических комбинаций точек из множества $A$ называется конической оболочкой $\con A$ множества $A$
$$\con A=\biggl\{\,x\in X:x=\sjn\alpha_jx_j:x_1,\ldots,x_n\in A,\ \alpha_j\ge0,\ n\in\mathbb N\,\biggr\}.$$

Напомним, что линейной оболочкой множества $A$ называется множество всех линейных комбинаций элементов из множества $A$:
$$\lin A=\biggl\{\,x\in X:x=\sjn\alpha_jx_j:x_1,\ldots,x_n\in A,\ \alpha_j\in\mathbb R,\ n\in\mathbb N\,\biggr\}.$$

\begin{theorem}[Каратеодори для конической оболочки]\label{Kcone}
Если $\dim\lin A=d$, то любой элемент множества $\con A$ представляется в виде конической комбинации не более, чем $d$ линейно независимых элементов множества $A$.
\end{theorem}

\begin{proof}
Пусть
$$x=\sjn\alpha_jx_j,\quad\alpha_1,\ldots,\alpha_n\ge0.$$
Если $x_1,\ldots,x_n$ линейно независимы, то $n\le d$ и все доказано.
Если элементы $x_1,\ldots,x_n$ линейно зависимы, то найдутся не все равные нулю $\gamma_1,\ldots,\gamma_n$ такие, что
$$\sjn\gamma_jx_j=0.$$
Без ограничения общности можно считать, что среди $\gamma_1,\ldots,\gamma_n$ есть отрицательные числа (если они все положительные, то можно рассматривать $-\gamma_1,\ldots,-\gamma_n$). Пусть
$$a=\min\left\{\,-\frac{\alpha_j}{\gamma_j}:\gamma_j<0\,\right\}=
-\frac{\alpha_k}{\gamma_k}.$$
Тогда $\alpha_j+a\gamma_j\ge0$ для всех $j=1,\ldots,n$ и
$$x=\sjn(\alpha_j+a\gamma_j)x_j.$$
Так как $\alpha_k+a\gamma_k=0$, то $x$ представляется в виде конической комбинации из $n-1$ точки. Если эти элементы линейно зависимы, то продолжая этот процесс придем к тому, что $x$ представляется в виде конической комбинации не более, чем $d$ линейно независимых элементов множества $A$.
\end{proof}

\section{Теоремы Радона и Хелли}

\begin{theorem}[Радона]
Пусть $X$ --- линейное пространство и $\dim X=d$. Тогда любое конечное множество из $X$, содержащее не менее $d+2$ точек, может быть разбито на два непересекающихся множества, выпуклые оболочки которых пересекаются.
\end{theorem}

\begin{proof}
Пусть даны точки $x_1,\ldots,x_n$, $n\ge d+2$. Векторы $x_2-x_1,\ldots,x_n-x_1$ --- линейно зависимы, т.к. их не менее $d+1$. Следовательно, существуют $\alpha_2,\ldots,\alpha_n$, не все равные нулю, такие, что
$$\sum_{j=2}^n\alpha_j(x_j-x_1)=0.$$
Положим
$$\beta_1=-\sum_{j=2}^n\alpha_j,\quad\beta_j=\alpha_j,\quad j=2,\ldots,n.$$
Имеем
$$\sjn\beta_jx_j=0,\quad\sjn\beta_j=0,$$
причем $\beta_1,\ldots,\beta_n$ не все равны нулю. Поменяем нумерацию и будем считать, что $\beta_1,\ldots,\beta_m\ge0$, а $\beta_{m+1},\ldots,\beta_n<0$. Положим
$$\beta=\sum_{j=1}^m\beta_j=-\sum_{j=m+1}^n\beta_j,\quad A=\{x_1,\ldots,x_m\},\quad
B=\{x_{m+1},\ldots,x_n\}.$$
Тогда
\begin{equation}\label{vk}
\sum_{j=1}^m\gamma_jx_j=\sum_{j=m+1}^n\gamma_jx_j,
\end{equation}
где $\gamma_j=\beta_j/\beta$, $j=1,\ldots,m$, и $\gamma_j=-\beta_j/\beta$, $j=m+1,\ldots,n$. Причем
$$\sum_{j=1}^m\gamma_j=\sum_{j=m+1}^n\gamma_j=1.$$
Таким образом, выпуклая комбинация в левой части равенства \eqref{vk} лежит в $\co A$, а выпуклая комбинация в правой части равенства \eqref{vk} лежит в $\co B$. Тем самым $\co A\cap\co B\ne\emptyset$.
\end{proof}

\begin{theorem}[Хелли]
\

$1$. Если $\dim X=d$ и в $X$ имеются $n\ge d+1$ выпуклых множеств, любые $d+1$ из которых имеют общую точку, то и все эти множества имеют общую точку.

$2$. Пусть $X$ --- линейное нормированное пространство, $\dim X=d$, $\mathcal I$ --- некоторое бесконечное множество индексов и $\{A_\alpha\}_{\alpha\in\mathcal I}$ --- семейство замкнутых выпуклых подмножеств $X$, по крайней мере одно из которых компактно. Тогда если любое подсемейство из $d+1$ множеств имеет общую точку, то и все семейство имеет общую точку.
\end{theorem}

\begin{proof}
1. Будем доказывать утверждение индукцией по числу множеств $n$. При $n=d+1$ утверждение очевидно. Пусть $n\ge d+2$ и теорема доказана для любых $n-1$ выпуклых множеств. Обозначим данные множества через $A_j$, $j=1,\ldots,n$. Для каждого $k=1,\ldots,n$ возьмем произвольную точку
$$x_k\in\bigcap_{\substack{j=1\\j\ne k}}^nA_j$$
(по предположению индукции эти пересечения не пусты). Так как $n\ge d+2$, то к точкам $x_1,\ldots,x_n$ применима теорема Радона. С возможной перенумерацией точек  получаем, что существует натуральное число $m\le n-1$, для которого множества $\co\{x_1,\ldots,x_m\}$ и $\co\{x_{m+1},\ldots,x_n\}$ имеют общую точку $x$. Точка $x_j$ при всех $j=1,\ldots,m$ принадлежит каждому из множеств $A_{m+1},\ldots,A_n$. В силу выпуклости этих множеств каждое из них содержит $\co\{x_1,\ldots,x_m\}$. Следовательно, каждое из этих множеств содержит точку $x$. Аналогично доказывается, что каждое из множеств $A_1,\ldots,A_m$ содержит точку $x$. Тем самым доказано, что у всех множеств $A_1,\ldots,A_n$ имеется общая точка.

2. Пусть $A_{\alpha_0}$ --- компактное множество. Из 1 следует, что любое конечное семейство из множества замкнутых подмножеств $B_\alpha=A_\alpha\cap A_{\alpha_0}$, $\alpha\in\mathcal I$, содержащихся в $A_{\alpha_0}$ имеет общую точку. Предположим, что все семейство не имеет общей точки. Тогда множества $\{X\setminus B_\alpha\}_{\alpha\in\mathcal I}$ --- открытые и образуют покрытие компактного множества $A_{\alpha_0}$. В силу компактности из этого покрытия можно выбрать конечное покрытие $\{X\setminus B_\alpha\}_{\alpha\in\mathcal I_n}$. Но тогда конечное семейство $\{B_\alpha\}_{\alpha\in\mathcal I_n}$ не может иметь общей точки. Полученное противоречие доказывает утверждение 2.
\end{proof}

\section{Выпуклые функции. Теорема Каруша--Куна--Таккера}

Мы будем рассматривать функции, которые принимают не только конечные значения. С этой целью вводится понятие расширенной прямой $\ov{\mathbb R}=\mathbb R\cup\{-\infty\}\cup\{+\infty\}$. Арифметические операции и неравенства для элементов расширенной прямой понимаются следующим образом: $-\infty<a<+\infty$, $a\in\mathbb R$, $a+(\pm\infty)=\pm\infty$ для всех $a\in\mathbb R$, $$a(\pm\infty)=\begin{cases}\pm\infty,&a>0,\\
0,&a=0,\\
\mp\infty,&a<0,\end{cases},$$
$+\infty+(+\infty)=+\infty$, $-\infty+(-\infty)=-\infty$.

Пусть $X$ --- линейное пространство и $f\colon X\to\ov{\mathbb R}$. Множества
\begin{gather*}
\dom f=\{\,x\in X:f(x)<+\infty\,\},\\
\epi f=\{\,(x,\alpha)\in X\times\mathbb R:\alpha\ge f(x),\ x\in\dom f\,\}
\end{gather*}
называются соответственно эффективным множеством и надграфиком (или эпиграфом) функции $f$. Функцию $f$ называют собственной, если $\dom f\ne\emptyset$ и $f(x)>-\infty$ при всех $x\in X$.

Функция $f\colon X\to\ov{\mathbb R}$ называется выпуклой, если ее надграфик выпуклое множество в $X\times\mathbb R$. Нетрудно проверить, что функция $f$ выпукла тогда и только тогда, когда для любых
$x_1,x_2\in\dom f$ и любого $0\le\alpha\le1$ выполняется неравенство
$$f((1-\alpha)x_1+\alpha x_2)\le (1-\alpha)f(x_1)+\alpha f(x_2),$$
которое называется неравенством Йенссена.

\begin{theorem}
Пусть $X$ --- линейное нормированное пространство и $f\colon X\to\mathbb R$ --- дважды дифференцируема на $X$. Тогда $f$ --- выпуклая функция тогда и только тогда, когда $f''(x)[h,h]\ge0$ для всех $x\in X$ и всех $h\in X$.
\end{theorem}

Доказательство этой теоремы приводилось в \cite[Теорема 18, стр. 31]{Os}.

Пусть $X=\Rd$ и $f\colon\Rd\to\mathbb R$. Если $f$ --- дважды дифференцируема, то $f''(x)$ --- гессиан $f$ в точке $x$
$$f''(x)=\begin{pmatrix}
\dfrac{\partial^2f}{\partial x_1^2}(x)&\dfrac{\partial^2f}{\partial x_1\partial x_2}(x)&\ldots&\dfrac{\partial^2f}{\partial x_1\partial x_d}(x)\\[10pt]
\dfrac{\partial^2f}{\partial x_2\partial x_1}(x)&\dfrac{\partial^2 f}{\partial x_2^2}(x)&\ldots&\dfrac{\partial^2f}{\partial x_2\partial x_d}(x)\\
\hdotsfor{4}\\
\dfrac{\partial^2f}{\partial x_d\partial x_1}(x)&\dfrac{\partial^2 f}{\partial x_d\partial x_2}(x)&\ldots&\dfrac{\partial^2f}{\partial x_d^2}(x)\end{pmatrix}.$$


\begin{corollary}\label{SS1}
Если функция $f\colon\Rd\to\mathbb R$ дважды дифференцируема на $\Rd$, то она является выпуклой в том, и только в том случае, если ее гессиан в любой точке $x\in\mathbb R^d$ удовлетворяет условию
$$h^Tf''(x)h\ge0$$
для всех $h\in\mathbb R^d$ $($матрица гессиана в любой точке является неотрицательно определенной$)$.
\end{corollary}

Пусть $X$ --- вещественное линейное пространство, $f_j\colon X\to\mathbb R$, $j=0,1,\ldots,m$, --- выпуклые функции и $A$ --- непустое выпуклое подмножество $X$. Задачу
\begin{equation}\label{eqp4}
f_0(x)\to\min,\quad f_j(x)\le 0,\quad j=1,\ldots,m,\quad x\in A
\end{equation}
называют выпуклой задачей или задачей выпуклого программирования.

Свяжем с задачей \eqref{eqp4} следующую функцию Лагранжа
$$\LL(x,\ov\lambda)=\sum_{j=0}^m\lambda_jf_j(x),$$
где $\ov\lambda=(\lambda_0,\lambda_1,\ldots,\lambda_m)$ --- набор множителей Лагранжа.

Имеет место следующая теорема (см.~\cite[Теорема 20, стр. 34]{Os}).

\begin{theorem}[Каруша--Куна--Таккера]\label{kkt}
Если $\wx$ ---  минимум в задаче \eqref{eqp4}, то найдется такой ненулевой набор множителей Лагранжа $\ov \lambda=(\lambda_0,\lambda_1,\ldots,\lambda_m)$, что выполнены следующие условия
\begin{itemize}
\item[$(a)$] $\min_{x\in A}\LL(x,\ov\lambda)=\LL(\wx,\ov\lambda)$
$($условие минимума$)$;
\item[$(b)$] $\lambda_j\ge0$, $j=0,1,\ldots,m$ $($условие неотрицательности$)$;
\item[$(c)$] $\lambda_jf_j(\wx)=0$, $j=1,\ldots,m$ $($условие дополняющей не\-жест\-кос\-ти$)$.
\end{itemize}

Если существует допустимая в \eqref{eqp4} точка $\wx$ и набор множителей Лагранжа $\ov
\lambda=(\lambda_0,\lambda_1,\ldots,\lambda_m)$, удовлетворяющие условиям $(a)$, $(b)$ и $(c)$ и при этом $\lambda_0>0$, то $\wx$ --- решение задачи \eqref{eqp4}.

Если найдется точка $\ov x\in A$ такая, что $f_j(\ov x)<0$, $1\le j\le m$, то $\lambda_0\ne0$ (условие Слейтера).
\end{theorem}

\section{Субдифференциал}

Пусть $X$ --- линейное нормированное пространство, $f\colon X\to\ov{\mathbb R}$, $\wx\in X$ и функция $f$ конечна в точке $\wx$. Субдифференциалом функции $f$ в точке $\wx$
называется множество (возможно пустое)
$$\partial f(\wx)=\{\, x^*\in X^*:f(x)-f(\wx)\ge\la x^*,x-\wx\ra,\ \forall\, x\in X\,\}.$$

\begin{proposition}\label{pred7}
Субдифференциал функции является выпуклым множеством.
\end{proposition}

\begin{proof}
Если субдифференциал --- пустое множество, то утверждение вытекает из того, что пустое множество --- выпукло. Пусть субдифференциал функции $f$ в точке $\wx$ не пуст и $x_1^*,x_2^*\in\partial f(\wx)$. Тогда для всех $x\in X$
$$f(x)-f(\wx)\ge\la x_1^*,x-\wx\ra,\quad f(x)-f(\wx)\ge\la x_2^*,x-\wx\ra.$$
Отсюда при всех $\alpha\in[0,1]$ имеем
$$(1-\alpha)(f(x)-f(\wx))+\alpha(f(x)-f(\wx))\ge(1-\alpha)\la x_1^*,x-\wx\ra+\alpha\la x_2^*,x-\wx\ra.$$
Следовательно,
$$f(x)-f(\wx)\ge\la(1-\alpha)x_1^*+\alpha x_2^*,x-\wx\ra.$$
Это означает, что $(1-\alpha)x_1^*+\alpha x_2^*\in\partial f(\wx)$.
\end{proof}

Для функции одной переменной субдифференциал $\partial f(\wx)$ это совокупность угловых коэффициентов $k$, при которых прямые $y=kx+b$, проходящие через точку $(\wx,f(\wx))$ лежат под
графиком функции $y=f(x)$
\begin{example}
Пусть $f(x)=|x|$. Тогда
$$\partial|x|=\begin{cases}\sign x,&x\ne0,\\
[-1,1],&x=0.\end{cases}$$

\begin{figure}[h]
$$\begin{picture}(300,120)
\put(55,40){\vector(1,0){190}}
\put(150,15){\vector(0,1){100}}
\put(142,115){$y$}
\put(140,25){$0$}
\put(235,32){$x$}
{\thicklines
\put(150,40){\line(1,1){80}}
\put(230,110){$y=|x|$}
\put(150,40){\line(-1,1){80}}
}
\put(150,40){\line(2,1){90}}
\put(150,40){\line(-2,-1){90}}
\put(150,40){\line(3,1){90}}
\put(150,40){\line(-3,-1){90}}
\put(150,40){\line(6,-5){60}}
\put(150,40){\line(-6,5){80}}
\end{picture}$$
\caption{}\label{ris1}
\end{figure}
\end{example}

На рис.~\ref{ris1} изображены несколько линий, проходящих через точку $(0,0)$ с угловыми коэффициентами из множества $\partial|x|$ при $x=0$.

\begin{example}
Пусть $X$ --- линейное нормированное пространство и $f(x)=\|x\|$. Найдем сначала $\partial f(0)$. Поскольку $f(0)=0$, то из определения субдифференциала вытекает, что
$$\partial f(0)=\{\, x^*\in X^*:\|x\|\ge\la x^*,x\ra,\ \forall\, x\in X\,\}.$$
Покажем, что единичный шар сопряженного пространства
$$BX^*=\{\,x^*\in X^*:\|x^*\|\le1\,\}$$
содержится в $\partial f(0)$. Действительно, если $x^*\in BX^*$, то для всех $x\in X$
$$\la x^*,x\ra\le\|x^*\|\|x\|\le\|x\|.$$
Если теперь $x^*\in\partial f(0)$, то $x^*\in BX^*$, ибо если $\|x^*\|>1$, то существует $x\in X$ такой, что $\|x\|\le1$ и $\la x^*,x\ra>1\ge\|x\|$. Итак, доказано, что $\partial f(0)=BX^*$.

Найдем теперь $\partial f(x_0)$ при $x_0\ne0$. Имеем
$$\partial f(x_0)=\{\, x^*\in X^*:\|x\|-\|x_0\|\ge\la x^*,x-x_0\ra,\ \forall\, x\in X\,\}.$$
Предположим, что $x^*\in\partial f(x_0)$. Подставив $x=0$, получим, что $\la x^*,x_0\ra\ge\|x_0\|$. С другой стороны, если подставить $x=2x_0$, то получим, что $\|x_0\|\ge
\la x^*,x_0\ra$. Следовательно, $\la x^*,x_0\ra=\|x_0\|$. Тогда для всех $x\in X$ должно выполняться неравенство $\|x\|\ge\la x^*,x\ra$. Как было показано выше, это означает, что $x^*\in BX^*$. Нетрудно убедиться, что если $x^*\in BX^*$ и $\la x^*,x_0\ra=\|x_0\|$, то $x^*\in\partial f(x_0)$. Таким образом, при $x_0\ne0$
$$\partial f(x_0)=\{\, x^*\in BX^*:\la x^*,x_0\ra=\|x_0\|\,\}.$$
\end{example}

Следующее предложение показывает, что субдифференциал достаточно естественное обобщение понятия производной на выпуклые функции.

\begin{proposition}\label{P2}
Пусть $X$ --- линейное нормированное пространство и $f\colon X\to\ov{\mathbb R}$ --- выпуклая функция, дифференцируемая в точке $\wx$. Тогда $\partial f(\wx)=\{f'(\wx)\}$.
\end{proposition}

\begin{proof}
Пусть $x\in\ X$. Для любого достаточно малого $\alpha>0$ имеем по
неравенству Йенссена
$$f((1-\alpha)\wx+\alpha x)\le(1-\alpha)f(\wx)+\alpha f(x),$$
откуда
$$f(\wx+\alpha(x-\wx))-f(\wx)\le\alpha(f(x)-f(\wx)).$$
В силу дифференцируемости функции $f$ в точке $\wx$ имеем
$$\alpha\la f'(\wx),x-\wx\ra+o(\alpha)\le\alpha(f(x)-f(\wx)).$$
Сокращая на $\alpha$ и переходя к пределу при $\alpha\to0$, получаем, что $f'(\wx)\in\partial f(\wx)$.

Обратно, если $x^*\in\partial f(\wx)$, то для любого $x\in X$ и любого $t>0$ имеем $f(\wx+tx)-f(\wx)\ge t\la x^*,x\ra$.
Следовательно,
$$t\la f'(\wx),x\ra+o(t)\ge t\la x^*,x\ra,$$
т.~е. $\la f'(\wx),x\ra\ge\la x^*,x\ra$ для любого $x$ и значит,
$x^*=f'(\wx)$.
\end{proof}

Пусть $X$ --- линейное нормированное пространство и $f\colon X\to\ov {\mathbb R}$ --- собственная функция. Рассмотрим задачу
\begin{equation}\label{FF1}
f(x)\to\min,\quad x\in X.
\end{equation}

\begin{theorem}[Ферма в субдифференциальной форме]\label{FD}
Точка $\wx\in\dom f$ является глобальным минимумом в задаче \eqref{FF1} тогда и только тогда, когда $0\in\partial f(\wx)$.
\end{theorem}

\begin{proof}
Если $\wx$ --- глобальный минимум, то $f(x)-f(\wx)\ge0=\la0,x-\wx\ra$ для любого $x\in X$, т.~е. $0\in\partial f(\wx)$. Если $0\in\partial
f(\wx)$, то $f(x)-f(\wx)\ge\la0,x-\wx\ra=0$, т.~е. $f(x)\ge f(\wx)$ для любого $x\in X$.
\end{proof}

Из предложения~\ref{P2} и теоремы~\ref{FD} вытекает

\begin{corollary}
Если в задаче \eqref{FF1} $f$ --- выпуклая функция, дифференцируемая в точке $\wx$, то $\wx$ --- глобальный минимум в том и только в том случае, если $f'(\wx)=0$.
\end{corollary}

\begin{proposition}\label{locmin}
Если $X$ --- линейное нормированное пространство и у выпуклой собственной функции $f\colon X\to\ov{\mathbb R}$ в точке $\wx\in\dom f$ локальный минимум, то в точке $\wx$ и глобальный минимум.
\end{proposition}

\begin{proof}
Пусть $\wx$ ---
локальный минимум, т.~е. существует такая окрестность $U$ точки $\wx$, что $f(\wx)\le f(x)$ для всех $x\in U$. Пусть теперь $x$ --- произвольная точка из $X$. Для достаточно малых $0<\alpha\le1$ точки $(1-\alpha)\wx+\alpha x$ принадлежат $U$ и поэтому (по неравенству Йенссена) $f(\wx)\le f((1-\alpha)\wx+\alpha x)\le(1-\alpha)f(\wx)+\alpha f(x)$, откуда следует, что $f(\wx)\le f(x)$.
\end{proof}

\begin{proposition}\label{locsub}
Если $X$ --- линейное нормированное пространство, $f\colon X\to\ov{\mathbb R}$ --- собственная выпуклая функция и для некоторого $x^*\in X^*$ в окрестности точки $\wx\in\dom f$ выполняется неравенство
\begin{equation}\label{loc1}
f(x)-f(\wx)\ge\la x^*,x-\wx\ra,
\end{equation}
то $x^*\in\partial f(\wx)$.
\end{proposition}

\begin{proof}
Функция $g(x)=f(x)-f(\wx)-\la x^*,x-\wx\ra$ является выпуклой и в точке $\wx$ имеет локальный минимум, равный нулю. Из предложения~\ref{locmin} следует, что $\wx$ --- глобальный минимум, т.е. для всех $x\in X$ выполняется неравенство \eqref{loc1}. Это и означает, что $x^*\in\partial f(\wx)$.
\end{proof}


\section{Субдифференциальное исчисление. Теорема Моро--Рокафеллара}

\begin{theorem}[Моро--Рокафеллара]
Если $f_1,f_2\colon X\to\ov{\mathbb R}$ --- собственные выпуклые функции, хотя бы одна из которых непрерывна в точке $\wx$, то
$$\partial(f_1+f_2)(\wx)=\partial f_1(\wx)+\partial f_2(\wx).$$
\end{theorem}

\begin{proof}
Докажем, что
$$\partial f_1(\wx)+\partial f_2(\wx)\subset\partial(f_1+f_2)(\wx).$$
Пусть $x^*\in\partial f_1(\wx)+\partial f_2(\wx)$. Это означает, что существуют $x_1^*\in\partial f_1(\wx)$ и $x_2^*\in\partial f_2(\wx)$ такие, что $x^*=x_1^*+x_2^*$. Имеем
\begin{multline*}
(f_1+f_2)(x)-(f_1+f_2)(\wx)-\la x^*,x-\wx\ra=f_1(x)-f_1(\wx)-\la x_1^*,x-\wx\ra\\
+f_2(x)-f_2(\wx)-\la x_2^*,x-\wx\ra\ge0.
\end{multline*}
Следовательно, $x^*\in\partial(f_1+f_2)(\wx)$.

Докажем теперь, что
$$\partial(f_1+f_2)(\wx)\subset\partial f_1(\wx)+\partial f_2(\wx).$$
Без ограничения общности можно читать, что $f_1(\wx)=f_2(\wx)=0$. Если это не так, то можно рассмотреть функции
$$g_1(x)=f_1(x)-f_1(\wx),\quad g_2(x)=f_2(x)-f_2(\wx).$$
Докажем, что если
\begin{equation}\label{mr0}
0\in\partial(f_1+f_2)(\wx),
\end{equation}
то найдется $\wix^*\in\partial f_1(\wx)$ такой, что $-\wix^*\in\partial f_2(\wx)$. Из \eqref{mr0} следует, что для всех $x\in X$
\begin{equation}\label{mr1}
(f_1+f_2)(x)\ge(f_1+f_2)(\wx)=0.
\end{equation}
Будем считать, что $f_2$ непрерывна в $\wx$. Положим
\begin{gather*}
A=\{\,(x,v):x\in\dom f_1,\ v<-f_1(x)\,\},\\
B=\epi f_2=\{\,(x,u):x\in\dom f_2,\ u\ge f_2(x)\,\}.
\end{gather*}
Эти два множества выпуклы и непусты. Они не пересекаются, так как из того, что $(x,v)\in A$ следует, учитывая \eqref{mr1}, что $v<-f_1(x)\le f_2(x)$. Тем самым $(x,v)\notin\epi f_2=B$. Поскольку $f_2$ непрерывна в $\wx$, она ограничена в некоторой окрестности $U$ этой точки. Положим
$$M=\sup_{x\in U}f_2(x).$$
Тогда открытое множество
$$V=\{\,(x,v):x\in U,\ v>M\,\}$$
лежит в $\epi f_2$. Следовательно, $\intt B\ne\emptyset$. По первой теореме отделимости (см.~\cite[теорема~11, стр.~23]{Os}, \cite[стр. 243]{KF}) множества $A$ и $B$ можно отделить, т.е. существуют $x^*\in X^*$ и $\lambda\in\mathbb R$, не равные одновременно нулю, такие, что для любых $(x_1,v)\in A$ и $(x_2,u)\in B$ выполняется неравенство
\begin{equation}\label{mr2}
\la x^*,x_1\ra+\lambda v\le\la x^*,x_2\ra+\lambda u.
\end{equation}

Положим в \eqref{mr2} $x_1=x_2=\wx$, $v<0$, a $u=f_2(x_2)=f_2(\wx)=0$. Тогда
$$\la x^*,\wx\ra+\lambda v\le\la x^*,\wx\ra.$$
Следовательно, $\lambda v\le0$, а так как $v<0$, получаем, что $\lambda\ge0$.

Если предположить, что $\lambda=0$, то из \eqref{mr2}
получаем
$$\sup_{x\in\dom f_1}\la x^*,x\ra\le\inf_{x\in\dom f_2}\la x^*,x\ra.$$
Поскольку $x^*\ne0$, а линейная функция, отличная от тождественного нуля, не может принимать минимального значения во внутренней точке, то
$$\la x^*,\wx\ra\le\sup_{x\in\dom f_1}\la x^*,x\ra\le\inf_{x\in\dom f_2}\la x^*,x\ra<\la x^*,\wx\ra.$$
Полученное противоречие показывает, что $\lambda\ne0$.

Пусть $x_1=\wx$, $v<0$, $x_2\in X$, $u=f_2(x_2)$. Тогда из \eqref{mr2} получаем
$$\la x^*,\wx\ra+\lambda v\le\la x^*,x_2\ra+\lambda f_2(x_2).$$
Устремляя $v$ к нулю, получаем
%\begin{equation}\label{mr3}
$$\la x^*,\wx\ra\le\la x^*,x_2\ra+\lambda f_2(x_2).$$
%\end{equation}
Отсюда
$$f(x_2)\ge\la-\lambda^{-1}x^*,x_2-\wx\ra.$$
Следовательно, $-\lambda^{-1}x^*\in\partial f_2(\wx)$.

Пусть теперь $x_2=\wx$, $x_1\in\dom f_1$. Тогда для любого $v<-f_1(x_1)$ выполняется неравенство
$$\la x^*,x_1\ra+\lambda v\le\la x^*,\wx\ra+\lambda f_2(\wx)=\la x^*,\wx\ra.$$
Устремляя $v$ к $f_1(x_1)$, получаем
$$\la x^*,x_1\ra-\lambda f_1(x_1)\le\la x^*,\wx\ra,$$
откуда $\lambda^{-1}x^*\in\partial f_1(\wx)$. Тем самым доказано, что $0\in\partial f_1(\wx)+\partial f_2(\wx)$.

Предположим, что $x^*\in\partial(f_1+f_2)(\wx)$. Положим
$$g(x)=f_1(x)-\la x^*,x-\wx\ra.$$
Нетрудно убедиться, что $0\in\partial(g+f_2)(\wx)$. По доказанному выше $0\in\partial g(\wx)+\partial f_2(\wx)$. Тем самым найдется $\wix^*\in\partial g(\wx)$ такой, что $-\wix^*\in\partial f_2(\wx)$. Включение $\wix^*\in\partial g(\wx)$ означает, что выполняется неравенство
$$f_1(x)-\la x^*,x-\wx\ra\ge\la\wix^*,x-\wx\ra.$$
Следовательно, $x^*+\wix^*\in\partial f_1(\wx)$. Поэтому $x^*\in\partial f_1(\wx)+\partial f_2(\wx)$.
\end{proof}

\begin{corollary}
Если $f$ --- выпуклая функция, непрерывная в точке $\wx$, то $\partial f(\wx)\ne\emptyset$.
\end{corollary}

\begin{proof}
Отметим сначала, что функция $f$ в силу непрерывности в точке $\wx$ является собственной (докажите!). Обозначим через $\delta\{\wx\}$ индикаторную функцию точки $\wx$
$$\delta\{\wx\}(x)=\begin{cases}0,&x=\wx,\\
+\infty,&x\ne\wx.\end{cases}$$
Функция $\delta\{\wx\}$ является собственной выпуклой функцией и нетрудно убедиться, что $\partial\delta\{\wx\}(\wx)=X^*$. Рассмотрим функцию $f+\delta\{\wx\}$. Из теоремы Моро--Рокафеллара получаем
$$X^*=\partial(f+\delta\{\wx\})(\wx)=\partial f(\wx)+\partial\delta\{\wx\})(\wx)=\partial f(\wx)+X^*.$$
Отсюда следует, что $\partial f(\wx)\ne\emptyset$.
\end{proof}

\section{Теорема Дубовицкого--Милютина}

\begin{theorem}[Дубовицкого--Милютина]\label{DM}
Если $f_1,\ldots,f_n\colon X\to\ov{\mathbb R}$ --- собственные выпуклые функции, непрерывные в точке $\wx$, и
$$f(x)=\max\{f_1(x),\ldots,f_n(x)\},$$
то
$$\partial f(\wx)=\co\biggl(\bigcup_{j\in I}\partial f_j(\wx)\biggr),$$
где $I=\{j:f_j(\wx)=f(\wx)\}$.
\end{theorem}

\begin{proof}
Сначала рассмотрим случай, когда
$$f_1(\wx)=\ldots=f_n(\wx)=f(\wx).$$
Докажем, что
\begin{equation}\label{sd}
\co\biggl(\bigcup_{j=1}^n\partial f_j(\wx)\biggr)\subset\partial f(\wx).
\end{equation}
Пусть $x^*\in\partial f_j(\wx)$ при некотором $j$, $1\le j\le n$. Тогда для всех $x\in X$
$$f(x)\ge f_j(x)\ge f_j(\wx)+\la x^*,x-\wx\ra=f(\wx)+\la x^*,x-\wx\ra.$$
Следовательно, $x^*\in\partial f(\wx)$. Тем самым $\partial f_j(\wx)\subset\partial f(\wx)$. Отсюда
$$\bigcup_{j=1}^n\partial f_j(\wx)\subset\partial f(\wx).$$
В силу выпуклости субдифференциала (см.~предложения~\ref{pred7} и \ref{P1}) имеет место \eqref{sd}.

Пусть $x^*\in\partial f(\wx)$. Положим
$$\varphi_j(x)=f_j(x)-f_j(\wx)-\la x^*,x-\wx\ra,\quad j=1,\ldots,n.$$
Для каждого $k=1,\ldots,n$ рассмотрим систему неравенств
\begin{equation}\label{sys}
\begin{cases}\varphi_k(x)<0,&\\
\varphi_j(x)\le0,&j\ne k.\end{cases}
\end{equation}
Предположим, что для всех $k$ эти системы совместны и обозначим через $x_k$ какое-либо решение каждой из этой системы. Рассмотрим точку
$$\wix=\frac1n\sum_{k=1}^nx_k.$$
Тогда при каждом $k=1,\ldots,n$
$$\varphi_k(\wix)\le\frac1n\sjn\varphi_k(x_j)\le\frac1n\varphi_k(x_k)<0.$$
Отсюда
$$f(\wix)-f(\wx)-\la x^*,x-\wx\ra<0,$$
что противоречит тому, что $x^*\in\partial f(\wx)$. Следовательно, найдется $k$, $1\le k\le n$, для которого система \eqref{sys} будет несовместна. Из непрерывности функций $f_j$, $j=1,\ldots,n$, в точке $\wx$ следует, что существует окрестность $U$ точки $\wx$, в которой все функции $f_j$ конечны. Тогда для такого $k$ экстремальная задача
$$\varphi_k(x)\to\min,\quad\varphi_j(x)\le0,\quad j\ne k,\quad x\in U$$
будет иметь решение $\wx$. По теореме Каруша--Куна--Таккера (теорема~\ref{kkt}) найдутся $\lambda_1,\ldots,\lambda_n\ge0$, не все равные нулю, для которых при всех $x\in U$
$$\sjn\lambda_j\varphi_j(x)\ge\sjn\lambda_j\varphi_j(\wx)=0.$$
Из предложения~\ref{locmin} вытекает, что это неравенство выполняется для всех $x\in X$. Без ограничения общности можно считать, что
$$\sjn\lambda_j=1.$$
Тогда получаем, что для всех $x\in X$
$$\sjn\lambda_jf_j(x)-\sjn\lambda_jf_j(\wx)-\la x^*,x-\wx\ra\ge0.$$
Следовательно, пользуясь теоремой Моро--Рокафеллара, получаем
\begin{multline*}
x^*\in\partial\biggl(\sjn\lambda_jf_j\biggr)(\wx)=\sjn\partial(\lambda_jf_j)(\wx)\\
=
\sjn\lambda_j\partial f_j(\wx)\subset\co\biggl(\bigcup_{j=1}^n\partial f_j(\wx)\biggr).
\end{multline*}

Рассмотрим теперь общий случай. Положим $J=\{j:f_j(\wx)<f(\wx)\}$ и $g(x)=\max_{j\in I}f_j(x)$.
В силу непрерывности функций $f_j$, $j=1,\ldots,n$, в точке $\wx$ существует окрестность $V$ точки $\wx$, в которой $f_j(x)<f(x)$ для всех $j\in J$. Тогда в окрестности $V$ функции $f$ и $g$ совпадают. Из предложения~\ref{locsub} получаем, что $\partial f(\wx)=\partial g(\wx)$, а для $\partial g(\wx)$ нужное равенство уже доказано.
\end{proof}

\section{Субдифференциальная форма теоремы  Каруша--Куна--Таккера}

Пусть $X$ --- линейное нормированное пространство, $f_j\colon X\to\ov{\mathbb R}$, $j=0,1,\ldots,m$, --- выпуклые собственные функции. Рассмотрим задачу
\begin{equation}\label{kt}
f_0(x)\to\min,\quad f_j(x)\le 0,\quad j=1,\ldots,m,\quad x\in X.
\end{equation}

\begin{theorem}[Каруша--Куна--Таккера в субдифференциальной форме]
Пусть $\wx\in X$ --- минимум в задаче \eqref{kt} и функции $f_j$, $j=0,1,\ldots,m$, --- непрерывны в точке $\wx$. Тогда найдутся числа $\lambda_j\ge0$, $j=0,1,\ldots,m$, такие, что
$$\sum_{j=0}^m\lambda_j=1,\quad\lambda_jf_j(\wx)=0,\ j=1,\ldots,m,$$
и
$$0\in\sum_{j=0}^m\lambda_j\partial f_j(\wx).$$
\end{theorem}

\begin{proof}
Рассмотрим функцию
$$f(x)=\max\{f_0(x)-f_0(\wx),f_1(x),\ldots,f_m(x)\}.$$
Точка $\wx$ является глобальным минимум этой функции. Действительно, если бы в некоторой точке $\wix\in X$ выполнялось бы неравенство $f(\wix)<0$, то это означало бы, что $f_0(\wix)<f_0(\wx)$ и $f_j(\wix)<0$, $j=1,\ldots,m$, что противоречит минимальности $\wx$ в задаче \eqref{kt}. Тогда из теоремы Ферма в субдифференциальной форме (теорема~\ref{FD}) следует, что $0\in\partial f(\wx)$. По теореме Дубовицкого--Милютина (теорема~\ref{DM}) имеем
$$\partial f(\wx)=\co\biggl(\bigcup_{j\in I}\partial f_j(\wx)\biggr),$$
где $I=\{0\}\cup\{j:f_j(\wx)=0,\ 1\le j\le m\}$. Таким образом (см. предложение~\ref{P3}), найдутся $x^*_j\in\partial f_j(\wx)$, $j\in I$, такие, что
$$0=\sum_{j\in I}\lambda_jx_j^*,\quad\sum_{j\in I}\lambda_j=1,\quad\lambda_j\ge0,\ j\in I.$$
Осталось положить $\lambda_j=0$ для $j\notin I$.
\end{proof}

\section{Двойственность. Сопряженные функции. Теорема Фенхеля--Моро}

В вопросах, связанных с изучением выпуклых объектов (выпуклых множеств, выпуклых функций
и выпуклых экстремальных задач), важную роль играет феномен двойственности. Он
заключается в том, что каждому выпуклому объекту можно сопоставить двойственный выпуклый
объект, который тесно связан с исходным и совместное их исследование, как правило, бывает
весьма плодотворным.

Пусть $X$ --- линейное нормированное пространство. Напомним, что гиперплоскостью называется множество
$$H=\{\,x\in X:\la x^*,x\ra=\gamma\,\},\quad x^*\in X^*,\quad\gamma\in\RR.$$
Гиперплоскость разбивает все пространство на два полупространства
$$H_+=\{\,x\in X:\la x^*,x\ra\le\gamma\,\},\quad H_-=\{\,x\in X:\la x^*,x\ra\ge\gamma\,\}.$$

В основе двойственности выпуклых множеств лежит следующий факт. Выпуклое замкнутое множество в линейном нормированном пространстве $X$ допускает двойное описание: первое (на языке исходного пространства) есть просто определение выпуклости и замкнутости, второе (на языке сопряженного пространства $X^*$) состоит в том, что это множество является пересечением всех полупространств, его содержащих. Докажем последнее утверждение.

\begin{proposition}
Выпуклое замкнутое множество в линейном нормированном пространстве есть пересечение всех полупространств, содержащих это множество.
\end{proposition}

\begin{proof}
Пусть $A$ --- выпуклое замкнутое множество в линейном нормированном пространстве $X$. Обозначим через $B$ пересечение всех полупространств, содержащих $A$. Так как каждое из полупространств содержит $A$, то и их пересечение тоже содержит $A$, т.е. $A\subset B$. Предположим, что существует точка $\wx\in B$, не принадлежащая $A$. По второй теореме отделимости (\cite[теорема~12, стр.~23]{Os}) множество $A$ и точка $\wx$ строго отделимы, т.е. существует ненулевой функционал $x^*\in X$, для которого
$$\sup_{x\in A}\la x^*,x\ra<\la x^*,\wx\ra.$$
Тогда найдется $\varepsilon>0$ такое, что для для всех $x\in A$
$$\la x^*,x\ra\le\gamma,$$
где $\gamma=\la x^*,\wx\ra-\varepsilon$. Тем самым нашлось полупространство, содержащее $A$ и не содержащее $\wx$, что противоречит тому, что $\wx$ принадлежит всем полупространствам, содержащим $A$.
\end{proof}

Функция $f\colon X\to\ov{\mathbb R}$ называется замкнутой, если множество $\epi f$ замкнуто в $X\times\mathbb R$.

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

Напомним, что функция $a(x)=\la x^*,x\ra+\alpha$, где $x^*\in X^*$, а $\alpha\in\mathbb R$, называется аффинной.

\begin{theorem}[о поточечной верхней грани аффинных функций]\label{aff}
Функция $f\colon X\to\mathbb R\cup\{+\infty\}$ является выпуклой и замкнутой
тогда и только тогда, когда она есть поточечная верхняя грань аффинных функций, не превосходящих $f$.
\end{theorem}

\begin{proof}
Если $f$ --- поточечная верхняя грань семейства аффинных функций, то ее надграфик есть
пересечение надграфиков этих функций, которые, очевидно, выпуклы и замкнуты и поэтому
функция $f$ выпукла и замкнута.

Обратно, пусть функция $f$ выпукла и замкнута. Если $f(x)\equiv+\infty$, то она есть,
например, поточечный предел констант. Пусть функция $f$ не равна тождественно $+\infty$ и
$x_0\in X$, $\alpha_0\in\mathbb R$ такие, что $\alpha_0<f(x_0)$. Ясно, что
$(x_0,\alpha_0)\notin{\rm epi}\,f$. По второй теореме отделимости (\cite[теорема~12, стр.~23]{Os}) найдется $x^*\in X^*$ и $\gamma\in\mathbb R$, не равные одновременно нулю, такие, что
\begin{equation}\label{go1}
\sup_{(x,\alpha)\in\epi f}(\la x^*,x\ra+\gamma\alpha)<\la x^*,x_0\ra+\gamma\alpha_0.
\end{equation}
Заметим, что $\gamma\le0$, ибо в противном случае, увеличивая $\alpha$, пришли бы к
противоречию с неравенством \eqref{go1}.

Пусть $f(x_0)<+\infty$. Подставляя точку $(x_0,f(x_0))\in\epi f$ в \eqref{go1}, получаем,
что $\gamma(\alpha_0-f(x_0))>0$. Но $\alpha_0-f(x_0)<0$ и поэтому в данном случае
$\gamma<0$. Можно считать, что $\gamma=-1$ (деля, если необходимо, обе части неравенства
\eqref{go1} на $-\gamma$). Тогда, обозначая через $c$ верхнюю грань в \eqref{go1}, это неравенство можно записать в виде двух неравенств
\begin{equation}\label{go2}
\la x^*,x_0\ra-c>\alpha_0,\quad\la x^*,x\ra-c\le\alpha\quad\forall\ (x,\alpha)\in\epi f.
\end{equation}
Рассмотрим аффинную функцию $a(x)=\la x^*,x\ra-c$. Если $f(x)=+\infty$, то, очевидно, $a(x)<f(x)$. Если $f(x)<+\infty$, то из второго неравенства в \eqref{go2} при $\alpha=f(x)$ следует, что $a(x)\le f(x)$. Таким образом, это неравенство выполняется для всех $x\in X$. Из первого неравенства в \eqref{go2} следует, что $\alpha_0<a(x_0)$, и значит, $\alpha_0<a(x_0)\le f(x_0)$. Выбирая $\alpha_0$ сколь угодно близко к $f(x_0)$, получаем, что во всех точках, где функция $f$ конечна, она есть поточечная верхняя грань семейства аффинных функций, не превосходящих $f$.

Пусть теперь $f(x_0)=+\infty$. Для доказательства теоремы в этом случае надо для любого
$\alpha_0\in\mathbb R$ построить аффинную функцию, не превосходящую $f$, значение которой в точке $x_0$ больше $\alpha_0$. Пусть $\alpha_0\in\mathbb R$. Если в \eqref{go1} $\gamma<0$ (как и выше, считаем тогда, что $\gamma=-1$), то из \eqref{go2} вытекает, что $a(x_0)=\la x^*,x_0\ra-c>\alpha_0$ и все доказано. Если же $\gamma=0$ (отделяющая гиперплоскость ``вертикальна''), то \eqref{go1}
запишется так
\begin{equation}\label{go3}
\la x^*,x_0\ra-c>0,\quad\la x^*,x\ra-c\le0\quad\forall\ (x,\alpha)\in\epi f.
\end{equation}
По доказанному выше существует аффинная функция $a$, которая всюду не превосходит $f$. Для
каждого $\mu>0$ рассмотрим аффинную функцию $a_\mu(x)=a(x)+\mu(\la x^*,x\ra-c)$. Из
второго неравенства в \eqref{go3} следует, что эта функция также всюду не превосходит $f$, а
из первого, что $a_\mu(x_0)=a(x_0)+\mu(\la x^*,x_0\ra-c)>\alpha_0$ для достаточно больших
$\mu$. Итак, $f$ есть поточечная верхняя грань семейства аффинных функций, ее не
превосходящих.
\end{proof}

Пусть $f\colon X\to\ov{\mathbb R}$. Функция на $X^*$, определяемая равенством
\begin{equation}\label{sop}
f^*(x^*)=\sup_{x\in X}(\la x^*,x\ra-f(x)),
\end{equation}
называется сопряженной к $f$ или преобразованием Лежандра--Фенхеля--Юнга.

Рассмотрим некоторые примеры.

\begin{example}
Пусть $X=\mathbb R$. Тогда $X^*=\mathbb R$ и $\la x^*,x\ra=x^*x$. Для $f(x)=e^x$ имеем
$$f^*(x^*)=\sup_{x\in\mathbb R}(x^*x-e^x)=\begin{cases}x^*\ln x^*-x^*,&x^*>0,\\
0,&x^*=0,\\
+\infty,&x^*<0.\end{cases}$$
\end{example}

\begin{example}
Пусть $X=\mathbb R^d$ с нормой $\|x\|=\sqrt{x_1^2+\ldots+x_d^2}$. Тогда $X^*=(\mathbb R^d)^*$ и $$\la x^*,x\ra=\sum_{j=1}^dx_j^*x_j.$$
Для
$$f(x)=\frac1p\sum_{j=1}^d|x_j|^p,\quad1<p<\infty,$$
имеем
$$f^*(x^*)=\frac1q\sum_{j=1}^d|x_j^*|^q,\quad\frac1p+\frac1q=1.$$
\end{example}



Функция $f^*$ есть верхняя грань выпуклых замкнутых функций $\la x^*,x\ra-f(x)$. Поэтому надграфик $f^*$ есть пересечение надграфиков этих функций, т.е. пересечение выпуклых замкнутых множеств. Значит, $f^*$ --- выпуклая замкнутая функция.

Второй сопряженной к $f$ называется функция $f^{**}\colon X\to\ov{\mathbb R}$, определяемая равенством
$$f^{**}(x)=\sup_{x^*\in X^*}(\la x^*,x\ra-f^*(x^*)).$$
По тем же соображениям, что были приведены выше, $f^{**}$ --- выпуклая и замкнутая функция.

Если $f$ --- собственная функция, то из определений вытекают неравенства
$$\la x^*,x\ra\le f(x)+f^*(x^*),\quad\la x^*,x\ra\le f^*(x^*)+f^{**}(x),$$
которые называются неравенствами Юнга. Кроме того, $f(x)\ge f^{**}(x)$, так как $f(x)\ge\la x^*,x\ra-f^*(x^*)$ для всех $x^*\in X^*$, и следовательно,
$$f(x)\ge\sup_{x^*\in X^*}(\la x^*,x\ra-f^*(x^*))=f^{**}(x).$$

Следующий результат об условии совпадения $f$ с ее второй сопряженной служит базой теории двойственности выпуклых функций.

\begin{theorem}[Фенхеля-Моро]\label{FMO}
Пусть $f\colon X\to\mathbb R\cup\{+\infty\}$. Тогда $f=f^{**}$ в том и только том случае, когда $f$ выпукла и замкнута.
\end{theorem}

\begin{proof}
Если $f=f^{**}$, то как было отмечено, $f^{**}$ выпукла и замкнута, поэтому и $f$ такова.

Докажем, что при условии выпуклости и замкнутости $f$ имеет место равенство $f=f^{**}$.
Если $f(x)\equiv+\infty$, то, очевидно, $f^{**}(x)\equiv+\infty$. Пусть $f\ne+\infty$. По доказанному существует такая аффинная функция $a(x)=\la x^*,x\ra-\alpha$, что $\la x^*,x\ra-\alpha\le f(x)$ для всех $x\in X$. Это равносильно тому, что
$$\alpha\ge\sup_{x\in X}(\la x^*,x\ra-f(x))=f^*(x^*).$$
Так как по теореме~\ref{aff} $f$ --- верхняя грань таких функций, то для всех $x\in X$
\begin{equation}\label{FM}
f(x)=\sup_{\substack {x^*\in X^*,\ \alpha\in\mathbb R\\
\alpha\ge f^*(x^*)}}(\la x^*,x\ra-\alpha).
\end{equation}
Поскольку $f$ не равна тождественно $+\infty$, то $f^*$ нигде не обращается в $-\infty$ и
поэтому в \eqref{FM} вместо $\alpha$ можно взять $f^*(x^*)$. Следовательно,
$$f(x)=\sup_{x^*\in X^*}(\la x^*,x\ra-f^*(x^*))=f^{**}(x)$$
для всех $x\in X$.
\end{proof}

\section{Двойственность экстремальных задач. Двойственная задача к задаче
линейного программирования}

Применим теорему Фенхеля--Моро к построению двойственных задач. Пусть $X$ --- линейное нормированное пространство и $f\colon X\to\ov{\mathbb R}$. Рассмотрим задачу
\begin{equation}\label{dv}
f(x)\to\min,\quad x\in X.
\end{equation}
Включим ее в серию ``подобных'' ей задач (или, как говорят, ``возмутим'' данную задачу). Точнее говоря, пусть $Y$ --- линейное нормированное пространство и функция $F\colon X\times Y\to\ov{\mathbb R}$ такова, что $F(x,0)=f(x)$ для всех $x\in X$. Каждому $y\in Y$ сопоставим задачу
\begin{equation}\label{dv1}
F(x,y)\to\min,\quad x\in X.
\end{equation}
Семейство таких задач называется возмущением задачи \eqref{dv}, а функция
$S\colon Y\to\ov{\mathbb R}$, сопоставляющая $y\in Y$ значение задачи \eqref{dv1}, называется $S$-функцией данного семейства. Ясно, что $S(0)$ --- значение исходной задачи \eqref{dv}.

Как уже было отмечено, $S^{**}(0)\le S(0)$, а если $S$-функция выпукла и замкнута, то по
теореме Фенхеля--Моро $S^{**}(0)=S(0)$. Выпишем задачу, значением которой является
величина $S^{**}(0)$. По определению
$$S^{**}(0)=\sup_{y^*\in Y^*}(-S^*(y^*)).$$
Далее,
\begin{multline*}
S^*(y^*)=\sup_{y\in Y}(\la y^*,y\ra-\inf_{x\in X}F(x,y))\\
=\sup_{(x,y)\in X\times Y}(\la 0,x\ra+\la y^*,y\ra-F(x,y))=F^*(0,y^*).
\end{multline*}
Таким образом, задача, значение которой равно $S^{**}(0)$ имеет вид
\begin{equation}\label{dv2}
-F^*(0,y^*)\to\max,\quad y^*\in Y^*.
\end{equation}

Задача \eqref{dv2} называется двойственной задачей к \eqref{dv} (относительно заданного возмущения).

Пусть $c^*\in(\mathbb R^d)^*$, $A$ --- матрица размера $n\times d$ и $b\in\mathbb R^n$. Задачу
\begin{equation}\label{lp}
c^*\cdot x\to\min,\quad Ax\ge b,\quad x\ge0,
\end{equation}
называют задачей линейного программирования (в нормальной форме). Здесь $x\in\mathbb R^d$, а неравенства понимаются покоординатно.

В терминах общей постановки здесь $f(x)=c^*\cdot x$, когда $Ax\ge b$, $x\ge0$ и
$f(x)=+\infty$ в противном случае.

Выпишем двойственную задачу к \eqref{lp} относительно возмущения
\begin{equation}\label{lpv}
c^*\cdot x\to\min,\quad Ax\ge b+y,\quad x\ge0,
\end{equation}
где $y\in\mathbb R^n$ (т.е. $F(x,y)=c^*\cdot x$, когда $Ax\ge b+y$, $x\ge0$ и
$F(x,y)=+\infty$ в противном случае). Имеем
\begin{multline*}
F^*(0,y^*)=\sup_{(x,y)\in\mathbb R^d\times\mathbb R^n}(y^*\cdot y-F(x,y))=\sup_{y\in\mathbb R^n}(y^*\cdot y-\inf_{\substack{Ax\ge b+y\\x\ge0}}c^*\cdot x)\\
=\sup_{\substack{Ax\ge b+y\\x\ge0, \ y\in\mathbb R^n}}(y^*\cdot y-c^*\cdot x)\\
=\begin{cases}
\displaystyle\sup_{x\ge0}(y^*\cdot(Ax-b)-c^*\cdot x),&\mbox{если }y^*\ge0, \\
+\infty,&\mbox{если не так}.
\end{cases}
\end{multline*}
Далее,
\begin{multline*}
\sup_{x\ge0}(y^*\cdot(Ax-b)-c^*\cdot x)=
\sup_{x\ge0}((y^*A-c^*)\cdot x-y^*\cdot b)\\
=\begin{cases}
-y^*\cdot b,&\mbox{если }y^*A-c^*\le0,\\
+\infty,&\mbox{если не так}.
\end{cases}
\end{multline*}
Таким образом,
$$F^*(0,y^*)=\begin{cases}
-y^*\cdot b,&\mbox{если }y^*A\le c^*,\ y^*\ge0,\\
+\infty,&\mbox{если не так},
\end{cases}$$
и следовательно, двойственная задача имеет вид
\begin{equation}\label{lp1}
y^*\cdot b\to\max,\quad y^*A\le c^*,\quad y^*\ge0.
\end{equation}

Мы докажем некоторые теоремы, касающиеся существования решений в задачах \eqref{lp} и \eqref{lp1}, а также двойственных связей между ними. Перед этим нам потребуется ряд предварительных результатов.

Пусть $X$ --- линейное пространство. Непустое множество $K\subset X$ называется конусом, если для всех $x\in K$ и всех $\alpha\ge0$ \ $\alpha x\in K$.

Множество $K\subset X$ называется конечнопорожденным конусом, если существуют $x_1,\ldots,x_n\in X$ такие, что
$$K=\con\{x_1,\ldots,x_n\}.$$

\begin{proposition}\label{KZ}
В линейном нормированном пространстве конечнопорожденный конус  замкнут.
\end{proposition}

\begin{proof}
Пусть $X$ --- линейное нормированное пространство, $x_1,\ldots,x_n\in X$ и $K=\cone\{x_1,\ldots,x_n\}$. Доказательство проведем индукцией по $n$. При $n=1$
$$K=\{\,x\in X:x=\alpha x_1,\ \alpha\ge0\,\}.$$
Если $x_1=0$, то, очевидно, конус $K$ замкнут. Предположим, что $x_1\ne0$ и $\alpha_kx_1\to\wx$ при $k\to+\infty$. Тогда последовательность $\{\|\alpha_kx_1\|\}$ ограничена, и следовательно, последовательность $\{\alpha_k\}$ ограничена. Выберем из нее сходящуюся подпоследовательность. Без ограничения общности можно считать, что $\alpha_k\to\wa$ при $k\to+\infty$. Имеем
$$\|\wx-\wa x_1\|=\|\wx-\alpha_kx_1-(\wa x_1-\alpha_kx_1)\|\le\|\wx-\alpha_kx_1\|+|\wa-\alpha_k|\| x_1\|.$$
В силу того, что правую часть этих соотношений можно сделать при достаточно больших $k$ сколь угодно малой, $\wx=\wa x_1$.

Пусть утверждение верно для конусов, порожденных $n-1$ точкой, $n\ge2$, $x_1,\ldots,x_n\in X$ и $K=\cone\{x_1,\ldots,x_n\}$. Докажем замкнутость конуса $K$. Если конус $K$ содержит точки $-x_1,\ldots,-x_n$, то $K$ --- конечномерное подпространство, и следовательно, замкнутое множество. В противном случае существует точка из множества $-x_1,\ldots,-x_n$, которая не принадлежит $K$. Пусть для определенности это будет $-x_n$. Тогда
$$K=\{\,x\in X:x=x'+\alpha x_n,\ x'\in K',\ \alpha\ge0\,\},$$
где $K'=\cone\{x_1,\ldots,x_{n-1}\}$. Пусть $x^k={x'}^k+\alpha_kx_n$ --- последовательность точек из $K$ сходящаяся к некоторой точке $\wx\in X$. Докажем, что $\wx\in K$. Если последовательность $\{\alpha_k\}$ неограничена, то из нее можно выбрать подпоследовательность, стремящуюся к $+\infty$. Без ограничения общности будем считать, что $\alpha_k\to+\infty$ при $k\to+\infty$. Тогда, поделив на $\alpha_k$ и пользуясь тем, что сходящаяся последовательность точек ограничена, получим
$$\frac{{x'}^k}{\alpha_k}+x_n=\frac{x^k}{\alpha_k}\to0.$$
Тем самым
$$\frac{{x'}^k}{\alpha_k}\to-x_n.$$
В силу замкнутости $K'$ точка $-x_n\in K'\subset K$, что противоречит сделанному ранее предположению. Таким образом, последовательность $\{\alpha_k\}$ ограничена, и следовательно, из нее можно выбрать сходящуюся. Будем считать, что $\alpha_k\to\wa$ при $k\to+\infty$. Тогда
$$x^k-\alpha_kx_n\to\wx-\wa x_n.$$
В силу замкнутости $K'$ \ $\wx-\wa x_n\in K'$. Тем самым существует точка $k'\in K'$, для которой $\wx-\wa x_n=k'$. Это означает, что $\wx=k'+\wa x_n\in K$.
\end{proof}

\begin{theorem}[существования]\label{exi}
Если значение задачи \eqref{lp} $($\eqref{lp1}$)$ конечно, то она имеет решение.
\end{theorem}

\begin{proof}
Начнем с задачи \eqref{lp}. Рассмотрим множество
\begin{equation}\label{KK}
K=\{\,(y,\alpha)\in\mathbb R^n\times\mathbb R:\exists\,x\in\mathbb R^d,\ x\ge0,\  c^*\cdot x\le\alpha,\ Ax\ge y\,\}.
\end{equation}
Нетрудно убедиться, что $K$ --- выпуклый конус. Покажем, что $K$ --- конечнопорожденный конус. Пусть $(y,\alpha)\in K$. Тогда найдется $x\in\mathbb R^d$, $x\ge0$, для которого $c^*\cdot x\le\alpha$ и $Ax\ge y$. Следовательно, найдутся такие $\beta_0\ge0$ и $\beta=(\beta_1,\ldots,\beta_n)^T\ge0$, что $c^*\cdot x+\beta_0=\alpha$ и $Ax-\beta=y$. Переходя к координатной записи, считая, что
$$c^*=(c_1,\ldots,c_n),\quad x=\begin{pmatrix}
x_1\\
\vdots\\
x_d\end{pmatrix},\quad A=\begin{pmatrix}
a_{11}&\ldots&a_{1d}\\
\hdotsfor{3}\\
a_{n1}&\ldots&a_{nd}\end{pmatrix},$$
получаем
$$(y,\alpha)=\sum_{j=1}^dx_j\xi_j+\sum_{j=0}^n\beta_j\xi_{d+j+1},$$
где $\xi_j=((a_{1j},\ldots,a_{nj})^T,c_j)$, $j=1,\ldots,d$, $\xi_{d+1}=((0,\ldots,0)^T,1)$,
$$\xi_{d+2}=((-1,\ldots,0)^T,0),\ldots,\xi_{d+n+1}=((0,\ldots,-1)^T,0).$$
Таким образом, $K\subset\cone\{\xi_1,\ldots,\xi_{d+n+1}\}$. Нетрудно убедиться, что $\xi_j\in K$ при всех $j=1,\ldots,d+n+1$. Для этого надо взять $x_j=1$ и $x_k=0$, если $k\ne j$, при $j=1,\ldots,d$, а при $j=d+1,\ldots,d+n+1$ надо взять $x=0$. Так как $K$ является выпуклым конусом, то $\cone\{\xi_1,\ldots,\xi_{d+n+1}\}\subset K$. Тем самым доказано, что $K$ --- конечнопорожденный конус. Из предложения~\ref{KZ} вытекает, что он замкнут.

Пусть $\wa$ --- значение задачи \eqref{lp}. Тогда существует последовательность $\{x^k\}$ допустимых в задаче \eqref{lp} векторов, для которых последовательность $\{\alpha^k\}$, $\alpha^k=c^*\cdot x^k$, сходится к $\wa$. Так как векторы $x^k$ допустимы в задаче \eqref{lp}, то $(b,\alpha^k)\in K$. Поэтому точка $(b,\wa)$ принадлежит замыканию $K$. В силу замкнутости $K$ \ $(b,\wa)\in K$. Это означает, что найдется вектор $\wx\in\mathbb R^d$ такой, что $\wx\ge0$, $A\wx\ge b$ и $c^*\cdot\wx\le\wa$, но последнее неравенство строгим быть не может (иначе значение задачи \eqref{lp} было бы меньше $\wa$), поэтому $\wx$ --- решение \eqref{lp}.

Для задачи \eqref{lp1} надо рассмотреть конус
$$K_1=\{\,(z^*,\alpha)\in(\mathbb R^d)^*\times\mathbb R:\exists y^*\in(\mathbb R^n)^*,\ y^*\ge0,\  y^*\cdot b\ge\alpha,\ y^*A\le z^*\,\}.$$
В остальном схема рассуждений остается той же, как и в предыдущем случае.
\end{proof}

\begin{theorem}[двойственности]\label{dul}
Для задач \eqref{lp} и \eqref{lp1} справедлива следующая альтернатива: либо значения этих задач
конечны, равны и в каждой из них существует решение, либо в одной из них множество допустимых элементов пусто, а в другой или множество допустимых элементов пусто, или ее значение бесконечно.

Пусть $\wx$ и $\wy^*$ допустимые элементы в задачах \eqref{lp} и \eqref{lp1}. Тогда они являются
решениями этих задач тогда и только тогда, когда
\begin{equation}\label{cy*}
c^*\cdot\wx=\wy^*\cdot b.
\end{equation}
\end{theorem}

\begin{proof}
Рассмотрим семейство задач, зависящих от $y\in\mathbb R^n$
\begin{equation}\label{lpy}
c^*\cdot x\to\min,\quad Ax\ge y,\quad x\ge0.
\end{equation}
Обозначим череp $S_1$ $S$-функцию этого семейства
$$S_1(y)=\inf_{x\ge0,\ Ax\ge y}c^*\cdot x.$$
Докажем, что $\epi S_1=K$, где конус $K$ определен равенством \eqref{KK}. Пусть $(y,\alpha)\in\epi S_1$. Это означает, что $S_1(y)\le\alpha$. Если $S_1(y)=-\infty$, то для любого $a\in\mathbb R$ (и, в частности, для $\alpha$) существует $x\in\mathbb R^d$ такой, что $Ax\ge y$, $x\ge0$ и $c^*\cdot x\le a$. Следовательно, $(y,\alpha)\in K$. Если $S_1(y)$ конечно, то по теореме~\ref{exi} существует решение задачи \eqref{lpy}, т.е. такой $\wx\in\mathbb R^d$, что $\wx\ge0$, $A\wx\ge y$ и $c^*\cdot\wx=S_1(y)\le\alpha$. Значит, и в этом случае $(y,\alpha)\in K$. Тем самым доказано, что $\epi S_1\subset K$.

Пусть теперь $(y,\alpha)\in K$. Это значит, что существует такой $x\in\mathbb R^d$, для которого
$x\ge0$, $Ax\ge y$ и $c^*\cdot x\le\alpha$. Следовательно, $S_1(y)\le\alpha$, и значит $(y,\alpha)\in\epi S_1$.

Итак, доказано, что надграфиком функции $S_1$ является конус $K$. В силу того, что $K$ --- выпуклое и замкнутое множество, функция $S_1$ --- выпукла и замкнута. Для $S$-функции задачи \eqref{lpv} имеем
$$S(y)=S_1(y+b).$$
Поэтому функция $S$ также является выпуклой и замкнутой.

Если $S\colon\mathbb R^n\to\mathbb R\cup\{+\infty\}$, то по теореме Фенхеля--Моро (теорема~\ref{FMO}) $S(0)=S^{**}(0)$, а $S^{**}(0)$ --- значение двойственной задачи \eqref{lp1}. Если $0\in\dom S$, то значения задач \eqref{lp} и \eqref{lp1} конечны, равны и по теореме существования у каждой из них существует решение. Если $0\notin\dom S$, то $S(0)=S^{**}(0)=+\infty$. Следовательно, множество допустимых элементов в задаче $\eqref{lp}$ пусто, а значение двойственной задачи бесконечно.

Пусть существует $y_0\in\mathbb R^n$, для которого $S(y_0)=-\infty$. В этом случае $S^*(y)\equiv+\infty$. Следовательно, $S^{**}(y)\equiv-\infty$. Это означает, что задача \eqref{lp1} несовместна. Нетрудно убедиться, что в рассматриваемом случае $S(y)=-\infty$ для всех $y\in\dom S$ (докажите это!). Поэтому если $0\in \dom S$, то $S(0)=-\infty$, т.е. значение задачи \eqref{lp} бесконечно, а если $0\notin\dom S$, то $S(0)=+\infty$, и следовательно, задача \eqref{lp} несовместна.

Пусть $\wx$ и $\wy^*$ являются решениями задач \eqref{lp} и \eqref{lp1}. Тогда по доказанному выше (поскольку значения конечны) значения задач совпадают, т.е. выполняется равенство \eqref{cy*}.

Пусть $\wx$ и $\wy^*$ допустимы в задачах \eqref{lp} и \eqref{lp1} и справедливо равенство \eqref{cy*}. Для произвольных допустимы в задачах \eqref{lp} и \eqref{lp1} векторов $x$ и $y^*$ имеем
$$c^*\cdot x\ge(y^*A)\cdot x=y^*\cdot(Ax)\ge y^*\cdot b.$$
Поэтому для всех допустимых $x$
$$c^*\cdot x\ge\wy^*\cdot b=c^*\cdot\wx.$$
Отсюда вытекает, что $\wx$ --- решение задачи \eqref{lp}. Из аналогичных соотношений
$$\wy^*\cdot b=c^*\cdot\wx\ge y^*\cdot b$$
вытекает, что $\wy^*$ --- решение задачи \eqref{lp1}.
\end{proof}

\section{Различные формы задач линейного программирования и соответствующие двойственные задачи}

Мы рассмотрели задачу линейного программирования в нормальной форме \eqref{lp}. Существуют и другие формы этой задачи. Пусть $c^*\in(\mathbb R^d)^*$, $A$ --- матрица размера $n\times d$ и $b\in\mathbb R^n$. Задачу
\begin{equation}\label{lpo}
c^*\cdot x\to\min,\quad Ax\ge b,
\end{equation}
называют задачей линейного программирования в общей форме. Напомним, что $x\in\mathbb R^d$, а неравенства понимаются покоординатно.

Задачу
\begin{equation}\label{lpk}
c^*\cdot x\to\min,\quad Ax=b,\quad x\ge0,
\end{equation}
называют задачей линейного программирования в канонической форме.

Задачи в различных формах легко сводятся друг к другу путем введения дополнительных переменных и изменением матрицы $A$. Покажем для примера сведение задачи в нормальной форме \eqref{lp} к задаче в канонической форме \eqref{lpk}. Положим $\wix=(x_{d+1},\ldots,x_{d+n})^T$. Тогда задача \eqref{lp} может быть записана в виде
$$c^*\cdot x\to\min,\quad Ax-\wix=b,\quad x\ge0,\quad\wix\ge0.$$
Введем обозначения: $\ov c^*=(c^*,0)$, $\ov x=(x,\wix)^T$, $\ov A=(A\,-I)$. Теперь задача \eqref{lp} запишется в виде
$$\ov c^*\cdot\ov x\to\min,\quad\ov A\ov x=b,\quad\ov x\ge0.$$

Отметим, что во всех трех формах задач линейного программирования (\eqref{lp}, \eqref{lpo} и \eqref{lpk}) отыскание точной нижней грани можно заменить на отыскание точной верхней грани (простой заменой вектора $c^*$ на $-c^*$ задачу можно свести к одному из рассмотренных видов).

Для получения двойственных задач к задачам \eqref{lpo} и \eqref{lpk} их надо свести к задаче в нормальной форме \eqref{lp}, двойственная к которой уже известна \eqref{lp1}. Начнем с задачи \eqref{lpo}. Представим вектор $x$ в виде разности двух неотрицательных векторов $\wix\in\mathbb R_+^d$ и $\wx\in\mathbb R_+^d$. Тогда задача \eqref{lpo} запишется в виде
$$c^*\cdot\wix-c^*\cdot\wx\to\min,\quad A\wix-A\wx\ge b,\quad\wix\ge0,\quad\wx\ge0.$$
Введя обозначения $\ov c^*=(c^*,-c^*)$, $\ov x=(\wix,\wx)^T$, $\ov A=(A\,-A)$, перепишем эту задачу в виде
$$\ov c^*\cdot\ov x\to\min,\quad\ov A\ov x\ge b,\quad\ov x\ge0.$$
Двойственная к этой задаче имеет вид (см. \eqref{lp1})
$$y^*\cdot b\to\max,\quad y^*\ov A\le\ov c^*,\quad y^*\ge0.$$
Легко убедиться, что условие $y^*\ov A\le\ov c^*$ означает равенство $y^*A=c^*$. Тем самым двойственной к задаче \eqref{lpo} является задача
\begin{equation}\label{lpo1}
y^*\cdot b\to\max,\quad y^*A=c^*,\quad y^*\ge0.
\end{equation}

Рассмотрим теперь задачу линейного программирования в каноническом виде \eqref{lpk}. Ее можно записать так
$$c^*\cdot x\to\min,\quad Ax\ge b,\quad Ax\le b,\quad x\ge0.$$
Положив
$$\ov A=\begin{pmatrix}
\hphantom-A\\
-A\end{pmatrix},\quad\ov b=\begin{pmatrix}
\hphantom-b\\
-b\end{pmatrix},$$
перепишем эту задачу в виде
$$c^*\cdot x\to\min,\quad\ov Ax\ge\ov b,\quad x\ge0.$$
Тогда двойственная задача имеет вид
$$\ov y^*\cdot\ov b\to\max,\quad\ov y^*\ov A\le c^*,\quad\ov y^*\ge0.$$
Если записать $\ov y^*$ в виде $\ov y^*=(\wiy^*,\wy^*)$, то эта задача примет вид
$$(\wiy^*-\wy)\cdot b\to\max,\quad(\wiy^*-\wy^*)A\le c^*,\quad\wiy^*\ge0,\quad\wy\ge0.$$
Так как любой вектор можно представить в виде разности двух неотрицательных векторов, двойственная задача в окончательном виде принимает форму
\begin{equation}\label{lpk1}
y^*\cdot b\to\max,\quad y^*A\le c^*.
\end{equation}

Из проведенных рассуждений и теоремы~\ref{dul} вытекает

\begin{corollary}\label{corr}
Пусть $\wx$ и $\wy^*$ допустимые элементы в задачах \eqref{lpk} и \eqref{lpk1}. Тогда они являются решениями этих задач тогда и только тогда, когда
\begin{equation}\label{cy*1}
c^*\cdot\wx=\wy^*\cdot b.
\end{equation}
\end{corollary}

\section{Выпуклый анализ и теория линейных неравенств}

Двойственность в задачах линейного программирования и соответствующий результат о решениях в двойственных задачах (теорема~\ref{dul}) позволяют достаточно легко получать критерии существования решений в ряде задач из теории линейных неравенств.

\begin{theorem}[Минковского--Фаркаша]
Пусть $A$ --- матрица размера $n\times d$ и $b\in\mathbb R^n$. Для того чтобы система
$$Ax=b$$
имела решение $x\ge0$, необходимо и достаточно, чтобы для любого $y^*\in(\mathbb R^n)^*$ такого, что $y^*A\le0$, выполнялось неравенство $y^*\cdot b\le0$.
\end{theorem}

\begin{proof}
Рассмотрим задачу
\begin{equation}\label{mf}
0\cdot x\to\min,\quad Ax=b,\quad x\ge0.
\end{equation}
Это задача линейного программирования в канонической форме. Двойственной к ней является задача
\begin{equation}\label{mf1}
y^*\cdot b\to\max,\quad y^*A\le0.
\end{equation}
По теореме двойственности задача \eqref{mf} имеет решение (а тем самым множество ее допустимых значений не пусто, а значение задачи равно нулю) в том и только том случае, когда задача \eqref{mf1} имеет решение, равное нулю. Последнее означает, что $y^*\cdot b\le0$ для всех $y^*\in(\mathbb R^n)^*$, удовлетворяющих условию $y^*A\le0$.
\end{proof}

\begin{theorem}[Ки Фаня]
Пусть $A$ --- матрица размера $n\times d$ и $b\in\mathbb R^n$. Для того чтобы система неравенств
$$Ax\le b$$
имела решение, необходимо и достаточно, чтобы для любого $y^*\in(\mathbb R^n)^*$ такого, что $y^*\ge0$ и $y^*A=0$, выполнялось неравенство $y^*\cdot b\ge0$.
\end{theorem}

\begin{proof}
Рассмотрим задачу
\begin{equation}\label{kf}
0\cdot x\to\min,\quad -Ax\ge-b.
\end{equation}
Это задача линейного программирования в общей форме. Двойственной к ней является задача
$$y^*\cdot(-b)\to\max,\quad y^*(-A)=0,\quad y^*\ge0.$$
Эту задачу можно переписать в виде
\begin{equation}\label{kf1}
y^*\cdot b\to\min,\quad y^*A=0,\quad y^*\ge0.
\end{equation}
По теореме двойственности задача \eqref{kf} имеет решение (а тем самым множество ее допустимых значений не пусто, а значение задачи равно нулю) в том и только том случае, когда задача \eqref{kf1} имеет решение, равное нулю. Последнее означает, что $y^*\cdot b\ge0$ для всех $y^*\in(\mathbb R^n)^*$, удовлетворяющих условию $y^*A=0$, $y^*\ge0$.
\end{proof}

\begin{theorem}[Гейла]
Пусть $A$ --- матрица размера $n\times d$ и $b\in\mathbb R^n$. Для того чтобы система неравенств
$$Ax\le b$$
имела решение $x\ge0$, необходимо и достаточно, чтобы для любого $y^*\in(\mathbb R^n)^*$ такого, что $y^*\ge0$ и $y^*A\ge0$, выполнялось неравенство $y^*\cdot b\ge0$.
\end{theorem}

\begin{proof}
Рассмотрим задачу
\begin{equation}\label{ga}
0\cdot x\to\min,\quad -Ax\ge-b,\quad x\ge0.
\end{equation}
Это задача линейного программирования в нормальной форме. Двойственной к ней является задача
$$y^*\cdot(-b)\to\max,\quad y^*(-A)\le0,\quad y^*\ge0.$$
Эту задачу можно переписать в виде
\begin{equation}\label{ga1}
y^*\cdot b\to\min,\quad y^*A\ge0,\quad y^*\ge0.
\end{equation}
По теореме двойственности задача \eqref{ga} имеет решение (а тем самым множество ее допустимых значений не пусто, а значение задачи равно нулю) в том и только том случае, когда задача \eqref{ga1} имеет решение, равное нулю. Последнее означает, что $y^*\cdot b\ge0$ для всех $y^*\in(\mathbb R^n)^*$, удовлетворяющих условию $y^*A\ge0$, $y^*\ge0$.
\end{proof}

\section{Примеры задач линейного программирования}

{\bf1. Задача оптимального планирования производства.} Предприятие выпускает $d$ видов продукции, потребляя при этом $n$ видов сырья. Для выпуска единицы $k$-го вида продукции, $k=1,\ldots,d$, затрачивается $a_{kj}$ единиц $j$-го сырья, $j=1,\ldots,n$. Суммарный объем $j$-го вида сырья, находящегося в распоряжении предприятия равен $b_j$. Прибыль с производства $k$-го вида продукции равна $r_k$ рублей. Задача заключается в том, чтобы получить максимальную прибыль при условии, что расход сырья не превысит тот, который находится в распоряжении предприятия. Пусть $x_k$ --- произведенный объем $k$-го вида продукции. Тогда общая прибыль равна
$$r\cdot x=\sum_{k=1}^dr_kx_k,\quad r=(r_1,\ldots,r_d),\quad x=(x_1,\ldots,x_d)^T.$$
Получаем следующую задачу
$$r\cdot x\to\max,\quad\sum_{k=1}^da_{kj}x_k\le b_j,\quad j=1,\ldots,n,\quad x\ge0.$$
Эта задача очевидным образом сводится к задаче линейного программирования в нормальной форме \eqref{lp}.

{\bf2. Транспортная задача.} Имеется $n$ карьеров с песком и $m$ потребителей, которых надо обеспечить песком. С $k$-го карьера можно увезти $a_k$ тонн песка в сутки, а $j$-му потребителю нужно $b_j$ тонн песка в сутки. При этом перевозка одной тонны песка с $k$-го карьера $j$-му потребителю обходится в $c_{kj}$ рублей. Требуется обеспечить всех потребителей, затратив при этом наименьшую возможную сумму денег. Обозначая через $x_{kj}$ количество песка, взятого с $k$-го карьера для перевозки $j$-му потребителю, получаем следующую задачу:
\begin{multline}\label{tz}
\sum_{k=1}^n\sum_{j=1}^mc_{kj}x_{kj}\to\min,\quad\sum_{j=1}^mx_{kj}=a_k,\ k=1,\ldots,n,\\
\sum_{k=1}^nx_{kj}=b_j,\ j=1,\ldots,m,\quad x_{kj}\ge0,\ k=1,\ldots,n,\ j=1,\ldots,m.
\end{multline}
Положим
\begin{align*}
c^*&=(c_{11},c_{12},\ldots,c_{1m},\ldots,c_{n1},c_{n2},\ldots,c_{nm}),\\ x&=(x_{11},x_{12},\ldots,x_{1m},\ldots,x_{n1},x_{n2},\ldots,x_{nm})^T,\\
\setcounter{MaxMatrixCols}{20}
A&=\begin{pmatrix}
1&1&\ldots&1&0&0&\ldots&0&\ldots&0&0&\ldots&0\\
0&0&\ldots&0&1&1&\ldots&1&\ldots&0&0&\ldots&0\\
\hdotsfor{13}\\
0&0&\ldots&0&0&0&\ldots&0&\ldots&1&1&\ldots&1\\
1&0&\ldots&0&1&0&\ldots&0&\ldots&1&0&\ldots&0\\
0&1&\ldots&0&0&1&\ldots&0&\ldots&0&1&\ldots&0\\
\hdotsfor{13}\\
0&0&\ldots&1&0&0&\ldots&1&\ldots&0&0&\ldots&1
\end{pmatrix},\\
\ov b&=(a_1,a_2.\ldots,a_n,b_1,b_2,\ldots,b_m)^T.
\end{align*}
Тогда задача \eqref{tz} запишется в канонической форме
$$c^*\cdot x\to\min,\quad Ax=\ov b,\quad x\ge0.$$

{\bf 3. Задача на минимакс.} Пусть $c^*_1,\ldots,c^*_k\in(\mathbb R^d)^*$, $\beta_1,\ldots,\beta_k\in\mathbb R$, $A$ --- матрица размера $n\times d$, $b\in\mathbb R^n$ и
$$f(x)=\max\{c^*_1\cdot x-\beta_1,\ldots,c^*_k\cdot x-\beta_k\},\quad x\in\mathbb R^d.$$
Рассмотрим следующую задачу
\begin{equation}\label{minmax}
f(x)\to\min,\quad Ax=b,\quad x\ge0.
\end{equation}
Функция $f$ не является линейной и поэтому задача \eqref{minmax} не является задачей линейного программирования, но ее легко свести к таковой, введя дополнительную переменную. Покажем, что задача \eqref{minmax} эквивалентна задаче
\begin{equation}\label{minmax1}
x_{d+1}\to\min,\quad c^*_j\cdot x-\beta_j\le x_{d+1},\ j=1,\ldots,k,\quad Ax=b,\quad x\ge0.
\end{equation}

Действительно, пусть $\wx=(\wx_1,\ldots,\wx_d)^T$ --- решение задачи \eqref{minmax}. Тогда $(\wx_1,\ldots,\wx_d,f(\wx))^T$ --- решение задачи \eqref{minmax1}, так как если предположить противное, то существовал бы вектор $\wix$, допустимый в задаче \eqref{minmax}, для которого $f(\wix)<f(\wx)$, что противоречит предположению о том, что $\wx$ --- решение задачи \eqref{minmax}.

Если предположить, что $(\wx_1,\ldots,\wx_d,\wx_{d+1})^T$ --- решение задачи \eqref{minmax1}, то вектор $\wx=(\wx_1,\ldots,\wx_d)^T$ --- допустимый в задаче \eqref{minmax}. Если он не является решением этой задачи, то найдется допустимый в ней вектор $\wix=(\wix_1,\ldots,\wix_d)^T$, для которого $f(\wix)<f(\wx)\le \wx_{d+1}$. Тогда вектор $(\wix_1,\ldots,\wix_d,\wix_{d+1})^T$, где $\wix_{d+1}=f(\wix)$, является допустимым в задаче \eqref{minmax1}, а для него $\wix_{d+1}<\wx_{d+1}$, что противоречит предположению об экстремальности вектора $(\wx_1,\ldots,\wx_d,\wx_{d+1})^T$.


\section{Крайние точки в задаче линейного программирования}

Пусть $X$ --- линейное пространство и $A\subset X$. Точка $x\in A$ называется крайней точкой множества $A$, если из того, что $x=(1-\alpha)x_1+\alpha x_2$ при некоторых $\alpha\in(0,1)$ и $x_1,x_2\in A$ вытекает, что $x_1=x_2$. Иными словами, точка $x$ не является внутренней точкой никакого отрезка с концами, принадлежащими $A$.

Множество в $\mathbb R^d$, образованное пересечением конечного числа полупространств, называется полиэдром. В частности, множество допустимых точек в задаче \eqref{lpo} (как и в любой другой задаче линейного программирования, так как они равносильны) является полиэдром. Крайние точки полиэдра называются его вершинами. Легко понять, что минимум линейной функции, если он конечен, достигается в вершинах полиэдра.

Таким образом, для решения задач линейного программирования надо перебрать все вершины и выбрать ту, значение в которой минимизируемой линейной функции минимально. Однако в прикладных задачах число вершин может быть очень большим. В связи с этим возникает задача ``целесообразного'' перебора. Одна из таких процедур и называется симплекс-методом.

Будем рассматривать задачу линейного программирования в канонической форме (для удобства рассматриваем задачу максимизации)
\begin{equation}\label{lpkk}
c^*\cdot x\to\max,\quad Ax=b,\quad x\ge0.
\end{equation}
Напомним, что здесь $c^*\in(\mathbb R^d)^*$, $A$ --- матрица размера $n\times d$ и $b\in\mathbb R^n$.

Двойственной задачей к \eqref{lpkk} является задача (см.~\eqref{lpk1})

\begin{equation}\label{Dlpkk}
y^*\cdot b\to\min,\quad y^*A\ge c^*.
\end{equation}

\begin{proposition}\label{Predk}
Пусть вектор $x=(x_1,\ldots,x_k,0,\ldots,0)^T\in\mathbb R^d$, $x_1,\ldots,x_k>0$, --- допустимый в задаче \eqref{lpkk}. Тогда $x$ является крайней точкой множества допустимых векторов в \eqref{lpkk} в том и только в том случае, если столбцы $a^1,\ldots,a^k$ матрицы $A$ линейно независимы.
\end{proposition}

\begin{proof}
Пусть $x$ --- крайняя точка. Докажем, что столбцы $a^1,\ldots,a^k$ матрицы $A$ линейно независимы. Предположим противное. Если столбцы $a^1,\ldots,a^k$ линейно зависимы, то найдутся не все равные нулю $\lambda_1,\ldots,\lambda_k$ такие, что
$$\sum_{j=1}^k\lambda_ja^j=0.$$
Тем самым $A\lambda=0$ для вектора $\lambda=(\lambda_1,\ldots,\lambda_k,0,\ldots,0)^T\in\mathbb R^d$. Тогда точка $x+t\lambda$ является допустимой для всех $t$ достаточно близких к нулю. Отсюда следует, что точка $x$ не является крайней. Получили противоречие. Таким образом, столбцы $a^1,\ldots,a^k$ линейно независимы.

Пусть теперь столбцы $a^1,\ldots,a^k$ линейно независимы. Докажем тогда, что допустимая точка $x$ --- крайняя точка. Предположим противное. В таком случае существуют допустимые точки $y$ и $z$, $y\ne z$, и число $t\in(0,1)$ такие, что $x=(1-t)y+tz$. Из этого равенства и того, что $x=(x_1,\ldots,x_k,0,\ldots,0)^T$, а $y,z\ge0$, вытекает, что $y=(y_1,\ldots,y_k,0,\ldots,0)^T$, $z=(z_1,\ldots,z_k,0,\ldots,0)^T$. В силу того, что $Ay=b$ и $Az=b$, получаем $A(y-z)=b$. Это означает, что
$$\sum_{j=1}^k(y_j-z_j)a^j=0.$$
Тем самым столбцы $a^1,\ldots,a^k$ линейно зависимы. Получили противоречие.
\end{proof}

Так как число линейно независимых столбцов не может превышать числа строк матрицы, то из предложения~\ref{Predk} следует, что крайняя точка содержит не более $n$ положительных координат.

Задача \eqref{lpkk} называется невырожденной, если любая крайняя точка множества допустимых значений содержит ровно $n$ положительных координат. Если $b=0$, то нетрудно убедиться, что $x=0$ --- крайняя точка. Поэтому в невырожденной задаче $b\ne0$.

\begin{proposition}\label{krab}
Пусть \eqref{lpkk} --- невырожденная задача и $x=(x_1,\ldots,x_k,0,\ldots,0)^T\in\mathbb R^d$, $x_1,\ldots,x_k>0$, --- допустимая точка в этой задаче. Тогда
\begin{itemize}
\item[$a)$] $k\ge n$,
\item[$b)$] точка $x$ является крайней точкой множества допустимых элементов тогда и только тогда, когда $k=n$.
\end{itemize}
\end{proposition}

\begin{proof}
$a).$ Предположим, что $k<n$. Тогда из теоремы~\ref{Kcone} следует, что найдутся $s\le k$ линейно независимых столбцов $a^{j_1},\ldots,a^{j_s}$ матрицы $A$ и такие $\beta_1,\ldots,\beta_s>0$, что элемент $y=(y_1,\ldots,y_d)$, в котором
$$y_j=\begin{cases}\beta_s,&j=j_s.\\
0,&j\notin\{j_1,\ldots,j_s\},\end{cases}$$
является допустимым. Из предложения~\ref{Predk} вытекает, что $y$ --- крайняя точка, но она содержит $s\le k<n$ положительных координат, что противоречит предположению о невырожденности задачи \eqref{lpkk}.

$b).$ Если $x=(x_1,\ldots,x_k,0,\ldots,0)^T$ --- крайняя точка, то по определению невырожденной задачи $k=n$.

Пусть $k=n$. Если столбцы $a^1,\ldots,a^n$ матрицы $A$ линейно зависимы, то из теоремы~\ref{Kcone} вытекает, что найдется крайняя точка с $p<n$ числом положительных координат, что противоречит невырожденности задачи \eqref{lpkk}. Поэтому столбцы $a^1,\ldots,a^n$ линейно независимы. Тогда из предложения~\ref{Predk} следует, что $x$ --- крайняя точка.
\end{proof}

\section{Симплекс-метод решения задач линейного программирования}

Приведем схему решения задач по симплекс-методу. Будем рассматривать невырожденную задачу линейного программирования в канонической форме \eqref{lpkk}.

Пусть дана крайняя точка $x=(x_1,\ldots,x_n,0,\ldots,0)$, $x_j>0$, $j=1,\ldots,n$ (для удобства записи схемы решения считаем, что положительные координаты стоят первыми). Один из методов нахождения начальной крайней точки будет описан ниже. Вектор $x$ можно представить в виде $x=(x_b,\wix)^T$, где $x_b=(x_1,\ldots,x_n)^T$, $x_b>0$, а $\wix=(0,\ldots,0)^T\in\mathbb R^{d-n}$. Аналогично матрицу $A$ можно представить в виде $A=(A_b\,\widetilde A)$, где матрица $A_b$ состоит из столбцов $a^1,\ldots,a^n$. Из предложения~\ref{Predk} вытекает, что матрица $A_b$ невырожденная.

Построим симплексную таблицу для этой крайней точки (см. рис.~\ref{st}).

\setlength{\extrarowheight}{3pt}
\begin{figure}[h]
$$\footnotesize
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
&c^*&&c_1&\ldots&c_n&c_{n+1}&\ldots&c_{k_0}&\ldots&c_d&t\\
\hline
\mbox{базис}&&b\,(x_b)&a^1&\ldots&a^n&a^{n+1}&\ldots&a^{k_0}&\ldots&a^d&\\
\hline
a^1&c_1&x_1&1&\ldots&0&x_{1,n+1}&\ldots&x_{1k_0}&\ldots&x_{1d}&t_1\\
\hline
\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&
\ldots&\ldots&\ldots&\ldots&\ldots\\
\hline
a^{j_0}&c_{j_0}&x_{j_0}&0&\ldots&0&x_{j_0,n+1}&\ldots&x_{j_0k_0}&
\ldots&x_{j_0d}&t_{j_0}\\
\hline
\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&
\ldots&\ldots&\ldots&\ldots&\ldots\\
\hline
a^n&c_n&x_n&0&\ldots&1&x_{n,n+1}&\ldots&x_{nk_0}&\ldots&x_{nd}&t_n\\
\hline
z&&c_b^*\cdot x_b&c_1&\ldots&c_n&c_b^*\cdot x^{n+1}&\ldots&c_b^*\cdot x^{k_0}&\ldots&c_b^*\cdot x^d&\\
\hline
\Delta&&&0&\ldots&0&\Delta_{n+1}&\ldots&\Delta_{k_0}&\ldots&\Delta_d&\\
\hline
\end{array}$$
\caption{Симплексная таблица}\label{st}
\end{figure}

Сделаем ряд пояснений к этой таблице. В первом столбце, начиная с третьей строки по $n+2$ обозначены базисные векторы, соответствующие положительным координатам крайней точки (в нашем случае это $a^1,\ldots,a^n$). Во втором столбце на соответствующих местах стоят значения $c_j$ вектора $c^*$ с теми же номерами, что и столбцы $a^j$.

Последний столбец заполняется при исследовании симплексной таблицы.

В первой строке, начиная с четвертого столбца, стоят элементы $c_1,\ldots,c_d$. Вторая строка, начиная с третьего столбца, --- векторы $b,a^1,\ldots,a^d$. Под ними --- разложение этих векторов по базису $a^1,\ldots,a^n$. Ясно, что в силу того, что $Ax=b$,
$$b=\sjn a^jx_j.$$
Тем самым разложением вектора $b$ является вектор $x_b$ ненулевых координат крайней точки $x$. Предположим, что векторы $a^k$, $k=1,\ldots,d$, имеют следующее разложение по базису $a^1,\ldots,a^n$
$$a^k=\sjn a^jx_{jk}.$$
Таким образом, $a^k=A_bx^k$, и следовательно, $A=A_bX$, где
$$X=\begin{pmatrix}
x_{11}&\ldots&x_{1d}\\
\hdotsfor{3}\\
x_{n1}&\ldots&x_{nd}
\end{pmatrix}$$
--- матрица разложений векторов $a^1,\ldots,a^d$ по базису $a^1,\ldots,a^n$, а $x^k$ --- столбцы этой матрицы. Тогда $X=A_b^{-1}A$. Очевидно, что при $k=1,\ldots,n$ разложения векторов $a^k$ тривиальны: $a^k=a^k$. Поэтому матрица $X$ на самом деле имеет вид
$$X=\begin{pmatrix}
1&\ldots&0&x_{1,n+1}&\ldots&x_{1d}\\
\hdotsfor{6}\\
0&\ldots&1&x_{n,n+1}&\ldots&x_{nd}
\end{pmatrix}.$$

Положим $c^*_b=(c_1,\ldots,c_n)$. В предпоследней строке $z$ в столбце под вектором $x_b$ запишем $z_0=c^*_b\cdot x_b$. Тогда $z_0$ --- значение функционала в начальной крайней точке $x$. Под векторами $a^k$, $k=1,\ldots,d$, запишем $z_k=c^*_b\cdot x^k$, то есть
$$z=(z_1,\ldots,z_d)=c^*_bX.$$
Очевидно, что $z_k=c_k$ при $k=1,\ldots,n$.

В последней строке $\Delta$, начиная с четвертого столбца, записывается разность между элементами предпоследней строки и элементами первой строки: $\Delta=z-c^*$.

Далее следует исследовать симплексную таблицу.

\begin{proposition}\label{PrS1}
Если $\Delta\ge0$, то вектор $x$ --- решение задачи \eqref{lpkk}, а вектор $y^*=c_b^*A_b^{-1}$ --- решение двойственной задачи \eqref{Dlpkk}.
\end{proposition}

\begin{proof}
Условие $\Delta\ge0$ означает, что $z\ge c^*$. Тем самым $c^*_bX\ge c^*$. Подставляя выражение $c_b^*$ через $y^*$, получаем, что $y^*A_bX\ge c^*$. Следовательно, $y^*A\ge c^*$. Таким образом, $y^*$ --- допустимый элемент в задаче \eqref{Dlpkk}. Кроме того,
$$c^*\cdot x=c_b^*\cdot x_b=y^*A_b\cdot x_b=y^*\cdot A_bx_b=y^*\cdot b.$$
Из следствия~\ref{corr} (с соответствующими заменами экстремальных задач с минимума на максимум и наоборот) вытекает утверждение предложения.
\end{proof}

\begin{proposition}\label{PrS2}
Если для некоторого $k$ \ $\Delta_k<0$ и $x^k\le0$, то значение задачи \eqref{lpkk} равно $+\infty$.
\end{proposition}

\begin{proof}
Положим
$$x(t)=x-t\begin{pmatrix}
x^k\\
0\\
\vdots\\
0\end{pmatrix}+te_k$$
($e_1,\ldots,e_d$ --- канонический базис в $\Rd$). В силу того, что $x^k\le0$, $x(t)\ge0$ для всех $t\ge0$. Кроме того,
$$Ax(t)=Ax-tA_bx^k+tAe_k=b-ta^k+ta^k=b.$$
Значит, $x(t)$ --- допустимый элемент при всех $t\ge0$. При этом
$$c^*\cdot x(t)=c^*_b\cdot x_b-tc^*_b\cdot x^k+tc^*_k=c^*_b\cdot x_b-t\Delta_k.$$
Отсюда видно, что $c^*\cdot x(t)\to+\infty$ при $t\to+\infty$.
\end{proof}

Пусть в строке $\Delta$ имеются отрицательные числа, а соответствующие столбцы $x^k$ содержат положительные числа. Предположим, что
$$\min_k\Delta_k=\Delta_{k_0},$$
где минимум берется именно по тем столбцам, которые обладают указанным выше свойством. Очевидно, что $n+1\le k_0\le d$. Столбец, соответствующий индексу $k_0$, называется разрешающим столбцом (если минимум достигается на нескольких значениях $k$, то выбираем любой из таких столбцов). Для тех $j$, при которых $x_{jk_0}>0$, положим
$$t_j=\frac{x_j}{x_{jk_0}}.$$
Эти значения ставим соответственно в последнем столбце симплексной таблицы. Пусть
$$t_{j_0}=\min_jt_j.$$
Строка вектора $a^{j_0}$ называется разрешающей. Элемент $x_{j_0k_0}$ называется разрешающим элементом симплексной таблицы.

Далее необходимо из числа базисных векторов исключить вектор $a^{j_0}$, вместо него взять $a^{k_0}$.

\begin{theorem}
Если не выполнены условия предложений~$\ref{PrS1}$ и $\ref{PrS2}$, то точка $x'$ с новыми базисными векторами $$a^1,\ldots,a^{j_0-1},a^{k_0},a^{j_0+1},\ldots,a^n$$
является новой крайней точкой, а значение функционала при этом возрастает на величину $-t_{j_0}\Delta_{k_0}$. Новая симплексная таблица (для новой крайней точки) может быть построена из старой с помощью следующих соотношений:
\begin{equation}\label{tab}
\begin{aligned}
x'_j&=\begin{cases}x_j-\dfrac{x_{j_0}x_{jk_0}}{x_{j_0k_0}},&1\le j\le n,\\
\dfrac{x_{j_0}}{x_{j_0k_0}},&j=k_0,
\end{cases}\\ x'_{jk}&=\begin{cases}x_{jk}-\dfrac{x_{j_0k}x_{jk_0}}{x_{j_0k_0}},&j\ne j_0,\ 1\le j\le n,\\
\dfrac{x_{j_0k}}{x_{j_0k_0}},&j=k_0.\end{cases}
\end{aligned}
\end{equation}
\end{theorem}

\begin{proof}
Положим
$$x'=x-t_{j_0}\begin{pmatrix}
x^{k_0}\\
0\\
\vdots\\
0\end{pmatrix}+t_{j_0}e_{k_0}.$$
Докажем, что вектор $x'$ является новой крайней точкой. Покажем сначала, что он является допустимым вектором. Имеем
$$Ax'=Ax-t_{j_0}A_bx^{k_0}+t_{j_0}Ae_{k_0}=b-t_{j_0}a^{k_0}+t_{j_0}
a^{k_0}=b.$$
Кроме того, при $j=1,\ldots,n$
$$x_j'=x_j-t_{j_0}x_{jk_0}=x_j-\frac{x_{j_0}}{x_{j_0k_0}}x_{jk_0}\ge0.$$
При этом $x_{j_0}'=0$. Для $n+1\le j\le d$, $j\ne k_0$, получаем $x_j'=0$, а
$$x_{k_0}'=t_{j_0}=\frac{x_{j_0}}{x_{j_0k_0}}>0.$$
По построению у вектора $x'$ по сравнению с вектором $x$ добавилась одна положительная координата $k_0$, а координата $j_0$ обратилась в ноль. Поскольку по предложению~\ref{krab} у допустимой точки не менее $n$ положительных координат, то в ноль обратилась только координата $j_0$. Таким образом, у точки $x'$ ровно $n$ положительных координат, и из того же предложения~\ref{krab} следует, что $x'$ --- крайняя точка.

Для новой крайней точки имеем
\begin{multline*}
c^*\cdot x'=c^*\cdot x-t_{j_0}c_b^*\cdot x^{k_0}+t_{j_0}c^*\cdot e_{k_0}=c^*\cdot x-t_{j_0}z_{k_0}+t_{j_0}c_{k_0}\\
=c^*\cdot x-t_{j_0}\Delta_{k_0}.
\end{multline*}
Тем самым
$$c^*\cdot x'-c^*\cdot x=-t_{j_0}\Delta_{k_0}.$$

Вычислим теперь координаты $x'_{jk}$ разложения столбцов $a^k$ матрицы $A$ по базису $a^1,\ldots,a^{j_0-1},a^{k_0},a^{j_0+1},\ldots,a^n$. В старом базисе мы имели следующие разложения
\begin{equation}\label{ak}
a^k=\sjn a^jx_{jk}=\sum_{\substack{j=1\\j\ne j_0}}^na^jx_{jk}+a^{j_0}x_{j_0k},\quad j=1,\ldots,d.
\end{equation}
В частности, при $k=k_0$
$$a^{k_0}=\sum_{\substack{j=1\\j\ne j_0}}^na^jx_{jk_0}+a^{j_0}x_{j_0k_0}.$$
Поскольку $x_{j_0k_0}\ne0$, то выразим $a^{j_0}$ из последнего уравнения
$$a^{j_0}=-\sum_{\substack{j=1\\j\ne j_0}}^na^j\frac{x_{jk_0}}{x_{j_0k_0}}+\frac{a^{k_0}}{x_{j_0k_0}}$$
и подставим в \eqref{ak}. Имеем
\begin{multline*}
a^k=\sum_{\substack{j=1\\j\ne j_0}}^na^jx_{jk}+\biggl(-\sum_{\substack{j=1\\j\ne j_0}}^na^j\frac{x_{jk_0}}{x_{j_0k_0}}+\frac{a^{k_0}}{x_{j_0k_0}}\biggr)
x_{j_0k}\\
=\sum_{\substack{j=1\\j\ne j_0}}^na^j\left(x_{jk}-\frac{x_{jk_0}x_{j_0k}}{x_{j_0k_0}}\right)+
a^{k_0}\frac{x_{j_0k}}{x_{j_0k_0}},\quad k=1,\ldots,d.
\end{multline*}
Получим разложения по базису $a^1,\ldots,a^{j_0-1},a^{k_0},a^{j_0+1},\ldots,a^n$. При этом коэффициенты разложения соответствуют соотношениям \eqref{tab}.
\end{proof}


Затем новая симплексная таблица вновь исследуется, и так далее, пока не придем к решению задачи. Формулы для вычисления элементов таблицы, лежащих под векторами $b,a^1,\ldots,a^d$, и не лежащими в разрешающей строке, называются правилом прямоугольника --- элементы, участвующие в этих формулах, стоят в вершинах прямоугольника в симплексной таблице.


\section{Примеры применения симплекс-метода}

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

\begin{example}
Пусть требуется решить задачу линейного программирования
\begin{gather*}
2x_1+x_2+x_3-x_4\to\max,\quad x_j\ge0,\ j=1,\ldots,4,\\
\begin{aligned}
x_1-x_2+x_3\hphantom{+x_4}&=1,\\
2x_1+x_2\hphantom{+x_3}+x_4&=3,
\end{aligned}
\end{gather*}
с заданной начальной крайней точкой $x=(0,0,1,3)^T$.

Базисные векторы здесь $a^3=(1,0)^T$ и $a^4=(0,1)^T$. Составим первую симплексную таблицу (рис.~\ref{st1}).

\begin{figure}[h]
$$\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
&c^*&&2&1&1&-1&t\\
\hline
\mbox{базис}&&x_b&a^1&a^2&a^3&a^4&\\
\hline
a^3&1&1&1&-1&1&0&\\
\hline
a^4&-1&3&2&\mathbf1&0&1&3\\
\hline
z&&-2&-1&-2&1&-1&\\
\hline
\Delta&&&-3&-3&0&0&\\
\hline
\end{array}$$
\caption{}\label{st1}
\end{figure}

Из таблицы видно, что в качестве разрешающего столбца можно взять столбцы $a^1$ или $a^2$. Возьмем столбец $a^2$. Тогда разрешающая строка $a^4$. Заменяем в базисе вектор $a^4$ на вектор $a^2$. Для нового базиса с помощью формул \eqref{tab} строим вторую симплексную таблицу (рис.~\ref{st2}).

\begin{figure}[h]
$$\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
&c^*&&2&1&1&-1&t\\
\hline
\mbox{базис}&&x_b&a^1&a^2&a^3&a^4&\\
\hline
a^3&1&4&3&0&1&1&\\
\hline
a^2&1&3&2&1&0&1&\\
\hline
z&&7&5&1&1&2&\\
\hline
\Delta&&&3&0&0&3&\\
\hline
\end{array}$$
\caption{}\label{st2}
\end{figure}

Вектор $\Delta\ge0$, поэтому точка $\wx=(0,3,4,0)^T$ является решением задачи, а ее значение равно $7$.

Если бы в качестве разрешающего столбца в первой симплексной таблице мы взяли столбец $a^1$, то пришли бы к той же точке, но за большее число шагов.
\end{example}

\section{Метод искусственного базиса для нахождения начальной крайней точки}

Будем снова рассматривать задачу линейного программирования в канонической форме
\begin{equation}\label{lpib}
c^*\cdot x\to\max,\quad Ax=b,\quad x\ge0,
\end{equation}
где $c^*\in(\mathbb R^d)^*$, $A$ --- матрица размера $n\times d$ и $b\in\mathbb R^n$. Не ограничивая общности, можно считать, что $b\ge0$. Если это не так, например $b_j<0$, то умножим обе части $j$-го уравнения на $-1$.

Рассмотрим вспомогательную задачу, добавляя искусственные переменные $\wix=(x_{d+1},\ldots,x_{d+n})^T$ и единичную матрицу $I$.
\begin{equation}\label{ib}
-\sjn x_{d+j}\to\max,\quad Ax+I\wix=b,\quad x\ge0,\quad\wix\ge0.
\end{equation}

Точка $\wx=(0,\ldots,0,b_1,\ldots,b_n)^T$ является допустимой в задаче \eqref{ib}. Кроме того, значение задачи конечно. Из теоремы~\ref{dul} вытекает, что решение в этой задаче существует.

Из предложения~\ref{Predk} вытекает, что точка $\wx$ является крайней для задачи \eqref{ib}. Будем решать эту задачу симплекс-методом. При этом могут встретиться следующие ситуации.

1. Решение задачи \eqref{ib} содержит ненулевые искусственные переменные. Это означает, что в исходной задаче \eqref{lpib} нет допустимых элементов. Действительно, если не все искусственные переменные нулевые, то значение задачи \eqref{ib} отрицательное, а если существует допустимый вектор $(x^0_1,\ldots,x^0_d)^T$ в задаче \eqref{lpib}, то вектор $(x^0_1,\ldots,x^0_d,0,\ldots,0)^T$ является допустимым в задаче \eqref{ib}, а значение максимизируемого функционала на нем равно нулю.

2. Решение задачи \eqref{ib} не содержит ненулевых искусственных переменных и среди базисных векторов нет векторов, соответствующих искусственным переменным. В этом случае решение задачи \eqref{ib} имеет вид $(\wx_1,\ldots,\wx_n,0,\ldots,0)^T$, а точка $(\wx_1,\ldots,\wx_n)^T$, в которой координаты, не соответствующие базисным, равны нулю, является крайней для задачи \eqref{lpib}, так как столбцы, соответствующие базисным координатам будут линейно независимы (см. предложение~\ref{Predk}).

Далее, взяв в качестве первоначальной крайней точки точку $(\wx_1,\ldots,\wx_n)^T$, можно приступать ко второму этапу - решению задачи \eqref{lpib} с помощью симплекс-метода. Тем самым мы получаем двухэтапный метод решения задачи \eqref{lpib}.

\begin{example}
Решить методом искусственного базиса задачу

\begin{gather*}
x_1+2x_2+3x_3-4x_4\to\max,\quad x_j\ge0,\ j=1,\ldots,4,\\
\begin{aligned}
x_1+\hphantom{14}x_2-\hphantom{10}x_3+\hphantom{10}x_4&=2,\\
x_1+14x_2+10x_3-10x_4&=24.
\end{aligned}
\end{gather*}

Рассмотрим вспомогательную задачу, добавляя искусственные переменные $x_5$ и $x_6$:

\begin{gather*}
-x_5-x_6\to\max,\quad x_j\ge0,\ j=1,\ldots,6,\\
\begin{aligned}
x_1+\hphantom{14}x_2-\hphantom{10}x_3+\hphantom{10}x_4+
x_5\hphantom{+x_6}&=2,\\
x_1+14x_2+10x_3-10x_4\hphantom{+x_5}+x_6&=24.
\end{aligned}
\end{gather*}

Исходная крайняя точка $x=(0,0,0,0,2,24)^T$. Базисные векторы
$$a^5=(1,0)^T,\quad a^6=(0,1)^T.$$
Составим первую симплексную таблицу для вспомогательной задачи (рис.~\ref{ist1}).

\begin{figure}[h]
$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|}
\hline
&c^*&&0&0&0&0&-1&-1&t\\
\hline
\mbox{базис}&&x_b&a^1&a^2&a^3&a^4&a^5&a^6&\\
\hline
a^5&-1&2&1&1&-1&1&1&0&2\\
\hline
\vspace{-14pt}&&&&&&&&&\\
a^6&-1&24&1&\mathbf{14}&10&-10&0&1&\dfrac{12}7\\[7pt]
\hline
z&&-26&-2&-15&-9&9&-1&-1&\\
\hline
\Delta&&&-2&-15&-9&9&0&0&\\
\hline
\end{array}$$
\caption{}\label{ist1}
\end{figure}

Разрешающим столбцом является столбец $a^2$, разрешающая строка $a^6$. Заменяем в базисе вектор $a^6$ на вектор $a^2$ и для нового базиса строим вторую симплексную таблицу (рис.~\ref{ist2}).

\begin{figure}[h]
$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|}
\hline
&c^*&&0&0&0&0&-1&-1&t\\
\hline
\mbox{базис}&&x_b&a^1&a^2&a^3&a^4&a^5&a^6&\\
\hline
\vspace{-14pt}&&&&&&&&&\\
a^5&-1&\dfrac27&\dfrac{13}{14}&0&-\dfrac{12}7&\mathbf{\dfrac{12}7}&1&-\dfrac1{14}&\dfrac16\\[7pt]
\hline
\vspace{-14pt}&&&&&&&&&\\
a^2&0&\dfrac{12}7&\dfrac1{14}&1&\dfrac57&-\dfrac57&0&\dfrac1{14}&\\[7pt]
\hline
\vspace{-14pt}&&&&&&&&&\\
z&&-\dfrac27&-\dfrac{13}{14}&0&\dfrac{12}7&-\dfrac{12}7&-1&\dfrac1{14}&\\[7pt]
\hline
\vspace{-14pt}&&&&&&&&&\\
\Delta&&&-\dfrac{13}{14}&0&\dfrac{12}7&-\dfrac{12}7&0&\dfrac{15}{14}&\\[7pt]
\hline
\end{array}$$
\caption{}\label{ist2}
\end{figure}

Теперь заменяем вектор $a^5$ на вектор $a^4$ и строим третью симплексную таблицу (рис.~\ref{ist3}).

\begin{figure}[h]
$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|}
\hline
&c^*&&0&0&0&0&-1&-1&t\\
\hline
\mbox{базис}&&x_b&a^1&a^2&a^3&a^4&a^5&a^6&\\
\hline
\vspace{-14pt}&&&&&&&&&\\
a^4&0&\dfrac16&\dfrac{13}{24}&0&-1&1&
\dfrac7{12}&-\dfrac1{24}&\\[7pt]
\hline
\vspace{-14pt}&&&&&&&&&\\
a^2&0&\dfrac{11}6&\dfrac{11}{24}&1&0&0&\dfrac5{12}&\dfrac1{24}&\\[7pt]
\hline
z&&0&0&0&0&0&0&0&\\
\hline
\Delta&&&0&0&0&0&1&1&\\
\hline
\end{array}$$
\caption{}\label{ist3}
\end{figure}

Так как $\Delta\ge0$, то точка
$$\left(0,\frac{11}6,0,\frac16,0,0\right)^T$$
является решением вспомогательной задачи. При этом среди базисных векторов нет векторов, соответствующих искусственным переменным. Таким образом, в качестве начальной крайней точки в исходной задаче можно взять точку
$$x=\left(0,\frac{11}6,0,\frac16,\right)^T.$$

Составим первую симплексную таблицу (рис.~\ref{ist4}), используя разложения векторов $x$, $a^1$ и $a^3$ из последней симплексной таблицы.

\begin{figure}[h]
$$\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
&c^*&&1&2&3&-4&t\\
\hline
\mbox{базис}&&x_b&a^1&a^2&a^3&a^4&\\
\hline
\vspace{-14pt}&&&&&&&\\
a^4&-4&\dfrac16&\mathbf{\dfrac{13}{24}}&0&-1&1&\dfrac4{13}
\\[7pt]
\hline
\vspace{-14pt}&&&&&&&\\
a^2&2&\dfrac{11}6&\dfrac{11}{24}&1&0&0&4\\[7pt]
\hline
\vspace{-14pt}&&&&&&&\\
z&&3&-\dfrac{15}{12}&2&4&-4&\\[7pt]
\hline
\vspace{-14pt}&&&&&&&\\
\Delta&&&-\dfrac94&0&1&0&\\[7pt]
\hline
\end{array}$$
\caption{}\label{ist4}
\end{figure}

Заменяем вектор $a^4$ на $a^1$ и строим вторую симплексную таблицу (рис.~\ref{ist5}).

\begin{figure}[h]
$$\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
&c^*&&1&2&3&-4&t\\
\hline
\mbox{базис}&&x_b&a^1&a^2&a^3&a^4&\\
\hline
\vspace{-14pt}&&&&&&&\\
a^1&1&\dfrac4{13}&1&0&-\dfrac{24}{13}&\dfrac{24}{13}&
\\[7pt]
\hline
\vspace{-14pt}&&&&&&&\\
a^2&2&\dfrac{22}{13}&0&1&\mathbf{\dfrac{11}{13}}&-\dfrac{11}{13}&2\\[7pt]
\hline
\vspace{-14pt}&&&&&&&\\
z&&\dfrac{48}{13}&1&2&-\dfrac2{13}&\dfrac2{13}&\\[7pt]
\hline
\vspace{-14pt}&&&&&&&\\
\Delta&&&0&0&-\dfrac{41}{13}&\dfrac{54}{13}&\\[7pt]
\hline
\end{array}$$
\caption{}\label{ist5}
\end{figure}

Заменяем вектор $a^2$ на $a^3$ и строим третью симплексную таблицу (рис.~\ref{ist6}).

\begin{figure}[h]
$$\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
&c^*&&1&2&3&-4&t\\
\hline
\mbox{базис}&&x_b&a^1&a^2&a^3&a^4&\\
\hline
\vspace{-14pt}&&&&&&&\\
a^1&1&4&1&\dfrac{24}{11}&0&0&
\\[7pt]
\hline
\vspace{-14pt}&&&&&&&\\
a^3&3&2&0&\dfrac{13}{11}&1&-1&\\[7pt]
\hline
\vspace{-14pt}&&&&&&&\\
z&&10&1&\dfrac{63}{11}&3&-3&\\[7pt]
\hline
\vspace{-14pt}&&&&&&&\\
\Delta&&&0&\dfrac{41}{11}&0&1&\\[7pt]
\hline
\end{array}$$
\caption{}\label{ist6}
\end{figure}

Вектор $\Delta\ge0$, поэтому точка
$$\wx=(4,0,2,0)^T$$
является решением задачи, а ее значение равно $10$.
\end{example}

\section{Транспортная задача}

Рассмотрим более подробно транспортную задачу \eqref{tz}. Напомним, что речь идет о перевозке однородного груза из $n$ пунктов отправления $A_1,\ldots,A_n$ в $m$ пунктов назначения $B_1,\ldots,B_m$. Из пункта отправления $A_k$ можно увезти $a_k$ единиц груза, а в пункт назначения $B_j$ требуется доставить $b_j$ единиц груза. При этом перевозка одной единицы груза из пункта $A_k$ в пункт $B_j$ обходится в $c_{kj}$ рублей. Требуется обеспечить перевозку грузов, затратив при этом наименьшую возможную сумму денег. Обозначая через $x_{kj}$ количество груза, перевозимого из пункта $A_k$ в пункт $B_j$, получаем следующую задачу:
\begin{gather}
\sum_{k=1}^n\sum_{j=1}^mc_{kj}x_{kj}\to\min,\quad x_{kj}\ge0,\ k=1,\ldots,n,\ j=1,\ldots,m,\label{tz1}\\
\sum_{j=1}^mx_{kj}=a_k,\ k=1,\ldots,n,\label{tz2}\\
\sum_{k=1}^nx_{kj}=b_j,\ j=1,\ldots,m.\label{tz3}
\end{gather}
Введя обозначения
\begin{align}
c^*&=(c_{11},c_{12},\ldots,c_{1m},\ldots,c_{n1},c_{n2},\ldots,c_{nm}),\notag\\ x&=(x_{11},x_{12},\ldots,x_{1m},\ldots,x_{n1},x_{n2},\ldots,x_{nm})^T,\notag\\
\setcounter{MaxMatrixCols}{20}
A&=\begin{pmatrix}
1&1&\ldots&1&0&0&\ldots&0&\ldots&0&0&\ldots&0\\
0&0&\ldots&0&1&1&\ldots&1&\ldots&0&0&\ldots&0\\
\hdotsfor{13}\\
0&0&\ldots&0&0&0&\ldots&0&\ldots&1&1&\ldots&1\\
1&0&\ldots&0&1&0&\ldots&0&\ldots&1&0&\ldots&0\\
0&1&\ldots&0&0&1&\ldots&0&\ldots&0&1&\ldots&0\\
\hdotsfor{13}\\
0&0&\ldots&1&0&0&\ldots&1&\ldots&0&0&\ldots&1
\end{pmatrix},\label{AA}\\
\ov b&=(a_1,a_2.\ldots,a_n,b_1,b_2,\ldots,b_m)^T,\notag
\end{align}
мы записывали задачу \eqref{tz1}--\eqref{tz3} в канонической форме
\begin{equation}\label{tk}
c^*\cdot x\to\min,\quad Ax=\ov b,\quad x\ge0.
\end{equation}
Всякий допустимый вектор в этой задаче мы называем допустимым планом перевозок, а решение транспортной задачи называется оптимальным планом перевозок.

Из условий \eqref{tz2}, \eqref{tz3} вытекает, что
$$\sum_{k=1}^n\sum_{j=1}^mx_{kj}=\sum_{k=1}^na_k=\sum_{j=1}^mb_j=M.$$
Иными словами, общий запас груза на всех пунктах отправления равен суммарной потребности всех пунктов назначения. В этом случае говорят, что имеется замкнутая модель транспортной задачи.

Можно рассматривать незамкнутые модели транспортной задачи. Покажем, что они могут быть сведены к замкнутой модели.

Пусть суммарные запасы отправителей больше суммарных потребностей пунктов назначения, т.е.
$$\sum_{k=1}^na_k>\sum_{j=1}^mb_j.$$
В этом случае равенства \eqref{tz2} заменяются неравенствами
$$\sum_{j=1}^mx_{kj}\le a_k,\ k=1,\ldots,n.$$
Введем фиктивный пункт назначения $B_{m+1}$ с величиной завоза
$$b_{m+1}=\sum_{k=1}^na_k-\sum_{j=1}^mb_j$$
и нулевыми стоимостями перевозок в этот пункт. Добавляя новые неотрицательные переменные $x_{k,m+1}$, $k=1,\ldots,n$, получаем замкнутую модель транспортной задачи с ограничениями в виде равенств
\begin{gather*}
\sum_{j=1}^{m+1}x_{kj}=a_k,\ k=1,\ldots,n,\\
\sum_{k=1}^nx_{kj}=b_j,\ j=1,\ldots,m+1.
\end{gather*}

Пусть теперь суммарные запасы отправителей меньше суммарных потребностей пунктов назначения, т.е.
$$\sum_{k=1}^na_k<\sum_{j=1}^mb_j.$$
Тогда равенства \eqref{tz3} заменяются неравенствами
$$\sum_{k=1}^nx_{kj}\le b_j,\ j=1,\ldots,m.$$
В этом случае вводится фиктивный пункт отправления $A_{n+1}$ с величиной вывоза
$$a_{n+1}=\sum_{j=1}^mb_j-\sum_{k=1}^na_k$$
и нулевыми стоимостями перевозок из этого пункта. Добавляя новые неотрицательные переменные $x_{n+1,j}$, $j=1,\ldots,m$, получаем замкнутую модель транспортной задачи с ограничениями в виде равенств
\begin{gather*}
\sum_{j=1}^mx_{kj}=a_k,\ k=1,\ldots,n+1,\\
\sum_{k=1}^{n+1}x_{kj}=b_j,\ j=1,\ldots,m.
\end{gather*}

\section{Свойства транспортной задачи}

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

\begin{lemma}\label{L1}
Для любой транспортной задачи существует допустимый план перевозок.
\end{lemma}

\begin{proof}
Без ограничения общности можно считать, что рассматривается замкнутая модель транспортной задачи. Положим
$$x_{kj}=\frac{a_kb_j}M.$$
Тогда
\begin{gather*}
\sum_{j=1}^mx_{kj}=\sum_{j=1}^m\frac{a_kb_j}M=\frac{a_k}M\sum_{j=1}^mb_j=\frac{a_k}MM=a_k,\\
\sum_{k=1}^nx_{kj}=\sum_{k=1}^n\frac{a_kb_j}M=\frac{b_j}M\sum_{k=1}^na_k=\frac{b_j}MM=b_j.
\end{gather*}
Тем самым $x_{jk}$ --- допустимый план перевозок.
\end{proof}

\begin{lemma}
Для любой транспортной задачи существует оптимальный план перевозок.
\end{lemma}

\begin{proof}
В силу леммы~\ref{L1} и того, что значение транспортной задачи ограничено снизу нулем, это значение конечно. По теореме существования (теорема~\ref{exi}), учитывая, что различные формы задач линейного программирования эквивалентны, получаем существование оптимального плана в любой транспортной задаче.
\end{proof}

\begin{lemma}
$\rg A=n+m-1$.
\end{lemma}

\begin{proof}
Прибавим к $n$-ой строке матрицы $A$ все предыдущие. Получим строку, состоящую из единиц. Прибавим в этой матрице к последней строке все строки, начиная с $n+1$-ой. Получим такую же строку. Следовательно, $\rg A\le n+m-1$.

Переставим строки, начиная со второй по $n$-ую, после последней строки матрицы $A$. Тогда, если в новой матрице взять строки со второй по последнюю и столбцы $1,\ldots,m,m+1,2m+1,\ldots,(n-1)m+1$, то получится минор порядка $n+m-1$, являющийся треугольной матрицей с единицами на главной диагонали. Тем самым $\rg A=n+m-1$.
\end{proof}

Из доказанной леммы и предложения~\ref{Predk} вытекает, что крайняя точка в рассматриваемой транспортной задаче может иметь не более $n+m-1$ положительных координат.

\begin{lemma}\label{L4}
Любые $n+m-1$ строк матрицы $A$ линейно независимы.
\end{lemma}

\begin{proof}
Как было отмечено, сумма первых $n$ строк совпадает с суммой оставшихся строк. Это означает, что любая строка есть линейная комбинация оставшихся $n+m-1$ строк. В силу того, что $\rg A=n+m-1$, эти оставшиеся строки линейно независимы.
\end{proof}

\section{Методы нахождения начальной крайней точки в транспортной задаче}

Будем рассматривать замкнутую модель транспортной задачи. Как было показано, незамкнутая модель легко сводится к замкнутой введением фиктивного поставщика или фиктивного потребителя.

Исходную транспортную задачу будем задавать в виде платежной матрицы (рис.~\ref{tt1}).

\begin{figure}[h]
$$\begin{array}{|c|c|c|c|c|}
\hline
&b_1&b_2&\ldots&b_m\\
\hline
a_1&c_{11}&c_{12}&\ldots&c_{1m}\\
\hline
a_2&c_{21}&c_{22}&\ldots&c_{2m}\\
\hline
\ldots&\ldots&\ldots&\ldots&\ldots\\
\hline
a_n&c_{n1}&c_{n2}&\ldots&c_{nm}\\
\hline
\end{array}$$
\caption{}\label{tt1}
\end{figure}


Для составления матрицы плана перевозок удобно использовать следующую таблицу (рис.~\ref{tt2}).

\begin{figure}[h]
$$\begin{array}{|c|c|c|c|c|}
\hline
&b_1&b_2&\ldots&b_m\\
\hline
a_1&x_{11}&x_{12}&\ldots&x_{1m}\\
\hline
a_2&x_{21}&x_{22}&\ldots&x_{2m}\\
\hline
\ldots&\ldots&\ldots&\ldots&\ldots\\
\hline
a_n&x_{n1}&x_{n2}&\ldots&x_{nm}\\
\hline
\end{array}$$
\caption{}\label{tt2}
\end{figure}

\bigskip

{\bf 1. Метод ``северно-западного угла''}

\bigskip

Назначим максимально возможную перевозку из пункта отправления $A_1$ в пункт назначения $B_1$. То есть заполняем верхний левый элемент ($x_{11}$) матрицы $X=\{x_{kj}\}$ плана перевозок так, чтобы пункт отправления $A_1$, либо пункт назначения $B_1$, либо оба эти пункта окажутся полностью обслуженными.

Если пункт отправления $A_1$ оказался полностью обслуженным, то в дальнейшем при нахождении первоначального плана перевозок выводим первую строку матрицы $X$ из рассмотрения и рассматриваем только оставшуюся часть матрицы $X$. Если пункт назначения $B_1$ оказался полностью обслуженным, то аналогично выводим первый столбец из дальнейшего рассмотрения. Если же и пункт отправления, и
пункт назначения оказались полностью обслуженными (так может случиться только в вырожденной задаче), то вывести из рассмотрения следует или первую строку, или первый столбец матрицы $X$. Для определенности будем выводить первый столбец матрицы $X$. В этом случае в число базисных элементов на следующем этапе введем элемент с нулевым значением перевозки, стоящий в северо-западном углу оставшейся части матрицы $X$ ($x_{12}=0$).

Эту процедуру продолжаем до тех пор, пока все пункты отправления и пункты назначения не будут обслужены. Последней перевозкой будет перевозка из пункта отправления $A_n$ в пункт назначения $B_m$.

На каждом шаге обслуживается один из пунктов отправления или назначения, а на последнем шаге обслуживаются оба пункта $A_n$ и $B_m$. Поэтому число базисных элементов будет ровно $n+m-1$. Найденный план будет допустимым планом перевозок, содержащим не более $n+m-1$ положительных координат и являющийся (как будет показано ниже) крайней точкой множества допустимых элементов.

\begin{example}\label{primer}
Зададим транспортную задачу в виде платежной матрицы (рис.~\ref{tp1}).

\begin{figure}[h]
$$\begin{array}{|c|c|c|c|c|}
\hline
&b_1=40&b_2=15&b_3=42&b_4=13\\
\hline
a_1=10&2&1&5&11\\
\hline
a_2=80&4&3&4&2\\
\hline
a_3=20&6&2&7&8\\
\hline
\end{array}$$
\caption{}\label{tp1}
\end{figure}

Построим по методу ``северо-западного угла'' первоначальный план перевозок. Назначим максимально возможную перевозку, равную $10$, из пункта отправления $A_1$ в пункт назначения $B_1$. То есть в матрице первоначального плана перевозок $X$ положим $x_{11}=10$. При этом из пункта отправления $A_1$ весь груз окажется вывезенным, поэтому $x_{12}=x_{13}=x_{14}=0$. Выводим из рассмотрения первую строку матрицы $X$ и рассматриваем только оставшуюся матрицу размера $2\times4$.

В пункт назначения $B_1$ остается привезти $30$ единиц груза. Назначим максимально возможную перевозку, равную $30$, из пункта отправления $A_2$ в пункт назначения $B_1$. Тем самым $x_{21}=30$. При этом пункт  назначения $B_1$ окажется полностью обслуженным, поэтому $x_{31}=0$. Выводим из рассмотрения первый столбец матрицы и рассматриваем только оставшуюся матрицу размера $2\times3$.

Далее, назначаем максимально возможную перевозку, равную $15$, из пункта отправления $A_2$ в пункт назначения $B_2$. Тем самым $x_{22}=15$, а $x_{32}=0$, так как пункт назначения $B_2$ оказывается полностью обслуженным. Продолжая этот процесс, приходим к матрице первоначального плана перевозок, в которой для наглядности не будем писать нулевые значения (рис.~\ref{tp2}).

\begin{figure}[h]
$$\begin{array}{|c|c|c|c|c|}
\hline
&b_1=40&b_2=15&b_3=42&b_4=13\\
\hline
a_1=10&10&&&\\
\hline
a_2=80&30&15&35&\\
\hline
a_3=20&&&7&13\\
\hline
\end{array}$$
\caption{}\label{tp2}
\end{figure}

Общая стоимость перевозок по такому начальному плану равна
$$c^*\cdot x=2\cdot10+4\cdot30+3\cdot15+4\cdot35+7\cdot7+8\cdot13=478.$$
\end{example}

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

\bigskip

{\bf2. Минимум по матрице}

\bigskip

Выберем в платежной матрице $C$ минимальный элемент. Пусть
$$\min_{k,j}c_{kj}=c_{k_0j_0}.$$
Если минимальная стоимость перевозки достигается на нескольких элементах, то выбираем любой из них. Назначим максимально возможную перевозку из пункта отправления $A_{k_0}$ в пункт назначения $B_{j_0}$. Тем самым пункт отправления $A_{k_0}$ или пункт назначения $B_{j_0}$ (или оба пункта одновременно) будет обслужен. В платежной матрице соответствующая строка или столбец выводятся из дальнейшего рассмотрения. Если и пункт отправления, и пункт назначения одновременно обслужились, то для определенности будем выводить из рассмотрения столбец матрицы $X$.

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

\begin{example}
Зададим транспортную задачу в виде той же платежной матрицы, которая была на рис.~\ref{tp1}. Выберем в платежной матрице $C$ минимальный элемент. Им является стоимость $c_{12}=1$. Назначим максимально возможную перевозку, равную $10$, из из пункта отправления $A_1$ в пункт назначения $B_2$. При этом из пункта отправления $A_1$ весь груз окажется вывезенным. В платежной матрице первая строка выводится из дальнейшего рассмотрения.

В оставшейся части платежной матрицы $2\times4$ вновь ищется минимальный элемент. Минимальная стоимость перевозки достигается на двух элементах $c_{32}=c_{24}=2$. Выбираем любой из них. Для определенности $c_{32}$. Назначим максимально возможную перевозку, равную $5$, из пункта отправления $A_3$ в пункт назначения $B_2$. При этом пункт назначения $B_2$ окажется полностью обслуженным. В платежной матрице $2\times4$ второй столбец выводится из дальнейшего рассмотрения.

В оставшейся части платежной матрицы $2\times3$ вновь ищется минимальный элемент. Им является стоимость $c_{24}=2$. Назначим максимально возможную перевозку, равную $13$, из из пункта отправления $A_2$ в пункт назначения $B_4$. При этом пункт назначения $B_4$ окажется полностью обслуженным. В платежной матрице последний столбец выводится из дальнейшего рассмотрения.

Продолжая этот процесс, придем к начальному плану перевозок, отображенному на рис.~\ref{tp3}.

\begin{figure}[h]
$$\begin{array}{|c|c|c|c|c|}
\hline
&b_1=40&b_2=15&b_3=42&b_4=13\\
\hline
a_1=10&&10&&\\
\hline
a_2=80&40&&27&13\\
\hline
a_3=20&&5&15&\\
\hline
\end{array}$$
\caption{}\label{tp3}
\end{figure}

Общая стоимость перевозок по такому начальному плану равна
$$c^*\cdot x=1\cdot10+2\cdot5+2\cdot13+4\cdot40+4\cdot27+7\cdot15=419.$$
Метод ``минимума по матрице'', учитывающий стоимости перевозок в данном примере оказался более эффективным по сравнению с методом ``северо-западного угла''.
\end{example}

\bigskip

{\bf3. Минимум по строке}

\bigskip

Выберем в первой строке платежной матрицы $C$ минимальный элемент. Пусть
$$\min_jc_{1j}=c_{1j_0}.$$
Если минимум достигается на нескольких элементах, то выбираем любой из них. Назначим максимально возможную перевозку из пункта отправления $A_1$ в пункт назначения $B_{j_0}$. Тем самым пункт отправления $A_1$ или пункт назначения $B_{j_0}$ (или оба пункта одновременно) будет обслужен. В платежной матрице соответствующая строка или столбец выводятся из дальнейшего рассмотрения. Если и пункт отправления, и пункт назначения одновременно обслужились, то для определенности будем выводить из рассмотрения столбец матрицы $X$.

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

\begin{example}
Зададим транспортную задачу в виде той же платежной матрицы, которая была на рис.~\ref{tp1}. Выберем в в первой строке платежной матрицы $C$ минимальный элемент. Им является стоимость $c_{12}=1$. Назначим максимально возможную перевозку, равную $10$, из из пункта отправления $A_1$ в пункт назначения $B_2$. При этом из пункта отправления $A_1$ весь груз окажется вывезенным. В платежной матрице первая строка выводится из дальнейшего рассмотрения.

В первой строке оставшейся части платежной матрицы $2\times4$ вновь ищется минимальный элемент. Минимальная стоимость перевозки достигается на $c_{24}=2$. Назначим максимально возможную перевозку, равную $13$, из из пункта отправления $A_2$ в пункт назначения $B_4$. При этом пункт назначения $B_4$ окажется полностью обслуженным. В платежной матрице $2\times4$ последний столбец выводится из дальнейшего рассмотрения.

В первой строке оставшейся части платежной матрицы $2\times3$ вновь ищется минимальный элемент. Им является стоимость $c_{22}=3$. Назначим максимально возможную перевозку, равную $5$, из пункта отправления $A_2$ в пункт назначения $B_2$. При этом пункт назначения $B_2$ окажется полностью обслуженным. В платежной матрице второй столбец выводится из дальнейшего рассмотрения.

Продолжая этот процесс, придем к начальному плану перевозок, отображенному на рис.~\ref{tp4}.

\begin{figure}[h]
$$\begin{array}{|c|c|c|c|c|}
\hline
&b_1=40&b_2=15&b_3=42&b_4=13\\
\hline
a_1=10&&10&&\\
\hline
a_2=80&40&5&22&13\\
\hline
a_3=20&&&20&\\
\hline
\end{array}$$
\caption{}\label{tp4}
\end{figure}

Общая стоимость перевозок по такому начальному плану равна
$$c^*\cdot x=1\cdot10+2\cdot13+3\cdot5+4\cdot40+4\cdot22+7\cdot20=439.$$
\end{example}

\newpage

{\bf4. Минимум по столбцу}

\bigskip

Метод аналогичен предыдущему, но вместо строк рассматриваются столбцы.

\begin{example}
Зададим транспортную задачу в виде той же платежной матрицы, которая была на рис.~\ref{tp1}. Выберем в в первом столбце платежной матрицы $C$ минимальный элемент. Им является стоимость $c_{11}=2$. Назначим максимально возможную перевозку, равную $10$, из из пункта отправления $A_1$ в пункт назначения $B_1$. При этом из пункта отправления $A_1$ весь груз окажется вывезенным. В платежной матрице первая строка выводится из дальнейшего рассмотрения.

В первом стролбце оставшейся части платежной матрицы $2\times4$ вновь ищется минимальный элемент. Минимальная стоимость перевозки достигается на $c_{21}=4$. Назначим максимально возможную перевозку, равную $30$, из из пункта отправления $A_2$ в пункт назначения $B_1$. При этом пункт назначения $B_1$ окажется полностью обслуженным. В платежной матрице $2\times4$ первый столбец выводится из дальнейшего рассмотрения.

В первой солбце оставшейся части платежной матрицы $2\times3$ вновь ищется минимальный элемент. Им является стоимость $c_{32}=2$. Назначим максимально возможную перевозку, равную $15$, из пункта отправления $A_3$ в пункт назначения $B_2$. При этом пункт назначения $B_2$ окажется полностью обслуженным. В платежной матрице второй столбец выводится из дальнейшего рассмотрения.

Продолжая этот процесс, придем к начальному плану перевозок, отображенному на рис.~\ref{tp5}.

\begin{figure}[h]
$$\begin{array}{|c|c|c|c|c|}
\hline
&b_1=40&b_2=15&b_3=42&b_4=13\\
\hline
a_1=10&10&&&\\
\hline
a_2=80&30&&42&8\\
\hline
a_3=20&&15&&5\\
\hline
\end{array}$$
\caption{}\label{tp5}
\end{figure}

Общая стоимость перевозок по такому начальному плану равна
$$c^*\cdot x=2\cdot10+4\cdot30+2\cdot15+4\cdot42+2\cdot8+8\cdot5=394.$$
Метод ``минимума по столбцу'' в данном примере оказался наиболее эффективным по сравнению с другими методами.
\end{example}

\begin{proposition}
Описанные выше методы нахождения первоначального плана перевозок приводят к первоначальной крайней точке множества допустимых элементов.
\end{proposition}

\begin{proof}
Из предложения~\ref{Predk} следует, что достаточно доказать, что столбцы матрицы $A$, соответствующие базисным элементам, линейно независимы.

Отметим, что во всех описанных методах на каждом этапе мы выводим из рассмотрения либо столбец, либо строку матрицы $X$.

Доказательство проведем индукцией по $n+m=k$. При $n+m=2$ матрица $A$ состоит из одного столбца и утверждение предложения очевидно. Предположим, что для $n+m=k$ столбцы, получаемые этими методами столбцы линейно независимы. Докажем соответствующее утверждение для $n+m=k+1$. Не ограничивая общности можно считать, что на первом этапе из рассмотрения выводится первая строка или первый столбец (в противном случае мы можем строки или столбцы переобозначить).

Если мы выводим из рассмотрения первую строку матрицы, то это означает, что первый пункт отправления $A_1$ обслужен полностью, $x_{11}$ --- базисный элемент, а $x_{1k}=0$, $k=2,\ldots,m$. Первое ограничение уравнений \eqref{tz2} выполнено. Поэтому в матрице ограничений $A$ можно убрать первую строку и первые $m$ столбцов. Для новой матрицы по предположению индукции полученные любым из рассмотренных методов базисные элементы стоят в $n+m-2$ линейно независимых столбцах. Добавление столбца с единицей на первом месте (и еще на одном) к $n+m-2$ линейно независимым столбцам с расширением и добавлением нуля на первое место к каждому из этих столбцов приводит к системе из $n+m-1$ линейно независимых столбцов.

Если мы выводим из рассмотрения первый столбец матрицы, то это означает, что первый пункт назначения $B_1$ обслужен полностью, $x_{11}$ --- базисный элемент, а $x_{j1}=0$, $j=2,\ldots,n$. Первое ограничение уравнений \eqref{tz3} выполнено. Поэтому в матрице ограничений $A$ можно убрать $n+1$ строку и еще $m$ столбцов. Для новой матрицы по предположению индукции полученные любым из рассмотренных методов базисные элементы стоят в $n+m-2$ линейно независимых столбцах. Добавление столбца с единицей на $n+1$ месте (и еще на одном) к $n+m-2$ линейно независимым столбцам с расширением и добавлением нуля на $n+1$ место к каждому из этих столбцов приводит к системе из $n+m-1$ линейно независимых столбцов.
\end{proof}

\section{Задача, двойственная к транспортной задаче. Метод потенциалов}

Пользуясь записью транспортной задачи в канонической форме \eqref{tk} и видом двойственной ей задачи (см. \eqref{lpk1}), получаем задачу, двойственную к транспортной:
$$y^*\cdot\ov b\to\max,\quad y^*A\le c^*.$$
Если положить
$$y^*=(u_1,\ldots,u_n,v_1,\ldots,v_m),$$
то двойственная задача может быть переписана в виде:
\begin{equation}\label{dt}
\begin{gathered}
\sum_{k=1}^nu_ka_k+\sum_{j=1}^mv_jb_j\to\max,\\
u_k+v_j\le c_{kj},\quad k=1,\ldots,n,\ j=1,\ldots,m.
\end{gathered}
\end{equation}

Двойственные переменные $u=(u_1,\ldots,u_n)$ и $v=(v_1,\ldots,v_m)$ называются потенциалами.

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

Пусть для исходной транспортной задачи найден первоначальный план перевозок $x$, являющийся крайней точкой множества допустимых значений. Он содержит $n+m-1$ неотрицательных компонент, которые мы называем базисными (при его нахождении можно использовать любой из описанных выше методов). Индексы $(k,j)$ соответствующие базисным компонентам будем называть базисными индексами. Множество базисных индексов $(k,j)$ обозначим через $B$.

Рассмотрим систему из $n+m-1$ уравнений для определения $n+m$ потенциалов $u_k$, $v_j$:
\begin{equation}\label{pot}
u_k+v_j=c_{kj},\quad (k,j)\in B.
\end{equation}
Строки матрицы этой системы (если расположить неизвестные в порядке $u_1,u_2,\ldots,u_n,v_1,v_2,\ldots,v_m$) совпадают с базисными столбцами и поэтому линейно независимы. Из доказательства леммы~\ref{L4} следует, что любой столбец системы \eqref{pot} есть линейная комбинация остальных. Отсюда вытекает, что любую неизвестную в системе \eqref{pot} можно принять за свободную неизвестную, а остальные тогда однозначно выразятся через нее. Положим, например, $u_1=0$. Тогда остальные $n+m-1$ потенциалов определятся однозначно.

Положим $\ov C=\{\ov c_{kj}\}$, где $\ov c_{kj}=u_k+v_j$, $k=1,\ldots,n$, $j=1,\ldots,m$, а матрицу $\Delta$ определим следующим образом: $\Delta=C-\ov C$.

\begin{theorem}\label{TP1}
Если $x$ --- крайняя точка в транспортной задаче и $\Delta\ge0$, то $x$ является решением транспортной задачи.
\end{theorem}

\begin{proof}
Условие $\Delta\ge0$ означает, что найдены потенциалы $u_k$ и $v_j$ такие, что
$$u_k+v_j\le c_{kj},\quad k=1,\ldots,n,\ j=1,\ldots,m,$$
причем $u_k+v_j=c_{kj}$ при $(k,j)\in B$. Таким образом, вектор $(u_1,\ldots,u_n,v_1,\ldots,v_m)$ является допустимым в двойственной задаче \eqref{dt}.

С другой стороны, поскольку $x_{kj}=0$ при $(k,j)\notin B$, то
\begin{multline*}
c^*\cdot x=\sum_{k=1}^n\sum_{j=1}^mc_{kj}x_{kj}=\sum_{(k,j)\in B}c_{kj}x_{kj}=\sum_{(k,j)\in B}(u_k+v_j)x_{kj}\\
=\sum_{k=1}^n\sum_{j=1}^m(u_k+v_j)x_{kj}.
\end{multline*}
Разбивая последнюю сумму на две и учитывая условия \eqref{tz2} и \eqref{tz3}, получаем
\begin{multline*}
c^*\cdot x=\sum_{k=1}^n\sum_{j=1}^mu_kx_{kj}+\sum_{k=1}^n\sum_{j=1}^mv_jx_{kj}=
\sum_{k=1}^nu_k\sum_{j=1}^mx_{kj}+\sum_{j=1}^mv_j\sum_{k=1}^nx_{kj}\\
=\sum_{k=1}^nu_ka_k+\sum_{j=1}^mv_jb_j.
\end{multline*}
Отсюда из следствия~\ref{corr} вытекает, что $x$ --- решение исходной задачи, а $(u,v)$ --- решение в двойственной задаче.
\end{proof}

Условие $\Delta\ge0$ является не только достаточным, но и необходимым для невырожденных транспортных задач. Для доказательства этого факта нам потребуются некоторые вспомогательные утверждения.

\begin{lemma}\label{LA}
Любой минор матрицы $A$ \eqref{AA} равен либо $0$, либо $\pm1$.
\end{lemma}

\begin{proof}
Доказательство проведем с помощью индукции по порядку миноров. Для миноров порядка $1$ утверждение леммы очевидно. Предположим, что утверждение доказано для всех миноров $A$ порядка $k-1$. Докажем справедливость утверждения леммы для миноров порядка $k$. Разделим строки матрицы $A$ на две группы: первые $n$ строк отнесем к первой группе, а последующие $m$ строк --- ко второй. Пусть $\Delta_k$ --- произвольный минор порядка $k$. Каждый столбец $\Delta_k$ может содержать либо две единицы, либо одну единицу, либо сплошь состоять из нулей. В последнем случае очевидно, что $\Delta_k=0$. Пусть каждый столбец $\Delta_k$ содержит хотя бы одну единицу. Тогда возможны два случая:
\begin{itemize}
\item[a)] хотя бы в одном столбце $\Delta_k$ содержится одна единица,
\item[б)] во всех столбцах $\Delta_k$ содержится ровно две единицы.
\end{itemize}

В случае а) выберем столбец, содержащий одну единицу и разложим по нему исследуемый минор. Получим, что $\Delta_k=\pm\Delta_{k-1}'$, где $\Delta_{k-1}'$ --- некоторый минор $A$ порядка $k-1$. Из предположения индукции вытекает, что $\Delta_k$ равен либо $0$, либо $\pm1$.

В случае б) среди строк $\Delta_k$ имеются представители как первой, так и второй групп строк. Возьмем любую строку $\Delta_k$, принадлежащую первой группе, и прибавим к ней все остальные строки из этой же группы. Получим строку, содержащую все единицы. Аналогично, прибавляя к любой строке второй группы все остальные строки из этой же группы, снова получим строку, состоящую из всех единиц. Поэтому в рассматриваемом случае $\Delta_k=0$.
\end{proof}

\begin{lemma}\label{Lt}
Для любых $(k_0,j_0)\notin B$ существует вектор $\ov t=\{t_{kj}\}$ такой, что $A\ov t=0$ и
$$t_{kj}=\begin{cases}\pm1\mbox{ или }0,&(k,j)\in B,\\
1,&(k,j)=(k_0,j_0),\\
0,&\mbox{ в остальных случаях}.\end{cases}$$
\end{lemma}

\begin{proof}
Вектор $\ov t$ должен удовлетворять системе
$$\sum_{(k,j)\in B}A_{kj}t_{kj}=-A_{k_0j_0},$$
где $A_{kj}$ --- соответствующий столбец матрицы $A$. Выбрав $n+m-1$ линейно независимых строк в этой системе (что возможно сделать, так как $\rg A=n+m-1$), получим систему с невырожденной матрицей $\tilde A$
$$\tilde A\tilde t=-b,$$
где $\tilde t=\{t_{kj}\}$, $(k,j)\in B$, а столбец $b$ --- получен из столбца $A_{k_0j_0}$ выбором соответствующих строк. Решая эту систему по правилу Крамера, будем иметь
$$t_{kj}=\frac{|\tilde A_{kj}|}{|\tilde A|},$$
где матрица $\tilde A_{kj}$ получена из матрицы $\tilde A$ заменой столбца $(k,j)$ на столбец $b$. Из леммы~\ref{LA} следует, что $|\tilde A|=\pm1$. Матрица $\tilde A_{kj}$ с точностью до знака и перестановки столбцов также является некоторым минором $A$. Поэтому определитель этой матрицы равен $0$ или $\pm1$.
\end{proof}

\begin{theorem}\label{TP2}
Если $x$ --- крайняя точка в транспортной задаче с $n+m-1$ положительными компонентами и
$$\min_{k,j}\Delta_{kj}<0,$$
то существует план $\wx$ такой, что $c^*\cdot\wx<c^*\cdot x$.
\end{theorem}

\begin{proof}
Пусть
$$\min_{k,j}\Delta_{kj}=\Delta_{k_0j_0}.$$
Положим $\wx=x+t\tilde t$, где $\tilde t$ из леммы~\ref{Lt}. Выберем $t>0$ достаточно малым, чтобы $x+t\tilde t\ge0$ (в качестве $t$ можно выбрать минимальное $x_{jk}$ из тех, для которых соответствующие $t_{kj}=-1$). Тогда $x+t\tilde t$ --- допустимый элемент в задаче и в силу того, что
$$c_{kj}=\Delta_{kj}+\ov c_{jk}=\Delta_{kj}+u_k+v_j,$$
имеют место равенства
\begin{multline*}
c^*\cdot\wx-c^*x=t\sum_{k=1}^nu_k\sum_{j=1}^m(\Delta_{kj}+u_k+v_j)t_{kj}=
t\sum_{k=1}^nu_k\sum_{j=1}^m\Delta_{kj}t_{kj}\\
+t\sum_{k=1}^nu_k\sum_{j=1}^mt_{kj}+t\sum_{j=1}^mv_j\sum_{k=1}^nt_{kj}=t\Delta_{k_0j_0}<0.
\end{multline*}
Последние два слагаемые в этой сумме равны нулю в силу того, что $A\tilde t=0$. Слагаемые $\Delta_{kj}t_{kj}=0$ при $(k,j)\ne(k_0,j_0)$, так как $\Delta_{kj}=0$ при $(k,j)\in B$, а $t_{kj}=0$ при $(k,j)\notin B$ и $(k,j)\ne(k_0,j_0)$.
\end{proof}

Из теорем~\ref{TP1} и \ref{TP2} непосредственно вытекает

\begin{corollary}
Крайняя точка $x$ является решением в невырожденной транспортной задаче тогда и только тогда, когда $\Delta\ge0$.
\end{corollary}

\section{Алгоритм решения транспортной задачи с помощью метода потенциалов}

Сформулируем правило решения транспортной задачи методом потенциалов. Для решения транспортной задачи следует:

\begin{itemize}
\item[1.] Привести задачу к замкнутой модели.
\item[2.] Найти первоначальный план перевозок $x$, являющийся крайней точкой множества допустимых точек (при нахождении можно использовать любой из описанных выше методов).
\item[3.] Найти потенциалы $u_k$, $v_j$ из системы \eqref{pot} и построить матрицу $\ov C=\{\ov c_{kj}\}$, где $\ov c_{kj}=u_k+v_j$, $k=1,\ldots,n$, $j=1,\ldots,m$.
\item[4.] Провести исследование матрицы $\Delta=C-\ov C$. Если $\Delta\ge0$, то исследуемый план $x$ является решением.
\item[5.] Если
$$\min_{k,j}\Delta_{kj}=\Delta_{k_0j_0}<0,$$
то строить новый план перевозок следующим образом: положим $x'_{k_0j_0}=t$, $x'_{kj}=x_{kj}\pm t$ или $x_{kj}$ для базисных индексов $j,k$ так, чтобы $x'_{kj}$ по-прежнему были неотрицательны, но одна из базисных компонент обратилась бы в ноль. Вектор матрицы $A$, соответствующий этой компоненте, выводится из числа базисных, а вектор матрицы $A$, соответствующий индексам $k_0,j_0$ вводится в число базисных векторов. Затем вновь начинается исследование полученной крайней точки $x'$, т.е. переходим к п.~3.

В невырожденной задаче в ноль может обратиться только одна из компонент вектора $x'$. В вырожденной задаче таковых может быть несколько. В этом случае из числа базисных элементов исключается любая компонента с нулевым значением, как правило исключается компонента с наибольшей стоимостью перевозок.
\end{itemize}

\begin{example}
Рассмотрим транспортную задачу из примера \ref{primer}.

\begin{figure}[h]
$$\begin{array}{|c|c|c|c|c|}
\hline
&b_1=40&b_2=15&b_3=42&b_4=13\\
\hline
a_1=10&2&1&5&11\\
\hline
a_2=80&4&3&4&2\\
\hline
a_3=20&6&2&7&8\\
\hline
\end{array}$$
\caption{}\label{pr}
\end{figure}

Выберем в качестве начального плана тот, который получался по методу ``северо-западного угла''.

\begin{figure}[h]
$$\begin{array}{|c|c|c|c|c|}
\hline
&b_1=40&b_2=15&b_3=42&b_4=13\\
\hline
a_1=10&10&&&\\
\hline
a_2=80&30&15&35&\\
\hline
a_3=20&&&7&13\\
\hline
\end{array}$$
\caption{}\label{pr1}
\end{figure}

Найдем потенциалы и построим матрицу $\ov C$.

\begin{figure}[h]
$$\begin{array}{|c|c|c|c|c|}
\hline
&v_1=2&v_2=1&v_3=2&v_4=3\\
\hline
u_1=0&\bf2&1&2&3\\
\hline
u_2=2&\bf4&\bf3&\bf4&5\\
\hline
u_3=5&7&6&\bf7&\bf8\\
\hline
\end{array}$$
\caption{}\label{pr2}
\end{figure}

Имеем
$$\Delta=C-\ov C=\begin{pmatrix}
0&0&3&8\\
0&0&0&-3\\
-1&-4&0&0
\end{pmatrix}
$$
Минимальный элемент $\Delta_{32}=-4<0$. Добавляя в первоначальный план на место нулевого небазисного элемента $x_{32}$ величину $t$, получим

\begin{figure}[h]
$$\begin{array}{|c|c|c|c|c|}
\hline
&b_1=40&b_2=15&b_3=42&b_4=13\\
\hline
a_1=10&10&&&\\
\hline
a_2=80&30&15-t&35+t&\\
\hline
a_3=20&&t&7-t&13\\
\hline
\end{array}$$
\caption{}\label{pr3}
\end{figure}

Положив $t=7$, получим второй план перевозок (рис.~\ref{pr4}).

\begin{figure}[h]
$$\begin{array}{|c|c|c|c|c|}
\hline
&b_1=40&b_2=15&b_3=42&b_4=13\\
\hline
a_1=10&10&&&\\
\hline
a_2=80&30&8&42&\\
\hline
a_3=20&&7&&13\\
\hline
\end{array}$$
\caption{}\label{pr4}
\end{figure}

Значение минимизируемого функционала для этого плана $450$ (на первоначальном плане оно было $479$).

Найдем вновь потенциалы и построим матрицу $\ov C$.

\begin{figure}[h]
$$\begin{array}{|c|c|c|c|c|}
\hline
&v_1=2&v_2=1&v_3=2&v_4=7\\
\hline
u_1=0&\bf2&1&2&7\\
\hline
u_2=2&\bf4&\bf3&\bf4&9\\
\hline
u_3=1&3&\bf2&3&\bf8\\
\hline
\end{array}$$
\caption{}\label{pr5}
\end{figure}

Имеем
$$\Delta=C-\ov C=\begin{pmatrix}
0&0&3&4\\
0&0&0&-7\\
3&0&4&0
\end{pmatrix}
$$
Минимальный элемент $\Delta_{24}=-7<0$. Добавляя в первоначальный план на место нулевого небазисного элемента $x_{24}$ величину $t$, получим

\begin{figure}[h]
$$\begin{array}{|c|c|c|c|c|}
\hline
&b_1=40&b_2=15&b_3=42&b_4=13\\
\hline
a_1=10&10&&&\\
\hline
a_2=80&30&8-t&42&t\\
\hline
a_3=20&&7+t&&13-t\\
\hline
\end{array}$$
\caption{}\label{pr6}
\end{figure}

Положив $t=8$, получим третий план перевозок (рис.~\ref{pr7}).

\begin{figure}[h]
$$\begin{array}{|c|c|c|c|c|}
\hline
&b_1=40&b_2=15&b_3=42&b_4=13\\
\hline
a_1=10&10&&&\\
\hline
a_2=80&30&&42&8\\
\hline
a_3=20&&15&&5\\
\hline
\end{array}$$
\caption{}\label{pr7}
\end{figure}

Значение минимизируемого функционала для этого плана $394$. Найдем вновь потенциалы и построим матрицу $\ov C$.

\begin{figure}[h]
$$\begin{array}{|c|c|c|c|c|}
\hline
&v_1=2&v_2=-6&v_3=2&v_4=0\\
\hline
u_1=0&\bf2&-6&2&0\\
\hline
u_2=2&\bf4&-4&\bf4&\bf2\\
\hline
u_3=8&10&\bf2&10&\bf8\\
\hline
\end{array}$$
\caption{}\label{pr8}
\end{figure}

Имеем
$$\Delta=C-\ov C=\begin{pmatrix}
0&7&2&11\\
0&7&0&0\\
-4&0&-3&0
\end{pmatrix}
$$
Минимальный элемент $\Delta_{31}=-4<0$. Добавляя в первоначальный план на место нулевого небазисного элемента $x_{31}$ величину $t$, получим

\begin{figure}[h]
$$\begin{array}{|c|c|c|c|c|}
\hline
&b_1=40&b_2=15&b_3=42&b_4=13\\
\hline
a_1=10&10&&&\\
\hline
a_2=80&30-t&&42&8+t\\
\hline
a_3=20&t&15&&5-t\\
\hline
\end{array}$$
\caption{}\label{pr9}
\end{figure}

Положив $t=5$, получим четвертый план перевозок (рис.~\ref{pr10}).

\begin{figure}[h]
$$\begin{array}{|c|c|c|c|c|}
\hline
&b_1=40&b_2=15&b_3=42&b_4=13\\
\hline
a_1=10&10&&&\\
\hline
a_2=80&25&&42&13\\
\hline
a_3=20&5&15&&\\
\hline
\end{array}$$
\caption{}\label{pr10}
\end{figure}

Значение минимизируемого функционала для этого плана $374$. Найдем потенциалы и построим матрицу $\ov C$ (рис.~\ref{pr11}).

\begin{figure}[h]
$$\begin{array}{|c|c|c|c|c|}
\hline
&v_1=2&v_2=-2&v_3=2&v_4=0\\
\hline
u_1=0&\bf2&-2&2&0\\
\hline
u_2=2&\bf4&0&\bf4&\bf2\\
\hline
u_3=4&\bf6&\bf2&6&4\\
\hline
\end{array}$$
\caption{}\label{pr11}
\end{figure}

Имеем
$$\Delta=C-\ov C=\begin{pmatrix}
0&3&3&11\\
0&3&0&0\\
0&0&1&4
\end{pmatrix}
$$
В силу того, что $\Delta\ge0$, построенный четвертый план перевозок является оптимальным и суммарная стоимость перевозок равна $374$.
\end{example}


\begin{thebibliography}{11}

\bibitem{Os} Осипенко К.~Ю. Вариационное исчисление и оптимальное управление. МАТИ--РГТУ. Каф. ``Высш. мат.'', 2014, 1--56.

\bibitem{KF} Колмогоров А.~Н., Фомин С.~В. Элементы теории функций и
фукционального анализа. М.: ФИЗМАТЛИТ, 2004.

\end{thebibliography}
\end{document}