Programación lineal entera PDF

Preview

Summary

Download Programación lineal entera PDF

Description

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera

Métodos Cuantitativos para la Toma de Decisiones 1ª parte (2º trimestre)

Programación Lineal Entera

1

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera 2

Casos Especiales ► Modelo

de Transportes ► Modelo de Asignación ► Modelo de Transbordo

Clase anterior

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera 3

Programación Lineal Entera ► Programación

Lineal Entera: Conceptos

básicos ► Modelos de Programación Lineal Entera ► Modelos de Localización ► Uso de Excel para resolver problemas de Programación Lineal Entera

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera

Programación Lineal Entera ► Programación

Lineal Entera

 Extensión de la Programación Lineal  Modelos de PL • Las variables de decisión son continuas.

 Modelos de PLE

– Algunas o todas las variables son enteras

• Programación Entera Pura – Todas las variables son enteras

• Programación Entera Mixta – Algunas variables son enteras

• Programación Lineal Binaria – “Hacer o no hacer” – Acciones binarias 4

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera 5

Programación Lineal Entera ►Ejemplo Max Z =X1+ 1,4X2 s.a. X1 + 0,5X2 6 0,5X1 + X2  5,5 X1 + X2  6,8 1,4X1 + X2  9 X1, X2 enteras X1, X2 ≥ 0

6

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera

7

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera

Valor óptimo (lineal): Z=8,4

Solución óptima (lineal): X1=2,6 X2=4,2

8

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera

Las soluciones enteras son los puntos en la región de soluciones factibles

9

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera

Valor óptimo (entera): Z=8

Solución óptima (entera): X1=1 X2=5

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera

Algoritmo de Bifurcación y Acotamiento ► Branch-and-Bound

Algorithm

 1. Obtener una solución inicial del problema relajado (Algoritmo Simplex) • Si las variables especificadas como enteras tienen valores enteros: – Solución Óptima

• En caso contrario: – Aplicar Algoritmo de Bifurcación y Acotamiento (ABA)

10

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera

Algoritmo de Bifurcación y Acotamiento ► En

cada iteración: • Escoger una variable que presenta una solución noentera. • Dividir el problema en dos sub-problemas, añadiendo en cada uno de ellos una nueva restricción: – acotar la variable por su valor entero superior – acotar la variable por su valor inferior

11

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera

Algoritmo de Bifurcación y Acotamiento ► En

• Método Simplex • Se verifica si la solución es entera – Si, solución óptima para sub-problema. – Caso contrario, se vuelve a bifurcar el sub-problema.

►

12

cada sub-problema:

El proceso se repite en todas las ramificaciones del árbol, hasta obtener solución óptima.

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera 13

Programación Lineal Entera ►Ejemplo

1

Max Z =X1+ 1,4X2 s.a. X1 + 0,5X2 6 0,5X1 + X2  5,5 X1 + X2  6,8 1,4X1 + X2  9 X1, X2 enteras X1, X2 ≥ 0

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera

Programación Lineal Entera ► Ejemplo

1: problema P0: Relajación lineal

Max Z =X1+ 1,4X2 s.a. X1 + 0,5X2 6 0,5X1 + X2  5,5 X1 + X2  6,8 1,4X1 + X2  9 X1, X2 ≥ 0

14

15

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera

P0 Z = 8,5; X1 = 2,6 X2 = 4,2 X2

4,2

P0

2,6 X1

16

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera P1

P0 + X1  3

P2

P0 Z = 8,5; X1 = 2,6 X2 = 4,2

P0 + X1  2

X2

4,2

P0

2,6 X1

17

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera

Sub-problema P1

Restricción X1≤2

Solución: X1=2 X2=4,5

18

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera

Sub-problema P2

Restricción X1≥3

Solución: X1=3 X2=3,8

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera 19

X2

P0

4,2

P0 Z = 8,5; X1 = 2,6 X2 = 4,2

2,6

X2 P1

P2

P0 + X1  2

P0 + X1  3

Z1 = 8,3 X1 = 2 X2 = 4,5

Z2 = 8,3 X1 = 3 X2 = 3,8

X1

X2

P1

4,5

P2

3,8

2

X1

3

X1

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera

X2 4,2

P0 Z = 8,5; X1 = 2,6 X2 = 4,2

2,6

X2 P1

P2

P0 + X1  2

P0 + X1  3

Z1 = 8,3 X1 = 2 X2 = 4,5

P11

P12

P1 + X2  4

P1 + X2  5

20

P0

Z2 = 8,3 X1 = 3 X2 = 3,8

X1

X2

P1

4,5

P2

3,8

2

X1

3

X1

21

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera

Sub-problema P11

Restricción X2≤ 4

Solución Entera: X1=2 X2=4

22

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera

Sub-problema P12

Restricción X2≥ 5

Solución Entera: X1=1 X2=5

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera

X2 4,2

P0 Z = 8,5; X1 = 2,6 X2 = 4,2

2,6

X2 P1

P2

P0 + X1  2

P0 + X1  3

Z1 = 8,3 X1 = 2 X2 = 4,5

P11

P12

P1 + X2  4

P1 + X2  5

Z11 = 7,6 X1 = 2 X2 = 4 Descartado Z12 < Z11

23

P0

X2

P1

4,5

Z2 = 8,3 X1 = 3 X2 = 3,8

3

X1

X2

P11

P12 5

4

Z12 = 8,0 X1 = 1 X2 = 5 2

P2

3,8

2

X2

X1

X1

1

X1

X1

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera

X2 4,2

P0 Z = 8,5; X1 = 2,6 X2 = 4,2

2,6

X2 P1

P2

P0 + X1  2

P0 + X1  3

Z1 = 8,3 X1 = 2 X2 = 4,5

Z2 = 8,3 X1 = 3 X2 = 3,8

P12

P21

P22

P1 + X2  4

P1 + X2  5

P2 + X2  3

P1 + X2  4

Z11 = 7,6 X1 = 2 X2 = 4 Descartado Z12 < Z11

Z12 = 8,0 X1 = 1 X2 = 5

3

X1

X2

P11

P12 5

4

2

P2

3,8

2

X2

X1

X2

P1

4,5

P11

24

P0

X1

1

X1

X1

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera

Algoritmo de Bifurcación y Acotamiento ► Problemas

de maximización

 Valor óptimo: Zmax(P) ≤ Zmax(P0)  P0 es la relajación lineal de P  Para los sub-problemas Pi: Zmax(Pi) ≤ Zmax(P0) • Si una solución entera de un sub-problema Pi tiene valor óptimo ≥ que el valor óptimo de cualquier sub-problema en otra rama del árbol, ya no hace falta ramificar este última rama.

25

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera

X2 4,2

P0 Z = 8,5; X1 = 2,6 X2 = 4,2

2,6

X2 P2

P0 + X1  2

P0 + X1  3

Z1 = 8,3 X1 = 2 X2 = 4,5

Z2 = 8,3 X1 = 3 X2 = 3,8

P11

P12

P21

P22

P1 + X2  4

P1 + X2  5

P2 + X2  3

P1 + X2  4

Z12 = 8,0 X1 = 1 X2 = 5

Descartado Óptimo Z12 < Z11

Z21 = 8,0 X1 = 3,8 X2 = 3

X1

X2

P1

4,5

P1

Z11 = 7,6 X1 = 2 X2 = 4

26

P0

Descartado Descartado No se consigue Sol. no factible solución con variables enteras mejor a P12 bajando

3,8

2

X2

P2

X2

P11

3

X1

X2

P12

P21

X2

X1

P22

5

4

No factible

3 2

X1

1

X1

3,8 X1

X1

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera

Algoritmo de Bifurcación y Acotamiento ►

Resumen (problemas de maximización)  Resolver la relajación lineal del problema P: P0. • Si la solución es entera, entonces es la óptima. • Si la solución NO es entera, – Escoger cualquier variable que tenga un valor no-entero. – Dividir el problema en dos sub-problemas en base en los valores enteros. – Solucionar los sub-problemas en cada rama. • Si solución no factible: terminar la rama. • Si la solución es factible pero no entera, volver a ramificar.

(solo si el valor de la función objetivo es mayor que el valor obtenido hasta entonces por una solución entera en otras ramas)

• Si la solución es entera, no ramificar. Si es superior o igual a los valores en todas las ramas abiertas, es la solución óptima

– Examinar todas las ramas no terminadas 27

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera 28

Algoritmo de Bifurcación y Acotamiento ► Un

nodo o subproblema se agota en las siguientes situaciones: 1. Se alcanza una solución entera, 2. El problema es infactible, 3. Se obtiene una solución con variables NO enteras pero no es necesario continuar dado que ésta no es mejor (en términos de valor de la función objetivo) que una solución entera que se ha alcanzado previamente.

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera

An Example Minimization Problem Z*=355.8 x = (1.2, 2.6, 3.2, 2.8) X1≤ 1 Z1*=364.1 x = (1, 2.8, 3.2, 2.4) X2≤ 2

Z2*=∞ Infeasible X2≥ 3

Z11*=375.2 x = (1, 2, 3.5, 3.1) X3≤ 3

Z12*=384.1 x = (1, 3, 4.1, 2.2) X3≥ 4

Z112*=378.1 x = (1, 2, 4, 1.2)

Z111*=380 x = (1, 2, 3, 4) X4≤ 1

29

X1≥ 2

Z1121*=381 x = (1, 2, 4, 0)

X4≥ 2 Z1122*=382.1 x = (1, 2, 4, 3.3)

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera 30

Programación Lineal Binaria ►

Quemo Chemical Company está considerando tres posibles proyecto de mejora para su planta:  Un nuevo convertidor catalítico  Un nuevo programa de ordenador para controlar las operaciones  La expansión del almacén

►

Nos es posible invertir en los 3…

►

¿En cuál se debe invertir de forma que se maximice el valor actual neto de los proyectos emprendidos?

Ejemplo adaptado del libro de Render, Stair, Hanna (2006).

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera

Programación Lineal Binaria  Datos de Quemo Chemical Company PROJECT

NET PRESENT VALUE

YEAR 1

YEAR 2

Catalytic Converter

$25,000

$8,000

$7,000

Software

$18,000

$6,000

$4,000

Warehouse expansion

$32,000

$12,000

$8,000

$20,000

$16,000

Available funds

►

Modelo básico Maximizar el valor actual neto de los proyectos emprendidos sujeto a

31

Fondos totales utilizados en el año 1 ≤ $20,000 Fondos totales utilizados en el año 2 ≤ $16,000

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera

Programación Lineal Binaria  Variables de decisión

X1 = X2 = X3 = ►

Modelo de programación lineal binaria Maximizar NPV = Sujeto a

32

1 si el proyecto del convertidor catalítico recibe fondos 0 de lo contrario 1 si el proyecto de software recibe fondos 0 de lo contrario 1 si el proyecto de expansión del almacén recibe fondos 0 de lo contrario

25,000X1 + 18,000X2 + 32,000X3 8,000X1 + 6,000X2 + 12,000X3 ≤ 20,000 7,000X1 + 4,000X2 + 8,000X3 ≤ 16,000 X1, X2, X3 = 0 or 1

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera

Programación Lineal Binaria Problema P0: relajación lineal Maximizar NPV = 25,000X1 + 18,000X2 + 32,000X3 Sujeto a 8,000X1 + 6,000X2 + 12,000X3 ≤ 20,000 7,000X1 + 4,000X2 + 8,000X3 ≤ 16,000 0≤X 1, X2, X3 ≤ 1 NET PRESENT VALUE $25,000 $18,000 $32,000

PROJECT Catalytic Converter Software Warehouse expansion Available funds Variables Catalytic Converter Software Warehouse expansion

1 1 0.5

Restricciones 20000 15000 Función Objetivo 33

59000

$20,000 $16,000

YEAR 1 $8,000 $6,000 $12,000 $20,000

YEAR 2 $7,000 $4,000 $8,000 $16,000

34

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera

Problema P0; Solución X1= 1, X2=1, X3= 0,5 Z=59000

X3= 1

Programación Lineal Binaria

X3= 0

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera

Programación Lineal Binaria ► Sub

problema P1 NET PRESENT VALUE $25,000 $18,000 $32,000

PROJECT Catalytic Converter Software Warehouse expansion Available funds Variables Catalytic Converter Software Warehouse expansion

1 1 0

Restricciones 14000 11000 Función Objetivo 43000

35

$20,000 $16,000

YEAR 1 $8,000 $6,000 $12,000 $20,000

YEAR 2 $7,000 $4,000 $8,000 $16,000

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera

Programación Lineal Binaria ► Sub

problema P2 NET PRESENT VALUE $25,000 $18,000 $32,000

PROJECT Catalytic Converter Software Warehouse expansion Available funds Variables Catalytic Converter Software Warehouse expansion

1 0 1

Restricciones 20000 15000 Función Objetivo 57000

36

$20,000 $16,000

YEAR 1 $8,000 $6,000 $12,000 $20,000

YEAR 2 $7,000 $4,000 $8,000 $16,000

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera 37

Programación Lineal Binaria Problema P0; Solución X1= 1, X2=1, X3= 0,5 Z=59000 X3= 0 Problema P1:P0 + (X3= 0) Solución binaria X1= 1, X2=1, X3= 0 Z=43000

X3= 1 Problema P2:P0 + (X3= 1) Solución binaria X1= 1, X2=0, X3= 1 Z=57000

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera 38

Programación Lineal Binaria ► La

solución óptima es invertir en los proyectos:

 Un nuevo convertidor catalítico  La expansión del almacén

► Con

un valor actual neto de 57000.

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera 39

Programación Lineal Entera ►Resolver

el Ejemplo 2 con el método de bifurcación y acotamiento Max Z =220X1+ 80X2 s.a. 8X1 + 2X2  21 2X1 - X2  4 -X1 + 2X2  4 X1, X2 enteras X1, X2 ≥ 0

40

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera

Ejemplo 2

41

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera

Ejemplo 2

42

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera

Ejemplo 2

43

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera

Ejemplo 2

44

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera

Ejemplo 2

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera

Modelos de Localización ► Modelos

mas sofisticados de Investigación Operativa  Modelos de p-mediana  Modelos de cobertura  Modelos de localización con capacidades

45

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera

Modelos de p-mediana ► Localización

de p centros/locales para servir una determinada población.

► ¿Cuál

es la mejor ubicación de estos centros?

 Minimizando costes de transporte.  Minimización de tiempos/distancias de traslado.  Etc.

46

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera

Modelos de p-mediana ► Ejemplo:

problema

de

localización

de

p

servicios.  Considera que tenemos de ubicar 3 escuelas para servir 9 distritos.  Todos los distritos deben estar asignados a un escuela.  Los tiempos de traslado están indicados en la tabla siguiente.

47

Métodos Cuantitativos para la Toma de Decisiones (1) Tema 5. Programación Lineal Entera

Modelo de p-mediana ► Ejemplo:

problema de localización de p servicios. Distrito

Tiempo entre distritos 1 2 3 1 0 5 4 2 5 0 12 3 4 12 0 4 2 10 11 5 1 8 2 6 7 4 2 7 2 2 7 8 9 1 10 9 1 9 12

► ¿Cuál

4 2 10 11 0 2 7 1 1 14

5 1 8 2 2 0 6 4 4 5

6 7 4 2 7 6 0 4 3 2

7 2 2 7 1 4 4 0 8 5

8 9 1 10 1 4 3 8 0 9

9 1 9 12 14 5 2 5 9 0

es la mejor ubicación de los 3 centros...