Optimizacion

OPTIMIZACION PARA ESTUDIANTES DE
INGENIERIA 1
Jorge Amaya A.
Departamento de Ingenier´ Matem´tica y
ıa
a
Centro de Modelamiento Matem´tico
a
Universidad de Chile

21 de octubre de 2012

1 Texto

para uso exclusivo de los estudiantes del curso MA3701-Optimizaci´n, de la Escuela
o
de Ingenier´ de la Universidad de Chile. Los comentarios son bienvenidos: jamaya@dim.uchile.cl
ıa´
Indice general
1. Matem´ticas para la Optimizaci´n
a
o

4

1.1. El problema de Optimizaci´n . . . . . . . . . . . . . . . . . . . . . . . . . .
o

4

1.2. Conjuntos convexos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.2.1. Poliedros: caracterizaci´n y propiedades . . . . . . . . . . . . . . . .
o

11

1.2.2. Puntos extremos . . . . . . . . . . . . .. . . . . . . . . . . . . . . .

13

1.2.3. Direcciones y direcciones extremas . . . . . . . . . . . . . . . . . . .

20

1.2.4. Proyecci´n sobre conjuntos convexos . . . . . . . . . . . . . . . . . .
o

24

1.2.5. Separaci´n de convexos: teoremas de Farkas y Gordan . . . . . . . . .
o

28

1.3. Funciones convexas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .33

1.3.1. Conjuntos relevantes asociados a funciones convexas . . . . . . . . . .

37

1.3.2. Funciones convexas diferenciables . . . . . . . . . . . . . . . . . . . .

39

2. Caracterizaci´n de optimalidad
o

45

2.1. Definici´n del problema de Optimizaci´n . . . . . . . . . . . . . . . . . . . .
o
o

45

2.2. Condiciones de optimalidad . . . . . . . . . . . . . . . . . . .. . . . . . . .

46

2.2.1. Optimizaci´n sin restricciones . . . . . . . . . . . . . . . . . . . . . .
o

46

2.2.2. Optimizaci´n con restricciones . . . . . . . . . . . . . . . . . . . . . .
o

48

3. Programaci´n Lineal
o

56

3.1. Introducci´n y ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
o

56

3.2. Resoluci´n de problemas de Programaci´n Lineal:algoritmo Simplex . . . .
o
o

58

1

3.2.1. Fase II del algoritmo Simplex: mejorar soluci´n en curso . . . . . . .
o

60

3.2.2. Fase I del algoritmo Simplex: obtener una soluci´n inicial b´sica factible 67
o
a
3.3. Programaci´n Lineal Entera (ramificaci´n y acotamiento) . . . . . . . . . . .
o
o
4. Dualidad en Programaci´n Lineal y Aplicaciones
o

71
76

4.1. Definici´nde dualidad y principales propiedades . . . . . . . . . . . . . . . .
o

78

4.2. Interpretaci´n econ´mica de la dualidad . . . . . . . . . . . . . . . . . . . .
o
o

83

4.3. Dual de cualquier problema lineal . . . . . . . . . . . . . . . . . . . . . . . .

85

4.4. Algoritmo Simplex-dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

85

4.5. Introducci´n alan´lisis post-optimal . . . . . . . . . . . . . . . . . . . . . .
o
a

86

4.5.1. Variaci´n en los coeficientes de la funci´n objetivo . . . . . . . . . . .
o
o

87

4.5.2. Variaci´n en el vector de recursos (o lado derecho) . . . . . . . . . . .
o

89

4.5.3. Introducci´n de una nueva actividad (o variable) . . . . . . . . . . . .
o

91

4.5.4. Introducci´n de una nueva restricci´n. . . . . . . . . . . . . . . . . .
o
o

93

5. Modelos para flujos en redes

97

5.1. Motivaci´n y descripci´n de problemas cl´sicos . . . . . . . . . . . . . . . . .
o
o
a
5.1.1. Problema de asignaci´n
o

97

. . . . . . . . . . . . . . . . . . . . . . . . . 100

5.1.2. Problema de transporte . . . . . . . . . . . . . . . . . . . . . . . . . 101
5.1.3. Problema de flujom´ximo . . . . . . . . . . . . . . . . . . . . . . . . 103
a
5.1.4. Problema de camino m´s corto . . . . . . . . . . . . . . . . . . . . . 104
a
5.2. Resoluci´n del problema de transporte . . . . . . . . . . . . . . . . . . . . . 106
o
5.2.1. Obtener una soluci´n b´sica factible inicial (Fase I) . . . . . . . . . . 106
o a
5.2.2. Examinar si una soluci´n b´sica factible es ´ptima . . . . ....