Компьютерные исследования и моделирование
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Компьютерные исследования и моделирование:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Компьютерные исследования и моделирование, 2017, том 9, выпуск 2, страницы 143–165
DOI: https://doi.org/10.20537/2076-7633-2017-9-2-143-165
(Mi crm55)
 

Эта публикация цитируется в 4 научных статьях (всего в 4 статьях)

МАТЕМАТИЧЕСКИЕ ОСНОВЫ И ЧИСЛЕННЫЕ МЕТОДЫ МОДЕЛИРОВАНИЯ

Прямые мультипликативные методы для разреженных матриц. Линейное программирование

А. Б. Свириденко

ФГБОУ ВПО «Кубанский государственный университет», филиал в г. Новороссийске, Россия, 353922, г. Новороссийск, ул. Героев Десантников, д. 87
Список литературы:
Аннотация: Мультипликативные методы для разреженных матриц являются наиболее приспособленными для снижения трудоемкости операций решения систем линейных уравнений, выполняемых на каждой итерации симплекс-метода. Матрицы ограничений в этих задачах слабо заполнены ненулевыми элементами, что позволяет получать мультипликаторы, главные столбцы которых также разрежены, а операция умножения вектора на мультипликатор по трудоемкости пропорциональна числу ненулевых элементов этого мультипликатора. Кроме того, при переходе к смежному базису мультипликативное представление достаточно легко корректируется. Для повышения эффективности таких методов требуется уменьшение заполненности мультипликативного представления ненулевыми элементами. Однако на каждой итерации алгоритма к последовательности мультипликаторов добавляется еще один. А трудоемкость умножения, которая линейно зависит от длины последовательности, растет. Поэтому требуется выполнять время от времени перевычисление обратной матрицы, получая ее из единичной. Однако в целом проблема не решается. Кроме того, набор мультипликаторов представляет собой последовательность структур, причем размер этой последовательности неудобно велик и точно неизвестен. Мультипликативные методы не учитывают фактора высокой степени разреженности исходных матриц и ограничения-равенства, требуют определения первоначального базисного допустимого решения задачи и, как следствие, не допускают сокращения размерности задачи линейного программирования и регулярной процедуры сжатия — уменьшения размерности мультипликаторов и исключения ненулевых элементов из всех главных столбцов мультипликаторов, полученных на предыдущих итерациях. Таким образом, разработка численных методов решения задач линейного программирования, позволяющих преодолеть или существенно ослабить недостатки схем реализации симплекс-метода, относится к актуальным проблемам вычислительной математики.
В данной работе рассмотрен подход к построению численно устойчивых прямых мультипликативных методов решения задач линейного программирования, учитывающих разреженность матриц, представленных в упакованном виде. Преимущество подхода состоит в уменьшении размерности и минимизации заполнения главных строк мультипликаторов без потери точности результатов, причем изменения в позиции очередной обрабатываемой строки матрицы не вносятся, что позволяет использовать статические форматы хранения данных.
В качестве прямого продолжения данной работы в основу построения прямого мультипликативного алгоритма задания направления спуска в ньютоновских методах безусловной оптимизации предлагается положить модификацию прямого мультипликативного метода линейного программирования путем интеграции одной из существующих техник построения существенно положительно-определенной матрицы вторых производных.
Ключевые слова: численно устойчивые прямые мультипликативные методы, линейное программирование, формат хранения разреженных матриц, параллельное выполнение матричных операций без распаковывания, минимизация заполнения главных строк мультипликаторов, разреженные матрицы.
Поступила в редакцию: 20.07.2016
Исправленный вариант: 06.12.2016
Принята в печать: 19.01.2017
Тип публикации: Статья
УДК: 519.85
Образец цитирования: А. Б. Свириденко, “Прямые мультипликативные методы для разреженных матриц. Линейное программирование”, Компьютерные исследования и моделирование, 9:2 (2017), 143–165
Цитирование в формате AMSBIB
\RBibitem{Svi17}
\by А.~Б.~Свириденко
\paper Прямые мультипликативные методы для разреженных матриц. Линейное программирование
\jour Компьютерные исследования и моделирование
\yr 2017
\vol 9
\issue 2
\pages 143--165
\mathnet{http://mi.mathnet.ru/crm55}
\crossref{https://doi.org/10.20537/2076-7633-2017-9-2-143-165}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/crm55
  • https://www.mathnet.ru/rus/crm/v9/i2/p143
  • Эта публикация цитируется в следующих 4 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Компьютерные исследования и моделирование
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024