EII405 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

EII405 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.


2

Problema tipoUn gerente de producción debe decidir cuantos bolsos y mochilas fabricar, para obtener la máxima ganancia.

Se sabe que por cada mil bolsos producidos se obtiene una ganacia de $ 3 millones, y por cada mil mochilas producidas se obtiene una ganacia de $ 5 millones.

Para fabricar mil bolsos se necesita 1 pieza de tela roja y 3 piezas de tela azul, y para fabricar mil mochilas se requieren 2 piezas de tela verde y 2 piezas de tela azul.

Además, se sabe que se dispone de 4 piezas de tela roja, 12 piezas de tela verde, y 18 piezas de tela azul.


3

Problema tipoResumiendo, se tiene la siguiente situación:

Bolsos Mochilas Cant. Disp.

Consumo (1)

Tela Roja 1 4

Tela Verde 2 12

Tela Azul 3 2 18

Ganancia (2) 3 5

(1) Consumo en piezas de tela por mil unidades producidas

(2) Ganacia en millones de $ por cada mil unidades


4

Modelo matemáticoTiene 3 componentes principales:

1.- Definir las variables de decisión

X : miles de bolsos producidosY : miles de mochilas producidas

2.- Definir la Función Objetivo del problema

Maximizar Ganancia (en MM$):

Max Z = 3 x + 5 y


5

Modelo matemático3.- Definir las restricciones que posee el problema que se

está modelando

En el ejemplo, el consumo de tela necesario para producir los bolsos y mochilas debe ser menor o igual que la cantidad de tela disponible:

Tela Roja X 4

Tela Verde 2 Y 12

Tela Azul 3 X + 2 Y 18

4.- Además, las cantidades a producir de bolsos y mochilas deben ser mayores o iguales que cero ( X 0 e

Y 0)


6

Modelo matemáticoResumiendo se tiene el siguiente problema:

MAX Z = 3 x1 + 5 x2

s.a. x1 4

2 x2 12

3 x1 + 2 x2 18

x1 , x2 0

En donde X e Y se han reemplazado por X1 y X2


7

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

En terminos generales, se utilizará el siguiente modelo de programación lineal


8

Componentes del modelo

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

en donde :

xj : variable de decisión

cj : contribución de xj a la función objetivo

con j = 1 hasta n (cant. de variables de decisión)

1. Funcion objetivo (F.O.):


9


a11x1 + a12x2 +... + a1nxn b1

a21x1 + a22x2 +... + a2nxn b2

a31x1 + a32x2 +... + a3nxn b3

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

en donde :

a ij : consumo del recurso i por la actividad jbi : disponibilidad del recurso i

con i = 1 hasta m (cant. de recursos)

2. Restricciones:


10


Corresponden a los “datos” del problema, cuyos valores son conocidos.

Los valores de los parámetros permiten que el modelo represente las condiciones del problema real.

Los parámetros son:

cj aij bi

que ya han sido explicados

3. Parámetros:


11

Propiedades de los PPL’s

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

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


12

Propiedades de los PPL’s

Linealidad.

La función objetivo y las restricciones son lineales (exponente 1). Además, no hay multiplicación entre variables.

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.


13

Resolución Gráfica de PPL

Cuando el problema se transforma en un modelo matemático con 2 variables de decisión, entonces es posible resolver gráficamente el problema.


14

Método gráfico

• Graficar la región de soluciones factibles.

• Obtener los puntos extremos de la región de soluciones factibles.

• Evaluar dichos puntos en la F.O. El óptimo estará en aquel punto que entregue una solución mayor o menor, según corresponda.


15

EjemploDado el problema anterior:

MAX Z = 3 x1 + 5 x2

s.a. x1 4

2 x2 12

3 x1 + 2 x2 18

x1 , x2 0


16

EjemploSe dibuja la región de puntos factibles. Para ello se grafican las restricciones.

62 4

6

4

2

x1

x2

x2 = 6

x1 = 4

3 x1 + 2 x2 = 18

Región Factible


17

EjemploDeterminada la región factible, se evalúan los puntos factibles en la F.O. y el de mejor valor es el punto óptimo.

62 4

6

4

2

x1

x2

(0,6)

Región Factible

(2,6)

(4,3)

(4,0)

(0,0)

Pto. Z(0,0) 0(0,6) 30(2,6

)36

(4,3) 27(4,0) 12


18

EjemploOtra forma posible, que evita tener que evaluar todos los punto es calculando el gradiente de la F.O y trazando sus curvas de nivel.

62 4

6

4

2

x1

x2

3 x1 + 5 x2 = 36

3 x1 + 5 x2 = 20

3 x1 + 5 x2 = 10


19

EjemploCon la región de puntos factibles dibujada, se trazan las curvas de nivel de la F.O.

62 4

6

4

2

x1

x2

3 x1 + 5 x2 = 36

3 x1 + 5 x2 = 20

3 x1 + 5 x2 = 10

Z=(3,5)


20

Importante

• Cada vez que el dominio (o región factible) sea cerrado y acotado, el problema tiene solución.

• De existir una solución, siempre se encontrará en un vértice.

• Cuando se está minimizando, las curvas de nivel se desplazan en sentido contrario a la maximización.


21

Múltibles solucionesSupongamos el siguiente ejemplo:

MAX Z = 6 x1 + 4 x2

s.a. x1 4

2 x2 12

3 x1 + 2 x2 18

x1 , x2 0


22

Múltibles solucionesEn este caso, al trazar las curvas de nivel vemos que son paralelas a una de las restricciones. Es decir, la pendiente de la F.O. es igual a la de una restricción.

Z=(6,4)

62 4

6

4

2

x1

x2

3 x1 + 2 x2 = 18

3 x1 + 2 x2 = k

Múltiples soluciones óptimas.


23

Región no acotada

Supongamos este otro ejemplo:

MAX Z = 5 x1 + 12 x2

s.a. x1 5

2 x1 - x2 2

x1 , x2 0


24

Región no acotadaEn este caso, al trazar las curvas de nivel vemos quepueden crecer infinitamente en la dirección de la gradiente. La región factible (o dominio) no es acotado.

1 5

6

4

2

x1

x2

Z=(5,12)


25

Región infactible

Dado el ejemplo:

MAX Z = 3 x1 + 5 x2

s.a. x1 5

x2 4

3 x1 + 2 x2 18

x1 , x2 0


26

Región infactiblePuede ser que la intersección de todas las restricciones de vacía. En este caso no existe región factible y el problema es infactible.

5

4

x1

x2

Documents

EII405 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