Estoy tratando de crear un algoritmo para resolver rápidamente sistemas de ecuaciones lineales con restricciones, sin depender necesariamente de los algoritmos de LP existentes, como Simplex. La razón por la que no quiero utilizar necesariamente los algoritmos existentes es porque sólo estoy buscando encontrar rápidamente una solución general del sistema, NO una optimizada.
Algunas notas de fondo sobre el propio algoritmo:
El algoritmo se desarrolla con enteros de Java como tipo de datos de destino, y todos los valores involucrados, por lo tanto, deben respetar las restricciones impuestas por Java en tales valores. En particular, esto significa que todos estos valores deben estar en el rango [2^32-1, 2^32].
Aunque los valores objetivo tienen que ser enteros, los valores pueden ser tratados como números reales durante la parte computacional del algoritmo en aras de la simplicidad, y simplemente ser redondeados en el conjunto de resultados (es decir, se puede utilizar la relajación del LP).
Por último, una suposición básica importante del algoritmo (debido al contexto en el que se utilizará) es que SIEMPRE existe una solución, por lo que no es necesario comprobar la viabilidad.
Consideremos el ejemplo trivial (a, b y c son enteros de Java):
- a <= b
- b >= c
Sean MIN y MAX los valores mínimos y máximos posibles de los enteros de Java, respectivamente. Así, añadimos al sistema las siguientes restricciones:
- a <= MAX
- a >= MIN
- b <= MAX
- b >= MIN
- c <= MAX
- c >= MIN
Ahora, el sistema anterior puede transformarse en un sistema de ecuaciones equivalente introduciendo variables ficticias:
- a - b + s1 = 0
- b - c - s2 = c
- a + s3 = MAX
- a - s4 = MIN
- b + s5 = MAX
- b - s6 = MIN
- c + s7 = MAX
- c - s8 = MIN
En lo anterior, se impone la restricción adicional de que s1...s8 sean todos >= 0.
Ahora, aquí es donde estoy atascado, y mi pregunta es la siguiente: ¿qué método debo utilizar para resolver el sistema anterior, ya que tengo que tener en cuenta las restricciones implícitas en las variables ficticias? Por lo que sé, podría aplicar la fase inicial del algoritmo Simplex (es decir, utilizar el propio algoritmo para encontrar un cuadro inicial), pero no sé si es la mejor manera de hacerlo teniendo en cuenta el rendimiento, ya que sigue implicando la optimización y, por tanto, varios pasos de cálculo.
Desgraciadamente, no tengo muchos conocimientos de matemáticas, así que ¿hay alguna otra teoría para sistemas de ecuaciones que pueda aplicar para llegar a una solución rápidamente? Gracias de antemano.
