Cómo determinar si un sistema de inecuaciones lineales tiene un positivo ¿solución o no?
¿Existe algún algoritmo de poli tiempo para hacer esto? ¿O los mejores algoritmos conocidos no son menos complejos que los algoritmos para resolver conjuntos de desigualdades lineales?
Su problema se conoce como Programación Lineal (si se cambia el positivo por el no negativo). Normalmente se piensa en la programación lineal como un problema de optimización, pero en realidad el problema de optimización es equivalente a viabilidad que es exactamente lo que estás preguntando: si un sistema de desigualdades tiene alguna solución.
Si realmente quieres preguntar si hay una solución positiva, entonces lo que puedes hacer es tomar tu sistema de desigualdades $Ax \geq b$ y añadir la restricción $x_i \geq m$ maximizando sobre $m$ . Si el máximo es $m > 0$ entonces hay una solución estrictamente positiva, de lo contrario no la hay.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
0 votos
Pregunta publicada en mathoverflow y fue cerrada. No recuerdo el enlace.
1 votos
Obsérvese que la búsqueda de soluciones positivas puede escribirse como otra desigualdad lineal general porque $x_i>0$ es sólo una desigualdad lineal, así que puedes añadirla a tu sistema y seguirás teniendo un sistema de igualdades lineales.
0 votos
@Benjamin: Se publicaron dos versiones en MO: Este y este . Ambos estaban cerrados allí. Pero, están claramente en el tema aquí.