Все выпуски
- 2024 Том 16
- 2023 Том 15
- 2022 Том 14
- 2021 Том 13
- 2020 Том 12
- 2019 Том 11
- 2018 Том 10
- 2017 Том 9
- 2016 Том 8
- 2015 Том 7
- 2014 Том 6
- 2013 Том 5
- 2012 Том 4
- 2011 Том 3
- 2010 Том 2
- 2009 Том 1
- Просмотров за год: 2.
-
Прямые мультипликативные методы для разреженных матриц. Линейное программирование
Компьютерные исследования и моделирование, 2017, т. 9, № 2, с. 143-165Просмотров за год: 10. Цитирований: 2 (РИНЦ).Мультипликативные методы для разреженных матриц являются наиболее приспособленными для снижения трудоемкости операций решения систем линейных уравнений, выполняемых на каждой итерации симплекс-метода. Матрицы ограничений в этих задачах слабо заполнены ненулевыми элементами, что позволяет получать мультипликаторы, главные столбцы которых также разрежены, а операция умножения вектора на мультипликатор по трудоемкости пропорциональна числу ненулевых элементов этого мультипликатора. Кроме того, при переходе к смежному базису мультипликативное представление достаточно легко корректируется. Для повышения эффективности таких методов требуется уменьшение заполненности мультипликативного представления ненулевыми элементами. Однако на каждой итерации алгоритма к последовательности мультипликаторов добавляется еще один. А трудоемкость умножения, которая линейно зависит от длины последовательности, растет. Поэтому требуется выполнять время от времени перевычисление обратной матрицы, получая ее из единичной. Однако в целом проблема не решается. Кроме того, набор мультипликаторов представляет собой последовательность структур, причем размер этой последовательности неудобно велик и точно неизвестен. Мультипликативные методы не учитывают фактора высокой степени разреженности исходных матриц и ограничения-равенства, требуют определения первоначального базисного допустимого решения задачи и, как следствие, не допускают сокращения размерности задачи линейного программирования и регулярной процедуры сжатия — уменьшения размерности мультипликаторов и исключения ненулевых элементов из всех главных столбцов мультипликаторов, полученных на предыдущих итерациях. Таким образом, разработка численных методов решения задач линейного программирования, позволяющих преодолеть или существенно ослабить недостатки схем реализации симплекс-метода, относится к актуальным проблемам вычислительной математики.
В данной работе рассмотрен подход к построению численно устойчивых прямых мультипликативных методов решения задач линейного программирования, учитывающих разреженность матриц, представленных в упакованном виде. Преимущество подхода состоит в уменьшении размерности и минимизации заполнения главных строк мультипликаторов без потери точности результатов, причем изменения в позиции очередной обрабатываемой строки матрицы не вносятся, что позволяет использовать статические форматы хранения данных.
В качестве прямого продолжения данной работы в основу построения прямого мультипликативного алгоритма задания направления спуска в ньютоновских методах безусловной оптимизации предлагается положить модификацию прямого мультипликативного метода линейного программирования путем интеграции одной из существующих техник построения существенно положительно-определенной матрицы вторых производных.
Журнал индексируется в Scopus
Полнотекстовая версия журнала доступна также на сайте научной электронной библиотеки eLIBRARY.RU
Журнал входит в систему Российского индекса научного цитирования.
Журнал включен в базу данных Russian Science Citation Index (RSCI) на платформе Web of Science
Международная Междисциплинарная Конференция "Математика. Компьютер. Образование"
