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

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

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

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

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

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

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

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

Л кон

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

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

требуем (*)

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

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

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

A = A(m,n), rankA =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Следующая ⇒

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

ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...

Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...

---

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