Первая  теорема двойственности.

      Если  одна из пары двойственных задач (I) и (II разрешима, то разрешима и другая задача, причем оптимальные значения целевых функций прямой и двойственной задач совпадают

      

      оптимальные планы задач (I) и (II) соответственно.

      Доказательство.

      1. Пусть задача (I) разрешима, и пусть

      

      т.е. х* - оптимальное решение. Обозначим  M= L(х*).

      Тогда по основной лемме существует

      

      для которого

      Но  по основному неравенству двойственности имеем :

      

      Объединяя последние два соотношения, имеем 

      откуда  следует, что у* - оптимальное решение  задачи (II) и

      

      2. Пусть теперь задача (II) -разрешима. Построим эквивалентную (II) задачу

      

      Задача (II') разрешима, так как задача (II) разрешима. Тогда по пункту 1 двойственная к (II') задача :

      

      Но  эта задача эквивалентна задаче (I). Следовательно, задача (I) разрешима.

      Теорема доказана.

      Первый  критерий оптимальности

      Решение   оптимально тогда и только тогда, когда существует решение

         такое, что

      Доказательство.

      Необходимость следует из первой теоремы двойственности.

      Достаточность следует из достаточного условия  оптимальности. 

      Вторая  теорема двойственности

      Рассмотрим  пару симметрических двойственных задач  ЛП

      

      Вторая  теорема двойственности

      Чтобы допустимые решения  х, у пары двойственных задач (I) и (II) были оптимальными необходимо и достаточно, чтобы выполнялись  условия :

      

      Доказательство.

      Необходимость. По условию допустимые решения х, у - оптимальны.

      

      то  из оптимальности решений х, у по первой теореме двойственности

      В результате имеем 

      Необходимость доказана.

      Достаточность. По условию

      

      

      По  первой теореме двойственности получаем, что х, у - оптимальные решения  задач (I) и (II).

      Допустимые  решения х, у задач (I) и (II) удовлетворяют условиям дополняющей нежесткости (УДН), если при подстановке этих векторов в ограничения задач (I) и (II) хотя бы одно из любой пары сопряженных неравенств обращается в равенство

      Второй  критерий оптимальности (следствие  из условий дополняющей нежесткости)

      Чтобы допустимые решения х, у пары двойственных задач (I) и (II) были оптимальны, необходимо и достаточно, чтобы выполнялись  соотношения :

        

      Доказательство. Распишем

      

      покоординатно :

      

      Из  допустимости решений х и у  следует, что

      

      

      тогда, когда каждое слагаемое в этих равенствах равно нулю

      

      Произведение  двух сомножителей, как известно, равно  нулю, тогда и только тогда, когда  хотя бы один из множителей равен нулю.

      Следовательно, равенства (*) или, что то же самое

      

      эквивалентны  условиям (1)-(4), и по второй теореме  двойственности получаем справедливость утверждения.

      Критерий  доказан. 

      Замечание Условия (1)-(4) есть условия дополняющей  нежесткости, поэтому критерий можно  сформулировать более лаконично.

      Второй  критерий оптимальности

      Чтобы допустимые решения х, у пары двойственных задач (I), (II) были оптимальны, необходимо и достаточно, чтобы выполнялись  УДН. 

      Критерий  разрешимости задачи ЛП

      Точной  верхней гранью (супремумом) функции L(х) на множестве D называется такое число М*, что

      

      Двойственный метод  решения ЗЛП

      Каждой  задаче линейного программирования можно определенным образом сопоставить  некоторую другую задачу (линейного  программирования), называемую двойственной или сопряженной по отношению к исходной или прямой задаче. Дадим определение двойственной задачи по отношению к общей задаче линейного программирования, состоящей, как мы уже знаем, в нахождении максимального значения функции

       (32)

      при условиях

       (33)

       (34)

      Задача, состоящая в нахождении минимального значения функции

       (35)

      при условиях

       (36)

       (37)

      называется  двойственной по отношению к задаче (32) – (34). Задачи (32) – (34) и (35) – (37) образуют пару задач, называемую в линейном программировании двойственной парой. Сравнивая две сформулированные задачи, видим, что двойственная задача составляется согласно следующим правилам: 

      1. Целевая функция исходной задачи (32) – (34) задается на максимум, а целевая функция двойственной (35) – (37) – на минимум. 
 

      2. Матрица

       (38)

      составленная  из коэффициентов при неизвестных  в системе ограничений (33) исходной задачи (32) – (34), и аналогичная матрица

       (39)

      в двойственной задаче (35) – (37) получаются друг из друга транспонированием (т. е. заменой строк столбцами, а  столбцов – строками). 

      3. Число переменных в двойственной  задаче (35) – (37) равно числу ограничений  в системе (33) исходной задачи (32) – (34), а число ограничений  в системе (36) двойственной задачи  – числу переменных в исходной  задаче. 

      4. Коэффициентами при неизвестных в целевой функции (35) двойственной задачи (35) – (37) являются свободные члены в системе (33) исходной задачи (32) – (34), а правыми частями в соотношениях системы (36) двойственной задачи – коэффициенты при неизвестных в целевой функции (32) исходной задачи. 

      5. Если переменная xj исходной задачи (32) – (34) может принимать только  лишь положительные значения, то j–е условие в системе (36) двойственной  задачи (35) – (37) является неравенством  вида “? ”. Если же переменная xj может принимать как положительные, так и отрицательные значения, то 1 – соотношение в системе (54) представляет собой уравнение. Аналогичные связи имеют место между ограничениями (33) исходной задачи (32) – (34) и переменными двойственной задачи (35) – (37). Если i – соотношение в системе (33) исходной задачи является неравенством, то i–я переменная двойственной задачи В противном случае переменная уj может принимать как положительные, так и отрицательные значения. 

      Двойственные  пары задач обычно подразделяют на симметричные и несимметричные. В симметричной паре двойственных задач ограничения (33) прямой задачи и соотношения (36) двойственной задачи являются неравенствами вида “ ”. Таким образом, переменные обеих задач могут принимать только лишь неотрицательные значения. 

      Пример 11.  

      Составить двойственную задачу по отношению к  задаче, состоящей в максимизации функции

       (40)

      при условиях

       (41)

       (42)

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

        и 

      Число переменных в двойственной задаче равно  числу уравнений в системе (41), т. е. равно трем. Коэффициентами в целевой функции двойственной задачи являются свободные члены системы уравнений (41), т.е. числа 12, 24, 18. 

      Целевая функция исходной задачи (40) – (42) исследуется  на максимум, а система условий (41) содержит только уравнения. Поэтому  в двойственной задаче целевая функция исследуется на минимум, а ее переменные могут принимать любые значения (в том числе и отрицательные). Так как все три переменные исходной задачи (40) – (42) принимают только лишь неотрицательные значения, то в системе условий двойственной задачи должны быть три неравенства вида “? ”. Следовательно, для задачи (40) – (42) двойственная задача такова: найти минимум функции

      при условиях

      

      Пример 12.  

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

      

      при условиях

      

      

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

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

       ,

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

      

 

       Заключение

 

       Пример:

      Составить задачу, двойственную данной задаче:

 

      F=-4x₁-18x₂-30x₃-5x₄ → max

      при ограничениях:

        

        

        

      Составим  расширенную матрицу системы: 

              x₁   x₂    x₃     x₄

      

Найдём матрицу  А, транспонированную к А’:  

                y₁     y₂

        

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

      F=-3y₁+3y₂ → min 

      при ограничениях: 

      

 

      

 
 

 

       Чтобы определить направление возрастания линейной функции, построим вектор q:

      F(y)=-3y₁+3y₂ , следовательно, по оси у₁ ставим точку на -3, по оси у₂  на 3  (т.к. коэффициент при у₁=-3, при у₂=3), затем от нуля к их точке пересечения проводим вектор.

      Так как рассматриваемая задача –  на отыскание минимума, то оптимальное решение в точке B, которая находится на пересечении 3 и 4 прямых. Следовательно, можно вычислить координаты этой точки для нахождения максимума целевой функции: