Matematicas

Clase # 18

Puede parecer que los problemas de Programación Entera son relativamente fáciles de resolver.

Solución de Problemas de Programación entera.
Por lo general resulta mucho más sencillo resolver los problemas de programación lineal que los de programación entera.
18-1 18-2

Una primera idea para resolver un problema de P.E podría ser resolver el problema lineal (llamadarelajación PL) del problema entero, y redondear la solución.

Ejemplo. (peligro 1) Max Z = X2 -X1 + X2 ≤ 1/2

Hay que tener mucho cuidado pues al hacer esto existen algunos peligros.

X1 + X2 ≥ 7/2 X1 , X2 ≥ 0

Veamos un ejemplo.
18-3

X1 , X2 enteros positivos
18-4

5

X2
X1 + X2 = 7/2 -X1 + X2 = 1/2

La función objetivo es Z = X2 .. Si resolviéramos el P.L con variables que nonecesariamente fueran enteras, hallaríamos el óptimo gráficamente en el punto ( 3/2 , 2). Redondeando obtendríamos o bien el punto (1,2) o el punto (2,2)
X1

4

3

2

1

0

1

2

3

4

5

Veamos
18-5 18-6

1

5

X2 óptimo de la relajación P.L

Ejemplo. (peligro 2) Max Z = X1 + 5 X 2 X1 + 10X2 ≤ 20 X1 X1 , X2 ≥ 0 X1 , X2 enteros positivos
18-7 18-8

4

3

2

Si seredondea, las soluciones que se obtienen no son factibles

≤ 2

1

X1
0 1 2 3 4 5

X2 X1+10X2 = 20 X2 = 2 2

3

El óptimo de la relajación P.L es el punto ( 2, 9/5 ) , que redondeado en la dirección factible sería (2,2) . Sin embargo esta solución no es la óptima del problema de programación entera. (2,2) no es un punto factible

1

0

1

2

3

X2
18-9

Veamos
18-10X2

Se han propuesto muchos métodos para resolver los problemas de P.E (algoritmos heurísticos). El más utilizado es el método de ramificación y acotamiento (Branch and Bounds)

3

óptimo del problema real

óptimo de la relajación P.L

2

Antes de explicar cómo funciona este método es importante anotar que: Si se resuelve la relajación P.L de una P.E pura y obtiene una solución en lacual todas las variables son números enteros, entonces la solución óptima de la relajación P.L será también la solución óptima del P.E.
18-12

1

0

1

2

3

X2
18-11

2

Ejemplo.

10 X2 9 8 7

Max Z = 8X1 +5X2 X1 + X2 ≤6

9 X1 + 5X2 = 45

6 5 4 3 2 1

9X1 + 5X2 ≤ 45 X1 , X2 ≥ 0 X1 , X2 enteros no negativos
Veamos

X1 + X2 = 6
X1 1 2 3 4 5 6 7

18-13

18-14El método de ramificación y acotamiento empieza por resolver la relajación P.L del P.E. Así entonces la relajación P.L será:
Max Z = 8X1 +5X2 X1 + X2 ≤6 ≤ 9X1 + 5X2 ≤ 45 ≤ X1 , X2 ≥ 0 ≥

10 X2 9 8 7 6 5 4 3 2 1

Relajación P.L

9 X1 + 5X2 = 45

óptimo de la relajación P.L

X1 + X2 = 6
X1 1 2 3 4 5 6 7

Veamos

18-15

Z=20

18-16

Solución óptima relajación P.L

X1 = 15/4 X2= 9/4 Z = 165/4

10 X2 9 8 7 6 5

Subproblemas 1y2 Subproblema 2

Debemos dividir la región factible de la relajación P.L

Así entonces elegimos arbitrariamente entre X1 y X2 para crear dos subproblemas
Veamos
18-17

4 3 2 1 1 2 3 4 5

Subproblema 1
X1 6 7
18-18

3

10 X2 9

Subproblemas 1y2 Subproblema 2

Así entonces :
Subproblema 1
Max Z = 8X1 +5X2 X1 + X2 ≤6 ≤ 9X1 +5X2 ≤ 45 ≤ X1 ≥4 ≥ X1 , X2 ≥ 0 ≥

8 7 6 5 4 3 2 1

Subproblema 2
Max Z = 8X1 +5X2 X1 + X2 ≤6 ≤ 9X1 + 5X2 ≤ 45 ≤ X1 ≤ 3 ≤ X1 , X2 ≥ 0 ≥

óptimo del subproblema 1

Subproblema 1
X1 1 2 3 4 5 6 7

Veamos

18-19

Z=20

18-20

Solución óptima subproblema 1

X1 = 4 X2 = 9/5 Z = 41 X1 = 3 X2 = 3 Z = 39

Relajación P.L X1 = 15/4 X2 = 9/4 Z = 165/4
X1 ≥ 4 ≥ X1 ≤ 3 ≤

Soluciónóptima subproblema 2 Debemos dividir la región factible del subproblema 1

Recordemos que esta elección es arbitraria. Escogemos X2 para hacer la división

Subproblema 1 X1 = 4 X2 = 9/5 Z = 41 Resumiendo 18-21

Subproblema 2 X1 = 3 X2 = 3 Z = 39
18-22

10 X2 9

Subproblemas 3y4

Así entonces :
Subproblema 3
Max Z = 8X1 +5X2 X1 + X2 ≤6 ≤ 9X1 + 5X2 ≤ 45 ≤ X1 ≥4 ≥ X2 ≥ 2 ≥ X1 , X2 ≥ 0...