Puedes ayudar a ampliar este artículo con texto traducido del artículo correspondiente en alemán (septiembre de 2013) . Haz clic en [mostrar] para obtener instrucciones de traducción importantes.
|
La eliminación de Fourier-Motzkin , también conocida como método FME , es un algoritmo matemático para eliminar variables de un sistema de inecuaciones lineales . Puede generar soluciones reales .
El algoritmo lleva el nombre de Joseph Fourier [1], quien propuso el método en 1826, y Theodore Motzkin, quien lo redescubrió en 1936.
La eliminación de un conjunto de variables, digamos V , de un sistema de relaciones (aquí desigualdades lineales) se refiere a la creación de otro sistema del mismo tipo, pero sin las variables en V , de modo que ambos sistemas tienen las mismas soluciones sobre las variables restantes.
Si se eliminan todas las variables de un sistema de inecuaciones lineales, se obtiene un sistema de inecuaciones constantes. En ese caso, resulta trivial decidir si el sistema resultante es verdadero o falso. Es verdadero si y solo si el sistema original tiene soluciones. En consecuencia, la eliminación de todas las variables puede utilizarse para detectar si un sistema de inecuaciones tiene soluciones o no.
Considérese un sistema de inecuaciones con variables a , con la variable a eliminar. Las inecuaciones lineales del sistema se pueden agrupar en tres clases según el signo (positivo, negativo o nulo) del coeficiente para .
El sistema original es por tanto equivalente a
La eliminación consiste en producir un sistema equivalente a . Obviamente, esta fórmula es equivalente a
La desigualdad
es equivalente a las desigualdades , para y .
Por lo tanto, hemos transformado el sistema original en otro sistema donde se elimina . Observe que el sistema de salida tiene desigualdades. En particular, si , entonces el número de desigualdades de salida es .
Consideremos el siguiente sistema de desigualdades: [2] : 100–102
Como todas las inecuaciones tienen la misma forma (todas menores que o todas mayores que), podemos examinar los signos de los coeficientes de cada variable. Si eliminamos x obtendremos 2*2 = 4 inecuaciones en las variables restantes, y lo mismo ocurriría si eliminamos y. Si eliminamos z obtendremos solo 3*1 = 3 inecuaciones, por lo que utilizaremos esa en su lugar.
lo que da las 3 desigualdades:
Simplificando:
Este sistema utiliza sólo 2 variables en lugar de 3. Examinando los signos de los coeficientes para cada variable se obtiene que y es todo positivo, por lo que podemos decir inmediatamente que el sistema no está acotado en y: dado que todos los coeficientes de y son positivos y todas las desigualdades son menores o iguales, fijar y en menos infinito (o cualquier número negativo suficientemente grande) satisfaría el sistema reducido, por lo tanto, existen x y z correspondientes para los sistemas más grandes también, y hay infinitas soluciones de este tipo. Por ejemplo, fijar y = -1000000, x = 0, z = -2222222 satisface tanto el sistema original como los reducidos.
La ejecución de un paso de eliminación sobre desigualdades puede dar como resultado, como máximo, desigualdades en el resultado, por lo que la ejecución ingenua de pasos sucesivos puede dar como máximo una complejidad exponencial doble. Esto se debe a que el algoritmo produce muchas restricciones redundantes implícitas en otras restricciones.
Teorema de límite superior de McMullen que establece que el número de restricciones no redundantes crece como un exponente único. [3] En [4] se proporciona una implementación exponencial única de la eliminación de Fourier-Motzkin y estimaciones de complejidad.
Es bien conocido que la programación lineal brinda soluciones a sistemas de desigualdades en tiempo polinomial, favoreciéndola sobre la eliminación de Fourier-Motzkin.
Dos teoremas de "aceleración" debidos a Imbert [5] permiten la eliminación de desigualdades redundantes basadas únicamente en propiedades sintácticas del árbol de derivación de fórmulas, reduciendo así la necesidad de resolver programas lineales o calcular rangos de matrices.
Defina la historia de una desigualdad como el conjunto de índices de desigualdades del sistema inicial que se utilizaron para producir . Por lo tanto, para las desigualdades del sistema inicial. Al agregar una nueva desigualdad (eliminando ), la nueva historia se construye como .
Supongamos que las variables han sido eliminadas oficialmente . Cada desigualdad divide el conjunto en :
Una desigualdad no redundante tiene la propiedad de que su historia es mínima . [6]
Teorema (primer teorema de aceleración de Imbert). Si la historia de una desigualdad es mínima, entonces .
Una desigualdad que no satisface estos límites es necesariamente redundante y puede eliminarse del sistema sin cambiar su conjunto de soluciones.
El segundo teorema de aceleración detecta conjuntos históricos mínimos:
Teorema (segundo teorema de aceleración de Imbert). Si la desigualdad es tal que , entonces es mínima.
Este teorema proporciona un criterio de detección rápido y se utiliza en la práctica para evitar comprobaciones más costosas, como las basadas en rangos de matrices. Consulte la referencia para obtener detalles de implementación. [6]
Las pruebas de viabilidad de la teoría de la información dan como resultado condiciones bajo las cuales se garantiza la existencia de un esquema de codificación de buen rendimiento. Estas condiciones se describen a menudo mediante un sistema lineal de desigualdades. Las variables del sistema incluyen tanto las tasas de transmisión (que son parte de la formulación del problema) como las tasas auxiliares adicionales utilizadas para el diseño del esquema. Comúnmente, uno apunta a describir los límites fundamentales de la comunicación solo en términos de los parámetros del problema. Esto da lugar a la necesidad de eliminar las tasas auxiliares mencionadas anteriormente, lo que se ejecuta mediante la eliminación de Fourier-Motzkin. Sin embargo, el proceso de eliminación da como resultado un nuevo sistema que posiblemente contiene más desigualdades que el original. Sin embargo, a menudo algunas de las desigualdades en el sistema reducido son redundantes. La redundancia puede estar implícita en otras desigualdades o en desigualdades en la teoría de la información (también conocidas como desigualdades de tipo Shannon). Un software de código abierto desarrollado recientemente para MATLAB [7] realiza la eliminación, al tiempo que identifica y elimina las desigualdades redundantes. En consecuencia, el software genera un sistema simplificado (sin redundancias) que involucra únicamente las velocidades de comunicación.
La restricción redundante se puede identificar resolviendo un programa lineal como sigue. Dado un sistema de restricciones lineales, si la -ésima desigualdad se satisface para cualquier solución de todas las demás desigualdades, entonces es redundante. De manera similar, las STI se refieren a desigualdades que están implícitas por la no negatividad de las medidas de teoría de la información y las identidades básicas que satisfacen. Por ejemplo, la STI es una consecuencia de la identidad y la no negatividad de la entropía condicional, es decir, . Las desigualdades de tipo Shannon definen un cono en , donde es el número de variables aleatorias que aparecen en las medidas de información involucradas. En consecuencia, cualquier STI se puede demostrar mediante programación lineal verificando si está implícita por las identidades básicas y las restricciones de no negatividad. El algoritmo descrito primero realiza la eliminación de Fourier-Motzkin para eliminar las tasas auxiliares. Luego, impone las restricciones de no negatividad de la teoría de la información en el sistema de salida reducido y elimina las desigualdades redundantes.