Utilizar métodos de álgebra lineal (por ejemplo, matrices) para resolver un sistema de inecuaciones lineales

Question

Digamos que tenemos la ecuación $Ax>b$ , donde $A$ es un M -por- N matriz, $b$ es un vector conocido de longitud N x es un vector desconocido de longitud N y el signo de desigualdad significa que cada elemento de $Ax$ es mayor que el elemento correspondiente de $b$ . ¿Existe algún método basado en el álgebra lineal, como, por ejemplo, alguna modificación de la descomposición LU o algo similar, que se pueda programar en un ordenador y que me permita resolver genéricamente este sistema para $x$ , dados los valores numéricos de $A$ y $b$ ? También aceptaré cualquier método para determinar simplemente si existe una solución, si no cualquier solución en sí.

EDIT: Debo aclarar que estoy trabajando principalmente con matrices con N y M ambos inferiores a 10, por lo que un método exacto que funcione de forma análoga a, por ejemplo, la descomposición LU, será probablemente más rápido que un método iterativo.

Answer 1

La descomposición LU es efectivamente hacer la contabilidad de la eliminación gaussiana. El análogo de la eliminación gaussiana para resolver un sistema lineal de inecuaciones es la eliminación de Fourier-Motzkin. Este procedimiento no es útil en la práctica.

Usted está pidiendo $Ax>b$ pero puede ser más fácil pensar en ello de la siguiente manera:

• El álgebra lineal es para $Ax=b$
• La programación lineal es para $Ax=b$ , donde $x\geq0$

De alguna manera, añadir esa desigualdad te da un salto en la dificultad y la expresividad.

Si quieres implementar algo por ti mismo, es casi seguro que tendrás que aprender sobre el Método Simplex. La Tabla Simplexu ofrece una manera fácil de codificar una implementación ingenua.

Para ver cómo convertir su problema en la forma estándar $Ax=b$ con $x\geq 0$ , ver http://ocw.mit.edu/courses/sloan-school-of-management/15-053-optimization-methods-in-management-science-spring-2013/tutorials/MIT15_053S13_tut06.pdf