EII-405 Investigación de operaciones1 Programación Lineal La programación lineal es el área de la IO que se ocupa de problemas en donde el modelo matemático

EII-405 Investigación de operaciones 1

Programación Lineal

La programación lineal es el área de la IO que se ocupa de problemas en donde el modelo matemático que se formula es expresado en términos de funciones lineales.


Ejemplo tipo

Supongamos que se dispone de determinadas piezas: 8 piezas pequeñas y 6 piezas grandes. Estas son utilizadas en la elaboración de 2 productos: sillas y mesas. En una silla se utilizan 2 piezas pequeñas y 1 grande, mientras que en la mesa se utilizan 2 pequeñas y 2 grandes.

Interesa decidir cuántas sillas y mesas fabricar, dada una utilidad de U$15 por silla y U$20 por mesa.

Posibles soluciones: Sillas Mesas Utilidadi 4 U$60ii 2 2 U$70iii 3 U$60iv 1 3 U$65

etc.. .. ..

Todas son factibles pues respetan las

restricciones


modelo matemático

Tiene 3 componentes principales:

1.- Definir las variables de decisión.

x:número de sillas elaboradas.y:número de mesas elaboradas.

2.- Definir la Función Objetivo del problema.

Maximizar z=15x+20y


modelo matemático

3.- Definir las restricciones que posee el problema o modelo que se está construyendo.

En el ejemplo era respetar la disponibilidad de piezas para la fabricación de sillas y mesas.

2x+2y 8 (piezas pequeñas)

x+2y 6 (piezas grandes)


Modelo General de Programación Lineal

MIN/MAX z = c1x1 + c2x2 + ... + cnxn

s.a.a11x1 + a12x2 +... + a1nxn b1

a21x1 + a22x2 +... + a2nxn = b2

a31x1 + a32x2 +... + a3nxn b3

...am1x1 + am2x2 +... + amnxn bm

xi 0 con i:1.. n

Se utilizará el siguiente modelo de programación lineal (PPL)


Propiedades de los PPL’s

Algunas propiedades básicas que se asumen en la formulación de PPL’s:

Linealidad. Divisibilidad. No presencia de incertidumbre. No negatividad.


Propiedades de los PPL’s

Linealidad.

La función objetivo y las restricciones son lineales (exponente 1). Lo que tiene una serie de implicancias.

Divisibilidad.

Las variables de decisión pueden tomar valores fraccionarios.

No presencia de incertidumbre.

Los parámetros son conocidos con certeza.

No negatividad.

Las variables de decisión son 0.


Ejemplos de Modelamiento de PPL’s

a) Problema de la dieta.

El problema consiste en determinar una dieta a partir de un conjunto dado de alimentos, de manera eficiente (bajo costo), de modo de satisfacer ciertos requerimientos nutricionales.

Supongamos que se tiene la siguiente información:Leche(Gl)

Legumbre(1 porción)

Naranjas(unid.)

Necesidad nutricional

Niacina (mg) 3.2 4.9 0.8 13Tianina (mg) 1.12 1.3 .19 1.5Vit. C (mg) 32.0 0 93.0 45Costo (U$) 2 0.2 0.25



Variables de decisión:

x: Galones de leche utilizados en la dieta.y: Porciones de legumbre utilizados en la dieta.z: Unidades de naranjas utilizados en la dieta.

Función objetivo:

Minimizar el costo total de la dieta, dado por

F=2x+0.2y+0.25z



Restricciones del problema:

3.2 x + 4.9 y + 0.8 z 13 (Req. de Niacina)1.12x + 1.3 y + 0.19 z 1.5(Req. de Tiamina)32.0x + 93.0 z 45 (Req. de Vitamina C)

x, y, z 0



b) Problema de dimensionamiento de lotes (de producción).

El problema consiste en hallar una política óptima de producción para satisfacer demandas fluctuantes en el tiempo, de modo de minimizar costos de producción e inventario, considerando la disponibilidad de diversos recursos escasos. Se supone que la demanda de cada producto es distinta en cada período de tiempo.

Supongamos que una fábrica puede elaborar hasta 150 unidades en cada uno de los 4 períodos y se tiene la siguiente información:

PeríodosDemanda

(Unid.)Costo Prod.(U$/Unid.)

Costo Inventario(U$/Unid.)

1 130 6 22 80 4 13 125 8 2.54 195 9 3



Suspuestos:

•Existe un inventario inicial de 15 unidades.•No se acepta demanda pendiente o faltante (se debe

satisfacer la demanda)


Cuánto se produce y cuánto queda en inventario.

xi: número de unidades elaboradas en el período i.Ii: número de unidades en inventario al final del período i.



Función objetivo:

Minimizar los costos de producción y el costo de mantención en inventario.

F= 6 x1 + 4 x2 + 8 x3 + 9 x4 + 2 I1 + I2 + 2.5 I3 + 3 I4

I4 en la sol. óptima va a ser cero, así que podría no incluirse. Sin embargo conviene dejarla, sobretodo en problemas que requieran un stock de seguridad.


Restricción de cota.

xi 150 (capacidad de producción)



Restricciones de demanda.

I0 = 15x1 + I0 - I1 = 130 (Período 1)x2 + I1 - I2 = 80 (Período 2)x3 + I2 - I3 = 125 (Período 3)x4 + I3 - I4 = 195 (Período 4)

Restricción de no negatividad.

xi 0



b) Problema de transporte.

El problema consiste en decidir cuántas unidades trasladar desde ciertos puntos de origen (plantas, ciudades, etc.) a ciertos puntos de destino (centros de distribución, ciudades, etc.), de modo de minimizar los costos de transporte, dada la oferta y demanda en dichos puntos.

Supongamos que una empresa posee 2 plantas que elaboran un determinado producto en cantidades de 250 y 450 unidades respectivamente. Dichas unidades deben ser trasladadas a 3 centros de distribución, con demandas de 200, 200, y 250 unidades respectivamente. Los costos unitarios de transporte son:



C.D. 1($/Unid.)

C.D. 2($/Unid.)

C.D. 3($/Unid.)

Planta 1 21 25 15Planta 2 28 13 19

Planta 1

Planta 2

C.D. 1

C.D. 1

C.D. 1

21

28

25

13

15

19

x11

x12x13

x 21

x22

x23




xij: unidades transportadas desde la planta i hasta el centro de distribución j.(con i:1,2 y j:1,2,3)

Función objetivo:

Minimizar el costo de transporte.

F= 21 x11 + 25 x12 + 15 x13 + 28 x21 + 13 x22 + 19 x23

Restricciones del problema:Restricción de no negatividad.

xi 0



Restricciones de demanda.

x11 + x21 = 200 (C.D. 1)x12 + x22 = 200 (C.D. 2)x13 + xI23 = 250 (C.D. 3)

Restricciones de oferta.

x11 + x12 + x13 250 (Planta 1)x21 + x22 + x23 450 (Planta 2)

Las variables de decisión deben aceptar soluciones reales. Sin embargo, en este problema si los parámetros de oferta y demanda son enteros, entonces la solución óptima también resulta entera.



d) Problema de selección de procesos y elaboración de productos.

Consideremos un problema que consiste en la elaboración de 3 productos, que pueden ser elaborados de maneras distintas, haciendo uso de ciertas máquinas y ciertas capacidades máximas de utilización. Los parámetros del modelo son:

Prod. 1 Prod. 2 Prod. 3Cap. Máx.

(hrs.)ab a b

Máq. A 2 0 2 3

2

2 100Máq. B 0 4 7 1 200

250Máq. C 6 5 1 5 9



El problema consiste en determinar cuántas unidades elaborar de cada producto, en cada proceso, considerando beneficios netos de U$4, U$3 y U$6 para los productos 1, 2, y 3 respectivamente. Se supone que todo lo que se fabrica se va a vender.


x1a: unidades elaboradas del producto 1 en el proceso a.

x1b: unidades elaboradas del producto 1 en el proceso b.

x2 : unidades elaboradas del producto 2.x3a: unidades elaboradas del producto 3 en el proceso

a.x3b: unidades elaboradas del producto 3 en el proceso

b.



Función objetivo:

Maximizar los beneficios totales.

F= 4( x1a + x1b ) + 3 x2 + 6 ( x3a + x3b )


Restricciones de capacidad máxima.

2 x1a + 2 x2 + 3 x3a + 2 x3b 100(Máq. A)

4 x1b + 7 x2 + 2 x3a + x3b 200(Máq. B)

6 x1a + 5 x1b + x2 + 5 x3a + 9 x3b 100(Máq. C)

x1a , x1b , x2 , x3a , x3b 0



e) Planificación de turnos.

Una aerolínea tiene abierta una oficina de reservas telefónicas las 24 hrs. del día, de lunes a viernes, y el número de agentes necesarios en cada uno de los siguientes horarios son:

Períodos Nº requerido de agentes

12 am - 4 am 114 am - 8 am 15

8 am - 12 pm 3112 pm - 4 pm 174 pm - 8 pm 25

8 pm - 12 am 19



Las personas contratadas deben hacer turnos de 8 horas consecutivas y la empresa desea conocer el mínimo número de turnos requeridos para cada período.


xi: Nº de turnos requeridos al inicio del período i.

Función objetivo:

Minimizar los turnos requeridos.

F= x1 + x2 + x3 + x4 + x5 + x6




x1 + x2 15x2 + x3 31x3 + x4 17x4 + x5 25x5 + x6 19x6 + x1 11

xi 0 (y entero)

Documents

EII-405 Investigación de operaciones1 Programación Lineal La programación lineal es el área de la IO que se ocupa de problemas en donde el modelo matemático