I. ДВОЙСТВЕННОСТЬ ДЛЯ ЛИНЕЙНЫХ ЗАДАЧ ОПТИМИЗАЦИИ.

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

Если $\mathfrak{M}$ - некоторый исходный математический объект (модель), то двойственный объект  ${\mathfrak{M}}^{\ast}$, вообще говоря, выступает как некий внешний по отношению к $\mathfrak{M}$ объект ''наблюдения'' за $\mathfrak{M}$. Конечно, двойственность в зависимости от ее конкретного содержания, определяемого конкретной математической дисциплиной (алгебра, функциональный анализ, выпуклый анализ, теория оптимального управления и т.д.), несет в себе следы специфики соответствующей дисциплины. Но именно это обстоятельство и превращает двойственность в математике в здание хотя в определенном смысле и единой, но гармонически организованной и насыщенной архитектуры.

Содержание двойственности в математическом программировании состоит в сопоставлении исходной задаче C другой задачи $C^{\ast}$, формируемой по определенным правилам и называемой двойственной. Эти задачи связаны математически содержательными соотношениями, позволяющими, например, получить оценки критериальной эффективности всех параметров, формирующих задачу C; свести решение оптимизационной задачи к решению некоторой системы неравенств; сформировать в изящной форме условия оптимальности; оценить скорость сходимости итерационных процессов для задачи C и т.д.

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

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

1. Задача линейного программирования и ее экономическая интерпретация

Выпишем задачу ЛП в удобном для дальнейшего виде:

$$\max\, \{(c,\ x) \mbox{$\,\mid\,$}(a_j,\ x) \leq b_j,\quad j=1,\,...\,,m,\quad x\geq 0 \};$$ (1.1)

здесь $c=[c_1,\,...\,,c_n]^T$, $a_j=[a_{j1},\,...\,,a_{jn}]^T$. Введя обозначения $b=[b_1,\,...\,,b_m]^T$, $A=[a_{ji}]_{1,1}^{m,n}$, $X=[x_1,\,...\,,x_n]^T$, задачу (1.1) можно переписать в матричном виде

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

Дадим экономическую интерпретацию этой задачи.

Пусть имеется некое производство, выступающее в качестве преобразователя ${\mathfrak{U}}$ системы исходных ингредиентов $b_1,\,...\,,b_m,$ обладающих ценностью, в новую систему носителей ценности - совокупность продуктов. Термины производство, ценность, продукт, а ниже - оценка (как измеритель ценности) будут употребляться в качестве исходных.

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

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

$$p_i=[a_{1i},\,...\,,a_{mi}]^T \,\in\,\mbox{{\bf E}$_{m}$},\qquad i=1,\,...\,,n,$$

при этом координаты вектора p_i будем интерпретировать как затраты ингредиентов, приходящиеся на единичную интенсивность (например на единицу времени) использования i-го технологического способа. Саму же интенсивность обозначим через x_i (x_i =1 - единичная интенсивность).

Предположим, что затраты ингредиентов и создаваемая ценность подчиняются закону линейной зависимости от вектора интенсивностей $x=[\, x_1,\,...\,,x_n \,]^T$. В этом предположении затраты j-го ингредиента, отнесенные к вектору x, выразятся величиной $(a_j,\ x)$, $i=1,\,...\,,m$. Так как границы сверху для них определены числами b_j, то должны выполняться неравенства

$$(a_j,\ x) \leq b_j,\qquad j=1,\,...\,,m.$$

Содержательный смысл вектора x, задающего уровень производства, диктует ограничение $x\geq 0$. Таким образом, нами получена система ограничений задачи (1.1). Сказанное может быть подытожено схемой

$$\mbox{{\bf E}$_{n}$}\,\ni\, x \,\stackrel {\textstyle {\mathfrak{U}}}{\longrightarrow }\, Ax =y \,\in\,\mbox{{\bf E}$_{m}$};$$

при этом $x\geq 0,\ \ y\leq b = [\, b_1,\,...\,,b_m \,]^T$.

Если c_i понимать как оценку ценности, заключенной в носителе конечного результата применения i-го технологического способа с интенсивностью x_i=1, то величина

$$(c,\ x)=\sum_{i=1}^{n} c_ix_i$$

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

Следовательно, задача (1.1) решает вопрос об отыскании уровня производства (вектора интенсивностей), подчиненного условиям технологической допустимости (формально - системе линейных неравенств) и доставляющего для $(c,\ x)$ максимальное значение.

Возможна несколько модифицированная интерпретация задачи (1.1), а именно: пусть x_i - объем производства продукции i-го вида по i-му технологическому способу, c_i - цена реализации единицы продукции i-го вида. Тогда $(c,\ x)$ выражает доход от реализации продукции, который максимизируется.

Остановимся на полезной интерпретации задачи ЛП в форме

$$\min\,\{ (c,\ x) \mbox{$\,\mid\,$}Ax\leq b,\quad Bx\geq d,\quad x\geq 0 \}.$$ (1.2)

В основу положим перечень технологических способов $i=1,\,...\,,n$ с интенсивностями $x_i\geq 0$ их использования; c_i - трудозатраты на единицу интенсивности x_i=1; b - вектор ресурсов; i-ый столбец p_i матрицы A - вектор затрат ресурсов, приходящихся на единичную интенсивность x_i=1; i-ый столбец h_i матрицы B - вектор выпуска продукции, приходящийся на единичную интенсивность x_i=1; d - зафиксированный уровень производства продукции. Модель (1.2) в введенных терминах читается так: отыскать уровень производства $x\geq 0$, удовлетворяющий ресурсным ограничениям $Ax\leq b$ и условиям на необходимый уровень производства продукции $Bx\geq d$, обеспечивающий минимум трудозатрат.

По существу, модель (1.2) и приведенная интерпретация (с возможностями расширения объема содержания введенных терминов) реализуют синтез требований и характеристик общеэкономического уровня, предъявляемых ко всякой естественной экономике. Положив M= $\{ x\geq 0 \mbox{$\,\mid\,$}Ax\leq b \}$, $N=\{ x\geq 0 \mbox{$\,\mid\,$}Bx\geq d \}$, ситуацию модели (1.2) можно изобразить геометрически: см. Рис. 1.

На рисунке $S=M\,\bigcap\,N\neq \emptyset$, $\bar{x}$ - вектор оптимального уровня производства, отвечающий направлению изображенного вектора c. Многогранники M и N выступают в качестве областей ''ресурсных возможностей'' и ''потребностей''. На практике, да и в общем смысле (в соответствии с аксиомами ''общества потребления''), многогранники M и N находятся в состоянии ''противостояния'', несогласованности, что можно выразить пустотой их пересечения: $S=M\,\bigcap\,N =\emptyset$.

Обобщением модели (1.2) в смысле задания структуры ее ограничений могла бы служить система неравенств

$$A_jx \left ( \begin{array}{c}\leq \\ \geq \\ = \end{array}\right ) b^j,\qquad j=1,\,...\,,k,\qquad x\geq 0,$$ (1.3)

где A_jx и b^j соединены одним из перечисленных отношений порядка. Это соответствует возможности как угодно полной структуризации всех участвующих в экономическом (производственном) процессе факторов, покрывающих области ресурсных, технологических и потребительских описаний. Детализация моделей типа (1.2) при ограничениях (1.3) приводит к различным классическим моделям математической экономики. В (1.3) отдельные блоки (т.е. подсистемы при различных j) могут не согласовываться (вступать в противоречие), т.е. при объединении давать несовместные системы. Такие ситуации соответствуют так называемым несобственным задачам линейного программирования.

2. Игра двух лиц с нулевой суммой

Игра двух лиц определяется: 1) перечнем игроков (1-ый игрок, 2-ой игрок), 2) множествами X и U стратегий x и u 1-го и 2-го игроков соответственно и 3) платежными функциями $F_1(x,\ u)$ и $F_2(x,\ u)$, означающими выигрыши игроков при независимом выборе ими стратегий $x\,\in\,X$ и $u\,\in\,U$. Если $F_1(x,\ u) +F_2(x,\ u) =0$, т.е. выигрыш 1-го игрока равен проигрышу 2-го, то игра называется игрой с нулевой суммой. В случае такой игры можно оперировать лишь функцией выигрыша 1-го игрока $F_1(x,\ u) =:\ F(x, u)$, она же - функция проигрыша для 2-го игрока. Одним из важнейших принципов анализа такой игры является принцип гарантированного результата. Он направлен на отыскание игроками стратегий, обеспечивающих гарантированные выигрыши. Формализацию такого подхода можно осуществить путем следующих рассуждений. Если 1-ый игрок зафиксирует свою стратегию $x\,\in\,X$, то он может подсчитать свой гарантированный выигрыш $E_1(x) =\min\limits_{u\,\in\,U}\, F(x,\ u)$, а затем его максимизировать, т.е. подсчитать

$$\max_{x\,\in\,X}\, E_1(x) =\max_{x\,\in\,X}\, \min_{u\,\in\,U}\, F(x, u).$$

Для 2-го игрока такой подход дает

$$\max_{u\,\in\,U}\, \min_{x\,\in\,X}\, [-F(x,\ u)] = - \min_{u\,\in\,U}\, \max_{x\,\in\,X}\, F(x,\ u).$$

Таким образом, содержательно возникли две задачи:

$$\max_{x\,\in\,X}\, \min_{u\,\in\,U}\, F(x,\ u) =:\ F_1,$$ (2.1)

$$\min_{u\,\in\,U}\, \max_{x\,\in\,X}\, F(x,\ u)=:\ F_2.$$ (2.2)

Если $F_1 =F_2\ (=:\ F_0) =F(\bar{x},\ \bar{u}),\ \ \bar{x} \,\in\, X,\ \ \bar{u} \,\in\,U$, то число F₀ называется ценой игры, а $\bar{x}$ и $\bar{u}$ - оптимальными стратегиями 1-го и 2-го игроков соответственно (стратегиями равновесия). Вообще говоря, совпадение F₁ и F₂ необязательно. Задачи (2.1) и (2.2) по совокупности будем называть формализацией игры двух лиц с нулевой суммой на основе принципа гарантированного результата.

3. Игровая модель ''Производство - Рынок''

На задачу L можно смотреть как на модель Производства (учитывая данную ей экономическую интерпретацию). Осуществим расширение ситуации за счет включения Рынка, образуя таким образом систему ''Производство-Рынок'':

Рассмотрим Производство в роли 1-го игрока с множеством стратегий $X =\{ x\geq 0\}\,\subset \,\,$E_n, а Рынок - в роли 2-го игрока с функциями: 1) поглощение продукции Производства по фиксированным ценам c_i, $i=1,\,...\,,n$ и 2) поглощение (покупка) или продажа ресурсов по ценам игрового взаимодействия в системе ''Производство - Рынок''. Множеством стратегий ''Рынка'' будет совокупность ценовых векторов $U =\{ u\geq 0\}\,\subset \,\,$E_m, т.е. u_j - цена единицы ресурса с номером j, $j=1,\,...\,,m$. В роли платежной функции в данной игре выступает

$$F(x,\ u) =(c,\ x) -(Ax-b,\ u)$$ (3.1)

$$(=(c,\ x) -\sum_{j=1}^{m} u_j\, [(a_j,\ x) -b_j]),$$

являющаяся функцией Лагранжа, соотнесенной задаче L. Эта функция, очевидно, и имеет смысл выигрыша (дохода) 1-го игрока в результате реализации игроками своих стратегий $x\,\in\,X$ и $u\,\in\,U$, т.е. в результате обменных операций по продукции и ресурсам: $(c,\ x)$ - доход от продажи продукции x_i по фиксированным ценам c_i, $i=1,\,...\,,n$; если $(a_j,\ x) -b_j>0$, то $u_j\,[(a_j,\ x) -b_j]$ - плата 1-го игрока 2-му игроку за покупку j-го ресурса в количестве $(a_j,\ x) -b_j$ по цене u_j; если $(a_j,\ x) -b_j<0$, то слагаемое $-u_j\,[(a_j,\ x) -b_j] = u_j\,[b_j -(a_j,\ x)]$ читается как доход 1-го игрока от продажи излишков j-го ресурса в количестве $b_j -(a_j,\ x)$ по цене u_j, $j=1,\,...\,,m$. Следовательно, вся сумма $-\mbox{$\sum\limits_{j=1}^{m}$} u_j\, [(a_j,\ x) -b_j] =-(Ax-b,\ u)$ - это доход 1-го игрока от совокупности рыночных операций по продаже излишков и покупке недостающих ресурсов, рассчитанных на уровень производства x, а $F(x,\ u)$ - доход 1-го игрока в целом.

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

$$\max_{x\geq 0}\, \min_{u\geq 0}\,[(c,\ x) -(Ax-b,\ u)],$$ (3.2)

$$\min_{u\geq 0}\, \max_{x\geq 0}\,[(c,\ x) -(Ax-b,\ u)].$$ (3.3)

К ним применимы все определения, сформулированные для задач (2.1) и (2.2). В данной ситуации оптимальную стратегию 1-го игрока (Производства) естественно назвать оптимальным планом, а оптимальную стратегию 2-го игрока (Рынка) - вектором оптимальных (равновесных) цен на ресурсы. На самом деле, понятия оптимального плана в смысле оптимальной стратегии и оптимального плана задачи L совпадают.

4. Игровой подход к двойственности

Содержательный подход к двойственности, т.е. подход к формулировке задачи $L^{\ast}$ - двойственной к L, может быть реализован путем установления следующих эквивалентных переходов $\stackrel {\textstyle \sim}{\longrightarrow }$:

$$(3.2)\, \stackrel {\textstyle \sim}{\longrightarrow }\,L,$$ (4.1)

$$\,(3.3)\, \stackrel {\textstyle \sim}{\longrightarrow }\,L^{\ast}.$$ (4.2)

Здесь эквивалентный переход означает эквивалентное преобразование. Обратимся к (4.1). Рассмотрим внутреннюю операцию в (3.2), т.е. $\min\limits_{u\geq 0}\, F(x,\ u)$.

$$\min_{u\geq 0}\, F(x,\ u) = \min_{u\geq 0}\,[(c,\ x) -(Ax-b,\ u)]=$$

$$= \left \{ \begin{array}{rl} (c,\ x), & \ {\mbox{\rm если}}\... ...$}, & \ {\mbox{\rm если}}\quad Ax\not\leq b \end{array}\right.$$

(здесь $x\geq 0$). Отсюда и следует

$$\max_{x\geq 0}\, \min_{u\geq 0}\, F(x,\ u) = \max_{x\geq 0}\,\{ (c,\ x) \mbox{$\,\mid\,$}Ax\leq b \},$$

т.е. имеет место (4.1). Убедимся в справедливости (4.2). Преобразуем вначале функцию Лагранжа

F(x, u) =(c, x) -(Ax-b, u) = (b, u) +(-A^Tu+c, x). (4.3)

Рассмотрим внутреннюю операцию в (3.3), т.е. $\max\limits_{x\geq 0}\, F(x,\ u)$. Имеем

$$\max_{x\geq 0}\, F(x,\ u) =\max_{x\geq 0}\, [(b,\ u) +(-A^Tu+c,\ x)]=$$

$$= \left \{ \begin{array}{rl} (b,\ u), & \ {\mbox{\rm если}}\... ..., & \ {\mbox{\rm если}}\quad A^Tu\not\geq c \end{array}\right.$$

(здесь $u\geq 0$). Отсюда и следует

$$\min_{u\geq 0}\, \max_{x\geq 0}\, F(x,\ u) = \min_{u\geq 0}\,\{ (b,\ u) \mbox{$\,\mid\,$}A^Tu\geq c \}.$$

Итак, задачу $L^{\ast}$ - двойственную к L, мы получили как эквивалент игровой задачи (3.3) в рамках игровой модели ''Производство - Рынок'', при этом (3.3), а следовательно и $L^{\ast}$, выступает как задача построения оптимальных (равновесных) цен на ресурсы. Вместе с тем мы получили эквивалентность задачи L игровой задаче (3.2). Это, в частности, дает оптимальность $\bar{x}$ для L, если $\bar{x}$ - оптимальная стратегия игры (3.2), (3.3); и обратно: если $\bar{x}$ - оптимальное решение (оптимальный план) задачи L, то при некотором $\bar{u}\geq 0$ пара $[\bar{x},\ \bar{u}]$ будет отвечать определению оптимальных стратегий игроков.

5. Подход к двойственности, связанный с переобозначением роли переменных x и u в функции Лагранжа

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

Функция Лагранжа может быть соотнесена вообще любой задаче на условный экстремум, при этом необходимо соблюсти вполне определенное правило такого соотнесения. Выпишем эти правила (прямое и обратное) для задач на $\max$ и $\min$ в двух формах:

$$\left. \begin{array}{l} P_1:\ \max f(x)\\ [4pt] \qquad f_j(... ...\\ [4pt] \qquad x\geq 0 \end{array}\right \} \rightleftarrows$$

$$\rightleftarrows \begin{array}{l}\\ [4pt] F_1(x,\ u) =f(x) ... ...m} u_j f_j(x),\\ [4pt] u_j\geq 0,\ \ \forall \,j, \end{array}$$

$$\left. \begin{array}{l} P_2:\ \min f(x)\\ [4pt] \qquad f_j(... ...\\ [4pt] \qquad x\geq 0 \end{array}\right \} \rightleftarrows$$

$$\rightleftarrows \begin{array}{l}\\ [4pt] F_2(x,\ u) =f(x) ... ...m} u_j f_j(x),\\ [4pt] u_j\geq 0,\ \ \forall \,j. \end{array}$$

Обратное соответствие $\longleftarrow$ неоднозначно в связи с возможностью переписать $F_1(x,\ u)$ и $F_2(x,\ u)$ в виде $F_1(x,\ u) =f(x) +\mbox{$\sum\limits_{j=1}^{m}$} u_j\, [-f_j(x)]$, $F_2(x, u) =f(x) -\mbox{$\sum\limits_{j=1}^{m}$} u_j\, [-f_j(x)]$. Тогда справедливы и такие соответствия:

$$F_1(x,\ u) \,\longrightarrow \, \left \{ \begin{array}{l} P_... ...uad j=1,\,...\,,m,\\ [4pt] \qquad x\geq 0 \end{array}\right .$$

и

$$F_2(x,\ u) \,\longrightarrow \, \left \{ \begin{array}{l} P_... ...ad j=1,\,...\,,m,\\ [4pt] \qquad x\geq 0. \end{array}\right .$$

Схема рассмотренных соответствий не противоречит логике механического смысла функции Лагранжа. Эту схему изобразим в кратком виде:

$$\begin{array}{l} P_1 \,\rightleftarrows\, F_1 \,\longright... ...,\rightleftarrows\, F_2 \,\longrightarrow \, P_4. \end{array}$$ (5.1)

Применим ее к задаче L и ее функции Лагранжа. Равенство (4.3) позволяет посмотреть на функцию Лагранжа F(x, u) иначе, а именно: на u как на переменную, а на x как на вектор множителей Лагранжа. Тогда по правилу соответствия $F_1 \,\longrightarrow \, P_3$ будем иметь:

$$L \,\longrightarrow \, F(x,\ u) \,\longrightarrow \, \min\,\{ (b,\ u) \mbox{$\,\mid\,$}A^Tu\geq c, \ u\geq 0 \},$$

т.е. задача $L^{\ast}$ возникла как результат реализации соответствия $F_1 \,\longrightarrow \, P_3$, в котором в выражении функции Лагранжа переменные x и u поменялись своими смысловыми ролями. Приведем более полную картину применения схемы (5.1):

Заметим, что правило перехода $(\ast)$ к двойственной задаче в верхней строчке схемы согласуется с правилом перехода $(\ast)$ в нижней строчке.

6. Построение двойственной задачи на основе термодинамической аксиоматики

Оттолкнемся от схемы:

в которой изображен Преобразователь (под термином Производство) входа (вектор ресурсов b) в выход (вектор продукции x). В принятой интерпретации задачи ЛП (1.1) вектор исходных ингредиентов (ресурсов) b не наделен системой цен - как измерителей ценностей этих ингредиентов, вектор же продукции такими измерителями наделен - это вектор c. Можно на систему ценностных измерителей посмотреть более широко, а именно - как на систему неких энергетических измерителей, подчиняющихся законам термодинамики, запрещающих для любого энергетического преобразователя КПД (коэффициент полезного действия) больше единицы. В нашей ситуации это означает, что суммарная энергетическая оценка входа должна быть не меньше, чем аналогичная оценка выхода. Если вектор c трактовать как вектор энергетических измерителей продукции x, а $u\,\in\,$E_n⁺ - подлежащий определению вектор энергетических измерителей исходных ингредиентов, то высказанная аксиома может быть выражена неравенством $(h,\ u)\geq (c,\ x)$. В частности, если h=h_i - i-ый столбец матрицы A, выражающий расход ингредиентов на единицу продукции i-го вида и оцениваемый величиной c_i, то выписанное неравенство примет вид $(h_i,\ u)\geq c_i$.

Свойства, накладываемые на Преобразователь, сформулируем в форме следующих аксиом:

1)

суммарная оценка используемых ингредиентов подчиняется закону линейной зависимости от вектора их оценок u_j, $j=1,\,...\,,m$;

2)

суммарная оценка ингредиентов, расходуемых в результате применения i-го технологического способа на единицу продукции, не менее оценки c_i получаемой единицы этой продукции;

3)

оптимальные оценки ингредиентов определяются из условия максимума КПД Преобразователя.

Условия 1) и 2) диктуют систему линейных ограничений

$$(h_i,\ u) =\sum_{j=1}^{m} a_{ji}u_j \geq c_i,\qquad i=1,\,...\,,n$$

с многогранником $M^{\ast}$. Условие 3) формулирует задачу

$$\mbox{КПД} = \frac{\mbox{выход}}{\mbox{вход}} = \frac{\textstyle (c,\ x)}{\textstyle (b,\ u)} \,\longrightarrow \, \max,$$

при этом, естественно, $x\,\in\,M,\ \ u\,\in\,M^{\ast}$. В соответствии с этим

$$\mbox{КПД}_{\mathrm{opt}} =\max\, \frac{\textstyle \{ (c, x) ... ...id x\in M \}}{\textstyle \min \{ (b, u) \mid u\in M^{\ast} \}}.$$

В числителе данного соотношения стоит задача L, моделирующая Производство, в знаменателе - задача $L^{\ast}$ - двойственная к L, моделирующая задачу отыскания оптимальных оценок (в энергетическом истолковании) исходных ингредиентов.

В изложенной интерпретации задачи $L^{\ast}$ употребленный термин ''энергетическая оценка'' имеет чисто ассоциативный смысл, и большего в него вкладывать не следует (по крайней мере в рамках данного кратко изложенного подхода к формированию двойственности в ЛП).

7. Теорема двойственности

Сформулируем основные утверждения, связывающие задачи

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

и

$$% latex2html id marker 3664 L^{\ast}:\ \min\,\{ (b,\ u) \mbox{$\,\mid\,$}A^Tu\geq c,\ \ u\geq 0\}.\eqno (\ref{n1771})^{\ast}$$

Введем стандартные обозначения: $\mathrm{Arg}\,$L - оптимальное множество задачи L, $\mathrm{arg}\,$L - конкретный элемент из $\mathrm{Arg}\,$L, $\mathrm{opt}\,$L - оптимальное значение задачи L. Если S - символ для обозначения некоторой системы линейных неравенств, то $\mathrm{Arg}\,$S будет означать множество ее решений. Отметим очевидные соотношения:

$$\mathrm{Arg}\,L =M\,\bigcap\,\{x\ \mbox{$\,\mid\,$}\ (c,\ x) =\, \mathrm{opt}\,L \},$$

$$\mathrm{Arg}\,L^{\ast} =M^{\ast}\,\bigcap\,\{u\ \mbox{$\,\mid\,$}\ (b, u) =\, \mathrm{opt}\,L^{\ast} \},$$

где $M= \{ x\geq 0 \mbox{$\,\mid\,$}Ax\leq b\}$, $M^{\ast}= \{ u\geq 0 \mbox{$\,\mid\,$}A^Tu\geq c\}$.

Теорема 7.1   Справедливо неравенство

$$(c,\ x)\leq (b,\ u),\quad \forall \,x\,\in\,M,\quad \forall \,u\,\in\,M^{\ast}.$$

Следствие 7.1   Если $(c, \bar{x}) = (b, \bar{u})$, $\bar{x}\in M$, $\bar{u}\in M^{\ast}$, то $\bar{x}\,\in\,\mathrm{Arg}\,L$, $\bar{u}\,\in\, \mathrm{Arg}\,L^{\ast}$.

Теорема 7.2 (двойственности)   Если задача L разрешима, то $L^{\ast}$ также разрешима, при этом их оптимальные значения совпадают.

Теорема 7.3   Двойственная задача к двойственной совпадает с исходной, т.е. $(L^{\ast})^{\ast} =L$.

З а м е ч а н и е 7.1. Свойство взаимности является универсальным, т.е. не зависит от формы задания исходной задачи.

З а м е ч а н и е 7.2. Теорема 7.2 в силу свойства взаимности допускает и такую редакцию: из разрешимости $L^{\ast}$ вытекает разрешимость L и совпадение их оптимальных значений.

Теорема 7.2 позволяет сформулировать следующее утверждение.

Теорема 7.4   Задача L разрешима тогда и только тогда, когда $M\neq \emptyset$, $M^{\ast} \neq \emptyset$.

Задачам (7.1) и (7.1)$^{\ast}$ поставим в соответствие систему линейных неравенств

$$\left. \begin{array}{crcr} S: & Ax\leq b, & & A^Tu\geq c,\... ...[8pt] & (c,\ x) & \quad\geq & (b,\ u). \end{array}\right \}$$ (7.2)

Задача нахождения хотя бы одного решения этой системы называется симметрической задачей.

Связь между задачами L, $L^{\ast}$ в форме (7.1), (7.1)$^{\ast}$ и системой S устанавливает

Теорема 7.5   Задача L и система S одновременно разрешимы или неразрешимы, при этом в случае разрешимости

$$\mathrm{Arg}\,S = \mathrm{Arg}\,L \,\times\, \mathrm{Arg}\,L^{\ast},$$

т.е. множество решений системы S является декартовым произведением оптимальных множеств задач L и $L^{\ast}$.

Приведем схему формирования двойственной задачи $L^{\ast}$ при задании L в самом общем виде.

Сказанное выше о взаимных свойствах пары двойственных задач ЛП сохраняется, естественно, и для выписанной пары задач $\{L, L^{\ast}\}$.

В заключение данного пункта остановимся на некоторых содержательных аспектах двойственности. При игровом подходе к двойственности, т.е. к формированию двойственной задачи $L^{\ast}$ (см. п. 4), переменный вектор $u\geq 0$ выступает как вектор допустимых цен на ресурсы в игре ''Производство-Рынок'', а оптимальный вектор цен $\bar{u}\geq 0$ в силу эквивалентности (4.2) как оптимальный вектор задачи $L^{\ast}$. Таким образом, задача L как модель производства с фиксированными ценами на продукт дополняется моделью определения оптимальных цен (двойственных оценок) на ресурсы.

В соответствии с подходом к двойственности, изложенным в п. 6, $\mbox{КПД}_{\mathrm{opt}}\,=\,\frac{\textstyle (c,\ \bar{x})} {\textstyle (b,\ \bar{u})}$, где $\bar{x}\,\in\,\mathrm{Arg}\,$L, $\bar{u}\,\in\,$ $\mathrm{Arg}\,$$L^{\ast}$. По теореме двойственности $\mbox{КПД}{_\mathrm{opt}}\,=\,1$ ( $(c, \bar{x}) = (b, \bar{u})$), т.е. при оптимальном плане $\bar{x}$ Производства и оптимальных ценах $\bar{u}$ на ресурсы схема, изображенная на стр. , работает с коэффициентом полезного действия, равным единице. Заметим, что расширительного толкования этому факту придавать не следует.

8. Элементы маргинального анализа

Двойственность для задач ЛП позволяет исследовать некоторые дифференциальные свойства функции оптимума $\tilde{f}(y):=$ optL, где L -- произвольная задача ЛП, $y=[A,\ b,\ c \,]$.

Пусть

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

Теорема о маргинальных значениях для L - это теорема о формульном представлении производной функции оптимума $\tilde {f}(y)$ по произвольному направлению l из пространства вектора y. Примем в качестве l вектор $[\bigtriangleup A,\ \bigtriangleup b,\ \bigtriangleup c \,]$. Частный случай этой ситуации реализуется соотношением

$$\frac{\textstyle \partial \tilde {f}(y)}{\textstyle \partial l} =(\bar{u},\ \bigtriangleup b),$$ (8.2)

в котором роль направления l играет вектор  $\bigtriangleup b$ в пространстве вектора b (как информационного параметра задачи L), т.е. $l=\bigtriangleup b$. Если оптимальный вектор $\bar{x}$ исходной задачи (8.1) единственный, то имеет место аналог соотношения (8.2) в форме

$$\frac{\textstyle \partial \tilde {f}(y)}{\textstyle \partial l} =(\bar{x},\ \bigtriangleup c),$$ (8.3)

где $l=\bigtriangleup c$. В общем случае получение формулы для $\frac{\textstyle \partial \tilde {f}(y)}{\textstyle \partial l}$ выводит за рамки линейного анализа линейной задачи L.

Теорема 8.1   Пусть выполнены для задачи L условия:
$1.\ \exists\, p:\ Ap<b\,;$
2. Оптимальные множества $\mathrm{Arg}\,L=:\,\widetilde {M}$ и $\mathrm{Arg}\,L^{\ast} =:\,\widetilde {M}^{\ast}$ не пусты и ограничены.
Если $l= [\bigtriangleup A,\ \bigtriangleup b,\ \bigtriangleup c \,]$ - произвольное направление в пространстве вектора $y=[A,\ b,\ c \,]$, то

$$\frac{\textstyle \partial \tilde {f}(y)}{\textstyle \partia... ...x}) - (\bigtriangleup A\bar{x} -\bigtriangleup b,\ \bar{u})].$$ (8.4)

Следовательно, если L и $L^{\ast}$ разрешимы в единственных точках $\bar{x}$ и $\bar{u}$, то

$$\frac{\textstyle \partial \tilde {f}(y)}{\textstyle \partia... ...{x}) - (\bigtriangleup A\bar{x} -\bigtriangleup b,\ \bar{u}).$$ (8.5)

Следствие 8.1   В предположениях, дающих (8.5), справедливы соотношения:

$$\frac{\textstyle \partial \tilde {f}(y)}{\textstyle \partia... ...e {f}(y)}{\textstyle \partial a_{ji}} = -\bar{u}_j \bar{x}_i;$$ (8.6)

здесь     $\bar{u}^T =[\bar{u}_1,\,...\,,\bar{u}_m],\quad \bar{x}^T = [\bar{x}_1,\,...\,,\bar{x}_n]$.

В обозначении функции оптимума $\tilde {f}(y)$ в качестве аргумента ниже будем ставить тот фрагмент информационного вектора, который нас интересует: $\tilde {f}(b)$, $\tilde {f}(b_j)$ и т.д.

Сделаем замечание, связанное с содержательной интерпретацией двойственных оценок $\bar{u}_j$, $j=1,\,...\,,m$. В случае единственности оптимального вектора $\bar{u}$ задачи $L^{\ast}$ существует окрестность v(b) вектора $b\,\in\,V^0(b)$ (V⁰ - внутренность множества V) такая, что

$$\bar{b}\,\in\,V(b) \,\Longrightarrow \, \mathrm{Arg}\, \min_{u\in M^{\ast}} \,(\bar{b},\ u) =\{ \bar{u} \}.$$

Тогда при некотором малом t₀>0 и $\forall \, t\,\in\,(0, t_0 \,]$ имеем

$$\frac{\textstyle \tilde {f}(b+t\bigtriangleup b) -\tilde {f}(... ...}) -(b,\ \bar{u})}{\textstyle t} =(\bigtriangleup b,\ \bar{u}),$$

т.е.

$$\tilde {f}(b+t\bigtriangleup b) =\tilde {f}(b) +t (\bigtriangleup b,\ \bar{u}).$$ (8.7)

Если t₀>1, т.е. в качестве t, обеспечивающего (8.7), можно взять t=1, то при $\bigtriangleup b =[0,\ldots ,\bigtriangleup b_j=1,0,\ldots , 0]^T$ из (8.7) получается

$$\tilde {f}(b_j+1) =\tilde {f}(b_j) +\bar{u}_j,\qquad j=1,\,...\,,m.$$

Эти соотношения говорят о том, что оценки $\bar{u}_j$ выступают в качестве измерителей эффективности единицы j-го ресурса b_j в стандартной экономической интерпретации задачи L.

9. Двойственность для несобственных задач линейного программирования [23]

Под собственной задачей МП понимается разрешимая задача МП, для которой двойственная также разрешима и оптимальные значения этих задач совпадают. В противном случае задача называется несобственной (НЗ). В частности, если система ограничений в задаче неразрешима (противоречивая), то задача - несобственная. В случае задачи ЛП несобственность и неразрешимость - понятия эквивалентные. Если $M = \{ x\ge 0 \mbox{$\,\mid\,$}Ax\leq b\}$ и $M^{\ast} = \{ u\ge 0 \mbox{$\,\mid\,$}A^T u\ge c \}$ - допустимые множества для пары взаимно двойственных задач ЛП, например, в форме (1.1), то (как уже отмечалось) непустота M и $M^{\ast}$ соответствует разрешимости этих задач. В случае неразрешимости L (следовательно, и $L^{\ast}$) возможны три альтернативы:

1)

$M = \emptyset ,\ \ M^{\ast} \ne \emptyset$ - НЗ ЛП 1-го рода,

2)

$M \ne \emptyset ,\ \ M^{\ast} \ne \emptyset$ - НЗ ЛП 2-го рода,

3)

$M = \emptyset ,\ \ M^{\ast} = \emptyset$ - НЗ ЛП 3-го рода.

Причины и обстоятельства, порождающие неразрешимость модели, разнообразны. Это, в частности: неадекватное моделирование, противоречия между целями и ресурсными возможностями их достижения (находящие свое отражение в модели), перегруженность требований к объекту моделирования (например, к конструкции самолета), некорректность постановки (в смысле некорректности по Тихонову), противоречия между технологиями и средой (''грязные'' технологии и требования экологии) и т.д.

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

В ней $\stackrel {(\pi)}{\longrightarrow }$ означает переход (сопоставление) задачам L и L^* по единому правилу $\pi$ к разрешимым задачам P и P^*, обладающих свойствами: (P#)# = P и $\mathrm{opt}\,$P = $\mathrm{opt}\,$P#. Примерами реализаций Схемы 2 могут служить:

$$\left\{ \begin{array}{l} P_0:\ \max\,\{ (c,\,x) - (R,\,(Ax - ... ...- A^T u)^+) \mbox{$\,\mid\,$}0\le u\le R \}; \end{array}\right.$$

$$\left\{ \begin{array}{l} P_1: \max \{ (c, x) -(R_0\,\mbox{$\p... ...l$}u \mbox{$\parallel$}_p^{\ast} \le R_0 \}. \end{array}\right.$$

Здесь R и r - неотрицательные векторные параметры, $(\,\cdot\,)^+$ - положительная срезка вектора $(\,\cdot\,)$, R₀ и r₀ - неотрицательные числовые параметры, $\mbox{$\parallel$}\cdot \mbox{$\parallel$}_p$ и $\mbox{$\parallel$}\cdot \mbox{$\parallel$}_q$ - произвольные нормы в соответствующих пространствах, $\mbox{$\parallel$}\cdot \mbox{$\parallel$}_p^{\ast}$ и $\mbox{$\parallel$}\cdot \mbox{$\parallel$}_q^*$ - им сопряженные нормы.

Приведем более общую реализацию приведенной схемы. Пусть $A_j x \le b^j$ $(j =1,\,...\,,m_0)$ и $B_i^T u \ge c^i$ $(i =1,\,...\,,n_0)$ - произвольные разбиения систем $A x \le b$ и $A^T u \ge c$ на подсистемы (в предположении, что подсистемы $A_0 x \le b^0$, $x \ge 0$ и $B_0^T u \ge c^0$, $u\ge 0$ - совместны); {b^j}, {u^j}, {cⁱ}, {xⁱ} - разбиения векторов $b, u,\ c,\ x$ на подвекторы, соответствующие указанному разбиению. В принятых обозначениях задачи P и P# могут быть записаны следующим образом:

$$P: \sup \{ (c, x) -\sum_{j = 1}^{m_0} R_j\, \mbox{$\parallel$... ...\parallel$}_{p (j)} \mbox{$\,\mid\,$}A_0 x \le b^0,\ \ x \ge 0,$$

$$\mbox{$\parallel$}x^i \mbox{$\parallel$}_{q (i)} \le r_i\ \ (i =1,\,...\,,n_0) \},$$

$$P^\char93 : \inf \{ (b, u) -\sum_{i = 1}^{n_0}r_i\, \mbox{$\p... ...el$}_{q (i)}^{\ast} \mbox{$\,\mid\,$}B_0^T u\ge c^0,\ \ u\ge 0,$$

$$\mbox{$\parallel$}u^j \mbox{$\parallel$}_{p (j)}^* \le R_j\ \ (j =1,\,...\,,m_0) \}.$$

Теорема 9.1   1). Пусть $r_i > \min\, \{ \mbox{$\parallel$}x^i \mbox{$\parallel$}_{q (i)} \mbox{$\,\mid\,$} A_0 x\le b^0$, $x \ge 0 \}$ $(i =1,\,...\,,n_0)$ и задача P разрешима. Тогда $P^{\ast}$ разрешима и $\mathrm{opt}\,$ $P =\mathrm{opt}\,P^\char93$.
2). Если $\bar x$ и $\bar u$ допустимы для P и P# соответственно, то $f(\bar x) \le f^\char93 (\bar u)$, где f(x) и f#(u) - функции, оптимизируемые в P и P#. Отсюда следует: если $f(\bar x) = f^\char93 (\bar u)$, то $\bar x \,\in\, \mathrm{Arg}\,P$, $\bar u \,\in\,\mathrm{Arg}\,P^\char93$.

З а м е ч а н и е 9.1. Все нормы, фигурирующие в написании задач P и P#, предполагаются монотонными.

З а м е ч а н и е 9.2. Справедлив и обратный вариант теоремы.

З а м е ч а н и е 3. Решение задач P и P# сводится к решению следующей системы линейных и выпуклых неравенств:

$$\left\{ \begin{array}{l} A_0 x\le b^0,\ \ c\ge 0;\quad B_0^T ... ...rallel$}_{p(j)}^* \le R_j\ \ (i =1,...,m_0). \end{array}\right.$$

10. Двойственность для лексикографической задачи ЛП [42,47]

Двойственность в линейном программировании обладает двумя замечательными свойствами:

1⁰

Если L - задача линейного программирования, то двойственная задача $L^{\ast}$ также задача линейного программирования.

2⁰

$(L^{\ast})^{\ast} =L$ - свойство взаимности.

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

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

1)

формирование двойственной задачи давало также лексикографическую задачу;

2)

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

Один из реализованных подходов к его решению состоит в следующем.

Пусть

$$\max\nolimits_p\,\left\{ \left[ \begin{array}{c} (c_k,\,x)\\... ...rray}\right]\ \mbox{$\,\mid\,$}\ Ax \le b,\ \ x \ge 0 \right\}$$ (10.1)

- задача лексикографической оптимизации, где p - упорядочение функций $\{ (c_i,\,x) \}_0^k$ (или их индексов, что одно и то же) по ''важности''. Для определенности можно считать $p = (k,\,...\,,0)$, т.е. $(c_k,\,x)\succeq \ldots\succeq (c_0,\,x)$. Не приводя расшифровку смысла задачи $\max\nolimits_p \{ \ldots\}$ через лексикографическое упорядочение функций $\{ (c_i,\,x) \}_0^k$ скажем, что задачу (10.1) можно понимать как заключительную из задач:

$$\max\,\{ (c_k,\ x) \mbox{$\,\mid\,$} Ax\leq b,\ \ x\geq 0\},\eqno (10.2)_k\ \ \$$

$$\max\,\{(c_{k-1},\ x) \mbox{$\,\mid\,$} x\,\in\,\mathrm{Arg}\,(10.2)_k \},\eqno (10.2)_{k-1}$$

$${\makebox[9.7cm]{\,\dotfill\,}}$$

$$\framebox{\mbox{$\max\,\{ (c_0,\ x) \mbox{$\,\mid\,$} x\,\in\,\mathrm{Arg}\,(10.2)_1 \}$}.}\eqno (10.2)$$

Задачи (10.1) и (10.2) эквивалентны в смысле совпадения их оптимальных множеств. Это следует из смысла лексикографического оптимума.

Если вместо вектора b взять матрицу $[b_0,\ b_1,\,...\,,b_l]$ и положить $b = b_0 +\sum\limits_{j = 1}^l r_j b_j = b_0 + Br$, то задача (10.1) может быть переписана в следующем виде:

$$L_p:\ \max\nolimits_p \left\{ \left[ \begin{array}{c}C^T x\\... ...ht]\ \mbox{$\,\mid\,$}\ Ax \leq b_0 + Br,\ \ x \ge 0 \right\},$$ (10.3)

выше $B = [b_1,\,...\,,b_l]$, $r^T = [r_1,\,...\,,r_l] \ge 0$, $C = [c_1,\,...\,,c_k]$. Заметим, что повсюду, как и ранее, предполагается столбцовая запись вектора.

В качестве двойственного для (10.3) объекта можно естественным образом записать задачу:

$$L_q^{l}:\ \min\nolimits_q \left\{ \left[ \begin{array}{c}B^T... ...\ \mbox{$\,\mid\,$}\ A^T u \ge c_0 + C R,\ \ u \ge 0 \right\},$$ (10.4)

где q - упорядочение функций $\{ (b_j,\, u)\}_0^l$ (или их индексов, что одно и то же), $R^T = [R_1,\,...\,,R_k] \ge 0$. Для определенности можно считать $q = (l,\,...\,,0)$.

Симметрично скаляризовав (10.3) и (10.4) с помощью векторных параметров $R \ge 0$ и $r \ge 0$, соответственно, получим пару взаимно сопряженных (в классическом смысле) задач ЛП:

$$L:\ \max\,\{ (c,\,x) + (R,\,C^Tx) \mbox{$\,\mid\,$} Ax \le b_0 + Br,\ \ x \ge 0\},$$

$$L^{\ast}:\ \min\,\{ (b,\,u) + (r,\,B^Tu) \mbox{$\,\mid\,$} A^Tu \ge c_0 + CR,\ \ u \ge 0\}.$$

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

$$\begin{array}{rcc} L_p & \stackrel { \textstyle{\stackrel {{\... ...arrow } & L^{\ast}\,. \\ [18pt] & \mbox {Схема 3} & \end{array}$$

В ней символ $\stackrel {\textstyle{\stackrel {{\,\mathrm{Arg}}}{\sim}}}{\longrightarrow }$ означает переход к новой задаче с наследованием (сохранением) оптимального множества. Точная формулировка факта такова.

Теорема 10.1   Если задачи $\max\,\{ (c_i,\ x)\ \mbox{$\,\mid\,$}\ Ax \le b_j$, $x \ge 0 \}$ для всех $i =0,\,...\,,k$ и $j =0,\,...\,,l$ разрешимы, то существует непустая область конструктивно определяемых параметров $r \ge 0$ и $R \ge 0$ таких, что

$$\mathrm{Arg}\,L_p = \mathrm{Arg}\,L \ne \emptyset ,\qquad \mathrm{Arg}\,L_q^{(l)} = \mathrm{Arg}\,L^{\ast} \ne \emptyset .$$

Понятно, что $\mathrm{opt}\,L = \mathrm{opt}\,L^{\ast}$ (теорема двойственности в ЛП).

11. Двойственность для несобственных задач ЛП в лексикографической интерпретации [58]

Пусть P и $P^{\ast}$ - задача из п. 9. Важным является вопрос об аппроксимационном смысле задач P и $P^{\ast}$ по отношению к L и $L^{\ast}$. Ниже этот смысл будет раскрыт через термины лексикографической оптимизации.

Будем исходить (в содержательном плане) из того, что системы ограничений задач L и $L^{\ast}$ разбиты на подсистемы $A_j x \le b^j$ $(j =1,\,...\,,m_0)$ и $B^T u \ge c^i$ $(i =1,\,...\,,n_0)$, причем неравенства из одной подсистемы не ранжируются, а сами подсистемы ранжируются, например, в соответствии с такими упорядочениями: $p = (0,\,m_0,\,...\,,1)$ и $q = (0,\,n_0,\,...\,,1)$. Введенному упорядочению можно придать следующий смысл: ограничения $A_0 x \le b^0$, $x \ge 0$ и $B_0^T u \ge c^0$, $u\ge 0$ носят директивный характер и предполагаются совместными, остальные - факультативными (в целом же они могут быть несовместными). Однако в силу введенной упорядоченности подсистем их невязки $f_j(x) = \mbox{$\parallel$}(A_j x - b^j)^+ \mbox{$\parallel$}_{p(j)}$ $(j =1,\,...\,,m_0)$, $g_i(u) = \mbox{$\parallel$}(c^i - B_i^T u)^+ \mbox{$\parallel$}_{q(i)}^{\ast}$ $(i =1,\,...\,,n_0)$ должно минимизировать последовательным образом в соответствии с упорядочениями p и q. Как уже было отмечено в предыдущем пункте, это эквивалентно постановке следующих двух задач лексикографической оптимизации:

$$P_p(r):\ \max\nolimits_p \left\{ \left[ \begin{array}{c}-f_{m... ... \end{array}\right]\ \mbox{$\,\mid\,$}\ x \,\in\,M(r) \right\},$$

$$P_q^\char93 (R):\ \min\nolimits_q \left\{ \left[ \begin{array... ...ay}\right]\ \mbox{$\,\mid\,$}\ u \,\in\,M^\char93 (R) \right\},$$

где M(r) и M#(R) - допустимые множества задач P и P# соответственно. Предполагается, что функционалы $(c,\,x)$ и $(b,\,u)$ в упорядочениях p и q поставлены на последнее место.

Теорема 11.1   Пусть нормы $\{\mbox{$\parallel$}\cdot \mbox{$\parallel$}_{p(j)}\}$, $\{\mbox{$\parallel$}\cdot \mbox{$\parallel$}_{q(i)}\}$ - монотонны вместе со своими сопряженными и кусочно-линейны. Тогда существует непустая область конструктивно определяемых $r \ge 0$ и $R \ge 0$ таких, что

$$\mathrm{Arg}\,P = \mathrm{Arg}\,P_p(r) \ne \emptyset ,$$

$$\mathrm{Arg}\,P^\char93 = \mathrm{Arg}\,P_q^\char93 (R) \ne \emptyset ,$$

$$\mathrm{opt}\,P =\mathrm{opt}\,P^\char93 .$$

12. Двойственность для дизъюнктивных задач линейной оптимизации [52, 53, 63]

Дизъюнктивная задача МП - это задача поиска экстремума функции на объединении конечной системы множеств, каждое из которых задано некоторой системой неравенств:

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

где $M_j:=\ \{ x \mbox{$\,\mid\,$}F_j(x) \le 0 \}$, F_j: R$^n \to$R $^{m_{\scriptstyle j}}$. Такой задаче можно поставить в соответствие дизъюнктивную функцию Ланранжа

$$F(x,\,u) = f(x) -\min_{(j)}\,(u_j,\ F_j(x)),$$ (12.2)

с использованием которой можно связать построение двойственности для задач типа (12.1). Важным оправдательным моментом этого служит тот факт (достаточно простой), что если функция $F(x,\,u)$ обладает седлом $[\bar x,\,\bar u]$, то $\bar x \,\in\,$ $\mathrm{Arg}\,$(12.1). Если постановка задачи (12.1) линейная (или выпуклая), то можно формулировать теоремы двойственности в разных формах, например, в форме теоремы Куна-Таккера. Приведем пример. Пусть в (12.1): $f(x)=(c,\,x)$, $M_j =\{ x \ge 0 \mbox{$\,\mid\,$}A_j x \le b^j \}$. Обозначим эту задачу через $L_\cup$.

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

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

$$\bar{u}_j \,\in\,{\,\mathrm{Arg}} \min_{u_{\scriptstyle j} \in M_{\scriptstyle j}^*} (b^j,\,u_j),$$

где $M_j^* =\{ u_j \ge 0 \mbox{$\,\mid\,$}A_j^T u_j \ge c \}$. Подробное изложение двойственности для дизъюнктивных задач линейного программирования см. в статье [63], которая помещена в настоящей книге.

13. Игровой подход к формированию стандартной двойственности в нелинейном программировании

Указанный подход аналогичен тому, который был изложен в пунктах 3 и 4, в связи с этим ниже имеют место некоторые повторения.

Модель МП запишем в виде

$$C:\ \max\,\{f_0(x) \mbox{$\,\mid\,$}f_j(x) \le b_j,\ \ j =1,\,...\,,m,\ \ x\ge 0\},$$ (13.1)

где $x \in$Rⁿ. Этой постановке можно придать следующий экономический смысл (аналогичный тому, который был изложен в п. 1): $b^T = [b_1,\,...\,,b_m]$ - вектор ресурсов, перерабатываемых в вектор продукции $x^T = [x_1,\,...\,,x_n]$, $F^T (x) = [f_1(x),\,...\,,f_m(x)]$ - вектор затрат ресурсов, необходимых для обеспечения производства продукции уровня x, f₀(x) - доход от реализации этой продукции. На задачу C можно смотреть как на результат формализации Производства - I-го игрока с множеством стратегий $X = \{ x \ge 0 \}$. Роль II-го игрока приписывается Рынку с функциями поглощения продукции Производства по фиксированной функции дохода, купле излишних (для I-го игрока) ресурсов и продаже недостающих по ценам Рынка, формирующимся в результате рыночного взаимодействия Производства и Рынка на основе принципа гарантированного результата. В качестве платежной функции в описанной ситуации выступает функция Лагранжа

$$F (x,\,u) = f_0(x) -\sum_{j=1}^m u_j\, (f_j(x) -b_j),$$

поставленная в соответствие задаче C. Здесь {u_j}₁^m - неотрицательные множители Лагранжа, играющие роль цен на ресурсы. Принцип гарантированного результата формирует следующую схему:

$$\begin{array}{ccccc} & \fbox{ I }& \stackrel {\textstyle\lon... ...equiv:\! C^{\ast}.\\ [36pt] & & \mbox {Схема 4} & & \end{array}$$

В этой схеме зафиксировано то обстоятельство, что максиминная задача (I-го игрока) эквивалентна исходной задаче C, а минимаксная задача (II-го игрока) объявляется двойственной.

Если $\bar x \,\in\,X$, $\bar u \,\in\,U = \{ u \ge 0 \}$ и $\tilde v$ таковы, что $F(\bar x,\ \bar u) = \mbox{$\underline{v}$} = \bar v = \tilde v$, то $\bar x$ и $\bar u$ называются оптимальными стратегиями I-го и II-го игроков соответственно, а $\tilde v$ - ценой игры. В нашей экономической интерпретации: $\bar x$ - оптимальный план Производства, $\bar u$ - вектор оптимальных цен Рынка, $\mbox{$\underline{v}$} = \bar v$ - фактор равновесия Производства и Рынка ($\bar u$ - вектор равновесных цен).

Справедлива

Теорема 13.1 (Куна-Таккера)   Пусть C - разрешимая (в точке $\bar{x})$ задача выпуклого программирования, удовлетворяющая условию Слейтера $(\exists\,p\geq 0:\ f_j(p)<~\!b_j$, $\forall \,j)$. Тогда существует такой вектор $\bar{u}\geq 0$, что $[\bar{x},\ \bar{u}] \,\in\,\mathrm{Arg}\,C^*$.

14. Принцип линеаризации в формировании
двойственности для нелинейных задач МП [6]

В основе формирования $C^{\ast}$ на основе принципа линеаризации лежит следующая схема:

$$\framebox[7cm][c]{$ C \stackrel {(l)}{\longrightarrow } L_p ... ...(p = x)}{\longrightarrow } L_x^{\ast} \equiv :\ C^{\ast} $}\ .$$ (14.1)

Здесь $\stackrel {( l )}{\longrightarrow }$ означает линеаризацию всех функций, формирующих задачу C, в точке p (в результате получается задача ЛП: L_p), $\stackrel {(p = x)}{\longrightarrow }$ - это операция автоматической замены p на переменную x. Линеаризация в точке p произвольной дифференцируемой функции f(x) состоит в замене ее линейной функцией $l_p(x):=\ (\bigtriangledown f(p),\ x-p) +f(p)$.

Если следовать этой схеме (в предположении дифференцируемости функций {f_j(x)}₀^m), то задача C^* из схемы (14.1) примет вид:

$$\min\,\{ F(x,\,u) - (x,\,\bigtriangledown F (x,\,u))\ \mbox{$\,\mid\,$} \bigtriangledown _x F(x,\,u) \le 0,\ \ u \ge 0 \},$$

где $F(x,\,u) = f_0(x) -\sum\limits_{j = 1}^m u_j\, [f_j(x) -b_j]$. Если в ограничениях задачи C нет требования $x \ge 0$ (обозначим ее C₀), то $C_0^{\ast}$ будет иметь несколько иной вид:

$$\min\,\{F(x,\,u)\ \mbox{$\,\mid\,$}\ \bigtriangledown _x F(x,\,u) = 0,\ \ u \ge 0\}.$$ (14.2)

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

В предположении выпуклости задачи C теорема двойственности формулируется следующим образом:

Теорема 14.1   Если задача C₀ разрешима и удовлетворяет условию регулярности, то задача $C_0^{\ast}$ также разрешима и их оптимальные значения совпадают.

Задачи C и $C^{\ast}$ свойством взаимности не обладают, поэтому в этом случае имеет смысл формулировать и обратную теорему двойственности [6]:

Теорема 14.2   Если задача C₀ разрешима, пусть в точке $[\bar x,\ \bar u]$, и функция $F(x,\,\bar u)$ строго вогнута в некоторой окрестности точки $\bar x$, то $C_0^{\ast}$ разрешима, при этом $\bar x \,\in\, \mathrm{Arg}\,C_0$, $\mathrm{opt}\,C_0 = \mathrm{opt}\,C_0^{\ast}$ (т.е. совпадение оптимальных значений). Заметим, что условия оптимальности для задачи C₀ имеют вид соотношений:

$$f_j(x) \le b_j\quad (j =1,\,...\,,m),$$

$$\bigtriangledown _x F(x,\,u) = 0,\quad u \ge 0,\quad u_j\, (f_j(x) -b_j) = 0\quad (j =1,\,...\,,m)$$

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

З а м е ч а н и е 14.1. Рассмотренный выше принцип линеаризации может быть применен к анализу любой проблемы нелинейного программирования, формулируемой для того или иного подкласса задач оптимизации, в частности тех, которые были рассмотрены в [67]. Если речь идет о проблеме формирования двойственности, например, для несобственных задач нелинейного программирования, то это можно осуществить на основе соединения схем 2 и (14.1). Аналогичный подход можно реализовать и для других специальных задач нелинейного программирования, для которых в предположении линейности соответствующие вопросы уже нашли свое решение (например, вопрос о формировании двойственности для лексикографических задач). Разумеется, подход, основанный на применении принципа линеаризации, еще не порождает справедливости аналога той или иной теоремы для нелинейного случая, если эта теорема справедлива для случая линейного. Речь идет только об идентификации образа этой теоремы, ее формулировки.

15. Схема формирования двойственности для несобственных задач нелинейного программирования [23]

Приведенная схема на стр.  является соединением схем 2 и (14.1), о чем уже было сказано выше. Схема не требует особых пояснений, так как все необходимые разъяснения приведенных здесь символов имеются в предыдущих пунктах. Если в качестве исходной задачи взять

$$C:\ \sup\,\{ f_0(x) \mbox{$\,\mid\,$}f_j(x) \le 0\ \ (j =1,\,...\,,m),\ \ x\ge 0 \},$$

то в предположении дифференцируемости функций {f_j(x)}₀^m в полном соответствии со схемой 2 и ее последующей реализацией получаем:

$$P: \sup\,\{ f_0(x) -\sum_{j = 1}^{m_0} R_j\, \mbox{$\parallel... ...parallel$}_{p(j)}\ \mbox{$\,\mid\,$}\ F_0(x) \le 0,\ \ x \ge 0,$$

$$\mbox{$\parallel$}x^i \mbox{$\parallel$}_{q (i)} \le r_i\ \ (i =1,\,...\,,n_0) \},$$

$$P^\char93 : \inf\,\{ F(x,\,u) - (\bigtriangledown _x F(x,\,u)... ...i^T(x) u)^+ \mbox{$\parallel$}_{q(i)}^{\ast}\ \mbox{$\,\mid\,$}$$

$$B_0^T(x) u \ge c_x^0,\ \ u \ge 0,\ \ \mbox{$\parallel$}u^j \mbox{$\parallel$}_{p(j)}^* \le R_j (j=1,\,...\,,m_0)\}.$$

Здесь

$F(x,\ u):=\ f_0(x) -(u,\ F(x))$, $F^T(x):=\ [f_1(x),\ldots ,$ $f_m(x)] = [F_0(x),\,...\,,F_{m_0}(x)]$;

$$\bigtriangledown _x F(x) = \left[ \begin{array}{c} \frac{\tex... ...ial x_n} \end{array}\! \right]\! = [B_0(x),\,...\,,B_{n_0}(x)],$$

$c_x:=\ \bigtriangledown f_0(x) = \left[ \frac{\textstyle \partial f_0(x)}{\text... ...partial f_0 (x)}{\textstyle \partial x_n} \right]^T = [c_x^1,\,...\,,c_x^{n_0}]$.

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

16. Некоторые замечания к общей схеме формирования двойственности

Запишем задачу (13.1)

$$C:\ \max\,\{ f (x) \mbox{$\,\mid\,$}f_j (x) \le 0,\ \ j =1,\,...\,,m\},$$ (16.1)

не выделяя специально условие $x \ge 0$ (если в конкретной задаче таковое присутствует, то оно может быть учтено в общем списке ограничений в форме неравенств $-x_i \le 0$, $i=1,\,...\,,n$). Запишем двойственную к ней задачу

$$C^*:\ \min\,\{ F (x,\, u) \mbox{$\,\mid\,$}\bigtriangledown _x F(x,\, u) = 0,\ \ u \ge 0\}$$ (16.2)

(см. (14.2)). На формирование двойственности в силу отображения $C\, \stackrel {(*)}{\longrightarrow }\, C^*$ можно смотреть как на универсальную схему, распространяющуюся на оптимизационные задачи и из других разделов математики (математическая экономика, оптимальное управление, приближение функций и др.). Схема работает, естественно, и для задач ЛП. Проиллюстрируем это на задаче $L: \max\,\{ (c,\, x) \mbox{$\,\mid\,$}Ax \le b \}$. Запишем для нее функцию Лагранжа $L(x,\, u) = (c,\, x) - (u,\ Ax - b)$, $u\ge 0$. С помощью элементарных преобразований ее можно переписать в виде $L(x,\, u) = (b,\, u) - (A^T u -c,\ x)$. Тогда двойственная к L задача L^* по схеме (16.2) запишется так:

$$\min\,\{ (b,\, u) - (A^T u -c,\ x) \mbox{$\,\mid\,$}A^Tu -c = 0,\ \ u\ge 0 \},$$

что эквивалентно задаче

$$L^*:\ \min\,\{ (b,\, u) \mbox{$\,\mid\,$}A^T u = c,\ \ u \ge 0\},$$ (16.3)

что и требовалось.

Проиллюстрируем обсуждаемую схему еще одним весьма важным примером, а именно примером задачи, регуляризирующей (по Тихонову) задачу L :

$$L_{{\,\mathrm{reg}}}:\ \max\,\{ (c,\, x) -\mbox{$\alpha$}\, ... ...el$}^2 \mbox{$\,\mid\,$}Ax\le b \}, \qquad \mbox{$\alpha$}> 0.$$ (16.4)

Запишем для $L_{{\,\mathrm{reg}}}$ ее функцию Лагранжа

$$F(x,\, u) = (c,\, x) - \mbox{$\alpha$}\, \mbox{$\parallel$}x \mbox{$\parallel$}^2 - (u,\ Ax - b),\qquad u\ge 0$$

и ее градиент $\bigtriangledown _x F(x,\, u) = -A^T u +c - 2\,\mbox{$\alpha$}\, x$. Двойственная к  $L_{{\,\mathrm{reg}}}$ задача $(L_{{\,\mathrm{reg}}})^*$ запишется по правилу (16.2) в форме:

$$\min\,\{ (b,\, u) +(c -A^T u,\ x) -\mbox{$\alpha$}\, \mbox{$\... ...x{$\,\mid\,$} 2\, \mbox{$\alpha$}\, x = c -A^T u,\ \ u\ge 0 \},$$

или путем замены $x = 1 \,/\, 2\, \mbox{$\alpha$}\, (c -A^T u)$:

$$\min\,\{ (b,\, u) + \frac{1}{4\, \mbox{$\alpha$}}\, \mbox{$\... ...lel$}c-A^T u \mbox{$\parallel$}^2 \mbox{$\,\mid\,$}u \ge 0 \}.$$ (16.5)

Итак, в качестве двойственной к  $L_{{\,\mathrm{reg}}}$ мы получим задачу (16.5), обозначенную $(L_{{\,\mathrm{reg}}})^*$. Последняя является ничем иным как задачей, реализующей метод квадратичных штрафных функций, примененным к задаче (16.3) со штрафной константой $1 \,/\, 4\, \mbox{$\alpha$}$. Обозначим задачу (16.5) символом $(L^*)_{{\,\mathrm{pen}}}$. Нами показано

$$(L_{{\,\mathrm{reg}}})^* = (L^*)_{{\,\mathrm{pen}}}.$$ (16.6)

На самом деле реализуется схема:

$$\begin{array}{lcl} L & \stackrel {\scriptstyle (*)} {\stackre... ...^*)_{{\,\mathrm{pen}}}.\\ [18pt] & \mbox{Схема~6} & \end{array}$$

В нижней части этой схемы переход $\stackrel {(*)}{\longrightarrow }$ соответствует проверенному соотношению (16.6). Верен и обратный переход $\stackrel {(*)}{\longleftarrow }$, однако его обоснование требует специального подхода, базирующегося на искусственном преобразовании задачи (16.5). Это преобразование состоит в замене c-A^T u = w и перезаписи задачи в форме

$$\min\,\{ (b,\, u) +\frac{1}{4\, \mbox{$\alpha$}}\,\mbox{$\pa... ... \mbox{$\parallel$}^2 \mbox{$\,\mid\,$}w = A^T u -c, u\ge 0\}.$$ (16.7)

Функцией Лагранжа для этой задачи (с учетом в ней ограничения $u\ge 0$) будет

$$F(u, w;\ x, v) = (b,\, u) + \frac{1}{4\, \mbox{$\alpha$}} \, ... ...allel$}w \mbox{$\parallel$}^2 + (x,\ w - A^T u + c) - (v,\, u),$$

где x - вектор множителей Лагранжа, соответствующий векторному уравнению w = A^T u - c; $0\le v$ - аналогичный вектор для $u\ge 0$. Двойственной к (16.5) (следовательно, и к (16.7)) будет задача

$$\max\,\{ F(u, w;\ x, v) \mbox{$\,\mid\,$}\bigtriangledown _{[u, w]} F(u, w;\ x, v) = 0, v \ge 0 \}.$$ (16.8)

Вычисляем

$$\left. \begin{array}{l} \bigtriangledown _u F = b - Ax - v =... ...\Rightarrow \, w = -2\,\mbox{$\alpha$}\,x. \end{array}\right\}$$ (16.9)

С учетом (16.9) преобразуем функцию Лагранжа:

$$% latex2html id marker 4660 F \equiv (b -Ax -v,\ u) +\frac{1... ...(w,\ x) +(c,\ x) \,\stackrel {(\ref{n216169})}{\mbox{\Large =}}$$

$$% latex2html id marker 4662 \stackrel {(\ref{n216169})}{\mbo... ...x) -\mbox{$\alpha$}\, \mbox{$\parallel$}x \mbox{$\parallel$}^2.$$

Таким образом, применяя к (16.5) схему формирования двойственной задачи, мы получим задачу

$$\max\,\{ (c,\, x) -\mbox{$\alpha$}\, \mbox{$\parallel$}x \mbox{$\parallel$}^2 \mbox{$\,\mid\,$}b -Ax -v = 0,\ \ v\ge 0,$$

т.е.

$$\max\,\{ (c,\, x) - \mbox{$\alpha$}\, \mbox{$\parallel$}x \mbox{$\parallel$}^2 \mbox{$\,\mid\,$}Ax\le b \},$$

а это - задача  $L_{{\,\mathrm{reg}}}$. Следовательно, мы проверили соотношение

$$((L^*)_{{\,\mathrm{pen}}})^* \equiv L_{{\,\mathrm{reg}}}.$$ (16.10)

Наравне со схемой 6 можно выписать ей симметричную схему:

$$\begin{array}{lcl} L & \stackrel {\scriptstyle (*)} {\stackre... ...^*)_{{\,\mathrm{reg}}},\\ [18pt] & \mbox{Схема~7} & \end{array}$$

в соответствии с которой справедливо соотношение

$$((L^*)_{{\,\mathrm{reg}}})^* \equiv L_{{\,\mathrm{pen}}}.$$ (16.11)

Задачи $L_{{\,\mathrm{reg}}}$ и $(L^*)_{{\,\mathrm{pen}}}$ связаны между собой классической теоремой двойственности (вытекает из обоснования схемы 6 и теоремы 13.1).

Теорема 16.1   Задачи $L_{{\,\mathrm{reg}}}$ и $(L^*)_{{\,\mathrm{pen}}}$ одновременно разрешимы или неразрешимы, при этом в случае разрешимости $\mathrm{opt}\,L_{{\,\mathrm{reg}}} = \mathrm{opt}\,(L^*)_ {{\,\mathrm{pen}}}$.

П р и м е ч а н и е. Естественно, это утверждение верно и для пары задач $L_{{\,\mathrm{pen}}}$, $(L^*)_{{\,\mathrm{reg}}}$.

Выпишем тройку задач:

$$L:\ \max\,\{ (c,\, x) \mbox{$\,\mid\,$}Ax \le b \},$$

$$L_{{\,\mathrm{pen}}}:\ \max\,\{ (c,\, x) - \frac{1}{4\, \mbox{$\alpha$}}\, \mbox{$\parallel$}(Ax-b)^+ \mbox{$\parallel$}^2 \},$$

$$(L^*)_{{\,\mathrm{reg}}}:\ \min\,\{ (b,\, u) + \mbox{$\alpha$... ...mbox{$\parallel$}^2 \mbox{$\,\mid\,$} A^T u = c,\ \ u \ge 0 \}.$$

Отметим связи между ними (при разрешимости L):

1)

$\mathrm{opt}\,L_{{\,\mathrm{pen}}} = \mathrm{opt}\, (L^*)_{{\,\mathrm{reg}}}$ (теорема двойственности);

2)

$0 \le \mathrm{opt}\, L_{{\,\mathrm{pen}}} - \mathrm{opt}\, L \le \mbox{$\alpha$}\, \mbox{$\parallel$}\bar u \mbox{$\parallel$}^2$, $\bar u \,\in\,\mathrm{Arg}\;L^*$;

3)

при достаточно малом $\mbox{$\alpha$}> 0$ оптимальный вектор $\bar u$ задачи $(L^*)_{{\,\mathrm{reg}}}$ является минимальным по норме оптимальным вектором задачи L^*.

Следствие. Пусть L разрешима. Тогда при достаточно малом $\mbox{$\alpha$}> 0:\ \ \mathrm{opt}\, L_{{\,\mathrm{pen}}} - \mathrm{opt}\, L = \mbox{$\alpha$}\, \mbox{$\parallel$}\bar u \mbox{$\parallel$}$.

Заметим, что для задачи L в качестве $L_{{\,\mathrm{pen}}}$ чаще записывают задачу: $\max\,\{ (c,\, x) -\sum\limits_{j=1}^m R_j l_j^{+^2}(x) \}$, где l_j(x) - левые части системы $Ax-b \le 0$, R_j > 0, $j=1,\,...\,,m$. В этом случае оценка 2) и соотношение из следствия принимают вид:

$$0 \le \mathrm{opt}\, L_{{\,\mathrm{pen}}} - \mathrm{opt}\, L \le \sum_{j=1}^m \frac{\bar{u}_j^2}{4\, R_j}$$

и

$$\mathrm{opt}\, L_{{\,\mathrm{pen}}} -\mathrm{opt}\, L = \sum_{j=1}^m \frac{\bar{u}_j^2}{4\, R_j}$$

- при достаточно большом $R:=\ \min\limits_{(j)}\,R_j$.

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

ЛИТЕРАТУРА

1. Wolfe P. A Duality Theorem for Nonlinear Programming. Quarterly of Applied Mathematics, 1961, 19, pp. 239-244.
2. Mangasarian O.L. Duality in Nonlinear Programming. Quarterly of Applied Mathematics, 1962, 20, pp. 300-302.
3. Charnes A., Cooper W.W., Kortanek K.O. A Duality Theory for Convex Programs with Convex Constraints. Bull. American Mathematical Society, 1962, 68, pp. 605-608.
4. Mangasarian O.L., Ponstein J. Minimax and Duality in Nonlinear Programming. J. Mathematical Analysis and Applications, 1965, 11, pp. 504-518.
5. Kuhn H.W. Duality in Mathematical Programming. Mathematical Systems Theory and Economics (Lecture Notes in Operations Research and Mathematical Economics,  11), 1969, New York: Springer-Verlag, pp. 67-91.
6. Mangasarian O.L. Optimality and Duality in Nonlinear Programming. In Proceedings of Princeton Simposium on Mathematical Programming (Ed. Kuhn H.W.), 1970, pp. 429-443.
7. Bazaraa M.S. Geometry and Resolution of Duality Gaps. Naval Research Logistics Quarterly, 1973, 20, pp. 357-365.
8. Гольштейн Е.Г. Теория двойственности в математическом программировании и ее приложения. М.: Наука, 1971, 352 с.
9. Астафьев Н.Н. Линейные неравенства и выпуклость. М.: Наука, 1982, 152 с.
10. Evers J.J.&H. van Maaren. Duality Principes in Mathematics and Their Relations to Conjugate Functions. Nieuw arohiff voor wiskunde (4), 1985, v. 3.
11. Еремин И.И. О методе штрафов в выпуклом программировании. Кибернетика, 1967,  4, 4 c.
12. Еремин И.И. Метод штрафов в выпуклом программировании. ДАН СССР, 1967,  4, 4 c.
13. Еремин И.И., Астафьев Н.Н. Двойственность в выпуклом программировании. Книга ''Методы управления большими системами'', 1970,  1, 25 c.
14. Еремин И.И. О задачах последовательного программирования. Сибирский матем. журнал, 1973, т. 14,  1, 10 c.
15. Еремин И.И., Астафьев Н.Н. Введение в теорию линейного и выпуклого программирования. М.: изд-во физ.-мат. литературы, 1976, 192 c.
16. Еремин И.И., Мазуров Вл.Д. Нестационарные процессы математического программирования. М.: Наука, 1979, 288 c.
17. Еремин И.И. Двойственность для несобственных задач линейного и выпуклого программирования. ДАН СССР, 1981, т. 256,  2, 5 c.
18. Eremin I.I. Duale uneigentliche lineare und Konvexe Optimierungeprobleme. Math. Operationsforsch. Statist., Ser. Optimization, 1982, v. 13,  2, 12 p.
19. Еремин И.И. Двойственность для несобственных задач линейного программирования. Сб. ''Несобственные задачи оптимизации''. Свердловск: УНЦ АН СССР, 1982, 8 c.
20. Еремин И.И. Двойственность для несобственных задач линейного программирования. Матем. заметки, 1982, т. 32, вып. 2, 11 c.
21. Еремин И.И. О двойственности для несобственных задач линейного и выпуклого программирования. Труды 27 Междунар. научного коллоквиума. Берлин, Высшая техническая школа Ильменау, 1982, тетрадь 5, 3 c.
22. Еремин И.И. Двойственность для несобственных задач линейного и выпуклого программирования и методы их коррекции. Изв. АН СССР. Техн. кибернетика, I, 1983, 12 c.
23. Еремин И.И., Мазуров Вл.Д., Астафьев Н.Н. Несобственные задачи линейного и выпуклого программирования. М.: Наука, 1983, 336 c.
24. Еремин И.И. Двойственность для несобственных задач квадратичного программирования. Тезисы докладов конф. ''Методы математического программирования и их программное обеспечение''. Свердловск: УНЦ АН СССР, 1984, 2 c.
25. Еремин И.И., Ватолин А.А. Двойственность для несобственных бесконечномерных задач линейного и выпуклого программироания. Сб. ''Методы аппроксимации несобственных задач математического программироания''. Свердловск: УНЦ АН СССР, 1984, 17 c.
26. Еремин И.И., Ватолин А.А. Двойственность для несобственных задач математического программирования в условиях информационной неопределенности. Тезисы докладов Междунар. конф. ''Стохастическая оптимизация'' (часть I). Киев, 1984, 1 c.
27. Еремин И.И. Вопросы двойственности для несобственных задач математического программирования. Алгебра и логика. Новосибирск, 1984, т. 23,  6, c. 624-635.
28. Еремин И.И. Несобственные задачи квадратичного программирования и вопросы регуляризации. Сб. ''Параметрическая оптимизация и методы аппроксимации несобственных задач математического программирования''. Свердловск: УНЦ АН СССР, 1985, c. 47-50.
29. Eremin I.I. Parametrization methods in the analysis of improper mathematical programming problems. Abstracts International Conference ''Parametric Optimization and Related Topics''. Plane / Thüringen, GDR, 1985, pp. 10-11.
30. Еремин И.И., Ватолин А.А. Двойственность для несобственных задач математического программирования. Свердловск: УНЦ АН СССР, 1985, 50 c.
31. Еремин И.И. Противоречивые модели экономики. Свердловск: Средне-Уральское книж. изд-во, 1986, 96 c.
32. Eremin I.I. Duality and the correcting methods for ill-posed of linear and convex programming. Seminarber., Humboldt-Univ. Berlin. Sekt. Math. 81, 1986, pp. 27-45.
33. Eremin I.I., Vatolin A.A. Duality in improper mathematical programming problems under uncertainty. Stochastic optimization. Prac. Int. Conf. Kiev / USSR, 1984. Lect. Notes Control Inf. Sci. 81, 1986, pp. 326-333.
34. Еремин И.И. О двойственности в линейной векторной оптимизации. Тезисы докладов конф. ''Методы математического программирования и программное обеспечение''. Свердловск: УНЦ АН СССР, 1987, c. 41-42.
35. Eremin I.I. Methods of Parametrization in the Analysis of Improper Mathematical Programming Problems. Parametric Optimization and Related Topics. Akademie-Verlag Berlin, 1987, pp. 82-94.
36. Еремин И.И. Вопросы двойственности для несобственных задач многокритериальной линейной оптимизации. Сб. ''Исследования по несобственным задачам оптимизации''. Свердловск: УрО АН СССР, 1988, c. 27-33.
37. Еремин И.И. Симметрическая двойственность в линейной векторной оптимизации. Тезисы докладов Междунар. конф. ''Многокритериальные задачи математического программирования''. Киев, 1988, c. 6-7.
38. Еремин И.И. Двойственность для противоречивых задач оптимальной линейной дискриминации. Тезисы докладов конф. ''Численные методы и оптимизация''. Таллинн, 1988, c. 81-87.
39. Еремин И.И. Общая схема формирования двойственности для несобственных задач математического программирования. Кибернетика, 1989,  5, c. 79-82.
40. Eremin I.I., Vatolin A.A. Improper Mathematical Programming Problems. Problems of Control and Information Theory, 1989, v. 18(6), pp. 359-380.
41. Еремин И.И. Симметричная двойственность для лексикографической постановки задачи линейного программирования. Тезисы докладов конф. ''Математическое программирование и приложения''. Свердловск: УрО АН СССР, 1991, c. 58-59.
42. Еремин И.И. Симметричная двойственность для задач последовательного линейного программирования. ДАН СССР, 1991, т. 317,  5, c. 1045-1048.
43. Eremin I.I. Lexicographic duality in linear optimization. Proceedings of International Workshop on Computationally-intensive Methods in Simulation and Optimization. Wien, 1991, pp. 8-11.
44. Еремин И.И., Ватолин А.А., Попов Л.Д., Третьяков Н.В. Несобственные задачи математического программирования. Математические методы в экономико-математическом моделировании. М.: Наука, 1991.
45. Еремин И.И. Двойственность в математическом программировании. Информ. бюлл. АМП. Екатеринбург: УрО РАН, 1992,  3, c. 11-30.
46. Еремин И.И. Симметрическая двойственность для лексикографических задач линейного программирования. Украинский матем. журнал, 1992, т. 44,  6, c. 766-773.
47. Еремин И.И. Лексикографическая двойственность для несобственных задач линейного и квадратичного программирования. Труды ИММ УрО РАН. Екатеринбург: УрО РАН, 1992, т. I, c. 178-192.
48. Еремин И.И., Жан-Гериев А.А. Двойственность для полупаретовской постановки задачи линейного программирования. Информ. бюлл. АМП. Екатеринбург: УрО РАН, 1993,  4, c. 46.
49. Еремин И.И. Лексикографическая двойственность в математическом программировании. Тезисы докладов Междунар. семинара ''Негладкие и разрывные задачи управления и оптимизации''. Челябинск, 1993, c. 54-55.
50. Еремин И.И. Двойственность для парето-лексикографических задач линейной оптимизации. Известия ВУЗов. Математика. Казань: изд-во ФОРТ ДИАЛОГ, 1993,  12(379), c. 3-10.
51. Eremin I.I. Duality for Pareto-Lexicographic Problems of Linear Optimization. Pattern Recognition and Image Analysis, 1993, v. 3,  4, pp. 482-487.
52. Еремин И.И. Парето-последовательная задача линейной оптимизации и двойственность. Доклады РАН, 1994, т. 334,  4, c. 141-143.
53. Eremin I.I. Summetric Duality in Lexicographic Problems of Linear Optimization. Yugoslav Journal of Operations Research. Belgrade: University of Belgrade, 1995, v. 5,  2, pp. 165-172.
54. Еремин И.И. Двойственность для задач дискриминации и таксономии систем линейных неравенств. Pattern Recognition and Image Analysis, 1995,  3, c. 233-236.
55. Еремин И.И. Двойственность для Парето-последовательных задач линейного программирования. Труды ИММ УрО РАН. Екатеринбург: УрО РАН, 1995, т. III, c. 245-261.
56. Еремин И.И. Двойственность для Парето-последовательных задач линейного программирования. Управление. Оптимизация. Интеллект. Иркутск: СЭИ СО РАН, 1995,  1, c. 3-19.
57. Еремин И.И. Двойственность в несобственном программировании. Кибернетика и системный анализ, 1996,  6, 13 c.
58. Еремин И.И. Двойственность для несобственных задач паретовской и лексикографической линейной оптимизации. Труды ИММ УрО РАН. Екатеринбург: УрО РАН, 1996, т. IV, c. 322-336.
59. Еремин И.И. Двойственность для несобственных задач линейной оптимизации. Информ. бюлл. АМП. Екатеринбург: УрО РАН, 1996,  6, c. 32-37.
60. Еремин И.И. Двойственность для кусочно-линейных задач оптимизации. Информ. бюлл. АМП. Екатеринбург: УрО РАН, 1997,  7, c. 88-89.
61. Eremin I.I. About some problems of disjunctive programming. Yugoslav Journal of Operations Research. Belgrade: University of Belgrade, 1998, v. 8,  1, pp. 25-43.
62. Еремин И.И. Сигма-кусочные функции и задачи дизъюнктивного программирования. Доклады РАН, 1998, т. 358,  5, c. 538-540.
63. Еремин И.И. Сигма-кусочные функции и задачи дизъюнктивного программирования. Труды ИММ УрО РАН. Екатеринбург: УрО РАН, 1998, т. V, c. 357-380.
64. Еремин И.И. Теоремы о седловой точке дизъюнктивной функции Лагранжа. Алгоритмический анализ некорректных задач. Тезисы докл. конф., 1998 г. Екатеринбург: УрГУ, 1998, c. 85-86.
65. Еремин И.И. О квадратичных и полноквадратичных задачах выпуклого программирования. Известия ВУЗов. Математика. Казань: изд-во ФОРТ ДИАЛОГ, 1998,  12, c. 22-28.
66. Еремин И.И. Двойственность для задач квадратичного программирования в гильбертовом пространстве. Информ. бюлл. АМП. Екатеринбург: УрО РАН, 1999,  8, c. 99-102.
67. Еремин И.И. Теория линейной оптимизации. Екатеринбург: Изд-во ''Екатеринбург'', 1999, 312 c.

Список научных трудов Еремина И.И.
e-mail: Еремин И.И.