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

 

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

 

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

 

Направление поиска в случае мини-мизации целевой функции совпадает с на-правлением антиградиента. Пусть имеется Y=F(x1;x2), тогда

  ,

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

 

 

 

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

.

Для вычисления приращений функции в направлении осей ее аргументов построим две дополнительные точки N и P, лежащие вблизи начальной точки поиска М на расстояниях ε1 и ε2 сответственно. Вычислив значения целевой функции в этих точках, а затем вычислим приращения в направлении аргументов.

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

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

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

 

 

 

 

 

 

 

 

 

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

 

 

Симплексные методы

 

 

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

Поиск решения осуществляется с использованием симплекса.

Симплекс – геометрический комплекс, имеющий n+1 вершину; где n – число факторов оптимизационной задачи. Для функции двух переменных n=2, а симплекс представляет собой треугольник на плоском пространстве переменных. Если этот треугольник равносторонний, то метод поиска называется методом регулярного симплекса. Когда начальный размер симплекса известен и равен R, координаты всех его вершин легко определить, если заданы координаты любой вершины, кА это показано в таблице. Пусть вершина А является начальной точкой поиска. Начиная поиск, определим координаты двух других вершин симплекса и вычислим значения целевой функции во всех трех вершинах. Сравним значения функции между собой и определим наихудшее (при поиске минимума – наибольшее, при поиске максимума – наименьшее). Дальнейший поиск следует предпринимать в направлении, противоположном той вершине, в которой наблюдается наихудшее значение функции. Для этого используется процедура отражения: ищем точку, зеркально отражая наихудшую вершину через противоположную сторону симплекса. Получаем новый симплекс, две из трех вершин которого принадлежат старому. Рассчитываем значение целевой функции в новой вершине и сравниваем его со значениями в двух других вершинах нового симплекса (эти значения были рассчитаны на предыдущем шаге решения). Вновь определяем наихудшее значение функции на новом симплексе, проводим процедуру отражения и ищем вершину следующего симплекса. Продолжая движение таким способом, мы неизбежно придем в область экстремума целевой функции, где при использовании процедуры отражения начнется вращение симплекса вокруг одной из его вершин. Если симплекс начал вращение и совершил (путем последовательных отражений вершин) полный оборот, то улучшить значение функции при движении симплекса начального размера уже не удастся. Необходимо уменьшить размер симплекса, разделив начальный размер на коэффициент сокращения, и продолжить решение задачи до достижения заданной точности.

 

y=F(x1;x2), R – начальный размер симплекса.

 

	Х1	Х2
А В С	Х10 Х10+R/2 X10+R	X20 X20+ X20

 

 

 

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

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

Y(M2) < Y(M1)

глоб.                  лок.

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

 

 

 

 

Экспериментальные методы оптимизации

 

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

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

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

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

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

 

Методы линейного программирования

 

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

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

• Шихтовая задача;
• Задача об использовании ресурсов;
• Транспортная задача;
• Задача о составлении расписаний.

 

 

 

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

 

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

Обозначим обогатительные фабрики А1…А4, а медеплавильные заводы В1…В3. Пусть стоимость перевозки одной тонны концентрата от i-того поставщика к j-тому потребителю составляет Сij. Такая матрица носит название стоимости перевозок. Количество тонн концентрата, перевозимое от i-того поставщика к j-тому потребителю обозначим как хij и запишем в соответствующую матрицу, которая называется матрицей элементов решения.

	В1	В2	В3
А1 А2 А3 А4	С11 С21 С31 С41	С12 С22 С32 С42	С13 С23 С33 С43	а1 а2 а3 а4

Суммарная стоимость перевозки концентрата от Аi к Вi будет:

.

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

.

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

,

и доставлены потребителям:

.

 

 

	В1	В2	В3
А1 А2 А3 А4	Х11 Х21 Х31 Х41	Х12 Х22 Х32 Х42	Х13 Х23 Х33 Х43
	b1	b2	b3

 

 

 

 

 

 

 

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

 

 

 

Решение задач линейного программирования

 

Рассмотрим решение задачи линейного программирования графическим методом на следующем при мере.

Имеется предприятие, производящее 2 продукта: А и В. Продукты отличаются по цене: продукт А имеет цену 3 у.е. за тонну, продукт В – 5 у.е. за тонну. Кроме того, производство одной тонны продукта  А требует 3, а продукта В -9 единиц сырья. Запас сырья на предприятии ограничен и составляет 75 единиц. Общее количество продуктов А и В не должно превышать 10 тонн, что обеспечит стабильность цен при их продаже. Производство более дешевого продукта А не может превышать производство более дорогого продукта В более чем на 3 тонны. Расход сырья на производство не может превышать имеющегося запаса в 75 единиц.

С учетом этого сформулируем математически условия задачи. Обозначим как х1 массу продукта А, а х2 – массу продукта В соответственно. Тогда целевая функция L будет определяться следующим выражением:

 

	А	В
Цена	3	5
Выпуск, т	Х1	Х2