Upload
lev-abbott
View
37
Download
1
Embed Size (px)
DESCRIPTION
Formulación de problemas. Ejemplo sencillo de producción Fábrica de muebles Dos productos: sillas modelo A y B Demanda estimada (máxima): A: 100 B: 400 Beneficios por unidad: A: 6000 B: 3000 Requisitos de producción: A: 20 hh B: 15 hh - PowerPoint PPT Presentation
Citation preview
1
Formulación de problemas
Ejemplo sencillo de producción Fábrica de muebles
Dos productos: sillas modelo A y B Demanda estimada (máxima):
A: 100 B: 400 Beneficios por unidad:
A: 6000 B: 3000 Requisitos de producción:
A: 20 hh B: 15 hh Disponibilidad de trabajadores: 5000
hh/mes
2
Formulación de problemas
Función objetivo: beneficiosmax 6000 xA + 3000 xB
Restricciones: Capacidad de fabricación
20 xA + 15 xB 5000 Límites de demanda
0 xA 100 , 0 xB 400
3
Formulación de problemas
Planteamiento: max 6000 xA + 3000 xB
s.a 20 xA + 15 xB 5000
0 xA 100
0 xB 400
4
Formulación de problemas
Estimación costes generación eléctrica Obtener función cuadrática de costes
c (x ) = a + b x + c x 2
Dados un conjunto de observaciones,( xi , yi )
Encontrar la mejor función cuadrática que se ajuste a ellas
Mínimo error en el ajuste
5
Formulación de problemas
DatosPPootteenncciiaa CCoossttee
113300 55880066114400 66114422114455 77333366118800 1111225599220000 1133446644221100 1144993355223355 1166222200224400 1177888844225500 1199996688225555 1199660066
Cost es gener aci ón
0
5000
10000
15000
20000
25000
100 150 200 250 300
Pot enci a
Co
st
e
6
Formulación de problemas
Planteamiento Función objetivo( 5806 - a - b 130 - c 1302 )2 + ( 6142 - a -
b 140- c 1402 )2 + ( 7336 - a - b 145 - c 1452 )2 +
... En formato compacto
min i ( yi - a - b xi - c xi 2 )2
Función cuadrática de a, b, c
Formulación de problemas
Problema de transporte Descripción del problema:
Atender demanda de dos productos PR1 y PR2
Para cuatro clientes C1, C2, C3 y C4 Desde tres almacenes A1, A2 y A3
Se dispone de datos sobre demandas, capacidades y costes
77
Formulación de problemas
Datos: Capacidades de almacenesAlmacén A1 Almacén A2 Almacén A3
8500 11500 10300Demandas de clientes
Cliente C1 Cliente C2 Cliente C3 Cliente C4Producto PR1 1700 1200 1100 1000Producto PR2 750 950 500 450
Coste de transporte PR1 Cliente C1 Cliente C2 Cliente C3 Cliente C4Almacén A1 9 46 39 28Almacén A2 22 23 12 30Almacén A3 24 20 50 13
Coste de transporte PR2 Cliente C1 Cliente C2 Cliente C3 Cliente C4Almacén A1 12 55 40 32Almacén A2 25 27 15 35Almacén A3 28 70 56 18
88
Formulación de problemas
Otros datos:Espacio ocupado por los productos
Producto PR1 Producto PR2 3 5
Costes fijos: Independientes de la cantidad Cada envío supone unos costes de 5000
¿Tiempos de entrega? Se ignoran
99
Formulación de problemas
Planteamiento del problema: Variables:
Cantidades a transportar desde cada almacén i a cada cliente j de cada producto k, xijk
Función objetivo:Minimizar los costes de transporte totales
minx ijk cijk xijk
1010
Formulación de problemas
Planteamiento del problema: Función objetivo:
9x111 + 12x112 + 46x121 + 55x122 + 39x131 + 40x132
+ 28x141 + 32x142 + 22x211 + 25x212 + 23x221
+ 27x222 + 12x231 + 15x232 + ...
Restricciones: Satisfacción de la demanda de cada cliente
i xijk = djk j,k
1111
Formulación de problemas
Restricciones: Formulación de satisfacción de demandax111 + x211 + x311 = 1700, x112 + x212 + x312 = 750,
x121 + x221 + x321 = 1200, ...
Capacidad de los almacenesk ek j xijk vi i
Formulación3(x111+x121+x131+x141) + 5 (x112+x122+x132+x142) 8500,
3(x211+x221+x231+x241) + 5 (x212+x222+x232+x242) 11500,
...
1212
Formulación de problemas
Modelo resultante (un producto): min 9x11 + 22x21 + 24x31 + 46x12 + 23x22 + 20x32 + 39x13 + 12x23 +
50x33
+ 28x14 + 30x24 + 13x34
s.a x11 + x21 + x31 = 1700 x12 + x22 + x32 = 1200 x13 + x23 + x33 = 1100 x14 + x24 + x34 = 1000 x11 + x12 + x13 + x14 1500 x21 + x22 + x23 + x24 2500 x31 + x32 + x33 + x34 1500 xij 0 i = 1,2,3 j = 1,2,3,4
Solución: x11 = 1500, x21 = 200, x22 = 700, x23 = 1100, x32 = 500, x34 = 1000
1 = -13, 2 = 0, 3 = -3, 1 = 22, 2 = 23, 3 = 12, 4 = 16 1313
14
Formulación de problemas
Problema de transporte Formulación en AMPL
1414
set ORIG; # orígenesset DEST; # destinosparam supply {ORIG} >= 0; # cantidades disponibles en orígenesparam demand {DEST} >= 0; # cantidades a servir en destinos check: sum {i in ORIG} supply[i] >= sum {j in DEST} demand[j];param cost {ORIG,DEST} >= 0; # costes de transporte por unidadvar Trans {ORIG,DEST} >= 0; # número de unidades a transportarminimize total_cost: sum {i in ORIG, j in DEST} cost[i,j] * Trans[i,j];subject to Supply {i in ORIG}: sum {j in DEST} Trans[i,j] = supply[i];subject to Demand {j in DEST}: sum {i in ORIG} Trans[i,j] = demand[j];
Formulación de problemas
Planteamiento del problema: Otras restricciones:
Variables no pueden tomar valores negativos,
xijk 0 Otras consideraciones:
Costes fijos de envío: Sumar 5000 a la función objetivo por cada
variable distinta de cero
1515
Formulación de problemas
Planteamiento del problema: Costes fijos de envío:
Se introducen nuevas variables, zijk
Estas variables valen: 1 si se produce un envío (si xijk > 0) 0 si no se produce
Término adicional en la función objetivo:
...+5000 ijk xijk
1616
Formulación de problemas
Planteamiento del problema: Relación entre las variables x y z :
xijk K zijk
donde K es constante suficientemente grande (mayor que cualquier valor razonable de x )
Condición sobre z :zijk {0,1} i,j,k
1717
Formulación de problemas
Campaña de publicidad Se quiere llevar a cabo una campaña
de promoción de un nuevo producto Para ello se dispone de un
presupuesto a invertir en diferentes medios publicitarios
El objetivo es alcanzar la mayor audiencia posible de clientes potenciales
1818
Formulación de problemas
Campaña de publicidad Medios disponibles:
televisión, revistas, radio, periódicos, buzoneo
Datos Audiencia Televisión Revistas Radio Periódicos Buzoneo
3 2 1 1,5 2Costes
Televisión Revistas Radio Periódicos Buzoneo 6 2,5 1 1,2 1
Recursos necesarios Televisión Revistas Radio Periódicos Buzoneo
MáximoEscritores 12 5 2 4 3 200Ilustradores 12 8 0 6 4 300Auxiliares 2 2 2 2 2 200
1919
Formulación de problemas
Campaña de publicidad Otros datos:
Presupuesto: 100 millones de Pta Campaña debe utilizar al menos tres
medios Audiencia que se alcanza invirtiendo z
millones de Pta. en un medio:
a z 0,7
donde a constante indicada en la tabla
2020
Formulación de problemas
Campaña de publicidad Variables:
unidades de publicidad compradas a cada medio, xi
Función objetivo: audiencia alcanzada,
i ai xi
o en el caso no lineal,
i ai xi0,7
2121
Formulación de problemas
Campaña de publicidad Restricciones
Presupuesto: i ai xi P
Disponibilidad de recursos: i rij xi dj j
No negatividad: xi 0 Número mínimo de medios:
i zi 3, xi K zi , zi {0,1} i
zi k xi ¿ valor de k ?
2222
Formulación de problemas
Asignación de tripulaciones Determinar:
Número de tripulaciones a tener disponibles durante los próximos meses
Las tripulaciones pueden tomarse de una reserva, o devolverse a dicha reserva
Se desea emplear el número mínimo de tripulaciones necesario
2323
Formulación de problemas
Asignación de tripulaciones Condiciones:
Se deben cubrir las horas de vuelo:Noviembre 440Diciembre 580Enero 600Febrero 420
Cada tripulación puede hacer un máximo de 40 h. de vuelo al mes
2424
Formulación de problemas
Asignación de tripulaciones Otras condiciones:
Cada nueva tripulación debe ser entrenada
Durante el primer mes, entrenamiento cuesta 10 h. a nueva tripulación y a una tripulación ya veterana
Como máximo pueden tomarse de la reserva tres tripulaciones en un mes
2525
Formulación de problemas
Asignación de tripulaciones Variables:
Tripulaciones asignadas cada mes, xt
Var. auxiliares para facilitar la formulación Número de tripulaciones a añadir at y a
devolver a la reserva dt en cada mes Función objetivo:
t xt
2626
Formulación de problemas
Asignación de tripulaciones Restricciones:
Cumplimiento de las horas: 40xt - 10at ht
Límite nuevas tripulaciones: at 3
Necesidades de entrenamiento: xt at
Relación entre variables: xt+1 = xt + at - dt
No negatividad: xt , at , dt 0
Integralidad: xt , at , dt enteras
2727
28
Formulación de problemas
Problema resultantemin t xt
s.a 40xt - 10at ht
xt+1 = xt + at - dt
xt at
at 3
xt , at , dt 0
xt , at , dt enteras
Formulación de problemas
Optimización de carteras Dada una cantidad de dinero a
invertir Determinar proporciones a invertir en
distintos activos Criterios para seleccionar activos:
Rentabilidad Riesgo
2929
Formulación de problemas
Optimización de carteras Datos rentabilidades/riesgos:
aaaccctttiiivvvooo---111 aaaccctttiiivvvooo---222 aaaccctttiiivvvooo---333 aaaccctttiiivvvooo---444 aaaccctttiiivvvooo---555 aaaccctttiiivvvooo---666888555000444 555,,,555333 333,,,111999 111444,,,666666 888,,,555999 000,,,888888 ---111555,,,999333888555000555 444,,,888000 000,,,444111 ---222,,,111111 ---111,,,000888 777,,,444666 ---222,,,111111888555000666 ---333,,,111333 ---555,,,777555 111555,,,888222 111666,,,000000 ---888,,,111666 ---555,,,999111888555000777 666,,,888888 222000,,,000444 999,,,999555 111333,,,444888 111777,,,777888 444,,,000000888555000888 777,,,444444 222444,,,666888 222111,,,888333 333222,,,888777 ---777,,,555555 ---555,,,222222888555000999 ---111,,,666999 ---111000,,,777777 ---111000,,,888999 ---111777,,,000555 000,,,000000 111222,,,444666888555111000 ---555,,,777111 ---111666,,,444888 ---111,,,000000 ---444,,,222666 ---333,,,222777 333,,,000999888555111111 ---111,,,000111 222111,,,444888 111,,,000111 ---333,,,444000 ---111,,,666999 666,,,222555
activo-1 activo-2 activo-3 activo-4 activo-5 activo-6Media 1,64 4,60 6,16 5,64 0,68 -0,42Desv.típica 5,09 15,74 11,10 15,39 8,50 8,77
3030
Formulación de problemas
Optimización de carteras: Datos para la formulación
Rentabilidades medias y objetivo:r = ( 1.6 4.6 6.2 5.6 0.7 -0.4 ) , = 5
Riesgos: matriz de covarianzas, 26 56 28 45 21 -19 56 248 89 141 31 -15 R = 28 89 223 63 -22 -63 45 141 63 137 -22 -82 21 31 -22 -22 72 16 -19 -15 -63 -82 16 77
3131
Formulación de problemas
Optimización de carteras Variables:
Proporción de la cartera en activo i , xi
Función objetivo: Riesgo de la cartera, medido por la
varianza
xTR x Restricciones: rentabilidad objetivo
3232
Formulación de problemas
Optimización de carteras Restricciones
Rentabilidad, rTx Normalización,
eTx = 1 No negatividad, x 0
3333
34
Formulación de problemas
Optimización de carteras En formato menos compacto
Rentabilidad, i ri xi Normalización,
i xi = 1 No negatividad, xi 0 Función objetivo, i rij xi xj
35
Formulación de problemas
Modelo resultante min xTR x s. a rTx eTx = 1 x 0 Solución:
x = ( 0 0 0.32 0.55 0 0.13 )T
36
Formulación de problemas
Problema de producción Una empresa fabrica 3 productos: A, B y C
empleando 5 equipos: I, II, III, IV y V El producto C requiere una unidad de A y 2 de B Los beneficios por unidad son: A: 20 B: 8 C:
38 Los tiempos necesarios por unidad son I II III IV V A 0.8 0.5 0.1 0.3 B 0.25 0.1 0.15 C 0.15 El número de equipos disponibles es I: 20 II: 5 III: 10 IV: 4 V: 6 Cada equipo se puede operar 200 horas en un
mes
37
Formulación de problemas
Problema de producciónmax 20 xA + 8 xB + (38 - 20 - 16) xC
s.a 0.8 xA + 0.25 xB 4000
0.1 xB 1000
0.5 xA + 0.15 xB 2000
0.1 xA + 0.15 xC 800
0.3 xA 1200
- xA + xC 0
- xB + 2 xC 0
xA , xB , xC 0
38
Formulación de problemas
Problema en forma estándarmax 20 xA + 8 xB + (38 - 20 - 16) xC
s.a 0.8 xA + 0.25 xB + sI = 4000
0.1 xB + sII = 1000
0.5 xA + 0.15 xB + sIII = 2000
0.1 xA + 0.15 xC + sIV = 800
0.3 xA + sV = 1200
- xA + xC + sA = 0
- xB + 2 xC + sB = 0
x , s 0
39
Formulación de problemas
Posibles soluciones ¿Puede ser solución fabricar las cantidadesxA = 2500 , xB = 5000 , xC = 2000 ?
(sI = 750, sII = 500, sIII = 0, sIV = 205, sV = 450, sA = 200, sB = 400)
¿Puede ser solución fabricar solo C?xA = 2500 , xB = 5000 , xC = 2500 (z = 95000)
(sI = 750, sII = 500, sIII = 0, sIV = 175, sV = 450, sA = 0, sB = 0) III = -47.5, A = -3.75, B = 0.875
La solución es:xA = 1000 , xB = 10000 , xC = 1000 (z = 102000)
(sI = 700, sII = 0, sIII = 0, sIV = 550, sV = 900, sA = 0, sB = 8000)
40
Formulación de problemas
Problema dualmin 40 yI + 10 yII + 20 yIII + 8 yIV + 12 yV
s.a 0.8 yI + + 0.5 yIII + 0.1 yIV + 0.3 yV - zA - w1 = 20 0.25 yI + 0.1 yII + 0.15 yIII + - zB - w2 = 8 0.15 yIV + zA + 2zB - w3 = 2
y , z , w 0
Formulación de problemas
Planificación de generación eléctrica Se dispone de una central de generación
Determinar niveles óptimos de generación Para una estimación de precios Correspondiente a 24 horas del día siguiente
Beneficios Ingresos basados en precios de mercado Costes asociados a la tecnología
4141
Formulación de problemas
Planificación de generación eléctrica Restricciones tecnológicas
Límites a la generación 0 gt 400 Mínimos técnicos gt { 0 , [100,400] } Límites en los cambios de nivel de
generaciónDe un periodo al siguiente, cambio máximo de 50
MWh
4242
Formulación de problemas
Planificación de generación eléctrica Costes de generación
Costes variables 55 + 6.4 g + 0.001 g 2
Costes fijos Arranque: 720 , Parada: 260
Precios estimados 3.47 3.67 6.17 6.36 6.36 8.68 8.78 8.70 7.50 6.32 6.38
6.37
4343
Formulación de problemas
Planificación de generación eléctrica Variables: niveles de generación gt
Función objetivo: beneficios totales t ( pt gt - 55 - 6.4 gt - 0.001 gt
2 )
Restricciones: Límites a los cambios de nivel -50 gt - gt -1 50
¿Arranques y paradas?
4444
Formulación de problemas
Restricciones planificación generación
Valores permitidos de las variables gt = 100 zt + wt , 0 wt 300zt , zt {0,1} Cambios en nivel de generación
-50 wt - wt -1 50 Costes de arranque
Cuándo se produce un arranque: yt {0,1}
Costes totales de arranque: 720 t yt
Relación con otras variables: zt - zt -1 yt
4545
46
Formulación de problemas
Generación central ciclo combinado Central eléctrica: dos modos de operación
Ciclo de gas Ciclo combinado (gas + carbón)
Características diferentes en ambos ciclos Costes Capacidad
Restricciones que ligan los ciclos
47
Formulación de problemas
Datos Costes operación:
gas: cg + agx + bgx2
combinado: cc + acx + bcx2
Costes arranque:gas: sg combinado: sc
Capacidades:gas: ug combinado: uc (mínimo:
lc )
48
Formulación de problemas
Datos Tiempos mínimos:
Entre arranque gas y arranque combinado: tc
Entre apagado y arranque: ta
Otros datos: Precios de mercado conocidos: pt
Objetivo: Beneficios
49
Formulación de problemas
Variables Generación de energía en cada periodo: xt
Ciclo de gas funcionando: yt
Ciclo combinado funcionando: zt
Arranque del ciclo de gas: vt
Arranque del ciclo combinado: wt
Función objetivot [ pt xt - yt (cg + agx + bgx2 ) - zt (cc + acx +
bcx2 - cg - agx - bgx2 ) - vt cg - wt cc ]
50
Formulación de problemas
Restriccioneszt lc xt yt ug + zt (uc - ug )
wt yt-t’ t’ = 0,...,tc
vt 1 - yt-t’ t’ = 1,...,ta
vt yt - yt -1
wt zt - zt -1
zt yt
yt , zt , vt , wt { 0,1 }
51
Formulación de problemas
Ampliación de la red de transporte Estudiar la instalación de nuevas
líneas para transmisión de energía eléctrica
Se dispone de una red de transmisión Se estudian alternativas de líneas entre
diferentes puntos (nodos) del sistema Se conocen a priori las características de
las líneas a construir (y su coste)
52
Formulación de problemas
Datos Capacidades de generación, gi
Capacidades máximas de las líneas, kij
Coste de cada nueva línea, vij
Conductancia de líneas, cij
Susceptancia de líneas, ij
Existencia de líneas, sij
Vale 1 si la línea existe y 0 si no
Límites para los ángulos de voltaje, dij
53
Formulación de problemas
Variables Energía transportada en cada línea, xij
Generación en cada central, yi
Construcción (o no) de una línea, zij
Pérdidas en cada línea, wij
Diferencia de ángulos de voltaje, ij
54
Formulación de problemas
Función objetivo: Coste de operación y construcción
jj vij zij + j yi Restricciones
Balance de energía- j sij xij + yi = di
Pérdidas en las líneaswij = 2 cij zij (1 - cos ij )
Relación entre flujos y ángulosxij = ij zij sin ij
55
Formulación de problemas
Otras restricciones Restricciones de cota
0 xij kij
0 yi gi
-dij ij dij
Otras restriccioneszij [0,1]
56
Formulación de problemas
Ejercicio formulación Frutos secos: almendras, cacahuetes, nueces Dispone de 150 Kg, 100 Kg y 50 Kg respect. Tres productos, con porcentajes A 20 80 0 B 30 50 20 C 50 20 30 Beneficios esperados: 90 (A), 120 (B), 160 (C) ¿Cantidad de cada producto?
57
Formulación de problemas
Ejercicio formulación Dispones de 5 Mpta para invertir Alternativas
Bonos a 1 año: 5,5 % Letras a 2 años: 12,5 % (total) Inicio del segundo año: oblig. a 3 años,
19 % Inversiones al comienzo de cada año
Durante los próximos 5 años
58
Indice
Ejemplo sencillo de producciónEstimación costes generación eléctricaProblema de transporteCampaña de publicidadAsignación de tripulacionesOptimización de carterasProblema de producciónPlanificación de generación eléctricaGeneración central ciclo combinado