ДВОЙСТВЕННОСТИ ТЕОРИЯ в программировании линейном

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

где все — заданные числа, а все переменные этих задач, наз. двойственной (сопряженной) парой; каждая из задач наз. двойственной по отношению к другой. Свойство двойственной пары задач выражено в теоремах двойственности.

Первая теорема. Если оптим. план 1-й (2-й) задачи существует, то существует оптим. план другой из этих задач, при этом для произвольной пары допустимых планов этих задач выполняется неравенство которое переходит в равенство, когда X и U являются оптим. планами соответствующих

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

Вторая теорема. Если X — оптим. план 1-й задачи, a U - оптим. план 2-й задачи, то компоненты этих планов связаны соотношениями

Наоборот, если соотношения (1) и (2) выполняются для пары опорных планов X, U, то эти планы оптимальны. Соотношения (1) и (2) служат критерием оптимальности текущего плана в большинстве методов решения задачи линейного программирования. Пусть X — опорный план 1-й задачи. Подставив его компоненты в ф-лы (1) и (2), вычислим вектор U. Если U — план 2-й задачи, из сказанного выше следует оптимальность пары X, V.

Переменные 2-й (1-й) задачи можно рассматривать как множители Лагранжа для 1-й (2-й) задачи.

Пусть - функцвя Лагранжа:

Тогда планы X и U являются соответственно оптим. планами 1-й и 2-й задачи в том и только в том случае, если (X, U является седловой точкой ф-ции при ограничениях Если одна из задач двойственной пары представлена в общем виде, то пара двойственных задач записывается так:

Все перечисленные выше свойства 1-й и 2-й задачи сохраняются и для 3-й и 4-й задач. Соотношения (1) и (2) для задачи переписываются в виде

Теоремы двойственности лежат в основе построения и обоснования основных численных построений методов линейного программирования. Они в большой мере обобщены на случай программирования выпуклого и на бесконечномерный случай. Д. т. в линейном программировании тесно связана с игр теорией. Рассмотрение пары двойственных задач линейного программирования особенно характерно для эконом, исследований. В частности, если 1-я задача является задачей максимизации производства однородного продукта при ограничениях на к-во ресурсов, то оптим. план 2-й задачи дает оценку стоимостей единиц ресурсов. Эти оценки играют большую роль в теории ценообразования.

Лит. см. к ст. Программирование линейное.

Н. 3. Шор, В. А. Трубин.