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

Теория двойственности в линейном программировании строится на следующих основных теоремах.

Теорема 1. Если задача линейного программирования имеет конечный оптимум, то двойственная к ней также имеет конечный оптимум, и оптимальные значения линейных форм обеих задач совпадают, то есть F_max = Z_min или F_min  = Z_max .

Если линейная форма одной из двойственных задач не ограничена, то условия другой задачи противоречивы.

Прежде чем сформулировать теорему 2, установим соответствия между переменными исходной и двойственной задач.

При решении симплексным методом исходной задачи для обращения системы неравенств в эквивалентную ей систему уравнений должны быть введены m добавочных неотрицательных переменных (по числу неравенств в системе ограничений): х_n+1, х_n+2,..., х_n+i,..., х_n+m, где i=1, 2,..., m означает номер неравенства, в которое была введена добавочная переменная х_n+i.

Система ограничений двойственной задачи состоит из n неравенств, в которых имеются m переменных. При решении этой задачи симплексным методом необходимо ввести n добавочных неотрицательных переменных: у_m+1, y_m+2,..., у_m+j,..., y_m+n , где j = 1, 2,..., n означает номер неравенства системы ограничений двойственной задачи, в которое была введена добавочная переменная у_m+j.

Установим следующее соответствие между переменными исходной и двойственной задачи:

x1   x2 ... x j... xn                   ym+1  ym+2 ... ym+j... ym+n

xn+1 xn+2... xn+i... xn+m                     y1      y2 ... yi  ... ym

Иными словами, каждой первоначальной переменной исходной задачи x_j (j = 1, 2,..., n) ставится в соответствие добавочная переменная у_m+j, введенная в j-е неравенство двойственной задачи, а каждой добавочной переменной x_n+i исходной задачи (i = 1, 2,..., m), введенной в i-е неравенство исходной задачи, ставится в соответствие первоначальная переменная y_i  двойственной задачи.

Теорема 2. Компоненты оптимального решения задачи линейного программирования равны абсолютным величинам коэффициентов при соответствующих переменных в выражении линейной формы двойственной ей задачи при достижении ею оптимума.

Замечание. Если в одной из задач (прямой или двойственной) нарушается единственность оптимального решения, то оптимальное решение другой задачи будет вырожденным.

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

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

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

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

(5.2.)

y_i = .                        (2.15)

Эта теорема показывает еще одну связь между переменными прямой и двойственной задач. Поясним это подробнее.

Пусть (х₁, х₂,..., х_j,..., x_n ) - оптимальное решение прямой задачи, а (у₁, у₂,..., у_i,..., у_m) - оптимальное решение двойственной задачи. Оптимальные значения целевых функций F и Z достигаются при подстановке компонент оптимального решения в их первоначальные выражения, т. е.:

F_max = c₁x₁ +... + c_jx_j +... + c_nx_n,

Z_min = b₁y₁ +... + b_iy_i +... + b_my_m.

На основании первой теоремы двойственности (F_max = Z_min) можно записать

c₁x₁ +... + c_jx_j +... + c_nx_n = b₁y₁ +... + b_iy_i +... + b_my_m.

Отсюда следует, что

F_max = b₁у₁ +... + b_iу_i +... + b_mу_m.

Поставим вопрос, как изменится величина F_max, если в исходной задаче увеличить свободный член b_i, в i-м ограничении-неравенстве на величину
Db_i (i = 1,2,..., m). Величина F_max, рассматриваемая теперь как функция переменных b₁,..., b_i,..., b_m, получит приращение DF_max. Частные производные этой функции по любому из этих аргументов имеют вид

 = y_i,

т.е. мы пришли к формуле (2.16). Учитывая, что функция F_max  линейная, получим

(5.3)

DF_max = y_iDb_{i .}                                                                   (2.16)