Tema4

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



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



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



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



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



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?

Documents

Tema4