1 Introducción y ejemplos de modelamiento a) Problema de la mochila. Una empresa está pensando invertir en cuatro proyectos diferentes, cada proyecto se finaliza a lo más en 3 años. Los flujos de caja requeridos en cada año junto con el Valor Presente Neto de cada proyecto, concluídos los años de ejecución, y las disponibilidades de recursos financieros se resumen en la siguiente tabla:
Interesa determinar en cuáles proyectos invertir de modo de conseguir el mayor V.P.N. de la inversión.
Variables de decisión: Función objetivo: Max 35×1 + 18×2 + 24×3 + 16×4 Restricciones (tres alternativas): 1° Reinvirtiendo el dinero no utilizado en un período Año 1: 10×1 + 8×2 + 6×3 + 12×4 + s1 = 30 Año 2: 8×1 + 15×2 + 4×3 + s2 = 15 + s1 Año 3: 18×1 + 16×3 ? 12 + s2 xi ? {0,1} i = 1,2,3,4 (Gp:) { (Gp:) 1,2,3,4 (Gp:) (Gp:) i (Gp:) (Gp:) con (Gp:) (Gp:) i, (Gp:) (Gp:) proyecto (Gp:) (Gp:) el (Gp:) (Gp:) en (Gp:) (Gp:) invierte (Gp:) (Gp:) se (Gp:) (Gp:) si (Gp:) (Gp:) no (Gp:) (Gp:) si (Gp:) (Gp:) 0 (Gp:) (Gp:) (Gp:) = (Gp:) = (Gp:) 1 (Gp:) xi
2° Sin invertir el dinero no utilizado en un período, pero utilizando el retorno de los proyectos concluídos: Año 1: 10×1 + 8×2 + 6×3 + 12×4 ? 30 Año 2: 8×1 + 15×2 + 4×3 ? 15 + 16×4 Año 3: 18×1 + 16×3 ? 12 + 18×2 Xi ? {0,1} i = 1,2,3,4 3° Reinvirtiendo dinero no utilizado en un período y retorno de proyectos concluídos: Año 1: 10×1 + 8×2 + 6×3 + 12×4 + s1 = 30 Año 2: 8×1 + 15×2 + 4×3 + s2 ? 15 + s1 + 16×4 Año 3: 18×1 + 16×3 ? 12 + s2 + 18×2 Xi ? {0,1} i = 1,2,3,4
Notar que el conjunto de las soluciones factibles es finito. Esto ocurrirá generalmente con los problemas de programación entera (puros). En el ejemplo, el número de soluciones factibles no supera el número de las soluciones binarias del problema (variables restringidas sólo a valores 0 o 1) que son 24 = 16, dado el número de variables utilizadas, de hecho las soluciones factibles son menos de 16 pues en particular xi=1 para i=1,2,3 y 4 no satisface las disponibilidades de capital en cualquiera de las tres alternativas.
Supongamos que adicionalmente la inversión efectuada requiera nuevas restricciones. Se debe invertir en al menos 1 de los 3 primeros proyectos: El proyecto 2 no puede ser tomado a menos que el proyecto 3 si sea tomado: Se puede tomar el proyecto 3 o 4 pero no ambos: No se puede invertir en más de dos proyectos: (Gp:) 3 (Gp:) 2 (Gp:) x (Gp:) x (Gp:) £ (Gp:) 1 (Gp:) 4 (Gp:) 3 (Gp:) £ (Gp:) + (Gp:) x (Gp:) x (Gp:) 2 (Gp:) 4 (Gp:) 3 (Gp:) 2 (Gp:) 1 (Gp:) £ (Gp:) + (Gp:) + (Gp:) + (Gp:) x (Gp:) x (Gp:) x (Gp:) x (Gp:) 1 (Gp:) 3 (Gp:) 2 (Gp:) 1 (Gp:) ³ (Gp:) + (Gp:) + (Gp:) x (Gp:) x (Gp:) x
b) Cumplimiento de un subconjunto de las restricciones de un problema. Consideremos un problema que posee las siguientes restricciones: 12×1 + 24×2 + 18×3 ? 2400 15×1 + 32×2 + 12×3 ? 1800 20×1 + 15×2 + 20×3 ? 2000 Supongamos que nos basta con obtener alguna solucion óptima que verifique el cumplimiento de al menos 2 de las 3 restricciones anteriores.
Variables de decisión Cada inecuación anterior la reemplazamos por: 12×1 + 24×2 + 18×3 ? 2400 + M1 (1-y1) 15×1 + 32×2 + 12×3 ? 1800 + M2 (1-y2) 20×1 + 15×2 + 20×3 ? 2000 + M3 (1-y3) Además, debemos agregar la restricción que permita que a lo más una de las restricciones no se cumpla: y1 + y2 + y3 ? 2 Mi = constante lo suf. grande (Gp:) { (Gp:) (Gp:) (Gp:) (Gp:) (Gp:) (Gp:) (Gp:) (Gp:) (Gp:) (Gp:) Si la restricción j no se satisface (Gp:) (Gp:) 0 (Gp:) (Gp:) (Gp:) = (Gp:) 1 (Gp:) yi (Gp:) La restricción j se satisface
c) Inclusión de costos fijos. Supongamos que se desea tener lotes de compra de un producto dado, para satisfacer demandas que fluctúan en el tiempo sobre un horizonte de planificación dividido en T períodos. Asumimos conocidos: una estimación de la demanda dt, con t = 1, 2, …, T, los costos fijos asociados a la compra de una unidad pt, los costos asociados a la mantención de una unidad en inventario de cada período ht y los costos fijos asociados a la gestión de compra en el período t, st. Observación: no se permite unidades de faltante.
Variables de decisión xt: número de unidades compradas en t. It: nivel de inventario al final del período t. yt 1 si se hace una compra en el período t. 0 si no t: 1, 2, …, T Función objetivo (Gp:) å (Gp:) = (Gp:) + (Gp:) + (Gp:) T (Gp:) t (Gp:) t (Gp:) t (Gp:) t (Gp:) t (Gp:) t (Gp:) t (Gp:) I (Gp:) h (Gp:) x (Gp:) p (Gp:) y (Gp:) s (Gp:) 1
Restricciones xt + It-1 – It = dt t = 1, 2, …, T I0 = inventario inicial xt ? Mt yt t = 1, 2, …, T Mt = cte. grande
d) Problema de cobertura: Dado un número de regiones o zonas en las cuales se ha subdividido una comuna, cuidad, país, etc., digamos que un total de m, se desea instalar un cierto número de servidores ( escuelas, centros de atención primaria de salud, compañías de bomberos, etc.) de entre un conjunto de n potenciales servidores ubicados en alguna de las zonas dadas. Se conoce la información relativa a que zonas pueden ser atendidas por cada uno de los n potenciales servidores, es decir, se conoce la matriz de incidencia A =( aij ) donde : si la zona i se puede ser atendida por el servidor j. si no i = 1,2,…..,m. j = 1,2,…..,n. (Gp:) î (Gp:) í (Gp:) ì (Gp:) = (Gp:) 0 (Gp:) , (Gp:) 1 (Gp:) ij (Gp:) a
Se desea determinar cuáles son los servidores que deben ser instalados de modo de dar cobertura a cada zona, dados los costos de instalación Cj del servidor j. Variables de desición : si se instala el servidor j. si no Función objetivo: Restricciones : Min ?j cjxj ; j =1,…,n. ?j aijxj ?1 ; i =1,…,m. Si adicionalmente, hay algún limite en el número de servidores que se pueden instalar, digamos k : ?j xj ? k (Gp:) î (Gp:) í (Gp:) ì (Gp:) = (Gp:) 0 (Gp:) , (Gp:) 1 (Gp:) j (Gp:) x
e) Problema de transporte y localización : Si se tiene un conjunto de m clientes que demandan di unidades de un producto determinado. Una compañía desea satisfacer esas demandas desde un cierto conjunto de plantas elegidas de n potenciales lugares donde se instalarán. Sean cj los costos asociados a la instalación de la planta j , vj el costo unitario de producción de la planta j y tij el costo de transporte de una unidad desde la planta j al cliente i . Se desea decidir cuáles plantas abrir y el tamaño de cada una de modo de satisfacer las demandas estimadas.
(Gp:) î (Gp:) í (Gp:) ì (Gp:) = (Gp:) 0 (Gp:) , (Gp:) 1 (Gp:) j (Gp:) y (Gp:) Si se abre la planta j. Si no xij = el número de unidades elaboradas en la planta j para satisfacer el cliente i, con j = 1,…,n. y i = 1,….,m. . Función objetivo : ?cjyj + ?vj (?xij) + ? ? tijxij costo instalación costo producción costo transporte
Restricciones : demanda cliente i: ?xij ? di i = 1,….,m Relacionar variables de producción con las asociadas a la apertura de plantas (variables binarias ): ?xij ? Mjyj ; j = 1,…,n donde Mj es una constante grande (por ejemplo, capacidad máxima de producción de la planta j). xij ? 0 ; yj ? { 0, 1}
2 Resolución de problemas de Programación Entera Supongamos que tenemos el siguiente problema de programación lineal: PL) Max cTx s.a. A x = b x ? 0 Pero todas o una parte de las variables deben restringir su valor a números enteros, dando origen a un problema de Programación Entera (puro) o de Programación Entera- Mixta, respectivamente.
Por ejemplo: PLE) Max cTx s.a. A x = b x ? 0, xj entero El problema PL) corresponde a la relajación continua del problema PLE), que resulta de eliminar las condiciones de integralidad de las variables de decisión en PLE). El valor óptimo de PL) provee sólo una cota superior del valor óptimo de PLE). Notar sin embargo, que si la solución óptima de PL) cumple con la integralidad de los valores requiridos, entonces esta solución es también solución óptima de PLE).
Ejemplo PLE) Max x2 s.a. – 2×1 + 2×2 ? 1 + 2×1 + 2×2 ? 7 x1 ? 0, x2 ? 0 enteros 7 3.5 1.5 – 2×1 + 2×2 ? 1 2×1 + 2×2 ? 7 x1 x2 . . . . . . . . .
Notar que en el ejemplo la solución óptima puede ser hallada por simple enumeración de todas las soluciones factibles, aquí las soluciones óptimas son: x1* = 1 o x1* = 2 x2* = 1 x2* = 1 Esta alternativa de enumeración queda naturalmente restringida a problemas muy pequeños. Alternativamente, podemos resolver la relajación continua asociada al problema PLE). Si la solución óptima de la relajación continua da una solución entera, esa es la solución óptima no solo del problema lineal sino que también lo es del problema lineal entero.
En el ejemplo, la solución de la relajación continua es: x1 = 3/2 x2 = 2 A partir de esta última solución podemos redondear o truncar los valores que no salieron enteros, obteniendo respectivamente en el ejemplo: x1 = 2 x1 = 1 x2 = 2 x2 = 2 las cuales no son soluciones factibles de PLE), de modo que desde el punto de vista de una resolución numérica no es suficiente con resolver la relajación continua.
Todavía podrían resultar soluciones factibles de PLE) pero no neceasariamente óptimas. Por ejemplo: PLE) Max f(x1, x2) = x1 + 5×2 s.a. x1 + 10×2 ? 10 x1 ? 1 x1 ? 0, x2 ? 0 enteros Solución óptima de PL) x1 = 1 f(1,9/10)=5,5 x2 = 9/10 Redondeando o truncando los valores x1 = 1 infactible x1 = 1 f(1,0)=1 x2 = 1 x2 = 0 Pero la solución óptima de PLE) x1=0; x2=1; v(PLE)=5
3 Método de Branch and Bound Consideremos el siguiente problema de programación entera: PLE) Max 21×1 + 11×2 s.a. 7×2 + 4×2 ? 13 x1 ? 0 x2 ? 0 x1, x2 enteros Consideremos inicialmente la resolución de la relajación continua de PLE), que consiste en eliminar las condiciones de integralidad.
x1 x2 1 2 3 21×1+11×2 21×1+11×2=39 7×1+4×2=13 X2 = 3 X2 = 2 X2 = 1 X1 = 1 X1 = 2 13/7 sol. relajada 3/2
Descripción del método Branch and Bound (maximización) Paso 0 Hacer P0, la relajación continua de PLE) fijar la cota inferior del v(PLE) en -?. Paso 1 Seleccionar un problema no resuelto, Pi Resolver Pi) como problema de programación lineal. Agotar este problema, usando: (i) que se encontró una solución entera (ii) que el problema resulta infactible (iii) que el problema no provee un valor mejor que la actual cota del valor óptimo v(PLE).
Si el problema Pi resulta agotado y da solución entera, mejorar el valor de la cota inferior de v(PLE). Si todos los problemas están agotados parar. Solución óptima de PLE), la solución entera asociada a la actual cota inferior de v(PLE), si existe (si no existe entonces PLE) es infactible) Si el problema no está agotado pasar al paso 2.
Paso 2 Seleccionar una variable xj=ûj, cuyo valor en la solución óptima de Pi) no de entero. Eliminamos la región correspondiente a ?ûj? < ûj < ?ûj? +1 Crear dos nuevos problemas de programación lineal que incorporan a Pi) dos restricciones mutuamente excluyentes: xj ? ?ûj? xj ? ?ûj? +1 una en cada problema y volver al paso 1.
(Gp:) P0 (Gp:) P1 (Gp:) P2 (Gp:) P11 (Gp:) P12 (Gp:) P121 (Gp:) P122 (Gp:) P1211 (Gp:) P1212 (Gp:) infactible (Gp:) infactible (Gp:) infactible (Gp:) x2?4 (Gp:) x2?2 (Gp:) x1?2 (Gp:) x1?1 (Gp:) x2?3 (Gp:) x2?1 (Gp:) x1?1 (Gp:) x1 = 13/7 x2 = 0 z = 39 (Gp:) x1 = 1 x2 = 3/2 z = 37.5 (Gp:) x1 = 1 x2 = 1 z = 32 (Gp:) x1 = 5/7 x2 = 2 z = 37 (Gp:) x1 = 0 x2 = 13/4 z = 35.75 (Gp:) x1 = 0 x2 = 3 z = 33 P0) Relajación continua -?< z ? 39 P1) Max 21×1 + 11×2 s.a. 7×1 + 4×2 ? 13 x1 ? 1 x1 ? 0 x2 ? 0 P2) Max 21 x1 + 11×2 s.a. 7×1 + 4×2 ? 13 x1 ? 1 x2 ? 1 x1 ? 0 x2 ? 0 De donde 32 ? z ? 39 ? ? ? Solución óptima X1* = 0 X2* = 3 Z = 33