Леммы и теоремы двойственности

Лемма 1. Пусть - допустимое множество исходной задачи и - допустимое множество двойственной задачи. Тогда для всех и выполнено:

.

Доказательство: Так как , а , то необходимо доказать, что для всех и .

Будем доказывать утверждение для канонической формы задачи.

Имеем

.

Обе части неравенства умножим на и получим

.

С другой стороны из двойственной задачи имеем

. (3.2.1)

Обе части неравенства справа умножаем на . Получаем

. (3.2.2)

Из (3.2.1) и (3.2.2) следует

,

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

Лемма 2. Если одна из задач двойственной пары неразрешима из-за неограниченности целевой функции, то другая несовместна.

Доказательство: Пусть неразрешима исходная задача, покажем, что двойственная несовместна.

Это означает, что .

Предположим противное. Пусть , тогда существует . Из леммы 1 следует, что для любого

,

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

Лемма 3. Если и , то обе задачи разрешимы.

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

Лемма 4. Пусть и таковы, что

,

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

Доказательство: Из леммы 1 следует, что для всех

,

то есть - оптимальное решение исходной задачи. Аналогично доказывается оптимальность . (Доказать самостоятельно.)

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

,

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

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

Кроме того имеются оценки

, (3.2.3)

где - вид столбца на последней итерации симплекс-метода.

Представим матрицу А в виде

, (3.2.4)

где В – базисные столбцы матрицы А и D – небазисные столбцы и подставим вектор в систему уравнений. Получим

.

Так как В – квадратная невырожденная матрица, то умножим обе части уравнения на . Получим

или

.

Так как на последней итерации симплекс-метода базисные столбцы являются единичными, то отсюда следует, что

, (3.2.5)

а

. (3.2.6)

Подставим (3.2.5) в (3.2.3), получим

для

и

для .

Обозначим через

. (3.2.7)

Получим

, (3.2.8)

и

, . (3.2.9)

В неравенствах (3.2.8), (3.2.9) перенесем вправо. Получим

, ,

,

И с учетом (3.2.4) имеем

,

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

Тогда по лемме 3 двойственная задача также разрешима.

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

.

Так как , то по лемме 4 - оптимальное решение.

Симплекс-метод с точки зрения теории двойственности.

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

Заметим, что при этом на любой итерации, если х – базисные решения исходной задачи, а y – псевдорешения двойственной задачи, то . Таким образом можно сделать вывод о том, что при решении ЗЛП симплекс-методом в исходном решении происходит движение по допустимым точкам к оптимальной, а в двойственной движение происходит по псевдо решениям и первое полученное допустимое решение будет являться оптимальным.

Вторая теорема двойственности. Пусть и . Для того чтобы и были оптимальными решениями исходной и двойственной задач соответственно, необходимо и достаточно выполнение следующих условий:

, (3.2.10)

. (3.2.11)

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

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

Необходимость. Пусть и - оптимальные решения исходной и двойственной задач соответственно.

Это значит, что

, (3.2.12)

,

, (3.2.13)

,

,

. (3.2.14)

Умножим обе части неравенства (3.2.12) слева на , а неравенство (3.2.13) справа на .

Получим

,

,

откуда следует с учетом (3.2.14)

,

то есть

или

,

.

А также

,

откуда

.

Необходимость доказана.

Достаточность. Пусть для и выполняются условия (3.2.10) и (3.2.11). Тогда

и

,

то есть

,

.

Из четвертой леммы 4 следует, что и - оптимальные решения, что и требовалось доказать.

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

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

Доказательство. Выпишем векторные равенства (3.2.8), (3.2.9) в виде сумм. Получим

, (3.2.15)

. (3.2.16)

Так как и , то каждое слагаемое суммы (3.2.14) – неотрицательно и так как сумма равна нулю, то и каждое слагаемое равно нулю, то есть для всех i

.

Откуда следует, что если , то .

Аналогично в равенстве (3.2.16) для всех j

(доказать самостоятельно), то есть если , то

.

Следствие доказано.

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

Алгоритм решения двойственной задачи

Шаг 1. Выписыввется двойственная задача (см. Алгоритм построения двойственнй задачи).

Шаг 2. Просматриваются пременные исходной задачи.

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

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

Шаг 4. Решается полученная система линейных уравнений, относительно двойственных переменных . Решение этой системы естб оптимальное решение двойственной задачи.

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

Замечание. Может оказаться, что в оптимальной точке исходной задачипеременных не две, а три прямые. Тогда система уравнений для решения двойственной задачи будет иметь переменных больше, чем ограничений. Это означает, что двойственная задача имеет неединственное решение.

Пример 3.2.1. Дана ЗЛП и ее оптимальное решение

, (3.2.17)

, (3.2.18)

, (3.2.19)

,

,

.

Требуется записать двойственную задачу и найти ее решение.

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

	,
	,
	.

Двойственная задача

	,

,

.

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

и , следовательно, оба ограничения двойственной задачи записываются как строгие равенства

,

.

Подставим поочередно в каждое из неравенств исходной задачи

,

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

.

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

То есть

.

Вычислим значение целевой функции

,

из чего следует

.