io
Páginas: 14 (3500 palabras)
Publicado: 30 de agosto de 2015
RAMIFICACIÓN Y ACOTAMIENTO (LAND Y DOING)
El primer algoritmo de ramificación y acotamiento fue desarrollado por A. Land y G. Doig, en 1960, para el problema de programación lineal entera mixta y pura. Este algoritmo corresponde a la técnica más utilizada, en la cual la ramificación se refiere a la parte enumerativa de la solución y el acotamiento refleja la comparación de las posiblessoluciones con una cota superior o inferior, según sea el caso.
Considere un problema de maximización. Establezca una cota inferior inicial para el valor objetivo óptimo de la PLE y establezca .
Paso 1. (Examine a fondo/acotamiento).
Seleccione , el siguiente subproblema a ser examinado. Resuelva , y trate de examinarlo a fondo utilizando una de estas tres condiciones.
a) El valor z óptimo de nopuede dar un valor objetivo mejor que la cota inferior actual.
b) da por resultado una solución entera factible mejor que la cota inferior actual.
c) no tiene ninguna solución factible.
Surgirán dos casos.
a) Si se examina a fondo y se determina una solución mejor, actualice la cota inferior. Si todos los subproblemas han sido examinados a fondo, deténgase; la cota inferior da la solución óptima(si no existe una cota inferior finita, el problema no tiene ninguna solución factible). De otro modo, establezca , y repita el paso 1.
b) Si no se ha examinado a fondo, proceda al paso 2 para ramificación.
Paso 2. (Ramificación).
Seleccione una de las variables enteras , cuyo valor óptimo en la solución de no es entero. Cree los dos subproblemas de correspondientes a
Establezca , yproceda el paso 1.
El algoritmo de ramificación y acotamiento puede ampliarse a problemas combinados (en los que sólo algunas de las variables son enteras). Nunca se selecciona una variable continua como variable de ramificación. Un subproblema factible proporciona una nueva cota del valor objetivo si los valores de las variables discretas son enteros con un valor objetivo mejorado.
Ejemplo deaplicación:
Minimizar
Sujeto a;
Los puntos de cuadrícula en la figura 1 definen el espacio de soluciones de PLE. El problema PL1 continuo asociado en el nodo 1 (área sombreada) se define a partir de la PLE eliminando las restricciones enteras. La solución óptima de PL1 es , y . Como la solución óptima de PL1 no satisface las restricciones enteras, el espacio de soluciones se subdivide de unamanera sistemática que finalmente localiza el óptimo de la PLE. En primer lugar, el algoritmo de ramificación y acotamiento selecciona una variable entera cuyo valor óptimo en PL1 no es entero. En este ejemplo, tanto como califican. Seleccionando arbitrariamente, la región 3, ,4 del espacio de soluciones de PL1 contiene valores no enteros de , y por lo tanto puede ser eliminada. Esto equivale areemplazar el PL1 original con dos problemas de PL nuevos.
Espacio de PL2 = Espacio de PL1
Espacio de PL3 = Espacio de PL1
La figura 2 ilustra los espacios de PL2 y PL3. Los dos espacios combinados contienen los mismos puntos enteros factibles que la PLE original, es decir, que no se pierde información cuando PL1 se reemplaza con PL2 y PL3.
Figura 1 Espacio de soluciones de la PLE (puntos decuadrícula) y del PL1 (área sombreada)
Si de una forma inteligente imponemos restricciones secuenciales que excluyan las regiones libres de enteros (por ejemplo en PL1), estaremos reduciendo el espacio de soluciones continuo de PL1 a varios subproblemas de programación lineal cuyos puntos extremos óptimos satisfacen las restricciones enteras. El mejor de estos subproblemas es la solución óptima dePLE. Las nuevas restricciones, y , son mutuamente excluyentes, de modo que el PL2 y el PL3 en los nodos 2 y 3 deben tratarse como programaciones lineales distintas, como se muestra en la figura 3. Esta dicotomización da lugar al concepto de ramificación en el algoritmo de ramificación y acotamiento. Es este caso, x1 se llama variable de ramificación.
Figura 2. Espacios de soluciones de PL2...
El primer algoritmo de ramificación y acotamiento fue desarrollado por A. Land y G. Doig, en 1960, para el problema de programación lineal entera mixta y pura. Este algoritmo corresponde a la técnica más utilizada, en la cual la ramificación se refiere a la parte enumerativa de la solución y el acotamiento refleja la comparación de las posiblessoluciones con una cota superior o inferior, según sea el caso.
Considere un problema de maximización. Establezca una cota inferior inicial para el valor objetivo óptimo de la PLE y establezca .
Paso 1. (Examine a fondo/acotamiento).
Seleccione , el siguiente subproblema a ser examinado. Resuelva , y trate de examinarlo a fondo utilizando una de estas tres condiciones.
a) El valor z óptimo de nopuede dar un valor objetivo mejor que la cota inferior actual.
b) da por resultado una solución entera factible mejor que la cota inferior actual.
c) no tiene ninguna solución factible.
Surgirán dos casos.
a) Si se examina a fondo y se determina una solución mejor, actualice la cota inferior. Si todos los subproblemas han sido examinados a fondo, deténgase; la cota inferior da la solución óptima(si no existe una cota inferior finita, el problema no tiene ninguna solución factible). De otro modo, establezca , y repita el paso 1.
b) Si no se ha examinado a fondo, proceda al paso 2 para ramificación.
Paso 2. (Ramificación).
Seleccione una de las variables enteras , cuyo valor óptimo en la solución de no es entero. Cree los dos subproblemas de correspondientes a
Establezca , yproceda el paso 1.
El algoritmo de ramificación y acotamiento puede ampliarse a problemas combinados (en los que sólo algunas de las variables son enteras). Nunca se selecciona una variable continua como variable de ramificación. Un subproblema factible proporciona una nueva cota del valor objetivo si los valores de las variables discretas son enteros con un valor objetivo mejorado.
Ejemplo deaplicación:
Minimizar
Sujeto a;
Los puntos de cuadrícula en la figura 1 definen el espacio de soluciones de PLE. El problema PL1 continuo asociado en el nodo 1 (área sombreada) se define a partir de la PLE eliminando las restricciones enteras. La solución óptima de PL1 es , y . Como la solución óptima de PL1 no satisface las restricciones enteras, el espacio de soluciones se subdivide de unamanera sistemática que finalmente localiza el óptimo de la PLE. En primer lugar, el algoritmo de ramificación y acotamiento selecciona una variable entera cuyo valor óptimo en PL1 no es entero. En este ejemplo, tanto como califican. Seleccionando arbitrariamente, la región 3, ,4 del espacio de soluciones de PL1 contiene valores no enteros de , y por lo tanto puede ser eliminada. Esto equivale areemplazar el PL1 original con dos problemas de PL nuevos.
Espacio de PL2 = Espacio de PL1
Espacio de PL3 = Espacio de PL1
La figura 2 ilustra los espacios de PL2 y PL3. Los dos espacios combinados contienen los mismos puntos enteros factibles que la PLE original, es decir, que no se pierde información cuando PL1 se reemplaza con PL2 y PL3.
Figura 1 Espacio de soluciones de la PLE (puntos decuadrícula) y del PL1 (área sombreada)
Si de una forma inteligente imponemos restricciones secuenciales que excluyan las regiones libres de enteros (por ejemplo en PL1), estaremos reduciendo el espacio de soluciones continuo de PL1 a varios subproblemas de programación lineal cuyos puntos extremos óptimos satisfacen las restricciones enteras. El mejor de estos subproblemas es la solución óptima dePLE. Las nuevas restricciones, y , son mutuamente excluyentes, de modo que el PL2 y el PL3 en los nodos 2 y 3 deben tratarse como programaciones lineales distintas, como se muestra en la figura 3. Esta dicotomización da lugar al concepto de ramificación en el algoritmo de ramificación y acotamiento. Es este caso, x1 se llama variable de ramificación.
Figura 2. Espacios de soluciones de PL2...
Leer documento completo
Regístrate para leer el documento completo.