Аннотация 2
Введение 5
1 Анализ задач линейного программирования 7
1.1 Современные аспекты линейного программирования 7
1.2 Методы решения задач линейного программирования 10
2 Решение задач линейного программирования с использованием Python 12
2.1 Постановка транспортной задачи 12
2.2 Библиотеки Python для решения задач линейного программирования 15
3 Разработка программного обеспечения для решения транспортной задачи с дополнительными условиями 18
3.1 Алгоритм решения транспортной задачи 18
3.2 Формирование дополнительных условий для транспортной задачи 20
3.3 Решение задач с использованием методов библиотеки cvxopt 21
3.4 Решение задач с использованием методов библиотеки scipy.optimize 27
3.5 Решение задач с использованием методов библиотеки pulp 32
3.6 Визуализация результатов вычислительного эксперимента 39
Заключение 42
Список используемой литературы 43
В настоящее время площадь России по официальным данным составляет порядка 17,13 миллионов квадратных километров. При этом количество населенных пунктов по данным общероссийского классификатора территорий муниципальных образований равно 155649. С учетом данных фактов, продумывание логистики доставки товаров превращается в большую исследовательскую задачу, требующую использования компьютерных мощностей для ее решения.
С точки зрения математики логистическую задачу можно свести к решению оптимизационной задачи линейного программирования (к транспортной задаче) [1, 3]. От успеха решения транспортной задачи, например, зависит количество издержек транспортной компании при доставке заказов. Крупные интернет-магазины также вынуждены периодически решать транспортные задачи для своевременного обеспечения своих клиентов заказами.
Одновременно с этим сложность транспортных задач постоянно увеличивается, и для их решения привлекаются компьютерные мощности [5]. Поэтому увеличивается актуальность в разработке программных комплексов для решения задач линейного программирования. При создании программных комплексов часто используется компонентный подход, когда вместо написания своей реализации алгоритма, применяются свободно распространяемые библиотеки. С одной стороны это упрощает разработку программного обеспечения, но с другой – у каждой реализации есть скрытые особенности, определить которые можно только в условиях вычислительных экспериментов.
В настоящее время существует множество библиотек для языка Python, в которых реализованы методы, позволяющие решать задачи линейного программирования [10, 12, 14]. Из их числа наиболее известные свободно распространяемые библиотеки с открытым исходным кодом – cvxopt, SciPy и PuLp. В этих библиотеках для решения задач линейного программирования используются различные реализации симплекс-метода.
Из-за различий в реализациях сложно оценить, как поведут себя реализованные в этих библиотеках методы при решении одной и той же транспортной задачи с дополнительными условиями. Поэтому актуальной проблемой является разработка программного обеспечения для сравнительного анализ методов решения транспортной задачи.
Цель работы - разработка программного обеспечения для сравнения различных программных методов решения транспортных задач с дополнительными условиями.
Для достижения поставленной цели в работе решаются следующие задачи:
1. Анализ современных аспектов линейного программирования.
2. Исследование подходов по решению задач линейного программирования с использованием Python.
3. Разработка программного обеспечения для сравнения различных программных методов решения транспортных задач с дополнительными условиями.
Отметим основные моменты проведенного исследования:
1. В ходе анализа источников литературы проведен обзор аспектов линейного программирования. Описана математическая постановка задач «максимального паросочетания», «максимального потока» и «игры с нулевой суммой». Установлено что при программном решении оптимизационных задач линейного программирования в подавляющем большинстве случаев используется симплекс-метод.
2. Сформулировано математическое описание транспортной задачи в общем виде. Проанализированы наиболее известные свободно распространяемые библиотеки Python (cvxopt, scipy и pulp), реализующие методы решения транспортных задач. Установлено, что в данных библиотеках решение оптимизационных задач линейного программирования реализовано с использованием симплекс-метода.
3. На языке программирования Python разработано программное обеспечение для сравнения методов библиотек cvxopt, scipy, pulp при решении задач оптимизации. Разработанное программное обеспечение производит решение транспортной задачи с заданными пользователем исходными данными, объединяет результаты тестирования методов этих библиотек в таблицу и визуализирует результаты экспериментов в виде графиков.
4. При тестировании методов библиотек cvxopt, scipy, pulp на задаче с 4 дополнительными условиями установлено, что быстродействие библиотек cvxopt и scipy приблизительно равное, а библиотека pulp затрачивает на решение в 2.5-3 раза больше времени. Однако стоить отметить, что результаты быстродействия во многом зависят от исходных данных, поэтому производить сравнительный анализ методов из данных библиотек необходимо для конкретного экземпляра данных.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
