Primer Parcial de Introducción a la Investigación de Operaciones Fecha: 5 de mayo de 2015 INDICACIONES • Duración del parcial: 3 hrs. • Escribir las hojas de un solo lado. • No se permite el uso de material ni calculadora. • Numerar las hojas. • Poner nombre y número de cédula en el ángulo superior derecho de cada hoja. • Escribir en la primera hoja el total de hojas entregadas. • Las partes no legibles del examen se considerarán no escritas. • Justifique todos sus razonamientos.

6 Puntos (3, 3) Pregunta 1 Dado el siguiente problema de Programación Matemática:

min x + y 2  (P) s.a. x + y ≥ 2  x  y ≥e

a) Escriba las ecuaciones de Kuhn Tucker para (P). No se pide resolver. b) ¿Son esas ecuaciones necesarias y suficientes para la existencia de un óptimo global al problema? Justifique. SOLUCION: a)

Reescribimos (P) para llevarlo a la forma canónica de programación matemática

min f = x + y 2  (M) s.a. g = 2 − (x + y) ≤ 0 1  x  g2 = e − y ≤0

y escribimos las condiciones de Kuhn Tucker

1− λ1 + λ2e x

=0

2y − λ1 − λ2

=0

λ1 (x + y − 2) = 0 λ2 (y − e x )

=0

x + y −2

≥0

y −e

≥0

x

λ1, λ2

≥0

NOTA: Aunque no se pide, numéricamente se puede verificar que la solución es x = 0.4428544 , y = 1.5571456 , λ1 = 2.287473 y λ2 = 0.826169 . b) Sí son necesarias y suficientes porque f , g1 y g2 en (M) son convexas, lo que implica que la región factible de (M) lo sea también. Cuando las funciones y el dominio son diferenciablas y convexas, las condiciones de Kuhn Tucker son necesarias y suficientes. 2 x La convexidad se justifica porque ± x,± y, y y e , además de infinitamente diferenciables son funciones convexas y por tanto las distintas formas de sumarlas (conjunto que incluye a f , g1 y g2 ) lo son. Por propiedad teórica, las regiones definidas por {x | g(x) ≤ α } para g convexas son convexas y las región factible de (M) es por tanto la intersección de conjuntos convexos, que también hereda la propiedad.

10 Puntos Pregunta 2 Una empresa de fabricación de muebles, fabrica escritorios, mesas y sillas. La producción de cada tipo de mueble requiere de madera y de dos tipos de mano de obra calificada: terminación y carpintería. La cantidad necesaria de cada recurso para cada tipo de mueble se da en la siguiente tabla: Recurso Madera Horas terminación Horas carpintería

Escritorio 2.5 metros 4 horas 2 horas

Mesa 1,8 metros 2 horas 1.5 horas

Silla 0.5 metros 1.5 horas 0.5 horas

La empresa dispone de 12 metros de madera, 20 horas de terminación y 8 horas de carpintería. La empresa espera vender todo lo producido de sillas y escritorios pero no se espera vender más de 5 mesas. Un escritorio se vende a 60 dólares, una mesa a 30 dólares y una silla a 20 dólares. Formular como un problema de Programación Lineal el problema de maximizar la ganancia de la empresa satisfaciendo las restricciones. SOLUCION:

x1 = cantidad de escritorios producidos x2 = cantidad de mesas producidas x3 = cantidad de sillas producidas

max 60x 1 + 30 x 2 + 20 x3 s.a.   2.5 x1 + 1.8 x 2 + 0.5 x3 ≤ 12   4 x1 + 2 x 2 + 1.5 x3 ≤ 20  2 x + 1 .5 x + 0 .5 x ≤ 8 1 2 3   x2 ≤ 5   x1 , x 2 , x3 ≥ 0

15 Puntos Pregunta 3 Dado el siguiente problema de Programación Lineal:

min x 1 − 2 x 2 s.a.   2 x1 + 3 x3 = 1  3x + 2 x − x = 5 1 2 3   x1 , x 2 , x3 ≥ 0 Determinar una solución óptima usando el Método Simplex.

SOLUCION: Planteamos la tabla inicial de Simplex para aplicar Fase I, con las variables artificiales y1, y2.

x1

x2 2 3 1 0

Fase II Fase I

x3 0 2 -2 0

y1 3 -1 0 0

y2 1 0 0 1

b 0 1 0 1

1 5 0 0

Restamos de la última fila correspondiente al problema de Fase I las filas 1 y 2, para dejar costo reducido igual a cero en las variables correspondientes a la base actual y poder comenzar el simplex. x1

x2 2 3 1 -5

Fase II Fase I

x3 0 2 -2 -2

y1 3 -1 0 -2

y2 1 0 0 0

b 0 1 0 0

1 5 0 -6

La base actual es (y1,y2). Se selecciona x1 para entrar en la base ya que es la variable no básica con menor costo reducido negativo. La variable básica que sale es y1 ya que min{1/2, 5/3} = 1/2. La nueva tabla es la siguiente. x1

x2 1 0 0 0

Fase II Fase I

x3 0 2 -2 -2

y1

3/2 -11/2 -3/2 11/2

y2 1/2 -3/2 -1/2 5/2

b 0 1 0 0

1/2 7/2 -1/2 -7/2

La base actual es (x1,y2). Se selecciona x2 para entrar en la base ya que es la variable no básica con menor costo reducido negativo. La variable básica que sale es y2. La nueva tabla es la siguiente. x1

Fase II Fase I

x2 1 0 0 0

x3 0 1 0 0

3/2 -11/4 -7 0

y1

y2 1/2 -3/4 -2 1

b 0 1/4 1 1

1/2 7/4 3 0

La base actual es (x1,x2). Llegamos al fin del problema de Fase I ya que todos los costos reducidos de la fila correspondiente son no negativos. Se encontró una solución óptima igual a cero para cada una de las variables de la Fase I y se puede continuar con el problema original de Fase II. Se selecciona x3 para entrar en la base ya que es la variable no básica con menor costo reducido negativo. La variable básica que sale es x1. La nueva tabla es la siguiente. x1

x2 2/3 11/6 14/3

Fase II

x3 0 1 0

B 1 0 0

1/3 8/3 16/3

La base actual es (x2,x3). Llegamos al fin del problema de Fase II ya que todos los costos reducidos de la fila correspondiente son no negativos. La solución óptima es x1 = 0, x2 = 8/3 y x3 = 1/3 con valor óptimo –16/3.

9 Puntos (1,1,1,4,1,1) Pregunta 4 a) Defina flujo a-z en una red de transporte b) Defina corte a-z en una red de transporte c) Dada la siguiente red de transporte: 8,7

b

d

7,7

7,7 1,0

a

z 3,0

5,0 9,5

12,5 c

e 10,5

i. ii. iii. iv.

Indique la capacidad del corte a-z (P,Pc) determinado por P = {a,b,e}. Hallar el flujo máximo aplicando el algoritmo de Ford-Fulkerson, partiendo del flujo asignado. Indique cual es el corte de capacidad mínima Indique y justifique si cambia el flujo máximo si se incrementa la capacidad del arco (e,z).

Nota: las etiquetas sobre los arcos son: Capacidad del arco, Flujo actual. SOLUCION:

a) Ver teórico b) Ver teórico c) i) (P,Pc) = { (a,c), (a,d), (b,d), (b,c), (e,d), (e,z)} K(P,Pc) = 9 + 1 + 8 + 5 + 3 + 12 = 38

ii) En la primer iteración del algoritmo, se obtiene el grafo etiquetado del siguiente modo: (a+,1) 8,7

b

d

7,7

7,7 1,0

a

(e+,4)

z 3,0

(-,∞)

5,0 9,5

12,5 c

e 10,5

(a+,4)

(c+,4)

Se ha encontrado el camino a – c – e – z, con holgura 4. Se aumenta el flujo en 4 unidades a lo largo del camino y se realiza una nueva iteración. Se obtiene el siguiente grafo etiquetado: (a+,1)

(d-,1) 8,7 b

d

7,7

7,7 1,0

a

z 3,0

(-,∞)

(e+,1)

5,0 9,9

12,9 c

e 10,9

(b+,1)

(c+,1)

Es decir, se halla el camino a – d – b – c – e – z, con holgura 1. Se aumenta el flujo en 1 unidad a lo largo de ese camino y se realiza una nueva iteración. Se obtiene el grafo: 8,6

b

d

7,7

7,7 1,1

a

z 3,0

(-,∞)

5,1 9,9

12,10 c

e 10,10

max |ϕ| = k(P,PC) = 17 iii) El corte mínimo es P = {a}, (P,PC) = {(a,b), (a,d), (a,c)}. iv) si se incrementa la capacidad del arco (e,z) no cambia el flujo máximo porque este arco no pertenece al corte mínimo y por lo tanto el aumento de capacidad no redunda en un aumento del flujo a – z. Por otro lado

los arcos entrantes al nodo e ya están saturados y no es posible aumentar el flujo saliente manteniendo la conservación del flujo, por lo cual no sirve de nada aumentar la capacidad de la arista saliente (e,z).