Details

Данная работа посвящена реализации метода исключений Фурье-Моцкина и полиномиального алгоритма проверки совместности и решения систем строгих и нестрогих линейных неравенств в рациональных числах. В ходе данной работы решались следующие задачи:     1. Провести обзор известных алгоритмов решения данной задачи и смежных задач, а также их реализаций.     2. Модифицировать метод исключений Фурье-Моцкина для работы с системами строгих и нестрогих линейных неравенств и расширить его до их решения.     3. Выявить полиномиальный алгоритм проверки совместности строгих и нестрогих линейных неравенств и расширить его до их решения.     4. Реализовать выбранные алгоритмы.     5. Протестировать реализованные алгоритмы и экспериментально сравнить их работу с другими реализациями. В работе приводится формальное описание модификации метода исключений Фурье-Моцкина для работы с системами, содержащими строгие неравенства, а также расширение данного метода и полиномиального алгоритма проверки совместности систем строгих и нестрогих линейных неравенств для решения таких систем. В результате работы данные алгоритмы были реализованы на языке Java, в виде позволяющем работать с рациональными числами произвольной точности.

The given work is devoted to the implementation of the Fourier-Motzkin elimination method and polynomial algorithm for checking the consistency and solving systems of strict and nonstrict linear inequalities in rational numbers. In the course of this work the following tasks were solved:     1. Review the known algorithms for solving this problem and related problems, as well as their implementations.     2. Modify Fourier-Motzkin elimination method of exceptions to work with systems of strict and nonstrict linear inequalities and extend it to their solution.     3. Identify a polynomial algorithm for checking the consistency of strict and nonstrict linear inequalities and extend it to their solution.     4. Implement the selected algorithms.     5. Test the implemented algorithms and experimentally compare their performance with other implementations. The paper provides a formal description of the modification of Fourier-Motzkin elimination method to work with systems containing strict inequalities, as well as an extension of this method and polynomial algorithm for checking the consistency of systems of strict and nonstrict linear inequalities to solve such systems. As a result, these algorithms were implemented in Java language, in a form that allows to work with rational numbers of arbitrary precision.