Математические методы оптимизации технологических систем
Технологические системы в металлургии – искусственные системы, предназначенные для достижения поставленных целей. Общая цель таких систем состоит в переработке сырья, содержащего цветные металлы и сопутствующие ценные составляющие, и получении продукта с заданными свойствами.
По виду сырья, применяемых технологических приемов, особенностей получаемых продуктов, металлургические технологии весьма разнообразны. Однако наличие общей цели позволяет наметить общие подходы к оптимизации таких систем.
Оптимизация предполагает наличие критериев оптимальности. Критерии оптимальности характеризуют качество технологического процесса, т.е. степень достижения поставленных целей.
К критериям оптимальности предъявляются два важнейших требования:
1. Критерий должен быть количественным, т.е. выражаться числом. В том случае, когда критерий не имеет ясного количественного смысла, для получения количественных критериев используется метод экспертных оценок.
2. Критерий должен быть монотонно связан с качеством функционирования технологической системы. Чем лучше качество системы, тем выше значение критерия оптимальности (или наоборот).
Например, извлечение металла в целевой продукт часто является критерием оптимальности: чем лучше работает технология, тем больше извлечение (меньше потерь металла). Другим критерием оптимальности можно считать удельные затраты энергии или топлива на единицу произведенного продукта. Ясно, что чем лучше работает технология, тем меньше удельный расход энергии или топлива. Но и в первом, и во втором случае эта связь монотонна.
Критерий оптимальности по происхождению можно разделить на группы:
· Технический критерий оптимальности (извлечение металла в целевой продукт, удельная производительность аппарата, удельные затраты энергии и др.).
· Технико-экономический критерий (себестоимость продукции, рентабельность и др.).
· Экологические критерии.
Как правило, при постановке оптимизационной задачи, не удаётся сформулировать единственный критерий оптимальности. На начальном этапе реальные оптимизационные задачи являются многокритериальными. Решения многокритериальных задач часто не являются однозначными – улучшая часть критериев оптимальности, мы ухудшаем другие критерии. Всегда при постановке оптимизационной задачи следует стремиться к формулировке обобщённого единственного критерия оптимальности. Математические методы решения оптимизационных задач при наличии нескольких критериев разработаны недостаточно.
Методы построения обобщённых критериев оптимальности
В том случае, когда имеется несколько частных критериев оптимальности, имеет смысл попытаться свести задачу к однокритериальной. Для этого существует несколько методов построения обобщенных критериев оптимальности.
1. Аддитивный метод: 
, где Ki – частный критерий оптимальности;
ai – весовой коэффициент при этом критерии.
Весовые коэффициенты имеют положительные и отрицательные знаки, в зависимости от того, в каком направлении действует частный критерий оптимальности. Так например, частным критерием оптимальности выбрано извлечение. Понятно, что при весовом коэффициенте выбирается знак плюс, поскольку улучшение частного критерия способствует улучшению обобщенного. Наоборот, если частный критерий – удельные энергозатраты, то знак весового коэффициента уместно выбирать отрицательным: увеличение удельных энергозатрат снижает значение обобщенного критерия оптимальности. Величина весового критерия выбирается в зависимости от степени важности частного критерия. Выбор величин весовых коэффициентов вносит элемент субъективности в формирование обобщенного критерия. Для уменьшения этой субъективной составляющей выбор величин весовых коэффициентов проводят с использованием метода экспертных оценок. Для этого привлекается коллектив экспертов, знающих особенности работы оптимизируемого объекта.
2. Мультипликативный метод: 
.
Обобщенный критерий в этом случае является произведением частных критериев оптимальности. Например, сквозное извлечение по технологической схеме переработки сырья без оборотных материалов является произведением величин извлечения по всем стадиям технологической схемы. Аналогом в механике является к.п.д.: для всего механизма он является произведением к.п.д. отдельных частей этого механизма.
При постановке оптимизационных задач следующим шагом является назначение ограничений. Не будет преувеличением сказать, что все реальные задачи оптимизации являются задачами с ограничениями. Наличие ограничений способно радикально влиять на результат решения оптимизационной задачи, изменяя его в очень сильной степени. Поэтому к выбору ограничений следует подходить весьма серьезно.
Ограничения 1-го рода наложены на входные величины, поэтому являются более простыми.
Ограничения 2-го рода касаются выходных характеристик системы. Они являются более сложными, поскольку требуют ответа на вопрос: какие ограничения первого рода (на входные характеристики) требуется установить, чтобы не нарушались ограничения второго рода. Примером ограничений второго рода являются требования по химическому составу полученного продукта. Обычно они регламентированы соответствующими документами (ГОСТ, технические условия и т.п.). Возникает вопрос: какие ограничения на фиксированные входные характеристики (состав сырья) и управляющие воздействия (время пребывания вещества в аппарате, температура и др.) должны быть приняты, чтобы не нарушались ограничения первого рода (т.е. состав полученного продукта соответствовал требуемому)? Разумеется, выбор ограничений – это задача для специалиста, глубоко знающего оптимизируемый технологический процесс.
Следующим этапом постановки задачи является выбор оптимизирующих факторов. Выбираются из вектора управляющих воздействий те величины, которые влияют на выход системы, и которые мы можем изменять в пределах выбранных ограничений. Большинство задач оптимизации содержат эти ограничения.
В реальных задачах оптимизации технологических систем в цветной металлургии в качестве оптимизирующих факторов могут рассматриваться :
-массовые соотношения между компонентами шихты (соотношение между массами концентратов разных производителей и флюсов различного состава),
- время пребывания вещества в технологическом аппарате (фактически определяет, как полно пройдут необходимые физико-химические превращения компонентов сырья в продукт),
-температура,
-давление,
-условия перемешивания и т.п.
Как и выбор ограничений, выбор оптимизирующих факторов способен выполнить только специалист, глубоко знающих оптимизируемый процесс.
Последним этапом постановки оптимизационной задачи является формулирование вида целевой функции. Она является математическим выражением зависимости критерия оптимальности от оптимизирующих факторов. Целевая функция далеко не всегда представляет собой аналитическое выражение этой зависимости, значительно чаще эта связь представляет собой алгоритм вычислений, иногда достаточно сложных, следуя которому мы по известным значениям оптимизирующих факторов можем рассчитать значение целевой функции.
Для решения оптимизационной задачи необходима математическая модель процесса или объекта, который мы оптимизируем.
В математической форме оптимизационная задача сводится к следующему:
F(x, u, V, t) → max (min)
a1≤u1≤b1
a2≤u2≤b2
. . . . . . .
an≤un≤bn.
имеются управляющие воздействия u1, u2, …, un, которые могут изменяться в интервалах разрешённых ограничений a1 – b1, a2 – b2, …, an – bn. Целевая функция (F) отображает зависимость критерия оптимальности от управляющих воздействий u1 –un. Требуется отыскать такие управляющие воздействия u1 –un, которые, с одной стороны не нарушают ограничений поставленной задачи, а с другой – обращают целевую функцию в максимум или минимум.
Таким образом, на этапе постановки оптимизационной задачи требуется участие специалиста предметной области – металлурга по цветным металлам, глубоко разбирающегося в особенностях оптимизируемого объекта. Для оптимизации также необходима математическая модель оптимизируемого объекта.
Когда оптимизационная задача формализована, т.е. поставлена в математической форме, переходят к выбору математического метода ее решения. Выбор метода определяется свойствами самой оптимизационной задачи: какова задача, таков и адекватный задаче метод решения. Методы решения многих классов оптимизационных задач математически разработаны довольно хорошо, алгоритмы этих методов описаны, на базе алгоритмов разработаны и пакеты прикладных программ для решения оптимизационных задач.
Если знаний металлурга в этой области недостаточно (а это естественно), то на этапе решения оптимизационной следует привлечь к работе специалистов по прикладной математике, программистов и т.п. На этапе постановки задачи от специалистов этого профиля помощи ждать бессмысленно.
Выбор метода решения задачи зависит от ее свойств. В этой связи необходимо познакомиться с классификацией оптимизационных задач по их свойствам.
Классификация оптимизационных задач
Все множество оптимизационных задач можно разделить на несколько классов по следующим признакам:
1. Вид экстремума целевой функции. Нас может интересовать поиск максимума или минимума целевой функции. Как известно, переход от поиска минимума к поиску максимума не представляет труда: минимум функции y=f(x) достигается при тех же условиях, что и максимум функции –y=–f(x). Таким образом, для смены знака экстремума достаточно целевую функцию умножить на минус единицу. Пример пояснен на рисунке.
2. Число критериев оптимальности. По этому признаку все множество задач оптимизации можно разделить на два подмножества:
а) однокритериальные задачи;
б) многокритериальные задачи.
В первом случае в задаче может быть сформулирован единственный критерий оптимальности. При необходимости он может быть получен из нескольких частных критериев оптимальности одним из ранее описанных методов (аддитивный, мультипликативный).
Во втором случае в задаче по принципиальным соображениям нет единственного критерия оптимальности. Решение такой задачи часто бывает неоднозначным, а математические методы решения разработаны хуже, чем для однокритериальных задач. По этой причине всегда имеет смысл попытаться построить единственный критерий оптимальности путем свертки нескольких частных критериев.
3. По числу оптимизирующих факторов. Здесь также можно выделить два подмножества:
а) однофакторные задачи;
б) многофакторные задачи.
В первом случае в задаче имеется единственный оптимизирующий фактор (единственное управляющее воздействие не объект, которое мы можем изменять в заданных пределах). Математически это означает, что целевая функция зависит от величины единственного своего аргумента.
Во втором случае целевая функция зависит от нескольких (двух и более) аргументов. Имеется два и более управляющих воздействия, изменяя которые в заданных пределах, мы управляем объектом.
4. Наличие ограничений.
Большинство реальных задач содержат ограничения. Наличие ограничений существенно влияет на получение решения оптимизационной задачи. Некоторые задачи можно рассматривать как задачи безусловной оптимизации. В таких задачах ограничения очень широкие и не влияют на результат решения задачи.
5. По особенностям целевой функции.
Целевая функция может быть задана математически различными способами:
· Аналитический способ F = (u1, u2, …, um). Имеется некое аналитическое выражение, при подстановке в которое значений аргументов может быть определено значение функции.
· Алгоритм, т.е. последовательность вычислений, в результате выполнения которых определяется значение целевой функции при заданных значениях ее аргументов (оптимизирующих факторов).
Целевая функция может быть линейной или нелинейной относительно оптимизирующих факторов. В задачах линейного программирования, например, целевая функция линейная. Существует много задач с нелинейно-заданной функцией.
Итак, выбор математического метода решения оптимизационных задач зависит от свойств поставленной задачи. К настоящему времени существует достаточно много математических методов решения оптимизационных задач. По особенностям их реализации методы можно объединить в три группы:
1. Аналитические.
2. Поисковые.
3. Экспериментальные.
Аналитические методы решения оптимизационных задач
Для реализации аналитических методов целевая функция должна быть задана аналитически. Аналитические методы могут использоваться для решения однофакторных и многофакторных задач.
1. Однофакторные задачи. Пусть целевая функция зависит от единственного аргумента. Для поиска ее экстремума (скажем, минимума) используем известные приемы математического анализа. Достаточно взять производную функции и приравнять ее к нулю, а затем решить полученное уравнение. Для определения типа экстремума (минимум, максимум или точка перегиба) потребуется также взять вторую производную. Знак второй производной указывает на тип экстремума: положительное значение говорит о том, что найден минимум, отрицательное – максимум функции.
y = f (x) → min
y = 2x2 + 4x – 8 → min
y'=0 4x + 4 = 0
x = -1
y''Є(- ∞; +∞ ) y'' = 0 – точка перегиба
y'' < 0 – максимум функции
y'' > 0 – минимум функции.
Аналитический метод для однофакторных задач предъявляет высокие требования к целевой функции: она должна быть задана аналитически и иметь 1-ю и 2-ю производные. В этом случае поиск решения может быть осуществлен методами математического анализа.
2. Многофакторные задачи.
В многофакторных задачах целевая функция зависит от двух и более аргументов.
F(x1, x2, …, xn) – функция нескольких переменных (≥2). Пусть, например, аналитическое выражение целевой функции имеет следующий вид:
у = 2х12 + 3х22 + 4х1 + 5х2 – 16.
4х1 + 4 = 0
6х2 + 5 = 0.
Для решения воспользуемся методами математического анализа применительно к функции нескольких переменных. Возьмем частные производные по каждому аргументу и приравняем их к нулю. Получим систему уравнений, решая которую определим условия экстремума целевой функции. В нашем примере получаем систему линейных уравнений, решая которую находим условия экстремума целевой функции: х1=-1; х2=-5/6.
Аналитические методы для решения многофакторных задач так же используются крайне редко, т.к.:
-функция должна быть задана аналитически (иметь 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. Разделив начальные шаги на соответствующие коэффициенты сокращения продолжают поиск, пока одна из точек вновь не станет наилучшей и т.д. Критерием завершения поиска является достижение заданной точности решения.
Градиентные методы
Эти методы отличаются от предыдущего некоторыми элементами стратегии, в частности направлением поиска. Известно, что градиент функции – это вектор, указывающий направление наискорейшего возрастания функции из данной точки пространства ее переменных. Противоположно направленный вектор антиградиента функции указывает направление наискорейшего ее убывания из данной точки.
Направление поиска в случае мини-мизации целевой функции совпадает с на-правлением антиградиента. Пусть имеется 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 |
L = 3x1 + 5x2 → max.
Требуется определить такие х1 и х2, при которых эта функция максимальна.
Из условий задачи вытекает ряд ограничений:
x1 ≥ 0
x2 ≥ 0
3x1 + 9x2 ≤ 75
x1 + x2 ≤ 10
x1 – x2 ≤3
Используем имеющиеся ограничения и вид целевой функции для поиска решения графическим методом.
Поскольку наша задача содержит две неизвестных величины, отведем для них две оси в декартовой системе координат. Обе оси лежат в одной плоскости, которая в данном случае является пространством переменных.
Первое ограничение задачи x1 ≥ 0 делит пространство переменных на две половины, одна из которых является разрешенным, а другая – запрещенным полупространством. Второе ограничение x2 ≥ 0 также отсекает от пространства переменных разрешенное полупространство. Оба первых ограничения совместны в первом квадранте декартовой плоскости. Заметим, что и на осях переменных ограничения не нарушаются, поскольку ограничения являются нестрогими неравенствами. Разрешенное полупространство покажем штриховкой.
Третье ограничение задачи 3x1 + 9x2 ≤ 75 в предельном виде можно рассматривать как уравнение прямой в выбранной системе координат: 3x1 + 9x2 =75, или х2= -1/3х1+25. Положение этой прямой показано ниже на рисунке. Разрешенное полупространство расположено ниже прямой.
Используя оставшиеся ограничения, проведем соответствующие им прямые и покажем разрешенное полупространство для каждой из них.
В результате всех построений на пространстве переменных образуется область, внутри которой и на границах которой совместно выполняются все ограничения данной задачи. Это область 0ACEG, имеющая вид пятиугольника, называется областью допустимых решений данной задачи. Особенности области допустимых решений (ОДР) вытекают из ограничений задачи.
Любая точка внутри и на границах ОДР, а также на пересечении границ, т.е. в вершинах ОДР, является допустимым решением. Также очевидно, что число допустимых решений бесконечно велико. Нас же интересует оптимальное решение, т.е. такое, при котором целевая функция нашей задачи обращается в максимум.
Вторым этапом решения и является поиск оптимального решения на области допустимых решений. Для этого воспользуемся выражением для целевой функции
L = 3x1 + 5x2. Зададим L произвольное значение, пусть например L=15. Последнее означает, что мы определили в трехмерном пространстве, имеющем ось для отображения целевой функции, некую плоскость, для любой точки которой значение целевой функции неизменно и равно 15, независимо от значений x1 и х2. С другой стороны, выражение L = 3x1 + 5x2 определяет положение плоскости целевой функции в выбранной системе координат. Плоскость целевой функции проходит через начало координат и наклонена к по отношению к осям переменных. Этот наклон тем больше, чем больше коэффициент при соответствующей переменной.
Выражение 3x1 + 5x2=15 означает, что плоскости в пространстве пересекаются. Линия пересечения плоскости постоянного уровня и плоскости целевой функции есть прямая, проекция ее на пространство переменных также является прямой, которая называется прямой опорного решения (ПОР).
В нашей задаче положение ПОР соответствует уравнению прямой х2=-3/5х1+3.
Она отсекает на оси х1 отрезок, равный 5, а на оси х2 – 3 единицам. Возрастание целевой функции происходит при увеличении х1 и х2, что показано стрелками на ПОР на рисунке.
Значение 15 мы выбрали произвольно. Если задать большее значение, линия пересечения плоскости целевой функции и плоскости постоянного уровня целевой функции переместится в пространстве параллельно самой себе, а ее проекция переместится параллельно ПОР вправо и вверх.
Нетрудно заметить, что наиболее далеко отстоящей точкой от ПОР является вершина области допустимых решений С, в которой и будет наибольшее значение целевой функции L. Эта вершина области и будет оптимальным решением нашей задачи.
Положение вершины С определяется решением системы уравнений:
х1+х2=10
3х1+9х2=75,
что дает координаты С(2,5;7,5). Значение целевой функции при этом равно 45.
ПОР –прямая опорного решения.
3x1 + 9x2 = 75
x1 + x2 = 10
x1 = 2,5, x2 = 7,5
L = 45
Графический метод не может быть использован, если число переменных в задаче больше двух, поскольку пространство переменных становится многомерным, а задача лишается наглядного образа. Для решения таких задач линейного программирования (а реальные задачи могут содержать сотни переменных) используются иные методы, например симплекс-метод и метод искусственного базиса.
Алгоритмы методов решения задач линейного программирования известны, исследованы математиками с точки зрения сходимости и наличия решения. На базе имеющихся алгоритмов созданы программы, входящие в пакеты прикладных программ общего назначения и проблемно-ориентированных. В частности, решение задач линейного программирования может быть достигнуто при использовании электронных таблиц Microsoft Excel или математического пакета MathCAD. Наличие таких инструментов упрощает получение решения. Основная сложность состоит в корректной постановке задачи, а также в интерпретации и проверке полученных результатов.