¿Cómo resolver un sistema de desigualdades?

Question

He reducido mi problema (algoritmo de diseño de tabla) al siguiente problema:

Imagina que tengo N variables X ₁ , X ₂ , ..., X _N . También tengo un número (indeterminado) de desigualdades, como:

X ₁ > = 2
x ₂ + X ₃ > = 13
etc.

Cada desigualdad es una suma de una o más variables, y siempre se compara con una constante utilizando el operador > =. No puedo decir de antemano cuántas desigualdades tendré cada vez, pero todas las variables tienen que ser no negativas, por lo que ya es una para cada variable.

¿Cómo resolver este sistema de tal manera que los valores de las variables sean lo más pequeños posible?

Agregado: Lee el artículo de Wikipedia y me di cuenta de que olvidé mencionar que las variables tienen que ser enteros. Supongo que esto hace que sea NP-hard, ¿eh?

Answer 1

Minimizar x1 + x2 + ... donde xi satisface las restricciones lineales se llama Programación lineal. Está cubierto con algunos detalles en Wikipedia

Answer 2

Lo que tienes allí es un problema bastante básico Programación lineal . Desea maximizar la ecuación X_1 + ... + X_n sujeto a

X_1 >= 2
X_2 + X_3 >= 13
etc.

Existen numerosos algoritmos para resolver este tipo de problema. El más conocido es el Algoritmo simple que resolverá su ecuación (con ciertas advertencias) de manera bastante eficiente en el caso promedio, aunque existen problemas de LP para los cuales el algoritmo Simplex requerirá exponencialmente muchos pasos para resolver (en el tamaño del problema).

Existen varias implementaciones de solucionadores de LP. Por ejemplo, LP_Solve debería satisfacer la mayoría de sus requisitos

Answer 3

También puede publicar directamente su modelo lineal en la plataforma NEOS ( http: / /neos.mcs.anl.gov/neos/solvers/index.html ). Lo que simplemente tiene que hacer primero es escribir su modelo en un lenguaje algebraico como AMPL. Luego NEOS resolverá el modelo y devolverá los resultados por correo electrónico.

Answer 4

Programación lineal