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

Двойственная задача линейного программирования.
Рассмотрим задачу ЛП
(1)
или, в матричной записи,
(2)
Задачей, двойственной к (1) (двойственной задачей), называется задача ЛП от переменных вида
(3)
или, в матричной записи,
(4)
где .
Правила построения задачи (3) по форме записи задачи (1) таковы: в задаче (3)

переменных столько же, сколько строк в матрице задачи (1). Матрица ограничений в (3) — транспортированная матрица . Вектор правой части ограничений в (3) служит вектором коэффициентов максимизируемой линейной форме в (1), при этом знаки неравенств меняются на равенство. Наоборот, в качестве целевой функции в (3) выступает линейная форма, коэффициентами которой задаются вектором правой части ограничений задачи (1), при этом максимизация меняется на минимизацию. На двойственные переменные накладывается условие неотрицательности. Задача (1), в отличии от двойственной задачи (3) называется прямой.
Теорема двойственности. Если взаимодвойственные задачи (2), (4) допустимы, то они обе имеют решение и одинаковое значение.