Файл: Теорема КунаТаккера. Рассмотрим основную задачу выпуклого программирования (1).doc

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 08.11.2023

Просмотров: 82

Скачиваний: 3

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
§ 1. Теорема Куна-Таккера.Рассмотрим основную задачу выпуклого программирования:(1) , (2) , (3)где и - выпуклые функции.В теории нелинейного программирования центральное место занимает теорема Куна-Таккера, которая обобщает метод множителей Лагранжа на случай, когда в З.Н.П., кроме ограничений равенств, содержатся также ограничения-неравенства.Теорема Куна-Таккера устанавливает связь между оптимальным планом задачи (1) – (3) и седловой точкой функции Лагранжа для этой задачи:(4)где ; .Теорема Куна-Таккера. Пусть существует вектор , такой что < 0, . Вектор тогда и только тогда является оптимальным решением задачи (1) – (3), когда существует вектор , такой что, при , для всех и выполняется условие:
(5)Точка называется седловой точкой функции Лагранжа, а теорема Куна-Таккера – теоремой о седловой точке. Точка называется седловой точкой функции Лагранжа (4), если вектор минимизирует функцию , а вектор максимизирует функцию , так что для всех , выполняется условие: .Доказательство: Достаточность. Пусть - седловая точка функции и для нее выполняются условия (5). С учетом (4) эти условия имеют вид: Учитывая левую часть неравенства получим: для всех = 0, а это возможно тогда, когда = 0. Тогда из правого неравенства получим: , но , следовательно , таким образом, удовлетворяет условиям исходной задачи и во всех других точках функция принимает значение больше, чем в точке .Достаточность доказана.Доказательство необходимости является громоздким, и его не приводим.
§ 2. Градиентный метод (случай, когда оптимум находится на границе).Рассмотрим задачу Н.П. следующего вида:(1) , (2) . (3)Рассмотрим геометрическую интерпретацию задачи.Пусть область решения задачи и линии уровня изображены на чертеже:Если точка оптимума находится на границе области, то вектор-градиент Z в этой точке не равен нулю.Найдем начальную точку А принадлежащую области решений. Из этой точки будем двигаться в направлении qradZ(A) до тех пор, пока Z не достигнет max значение в данном направлении. В данном случае, двигаясь в направлении qradZ(A) мы попадаем в точку находящуюся за границей области. Например, в точку B. Уменьшение значения параметра t приведет к тому, что мы будем двигаться по прямой AB и точку максимума не найдем. В этом случае в область решений надо вернуться иначе, а именно в направлении вектора qradZ(B). Пусть двигаясь в направлении этого вектора, мы попадем в точку С. Затем из точки С двигаемся в направлении вектора qradZ(С), попадаем в точку D из точки D в направлении qradZ(D) и т.д. такими зигзагообразными движениями мы, наконец, попадем в точку K.При нахождении точек надо их находить так, чтобы значение Z возрастало. Из K попадем в точку L. Из чертежа видим, что точки K, L и находится на одной прямой. Как проверить то, что точкиK иL находятся на одной прямой?Отношения их координат приблизительно будут равны между собой. В этом случае находим точку пересечения

прямой KL с линией или, изменяя значение t, постараемся, двигаясь вдоль прямой KL попасть в область решений по возможности ближе к границе = 0.

Градиентные методы являются приближенными методами и применяются для решения задач с помощью вычислений техники: ПК. Как правило, с их помощью находится только локальные оптимумы и лишь в частных случаях, для задач выпуклого программирования находим глобальный оптимум. При этом функции f и qi должны быть непрерывными и дифференцированными функциями.

Замечание, Часто можно ограничиваться нахождением приближенного решения (не искать ) близко к . Критерием в этом случаем служит малое изменение Z при движении по прямой KL (для точек принадлежащих области решений).




Смотрите также файлы