Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







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





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

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

 

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

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

 







ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...

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

ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...

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





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


©2015- 2024 zdamsam.ru Размещенные материалы защищены законодательством РФ.