28. Метод симплекса
Под симплексом понимается n-мерный выпуклый многогранник n-мерного пространства, имеющий n+1 вершину. Для n=2 это треугольник, а при n=3 это тетраэдр.
Идея метода состоит в сравнении значений функции в n+1 вершинах симплекса и перемещении симплекса в направлении лучшей точки. В рассматриваемом методе симплекс перемещается с помощью операций отражения. Далее принято следующее: х0(k), х1(k), …, хn(k) - вершины симплекса, где к - номер итерации.
Схема алгоритма
Шаг 1. Построение начального симплекса.
Для этого задаются начальная точка х0(0) и длина ребра симплекса l. Формируются остальные вершины симплекса:
xi(0) = x0(0) + l*ei (i=1,2,…,n), где ei - единичные векторы.
Шаг 2. Определение направления улучшения решения.
Для этого на к-й итерации вычисляются значения целевой функции в каждой точке симплекса. Пусть для всех i: f(xmin(k))f(xi(k))f(xmax(k)), где min, max, i - номера соответствующих вершин симплекса. Опр-м центр тяжести всех точек, исключая точку xmax(k), Ck=(xi(k))/n.
Тогда направление улучшения решения опр-ся вектором Ck-xmax(k).
Шаг 3. Построение отраженной точки.
Замена вершины xmax(k) с максимальным значением целевой функции на новую точку с помощью операции отражения, результатом которой является новая точка:
uk=ck+(ck-xmax(k))=2ck-xmax(k)
Шаг 4. Построение нового симплекса.
Вычисляем f(uk). При этом возможен один из двух случаев:
а) f(uk)<f(xmax(k);
б) f(uk)f(xmax(k).
Случай а): вершина xmax заменяется на uk, чем определяется набор вершин к+1-й итерации и к-я итерация заканчивается.
Случай б): в результате отражения получается новая точка uk, значение функции в которой еще хуже, чем в точке xmax, то есть отражать симплекс некуда. Поэтому в этом случае производится пропорциональное уменьшение симплекса (например, в 2 раза) в сторону вершины xmin(k): xi(k+1)=x^i=(xi(k)+xmin(k))/2, где i=0,1,…,n.
На этом к-я итерация заканчивается.
Шаг 5. Проверка сходимости.
Если , то поиск минимума заканчивается и полагается
.В противном случае к=к+1 и происходит переход к шагу 2.
29. Метод циклического покоординатного спуска.
30. Градиент. Градиент и направление роста целевой функции. Градиент и линия уровня.
Градиент – вектор, своим направлением указывающий направление наибольшего возрастания некоторой величины, значение которой меняется от одной точки пространства к другой, а по величине (модулю) равный скорости роста этой величины в этом направлении.
Градиент указывает направление скорейшего возрастания функции. В самом деле, приращение (смещение вдоль поверхности), с точностью до бесконечно малой (которая повлиять не сможет из-за малости) равно дифференциалу (смещению вдоль касательной плоскости), а он равен Adx+Bdy, то есть скалярному произведению градиента на вектор приращения (dx,dy). Если этот последний одной длины, только направление можно менять, то скалярное произведение максимально, если угол между векторами равен единице, то есть векторы направлены в одну сторону: приращение направлено по градиенту.
Определение. Линией уровня функции U=F(X, Y) называется линия F(X, Y)=С на плоскости XOy, в точках которой функция сохраняет постоянное значение U=C.
Линии уровня геометрически изображаются на плоскости изменения независимых переменных в виде кривых линий. Получение линий уровня можно представить себе следующим образом. Рассмотрим множество С, которое состоит из точек трехмерного пространства с координатами (X, Y, F(X, Y)=Const), которые, с одной стороны, принадлежат графику функции Z=F(X, Y), с другой - лежат в плоскости, параллельной координатной плоскости ХОУ, и отстоящей от неё на величину, равную заданной константе. Тогда для построения линии уровня достаточно поверхность графика функции пересечь плоскостью Z=Const и линию пересечения спроектировать на плоскость ХОУ. Проведенное рассуждение является обоснованием возможности непосредственно строить линии уровня на плоскости ХОУ.
31. Градиентные методы
32. Градиентный метод с постоянным шагом.
33. Градиентный метод с дроблением шага.
34. Метод наискорейшего спуска.
35. Метод покоординатного спуска
36. Метод покоординатного спуска с постоянным шагом.
37. Метод покоординатного спуска с дроблением шага.
38. Алгоритм Гаусса-Зейделя
Метод Гаусса-Зейделя представляет собой итерационную процедуру для поиска приближенных решений системы линейных алгебраических уравнений с произвольно выбранной точностью. Метод применяется к квадратным матрицам с ненулевыми элементами на их диагоналях, и сходимость гарантируется, если матрица диагонально доминирует.
39. Постановка задач линейного программирования
Линейное программирование (ЛП)— это метод математического моделирования, разработанный для оптимизации использования ограниченных ресурсов. ЛП успешно применяется в военной области, индустрии, сельском хозяйстве, транспортной отрасли, экономике, системе здравохранения и даже в социальных науках. Широкое использование этого метода также подкрепляется высокоэффективными компьютерными алгоритмами, реализующими данный метод. На алгоритмах линейного программирования (учитывая их компьютерную эффективность) базируются оптимизационные алгоритмы для других, более сложных типов моделей и задач исследования операций (ИО), включая целочисленное, нелинейное и стохастическое программирование. Вычисления в методе ЛП, как и во многих задачах ИО, как правило, очень трудоемкие и поэтому требуют применения вычислительной техники. Свободно распространяемая программа TORA, сопровождающая изложение материала данной книги, значительно облегчает эту вычислительную ношу.
