Текущий выпуск Номер 2, 2025 Том 17

Все выпуски

Результаты поиска по '2024年南大核心期刊目录':
Найдено статей: 109
  1. От редакции
    Компьютерные исследования и моделирование, 2024, т. 16, № 1, с. 5-10
  2. От редакции
    Компьютерные исследования и моделирование, 2024, т. 16, № 3, с. 581-584
  3. От редакции
    Компьютерные исследования и моделирование, 2024, т. 16, № 4, с. 821-823
  4. От редакции
    Компьютерные исследования и моделирование, 2024, т. 16, № 5, с. 1037-1040
  5. От редакции
    Компьютерные исследования и моделирование, 2024, т. 16, № 6, с. 1341-1343
  6. От редакции
    Компьютерные исследования и моделирование, 2024, т. 16, № 7, с. 1533-1538
  7. От редакции
    Компьютерные исследования и моделирование, 2025, т. 17, № 1, с. 5-7
  8. От редакции
    Компьютерные исследования и моделирование, 2025, т. 17, № 2, с. 175-177
  9. Яшина М.В., Таташев А.Г.
    Памяти А. П. Буслаева — друга, ученого и основателя научной школы математического моделирования транспортных потоков
    Компьютерные исследования и моделирование, 2024, т. 16, № 1, с. 11-16
  10. Свириденко А.Б.
    Оценка числа итераций для сильно полиномиальных алгоритмов линейного программирования
    Компьютерные исследования и моделирование, 2024, т. 16, № 2, с. 249-285

    Рассматривается прямой алгоритм решения задачи линейного программирования (ЛП), заданной в каноническом виде. Алгоритм состоит из двух последовательных этапов, на которых прямым методом решаются приведенные ниже задачи ЛП: невырожденная вспомогательная задача (на первом этапе) и некоторая задача, равносильная исходной (на втором). В основе построения вспомогательной задачи лежит мультипликативный вариант метода исключения Гаусса, в самой структуре которого заложены возможности: идентификации несовместности и линейной зависимости ограничений; идентификации переменных, оптимальные значения которых заведомо равны нулю; фактического исключения прямых переменных и сокращения размерности пространства, в котором определено решение исходной задачи. В процессе фактического исключения переменных алгоритм генерирует последовательность мультипликаторов, главные строки которых формируют матрицу ограничений вспомогательной задачи, причем возможность минимизация заполнения главных строк мультипликаторов заложена в самой структуре прямых методов. При этом отсутствует необходимость передачи информации (базис, план и оптимальное значение целевой функции) на второй этап алгоритма и применения одного из способов устранения зацикливания для гарантии конечной сходимости.

    Представлены два варианта алгоритма решения вспомогательной задачи в сопряженной канонической форме. Первый основан на ее решении прямым алгоритмом в терминах симплекс-метода, а второй — на решении задачи, двойственной к ней, симплекс-методом. Показано, что оба варианта алгоритма для одинаковых исходных данных (входов) генерируют одинаковую последовательность точек: базисное решение и текущее двойственное решение вектора оценок строк. Отсюда сделан вывод, что прямой алгоритм — это алгоритм типа симплекс-метода. Также показано, что сравнение вычислительных схем приводит к выводу, что прямой алгоритм позволяет уменьшить по кубическому закону число арифметических операций, необходимых для решения вспомогательной задачи, по сравнению с симплекс-методом. Приводится оценка числа итераций.

    Ключевые слова: линейное программирование, алгоритм симплекс-метода, прямой алгоритм, число итераций, сильно полиномиальный алгоритм.
Страницы: следующая последняя »

Журнал индексируется в Scopus

Полнотекстовая версия журнала доступна также на сайте научной электронной библиотеки eLIBRARY.RU

Журнал входит в систему  Российского индекса научного цитирования.

Журнал включен в базу данных Russian Science Citation Index (RSCI) на платформе Web of Science

Международная Междисциплинарная Конференция "Математика. Компьютер. Образование"

Международная Междисциплинарная Конференция МАТЕМАТИКА. КОМПЬЮТЕР. ОБРАЗОВАНИЕ.

Copyright © 2009–2025 Институт компьютерных исследований