Тема: Точный симплекс-метод при целочисленных исходных данных

Решение задач линейного программирования или ЛП стандартным симплекс- методом на каждом шаге приводит к вычислениям с действительными числами. Та­ким образом, на каждом шаге теряется точность, кроме того такие вычисления тре­буют больших затрат памяти компьютера. Одна из модификаций симплекс-метода связана с тем, чтобы промежуточные вычисления на каждом шаге были целочислен­ные. Это стало возможным благодаря Q - матрицам. Q - матрицы, введенные Дж. Эдмонсом [4], позволяют достаточно легко пройти различные шаги симплекс-метода и использовать в решении системы линейных уравнений вместо действительных чи­сел целые.
В данной работе будет описан алгоритм симплекс-метода с целочисленными промежуточными вычислениями с применением Q - матриц.
Для достижения результата выполнения работы необходимо:
1. Поставить алгоритм решения задач линейного программирования модифици­рованным симплекс-методом с применением Q - матриц.
2. Реализовать алгоритм в виде компьютерной программы и протестировать ее на различных примерах.
3. Использовать аналогичный алгоритм без операции деления для нахождения решения систем линейных уравнений.
4. Реализовать алгоритм решения систем уравнений в кольце целых чисел в виде компьютерной программы.
Купить

Дипломная работа посвящена точным методам решения задач. Точное решение задач необходимо для получения на выходе точного результата (целого или рацио­нального) и, соответственно, сокращения времени нахождения решения.
В ходе работы был выполнен ряд расчетов, а именно:
Численные примеры решения задач точным симплекс-методом решены при размер­ности m = 3, n = 5, m = 3,n = 4, m = 2,n = 4.
Система линейных уравнений была решена методом решения систем без операции деления при размерности m = 4, n = 4 .
Прозводились описание, подсчет и введение Q - матриц в точный алгоритм симплекс- метода.
Точный алгоритм симплекс-метода реализован на языке Python. Используется биб­лиотека numpy. Программу тестировали на задачах размерности m = 2, n = 5, m = 3, n = 5, m = 4, n = 8, m = 10, n = 17, на задачах с коэффициентами выше 1000. Решение линейных систем без операции деления было запрограммировано на языке Python. Программа была протестирована на примере m = 4, n = 4.
По результатам проделанной работы можно заключить, что методы решения за­дач без операции деления - это большая и интересная область для исследования.
Купить