IIND 2103: Principios de Optimización

Introducción a programación entera

Juliana Gómez Camilo Gómez Jorge Huertas

Departamento de Ingeniería Industrial

Centro para la Optimización y la Probabilidad Aplicada
(http://copa.uniandes.edu.co)
Método Simplex

min cT x
s.a.
Ax  b
x0

http://news-service.stanford.edu

2
Clasificación de los problemas de
optimización

Nivel 1: Problema general Problema

Nivel 2: Clasificación del
objetivo Único Objetivo Multiobjetivo

Nivel 3: Clasificación del

problema No restringido Restringido

Nivel 4: Clasificación de
las variables Continuas Enteras/Discretas Mixtas

Nivel 5: Clasificación de
las funciones Lineales No lineales Otros

3
Clasificación de los problemas de
optimización

Nivel 1: Problema general Problema

Nivel 2: Clasificación del
objetivo Único Objetivo Multiobjetivo

Nivel 3: Clasificación del

problema No restringido Restringido

Nivel 4: Clasificación de
las variables Continuas Enteras/Discretas Mixtas

Nivel 5: Clasificación de
las funciones Lineales No lineales Otros

4
Clasificación de los problemas de
optimización

Nivel 1: Problema general Problema

Nivel 2: Clasificación del
objetivo Único Objetivo Multiobjetivo

Nivel 3: Clasificación del

problema No restringido Restringido

Nivel 4: Clasificación de
las variables Continuas Enteras/Discretas Mixtas

Nivel 5: Clasificación de
las funciones Lineales No lineales Otros

5
Ejemplo

max z  1x1  0.64 x2

s.a.
50 x1  31x2  250
3x1  2 x2  4
x1 , x2  0

6
Ejemplo

max z  1x1  0.64 x2

s.a.
50 x1  31x2  250
3x1  2 x2  4

x1 , x2  Z  {0}
?

7
Ejemplo

max z  1x1  0.64 x2

s.a.
50 x1  31x2  250
3x1  2 x2  4
x1 , x2  Z   {0}

8
Ejemplo

max z  1x1  0.64 x2

s.a.
50 x1  31x2  250
3x1  2 x2  4
x1 , x2  0

9
Ejemplo

max z  1x1  0.64 x2

s.a.

50 x1  31x2  250
3x1  2 x2  4
x1 , x2  Z   {0}

10
Estrategia de solución

max z  4 x1  x2
s.a.
7 x1  2 x2  14
x2  3
2 x1  2 x2  3
x1 , x2  Z   {0}

11
Estrategia de solución

max z  4 x1  x2 z*  8.42
xT  2.85 3
s.a.
7 x1  2 x2  14
x2  3
2 x1  2 x2  3
x1 , x2  0
1

12
Estrategia de solución

z*  8.42
1 xT  2.85 3

13
Estrategia de solución

max z  4 x1  x2 z*  8.42
xT  2.85 3
s.a.
7 x1  2 x2  14
x2  3
2 x1  2 x2  3
x1 , x2  0

14
Branch & Bound (Ramificación y Acotamiento)

max z  4 x1  x2
s.a.
7 x1  2 x2  14
x2  3
2 x1  2 x2  3
x1  3
x1 , x2  0 2

15
Branch & Bound (Ramificación y Acotamiento)

z*  8.42
1 x1  3
xT  2.85 3

INFACTIBLE
2

16
Branch & Bound (Ramificación y Acotamiento)

max z  4 x1  x2
s.a.
7 x1  2 x2  14
x2  3
2 x1  2 x2  3
x1  2
x1 , x2  0
3

17
Branch & Bound (Ramificación y Acotamiento)

1
z*  8.42
x1  2 x1  3
xT  2.85 3

z*  7.5
3 xT  2 0.5
INFACTIBLE
2

18
Branch & Bound (Ramificación y Acotamiento)

max z  4 x1  x2
s.a.
7 x1  2 x2  14
x2  3
2 x1  2 x2  3
x1  2
x1 , x2  0
3

19
Branch & Bound (Ramificación y Acotamiento)

1
z*  8.42
x1  2 x1  3
xT  2.85 3

3 z*  7.5
xT  2 0.5
INFACTIBLE
2

5 4

20
Branch & Bound (Ramificación y Acotamiento)

1
z*  8.42
x1  2 x1  3
xT  2.85 3

3 z*  7.5
x2  0 xT  2 0.5 x2  1
INFACTIBLE
2

5 4

21
Branch & Bound (Ramificación y Acotamiento)

max z  4 x1  x2
s.a.
7 x1  2 x2  14
x2  3
2 x1  2 x2  3
x1  2
x2  1
x1 , x2  0 4

22
Branch & Bound (Ramificación y Acotamiento)

1
z*  8.42
x1  2 x1  3
xT  2.85 3

3 z*  7.5
x2  0 xT  2 0.5 x2  1
INFACTIBLE
2

z*  7
5 xT  2 1 4

23
Branch & Bound (Ramificación y Acotamiento)

max z  4 x1  x2
s.a.
7 x1  2 x2  14
x2  3
2 x1  2 x2  3
x1  2
x2  0
x1 , x2  0 5

24
Branch & Bound (Ramificación y Acotamiento)

1
z*  8.42
x1  2 x1  3
xT  2.85 3

3 z*  7.5
x2  0 xT  2 0.5 x2  1
INFACTIBLE
2

z*  6 z*  7
5 x  1.5 0
T
xT  2 1 4

25
Branch & Bound (Ramificación y Acotamiento)

1
z*  8.42
x1  2 x1  3
xT  2.85 3

3 z*  7.5
x2  0 xT  2 0.5 x2  1
INFACTIBLE
2

z*  6 z*  7
5 x  1.5 0
T
xT  2 1 4

? ?

26
Branch & Bound (Ramificación y Acotamiento)

1
z*  8.42
x1  2 x1  3
xT  2.85 3

3 z*  7.5
x2  0 xT  2 0.5 x2  1
INFACTIBLE
2

z*  6 z*  7
5 x  1.5 0
T
xT  2 1 4

27
Branch & Bound (Ramificación y Acotamiento)

28
Branch & Bound (Ramificación y Acotamiento)

max z  8 x1  11x2  6 x3  4 x4
s.a.

5 x1  7 x2  4 x3  3x4  14
x1 , x2 , x3 , x4 {0,1}

29
Branch & Bound (Ramificación y Acotamiento)

max z  8 x1  11x2  6 x3  4 x4
s.a.
1
5 x1  7 x2  4 x3  3x4  14
0  x j  1, j  1,2,3,4

30
Branch & Bound (Ramificación y Acotamiento)

1 z*  22
xT  1 1 0.5 0

31
Branch & Bound (Ramificación y Acotamiento)

1 z*  22
xT  1 1 0.5 0

3 ? ? 2

32
Branch & Bound (Ramificación y Acotamiento)

1 z*  22
xT  1 1 0.5 0
x3  1

3 ? ? 2

33
Branch & Bound (Ramificación y Acotamiento)

max z  8 x1  11x2  6 x3  4 x4
s.a.
1
5 x1  7 x2  4 x3  3x4  14
0  x j  1, j  1,2,3,4
x3  1

34
Branch & Bound (Ramificación y Acotamiento)

1 z*  22
xT  1 1 0.5 0
x3  1

z*  21.85 2
3 ? xT  1 0.71 1 0

35
Branch & Bound (Ramificación y Acotamiento)

1 z*  22
xT  1 1 0.5 0
x3  1

z*  21.85 2
3 ? xT  1 0.71 1 0
x2  1
4
z*  21.8
5 ? xT  0.6 1 1 0

36
Branch & Bound (Ramificación y Acotamiento)

1 z*  22
xT  1 1 0.5 0
x3  1

z*  21.85 2
3 ? xT  1 0.71 1 0
x2  1
4
z*  21.8
5 ? xT  0.6 1 1 0
x1  1

7 ? INFACTIBLE 6

37
Branch & Bound (Ramificación y Acotamiento)

1 z*  22
xT  1 1 0.5 0
x3  1

z*  21.85 2
3 ? xT  1 0.71 1 0
x2  1
4
z*  21.8
5 ? x1  0 xT  0.6 1 1 0
x1  1

7 ? INFACTIBLE 6

38
Branch & Bound (Ramificación y Acotamiento)

1 z*  22
xT  1 1 0.5 0
x3  1

z*  21.85 2
3 ? xT  1 0.71 1 0
x2  1
4
z*  21.8
5 ? x1  0 xT  0.6 1 1 0
x1  1

z*  21
7 xT  0 1 1 1
INFACTIBLE 6

39
Branch & Bound (Ramificación y Acotamiento)

1 z*  22
xT  1 1 0.5 0
x3  1

z*  21.85 2
3 ? x2  0 xT  1 0.71 1 0
x2  1
4
z*  21.8
5 ? x1  0 xT  0.6 1 1 0
x1  1

z*  21
7 xT  0 1 1 1
INFACTIBLE 6

40
Branch & Bound (Ramificación y Acotamiento)

1 z*  22
xT  1 1 0.5 0
x3  1

z*  21.85 2
3 ? x2  0 xT  1 0.71 1 0
x2  1
4
z*  18 z*  21.8
5 xT  1 0 1 1 x1  0 xT  0.6 1 1 0
x1  1

z*  21
7 xT  0 1 1 1
INFACTIBLE 6

41
Branch & Bound (Ramificación y Acotamiento)

1 z*  22
xT  1 1 0.5 0
x3  1

z*  21.85 2
3 ? x2  0 xT  1 0.71 1 0
x2  1
4
z*  18 z*  21.8
5 xT  1 0 1 1 x1  0 xT  0.6 1 1 0
x1  1

z*  21
7 xT  0 1 1 1
INFACTIBLE 6

42
Branch & Bound (Ramificación y Acotamiento)

1 z*  22
xT  1 1 0.5 0
x3  0 x3  1

z*  21.85 2
3 ? x2  0 xT  1 0.71 1 0
x2  1
4
z*  18 z*  21.8
5 xT  1 0 1 1 x1  0 xT  0.6 1 1 0
x1  1

z*  21
7 xT  0 1 1 1
INFACTIBLE 6

43
Branch & Bound (Ramificación y Acotamiento)

1 z*  22
xT  1 1 0.5 0
x3  0 x3  1

z*  21.66 z*  21.85 2
3 xT  1 1 0 0.66 x2  0 xT  1 0.71 1 0
x2  1
4
z*  18 z*  21.8
5 xT  1 0 1 1 x1  0 xT  0.6 1 1 0
x1  1

z*  21
7 xT  0 1 1 1
INFACTIBLE 6

44
Branch & Bound (Ramificación y Acotamiento)

45
Complejidad
Variables Nodos Variables Nodos
2 7 31 4294967295
3 15 32 8589934591
4 31 33 17179869183
5 63 34 34359738367
6 127 35 68719476735
7 255 36 137438953471
8 511 37 274877906943
9 1023 38 549755813887
10 2047 39 1099511627775
11 4095 40 2199023255551 Si un computador procesara
12 8191 41 4398046511103
13 16383 42 8796093022207 1,000,000 nodos por segundo,
14 32767 43 17592186044415
15 65535 44 35184372088831
procesar los nodos de un problema
16 131071 45 70368744177663 con 59 variables tomaría …
17 262143 46 140737488355327
18 524287 47 281474976710655 36 559 años!
19 1048575 48 562949953421311
20 2097151 49 1125899906842620
21 4194303 50 2251799813685250
22 8388607 51 4503599627370490
23 16777215 52 9007199254740990
24 33554431 53 18014398509482000
25 67108863 54 36028797018964000
26 134217727 55 72057594037927900
27 268435455 56 144115188075856000
28 536870911 57 288230376151712000
29 1073741823 58 576460752303423000
30 2147483647 59 1152921504606850000

46
Búsqueda de una buena formulación

47