|
Использование ЛП постановок для решенияНелинейных оптимизационных задач Если удается более сложный класс задач свести к решению каких-то пусть и многих задач ЛП - это считается большой удачей - проблема обычно эффективно разрешается.
1. Аппроксимация нелинейной выпуклой 2 . Разбиения нелин невыпуклой области линейными ограничениями на несколько выпуклых областей Их аппрокс линейными ограничениями
и находим направление аппрокс-щих линейных ограничений
Л кон Матричная постановка каноническойЛП задачи В матричном виде постановкa ЛПЗ имеет вид требуем приограниченияx Ax = b (**) Здесь у насmограничений иnпеременныхх
при с э Rn , x э Rn, b э Rm , A = A(m,n), rankA =m, (m<n),
2.1.1 Общее и отличия в формализациях ЛП и МНК Общее - и МНК и ЛП - разновидности задач оптимизации -и ЛП и МНК применяются для решения задач моделирования но в случае ЛП - мы гораздо больше можем сформулировать разнообразных ЗадМоделирования так как ограничения на область моделирования (неравенства) - естественный элемент ЗЛП - это очень интересно но на это у нас сейчас в курсе времени нет) Отличия - Оптимизацонная постановка МНК определяет функционал задачи мин матричная запись системы условных уравнений-требований в МНК
определяетпереопределенную систему -то есть число ограничений- требований (точек х) к решению - m > n -числа переменныхсистемы, и, то есть, больше чем число искомых параметров при них (то есть размерности вектора А) Т.о. в постановкеМНКмы имеем такуюспецифическую форму задачи оптимизации когда у нас нет допустимых решений - и мы находим наилучшее из недопустимых (дальше мы напомним механизм такого подхода) А вот в задачеЛП когдаmтребов>nпеременных- решения нет иничего найти нельзя так как нетдопустимой области решений. То есть решениеоптимизационной задачи в форме ЗЛПприменимо только принедоопределенной системе типа (0)то есть когдаnпеременных> mтребов Подходы к решению несовместных оптимизационных задач Рассмотрим задачу слинейным ф-лом и ограничениями Ax = b (**) при этом имеем ситуацию mтребов>nпеременных Попытка решать ее через ЗЛП в лоб упирается в несовместность (**) и отсутствие ОДР ввидуm>n Тогда введя в Ax= *= b невязки - вектор у = Ax - b имеем 2 пути решения 1.Вариант типа МНК: Метод безусловной оптимизации при несовместной системе ограничений Сформируем безусловный критерий L=
или правильнее Далее как и в МНК берутся производные Остается вопрос балансировки требований к нашей задаче - 1.минимизации исходного критерия стхи 2. минимизации невязок у = Ax - b Это вопрос выбора парамертров 2.Второй вариант - Использование ЗЛП для оптимизации при несовместной системе ограничений И так - линейный ф-л и ограничения 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 зайцев - осуществляемминимизациюисходного ф-ла Возникаетоднако как и в первом случае необходимо балансироватьисходный критерий стх с требованием мин невязоку - этовопрос выбора вектора коэффициентов Интересен частный случай вышеприведенной задачи -
![]() ![]() Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам... ![]() ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала... ![]() Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все... ![]() ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|