- Код статьи
- S0205-96060000513-1-
- DOI
- 10.31857/S60000513-1-1
- Тип публикации
- Статья
- Статус публикации
- Опубликовано
- Авторы
- Том/ Выпуск
- Том 38 / №2
- Страницы
- 351-361
- Аннотация
- В статье рассмотрены становление и начальные этапы развития алгоритмов решения задач линейного программирования (ЗЛП) и их влияние на развитие математики. Центральная проблема, связующая исследования, - поиск полиномиального и эффективного метода решения ЗЛП. Анализируется вклад А.Ю. Левина (метод центрированных сечений Левина - Ньюмана), А.С. Немировского (метод описанных эллипсоидов), Л.Г. Хачияна (доказательство полиномиальной разрешимости ЗЛП на основании нового подхода). Показано значение работы Н. Кармаркара, создавшего алгоритм, сходящийся к решению не по границе допустимого множества, а сквозь многогранник. Проанализирован вклад Л.А. Левина, изучавшего универсальные задачи, сложность и сводимость комбинаторных проблем.
- Ключевые слова
- линейное программирование, оптимизация, метод центрированных сечений Левина – Ньюмана, метод эллипсоидов, полиномиальная разрешимость, А.Ю. Левин, А. С. Немировский, Л. Г. Хачиян, Н.К. Кармаркар
- Дата публикации
- 01.04.2017
- Всего подписок
- 4
- Всего просмотров
- 1173
Президиум РАНВопросы истории естествознания и техники
- ISSN (Print) 0205-9606
- ISSN (Online)2713-041X
СТАНОВЛЕНИЕ И НАЧАЛЬНЫЕ ЭТАПЫ РАЗВИТИЯ МЕТОДОВ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Индексирование
Scopus
Crossref
Высшая аттестационная комиссия
При Министерстве образования и науки Российской Федерации
Научная электронная библиотека