Шпаргалка по "Логистике"

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

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

или, в матричной записи

Задачей, двойственной к (5) (двойственной задачей), называется задача ЛП от переменных вида

или, в матричной записи,

где .

Правила построения задачи (7) по форме записи задачи (5) таковы: в задаче (7) переменных столько же, сколько строк в матрице задачи (5). Матрица ограничений в (7) – транспортированная матрица . Вектор правой части ограничений в (7) служит вектором коэффициентов максимизируемой линейной форме в (5), при этом знаки неравенств меняются на равенство. Наоборот, в качестве целевой функции в (7) выступает линейная форма, коэффициентами которой задаются вектором правой части ограничений задачи (5), при этом максимизация меняется на минимизацию. На двойственные переменные накладывается условие неотрицательности. Задача (5), в отличии от двойственной задачи (7) называется прямой.

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

Теорема двойственности. Если взаимодвойственные задачи (6) и (8) допустимы, то они обе имеют решение и одинаковое значение.