Post on 07-Dec-2014
Tema V Programación lineal
Simulación y Optimización de Procesos Químicos
1
PROGRAMACIÓN LINEAL• Formulación general.
• Soluciones– Factibles. Cumplen las restricciones.– Básicas.n-m variables del vector de decisión son nulas– Óptimas
• Teoremas.– 1.- Si existe una solución factible existe una solución factible básica.– 2.- Si existe una solución factible básica existe una solución factible
básica óptima.
• Interpretación geométrica.– Las restricciones forman una región convexa.– Las soluciones básicas son los vértices de esa región convexa.
nmmxnxmxnasujeto
f
),1(),1(),(
)(min
bxAbAx
xcx T
Tema V Programación lineal
Simulación y Optimización de Procesos Químicos
2
PROGRAMACIÓN LINEAL
• Método simplex. • Ejemplo. Forma estandar
• Forma canónica inicial Iteración 1 Iteración 2
• Esta solución es la óptima porque todos los coeficientes del coste son positivos
0x,0 x
2x x
1xx
3xx
21
21
21
21
asujeto
fMaximizar
0x,0x0x,0 x
2 xx
1 xx
3xx
4321
421
321
21
x
xasujeto
fMinimizar
0,2x,1x,0x,0 x
0 3xx
2 x x
1 xx
4321
21
421
321
f
inicialbásicafactibleSolución
f-
x
x
3,1x,0x,1x,0 x
3 3x x4
1 x- 2x
1 xx
4321
31
431
321
f
nuevabásicafactibleSolución
f-
x
x
5,0x,0x,5.1x,5.0 x
5 2x x
5.0 0.5x 5.0 x
5.1 0.5x 5.0 x
4321
43
431
432
f
nuevabásicafactibleSolución
f-
x
x
Tema V Programación lineal
Simulación y Optimización de Procesos Químicos
3
PROGRAMACIÓN LINEAL
• Problema del transporte.
• Ejemplo en Archivos de programa/MicrosoftOffice/office10/samples/solvsamp.xls
• Formulación algebraica.
ijij
ij
ijij
jiij
ij
xc
jix
jDx
iPx
x
5
1j
3
1i
3
1
5
1
Coste
minimizar es objetivo El
,,0
negativas no son variablesLas
5,4,3,2,1,
demanda de limitaciónla cumplir debe Se
3,2,1,
producción de ónlalimitacicumplir debe Se
j. almacén al ifábrica la desde
enviadas unidades de número al Llamamos
Tema V Programación lineal
Simulación y Optimización de Procesos Químicos
4
Ejemplo 2: Problema de transporte.
Minimizar el costo de envío de mercancías desde las plantas de producción hasta los almacenes
cercanos a los centros de demanda regionales, sin exceder las existencias disponibles
en cada planta y satisfaciendo la demanda de cada almacén regional.
Cantidad a enviar de la planta "x" al almacén "y' (en la
intersección):
Plantas TotalSevill
a
Madri
d
Barcelona
Santander
Bilbao
Galicia 5 1 1 1 1 1
La Rioja 5 1 1 1 1 1
Murcia 5 1 1 1 1 1
--- --- --- --- ---
TOTAL: 3 3 3 3 3
Demandas por
almacén--> 180 80 200 160 220
Plantas: ExistenciasCostos de envío de la planta "x" al almacén "y" (en la
intersección):
Galicia 310 10 8 6 5 4
La Rioja 260 6 5 4 3 6
Murcia 280 3 4 5 5 9
Envío: 83 $ 19 $ 17 $ 15 $ 13 $ 19 $
PROGRAMACIÓN LINEALPROBLEMA TRASPORTE
Tema V Programación lineal
Simulación y Optimización de Procesos Químicos
5
PROGRAMACIÓN LINEALPROBLEMA DIETA
• 1.-Minimizar el coste de una dieta basada en el cuadro siguiente y condicionada a los requerimientos diarios de proteínas(70gr..),
• vitamina C(50gr..) y hierro(12gr.)
Medida
1 unidad
Proteína g/u
Vitamina C
mg./u.
Hierro
mg./u.
Coste
Cent/u.
Manzanas 1 med 0.4 6 0.4 8
Plátanos 1 med 1.2 10 0.6 10
Zanahorias 1 med 0.6 3 0.4 3
Dátiles ½ copa 0.6 1 0.2 20
Huevos 2 med. 12.2 0 2.6 15
Tema V Programación lineal
Simulación y Optimización de Procesos Químicos
6
PROGRAMACIÓN LINEALPROBLEMA UNIVERSIDAD
• La universidad U proporciona enseñanza de calidad tanto a estudiantes de primer ciclo como de segundo ciclo.Según el programa de calidad o de acuerdo con el plan de estudios, cada alumno de primer ciclo debe recibir por año 70 créditos de los cuales 40 son teóricos y 30 prácticos.Para los alumnos de segundo ciclo los números son: 60 créditos (30 teóricos y 30 prácticos).El número máximo de estudiantes en cada hora teórica es de 40 y en cada hora práctica 20.
• La universidad dispone de 1000 profesores de los cuales 750 son estables y 250 contratados.Cada profesor numerario puede impartir como máximo 15 créditos teóricos y 9 prácticos.Cada profesor contratado lo es para explicar 10 y 14 respectivamente.
• El precio de la matrícula es A en primer ciclo y B en segundo ciclo,• ¿ Cuántos alumnos de primer y segundo ciclo debe admitir la universidad para
que sus beneficios sean máximos?