Сравнительный анализ эффективности алгоритмов Кармаркара и симплекс-метода для решения задач линейного программирования
В экономике существует ряд прикладных задач, которые могут быть сведены к задачам линейного программирования, в частности в микроэкономике это – транспортная задача, задачи оптимального распределения ресурсов производства и т. д. Для их решения часто используется специальное программное обеспечение, реализующее наиболее успешные алгоритмы. Однако программные пакеты содержат разные методы, отличающиеся эффективностью решения различных классов задач. Исследованы возможности математических пакетов MatLab, SciLab и MS Excel для решения прикладных задач линейного программирования. В разных средах реализованы алгоритмы по различным методам – двойственному симплекс-методу, методу Кармаркара и симплекс-методу. Был проведен сравнительный анализ эффективности реализуемых алгоритмов для ряда различных задач и сделаны рекомендации по применению программного обеспечения. Новым является сравнение эффективности рассмотренных методов для решения различных прикладных задач.
Авторы: Д. Е. Гейер, Д. А. Соснило
Направление: Информатика, вычислительная техника и управление
Ключевые слова: Методы оптимизации, симплекс, Кармаркар, экономические задачи
Открыть полный текст статьи