УДК 519.85
Т.В. БЄЛИХ,
Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, Україна,
krainaz@ukr.net
В.І. ЗОРКАЛЬЦЕВ,
Лімнологічний інститут СО РАН, Іркутськ, Росія,
zork@isem.irk.ru
АЛГОРИТМИ ВНУТРІШНІХ ТОЧОК: ІСТОРІЯ СТВОРЕННЯ,
РЕЗУЛЬТАТИ ДОСЛІДЖЕНЬ, ЗАСТОСУНКИ ТА ПЕРСПЕКТИВИ
Анотація. Розглянуто низку алгоритмів внутрішніх точок для розв’язання задач лінійного програмування.
Наведено результати їхнього теоретичного обґрунтування. Виокремлено підмножини алгоритмів,
що мають лінійну, асимтотично незалежну від параметрів розв’язуваної задачі швидкість збіжності,
підмножину алгоритмів, що приводять до відносно внутрішніх точок множини оптимальних розв’язків.
Викладено історію створення та розвитку алгоритмів. Наведено нові модифікації алгоритмів внутрішніх точок,
що містять як окремий випадок розроблені раніше алгоритми.
Ключові слова: лінійне програмування, лінійні нерівності, алгоритми внутрішніх точок.
ПОВНИЙ ТЕКСТ
СПИСОК ЛІТЕРАТУРИ
- Шор Н.З. Монотонные модификации r-алгоритмов и их приложения. Кибернетика и системный анализ. 2002. № 6. С. 74–96.
- Сергиенко И.В., Стецюк П.И. О трёх научных идеях Н.З. Шора. Кибернетика и системный анализ. 2012. № 1. C. 4–10.
- Стецюк П.И., Фесюк А.В., Хомяк О.Н. Обобщенный метод эллипсоидов. Кибернетика и системный анализ. 2018. Т. 54, № 4. C. 70–80.
- Стецюк П.И. r-алгоритмы и эллипсоиды. Кибернетика и системный анализ. 1996. № 1. С. 113–134.
- Дикин И.И., Зоркальцев В.И. Итеративное решение задач математического программирования: алгоритмы метода внутренних точек. Новосибирск: Наука, 1980. 144 с.
- Зоркальцев В.И., Пержабинский С.М., Стецюк П.И. Поиск нормальных решений СЛАУ при двусторонних ограничениях на переменные методом внутренних точек. Кибернетика и системный анализ. 2015. Т. 51, № 6. С. 71–80.
- Епифанов С.П., Зоркальцев В.И. Задача потокораспределения с нефиксированными отборами. Кибернетика и системный анализ. 2011. № 1. С. 81–92.
