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

Двойственная задача для заданной задачи линейного программирования (ЛП, англ. Linear programming, LP) — это другая задача линейного программирования, которая получается из исходной (прямой) задачи следующим образом: * Каждая переменная в прямой задаче становится ограничением двойственной задачи; * Каждое ограничение в прямой задаче становится переменной в двойственной задаче; * Направление цели обращается – максимум в прямой задаче становится минимумом в двойственной, и наоборот. Теорема о слабой двойственности утверждает, что значение двойственной задачи для любого допустимого решения всегда ограничено значением прямой задачи для любого допустимого решения (верхняя или нижняя граница, в зависимости от того, это задача максимизации или минимизации). Теорема о сильной двойственности утверждает, что более того, если прямая задача имеет оптимальное решение, то двойственная задача имеет также оптимальное решение, и эти два оптимума равны. Эти теоремы принадлежат более широкому классу теорем двойственности в оптимизации. Теорема о сильной двойственности является одним из случаев, в котором разрыв двойственности (разрыв между оптимумом прямой задачи и оптимумом двойственной) равен 0. О геометрическом смысле двойственной задачи можно почитать в книге Юдина и Гольштейна. Там же можно прочитать об экономическом смысле задачи.