стр 240
Теория двойственности представляет собой весьма важное, как с чисто теоретической, так и с практической точки зрения, направление математического программирования. Основная идея теории двойственности: для каждой задачи ЛП существует некоторая задача ЛП, решение которой тесно связано с прямой. Между решениями прямой и двойственной задач имеется ряд важных соотношений, полезных при исследовании общих свойств оптимального решения ЗЛП и проверке оптимальности допустимого решения.
Двойственная задача к ЗЛП в стандартной форме: рассмотрим ЗЛП (в стандартной форме)
min Z = C*X,
A*X = B,
X ≥ 0
(П) Прямая задача.
Каждому i–му (i = 1,m) ограничению поставим в соответствие переменное ui, положительное, отрицательное или нуль (называемое двойственным переменным), и рассмотрим ЗЛП.
max W = U*B
U* AT ≤ C, AT*U ≤ C
(Д) Двойственная задача
где U есть, так называемый, вектор–строка (u1, u2, …, um).
Линейная задача (Д) тесно связана с линейной задачей (П):
- матрица ограничений (Д) есть транспонированная матрица задачи (П);
- вектор "цен" для задачи (П) есть вектор правых частей ограничений задачи (Д) и наоборот.
Данная таблица соответствий между прямой и двойственной задачами позволяет записать непосредственно двойственную задачу для любой линейной задачи.
Таблица
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Замечание: двойственная к двойственной задаче совпадает с прямой.
Каждой задаче линейного программирования соответствует двойственная задача. Двойственная задача по отношению к исходной задаче строится по следующим правилам: 1. Если исходная задача ставится на максимум, то двойственная ставится на минимум и наоборот. 2. Коэффициенты целевой функции исходной задачи становятся правыми частями ограничений двойственной задачи. Правые части ограничений исходной задачи становятся коэффициентами целевой функции двойственной задачи. 3. Если A-матрица коэффициентов исходной задачи, то транспонированная матрица T A будет матрицей коэффициентов двойственной задачи. 4. В задаче на максимум все ограничения имеют знак ≤ (=), а в задаче на минимум все ограничения имеют знак ≥ . 5. Число переменных в двойственной задаче равно числу ограничений в исходной задаче. Каждому ограничению исходной задачи соответствует переменная двойственной задачи. Если ограничение исходной задач имеет знак ( ≥ ), то соответствующая переменная двойственной задачи неотрицательна. Если ограничение имеет знак (=), то соответствующая переменная двойственной задачи может принимать положительные и отрицательные значения и наоборот
