Лекции по «Моделирование процессов и объектов в металлургии»

Аналитические методы для решения многофакторных задач так же используются крайне редко, т.к.:

-функция должна быть задана аналитически (иметь 1-ю и 2-ю производные);

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

 

Поисковые (численные) методы решения однофакторных

оптимизационных задач

 

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

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

Для получения решения численным методом необходимо:

а) задать способ вычисления целевой функции (алгоритм или аналитическое выражение): y = f (x) → min.

б) все поисковые методы – приближённые, поэтому перед началом решения следует задать интересующую нас точность решения .

в) выбрать интервал допустимых значений оптимизирующего фактора: a≤x≤b.

 

1. Метод перебора (сплошного поиска).

 

Разбиваем ось аргументов на конечное число шагов решения, которое определяется интересующей нас точностью: . При точности 1% от интервала изменения фактора это будет соответствовать разбиению интервала на 100 шагов, при точности 5% потребуется разбить интервал на 20 шагов и т.д.

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

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

2. Метод дихотомии (половинного деления).

 

 

Исходно требуется то же, что и в предыдущем методе. Разбиваем интервал значений аргумента пополам:

 

. Строим две дополнительные  узловые точки с координатами:

 

 

 и вычисляем значения целевой  функции в этих точках.

 

y1 = f (x1)

y2 = f (x2).

 

Представим, что функция имеет один минимум на отрезке от a до b. Ординаты у1 и у2 вычислены в точках, лежащих достаточно близко друг к другу, на расстоянии удвоенной точности решения. Если у2>у1, поиск минимума на левой половине интервала теряет смысл, и ее можно отбросить. На этом первая итерация решения заканчивается, и после сокращения интервала вдвое задача вновь возвращается к исходной, но интервал дальнейшего поиска сокращается вдвое.

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

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

Поскольку сокращение интервала на каждой итерации происходит вдвое, то совершив 7 итераций, например, мы уменьшим первоначальный интервал в 27= 128 раз, достигнув точности решения 1/128, что менее 1% от первоначального интервала.

Поскольку на каждой итерации целевая функция вычисляется дважды, общее количество ее вычислений будет равно 14. При этом нет необходимости запоминать результаты вычислений, в отличие от метода сплошного поиска. К тому же, решая задачу по методу сплошного поиска с более высокой точностью 1%, мы были бы вынуждены выполнить 100 вычислений целевой функции, и при этом все результаты вычислений надо было бы сохранить. При повышении точности решения различия методов становятся еще больше: при точности 0.5% метод дихотомии требует 16 вычислений функции, а метод сплошного поиска – 200 вычислений, при точности 0.1% - 20 и 1000 вычислений соответственно!

 

 

1

 

   7 шагов

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

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

 

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

 

В таких оптимизационных задачах F(x1, x2, …, xn) – целевая функция двух и более аргументов.

F(x1, x2, …, xn) → min.

Рассмотрим Y=F(x1;x2). В этом случае пространство переменных есть плоскость.

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

 

 

 

 

 

 

 

 

 

 

 

Нужно найти такие х1 и х2, при которых Y → min.

Необходимо предварительно установить точность решения ( ). Точность решения оптимизационной задачи определяется тем, как в последующем будут использованы результаты решения. Оптимальные значения технологических параметров, найденные в результате решения оптимизационной задачи, необходимо поддерживать при проведении технологического процесса. Для этого служат регуляторы соответствующих параметров: температуры, объемных и массовых расходов и т.п. Регуляторы позволяют измерять и поддерживать значения параметров с некоторой точностью, составляющей обычно от 0.5% до 5% диапазона измерения. Поэтому нет смысла задавать точность решения оптимизационной задачи более жестко, поскольку регулятор впоследствии не позволит поддерживать значение параметра с высокой точностью.

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

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

%

%

а1≤x1≤b1

a2≤x2≤b2

N = n1 ∙ n2

 

 

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

Пусть целевая функция имеет три оптимизирующих фактора. Используя метод сплошного поиска, мы могли бы построить и исследовать область допустимых решений. В нашем случае такая область представляет собой параллелепипед. Предположим, нас интересует точность решения в 1% от диапазона изменения каждого фактора. Мы могли бы разбить интервал каждого фактора на сто шагов, что привело бы к пространственной сетке, содержащей сто плоских слоев, в каждом из которых  количество узлов составило бы десять тысяч. Таким образом, общее число узлов на области допустимых решений составило бы миллион. Далее следовало бы вычислить (и запомнить значения) целевую функцию в каждом узле, отсортировать полученные значения и найти экстремум. Значения факторов в точке экстремума и были бы решением оптимизационной задачи. Однако для получения решения таким путем потребовалось бы слишком много времени, поскольку вычисление целевой функции каждый раз требует некоторых затрат времени. К тому же требуется время на сортировку и поиск оптимального решения, а также огромный объем памяти для хранения результатов вычислений. А если число оптимизирующих факторов (аргументов целевой функции) больше трех, то легко показать, что задача вообще не может быть решена за приемлемое время - пока мы занимаемся ее решением, условия технологического процесса изменятся. Поэтому усилия специалистов в области прикладной математики были сосредоточены в направлении разработки «быстрых» методов решения многофакторных оптимизационных задач. В настоящее время создано несколько групп методов для решения таких задач.

Математиками разработаны следующие методы для решения многофакторных оптимизационных задач:

• Метод координатного спуска.
• Градиентные методы.
• Симплексные методы.

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

Общие требования:

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

Наряду с общими поисковые методы отличаются элементами стратегии поиска, к которым относятся:

1. Начальная точка поиска.
2. Направление поиска.
3. Величина начального шага.
4. Способ сокращения начального шага и коэффициент сокращения.

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

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

Направление поиска – выбирается в каждом методе, исходя из особенностей метода.

Начальный шаг. Идея поисковых методов – движение по области допустимых решений, причём направление и размер шага зависят от результатов решения, полученных на предыдущем шаге. При этом, для более быстрого получения решения (за меньшее число вычислений) следует выбирать начальный шаг достаточно большим: величина начального шага 20…25% от интервала изменения фактора.

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

 

Метод координатного спуска

 

В этом методе направление поиска совпадает с направлением координат (осями факторов). На любом шаге решения можно менять только один фактор, а все остальные остаются без изменения.

 

 

 

 

Поиск решения начинается в начальной точке 1 (см. рис.), где вычисляется значение целевой функции. Затем начинаем движение по пространству переменных в пределах области допустимых решений. Это означает, что увеличив координату на величину начального шага вдоль х1, и оставив без изменения х2, мы переместимся в новую точку 2. Вычислим значение целевой функции в этой точке и сравним его с предыдущим. Если при поиске минимума значение функции в точке 2 меньше, чем в точке 1, то такой шаг следует считать удачным. В этом случае поиск продолжается в выбранном направлении. Двигаясь вдоль х1 и вычисляя на каждом шаге значение целевой функции, мы рано или поздно можем убедиться в том, что последующее значение станет больше предыдущего. Такой шаг является неудачным. Если очередной шаг решения оказался неудачным, направление поиска изменяется. Для этого координату последней удачной точки по х1 фиксируют, и начинают движение в направлении х2, используя величину начального шага. Вблизи области минимума движение начальным шагом во всех разрешенных направлениях не приводит к улучшению значения целевой функции. При этом одна из точек окажется наилучшей, в ней значение целевой функции наименьшее. Однако задача еще не решена, поскольку величина начального шага выбирается заведомо больше интересующей нас точности решения. Фактически задача пришла к исходной – имеется начальная точка поиска (наилучшая), и требуется путем движения по пространству переменных найти такую точку, в которой значение целевой функции еще меньше. Для этого последующий поиск надо проводить, двигаясь шагом уменьшенной величины. Такой шаг получают делением начального шага на коэффициент сокращения шага, обычно его выбирают равным от 2 до 5. Разделив начальные шаги на соответствующие коэффициенты сокращения продолжают поиск, пока одна из точек вновь не станет наилучшей и т.д. Критерием завершения поиска является достижение заданной точности решения.