Правила составления двойственных задач

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

Различают два основных вида пар двойственных задач:

Симметричные пары	Несимметричные пары
Исходная	Двойственная	Исходная	Двойственная

Алгоритм составления двойственной задачи:

1. Привести исходную задачу к одному виду (если , то , если , то ).

2. Составить расширенную матрицу исходной задачи из коэффициентов системы ограничений и целевой функции.

3. Составить транспонированную матрицу.

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

Пример 10. Для заданной задачи линейного программирования составить двойственную задачу:

, , , .

Решение.

1. Приведем исходную задачу к одному виду:

, , , .

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

3. Транспонируем матрицу: .

4. Составим двойственную задачу:

, , , .

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