• Author / Uploaded
• Nico MV

Citation preview

14/05/2017

Unidad 2 Introducción a la programación lineal

Ing. Enrique M. Avendaño Delgado [email protected]

INTRODUCCIÓN:

No existe una metodología muy concreta acerca de como se debe modelar matemáticamente un problema y el asunto tiene mucho de intuición y arte. Se muestra un par de problemas típicos los cuales nos servirá para discutiendo un poco las dificultades que pueden presentarse y cuales son los errores mas comunes. Una forma sencilla y bastante general de ordenar el proceso de modelación, consiste en dividirlo en tres partes: 1. Definición de variables de decisión. 2. Planteamiento de las restricciones del problema.

3. Planteamiento de la función objetivo.

1

14/05/2017

DEFINICIÓN DE VARIABLES: Como primer paso para poder modelar ordenadamente un problema de optimización debemos distinguir que variables son aquellas sobre las que podemos tomar decisiones en el problema y darles un nombre, es decir, debemos darnos cuenta que variables están bajo nuestro control.

•

A veces es necesario incluir variables que si bien no podemos ejercer una decisión directa sobre ellas, nos sirven como herramienta auxiliar ya sea para plantear restricciones o para escribir nuestra función objetivo. Serian variables de decisión por ejemplo la cantidad de producto a enviar desde el centro de producción i hasta el centro de consumo j (que podríamos llamar xij), la cantidad de insumos a adquirir en el período t (que podríamos llamar yt), el numero de horas que destinaremos la máquina i a trabajar en el proceso j en el período t (que podríamos llamar ztij), etc.

PLANTEAMIENTO DE FUNCIÓN OBJETIVO: En general podemos decir que en un problema de optimización se intenta encontrar el mejor valor de algo. Es por esto que necesitamos especificar que criterio usaremos para decir que una solución es mejor que otra. Para ello deberemos especificar una función de IRn a IR en que una combinación de variables será mejor que otra si genera un mayor valor de la función en el caso de maximización y un menor valor de la función en el caso de minimización. Ejemplos típicos de funciones objetivos vienen dados por maximización de utilidades y minimización de costos, los que deben ser escritos en función de las variables del problema.

10

2

14/05/2017

PLANTEAMIENTO DE RESTRICCIONES: En un problema de optimización, intentaremos buscar combinaciones de variables de decisión que generen un mejor valor de la función objetivo, pero en la práctica nuestro problema esta limitado por un gran número de restricciones físicas, económicas, técnicas, etc. Es por esto que en el planteamiento de nuestro problema debemos especificar que limitantes tienen los valores que puedan tomar las variables de decisión. En síntesis, en esta parte debemos escribir matemáticamente las limitaciones que nos impone la naturaleza del problema.

10

EJEMPLO 1

MOCHILA

¿Qué necesitamos?

Poliester rayón tejido para mochila

Cierres

Mano de Obra

Hilo

Cierres plástico

¿Son abundantes o escasos?

3

14/05/2017

MOCHILAS

Universitario

Escolar

Poliester rayón tejido para mochila

Junior

Cierres

Mano de Obra

EJEMPLO 1

Universitario

Escolar

Una empresa de confecciones de mochilas, produce tres modelos: Universitario, Escolar y Junior; los cuales vende a 200, 155 y 130 soles c/u. Se utiliza poliester rayón tejido para mochila, 4.0 metros para el modelo Universitario, 2.5 metros para el modelo Escolar y 1.8 metros para el modelo Junior; la mano de obra utilizada para cada modelo es: 4 hr para el modelo ejecutivo, 3 hr para el modelo Escolar y 3.2 para el modelo Junior; también se utilizan cierres: 4 cierres cada uno para los modelos Universitario y Escolar y 3 cierres para el modelo Junior. Se consigue semanalmente 500 metros de Poliester, se tiene 192 hr disponibles (4 operarios, 8 hr/dia, 6 días/sem), 230 cierres. Además se sabe que se tiene que producir al menos 10 mochilas Junior. Hacer un modelo de Programación lineal entera para maximizar las ganancias y establecer el número de mochilas optimo que se debe producir.

Junior

4

14/05/2017

EJEMPLO 1 Datos:

Universitario

Producto

P. Venta

Poliéster

Horas (MO)

Cierres

M. Universitario

200

4

4

4

M. Escolar

155

2.5

3

4

M. Junior

130

1.8

3.2

3

500 mt

192 hr/sem

230 und

Demanda

>= 10

Variables: Escolar

X1 : Cantidad de Mochilas modelo Universitario producidas por semana X2 : Cantidad de Mochilas modelo Escolar producidas por semana X3 : Cantidad de Mochilas modelo Junior producidas por semana

Junior

EJEMPLO 1 Variables: X1 : Cantidad de Mochilas modelo Universitario producidas por semana X2 : Cantidad de Mochilas modelo Escolar producidas por semana X3 : Cantidad de Mochilas modelo Junior producidas por semana

Producto

Variable

P. Venta

Poliéster

Horas (MO)

Cierres

M. Universitario

x1

200

4

4

4

M. Escolar

X2

155

2.5

3

4

M. Junior

X3

130

1.8

3.2

3

500 mt

192 hr/sem

230 und

Función Objetivo: Maximizar Ganancias

FO Max Z = 200x1 + 155x2 + 130x3

Demanda

>= 10

Tener en cuenta: Se maximiza Ganancias o utilidades. Se minimiza costos

5

14/05/2017

EJEMPLO 1 X1 : Cantidad de Mochilas modelo Universitario producidas por semana X2 : Cantidad de Mochilas modelo Universitario producidas por semana X3 : Cantidad de Mochilas modelo Universitario producidas por semana

Variables:

Producto

Variable

P. Venta

Poliéster

Horas (MO)

Cierres

M. Universitario

x1

M. Escolar

X2

200

4

4

4

155

2.5

3

4

M. Junior

X3

130

1.8

3.2

3

500 mt

192 hr/sem

230 und

Demanda

>= 10

FO Max Z = 200x1 + 155x2 + 130x3 Restricciones de Recursos: Poliéster: 4x1 + 2.5x2 + 1.8x3