Аннотация:
В статье предлагается новый алгоритм вычисления вершины многогранника, представляющего собой область допустимых решений системы линейных ограничений. Алгоритм, получивший название VeSP, начинает работу в произвольной точке многогранника и, перемещаясь по его граням, завершает свою работу в некоторой его вершине. Для вычисления направления движения по грани используется проекционный метод, суть которого заключается в следующем. Для точки текущего приближения вычисляется аффинное подпространство, являющееся аффинной оболочкой грани, на которой расположена эта точка. К точке текущего приближения прибавляется ненулевой вектор, дающий «внешнюю» точку. Из «внешней» точки по известной аналитической формуле вычисляется ортогональная проекция на текущее аффинное подпространство. Точка проекции определяет направление движения по грани до ее границы, что дает следующее приближение. При каждом таком перемещении размерность текущей грани уменьшается. В конечном итоге приходим к грани нулевой размерности, то есть к вершине многогранника. Дается формальное описание алгоритма VeSP. Доказывается сходимость алгоритма VeSP к вершине многогранника за конечное число итераций, не превышающих размерность пространства. Приводится информация о реализации алгоритма VaSP на языке C++. Описываются результаты вычислительных экспериментов на эталонных задачах из репозитория Netlib-LP. Результаты экспериментов показывают, что алгоритм VeSP применительно ко всем тестовым задачам успешно нашел вершину многогранника за количество итераций, не превышающее размерность пространства. Для большинства задач время нахождения вершины на обычном персональном компьютере потребовало менее одной секунды.
Полный текст:
PDF файл (630 kB)