Метод Вольфа

Идея метода Вольфа.

Раньше мы перебирали ребра, вершин и т.д. нельзя ли этот набор сделать целенаправленным, так чтобы за малое число итераций локализовать место

Метод начинается с выбора любой точки на многоугольнике ограничений. Возьмем в качестве начальной точки вершину . Линеаризуем , т.е. разложим в ряд Тейлора и ограничимся линейными членами.

1. Найдем на данном многоугольнике, а это Задача линейного применения. Перемещение параллельной самой себе при росте и , что видно из ведет к . Получим , проходящую через точку (0;6).

Далее соединяем точку (0;6) с начальной точкой (откуда мы начинали). В данном примере эта линия совпадает с т.к. многоугольник выпуклый, то эта линия принадлежит выпуклому множеству.

2. Ищем (уже не линеаризованной) на этой линии т.е. задача Лагранжа: на ребре (0;6).

Не приводя вычислений, получим этот в точке (0,5).

3. Линеаризуем в точке (0,5) получим . Найдем на многоугольнике, получим в вершине (2).

4. Соединяем вершину (2) с точкой (0;5) получим ребро (0;5)(2). Ищем на этом ребре. Получим точку (3).

5. Линеаризуем в точке (3). Решаем задачу линейного программирования на многоугольнике. Получим в точке (1). Соединяем (1) и (3) и т.д., приближаясь к точке на ребре (1)(2)многоугольника.

Существуют и другие модификации метода симплексных процедур.

Дата добавления: 2014-01-11