при ограничениях

х, + х2 + х3 + х4 > 25, 5х, + х2 < 20, 5Xj - х2> 5, х3 + х4 = 20,

1 2* *3 4 -

7. Решите следующую задачу методом декомпозиции.

Минимизировать z = 10yi + 2у2 + 4у3 + 8у4 + уъ при ограничениях

Ух + 4(/2 - у3 > 8, 2у, + </2 + </3>2, Зу, + г/4 + i/5 > 4, + 2у4-(/6>Ю,

<Л.</2> 3 У4>У0-

(Совет. Рассмотрите сначала задачу, двойственную к данной.)

8. Пусть при применении метода декомпозиции количество общих ограничений в исходной задаче равно г. Покажите, что целевую функцию для подзадачи j можно записать следующим образом.

Минимизировать wj = zl-cJ = (CsRAy - С;)Х; + СУ

Здесь матрица R состоит из первых г столбцов матрицы В 1, а V - ее (г + у)-й столбец.

7.5. ДВОЙСТВЕННОСТЬ

Двойственные задачи и соотношения двойственности на элементарном уровне мы изучали в главе 4. В этом разделе рассмотрим теорию двойственности на более строгом (доказательном) уровне, в частности, представим доказательства соотношений двойственности, которые являются основой анализа чувствительности (см. главу 4). Эти теоретические построения послужат фундаментом для описанных далее методов параметрического программирования.

7.5.1. Матричное представление двойственной задачи

Пусть прямая задача ЛП с т ограничениями и п переменными уже записана в стандартной форме.

Максимизировать z = СХ

при ограничениях

АХ = Ь, Х>0.

Обозначим через Y = (yv у2, ут) вектор переменных двойственной задачи. В соответствии с правилами, представленными в табл. 4.2, получаем следующую двойственную задачу.

Минимизировать w = Yb

при ограничениях

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) вычисления начинаются с допустимого, но худшего , чем оптимальное, решения и продолжаются до тех пор, пока не будет достигнуто оптимальное решение.