Введение 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. Реализовать алгоритм решения систем уравнений в кольце целых чисел в виде компьютерной программы.

Купить