Понятие двойственной задачи

Пусть имеется следующая задача линейного программирования, которую будем называть прямой:

Задача 1.

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

Задача 2.

Можно показать, что имеет место принцип взаимной двойственности: двойственной к задаче 2 является задача 1. Таким образом, несущественно, какую из задач 1 или 2 называть прямой, а какую двойственной.

Пример 1. Дана ЗЛП

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

Задачу нужно привести к виду, в котором записана задача 1. Все ограничения, кроме требований неотрицательности переменных, должны быть неравенствами вида ≤. Первое неравенство умножим на (-1). Затем заменим равенство – x₁+x₂=2 двумя неравенствами –x₁+x₂≤2 и –x₁+x₂≥2; второе из этих неравенств умножим на (-1). В результате ЗЛП примет вид:

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