Введение 3
1 Q - матрицы и действия с ними 4
1.1 Определение Q - матриц и их свойства 4
1.2 Q - поворот с ведущим элементом 6
1.3 Q - матрица и присоединенная матрица 8
2 Целочисленная модификация симплекс-метода 10
2.1 Постановка задачи и основные обозначения 10
2.2 Описание алгоритма 11
3 Решение систем линейных уравнений без операции деления 14
3.1 Целочисленный метод решения систем линейных уравнений и целочисленный метод нахождения присоединенной матрицы 14
3.2 Применение Q - матриц к решению систем линейных уравнений .... 17
4 Программная реализация алгоритмов решения задач 20
Заключение 26
Список литературы 27
Приложение 1 Примеры решения задач ЛП целочисленным симплексметодом 28
Приложение 2 Примеры решения системы линейных уравнений без операции деления и нахождения присоединенной матрицы без операции деления 39
Приложение 3 Пример решения системы линейных уравнений точным симплекс-методом
Решение задач линейного программирования или ЛП стандартным симплексметодом на каждом шаге приводит к вычислениям с действительными числами. Таким образом, на каждом шаге теряется точность, кроме того такие вычисления требуют больших затрат памяти компьютера. Одна из модификаций симплекс-метода связана с тем, чтобы промежуточные вычисления на каждом шаге были целочисленные. Это стало возможным благодаря 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.
По результатам проделанной работы можно заключить, что методы решения задач без операции деления - это большая и интересная область для исследования.
