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

Question

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

Спасибо!

Answer 1

Это можно сделать с помощью линейного программирования с постоянной целевой функцией. То есть только проверка на осуществимость программы.

Answer 2

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

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

Answer 3

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

Answer 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 

Answer 5

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

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