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

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

Задача условной оптимизации заключается в поиске минимального или максимального значения скалярной функции f(x) n-мерного векторного аргументах. Решение задачи основывается на линейной или квадратичной аппроксимации целевой функции для определения приращений x1, …,xn на каждой итерации. Существуют также приближенные методы решения нелинейных задач. Это методы основанные на методе кусочно-линейной аппроксимации. Точность нахождения решений зависит от количества интервалов, на которых мы находим решение линейной задачи, максимально приближенной к нелинейной. Такой метод позволяет производить расчеты с помощью симплекс-метода. Обычно в линейных моделях коэффициенты целевой функции постоянны и не зависят от значения переменных. Однако существует ряд задач, где затраты зависят от объема нелинейно.

Алгоритм решения:

1. Работа начинается с построения регулярного симплекса в пространстве независимых переменных и оценивая значения целевой функции в каждой из вершин симплекса.
2. Определяется вершина - наибольшее значение функции.
3. Вершина проецируется через центр тяжести остальных вершин в новую точку, которая используется в качестве вершины нового симплекса.
4. Если функция убывает достаточно плавно, итерации продолжаются до тех пор, пока либо не будет накрыта точка min, либо не начнется циклическое движение по 2 или более симплексам.
5. Поиск завершается, когда или размеры симплекса, или разности между значениями функции в вершинах останутся достаточно малыми.

Задача: оптимизация емкостей. Добиться минимальных затрат на изготовление емкости объёмом 2750 литров для хранения песка.

Z = C1X1 + C2X2 + C3X3 + C4X4 + C5X5 min;

где: X1 - количество необходимого металла, кг;

C1 - стоимость металла, руб/кг;

X2 - масса требующихся электродов, кг;

C2 - стоимость электродов, руб/кг;

X3 - количество затраченной электроэнергии, кВт ч;

C3 - стоимость электроэнергии, руб/кВт ч;

X4 - время работы сварщика, ч;

C4 - тарифная ставка сварщика, руб/ч;

X5 - время работы подъемника, ч;

C5 - оплата подъемника, руб/ч.

1. Найдем оптимальную поверхностную площадь емкости:

F = 2ab+2bh+2ah min (1)

где V=2750 литров.

x1=16,331; x2=10,99

Минимум функции получен в процессе оптимизации по методу Бокса- 1196,065 дм2

В соответствие с ГОСТ 19903 - 74, примем:

h=16,50 дм, b=10,00 дм.

Выразим a из (1) и получим:

Рассчитаем оптимальную толщину листа металла

Выберем углеродистую обыкновенную сталь Ст2сп

Для этой стали 320 МПа, ;

Масса песка.

Нагрузка на стенку емкости наибольшей площади:

Высчитаем нагрузку на 1 погонный сантиметр листа шириной 100 см:

Определим толщину стенки, исходя из условия:

где: l - длина листа (желательно наибольшая, чтобы оставить дополнительный запас прочности);

q - нагрузка на 1 погонный сантиметр, кг/см;

Толщина листа металла, м

Максимально допустимое напряжение металла, Н/мм2.

Выразим из (2) толщину стенки:

Учитывая, что 320 МПа = 3263 кг/см2,

Масса металла

где: F - площадь поверхности емкости, м2 ;

Толщина стенки металла, м;

Плотность металла, кг/м3.

Цена на сталь Ст2сп составляет около 38 руб/кг.

2. Длина сварного шва:

Воспользуемся электродами для нержавеющей стали «УОНИ-13/45»

Цена 88,66 руб/кг;

где: Sшва - поперечная площадь сечения сварного шва, м2;

l - длина сварного шва, м;

Плотность наплавленного металла, кг/м3.

3. Время сварки:

где l - длина сварного шва, м;

v - скорость сварки, м/ч.

Суммарная потребляемая мощность:

Рсум = 5 17 = 85 кВт ч;

Стоимость электроэнергии 5,7 руб/ кВт ч.

4. Для ручной дуговой сварки затраты вспомогательного, подготовительно-заключительного времени и времени на обслуживание рабочего места составляют в среднем 40 - 60%. Воспользуемся средним значением в 50%.

Общее время:

Оплата сварщика VI разряда - 270 руб/час.

Плюс тарифный коэффициент 17% за работу в замкнутом плохо проветриваемом пространстве:

Оплата помощника составит 60% от оплаты сварщика:

8055 0,6 = 4833 руб.

Итого: 8055+4833 = 12888 рублей.

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

Чтобы «прихватить» всю конструкцию, сварщику необходимо наложить около 30% швов.

Оплата крана - 1000 руб/час.

Общая стоимость емкости.

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

Задача на безусловный экстремум

Пусть в некоторой области n-мерного пространства R n задана функция п переменных WQQ. Требуется найти точки X * =(*1 х„), в которых эта функция имеет максимальные

(минимальные значения). Формально это можно записать так:

Задача (13.1) относится к множеству задач, которые объединены термином «задача на безусловный экстремум». Решение такого рода задач целиком и полностью определяется свойствами функции W(X).

Введем некоторые определения. Говорят, что функция W(X) имеет в точке X* локальный максимум (нестрогий), если при любых малых АХ имеет место условие

При выполнении же условия

говорят, что вХ* функция W(X) имеет минимум (нестрогий).

Если неравенства строгие («>» или «максимум (минимум ) называют глобальным («самый большой максимум» и «самый маленький минимум»).

Все точки максимума и минимума функции имеют обобщенное название - экстремумы. Очевидно, что глобальный экстремум является в то же время и локальным экстремумом. Функция W(X) может иметь в области своего определения один, несколько или даже бесконечное количество экстремумов. Она может и не иметь экстремума. На рис. 13.1 представлен график функции одной переменной Дх), рассматриваемой на отрезке [а; Ь]. Внутри отрезка эта функция имеет экстремумы в точках х, х 2 , х 3 , х 4 , х 5 . Из них точка х 2 - глобальный минимум, х 3 - глобальный максимум, а в точках х г и х 5 функция имеет локальные максимумы, в точке х 4 - локальный минимум. Отметим, что граничные точки также могут являться точками экстремума.

Рис. 13.1.

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

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

1) Дх) терпит разрыв (на рис. 13.2 - точка х 2);
2) Дх) непрерывна, но производная/"(х) не существует (точках^;
3) Д(х) = 0 (точки х 3 и х 4);
4) граничные точки (точки х = а и х = Ь).

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

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

Рис. 13.2.

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

Отметим, что эта теорема говорит лишь о возможности решения задачи (13.1), но не о методах ее решения.

В некоторых случаях могут быть сформулированы необходимые условия существования экстремума в точке. Так, для дифференцируемых функций имеет место следующее необходимое условие существования экстремума: если дифференцируемая функция f(x) имеет в точке х = х* экстремум, то ее производная обращается в этой точке в нуль, т.е. f"(x*) = 0.

Для функции нескольких переменных W(X) необходимое условие экстремума выполняется там, где все ее частные производные равны нулю, Например, для точки максимума имеем

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

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

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

Теорема 13.2 . Если в стационарной точке функция дважды дифференцируема и матрица ее вторых производных (матрица

Гессе ) положительно полуопределена, то функция в этой точке имеет минимум, если же матрица отрицательно полуопреде- ленна, то в этой точке функция имеет максимум.

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

Пример 13.1

Найти экстремум функции Дх х, х 2) = х? + х| - 3xiX 2 .

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

Эта система имеет два решения - две стационарные точки: =

= (о, 0),Х 2 =(1, 1).

Составим матрицу Гессе:

Рассмотрим матрицу в каждой из найденных точек.

Для X, имеем Диагональные члены матрицы нулевые, а определитель равен -9. Следовательно, в точке Х 1 = (0, 0) функция имеет максимум.

Для Х 2 имеем . Диагональные члены положительны,

а определитель матрицы равен 27 > 0. Отсюда вывод: в точке Х 2 = (1,1) функция /(xj, х 2) = X] 3 +х| -ЗХ[Х 2 имеет минимум, т.е. min/(x x , х 2) = =/(1,1) =-1.

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

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

Пусть известная функция Дх) на отрезке [а; Ъ ] имеет один максимум, расположенный в неизвестной точке х*. Поскольку х* находится в неизвестной точке отрезка [а; Ь], то его называют отрезком неопределенности. Требуется с наперед заданной точностью г найти точку максимума функции Дх).

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

Рассмотрим схему алгоритма этого метода немного детальнее. Пусть известно, что искомая точка х* находится на отрезке [а 0 ; Ь 0 ]. Выберем середину отрезка с 0 = (а 0 + Ь 0)/2. Далее анализируются два пересекающихся отрезка [а; с 0 + 5] и [с 0 -5; Ь], где 8 - малое число, много меньшее е, т.е. 8 «: е (иногда для удобства выбирают величину S/2). Очевидно, что если/(с 0 - б) >/(с 0 + б), то максимум находится на отрезке [а 0 ; с 0 + 5], иначе - на отрезке [с 0 - б; Ь 0 ]. Поэтому если выполнено условие/(с 0 - б) >/(с 0 + 5), то за новый интервал неопределенности принимается отрезок [а а; Ь х ], где а а = а 0 , Ь а = с 0 + 5, в противном случае - отрезок, где а 0 = с 0 - 8, Ь г = Ь 0 . Этот отрезок вновь делится пополам, и процедура продолжается до выполнения условия | fo fc - a fc |

Пример 13.2

Рассмотрим для примера следующую задачу: на отрезке найти точку минимума функции Дх) = 2х 2 - 4х + 4 с точностью до е = 0,5.

Решение. Выберем параметр 5 = 0,2. Исходный отрезок неопределенности - . Находим точки «середин» этого отрезка:

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

В качестве нового отрезка неопределенности выбираем тот, где находится искомая точка минимума, т.е. = [а; х 2 ] = .

Вновь определим «средние» точки:

Поскольку ДО,95) е, поэтому продолжаем процесс:

Так как/(х 5) >/(х 6), то полагаем а 3 = х 5 , Ь 3 = Ь 2 . Новый отрезок неопределенности [а 3 ; Ь 3 ] = . Его длина 0,675 превышает заданную точность, поэтому продолжаем процесс дихотомии:

Поскольку Дх 7) = 2,1653, Дх 8) = 2,0153, то новым отрезком неопределенности будет [а 4 ; Ь 4 ] = . Этот отрезок имеет длину 0,4375, что меньше, чем 0,5. Следовательно, процесс дихотомии закончен. Из двух точек х 7 и х 8 в качестве искомого приближения х* выбираем точку х 8 , так как/(х 8)

Рис. 13.3.

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

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

Пусть найдено некоторое начальное решение задачи (13.1) Х° =(xJ) ,X2,...,x®) и выбран шаг h. Следующий и все последующие шаги выполняются последовательно согласно следующему рекуррентному соотношению:

Смысл формулы такой: из данной точки X й делается шаг длиной h в направлении, указанном градиентом. Знак «плюс» выбирается при поиске максимума, знак «минус» - в противоположном случае.

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

где 8 - заранее назначенная малая величина - точность решения задачи. Возможно использование и такого условия завершения процесса:

Очевидно, что эффективность градиентного метода зависит от выбранного шага. Если шаг мал, то сходимость в общем случае будет медленной, если шаг большой, то может возникнуть эффект «перешагивания» точки экстремума и процесс не будет сходиться. В связи с этим в ходе решения задачи целесообразно сначала шаг взять достаточно большим, а затем постепенно его уменьшать. Можно, например, задаться изменением шага по формуле h k = h/k.

Пример 13.3

Найти минимум функции

Решение. Выберем начальную точку Х° =(3,1,1) и шаг h = 0,16. Значение функции в этой точке есть /(Х°) = 26, градиент - (4х х; 10х 2 ; 6х 3) = (12; 10; 6).

Проведем согласно формуле (13.4) первую итерацию:

Значение функции в новой точке/(X 1) =4,15.

Для второй итерации градиент равен (4,32; -6; 0,24), шаг h 2 = 0,08. Проведем вторую итерацию:

Значение функции в точке Х 2 следуюгцее: /(X 2) = 1,071. Налицо быстрая сходимость. Продолжая процесс по приведенной схеме, можно быстро приблизиться к точному решению задачи - (0, 0, 0).

Метод статистических испытаний (Монте-Карло). С развитием возможностей вычислительной техники широкое применение находят так называемые методы случайного поиска. Суть этих методов заключается в выборе величины и направления очередного шага случайным образом. Различают направленный и ненаправленный случайный поиск, случайный поиск с обучением и ряд других методов .

Схема простейшего метода случайного поиска максимума может быть такой. Определяется начальная (отправная) точка Х° и из этой точки в случайном направлении совершается перемещение на расстояние |й| в точку X 1 . При этом случайное направление формируется посредством генерации последовательности псевдослучайных чисел в количестве, равном числу переменных анализируемой функции, т.е. компонентами вектора h являются разыгранные значения случайной величины, равномерно распределенной на отрезке , где I - максимальное допустимое смещение по той или иной координате h е .

Если значение функции W (X 1) не увеличилось по сравнению с W(X°), то возвращаются в точку Х°. Разыгрывают новое направление и в этом направлении делают шаг. В том случае, если значение W(X*) > W(X°), точка X 1 принимается за отправную и процедура повторяется уже из этой точки. В противном случае попытка найти эффективное направление повторяется. В каждой очередной точке процедура поиска улучшающего направления повторяется не более заданного числа, например т раз. Та точка, из которой т раз подряд были совершены неудачные попытки увеличения значения анализируемой функции, принимается за точку максимума. В приложении 2 приведены пример и программа его решения на языке Visual Basic for Application.

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

Другое