Итерационные методы решения задач математического программирования со специальной структурой
Диссертация
В настоящее время имеются заделы по решению задач большой размерности методами внутренней точки. В работах и рассматриваются модификации алгоритма Кармаркара для решения разреженных задач большой размерности, но произвольной структуры. В предполагается, что матрица ограничений имеет некоторую специальную структуру без уточнения, какого именно вида. При модификации используются идеи метода… Читать ещё >
Содержание
- Глава 1. Методы решения узкоблочных задач
- 1. 1. Алгоритм, основанный на методе симплексных погружений
- 1. 1. 1. Вычислительная схема метода
- 1. 1. 2. Модификация метода для узкоблочных ЗМП
- 1. 2. Алгоритм, основанный на методе Дикина
- 1. 2. 1. Вычислительная схема метода Дикина
- 1. 2. 2. Алгоритм решения узкоблочных ЗЛП
- 1. 3. Алгоритм, основанный на методе Кармаркара
- 1. 3. 1. Краткое описание метода
- 1. 3. 2. Модификация метода Кармаркара для узкоблочных задач
- 1. 4. Алгоритм, основанный на методе Ринальди
- 1. 4. 1. Краткое описание метода
- 1. 4. 2. Алгоритм решения узкоблочных ЗЛП
- 1. 5. Сравнение трудоемкости методов решения узкоблочных задач
- 1. 1. Алгоритм, основанный на методе симплексных погружений
- Глава 2. Методы решения задач с блочной и ленточной структурой
- 2. 1. Вычислительные схемы, основанные на методе симплексных погружений
- 2. 2. Вычислительные схемы, основанные на методе Дикина
- 2. 2. 1. Алгоритм решения блочных задач
- 2. 2. 2. Алгоритм решения задач с ленточной структурой
- 2. 3. Вычислительные схемы, основанные на методе Кармаркара
- 2. 4. Вычислительные схемы, основанные на методе Ринальди
- 2. 5. Сравнение трудоемкости методов решения блочных и ленточных задач
- Глава 3. Исследование устойчивости предложенных методов
- 3. 1. Исследование устойчивости метода Дикина
- 3. 1. 1. Оценка погрешности решения СЛУ методом квадратного корня
- 3. 1. 2. Определение гарантированной точности вычисления выражения Sn = Л bjCjdj
- 3. 1. 3. Оценка точности итерации метода Дикина
- 3. 2. Исследование устойчивости метода Кармаркара
- 3. 2. 1. Гарантированная точность обращения матрицы по формуле одноранговой модификации
- 3. 2. 2. Оценка точности итерации метода Кармаркара
- 3. 3. Устойчивая модификация метода Дикина
- 3. 1. Исследование устойчивости метода Дикина
Список литературы
- Анцыз С. М., Дикин И. И. Об одном численном методе решения задачи линейного программирования и некоторых его обобщений. // Управляемые системы, 1969. Вып.З. Новосибирск: Ин-т математики СО РАН СССР.
- Анцыз С.М., Гайзлер М. В. Модификация метода Дикина для решения задач со специальной структурой. Второй Сибирский Конгресс по Прикладной и Индустриальной Математике. Новосибирск, 1996. Тезисы докладов. С. 131.
- Анцыз С.М., Гайзлер М. В. О задачах математического программирования со специальной структурой. Проблемы Оптимизации и Экономические Приложения. Омск, 1997 г. Международная конференция, тезисы докладов. С. 16.
- Анцыз С. М., Пудoea М. В. Методы внутренней точки для решения задач со специальной структурой. Новосибирск: Изд-во ИМ СО РАН. 1997 г. 27 с. (Препринт / РАН Сиб. отд-е. Институт математики- № 44).
- Ащепков JI. Т., Белов Б. И., Булатов В. П. Методы решения задач математического программирования и оптимального управления. Новосибирск: Наука, 1984.
- Бахтин А. Е., Пастухов Н. Ф. Об одном композиционном методе построения и анализа оптимальных производственнотранспортных планов. // «Оптимизация развития и размещения промышленного производства». Н-к: Наука, 1974. С. 62−86.
- Белоусов Е. Г., Андронов В. Г. Разрешимость и устойчивость задач полиномиального программирования. М.: Изд-во МГУ, 1993.
- Болдина Н. В. Об одной модели функционирования и развития региона. // Материалы конференции «Дискретный анализ и исследование операций». Новосибирск, 2000 г. С. 205.
- Булавский В. А., Звягина Р. А., Яковлева М. А. Численные методы линейного программирования: специальные задачи. М.: Наука, 1977.
- Верина JI. Ф., Танаев В. С. Декомпозиционные подходы к решению задач математического программирования (обзор). // Экономика и Мат. Методы, 1975. Т. XI. Вып. 6, с. 1160−1172.
- Воеводин В. В. Численные методы алгебры. Теория и алгорифмы. М.: Наука, 1966.
- Воеводин В. В. Ошибки округления и устойчивость в прямых методах линейной алгебры. М.: Изд-во МГУ, 1969.
- Годунов С. К. Решение систем линейных уравнений. Новосибирск: Наука, 1980.
- Годунов С. К. и др. Гарантированная точность решения систем линейных уравнений в евклидовых пространствах. Новосибирск: Наука, 1988.
- Голъштейн Е. Г., Немировский А. С., Соколов Н. А. Новый алгоритм двойственной декомпозиции с приложением к задачам транспортного типа. // Экономика и Мат. Методы, 1994, Т. 30, № 2. С. 127−136.
- Голъштейн Е. Г. Двойственный декомпозиционный метод решения общей задачи дробно-линейного программирования. // Экономика и Мат. Методы, 1999. Т. 35, № 1. С. 80−87.
- Гранберг А. Г. Оптимизация территориальных пропорций народного хозяйства. М.: Экономика, 1973. 246 с.
- Данциг Дж. Линейное программирование, его применение и обобщения. М.:" Прогресс", 1966.
- Дикин И. И., Зоркалъцев В. И. Итеративное решение задач математического программирования. Новосибирск: Наука, 1980.
- Дикин И.И., Попова О. М. Поиск внутренней допустимой точки системы линейных ограничений. Иркутск: Изд -во СЭИ СО РАН, 1995 г. (Препринт / РАН. Сиб. отд-е. СЭИ)
- Дикин И.И. Letter to the editor. //Math. Program. 1988. Vol. 41, P. 393−394.
- Дикин И.И., Попова О. М. Исследование и ускорение сходимости алгоритмов метода внутренних точек. Новосибирск: Наука. СО РАН, 1997.
- Звягина Р. А. Задачи линейного программирования с блочно-диагональными матрицами. // Оптимальное планирование: сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1964. Вып. 2. С. 50−61.
- Звягина Р. А. Программа реализации на М-20 модифицированного симплекс метода с узкоблочной матрицей. // Оптимальное планирование: сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1966. Вып. 4. С. 63−124.
- Звягина Р. А. Об общем методе решения задач линейного программирования блочной структуры. // Оптимизация: сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1971. Вып. 1(18). С. 22−40.
- Звягина Р. А. Об оценке погрешности в системе с клеточным разбиением матрицы. // Оптимизация: сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1984. Вып. 34(51). С. 76−87.
- Зоркалъцев В. И. Обоснование алгоритмов внутренних точек // Журнал вычислительной математики и математической физики, 1999. Т. 39. № 2. С. 208−221.
- Зоркалъцев В. И., Филатов А. Ю. Новые алгоритмы оптимизации в конусе центрального пути. // Дискретный анализ и исследование операций, 1999. Серия 2. Т. 6. № 1. С. 33−42.
- Зоркалъцев В. И. Алгоритмы оптимизации в конусе центрального пути. // Журнал вычислительной математики и математической физики, 2000. Т. 40. № 2. С. 318−327.
- Ильин В. П. Методы неполной факторизации для решения алгебраических систем. М.: Наука, 1995.
- Канторович Л. В. Экономический рассчет наилучшего использования ресурсов. М., Изд-во АН СССР, 1959.
- Корнай ИЛиптак Т. Планирование на двух уровнях. / В кн. «Применение математики в экономических исследованиях», т. 3. М.: Мысль, 1965.
- Лэсдон Л. С. Оптимизация больших систем. М.: Наука, 1975.
- Макаров В. ЛМаршак В. Д. Модели функционирования отраслевых систем М.: Экономика, 1979.
- Первозванский А. А., Гайцгори В. Г. Декомпозиция, агрегирование и приближенная оптимизация. М.: Наука, 1979.
- Писсанецки С. Технология разреженных матриц. М.: Мир, 1988.
- Пудова М.В. О коэффициенте уменьшения трудоемкости для задач со специальной структурой. Международная Сибирская Конференция по Исследованию Операций. Новосибирск, 1998. Тезисы докладов. С. 46.
- Пудова М.В. О коэффициенте уменьшения трудоемкости некоторых алгоритмов для задач со специальной структурой. Проблемы Теоретической Кибернетики. Нижний Новгород, 1999. Тезисы докладов. С. 194.
- Пудова М.В. О коэффициенте уменьшения трудоемкости для задач со специальной структурой. Международная Сибирская Конференция по Исследованию Операций. Новосибирск, 2000. Тезисы докладов. С. 106.
- Пудова М. В. Решение производственно-транспортных задач методами внутренней точки. XII Международная конференция «Методы оптимизации и их приложения». Иркутск. Байкал. 2001 г. Т. 1-«Математическое программирование». С. 43−47.
- Пудова М. В. Устойчивая модификация метода Дикина. // Применение математических методов в исследовании динамических процессов: сб. науч. тр. (под ред А. Т. Семенова). Новосибирск: НГА-ЭиУ, 2002. С. 63−83.
- Рубинштейн Г. Ш. О решении задач линейного программирования большого объема. // Оптимальное планирование: сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1966. Вып. 2. С. 3−22.
- Схрейвер А. Теория линейного и целочисленного программирования. М.: Мир, 1991.
- Танаев В. С. Декомпозиция и агрегирование в задачах математического программирования. Минск, 1987.
- Треногин В. А. Функциональный анализ. М.: Наука, 1993.
- Уилкинсон Дж. X. Алгебраическая проблема собственных значений. М.: Наука, 1970.
- Фаддеева В. Н., Колотилина JI. Ю. Вычислительные методы линейной алгебры: набор матриц для тестирования. Ленинград, 1982.
- Хачиян JI. Г. Полиномиальный алгоритм для задач линейного программирования. Докл АН СССР. 1979. № 20. С. 191−194.
- Шмырев В. И. Контроль исходных данных для программы, реализующей модифицированный симплекс метод с узкоблочной матрицей. // Оптимальное планирование: сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1966. Вып. 4. С. 125−136.
- Шор Н. 3., Соломон Д. И. Декомпозиционные методы в дробно -линейном программировании. Кишинев, 1989.
- Цурков В. И. Декомпозиция в задачах большой размерности. М.: Наука, 1981.
- Юдин Д. Б., Голъштейн Е. Г. Линейное программирование. Теория и конечные методы. М.: Физматгиз, 1963.
- Яковлева М. И. Вычисление сингулярных чисел базисной матрицы в двухкомпонентных задачах линейного программирования. // Оптимизация: сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1984. Вып. 31(48). С. 74−89.
- Adler I., Resende M. G., Veiga G., Karmakar N. An implementation of Karmakar’s algorithm for linear programming// Math. Program. 1984. V. 44. N 3. P. 297−337.
- Bernes E. K. A variation on Karmarkar’s algorithm for solving programming problems // Math. Program. 1986. V. 36. N 2. P. 174 182.
- Choi I. C., Goldfarb D. Exploiting special structure in a primal-dual path-following algorithm // Math. Program. 1993. V. 58. N 2. P. 3353.
- Fujisawa K., Kojima M., Nakata K. Exploiting sparsity in primal-dual interior-point methods for semidefinite programming. // Math. Program. 1997. V. 79. N 2. P. 235−255.
- Gay D. A variant of Karmarkar’s linear programming algorithm for problems in standart form. // Math. Program. 1987. V. 37. N 1. P. 81−90.
- Goldfarb D., Mehrotra S. A relaxed version of Karmarkar’s method 11 Math. Program. 1988. V. 40. N 3. P. 289−315.
- Goldfarb D., Mehrotra S. Relaxed variant of Karmarkar’s algorithm for linear programming with unknown optimal objective value. // Math. Program. 1988. V. 40. N 2. P. 183−195.
- Gonzaga С. C. Polinomial affine algorithms for linear programming. 11 Math. Program. 1990. V. 49. N 2. P. 7−21.
- Gonzaga С. C. An algorithm for Solving Linear Programming Problems in 0(пъЬ) Operations, in: Progress in Mathematical Programming: Interior-Point and Related Methods, N. Megiddo, ed., Springer-Verlag. New York, 1989. P. 1−28.
- Jansen В., Roos С., Terlaky Т. A polynomial primal-dual Dikin-type algorithm for linear programming. // Delft University of Texnology, The Netherlands, 1993. To appear in Journal of Optimisation Theory and Applications. Report N 93−36. 30 P.
- Dikin I.I., Roos C. Convergence of the dual variables for the primal affine scaling method with unit steps in the homogeneous case. // J. Optimisation Theory and Applications, 1997. V. 95. N. 2. P. 305−321.
- Flippo О. E., A. H. J. Rinnooy Kan. Decomposition in general mathematical programming. // Math. Program. 1993. V. 60. N 3. P. 361−381.
- Karmarkar N. A new polynomial-time algorithm for linear programming // Combinatorica. 1984. V. 4. N 4. P. 373−395.
- Kojima M., Mizuno S., Yoshise A. A primal-dual interior-point algorithm for linear programming, in: Progress in Mathematical Programming: Interior-Point and Related Methods, N. Megiddo, ed., Springer-Verlag. New York, 1989. P. 29−47.
- Kojima M., Mizuno S., Yoshise A. An 0(л/пЬ) iteration potential reduction algorithm for linear complementarity problems. // Math. Program. 1991. V. 50. N 3. P. 331−343.
- Megiddo N. Pathways to the Optimal Set in Linear Programming, in: Progress in Mathematical Programming: Interior-Point and Related Methods, N. Megiddo, ed., Springer-Verlag. New York, 1989. P. 131 158.
- Monteiro R., Adler I. Interior path-following primal-dual algorithms. Pt 1: Linear programming. // Math. Program. 1989. V. 44. N 1. P. 27−41.
- Shanno D. F. Computing Karmarkar projections quicly. j I Math. Program. 1988. V. 41. N 1. P. 61−71.
- Rinaldi G. A projective method for linear programming with box-type constrains // Algorithmica. 1986. N 1. P. 517−527.
- Todd M. J. Exploiting special structure in Karmarkar’s linear programming algorithm. // Math. Program. 1988. V. 41. N 1. P. 97 113.
- Todd M. J., Burrell B. P. An extension of Karmarkar’s algorithm for linear programming using dual variables. // Algorithmica. 1986. N 1. P. 409−424.
- Vanderbei R. JCarpenter I. J. Symmetric indefinite systems for interior point methods// Math. Program. 1993. V. 58. N 1. P. 1−33.
- Vanderbei R. J., Meketon M. S., Freedman B. A. A modifications of Karmarkar’s linear programming algorithm. // Algorithmica. 1986. N 1. P. 395−401.
- Ye Y. An Extention of Karmarkar’s Algorithm and the Trust Region Method for Quadratic Programming, in: Progress in Mathematical Programming: Interior-Point and Related Methods, N. Megiddo, ed., Springer-Verlag. New York, 1989. P. 49−63.
- Ye Y., Kojima M. Recovering optimal dual solutions in Karmarkar’s polinomial algorithm for linear programming. // Math. Program. 1987. V. 39. N. 3. P. 305−317.