VI. Задачи дизъюктивного программирования и двойственность⁶

1. Вводные соображения

Изучение вопросов кусочно-линейного программирования естественным образом приводит к постановке задачи дизъюнктивного программирования. Произвольная непрерывная кусочно-линейная функция (k-линейная функция или просто k-функция), заданная на Rⁿ, допускает стандартное представление в форме [1]

$$f(x):=\ \min_{(j)}\, \vert A_j x -b^j \vert _{\,\max};$$ (1.1)

здесь A_j -- матрица, $x\!\in$Rⁿ, $b^j \!\in$R $^{m_{\scriptstyle j}}$, символ $\mid \cdot \mid_{\,\max}$ означает взятие максимального значения координат вектора, стоящего внутри символа $\mid \cdot \mid_{\,\max}$. Неравенство $f(x)\leq 0$ задает множество $M=\bigcup\limits_{(j)}\,M_j$, $M_j= \{ x\mbox{$\,\mid\,$} A_j x\leq~\!\!b^j \}$. Произвольная конечная система неравенств из k-функций конструктивно сводится к одному неравенству с функцией f(x) вида (1.1), а произвольная задача кусочно-линейного программирования допускает стандартное представление

$$\max\,\{(c,\ x) \mbox{$\,\mid\,$}f(x)\leq 0\},$$ (1.2)

где f(x) имеет вид (1.1). В отличие от традиционного представления допустимой области в виде пересечения конечной совокупности множеств (полупространств, простых выпуклых множеств и т.д.) в рассматриваемом случае допустимая область задачи оптимизации (1.2) задается объединением множеств (многогранников), т.е. $M=\{ x\ \mbox{$\,\mid\,$}$ $f(x)\leq 0\} = \bigcup\limits_{(j)}\,M_j$, $M_j= \{ x\mbox{$\,\mid\,$}A_j x\leq b^j \}$.

В схеме общей постановки пусть {M_j}₁^m -- произвольные множества из Rⁿ и f(x) -- произвольная функция, заданная на Rⁿ. Запишем задачи

$$P_{\cap}:~\max\,\{ f(x) \mbox{$\,\mid\,$}x \,\in\,\bigcap_{j=1}^m M_j \},$$ (1.3)

$$P_{\cup}:~\max\,\{ f(x) \mbox{$\,\mid\,$}x \,\in\,\bigcup_{j=1}^m M_j \}.$$ (1.4)

Первую из них назовем задачей в конъюнктивной постановке, вторую -- в дизъюнктивной. Форма (1.3) является обычной для задач математического программирования. Вторая из них отражает ситуацию кусочно-линейной задачи (1.2). Пусть в (1.4): $M_j =\{ x \mbox{$\,\mid\,$}F_j (x) \le 0 \}$, F_j: R$^n \,\to$R $^{m_{\scriptstyle j}}$, $j=1,\,...\,,m$. Для задачи $P_{\,\cap}$ функцией Лагранжа является

$${\mit\Phi}_{\,\cap} (x,\ u) = f(x) - \sum_{j = 1}^m (u_j,\ F_j (x)).$$ (1.5)

Задаче $P_{\,\cup}$, т.е. (1.4) поставим в соответствие функцию

$${\mit\Phi}_{\,\cup} (x,\ u) = f(x) - \min_{(j)}\, (u_j,\ F_j (x)),$$ (1.6)

которую будем называть дизъюнктивной функцией Лагранжа для задачи $P_{\,\cup}$. Зафиксируем схему соответствия задачам $P_{\,\cap}$ и $P_{\,\cup}$ их функций Лагранжа:

$$\begin{array}{rcl} P_{\,\cap} & \to & {\mit\Phi}_{\,\cap} (x... ...x,\ u) = f(x) -\min\limits_{(j)}\, (u_j,\ F_j (x)). \end{array}$$

Задаче кусочно-линейного программирования (k-задаче) в стандартной форме (1.2) будет соответствовать дизъюнктивная функция Лагранжа вида

$$L_{\cup} (x,\ u) = (c,\ x) -\min_{(j)}\, (u_j,\ A_j x - b^j).$$ (1.7)

С этой функцией можно связать многие проблемы, относящиеся к изучению k-задач, часть из которых рассматривается ниже. Алгебра k-функций и k-задач допускает расширение своих постановок до рамок более общих конструкций, а именно -- до рамок $\mbox{$\sigma$}$-расширений линейных функциональных пространств. Речь идет об алгебраическом расширении фиксированного функционального пространства F₀ до минимального линейного пространства F, замкнутого относительно операции дискретного максимума, т.е. если $\{f_j(x)\}\,\subset$F, то $\max\limits_{(j)}\, f_j(x)\,\in\,$F. Если F₀ -- класс линейных функций, то F -- класс k-функций; если F₀ -- класс квадратичных функций, то F -- класс кусочно-квадратичных функций и т.д. Отмеченное обстоятельство позволяет ряд проблем кусочного программирования и связанных с ним дизъюнктивных задач оптимизации выносить за рамки линейных постановок.

Хотя кусочно-линейные функции и соответствующий им аппарат имеют важное значение, тем не менее число работ, посвященных этим вопросам, незначительно. Отметим работы [1-6].

2. $\mbox{$\sigma$}$-расширения линейных функциональных пространств

Пусть F₀ -- некоторое линейное функциональное пространство с вещественным пространством X значений аргумента функций из F₀. Если $\{f_j(x)\}_{j\in J} \,\subset$ F₀, то функция дискретного максимума $f(x):=\ \max\limits_{j\in J}\, f_j(x)$ может как принадлежать F₀, так и не принадлежать. Способ образования функции f(x) назовем $\mbox{$\sigma$}$-операцией.

Речь пойдет о минимальном расширении пространства F₀ до линейного пространства F, обеспечивающего свойство $\mbox{$\sigma$}$-замкнутости:

$$\{f_j(x)\}_{j\in J} \,\subset \,{\mbox \mbox{\bf F}} \,\Longrightarrow \, \max_{j\in J}\, f_j(x) \,\in\,\mbox{\bf F}.$$ (2.1)

В этой ситуации выполняется, очевидно, свойство линейной замкнутости:

$$\{f_j^i \mbox{$\,\mid\,$}i\in I,\ j\in J_i\, \} \,\subset \,... ...}_i\, \max_{j\in J_{\scriptstyle i}}\, f_j^i \in \mbox{\bf F},$$ (2.2)

где $\mbox{$\alpha$}_i \,\in\,\mbox{\bf R},\ \ i \,\in\,I$.

Минимальное $\mbox{$\sigma$}$-замкнутое расширение назовем
$\mbox{$\sigma$}$-расширением. Из смысла такого расширения видно, что

$$\mbox{\bf F}= \,\bigcup_{k=0}^{+\infty}\, \mbox{\bf F}_k,$$

где F $_{k+1} =\{\, \mbox{$\sum\limits_{i\in I}^{}$} \mbox{$\alpha$}_i\, \max\limits_{j\in J_{\scriptstyle i}}\, f_j^i\ \mbox{$\,\mid\,$}\ f_j^i \,\in\,\mbox{\bf F}_k$, $\mbox{$\alpha$}_i \,\in\, \mbox{\bf R}$, $i \,\in\,I$, $j\,\in\,J_i$, $\vert I \vert < +\infty$, $\vert J_i \vert < +\infty \}$.

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

$$\max_{j\in J}\, f_j + \max_{i\in I}\, g_i = \max_{(j,\,i) \in J\times I}\, (f_j +g_i);$$ (2.3)

$$\sum_{i\in I} \mbox{$\alpha$}_i \max_{j\in J_{\scriptstyle ... ...n I_-} \vert \mbox{$\alpha$}_i \vert f_{s_{\scriptstyle i}}^i,$$ (2.4)

здесь $I_+ =\{ i\ \mbox{$\,\mid\,$}\ \mbox{$\alpha$}_i >0\}$, $I_- =\{ i \mbox{$\,\mid\,$}\ \mbox{$\alpha$}_i <0\}$;

$$\max_{j=1,\ldots ,m}\, f_j = [\, \max_{j=1,\ldots ,m-1}\, f_j -f_m\,]^+\ +f_m =$$

$$=[\, f_m - \max_{j=1,\ldots ,m-1}\, f_j \,]^+\ + \max_{j=1,\ldots ,m-1}\, f_j;$$ (2.5)

$$\min_{i=1,\ldots ,n}\, f_i = - [\, \min_{i=1,\ldots ,n-1}\, f_i -f_n\,]^+\ + \min_{i=1,\ldots ,n-1}\, f_i =$$

$$= -[\, f_n - \min_{i=1,\ldots ,n-1}\, f_i \,]^+\ +f_n;$$ (2.6)

$$[\, \max_{j\in J} f_j - \max_{i\in I} g_i \,]^+ = \max_{(j,\,i) \in J\times I}\, \{ f_j, g_i\} - \max_{i\in I} g_i;$$ (2.7)

$$\begin{array}{c} \max\limits_{j\in J}\, f_j - \max\limits_{i... ...imits_{j\in J}\, \min\limits_{i\in I}\, (f_j -g_i). \end{array}$$ (2.8)

Выписанные тождества носят общелогический характер и проверяются непосредственно.

Наравне с F введем пространство

$${\mbox {\bf H}} = \,\bigcup_{i=0}^{+\infty}\, {\mbox{\bf H}}_i,$$

где H₀ =F₀, H $_{k+1} =\{\, \mbox{$\sum\limits_{i\in I}^{}$} \mbox{$\alpha$}_i\, f_i^+ \mbox{$\,\mid\,$}\mbox{$\alpha$}_i \,\in\,\mbox{\bf R}, f_i \,\in\,{\mbox{\bf H}}_k$, $\vert I \vert \ <~\!+\infty \}$.

Операция взятия положительной срезки ``+'' является частным случаем $\mbox{$\sigma$}$-операции, однако она потенциально (т.е. многократно примененная) дает тот же класс функций F. Имеет место

Теорема 2.1   1) Все функции из $\mbox{\bf F}$ могут быть приведены к любому из стандартных видов:

$$\max_{j\in J}\, f_j - \max_{i\in I}\, g_i,$$ (2.9)

$$\min_{i\in I}\, \max_{j\in J_{\scriptstyle i}}\, f_j^i,$$ (2.10)

$$\max_{j\in J}\, \min_{i\in I_{\scriptstyle j}}\, f_i^j,$$ (2.11)

где $\{f_j,\ g_i,\ f_j^i \} \,\subset \,$ $\mbox{\bf F}_0$; (2.9) диктует $\mbox{\bf F}_k = \mbox{\bf F}_1$ при k>1, следовательно, $\mbox{\bf F}$ $=\mbox{\bf F}_1$.

2) Классы $\mbox{\bf F}$ и $\mbox{\bf H}$ совпадают.

Д о к а з а т е л ь с т в о. 1) Соотношение $(\ref{f7469})$ означает совпадение F_k с F₁ при k>1. На самом деле достаточно доказать F₂ =F₁. В силу (2.4) можно ограничиться преобразованием функции $f(x)= \max\limits_{i\in I}\, f_i$ при $\{f_i\}_I \,\subset$F₁ к виду (2.9). Пусть $I=\{ 1,\,...\,,n \}$. Доказательство можно вести индукцией по n. Если n=1, то f(x) = f₁(x) удовлетворяет требуемому свойству представления (2.9). Пусть n>1. Так как $f_i \,\in\,$F₁, то эти функции можно представить в виде

$$f_i = \max_{j\in J_{\scriptstyle i}}\, f_j^i - \max_{k\in I_{\scriptstyle i}}\,g_k^i$$

при $\{ f_j^i,\ g_k^i \} \,\subset$F₀. Имеем

$$% latex2html id marker 18008 f(x) \ \stackrel {(\ref{f7465})}{=}\ [\, \max_{i=1,\ldots ,n-1}\, f_i - f_n \,]^+\ +f_n.$$

По индукции $\max\limits_{i=1,\ldots ,n-1}\, f_i =:\ \bar{f} \,\in\,$F₁. Так как $f= [\bar{f} -f_n]^+\ +f_n$, причем $\{ \bar{f},\ f_n \} \subset$F₁, то по (2.4): $\bar{f} -f_n \,\in\,$F₁, а по (2.7): $[ \bar{f} -f_n ]^+ \,\in\,$F₁, что (с учетом $f_n \,\in\,$F₁) и дает $f\,\in\,$F₁. Итак, мы доказали F₂ =F₁, а вместе с тем и F=F₁.

Представимость функций из F в виде (2.10) или (2.11) следует из тождества (2.8).

2) Докажем вначале включение H$\subset$F₁, т.е. H$_k \subset$F₁, $\forall \,k$. Если $f\in$H₁, то в силу (2.4): $f\in$F₁. Следовательно, H$_1\! \subset$F₁. Пусть H$_k \subset$F₁, докажем H $_{k+1} \subset$F₁. Произвольная функция из H_k+1 имеет вид

$$f = \sum_{i\in I} \mbox{$\alpha$}_i\, f_i^+,\quad \{ f_i \} \,\subset \,{\mbox{\bf H}}_k \,\subset \,\mbox{\bf F}_1.$$

Из этого следует, что f представляется линейной комбинацией функций дискретного максимума при образующих из F₀, что с учетом (2.4) и дает для f требуемое представление (2.9).

Обратно, если $f\,\in\,$F, т.е. f имеет вид (2.9), то, показав, что функция дискретного максимума при образующих из F₀ принадлежит H, т.е. некоторому H_k, мы тем самым покажем и $f\,\in\,$H. Итак, пусть

$$f = \max_{j\in J}\, f_j,\quad \{ f_j \} \,\subset \,\mbox{\bf F}_0,\quad j=1,\,...\,,m.$$

Если m=1, то $f =f_1 \,\subset \,$H₀. Пусть m>1. Выпишем соотношение (2.5):

$$f = [\, \max_{j=1,\ldots ,m-1}\, f_j -f_m\,]^+\ +f_m.$$

Если по индуктивному предположению $\bar{f} =\! \max\limits_{j=1,...,m-1} f_j \!\in$H_k, то $f = [\bar{f} -f_m]^+\ +f_m \,\in\,$H_k+1, что и требовалось.

Представления (2.9)-(2.11) функций класса F, таким образом, эквивалентны. Конструктивное доказательство этого опирается на тождества (2.3)-(2.8).

Мы уже отметили, что представление функции в форме (2.9) может быть переписано в форме (2.10) при f_jⁱ = f_j -g_i (см. (2.8)). Нужно убедиться в обратном. Итак, пусть f вида (2.10), т.е. $f = \min\limits_{i\in I}\, \max\limits_{j\in J_{\scriptstyle i}}\, f_j^i$. Если $I=\{ 1,\,...\,,n \}$ и n=1, то $f = \max\limits_{j\in J_{\scriptstyle 1}}\, f_j^1 \in$F₁. При n>1 доказательство, как это и делалось выше, можно провести индукцией по n. По (2.6):

$$f = [\, \min_{i=1,\ldots ,n-1}\, \max_{j\in J_{\scriptstyle i... ...tyle n}}\, f_j^n ]^+\ + \max_{j\in J_{\scriptstyle n}}\, f_j^n.$$

По индуктивному предположению

$$\bar{f} = \min_{i=1,\ldots ,n-1}\, \max_{j\in J_{\scriptstyle i}} f_j^i \,\in\,\,\mbox{\bf F}_1,$$

т.е. $\bar{f}$ может быть представлена в форме (2.9), но тогда с использованием преобразований (2.3), (2.4) и (2.7) функция f приводится к виду (2.9), что и требовалось.

Эквивалентность представлений (2.11) и (2.9) доказывается аналогично. Теорема доказана полностью.

Функции f из F будем называть $\mbox{$\sigma$}$-функциями, или $\mbox{$\sigma$}$-кусочными функциями. Если F₀ -- пространство линейных функций, то F -- пространство кусочно-линейных функций.

3. Задача о седловой точке дизъюнктивной функции Лагранжа

Рассмотрим задачи (1.3) и (1.4) с их функциями Лагранжа соответственно (1.5) и (1.6). Задачу (1.4), в которой $M_j =\{ x \vert F_j (x) \le~0\}$, $j=1,\,...\,,m$, можно переписать в виде

$$\max\, \{ f(x)\ \mbox{$\,\mid\,$}\ \min_{(j)} \vert F_j(x) \vert _{\,\max}\ \le 0,\quad x \ge 0 \}.$$ (3.1)

Здесь ограничения задачи (1.4) мы дополнили требованием неотрицательности вектора x, т.е. $x\geq 0$. Это связано с обеспечением симметрии в постановках двойственных задач. Под множествами M_j будут пониматься $\{ x \vert F_j (x) \le 0$, $x\geq0\}$, $j=1,\,...\,,m$. Если ${\mit\Phi}_{\,\cup} (x,\ u)$ -- функция (1.6), то с (3.1) связывается задача о седле $[ \bar{x},\ \bar{u} ] \ge 0$:

$${\mit\Phi}_{\cup}(x,\ \bar{u}) \,\begin{array}[t]{c}\leq\\ [... ...\forall\,u\geq 0}\end{array}\, {\mit\Phi}_{\cup}(\bar{x},\ u).$$ (3.2)

В математическом программировании хорошо известен факт [7] (впрочем, просто доказываемый).

Если $[ \bar{x}, \bar{u} ]\! \ge\! 0$ - седло функции Лагранжа ${\mit\Phi}_{\,\cap} (x, u)$, поставленной в соответствие задаче $(\ref{f7453})$, то $(\bar{u}_j, F_j(\bar{x}))\! =\! 0$, $\forall \,j$ и $\bar{x}\,\in\,$Arg(1.3).

Для задачи (3.1) и ее дизъюнктивной функции Лагранжа ${\mit\Phi}_{\cup}(x,\ u)$ имеет место аналогичное утверждение.

Теорема 3.1   Если $[ \bar{x},\ \bar{u} ] \ge 0$ -- седловая точка для  ${\mit\Phi}_{\cup}(x,\ u)$, то $\min\limits_{(j)}\, (\bar{u}_j,\ F_j(\bar{x})) =0$ и $\bar{x} \,\in\,\,$ $\mathrm{Arg}\,$ (3.1).

Д о к а з а т е л ь с т в о. В соответствии с определением седловой точки

$${\mit\Phi}_{\cup} (x,\ \bar{u})\ \begin{array}[t]{c} \le\\ [-... ...\forall \, u \ge 0} \end{array}{\mit\Phi}_{\cup} (\bar{x},\ u),$$

или

$$f(x) -\min_{(j)}\, (\bar{u}_j, F_j(x)) \begin{array}[t]{c} \... ...} \end{array}f(\bar{x}) -\min_{(j)} (\bar{u}_j, F_j(\bar{x})),$$ (3.3)

$$f(\bar{x}) -\min_{(j)}\, (\bar{u}_j, F_j (\bar{x})) \begin{a... ...e 0} \end{array}f(\bar{x}) -\min_{(j)}\, (u_j, F_j (\bar{x})).$$ (3.4)

Соотношение (3.4) перепишем в виде

$$\min_{(j)}\, (\bar{u}_j,\ F_j (\bar{x}))\ \begin{array}[t]{c... ...forall u \ge 0} \end{array}\min_{(j)}\, (u_j,\ F_j (\bar{x})).$$ (3.5)

Докажем, во-первых, $\bar{x} \,\in\,M = \bigcup\limits_{(j)}\, M_j$, т.е. $\exists\,j_0:$ $F_{j_0} (\bar{x}) \le 0$. Если бы $F_j (\bar{x}) \not\le 0$, $\forall \,j$, то за счет выбора $u\ge 0$ можно было бы значение правой части в (3.5) сделать как угодно большим, что будет противоречить соотношению (3.5). Доказанное дает: $\mbox{$\alpha$}:=\ \min\limits_{(j)}\, (\bar{u}_j,\ F_j (\bar{x})) \le 0$. На самом деле, $\mbox{$\alpha$}= 0$. Если $\mbox{$\alpha$}< 0$, то соотношение (3.5) при u = 0 порождало бы противоречивое неравенство $0 > - \vert \mbox{$\alpha$}\vert \ge 0$. Итак, соотношение $\min\limits_{(j)}\, (\bar{u}_j,\ F_j (\bar{x}))$ доказано.

Необходимо доказать оптимальность вектора $\bar{x}$ для (3.1), т.е. $f(x) \le f(\bar{x})$, $\forall \, x \,\in\, M$. Обратимся к соотношению (3.3), которое можно теперь пареписать в виде

$$f(\bar{x}) - f(x) \ge -\min_{(j)}\, (\bar{u}_j,\ F_j (x)).$$ (3.6)

Если $x \,\in\,M$, т.е. $x \,\in\,M_{j_0}$ при некотором j₀, то $\min\limits_{(j)}\, (\bar{u}_j,\ F_j (x)) \le 0$, что в силу (3.6) дает $f(\bar{x}) -f(x) \ge 0$, $\forall \, x \,\in\, \bigcup\limits_{(j)}\, M_j$. Теорема доказана.

В математическом программировании (МП) более важной является обратная теорема, формулирующая условия, гарантирующие существование седловой точки для соответствующей функции Лагранжа. Такие теоремы имеют место для разрешимых задач линейного программирования (ЛП), выпуклого программирования (ВП) с условиями регулярности и некоторых других классов задач МП. Для дизъюнктивных постановок задач МП ситуация усложняется. В частности, усиливаются требования типа регулярности.

Задачу (3.1) назовем вполне регулярной, если каждая из задач

$$\max\, \{ f(x) \mbox{$\,\mid\,$}F_j (x) \le 0,\ \ x \ge 0 \},\quad j=1,\,...\,,m$$ (3.7)

разрешима. Эквивалентом такой регулярности является разрешимость задачи (1.4) и непустота всех M_j: $M_j \ne \emptyset$, $j=1,\,...\,,m$.

Пусть ${\mit\Phi}_j (x,\ u_j)\ =\ f(x)\ -\ (u_j,\ F_j (x))$ -- функция Лагранжа для (3.7), здесь $x \,\in\,\mbox{\bf R}^n$, $u_j \,\in\, \mbox{\bf R}^{m_{\scriptstyle j}}$.

Теорема 3.2   Пусть каждая из функций ${\mit\Phi}_j (x,\ u_j)$ обладает седлом $[ \bar{x}_j,\ \bar{u}_j ] \ge 0$, $j=1,\,...\,,m$. Если $\bar{x}$ -- то значение $\bar{x}_j$, на котором достигается $\max\limits_{(j)}\, f(\bar{x}_j)$, то

$${\mit\Phi}_{\cup} (x,\ \bar{u})\ \begin{array}[t]{c} \le\\ [-3pt] {\scriptstyle \forall x \ge 0} \end{array}f(\bar{x}),$$ (3.8)

где ${\mit\Phi}_{\cup} (x,\ \bar{u}) = f(x) - \min\limits_{(j)}\, (\bar{u}_j,\ F_j (x))$. Д о к а з а т е л ь с т в о. Во-первых, имеем: $(\bar{u}_j,\ F_j (\bar{x}_j)) =~\!0$, $j=1,\,...\,,m$ и $f(x) - (\bar{u}_j,\ F_j (x)) \le f(\bar{x}_j)$ $(\le f(\bar{x}))$, $\forall \, x \ge 0$. Отсюда $\max\limits_{(j)}\, [f(x) - (\bar{u}_j,\ F_j (x))] \le f(\bar{x})$, но поскольку левая часть этого неравенства равна $f(x) - \min\limits_{(j)}\, (\bar{u}_j,\ F_j (x))\quad \left (={\mit\Phi} (x, \bar{u}) \right )$, то доказываемое неравенство (3.8) верно.

Несколько модифицируем функцию ${\mit\Phi}_{\cup}(x,\ u)$, а именно, положим

$$\overline{\mit\Phi}_{\cup} (x,\ u) =f(x) - \min_{(j)}\, (u_j, F_j^+ (x)),$$

где ``+'' над F_j означает положительную срезку. Справедлива

Теорема 3.3   1) Для $\overline{\mit\Phi}_{\cup}$ $(x,\ u)$ справедливы теоремы 1 и 2.
2) В условиях теоремы 2 точка $[\bar{x},\ \bar{u}]$ (из этой теоремы) реализует седло для $\overline{\mit\Phi}_{\cup} (x,\ u)$.

Д о к а з а т е л ь с т в о. Что касается утверждений из формулировки 1), то они проверяются так же, как и теоремы 1 и 2. Рассмотрим утверждение 2). Требуется доказать

$$f(x) -\min_{(j)}\,(\bar{u}_j, F_j^+ (x)) \begin{array}[t]{c} ... ...]{c} \le\\ [-3pt] {\scriptstyle \forall \, u \ge 0} \end{array}$$

$$\begin{array}[t]{c} \le\\ [-3pt] {\scriptstyle \forall \, u ... ...0} \end{array}f(\bar{x}) -\min_{(j)}\,(u_j,\ F_j^+ (\bar{x})).$$ (3.9)

Так как $\bar{x}$ реализует $\max\limits_{(j)} f_j(\bar{x}_j)$, пусть $\bar{x} = \bar{x}_{j'}$, то $F_{j'}^+ (\bar{x}) =~\!0$, а потому $\min\limits_{(j)}\,(u_j,\ F_j (\bar{x})) =0$ при любых $u_j\geq 0$, $\forall \,j$. Поэтому, в частности, $\min\limits_{(j)}\,(\bar{u}_j,\ F_j^+ (\bar{x})) =0$. В силу сказанного правое неравенство в (3.9) выполняется очевидным образом для любых $u_j\geq 0$, а левое повторяет доказанное неравенство (3.8) (на случай функции $\overline{\mit\Phi}_{\cup} (x,\ u)$). Теорема доказана.

З а м е ч а н и е к формулировкам теорем 1-3. Доказанные теоремы носят довольно общий характер. В них не уточняется, например, постановка задач (3.7). Но если, скажем, (3.7) -- задача выпуклого программирования, то вместо постулирования существования седла для их функций Лагранжа (в теореме 2) можно было бы предположить разрешимость задач (3.7) и выполнимость условия: $\exists\,p\geq 0$, F_j(p) <0 (условие регулярности). Этим бы и гарантировалось существование седла для ${\mit\Phi}_j (x,\ u)$, $j=1,\,...\,,m$. Что касается случая линейной постановки задачи (3.1), то ниже дается уточнение соответствующих теорем. Заметим, что линейный случай имеет самостоятельный интерес в связи с актуальностью задач кусочно-линейного программирования.

Если

$$\max\, \{f(x)\mbox{$\,\mid\,$}f_j(x)\leq 0,\ \ j=1,\,...\,,m,\ \ x\geq 0\}$$

-- общая постановка задачи кусочно-линейного программирования, т.е. $\{f,\ f_j\}_j$ -- кусочно-линейные функции, то ее можно эквивалентно переписать в виде

$$\max\, \{t\ \mbox{$\,\mid\,$}\ t\leq f(x),\ \ f_j(x)\leq 0,\ \ j=1,\,...\,,m,\ \ x\geq 0\},$$

а потому и в виде

$$\max \{t\, \mbox{$\,\mid\,$}\, \varphi (x, t):= (t-f(x))^+\, +\, \sum_{j=1}^m f_j^+(x) \leq 0,\ \ x\geq 0\}.$$

Так как $\varphi (x,\ t)$ также кусочно-линейная функция от $z=[x,\ t]$, то эту задачу можно привести к виду (2.10), соответствующему той ситуации, когда F₀ -- пространство линейных функций. Этим мы подчеркнули, что произвольную задачу кусочно-линейного программирования (k-задачу) можно записать в форме

$$L_{\cup}: \max \{ (c, x)\, \mbox{$\,\mid\,$}\, \min_{(j)} \vert A_jx-b^j \vert _{\,\max} \le 0,\ \ x \ge 0 \},$$ (3.10)

или

$$\max\, \{ (c,\ x)\ \mbox{$\,\mid\,$}\ x \,\in\,\bigcup_{j=1}^m\, M_j \},$$

где $M_j =\{ x\geq 0\ \mbox{$\,\mid\,$}\ A_j (x) \le b^j \}$, $j=1,\,...\,,m$.

Итак, далее речь идет о задаче (3.10) и ее функции Лагранжа в форме

$$L_{\cup} (x,\ u):=\ (c,\ x) -\min_{(j)}\, (u_j,\ A_j x - b^j).$$

Лемма 3.1   Пусть задача  $(\ref{f74710})$ разрешима и $M_j\!\ne~\!\!\emptyset$, $\forall \,_j$ (т.е. вполне регулярна). Тогда функция $L_{\cup}(x, u) =(c, x) -\min\limits_{(j)} (u_j, A_j x - b^j)$ обладает седлом $[\bar{x},\ \bar{u}]$, причем в качестве $\bar{x}$ и $\bar{u} = [ \bar{u}_1,\,...\,,\bar{u}_m ]$ выступают:

$$\bar{x} ={\,\mathrm{arg}} \max_{(j)}\, (c,\ \bar{x}_j),\quad ... ...,{\,\mathrm{Arg}} \max_{x \,\in\,M_{\scriptstyle j}}\, (c,\ x),$$

$$\bar{u}_j \,\in\,{\,\mathrm{Arg}} \min_{u \,\in\,M_{\scriptstyle j}^*}\, (b^j, u),\quad j=1,\,...\,,m,$$

где $M_j^*:=\ \{u\geq 0\ \mbox{$\,\mid\,$}\ A_j^Tu\geq c\}$.

Д о к а з а т е л ь с т в о. Если показать, что $\mbox{$\alpha$}:=\,\min\limits_{(j)} (\bar{u}_j, A_j \bar{x} -b^j) =~0$, то в силу теоремы 2 левое неравенство в определении седла для $L_{\cup} (x,\ u)$ будет выполнено. Так как вектор $\bar{x} \ge 0$ удовлетворяет одной из систем $A_j x \le b^j$, то $\mbox{$\alpha$}\le 0$. Покажем $\mbox{$\alpha$}\ge 0$. Имеем:

$$\min_{(j)}\, (\bar{u}_j,\ A_j \bar{x} -b^j) =$$

$$= \min_{(j)}\, [ -(b^j,\ \bar{u}_j) +(c,\ \bar{x}) + (A_j^T \bar{u}_j - c,\ \bar{x}) ] \ge$$

$$\geq \min_j\, [ (c,\ \bar{x}) - (c,\ \bar{x}_j) ] \ge 0.$$

Выше мы воспользовались соотношениями: $A_j^T \bar{u}_j - c \ge~\!0$; $(b^j,\ \bar{u}_j) = (c,\ \bar{x}_j)$ -- по теореме двойственности в ЛП; $(c,\ \bar{x}) \ge (c,\ \bar{x}_j),\ \forall \, j$.

Остается показать выполнимость правого неравенства в определении седловой точки для $L_{\cup} (x,\ u)$, т.е.

$$L_{\cup} (\bar{x},\ \bar{u}) \begin{array}[t]{c} \le\\ [-3pt]... ...iptstyle \forall \, u \ge 0} \end{array}L_{\cup} (\bar{x},\ u).$$

С учетом $\mbox{$\alpha$}= 0$ выписанное неравенство принимает вид

$$0 \begin{array}[t]{c} \le\\ [-3pt] {\scriptstyle \forall \, ... ...j} \ge 0} \end{array} -\min_{(j)}\, (u_j,\ A_j \bar{x} - b^j).$$ (3.11)

Так как $\exists\, j_0$: $A_{j_0} \bar{x} -b^j \le 0$, то при любом $u\geq 0$: $\min\limits_{(j)}\, (u_j$, $A_j \bar{x} -b^j) \le 0$, следовательно, (3.11) верно. Лемма доказана.

Отсюда и теоремы 1 вытекает

Теорема 3.4   Если системы $A_j x \le b^j,\ \ x \ge 0,\ \ j=1,\,...\,,m$ совместны, то задача  $(\ref{f74710})$ разрешима тогда и только тогда, когда ее дизъюнктивная функция Лагранжа

$$L_{\cup} (x,\ u) = (c,\ x) -\min_{(j)}\, (u_j,\ A_j x - b^j)$$

обладает седлом $[ \bar{x},\ \bar{u} ] \ge 0$, при этом
1) если $L_{\cup}$ разрешима и $\bar{x}_j \,\in\, {\,\mathrm{Arg}} L_j$, $\bar{u}_j \,\in\,{\,\mathrm{Arg}} L_j^*$, $\bar{x} = {\,\mathrm{arg}} \max\limits_{(j)}\, (c,\ \bar{x}_j)$, то $[\bar{x},\ \bar{u}]$ -- седло;
2) если $[\bar{x},\ \bar{u}]$ -- седло для $L_{\cup} (x,\ u)$, то $\{ \bar{x},\ \bar{u}_j \}$ удовлетворяют всем соотношениям из 1).

4. Кусочно-линейные функции и системы кусочно-линейных неравенств

Кусочно-линейные функции -- это $\mbox{$\sigma$}$-функции в ситуации, когда F₀ -- пространство линейных функций. К определению кусочно-линейных функций можно подойти двояко: либо так, как это только что сделано в п. 2, либо исходя из некоторой аксиоматики, идентифицирующей такие функции. Остановимся на втором подходе.

Пусть имеются конечные совокупности многогранников { M_j }_J и собственных линейных функций  { l_j(x) }_J. Будем говорить, что система $\{ M_j,\ l_j(x) \}$ задает однозначную кусочно-линейную функцию l(x), заданную на X, если:

1)

$\bigcup\limits_{j \,\in\,J}\, M_j =\mbox{\bf X},\quad M_i^0 \,\bigcap\, M_j^0 = \emptyset$    при    $i \,\neq\, j$;

2)

$l (x) \,\equiv\, l_j (x),\quad \forall \, x \,\in\, M_j,\quad \forall \, j \,\in\,J$.

Здесь M_j⁰ -- алгебраическая внутренность многогранника M_j, т.е. $y \,\in\,M_j^0 \,\Longleftrightarrow \, y +t s \,\in\, M_j$ при любом $s \,\in\,$X и достаточно малом $t \geq 0$. Термином многогранник, как и ранее, обозначается множество, задаваемое конечной системой собственных линейных неравенств

$$(f_j,\ x) -\mbox{$\alpha$}_j \,\leq\, 0,\quad j\,\in\,J.$$

В данном определении некоторые из M_j, или M_j⁰, могут быть и пустыми.

Будем использовать обозначения: L₀ -- пространство линейных функций, L -- пространство k-линейных функций, определенных внешним образом в силу свойств 1) и 2). На самом деле класс функций L совпадает с классом F из предыдущего параграфа, который строится из F₀ =L₀, т.е. L -- это минимальное расширение пространства линейных функций, замкнутое относительно операций дискретного максимума (см. п. 2). Следовательно, представление (2.9), а также каждое из (2.10) и (2.11), являются универсальным представлением кусочно-линейных функций (далее будем говорить короче: k-функций).

Для унификации и упрощения записи k-функций, систем неравенств из k-функций, задач кусочно-линейного программирования и т.д. будем в дальнейшем полагать: X=Rⁿ, тогда

$${\mbox{\bf L}}_0 = \{ l(x) = (a,\ x) - \mbox{$\alpha$}\ \mbox... ...in\, \mbox{\bf R}^n,\quad \mbox{$\alpha$}\,\in\,\mbox{\bf R}\},$$

$${\mbox{\bf L}} = \{ \max_{j \,\in\,J}\,l_j(x) - \max_{i \,\in\,I}\, h_i (x)\ \mbox{$\,\mid\,$}$$

$$\mbox{$\,\mid\,$}\ \{ l_j,\ h_i \} \subset {\mbox{\bf L}}_0,\ \ \vert J \vert < +\infty, \ \vert I \vert < +\infty\}.$$

Пусть

$$\vert z\vert _{\,\max} = \max_{(i)}\, z_i,\quad \vert z\vert _{\,\min} = \min_{(i)}\, z_i,$$

где z -- вектор конечномерного пространства. Если $Ax -b = [\, l_1(x),\,...\,,l_m(x) \,]^T$ -- вектор линейных функций, то в соответствии с введенным обозначением будем иметь:

$$\vert Ax - b\, \vert _{\,\max} \ =\ \max_{(i)}\, l_i(x).$$

Представления кусочно-линейных функций в виде (2.9) - (2.11) принимают унифицированную форму:

$$\vert Ax -b\, \vert _{\,\max} - \vert Bx -d\, \vert _{\,\max},$$ (4.1)

$$\min_i\, \vert A_i x -b^i\, \vert _{\,\max},$$ (4.2)

$$\max_{(j)}\, \vert A_j x -b^j\, \vert _{\,\min}.$$ (4.3)

Отметим также свойства функций дискретного максимума:

$$\vert z\vert _{\,\max}\ =\ - \vert-z\vert _{\,\min};$$

$${\mbox{\rm при}}\ \ \mbox{$\alpha$}> 0:\ \ \vert\mbox{$\alpha... ... z\vert _{\,\max}\ =\ \mbox{$\alpha$}\, \vert z\vert _{\,\max};$$

$${\mbox{\rm при}}\ \ \mbox{$\alpha$}< 0:\ \ \vert\mbox{$\alpha... ... z\vert _{\,\max}\ =\ \mbox{$\alpha$}\, \vert z\vert _{\,\min}.$$

Конечная система неравенств из кусочно-линейных функций (k-функций) может быть записана в виде

$$\min_{(j)}\, \vert A_j^t x -b_t^j \vert _{\,\max}\ \leq 0,\quad t=1,\,...\,,T.$$ (4.4)

Она может быть переписана с помощью одного неравенства

$$\sum_{t=1}^T \,(\, \min_{(j)}\, \vert A_j^t x -b_t^j \vert _{\,\max} \,)^+ \leq 0,$$

или (на основе теоремы 1) в виде

$$\min_{j=1,\ldots , m}\, \vert A_jx -b^j \vert _{\,\max}\ \leq 0.$$ (4.5)

Это задание будем считать одним из стандартных. Другим стандартным видом является

$$\vert Ax - b \vert _{\,\max} - \vert Bx - d \vert _{\,\max}\ \leq 0.$$ (4.6)

Итак, произвольная конечная система кусочно-линейных неравенств может быть приведена к любому из стандартных видов (4.4)-(4.6).

Рассмотрим представление системы в виде (4.5). Положим $M_j = \{ x \mbox{$\,\mid\,$}A_j x \le b^j \}$. Тогда множеством решений неравенства (4.5) будет $M = \bigcup\limits_{j=1}^m\, M_j$. С другой стороны, если M -- произвольное полиэдральное множество, пусть из Rⁿ, т.е. $M = \bigcup\limits_{j=1}^m\, M_j$ и { M_j } -- многогранники: $M_j= \{ x\mbox{$\,\mid\,$}A_j x\leq b^j \}$, то M является множеством решений неравенства (4.5).

С этой же точки зрения посмотрим на неравенство (4.6). Пусть

$$Ax -b = [\, l_1 (x),\,...\,,l_m (x) \,]^T,\quad Bx -d = [\, s_1 (x),\,...\,,s_k (x) \,]^T,$$

$$\{ l_j(x),\ s_i(x) \}_{\scriptscriptstyle 1,\,1}^{m,\,k} \,\subset \, {\mbox{\bf L}}_0$$

(L₀ -- пространство линейных функций). Положим

$$M_i = \{ x\ \mbox{$\,\mid\,$}\ l_j(x) \leq s_i(x),\ \ j=1,\,...\,,m \}.$$

Тогда, как легко видеть, $\bigcup\limits_{i=1}^s\, M_i$ совпадает с множеством решений неравенства (4.6). Тем самым, для неравенства (4.6) указаны те многогранники M_i, объединение которых и дает множество решений неравенства (4.6). С другой стороны, если полиэдральное множество M задано тем или иным образом, например, как в предыдущем случае -- совокупностью систем линейных неравенств, каждая из которых задает выпуклую многогранную компоненту множества M, то требуется цепочка тех или иных преобразований типа (2.3)-(2.8), приводящая к заданию множества M одним неравенством вида (4.6).

Наконец, рассмотрим систему кусочно-линейных неравенств в форме (4.4), формально более сложную, чем (4.5) или (4.6). Положим

$$M_j^t:=\ \{ x\ \mbox{$\,\mid\,$}\ A_j^t x \leq b_t^j \},\quad M_t:=\ \bigcup_{(j)}\, M_j^t,\quad M=:\ \bigcap_{(t)}\, M_t.$$

Множество M_t -- это множество решений t-го неравенства в системе (4.4), так что M -- множество решений всей системы.

Материал, изложенный в п. 2 и п. 4, устанавливает способы конструктивного соответствия между полиэдральными множествами и их аналитическим заданием. Хотя сопутствующая этому алгебра преобразований может быть достаточно громоздкой, тем не менее логика этих преобразований проста и может быть в реальных прикладных ситуациях поручена компьютеру.

5. Задача кусочно-линейного программирования

5.1. Предварительные замечания

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

$$P: \max \{ (c, x)\, \mid \min_{j=1,\ldots ,m}\, \vert A_j x -b^j \vert _{\,\max}\ \leq\ 0,\,\ x \ge 0 \}.$$ (5.1)

Если же f(x) -- произвольная оптимизируемая, пусть максимизируемая, k-функция при одном k-неравенстве, пусть $g (x) \le 0$ (возможно, с $x \ge 0$), то переписав задачу $\max\, \{ f(x) \mbox{$\,\mid\,$}g (x) \le 0 \}$ в виде

$$\max\, \{ t\ \mbox{$\,\mid\,$}\ g(x) \le 0,\quad f(x) \ge t \}$$

и преобразовав систему из двух k-неравенств к одному
k-неравенству, получим задачу поиска максимума линейной функции при одном ограничении в форме k-неравенства.

Итак, объектом рассмотрения примем задачу (5.1). Введем частичную задачу (подзадачу)

$$L_j:\ \max\, \{ (c,\ x) \mbox{$\,\mid\,$}A_j x \le b^j,\quad x \ge 0 \}.$$ (5.2)

Связь между задачей (5.1) и L_j проста:

$$% latex2html id marker 17326{\,\mathrm{opt}}(\ref{f7491})... ...(j:\ M_{\scriptstyle j} \neq \emptyset )}{\,\mathrm{opt}} L_j,$$ (5.3)

где $M_j =\{ x \ge 0 \mbox{$\,\mid\,$}A_j x \le b^j \}$. В (5.2) для некоторых j множества $M_j =\{ x \ge 0 \mbox{$\,\mid\,$}A_j x \le b^j \}$ могут быть пустыми при свойстве разрешимости исходной задачи (5.1), т.е. произвольная k-задача, будучи преобразована к виду (5.1), распадается на конечное число задач линейного программирования, решив которые, мы тем самым находим решение и исходной задачи. Поскольку конструктивизм соответствующих преобразований обеспечен, то формально решение произвольной задачи кусочно-линейного программирования сводится к использованию отмеченного конструктивизма и некоторого метода (например симплекс-метода) решения задачи ЛП.

5.2. Условия разрешимости k-задачи

Для k-задач выполняется ряд свойств и теорем, формулируемых в рамках теории линейного программирования. Некоторые из них являются следствиями теорем из ЛП, некоторые же требуют своих доказательств, по крайней мере, уточнений. Не требует самостоятельного доказательства

Теорема 5.1 (о достижимости)   Если

$$\sup\, \{ (c,\ x)\ \mbox{$\,\mid\,$}\ \min_{(j)}\, \vert A_j x -b^j \vert _{\,\max}\ \le\ 0,\quad x \ge 0 \} \,<\, +\infty,$$

то операция $\sup$ в этой задаче достижима.

Выпишем задачу, двойственную к L_j:

$$L_j^*:\ \min\, \{ (b^j,\ u^j)\ \mbox{$\,\mid\,$}\ A_j^T u^j \ge c,\quad u^j \ge 0\}.$$ (5.4)

Пусть $M_j^* = \{ u^j \ge 0 \mbox{$\,\mid\,$}A_j^T u^j \ge c \}$.

Теорема 5.2   Задача $(\ref{f7491})$ разрешима тогда и только тогда, когда

$$M\, =\, \bigcup_{j=1}^m\, M_j \ne \emptyset \quad \mbox{и} \quad M_j \ne \emptyset \, \Longrightarrow \, M_j^* \ne \emptyset .$$

Д о к а з а т е л ь с т в о. Поскольку условия $M_j \ne \emptyset$ и $M_j^* \ne \emptyset$ являются необходимыми и достаточными для разрешимости задачи L_j, то $\max\limits_{j:\ M_{\scriptstyle j} \ne \emptyset } {\,\mathrm{opt}} L_j$ конечен и является значением optP. Обратно, если задача P разрешима, то все задачи L_j c $M_j \ne \emptyset$ разрешимы (т.е. ситуации opt $L_j\, =\, +\infty$ исключаются), а тогда в соответствии с теоремой двойственности в ЛП: $M_j^* \ne \emptyset$, что и требовалось.

З а м е ч а н и е 5.1. Другой вариант формулировки теоремы 2 состоит в эквивалентности

$$P\ {\mbox{разрешима}} \,\Longleftrightarrow \,(M \ne \emptyse... ...j \ne \emptyset \,\Longrightarrow \, L_j\ {\mbox{разрешима}})).$$

5.3. Двойственность

Исходную k-задачу возьмем в форме (5.1), дополнив ее предположением (впрочем, несущественным): размерность векторов A_j x -b^j одинакова, т.е. число неравенств в каждой из систем $A_j x \le b^j$ одно и то же. Введенное условие позволяет двойственную переменную для L_j, т.е. переменную u^j в задаче (5.4), обозначать одним символом u. В соответствии со сказанным задачу (5.4) перепишем в виде:

$$\min \{ (b^j,\ u) \mbox{$\,\mid\,$}A_j^T u \ge c,\ \ u \ge 0 \},\quad j=1,\,...\,,m.$$ (5.5)

Сформулируем задачу

$$P^*:\ \max_{j:\ M_{\scriptstyle j}^* \ne \emptyset }\, \min\, \{ (b^j,\ u) \mbox{$\,\mid\,$} A_j^T u \ge c,\quad u \ge 0 \}.$$ (5.6)

Задачу P^* будем рассматривать как один из вариантов задачи, двойственной к P.

В отношении задачи (5.6) справедлива

Теорема 5.3   Задача $(\ref{f7496})$ разрешима тогда и только тогда, когда

$$\exists\, j \,\in\,\overline{1,\, m}:\ \ M_j^* \ne \emptyset \ \&\ M_j \ne \emptyset .$$ (5.7)

Д о к а з а т е л ь с т в о. Действительно, если $J:=\ \{ j \mbox{$\,\mid\,$}M_j \ne \emptyset$, $M_j^* \ne~\emptyset \}$, то для $j \,\not\in\, J:\ \inf\, \{ (b^j,\ u) \mbox{$\,\mid\,$}x \,\in\,M_j^* \}\, =\, -\infty$, поэтому в (5.6) максимум можно брать только по $j \,\in\,J$. Этим и обеспечивается разрешимость задачи P^*. Необходимость условий (5.7) очевидна: если P^* разрешима, то хотя бы для одного  j' задача L_j^* разрешима, что и эквивалентно (5.7).

Из теорем 2 и 3, а также теоремы двойственности в ЛП, вытекает

Теорема 5.4   Если задача $(\ref{f7491})$ разрешима, то $(\ref{f7496})$ также разрешима, при этом их оптимальные значения совпадают.

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

$$\begin{array}{rl} P: & \sup\limits_{(j)}\, \inf\limits_{x \in... ...nf\limits_{u \in M_{\scriptstyle j}^*}\, (b^j,\ u). \end{array}$$

Условия одновременной разрешимости P и P^* определяются теоремами 2 и 3, но возможна и ситуация: P не разрешима, P^* разрешима. Это соответствует тому, что при разрешимости P^* $\exists\,j_0:$ $M_{j_0} \ne \emptyset \ \&$ $M_{j_0}^* = \emptyset$, т.е. задача L_j0 -- несобственная 2-го рода. Так как в рассматриваемой ситуации $\sup\limits_{x \in M_{\scriptstyle j_0}}\, (c,\ x)\, =\, + \infty$, то opt $P\, =\, + \infty$, т.е. P не разрешима. Одновременная неразрешимость задач P и P^* реализуется на паре задач линейного программирования L и L^*, являющихся несобственными 3-го рода.

Конструкция двойственной задачи P^* в форме (5.6) подсказывается понятными соображениями, исходящими из двойственного перехода $L_j \,\stackrel {(*)}{\longrightarrow }\, L_j^*$ и необходимости выполнения главного свойства теорем двойственности в МП, а именно: optP=optP^*. Для обеспечения последнего соотношения в P^* и введена операция $\max\limits_{j:\ M_{\scriptstyle j}^* \ne \emptyset }\, \ldots\,$, хотя соображения симметрии требуют в двойственной задаче иметь общую операцию $\min$ (как в исходной $\max$). В этом смысле конструкция задачи P^* выглядит несколько искусственной. Здесь возможен несколько другой подход. Он связан с известным генеральным положением относительно двойственности, когда исходная задача записывается через свой эквивалент в форме максимина функции Лагранжа, а тогда минимакс этой функции объявляется объектом, двойственным к исходному. Для задач линейного программирования это и приводит к классической двойственности. Для пояснения можно привести схему:

$$L:\ \max\, \{ (c,\ x) \mbox{$\,\mid\,$}Ax \le b,\ \ x \ge 0 \} \stackrel {\textstyle \sim}{\longrightarrow }$$

$$\stackrel {\textstyle \sim}{\longrightarrow }\, \max_{x \ge 0}\, \min_{u \ge 0}\, [ (c,\ x) - (u,\ Ax - b) ] =$$

$$= \max_{x \ge 0}\, \min_{u \ge 0}\, [ (b,\ u) + (c - A^T u,\ x) ];$$

$$\min_{u \ge 0}\, \max_{x \ge 0}\, [ (b,\ u) + (c - A^T u,\ x) ] \,\stackrel {\textstyle \sim}{\longrightarrow }$$

$$\stackrel {\textstyle \sim}{\longrightarrow }\, L^*:\ \min\, \{ (b,\ u) \mbox{$\,\mid\,$}A^T u \ge c,\ \ u \ge 0 \};$$

здесь символ $\stackrel {\textstyle \sim}{\longrightarrow }$ означает эквивалентный переход.

Оказывается, что, как и в классическом случае, максимин дизъюнктивной функции Лагранжа, т.е. $\max\limits_{x \ge 0}\, \min\limits_{u \ge 0}\, L_{\cup} (x,\ u)$, эквивалентен исходной задаче, которой для нас является (5.1) (она обозначена символом P), а минимакс этой функции, т.е. $\min\limits_{u \ge 0}\, \max\limits_{x \ge 0}\, L_{\cup} (x,\ u)$, эквивалентен как раз задаче (5.6), что будет показано ниже. Задачи (5.1) и (5.6) допускают эквивалентную перезапись:

$$\max_{(j)}\, \max\, \{ (c,\ x_j) \mbox{$\,\mid\,$}x_j \,\in\,M_j \},$$ (5.8)

$$\max_{(j)}\, \min\, \{ (b^j,\ u_j) \mbox{$\,\mid\,$}u_j \,\in\,M_j^* \};$$ (5.9)

здесь $M_j = \{ x_j \ge 0 \mid A_j x_j \le b^j \}$, $M_j^* = \{ u_j \ge 0 \mid A_j^T u_j \ge c\}$. Прежде чем установить эквивалентности

$$% latex2html id marker 17388\max_{x \ge 0}\, \min_{u \ge ... ...x,\ u) \,\sim\, (\ref{f7491})\quad [ \,\sim\, (\ref{f7498}) ],$$ (5.10)

$$% latex2html id marker 17392\min_{u \ge 0}\, \max_{x \ge ... ...x,\ u) \,\sim\, (\ref{f7496})\quad [ \,\sim\, (\ref{f7499}) ],$$ (5.11)

докажем вспомогательное утверждение. Запишем задачу

$$\begin{array}{c} \min\, \{ \max\limits_{(j)} (b^j,\ u_j)\ \m... ...,...\,,u_m\,] \,\in\,M^*:=\ \prod_{(j)}\, M_j^* \}. \end{array}$$ (5.12)

Лемма 5.1   Задачи $(\ref{f7499})$ и $(\ref{f74912})$ эквивалентны в смысле ${\,\mathrm{opt}}(\ref{f7499}) = {\,\mathrm{opt}}(\ref{f74912})$ и 1) если $\bar{u}_{j_0}\, =\, {\,\mathrm{arg}}(\ref{f7499})$, то $\bar{u}_{j_0}$ является j₀-ой координатой некоторого оптимального вектора $\bar u$ задачи  $(\ref{f74912})$, и обратно 2) если $\bar u = [\,\bar{u}_1,\,...\,,\bar{u}_m \,] = {\,\mathrm{arg}}(\ref{f74912})$, $\max\limits_{(j)}\, (b^j,\ \bar{u}_j) = (b^{j_0},\ \bar{u}_{j_0})$, то $\bar{u}_{j_0} = {\,\mathrm{arg}}(\ref{f7499})$.

Д о к а з а т е л ь с т в о. Пусть $\bar{t}_j:=$optL_j (=optL_j^*), $\bar{t}:=\ \max\limits_{(j)}\, \bar{t}_j = \bar{t}_{j_0}$. Очевидно, $\bar{t} =$opt(5.9). Задачу (5.12) можно переписать в эквивалентном виде

$$\max\, \{ t\ \mbox{$\,\mid\,$}\ (b^j,\ u_j) \le t,\ \ \forall \,j,\ \ u \,\in\,M^* \}.$$ (5.13)

Значение $\bar{t}$ (=opt(5.9)) неуменьшаемо в (5.13), так как оно неуменьшаемо в задаче $\min\, \{ t\ \mbox{$\,\mid\,$}\ (b^{j_0},\ u_{j_0}) \le t$, $u_{j_0} \,\in\,M_{j_0}^* \}$. Это и дает равенство opt(5.9)=opt(5.12). Свойства 1) и 2) из формулировки леммы вытекают из конструкции рассматриваемой пары задач.

Теорема 5.5   Пусть задача $(\ref{f7491})$ разрешима и вполне регулярна, т.е. $M_j \ne \emptyset$, $\forall \,j$. Тогда

$$% latex2html id marker 174361.\ \max_{x \ge 0}\, \min_{u ... ... = {\,\mathrm{opt}}(\ref{f7491})\ \ ( \,\sim\,(\ref{f7498}) ),$$ (5.14)

$$% latex2html id marker 174422.\ \min_{u \ge 0}\, \max_{x ... ...t}}(\ref{f7496})\ \ ( \,\sim\,(\ref{f74912}) ). \hspace*{-2mm}$$ (5.15)

Д о к а з а т е л ь с т в о. 1. Рассмотрим внутреннюю операцию в левой части (5.14):

$$\min_{u \ge 0}\, [ (c,\ x) -\min_{(j)}\, (u_j,\ A_j(x) -b^j) ]=$$

$$= \left\{ \begin{array}{rl} (c,\ x), & {\mbox{\rm если}}\ \ex... ...\infty, & {\mbox{\rm в\ противном\ случае}}. \end{array}\right.$$

Выписанное равенство не нуждается в особом обосновании, из него и следует

$$% latex2html id marker 18880 \max_{x \ge 0}\, \min_{u \ge 0}... ...\mid x \in \bigcup_{(j)} M_j \} ={\,\mathrm{opt}}(\ref{f7491}).$$

2. Выпишем внутреннюю операцию в левой части (5.15), преобразовав очевидным образом функцию $L_{\cup} (x,\ u)$:

$$\max_{x \ge 0}\, L_{\cup} (x,\ u) = \max_{x \ge 0}\, \{ \max_{(j)}\, [ (b^j,\ u_j) + (c -A_j^T u_j,\ x) ] \}.$$

Отсюда следует

$$\max_{x \ge 0}\, L_{\cup} (x, u) = \left\{ \begin{array}{rl} ... ...\infty, & {\mbox{\rm в\ противном\ случае}}. \end{array}\right.$$

Полученное соотношение дает

$$\min_{u \ge 0}\, \max_{x \ge 0}\, L_{\cup} (x,\ u) =$$

$$= \min_{u \ge 0}\, \{ \max_{(j)}\, (b^j,\ u_j)\ \mbox{$\,\mid... ... = [\, u_1,\,...\,,u_m \,] \,\subset \, \prod_{(j)}\, M_j^* \}.$$

Задача, стоящая в правой части полученного равенства, по лемме 1 эквивалентна задаче (5.9), т.е. задаче (5.6), двойственной к (5.1). Теорема доказана.

З а м е ч а н и е 5.2. На самом деле равенство из п. 1 теоремы 5 имеет место для общей постановки задачи дизъюнктивного программирования (1.4) и ее дизъюнктивной функции Лагранжа (1.6). Проверка этого аналогична предыдущему обоснованию.

5.4. Симметричная постановка задач (5.1) и (5.6), находящихся в двойственности

Задача (5.1), к которой сводится любая задача кусочно-линейного программирования, распадается на конечное число параллельных задач

$$L_j:\ \max\, \{ (c,\ x) \mbox{$\,\mid\,$}A_jx \le b^j,\ \ x \ge 0 \},\quad j=1,\,...\,,m,$$

оптимальные значения которых и формируют оптимальное значение задачи (5.1): opt(5.1) $\,=\max\limits_{(j)}$opt$\,L_j$. Очевидным обобщением этой постановки является задача

$$\max_{(j)}\, \max\, \{ (c_j,\ x_j) \mbox{$\,\mid\,$}A_jx \le b^j,\ \ x \ge 0 \},$$

которую можно записать в эквивалентном виде:

$$\begin{array}{c} \max\, \{ f(x):=\ \max\limits_{(j)}\, (c_j... ... A_jx_j \le b^j,\ \ x_j \ge 0,\ \ j=1,\,...\,,m \}. \end{array}$$ (5.16)

В качестве двойственной к ней, согласно примененной выше схеме, выступает задача

$$\begin{array}{c} \min\, \{ f^*(u):=\ \max\limits_{(j)}\, (b^... ..._j^Tu_j \ge c_j,\ \ u_j \ge 0,\ \ j=1,\,...\,,m \}. \end{array}$$ (5.17)

Эти задачи (в предположении разрешимости L_j, $\forall _j$) связаны классическими соотношениями двойственности:

1. $f(\bar{x}) \le f^*(\bar{u})$ для
   допустимых $\bar{x}= [\, \bar{x}_1,\, \ldots\,]$ и $\bar{u}= [\, \bar{u}_1,\, \ldots\,]$;
2. opt(5.16)=opt(5.17).

В аналогичных соотношениях двойственности находится и пара задач, которая соответствует тому, что в (5.16) вместо $\max\limits_{(j)}$ берется $\min\limits_{(j)}$:

$$\max\, \{ \min_{(j)}\, (c_j,\ x_j) \mbox{$\,\mid\,$}A_jx_j \le b^j,\ \ x_j \ge 0,\ \ j=1,\,...\,,m \},$$

$$\min\, \{ \min_{(j)}\, (b^j,\ u_j) \mbox{$\,\mid\,$}A_j^Tu_j \ge c_j, u_j \ge 0,\ \ j=1,\,...\,,m \}.$$

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

$$\max\, \{ \min_{(j)}\,(\max) \, f_j(x_j)\ \mbox{$\,\mid\,$}\ x=[\, x_1, \ldots\,] \,\in\,\prod_{(j)}\, M_j \},$$

где M_j -- множество из пространства переменной x_j. Через этот тип оптимизационной операции выражается как исходная задача $\mbox{$\sigma$}$-кусочного программирования, так и формируемая для них двойственность.

Заметим также, что отмеченное свойство $f(x)\le f^*(u)$ для допустимых x и u позволяет решение задач (5.1) и (5.6) редуцировать к решению системы кусочно-линейных неравенств

$$\left. \begin{array}{l} (c,\ x)\ge \max\limits_{(j)}\, (b^j... ...\ge 0,\quad u_j\ge 0,\quad j=1,\,...\,,m. \end{array}\right \}$$ (5.18)

Связь между задачами (5.1), (5.6) и (5.18) очевидная:

$$% latex2html id marker 18942 {\,\mathrm{Arg}}(\ref{f74918})\... ...rm{Arg}}(\ref{f7491}) \,\times\, {\,\mathrm{Arg}}(\ref{f7496}),$$

здесь символ Arg(5.18) означает множество решений системы (5.18), которая является аналогом системы: $(c,\ x)\ge (b,\ u)$, $A x \le b$, $A^T u \ge c$, $x \ge 0$, $u\ge 0$ для задачи ЛП:

$$\max\, \{ (c,\ x) \mbox{$\,\mid\,$}Ax\le b,\ \ x\ge 0 \}.$$

6. Двойственность для несобственных задач
кусочно-линейного программирования

Запишем обобщения задач (5.1) и (5.6) в форме (5.16) и (5.17), несколько изменив обозначения нумерующих индексов, а именно: пусть

$$L_k:\ \max\, \{ (c_k,\ x_k)\ \mbox{$\,\mid\,$}\ A_kx_k\leq b_k,\ \ x_k\geq 0\},$$

$$L_k^*:\ \min\, \{ (b_k,\ u_k)\ \mbox{$\,\mid\,$}\ A_k^T u_k \geq c_k,\ \ u_k\geq 0\},$$

$$f(x):=\ \max_{(k)}\, (c_k,\ x_k),\quad f^*(u):=\ \max_{(k)}\, (b_k,\ u_k),$$

$$M_k:=\ \{ x_k\ \mbox{$\,\mid\,$}\ A_kx_k\leq b_k,\ \ x_k\geq 0\},$$

$$M_k^*:=\ \{ u_k\ \mbox{$\,\mid\,$}\ A_k^T u_k \geq c_k,\ \ u_k\geq 0\},$$

$$k=1,\,...\,,\bar{k}.$$

Задачи (5.16) и (5.17) можно переписать в симметричном виде

$$\max\,\{ f(x)\, \mid\, x=[\, x_1,\, \ldots\,] \in \prod\limits_{(k)} \,M_k\},$$ L: (6.1)

$$L^{\circledast}: \min\,\{ f^*(u)\, \mid\, u=[\, u_1,\, \ldots\,] \in \prod\limits_{(k)} \,M_k^*\}.$$ (6.2)

Рассмотрим ситуацию несобственности (неразрешимости) задач L и $L^{\circledast}$ с позиций построения двойственности. Поскольку формально эти задачи распадаются на совокупности задач {L_k} и {L_k^*}, то к парам взаимно двойственных задач {L_k, L_k^*}, независимо от их разрешимости или неразрешимости, можно применить схему двойственности для несобственных задач ЛП (см. [9, §25]):

$$\begin{array}{rcl} L_k & \stackrel {\textstyle \pi}{\longrig... ...tstyle \pi}{\longrightarrow } & C_k^{\char93 }\, , \end{array}$$

в силу которой задачи C_k и C_k^# разрешимы, при этом optC_k=optC_k^#. Задачи C_k и C_k^# в полном соответствии с [8, § 6] имеют вид:

$$\max\, \{ (c_k,\ x_k) - \sum_{j=1}^{m_{\scriptstyle k}} R_j^k... ...\, \mbox{$\parallel$}_{p_{\scriptstyle jk}}\, \mbox{$\,\mid\,$}$$

$$\mid\, A_0^k x_k\leq b_k^0,\ \mbox{$\parallel$}x_k^i \mbox{$... ...\scriptstyle ik}} \leq r_i^k,\ i=1,\,...\,,n_k,\ x_k\geq 0 \},$$ (6.3)

$$\min\, \{ (b_k,\ u_k) + \sum_{i=1}^{n_{\scriptstyle k}} r_i^k... ... \mbox{$\parallel$}_{q_{\scriptstyle ik}}^*\, \mbox{$\,\mid\,$}$$

$$\hspace*{-0.6cm}\mid {B_0^k}^T u_k\geq c_k^0, \mbox{$\parall... ...criptstyle jk}}^* \leq R_j^k,\ j=1,\,...\,,m_k,\ u_k\geq 0 \}.$$ (6.4)

Здесь $\{A_j^k\}_{j=0}^{m_{\scriptstyle k}}$ и $\{B_i^k\}_{i=0}^{n_{\scriptstyle k}}$ -- произвольные разрезы матрицы A_k на горизонтальные и вертикальные
подматрицы, $\{c_k^i,\ x_k^i\}$ и $\{b_k^j,\ u_k^j\}$ -- соответствующие этому разрезы векторов $\{c_k,\ x_k\}$ и $\{b_k,\ u_k\}$; $\{\mbox{$\parallel$}\,\cdot\, \mbox{$\parallel$}_{p_{\scriptstyle jk}} \}$ и $\{\mbox{$\parallel$}\,\cdot\, \mbox{$\parallel$}_{q_{\scriptstyle ik}} \}$ -- наборы норм в соответствующих пространствах; {R_j^k} и {r_i^k} -- неотрицательные параметры. Подсистемы $A_0^k x_k \leq b_k^0$, $x_k\geq 0$ и ${B_0^k}^T u_k \geq c_k^0$, $u_k\geq 0$ в (6.3) и (6.4) предполагаются совместными, что при подходяще выбранных параметрах r_i^k и R_j^k системы ограничений в задачах C_k и C_k^# становятся совместными. Смысл теоремы двойственности для C_k и C_k^# состоит в равенстве optC_k=optC_k^# ([9, теорема 25.2]).

В основу двойственности для L и $L^{\circledast}$ может быть положена схема:

$$\begin{array}{lclclcl} L & \longrightarrow & \{L_k\} & \stack... ..._k^{\char93 }\} & \longrightarrow & C^{\char93 }, \end{array}$$

при этом формирование задач C и C^# в данной схеме производится по логике формирования задач (6.1) и (6.2) из задач {L_k} и {L_k^*}.

Пусть g_k(x_k) и g_k^#(u_k) -- целевые функции в задачах (6.3) и (6.4), N_k и N_k^# -- допустимые множества этих задач; $g(x):=\ \max\limits_{(k)}\, g_k(x_k)$, $g^{\char93 }(u):=\ \max\limits_{(k)}\, g_k^{\char93 }(u_k)$. Сформируем задачи:

$$\begin{array}{rl} C: & \sup\,\{ g(x)\ \mbox{$\,\mid\,$}\ x=[... ...,] \,\in\, N^{\char93 }:=\ \prod\,N_k^{\char93 }\}. \end{array}$$

Теорема 6.1   Пусть выполнены условия:

1. Параметры r_i^k и R_j^k выбраны так, что системы ограничений в $(\ref{f7503})$ и $(\ref{f7504})$ совместны при строгих неравенствах $\mbox{$\parallel$}x_k^i \mbox{$\parallel$}_{q_{\scriptstyle ik}} < r_i^k$ $(i=1,\,...\,,n_{\scriptstyle k})$ и $\mbox{$\parallel$}u_k^j \mbox{$\parallel$}_{p_{\scriptstyle jk}}^* < R_j^k$ $(j=1,\,...\,,m_{\scriptstyle k})$.

2. Все нормы, участвующие в формировании задач {C_k} и {C_k^#}, монотонны.

3. Операция $\sup$ в C достижима (ее конечность следует из условия 1 в силу свойства $:\ g(x) \leq g^{\char93 }(u)$, $\forall \,[x,\ u] \,\in\,N \,\times\, N^{\char93 })$.

Тогда задача C^# разрешима, при этом ${\,\mathrm{opt}}C =\,{\,\mathrm{opt}}C^{\char93 }$.

Справедливость данного утверждения следует из основной теоремы двойственности для несобственных задач ЛП, на которую уже была ссылка выше, и тех соображений, которые легли в основу обоснования теоремы 4.

З а м е ч а н и е 6.1. Теорема 1 соотнесена к задаче довольно общего вида, содержит много параметров с широким диапозоном их выбора (разбиения систем ограничений на подсистемы, выбор норм, назначение числовых параметров R_j^k и r_i^k). Поэтому она допускает много частных формулировок, имеющих и самостоятельный интерес. Этот вопрос здесь детально не рассматривается, так как несколько уводит от основных акцентов данной статьи.

7. Метод точных штрафных функций для задачи кусочно-линейного программирования

Рассмотрим общую задачу кусочно-линейного программирования в канонической постановке (5.1), т.е.

$$P_{\cup}: \max \{ (c, x)\, \mid \min_{j=1,\ldots ,m} \vert A_j x -b^j \vert _{\,\max}\ \leq\ 0,\ x \ge 0 \},$$ (7.1)

с точки зрения ее эквивалентной редукции к задаче этого же типа, но со снятием основного ограничения в (7.1). Поставим задаче $P_{\cup}$ в соответствие k-задачу

$$\sup_{x \ge 0}\, [(c,\ x) -\min_{(j)}\, (R_j,\ (A_j x -b^j)^+\, )],$$ (7.2)

здесь R_j -- неотрицательный векторный параметр размерности m_j, т.е. m_j -- число неравенств в системе $A_j x - b^j \le 0$.

Как и в предыдущем параграфе, будем использовать следующие обозначения: L_j -- это задача $\max\, \{ (c,\ x)\ \mbox{$\,\mid\,$}$ $A_j x \le b^j$, $x \ge 0 \}$, L_j^* -- двойственная к ней, $\bar{u}_j =$argL_j^*, $\bar{u} = [ \bar{u}_1,\,...\,,\bar{u}_m ]$, $M_j = \{ x \ge 0 \mbox{$\,\mid\,$}$ $A_j x \le b^j \}$.

Теорема 7.1   Пусть задача $(\ref{f7511})$ разрешима, $M_j\! \ne\! \emptyset$, $\forall \,j$; $\bar{u}_j \,\in\, {\,\mathrm{Arg}}L_j^{\ast}$. Если $R_j \ge R_0\, \bar{u}_j$, R₀ > 1, то оптимальные значения и оптимальные множества задач $(\ref{f7511})$ и $(\ref{f7512})$ совпадают, т.е.

$$% latex2html id marker 17589{\,\mathrm{opt}}(\ref{f7511})\, =\,{\,\mathrm{opt}}(\ref{f7512}),$$ (7.3)

$$% latex2html id marker 17597{\,\mathrm{Arg}}(\ref{f7511})\, =\,{\,\mathrm{Arg}}(\ref{f7512}).$$ (7.4)

Д о к а з а т е л ь с т в о. Обозначим целевую функцию в (7.2) через  ${\mit\Phi}_R (x)$, а вычитаемую из $(c,\ x)$ часть -- через ${\mit\Phi}_0 (x)$. Докажем вначале равенство (7.3). Для $\bar{x}\,\in\,$Arg(7.1) получаем ${\mit\Phi}_R (\bar{x}) = (c,\ \bar{x})\, =$opt(7.1), следовательно, opt(7.2) $\, =\, \sup\limits_{x \ge 0}\, {\mit\Phi}_R (x) \ge$opt(7.1).

Докажем обратное неравенство. По теореме 2:

$$(c,\ x) -\min_{(j)}\, (\bar{u}_j,\ A_j x -b^j) \le (c, \bar{x}),\quad \forall \, x \ge 0.$$

С учетом этого неравенства оценим ${\mit\Phi}_R (x)$ для $x \ge 0$:

$$% latex2html id marker 17613\left. \begin{array}{c} {\mit\... ...12pt] \leq\,{\,\mathrm{opt}}(\ref{f7511}). \end{array}\right\}$$ (7.5)

Отсюда $\sup\limits_{x \ge 0} {\mit\Phi}_R (x) \le$opt(7.1). Таким образом, равенство (7.3) доказано. Из него, в частности, следует включение Arg(7.1)$\, \subset$Arg(7.2), что позволяет, на самом деле, в задаче (7.2) вместо $\sup$ писать $\max$. Докажем обратное включение. Пусть $\bar{x}\,\in\,$Arg(7.2). Согласно (7.5), имеем:

$$% latex2html id marker 19220 {\,\mathrm{opt}}(\ref{f7511})\, =\, {\mit\Phi}_R (\bar{x}) \le$$

$$% latex2html id marker 19222 \leq\,{\,\mathrm{opt}}(\ref{f75... ...textstyle R_0}\, \min_{(j)}\, (R_j,\ (A_j \bar{x} - b^j)^+ \,).$$

Отсюда вытекает

$$\min_{(j)}\,(R_j,\ (A_j \bar{x} - b^j)^+ \,) = 0,$$

а потому $\exists\, j_0$: $(R_{j_0},\ (A_{j_0} \bar{x} - b^{j_0})^+ \,) = 0$, что ввиду R_j0 > 0 дает $A_{j_0} \bar{x} \le b^{j_0}$. Следовательно, $\bar{x} \,\in\,M_{j_0} \,\subset \, M = \bigcup\limits_{j=1}^m\, M_j$. Допустимость вектора $\bar{x}$ для задачи (7.1) вместе с $(c,\ \bar{x})\, =$opt(7.1) означает $\bar{x}\,\in\,$Arg(7.1), а потому и Arg(7.2) $\, \subset$Arg(7.1). Доказательство равенства (7.4) также завершено.

Конструкция доказательства может быть повторена для более общей ситуации, а именно для задачи (3.1) и эквивалентной редукции ее к задаче

$$\sup_{x \ge 0}\, [ f(x) - \min_{(j)}\, (R_j,\ F_j^+ (x)) ].$$ (7.6)

Справедлива

Теорема 7.2   Пусть каждая из задач $\max \{ f(x)\ \mid$ $F_j (x) \le 0$, $x \ge 0 \}$ обладает седлом $[ \bar{x}_j,\ \bar{u}_j ]$. Тогда при $R_j > R_0\,\bar{u}_j$, R₀ > 1 задачи $(\ref{f7471})$ и $(\ref{f7516})$ эквивалентны в смысле совпадения их оптимальных значений и оптимальных множеств.

Действительно, в соответствии с теоремой 2 можно выписать неравенство

$$f(x) \le f(\bar{x}) + \min_{(j)}\, (\bar{u}_j,\ F_j(x)),\quad \forall \, x \ge 0,$$

а далее все повторить в соответствии с выкладками (7.5).

8. Вопросы полиэдральной разделимости

Задача разделимости непересекающихся множеств M и N из некоторого пространства X с помощью функции f(x) из фиксированного класса ${\cal F}_0$ называется задачей дискриминации множеств. Функция f(x) в этом случае называется дискриминантной. Разделимость состоит в выполнимости неравенств

$$f(x) > 0,\quad \forall \, x \,\in\,M;\qquad f(y) < 0,\quad \forall \, y \,\in\,N.$$ (8.1)

Можно говорить и о не строгой разделимости, когда в (8.1) допускаются не строгие неравенства.

Если M и N -- выпуклые многогранники, а ${\cal F}_0$ -- класс аффинных функций, то говорят о задаче линейной дискриминации. Задача линейной дискриминации является одной из важнейших задач в распознавании образов (РО). В качестве одной из базовых формальных моделей РО является система строгих линейных однородных неравенств. Убедимся в этом.

Пусть ${\cal G}$ и ${\cal L}$ -- некоторые образы, $A = \{a_j\} \subset$Rⁿ и $B = \{b_i\} \subset$Rⁿ -- формализованные конечные выборки представителей этих образов. Если {f_s(x)}₁^k -- некоторый базовый набор функций (вообще говоря, произвольный), то разделяющую функцию можно искать в виде $f (x) = \mbox{$\sum\limits_{s=1}^{k}$}z_s\,f_s(x)$, где {z_s} -- числовые коэффициенты. Свойство разделимости состоит в выполнимости системы неравенств:

$$\sum_{s=1}^k z_s\, f_s (a_j) > 0,\quad \forall \, j\,;\qquad \sum_{s=1}^k z_s\, f_s (b_i) < 0,\quad \forall \, i,$$

или в матричном виде

$$\bar{A} z > 0,\quad \bar{B} z < 0,$$ (8.2)

где $\bar{A}:=\ [a_{js}]$, $a_{js}:=\ f_j(a_s)$; $\bar{B}:=\ [b_{is}]$, $b_{is}:=\ f_s(b_i)$.

Если $\bar{z} = [\, \bar{z_1},\,...\,,\bar{z_k} \,]$ -- некоторое решение системы (8.2), то функция $f(x) =\mbox{$\sum\limits_{s=1}^{k}$} \bar{z}_s\, f_s(x)$ будет строго разделяющей множества A и B. Дискриминантная функция f(x) реализует правило соотнесения (по свойству принадлежности одному из образов ${\cal G}$ и ${\cal L}$) предъявляемого для распознавания вектора y по правилу:

$$y \,\in\,{\cal G},\quad \mbox{если}\quad f(y) > 0;$$

$$y \,\in\,{\cal L},\quad \mbox{если}\quad f(y) < 0.$$

Функция f(x) реализует решающее правило. Система (8.2) может быть как совместной, так и несовместной. На случай несовместности имеется обобщение понятия решения как конечной совокупности векторов $\{c_l\} \,\subset$Rⁿ (именуемой комитетным решением), такой, что любое из неравенств системы (8.2) удовлетворяется более чем половиной векторов этой совокупности. Комитетная технология и ее использование в задачах распознавания составляют важное и хорошо разработанное направление в распознавании образов [10].

Если M и N -- многогранники, причем $M \,\bigcap\, N = \emptyset$, то эти множества строго разделяются аффинной функцией. Ниже речь пойдет о разделимости произвольных непересекающихся полиэдральных множеств кусочно-линейной функцией (k-функцией).

Итак, пусть $M = \,\bigcup\limits_{(j)}\, M_j$, $N = \,\bigcup\limits_{(i)}\, N_i$, {M_j} и {N_i} -- конечные совокупности выпуклых многогранников, причем $M \,\bigcap\, N = \emptyset$. Имеет место

Теорема 8.1   Полиэдральные множества M и N с пустым пересечением строго разделяются k-функцией, т.е. функцией вида  $(\ref{f7482}):$

$$f (x) = \min_{j \in \overline{1,m}}\, \vert A_j x -b^j \vert _{\,\max}.$$ (8.3)

Д о к а з а т е л ь с т в о. Полиэдральное множество может быть задано одним k-неравенством: если $M_j = \{ x \mbox{$\,\mid\,$}A_j x \le b^j \}$ и $N_i = \{ x \mbox{$\,\mid\,$}B_i x \ge d^i \}$, то

$$M = \{ x\ \mbox{$\,\mid\,$}\ f (x) \le 0 \},$$

где f(x) -- функция (8.3);

$$N = \{ x\ \mbox{$\,\mid\,$}\ g (x) \ge 0 \},$$

где $g (x) =\max\limits_{(i)} \vert B_i x -d^i \vert _{\,\min}$. Учитывая соотношения: (X $\backslash\,M) \,\supset\, N$, (X $\backslash\,N) \,\supset\, M$, при любых $\mbox{$\alpha$}> 0$ и $\mbox{$\beta$}> 0$ будем иметь

$$\mbox{$\alpha$}\, f(x) + \mbox{$\beta$}\, g(x) < 0,\quad \forall \, x \,\in\,M;$$

$$\mbox{$\alpha$}\, f(y) + \mbox{$\beta$}\, g(y) > 0,\quad \forall \, y \,\in\,N.$$

Таким образом, построена функция $f_{\alpha,\beta} (x):= \mbox{$\alpha$}\, f(x) + \mbox{$\beta$}\, g(x)$, зависящая от числовых параметров $\mbox{$\alpha$}> 0$ и $\mbox{$\beta$}> 0$, строго разделяющая полиэдральные множества M и N.

Следствие 8.1   Пусть $\mbox{\bf R}^n \supset \{a_j\}_{j \in J}$ и $\mbox{\bf R}^n \supset \{b_i\}_{i \in I}$ -- конечные совокупности точек из $\mbox{\bf R}^n$, при этом $\{a_j\} \,\bigcap\, \{b_i\} = \emptyset$. Тогда существует k-функция f(x), строго разделяющая эти множества, т.е.

$$f(a_j) < 0,\quad \forall \, j \,\in\,J;\qquad f(b_i) > 0,\quad \forall \, i \,\in\,I.$$

Д е й с т в и т е л ь н о, поскольку точка из Rⁿ может быть задана конечной системой линейных неравенств (если $\bar x = [\, \bar{x}_1,\,...\,,\bar{x}_n \,]$, то $\bar x = \{ x \mbox{$\,\mid\,$} \bar x \le x \le \bar x \}$), сформулированное следствие превращается в частный случай теоремы 1.

На самом деле, в данном следствии пространство, из которого берутся точки, может быть произвольным. Сведение к конечномерному арифметическому пространству тривиально: достаточно взять подпространство E_k исходного пространства, натянутое на совокупность $\{a_j\}_{j \,\in\,J} \,\bigcup\, \{b_i\}_{i \,\in\,I}$, выделить его некоторый базис, в котором векторы a_j и b_i будут представлены точками конечномерного арифметического пространства. Если взять прямое разложение X=E_k+H, то k-функция f(x), разделяющая указанные совокупности точек в E_k, может быть продолжена до k-функции $\bar{f}(x)$, определенной на всем пространстве X, по правилу: если $x \,\in\,$X и $x = \bar{x} + h$, $\bar{x}\,\in\,$E_k, $h \,\in\,$H, то $\bar{f}(x) =f(\bar{x})$.

СПИСОК ЦИТИРОВАННОЙ ЛИТЕРАТУРЫ

1. Плотников С.В. Методы проектирования в задачах нелинейного программирования. Дисс. ...канд. физ.-мат. наук. -Свердловск: УрГУ, 1983. -С. 83-118.
   
2. Волокитин Е.П. О представлении непрерывных кусочно-линейных функций // Управляемые системы. -Новосибирск: Наука, 1979. - 19. -C. 14 - 21.
   
3. Benchekroun B. A nonconvex piecewise linear optimization problem // Computers Math. Applic., 1991. -V. 21,  6/7. -P. 77 - 85.
   
4. Gorokhovik V.V., Zorko O.I. Piecewise affine functions and polyhedral sets // Optimization, 1994. -V. 33. -P. 209 - 221.
   
5. Kripfganz A., Schulze R. Piecewise affine functions as a difference of two convex functions // Optimization, 1987. -V. 18,  1. -P. 23 - 29.
   
6. Meltzer D. On the expressibility of piecewise linear continuous functions as the difference of two piecewise linear convex functions // Math. Program., Study 29, 1986. -P. 118 - 134.
   
7. Исследования по линейному и нелинейному программированию // Сб. работ под ред. K. Дж. Эрроу, Д. Гурвица, Х. Удзавы. -M.: ИЛ, 1962. -298 c.
   
8. Еремин И.И., Мазуров В.Д., Астафьев Н.Н. Несобственные задачи линейного и выпуклого программирования. -М.: Наука, 1983. -336 с.
   
9. Еремин И.И. Теория линейной оптимизации. -Екатеринбург: изд-во ``Екатеринбург'', 1999. -312 с.
   
10. Мазуров В.Д. Метод комитетов в задачах оптимизации и классификации. -М.: Наука, 1990. -246 с.