 |
 |
 |
 |
|
 |
 |
32
Из приведенного определения вытекает важное свойство — симметричность отношения
двойственности, т. е. задача, двойственная по отношению к двойственной, совпадает с прямой
(исходной) задачей:
Тем самым имеет смысл говорить о паре взаимно двойственных задач.
В матричной форме пара двойственных общих задач линейного программирования может быть
кратко записана как:
Рассмотрим процесс построения двойственной задачи на конкретном примере. Пусть задана ОЗЛП
(D, f):
тогда двойственной к ней будет задача (D*, f*):
1.6.3. Теоремы двойственности и их применение. Фундаментальные свойства, которыми обладают
двойственные задачи линейного программирования, могут быть сформулированы в виде приводимых
ниже утверждений. Их обычно называют теоремами двойственности.
Теорема 1.4. Если х, и— допустимые планы для пары двойственных задач (D,f) и (D*,f*), тo f(x)
?
f(u).
Доказательство.
Достаточно доказать теорему для случая, когда задача (D, f) является канонической. Рассмотрим пару
двойственных задач
Из того, что вектор и является допустимым планом задачи (D*, f*), следует, что иА
?
с. Умножив
левую и правую части данного неравенства на вектор х
? 0 ,
получим равносильную сис
тему неравенств
Одновременно для вектора х, являющегося допустимым планом задачи (D, f), справедливо равенство