Метод деформируемого многогранника

Государственный комитет Российской Федерации по высшему образованию НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Кафедра АСУ Реферат по дисциплине ИССЛЕДОВАНИЕ ОПЕРАЦИЙ на тему МЕТОД ДЕФОРМИРУЕМОГО МНОГОГРАННИКА Студент Борзов Андрей Николаевич Группа АС–513 Преподаватель Ренин Сергей Васильевич Новосибирск 1997 Поиск по деформируемому многограннику Впервые метод деформируемого многогранника был предложен

Нелдером и Мидом. Они предложили метод поиска, оказавшийся весьма эффективным и легко осуществляемым на ЭВМ. Чтобы можно было оценить стратегию Нелдера и Мида, кратко опишем симплексный поиск Спендли, Хекста и Химсворта, разработанный в связи со статистическим планированием эксперимента. Вспомним, что регулярные многогранники в En являются симплексами. Например, как видно из рисунка 1, для случая двух переменных регулярный

симплекс представляет собой равносторонний треугольник (три точки); в случае трёх переменных регулярный симплекс представляет собой тетраэдр (четыре точки) и т.д. A A B а б B Рисунок SEQ Рисунок * ARABIC 1. Регулярные симплексы для случая двух (а) и трёх (б) независимых переменных.  обозначает наибольшее значение f(x). Стрелка указывает направление наискорейшего улучшения. При поиске минимума целевой функции f(x) пробные векторы x могут

быть выбраны в точках En, находящихся в вершинах симплекса, как было первоначально предложено Спендли, Хекстом и Химсвортом. Из аналитической геометрии известно, что координаты вершин регулярного симплекса определяются следующей матрицей D, в которой столбцы представляют собой вершины, пронумерованные от 1 до (n+1), а строчки – координаты, i принимает значения от 1 до n: – матрица n X (n+1), где t – расстояние между двумя вершинами.

Например, для n=2 и t=1 треугольник, приведённый на рисунке 1, имеет следующие координаты: Вершина x1,i x2,i 1 0 0 2 0.965 0.259 3 0.259 0.965 Целевая функция может быть вычислена в каждой из вершин симплекса; из вершины, где целевая функция максимальна (точка A на рисунке 1), проводится проектирующая прямая через центр тяжести симплекса. Затем точка A исключается и строится новый симплекс, называемый отражённым, из оставшихся прежних точек и одной