Optimizacion
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 . . . . ....
Regístrate para leer el documento completo.