Основные обозначения 2
Введение 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 Пример решения системы линейных уравнений точным симплекс-методом 42
Купить

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