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