Алгоритм решения систем линейных неравенств

У меня есть k линейных неравенств по n переменным (0 < k < n). Меня не особо волнует, что такое решение, я только хочу проверить, пуст ли он или нет, т.е. Удовлетворяет ли какое-либо присвоение моим переменным n системе. Кто-нибудь знает способ решить эту проблему?

Спасибо!

Ответы

Ответ 2

Используйте решатель SMT для теории линейной арифметики (Yices, Z3,...). Эти программы предназначены для поиска моделей для введенного вами ввода. Конечно, вы также можете использовать существующие алгоритмы другими способами.

Ответ 3

Вы можете использовать устранение Фурье-Моцкина для решения системы неравенств. Однако вам нужно знать основную алгебру, чтобы понять решение.

http://en.wikipedia.org/wiki/Fourier%E2%80%93Motzkin_elimination

Ответ 4

Вам просто нужно пересечь диапазоны. Здесь, как в псевдокоде:

// An array that has the ranges (inequalities) to test:
fromToArray = [[0, 10], [5, 20], [-5, Infinity]] 

currentRange = [-Infinity, Infinity];
for each pair myRange in fromToArray
   if currentRange[0] < myRange[0] 
          then currentRange[0] = myRange[0]
   if currentRange[1] > myRange[1] 
         then currentRange[1] = myRange[1]
   if currentRange[0] >= currentRange[1]    // from greater than to, so set is empty.
         then return "NO SOLUTION"
end for each

return "Solution is: " + currentRange

Ответ 5

Вычислить определитель соответствующей матрицы; если оно отличное от нуля, есть единственное решение; если оно равно нулю, существует либо бесконечно много решений, либо нет - http://en.wikipedia.org/wiki/System_of_linear_equations

В качестве альтернативы используйте исключение Гаусса - http://en.wikipedia.org/wiki/Gaussian_elimination