Скаждой задачей линейного программирования можно связать некоторую другую задачу, называемую двойственной. Первоначальную задачу при этом называют исходной. Оптимальный план одной из задач тесно связан с оптимальным планом другой задачи. В этой главе мы познакомимся с понятием двойственной задачи и основными теоремами, связанными с практическим использованием понятия двойственности при решении оптимизационных задач.
Рассмотрим двойственную задачу в общей постановке.
I. Пусть ограничения исходной задачи имеют вид:
(4.1)
На множестве решений этой системы требуется максимизировать функцию
(4.2)
Двойственной для этой задачи будет задача с ограничениями
(4.3)
и минимизируемой целевой функцией
(4.4)
Сравнивая обе задачи, нетрудно заметить, что:
1. Матрица из коэффициентов при переменных в исходной задаче
и аналогичная матрица в двойственной задаче
получаются друг из друга простой заменой строк столбцами с сохранением
их порядка. Такая операция получила название транспонирование.
2. В исходной задаче п переменных и т ограничений, в двойственной т переменных и п ограничений.
3. В правых частях систем ограничений каждой из задач стоят коэффициенты целевой функции, взятой из другой задачи.
4. В систему ограничений исходной задачи входят неравенства типа 
, причем в задаче требуется максимизировать целевую функцию F. В систему ограничений двойственной задачи входят неравенства типа 
, причем в двойственной задаче требуется минимизировать целевую функцию 
.
Исходная и двойственная ей задачи образуют пару задач, называемую в линейном программировании двойственный парой. Следует заметить, что за исходную задачу можно "взять" любую задачу из этой пары, для дальнейшего решения это несущественно.
Следующая таблица значительно облегчает процесс составления математической модели двойственной задачи.
| x1 | x2 | x3 | … | xn | ||
| y1 | a11 | a12 | a13 | … | a11 | b1 |
| y2 | a21 | a22 | a23 | … | a11 | b2 |
| y3 | a31 | a32 | a33 | … | a11 | b3 |
| … … … | … … … | … … … | … … … | … … … | … … … | … … … |
| ym | am1 | am2 | am3 | … | amn | bm |
| c1 | c2 | c3 | … | cn |  bi
ci
|
В первой строке таблицы записываются все переменные исходной задачи, в первом столбце записываются все переменные двойственной задачи. В последней строке стоят коэффициенты целевой функции исходной задачи, в последнем столбце - коэффициенты целевой функции двойственной задачи. В прямоугольнике, который получился в результате ограничения указанными строками и столбцами, записаны коэффициенты при переменных исходной задачи - это матрица исходной задачи.
Чтобы получить, например, первое ограничение двойственной задачи, надо найти сумму произведений чисел, стоящих в столбце под x1 на соответствующие переменные первого столбца:
Считаем, что эта сумма не меньше 
.
Аналогично составляются и остальные ограничения для двойственной задачи. При этом устанавливается такое соответствие:
а) переменной х1 исходной задачи соответствует первое ограничение двойственной задачи, переменной х2 — второе ограничение двойственной задачи и т.д., переменной хn - последнее
ограничение двойственной задачи и наоборот;
б) переменной у1 двойственной задачи соответствует первое
ограничение исходной задачи и т. д., переменной ут двойственной задачи соответствует последнее ограничение исходной задачи
и наоборот.
Выражение для целевой функции получается как сумма произведений переменных первого столбца на соответствующие числовые значения последнего столбца.