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

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

(1)

при условиях (2)

(3)

Определение 1. Задача, состоящая в нахождении минимального значения функции (4) при условиях (5) (6) называется двойственной по отношению к задаче (1) – (3). Задачи (1) – (3) и (4) – (6) образуют пару задач, называемую в линейном программировании двойственной парой. Сравнивая две сформулированные задачи, видим, что двойственная задача составляется согласно следующим правилам:

1. Целевая функция исходной задачи (1) – (3) задается на максимум, а целевая функция двойственной (4) – (6) – на минимум.

2. Матрица

(7)

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

(8)

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

3. Число переменных в двойственной задаче (4) – (6) равно числу ограничений в системе (2) исходной задачи (1) – (3), а число ограничений в системе (5) двойственной задачи – числу переменных в исходной задаче.

4. Коэффициентами при неизвестных в целевой функции (35) двойственной задачи (4) – (6) являются свободные члены в системе (2) исходной задачи (1) – (3), а правыми частями в соотношениях системы (5) двойственной задачи – коэффициенты при неизвестных в целевой функции (1) исходной задачи.

5. Если переменная x_j исходной задачи (1) – (3) может принимать только лишь положительные значения, то j–е условие в системе (5) двойственной задачи (4) – (6) является неравенством вида “? ”. Если же переменная x_j может принимать как положительные, так и отрицательные значения, то 1 – соотношение в системе (2) представляет собой уравнение. Аналогичные связи имеют место между ограничениями (2) исходной задачи (1) – (3) и переменными двойственной задачи (4) – (6). Если i – соотношение в системе (2) исходной задачи является неравенством, то i–я переменная двойственной задачи  . В противном случае переменная у_j может принимать как положительные, так и отрицательные значения.

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

17. Основные теоремы двойственности.

Теор. 1 (осн.): Если одна из взаимно двойственных задач имеет оптимальное решение, то и другая также имеет оптимальное решение, причем их оптимальные решения совпадают.

Max f = min ɥ

Напр.: max f = f(6;4)=24

По теореме min ɥ = 24

Если целевая функция (прод. теор.) одной из двойственной задачи неограниченна (max f=∞ или min f=-∞) то условие другой задачи противоречивы.

Установка соответствия между переменными взаимно двойственных задач:

Исх. задача: осн: x1,x2; вспомогат: x3,x4,x5,x6

Двойств. задача: осн: y5,y6; вспомогат: y1,y2,y3,y4

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