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

Каждой задаче ЛП соответствует некоторая другая задача, которую называют двойственной (сопряженной) к исходной.

Предположим, что исходная задача представлена в стандартной форме:

(1.8)

Задачей ЛП, двойственной к задаче (8), называется задача, представленная в виде:

(1.9)

Обратно, если рассматривается задача (1.9), то задача (1.8) называется двойственной к (1.9).

Отметим основные соотношения между двойственными задачами:

количество переменных в двойственной задаче равно количеству основных ограничений неравенств;

коэффициенты целевой функции одной из задач являются свободными членами в ограничениях двойственной задачи ;

если первая задача (1.8) является задачей на максимум целевой функции, то задача (1.9) - задачей на минимум целевой функции;

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

знаки в основных ограничениях-неравенствах меняются на противоположные.

Пример 1.7. Записать задачу, двойственную к задаче:

Решение. Прежде всего, приведем исходную задачу к стандартному виду (1.8). Для этого умножим обе части второго неравенства на (-1). Получим новую систему ограничений:

Данная система содержит два основных ограничения-неравенства. Поставим им в соответствие переменные y₁ и y₂. Запишем целевую функцию двойственной задачи; используя в качестве ее коэффициентов свободные члены 8 и -6:

Матрица коэффициентов перед переменными в левых частях основных ограничений имеет вид:

Транспонируя матрицу А, запишем ограничения-неравенства двойственной задачи:

(1.11)

Свободные члены ограничений-неравенств соответствуют коэффициентам целевой функции L.

Пара двойственных задач связана определенными соотношениями, составляющими предмет теории двойственности.