Fotosintesis Bach

TEMAS DE ´ OPTIMIZACION
H´ctor Manuel Mora Escobar e Departamento de Matem´ticas a Universidad Nacional de Colombia Bogot´ a enero de 2008

i

A H´l`ne y Nicol´s ee a

´ Indice general
Pr´logo o 1. M´todos de optimizaci´n lineal e o 1.1. M´todo simplex acotado . . . . . . . . . . . . . . . . . . . . . e 1.1.1. Una fase . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.2. Dos fases. . . . . . . . . . . . . . . . . . . . . . . . . 1.2. M´todo de descomposici´n de Dantzig y Wolfe . . . . . . . . e o 1.2.1. Conjunto acotado . . . . . . . . . . . . . . . . . . . . 1.2.2. Conjunto no acotado . . . . . . . . . . . . . . . . . . . 2. Optimizaci´n entera o 2.1. Cortes de Gomory . . . . . . . . . . . . . . . . . . . . . . . . 2.2. Ramificaci´n y acotamiento . . . . . . . . . . . . .. . . . . . o 2.2.1. Escogencia de la variable que bifurca . . . . . . . . . . 2.2.2. Escogencia del nodo . . . . . . . . . . . . . . . . . . . 2.2.3. Escogencia de la rama . . . . . . . . . . . . . . . . . . 2.2.4. Aproximaciones . . . . . . . . . . . . . . . . . . . . . . 3. Optimizaci´n en grafos o 3.1. Conceptos iniciales . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1. Grafos dirigidos. . . . . . . . . . . . . . . . . . . . . . 3.1.2. Detecci´n de descendientes de un nodo . . . . . . . . . o 3.1.3. Detecci´n de un circuito . . . . . . . . . . . . . . . . . o v 1 1 4 10 15 19 33 53 61 65 72 74 76 84 89 89 90 96 99

3.1.4. Grafos no dirigidos . . . . . . . . . . . . . . . . . . . . 102 3.2. Camino m´s corto . . . . . . . . . . . . . . . . . . . . . . . . 104 a iii

´ INDICEGENERAL

3.2.1. Introducci´n . . . . . . . . . . . . . . . . . . . . . . . 104 o 3.2.2. Algoritmo de Dijkstra . . . . . . . . . . . . . . . . . . 106 3.2.3. Algoritmo de Floyd-Warshall . . . . . . . . . . . . . . 112 3.3. Flujo m´ximo . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 a 3.3.1. Introducci´n . . . . . . . . . . . . . . . . . . . . . . . 116 o 3.3.2. Algoritmo deFord-Fulkerson . . . . . . . . . . . . . . 119 3.4. Flujo de costo m´ ınimo . . . . . . . . . . . . . . . . . . . . . . 130 3.5. Ruta cr´ ıtica . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 3.5.1. De la tabla de actividades a la red . . . . . . . . . . . 138 3.5.2. Simplificaci´n de una red . . . . . . . . . . . . . . . . 141 o 3.5.3. Preproceso de la lista de actividades previas . . . . . .142 ´ 3.6. Arbol generador minimal . . . . . . . . . . . . . . . . . . . . 146 3.6.1. Detecci´n de un ciclo . . . . . . . . . . . . . . . . . . . 147 o 3.6.2. Algoritmo de Kruskal . . . . . . . . . . . . . . . . . . 151 3.6.3. Algoritmo de Prim . . . . . . . . . . . . . . . . . . . . 153 3.6.4. Versi´n matricial del algoritmo de Prim . . . . . . . . 154 o 4. Optimizaci´n no diferenciable o 1654.1. Introducci´n . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 o 4.1.1. Ejemplos de problemas de OND . . . . . . . . . . . . 165 4.1.2. Algunos conceptos . . . . . . . . . . . . . . . . . . . . 167 4.1.3. Formas generales . . . . . . . . . . . . . . . . . . . . . 168 4.1.4. Subgradiente, subdiferencial, optimalidad . . . . . . . 170 4.1.5. Algunos resultados . . . . . . . . . . . . .. . . . . . . 172 4.2. M´todos de OND . . . . . . . . . . . . . . . . . . . . . . . . . 173 e 4.3. M´todo de planos cortantes . . . . . . . . . . . . . . . . . . . 174 e 4.3.1. Problema no restringido . . . . . . . . . . . . . . . . . 175 4.3.2. Problema restringido . . . . . . . . . . . . . . . . . . . 180 4.3.3. M´todo de haces penalizados . . . . . . . . . . . . . . 186 e 4.4. ACCPM . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . 187 4.4.1. Centro anal´ ıtico . . . . . . . . . . . . . . . . . . . . . 188 4.4.2. M´todos de punto interior . . . . . . . . . . . . . . . . 192 e 4.4.3. M´todo de Newton primal factible . . . . . . . . . . . 195 e iv

´ INDICE GENERAL

4.4.4. Algoritmo potencial af´ . . . . . . . . . . . . . . . . . 199 ın 4.4.5. M´todo primal-dual factible...