Решебник_МО

начальное приближение к решению задачи оптимизации. Испытания проводятся последовательно в n точках X1, X2,..., Xn таких, что каждая последующая точка Xr является в общем случае некоторой функцией Fr координат всех предыдущих точек, а также значений критерия оптимальности и функций-ограничений в этих точках. В качестве решения задачи оптимизации берется та из указанных точек, в которой достигается экстремум критерия оптимальности.

Метод последовательного поиска – метод, в котором точки поиска

Xr определяются на основе всей или части информации об испытаниях в предыдущих точках.

Метод случайного поиска – если функции Fr являются случайными функциями (содержат случайные параметры).

Метод условной оптимизации – метод поиска, ориентированный на решение задач условной оптимизации.

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

Мутация – эволюционный оператор, который в отличие от оператора скрещивания затрагивает только одну хромосому. Мутация в ЭА имеет аналогию в природе, когда происходит замена одного гена другим в ДНК под воздействием, например, радиоактивности. Считается, что мутация – это причина эволюции, и благодаря ей появляются новые виды. В ГА мутация способствует защите от преждевременной сходимости, реализуется выбором случайного гена или группы генов и их изменения по определенным правилам. В бинарном случае оператор мутации заключается в инвертировании символов в случайно выбранных позициях. В случае работы с конечным алфавитом случайно выбранный символ заменяется на любой, отличный от него. Обычно задается вероятность мутации. Надо следить за корректностью результатов оператора мутации.

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

Ограничение параметрическое – соотношение, задающее область изменения значений конкретных параметров: xi≥0 – одностороннее

11

параметрическое ограничение; aj≤xj≤bj – двустороннее параметрическое ограничение.

Ограничение функциональное – функция, представляющая собой равенство или неравенство (gj-bj=0 – функциональное ограничение равенство, gj-bj ≥0 – функциональное ограничение неравенство), определяющая область существования целевой функции.

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

Оптимизация безусловная – оптимизация целевой функции без ограничений.

Оптимизация дискретная – если параметры задачи могут принимать только заранее установленные дискретные значения.

Оптимизация условная – оптимизация целевой функции при наличии ограничений.

Оптимизация целочисленная – дискретная оптимизация, когда параметры могут принимать только целые значения.

Поиск – движение в структурированном пространстве от одних узлов этого пространства к другим. Если поиск является целенаправленным, то задаётся множество начальных узлов, с которых поиск может начинаться, и множество конечных узлов, при достижении которых поиск прекращается. Движение по структуре поискового пространства определяется стратегией поиска.

Поиск эвристический – осуществляется на основе правил, упрощающих или ограничивающих пространство поиска решения. Эвристики могут быть как количественными, так и качественными.

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

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

Условия окончания поиска (стандартные) – это два следующих условия: некоторая векторная норма разности координат двух

12

соседних точек меньше или равна требуемой точности решения по X; модуль разности значений критерия оптимальности в двух соседних точках меньше или равен требуемой точности решения.

Фенотип – раскодированное решение. Хромосома – решение (код).

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

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

Эволюционное программирование (ЭП) – разновидность ЭА,

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

13

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

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

КЛАССИФИКАЦИЯ ЗАДАЧ ОПТИМИЗАЦИИ

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

Классическая математическая постановка задачи оптимизации состоит в том, чтобы найти значения переменных, дающих экстремальное значение некоторой функции f(X) в определенной области G значений переменных X=(xl,х2,...,xn). Область G обычно задается системой неравенств вида gj(xl,х2,...,xn) >bj, j=l,2,…, m, Предполагается, что точка X=(xl,х2,...,xn) и функции ограничений gj(x) принадлежат n-мерному действительному эвклидову пространству.

Задачи оптимизации можно классифицировать в соответствии с видом целевой функций f(X), ограничений gi(Х) и размерностью вектора Х.

Задачи без ограничений, в которых Х представляет собой одномерный вектор, называются задачами одномерной оптимизации.

Задачи условной оптимизации, в которых функции gi(Х) являются линейными, носят название задач с линейными

14

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

В задачах целочисленного программирования компоненты вектора Х должны принимать только целые значения.

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

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

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

Если f(X) представляет собой действительную непрерывно дифференцируемую функцию, а ограничения представляют систему уравнений вида gj–bj=0 и являются непрерывно дифференцируемыми скалярными функциями, то задача называется классической задачей на условный (относительный) экстремум. Эти задачи сводятся к задачам безусловной оптимизации с помощью метода множителей Лагранжа. Поэтому для их решения и анализа используется тот же аппарат, что и для задач на безусловный экстремум.

Если на переменные задачи накладывается условие целочисленности, то она называется задачей целочисленного программирования.

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

Деление оптимизационных задач на классы представляет значительный интерес, поскольку специфические особенности тех

15

или иных задач играют важную роль при разработке методов их решения.

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

КЛАССИФИКАЦИЯ МЕТОДОВ ОПТИМИЗАЦИИ

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

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

Приведем классификацию по исторически принятым делениям методов. Ряд одних и тех же задач может быть решен разными методами.

1.Метод «проб и ошибок». Данный метод применяется, когда либо затруднено построение формальной математической модели, либо затруднена формализация оценки, либо математические методы оптимизации не эффективны.

2.Аналитические методы оптимизации. Это методы, позволяющие определить качественную картину поведения оптимизируемой

16

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

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

4.Численные методы многомерной оптимизации. Данные методы подразделяются на направления:

˗Линейное программирование – решение задач линейного программирования.

˗Квадратичное программирование – решение задач квадратичного программирования.

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

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

˗Нелинейное программирование – решения задач нелинейного программирования.

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

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

17

Такие методы оптимизации называются детерминированными методами.

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

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

ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ

1.Что подразумевается под термином "оптимизация"?

2.Оптимизация системы состоит:

a) в поиске такой системы, в которой максимум параметров управления;

b)поиске такого набора параметров управления, при котором целевая функция достигает экстремума;

c)поиске такого набора параметров управления, при котором целевая функция наиболее оптимальна;

d)поиске такого набора параметров управления, при котором целевая функция самая оптимальная;

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

3.Что необходимо при постановке задачи оптимизации?

4.Что подразумевается под термином целевая функция?

5.Целевая функция это:

a)любая функция, у которой есть экстремумы;

b)любая функция, у которой нет экстремумов;

c) любая функция, у которой есть минимумы;

d) функция, экстремумы которой необходимо найти; e) любая функция, у которой есть максимумы.

6.Что подразумевается под термином показатель качества?

18

7.Выберете правильную фразу:

a) наиболее оптимальный по заданному критерию; b) самый оптимальный по заданному критерию; c) самый оптимальный;

d) наиболее оптимальный;

e) оптимальный по заданному критерию.

8.Что подразумевается под термином скалярная оптимизация?

9.Что подразумевается под термином одномерная и многомерная оптимизация?

10.Что подразумевается под термином дискретная оптимизация?

11.Что подразумевается под термином целочисленная оптимизация?

12.Что в задачах оптимизации называют ограничениями и какими они бывают?

13.Какие методы оптимизации называют методами нулевого, первого, второго порядка?

14.Какие задачи называют задачами одномерной оптимизации?

15.Какие задачи называют задачами линейного программирования?

16.Какие задачи оптимизации называют задачами квадратичного программирования?

17.Какую задачу называют классической задачей на условный (относительный) экстремум?

18.Какие задачи называют задачами статической оптимизации?

19.Из каких этапов состоит процесс решения задачи оптимизации?

20.В каких ситуациях при решении задачи оптимизации применяется метод «проб и ошибок»?

21.Для решения каких задач применяются аналитические методы оптимизации?

22.Для решения каких задач применяются методы динамического программирования?

23.Какие задачи оптимизации решаются методами нелинейного программирования?

24.Какие методы оптимизации называют детерминированными?

25.Что подразумевается под термином стохастическое программирование?

19

АНАЛИТИЧЕСКИЕ МЕТОДЫ ОПТИМИЗАЦИИ. ОБЩАЯ ЗАДАЧА МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ

МЕТОДЫ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ

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

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

и проверить его на максимум и минимум.

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

20