Algoritmo para resolver sistemas de desigualdades lineales

Question

Tengo k desigualdades lineales en n variables (0 < k < n). No me interesa en particular qué es la solución, solo quiero comprobar si está vacía o no, es decir, si cualquier asignación de a mis variables n satisface el sistema. Alguien sabe una manera de resolver esto?

Gracias!

Answer 1

Esto se puede hacer usando un linear programming con una función objetivo constante. Es decir, solo verificando factibilidad del programa.

Answer 2

Solo necesita intersecar los rangos. He aquí cómo hacerlo en pseudocódigo:

// 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 3

Calcule el determinante de la matriz relacionada; si no es cero, hay una solución única; si es cero, o bien hay un número infinito de soluciones o ninguno - http://en.wikipedia.org/wiki/System_of_linear_equations

Alternativamente, usa Gaussian eliminación - http://en.wikipedia.org/wiki/Gaussian_elimination

Answer 4

Utilice un solucionador SMT para la teoría de la aritmética lineal (Yices, Z3, ...). Estos programas están diseñados para encontrar modelos para la entrada que especificó. Por supuesto, también puede beneficiarse de los algoritmos existentes de otras maneras.

Answer 5

Puede usar la eliminación de Fourier-Motzkin para resolver el sistema de desigualdades. Sin embargo, necesitará saber álgebra básica para comprender la solución.

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