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