Поиск допустимых решений алгоритмами внутренних точек (300,00 руб.)

19, №3 УДК 519.23 Поиск допустимых решений алгоритмами внутренних точек∗ В.И. Зоркальцев Институт систем энергетики им. <...> Рассматривается семейство алгоритмов внутренних точек для решения задачи линейного программирования. <...> В этих алгоритмах процедуры ввода в область допустимых решений исходной задачи представлена как процесс оптимизации в области допустимых решений расширенной задачи. <...> Основная цель статьи — изложение теоретического обоснования процесса ввода в область допустимых решений исходной задачи при условии невырожденности расширенной задачи. <...> В частности, доказано, что в случае совместности ограничений исходной задачи, исследуемые процедуры ввода в область допустимых решений приводят к относительно внутренней точке этой области. <...> DOI: 10.15372/SJNM20160302 Ключевые слова: метод внутренних точек, линейное программирование, ввод в область допустимых решений. <...> A family of interior point algorithms for the linear programming problems is considered. <...> Keywords: interior point algorithm, linear programming, techniques of arriving at the feasible solutions region. <...> Семейство алгоритмов внутренних точек Исходной задачей будем называть задачу линейного программирования в стандартной форме: cx→min, x ∈ X, где ∗Работа поддержана грантом РФФИ (проект № 15-07-074121а). <...> Рассматривается вычислительный процесс, вырабатывающий последовательность векторов xk ∈ Rn по правилу xk+1 = xk +λksk, k = 0, 1, 2, . . . , (3) где k — номер итерации, sk — вектор Rn направления корректировки решения, λk — вещественная величина шага корректировки. <...> Причем на всех итерациях xk > 0, т. е. все компоненты вектора xk положительные. <...> В качестве стартовой точки может использоваться любой вектор x0 с положительными всеми компонентами. <...> Направление улучшения решения определяется как результат решения задачи минимизации квадратичной, сепарабельной, строго выпуклой функции от вектора переменных s ∈ Rn при линейных ограничениях–равенствах: sk = arg min{Fk(s) : As = rk}. <...> От весовых коэффициентов требуется выполнение неравенств: σxk где σ, ¯ j  ≤ dk j ≤ ¯ σxk j , j = 1 <...>