МЕТОДЫ ПОИСКА НЕСКОЛЬКИХ РЕШЕНИЙ СИСТЕМЫ РАЗНОСТНЫХ И ИНТЕРВАЛЬНЫХ ОГРАНИЧЕНИЙ
Аннотация
Рассматриваются методы поиска решений систем линейных неравенств специального вида, состоящих из разностных неравенств с двумя переменными и интервальных ограничений с одной переменной. Для решения таких систем предлагаются два подхода, с помощью которых могут быть найдены два экстремальных («максимальное» и «минимальное») решения, а также некоторые другие решения. Первый подход основан на методе Фурье – Моцкина, второй – на представлении системы в виде сети ограничений.
Об авторах
И. В. Рубанов
Объединенный институт проблем информатики НАН Беларуси
Беларусь
Беларусь
М. С. Баркетов
Объединенный институт проблем информатики НАН Беларуси
Беларусь
Беларусь
М. Я. Ковалев
Объединенный институт проблем информатики НАН Беларуси
Беларусь
Беларусь
Список литературы
1. Рубанов, И.В. Задача выбора маршрутов движения объектов при ограничении на сближение / И.В. Рубанов, М.С. Баркетов, М.Я. Ковалев // Танаевские чтения : докл. Междунар. науч. конф., Минск, 27–29 марта 2014 г. – Минск : ОИПИ НАН Беларуси, 2014. – С. 136–140.
2. Peron, M. An Abstract Domain Extending Difference-Bound Matrices with Disequality Constraints / M. Peron, N. Halbwachs. – Grenoble, France : Vérimag, 2006. – 15 p.
3. Bellman, R. On a Routing Problem / R. Bellman // Quarterly of Applied Mathematics. – 1958. – Vol. 16, no. 1. – P. 87–90.
4. Данциг, Дж. Линейное программирование, его применения и обобщения / Дж. Данциг. – М. : Прогресс, 1966. – 600 с.
5. Кормен, Т. Алгоритмы, построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест ; пер. с англ. под. ред. А. Шеня. – М. : МЦНМО, 2002. – 960 с.
6. Писарук, Н.Н. Исследование операций / Н.Н. Писарук. – Минск : БГУ, 2015. – 304 c.
7. Solving Systems of Difference Constraints Incrementally / G. Ramalingam [et al.] // Algorithmica. – 1999. – Vol. 23. – P. 261–275.
8. Fourier, J.B.J. Solution d'une question particulière du calcul des inégalités / J.B.J. Fourier. – France, 1826.
9. Герман, В.Н. Решение линейных ограничений над полем вещественных и рациональных чисел / В.Н. Герман // Кибернетика и системный анализ. – 2010. – № 4. – С. 123–133.
10. 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.
Рецензия
Для цитирования:
Рубанов И.В., Баркетов М.С., Ковалев М.Я. МЕТОДЫ ПОИСКА НЕСКОЛЬКИХ РЕШЕНИЙ СИСТЕМЫ РАЗНОСТНЫХ И ИНТЕРВАЛЬНЫХ ОГРАНИЧЕНИЙ. Информатика. 2016;(3):67-69.
For citation:
Rubanov I.V., Barketau M.S., Kovalyov M.Y. TWO METHODS OF SOLVING THE SYSTEM OF DIFFERENCE AND INTERVAL CONSTRAINTS. Informatics. 2016;(3):67-69. (In Russ.)
Просмотров: 4251
Послать статью по эл. почте 