Поиск допустимых решений алгоритмами внутренних точек
В.И. Зоркальцев
Институт систем энергетики им. Л.А. Мелентьева Сибирского отделения Российской академии наук, ул. Лермонтова, 130, г. Иркутск, 664033
zork@isem.irk.ru
Ключевые слова: метод внутренних точек, линейное программирование, ввод в область допустимых решений, interior point algorithm, linear programming, techniques of arriving at the feasible solutions region
Страницы: 249-265
Аннотация
Рассматривается семейство алгоритмов внутренних точек для решения задачи линейного программирования. В этих алгоритмах процедуры ввода в область допустимых решений исходной задачи представлена как процесс оптимизации в области допустимых решений расширенной задачи. Причем расширение осуществляется добавлением только одной новой переменной. Основная цель статьи - изложение теоретического обоснования процесса ввода в область допустимых решений исходной задачи при условии невырожденности расширенной задачи. В частности, доказано, что в случае совместности ограничений исходной задачи, исследуемые процедуры ввода в область допустимых решений приводят к относительно внутренней точке этой области.
DOI: 10.15372/SJNM20160302 |
