Operaciones2
Páginas: 7 (1506 palabras)
Publicado: 25 de julio de 2012
PREPROCESAMIENTO
Antes de resolver un programa lineal o entero, es natural verificar si la formulación es sensible o no a la información disponible. Todos los sistemas comerciales que utilizan la técnica Branch and Bound llevan a cabo esta verificación llamada preprocesamiento. La idea de base es tratar de detectar y eliminar rápidamente restricciones y variables redundantes y fortalecer lascotas donde sea posible. Este tema es importante en el caso del Branch and Bound dado que cientos de miles de programas lineales deberían ser resueltos.
Primero consideremos el preprocesamiento mediante un ejemplo:
Considere el programa lineal
[pic]
Fortaleciendo las cotas asociadas a las variables:
Restricción (1):
Aislando la variable x1 se tiene:
Deseamos encontrar la mejorcota superior (restricción de menor o igual con coeficiente positivo asociado a x1). Ésta será igual a la menor entre la actual cota superior de x1 y la que obtendremos a partir de la primera restricción.
[pic]
El mayor valor del lado derecho de la restricción se obtiene reemplazando en x2 su mayor valor posible (pues su coeficiente asociado en esta restricción es positivo) que es 1 yreemplazando en x3 su menor valor posible (pues su coeficiente asociado en esta restricción es negativo) que es 1. Haciendo esto, se obtiene:
[pic]
La mejor cota superior para x1 es mínimo {3,9/5}=9/5. Por lo tanto, 0(x1(9/5.
Aislando la variable x2 se tiene:
Deseamos encontrar la mejor cota inferior (restricción del tipo menor o igual con coeficiente negativo asociado a la variable x2). Ésta seráigual a la mayor entre la actual cota inferior de x2 y la que obtendremos a partir de la primera restricción.
[pic]
El menor valor del lado derecho de la restricción se obtiene reemplazando en x1 su menor valor posible (pues su coeficiente asociado en esta restricción es positivo) que es 0 y reemplazando en x3 su menor valor posible (pues su coeficiente asociado en esta restricción espositivo) que es 1. Haciendo esto, se obtiene:
[pic]
La mejor cota inferior para x2 es máximo {0,-7/2}=0. Por lo tanto, 0(x2(1 (no hubo modificación).
Aislando la variable x3 se tiene:
Deseamos encontrar la mejor cota superior (restricción de menor o igual con coeficiente positivo asociado a x1). Ésta será igual a la menor entre la actual cota superior de x3 y la que obtendremos a partir dela primera restricción.
[pic]
El mayor valor del lado derecho de la restricción se obtiene reemplazando en x2 su mayor valor posible (pues su coeficiente asociado en esta restricción es positivo) que es 1 y reemplazando en x1 su menor valor posible (pues su coeficiente asociado en esta restricción es negativo) que es 0. Haciendo esto, se obtiene:
[pic]
La mejor cota superior para x3 esmínimo {(,17/8}=17/8. Por lo tanto, 1(x3(17/8.
Restricción (2):
Debemos hacer el mismo análisis realizado con la restricción 1.
Aislando la variable x1 se tiene:
Deseamos encontrar la mejor cota inferior. Ésta será igual a la mayor entre la actual cota inferior de x1 y la que obtendremos a partir de la segunda restricción.
[pic]
El menor valor del lado derecho de la restricción seobtiene reemplazando en x2 su mayor valor posible (pues su coeficiente asociado en esta restricción es negativo) que es 1 y reemplazando en x3 su menor valor posible (pues su coeficiente asociado en esta restricción es positivo) que es 1. Haciendo esto, se obtiene:
[pic]
La mejor cota inferior para x1 es máximo {0,7/8}=7/8. Por lo tanto, 7/8(x1(9/5.
Aislando la variable x2 se tiene:Deseamos encontrar la mejor cota inferior. Ésta será igual a la mayor entre la actual cota inferior de x2 y la que obtendremos a partir de la segunda restricción.
[pic]
El menor valor del lado derecho de la restricción se obtiene reemplazando en x1 su mayor valor posible (pues su coeficiente asociado en esta restricción es negativo) que es 9/5 y reemplazando en x3 su menor valor posible (pues su...
Antes de resolver un programa lineal o entero, es natural verificar si la formulación es sensible o no a la información disponible. Todos los sistemas comerciales que utilizan la técnica Branch and Bound llevan a cabo esta verificación llamada preprocesamiento. La idea de base es tratar de detectar y eliminar rápidamente restricciones y variables redundantes y fortalecer lascotas donde sea posible. Este tema es importante en el caso del Branch and Bound dado que cientos de miles de programas lineales deberían ser resueltos.
Primero consideremos el preprocesamiento mediante un ejemplo:
Considere el programa lineal
[pic]
Fortaleciendo las cotas asociadas a las variables:
Restricción (1):
Aislando la variable x1 se tiene:
Deseamos encontrar la mejorcota superior (restricción de menor o igual con coeficiente positivo asociado a x1). Ésta será igual a la menor entre la actual cota superior de x1 y la que obtendremos a partir de la primera restricción.
[pic]
El mayor valor del lado derecho de la restricción se obtiene reemplazando en x2 su mayor valor posible (pues su coeficiente asociado en esta restricción es positivo) que es 1 yreemplazando en x3 su menor valor posible (pues su coeficiente asociado en esta restricción es negativo) que es 1. Haciendo esto, se obtiene:
[pic]
La mejor cota superior para x1 es mínimo {3,9/5}=9/5. Por lo tanto, 0(x1(9/5.
Aislando la variable x2 se tiene:
Deseamos encontrar la mejor cota inferior (restricción del tipo menor o igual con coeficiente negativo asociado a la variable x2). Ésta seráigual a la mayor entre la actual cota inferior de x2 y la que obtendremos a partir de la primera restricción.
[pic]
El menor valor del lado derecho de la restricción se obtiene reemplazando en x1 su menor valor posible (pues su coeficiente asociado en esta restricción es positivo) que es 0 y reemplazando en x3 su menor valor posible (pues su coeficiente asociado en esta restricción espositivo) que es 1. Haciendo esto, se obtiene:
[pic]
La mejor cota inferior para x2 es máximo {0,-7/2}=0. Por lo tanto, 0(x2(1 (no hubo modificación).
Aislando la variable x3 se tiene:
Deseamos encontrar la mejor cota superior (restricción de menor o igual con coeficiente positivo asociado a x1). Ésta será igual a la menor entre la actual cota superior de x3 y la que obtendremos a partir dela primera restricción.
[pic]
El mayor valor del lado derecho de la restricción se obtiene reemplazando en x2 su mayor valor posible (pues su coeficiente asociado en esta restricción es positivo) que es 1 y reemplazando en x1 su menor valor posible (pues su coeficiente asociado en esta restricción es negativo) que es 0. Haciendo esto, se obtiene:
[pic]
La mejor cota superior para x3 esmínimo {(,17/8}=17/8. Por lo tanto, 1(x3(17/8.
Restricción (2):
Debemos hacer el mismo análisis realizado con la restricción 1.
Aislando la variable x1 se tiene:
Deseamos encontrar la mejor cota inferior. Ésta será igual a la mayor entre la actual cota inferior de x1 y la que obtendremos a partir de la segunda restricción.
[pic]
El menor valor del lado derecho de la restricción seobtiene reemplazando en x2 su mayor valor posible (pues su coeficiente asociado en esta restricción es negativo) que es 1 y reemplazando en x3 su menor valor posible (pues su coeficiente asociado en esta restricción es positivo) que es 1. Haciendo esto, se obtiene:
[pic]
La mejor cota inferior para x1 es máximo {0,7/8}=7/8. Por lo tanto, 7/8(x1(9/5.
Aislando la variable x2 se tiene:Deseamos encontrar la mejor cota inferior. Ésta será igual a la mayor entre la actual cota inferior de x2 y la que obtendremos a partir de la segunda restricción.
[pic]
El menor valor del lado derecho de la restricción se obtiene reemplazando en x1 su mayor valor posible (pues su coeficiente asociado en esta restricción es negativo) que es 9/5 y reemplazando en x3 su menor valor posible (pues su...
Leer documento completo
Regístrate para leer el documento completo.