Понятия об оптимизации. Целевая функция. Понятие оптимизации

Понятие об оптимизации многофакторных моделей на основе линейного программирования.

В настоящее время оптимизация находит применение в науке, технике и в любой другой области человеческой деятельности.

Оптимизация - целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.

Поиски оптимальных решений привели к созданию специальных математических методов и уже в 18 веке были заложены математические основы оптимизации (вариационное исчисление, численные методы и др). Однако до второй половины 20 века методы оптимизации во многих областях науки и техники применялись очень редко, поскольку практическое использование математических методов оптимизации требовало огромной вычислительной работы, которую без ЭВМ реализовать было крайне трудно, а в ряде случаев - невозможно.

Постановка задачи оптимизации предполагает существование конкурирующих свойств процесса, например:

· количество продукции - расход сырья

· количество продукции - качество продукции

Выбор компромиcного варианта для указанных свойств и представляет собой процедуру решения оптимизационной задачи. При постановке задачи оптимизации необходимо:

1. Наличие объекта оптимизации и цели оптимизации. При этом формулировка каждой задачи оптимизации должна требовать экстремального значения лишь одной величины, т.е. одновременно системе не должно приписываться два и более критериев оптимизации, т.к. практически всегда экстремум одного критерия не соответствует экстремуму другого. Приведем примеры.

Типичный пример неправильной постановки задачи оптимизации:

«Получить максимальную производительность при минимальной себестоимости».

Ошибка заключается в том, что ставится задача поиска оптимальности 2-х величин, противоречащих друг другу по своей сути.

Правильная постановка задачи могла быть следующая:

а) получить максимальную производительность при заданной себестоимости;

б) получить минимальную себестоимость при заданной производительности;

В первом случае критерий оптимизации - производительность а во втором - себестоимость.

2. Наличие ресурсов оптимизации, под которыми понимают возможность выбора значений некоторых параметров оптимизируемого объекта.

3. Возможность количественной оценки оптимизируемой величины, поскольку только в этом случае можно сравнивать эффекты от выбора тех или иных управляющих воздействий.

4. Учет ограничений.

Обычно оптимизируемая величина связана с экономичностью работы рассматриваемого объекта (аппарат, цех, завод). Оптимизируемый вариант работы объекта должен оцениваться какой-то количественной мерой - критерием оптимальности.

Критерием оптимальности называется количественная оценка оптимизируемого качества объекта.

На основании выбранного критерия оптимальности составляется целевая функция, представляющая собой зависимость критерия оптимальности от параметров, влияющих на ее значение. Вид критерия оптимальности или целевой функции определяется конкретной задачей оптимизации.

Таким образом, задача оптимизации сводится к нахождению экстремума целевой функции.

В зависимости от своей постановки, любая из задач оптимизации может решаться различными методами, и наоборот – любой метод может применяться для решения многих задач. Методы оптимизации могут быть скалярными (оптимизация проводится по одному критерию), векторными (оптимизация проводится по многим критериям), поисковыми (включают методы регулярного и методы случайного поиска), аналитическими (методы дифференциального исчисления, методы вариационного исчисления и др.), вычислительными (основаны на математическом программировании, которое может быть линейным, нелинейным, дискретным, динамическим, стохастическим, эвристическим и т.д.), теоретико-вероятностными, теоретико-игровыми и др. Подвергаться оптимизации могут задачи как с ограничениями, так и без них.Линейное программирование - один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого начала развиваться сама дисциплина «математическое программирование». Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программ) для ЭВМ» не имеет, так как дисциплина «линейное программирование» возникла еще до того времени, когда ЭВМ стали широко применяться при решении математических, инженерных, экономических и др. задач. Термин «линейное программирование» возник в результате неточного перевода английского «linear programming». Одно из значений слова «programming» - составление планов, планирование. Следовательно, правильным переводом «linear programming» было бы не «линейное программирование», а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термин линейное программирование, нелинейное программирование и т.д. в нашей литературе стали общепринятыми.

Итак, линейное программирование возникло после Второй Мировой Войны и стал быстро развиваться, привлекая внимание математиков, экономистов и инженеров благодаря возможности широкого практического применения, а так же математической «стройности».

Можно сказать, что линейное программирование применимо для построения математических моделей тех процессов, в основу которых может быть положена гипотеза линейного представления реального мира: экономических задач, задач управления и планирования, оптимального размещения оборудования и пр.

Задачами линейного программирования называются задачи, в которых линейны как целевая функция, так и ограничения в виде равенств и неравенств. Кратко задачу линейного программирования можно сформулировать следующим образом: найти вектор значений переменных, доставляющих экстремум линейной целевой функции при m ограничениях в виде линейных равенств или неравенств.

Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:

· рационального использования сырья и материалов; задачи оптимизации раскроя;

· оптимизации производственной программы предприятий;

· оптимального размещения и концентрации производства;

· составления оптимального плана перевозок, работы транспорта;

· управления производственными запасами;

· и многие другие, принадлежащие сфере оптимального планирования.

Так, по оценкам американских экспертов, около 75% от общего числа применяемых оптимизационных методов приходится на линейное программирование. Около четверти машинного времени, затраченного в последние годы на проведение научных исследований, было отведено решению задач линейного программирования и их многочисленных модификаций.Первые постановки задач линейного программирования были сформулированы известным советским математиком Л.В.Канторовичем, которому за эти работы была присуждена Нобелевская премия по экономике. Значительное развитие теория и алгоритмический аппарат линейного программирования получили с изобретением и распространением ЭВМ и формулировкой американским математиком Дж. Данцингом симплекс-метода.

В настоящее время линейное программирование является одним из наиболее употребительных аппаратов математической теории оптимального принятия решения. Для решения задач линейного программирования разработано сложное програмное обеспечение, дающее возможность эффективно и надежно решать практические задачи больших объемов. Эти программы и системы снабжены развитыми системами подготовки исходных данных, средствами их анализа и представления полученных результатов.

В развитие и совершенствование этих систем вложен труд и талант многих матеметиков, аккумулирован опыт решения тысяч задач. Владение аппаратом линейного программирования необходимо каждому специалисту в области математического программирования. Линейное программирование тесно связано с другими методами математического программирования (например, нелинейного программирования, где целевая функция нелинейна).

Задачи с нелинейной целевой функцией и линейными ограничениями называют задачами нелинейного программирования с линейными ограничениями. Оптимизационные задачи такого рода можно классифицировать на основе структурных особенностей нелинейных целевых функций. Если целевая функция Е - квадратичная функция, то мы имеем дело с задачей квадратичного программирования; если Е – это отношение линейных функций, то соответствующая задача носит название задачи дробно-линейного программирования, и т.д. Деление оптимизационных задач на эти классы представляет значительный интерес, поскольку специфические особенности тех или иных задач играют важную роль при разработке методов их решения.

Современные методы линейного программирования достаточно надежно решают задачи общего вида с несколькими тысячами ограничений и десятками тысяч переменных. Для решения сверхбольших задач используются уже, как правило, специализированные методы.

Рекомендуемые страницы:

Воспользуйтесь поиском по сайту:

megalektsii.ru

Понятия об оптимизации. Целевая функция. — МегаЛекции

Оптимизация —задача нахождения экстремума (минимума или максимума) целевой функции в некоторой области конечномерного векторного пространства, ограниченной набором линейных и/или нелинейных равенств и/или неравенств.

Методы оптимизации классифицируют в соответствии с задачами оптимизации:

Локальные методы: сходятся к какому-нибудь локальному экстремуму целевой функции. В случае унимодальной целевой функции, этот экстремум единственен, и будет глобальным максимумом/минимумом.

Глобальные методы: имеют дело с многоэкстремальными целевыми функциями. При глобальном поиске основной задачей является выявление тенденций глобального поведения целевой функции.

Целевая функция - Функция, связывающая цель (оптимизируемую переменную) с управляемыми переменными в задаче оптимизации.

В широком смысле целевая функция есть математическое выражение некоторого критерия качества одного объекта (решения, процесса и т.д.) в сравнении с другим. Примером критерия в теории статистических решений является среднеквадратический критерий точности аппроксимации.

Цель – найти такие оценки, при которых целевая функция достигает минимума.Важно, что критерий всегда привносится извне, и только после этого ищется правило решения, минимизирующее или максимизирующее целевую функцию.

Вопрос № 12

Метод градиентный. Метод поиска экстремума.

Градиентные методы оптимизации относиться к численным методам поискового типа. Сущность указанных методов заключается в определении значений независимых переменных, дающих наибольшее изменение целевой функции.

Метод поиска экстремума действительной функции одной переменной на заданном отрезке, в основе метода лежит принцип деления отрезка в пропорциях золотого сечения. Является одним из простейших вычислительных методов решения задач оптимизации.

Описание метода:

Пусть задана функция Тогда для того, чтобы найти определённое значение этой функции на заданном отрезке, отвечающее критерию поиска (пусть это будет минимум), рассматриваемый отрезок делится в пропорции золотого сечения в обоих направлениях, то есть выбираются две точки Х1 и Х2, такие что где - пропорция золотого сечения.

Вопрос №13

Симплексный метод поиска экстремума.

Симплекс-метод-алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве.

Задача линейного программирования состоит в том, что необходимо максимизировать или минимизировать (экстремум) некоторый линейный функционал на многомерном пространстве при заданных линейных ограничениях.

Последовательность вычислений симплекс-методом можно разделить на две основные фазы:

-нахождение исходной вершины множества допустимых решений,

-последовательный переход от одной вершины к другой, ведущий к оптимизации значения целевой функции.

При этом в некоторых случаях исходное решение очевидно или его определение не требует сложных вычислений, например, когда все ограничения представлены неравенствами вида «меньше или равно» (тогда нулевой вектор совершенно точно является допустимым решением, хотя и, скорее всего, далеко не самым оптимальным). В таких задачах первую фазу симплекс-метода можно вообще не проводить. Симплекс-метод, соответственно, делится на однофазный и двухфазный.

Вопрос №14

Рекомендуемые страницы:

Воспользуйтесь поиском по сайту:

megalektsii.ru

Понятие о задаче оптимизации.

Возможность применени теории оптимизации и обучению нейронных сетей крайне привлекательна, так как имеется множество хорошо опробованных методов оптимизации, доведенных до стандартных компьютерных программ. Сопоставление процесса обучения с процессом поиска некоторого оптимума также не лишено и биологических оснований, если рассматривать элементы адаптации организма к окружающим условиям в виде оптимального количества пищи, оптимального расходования энергии и т.п. Подробное рассмотрение методов оптимизации выходит за рамки данных лекций, поэтому здесь мы органичимся лишь основными понятиями. Для более подробного знакомства можно порекомендовать книгу Б.Банди.

Функция одной действительной переменной f(x) достигает локального минимума в некоторой точке x0, если существует такая d -окрестность этой точки, что для всех x из этой окрестности, т.е. таких, что | x - x0 | < d, имеет место f(x) > f(x0).

Без дополнительных предположений о свойствах гладкости функции выяснить, является ли некоторая точка достоверной точкой минимума, используя данное определение невозможно, поскольку любая окрестность содержит континуум точек. При примененнии численных методов для приближенного поиска минимума исследователь может столкнуться с несколькими проблемами. Во-первых, минимум функции может быть не единственным. Во-вторых, на практике часто необходимо найти глобальный, а не локальный минимум, однако обычно не ясно, нет ли у функции еще одного, более глубокого, чем найденный, минимума.

Матем. определение локального минимума функции в многомерном пространстве имеет тот же вид, если заменить точки x и x0 на вектора, а вместо модуля использовать норму. Поиск минимума для функции многих переменных (многих факторов) является существенно более сложной задачей, чем для одной переменной. Это связано прежде всего с тем, что локальное направление уменьшения значения функции может не соответствовать направлению движения к точке минимума. Кроме того, с ростом размерности быстро возрастают затраты на вычисление функции.

Решение задачи оптимизации во многом является искусством, общих, заведомо работающих и эффективных в любой ситуации методов нет. Среди часто использемых методов можно рекомендовать симплекс-метод Нелдера, некоторые градиентные методы, а также методы случайного поиска. В Приложении 2 для решения задачи оптимизации рассматриваются методы имитации отжига и генетического поиска, относящиеся к семеству методов случайного поиска.

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

Для комбинаторных задач также существуют методы поиска приближенного решения, предлагающие некоторую стратегию перебора точек, сокращающую объем вычислительной работы. Отметим, что имитация отжига и генетический алгоритм также применимы и к комбинаторной оптимизации.

studfiles.net

Основные понятия теории оптимизации.

Количество просмотров публикации Основные понятия теории оптимизации. - 137

Говорят, что функция F(x) имеет в т. х*(х1,х2, … , хn) локальный максимум (минимум), в случае если существует такая окрестность т. х*, в которой для любого х выполняется неравенство F(x) ≤ F(x*) (F(x) ≥ F(x*)).

F(x) 1 – точки локального максимума;

1 Fmax 2 – точки локального минимума.

2 Точки локального максимума и

локального минимума называют

Fmin точками экстремума.

Необходимое условие экстремума:чтобы F(x) имела в т. х* экстремум крайне важно , чтобы ∂F(x*)/∂xj = 0, .

Достаточное условие экстремума: если F(x) в т. х* имеет ∂F(x*)/∂xj = 0, , то чтобы в этой точке F(x) имела экстремум достаточно, чтобы квадратичная форма

была положительно (минимум) или отрицательно (максимум) определена.

Очевидно, что точки локального экстремума могут не давать наибольшего или наименьшего значений функции в некоторой области, кроме того, их должна быть несколько. Большое значение в этой связи приобретает понятие выпуклости множества допустимых значений и выпуклости (вогнутости) функции.

Множество S принято называть выпуклым, в случае если для любых двух точек этого множества оно содержит и отрезок, соединяющий эти точки:

Функция F(x), определенная на выпуклом множестве S, выпукла, в случае если ее график целиком лежит ниже (не выше) отрезка, соединяющего любые две точки графика:

Функция F(x), определенная на выпуклом множестве S, вогнута͵ если ее график целиком лежит выше (не ниже) отрезка, соединяющего любые две точки графика:

Теорема 1:пересечение выпуклых множеств является выпуклым множеством.

Теорема 2: сумма выпуклых функций является выпуклой функцией,

сумма вогнутых функций – вогнутой функцией.

Теорема 3 (основное свойство выпуклых задач):

Всякий локальный оптимум является глобальным.

Теорема Вейерштрасса:

Непрерывная функция, определенная на непустом замкнутом

ограниченном множестве, достигает максимума (минимума) по

крайней мере в одной точке этого множества.

Из сказанного можно определить общий принцип решения задач оптимизации: максимум (минимум) F(x) при х, принадлежащих замкнутому допустимому множеству, в случае если оно существует, является либо точкой экстремума, либо граничной точкой допустимого множества, либо и тем и другим одновременно.

При численных расчетах часто крайне важно использовать еще два важных понятия.

Вектор, указывающий направление наискорейшего возрастания функции, принято называть градиентом функции grad F(x) = (∂F/∂x1, … ,∂F/∂xn). Противоположный ему вектор называют антиградиентом, он указывает направление наискорейшего убывания функции.

Линией уровня (или линией равного значения) функции F(x) называют геометрическое место точек, координаты которых удовлетворяют уравнению F(x) = Const.Линия уровня и вектор градиент в каждой точке взаимно перпендикулярны.

referatwork.ru