6. Методы нелинейного программирования и многокритериальной оптимизации. Методы нелинейной оптимизации
Классификация методов нелинейной оптимизации
В настоящее время не существует универсальных методов оптимизации, пригодных для решения задач произвольного вида. В связи с этим ведется постоянная работа в направлении совершенствования и разработок алгоритмов нелинейной оптимизации, которые можно классифицировать:
по наличию ограничений на методы
по способу поиска экстремальной точки на методы
прямого поиска - основаны на сравнении вычисленных значений
в различных точках.косвенного поиска - основаны на стремлении, найти решение задачи оптимизации, не исследуя промежуточные точки, удаленные от оптимума.
Основным достоинством методов прямого поиска является то, что с их помощью можно решать задачи с разрывной целевой функцией. Однако эти вычисления занимают много вычислительных ресурсов и часто не позволяют найти оптимальное решение с необходимой точностью.
по количеству независимых переменных на методы
по способу вычисления производных на методы
по способу определения направления поиска на методы
нулевого порядка – методы прямого поиска
первого порядка – используют для вычисления направления поиска значение первых производных (градиент функции
или Якобиан системы уравнений
)второго порядка – используют для вычисления направления поиска производные второго порядка (матрица Гессе
)
Основы вычислительной алгебры
Векторная и матричная норма
Определение нормы
Нормой в 
на, удовлетворяющая условиям:, причем
, если
Виды норм
илиsup-норма:
или норма наименьших абсолютных разностей:
или норма наименьших квадратов – евклидова норма
норма порядка
Матричная норма
Представим матрицу 
,
тогда можно применить к матрице любую из векторных норм. Например, евклидова норма:
Определенность матриц.
Скалярная функция 
-переменных называется квадратичной формой, если:
,
где 
- некоторая матрица,
- вектор переменных.
Положительно определенная матрица
Матрица 
является положительно определенной тогда и только тогда, когда значение квадратичной формы
,
.
Пример:
Положительно полуопределенная матрица
Матрица 
,
и
, такой что
.Пример:
Отрицательно определенная матрица
Матрица 
является отрицательно-определенной, если –
- положительно определенная матрица.
Пример:
Отрицательно полуопределенная матрица
Матрица 
является отрицательно-полуопределенной, если -– положительно полуопределенная матрица.
Пример:
Неопределенная матрица
Матрица 
Пример:
Критерий Сильвестра для проверки определенности матрицы
Для проверки определенности (полуопределенности) служит критерий Сильвестра:
Матрица положительно определена, если:
Матрица отрицательно определена, если:
все диагональные элементы матрицы отрицательны;
все угловые миноры матрицы имеют чередующиеся знаки, начиная со знака "-".
Матрица положительно полуопределена, если значения диагональных элементов и главных миноров матрицы неотрицательны.
Матрица неопределенна, если элементы главной диагонали имеют разные знаки.
studfiles.net
Нелинейное программирование оптимизация, методы - Справочник химика 21
Локальные задачи оптимизации — это задачи нелинейного программирования с ограничениями. Для их решения можно использовать методы, изложенные в разд. У.4. [c.226]Для решения задач 1-6 используют методы нелинейного стохастического программирования, методы статистической оптимизации, методы статистического моделирования и тео- [c.126]
В такой формулировке задача синтеза — это задача нелинейного программирования с параметрами оптимизации Р к Т, критерием оптимизации 3 с Л т ограничениями типа равенств, которые решаются относительно зависимых температур потоков. Поэтому для решения задачи синтеза могут быть применены методы нелинейного программирования, которые позволяют найти т1п 3 по целочисленным параметрам Му, Р к по непрерывным параметрам Т. Назовем такой подход к решению задачи синтеза прямым подходом. [c.146]
Рассмотренные в главе IX методы нелинейного программирования предназначены для решения задач оптимизации с критерием оптимальности, сформулированным как нелинейная функция независимых переменных, на допустимую область изменения которых накладываются ограничения, имеющие вид равенств или неравенств, возможно также нелинейного вида. Как правило, решение подобных задач методами нелинейного программирования требует значительного объема вычислений и сопряжено с определенными трудностями, обусловленными особенностями целевой функции и ограничений. [c.547]
Применение классических методов математического анализа и вариационного исчисления для оптимизации химических реакторов наталкивалось на значительные затруднения, связанные с наличием в реальных задачах ограничений на фазовые и управляющие переменные. Аналогичные трудности возникали при постановке оптимальных задач в других областях науки и техники. Это способствовало развитию таких мощных методов, как метод динамического программирования принцип максимума методы нелинейного программирования 2о-22 [c.10]
Для оптимизации химических реакторов широкое применение должны найти методы нелинейного программирования. Общие вопросы использования этих методов обсуждаются в ряде работ С использованием указанных методов рассмотрены вопросы оптимизации систем, описываемых обыкновенными дифференциальными уравнениями [c.11]
Оптимизация без математической модели. В данном случае оптимальный режим находится поиском на объекте На объект подают искусственные возмущения и на основании анализа их результатов последовательно улучшают режим работы процесса. Для поиска оптимального режима используют один из методов нелинейного программирования, причем математической моделью здесь служит сам объект. Важным частным случаем являются системы экстремального регулирования [c.20]
Следующий важный этап оптимизации химических реакторов — выбор метода расчета оптимальных режимов. Широкое распространение получили как классические методы математического анализа и вариационного исчисления, так и новые методы — принцип максимума динамическое и нелинейное программирование. В системе автоматической оптимизации время расчета оптимальных режимов Тр должно быть существенно меньше среднего времени между двумя последовательными возмущениями, т. е. [c.21]
Первая группа методов, в свою очередь, делится на непрямые (блок 5, рис. 1) и прямые (или методы спуска) (блок 4, рис. 1). Разберем прежде всего прямые методы. В большинстве случаев при решении задач оптимизации управляющие переменные принимаются независимыми. Известно [3], что в этом случае задача оптимизации сложных схем сводится к следующей задаче нелинейного программирования найти минимум функции [c.12]
Особенности сопряженного процесса при наличии дополнительных ограничений. Дополнительные ограничения на переменные схемы могут быть учтены в алгоритме оптимизации обычными методами, принятыми в теории нелинейного программирования. В ряд случаев, однако, удается предусмотреть учет дополнительных ограничений непосредственно в конструкции сопряженного процесса. [c.149]
Рост сложности и размерности этих задач, особенно задач 2-го класса, требует применения наиболее эффективных (как по быстродействию, так и по надежности определения наилучшего решения) методов оптимизации, позволяющих решать эти задачи в реальное время. Гибкость и универсальность поисковых методов оптимизации, относящихся к классу численных методов нелинейного программирования, сделали их основным средством решения задач 1-го класса и существенной частью алгоритмов решения задач 2-го класса. В последнее время такие методы получили большое развитие, особенно это относится к квазиньютоновским методам, и к методам оптимизации больших систем. Основное внимание в книге уделяется этим методам и опыту их использования для оптимизации ХТС. Вместе с тем комбинаторная природа задач синтеза ХТС требует применения методов дискретной математики, использованию которых также уделено большое внимание. [c.5]
В книге в доступной форме изложены основы методов оптимизации химических производств (классический анализ, вариационное исчисление, принцип максимума, динамическое, линейное, нелинейное и геометрическое программирование). Сформулированы общие положения, касающиеся выбора критериев оптимальности химико-технологических процессов, и приведены их математические модели. Рассмотрены задачи оптимизации конкретных процессов. Второе издание (первое издание выпущено в 1969 г.) дополнено изложением основ геометрического программирования, а также примерами, иллюстрирующими практическую реализацию методов нелинейного программирования. [c.4]
Задача оптимизации глобальной схемы будет иметь вид (VI, 27). Поскольку в этом случае все переменные являются непрерывными, для решения могут быть использованы хорошо разработанные численные методы нелинейного программирования (см. гл. III, IV). Ясно, что в результате решения могут быть получены нецелочисленные значения а , принимающие любые значения в интервале (VI, 26). Если условия задачи допускают любые значения структурных параметров в интервале (VI, 26), то полученный результат будет решением первоначальной задачи (VI, 5). При этом, если какие-либо структурные параметры при k = k ,. . kj/, s = 1, примут нецелые значения, то на /-том выходе -го блока необходимо поставить делитель потока, а на входных потоках блоков. . ., кр смесители. В дальнейшем этот метод будем называть методом структурных параметров (МСП). Рассмотренный подход выглядит очень заманчивым, поскольку позволяет сводить многомерную комбинаторную задачу к задаче нелинейного программирования. Особенности этой задачи состоят в следующем [c.204]
Как обычно, структурные параметры являются непрерывными переменными, удовлетворяющими соотношениям (1, 7), (VI, 26). Давая структурным параметрам определенные значения, можно из глобальной получить любую заданную ТС (без рециклов), а после проведения оптимизации глобальной схемы, получить схему ТС, наилучшую из всех возможных. Поскольку в глобальной схеме все поисковые переменные (структурные и технологические) непрерывны, для ее оптимизации могут быть использованы численные методы нелинейного программирования. После решения задачи оптимизации глобальной схемы ТС будут получены какие-то значения структурных параметров (вообще говоря, нецелые). Однако, если условия задачи разрешают разветвления потоков, это не страшно если структурные параметры, соответствующие какому-либо потоку, окажутся нецелыми, на нем надо ставить делитель потоков. Если же разветвление потоков не разрешается, необходимо потребовать целочисленность структурных параметров. В этом случае, также как и при использовании обычной глобальной схемы, [c.223]
Сравним теперь 1-й и 2-й подходы с методом структурных параметров. Будем считать, что Л/ = М и что число стадий т в глобальной схеме ТС, используемой в методе структурных параметров и во 2-м подходе, равно числу п элементарных потоков, на которые разбивают исходные потоки в 1-м подходе. Тогда при использовании метода структурных параметров задача синтеза ТС сведется к задаче нелинейного программирования с числом переменных 7 = = ЗпЫ -Ь ЗЫ. При использовании 1-го подхода на каждой итерации потребуется решить задач оптимизации размерности 4 и одну задачу оптимизации размерности 4/гЛ . При использовании [c.224]
Известен ряд работ, где для управления процессом ферментации используют оптимальные подпитки субстратом в ходе периодического процесса ферментации [3, 28], оптимальный температурный профиль [23, 27], изменения рОг среды в течение режима ферментации [25]. При рещении указанных задач применяют такие методы оптимизации, как принцип максимума Понтрягина, динамическое, нелинейное программирование. [c.33]
Заслуживают внимания прямые методы решения задач оптимизации функционалов (см. главу V, стр. 232), обычно позволяющие свести исходную вариационную задачу к задаче нелинейного программирования, решить которую иногда проще, чем краевую задачу для уравнений Эйлера. [c.32]
По существу метод динамического программирования представляет собой алгоритм определения оптимальной стратегии управления на всех стадиях процесса. При этом закон управления на каждой стадии находят путем решения частных задач оптимизации последовательно для всех стадий процесса с помощью методов исследования функций классического анализа или методов нелинейного программирования. Результаты решения обычно не могут быть выражены в аналитической форме, а получаются в виде таблиц. [c.32]
Решение задачи оптимизации существенно усложняется, когда критерий оптимальности является функцией нескольких независимых переменных даже при известном аналитическом выражении этой функции. Наибольшие трудности возникают при отсутствии непрерывности у всех или некоторых производных оптимизируемой функции. В последнем случае для решения оптимальной задачи целесообразно использовать методы нелинейного программирования (см. главу IX).. [c.97]
В настоящее время для решения подобных задач разработано и применяется довольно значительное число методов. Однако пока еще не представляется возможным отдать предпочтение какому-либо одному из них. Это объясняется, прежде всего, тем, что практически каждая конкретная задача оптимизации, сводящаяся к задаче нелинейного программирования, обладает присущими только ей особенностями, позволяющими с наибольшим успехом применить тот или иной метод решения. Более того, обычно заранее даже нельзя сказать определенно, какой из методов окажется в данном случае более эффективным. [c.476]
Вместе с тем, владение методами нелинейного программирования нужно не только как самоцель, но также и в связи с использованием таких методов оптимизации, как динамическое программирование или принцип максимума, в которых на различных этапах приходится решать задачи нелинейного программирования. [c.476]
В предыдущих главах неоднократно встречались случаи, когда при использовании того или иного метода решения задачи оптимизации, например принципа максимума- или динамического программирования, на некоторых этапах их применения возникала необходимость решения типичной задачи нелинейного программирования. [c.545]
ЧИСЛЕННОЕ РЕШЕНИЕ ЗАДАЧ ОПТИМИЗАЦИИ МЕТОДАМИ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ, РЕШЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ В ФОРМЕ НЕЛИНЕЙНОГО АЛГЕБРАИЧЕСКОГО УРАВНЕНИЯ) [c.76]
Приведенные выше задачи оптимизации надежностп ХТС являются задачами целочисленного нелинейного программирования с линейными или нелинейными ограничениями в виде неравенств. Предложены различные методы решения основных задач оптимизации резервирования технических систем, которые рассмотрены в разделе 8.2. Все указанные методы решения основных задач оптимизации резервирования ХТС и различных технических систем [2, 7, 231, 237] являются одноуровневыми. Они учитывают влияние включения резервных элементов на повышение надежности системы без использования обобщенных технико-экономических показателей. В качестве КЭ оптимального резервирования в данных методах используются лишь капитальные затраты на резервные элементы системы или величина Р(Х). [c.204]
Система включает следующие подсистемы и пакеты программ (рис. 7.37) пакет проблемно-ориентированных прикладных программ — математических моделей типовых процессов низкотемпературного газоразделения и энергетических подсистем подсистему расчета волюметрических, термодинамических, транспортных свойств и эксергии многокомпонентных смесей легких углеводородов и неуглеводородных газов на основе уравнения состояния Бенедикта—Вебба—Рубина программы пользователя — математическую модель исследуемой ЭТС, включающую модели тех-но.яогических и энергетических подсистем и использующую модули всех остальных подсистем и пакетов методо-ориентирован-ную интерактивную подсистему оптимизации, базирующуюся на методах нелинейного программирования программы методов вычислительной математики, используемых при построении моделей сервисное математическое обеспечение. [c.418]
В книге в доступной форме изложены основы методом оптимизации (классический анализ, вариационное исчисление, принцип максимума, динамическое, линейное и нелинейное программирование) с иллюстрацией их на объектах химической технологии. Сформулированы общие положения, касающиеся выбора критериев о[1ти-мальности химико-технологических процессов, и приведены их математические модели. Рассмотрены задачи, связанные с оптимизацией конкретных процессов. [c.4]
Названием методы нелинейного программирования объединяется большая группа численных методов, многие из которых приспособлены для репгения оптимальных задач соответствующего класса. Выбор того или иного метода обусловлен сложностью вычисления критерия оптимальности и сложностью ограничивающих условий, необходимой точностью решения, мощностью имеющейся машины и т. д. Ряд методов нелинейного программирования практически постоянно используется в сочетании с другими методами оптимизации, как, например, метод сканирования (см. главу IX, стр. 551) в динамическом программировании. Кроме того, эти методы служат основой построения систем автоматической оптими- [c.33]
Рецептура товарного бензина основывается на показателях качества имеющихся компонентов и задании заводу по выпуску отдельных марок бензинов. Находят наиболее целесообразное и экономически выгодное соотношение компонентов для каждой иартпи бензина. Задача оптимизации компонентного состава товарных бензинов решается с помощью ЭВМ методом линейного или нелинейного программирования. С помощью ЭВМ при оптимизации учитывают наибольшее число факторов. [c.159]
Функция желательности. Задачу оптимизации процессов, ха-ракгеризующихся несколькими откликами, обычно сводят к задаче оптимизации по одному критерию с ограничениями в виде равенств или неравенств. В зависимости от вида поверхности отклика и ха-ракгера ограничений для оптимизации предлагается использовать методы неопределенных множителей Лагранжа, линейного и нелинейного программирования, ридж-анализ [10] и др. К недостаткам этих способов решения задачи оптимизации следует отнести вычислительные трудности. В частности, при описании поверхности отклика полиномами второго порядка решение задачи на условный экстремум с применением неопределенных множителей Лагранжа приводит к необходимости решать систему нелинейных уравнений. Поэтому одним из наиболее удачных способов решения задачи оптимизации процессов с большим количеством откликов является использование предложенной Харрингтоном [23] в качестве обобщенного критерия оптимизации так называемой обобщенной функции желательности О. Для построения обобщенной функции желательности О предлагается преобразовать измеренные значения от- [c.207]
Методы структурной оптимизации. Они предполагают на первом этапе определение способов реализации химического производства (выбор альтернативных способов ведения процесс на отдельных стадиях) и создание на их основе некоторой интегрально-гипотетической технологической схемы, включающей все возможные варианты распределения материальных и энергетических ресурсов. Оптимизация ведется по специально определенным структурным параметрам распределения потоков, значения которых обычно задаются в диапазоне от О до 1 и характеризуют разделение или разветвление некоторого выходного потока. Конечные значения параметров и определяют технологическую схему. Нулевые значения отдельных из них свидетельствуют об отсутствии соответствующей связи аппаратов. С математической точки зрения задача синтеза представляет собой решение систем нелинейных уравнений, соответствующих описанию отдельных элементов (подсистем), и уравнений, отражающих структурные взаимосвязи между этими элементами (подсистемами). Основными методами решения являются методы нелинейного программирования. В виду высокой размерности системы уравнений поиск оптимального решения (технологической схемы) представляет определенные трудности вследствие многоэкстремальности и нелинейности задачи. [c.438]
Если потребитель желает создать новый кристаллизатор для обеспечения мощности своего иредприятпя, то обычно для оптимизации используются параметры первой группы. Так как параметры первой группы являются непрерывными, то задача поиска (диаметра сечения, высоты кристаллизатора и т. д.) конструктивных параметров кристаллизатора, отвечающего заданной производительности, решается методами нелинейного программирования, кратко описанных выше, обеспечивающих минимум целевой функции 9 . Наибольшие трудности возникают в задачах оптимизации, где в качестве дискретно изменяющихся оптимизируемых параметров являются параметры, принадлежащие группам 2—4. [c.364]
Оптимизация вида адсорбционной схемы. Технологические схемы адсорбционных установок с оптимальными свойствами могут быть синтезированы путем последовательного применения методов нелинейного программирования для множества технологических графов, отображающих различные структурные состояния технологической схемы адсорбционной установки. Эта наиболее общая задача оптимизации адсорбционной установки должна решаться с учетом как иерархической взаимосвязи между подзадачами оптимизации параметров элементов оборудования, агрегатов и установки в целом, так и алгоритмических особенностей оптимизации непрерывно и дискретно изменяющихся параметров. Соответственио в методике решения задачи синтеза оптимальных схем адсорбционных установок должны быть итерационно взаимосвязаны алгоритм нелинейного математического программирования, принятый для оптимизации непрерывно изменяющихся концентрационных, термодинамических и расходных параметров установки алгоритм дискретного нелинейного программирования, с помощью которого осуществляется оптимизация дискретно изменяющихся конструктивно-компо-новочных параметров элементов оборудования и агрегатов установки алгоритм оптимизации вида технологической схемы установки с учетом технических и структурных ограничений. [c.149]
Для оптимизации достаточно большой группы параметров, которые характеризуют количество элементов оборудования и связей, имеюших сходное назначение в технологической схеме установки, разработан метод, основанный на обеспечении неизменности структурных условий- задачи в процессе оптимизации [62, 63]. Здесь использована возможность представления структуры схемы и компоновочных взаимосвязей между ее элементами характерными граничными значениями непрерывно изменяющихся параметров. Используется максимально сложная исходная схема установки, а промежуточные варианты схемы в процессе ее оптимизации образуются как ее части. Достижение некоторыми непрерывно изменяющимися параметрами своих граничных (нулевых) значений означает частичное вырождение максимально сложной схемы в промежуточную, а затем и в оптимальную схему установки. Благодаря эквивалентированию изменений дискретных параметров максимально сложной схемы изменениями непрерывно изменяющихся параметров для оптимизации вида схемы может быть использован один из эффективных алгоритмов нелинейного программирования. При такой постановке задачи возможна одновременная оптимизация (без подразделения на этапы) непрерывно изменяющихся параметров и группы дискретно изменяющихся параметров. [c.150]
Книга посвящена актуальному в настоящее время вопросу применения математических методов для расчета оптимальных (наилучших) режимов технологических процессов. Дана характеристика основных этапов работ по статической, квазистатической и динамической оптимиаации как действующих химических реакторов, так и при их проектировании. Сопоставлены два важнейших метода оптимизации — метод поиска на объекте и метод оптимизации с помощью математической модели. Большое внимание уделено математическим способам оптимизации — нелинейному программированию и Принципу максимума. [c.4]
Оадача оптимизации статических режимов работы реакторов со стационарным слоем катализатора сформулирована в общем виде в главе П. Для решения поставленной задачи в этой главе применим методы нелинейного программирования. [c.96]
Однако преимущество 1-го и 2-го подходов состоит не только в уменьшении размерности экстремальных задач, но и связано с проблемой многоэкстремальности. Метод структурных параметров приводит обычно к многоэкстремальной задаче [122], что связано, по-видимому, с тем, что в глобальную схему включены все возможные варианты схем ТС. Выбор той или иной структуры определяется решением задачи нелинейного программирования. В то же время при 1-м и 2-м подходах основная тяжесть выбора структуры ложится на решение задачи о назначениях, а с помощью метода нелинейного программирования приходится решать задачу оптимизации ТС, фиксированной структуры. Конечно, полностью избавиться от многоэкстремальности не удается, поскольку даже задача оптимизации ТС фиксированной структуры часто оказывается многоэкстремальной. [c.224]
Аоки М. введение в методы оптимизации Основы и приложения нелинейного программирования. М. Наука. Гл. ред. физ.-мат. лит., 1977. 344с. [c.268]
Данный алгоритм реализует метод Гаусса — Зейделя нелинейного программирования с ограничениями типа неравенств на параметры оптимизации. Размерность оптимизируемого вектора Ут равна 2 для аппаратов типа А Ут = (Сх, ) или 1 для ап паратов типа В и С Ут = ((3х). П > решении аадачи статической оптимизации в качестве критерия оптимальности принимаются приведенные годовые затраты (Я), а при решении задачи приближения — разность между значениями длины трубчатки конденсатора, соответствующей набору Ук, УС, Ф, задаваемым технологическим параметрам X, текущему значению вектора Ут и значением нормализованной длины трубчатки,, к которому осуществляется приближение варьированием координат вектора Ут. Таким образом, в данной постановке алгоритм должен минимизировать выбранные критерии оптимизации. [c.136]
Задача оптиналь ого выбора средств измерения ддя указанного класса моделей может быть репена с использованием метода нелинейного программирования, (формулируем для атого критерий оптимизации и соответствущие ограничения. [c.92]
Методы оптимизации режимов ЭЭС имеют уже большую историю [99], начало которой относится к концу прошлого столетия, когда появились первые сравнительно непротяженные электрические системы. В СССР одними из первых здесь были работы H.A. Сахарова [194] и Б.Л. Шифринсона, опубликованные в 1927 и 1930 гг. и посвященные наивыгоднейшему распределению нагрузки между параллельно работающими генераторами и электрическими станциями. Позднее, особенно в послевоенные годы, в связи с созданием и развитием объединенных ЭЭС стали активно разрабатываться теория и методы управления сложными ЭЭС, базирующиеся на использовании современных методов линейной и нелинейной алгебры, теории графов, нелинейного программирования и ЭВМ [5, 28, 45, 58, 98, 99, 101, 119, 187, 191, 202, 203 и др.]. [c.231]
chem21.info
6. Методы нелинейного программирования и многокритериальной оптимизации
6.1. Постановка задачи нелинейного программирования
В общем виде задача нелинейного программирования (ЗНП) формируется следующим образом:
f (x1, x2, ..., xn) max (min) (6.1)
gi (x1, x2 ..., xn bi, i=1, m1
gi (x1, x2 ..., xn bi, i=m1+1, m2
(6.2) ... ... ... ... ... ... ... ... ... ... ...
gi (x1, x2 ..., xn bi, i=m2+1, m2
где xj - управляющие переменные или решения ЗНП, j=1, n;
bi - фиксированные параметры, i=1, m;
f, gi, i=1, n - заданные функции от n переменных.
Если f и gi линейны, то (6.1), (6.2) проходит в задачу линейного программирования.
Решить задачу нелинейного программирования - это значит найти такие значения управляющих переменных xj, j=1, n, которые удовлетворяют системе ограничений (6.2) и доставляют максимум или минимум функции f.
Для задачи нелинейного программирования, в отличие от линейных задач, нет единого решения. В зависимости от вида целевой функции (6.1) и ограничений (6.2) разработано несколько специальных методов решения, к которым относятся методы множителей Лагранжа, квадратичное и выпуклое программирование, градиентные методы, ряд приближенных методов решения, графический метод. Заметим, что нелинейное моделирование экономических задач часто бывает довольно искусственным. Большая часть экономических проблем сводится к линейным моделям.
6.2. Постановка задачи динамического программирования. Основные условия и область применения.
В ряде реальных экономических и производственных задач необходимо учитывать изменение моделируемого процесса во времени и влияние времени на критерий оптимальности. Для решения указанных задач используется метод динамического планирования (программирования). Этот метод более сложен по сравнению с методами расчета статических оптимизационных задач. Также не простым делом является процесс построения для реальной задачи математической модели динамическою программирования.
Пусть рассматривается задача, распадающаяся на m шагов или этапов, например планирование деятельности предприятия на несколько лет, поэтапное планирование инвестиций, управление производственными мощностями в течение длительного срока. Показатель эффективности задачи в целом обозначим через W, а показатели эффективности на отдельных шагах - через i, i=1, m. Если W обладает свойством аддитивности, т.е.:
(6.3)
можно найти оптимальное решение задачи методом динамического программирования.
Таким образом, динамическое программирование - это метод оптимизации многошаговых или многоэтапных процессов, критерий эффективности которых обладает свойством (6.3).
В задачах динамического программирования критерий эффективности называется выигрышем. Данные процессы управляемые, и от правильного выбора управления зависит величина выигрыша.
Переменная хi, от которой зависят выигрыш на i-м шаге и, следовательно, выигрыш в целом, называются шаговым управлением i=1, m.
Управлением процесса в целом (х) называется последовательность шаговых управлений х=(х1, х2, ..., хi, ..., хm).
Оптимальное управление х - это значение управления х, при котором значение W(x) является максимальным (или минимальным, если требуется уменьшить проигрыш)
W=W(x)=max W(x)
xX, (6.4)
где X - область допустимых управлений.
Oптимальное управление xопределяется последовательностью оптимальных шаговых управлений: x = (x1, x, ..., xi, ..., xm).
В основе метода динамического программирования лежит принцип оптимальности Беллмана, формулирующийся следующим образом: управление на каждом шаге надо выбирать так, чтобы оптимальной была сумма выигрышей на всех оставшихся до конца процесса шагах, включая выигрыш на данном шаге.
Поясним это правило. При решении задач динамического программирования на каждом шаге выбирается управление, которое должно привести к оптимальному выигрышу. если считать все шаги независимыми друг от друга, то оптимальным шаговым управлением будет то управление, которое приносит максимальный выигрыш именно на данном шаге. Но, например, при покупке новой техники взамен устаревшей, на ее приобретение затрачиваются определенные средства. Поэтому прибыль от ее эксплуатации вначале может быть небольшой. Однако в следующие годы новая техника будет приносить большую прибыль. И наоборот, если руководитель примет решение оставить старую технику для получения прибыли в текущем году, то в дальнейшем это приведет к значительным убыткам. Данный пример демонстрирует следующий факт: в многошаговых процессах все шаги зависят друг от друга, и, следовательно, управление на каждом конкретном шаге надо выбирать, с учетом его будущих воздействий на весь процесс.
Другой момент, который следует учитывать при выборе управления на данном шаге, - это возможные варианты окончания предыдущего шага. Эти варианты определяют состояние процесса. Например, при определении количества средств в i-ом году, необходимо знать, сколько средств осталось в наличии к этому году, и какая прибыль получена в предыдущем (i-1)-ом году.
studfiles.net
6.2. Прямые методы одномерной оптимизации нелинейных функций без ограничений
Пусть на множестве UєR определена функцияF(X). Подминимизацией функции F(X)на множествеUбудем понимать решение следующей задачи: найти хотя бы одну точку минимумаx* и минимумF*=F(X*)этой функции на множествеU.
Многие приближенные методы минимизации применимы только тогда, когда любой локальный минимум F(X)является одновременно и глобальным. Один из классов функций, удовлетворяющих этому условию, является классунимодальных функций.
Функция F(X) называетсяунимодальнойна отрезке [a;b], если она непрерывна на [a;b] и существуют числа α и β,a≤α≤β≤b,такие, что:
если a<α,то на отрезке [a;α]F(X)монотонно убывает;
если β<b,то на отрезке [β;b]F(X)монотонно возрастает;
при x є [α;β].
Для проверки унимодальности функции F(X)на практике обычно используют следующие критерии:
если функция F(X)дифференцируема на отрезке [a;b]и производная F(X)не убывает на этом отрезке, тоF(X)) унимодальна;
если функция F(X)дважды дифференцируема на отрезке [a;b] и F(X))≥0 при xЕ [a;b], то F(X)) также унимодальна.
Большую группу приближенных методов минимизации функций составляют прямые методы минимизации, основанные на вычислении только значений минимизируемой функции в некоторых точках и не использующие значений ее производных.
Метод перебора (пассивный поиск) является простейшим из прямых методов минимизации. ПустьF(X)унимодальна, и требуется найти какую-либо из точек минимумаx* функцииF(X)на отрезке [a;b] с абсолютной погрешностью ε>0. Разобьем [a;b] наn равных частей точками деленияXi=a+i(b-a)/n, i=0, 1, 2, …, n, гдеn≥(b-a)/ε. Вычислив значенияF(X) в этих точках, путем сравнения найдем точкуxm, для которой
F(Xm)=min F(Xi). (6.1)
0≤ i≤ n
Далее полагаем x*=xm, F*=F(Xm).При этом максимальная погрешностьεn определения точкиX*равна εn=(b-a)/n.
Метод деления отрезка пополам(метод дихотомии) является простейшим последовательным методом минимизации. Он позволяет для любой унимодальной функцииF(X)построить последовательность вложенных отрезков [a;b] [a1;b1] … [an-1;bn-1] [an;bn], каждый из которых содержит хотя бы одну из точек минимумаX*функцииF(X).
Пусть ε>0 – требуемая точность определения точки X*.Выбрав δ=2ε, построим последовательности {an}, {bn}, {X1(n)}, {X2(n)},n=0, 1, … ,используя рекуррентные формулыa0=a, b0=b;
x1(n-1)=(an-1+ bn-1- δ)/2, x2(n-1)=(an-1+ bn-1+ δ)/2; ( 6.2)
an =an-1, bn = x2(n-1), если f(x1(n-1))≤ f(x2(n-1)),
an = x1(n-1), bn = bn-1, если f(x1(n-1))> f(x2(n-1)).
Переход от отрезка [an-1; bn-1] к отрезку [an; bn] методом деления отрезка пополам иллюстрируется на на рис.3, еслиF(X1(n-1))< F(X2(n-1)),рис.4, еслиF(X1(n-1))>F(X2(n-1)).
Полагая x* = (an+ bn)/2,находимX*с абсолютной погрешностью, не превосходящей величины
εn =(bn- an)/2=(b-a-δ)/2n+1+δ/2
Кроме этих методов известны и другие, более эффективные методы, такие как: метод Фибоначчи, метод золотого сечения, метод поиска по дискретным точкам.[12, 25]
6.3. Градиентные методы многомерной оптимизации
Если ограничения в задаче НЛП отсутствуют, то применяют все методы оптимизации нелинейных функций. Причём, если в задаче с ограничениями решение гарантированно находится внутри области, то его можно найти этими методами, так как эти ограничения не являются активными и их можно отбросить. Рассмотрим наиболее широко применяемые методы оптимизации нелинейных функций многих переменных – это так называемые поисковые методы. Здесь поиск оптимальной точки начинают из начальной точки (ее выбирают из некоторых знаний о примерном месте нахождения решения). Далее в соответствии с некоторым разумным правилом переходят в новую точку с лучшим значением ЦФ и т.д. до тех пор, пока не выполнится некоторое заранее заданное правило остановки, например выполнение условия по точности.
studfiles.net
