Использование ЛП постановок для решения

Нелинейных оптимизационных задач

Если удается более сложный класс задач свести к решению каких-то пусть и многих задач ЛП - это считается большой удачей - проблема обычно эффективно разрешается.

1. Аппроксимация нелинейной выпуклой 2. Разбиения нелин невыпуклой области линейными ограничениями на несколько выпуклых областей

Их аппрокс линейными ограничениями

В точках сетки берем частн произ и решение ЛП задач в каждой из них

и находим направление аппрокс-щих

линейных ограничений

Л кон

Матричная постановка каноническойЛП задачи

В матричном виде постановкa ЛПЗ имеет вид

требуем (*)

при ограниченияx Ax = b (**)

Здесь у нас m ограничений и n переменных х

при с э Rⁿ, x э Rⁿ, b э R^m,

A = A (m,n), rank A =m, (m<n),

Общее

- и МНК и ЛП - разновидности задач оптимизации

-и ЛП и МНК применяются для решения задач моделирования но в случае ЛП - мы гораздо больше можем сформулировать разнообразных ЗадМоделирования так как ограничения на область моделирования (неравенства) - естественный элемент ЗЛП - это очень интересно но на это у нас сейчас в курсе времени нет )

Отличия -

Оптимизацонная постановка МНК определяет функционал задачи мин где - составляющие вектора невязок условной системы уравнений , при этом

матричная запись системы условных уравнений -требований в МНК

(*)

(О)

определяет переопределенную систему -то есть число ограничений- требований (точек х) к решению - m > n -числа переменных системы, и, то есть, больше чем число искомых параметров при них (то есть размерности вектора А)

Т.о. в постановке МНК мы имеем такую специфическую форму задачи оптимизации когда у нас нет допустимых решений - и мы находим наилучшее из недопустимых (дальше мы напомним механизм такого подхода)

А вот в задаче ЛП когда m_требов>n_{переменных}- решения нет и ничего найти нельзя так как нет допустимой области решений.

То есть решение оптимизационной задачи в форме ЗЛП применимо только при недоопределенной системе типа (0) то есть когдаn_{переменных}> m_требов

Подходы к решению несовместных оптимизационных задач

Рассмотрим задачу с линейным ф-лом (*)

и ограничениями Ax = b (**)

при этом имеем ситуацию m_требов>n_{переменных}

Попытка решать ее через ЗЛП в лоб упирается в несовместность (**) и отсутствие ОДР ввиду m>n

Тогда введя в Ax= *= b невязки - вектор у = Ax - b имеем 2 пути решения

1. Вариант типа МНК:

Метод безусловной оптимизации при несовместной системе ограничений

Сформируем безусловный критерий

L= и потребуем его минимизации

- здесь " у² "^- так как невязка может быть и +и -

или правильнее

Далее как и в МНК берутся производные и приравнивая их нулю -получаем систему линейных уравнений относительно х

Остается вопрос балансировки требований к нашей задаче -

1.минимизации исходного критерия с^тх и 2. минимизации невязок у = Ax - b

Использование ЗЛП для оптимизации при несовместной системе ограничений

И так - линейный ф-л (*)

и ограничения Ax = b (**) при m_огр>n_пер

Рассм. минимизацию исходного ф-ла и модуля вектора невязок

у =/ Ax - b / ----тогда возможно получить задачу уже в классе ЛП

( имеем в виду что

1. после введения в ограничения(**) вектора у в качестве невязок и

2. после приведения к канонической форме системы (***) будем иметь уже количество m_требов<n_{переменных} )

Итак задача будет иметь вид

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

(1***) (***)

(2***)

Понимаем что

если получается так, что в одном из (1***) Ax - b >0 то соответствующий "у" обязан быть некоторым +: у=(+) чтобы оно выполнлось и при этом работает минимизация "у" верхнего неравенства (1***), а соответствующее нижнее (2***)автоматом выполняется,

если же получается так, что в одном из (2***) Ax - b <0 то соответствующий"у" также обязан быть некоторым +: у=(+) чтобы оно выполнялось и при этом работает минимизация "у" нижнего неравенства (2***), а соответствующее верхнее (1***) автоматом выполняется

Минимизируется именно модуль невязки потому что структура неравенств системы (***) как видим обеспечивает всегда ( выполняется автоматом - это доказывается)

Таким образом убиваем 2 зайцев - осуществляем минимизацию исходного ф-ла и модуля вектора невязок у =/ Ax - b /

Возникает однако как и в первом случае необходимо балансировать исходный критерий с^тх с требованием мин невязок у - это вопрос выбора вектора коэффициентов - но это естественная плата за то что с одной стороны имеем требование мин с^тх а с другой несовместную систему из которой необходимо выбрать решение наиболее близкое к совместному этот компромис идолжны отражать параметры . В тривиальном случае возьмем все альфа=1

Интересен частный случай вышеприведенной задачи -

 

⇐ Предыдущая18192021222324252627Следующая ⇒

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычис­лить, когда этот...

Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...

---

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: