Журнал «Современная Наука»

Краткий очерк эволюции ранних методов линейного программирования

Андрианов Александр Львович (соискатель, Московский финансово-промышленный университет)

статья изучает эволюцию алгоритмов решения задач линейного программирования (ЗЛП), и их влияния на развития математики. Центральная проблема, связующая исследования, – поиск полиномиального и эффективного метода решения ЗЛП. Анализируется вклад Левина А.Ю. (метод центрированных сечений Левина-Ньюмана), Немировского А.С. (метод описанных эллипсоидов), Хачияна Л.Г. (доказательство полиномиальной разрешимости ЗЛП на основании нового подхода). Показано значение работы Кармаркара Н., автора алгоритма, сходящегося к решению не по границе допустимого множества, а сквозь многогранник. Проанализирован вклад Левина Л.А., изучавшего универсальные задачи, сложность и сводимость комбинаторных проблем.

Ключевые слова:Линейное программирование, оптимизация, метод центрированных сечений Левина-Ньюмана, метод эллипсоидов, полиномиальная разрешимость, Левин, Немировский, Хачиян, Кармаркар.

Читать полный текст статьи …

Ссылка для цитирования:
Андрианов А. Л. Краткий очерк эволюции ранних методов линейного программирования // Современная наука: актуальные проблемы теории и практики. Серия: Естественные и Технические Науки. -2017. -№01. -С. 23-28

ПРАВОВАЯ ИНФОРМАЦИЯ:
Перепечатка материалов допускается только в некоммерческих целях со ссылкой на оригинал публикации. Охраняется законами РФ. Любые нарушения закона преследуются в судебном порядке.
© ООО "Научные технологии"