В задаче 1 имеется n-переменных и m- ограничений типа (4). В задаче 1* имеется m –переменных и n-ограничений типа (8). Это значит, что каждой переменной в задаче 1 соответствует ограничение в задаче 1* и каждому ограничению в задаче 1 соответствует переменная в задаче 1*.
В задаче 1 требуется максимизировать целевую функцию на множестве заданных ограничений больше 0. В задаче 1* требуется минимизировать целевую функцию на множестве заданных ограничений меньше 0.
Коэффициенты сj линейной функции (1) в задаче 1 являются свободными членами ограничений (8) задачи 1*, свободные члены bi ограничений (4) в задаче 1 являются коэффициентами линейной функции (5) задачи 1*.
Коэффициенты при неизвестных аij в задачах 1 и 1* одни и те же, но матрицы из этих коэффициентов транспонированы по отношению друг к другу.
В задаче 1 все неравенства типа ³, а в задаче 1* все неравенства типа £.
Если на переменную задачи 1 налагается условие неотрицательности, то соответствующее ограничение в двойственной задаче является неравенством, а если условия неотрицательности на переменную нет, то соответствующее ограничение в задаче 1* является уравнением. И наоборот.
Пример составления двойственной задачи ЛП
Пример 1. Записать двойственную задачу к следующей задаче линейного программирования.
ЗАДАЧА1.
Найти х = (х1, х2, х3, х4), удовлетворяющий условиям:
| Решение. Заметим, что  т.е все переменные связаны условием неотрицательности, и все ограничения выполняются как неравенства. Двойственная задача имеет вид:
ЗАДАЧА 1*
Найти  удовлетворяющие условиям:
|
Пример составления двойственной задачи ЛП
Пример 2.
ЗАДАЧА 1.
Требуется максимизировать линейную функцию
 =2x1 — х2 + Зх3 + х4 — 5x5
на множестве пятимерных векторов
х = (х1, х2, х3, х4, х5),
удовлетворяющих условиям
 ,  ,  ,
Зх1 + 2х2 - 5х3 + х5 - 7  0,
3х2 - 4х3 - 2х4 + 1 = 0,
2х1 + 2х3 - 3х4 + х5 0.
| Решение.
ЗАДАЧА 1*
Требуется минимизировать линейную функцию
на множестве трехмерных векторов, удовлетворяющих условиям
 ,  ,
3y1 + 2y3 + 2  0,
2y1 + 3y2 -1 = 0,
- 5y1 + 4y2 + 3y3 + 3 0,
- 2y2 - 3y3 +1 0,
y1 + y3 - 5 = 0.
|
Связь между задачами 1 и 1*
Связь между парой двойственных задач устанавливает следующая лемма 1:
Для любых допустимых векторов х и у в задачах 1 и 1* выполняются неравенства
µ(x) £ 
(у), (9)
причем (9) выполняется как равенство в том и только в том случае, если справедливы следующие соотношения:
(10)
(11)
Связь между задачами 1 и 1*
Доказательство. Имеем:
хj ³0 для jÎJ2
(12)
Суммируя полученные соотношения, получим с учетом того, что 
(13)
Связь между задачами 1 и 1*
Доказательство (продолжение). Имеем:
yi ≥ 0 для iÎI2
(14)
(15)
Правые части в соотношениях (13) и (15) отличаются лишь порядком суммирования и, следовательно, равны между собой, т.е. выполняется µ(x) £ 
(у) (9). Для достижения равенства в (9), очевидно, необходимо и достаточно, чтобы достигались равенства во всех неравенствах (13) и (15). Последнее эквивалентно выполнению соотношений (10) и (11) ▄
Признак оптимальности в краткой форме
Для оптимальности допустимого вектора х= (х1,х2, …хn,) в задаче 1 достаточно существования допустимого вектора y= (y1,y2,…..yn) в задаче 1*, удовлетворяющего условию
m (х) = n (у)(16)
Тогда допустимый вектор y= (y1,y2,…..yn) также является оптимальным в задаче 1*.
Доказательство.
Пусть вектор х допустимый и существует допустимый вектор у такой, что справедливо (16). Покажем, вектор х оптимальный.
Рассмотрим некоторый другой оптимальный вектор х′ в задаче 1 (х′≠х), тогда имеем пару векторов х′ и у. Для этой пары допустимых векторов справедлива лемма 1, т. е. m (х′) ≤ n (у) =m (х)и m (х′) ≤m (х). Отсюда следует что х – оптимальный вектор.
Покажем теперь, что вектор у также является оптимальным.
Рассмотрим некоторый другой оптимальный вектор у′ в задаче 1 (у′≠у), тогда имеем пару векторов х и у′. Для этой пары допустимых векторов справедливо лемма 1, т. е. n(у′)≥m(х)= n(у) и n(у)≤ n(у′). Отсюда следует что у – оптимальный вектор.▄