В начало

Оптимальное управление технологическими процессами (Лекция)

 

ПЛАН ЛЕКЦИИ

1. Основные понятия нахождения экстремума функции

2. Классификация методов оптимального управления

 

1. Основные понятия нахождения экстремума функции

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

В общем случае задача оптимизации формулируется следующим образом:

Найти extr функции R(x), где ХХ

R(x) – называется целевой функцией или функцией или критерием оптимизации или оптимизируемой функцией

Х – независимая переменная.

Как известно необходимые условиям существования экстремума у непрерывной функции R(x) могут быть получены из анализа первой производной . При этом функция R(x) может иметь экстремальные значения при таких значениях независимой переменной Х, где первая производная  равна 0. т.е. =0. Графически равенство нулю производной означает, что касательная к кривой R(x) в этой точке параллельна оси абсцисс.

Рис. 1

Равенство производной =0 есть необходимое условие экстремума.

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

1.      Способ сравнения значений функций

Сравнивают значение функции R(x) в «подозреваемой» на экстремум точке ХК две соседние значения функции R(x) в точках ХК-ε и ХК+ε, где ε- малая положительная величина. (Рис. 2)

 

Рис. 2

 

Если оба рассчитанных значения RК+ε) и RК-ε), окажутся меньше или больше RК), то в точке ХК существует максимум или минимум функции R(х).

Если же RК) имеет промежуточное значение между RК-ε) и RК+ε), то функция R(х) не имеет ни максимума ни минимума.

2.  Способ сравнения знаков производных

Опять рассмотрим функцию RК) в окрестностях точки ХК, т.е. ХК+ε и ХК-ε . При этом способе рассматривается знак производной  в окрестности точки ХК. Если знаки производной в точках ХК-ε и ХК+ε различные, то в точке ХК существует экстремум. При этом вид экстремума (min или max) может быть найден по изменению знака производной при переходе от точки ХК-ε к точке ХК+ε.

Если знак  меняется с «+» на «-», то в точке ХК – максимум (рис. 3б), если наоборот с «-» на «+», то минимум. (Рис. 3а)

 

 

Рис. 3

 

3.  Способ исследования знаков высших производных.

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

Способ сводится к следующему:

В точке ХК «подозреваемой» на экстремум, для которой справедливо

 вычисляется значение второй производной .

Если при этом , то в точке ХК – максимум,

если , то в точке ХК – минимум.

При решении практических задач оптимизации требуется отыскать не какое-нибудь min или max значение функции RК), а наибольшее или наименьшее значение этой функции, которое называется глобальным экстремумом. (Рис. 4)

 

 

 

 

 

 

 

 

 


Рис. 4

 

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

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

Часто множество Х определяют как систему функции

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

 

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

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

 

Пример типовой задачи оптимизации

Задача о коробке максимального объема.

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

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

На примере данной задачи можно проиллюстрировать все элементы постановки задач оптимизации.

а) б) в)

Рис. 5. Схема изготовления коробки из прямоугольной заготовки фиксированного размера

 

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

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

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

 

Рис. 6. Схема изготовления из прямоугольной заготовки с указанием ее размеров

 

Для математической постановки данной задачи необходимо определить переменные соответствующей задачи оптимизации, задать целевую функцию и специфицировать ограничения. В качестве переменной следует взять длину стороны вырезаемого квадрата r, которая в общем случае, исходя из содержательной постановки задачи, принимает непрерывные действительные значения. Целевой функцией является объем полученной коробки. Поскольку длина стороны основания коробки равна: L - 2r, а высота коробки равна r, то ее объем находится по формуле: V(r) = (L-2r)2r . исходя из физических соображений, значения переменной r не могут быть отрицательными и превышать величину половины размера исходной заготовки L, т.е. 0,5L.

При значениях r = 0 и r = 0,5 L соответствующие решения задачи о коробке являются выраженными. Действительно, в первом случае заготовка остается без изменения, а во втором случае она разрезается на 4 одинаковых части. Поскольку эти решения имеют физическую интерпретацию, задачу о коробке для удобства ее постановки и анализа можно считать оптимизации с ограничениями типа нестрогих неравенств.

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

где  (1)

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

 

2. Классификация методов оптимального управления

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

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

Общая постановка задачи оптимизации заключается в следующем:

1.      Выбирается критерий

2.      Составляется уравнение модели

3.      Накладывается система ограничения

4.      Решение  

модель - линейная или нелинейная

Ограничения

В зависимости от структуры модели применяются различные методы оптимизации. К ним относятся:

1.      Аналитические методы оптимизации (аналитический поиск экстремума, метод множителей Лагранжа, Вариационные методы)

2.      Математическое программирование (линейное программирование, динамическое программирование)

3.      Градиентные методы.

4.      Статистические методы (Регрессионный анализ)

Линейное программирование. В задачах линейного программирования критерий оптимальности представляется в виде:

 

 

 

где  - заданные постоянные коэффициенты;

 - переменные задачи.

Уравнения модели представляют собой линейные уравнения (полиномы) вида  на которые накладывается ограничения в виде равенства или неравенства, т.е.  (2)

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

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

 , которая удовлетворяет условия (2) и обеспечивает в зависимости от постановки задачи max или min значение критерия.

Геометрическая интерпретация имеет вид: - критерий при наличии ограничении на переменных Х1 и Х2 типа равенств и неравенств

  

Рис. 7

 

R имеет постоянное значение вдоль линии l. Оптимальное решение будет в точке S, т.к. в этой точке критерий будет max.Одним из методов решения задачи оптимизации линейного программирования является симплекс-метод.

Нелинейное программирование. Математическая постановка задачи нелинейного программирования заключается в следующем: Найти экстремум целевой функции , которая имеет вид нелинейности.

На независимые переменные налагаются различные ограничения типа равенств или неравенств   

в настоящее время для решения задач нелинейного программирования применяются довольно большое число методов.

К ним относится: 1) Градиентные методы (метод градиента, метод наискорейшего спуска, метод образов, метод Розенброка и т.д.)

2) Безградиентные методы (метод Гауса-Зейделя, метод сканирования).

 

Градиентные методы оптимизации

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

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

 

Рис. 8. Поиск минимума методом градиента

 

Поиск оптимума производится в два этапа:

1-этап: - находят значения частных производных по всем независимым переменным, которые определяют направление градиента в рассматриваемой точке.

2-этап: - осуществляется шаг в направлении обратном направлению градиента, т.е. в направлении наибыстрейшего убывания целевой функции.

Алгоритм градиентного метода может быть записан следующим образом:

 (3)

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

 

Рис. 9

 

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

К безградиентным методам поиска экстремума относится:

1. метод золотого сечения

2. метод с использованием чисел Фибония

3. метод Гауса-Зейделя (метод получения изменения переменной)

4. метод сканирования и т.д.

 

3 месяца - Xbox Live Gold
3 месяца - Xbox Live Gold


Quake-4
Quake-4


Шрифт ККМ ШТРИХ-ФР
Шрифт ККМ ШТРИХ-ФР