Алгоритм симплекс-метода с использованием двойного базиса (330,00 руб.)

18, №4 УДК 519.852.61 Алгоритм симплекс-метода с использованием двойного базиса Г.И. Забиняко Институт вычислительной математики и математической геофизики Сибирского отделения Российской академии наук, просп. <...> Алгоритм симплекс-метода с использованием двойного базиса // Сиб. журн. вычисл. математики / РАН. <...> Рассматривается алгоритм симплекс-метода, в котором на итерациях не требуется в явном виде обновление LU-разложений. <...> Решения, полученные с фиксированными факторами LU, корректируются с помощью небольших вспомогательных матриц. <...> An algorithm of the simplex method using a dual basis // Siberian J. <...> An algorithm of the simplex method not requiring an explicit updating of the LU decomposition in iterations is considered. <...> Введение Рассмотрим применение модифицированного симплекс-метода [1] для решения задачи линейного программирования (ЛП): минимизировать cx при условиях Ax = b, α ≤ x ≤ β, где A — матрица размера m Ч n, векторы c, x, α, β ∈ Rn, b ∈ Rm, n ≥ m. <...> Базисным переменным соответствует базисная матрица, состоящая из m p -е место, заменяется столбцом aj. <...> Матрица Bk используется для определения направления y изменения исходных переменных и двойственных переменных π из линейных (aj −ai)e  Забиняко Г.И., 2015 c независимых столбцов матрицы A. <...> На итерациях метода происходят изменения базисной матрицы Bk+1 = Bk + p , где ep — p -й единичный орт из Rm, а столбец ai, который занимал в базисе 350 СИБИРСКИЙ ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ. <...> Эффективность и устойчивость метода существенно зависит от способа обновления k π = ck, где ck — целевые коэффициенты, отвечающие базисным LU-разложения на итерациях. <...> В модифицированном семплекс-методе выделяется этап так называемого перепостроения обратных матриц, когда заново производится LU-разложение текущей базисной матрицы. <...> Бартелс и Голуб предложили численно устойчивый алгоритм (BG) обновления LU МножительMk получается из единичной матрицы размера mЧm, у которой в столбцах k −1 и k расположена матрица В результате в матрице U на p -м месте окажется столбец γ = L−1aj <...>