Поиск допустимых решений алгоритмами внутренних точек

Рассматривается семейство алгоритмов внутренних точек для решения задачи линейного программирования. В этих алгоритмах процедуры ввода в область допустимых решений исходной задачи представлена как процесс оптимизации в области допустимых решений расширенной задачи. Причем расширение осуществляется добавлением только одной новой переменной. Основная цель статьи –изложение теоретического обоснования процесса ввода в область допустимых решений исходной задачи при условии невырожденности расширенной задачи. В частности, доказано, что в случае совместности ограничений исходной задачи, исследуемые процедуры ввода в область допустимых решений приводят к относительно внутренней точке этой области.