Programacion entera
Páginas: 5 (1058 palabras)
Publicado: 6 de diciembre de 2010
[pic]
INGENIERIA INDUSTRIAL
INVESTIGACION DE OPERACIONES
PROGRAMACION ENTERA
PRESENTADO POR:
JORGE MARTINEZ ZAMORA
N.C.: 08050012
FECHA DE ENTREGA: 30-11-10
Programación Entera
Un modelo de Programación Entera (PE) permite abordar aplicaciones donde la solución tiene sentido si una parte o todas las decisiones tomanvalores restringuidos a números enteros.
Por ejemplo, consideremos que tenemos el siguiente problema de Programación Lineal:
[pic]
Si todas las variables restringen sus valores a números enteros, entonces estamos frente a un modelo de Programación Entera (puro). Por el contrario, si al menos algun conjunto de variables no esta acotada a adoptar valores o números enteros, se trata de un modelode Programación Entera (mixta).
Luego, si consideramos que estamos a un modelo de Programación Entera (puro o mixto) y resolvemos el modelo de Programación Lineal asociado (esto es, admitiendo valores continuos para las variables), estarémos obtiendo la solución de la Relajación Contínua del modelo entero. Para un modelo de maximización, la relajación continua nos proporciona una cotasuperior del valor óptimo del modelo de Programación Entera asociado.
En el caso particular que la Relajación Contínua nos proporcione una solución entera, entonces ésta será también la solución del modelo de Programación Entera asociado. En caso contrario deberemos utilizar alguna estrategia o algoritmo para obtener la solución del modelo de PE.
Una herramienta eficiente para abordar estos casoses el algoritmo de Branch & Bound. Utilizaremos un ejemplo para explicar este método:
Resuelva el siguiente modelo de Programación Entera utilizando el algoritmo de Branch & Bound:
[pic]
Gráficamente corresponde a:
[pic]
El dominio de puntos factibles para el modelo de Programación Lineal asociado es el área demarcada con verde. Dicho modelo tiene valor óptimo igual a 39, con X1=1,9y X2=0. Esto corresponde a la relajación contínua del PLE y nos proporciona una cota superior del valor óptimo de dicho problema.
Además, claramente la solución de la relación contínua no satisface la condición de integralidad del modelo de PLE. Finalmente, en el gráfico anterior se han marcado con azul todas aquellas combinaciones que satisfacen las restricciones del modelo de PLE.Claramente esto corresponde a un subdominio del problema lineal asociado lo que justifica que la relajación continua nos entrega una cota superior del valor óptimo del PLE.
Al aplicar el algoritmo de Branch & Bound, el nodo inicial corresponde a la relajación continua y se van agregando las ramas o nodos necesarios hasta alcanzar la(s) soluciones que satisfacen las condiciones de integralidad. [pic]
P0: Corresponde a la relajación continua del PLE.
P1: Po + x1=2 (solución inicial X1=1,9 aproximada al entero superior). Infactible.
P11: P1 + x2=2 (solución X1=5/7 y X2=2. No es solución óptima de PLE debido a que X1 es aún fraccionario. Se continua el método debido a que el Valor Óptimo Z=37 es mayor que el Valor Óptimo de P11, en caso contrario se detiene el método y P11 sería la soluciónóptima de PLE).
P121: P12 + x1=1 Infactible.
P1211: P121 + X2=4 Infactible.
Luego la Solución Óptima del PLE) es X1=0 y X2=3 con Valor Óptimo Z=33.
Ejemplo:
Boxcar es una nueva cadena de restaurants de comida rápida (fast-food) que está planificando expandirse en Washington DC. Aún cuando la comida es de alta calidad, la principal atracción de esta cadena de restaurants es su diseño.En el centro de la ciudad el interior del local se contruyó de tal forma de parecerse al interior de un container, mientras que en los suburbios los restaurants se construyeron al interior de verdaderos containers.
La compañía dispone de US$2.7 millones para su expansión. Cada restaurant en los suburbios requiere US$200.000 en inversión, y cada local en el centro requiere de US$600.000. Se...
INGENIERIA INDUSTRIAL
INVESTIGACION DE OPERACIONES
PROGRAMACION ENTERA
PRESENTADO POR:
JORGE MARTINEZ ZAMORA
N.C.: 08050012
FECHA DE ENTREGA: 30-11-10
Programación Entera
Un modelo de Programación Entera (PE) permite abordar aplicaciones donde la solución tiene sentido si una parte o todas las decisiones tomanvalores restringuidos a números enteros.
Por ejemplo, consideremos que tenemos el siguiente problema de Programación Lineal:
[pic]
Si todas las variables restringen sus valores a números enteros, entonces estamos frente a un modelo de Programación Entera (puro). Por el contrario, si al menos algun conjunto de variables no esta acotada a adoptar valores o números enteros, se trata de un modelode Programación Entera (mixta).
Luego, si consideramos que estamos a un modelo de Programación Entera (puro o mixto) y resolvemos el modelo de Programación Lineal asociado (esto es, admitiendo valores continuos para las variables), estarémos obtiendo la solución de la Relajación Contínua del modelo entero. Para un modelo de maximización, la relajación continua nos proporciona una cotasuperior del valor óptimo del modelo de Programación Entera asociado.
En el caso particular que la Relajación Contínua nos proporcione una solución entera, entonces ésta será también la solución del modelo de Programación Entera asociado. En caso contrario deberemos utilizar alguna estrategia o algoritmo para obtener la solución del modelo de PE.
Una herramienta eficiente para abordar estos casoses el algoritmo de Branch & Bound. Utilizaremos un ejemplo para explicar este método:
Resuelva el siguiente modelo de Programación Entera utilizando el algoritmo de Branch & Bound:
[pic]
Gráficamente corresponde a:
[pic]
El dominio de puntos factibles para el modelo de Programación Lineal asociado es el área demarcada con verde. Dicho modelo tiene valor óptimo igual a 39, con X1=1,9y X2=0. Esto corresponde a la relajación contínua del PLE y nos proporciona una cota superior del valor óptimo de dicho problema.
Además, claramente la solución de la relación contínua no satisface la condición de integralidad del modelo de PLE. Finalmente, en el gráfico anterior se han marcado con azul todas aquellas combinaciones que satisfacen las restricciones del modelo de PLE.Claramente esto corresponde a un subdominio del problema lineal asociado lo que justifica que la relajación continua nos entrega una cota superior del valor óptimo del PLE.
Al aplicar el algoritmo de Branch & Bound, el nodo inicial corresponde a la relajación continua y se van agregando las ramas o nodos necesarios hasta alcanzar la(s) soluciones que satisfacen las condiciones de integralidad. [pic]
P0: Corresponde a la relajación continua del PLE.
P1: Po + x1=2 (solución inicial X1=1,9 aproximada al entero superior). Infactible.
P11: P1 + x2=2 (solución X1=5/7 y X2=2. No es solución óptima de PLE debido a que X1 es aún fraccionario. Se continua el método debido a que el Valor Óptimo Z=37 es mayor que el Valor Óptimo de P11, en caso contrario se detiene el método y P11 sería la soluciónóptima de PLE).
P121: P12 + x1=1 Infactible.
P1211: P121 + X2=4 Infactible.
Luego la Solución Óptima del PLE) es X1=0 y X2=3 con Valor Óptimo Z=33.
Ejemplo:
Boxcar es una nueva cadena de restaurants de comida rápida (fast-food) que está planificando expandirse en Washington DC. Aún cuando la comida es de alta calidad, la principal atracción de esta cadena de restaurants es su diseño.En el centro de la ciudad el interior del local se contruyó de tal forma de parecerse al interior de un container, mientras que en los suburbios los restaurants se construyeron al interior de verdaderos containers.
La compañía dispone de US$2.7 millones para su expansión. Cada restaurant en los suburbios requiere US$200.000 en inversión, y cada local en el centro requiere de US$600.000. Se...
Leer documento completo
Regístrate para leer el documento completo.