• Author / Uploaded
• Jenny Hicks

• Categories
• Matemática aplicada
• Física y matemáticas
• Matemática
• Programación de computadoras
• Áreas de la informática

Citation preview

Investigaci´on de Operaciones 1 Examen supletorio 8 de marzo de 2017

Escuela Polit´ecnica Nacional Facultad de Ciencias Profesor: Diego Recalde, Ph.D.

Pregunta 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . El administrador de una red de internet (miniatura) necesita establecer tres conexiones: entre los usuarios A y B, entre los usuarios B y C, y entre los usuarios A y C. Cada conexi´on requiere al menos dos unidades de banda ancha, pero obviamente se puede asignar un mayor ancho de banda. La conexi´ on A-B paga 3 USD por unidad de ancho de banda asignado, y las conexiones B-C y A-C pagan 2 USD y 4 USD, respectivamente. Cada conexi´on puede ser enrutada de dos maneras: por un camino corto y uno largo. ¿C´omo se deben enrutar estas conexiones para maximizar el beneficio por el pago de los usuarios de la red? (a) (6 puntos) Escriba un modelo de programaci´on lineal para este problema. (b) (6 puntos) Escriba el modelo en el lenguaje de modelizaci´on ZIMPL. (c) (2 puntos) Encuentre la soluci´on usando el solver SCIP y com´entela. Pregunta 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A continuaci´ on se presenta una tabla simplex ´optima para un problema de maximizaci´on.

z x3 x2 x1

x1 0 0 0 1

x2 0 0 1 0

x3 0 1 0 0

x4 3 1 1 -1

x5 2 -1 0 1

soluci´on ? 2 6 2

(a) (4 puntos) Si las variables x3 , x4 y x5 son variables de holgura en el problema original, use manipulaci´ on matricial (no ejecute iteraciones del Simplex) para encontrar el LP original y luego calcule la soluci´ on ´ optima. (b) (2 puntos) Encuentre el dual del problema original y sin ejecutar el Simplex, encuentre el valor ´ optimo de las variables duales.