informИнформатикаInformatics1816-03012617-6963UIIP NASBinform-71Research ArticleСТАТЬИ ПО МАТЕРИАЛАМ КОНФЕРЕНЦИЙARTICLES ON THE MATERIALS CONFERENCEМЕТОДЫ ПОИСКА НЕСКОЛЬКИХ РЕШЕНИЙ СИСТЕМЫ РАЗНОСТНЫХ И ИНТЕРВАЛЬНЫХ ОГРАНИЧЕНИЙTWO METHODS OF SOLVING THE SYSTEM OF DIFFERENCE AND INTERVAL CONSTRAINTSРубановИ. В.RubanovI. V.irubanov@inbox.ruБаркетовМ. С.BarketauM. S.КовалевМ. Я.KovalyovM. Y.Объединенный институт проблем информатики НАН БеларусиBelarus201630092016036769Copyright © Рубанов И.В., Баркетов М.С., Ковалев М.Я., 20162016Рубанов И.В., Баркетов М.С., Ковалев М.Я.Rubanov I.V., Barketau M.S., Kovalyov M.Y.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/71

Рассматриваются методы поиска решений систем линейных неравенств специального вида, состоящих из разностных неравенств с двумя переменными и интервальных ограничений с одной переменной. Для решения таких систем предлагаются два подхода, с помощью которых могут быть найдены два экстремальных («максимальное» и «минимальное») решения, а также некоторые другие решения. Первый подход основан на методе Фурье – Моцкина, второй – на представлении системы в виде сети ограничений.

We develop two methods of solving DBM system. One method is based on Fourier – Motskinelimination scheme, it has complexity O(n3) for finding initial solve and complexity O(n3) for finding solve by changing one of variable value for some cases. The other method is based on the network of constraints approach, it has complexity O(n3) for finding initial solve and  O(n) or approximately for finding solve by changing one of variable value if it is limited by special bounds.

 

 

 

 

ReferencesРубанов, И.В. Задача выбора маршрутов движения объектов при ограничении на сближение / И.В. Рубанов, М.С. Баркетов, М.Я. Ковалев // Танаевские чтения : докл. Междунар. науч. конф., Минск, 27–29 марта 2014 г. – Минск : ОИПИ НАН Беларуси, 2014. – С. 136–140.Рубанов, И.В. Задача выбора маршрутов движения объектов при ограничении на сближение / И.В. Рубанов, М.С. Баркетов, М.Я. Ковалев // Танаевские чтения : докл. Междунар. науч. конф., Минск, 27–29 марта 2014 г. – Минск : ОИПИ НАН Беларуси, 2014. – С. 136–140.Peron, M. An Abstract Domain Extending Difference-Bound Matrices with Disequality Constraints / M. Peron, N. Halbwachs. – Grenoble, France : Vérimag, 2006. – 15 p.Peron, M. An Abstract Domain Extending Difference-Bound Matrices with Disequality Constraints / M. Peron, N. Halbwachs. – Grenoble, France : Vérimag, 2006. – 15 p.Bellman, R. On a Routing Problem / R. Bellman // Quarterly of Applied Mathematics. – 1958. – Vol. 16, no. 1. – P. 87–90.Bellman, R. On a Routing Problem / R. Bellman // Quarterly of Applied Mathematics. – 1958. – Vol. 16, no. 1. – P. 87–90.Данциг, Дж. Линейное программирование, его применения и обобщения / Дж. Данциг. – М. : Прогресс, 1966. – 600 с.Данциг, Дж. Линейное программирование, его применения и обобщения / Дж. Данциг. – М. : Прогресс, 1966. – 600 с.Кормен, Т. Алгоритмы, построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест ; пер. с англ. под. ред. А. Шеня. – М. : МЦНМО, 2002. – 960 с.Кормен, Т. Алгоритмы, построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест ; пер. с англ. под. ред. А. Шеня. – М. : МЦНМО, 2002. – 960 с.Писарук, Н.Н. Исследование операций / Н.Н. Писарук. – Минск : БГУ, 2015. – 304 c.Писарук, Н.Н. Исследование операций / Н.Н. Писарук. – Минск : БГУ, 2015. – 304 c.Solving Systems of Difference Constraints Incrementally / G. Ramalingam [et al.] // Algorithmica. – 1999. – Vol. 23. – P. 261–275.Solving Systems of Difference Constraints Incrementally / G. Ramalingam [et al.] // Algorithmica. – 1999. – Vol. 23. – P. 261–275.Fourier, J.B.J. Solution d'une question particulière du calcul des inégalités / J.B.J. Fourier. – France, 1826.Fourier, J.B.J. Solution d'une question particulière du calcul des inégalités / J.B.J. Fourier. – France, 1826.Герман, В.Н. Решение линейных ограничений над полем вещественных и рациональных чисел / В.Н. Герман // Кибернетика и системный анализ. – 2010. – № 4. – С. 123–133.Герман, В.Н. Решение линейных ограничений над полем вещественных и рациональных чисел / В.Н. Герман // Кибернетика и системный анализ. – 2010. – № 4. – С. 123–133.On Solving Boolean Combinations of UTVPI Constraints / Sanjit A. Seshia [et al.] // J. on Satisfability, Boolean Modeling and Computation. – 2007. – Vol. 3. – P. 67–90.On Solving Boolean Combinations of UTVPI Constraints / Sanjit A. Seshia [et al.] // J. on Satisfability, Boolean Modeling and Computation. – 2007. – Vol. 3. – P. 67–90.

The authors declare that there are no conflicts of interest present.