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

Основные теоремы  двойственности и их экономическое  содержание     

Теорема. Для любых допустимых планов   и  прямой и двойственной ЗЛП справедливо неравенство  , т.е.  
                                    (2.29)  
     – основное неравенство теории двойственности. 
     Теорема (критерий оптимальности Канторовича). 
     Если для некоторых допустимых планов   и   пары двойственных задач выполняется неравенство  , то   и   являются оптимальными планами соответствующих задач. 
     Теорема (малая теорема двойственности). 
     Для существования оптимального плана любой из пары двойственных задач необходимо и достаточно существование допустимого плана для каждой из них. 
     Теорема. Если одна из двойственных задач имеет оптимальное решение, то и другая имеет оптимальное решение, причем экстремальные значения целевых функций равны:  . Если одна из двойственных задач неразрешима вследствие неограниченности целевой функции на множестве допустимых решений, то система ограничений другой задачи противоречива. 
     Экономическое содержание первой теоремы двойственности состоит в следующем: если задача определения оптимального плана, максимизирующего выпуск продукции, разрешима, то разрешима и задача определения оценок ресурсов. Причем цена продукции, полученной при реализации оптимального плана, совпадает с суммарной оценкой ресурсов. Совпадение значений целевых функций для соответствующих планов пары двойственных задач достаточно для того, чтобы эти планы были оптимальными. Это значит, что план производства и вектор оценок ресурсов являются оптимальными тогда и только тогда, когда цена произведенной продукции и суммарная оценка ресурсов совпадают. Оценки выступают как инструмент балансирования затрат и результатов. Двойственные оценки, обладают тем свойством, что они гарантируют рентабельность оптимального плана, т. е. равенство общей оценки продукции и ресурсов, и обусловливают убыточность всякого другого плана, отличного от оптимального. Двойственные оценки позволяют сопоставить и сбалансировать затраты и результаты системы. 
     Теорема (о дополняющей нежесткости)   
     Для того, чтобы планы   и   пары двойственных задач были оптимальны, необходимо и достаточно выполнение условий: 
                    (2.30) 
                   (2.31) 
     Условия (2.30), (2.31) называются условиями дополняющей нежесткости. Из них следует: если какое-либо ограничение одной из задач ее оптимальным планом обращается в строгое неравенство, то соответствующая компонента оптимального плана двойственной задачи должна равняться нулю; если же какая-либо компонента оптимального плана одной из задач положительна, то соответствующее ограничение в двойственной задаче ее оптимальным планом должно обращаться в строгое равенство. 
     Экономически это означает, что если по некоторому оптимальному плану   производства расход i-го ресурса строго меньше его запаса  , то в оптимальном плане соответствующая двойственная оценка единицы этого ресурса равна нулю. Если же в некотором оптимальном плане оценок его i-я компонента строго больше нуля, то в оптимальном плане производства расход соответствующего ресурса равен его запасу. Отсюда следует вывод: двойственные оценки могут служить мерой дефицитности ресурсов. Дефицитный ресурс (полностью используемый по оптимальному плану производства) имеет положительную оценку, а ресурс избыточный (используемый не полностью) имеет нулевую оценку. 
     Теорема (об оценках). Двойственные оценки показывают приращение функции цели, вызванное малым изменением свободного члена соответствующего ограничения задачи математического программирования, точнее 
                           (2.32)

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

Для задачи, состоящей  в максимизации функции

при условиях

сформулировать двойственную задачу.

Решение. Для данной задачи

В соответствии с общими правилами задача, двойственная по отношению к данной, формулируется  следующим образом: найти минимум  функции  при условиях