Определение двойственной задачи

ТЕМА 1.3 ПРЯМАЯ И ДВОЙСТВЕННАЯ ЗАДАЧИ ЛП. ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД.

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

(25)

при условиях

(26)

(27)

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

(28)

при условиях

(29)

(30)

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

1. Целевая функция исходной задачи (25) – (27) задается на максимум, а целевая функция двойственной (28) – (30) – на минимум.

2. Матрица

(31)

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

(32)

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

3. Число переменных в двойственной задаче (28) – (30) равно числу ограничений в системе (26) исходной задачи (25) – (27), а число ограничений в системе (29) двойственной задачи – числу переменных в исходной задаче.

4. Коэффициентами при неизвестных в целевой функции (28) двойственной задачи (28) – (30) являются свободные члены в системе (26) исходной задачи (25) – (27), а правыми частями в соотношениях системы (29) двойственной задачи – коэффициенты при неизвестных в целевой функции (25) исходной задачи.

5. Если переменная x_j исходной задачи (25) – (27) может принимать только лишь положительные значения, то j –е условие в системе (29) двойственной задачи (28) – (30) является неравенством вида “”. Если же переменная x_j может принимать как положительные, так и отрицательные значения, то 1 – соотношение в системе (27) представляет собой уравнение. Аналогичные связи имеют место между ограничениями (26) исходной задачи (25) – (27) и переменными двойственной задачи (28) – (30). Если i – соотношение в системе (26) исходной задачи является неравенством, то i –я переменная двойственной задачи. В противном случае переменная у_j может принимать как положительные, так и отрицательные значения.

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

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

(33)

при условиях

(34)

(35)

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

и

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

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

Дата добавления: 2014-01-15