WikiSort.ru - Программирование

ПОИСК ПО САЙТУ | о проекте

Метод эллипсоидов — алгоритм нахождения точки, лежащей в пересечении выпуклых множеств. Разработан А.С. Немировским и доведён до алгоритмической реализации Л.Г. Хачияном в ВЦ АН СССР.

Описание алгоритма

В начале выбирается большой шар, содержащий пересечение выпуклых множеств. Способ построения этого шара зависит от задачи. Далее на каждом шаге имеется эллипсоид, заданный центром и векторами . Эллипсоиду принадлежат точки для которых . Отметим, что один и тот же эллипсоид можно задать несколькими способами. Если центр этого эллипсоида принадлежит всем выпуклым множествам, то искомая точка найдена. Иначе существует гиперплоскость , проходящая через точку , такая, что одно из множеств целиком лежит по одну сторону от неё. Тогда можно перейти от исходного базиса к другому базису такому, что параллельны , а направлен в сторону множества. Положим теперь , , при . Этот новый эллипсоид содержит половину старого и имеет меньший объём. Таким образом, объём эллипсоида уменьшается экспоненциально с ростом числа шагов и искомая точка будет найдена за шагов, где  — объем исходного шара, а  — объем области пересечения. Общее время работы алгоритма получается равным , где  — число множеств,  — время проверки принадлежности точки множеству.

Применение к задаче линейного программирования

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

Эффективность метода

Полиномиальный алгоритм теоретически мог бы стать новым стандартом, однако, на практике алгоритм Хачияна применять следует с осторожностью: существуют задачи размером в 50 переменных, для которых требуются более 24 тысяч итераций метода Хачияна, количество же существенно более простых итераций симплекс-метода в таких случаях исчисляется сотнями или даже десятками [1][2]. Однако, есть примеры задач, для которых алгоритмы этого класса работают в сотни раз эффективнее стандартных реализаций симплекс-метода.

Примечания

Литература

  • С.А. Ашманов. Линейное программирование. М.: Главная редакция физико-математической литературы, 1981. — С. 288-289.
  • А. Схрейвер. Теория линейного и целочисленного программирования, т1. М.: «Мир», 1991. ISBN 5-03-002754-8.
  • С. Николенко. Теория и практика сложности // Компьютерра. М.: ООО Журнал «Компьютерра», 2005. Вып. 31.

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии