при ограничениях
YA>C,
Y - вектор свободных переменных (т.е. не имеющих ограничений в знаке). УПРАЖНЕНИЯ 7.5.1
1. Докажите, что задача, двойственная к двойственной задаче, совпадает с исходной (прямой) задачей.
2. Пусть прямая задача имеет вид: минимизировать z = {СХ АХ > b, X > 0}. Сформулируйте соответствующую двойственную задачу.
7.5.2. Оптимальное решение двойственной задачи
В этом разделе устанавливаются соотношения между прямой и двойственной задачами и показывается, как определить оптимальное решение двойственной задачи на основе оптимального решения прямой задачи. Обозначим через В оптимальный базис прямой задачи, через Св - вектор коэффициентов целевой функции, соответствующих оптимальным базисным переменным Хв.
Теорема 7.5.1. Первая теорема двойственности. Для любой пары допустимых решений (X, Y) прямой и двойственной задач значение целевой функции в задаче минимизации ограничивает сверху значение целевой функции в задаче максимизации. Для пары оптимальных решений (X*, Y ) значения целевых функций совпадают.
Доказательство. Пара допустимых решений (X, Y) удовлетворяет всем ограничениям обеих задач. Умножая слева обе части ограничений задачи максимизации на вектор (свободных) переменных Y, получим
YAX = Yb = ш.
Аналогично, умножая справа ограничения задачи минимизации на вектор (неотрицательных) переменных X, будем иметь
YAX>CX = 2.
(Неотрицательность вектора X здесь существенна, так как определяет "направленность" неравенства.) Комбинируя последние два выражения, получаем неравенство z<w, доказанное для пары любых допустимых решений (X, Y).
Отметим, что теорема не указывает, какая задача прямая, а какая - двойственная. Это очень важно при нахождении оптимальных решений обеих задач.
Из доказанной части теоремы (z < w для пары любых допустимых решений) следует, что максимум функции z и минимум функции w будут достигнуты только тогда, когда обе эти функции примут одинаковое значение. Исходя из этого, можно построить оценку близости полученных допустимых решений к оптимальным путем сравнения разности 2 - w и величины (2 + w)/2. Чем меньше отношение 2(2 - w)/(z + w), тем ближе данные решения к оптимальным. Но, конечно, из этого эмпирического правила не следует, что оптимальные значения целевых функций равны (г + w)/2.
Если в одной из задач целевая функция примет бесконечное значение, что можно сказать о решении другой? Ответ очевиден: другая задача не должна иметь допустимых решений. Если это не так (т.е. обе задачи имеют допустимые решения), неравенство z < w обязательно должно выполняться, что невозможно, например,
При 2 = +оо или w = -<*>.
Рассмотрим обратную ситуацию. Если одна из задач не имеет допустимых решений, то обязательно ли решение другой задачи будет неограниченным? Не
обязательно! В следующем примере и прямая, и двойственная задачи не имеют допустимых решений.
Прямая задача. Максимизировать z = {х1 + х2 х1 - х2 <-1, ~х1 + х2 <-1, х„ х2>0}.
Двойственная задача. Минимизировать w = {-yt - у2 \ у, - у2> 1, -у, + у2 > 1,
Теорема 7.5.2. Оптимальное решение двойственной задачи равно
Y = CSB\
где В - оптимальный базис прямой задачи, которому соответствует вектор Св коэффициентов целевой функции.
Доказательство. Для доказательства этой теоремы надо показать, что допустимое решение двойственной задачи можно вычислить по формуле Y = СВВ , и что в соответствии с теоремой 7.5.1 z = w для оптимальных решений.
Решение прямой задачи будет оптимальным, если выполняются неравенства гу - су> О для всехj (см. раздел 7.2.1), т.е.
СВВ А - С > 0.
Но решение Y допустимо, если оно удовлетворяет ограничению YA > С. Это доказывает равенство Y = СВВ-1 для допустимого решения двойственной задачи Y.
Равенство оптимальных значений z и w доказывается непосредственным сравнением выражений
w = Yb = CBB Ь, zXCBb.
Переменные двойственной задачи Y= СВВ-1 иногда называют симплексными мультипликаторами. Они также известны как двойственные цены - название, идущее от экономической интерпретации этих переменных (см. раздел 4.3.1).
Обозначим через Ру у-й столбец матрицы А. Из теоремы 7.5.2 следует, что величины
zrcrCBV1VrcrW-ci
равны разностям между левыми и правыми частями ограничений двойственной задачи. В начале решения прямой задачи максимизации по крайней мере для одного j выполняется неравенство zt - с. < 0; это означает, что соответствующее ограничение YP. >с не удовлетворяется. Если достигнуто оптимальное решение прямой задачи, тогда выполняются неравенства z. - с; > 0 для всех /; в этом случае соответствующее решение двойственной задачи Y= СВВ~ допустимо. Таким образом, если решение прямой задачи оптимально, то решение двойственной задачи автоматически допустимо. На этом соотношении построен двойственный симплекс-метод (раздел 4.4), в котором вычисления начинаются с недопустимого решения, "лучшего", чем оптимальное. Выполнение метода продолжается до тех пор, пока не будет достигнуто допустимое решение. В противоположность этому в "обычном" симплекс-методе (глава 3) вычисления начинаются с допустимого, но "худшего", чем оптимальное, решения и продолжаются до тех пор, пока не будет достигнуто оптимальное решение.
Пример 7.5.1
В следующей задаче ЛП оптимальный базис равен В = (Р,, Р4). Сформулируем двойственную задачу и найдем ее оптимальное решение, используя оптимальный базис прямой задачи.
Максимизировать z = Зх, + Ъх2
при ограничениях
х, + 2х2 + х3 = 5, ~х1 + Зх2 + xt = 2,
Х - 0.
Двойственная задача имеет следующий вид.
Минимизировать w = 5(/, + 2у2
при ограничениях
У\~Уг - 3> 2(/, + 3(/2>5,
«/,.«/, поимеем В = (лс,, x4)r, тогда Св = (3, 0). Оптимальный базис и его обратная матрица равны следующему.
ч: з-ct)-
Переменные прямой и двойственной задач имеют следующие значения.
(x1,x/ = B-1b = (5, 7f,
((/l,y2) = CBB,=(3(0).
Оба решения допустимы и 2 = w = 15 (проверьте!). Таким образом, решения оптимальны.
УПРАЖНЕНИЯ 7.5.2
1. Проверьте правильность формулировки двойственной задачи в примере 7.5.1. Проверьте графически, что прямая и двойственная задачи не имеют недопустимых решений.
2. Дана следующая задача линейного программирования.
Максимизировать z = 50х, + 30 х2 + 10х3 при ограничениях
2хх + х2 1, 2х2 - -5, 4x, + x3 = 6, *„ х2, х3>0.
a) Сформулируйте и запишите двойственную задачу.
b) Покажите с помощью непосредственной проверки, что прямая задача не имеет допустимого решения.