Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Рассмотрим задачу выпуклого программирования вида
, где и - выпуклые дифференцируемые функции. В данном случае допустимое множество выпукло, поэтому в любой допустимой точке существует возможное направление . Для того, чтобы в данной задаче направление было возможным и подходящим в точке , достаточно, чтобы оно удовлетворяло системе неравенств (1) , , где - множество активных в точке ограничений. Возможное и подходящее направление, удовлетворяющее данной системе неравенств, определяется из решения задачи линейного программирования , . Заметим, что удовлетворяет всем ограничениям задачи, следовательно, ожидаемый результат . Если , то система (1) имеет решение . В этом случае строится новая точка . При этом выбирается таким образом, чтобы была допустимой точкой, например, где выбирается из условия , а - максимально возможное перемещение из точки вдоль направления с учетом -го ограничения, которое найдено из условия . Если , то система (1) несовместна, т.е. все возможные в точке направления не являются подходящими. Это означает, что в точках допустимого множества, достаточно близких к , выполняется неравенство , т.е. -точка локального минимума на допустимом множестве. Но для выпуклой функции на выпуклом множестве этот минимум является и глобальным. Таким образом, точка есть решение задачи.
Алгоритм Шаг 1. Задать начальную точку , характеристику точности алгоритма . Положить . Шаг 2. Найти . Если , то вычисления прекратить и положить , иначе перейти к шагу 3. Шаг 3. Подставить в неравенства и определить множество индексов активных ограничений . Шаг 4. Если , то положить , иначе определить из решения задачи , . Шаг 5. Если или , то положить . Иначе для найденного вектора определить , где выбирается из условия , а - максимально возможное перемещение из точки вдоль направления с учетом -го ограничения, которое найдено из условия . Шаг 6. Найти очередное приближение . Пример 2. Найти минимум в задаче
. Решение. 1. Возьмем в качестве начальной точки . Легко проверить, что данная точка принадлежит допустимому множеству, причем . Положим , . 2. Найдем . Так как , то продолжим решение задачи. Для нахождения вычислим и составим задачу линейного программирования
, . 3. Решая полученную задачу симплексным методом, получим , , . Метод линеаризации (Франка Вулфа)
Рассмотрим задачу минимизации выпуклой нелинейной функции на множестве, задаваемом линейными ограничениями: Метод линеаризации основан на замене в окрестности точки xk нелинейной функции линейной функцией . Из формулы Тейлора следует, что . Положим . Рассмотрим задачу линейного программирования Обозначим решение к - той ЗЛП. Тогда направление в исходной задаче будет подходящим. Формула пересчета имеет вид , где шаг ищется по правилу наискорейшего спуска с учетом условия (при таком выборе точка будет выпуклой линейной комбинацией точек и , что обеспечивает ее допустимость). В качестве критериев останова алгоритма применяются стандартные критерии: Алгоритм Шаг 0. Зафиксировать начальное приближение. Положить к=0. Шаг 1. Решить задачу линейного программирования , найти . Шаг 2. Зафиксировать вектор в качестве направления поиска. Шаг 3. Вычислить . Шаг 4. Положить Шаг 5. Проверить условия останова и, если они выполнены, вычисления прекратить и взять точку в качестве искомого решения. Иначе положить k=k+1 и перейти на шаг1.
Пример 1. Решить методом линеаризации задачу нелинейного программирования Решение. Данная задача была графически решена в §2: x*=(5/2,1/2). Для решения задачи методом линеаризации выберем x0 , например, x0 =(0,0). Вычислим
, где . Запишем задачу одномерной оптимизации Решением этой задачи будет Итерация 2 . Рассмотрим задачу Решением этой ЗЛП является отрезок, соединяющий точки (2,1) и (0,2).
Выберем одну из них, например, (2,1). Тогда , . Запишем задачу одномерной оптимизации Решением этой задачи будет Итерация 3. . Рассмотрим задачу Решением этой ЗЛП является отрезок, соединяющий точки (2,1) и (3,0). Выберем одну из них, например, (3,0). Тогда . . Запишем задачу одномерной оптимизации
Решением этой задачи будет . Останов. Получено оптимальное решение х*= .
Метод секущих плоскостей
Данный метод применяется для решения задач выпуклого программирования с линейной целевой функцией: (1) Замечание 1. Любая задача выпуклого программирования может быть записана в виде (1). Действительно, если есть задача с нелинейной целевой функцией то она может быть переписана следующим образом
Метод секущих плоскостей основан на приближении всех нелинейных функций линейными с использованием разложения по формуле Тейлора. Рассмотрим задачу (2) Если множество ограничено, то задача (2) всегда разрешима (в противном случае может оказаться, что , даже если задача (1) разрешима) Так как функции выпуклы вниз, справедливо неравенство . Следовательно . Пусть - решение задачи (2). 1) Если точка допустима в задаче (1), то она является оптимальным решением этой задачи (поскольку это экстремум той же целевой функции на более широком множестве). 2) Если , то в задаче (2) добавляются новые линейные ограничения: .Эти ограничения обладают следующими свойствами: a) точка не удовлетворяет этим ограничениям; b) во всех точках множества они выполняются. Таким образом, получаем новое множество , такое что . Далее итерационный процесс повторяется. Доказано, что генерируемая таким образом последовательность { } решений ЗЛП сходится к оптимальной точке исходной задачи. Алгоритм метода имеет следующий вид.
|
|||||||||||||||||||||
Последнее изменение этой страницы: 2021-11-27; просмотров: 57; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.219.96.188 (0.055 с.) |