Заказать работу


Тип работы:
Предмет:
Язык работы:


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

Работа №61012
Тип работыДипломные работы, ВКР
Предметматематика
Объем работы47
Год сдачи2016
Стоимость4380 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено 8
Не подходит работа?

Узнай цену на написание

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



[1] Azulay D., Pique J.F. A revised simplex method with integer Q-matrices ACM Transactions on Mathematical Software,V. 27, No 3. P. 350-360, 2001
[2] Azulay D., Pique J.F. Optimized Q-pivot for exact linear solvers Principles and Practice of Constraint Programming, Pisa, Italy, Springer, Berlin, P. 55-71, 1998
[3] Chvatal V. Linear Programming W. H. Freeman and Company, New York , 1983
[4] Edmonds J., Maurras J.F. Notes sur les Q-matrices d’Edmonds Recherche operationelle , V. 31, No 2, P. 203-209, 1997
[5] Заславский Ю.Л. Сборник задач по линейному программированию М. Наука, 1969
[6] Золотых Н. Ю., Кубарев В. К. Полностью целочисленный разреженный симплекс-метод Вестник Нижегородского университета им. Н.И. Лобачевского , №4(1), с. 232-237, 2012
[7] Малашонок Г.И. Решение системы линейных уравнений в целостном кольце Журнал вычислительной математики и математической физики , Т. 23, No 6, С. 1497-1500, 1983
[8] NumPy URL: http://www.numpy.org/
[9] Python URL: https://www.python.org


Работу высылаем на протяжении 30 минут после оплаты.

Пожалуйста, укажите откуда вы узнали о сайте!



© 2008-2021 Cервис помощи студентам в выполнении работ
.