• Author / Uploaded
• ferg20142

Citation preview

Programación Entera Ejercicio1: Un municipio dispone del dinero para construir cinco estaciones de bomberos. Existen seis zonas que se encuentran sin este servicio. Se quiere construir las nuevas estaciones asegurando que un incendio en cualquiera de las zonas desprotegidas puede ser socorrido en menos de 30 minutos. Se conoce el coste para construir la estación en cada zona y el tiempo estimado de vieja entre una zona y otra. En la tabla siguiente se muestra el tiempo (en minutos) de viaje: Zona1 Zona2 Zona3 Zona4 Zona5 Zona6 Coste

Zona1 Zona2 Zona3 Zona4 0 21 40 59 20 0 48 65 41 48 0 28 55 72 30 0 58 39 61 30 41 22 40 50 36 42 45 48

Zona5 61 41 58 27 0 25 54

Zona6 42 20 39 48 28 0 60

Formule un IP que permita determinar dónde deben construirse las estaciones con el fin de minimizar costes. Defina claramente variables, función objetivo y restricciones. Solución: Variables:

Función objetivo:

Restricciones: Para construir las restricciones, se obtiene de la tabla anterior los lugares es factible construir la estaciones de bomberos para asegurar que cada zona quede a menos de 30 minutos de al menos una de ellas. Por ejemplo, para asegurar que al menos una estación quede a menos de 30 minutos de la zona 1

se debe construir en la propia zona 1 o bien en la zona 2. Construimos una tabla con las zonas factibles: .

Zona 1 2 3 4 5 6

Zonas factibles de construcción 1, 2 1,2,6 3,4 3,4,5 4,5,6 2,5,6

Entonces las restricciones quedan:

)

)

Ejercicio 2 El profesor de la asignatura de Fundamentos está preparando el certamen recuperativo. El certamen contempla cuatro preguntas las cuales serán copiadas exactamente de los certámenes 1 y 2 que ya fueron rendidos y evaluados. El puntaje promedio obtenido en cada pregunta de los certámenes 1 y 2, en escala 0.25, se presenta en la siguiente tabla:

P1 12

Cert1 P2 10

P3 17

P4 22

P1 19

Cert2 P2 13

P3 18

P4 15

El profesor considera las siguientes condiciones para la preparación del certamen recuperativo:

1. El certamen recuperativo debe incluir por lo menos una pregunta de cada certamen 1 y 2. 2. La pregunta 1 del certamen 1 no puede ser incluída si se incluye la pregunta 1 del certamen 2. 3. La pregunta 2 del certamen 1 puede ser incluída sólo si se incluye la pregunta 1 del certamen 1 y no se incluye la pegunta 2 del certamen 2. 4. La pregunta 3 del certamen 1 puede ser incluída sólo si se incluye la pregunta 4 del certamen 1. 5. La pregunta 4 del certamen 1 debe ser incluída si se incluye si se incluye la pregunta 1 del certamen 1. 6. Las preguntas 1 y 2 del certamen 2 deben ser incluídas si se incluye la pregunta 3 del certamen 1. 7. La pregunta 4 del certamen 2 puede ser incluída sólo si no se incluyen las preguntas 3 de los certámenes 1 y 2. 8. La pregunta 3 del certamen 2 no puede ser incluída si se incluyen las preguntas 1 de los certámenes 1 y 2. Formule un IP que permita determinar la composición del certamen recuperativo que entrega la mejor nota esperada. Defina claramente variables, función objetivo y restricciones. Solución: Variables:

Función objetivo:

Restricciones: 1.-

2.-

3.4.5.6.7.-

8.-

Ejercicio 3: Una fábrica de jugos procesa una bebida en sabores de melón, durazno y frutilla. La empresa estima que la demanda mínima sobre la producción sería de 12.000 litros de jugos de melón, 5.000 litros de jugo de frutilla y de 16.000 litros de jugo de durazno. El jugo se vende a 600 el litro (indistintamente sea de melón, durazno o de frutilla), y por cada tonelada de fruta se obtiene 1.000 litros de jugo. Para el refinamiento de la pulpa la empresa decide comprar la fruta a granjeros con parcelas cercanas a la fábrica. Los precios y la producción de frutas varían por cada granjero de la forma: Costo de la fruta [$/kilo] Granjero Producción [Tonelada] Melón Durazno Frutilla Melón Durazno Frutilla 1 5 7 1 150 70 500 2 6 3 120 80 3 4 2 140 550 4 6 4 70 530 5 2 2 180 60 -

Costo de transporte [$] 10000 4000 8000 6000 7000

 El granjero 1 vende los tres tipos de frutas juntas, no vende por separado.  Si la empresa compra frutillas al granjero 3 y compra duraznos al granjero 4, entonces debe comprar melones al granjero 5.

 El granjero 4 no vende menos de 2 toneladas de cada fruta que ofrece.  Se puede transportar un máximo de 40 toneladas de fruta.  La producción de jugos de durazno no debe superar a la de jugo de melón en un 50%.  La producción de jugos de melón no debe superar a la de jugo de frutilla en un 80%. Formule un modelo de programación lineal entera mixta, defina claramente objetivos, variables, función objetivo y restricciones. Solución Objetivo: Maximizar las utilidades de la empresa cumpliendo con todas las condiciones del problema. Variables:

 5 7 1   6 3  Constantes: Pij   4  2  , producción de fruta i del granjero j.     6 4 2 2    150 70 500     120 80   C ij   140  550  , costo de la fruta i del granjero j.     70 530   180 60    

10000  4000    CT j   8000  , costo de transporte por cada granjero j.  6000     7000 

Función objetivo:

Restricciones: . Producción máxima de los granjeros. . Demanda. .

El granjero 1 vende las frutas juntas. . Obligación de comprar al granjero 5. . Cantidad mínima de venta del granjero 4.

.

Cantidad máxima a transportar. . Producción de jugo de melón y durazno. Producción de jugo de melón y frutilla.

.

Activación de la variable .

.

Activación de la variable . Naturaleza de las variables.

Ejercicio 4 Considere el siguiente modelo de programación lineal entera mixta:

El Cuadro 4.3 presenta la solución óptima para todos los problemas relajados posibles de obtener (un guión en la columna correspondiente a las variables y1, y2 e y3 significa que la variable está libre en el problema relajado).

1. Resuelva este problema aplicando la técnica de ramificación y acotamiento. Explique y justifique claramente cada uno de los pasos. Solución: Se resuelve el problema relajado completo, es decir, se libera el valor de las tres variables binarias. Luego se tiene:

Subproblema 1:

En la solución del subproblema 1 el valor de la variable

no satisface la

condición de binaria, por lo tanto se ramifica en función de los valores que puede tomar: Subproblema 2: Subproblema 1 + (

)

Subproblema 3: Subproblema 1 + (

)

Subproblema 2:

Subproblema 3:

El subproblema 3 no representa una solución factible para el problema original, pero como se mencionó anteriormente, la solución del IP no puede ser mejor a la del IP relajado, como se está resolviendo un problema más

restrictivo que la relajación original el valor de la función objetivo no puede ser mejor. Se ramifica: Subproblema 4: Subproblema 1 + (

)+(

)

Subproblema 5: Subproblema 1 + (

)+(

)

Subproblema 2:

Subproblema 3: