Комплекс компьютерных программ для решения задач линейного программирования симплекс-методом

1.

Комплекс компьютерных программ для
решения задач линейного программирования
симплекс-методом
Научный руководитель:
кандидат физико-математических наук,
доцент кафедры математического
моделирования факультета математики и
компьютерных наук имени профессора
Н.И. Червякова
Ионисян Андрей Сергеевич
Работу выполнил:
студент 2 курса факультета математики и
компьютерных наук имени профессора
Н.И.Червякова по специальности «прикладная
математика и информатика»,
Щербаков Роман Александрович
Ставрополь 2024

2.

Комплекс компьютерных программ для решения задач
линейного программирования симплекс-методом
Цель работы: Разработка и анализ
комплекса компьютерных программ,
специализированных на решении задач
линейного программирования с
применением симплекс-метода.
Объект исследования: Программные
продукты, созданные для
автоматизированного решения задач
линейного программирования с
использованием симплекс-метода.
Предмет исследования: Анализ
технических и методологических
характеристик разработанных
программных решений. Оценка их
эффективности, точности получаемых
решений, а также возможные области
применения этих программ и
потенциальные ограничения в их
использовании.

3.

Задачи:
• Проанализировать имеющиеся программные решения для задач
линейного программирования
• Проанализировать преимущества и недостатки существующих
решений
• Разработать архитектуру, интерфейс, алгоритмы программы для
решения задач линейного программирования симплекс-методом
• Провести сравнительный анализ разработанного программного
комплекса с существующими решениями, а так же оценку
эффективности и точности разработанного комплекса на
различных наборах данных

4.

Архитектура программного комплекса
1.Пользовательский интерфейс (User Interface):
Графический интерфейс пользователя (GUI) для удобного взаимодействия с программой.
Формы для ввода данных (коэффициенты целевой функции, ограничения и т.д.).
Визуализация результатов: графики, таблицы с решением задачи.

5.

Архитектура программного комплекса
2.Модуль ввода и обработки данных (Data Input and Processing Module):
Парсинг и валидация входных данных (возможность загрузки данных из файлов различных форматов).
Преобразование данных в формат, подходящий для дальнейшей обработки симплекс-методом.

6.

Архитектура программного комплекса
3.Модуль реализации симплекс-метода (Simplex Method Implementation Module):
Реализация алгоритма симплекс-метода для поиска оптимального решения задачи линейного программирования.
Модуль для работы с таблицами симплекс-метода (создание, обновление и анализ таблиц).

7.

Архитектура программного комплекса
4.Модуль оптимизации производительности (Performance Optimization Module):
Оптимизация алгоритмов и структур данных для улучшения производительности программы при работе с большими объемами данных.
Параллельные вычисления (если возможно) для ускорения процесса решения задач.
5.Модуль отображения результатов (Results Visualization Module):
Графическое представление оптимального решения задачи.
Вывод результатов в виде таблиц и графиков для удобства анализа.
6.Модуль документации и обратной связи (Documentation and Feedback Module):
Руководство пользователя с подробным описанием возможностей программы и инструкциями по использованию.
Механизм обратной связи для пользователей, позволяющий отправлять отзывы, предложения и сообщать о проблемах.
7.Модуль тестирования (Testing Module):
Набор тестов для проверки корректности работы программы.
Автоматизация тестирования для обеспечения стабильности и надежности программного комплекса.
8.Модуль сохранения и загрузки результатов (Save and Load Module):
Возможность сохранения полученных результатов в файл для последующего анализа или использования.
Загрузка сохраненных данных для повторного применения алгоритма на тех же или измененных данных.

8.

Реализумые методы
Симплекс-метод (Simplex Method):
Один из основных алгоритмов для решения задач линейного программирования. Он ищет оптимальное
решение задачи, двигаясь по вершинам многогранника допустимых решений.
Двойственный симплекс-метод (Dual Simplex Method):
Вариант симплекс-метода, который работает с двойственной задачей линейного программирования. Он
может быть эффективен в случаях, когда прямой симплекс-метод сталкивается с трудностями.
Интериорные методы (Interior Point Methods):
Класс методов оптимизации, который решает задачи линейного программирования, перемещаясь внутри
допустимого множества, а не по его границе, как делает симплекс-метод.
Методы разбиения и оценки (Branch and Bound Methods):
Эффективные методы для решения целочисленных задач линейного программирования. Они разбивают
задачу на подзадачи и оценивают их, чтобы найти оптимальное решение.
Сетевой метод (Network Simplex Method):
Специализированный метод для решения задач транспортной оптимизации, которые могут быть
сформулированы как задачи линейного программирования.

9.

Реализумые структуры данных:
Симплекс-таблица (Simplex Tableau):
Основная структура данных, используемая для представления симплекс-таблицы, которая содержит
коэффициенты целевой функции, базисные и свободные переменные, а также значения функции
ограничений. Обновление и манипуляции с этой таблицей производятся в ходе работы симплекс-метода.
Симплекс-сетка (Simplex Grid):
Структура данных, представляющая сетку вершин многогранника допустимых решений. Это
вспомогательная структура, которая может использоваться для определения допустимых направлений
движения в алгоритмах симплекс-метода.
Очередь или стек (Queue or Stack):
Для реализации методов ветвей и границ, а также для управления порядком обработки задач в случае, если
используется алгоритм разбиения и оценки, может быть использована структура данных очереди или стека.
Матрицы и векторы (Matrices and Vectors):
Для хранения коэффициентов системы уравнений и неравенств, а также для выполнения операций
линейной алгебры, например, умножения матрицы на вектор или нахождения обратной матрицы.
Хэш-таблицы (Hash Tables):
В случае необходимости быстрого доступа к данным, например, при поиске переменных по их
идентификаторам, хэш-таблицы могут быть полезны для организации данных.

10.

Инструменты реализации:
• Для разработки нашего программного комплекса для решения задач линейного
программирования я выбрал язык программирования Python и среду разработки
PyCharm.
• Python был выбран из-за его простоты и удобства в использовании, а также из-за
обширного экосистемы библиотек, таких как NumPy и SciPy, которые могут быть
полезны при реализации алгоритмов оптимизации.
• Среда разработки PyCharm предоставляет мне мощные инструменты для
написания, отладки и тестирования кода на Python. Её интуитивный интерфейс и
широкий набор функций делают процесс разработки более эффективным и
комфортным.
• Выбор Python и PyCharm позволяет мне сосредоточиться на создании
высококачественного программного продукта, обеспечивая при этом высокую
производительность и удобство в работе.

11.

Заключение
• В результате выполнения выпускной квалификационной работы был разработан
программный комплекс для решения задач линейного программирования с
применением симплекс-метода.
• Разработанный программный комплекс позволил улучшить процесс решения
задач линейного программирования, обеспечивая более быстрое и эффективное
нахождение оптимального решения. Экспериментальные результаты показали,
что наш метод превосходит существующие решения по скорости вычислений и
точности результатов.
• Разработанный программный комплекс обладает интуитивно понятным
интерфейсом и легкостью в использовании, что делает его доступным для
широкого круга пользователей.
• Для достижения поставленной цели было разработано кроссплатформенное
приложение, которое предоставляет возможность решать задачи линейного
программирования на различных операционных системах.

12.

Спасибо за внимание!
Студент 2 курса ПМИ-б-о-22-1
Щербаков Роман Александрович
Почта: [email protected]