05 de octubre de 2017 formulaciÓn de modelos de ... 05 (05-10-17).pdfprogramación entera josé...
TRANSCRIPT
Programación Entera José Luis Quintero 1
FORMULACIÓN DE MODELOS DE PROGRAMACIÓN
ENTERAAPLICACIONES ECONÓMICAS
Ingeniería en Informática
Ingeniería Industrial
Universidad Católica Andrés Bello
05 de Octubre de 2017
Programación Entera José Luis Quintero 2
1. Economías de escala
2. Modelos de inversión en proyectos
3. Fabricación de vehículos
Puntos a tratar
Programación Entera José Luis Quintero 3
Una compañía fabrica tres productos, cuyosprecios de venta por unidad son 15, 40 y 60unidades monetarias. Para producir unaunidad de cada uno de ellos se requiere unahora, hora y media y dos horas máquina,respectivamente. La capacidad de la plantaimpone un límite de 2.000 horas máquina porsemana. Debido al descuento por volumende compras que ofrece un proveedor, loscostes unitarios decrecen de forma discreta amedida que aumenta la cantidad comprada.
Ejemplo 1. Economías de escala
Programación Entera José Luis Quintero 4
La cantidad máxima a fabricar por cadaproducto viene dada por 2000, 1340 y 1000unidades respectivamente.
En la tabla, se muestran estos costes:
Ejemplo 1. Economías de escala
2030403
1518202
58101
> 500�unidades
101- 500unidades
1-100unidades
Coste variable
Producto
2030403
1518202
58101
> 500�unidades
101- 500unidades
1-100unidades
Coste variable
Producto
Programación Entera José Luis Quintero 5
Se desea maximizar el margen deganancia neta (ingresos menos costesvariables) de tal forma que laproducción de cada uno de losproductos suponga, al menos, un 15 por100 de la cantidad total producida.
Ejemplo 1. Economías de escala
Programación Entera José Luis Quintero 7
Producto 1-100 ud. 101-500 ud. >500 ud.Precio
(um/ud)Requerimientos de máquina (h)
Producción mínima
1 10 8 5 15 1 15%2 20 18 15 40 1,5 15%3 40 30 20 60 2 15%
2000
Coste variable
Horas máquina por semana
El planteamiento del problema es el siguiente:yjk: variable binaria que toma valor 1 si se produce elproducto j en el tramo k y 0 en caso contrario.xjk: cantidad de producto j producida en el tramo k.
Ejemplo 1. Economías de escala
Programación Entera José Luis Quintero 8
Max (z)= (15-10) x11 + (15-8) x12+ (15-5) x13 + (40-20) x21 + (40-18) x22+(40-15) x23+(60-40) x31+(60-30)x32+ (60-20) x33
Sujeto a:
Horas disponibles:
x11+ x12+ x13+ 1,5x21 + 1,5x22+ 1,5x23+2x31+ 2x32+ 2x33 ≤≤≤≤ 2000
Límites superiores en tramos de producción:Producto 1) x11≤≤≤≤ 100 y11 x12≤≤≤≤ 500 y12 x13≤≤≤≤ 2000 y13Producto 2) x21≤≤≤≤ 100 y21 x22≤≤≤≤ 500 y22 x23≤≤≤≤ 1340 y33Producto 3) x31≤≤≤≤ 100 y31 x32≤≤≤≤ 500 y32 x33≤≤≤≤ 1000 y33
Límites inferiores en tramos de producción:Producto 1) x12 ≥≥≥≥ 101 y12 x13 ≥≥≥≥ 501 y13Producto 2) x22 ≥≥≥≥ 101 y22 x23 ≥≥≥≥ 501 y23Producto 3) x32 ≥≥≥≥ 101 y32 x33 ≥≥≥≥ 501 y33
Ejemplo 1. Economías de escala
Programación Entera José Luis Quintero 9
Sólo se puede producir en un tramo:
Producto 1) y11 + y12 + y13 ≤≤≤≤ 1
Producto 2) y21 + y22 + y23 ≤≤≤≤ 1
Producto 3) y31 + y32 + y33 ≤≤≤≤ 1
Restricciones de producción mínima:
P1) x11+x12+x13 ≥≥≥≥ 0.15 (x11+x12+x13+x21+x22+x23+x31+x32+x33)
P2) x21+x22+x23 ≥≥≥≥ 0.15 (x11+x12+x13+x21+x22+x23+x31+x32+x33)
P3) x31+x32+x33 ≥≥≥≥ 0.15 (x11+x12+x13+x21+x22+x23+x31+x32+x33)
No negatividad e integralidad:
x11, x12, x13, x21, x22, x23, x31, x32, x33 ≥≥≥≥ 0
y11, y12, y13, y21, y22, y23, y31, y32, y33 ∈{∈{∈{∈{0,1}}}}
Ejemplo 1. Economías de escala
Programación Entera José Luis Quintero 10
Una compañía de productos químicos fabricaun determinado compuesto. Las materiasprimas que lo forman, deben someterse a unproceso de mezcla a altas temperaturas enuna cuba con capacidad para mezclar 300tm/mes. Este proceso tiene economías deescala, de forma que el coste decalentamiento de las primeras 100tm es de400 €/tm, el de las siguientes 100tm es de 250€/tm y el de las últimas 100tm es de 150 €/tm.
Ejemplo 2. Economías de escala
Programación Entera José Luis Quintero 11
Además, la demanda es sensible a lacantidad lanzada al mercado, de forma queel precio neto del producto (PVP menos costede las materias primas) varía de acuerdo conla cantidad producida, tal y como se muestraen la tabla.
Ejemplo 2. Economías de escala
Programación Entera José Luis Quintero 12
Desde Hasta1 0 50 4502 51 100 4303 101 150 3804 151 200 3505 201 250 3106 251 300 280
Precio Neto (um/Tm)
Producción TmTramo
Se desea determinar el plan de operacionesque maximiza la ganancia neta del proceso(ingresos menos costes variables).
Ejemplo 2. Economías de escala
Programación Entera José Luis Quintero 14
Coste de calentamiento
(um/Tm)Primeras 100 400Siguientes 100 250Últimas 100 150
Tm Calentadas
Desde Hasta1 0 50 4502 51 100 4303 101 150 3804 151 200 3505 201 250 3106 251 300 280
Precio Neto (um/Tm)
Producción TmTramo
Ejemplo 2. Economías de escala
Programación Entera José Luis Quintero 15
El planteamiento del problema es el siguiente:
yi: variable binaria que toma valor 1 si se produceen el tramo i de la función de costes y 0 en casocontrario.
xi: cantidad de producto obtenida en el tramo i dela función de costes.
ij: variable binaria que toma valor 1 si se vende enel tramo j de la función de precios y 0 en casocontrario.
qj: cantidad de producto vendida en el tramo j dela función de ventas.
Ejemplo 2. Economías de escala
Programación Entera José Luis Quintero 16
Max (z)= 450 q1+430 q2+380 q3+350 q4+310 q5+280 q6-400 x1-250 x2 –150x3
L1 = 100, L2 = 200, L3 = 300Las primeras L1 se producen a un coste unitario de c1.Las siguiente L2-L1 unidades se producen a un coste unitariode c2.Las últimas L3-L2 unidades se producen a un coste unitariode c3
Sujeto a:Se escoge un solo tramo o ninguno: y1 + y2 + y3 ≤ 1
Límites de producción en cada tramo: Cada variable xi tiene unlímite superior, que se activa si alguna de las variables yi+1,yi+2,… toma el valor 1.x1 ≤ L1(y1+y2+y3) x2 ≤ (L2-L1) (y2+y3) x3 ≤ (L3-L2) y3
Ejemplo 2. Economías de escala
Programación Entera José Luis Quintero 17
Restricciones de continuidad: si se activa la variablecorrespondiente a un tramo, todos los tramos anteriores debenagotarse.
x1 ≥ L1(y2+y3) x2 ≥ (L2-L1) y3
Ejemplo 2. Economías de escala
Cantidad vendida igual a cantidad producida:q1 + q2 + q3 + q4 + q5 + q6 = x1 + x2 + x3
Límites en tramos de función de costes:x1≤≤≤≤ 100 (y1+ y2+ y3) x2≤≤≤≤ 100 (y2+ y3) x3≤≤≤≤ 100 y3
Restricciones de continuidad: x1 ≥≥≥≥ 100 (y2+ y3) x2 ≥≥≥≥ 100 y3
Programación Entera José Luis Quintero 18
Sólo se puede seleccionar un tramo: i1 + i2 + i3 + i4 + i5 + i6 ≤≤≤≤ 1
Límites en los tramos de la función de precios netos:q1≤≤≤≤ 50 i1 q1 ≥≥≥≥ 0 i1q2≤≤≤≤ 100 i2 q2 ≥≥≥≥ 51 i2q3≤≤≤≤ 150 i3 q3 ≥≥≥≥ 101 i3q4≤≤≤≤ 200 i4 q4 ≥≥≥≥ 151 i4q5≤≤≤≤ 250 i5 q5 ≥≥≥≥ 201 i5q6≤≤≤≤ 300 i6 q6 ≥≥≥≥ 251 i6
No negatividad e integralidad:x1, x2, x3 ≥≥≥≥ 0 q1, q2, q3, q4, q5, q6 ≥≥≥≥ 0 y1, y2, y3 ∈{∈{∈{∈{0,1}}}} i1, i2, i3, i4, i5 , i6 ∈{∈{∈{∈{0,1}}}}
Ejemplo 2. Economías de escala
Programación Entera José Luis Quintero 19
1. Economías de escala
2. Modelos de inversión en proyectos
3. Fabricación de vehículos
Puntos a tratar
Programación Entera José Luis Quintero 20
ProyectoNaturaleza de la
inversiónVAN Empleados
Flujos de caja
Año
1 2 3 4 5
1 Subcontratar laproducción de piezas
757 7 5 5 5 5 2
2 Adquirir una fábrica yaexistente
825 35 15 12 4 4 4
3 Construir una nuevafábrica
987 20 30 2 0 0 8
4 Subcontratar ensamblajede piezas
350 12 10 10 10 6 3
5 Ensamblar piezas enequipos existentes
596 65 7 4 4 4 4
6 Ensamblar piezas enequipos nuevos
650 60 15 2 2 2 2
7 Almacenar radios en unalmacén alquilado
1.420 20 50 10 5 0 0
8 Almacenar radios en unalmacén nuevo
1.425 5 7 7 7 7 7
Presupuesto de inversión
70 30 15 15 15
Ejemplo 3. Modelo de inversión
Programación Entera José Luis Quintero 21
FLUJOS DE CAJAPROYECTO VAN EMPLEADOS 1 2 3 4 5
1 757 7 5 5 5 5 22 825 35 15 12 4 4 43 987 20 30 2 0 0 84 350 12 10 10 10 6 35 596 65 7 4 4 4 46 650 60 15 2 2 2 27 1420 20 50 10 5 0 08 1425 5 7 7 7 7 7
MAXIMO 100 70 30 15 15 15
El planteamiento del problema sería:yi: variable binaria que toma valor 1 si se aceptael proyecto de inversión i y 0 en caso contrario.
Ejemplo 3. Modelo de inversión
Programación Entera José Luis Quintero 22
Max (z) = 757 y1+825 y2+987 y3+350 y4+596 y5+650 y6+1.420 y7+1.425 y8
Sujeto a:Máximo número de empleados:7 y1+ 35 y2+ 20 y3+ 12 y4+ 65 y5+ 60 y6+ 20 y7+ 5 y8 ≤≤≤≤ 100
Disponibilidades monetarias cada año:5y1+ 15y2+ 30y3+ 10y4+ 7y5+ 15y6+ 50y7+ 7y8≤≤≤≤ 705y1+ 12y2+ 2y3+ 10y4+ 4y5+ 2y6+ 10y7+ 7y8≤≤≤≤ 305y1+ 4y2 + 10y4+ 4y5+ 2y6+ 5y7+ 7y8≤≤≤≤ 155y1+ 4y2 + 6y4+ 4y5+ 2y6+ y7+ 7y8≤≤≤≤ 152y1+ 4y2 + 8y3+ 3y4+ 4y5+ 2y6+ y7+ 7y8≤≤≤≤ 15
Seleccionar un proyecto de cada tipo:y1 + y2 + y3 = 1 y4 + y5 + y6 = 1 y7 + y8 = 1Restricciones de integralidad:
y1, y2, y3, y4, y5, y6, y7, y8 ∈{∈{∈{∈{0,1}}}}
Ejemplo 3. Modelo de inversión
Programación Entera José Luis Quintero 31
En la tabla se resumen las características de unconjunto de proyectos de inversión, cada unopuede abordarse en dos fechas, el año 0 y el año 1.
A cada combinación de proyecto y fecha decomienzo le corresponde una proyección del flujode caja para un periodo de cuatro años, a partir dela fecha de comienzo de la inversión. Estos flujospermiten calcular el valor actualizado neto (VAN)de cada proyecto, que se obtiene descontando alaño 0 los flujos de caja a una tasa del 15 por 100.
Ejemplo 5. Proyectos de inversión
Programación Entera José Luis Quintero 32
Además, se establecen las siguientes relaciones de dependencia, indivisibilidad y reinversión de fondos:
Proyecto Comienzo 0 1 2 3 VAN (k=15%)1 0 -3.000 1.200 1.600 1.600 3051 1 -3.500 1.600 1.800 -6502 0 -1.000 1.000 1.300 1.300 1.7072 1 -1.200 1.400 1.500 1.0013 0 -2.000 1.200 1.600 1.600 1.3053 1 -2.500 1.800 1.800 3714 0 -1.000 400 800 900 5454 1 -1.250 900 1.000 2515 0 -800 1.000 1.000 1.000 1.4835 1 -850 1.500 1.500 1.381
Flujos de Caja
Ejemplo 5. Proyectos de inversión
Programación Entera José Luis Quintero 33
Los proyectos 2 y 3 dependen del proyecto 1, nopueden realizarse si éste no se selecciona.
Los proyectos 4 y 5 son independientes.
Los proyectos son indivisibles y sólo puedenseleccionarse una vez.
Las disponibilidades generadas por una inversióndurante el año, pueden aplicarse a las inversionesrealizadas en dicho año, si las hay.
La caja sobrante después de atender las alternativas deinversión se acumula a las disponibilidades del periodosiguiente, produciendo un interés del 10%,
Ejemplo 5. Proyectos de inversión
Programación Entera José Luis Quintero 34
¿Cuáles son las inversiones que proporcionan elmáximo VAN, teniendo en cuenta que en el año 0 sedispone de 6.000 u.m. y en el año 1 de 5.000 u.m.?
El planteamiento del problema sería:
ypt: variable binaria que toma valor 1 si se seleccionael proyecto p en la fecha de comienzo t y 0 en casocontrario.
Ct: Sobrante de caja del período t.
Ejemplo 5. Proyectos de inversión
Programación Entera José Luis Quintero 35
DEPENDENCIAS DEL PROYECTO 2
Ejemplo 5. Proyectos de inversión
Programación Entera José Luis Quintero 36
Max (z)= 305y10-650y11+1707y20+1001y21+1305y30+ 371y31+ 545y40+ 251y41+1483y50+1381y51
Sujeto a:
Cada inversión sólo se selecciona una vez:
Proyecto 1) y10+ y11≤≤≤≤ 1 Proyecto 2) y20+ y21≤≤≤≤ 1
Proyecto 3) y30+ y31≤≤≤≤ 1 Proyecto 4) y40+ y41≤≤≤≤ 1
Proyecto 5) y50+ y51≤≤≤≤ 1
Dependencia entre inversiones:
y20 - y10≤≤≤≤ 0 y30 - y10≤≤≤≤ 0
y21 - y11 - y10≤≤≤≤ 0 y31 - y11 - y10≤≤≤≤ 0
Ejemplo 5. Proyectos de inversión
Programación Entera José Luis Quintero 37
Restricción de caja:
Año 0)
3.000y10+1.000y20+2.000y30+1.000y40+800y50+C0 = 6.000
Año 1)
3.500y11+1.200y21+2.500y31+1.250y41+850y51–(1.200y10+1.000y20+1.200y30+400y40+1.000y50) –1,1C0 ≤≤≤≤ 5.000
Restricciones de integralidad:
y10, y20, y30, y40, y50, y11, y21, y31, y41, y51∈{∈{∈{∈{0,1}}}}
Ejemplo 5. Proyectos de inversión
Programación Entera José Luis Quintero 38
Una empresa está pensando invertir en cuatroproyectos diferentes, cada proyecto se finaliza a lomás en 3 años. Los flujos de caja requeridos en cadaaño junto con el Valor Presente Neto de cadaproyecto, concluídos los años de ejecución, y lasdisponibilidades de recursos financieros se resumen enla siguiente tabla:
Proy 1 Proy 2 Proy 3 Proy 4 Disp. Recursos
Año 1 10 8 6 12 30
Año 2 8 15 4 0 15
Año 3 18 0 16 0 12
V.P.N. 35 18 24 16
Ejemplo 6. Proyectos de inversión
Programación Entera José Luis Quintero 39
Interesa determinar en cuáles proyectos invertir demodo de conseguir el mayor V.P.N. de la inversión.
Variables de decisión:
4,3,2,1iconosin,0
iproyectoeleninviertesesi,1xi ====
====
Función objetivo:
Max 35x1 + 18x2 + 24x3 + 16x4
Ejemplo 6. Proyectos de inversión
Programación Entera José Luis Quintero 40
Restricciones (tres alternativas):
1) Reinvirtiendo el dinero no utilizado en unperíodo:
Año1: 10x1 + 8x2 + 6x3 + 12x4 + s1= 30
Año2: 8x1 + 15x2 + 4x3 + s2 = 15 + s1
Año3: 18x1 + 16x3 ≤≤≤≤ 12 + s2
xi ∈∈∈∈ {0,1} i = 1,2,3,4
Ejemplo 6. Proyectos de inversión
Programación Entera José Luis Quintero 41
2) Sin invertir el dinero no utilizado en unperíodo, pero utilizando el retorno de losproyectos concluídos:
Año1: 10x1 + 8x2 + 6x3 + 12x4 ≤≤≤≤ 30
Año2: 8x1 + 15x2 + 4x3 ≤≤≤≤ 15 + 16x4
Año3: 18x1 + 16x3 ≤≤≤≤ 12 + 18x2
xi ∈∈∈∈ {0,1} i = 1,2,3,4
Ejemplo 6. Proyectos de inversión
Programación Entera José Luis Quintero 42
3) Reinvirtiendo el dinero no utilizado en unperíodo y, también el retorno de proyectosconcluídos:
Año1: 10x1+ 8x2+ 6x3+ 12x4+ s1 = 30
Año2: 8x1+ 15x2+4x3+ s2 = 15 + s1 + 16x4
Año3: 18x1 + 16x3 ≤≤≤≤ 12 + s2 + 18x2
xi ∈∈∈∈ {0,1} i = 1,2,3,4
Ejemplo 6. Proyectos de inversión
Programación Entera José Luis Quintero 43
Note que el conjunto de las solucionesfactibles es finito. Esto ocurrirá generalmentecon los problemas de Programación Entera(puros). En el ejemplo, el número de solucionesfactibles no supera el número de las solucionesbinarias del problema (variables restringidassólo a valores 0 o 1) que son 2^4 = 16, dado elnúmero de variables utilizadas, de hecho lassoluciones factibles son menos de 16 pues enparticular xi=1 para i=1,2,3,4 no satisface lasdisponibilidades de capital en cualquiera delas tres alternativas.
Ejemplo 6. Proyectos de inversión
Programación Entera José Luis Quintero 44
Suponga que adicionalmente la inversiónefectuada requiera nuevas restricciones.
1. Se debe invertir en al menos 1 de los 3primeros proyectos:
x1 + x2 + x3 => 1
2. El proyecto 2 no puede ser tomado amenos que el proyecto 3 si sea tomado:
x2 <= x3
Ejemplo 6. Proyectos de inversión
Programación Entera José Luis Quintero 45
3. Se puede tomar el proyecto 3 o 4 pero noambos:
x3 + x4 <= 1
4. No se puede invertir en más de dosproyectos:
x1 + x2 + x3 + x4 <= 2
Ejemplo 6. Proyectos de inversión
Programación Entera José Luis Quintero 46
1. Economías de escala
2. Modelos de inversión en proyectos
3. Fabricación de vehículos
Puntos a tratar