Навигация
6.2.2 Метод проекции градиента
Этот метод является аналогом метода градиентного спуска, используемого в задачах без ограничений. Его идея состоит в проектировании точек, найденных методом наискорейшего спуска, на допустимое множество, определяемое ограничениями. Проекцией точки y на множество Х называется точка P(y)ОХ такая, что || P(y) - y || Ј || x - y || для всех хОХ. Задача проектирования формализуется как || x - y ||2® min, xОХ.
Выбор направления спуска осуществляется следующим образом :
Находим точку rk = хk - aЧ j’( хk )
Находим проекцию pk точки rk на множество Х
Направление спуска получаем как -sk = pk - хk
Таким образом итерация метода имеет вид: xk+1=PX[ xk - akЧСf( xk ) ], где РX(у) - ортогональная проекция точки у на множество Х.
Для отыскания направления спуска sk необходимо решить задачу минимизации квадратичной функции || rk - х ||2 на множестве Х. В общем случае эта задача того же порядка сложности, что и исходная, однако для задач, допустимое множество которых имеет простую геометрическую структуру, отыскание проекции значительно упрщается. Например, для многомерного параллелепипида QN={xОRN : a Ј x Ј b }, отыскание проекции осуществляется путем сравнения n чисел и имеет вид P(x)={ ai, xibi }.
6.2.3 Метод случайного спуска
Метод характеризуется тем, что в качестве направления спуска sK выбирается некоторая реализация n-мерной случайной величины S с известным законом распределения. Об эффективности этого метода судить трудно, однако благодаря использованию быстродействующих ЭВМ он оказывается практически полезным.
6.3 Метод множителей Лагранжа
Идея метода состоит в отыскании седловой точки функции Лагранжа задачи (6.1). Для нахождения решения вводится набор переменных li, называемых множители Лагранжа, и составляется функция Лагранжа, имеющая вид:
| | (6.6) |
Алгоритм метода состоит в следующем:
Составление функции Лагранжа
Нахождение частных производных функции Лагранжа
| | (6.7) |
Решение системы из n+m уравнений вида
| | (6.8) |
Решениями системы (6.8) являются точки, которые могут быть решениями задачи.
Выбор точек, в которых достигается экстремум и вычисление функции j(х) в этих точках.
7. Линейное программирование
Задача линейного программирования в каноническом виде имеет вид[15,16]:
|
| (7.1) |
Приведение к каноническому виду любой задачи линейного программирования осуществляется путем введения дополнительных неотрицательных переменных, за счет чего ограничения, имеющие вид неравенств, принимают вид эквивалентных им равенств.
Любая задача линейного программирования может быть решена за конечное число итераций с помощью симплексного метода[17,18]. Следует отметить, что поскольку этот метод разработан для неотрицательных элементов xj , это условие учитывается неявно и в систему уравнений (7.1) при численной реализации не входит.
7.1 Алгоритм симплексного метода
1. Приведение к каноническому виду
2. Выбор начального базиса
3. Проверка оптимальности базиса
Матрицу А можно рассматривать как совокупность столбцов aj т.е. еajЧxj=b где j=1,N. Не ограничивая общности можно считать, что базис образуют первые m столбцов, тогда остальные можно представить в виде ak=еajЧljk , j=1,m где ljk.- некоторые числа.
Рассмотрим коэффициенты Dk=еcjЧljk - ck где j=1,m и k=1,N. Заметим, что для базовых столбцов Dk є 0. Проверка на оптимальность осуществляется следующим образом:
| Dk < 0 , k=1,N | - текущий базис оптимален |
| | - решение не ограничено сверху |
| | - существует другой, более подходящий базис |
Похожие работы
... поверхностной трещины, когда однородное (или неоднородное) поле пересекает поверхностную трещину в ферромагнитной пластине (рис.4). Рисунок 4. Поток магнитного рассеяния для двумерного случая в поперечном сечении ферромагнитной пластины Считается, что однородное магнитное поле распространяется слева направо. Вблизи дефекта поток разделяется на две части. Одна часть потока пытается обогнуть ...
... приборов и визуальные наблюдения за процессом позволяют оперативно реагировать на возможные отклонения, во многом обеспечивает качество сварных соединений. При сварке ответственных конструкций используют системы автоматического управления и регулирования параметров режима с помощью датчиков автоматического контроля, встроенных в сварочное оборудование. В некоторых случаях ведут непрерывную запись ...
... в процесс, были одобрены, спланированы, получили материально-техническую поддержку и управлять в целях заинтересованных сторон. Глава 3. Перспектива автоматизации системы неразрушающего контроля изделий на предприятиях машиностроительного профиля 3.1 Комплексная технология АУЗК В связи с высоким техническим уровнем современного производства методом и средством НК предъявляют высокие ...
... , повысить вероятность выявления дефектов и, с другой стороны, снизить различные технико-экономические затраты на проведение контроля. 2. Проектирование системы контроля знаний 2.1 Общая структура системы По своей логической структуре система состоит из трёх частей: - подсистемы конфигурирования теста; - подсистемы тестирования; - подсистема сервиса. ...
0 комментариев