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

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

1. Постановка задачи, обозначения и определения

Под паретовской задачей линейного программирования будем понимать задачу характеризации (теоретической или алгоритмической) оптимального множества Arg$_\pi$ задачи

$$\mbox {$\max_{\pi}$} \{ C^Tx\ \mid \ Ax\leq b,\ \ x\geq 0 \}.$$ (1.1)

Здесь $\pi\, -\,$символ паретовской оптимизации, $C^T\!\!=\! [c_1,..., c_k]$, $c_j\in$Rⁿ (запись векторов столбцовая), $b\in$R^m, $M_0\! =\! \{ x\geq~\!\!0\,\mid$$Ax\leq b \}$, ${\mbox{Arg}}_{\pi}$ $(1.1)\!:=\! \{ \bar{x}\in M_0\, \vert \tilde {x}\in M_0 \& C^T \tilde {x} \geq C^T\bar{x} \Rightarrow C^T\tilde {x} = C^T \bar{x} \}.$

Под задачей последовательного (лексикографического) программирования понимается заключительная из задач

$$\begin{tabular}{lr} \hspace*{1.5cm}$ \max \{ (c_{j_k},\ x)\ ... ....2)_2 \}$}\ , & \hspace{0.9cm}$(1.2)_1$\ \ \ \\ \end{tabular}$$

где $(j_k,..., j_1)=p\ -\$некоторая перестановка индексов { j }₁^k. Для определенности в дальнейшем будем полагать j_s=s, s=1,..., k. Кратко задачу последовательного программирования будем записывать в форме

$$\max\nolimits_p \{ C^Tx\ \mid \ Ax\leq b,\ \ x\geq 0 \}.$$ (1.2)

В дальнейшем вектор b будет задаваться параметрически b=b(r), в частности, одним из следующих способов: $b(r)=Br,\ \ b(r)=b_0+Br,\ \ b(r)=\sum_{i=1}^l B_ir^i$, где матрицы $B,\ B_i$ и векторы $b_0,\ r,\ r^i$ согласованных размеров. Этого требует обеспечение симметричной двойственности для соответствующих задач.

Синтез постановок (1.1) и (1.2) реализуется в форме:

$$\max\nolimits_{p,\pi} \left \{ \left [ \begin{array}{c} C_... ...\end{array}\right ] \ \mid \ Ax\leq b ,\ \ x\geq0 \right \} .$$ (1.3)

Выше $p\ -\$перестановка индексов { j }₁^k, которую мы принимаем как (k, k-1,..., 1). Задача (1.3) понимается как заключительная из задач:

$$\begin{tabular}{lr} \hspace*{1.0cm} $\max_{\pi} \{ C_k^Tx\ \... ...3)_2 \} $}\ . & \hspace{0.5cm}$(1.3)_1$\ \ \ \\ \end{tabular}$$

Положив $\omega = [p,\ \pi ]$, под $\mbox{Arg}{\mbox{$_\omega$}}$(1.3) будем понимать $\mbox{Arg}{\mbox{$_{\pi}$}}\, (1.3)_1$. При $b=b(r) = \sum_{i=1}^l B_i r^i$ задача (1.3), принимающая вид

$$\max\nolimits_{p,\pi} \left \{ \left [ \begin{array}{c} C_... ...ight ]\ \mid \ Ax\leq \sum_{i=1}^l B_i r^i, x\geq0 \right \},$$ (1.4)

допускает формулировку формально двойственной задачи того же содержательного смысла:

$$\min\nolimits_{q,\pi} \left \{ \left [ \begin{array}{c} B_l^... ...^Tu\geq \sum_{j=1}^k C_j R^j, u\geq0 \right \} ,\eqno (1.4)^{W}$$

где $R^j\ -\$система векторных параметров, $q\ -\$перестановка индексов { i }₁^l, относительно которой будем, для определенности, полагать: q= (l, l-1,..., 1). Символ W обозначает правило перехода от задачи (1.3) к (1.3)^W: $(1.3)\ \stackrel {W} {\longrightarrow }\ (1.3)^{W}$.

Содержательные теоремы двойственности будут формулироваться через связь задач (1.3) и (1.3)^W с задачами, скаляризующими последние:

$$\max\, \{ \sum_{j=1}^k (C_j^Tx,\ R^j )\ \mid Ax\leq \sum_{i=1}^l B_ir^i,\ \ x\geq0 \},\eqno (1.4)_{scal}$$

$$\min\, \{ \sum_{i=1}^l (B_i^Tu,\ r^i )\ \mid A^Tu\geq \sum_{j=1}^k C_jR^j,\ \ u\geq0 \}.\eqno (1.4)_{scal}^W$$

Последние две задачи являются взаимно двойственными в классическом смысле, т.е. $(1.4)_{scal}^{\ast} \equiv (1.4)_{scal}^W$. Символ $(\ast)$ здесь и в дальнейшем будет означать классическое правило формирования двойственной задачи в линейном программировании (ЛП). Характер потенциальных связей выписанной четверки задач определяется схемой:

$$\begin{array}{lcl} (1.4) & \stackrel {\supset} {\longrightar... ... \ (1.4)_{scal}^{\ast})\ .\\ & \mbox {Схема 1} & \end{array}$$

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

Отметим, что $\omega$-задача (1.4) ( $\omega = [p,\ \pi ]$)$\ -\$трудная задача как в смысле идентификации $\mbox{Arg}\mbox{$_{\omega}$}\,$(1.4), так и (тем более!) в смысле реализации cхемы 1. Здесь трудности принципиального свойства. Поэтому нами будут рассматриваться отдельные типы задач названного класса.

Задачу (1.4) назовем задачей (k, l)-типа, (1.4)^W будет иметь (l, k)-тип. Обычная задача ЛП $\max \{ (c, x)\ \mid\ Ax \leq b$, $x\geq0\}$ и двойственная к ней $\min \{ (b,\ u)\ \mid\ A^Tu\geq c,\ u\geq 0 \}$ будут иметь (0, 0)-тип.

Выделим частный случай задач (1.4), (1.4)^W, а именно:

$$\max\, \{ (c_0,\ x)\ \vert \ x\in \mbox{Arg}\mbox{$_{\pi}$} \max \{ C^Tx\ \vert$$

$$\vert\ Ax\leq b_0+Br,\ x\geq 0 \} \}$$ (1.5)

в паре с W-двойственной:

$$\min\, \{ (b_0,\ u)\ \vert \ u\in \mbox{Arg}\mbox{$_{\pi}$} \... ... B^Tu\ \vert \ A^Tu \geq c_0 +CR,\ u\geq 0 \} \}. \eqno(1.5)^W$$

Это взаимно двойственные задачи поиска экстремума линейной функции на паретовских множествах соответствующих линейных многокритериальных задач. Постановка задачи (1.5) как таковой, а также проблемы двойственности (1.5) $\stackrel {\stackrel {W}{\longrightarrow }} {\longleftarrow }$ (1.5)^W, имеют самостоятельный интерес. Этому будет посвящен отдельный параграф.

2. Некоторые сведения по алгебре многогранников

Под многогранником M (выпуклым) будем понимать множество решений совместной конечной системы линейных неравенств

$$Ax\leq b\ \sim\ (a_j,\ x)-b_j\leq 0,\ \ \ j=1,...,m .$$ (2.1)

Множество решений (если оно не пусто) k-граничной системы [1]

$$\left. \begin{array}{ll} (a_{ j_s},\ x) - b_{ j_s} = 0, & ... ...\ x) - b_j \leq 0, & \forall j\neq j_s \end{array}\right \}\$$ (2.2)

называется k-гранью многогранника M, при этом считаем векторы { a _js }_s=1^k линейно независимыми.

Неравенство

$$(c,\ x)-\mbox{$\alpha$}\leq 0$$ (2.3)

есть следствие (по определению) системы (2.1), если $\forall \bar{x} \in M\ \Rightarrow \ (c,\ \bar{x} )-\mbox{$\alpha$}\leq 0$, при этом:

1) неравенство (2.3)$\ -\$следствие 1-го рода, если существует $\mbox{$\varepsilon$}>0$ такое, что $(c,\ x)-$ $\mbox{$\alpha$}\leq -\mbox{$\varepsilon$} -\$следствие системы (2.1);

2) в противном случае (2.3)$\ -\$следствие 2-го рода.

Отметим [1,2] некоторые элементарные сведения по алгебре многогранников и факты, из них вытекающие.

1⁰. Для любого k=1,..., r, где $r\ -\$ранг системы { a_j }^m_j=1, существует по крайней мере одна k-грань. Если r=n, то n-грань$\ -\$это вершина многогранника M.

2⁰. Если (2.3)$\ -\$следствие 2-го рода системы (2.1), то $M\ \cap \ \mbox {\normalsize\it П} \ \neq \emptyset$, где $\mbox {\normalsize\it П} = \{ x\ \mid \ (c,\ x) =\mbox{$\alpha$}\}$. В этом случае $\mbox{$\alpha$}=\max \{ (c,\ x)\ \mid \ x\in M \}$.

3⁰. Оптимальное множество задачи ЛП является некоторой k-гранью многогранника ограничений.

4⁰. Если $c=\sum_{s=1}^k \leftarrow _{ j_s} a_{ j_s}$, $\leftarrow _{ j_s} > 0$, { a _js }_s=1^k линейно независимы, то оптимальным множеством задачи $\max \{ (c,\ x)\ \mid x\in M \}$ является k-грань, задаваемая системой (2.2).

5⁰. Пусть $\{ M_j \}\ -\$конечная совокупность
многогранников и N =co $\overline {\cup_{(j)} M_j}$. Если $(c, x) - \mbox{$\alpha$}\leq 0\ -\$следствие 2-го рода
множества N (т.е. $(c, \bar{x}) - \mbox{$\alpha$}\leq 0$, $\forall \bar{x} \in N$; $\forall \mbox{$\varepsilon$}>0$, $\exists \bar{x} \in N: (c, \bar{x}) - \mbox{$\alpha$}>-\mbox{$\varepsilon$})$, то $\overline{(\cup_{(j)}\, M_j)}\, \cap \, \mbox{\it П} \neq \emptyset$. Это аналог свойства 2⁰ на случай, когда в роли исходного множества выступает объединение конечного числа многогранников. Здесь же отметим, что $N\ -\$многогранник.

3. Характеризация задач простейших типов

3.1. Задача (0, 1)-типа

Для задачи

$$\max \{ (c,\ x)\ \mid \ Ax\leq Br,\ \ x\geq 0 \}$$ (3.1)

W-двойственной будет

$$\min\nolimits_{\pi} \{ B^Tu\ \vert \ A^Tu\geq c,\ u\geq 0 \},\eqno(3.1)^W$$

а ее скаляризующей$\ -\$

$$\min\, \{ (B^Tu,\ r)\ \vert \ A^Tu\geq c,\ u\geq 0 \}.\eqno (3.1)_{scal}^W$$

Связь между выписанными задачами выражается простой схемой:

Эта схема реализуется при любом r>0, обеспечивающим разрешимость задачи (3.1), что эквивалентно условиям: 1) система $Ax\leq Br$, $x\geq 0$ совместна; 2) $c\in$cone{ a_j}.

Заметим, что задача (1, 0)-типа рассматривается аналогично.

3.2. Задача (1, 1)-типа

Для задач

$$\max\nolimits_{\pi} \{ C^Tx\ \vert \ Ax\leq Br,\ x\geq 0 \},$$ (3.2)

$$\min\nolimits_{\pi} \{ B^Tu\ \vert \ A^Tu\geq CR,\ u\geq 0 \}\eqno (3.2)^W$$

скаляризующими соответственно будут:

$$\max\, \{ (C^Tx,\ R)\ \vert Ax\leq Br,\ x\geq 0 \},\eqno (3.2)_{scal}$$

$$\min\, \{ (B^Tu,\ r)\ \vert \ A^Tu\geq CR,\ u\geq 0 \}.\eqno (3.2)_{scal}^W$$

При любых r>0 и R>0, обеспечивающих совместность систем ограничений в (3.2) и (3.2)^W, реализуется схема:

$$\begin{array}{rcc} (3.2)\ \ & \stackrel {\supset} {\longrigh... ...rrow } & (3.2)_{scal}^W\ .\\ & \mbox {Схема 3} & \end{array}$$

Задачи (2, 0) и (2, 1)-типов и двойственность, с ними связанная, требуют особого анализа.

4. Анализ $\omega$-задач (2,i)-типа, i=0,1

Выпишем задачи

$$\max\nolimits_{\omega} \left \{ \left [ \begin{array}{c} C... ...x \end{array}\right ] \ \vert \ Ax\leq b,\ x\geq0 \right \},$$ (4.1)

$$\max\, \{ (C_2^Tx,\ R^2 ) + (C_1^Tx,\ R^1)\ \vert x\in M_0 \}.\eqno (4.1)_{scal}$$

Для облегчения восприятия задачи (4.1) запишем ее в непосредственной смысловой интерпретации:

$$\max\nolimits_{\pi} \{ C_1^Tx\ \vert \ x\in \mbox{Arg}\, \max\nolimits_{\pi} \{ C^T_2x\ \vert \ x\in M_0 \}\}.$$

Лемма 4.1 [3]. Имеет место эквивалентность (в смысле совпадения оптимальных множеств) задач:

$$\max \{ (c^1,\ x)\ \mid\ x\in \mbox {Arg}\, \max \{ c^2,\ x)\ \mid\ Ax\leq b,\ x\geq 0 \} \},$$

$$\max \{ (c^1,\ x) + R_0\, (c^2,\ x)\ \mid\ Ax\leq b,\ x\geq0 \}$$

при всех $R_0>\bar{R}_0$, где $\bar{R}_0\ -\$некоторое неотрицательное число, не зависящее от вектора b правых частей ограничений.

В этой лемме речь идет об известном факте о двухэтапной задаче последовательного программирования.

Лемма 4.2. Пусть задача (1.1) разрешима. Тогда существует конечный набор векторов $\{ R^j\}^{\bar{j}}_1\ -\$инвариантный относительно вектора b, при котором

$$\mbox{Arg}{\mbox{$_{\pi}$}}\,(1.1) = \bigcup_{j=1}^{\bar{j}} \mbox{Arg}\, \max\, \{ (C^Tx,\ R^j)\ \mid\ Ax\leq b,\ x\geq0 \}.$$

Этот факт хорошо известен и вполне элементарен, в формулировке только подчеркивается уточнение, связанное с инвариантностью выбора $\{ R^j \}^{\bar{j}}_1$ относительно b.

Для полноты приведем о б о с н о в а н и е леммы. Множество $\mbox{Arg}{\mbox{$_{\pi}$}}$(1.1) совпадает с

$$\bigcup_{R>0} \mbox{Arg}\, \max\, \{ (C^Tx,\ R)\ \mid\ x\in M_0 \}.$$

Каждое из составляющих множеств является некоторой гранью многогранника M₀ (см. п. 2, 3⁰). Поэтому взяв для каждой такой грани по одному R, получим требуемое. Что касается уточнения, о котором шла речь, то его обоснование можно провести вполне конструктивно. А именно, в качестве R^j, соотнесенное грани с номером j, можно взять то значение для R, которое возникает в силу соотношения

$$\sum^k_{t=1}R^j_tc_t\in\, {\mbox{cone}}_{\,t\in J_j}\, \{a_t \},$$ (4.2)

где множество $J_j\ -\$множество { j_s }, фигурирующее в общем определении грани (см. (2.2)), но только поставленное в соответствие грани с номером j.

Теорема 4.1. Если задача (4.1) разрешима, то при некоторых R¹>0, R²>0 имеет место включение

$$\mbox{Arg}\, (4.1)_{scal}\ \subset \ \mbox{Arg}_{\omega}\,(4.1).$$ (4.3)

Д о к а з а т е л ь с т в о. В силу леммы 4.2 и 3⁰ из п. 2 имеем: Arg $\mbox{max}_{\pi} \{ C_2^Tx\ \vert x\in M_0 \} = \bigcup\limits_{j\in J}$Г_j, {Г$_j\}_J\ -\$некоторая совокупность
граней многогранника M₀. Образуем $M=\overline{ {\mbox{co}}\,\{ {\mbox{\it Г}}_j\}_J }$, т.е. замыкание выпуклой оболочки выписанной совокупности граней, и рассмотрим задачу

$$\max\nolimits_{\pi}\, \{ C^T_1x\ \mid\ x\in M \}.$$ (4.4)

По той же причине

$$\mbox{Arg}_{\pi}\, (4.4)\ = \bigcup_{i\in I}\widetilde {\mbox{\it Г\ }}_{\!\!\!\!i},$$

где $\{\,\widetilde {\mbox{\it Г\, }}_{\!\!\!\!i}\, \}_I\ -\$некоторая совокупность граней многогранника M. Нас будет интересовать множество

$$S = \{ (ji)\ \mid\ {\mbox{\it Г}}_j\ \bigcap \widetilde {\mbo... ... Г\ }}_{\!\!\!\!i} = \!\!{\mbox{\it Г}}_{ji} \neq \emptyset \}.$$

В силу свойства 5⁰ из п. 2 множество S непусто. Так как $\widetilde {\mbox{\it Г\ }}_{\!\!\!\!i}\ -\$паретовское множество на M, то $\{\! {\mbox{\it Г}}_{ji} \}_{(ji)\in S}\ -$ паретовское (как часть $\widetilde {\mbox{\it Г\ }}_{\!\!\!\!i}$) как на M, так и на его подмножестве $\bigcup\limits_{j\in J}\!\!{\mbox{\it Г}}_j$, более того - и на Г_j. Вот такую пару $(ji)\in S$ и рассмотрим. Далее:

1) Г_j выступает в качестве оптимального множества задачи

$$\max\, \{ (C^T_2x,\ \bar{R}^2 )\ \mid\ x\in M_0 \}$$

при некотором $\bar{R}^2 >0$.

2) $\widetilde {\mbox{\it Г\ }}_{\!\!\!\!i}$ является оптимальным множеством задачи

$$\max\, \{ (C^T_1x,\ R^1)\ \mid\ x\in M\}$$

при некотором R¹>0. Функционал последней задачи определяет оптимальное множество Г_ji на Г_j. Так что:

a) Arg $\max\, \{ (C^T_2x,\ \bar{R}^2 )\ \mid\ x\in M_0 \} =$Г_j,

b) Arg $\max\, \{ (C^T_1x,\ R^1)\ \mid x\in$Г_j } =Г_ji,

при этом Г$_{ji}\in$ $\mbox{Arg}\mbox{$_{\omega}$}$(4.1). По лемме 4.1 существует $\bar{R}_0$ такое, что при любом $R_0>\bar{R}_0$

$$\mbox{Arg}\, \max \{ (C^T_1x, R^1) + R_0 (C^T_2x, \bar{R}^2 )\ \vert x\in M_0 \} =$$

$$= \mbox{\it Г}_{ji}\subset \mbox{Arg}\mbox{$_{\omega}$}\,(4.1),$$

что и доказывает теорему (т.е. включение 4.3) при найденных R¹ и $R^2 = R_0\bar{R}^2$.

Рассмотрим теперь задачу (2, 1)-типа:

$$\max\nolimits_{\omega}\, \left \{ \left [ \begin{array}{c} ... ...1^Tx \end{array}\right ]\ \mid\ Ax\leq Br,\ x\geq0 \right \}$$ (4.5)

и W-двойственную:

$$\min\nolimits_{\pi}\, \{ B^Tu\ \mid\ A^Tu\geq C^T_1 R^1 + C^T_2 R^2,\ u\geq 0 \}.\eqno(4.5)^W$$

Теорема 4.2. При любом $r \geq0$, обеспечивающим совместность системы ограничений в (4.5), из разрешимости задачи (4.5) вытекает существование R¹>0 и R²>0 таких, что реализуется схема:

$$\begin{array}{rcc} (4.5)\ \ & \stackrel {\supset} {\longrigh... ...rrow } & (4.5)_{scal}^W\ .\\ & \mbox {Схема 4} & \end{array}$$

Понятно, что скаляризация задачи (4.5) осуществляется с помощью векторных параметров R¹ и R², а скаляризация задачи (4.5)$^W\ -\$с помощью r. Верхнее включение в схеме 4 выполняется в силу доказанной теоремы 4.1. Нижнее включение является тривиальным.

Еще раз подчеркнем, что правые задачи в cхеме 4 являются взаимно двойственными в классическом смысле.

Естественно, может быть сформулирован аналог теоремы 4.2 для симметричной постановки задачи, а именно, для задачи (1, 2)-типа:

$$\max\nolimits_{\pi}\, \{ C^Tx\ \mid\ Ax\leq B_1r^1 + B_2r^2,\ x\geq 0 \},$$

двойственной к которой будет

$$\min\nolimits_{\omega}\, \left \{ \left [ \begin{array}{c}B_... ...^Tu \end{array} \right ]\ \mid\ A^Tu\geq CR,\ u\geq0 \right \}.$$

5. $\!$Теорема двойственности для задач (1.5), (1.5)^W

Теорема двойственности для задач (1.5) и (1.5)^W будет формулироваться через связь с задачами, скаляризующими последние:

$$\max\, \{(c_0,\ x) + (C^Tx,\ R)\ \mid\ Ax\leq b_0 + Br, x\geq0 \},\eqno (5.1)_{scal}$$

$$\min\, \{(b_0,\ u) + (B^Tu,\ r)\ \mid\ A^Tu\geq c_0 + CR, u\geq0 \}.\eqno(5.1)_{scal}^{\ast}$$

Речь идет о реализации схемы:

$$\begin{array}{rcc} (1.5)\ \ & \stackrel {\supset} {\longrigh... ...} & (5.1)_{scal}^{\ast}\ .\\ & \mbox {Схема 5} & \end{array}$$

Множество {j₁,..., j_k } из определения k-граничной системы (2.2) назовем индексным идентификатором этой системы. Определение индексного идентификатора не зависит от реализации правых частей системы ограничений.

Применительно к внутренним задачам для (1.5) и (1.5)^W, а именно:

$$\max\nolimits_{\pi}\, \{ C^Tx\ \mid Ax\leq b_0 + Br,\ x\geq0 \},$$ (5.2)

$$\min\nolimits_{\pi}\, \{ B^Tu\ \mid\ A^Tu\geq c_0 + CR, u\geq0 \},\eqno (5.2)^W$$

множествами J_j и I_i идентификаторов (для систем ограничений выписанных задач) будут такие совокупности индексов j и i, для которых выполняются условия:

$$\sum_{t=1}^k R_t^j c_t\in \mbox{cone}_{s\in J_j} \{a^T_s\}$$ (5.3)

при некотором R^j>0;

$$\sum_{t=1}^l r_t^i b_t\in \mbox{cone}_{s\in I_i} \{h_s\}$$ (5.4)

при некотором rⁱ>0. Здесь мы полагаем C = [c₁,..., c_k], B = [b₁,..., b_l]; A^T = [a₁,..., a_m], A = [h₁,..., h_n], т.е. $a^T_j\ -$ j-я строка матрицы A, $h_i\ -\$ее i-й столбец.

В силу свойства 4⁰ из п. 2 выписанные идентификаторы определяют те грани многогранников $M(r):=\{ x\geq0\ \mid \ Ax\leq b_0 + Br \}$, $M^{\ast}(R) = \{ u\geq 0\ \mid \ A^Tu\geq c_0 + CR \}$, которые выступают в качестве оптимальных множеств задач

$$\max \{ (C^Tx,\ R^j)\ \mid \ x\in M(r) \},$$ (5.5)

$$\min \{ (B^Tu,\ r^i)\ \mid \ u\in M^{\ast}(R) \}$$ (5.6)

при $M(r)\neq \emptyset ,\ \ M^{\ast}(R) \neq \emptyset$.

В дальнейшем будут оговариваться условия, при которых $M(r^i) \neq \emptyset$, $M^{\ast}(R^j) \neq \emptyset$. В предположении выполнимости (5.3) и (5.4) положим Г_ji:=Arg(5.5) $\mid_{r=r^{\scriptstyle i}}$, Г $_{ji}^{\ \ast}$:=Arg(5.6) $\mid_{R=R^{\scriptstyle j}}$, т.е. {Г_ji} и {Г $_{ji}^{\ \ast} \}\ -\$ те совокупности граней многогранников M(rⁱ) и $M^{\ast}(R^j)$, которые являются оптимальными множествами задач

$$\max \{ (C^Tx,\ R^j)\ \mid\ x\in M(r^i) \},$$

$$\min \{ (B^Tu,\ r^i)\ \mid\ u\in M^{\ast}(R^j) \}.$$

Множества {R^j} и {rⁱ}, отвечающие выбранным совокупностям граней {Г_ji } и {Г $_{ji}^{\ \ast} \}$, назовем характеристическими.

В силу леммы 4.1 для каждого i существует j=j(i), при котором

$$\mbox{Arg}\,\max\, \{ (c_0,\ x)\ \mid\ x\in {\mbox{\it Г}}_{ji}\} =$$

$$= \mbox{Arg}\,\max\, \{ (c_0,\ x) + (C^Tx,\ R^j)\ \mid\ x\in M(r^i) \}.$$

Аналогично: для каждого j существует i=i(j), при котором

$$\mbox{Arg}\, \min\,\{(b_0,\ u)\ \mid u\in {\mbox{\it Г}}_{ji}^{\ \ast} \} =$$

$$= \mbox{Arg}\, \min\, \{(b_0,\ u) + (B^Tu,\ r^i)\ \mid u\in M^{\ast}(R^j) \}.$$

Характеристические множества {R^j} и {rⁱ} назовем равновесными, если

$$\exists j_0,\ i_0:\ j(i_0) = j_0,\ \ i(j_0) = i_0.$$ (5.7)

Теорема 5.1. Пусть задачи $L_{ij}:\ \max \{(c_i, x)\ \vert \ Ax\leq b_j$, $x\geq0\}$, i=0,1,..., k; j=0, 1,..., l разрешимы. Для существования R>0, r>0, реализующих схему 5, необходимо и достаточно существование равновесных характеристических множеств.

Д о к а з а т е л ь с т в о. Положим

$$\mbox{$\alpha$}(j,\ i)=\max\, \{ (c_0,\ x)\ \mid\ x\in \mbox{\it Г}_{ji} \},$$

$$\mbox{$\beta$}(j,\ i)=\min\, \{ (b_0,\ u)\ \mid u\in \mbox{\it Г}^{\ \ast}_{ji} \}.$$

Условия (5.7) можно записать в виде:

$$\left. \begin{array}{c} \max_j \mbox{$\alpha$}(j,\ i_0) = \mb... ...box{$\beta$}(j_0,\ i_0 ), \end{array}\right \} \eqno(5.7)^{'}$$

что влечет

$$\mbox{$\alpha$}(j,\ i_0 )\leq \mbox{$\alpha$}(j_0,\ i_0 ),\ \... ...x{$\beta$}(j_0,\ i)\geq \mbox{$\beta$}(j_0,\ i_0 ),\ \forall i.$$

Следовательно,

$$\mbox{$\alpha$}(j_0,\ i_0 ) = \max \{ (c_0,\ x)\ \mid \ x\in \bigcup_{j}\mbox{\it Г}_{j i_0} \}\ ,$$

$$\mbox{$\beta$}(j_0,\ i_0 ) = \min \{ (b_0,\ u)\ \mid \ u\in \bigcup_i \mbox{\it Г}^{\ \ast}_{ j_0i} \}\ .$$

Но так как

$$\bigcup_j \mbox{\it Г}_{j i_0} = \mbox{Arg\,(1.5)} \mid_{ r =r^{\scriptstyle i_0},\, R=R^{\scriptstyle j} }\, ,$$

$$\bigcup_i \mbox{\it Г}^{\ \ast}_{ j_0i} = \mbox{Arg\,(1.5)}^W \mid_{ R=R^{\scriptstyle j_0},\, r=r^{\scriptstyle i} }\, ,$$

то тем самым обеспечиваются верхнее и нижнее включения в схеме 5 при R=R^j₀ и r=r^i₀.

Условия (5.7) и необходимы. Действительно, если при некоторых $\bar{R} \geq 0$ и $\bar{r} \geq 0$ реализуется схема 5, то положим $\bar{R}=R^{j_0}$, $\bar{r}=r^{i_0}$. Дополним эти векторы до полных характеристических множеств { R^j }, { rⁱ }. Тогда по смыслу включений в схеме 5 получаем соотношения (5.7) (или (5.7)^', что одно и то же).

6. Случай несобственной задачи ЛП

Далее будет рассмотрен вариант теоремы 5.1, относящийся к ситуации неразрешимости (несобственности) задачи линейного программирования:

$$L:\ \max \{ (c,\ x)\ \mid \ Ax\leq b,\ \ x\geq 0 \}.$$

В работе [4] для несобственных задач ЛП была предложена и реализована схема двойственности:

$$\begin{array}{rcl} L & \stackrel {\Pi} {\longrightarrow } & ... ... } & P^{\char93 }\, .\\ \\ & \mbox {Схема 6} & \end{array}$$

В ней $L^{\ast}\ -\$задача ЛП, двойственная к L, т.е.

$$L^{\ast}:\ \min \{ (b,\ u)\ \mid\ A^Tu\geq c,\ \ u\geq 0 \};$$

$\Pi \ -\$правило отображения L и $L^{\ast}$ в P и P^# такое, что P и P^# разрешимы, при этом optP=optP^# (теорема двойственности). Одна из частных реализаций задач P и P^# в схеме 6 такова:

$$P:\ \max \{ (c,\ x) -\sum_{j=1}^{m_0} R_j\, \mbox{$\parallel$}( A_jx -b^j)^+ \mbox{$\parallel$}_j\ \mid \ A_0x\leq b^0\ ,$$

$$x\geq 0,\ \ \ \mbox{$\parallel$}x^i \mbox{$\parallel$}^{\ast}_i \leq r_i, i=1,..., n_0 \}\ ,$$

$$P^{\char93 }:\ \min \{ (b,\ u )+ \sum_{i=1}^{n_0} r_i\, \mbox... ...^i -B_i^T u )^+ \mbox{$\parallel$}_i\ \mid \ B_0^Tu \geq c^0\ ,$$

$$u\geq 0,\ \ \ \mbox{$\parallel$}u^j \mbox{$\parallel$}^{\ast}_j \leq R_j, j=1,..., m_0 \}\ ,$$

где A_j и $B_i\ -\$подматрицы разбиения матрицы A на горизонтальные и вертикальные фрагменты:

$$A=\left [ \begin{array}{c} A_0\\ .\ .\ .\ \\ A_{m_0} \end{array}\right ] =[B_0\ .\ .\ .\ B_{n_0} ];$$ (6.1)

$\{ b^j \},\ \{u^j \}$ и $\{ c^i \},\ \{ x^i \}\ -$разбиения векторов $b,\ u$ и $c,\ x$ на подвекторы, отвечающие разбиению (6.1); ``+'' над вектором означает замену его отрицательных координат нулями (положительная срезка); $\{ \mbox{$\parallel$}\cdot \mbox{$\parallel$}_j \}_1^{m_0},$ $\{ \mbox{$\parallel$}\cdot\mbox{$\parallel$}_i \}_1^{n_0}\ -\$произвольный набор норм в пространствах соответствующей размерности; $(\ast)$ над нормой $\mbox{$\parallel$}\cdot \mbox{$\parallel$}$ определяет сопряженную норму; $\{ r_i \}_1^{n_0}, \{R_j \}_1^{m_0}\ -$ системы неотрицательных параметров. Те или иные фрагменты разбиения матрицы A могут принимать значения $\emptyset$.

Заметим, что в задачах P и P^# подсистемы $A_0x\leq b^0$, $x\geq 0$ и $B_0^Tu\geq c^0$, $u\geq 0$ предполагаются совместными (выбор таких совместных подсистем из систем $Ax\leq b$, $x\geq 0$ и $A^Tu \geq c$, $u\geq 0$ всегда можно обеспечить; например, в содержательном плане: эти подсистемы$\ -\$набор согласованных директивных требований).

Для более компактной записи последующих задач введем обозначения:

$${\cal F}_x = \{ \mbox{$\parallel$}(A_jx -b^j )^+ \mbox{$\para... ...$\parallel$}(c^i -B_i^Tu )^+ \mbox{$\parallel$}_i \}_1^{n_0}\ ,$$

$$M(r) =\{ x\ \mid\ A_0x\leq b^0,\ x\geq 0,\ \mbox{$\parallel$} x^i \mbox{$\parallel$}_i^{\ast} \leq r_i,\ i=1,..., n_0 \} ,$$

$$M^{\char93 } (R) =\{ u\, \mid\, B_0^Tu\geq c^0,\ u\geq 0, \mb... ...lel$}u^j \mbox{$\parallel$}_j^{\ast}\leq R_j,\ j=1,..., m_0 \}.$$

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

$$P_{\pi}:\ \mbox {$\max_{\pi}$} \{ -{\cal F}_x\ \mid x\in M(r) \},$$

$$P_{\pi}^{\char93 }:\ \mbox {$\min_{\pi}$} \{ {\cal F}_u \mid \ u\in M^{\char93 }(R) \},$$

а также

$$Q_{\pi,\, lex}:\ \max \{ (c,\ x)\ \mid \ x\in \mbox {Arg}\ P_{\pi} \},$$

$$Q^{\char93 }_{\pi,\, lex}:\ \min \{ (b,\ u)\ \mid \ u\in \mbox {Arg}\ P_{\pi}^{\char93 } \}.$$

Легко заметить, что последние две задачи являются аналогами задач (5.2), (5.2)^W и (1.5), (1.5)^W, аналоги задач $P,\ P^{\char93 }\ -\$это задачи (5.1)_scal, $(5.1)^{\ast}_{scal}$.

В описанной ситуации схема 5 принимает вид:

$$\begin{array}{lcl} Q_{\pi,\, lex} & \stackrel {\mbox {\scrip... ...uiv P^{\char93 } )\ .\\ \\ & \mbox {Схема 7} & \end{array}$$

В этой схеме символ $\stackrel {\mbox {\scriptsize\mbox {Arg}}} {\stackrel {\supset} {\longrightarrow }}$ означает включение оптимальных множеств.

Теорема 6.1. Пусть в задачах P и P^# все нормы $\{ \mbox{$\parallel$}\cdot \mbox{$\parallel$}_j,\ \ \mbox{$\parallel$}\cdot \mbox{$\parallel$}_i\}$ кусочно-линейны и монотонны. Тогда

1) При любом $r \geq0$, обеспечивающем совместность системы ограничений в задаче P, существует $R=\linebreak R(r)\geq 0$ такое, что имеет место верхнее включение в схеме 7.

2) При любом $R \geq0$, обеспечивающем совместность системы ограничений в задаче P^#, существует $r=\linebreak r(R)\geq 0$ такое, что имеет место нижнее включение в схеме 7.

3) Схема 7 реализуется при некоторых $R \geq0$ и $r \geq0$ тогда и только тогда, когда для задач $P_{\pi}$ и $P_{\pi}^{\char93 }$ существует равновесное характеристическое множество.

П о я с н е н и я к д о к а з а т е л ь с т в у. Ситуация с задачами из схемы 7 отличается от ситуации схемы 5 тем, что в схеме 7 задачи формируются из выпуклых кусочно-линейных функций, в схеме 5 $\ -\$из линейных. Но, в принципе, первый случай сводим ко второму (т.е. ранее рассмотренному). Эту редукцию мы и опишем. Заметим, что произвольная выпуклая кусочно-линейная функция имеет универсальное представление в виде $\max_{j\in J}l_j(x)$ при линейных l_j(x). Зафиксируем необходимые представления:

$$\mbox{$\parallel$}(A_jx -b^j)^+ \mbox{$\parallel$}_j \equiv \... ...iu )^+ \mbox{$\parallel$}_i \equiv \max_{t\in I_i} w^i_t (u)\ .$$

Аналогичное представление имеют и функции $\mbox{$\parallel$}x^i \mbox{$\parallel$}_i^{\ast}$, $\mbox{$\parallel$}u^j \mbox{$\parallel$}_j^{\ast}$. Введя дополнительную систему переменных { t_j }₁^m₀ и $\{ \mu_i \}_1^{n_0}$, фигурирующие выше задачи могут быть эквивалентно переписаны следующим образом:

$$\begin{array}{c} P\sim \max \{ (c,\ x) -\sum_{j=1}^{m_0} R... ... \leq t_j,\ \ \ s\in J_j,\ \ \ j=1,..., m_0 \}\ ; \end{array}$$ (6.2)

$$\begin{array}{c} P^{\char93 } \sim \min \{ (b,\ u) +\sum_{... ...leq \mu_i,\ \ \ t\in I_i,\ \ \ i=1,..., n_0 \}\ ; \end{array}$$ (6.3)

$$\begin{array}{c} P_{\pi} \sim \mbox {$\min_{\pi}$} \{ \{ t... ... \leq t_j,\ \ \ s\in J_j,\ \ \ j=1,..., m_0 \}\ ; \end{array}$$ (6.4)

$$\begin{array}{c} P_{\pi}^{\char93 } \sim \mbox {$\min_{\pi... ...leq \mu_i,\ \ \ t\in I_i,\ \ \ i=1,..., n_0 \}\ ; \end{array}$$ (6.5)

$$Q_{\pi,\, lex} \sim \max \{ (c,\ x)\ \mid\ x\in {\mbox{Arg}}_x\, (6.4) \} ;$$ (6.6)

$$Q_{\pi,\, lex}^{\char93 } \sim \min \{ (b,\ u)\ \mid\ u\in {\mbox{Arg}}_u\, (6.5) \}.$$ (6.7)

Здесь Arg $_x\,(6.4)\ -\$алгебраическая составляющая оптимального множества задачи (6.4) по переменной x, Arg $_u\,(6.5)\ -\$алгебраическая составляющая оптимального множества задачи (6.5) по переменной u, эти множества совпадают с Arg$\,P_{\pi}$ и Arg $\,P_{\pi}^{\char93 }$.

Выписанные эквивалентности имеют ясный смысл, поэтому пояснения мы опускаем. Задачи (6.2)-(6.7) линейные. К ним применима схема доказательства теоремы 5.1. Следует только обратить внимание на необходимость (и возможность) при выборе параметров R и r обеспечить непустоту множеств M(r) и M^#(R). Это достигается тем, что при выборе R=R₀R^j₀ и r=r₀r^i₀ по схеме доказательства теоремы 4.1 (а она и лежит в основе обоснования теоремы 5.1) R₀ можно взять как угодно
большим, т.е. если годится $\widetilde {R_0}$, то годится и любое $R_0 > \widetilde {R_0}$. Этим и обеспечивается совместность систем $A_0x\leq b^0$, $x\geq 0$, $\mbox{$\parallel$}x^i \mbox{$\parallel$}_i^{\ast} \leq r_i$, i=1,..., n₀ и $B_0^Tu\geq c^0$, $u\geq 0$, $\mbox{$\parallel$}u^j \mbox{$\parallel$}_j^{\ast} \leq R_j$, j=1,..., m₀, т.е. $M(r) \neq \emptyset$ и $M^{\char93 }(R)\neq \emptyset$.

З а м е ч а н и е. В теоремах 5.1 и 6.1 фигурирует условие существования равновесного характеристического множества. Естественно, представляют интерес достаточные для этого условия или выделение случаев, когда условие существования равновесного характеристического множества вообще можно снять. Приведем пример такого рода. Частной реализацией задач P и P^# для случая, когда $L\ -\$несобственная задача 1-го рода, является [5]

$$\bar{P}:\ \max\, \{ (c,\ x) -(R,\ (Ax-b)^+ )\ \mid x\geq 0 \}\ ,$$

$$\hspace*{-0.2cm}\bar{P}^{\char93 }:\ \min\, \{ (b,\ u)\ \mid A^Tu\geq c,\ \ 0\leq u\leq R \}.$$

Сопутствующей задаче $\bar{P}$ является следующая задача

$$\bar{P}_{\pi,\, lex}:\ \max \{ (c,\ x)\ \mid\ x\in \mbox{Arg}\, \mbox {$\min_{\pi}$} \{ (Ax-b)^+\ \mid \ x\geq 0 \} \}.$$

В этой ситуации реализуется схема

$$\begin{array}{rll} \bar{P}_{\pi,\, lex} & \stackrel {\mbox {... ...3 )\, ,\vspace{4pt}\\ & & \bar{P}^{\char93 }\\ \end{array}$$

т.е. всегда существует $R \geq0$ такое, что выполняется верхнее включение приведенной схемы, при этом opt$\bar{P}=$opt$\bar{P}^{\char93 }$.

Аналогичная ситуация возникает и для случая, когда $L\ -\$несобственная задача 2-го рода [5].

7. Конструкция $\pi '$-оптимизации

Принципиальная трудность анализа общей постановки задачи (1.3), тем более (1.4) и (1.4)^W, состоит в сложном и плохо описываемом строении последовательности тех множеств, на которых определяется операция $\max_{\pi}$ в задачах (1.3)_k-(1.3)₁. Эти множества в общем случае не являются ни выпуклыми, ни замкнутыми, хотя и со свойством полиэдральности. Напрашивается мысль о некотором сужении $\pi '$-оптимизации, позволяющей идентифицировать отмеченную последовательность допустимых множеств и вносить определенный конструктивизм в их описание.

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

Формализуем эту конструкцию.

Пусть $M=\bigcup\limits_{(j)}M_j\ -\$полиэдральное множество, являющееся объединением конечного числа многогранников M_j, j=1,..., m.

Выпишем задачу

$$\max\nolimits_{\pi}\, \{ C^Tx\ \mid\ x\in M \}.$$ (7.1)

Сужение постановки (7.1), состоящей в идентификации отображения

$$M\ \stackrel {\pi} {\longrightarrow }\ \mbox{Arg}_{\pi}\, (7.1),$$

определим отображением

$$M\ \stackrel {\pi '} {\longrightarrow }\ \mbox{Arg}_{\pi '}\, (7.1)$$

в силу следующей конструкции. Запишем задачу

$$\mbox {$\max_{\pi}$} \{ C^Tx\ \mid \ x\in M'\},$$ (7.2)

где $M'=\overline{\mbox{co}\, \{M_j \}_1^m}$. Как уже отмечалось ранее,

$$\mbox{Arg}\mbox{$_{\pi}$}\, (7.2)\ = \bigcup_{t\in T}{\mbox{\it Г}}_t ,$$

где $\{\! \mbox{\it Г}_t \}\ -\$некоторая совокупность граней многогранника M'. Пусть $T'= \{t\in T \mid\$Г$_t\ \!\!':=$ Г $_t\ \bigcap\ M\neq \emptyset \}$. По свойству 5⁰ из п. 2 имеем: $T'\neq \emptyset$. Отображение $\pi '$ определим соответствием

$$M\ \stackrel {\pi '} {\longrightarrow } \ \bigcup_{t\in T'}\mbox{\it Г}_t\ \!\!'\ =:\ \mbox{Arg}_{\pi '}\, (7.1) .$$

По смыслу нашей конструкции выполняется включение

$$\mbox {Arg}_{\pi '}\, (7.1)\ \subset \ \mbox{Arg}_{\pi}\, (7.1).$$

В этом и состоит смысл употребленного термина ``сужение''.

Таким образом, мы приходим к новой постановке задачи паретовской оптимизации, а именно, $\pi '$-оптимизации:

$$\max\nolimits_{\pi '}\, \{ C^Tx\ \mid\ x\in M \}.\eqno(7.1)'$$

З а м е ч а н и е. Если множество M является выпуклым многогранником $M_0 = \{ x\geq0\ \mid \ Ax\leq b \}$, то задачи (7.1) и (7.1)' совпадают.

Действительно, $M = \overline{\mbox{co}\, M_0} = M_0$, Arg$_{\pi '}$(7.1)' = $\bigcup\limits_{(j)}(\!\mbox{\it Г}_j \bigcap\linebreak M_0 ) = \bigcup\limits_{(j)}\!\mbox{\it Г}_j =$Arg $_{\pi}\, (7.1)$ при M=M₀, где $\{\!\mbox{\it Г}_j \}\ -\$грани многогранника M₀, объединение которых составляет паретовское множество задачи (7.1) при M=M₀.

Новое понятие $\pi '$-оптимизации может быть перенесено и на общую постановку (1.3) в записи:

$$\max\nolimits_{\omega '}\, \left \{ \left [ \begin{array}{c... ...x \end{array}\right ] \ \mid\ Ax\leq b,\ \ x\geq0 \right \},$$ (7.3)

где $\omega '= [p,\, \pi ']$. Смысл задачи (7.3) состоит в заключительной из последовательности задач (1.3)_s, s = k, k-1,..., 1, в которых повсюду вместо символа $\pi$ паретовской оптимизации ставится символ $\pi '$. Чтобы не переписывать отмеченную последовательность задач с заменой $\pi$ на $\pi '$, мы присвоим им номера (7.3)'_s, s = k, k-1,..., 1.

Скаляризующая задача будет иметь вид:

$$\max\, \{ \sum_{j=1}^k (C_j^Tx,\ R^j)\ \mid Ax\leq b,\ \ x\geq0 \}.\eqno (7.3)_{scal}$$

Как уже отмечалось, попытка сужения $\omega$-оптимизации связана с желанием сделать допустимые множества последовательности задач (1.3)_s идентифицируемыми посредством определенных понятий. В этом смысле допустимые множества задач (1.3)_s допускают ясную характеристику. Имеет место

Лемма 7.1. Множество Arg $_{\omega '}\,(7.3)$ является объединением некоторой совокупности граней многогранника $M_0 = \{ x\geq0 \mid$ $Ax\leq~b \}$.

Д о к а з а т е л ь с т в о. Доказательство будем вести индукцией по числу компонент C^T_jx в целевом векторе задачи (7.3). При k=1 справедливость доказываемой леммы вытекает из леммы 4.2.

Выпишем задачу

$$\max\nolimits_{\omega '} \left \{ \left [ \begin{array}{c} ... ... ...\\ C_2^Tx \end{array}\right ]\ \mid\ x\in M_0 \right \}.$$ (7.4)

Пусть, по индуктивному предположению, Arg $_{\omega '}\,(7.4) = \bigcup\limits_{s\in S}$Г_s, где $\{\!\mbox{\it Г}_s \}_{s\in S}\ -\$некоторая совокупность граней многогранника M₀. Имеем: Arg $_{\omega '}\,(7.3)=$Arg $\max_{\pi '}\{ C^T_1x\ \mid x\in \bigcup\limits_{s\in S}$Г $_s \} = \bigcup\limits_{(s,\,t)}(\!$Г $_t^{\ '}\,\bigcap$Г_s), где $\{\! \mbox{\it Г}_t^{\ '}\}\ -\$некоторые грани многогранника $\overline{\mbox{co}\,\{\!\mbox{\it Г}_s \}}$, а объединение $\bigcup\limits_{(s,\, t)}$ берется по Г_ts:= Г $_t^{\ '}\,\bigcap$Г $_s \neq \emptyset$. Так как Г $_t^{\ '}\,\bigcap$Г$_s\ -\$подгрань грани Г_s, а Г$_s\ -\$грань многогранника M₀, то Г$_{ts}\ -\$грань последнего. Лемма доказана.

Теорема 7.1. Пусть задача (7.3) разрешима. Тогда существует непустое множество значений векторных параметров R^j>0, при которых

$$\mbox{Arg}\, (7.3)_{scal}\ \subset \ \mbox{Arg}_{\omega '}\,(7.3).$$ (7.5)

Д о к а з а т е л ь с т в о будем вести индукцией по числу компонент C^T_jx в целевом векторе задачи (7.3). Поскольку задача (7.1)' совпадает, как было отмечено, с (7.1), то при k=1 включение (7.5) справедливо при любом R>0, при этом его левая часть является одной из граней многогранника M₀. Пусть утверждение справедливо для задачи

$$\max\nolimits_{\omega '} \left \{ \left [ \begin{array}{c} ... ......\\ C_2^Tx \end{array}\right ]\ \mid \ x\in M_0 \right \},$$ (7.6)

т.е. существуют $\bar{R}^2>0,...,\bar{R}^k>0$ такие, что

$$\mbox{Arg}\, \max\, \{ \sum_{j=2}^k (C^T_jx,\ \bar{R}^j )\ \mid x\in M_0 \}\ \subset \ \mbox{Arg}_{\omega '}\, (7.6).$$ (7.7)

Опираясь на это индуктивное предположение, необходимо доказать включение (7.5).

Множество M:=Arg$_{\omega '}$(7.6) состоит (по лемме 7.1) из граней многогранника M₀, и максимизируемый функционал f(x) из (7.7) определяет одну из них, пусть Г = Arg(7.7). Так как

$$\mbox{Arg}_{\omega '}\, (7.3)= \mbox{Arg}\, \max\nolimits_{\pi '} \{ C_1^Tx\ \mid\ x\in \mbox{Arg}_{\omega '}\, (7.6)\},$$

то при некотором R¹:

$$\mbox{Arg}\, \max\, \{(C^T_1x,\ R^1)\ \mid \ x\in M \}= \mbox{\it Г}^{\ '},$$

причем можно считать Г$\bigcap$Г $^{ '}\neq \emptyset$, т.е. функционал f(x) определяет на M₀ грань Г, а функционал $(C^T_1x,\ R^1)$ определяет на M, следовательно, и на Г$^{\ '}\ -\$грань Г$\bigcap$Г $^{\ '}\,\subset$
Arg$_{\omega '}$(7.3). По лемме (4.1) при некотором R₀>0 функционал $(C^T_1x,\ R^1) + R_0f(x)$ определяет грань Г$\bigcap$Г$^{\ '}$, т.е. включение (7.5) имеет место при параметрах R¹, $R^j = R_0\bar{R}^j$, j=2,..., k.

З а м е ч а н и е. Из доказательства теоремы видно, что на самом деле ее можно формулировать в следующем виде:

Существует конечный набор скаляризующих задачу (7.3) векторных параметров $R^t=[\bar{R}^1_t,..., \bar{R}^k_t ]>0$, таких, что объединение граней многогранника M₀, определяемых функционалами $f_t(x):= \sum_{j=1}^k (C^T_jx,\ \bar{R}^j_t )$, совпадает с Arg$_{\omega '}\,$(7.3).

При обосновании теоремы в такой формулировке необходимо было бы сделать аналогичное индуктивное предположение относительно задачи (7.6), а в последующем вместо граней Г и Г$^{\ '}$ рассмотреть всю совокупность граней Г_s и Г$_t^{\ '}$ с непустым пересечением Г$_s\, \bigcap$Г$_t^{\ '}$, и для каждой такой ситуации определить параметр R^st, функцию f_st(x) и определяемую ею грань. Объединение последних дает Arg$_{\omega '}$(7.3).

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

1. Черников С.Н. Линейные неравенства. -M.: Наука, 1968. -488 c.
   
2. Еремин И.И., Астафьев Н.Н. Введение в теорию линейного и выпуклого программирования. -M.: Наука, 1978. -192 c.
   
3. Еремин И.И. О задачах последовательного программирования // Сибирск. матем. журн. -1973. -Т. 14,  1. -C. 53-63.
   
4. Еремин И.И. Двойственность для несобственных задач линейного и выпуклого программирования // ДАН СССР, -1981. -T. 256,  2. -C. 272-276.
   
5. Еремин И.И., Мазуров Вл.Д., Астафьев Н.Н. Несобственные задачи линейного и выпуклого программирования. -М.: Наука, 1983. -336 с.

90С25
Eremin, I.I. The duality for Pareto-successive linear optimization problems. (Russian)
Trudy Inst. Mat. i Mekh. (Ekaterinburg) 3 (1994), 245-260.

The linear optimization problem is regarded which is the synthesis of the Pareto optimization and lexicographical optimization formulations.

The main article point is the theory of duality and corresponding mathematical theorems.