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

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

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

Задачей, двойственной к задаче выше(двойственной задачей)- называется задача линейного программирования от m переменных вида:

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

, где

Теорема о двойственности: пусть х – допустимый план задачи линейного прог-я, у – допустимый план двойственной задачи:

1.

2. Если , то задача линейного прог-я не имеет допустимых планов, следовательно z=+бесконечность, следовательно двойственная задача не имеет допустимых планов.

3. Если х – допустимый план задачи линейного прог-я, у- допустимый план двойственной задачи и , то х – решение задачи линейного прог-я, у- решение двойственной задачи.

Док-во:

1) Т.к. х – допустимый план, то . Оценим

2) – противоречие => Z не имеет допустимых планов.

3) − допустимый планы. . Пусть – решение задачи линейного прог-я.

допустимый план двойственной задачи.

– решение задачи => y - решение двойственной задачи. Док-но.