Какие методы существуют для решения линейных алгоритмических задач?

Некоторые методы, которые используются для решения линейных алгоритмических задач:

• Симплекс-метод. 15 Разработан Джорджем Данцигом в 1947 году. 1 Суть метода — построение допустимого решения в вершине многогранника, а затем прохождение по пути по краям многогранника к вершинам с неубывающими значениями целевой функции. 1
• Графический метод. 2 Алгоритм включает следующие шаги: 2

1. Начертить область определения задачи (допустимое множество). 2
2. Найти градиент целевой функции. 2 Обычно его строят в начале координат. 2
3. Провести линию уровня целевой функции (то есть множество всех точек на плоскости, в которых функция принимает одно и то же значение). 2
4. Передвигать линию уровня параллельно самой себе до касания с допустимым множеством. 2

• Метод искусственного базиса. 2
• Венгерский метод. 5 Был разработан Б. Эгервари в 1931 году для решения задачи линейного программирования, которая называлась «проблема выбора». 5
• Метод потенциалов. 5 Разработан Л. В. Канторовичем совместно с М. К. Гавуриным в 1949 году, применяется при решении транспортных задач. 5