IV. Двойственность для несобственных задач паретовской и лексикографической линейной оптимизации ⁴

   Продолжены исследования по симметричной двойственности для линейных задач последовательной и парето-последовательной оптимизации. В отличие от работ [1,2] здесь возможность неразрешимости исходных задач предполагается изначально. Намечены пути оптимальной аппроксимации несобственных задач отмеченных типов.

В работах [1,3] автор рассматривал вопросы двойственности для задач лексикографического (последовательного) и парето-последовательного программирования. Цель состояла в конструировании двойственности симметричной архитектуры, при этом исходная задача вместе с двойственной предполагались разрешимыми или, более общо, обладающими свойством собственности [1]. В работе [3] двойственность для несобственных задач линейной оптимизации рассматривалась через призму ее лексикографической интерпретации.

В данной работе рассматривается двойственность для задач паретовской и лексикографической оптимизации (Pareto-opt и lex-opt) без предположения их разрешимости, т.е. возможность неразрешимости (несобственности) исходной постановки предполагается изначально. Анализ ведется с позиций теории двойственности для несобственных задач математического программирования [2].

Выпишем три задачи:

$$\max\nolimits_{\pi} \{ C^Tx \mbox{$\,\mid\,$}Ax\leq b,\ \ x\geq 0 \},$$ (1)

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

$$\max\,\{(C^Tx,\ R) \mbox{$\,\mid\,$}Ax\leq b,\ \ x\geq 0 \}.$$ (3)

В (1) и (2) символы $\max_{\pi}$ и $\max_p$ означают соответственно паретовский и лексикографический максимум для системы функций {c_i^Tx}_i=1^k; $C^Tx =[c_1^Tx,\,...\,,c_k^Tx]^T$, $C = [c_1,\,...\,,c_k]$ (т.е. c_i -- вектор-столбец); R -- положительный k-мерный вектор-параметр. Символ p в (2) будет в дальнейшем нести смысл упорядочения функций {c_i^Tx}_i=1^k, т.е. упорядочения номеров этих функций, например, $p=(k,\,...\,,1)$. Задачи (1) и (2) сближают два обстоятельства: во-первых, имеет место включение Arg(2) $\subset$ Arg(1) -- в случае их разрешимости; во-вторых, та и другая в определенном смысле редуцируются к скаляризующей их задаче (3). В случае неразрешимости одной из них связи между задачами (1)-(3) становятся более сложными.

Ниже рассматриваются вопросы симметричной двойственности (преимущественно) для задач (1) и (2) в случае их неразрешимости.

1. Двойственность для несобственных задач Pareto-opt

Для целей симметризации двойственности задачу (1) поставим в параметризованном виде

$$L_{\pi}:\ \max\nolimits_{\pi} \{ C^Tx \mbox{$\,\mid\,$}Ax\leq Br,\ \ x\geq 0 \};$$ (4)

здесь $B = [b_1,\,...\,,b_l]$, так что $Br=\mbox{$\sum\limits_{t=1}^{l}$}r_tb_t$, r -- положительный l-мерный вектор-параметр. Наравне с $L_{\pi}$ запишем задачу

$$L^{\ast}_{\pi}:\ \min\nolimits_{\pi} \{ B^Tu \mbox{$\,\mid\,$}A^Tu\geq CR,\ \ u\geq 0 \},$$ (5)

а также задачи

$$L_{\pi, scal}:\ \max\,\{ (C^Tx,\ R) \mbox{$\,\mid\,$}x\,\in\, M_r \},$$ (6)

$$L^{\ast}_{\pi, scal}:\ \min\, \{ (B^Tu,\ r) \mbox{$\,\mid\,$}u\,\in\, M_R^{\ast}\},$$ (7)

где $M_r =\{ x\, \vert\, Ax\leq Br,\ x\geq 0\}$, $M_R^{\ast} =\{ u\, \vert\, A^Tu\geq CR$, $u\geq0\}$.

Задачи (4) и (5) можно рассматривать как взаимно двойственные в смысле паретовской оптимизации. Задачи же (6) и (7) являются взаимно двойственными в классическом смысле.

1.1. Классификация НЗ Pareto-opt

Введенные множества M_r и $M_R^{\ast}$ являются многогранниками в пространствах E_n и E_m соответственно; системы неравенств, их задающие, получаются путем исключения всех переменных r_t и R_j из систем $Ax\leq Br,\ \ x\geq 0$ и $A^Tu\geq CR,\ \ u\geq 0$ методом Фурье-Черникова [4]. Введем также множества

$$N = \{ r>0 \mbox{$\,\mid\,$}M_r\neq \emptyset \},$$

$$N^{\ast} = \{ R>0 \mbox{$\,\mid\,$}M_R^{\ast} \neq \emptyset \};$$

они определяются системами линейных неравенств как результата исключения из выписанных систем переменных x_i и u_j соответственно по методу Фурье-Черникова.

Классификацию неразрешимых задач (4) можно провести по альтернативным свойствам либо пары $\{M_r,\ M_R^{\ast}\}$ -- при фиксированных r>0 и R>0, либо пары $\{N,\ N^{\ast}\}$. В первом случае классификация такова:

$$\begin{array}{lll} M_r =\emptyset , & M_R^{\ast} \neq \empty... ... \emptyset & {\mbox{\rm ---\ \ НЗ\ \ 3-го\ рода}}. \end{array}$$

Эта классификация соответствует классификации несобственных задач ЛП, в данном случае задач (6), (7). По отношению к задаче (4) назовем приведенную классификацию локальной. Заметим, что случай $M_r~\neq~\emptyset$, $M_R^{\ast} \neq \emptyset$ соответствует разрешимости всех задач (4)-(7).

Классификацию задач (4) по свойствам пары $\{N,\ N^{\ast}\}$ назовем тотальной; выпишем эти альтернативные свойства:

$$\begin{array}{lll} N \neq \emptyset , & N^{\ast} \neq \empty... ...{\mbox{\rm ---\ \ свойство}}\ \ \mbox{$\alpha$}_3. \end{array}$$

Двойная классификация задач (4) может быть объяснена следующим образом. Всякую параметрическую математическую модель можно рассматривать с двух позиций: 1) найти значение параметра, обеспечивающее модели необходимое свойство; 2) найти условие на модель, обеспечивающее модели необходимое свойство для всех значений параметра (из заданной области). В параметрическом программировании такой подход типичен. Две классификации, приведенные выше, отвечают такому подходу.

Задачи (4)-(7) свяжем естественной схемой

$$\begin{array}{rcl} L_{\pi} & \stackrel {(1)}{\longrightarrow... ...pi,\,scal}^{\ast}\ .\\ [12pt] & \mbox {Схема 1} & \end{array}$$

Здесь (1) -- переход по скаляризации, (2) -- классический переход к двойственной задаче, (3) -- восстанавливающий переход, т.е. переход к задаче типа $L_{\pi}$, обратный к которому по правилу (1) дает задачу $L_{\pi, scal}^{\ast}$. Тогда задачи $L_{\pi}$ и $L_{\pi}^{\ast}$ рассматриваются как $\pi$-двойственные (двойственными по Парето) -- по определению.

Требуют определенной расшифровки (интерпретации) условия $\mbox{$\alpha$}_i$, i=0-3. Свойство $\mbox{$\alpha$}_0$ означает, что $r\,\in\,N \Longleftrightarrow M_r \neq \emptyset$, $R\,\in\,N^{\ast} \Longleftrightarrow M_R^{\ast} \neq \emptyset$. Этот случай, как уже было отмечено, соответствует разрешимости задач (4)-(7). Условие $N=\emptyset$ означает, что при любом r>0 система

$$Ax\leq Br,\qquad x\geq 0$$ (8)

несовместна, что эквивалентно несовместности системы

$$Ax\leq Br,\qquad x\geq 0,\qquad r>0$$ (9)

по переменной $z=[x,\ r]$. Из общей теоремы об условиях совместности смешанной системы линейных неравенств [4] вытекает:

Система $(\ref{f9})$ несовместна тогда и только тогда, когда совместна система

$$A^Tu=0,\qquad B^Tu\leq 0,\qquad B^Tu\neq 0,\qquad u\geq 0.$$ (10)

Эту систему можно переписать в виде

$$A^Tu=0,\ \ B^Tu+v = 0,\ \ u\geq 0,\ \ \mbox{$\sum\limits_{(i)}^{}$} v_i>0,$$ (11)

где $v=[v_1,\,...\,,v_l]^T$. Таким образом, ситуацию пустоты (или непустоты) каждого из множеств $N,\ \ N^{\ast}$ можно охарактеризовать через термины условий совместности (или несовместности) смешанных систем линейных неравенств.

Выделим утверждение, отвечающее разрешимости задач (4) и (5).

Теорема 1. Задачи $(\ref{f4})$ и $(\ref{f5})$ при $r>0,\ \ R>0$ одновременно разрешимы или неразрешимы; необходимым и достаточным условием их разрешимости являются включения $r\,\in\,N,\ \ R\,\in\, N^{\ast}$, при этом реализуется схема связей между ними и задачами  $(\ref{f6}),\ (\ref{f7})$:

$$\begin{array}{rcl} L_{\pi} & \stackrel {\mbox {\scriptsize\... ...\ast}_{\pi, scal}\ .\\ [12pt] & \mbox {Схема 2} & \end{array}$$

Здесь символ $\stackrel {\mbox {\scriptsize\mbox {Arg}}} {\stackrel {\supset} {\longrightarrow }}$ означает переход к новой (в данном случае -- скаляризованной) задаче с включением $\supset$ их оптимальных множеств.

1.2. Двойственность для задачи Pareto-opt

Неразрешимость задачи (4), следовательно, и (5), состоит в несовместности хотя бы одной из систем их ограничений при r>0, R>0. Преодоление неразрешимости произвольной задачи осуществляется путем ее аппроксимации (в том или ином смысле). Неразрешимость систем ограничений в задаче оптимизации преодолевается в соответствии с методом штрафных функций. Этот прием, примененный одновременно к формально двойственной задаче, дает возможность аппроксимации и исходной задачи в целом (т.е. не только ее системы ограничений). Проблему аппроксимации и симметричной двойственности в этом случае можно поставить в соответствии со схемой анализа несобственных задач ЛП [2]. Рассмотрим вначале частный случай, а именно. Задачам (4) и (5) поставим в соответствие задачи по правилу (#) [2]:

$$\max \{ (C^Tx, R) -R_0 \mbox{$\parallel$}( Ax -Br)^+ \mbox{... ...\ \mbox{$\parallel$}x \mbox{$\parallel$}_{\beta} \leq r_0 \},$$ (12)

$$\min \{ (B^Tu, r) +r_0 \mbox{$\parallel$}( CR -A^Tu)^+ \mbo... ...$\parallel$}u \mbox{$\parallel$}_{\alpha}^{\ast} \leq R_0 \}.$$ (13)

Здесь r₀>0, R₀>0, $\mbox{$\parallel$}\,\cdot\,\mbox{$\parallel$}_{\alpha}$ и $\mbox{$\parallel$}\,\cdot\,\mbox{$\parallel$}_{\beta}$ -- монотонные нормы в пространствах соответствующей размерности, $\mbox{$\parallel$}\,\cdot\,\mbox{$\parallel$}_{\alpha}^{\ast}$ и $\mbox{$\parallel$}\,\cdot\,\mbox{$\parallel$}_{\beta}^{\ast}$ -- им сопряженные нормы.

Теорема 2. Задачи $(\ref{f12})$ и $(\ref{f13})$ тотально (т.е. при любых реализациях всех их параметров) разрешимы, при этом opt(12)=opt(13) и реализуется схема связей:

$$\begin{array}{rcccc} (4) & \stackrel {\scriptstyle {(\char93... ... & (13)_{\pi}\ ,\\ [12pt] & & \mbox {Схема 3} & & \end{array}$$

в которой

$$(12)_{\pi}:\ \max{\mbox{$_{\pi}$}} \left\{ \left. \left[ \be... ...box{$\parallel$}x \mbox{$\parallel$}_{\beta} \leq r_0 \right\},$$

$$(13)_{\pi}:\ \min{\mbox{$_{\pi}$}} \left\{ \left. \left[ \be... ...rallel$}u \mbox{$\parallel$}_{\alpha}^{\ast} \leq R_0 \right\}.$$

Справедливость сформулированного утверждения следует из общей теоремы двойственности для НЗ ЛП ([2], теорема 6.2) и хорошо известной связи между паретовской задачей и ее скаляризующей.

1.3. Двойственность, общий случай

Рассмотрим вариант двойственности, связанный с отображением (4) $\stackrel {(\char93 )}{\longrightarrow }$ из схемы 3 более общего вида. С этой целью системы ограничений в задачах (4) и (5) произвольным образом разобьем на подсистемы

$$A_jx\leq B_jr,\qquad j=0, 1,\,...\,,m_0$$ (14)

и

$$H_i^Tu\geq C_iR,\qquad i=0, 1,\,...\,,n_0$$ (15)

соответственно. Здесь {A_j}₀^m₀ -- горизонтальные подматрицы матрицы A, {H_i}₀^n₀ -- ее вертикальные подматрицы; {B_j}₀^m₀ и {C_i}₀^n₀ -- горизонтальные подматрицы матриц B и C, соответствующие разрезу матрицы A на горизонтальные и вертикальные полосы. В отношении разбиений (14) и (15) будет лишь одно предположение:

$$\begin{array}{ll} N_0 = \{ r>0 \mbox{$\,\mid\,$}A_0x\leq B_0... ...\geq 0 {\mbox{---\ совместна}} \}\neq \emptyset . \end{array}$$

Задачам (4) и (5) поставим в соответствие задачи

$$P:\ \sup\, \{ (C^Tx,\ R) -\sum_{j=1}^{m_0} \bar{R}_j \mbox{$\parallel$}( A_jx -B_jr)^+ \mbox{$\parallel$}_j \mbox{$\,\mid\,$}$$

$$A_0x\leq B_0r,\ \ x\geq 0,\ \ \mbox{$\parallel$}x^i \mbox{$\parallel$}_i \leq \bar{r}_i,\ \ i=1,\,...\,,n_0 \},$$ (16)

$$P^{\char93 }:\ \inf\, \{ (B^Tu,\ r) +\sum_{i=1}^{n_0} \bar{r}... ...( C_iR -H_i^Tu)^+ \mbox{$\parallel$}_i^{\ast} \mbox{$\,\mid\,$}$$

$$H_0^Tu\geq C_0R,\ \ u\geq 0,\ \ \mbox{$\parallel$}u^j \mbox{$\parallel$}_j^{\ast} \leq \bar{R}_j,\ \ j=1,\,...\,,m_0 \}.$$ (17)

Здесь $\bar{R}^T =[\bar{R}_1,\,...\,,\bar{R}_{m_0}]>0,\ \ \bar{r}^T =[\bar{r}_1,\,...\,,\bar{r}_{n_0}]>0$ -- параметры, не связанные непосредственно с R и r; {xⁱ}₀^n₀ и {u^j}₀^m₀ -- подвекторы векторов x и u, соответствующие разрезу матрицы A на подматрицы H_i и A_j. Из условия непустоты множеств N₀ и $N_0^{\ast}$ следует, что за счет выбора $r\in N_0$, $R\in N_0^{\ast}$ и $\bar{r}$, $\bar{R}$ системы ограничений в задачах P и P^# можно сделать совместными. Тогда аналогом теоремы 2 может служить

Теорема 3. Если параметры r, R и $\bar{r}$, $\bar{R}$ выбраны вышеуказанным образом, причем для P выполнено условие регулярности (например, условие Слейтера), то в задачах P и P^# $\sup$ и $\inf$ конечны, при этом optP=optP^# и реализуется схема связей:

$$\begin{array}{rcccc} L_{\pi} & \stackrel {\scriptstyle {(\ch... ...i}^{\char93 }\ ,\\ [12pt] & & \mbox {Схема 4} & & \end{array}$$

в которой

$$P_{\pi}:\ \max{\mbox{$_{\pi}$}} \left\{ \left. \left[ \begin... ...lel$}_j \}_1^{m_0} \end{array} \right ]\ \ \right \vert \right.$$

$$A_0x\leq B_0r,\ \ x\geq 0,\ \ \mbox{$\parallel$}x^i \mbox{$\parallel$}_i \leq \bar{r}_i,\ \ i=1,\,...\,,n_0 \biggr \},$$

$$P_{\pi}^{\char93 }:\ \min{\mbox{$_{\pi}$}} \left\{ \left. \le... ..._i^{\ast} \}_1^{n_0}\end{array} \right]\ \ \right \vert \right.$$

$$H_0^Tu\geq C_0R,\ \ u\geq 0,\ \ \mbox{$\parallel$}u^j \mbox{$\parallel$}_j^{\ast} \leq \bar{R}_j,\ \ j=1,\,...\,,m_0 \biggr\}.$$

З а м е ч а н и е. Если в теореме 3 предполагать достижимость операции $\inf$ в задаче P, что имеет место, например, когда нормы $\mbox{$\parallel$}\,\cdot\,\mbox{$\parallel$}_j$ кусочно-линейны, то задача P^# будет автоматически разрешимой, т.е. $\sup$ в P^# будет достигаться.

1.4. Аппроксимация несобственной задачи Pareto-opt

Разрешимость задачи (4) связана, как было сказано, с совместностью ограничений в задачах (4) и (5). Если эти условия нарушаются, то коррекцию (или оптимальную коррекцию) можно осуществить либо за счет коррекции параметров r и R, либо за счет коррекции матриц B и C. Рассмотрим конструкцию оптимальной коррекции (аппроксимации) матриц B и C для обеспечения совместности систем ограничений в задачах (4), (5), т.е. разрешимости этих задач. Пусть $\bigtriangleup \,B$ и $\bigtriangleup \,C$ -- приращения для матриц B и C, рассматриваемых как векторы пространств R^{n x l} и R^{m x k} соответственно, т.е. $\bigtriangleup \,B\in\,$R^{n x l}, $\bigtriangleup \,C\in\,$R^{m x k}. Если ввести функцию ``качества'' этих приращений $\varphi \, (\bigtriangleup \,B,\ \bigtriangleup \,C)$, то можно поставить задачу коррекции в форме: найти

$$\min\,\varphi \,(\bigtriangleup \,B,\ \bigtriangleup \,C)$$

при ограничениях

$$\leq (B+\bigtriangleup \,B)\,r,\ \ \ x\geq 0,$$ Ax (18)

$$\geq (C+\bigtriangleup \,C)\,R,\ \ u\geq 0.$$ A^Tu (19)

Для приращений $\bigtriangleup \,B$ и $\bigtriangleup \,C$ можно ввести допустимые области, чего мы делать не будем во избежание громоздкости. Функция $\varphi$ может быть нормой $\mbox{$\parallel$}\, [ \bigtriangleup \,B,\ \bigtriangleup \,C ]\,\mbox{$\parallel$}$. Если $\varphi \, (\bigtriangleup \,B,\ \bigtriangleup \,C) = \varphi _1(\bigtriangleup \,B) + \varphi _2 (\bigtriangleup \,C)$, то сформулированная задача коррекции распадется на две независимые задачи:

$$\min \{ \varphi _1(\bigtriangleup \,B) \mbox{$\,\mid\,$}Ax \leq (B+\bigtriangleup \,B)\,r,\ \ x\geq 0 \},$$ (20)

$$\min \{ \varphi _2(\bigtriangleup \,C) \mbox{$\,\mid\,$}A^Tu \geq (C+\bigtriangleup \,C)\,R, u\geq 0 \}.$$ (21)

Если $\varphi _1$ и $\varphi _2$ -- линейные функции, т.е. $\varphi _1 (\bigtriangleup \,B) = (\overline{\bigtriangleup \,B},\ \bigtriangleup \,B)$, $\varphi _2 (\bigtriangleup \,C) = (\overline{\bigtriangleup \,C},\ \bigtriangleup \,C)$, где $\overline{\bigtriangleup \,B}$ и $\overline{\bigtriangleup \,C}$ -- фиксированные векторы из пространств приращений $\bigtriangleup \,B$ и $\bigtriangleup \,C$, то задачи (20) и (21) -- задачи ЛП. Найдя из них оптимальные $\widetilde {\bigtriangleup \,B}$ и $\widetilde {\bigtriangleup \,C}$ и подставив в (18), (19), получим совместные относительно x и u системы неравенств, что обеспечивает разрешимость задач (4) и (5) при замене B и C на $\widetilde {B}= B+\widetilde {\bigtriangleup \,B}$ и $\widetilde {C}= C+\widetilde {\bigtriangleup \,C}$. В случае $\varphi _1 (\bigtriangleup \,B) = \mbox{$\parallel$} \bigtriangleup \,B\mbox{$\parallel$}^2$, $\varphi _2 (\bigtriangleup \,C) = \mbox{$\parallel$}\bigtriangleup \,C\mbox{$\parallel$}^2$ задачи (20) и (21) суть задачи квадратичного программирования, для которых (как и для задач ЛП) существуют эффективные методы их решения.

2. Двойственность для несобственных задач lex-opt

Рассмотрим задачу (2) в ее более общем параметрическом варианте:

$$\mbox{$L_{lex}:\ \max_p$} \left \{ \left. \left [ \begin{ar... ...right ] \ \right \vert \ Ax\leq b_0 +Br,\ \ x\geq0 \right \}.$$ (22)

Примем $p=(k,\,...\,,1, 0)$. Пусть $M(r) =\{ x\geq 0 \mbox{$\,\mid\,$}Ax\leq b_0 +Br\}$. Смысл задачи L_lex определим заключительной из последовательности задач:

$$\hspace*{-2.1cm}\max\,\{c_k^Tx \mbox{$\,\mid\,$}x \,\in\,M(r) \}\ \ \ (=: \mbox{$\alpha$}_k),\eqno (23)_k\ \ \$$

$$\hspace*{0.6cm}\max\,\{c_{k-1}^Tx \mbox{$\,\mid\,$}x \,\in\,{... ...}\,(23)_k \}\ \ \ (=:\ \mbox{$\alpha$}_{k-1}), \eqno (23)_{k-1}$$

$$\hspace*{0.7cm}{\makebox[9.25cm]{\,\dotfill\,}}$$

$$\max\,\{c_1^Tx \mbox{$\,\mid\,$}x \,\in\,{\mbox{\rm Arg}}\,(23)_2 \}\ \ \ (=: \mbox{$\alpha$}_1), \eqno (23)_1\ \ \$$

$$\framebox{\mbox{$\max\,\{c_0^Tx \mbox{$\,\mid\,$}x \,\in\, {\... ...}\,(23)_1 \}\ \ \ (=:\ \mbox{$\alpha$}_0)$}.}\eqno (23)_0\ \ \$$

Двойственную к L_lex запишем в форме

$$L_{lex}^{\ast}: \min\nolimits_q \left \{ \left. \left [ \be... ...right ] \ \right \vert \ A^Tu\geq c_0 +CR,\ u\geq0 \right \},$$ (24)

где q -- некоторое упорядочение номеров функций {b_j^Tu}₀^l. Примем для определенности $q =(l,\,...\,,1, 0)$. Смысл задачи (24) расшифровывается по аналогии с (22). Двойственность для задач (22), (24) в предположении их разрешимости автор рассматривал ранее [1]. Ниже будет рассматриваться ситуация неразрешимости (по крайней мере одной из $L_{lex},\ \ L_{lex}^{\ast }$).

Заметим, что задачи (22) и (24) в своей исходной постановке независимы по выбору параметров $r,\ R$ и упорядочений $p,\ q$. С L_lex и $L_{lex}^{\ast}$ свяжем перекрестно скаляризующие их задачи:

$$L_{scal}:\ \max\,\{ c_0^Tx +(C^Tx,\ R) \mbox{$\,\mid\,$}x \,\in\,M(r) \},$$ (25)

$$L^{\ast}_{scal}:\ \min\, \{ b_0^Tu +(B^Tu,\ r) \mbox{$\,\mid\,$}u \,\in\, M^{\ast}(R)\},$$ (26)

здесь $M^{\ast}(R) =\{ u \mbox{$\,\mid\,$}A^Tu\geq c_0 +CR, u\geq 0\}$.

2.1. Случай разрешимости задач $L_{lex},\ \ L_{lex}^{\ast }$, условия разрешимости

Из условий разрешимости задачи ЛП следуют условия разрешимости задач L_lex и $L_{lex}^{\ast}$ в следующих формах.

Пусть J ={ a_j, -e_i }_{1, 1}^{m, n}, {a_j}₁^m -- строчки матрицы A, {e_i}₁ⁿ -- единичные орты пространства Rⁿ; $I =\{ h_i, e_j^{\ast}\}_{1, 1}^{n, m}$, $\{e_j^{\ast}\}_1^m$ -- единичные орты пространства R^m. Выпишем две группы соотношений:

$$\left. \begin{array}{ll} c_k & \!\!\!\!\!\!\,\in\,\mbox{\r... ...\rm cone}\,\{ J,\ -c_k,\,...\,,-c_1 \}; \end{array}\right \}$$ (27)

$$\left. \begin{array}{ll} b_l & \!\!\!\!\!\!\,\in\,\mbox{\r... ...\rm cone}\,\{ I,\ -b_l,\,...\,,-b_1 \}. \end{array}\right \}$$ (28)

При $M(r) \neq \emptyset$ разрешимость задачи L_lex равносильна выполнимости условий (27); при $M^{\ast}(R)\neq \emptyset$ разрешимость задачи $L_{lex}^{\ast}$ равносильна выполнимости условий (28). Соотношения (27) и (28) записаны в предположении $p=(k,\,...\,,1, 0)$ и $q =(l,\,...\,,1, 0)$. Если в качестве ограничения принять разрешимость систем неравенств в задачах L_lex и $L_{lex}^{\ast}$ при любых $r \geq0$ и $R \geq0$ (а это эквивалентно разрешимости систем $Ax\leq b_i, x\geq 0$ и $A^Tu\geq c_j$, $u\geq 0$ для всех $i=0,\,...\,,l$ и $j=0,\,...\,,k$), то справедливо утверждение [1, теорема 3.1]: при выполнимости соотношений $(\ref{f27})$ и $(\ref{f28})$ существует непустая область значений параметров r> 0 и R> 0 таких, что

$${\mbox{\rm Arg}}\, L_{lex} =\,{\mbox{\rm Arg}}\, L_{scal},\qq... ...m Arg}}\, L_{lex}^{\ast} =\,{\mbox{\rm Arg}}\, L_{scal}^{\ast}.$$

Так как (25) и (26) находятся в классической двойственности, то opt(25) =opt(26).

В связи с этой теоремой представляет интерес то обстоятельство, что значения параметров r и R, обеспечивающих справедливость сформулированной теоремы, обеспечивают ее справедливость и в ситуации ``урезанных'' совокупностей функций {c<sub>j</sub><sup>T</sup>x} и {b<sub>i</sub><sup>T</sup>u}, а именно. Рассмотрим ``урезанные'' задачи

$$L_{lex}^{t,\ s}:\ \max\nolimits_p \left \{ \left. \left [ \... ...\vert \ Ax \leq \sum_{i=s}^l r_i b_i\ ,\ \ x\geq0 \right \},$$ (29)

$$(L_{lex}^{t,\ s})^{\ast}:\ \min\nolimits_q \left \{ \left. ... ...ert \ A^Tu \geq \sum_{j=t}^k R_j c_j\ ,\ \ u\geq0 \right \};$$ (30)

$t=0,\,...\,,k;\ \ s=0,\,...\,,l$. Для s=0 полагаем r₀=1; аналогично, если t=0, то полагаем R₀=1. Задачи, перекрестно скаляризующие (29) и (30), запишутся в форме:

$$% latex2html id marker 12098L_{scal}^{t,\ s}:\ \max\, \{ ... ...$\,\mid\,$} {\mbox{\rm ограничения\ \ из}}\ \ (\ref{f29}) \},$$ (31)

$$% latex2html id marker 12102(L_{scal}^{t,\ s})^{\ast}:\ \... ...box{\rm ограничения\ \ из}}\ \ (\ref{f30}) \}.\hspace*{0.3cm}$$ (32)

Теорема 4. Пусть системы неравенств $Ax\leq b_i$, $x\geq 0$ и $A^Tu\geq c_j$, $u\geq 0$ совместны для всех $i \,\in\,\mbox{$\overline{0,\ l}$}$, $j \,\in\, \mbox{$\overline{0,\ k}$}$ и выполнены условия $(\ref{f27})$, $(\ref{f28})$. Тогда существует непустая область значений параметров r>0 и R > 0 -- единых для всех $t \,\in\,\mbox{$\overline{0,\ k}$}$ и $s \,\in\,\mbox{$\overline{0,\ l}$}$ и таких, что

$${\mbox{\rm Arg}}\,L_{lex}^{t, s} =\, {\mbox{\rm Arg}}\,\,L_... ...t, s})^{\ast} =\, {\mbox{\rm Arg}}\,(L_{scal}^{t, s})^{\ast}.$$ (33)

Дадим пояснения к обоснованию сформулированной теоремы. Обоснование для случая задач (22), (24) и (25), (26) в соответствии с работой [2, теорема 2.1] состоит в последовательном назначении констант: $\bar{R}_k$ -- для обеспечения эквивалентности (по Arg) задач (23)_k-1 и $\max\, \{ c_{k-1}^Tx +\bar{R}_k c_k^Tx \mbox{$\,\mid\,$}x \,\in\,M(r) \}$, затем $\bar{R}_{k-1}$ -- для обеспечения эквивалентности задач (23)_k-2 и $\max\, \{ c_{k-2}^Tx +\bar{R}_{k-1}( c_{k-1}^Tx + \bar{R}_k c_k^Tx) \mbox{$\,\mid\,$}x \,\in\,M(r) \}$ и т.д., наконец, $\bar{R}_1$ -- для обеспечения эквивалентности задач (23)₀ и $\max\, \{ c_0^Tx +\bar{R}_1(c_1^Tx+ \ldots +\bar{R}_{k-1}( c_{k-1}^Tx + \bar{R}_k c_k^Tx) \ldots ) \mbox{$\,\mid\,$}x \,\in\,M(r) \}$. При этом назначение констант не зависит от r [2, лемма 2.1]. Значения параметров R_j, фигурирующих в формулировке теоремы 4, получаются в силу соотношений $R_j =\prod\limits_{i=j}^k \bar{R}_i$. Так же дело обстоит и с назначениями параметров r_i. Из описанной схемы формирования R_j и r_i видно, что эти же константы обслуживают схему эквивалентной сводимости задач (29), (31) к задачам (30), (32), что и является смыслом теоремы 4.

2.2. Оптимальная коррекция неразрешимых
лексикографических задач

Неразрешимость задачи (22) состоит либо в несовместности системы ее ограничений (при заданном r), либо в невыполнимости одного из включений (27). Так же дело обстоит и с неразрешимостью задачи (24): либо ее система ограничений несовместна (при заданном k), либо не выполняется одно из включений (28). Включения (27) и (28) могут быть эквивалентно записаны в форме последовательностей систем линейных неравенств:

$$\left.\begin{array}{l} c_k\leq A^Tu,\ \ u\geq 0;\\ [4pt] ... ...l \,j\,\in\,\mbox{$\overline{1,\ k}$}; \end{array} \right \}$$ (34)

$$\left.\begin{array}{l} Ax\leq b_l,\ \ x\geq 0;\\ [4pt] Ax... ...l \,i\,\in\,\mbox{$\overline{1,\ l}$}. \end{array} \right \}$$ (35)

Нарушение того или иного включения из (27), (28) выражается в несовместности соответствующей системы линейных неравенств из (34), (35). Коррекция задач L_lex и $L_{lex}^{\ast}$, т.е.  (22) и (24), может быть осуществлена за счет коррекции векторов {c_j}₀^k и {b_i}₀^l по следующей схеме.

Рассмотрим первую систему из (34), т.е. $c_k\leq A^Tu$, $u\geq 0$. Нарушение первого включения из (27) означает несовместность последней. Вектором невязки для нее будет (c_k - A^Tu)⁺, где ``+'' над вектором означает замену его отрицательных координат нулями (положительная срезка). Если в силу некоторой нормы $\mbox{$\parallel$}\,\cdot\,\mbox{$\parallel$}_k$ определить уклонение $\min\limits_{u\geq 0} \mbox{$\parallel$} (c_k - A^Tu)^+ \mbox{$\parallel$}_k~=~E_k$ и $\bar{u} \geq 0:\ \mbox{$\parallel$}(c_k - A^T\bar{u})^+ \mbox{$\parallel$}_k =E_k$, то вектор $\bigtriangleup _k = (c_k - A^T\bar{u})^+$ будет минимальной (по критерию введенной нормы $\mbox{$\parallel$}\,\cdot\,\mbox{$\parallel$}_k$) коррекцией вектора c_k, обеспечивающей совместность системы $c_k -\bigtriangleup _k \leq A^Tu,\ \ u\geq 0$, или (что одно и то же) выполнение включения $\bar{c}_k \,\in\,\,$cone$\,J$ при $\bar{c}_k =c_k -\bigtriangleup _k$. Подставив во вторую систему из (34) $\bar{c}_k$ вместо c_k, аналогично подсчитаем $\bar{c}_{k-1}$ путем введения для вектора-невязки своей нормы $\mbox{$\parallel$}\,\cdot\,\mbox{$\parallel$}_{k-1}$ и т.д.

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

Сделаем еще одно замечание: выполнимость соотношений (27), (28) эквивалентна
тому, что $\bigtriangleup _j =0$, $\bigtriangleup _i^{\ast} =0$, $\forall \,j \,\in\,\mbox{$\overline{0,\ k}$}$, $\forall \,i \,\in\,\mbox{$\overline{0,\ l}$}$ в приведенной схеме оптимальной коррекции.

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

Соотношения (27), (28), как необходимые условия разрешимости задач L_lex и $L_{lex}^{\ast}$ при рассмотрении двойственности, будем считать выполненными. Как показано, выполнимость их решается процедурой последовательной оптимальной коррекции.

Вопрос о преодолении несовместности систем ограничений в (22) и (24) (при всех или некоторых r>0 и R>0) может быть решен в рамках схемы двойственности для несобственных задач оптимизации. Системы $Ax\leq b_0 +Br,\ \ x\geq 0$ и $A^Tu\geq c_0 +CR,\ \ u\geq 0$ разобьем произвольным образом на подсистемы:

$$A_jx\leq b_{0j} +B_jr,\ \ \ x\geq 0,\ \ j=0,\ 1,\,...\,,m_0,$$ (36)

$$H_i^Tu\geq c_{0i} +C_iR, \ \ u\geq 0,\ \ i=0,\ 1,\,...\,,n_0$$ (37)

с требованием совместности подсистем

$$A_0x\leq b_{00} +B_0r,\ \ x\geq 0\ \ \ {\mbox{\rm и}} H_0^Tu\geq c_{00} +C_0R,\ \ u\geq 0$$ (38)

при любых r>0 и R>0. Здесь {A_j}₀^m₀ -- горизонтальные подматрицы матрицы A, {H_i}₀^n₀ -- ее вертикальные подматрицы. Множества их решений обозначим через M₀(r) и $M_0^{\ast}(R)$ соответственно. Условия, обеспечивающие свойства $M_0(r)\neq \emptyset$, $\forall \,r>0$ и $M_0^{\ast}(R)\neq \emptyset$, $\forall \,R>0$, состоят в следующем. Пусть {b_0t}₁^l -- столбцы матрицы B₀, {c_0t}₁^k -- столбцы матрицы C₀. Первое отмеченное свойство эквивалентно совместности систем $A_0x\leq b_{0t}$, $x\geq 0$, $\forall \,t \,\in\, \mbox{$\overline{0,\ l}$}$; второе -- совместности систем $H_0^Tu\geq c_{0t}$, $u\geq 0$, $\forall \,t \,\in\,\mbox{$\overline{0,\ k}$}$.

По исходным задачам (22) и (24), а также разбиениям (36) и (37), сконструируем следующие задачи лексикографической оптимизации:

$$\hspace*{-3mm} \max\nolimits_p \left\{ \left.\hspace{-4pt} \... ...\mbox{$\parallel$}_i \leq \bar{r}_i,\, i=1,...,n_0 \right \},$$ (39)

$$\hspace*{-3.3mm} \min\nolimits_q \left\{ \left.\hspace{-4pt... ...\parallel$}_j^{\ast} \leq \bar{R}_j,\, j=1,...,m_0 \right \};$$ (40)

здесь

$$F(x) =[f_1(x),\,...\,,f_{m_0}(x)],\ \ f_j(x) =\mbox{$\parallel$}(A_jx -b_{0j} -B_jr)^+ \mbox{$\parallel$}_j;$$

$$F^{\ast}(u) =[f_1^{\ast}(u),\,...\,,f_{n_0}^{\ast}(u)], f_i^{... ...mbox{$\parallel$}(c_{0i} -C_iR -H_i^Tu)^+ \mbox{$\parallel$}_i;$$

p и q соответствуют следующим упорядочениям оптимизируемых функций:

$$f_{m_o}(x),\,...\,,f_1(x);\qquad c_k^Tx,\,...\,,c_1^Tx, c_0^Tx;$$ (41)

$$f_{n_o}^{\ast}(u),\,...\,,f_1^{\ast}(u);\qquad b_l^Tu,\,...\,,b_1^Tu, b_0^Tu;$$ (42)

{xⁱ}₀^n₀ и {u^j}₀^m₀ -- подвекторы векторов x и u, соответствующие разрезу матрицы A на вертикальные H_i и горизонтальные A_j подматрицы; ``$\ast$'' над $\mbox{$\parallel$}\,\cdot\,\mbox{$\parallel$}$ -- сопряженная норма.

Задачи (39) и (40) синтезируют смысл последовательной аппроксимации несовместных ограничений задач (22), (24) и исходной последовательной оптимизации упорядоченных систем линейных функций {c_i^Tx}₁^k и {b_j^Tu}₁^l.

Следующий шаг состоит в двойной перекрестной скаляризации этих задач, а именно:

$$P: \max \{ c_0^Tx +(C^Tx, R) -\sum_{j=1}^{m_0} \bar{R}_j \mbox{$\parallel$}( A_jx -b_{0j} -B_Jr)^+ \mbox{$\parallel$}_j\ \vert$$

$$A_0x\leq b_{00} +B_0r,\ x\geq 0,\ \mbox{$\parallel$}x^i \mbox{$\parallel$}\leq \bar{r}_i,\ i=1,\,...\,,n_0 \},$$ (43)

$$P^{\char93 }: \min \{ b_0^Tu + (B^Tu, r) +\sum_{i=1}^{n_0} \b... ...l$}( c_{0i} -C_iR -H_i^Tu)^+ \mbox{$\parallel$}_i^{\ast}\ \vert$$

$$H_0^Tu \geq b_{00} +C_0R,\ u\geq 0,\ \mbox{$\parallel$}u^j \mbox{$\parallel$}^{\ast}_j \leq \bar{R}_j,\ j=1,\,...\,,m_0\}.$$ (44)

Заметим, что выписанные задачи -- это задачи (16) и (17), в которых выделены критериальные функции c₀^Tx и b₀^Tu, поставленные в упорядочениях (41) и (42) на последних местах. Конструкции задач (43) и (44) являются наиболее общими в исследованиях автора по двойственности для несобственных задач линейного, паретовского, последовательного и парето-последовательного программирования. В задачах (43), (44) присутствует система векторных и логических параметров, например, свобода разбиения матрицы A (и параллельно матриц B и C) на горизонтальные и вертикальные подматрицы, некоторые из которых могут принимать пустые значения. За счет назначения этих параметров можно обеспечивать необходимые свойства для двойственности, аппроксимационного ее смысла и т.д.

Сразу же отметим, что основная нацеленность в изучении задач (34), (40) и (43), (44) состоит в обеспечении реализации схемы:

$$\begin{array}{rcc} (39) & \stackrel {\mbox {\scriptsize\mbox... ...ightarrow }} & (44),\\ [12pt] & \mbox {Схема 5} & \end{array}$$

при этом связь между задачами (43) и (44) обеспечивается свойством регулярной двойственности.

Сформулируем ряд утверждений, подготовляющих доказательство теоремы 5. Для полноты приводится лемма из работы [1, лемма 2.2].

Лемма 1. Для разрешимой задачи

$$\max\nolimits_p\left\{ \left [ \begin{array}{c}c_0^Tx\\ [4pt] c_1^Tx \end{array} \right ]\ \Bigg \vert\ x\,\in\,M \right\}$$

(при $p=[1,\ 0])$ выбор числа $\bar{R}_1>0$, обеспечивающего эквивалентный (по Arg) переход к задаче

$$\max\,\{ (c_0,\ x) +\bar{R}_1(c_1,\ x) \mbox{$\,\mid\,$}x\,\in\,M \},$$

можно осуществить независимо от реализации вектора b; здесь $M=\{x\geq 0\,\mid\,Ax\leq b\}$.

Обобщением ее служит

Лемма 2. Пусть в разрешимой задаче

$$\max\, \left\{ \left [ \begin{array}{c}c_0^Tx\\ [4pt] -\mb... ...rallel$}\end{array} \right]\ \Bigg \vert\ x\,\in\,M \right \}$$ (45)

норма $\mbox{$\parallel$}\,\cdot\,\mbox{$\parallel$}$ кусочно-линейна. Тогда выбор числа $\mbox{$\alpha$}> 0$, обеспечивающего эквивалентный (по Arg) переход от $(\ref{f45})$ к задаче

$$\max\,\{(c_0,\ x)-\mbox{$\alpha$}\,\mbox{$\parallel$}\,(Dx-d)^+\mbox{$\parallel$}\mbox{$\,\mid\,$}x\,\in\,M\},$$ (46)

может быть осуществлен независимо от реализации вектора d, при этом, если для рассматриваемой эквивалентности годится $\mbox{$\alpha$}> 0$, то годится и $\bar{\mbox{$\alpha$}}>\mbox{$\alpha$}$.

Д о к а з а т е л ь с т в о этой леммы состоит в детализации доказательства леммы 1 с использованием универсального представления кусочно-линейной нормы $\mbox{$\parallel$}\,\cdot\,\mbox{$\parallel$}$ в виде $\mbox{$\parallel$}\,z\,\mbox{$\parallel$}=\max\limits_{(j)} \mid (c_j,\ z) \mid$, при этом r{c_j}=k -- размерность пространства переменной $z,\ \ c_j\geq 0,\ \ \forall \,j$.

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

$$\min\, \{\mbox{$\parallel$}\, (Dx-d)^+\mbox{$\parallel$}\mbox{$\,\mid\,$}x\in M\},$$ (47)

тогда сама задача (45) состоит в

$$% latex2html id marker 13305 \max\, \{c_0^Tx \mbox{$\,\mid\,$}x \,\in\,{\mbox{\rm Arg}}\,(\ref{f47}) \}.$$

Задачу (47) можно переписать в форме линейной программы

$$\min\, \{ t\ \vert\ -t\leq (c_j, z) \leq t,\ \ Dx-d\leq z, z\geq 0,\ \ x\in M \}.$$

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

Пусть система $Ax\leq b$ разбита произвольным образом на подсистемы $A_j x\leq b_j,\ \ j=0,1,\,...\,,m_0$, при этом подсистема $A_0 x\leq b_0,\ \ x\geq 0$ -- совместна. Выпишем задачи

$$\max\nolimits_p \left\{ \left. \left [ \setlength{\arrayco... ...ay} \right ] \right \vert A_0 x \leq b_0,\ x \geq 0 \right\},$$ (48)

$$p=[m_0,\,...\,,1,0];$$

$$\max \{(c, x)-\sum_{j=1}^{m_0}\bar{R_j} \mbox{$\parallel$}(... ...x{$\parallel$}_j \mbox{$\,\mid\,$}A_0x \leq b_0,\ x\geq 0 \}.$$ (49)

Обобщением леммы 2 служит

Лемма 3. Если нормы $\{\,\mbox{$\parallel$}\,\cdot\,\mbox{$\parallel$}_j\,\}$ кусочно-линейны и $(\ref{f48})$ разрешима, то выбор параметров $\bar {R}_j\geq 0$, реализующих эквивалентный переход от $(\ref{f48})$ к $(\ref{f49})$, может быть осуществлен независимо от реализации вектора b.

Д о к а з а т е л ь с т в о проводится путем последовательного применения леммы 2.

З а м е ч а н и е. Обозначения в леммах 1-3 мы не связываем прямым образом с обозначениями в задачах (39), (40), (43) и (44), хотя сформулированные леммы подготавливают анализ перечисленных задач.

Выделим некоторые условия, необходимые для формулировки теоремы:

1⁰. Выполняются необходимые условия (27), (28) разрешимости задач (22), (24);

2⁰. Все нормы в (43), (44) кусочно-линейны и монотонны;

3⁰. Подсистемы $A_0 x \leq b_{00}+B_0 r,\ \ x \geq 0$ и $H_0^T\geq c_{00}+C_0 R,\ \ u\geq 0$ совместны при любых $r \geq0$ и $R \geq0$.

Теорема 5.

1. Пусть при произвольных R>0 и r>0 выполняются условия $2^0,\ \ 3^0$ и $\bar{r}_i$ выбраны в соответствии $\bar{r}_i>\min\,\{ \mbox{$\parallel$}u^j\mbox{$\parallel$}_j^{\ast} \mbox{$\,\mid\,$}u\,\in\,M_0^{\ast}(R)\}$. Тогда задачи P и P^# разрешимы и их оптимальные значения совпадают.

2. Если выполняются условия 1⁰-3⁰, то существует непустая область значений параметров R>0 и r>0, $\{\bar{R}_j\}_1^{m_0}$, $\{\bar{r}_i\}_1^{n_0}$ таких, что реализуется схема 5.

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

1. Сделав в задачах (43), (44) переобозначения: b₀+Br=: b, c₀+Cr=: c, B_jr+b_0j=: b^j, c_0i+C_iR=: cⁱ, H_i=: B_i, мы получим формально задачи C и C^# из [3, стр. 49], для которых справедлива теорема 6.12 [3, стр. 60], что эквивалентно утверждению п. 1 сформулированной выше теоремы 5.1. Что касается условий упомянутой теоремы 6.12, то они выполняются в силу условий п. 1 теоремы 5.1.

2. Схема 5 оперирует lex-задачами (39), (40) и (43), (44), которым присвоены символы P и P^#. После переобозначений, приведенных в начале п. 1, последние принимают вид задач P и P^# из [1, стр. 179], а исходные задачи (39), (40) -- вид задач P_p(r), P_q^#(R). Разница между P_p(r), P_q^#(R) и (39), (40) состоит в том, что в последних lex-оптимизация осуществляется по расширительному списку функций (41), (42) с расширительным смыслом упорядочений p и q, соответствующим (41) и (42). Приведенные сопоставления приводят к редукции п. 2 теоремы 5.1 к теореме 4.1 [1, стр. 188], в нашем случае выраженной схемой 5. Здесь уместно следующее замечание относительно сказанной редукции. При скаляризации задач (39), (40), т.е. при реализации переходов (39) $\stackrel {\mbox {\scriptsize\mbox {Arg}}} {\stackrel {\sim} {\longrightarrow }}\,P$ и (40) $\stackrel {\mbox {\scriptsize\mbox {Arg}}} {\stackrel {\sim} {\longrightarrow }}\,P^{\char93 }$, выбор значений $\{\bar{R}_j\}_1^{m_0}$ и $\{\bar{r}_i\}_0^{n_0}$ не зависит от параметров r и R, в силу чего их выбор, обеспечивающий упорядочение функций {c_i}₀^k и {b_j}₀^l в общем списке упорядочений (41), (42), может осуществляться после выбора параметров $\{\bar{R}_j\}_1^{m_0}$ и $\{\bar{r}_i\}_0^{n_0}$. В этом состоит эффект применения лемм 1 и 2.

З а к л ю ч е н и е. Данную работу в определенном смысле можно считать замыкающей в ряду тех, которые посвящены симметричной двойственности для некоторых классов задач линейной оптимизации, а именно, для лексикографической, паретовской и парето-лексикографической оптимизации в вариантах их разрешимости (собственности) и неразрешимости (несобственности). В ней не косвенно (как в работах [1,2]), а прямым образом допускается свойство несобственности для исходных задач. В целом, в работах [1,2] и данной определены основные схемы двойственности, сформулированы теоремы двойственности, затронуты вопросы аппроксимации в случае неразрешимости задач. Конечно, возможности обобщений результатов здесь широкие, в частности, возможности переноса на случай произвольного пространства и числа критериев произвольной мощности. Для конечномерной ситуации представляет интерес дальнейшая разработка введенной автором $\pi$'-оптимизации [2, § 7], связанной с полиэдральной оптимизацией вообще. Под последней понимаются задачи оптимизации кусочно-линейных функций при ограничениях в форме систем кусочно-линейных неравенств без предположений выпуклости, что и определяет их трудность. Требует нетривиальных усилий и создание методов, обеспечивающих решение таких задач. Их теоретический анализ наталкивается на необходимость дальнейшего развития полиэдральной алгебры.

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

1. Еремин И.И. Лексикографическая двойственность для несобственных задач линейного и квадратичного программирования // Труды ИММ УрО РАН. -1992. -T. 1. -C. 178-192.
   
2. Еремин И.И. Двойственность для парето-последовательных задач линейного программирования // Труды ИММ УрО РАН. -1995. -T. 3.
   -C. 245-261.
   
3. Еремин И.И., Мазуров Вл.Д., Астафьев Н.Н. Несобственные задачи линейного и выпуклого программирования. -М.: Наука, 1983. -336 с.
   
4. Черников С.Н. Линейные неравенства. -М.: Наука, 1968. -488 с.

90С25
Eremin, I.I. Duality for improper problems of Pareto and lexicographical linear optimization. (Russian)
Trudy Inst. Mat. i Mekh. (Ekaterinburg) 4 (1996), 322-336.

Recent advances on symmetric duality for sequential and Pareto-sequential linear optimization problems are proceeded. Unlike to earlier author's works this problems may be improper (unsolvable in the usual sense). Some ways to optimal approximation of the problems are indicated.