Решение одной задачи выпуклого программирования.Рассмотрим следующую задачу оптимизации . (28) В (28) – симметричная матрица, . Очевидно, что (28) – задача со строго выпуклыми функциями и линейными ограничениями и имеет форму основной задачи выпуклого программирования с равенствами. Для этой задачи справедлива теорема Куна-Таккера, причем . Построим для задачи (28) функцию Лагранжа. и будем строить двойственную функцию: . Поскольку функция Лагранжа при строго выпукла, то достигается в стационарной точке, то есть там, где (29) Составим условие стационарности: (30) Отсюда получаем: . И построим двойственную задачу: (31) Нетрудно убедиться, что функция является строго вогнутой относительно (для этого нужно взять вторую производную по от и убедиться в том, что это будет матрица отрицательная). И поэтому задача (31) всегда имеет оптимальный план, и он достигается в стационарной точке (32) Составляем условие стационарности (32) . Отсюда находим оптимальный план (31), получаем: – оптимальный план (31). По теории двойственности тогда существует оптимальный план и прямой задачи, которая совпадает с (28) и он имеет вид: Таким образом, теория двойственности позволяет для задачи (28) сразу получить оптимальный план в явной форме. Задача (28)относится к задачам квадратичного программирования, то есть к задачам с квадратичной целевой функцией и линейными ограничениями.
|