tecnicas de c´ alculo´ para sistemas de ecuaciones ...jldelafuenteoconnor.es/libro98_full.pdf ·...

960
ecnicas de C´ alculo para Sistemas de Ecuaciones, Programaci ´ on Lineal y Programaci ´ on Entera odigos en FORTRAN y C con Aplicaciones de Sistemas de Energ´ ıa El´ ectrica Jos´ e Luis de la Fuente O’Connor Profesor Titular Universidad Polit´ ecnica de Madrid Escuela T´ ecnica Superior de Ingenieros Industriales

Upload: lenguyet

Post on 20-Sep-2018

220 views

Category:

Documents


0 download

TRANSCRIPT

Programacion Lineal y Programacion Entera
Codigos en FORTRAN y C con Aplicaciones de Sistemas de Energa Electrica
Jose Luis de la Fuente O’Connor Profesor Titular
Universidad Politecnica de Madrid
A mi familia.
Indice General
Indice General VII Indice de Figuras XXIII Indice de Tablas XXV Prefacio XXIX
I Sistemas de ecuaciones 1
Captulo 1. METODOS DIRECTOS DE SOLUCION DE SISTEMAS DE ECUACIONES LINEALES 3 1.1 Planteamiento del problema a resolver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Eliminacion de Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.1 Pivotacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.2.2 Numero de operaciones aritmeticas del metodo . . . . . . . . . . . . . . . . . . . . 20
1.3 Metodo de Gauss-Jordan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 1.4 Descomposicion o factorizacion LU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.4.1 Metodos directos para la obtencion de factorizaciones LU . . . . . . . . . . . . 29 1.4.1.1 Metodo de Crout. Version LU1 . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.4.1.2 Metodo de Crout. Version L1U . . . . . . . . . . . . . . . . . . . . . . . . . 34 1.4.1.3 Metodo de Doolittle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
1.5 Factorizacion de matrices simetricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 1.5.1 Factorizacion LDLT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 1.5.2 Factorizacion de Cholesky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 1.5.3 Matrices simetricas semidefinidas positivas . . . . . . . . . . . . . . . . . . . . . . . 46
1.5.3.1 Pivotacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 1.5.4 Matrices simetricas indefinidas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
1.5.4.1 El metodo de Parlett y Reid . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 1.5.4.2 El metodo de Aasen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 1.5.4.3 Factorizacion de pivotacion diagonal . . . . . . . . . . . . . . . . . . . . . 59
1.5.4.3.1 El metodo de Bunch y Kaufman . . . . . . . . . . . . . . . . . 60 1.6 Condicionamiento de sistemas de ecuaciones lineales . . . . . . . . . . . . . . . . . . . . . 66 1.7 Mnimos cuadrados lineales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
1.7.1 Fundamentos teoricos del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 1.7.1.1 Descomposicion en valores singulares . . . . . . . . . . . . . . . . . . . . 74 1.7.1.2 Sistemas incompatibles. Ecuaciones normales . . . . . . . . . . . . . . 79 1.7.1.3 Sistemas indeterminados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
VII
VIII Indice General
1.7.2 Resolucion numerica del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 1.7.2.1 Metodo de Gram-Schmidt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 1.7.2.2 Factorizacion QR o triangularizacion ortogonal. Transfor-
maciones ortogonales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 1.7.2.2.1 Transformaciones de Householder . . . . . . . . . . . . . . . . 90
1.7.2.2.1.1 Resolucion numerica de Ax = b, Am×n, m > n y rango completo . . . . . . . . . . . . . . . . . . 94
1.7.2.2.1.2 Resolucion numerica de Ax = b, Am×n, n > m y rango completo . . . . . . . . . . . . . . . . . . 98
1.7.2.2.1.3 Resolucion numerica de Ax = b, Am×n, m > n o m < n y rango incompleto . . . . . . . . . 98
1.7.2.2.2 Transformaciones de Givens . . . . . . . . . . . . . . . . . . . . 105 1.7.2.2.3 Transformaciones rapidas de Givens . . . . . . . . . . . . . . 110
1.7.3 Descomposicion numerica en valores singulares. Metodo de Golub-Reinsch 115 1.8 El problema generalizado de mnimos cuadrados . . . . . . . . . . . . . . . . . . . . . . . . . 128 1.9 Mnimos cuadrados lineales con restricciones lineales . . . . . . . . . . . . . . . . . . . . . 131
1.9.1 Resolucion numerica del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 1.9.1.1 Metodo de eliminacion directa . . . . . . . . . . . . . . . . . . . . . . . . . . 132 1.9.1.2 Metodo de la base del subespacio nucleo de la matriz de
restricciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 1.9.1.3 Metodo de la ponderacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
Referencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
Captulo 2. METODOS ITERATIVOS DE SOLUCION DE SISTEMAS DE ECUACIONES LINEALES 143 2.1 Metodo de Jacobi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 2.2 Metodo de Gauss-Seidel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 2.3 Convergencia de los metodos de Jacobi y Gauss-Seidel . . . . . . . . . . . . . . . . . . . . 152
2.3.1 Matrices generales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 2.3.2 Matriz de diagonal dominante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 2.3.3 Matriz simetrica definida positiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
2.4 Metodos de relajacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 2.4.1 Convergencia del metodo SOR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 2.4.2 Metodo SSOR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
2.5 Metodos de minimizacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 2.5.1 Direcciones de descenso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
2.5.1.1 Relajacion en una variable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 2.5.1.2 Relajacion SOR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 2.5.1.3 Maxima pendiente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
2.5.2 Direcciones de descenso conjugadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 2.5.2.1 Determinacion de direcciones conjugadas . . . . . . . . . . . . . . . . . 179 2.5.2.2 Determinacion de direcciones conjugadas. Metodo de los
gradientes conjugados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 2.5.2.2.1 Convergencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 2.5.2.2.2 Interpretacion geometrica del metodo de los gra-
dientes conjugados . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
Indice General IX
2.5.2.2.3 Implementacion practica del metodo de los gra- dientes conjugados . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
2.5.2.2.4 Metodo de los gradientes conjugados con precon- dicionamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
2.6 Comparacion numerica de los algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 2.7 Mnimos cuadrados y metodos iterativos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
2.7.1 Metodo de Jacobi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194 2.7.2 Metodo de Gauss-Seidel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194 2.7.3 Metodo de relajacion SOR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 2.7.4 Metodo de los gradientes conjugados . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
Referencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
Captulo 3. SISTEMAS DE ECUACIONES LINEALES DE MATRIZ DE COEFICIENTES DISPERSA 201 3.1 Almacenamiento en ordenador de matrices dispersas . . . . . . . . . . . . . . . . . . . . . 202
3.1.1 Almacenamiento por coordenadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202 3.1.2 Almacenamiento por filas o columnas . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 3.1.3 Almacenamiento por perfil o envolvente . . . . . . . . . . . . . . . . . . . . . . . . . . 204 3.1.4 Almacenamiento por listas encadenadas . . . . . . . . . . . . . . . . . . . . . . . . . . 207
3.2 Operaciones algebraicas elementales con matrices dispersas . . . . . . . . . . . . . . . . 208 3.2.1 Producto interior de dos vectores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208 3.2.2 Multiplicacion de matrices por vectores . . . . . . . . . . . . . . . . . . . . . . . . . . 210
3.2.2.1 Multiplicacion de una matriz por un vector . . . . . . . . . . . . . . . 210 3.2.2.2 Multiplicacion de un vector por una matriz . . . . . . . . . . . . . . . 210
3.2.3 Suma de matrices dispersas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211 3.2.3.1 Suma o resta simbolica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211 3.2.3.2 Suma o resta numerica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
3.2.4 Multiplicacion de matrices dispersas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 3.2.4.1 Multiplicacion AT A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
3.3 Solucion de grandes sistemas lineales de matriz dispersa . . . . . . . . . . . . . . . . . . . 219 3.3.1 Ordenacion de las ecuaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 3.3.2 Proceso de solucion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
3.4 Matrices dispersas simetricas y eliminacion de Gauss . . . . . . . . . . . . . . . . . . . . . 226 3.4.1 Nociones basicas sobre teora de grafos . . . . . . . . . . . . . . . . . . . . . . . . . . 227 3.4.2 Interpretacion grafo-teorica de la eliminacion de Gauss de matrices
dispersas de estructura simetrica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 3.4.3 El algoritmo de grado mnimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234 3.4.4 Reduccion del ancho de banda de una matriz dispersa simetrica. El
algoritmo de Cuthill-McKee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238 3.4.4.1 Seleccion del nudo inicial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
3.4.5 Reduccion de la envolvente de una matriz dispersa simetrica. El algoritmo inverso de Cuthill-McKee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
3.4.6 Metodo de la diseccion anidada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242 3.4.7 Metodo de la diseccion en un sentido . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
3.5 Matrices dispersas no simetricas y eliminacion de Gauss . . . . . . . . . . . . . . . . . . . 246 3.5.1 Nociones basicas sobre grafos dirigidos . . . . . . . . . . . . . . . . . . . . . . . . . . 248
X Indice General
3.5.2 Interpretacion grafo-teorica de la eliminacion de Gauss de matrices dispersas no simetricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
3.5.3 Obtencion de un transversal completo. Algoritmo de Hall . . . . . . . . . . . . 251 3.5.4 Permutaciones simetricas hacia una estructura triangular en bloques . . . 254
3.5.4.1 Algoritmo de Sargent y Westerberg . . . . . . . . . . . . . . . . . . . . . . 256 3.5.4.2 Algoritmo de Tarjan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
3.5.5 Pivotacion en matrices dispersas y eliminacion de Gauss . . . . . . . . . . . . 261 3.5.6 Metodo de los frentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
3.6 Problemas de mnimos cuadrados dispersos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266 3.6.1 El metodo de las ecuaciones normales . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
3.6.1.1 Dispersidad parcial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268 3.6.2 Metodos basados en transformaciones ortogonales. Metodo de George-
Heath . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270 3.6.2.1 Ordenacion de filas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
3.6.3 Otros metodos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272 Referencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
Captulo 4. SOLUCION DE SISTEMAS DE ECUACIONES NO LINEALES 279 4.1 Velocidad o rapidez de convergencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281 4.2 Problemas de una variable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
4.2.1 Metodo de la biseccion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284 4.2.2 Metodo de Newton-Raphson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286 4.2.3 Convergencia del metodo de Newton para una variable . . . . . . . . . . . . . . 291 4.2.4 Variantes del metodo de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293
4.2.4.1 Metodo de Newton por diferencias finitas . . . . . . . . . . . . . . . . . 295 4.2.4.2 Metodo de Newton modificado . . . . . . . . . . . . . . . . . . . . . . . . . 299
4.2.5 Metodo de la secante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300 4.2.6 Metodo de la falsa posicion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302 4.2.7 Metodo de Muller . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302
4.3 Sistemas de ecuaciones no lineales. Metodo de Newton-Raphson . . . . . . . . . . . . 306 4.3.1 Convergencia del metodo de Newton para sistemas de ecuaciones no
lineales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310 4.3.2 Modificaciones del metodo de Newton para sistemas de ecuaciones
no lineales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312 4.3.2.1 El metodo de Newton-Raphson por diferencias finitas para
sistemas de ecuaciones no lineales . . . . . . . . . . . . . . . . . . . . . . . 313 4.3.2.2 Newton modificado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316 4.3.2.3 Jacobi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316 4.3.2.4 Gauss-Seidel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318 4.3.2.5 Relajacion SOR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
4.4 Metodos cuasi Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320 4.4.1 Metodo de Broyden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321
4.4.1.1 Convergencia del metodo de Broyden . . . . . . . . . . . . . . . . . . . . 326 4.4.1.2 Implementacion practica del metodo de Broyden . . . . . . . . . . . 329
4.5 Metodos globalmente convergentes para sistemas de ecuaciones no lineales . . . . 331 4.6 Mnimos cuadrados no lineales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
Indice General XI
4.6.1 Referencias teoricas del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342 4.6.2 Resolucion numerica del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344
4.6.2.1 Metodo de Gauss-Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346 4.6.2.1.1 Convergencia del metodo de Gauss-Newton . . . . . . . . 349
4.6.2.2 Metodos de Gauss-Newton globalmente convergentes . . . . . . . . 351 4.6.2.3 Metodos de region de confianza. Metodo de Levenberg-
Marquardt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352 4.6.2.4 Metodos tipo Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358
Referencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359
II Programacion lineal 363
Captulo 5. PROGRAMACION LINEAL. FORMULACION 365 5.1 Conceptos y definiciones generales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366 5.2 Ejemplos de problemas de programacion lineal . . . . . . . . . . . . . . . . . . . . . . . . . . 368 Referencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372
Captulo 6. TEORIA BASICA DE LA PROGRAMACION LINEAL 379 6.1 Consideraciones geometricas sobre la programacion lineal . . . . . . . . . . . . . . . . . 379
6.1.1 Representacion geometrica del programa lineal en el subespacio de bienes 382 6.1.1.1 Factibilidad y condiciones de igualdad . . . . . . . . . . . . . . . . . . . 384 6.1.1.2 Factibilidad y condiciones de desigualdad . . . . . . . . . . . . . . . . . 386 6.1.1.3 Optimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386
6.2 Politopos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389 6.3 Puntos extremos y soluciones basicas factibles . . . . . . . . . . . . . . . . . . . . . . . . . . 391
6.3.1 Teorema de la representacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397 6.3.2 Teorema fundamental de la programacion lineal . . . . . . . . . . . . . . . . . . . 402
Referencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406
Captulo 7. El METODO SIMPLEX 411 7.1 Mejora de una solucion basica factible . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412 7.2 Finalizacion. Solucion optima, solucion no acotada y soluciones optimas
alternativas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417 7.3 El algoritmo simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 418
7.3.1 Degeneracion y ciclado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428 7.3.1.1 La regla lexicografica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 429 7.3.1.2 La regla de Bland . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 429
7.4 Solucion basica factible inicial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 429 7.4.1 Variables artificiales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431 7.4.2 Metodo de penalizacion o de la gran M . . . . . . . . . . . . . . . . . . . . . . . . . . 441
7.5 Implementaciones practicas del metodo simplex . . . . . . . . . . . . . . . . . . . . . . . . . 441 7.5.1 El metodo simplex en forma de tableau . . . . . . . . . . . . . . . . . . . . . . . . . . 442 7.5.2 Forma producto de la inversa de la base . . . . . . . . . . . . . . . . . . . . . . . . . 444
XII Indice General
7.5.3 Factorizacion LU de la base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447 7.6 El metodo simplex para variables acotadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 450 7.7 Complejidad computacional del metodo simplex . . . . . . . . . . . . . . . . . . . . . . . . . 459 Referencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461
Captulo 8. DUALIDAD Y ANALISIS DE SENSIBILIDAD 465 8.1 Dualidad y condiciones de optimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466
8.1.1 Condiciones de punto optimo de Karush-Kuhn-Tucker . . . . . . . . . . . . . . 475 8.2 Interpretacion economica de la dualidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476 8.3 El algoritmo dual del simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479
8.3.1 El algoritmo dual del simplex para variables acotadas . . . . . . . . . . . . . . . 482 8.4 El metodo primal–dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486 8.5 Analisis de sensibilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492 Referencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494
Captulo 9. PROGRAMAS LINEALES DE ESTRUCTURA ESPECIAL 499 9.1 Problemas de flujos en redes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 499
9.1.1 Conceptos basicos de teora de grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . 500 9.1.2 Problemas tpicos de flujos en redes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 502 9.1.3 El metodo simplex para problemas de flujos en redes . . . . . . . . . . . . . . . 505
9.1.3.1 Implementacion practica del metodo simplex . . . . . . . . . . . . . . 512 9.1.3.1.1 Paso 1. Asignacion de precios. Comprobacion de
condiciones de optimo . . . . . . . . . . . . . . . . . . . . . . . . . 512 9.1.3.1.2 Paso 2. Determinacion de la columna de pivotacion . . 515 9.1.3.1.3 Paso 3. Determinacion de la fila de pivotacion.
Analisis de ratios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515 9.1.3.1.4 Paso 4. Pivotacion. Actualizacion de las estructu-
ras de datos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 516 9.1.3.1.4.1 Actualizacion de s(·) . . . . . . . . . . . . . . . . . . . . . 517 9.1.3.1.4.2 Actualizacion de p(·) y d(·) . . . . . . . . . . . . . . . . 520
9.1.3.2 Solucion basica factible inicial . . . . . . . . . . . . . . . . . . . . . . . . . . 527 9.2 El principio de descomposicion de Dantzig-Wolfe . . . . . . . . . . . . . . . . . . . . . . . . 527
9.2.1 Implementacion practica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535 9.2.2 Problemas con estructura en escalera . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545
9.3 El problema del corte de materiales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 546 Referencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 550 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 551
Captulo 10. METODOS DE PUNTOS INTERIORES 557 10.1 Ideas basicas de los metodos de puntos interiores para programacion lineal . . . . 558 10.2 El metodo del escalado proyectivo de Karmarkar . . . . . . . . . . . . . . . . . . . . . . . . 561
10.2.1 Transformacion proyectiva en el simplex . . . . . . . . . . . . . . . . . . . . . . . . . 562 10.2.2 Complejidad computacional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 570
10.3 Variantes y extensiones del metodo de Karmarkar . . . . . . . . . . . . . . . . . . . . . . . 571 10.4 El metodo primal de escalado afn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 571
Indice General XIII
10.4.1 Transformacion afn del octante positivo . . . . . . . . . . . . . . . . . . . . . . . . . 572 10.4.2 Solucion de partida del metodo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 580
10.4.2.1 El metodo de la gran M . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 580 10.4.2.2 El metodo en dos fases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 580
10.4.3 Reglas de parada del metodo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 581 10.4.3.1 Factibilidad del programa primal . . . . . . . . . . . . . . . . . . . . . . . 581 10.4.3.2 Factibilidad del programa dual . . . . . . . . . . . . . . . . . . . . . . . . . 581 10.4.3.3 Complementariedad de holguras . . . . . . . . . . . . . . . . . . . . . . . . 582
10.4.4 Complejidad computacional del metodo primal de escalado afn . . . . . . . 582 10.4.4.1 Metodo del empuje potencial . . . . . . . . . . . . . . . . . . . . . . . . . . . 582 10.4.4.2 Metodo de funcion barrera logartmica . . . . . . . . . . . . . . . . . . . 585
10.5 El metodo dual de escalado afn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 587 10.5.1 Ideas basicas del metodo dual de escalado afn . . . . . . . . . . . . . . . . . . . . 588 10.5.2 Solucion de partida del metodo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 593
10.5.2.1 El metodo de la gran M . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 593 10.5.2.2 Metodo de la condicion artificial o del lmite superior . . . . . . . . 593
10.5.3 Reglas de parada del metodo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 594 10.5.4 Mejora de la complejidad computacional del metodo dual de escala-
do afn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 594 10.5.4.1 Metodo de funcion barrera logartmica . . . . . . . . . . . . . . . . . . . 594
10.6 El metodo primal-dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 595 10.6.1 Direccion y amplitud de movimiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . 598
10.6.1.1 Amplitud de movimiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 600 10.6.2 Ajuste del parametro de penalizacion y reglas de parada del metodo . . . 600
10.6.2.1 Reglas de parada del metodo . . . . . . . . . . . . . . . . . . . . . . . . . . . 601 10.6.3 Solucion de partida del metodo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604 10.6.4 Complejidad computacional del metodo . . . . . . . . . . . . . . . . . . . . . . . . . . 606
Referencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 607 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 608
III Programacion entera 611
Captulo 11. PROGRAMACION LINEAL EN VARIABLES ENTERAS 613 11.1 Formulacion y ejemplos de programas lineales en variables enteras . . . . . . . . . . . 615
11.1.1 Problemas de estructura especial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 620 11.1.2 Modelizacion con variables binarias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 622
11.2 Resolucion grafica de programas enteros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 623 11.3 Propiedades de la region factible de los programas enteros . . . . . . . . . . . . . . . . . 624 11.4 Algunas relajaciones de la formulacion de programas enteros . . . . . . . . . . . . . . . 625
11.4.1 Relajacion lineal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 626 11.4.1.1 Generacion de desigualdades . . . . . . . . . . . . . . . . . . . . . . . . . . . 627
11.4.2 Relajacion lagrangiana . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 632 11.4.3 Descomposicion y separacion de costes . . . . . . . . . . . . . . . . . . . . . . . . . . 633 11.4.4 Descomposicion de Benders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633
Referencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 635 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 635
XIV Indice General
Captulo 12. ALGORITMOS GENERALES DE RELAJACION 639 12.1 El algoritmo de los planos cortantes de Gomory . . . . . . . . . . . . . . . . . . . . . . . . . 639
12.1.1 Extension a programas enteros mixtos . . . . . . . . . . . . . . . . . . . . . . . . . . . 645 12.2 Algoritmos de ramificacion y acotamiento o branch and bound . . . . . . . . . . . . . 645
12.2.1 Algoritmos de ramificacion y acotamiento con relajacion lineal . . . . . . . . 648 12.2.1.1 Criterios de poda o rechazo de ramas del arbol enumerativo . . 649 12.2.1.2 Division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 650 12.2.1.3 Seleccion del nudo a estudiar . . . . . . . . . . . . . . . . . . . . . . . . . . . 652 12.2.1.4 Seleccion de la variable de ramificacion . . . . . . . . . . . . . . . . . . . 654
12.2.1.4.1 Seleccion basada en penalizaciones . . . . . . . . . . . . . . . 654 Referencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 664 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 664
IV Apendices 669
Apendice A. REPASO DE MATEMATICAS: DEFINICIONES, NOTACIONES Y RELA- CIONES BASICAS 671 A.1 Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 671 A.2 Aplicaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 672 A.3 Espacios vectoriales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 673
A.3.1 Espacios normados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 675 A.3.2 Espacios con producto interior . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 677 A.3.3 Aplicaciones lineales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 678
A.4 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 680 A.4.1 Normas de matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 681 A.4.2 Matrices ortogonales, matrices de permutacion y matrices de proyeccion 683
A.5 Autovalores, valores singulares y formas cuadraticas . . . . . . . . . . . . . . . . . . . . . . 685 A.5.1 Autovalores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 685 A.5.2 Valores singulares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 686 A.5.3 Formas cuadraticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 687
A.6 Topologa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 691 A.7 Teorema de la proyeccion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 692 A.8 Funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 693
A.8.1 Condiciones necesarias y suficientes de primer y segundo orden que ha de cumplir un punto mnimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 695
A.9 Conjuntos convexos. Existencia de los hiperplanos separador y soporte . . . . . . . 696
Apendice B. ERRORES DE REDONDEO Y ARITMETICA DE PRECISION FINITA 699 B.1 Sistema de numeracion en un ordenador de calculo . . . . . . . . . . . . . . . . . . . . . . . 699 B.2 Precision de un ordenador. Errores de redondeo . . . . . . . . . . . . . . . . . . . . . . . . . 703 B.3 Aritmetica en un ordenador . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 706
B.3.1 Solucion de una ecuacion cuadratica . . . . . . . . . . . . . . . . . . . . . . . . . . . . 708 B.3.2 Mas errores. Una suma de infinitos sumandos . . . . . . . . . . . . . . . . . . . . . 709
Referencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 710
Indice General XV
Apendice C. REDES ELECTRICAS: FLUJOS POR SUS ELEMENTOS Y POTENCIAS INYECTADAS EN SUS NUDOS 711 C.1 Lnea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 711
C.1.1 Potencias inyectadas en los nudos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 712 C.1.2 Flujos de potencia entre los nudos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 714
C.2 Transformador . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 716 C.2.1 Esquema equivalente con el regulador del transformador en el primario . 716 C.2.2 Esquema equivalente con el regulador del transformador en el secundario 717 C.2.3 Potencias inyectadas en los nudos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 719 C.2.4 Flujos de potencia entre los nudos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 720
Referencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 721
Apendice D. CASUISTICA DE PROGRAMACION LINEAL 723 D.1 Gestion financiera a corto plazo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 723
D.1.1 Modelo del problema a optimizar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 725 D.1.2 Analisis de sensibilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 732
D.1.2.1 Cambio en las condiciones de la adquisicion del pasivo no crediticio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 737
D.1.3 Solucion factible inicial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 741 D.1.3.1 Analisis de los valores duales de las condiciones . . . . . . . . . . . . 743
D.2 Gestion operativa de una refinera de crudo de petroleo . . . . . . . . . . . . . . . . . . . 744 D.2.1 Produccion de vapor de agua y electricidad en una refinera de petroleo 745 D.2.2 Modelo del problema a optimizar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 751 D.2.3 Formulacion del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 754 D.2.4 Analisis de sensibilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 761
Referencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 764
Apendice E. El PROGRAMA BBMI 765 E.1 Datos del problema. Formato MPS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 765
E.1.1 Clave NAME . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 766 E.1.2 Seccion ROWS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 767 E.1.3 Seccion COLUMNS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 768
E.1.3.1 Clave INT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 768 E.1.4 Seccion RHS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 769 E.1.5 Seccion RANGES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 769 E.1.6 Seccion BOUNDS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 771
E.2 Parametros y especificaciones de la resolucion . . . . . . . . . . . . . . . . . . . . . . . . . . . 772 E.3 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 773
E.3.1 Programas lineales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 773 E.3.2 Programas enteros puros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 779 E.3.3 Programas enteros mixtos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 783
E.4 Listado de BBMI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 791
XVI Indice General
Apendice F. EL PROGRAMA CCNET 813 F.1 Ejecucion del programa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 814 F.2 Datos del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 814 F.3 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 816 F.4 Listado de CCNET . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 819
Apendice G. VERSIONES EN C y FORTRAN 90 DE LOS PROGRAMAS DEL TEXTO EN FORTRAN 77 831 G.1 Codigos en C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 832
G.1.1 Codigos del captulo 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 832 G.1.2 Codigos del captulo 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 840 G.1.3 Codigos del captulo 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 842 G.1.4 Codigos del captulo 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 847 G.1.5 Codigos del apendice B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 856 G.1.6 Codigos del apendice H . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 856
G.2 Codigos en Fortran 90 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 858 G.2.1 Codigos del captulo 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 858 G.2.2 Codigos del captulo 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 866 G.2.3 Codigos del captulo 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 868 G.2.4 Codigos del captulo 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 868
Apendice H. ESTIMACION DEL NUMERO DE CONDICION DE MATRICES CUADRA- DAS 879 H.1 El estimador de Cline, Moler, Stewart y Wilkinson . . . . . . . . . . . . . . . . . . . . . . . 880 H.2 El algoritmo de Hager . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 886 Referencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 889
Apendice I. SOFTWARE DISPONIBLE EN INTERNET 891 I.1 Software de pago . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 892 I.2 Software de dominio publico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 893
Apendice J. EL SOFTWARE DEL LIBRO 895
Bibliografa 897
Indice de Figuras
1.1 Casos posibles de sistemas de ecuaciones lineales Ax = b dependiendo del tamano y rango de la matriz A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Descripcion geometrica en dos dimensiones de la resolucion de un sistema de ecuaciones lineales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Representacion geometrica en el subespacio Im(A) de dos dimensiones de la resolucion de un sistema de ecuaciones lineales . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4 Permutaciones elementales en una matriz triangular inferior . . . . . . . . . . . . . . . . . . 25 1.5 Ilustracion del proceso del algoritmo de Doolittle para la factorizacion LU por
columnas de una matriz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 1.6 Partes ya calculadas y por calcular de la factorizacion de Cholesky for filas
(etapa i) y por columnas (etapa j) de una matriz A . . . . . . . . . . . . . . . . . . . . . . . . 47 1.7 Ilustracion del buen y mal condicionamiento de dos sistemas de ecuaciones
lineales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 1.8 Ejemplo de problema de mnimos cuadrados: ajuste de una funcion a una nube
de puntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 1.9 Ilustracion en dos dimensiones de una transformacion lineal de la esfera unidad . . 76 1.10 Descripcion geometrica del problema minx∈2 Ax − b2, A ∈ 3×2 . . . . . . . . . . . 80 1.11 Interpretacion geometrica en 3 del problema x∗ = minx∈3 {x2:Ax = b} . . . . 82 1.12 Descripcion geometrica del proceso de ortonormalizacion de Gram-Schmidt . . . . . . 84 1.13 Representacion de la aplicacion a a de la transformacion de Householder de-
finida por w . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 1.14 Resultado de aplicar a x la transformacion de Householder que define el vector
(x − y)/x − y2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 1.15 Factorizacion de una matriz 6 × 4 por transformaciones de Householder . . . . . . . . 92 1.16 Representacion de como obtener las dos transformaciones de Householder po-
sibles de un vector a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 1.17 Resultado de la factorizacion de una matriz m×n de rango r por transforma-
ciones de Householder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 1.18 Segundo proceso de transformaciones ortogonales para resolver un problema
general de mnimos cuadrados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 1.19 Segundo proceso de transformaciones ortogonales para resolver un problema
general de mnimos cuadrados (continuacion) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 1.20 Ejemplo de una transformacion de Givens en el espacio eucldeo tridimensional . . . 106
XVII
XVIII Indice de Figuras
1.21 Proceso de bidiagonalizacion de una matriz 6 × 4 mediante transformaciones de Householder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
2.1 Movimiento a lo largo de un vector direccion de descenso . . . . . . . . . . . . . . . . . . . . 171 2.2 Minimizacion en la variable α . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 2.3 Relajacion SOR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 2.4 Proceso de convergencia del metodo de la maxima pendiente aplicado a una
funcion cuadratica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 2.5 Interpretacion geometrica del metodo de los gradientes conjugados . . . . . . . . . . . . 187
3.1 Estructura simbolica (simetrica) de una matriz 14× 14 antes de proceder a su factorizacion mediante eliminacion de Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
3.2 Estructura simbolica de la matriz de la figura 3.1 despues de proceder a su factorizacion mediante eliminacion de Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
3.3 Estructura simbolica de la matriz de la figura 3.1 despues de proceder a la reordenacion de sus filas y columnas mediante el algoritmo de grado mnimo y a su posterior factorizacion mediante eliminacion de Gauss . . . . . . . . . . . . . . . . . 221
3.4 Matriz 35×35, de estructura simbolica simetrica, antes y despues de reordenar sus filas y columnas con el algoritmo de Cuthill-McKee . . . . . . . . . . . . . . . . . . . . . 223
3.5 Matriz triangular inferior en bloques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223 3.6 Matriz 16×16, de estructura simbolica no simetrica, antes de reordenar sus
filas y columnas para reducirla a una de estructura triangular inferior en bloques . 224 3.7 Matriz de la figura 3.6 despues de reordenar sus filas y columnas para reducirla
a una de estructura triangular inferior en bloques . . . . . . . . . . . . . . . . . . . . . . . . . . 224 3.8 Patron de elementos distintos de cero de una matriz simetrica 480 × 480 y el
de su factor L una vez efectuada la factorizacion LLT . . . . . . . . . . . . . . . . . . . . . . 227 3.9 Patron de elementos distintos de cero de una matriz simetrica 480 × 480 or-
denada mediante el algoritmo de grado mnimo y el de su factor L una vez efectuada la factorizacion LLT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
3.10 Patron de elementos distintos de cero de una matriz simetrica 480 × 480 or- denada mediante el algoritmo de Cuthill-McKee y el de su factor L una vez efectuada la factorizacion LLT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
3.11 Matriz 11 × 11 de estructura simbolica simetrica y su grafo numerado asociado . . . 229 3.12 Grafo no dirigido de 20 nudos, su estructura de niveles y su correspondiente
arbol cociente con numeracion monotona . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 3.13 Arbol maximal del grafo de la figura 3.12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 3.14 Tres primeras etapas de la eliminacion de Gauss de una matriz simetrica 11 ×
11 y sus correspondientes grafos de eliminacion. Los elementos de relleno se indican mediante el smbolo ⊗ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
3.15 Resultado de la eliminacion simbolica de Gauss en la matriz de la figura 3.11 mediante grafos de eliminacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
3.16 Grafo asociado a una matriz 7×7 sobre el que se ilustra el algoritmo de grado mnimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
3.17 Matriz 7× 7 y su grafo asociado con la numeracion resultado del algoritmo de grado mnimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
3.18 Grafo donde la renumeracion que resultara de aplicarle el algoritmo de grado mnimo no es la optima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
Indice de Figuras XIX
3.19 Grafo de 10 nudos antes y despues de aplicarle el algoritmo de Cuthill-McKee, comenzando la numeracion en a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
3.20 Grafo de 10 nudos de la figura 3.19 una vez aplicado el algoritmo de Cuthill- McKee, comenzando la numeracion en e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
3.21 Grafo de 10 nudos de la figura 3.19 al que se le aplica el algoritmo de la tabla 3.6 para determinar que nudo ha de ser el de partida para el algoritmo de Cuthill-McKee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
3.22 Ejemplo 3.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242 3.23 Ejemplo de la adaptacion del algoritmo de Cuthill-McKee al grafo de la figura 3.22 243 3.24 Resultado de la aplicacion del algoritmo inverso de Cuthill-McKee al grafo de
la figura 3.22 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 3.25 Resultado del algoritmo inverso de Cuthill-McKee aplicado el grafo de la figura 3.19 243 3.26 Metodo de la diseccion anidada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244 3.27 Metodo de la diseccion en un sentido . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245 3.28 Matriz no simetrica y su digrafo asociado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249 3.29 Primera etapa de la eliminacion de Gauss y su correspondiente digrafo de
eliminacion de la matriz de la figura 3.28. El elemento de relleno se indica mediante el smbolo ⊗ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
3.30 Resultado final de la eliminacion de Gauss simbolica de la matriz de la figura 3.28 251 3.31 Algoritmo de Hall para la busqueda de un transversal completo en una matriz
12 × 12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 3.32 Digrafo con dos componentes fuertes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254 3.33 Digrafo de una matriz triangular . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256 3.34 Digrafo sobre el que se aplica el algoritmo de Sargent y Westerberg . . . . . . . . . . . . 257 3.35 Digrafo en el que el algoritmo de Sargent y Westerberg presenta dificultades . . . . . 257 3.36 Ejemplo de digrafo con dos componentes fuertes no triviales . . . . . . . . . . . . . . . . . 259 3.37 Digrafo de la figura 3.36 una vez renumerado con el algoritmo de Tarjan . . . . . . . . 260 3.38 Etapa k = 3 de la eliminacion de Gauss de una matriz de orden 7 . . . . . . . . . . . . . 262 3.39 Pieza mecanica mallada para su analisis por elementos finitos . . . . . . . . . . . . . . . . 263 3.40 Matriz A despues de ensamblados los primeros seis elementos de la figura 3.39 . . . 264 3.41 Malla 2× 4 y primeras tres filas de la matriz a que da lugar el metodo de los frentes 266 3.42 Matriz A de un problema no de elementos finitos en el proceso de tratamiento
por el metodo de los frentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266 3.43 Procesamiento simbolico de la fila 9 de una matriz A ∈ 9×8 por el algoritmo
de George y Heath. Los smbolos ⊗ designan los elementos de R8 involucrados en la eliminacion de aT
9 ; ⊕ los que se crean en esa eliminacion . . . . . . . . . . . . . . . . 271
4.1 Sistema electrico de generacion y transporte de 3 nudos, 3 lneas y 2 generadores . 282 4.2 Decisiones posibles en la primera iteracion del metodo de la biseccion . . . . . . . . . . 285 4.3 Proceso de obtencion de la solucion de x sen(x) − 1 = 0 con el metodo de la
biseccion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287 4.4 Telas de arana de g(x) = (sen(x))1/3 y g(x) = sen(x)/x2 . . . . . . . . . . . . . . . . . . . . 288 4.5 Aproximacion lineal de f(x) en x = x1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289 4.6 Obtencion de la solucion de x3 − sen(x) = 0 con el metodo de Newton . . . . . . . . . 290 4.7 Metodo de Newton aplicado a f(x) = arctan(x) . . . . . . . . . . . . . . . . . . . . . . . . . . . 294 4.8 Metodo de Newton con mecanismo de salvaguarda . . . . . . . . . . . . . . . . . . . . . . . . . 295 4.9 Metodo de Newton modificado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
XX Indice de Figuras
4.10 Metodo de la secante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301 4.11 Metodo Regula Falsi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303 4.12 Ejemplo donde los metodos de la secante y regula falsi convergen muy lentamente 303 4.13 Primera aproximacion parabolica del metodo de Muller . . . . . . . . . . . . . . . . . . . . . 304 4.14 Metodo de Broyden en una variedad lineal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327 4.15 Criterio de Armijo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331 4.16 Red electrica IEEE de 30 Nudos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337 4.17 Conjunto tpico de medidas para la estimacion del estado de un sistema electrico . 338 4.18 Geometra del ajuste de una funcion no lineal con un parametro a dos puntos . . . . 345
5.1 Region factible del problema de programacion lineal del ejemplo 5.1 . . . . . . . . . . . 367 5.2 Representacion grafica del problema del transporte . . . . . . . . . . . . . . . . . . . . . . . . . 370
6.1 Resolucion geometrica del problema de programacion lineal del ejemplo 6.1 . . . . . . 380 6.2 Solucion optima unica finita: (a) region factible acotada; (b) region factible no
acotada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381 6.3 Soluciones optimas alternativas: (a) region factible acotada; (b) region factible
no acotada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381 6.4 (a) Solucion optima no acotada. (b) Region factible vaca . . . . . . . . . . . . . . . . . . . . 382 6.5 Conjuntos convexo y no convexo; cono convexo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383 6.6 Interpretacion geometrica de la factibilidad de un programa lineal: (a) region
factible no vaca; (b) region factible vaca . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385 6.7 Regiones factibles del ejemplo 6.2: (a) no vaca; (b) vaca . . . . . . . . . . . . . . . . . . . . 386 6.8 Programa lineal con condiciones de desigualdad: (a) region factible no vaca;
(b) region factible vaca . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387 6.9 Descripcion geometrica del ejemplo 6.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388 6.10 Geometra del ejemplo 6.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388 6.11 Representacion del hiperplano −x1 + 4x2 = 11, y los semiespacios que define . . . . 390 6.12 Soluciones basicas/soluciones basicas factibles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393 6.13 Soluciones basicas factibles degeneradas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 396 6.14 Direcciones en el politopo del ejemplo 6.7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399 6.15 Puntos y direcciones extremos de un politopo P . . . . . . . . . . . . . . . . . . . . . . . . . . . 399 6.16 Representacion de un punto de un politopo (poliedro) como combinacion con-
vexa de puntos extremos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401 6.17 Representacion del politopo del ejemplo 6.8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403 6.18 Direcciones extremas y optimo: (a) solucion optima no acotada; (b) optimo acotado 405
7.1 Solucion basica degenerada y direccion no factible . . . . . . . . . . . . . . . . . . . . . . . . . 414 7.2 Proceso de mejora de una solucion basica factible del problema del ejemplo 7.1 . . . 415 7.3 Representacion del proceso seguido hasta la solucion en el problema del ejemplo 7.2 424 7.4 Problema con solucion no acotada del ejemplo 7.3 . . . . . . . . . . . . . . . . . . . . . . . . . 425 7.5 El algoritmo simplex resolviendo un problema con soluciones optimas alternativas 427 7.6 Trayectoria seguida en la resolucion del ejemplo 7.8 empleando las fases I y II
del metodo simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 441 7.7 Busqueda de la solucion del problema de Klee y Minty para n = 2 y n = 3 . . . . . . 460
8.1 Geometra de las condiciones de optimo del ejemplo 8.2 . . . . . . . . . . . . . . . . . . . . . 468
Indice de Figuras XXI
8.2 Descripcion geometrica de la existencia de un hiperplano separador . . . . . . . . . . . . 473 8.3 El sistema (I) del lema de Farkas no tiene solucion. La tiene (II) . . . . . . . . . . . . . . 474 8.4 El sistema (II) del lema de Farkas no tiene solucion. La tiene (I) . . . . . . . . . . . . . . 474
9.1 Grafo dirigido, o digrafo, de 4 nudos y 6 arcos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 500 9.2 Algunas estructuras basicas de un grafo dirigido . . . . . . . . . . . . . . . . . . . . . . . . . . . 501 9.3 Flujo maximo en una red y su formulacion como problema de coste mnimo . . . . . 504 9.4 El problema de la asignacion en forma de grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505 9.5 Determinacion del arbol maximal de una red . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507 9.6 Arbol maximal del ejemplo 9.2 con nudo ficticio . . . . . . . . . . . . . . . . . . . . . . . . . . . 509 9.7 Digrafo o grafo correspondiente a los datos de la tabla 9.3 . . . . . . . . . . . . . . . . . . . 513 9.8 Arbol maximal sobre el que se ilustra el proceso de adaptacion del vector s(·)
una vez efectuada una iteracion del metodo simplex . . . . . . . . . . . . . . . . . . . . . . . . 518 9.9 Arbol maximal resultante del de la figura 9.8 una vez introducido el arco (3,20)
en la base. Sale el (8,9) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 519 9.10 Arbol maximal del ejemplo de la tabla 9.3 una vez introducido el arco (7,9)
en la base y retirado el (1,8) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 521 9.11 Grafo correspondiente al problema del ejemplo 9.4 . . . . . . . . . . . . . . . . . . . . . . . . . 522 9.12 Arbol maximal de la iteracion 1 del ejemplo 9.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . 523 9.13 Iteracion 1 Paso 2: determinacion del camino para encontrar la fila de pivotacion . 524 9.14 Arbol maximal de la iteracion 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 525 9.15 Iteracion 2 Paso 2: determinacion del camino para encontrar la fila de pivotacion . 525 9.16 Arbol maximal de la iteracion 3 del ejemplo 9.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . 526 9.17 (a) Grafo de la figura 9.1 aumentado en el nudo artificial 5 para obtener una
solucion factible inicial. (b) Arbol maximal inicial . . . . . . . . . . . . . . . . . . . . . . . . . . 528 9.18 Estructura diagonal por bloques de la matriz del problema 9.6 . . . . . . . . . . . . . . . . 529 9.19 Politopos X1 y X2 que define el problema 9.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 539 9.20 Evolucion del valor de la funcion objetivo del problema del ejemplo 9.5 y del
de su lmite inferior calculado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545 9.21 Estructura en escalera de una matriz de condiciones . . . . . . . . . . . . . . . . . . . . . . . . 545 9.22 Digrafo del ejercicio 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 553
10.1 Itinerarios hacia el optimo por el interior y exterior del poliedro que definen las condiciones de un problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 559
10.2 Maxima esfera (circunferencia en este caso) que se puede centrar en a dentro de la region factible x ≥ 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 560
10.3 Maximas elipses que se pueden inscribir en a y en b′ en la region factible x ≥ 0 . . 561 10.4 Esferas de radio mnimo y maximo que pueden circunscribir un simplex e
inscribirse en el . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 562 10.5 Transformacion proyectiva del ejemplo 10.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 564 10.6 a. Region factible original; b. Despues de la primera transformacion proyectiva
x se convierte en e/n; c. Despues de la segunda transformacion . . . . . . . . . . . . . . . 565 10.7 Region factible del problema del ejemplo 10.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 568 10.8 Descripcion geometrica de la transformacion afn en dos dimensiones . . . . . . . . . . . 573 10.9 Obtencion de la direccion en el subespacio nucleo de Ak . . . . . . . . . . . . . . . . . . . . . 574 10.10 Representacion de la idea en la que se basa el metodo de empuje potencial . . . . . . 583
XXII Indice de Figuras
10.11 Funcion barrera logartmica del problema: minimizar f(x) = 3 − x/2 sujeta a x ≤ 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 586
11.1 Funcion objetivo concava del problema de la localizacion de almacenes . . . . . . . . . 618 11.2 Funcion de costes de un grupo de una central termica . . . . . . . . . . . . . . . . . . . . . . 619 11.3 Bucles en el problema del representante de comercio . . . . . . . . . . . . . . . . . . . . . . . . 620 11.4 Region factible del problema del ejemplo 11.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 624 11.5 Generacion de desigualdades por redondeo entero . . . . . . . . . . . . . . . . . . . . . . . . . . 628 11.6 Region factible del problema del ejemplo 11.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 629 11.7 Ilustracion del ejemplo 11.4 sobre desigualdades disyuntivas . . . . . . . . . . . . . . . . . . 631 11.8 Funciones del ejemplo 11.5 para generar desigualdades validas . . . . . . . . . . . . . . . . 632
12.1 Resolucion del problema del ejemplo 12.1 mediante el algoritmo de los planos cortantes de Gomory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 644
12.2 Division recursiva de una region factible . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 646 12.3 Division recursiva de una region factible de un problema en variables 0 o 1 . . . . . . 647 12.4 Division recursiva de la region factible del problema en variables 0 o 1 del
ejemplo 12.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 648 12.5 Division, por dicotoma de la variable xj , en un arbol enumerativo . . . . . . . . . . . . 650 12.6 Dicotoma debida a la existencia de cotas superiores generalizadas . . . . . . . . . . . . . 651 12.7 Division del arbol enumerativo en tantas ramas como valores enteros puede
tomar la variable xj . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 651 12.8 Seleccion de los nudos de un arbol enumerativo de acuerdo con la regla LIFO . . . . 653 12.9 Arbol enumerativo del problema del ejemplo 12.3 . . . . . . . . . . . . . . . . . . . . . . . . . . 661 12.10 Region factible y arbol enumerativo del problema del ejemplo 12.4 . . . . . . . . . . . . 665
A.1 Representacion grafica de la regla del triangulo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 675 A.2 Grafica de una de las funciones de una sucesion de Cauchy . . . . . . . . . . . . . . . . . . 677 A.3 Efecto de una aplicacion lineal sobre la bola unidad para diferentes normas . . . . . . 684 A.4 Representacion en dos dimensiones de una transformacion lineal de la esfera unidad 687
B.1 Conjunto F de numeros reales representables en un ordenador con β = 2, t = 3, L = −1 y U = 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 700
C.1 Esquema en Π de una lnea entre dos nudos i y j . . . . . . . . . . . . . . . . . . . . . . . . . . 712 C.2 Transformador entre los nudos i y j . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 716 C.3 Esquema en Π del transformador entre i y j con el regulador conectado a i . . . . . . 718 C.4 Transformador entre i y j . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 718 C.5 Esquema en Π del transformador entre i y j con el regulador conectado a j . . . . . 719
D.1 Proceso productivo simplificado de una refinera de crudo de petroleo . . . . . . . . . . 744 D.2 Esquema productivo de vapor de agua de una refinera de crudo de petroleo . . . . . 746 D.3 Esquema productivo de las turbinas de vapor de la refinera . . . . . . . . . . . . . . . . . . 747 D.4 Fluidos que se consumen y producen en la unidad de produccion numero 11 y
esquema de flujos energeticos en la refinera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 750
E.1 Estructura de elementos distintos de cero de un programa entero mixto para prueba de Bbmi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 784
Indice de Figuras XXIII
J.1 Representacion de la disposicion del software del libro que se incluye en el CD-ROM que se adjunta al mismo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 896
Indice de Tablas
1.1 Algoritmo para la resolucion de Ax = b mediante eliminacion de Gauss con pivotacion parcial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.2 Algoritmo para la factorizacion LU1 de una matriz An×n por el metodo de Crout . 30 1.3 Algoritmo de Crout con pivotacion parcial para la factorizacion LU1 de una
matriz An×n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 1.4 Algoritmo para la factorizacion L1U de una matriz An×n por el metodo de Crout . 36 1.5 Algoritmo para la factorizacion L1U de una matriz An×n por el metodo de
Doolittle. Los coeficientes de los factores se generan por columnas . . . . . . . . . . . . . 37 1.6 Algoritmo para la factorizacion LDLT de una matriz An×n simetrica . . . . . . . . . . 41 1.7 Algoritmo para la factorizacion GT G de Cholesky por filas de una matriz An×n
simetrica definida positiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 1.8 Algoritmo para la factorizacion GT G de Cholesky por columnas de una matriz
An×n simetrica definida positiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 1.9 Variante del algoritmo de Cholesky de la tabla 1.7 para matrices An×n simetricas
semidefinidas positivas. Sin pivotacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 1.10 Algoritmo para la factorizacion GT G de Cholesky de una matriz An×n simetrica
semidefinida positiva con pivotacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 1.11 Algoritmo de Aasen sin pivotacion para la factorizacion LTLT de una matriz
An×n simetrica indefinida . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 1.12 Algoritmo de Aasen con pivotacion para la factorizacion LTLT de una matriz
An×n simetrica indefinida . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 1.13 Operaciones de la pivotacion en el metodo de Bunch y Kaufman . . . . . . . . . . . . . . 62 1.14 Algoritmo para la factorizacion UBUT de una matriz An×n simetrica indefi-
nida por el metodo de Bunch y Kaufman con pivotacion . . . . . . . . . . . . . . . . . . . . 63 1.15 Algoritmo clasico de Gram-Schmidt para la ortonormalizacion de los vectores
columna de una matriz Am×n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 1.16 Algoritmo modificado de Gram-Schmidt para la ortonormalizacion de los vec-
tores columna de una matriz Am×n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 1.17 Algoritmo modificado de Gram-Schmidt para la ortonormalizacion de los vec-
tores columna de una matriz Am×n. Version por filas . . . . . . . . . . . . . . . . . . . . . . . 86 1.18 Algoritmo para la resolucion de minx∈n Ax − b2 por transformaciones de
Householder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 1.19 Algoritmo para la resolucion de minx∈n Ax−b2 mediante transformaciones
de Givens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
XXVI Indice de Tablas
1.20 Calculo de los elementos de las filas i y j de las matrices D y P en las trans- formaciones rapidas de Givens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
1.21 Algoritmo para la resolucion de minx∈n Ax − b2 por transformaciones rapidas de Givens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
1.22 Algoritmo de Golub-Kahan: etapa k del procedimiento de Golub-Reinsch para obtener los valores singulares de una matriz bidiagonal Bn×n . . . . . . . . . . . . . . . . . 121
1.23 Algoritmo de Golub-Reinsch para la obtencion de los valores singulares de una matriz A ∈ m×n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
1.24 Numero de operaciones necesarias para efectuar las distintas variantes de una descomposicion en valores singulares de una matriz A ∈ m×n . . . . . . . . . . . . . . . . 127
1.25 Numero de operaciones necesarias para resolver el problema de mnimos cua- drados minx∈n Ax − b2 por distintos metodos . . . . . . . . . . . . . . . . . . . . . . . . . . 129
2.1 Algoritmo de Jacobi para la resolucion de Ax = b . . . . . . . . . . . . . . . . . . . . . . . . . 147 2.2 Algoritmo de Gauss-Seidel para la resolucion de Ax = b . . . . . . . . . . . . . . . . . . . . . 150 2.3 Algoritmo de relajacion SOR para la resolucion de Ax = b . . . . . . . . . . . . . . . . . . 165 2.4 Algoritmo de la maxima pendiente para resolver Ax = b . . . . . . . . . . . . . . . . . . . . 176 2.5 Algoritmo de los gradientes conjugados para resolver Ax = b . . . . . . . . . . . . . . . . . 188 2.6 Proceso de convergencia de la resolucion de un sistema de ecuaciones lineales
mediante el metodo de los gradientes conjugados . . . . . . . . . . . . . . . . . . . . . . . . . . 190 2.7 Algoritmo de los gradientes conjugados con precondicionamiento para resolver
Ax = b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 2.8 Resultados obtenidos por diversos metodos iterativos para resolver un proble-
ma lineal mal condicionado de 50 ecuaciones con 50 incognitas . . . . . . . . . . . . . . . 193 2.9 Algoritmo de los gradientes conjugados para resolver AT (b − Ax) . . . . . . . . . . . . . 196
3.1 Algoritmo para resolver sistemas de ecuaciones lineales Ax = b, siendo A dispersa 221 3.2 Numero de operaciones a realizar con diversas variantes de la matriz de la figu-
ra 3.1 para, utilizando eliminacion de Gauss, resolver un sistema de ecuaciones lineales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
3.3 Algoritmo de grado mnimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235 3.4 Ejemplo de aplicacion del algoritmo de grado mnimo . . . . . . . . . . . . . . . . . . . . . . . 237 3.5 Algoritmo de Cuthill-McKee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238 3.6 Algoritmo para determinar un nudo pseudoperiferico en un grafo (para obtener
el nudo de partida del algoritmo de Cuthill-McKee) . . . . . . . . . . . . . . . . . . . . . . . . 241 3.7 Pasos y camino trazado para renumerar el digrafo de la figura 3.33 . . . . . . . . . . . . 256 3.8 Pila correspondiente al digrafo de la figura 3.34 . . . . . . . . . . . . . . . . . . . . . . . . . . . 258 3.9 Pila correspondiente al digrafo de la figura 3.36 . . . . . . . . . . . . . . . . . . . . . . . . . . . 259 3.10 Algoritmo de Tarjan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260 3.11 Algoritmo para resolver mnimos cuadrados con matrices dispersas mediante
las ecuaciones normales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269 3.12 Algoritmo de ortogonalizacion dispersa de George y Heath . . . . . . . . . . . . . . . . . . . 272
4.1 Convergencia de diversas sucesiones escalares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283 4.2 Convergencia del metodo de la biseccion aplicado a x sen(x) − 1 = 0 . . . . . . . . . . . 286 4.3 Convergencia del metodo de Newton modificado aplicado a x3 − sen(x) = 0 . . . . . 300 4.4 Algoritmo de Newton-Raphson para sistemas de ecuaciones no lineales . . . . . . . . . 307
Indice de Tablas XXVII
4.5 Proceso de convergencia del problema del ejemplo 4.3 mediante el metodo de Newton-Raphson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
4.6 Proceso de convergencia del problema del ejemplo 4.3 mediante el metodo de Newton-Raphson por diferencias finitas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316
4.7 Proceso de convergencia del problema del ejemplo 4.3 mediante el metodo de Newton, variante Jacobi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
4.8 Proceso de convergencia del problema del ejemplo 4.3 mediante el metodo de Newton, variante SOR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
4.9 Algoritmo cuasi Newton con la formula de Broyden para la solucion de sistemas de ecuaciones no lineales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323
4.10 Proceso de convergencia a la solucion del problema del ejemplo 4.5 con el metodo cuasi Newton basado en la formula de Broyden . . . . . . . . . . . . . . . . . . . . . 326
4.11 Algoritmo de Newton para sistemas de ecuaciones no lineales con el criterio de salvaguarda de Armijo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333
4.12 Proceso de convergencia a la solucion del sistema de ecuaciones no lineales del ejemplo 4.6 con el metodo de Newton y el criterio de Armijo . . . . . . . . . . . . . . . . . 336
4.13 Parametros del problema de la figura 4.17 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340 4.14 Algoritmo de Gauss-Newton para resolver problemas no lineales de mnimos
cuadrados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346 4.15 Metodo de Gauss-Newton. Proceso de convergencia a la solucion del problema
del ejemplo 4.8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349 4.16 Algoritmo de Levenberg-Marquart para resolver problemas no lineales de mnimos
cuadrados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353 4.17 Datos del problema no lineal de mnimos cuadrados del ejemplo 4.9 . . . . . . . . . . . . 354 4.18 Metodo de Levenberg-Marquardt. Proceso de convergencia a la solucion del
problema del ejemplo 4.9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357
5.1 Parametros del problema de la planificacion de la generacion de energa de una empresa electrica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371
6.1 Bases y soluciones basicas del poliedro del ejemplo 6.5 . . . . . . . . . . . . . . . . . . . . . . 394
7.1 El algoritmo simplex revisado (comienza a partir de una solucion factible) . . . . . . . 420 7.2 El metodo simplex en sus dos fases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 432 7.3 Algoritmo simplex revisado en la forma producto de la inversa de la base . . . . . . . 446 7.4 Algoritmo simplex revisado para variables acotadas . . . . . . . . . . . . . . . . . . . . . . . . 454
8.1 Combinaciones posibles primal-dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471 8.2 Algoritmo dual del simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481 8.3 Algoritmo dual del simplex para variables acotadas . . . . . . . . . . . . . . . . . . . . . . . . . 483 8.4 Algoritmo primal–dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489
9.1 Algoritmo para la obtencion de un arbol maximal de un grafo dirigido . . . . . . . . . 507 9.2 Algoritmo para la triangularizacion de una base . . . . . . . . . . . . . . . . . . . . . . . . . . . 510 9.3 Estructura de datos del grafo de la figura 9.7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513 9.4 Algoritmo para la obtencion de los multiplicadores simplex en el algoritmo
simplex para flujos en redes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514
XXVIII Indice de Tablas
9.5 Algoritmo para la actualizacion del vector s(·) en el metodo simplex especia- lizado para optimizacion de flujos en redes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 520
9.6 Estructura de datos del arbol de la figura 9.10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 522 9.7 Algoritmo de descomposicion de Dantzig-Wolfe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 538 9.8 Resultado del problema del ejemplo 9.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 551
10.1 Algoritmo de Karmarkar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 567 10.2 Algoritmo primal de escalado afn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 578 10.3 Algoritmo dual de escalado afn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 591 10.4 Proceso de convergencia del algoritmo dual de escalado afn aplicado al ejemplo 10.5 592 10.5 Algoritmo primal-dual de puntos interiores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 602 10.6 Proceso de convergencia del algoritmo primal-dual de puntos interiores apli-
cado al ejemplo 10.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604
12.1 Algoritmo general para programas enteros basado en relajaciones sucesivas . . . . . . 640 12.2 El algoritmo de los planos cortantes de Gomory . . . . . . . . . . . . . . . . . . . . . . . . . . . 643 12.3 El algoritmo de ramificacion y acotamiento o branch and bound . . . . . . . . . . . . . . . 649
A.1 Forma de la bola unidad para diferentes normas en 2 . . . . . . . . . . . . . . . . . . . . . . 676
B.1 Parametros de la aritmetica de precision finita de diversas maquinas . . . . . . . . . . . 701
D.1 Costes unitarios de la compra o venta de valores o productos financieros . . . . . . . . 725 D.2 Balance equilibrado a partir del cual se obtiene una solucion factible inicial
del problema de la gestion financiera a corto plazo . . . . . . . . . . . . . . . . . . . . . . . . . 742 D.3 Produccion/consumo horario de agua, vapor de agua y condensados de las
diversas unidades de produccion de la refinera . . . . . . . . . . . . . . . . . . . . . . . . . . . . 748 D.4 Requisitos horarios de energa electrica y combustibles en las distintas unidades
de produccion, y consumos de vapor y potencias de las turbinas . . . . . . . . . . . . . . 749 D.5 Entalpas en kcal/kg de los diversos fluidos de vapor de agua de la refinera . . . . . 752 D.6 Soluciones optimas de los diversos modelos del problema de la refinera . . . . . . . . . 762
E.1 Especificaciones numericas de un problema de dieta alimenticia como el intro- ducido en el captulo 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 775
F.1 Segundos de c.p.u. invertidos en una estacion de trabajo HP APOLLO 9000 730 para resolver diversos problemas de optimizacion en redes . . . . . . . . . . . . . . . . . . . 817
H.1 Algoritmo para la estimacion del numero de condicion κ1(T ) de una matriz triangular superior . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 881
H.2 El algoritmo de Hager para estimar el numero de condicion 1 de una matriz A . . . 887
Prefacio
El contenido de este libro tiene que ver fundamentalmente con la tecnologa hoy en da dis- ponible de lo que en sentido amplio se conoce como analisis numerico o calculo numerico. Por precisar un poco mas, se refiere a aquellas tecnicas y procedimientos de computo que abordan los problemas de resolver sistemas de ecuaciones lineales y no lineales, programas lineales (tam- bien denominados problemas de programacion lineal) y programas enteros (programas lineales donde algunas o todas las variables estan restringidas a tomar valores enteros). Constituye la tercera edicion impresa de un esfuerzo tendente a estudiar los problemas mencionados con cierta profundidad y a transmitir a los lectores las experiencias que de ello se han derivado en los ultimos tiempos. El precedente mas cercano es el publicado en 1993 en esta misma editorial bajo el ttulo Tecnologas Computacionales para Sistemas de Ecuaciones, Optimizacion Lineal y Entera, que merecio el honor de ser designado Premio Jose Morillo y Farfan por la Fundacion F 2I2 del Ministerio de Industria y Energa y la Universidad Politecnica de Madrid.
Aun cuando los ejemplos y la casustica que se abordan en el libro con mas enfasis son los que se suscitan en la modelizacion, simulacion y optimizacion de sistemas de energa electrica de generacion, transporte y distribucion, los metodos, tecnicas y algoritmos que se estudian son universalmente aplicables. Si se utilizan como banco de pruebas los problemas que se mencionan, es porque la experiencia profesional no academica del autor se ha desarrollado fun- damentalmente en el sector energetico-electrico (primero en Hidroelectrica Espanola, despues en Iberdrola), donde surgen con asiduidad.
El libro tiene un caracter esencialmente practico. Antes de abordar un procedimiento o algoritmo de calculo para resolver un problema, se estudian con rigor los fundamentos teoricos de lo que se va a proponer, el porque es ventajoso hacerlo de una u otra manera y cuales son los resultados que cabe esperar de las operaciones que hay que llevar a cabo. En la gran mayora de los casos, a todo lo expuesto le acompana un programa de ordenador, codificado en Fortran 77 o 90 y C, el cual se incluye en un CD-ROM que se adjunta al libro, con el fin de que el lector pueda constatar la utilidad de lo expuesto y aplicarlo a algun problema concreto si es el caso. Cuando la complejidad del algoritmo no aconseja listar su codificacion por ser excesivamente larga, se indican cuales son las mejores libreras de software donde se pueden recabar versiones adecuadas o aquellas direcciones de Internet donde se distribuyen programas similares.
Los algoritmos que se listan en las tablas correspondientes utilizan como vehculo de expre- sion un lenguaje muy similar al del software Matlab. Este, ya en su version 5.0, constituye sin duda uno de los instrumentos mas usados y referenciados para ensayar, disenar o inclu- so codificar profesionalmente procedimientos numericos y algoritmos. Una recomendacion que osamos hacer al lector interesado en los asuntos que trata este libro es que estudie en el los
XXIX
XXX Prefacio
fundamentos teoricos de los procedimientos que le interesen y su funcionamiento, y que si en el futuro necesita de su concurso para cualesquiera sean las oportunidades, utilice el software que se incluye en el libro o acuda a Matlab, pues aqu encontrara tratados de forma compacta muchas de las posibilidades que hoy en da se ofrecen numericamente para resolver problemas como los que aborda el libro. Una alternativa aceptable a Matlab es Mathematica. En cualquiera de los casos, si de lo que se trata es construir un programa que resuelva de forma robusta un problema de caractersticas profesionales, lo mejor siempre es disenar su esquele- to trozo a trozo, con herramientas como las que propone el libro, o proporcionan Matlab o Mathematica, y luego codificar de forma optima lo que se sabe que funciona en un lenguaje como Fortran 90 o C, ahorrandose el tratamiento de casustica no necesaria.
El libro se ha escrito con la intencion de dirigirse a personas que deseen poner al da sus conocimientos sobre tecnicas de calculo en ordenador para resolver los problemas que habitualmente surgen de la modelizacion matematica de sistemas fsicos, tecnicos, economicos o sociales: concretamente cuando se obtienen de ellos sistemas de ecuaciones lineales y no lineales, de pequeno y gran tamano, problemas de programacion lineal y problemas de programacion entera o mixtos lineales-enteros, tambien de cualquier dimension. Tambien esta dirigido a alumnos de cursos avanzados de ingeniera, licenciatura, o incluso doctorado, como libro de texto. En la Escuela Tecnica Superior de Ingenieros Industriales de Madrid este libro se utiliza como texto oficial de la asignatura Matematicas de la Especialidad Electricidad-Electrotecnia, en cuarto curso de la carrera.
Como estudiar el libro como texto
La primera parte, Sistemas de ecuaciones, puede constituir gran parte del programa de un curso cuatrimestral sobre tecnicas de calculo numerico para resolver sistemas de ecuaciones lineales y no lineales. Ademas de los tradicionales y mas novedosos procedimientos para llegar a la solucion numerica de sistemas en los que la matriz de coeficientes, o la matriz Jacobiana correspondiente, se guarda y estudia en su totalidad, en esta primera parte tambien se estu- dian los algoritmos necesarios para resolver sistemas de matrices dispersas. En este sentido se abordan todos los problemas anejos que esto representa: la reordenacion de las ecuaciones, las operaciones elementales con matrices dispersas, etc.
La segunda y tercera partes del libro, enfocadas dentro de lo que se conoce como tecnicas de optimizacion y dedicadas a la programacion lineal y a la programacion entera, pueden con- formar el programa idoneo de un curso cuatrimestral sobre tecnicas basicas y avanzadas de metodos y algoritmos de optimizacion lineal (programacion lineal y entera). Lo incluido en estas partes del libro son los procedimientos mas modernos y fiables para resolver programas lineales y enteros, cualesquiera sean sus dimensiones. Ademas de todas las variantes mas utili- zadas del metodo simplex, se estudian en profundidad los algoritmos de puntos interiores mas extendidos: el primal y el dual de escalado afn y los primal-dual. Estos ultimos permiten, con una sustancial ventaja respecto del simplex, resolver problemas de programacion lineal de muy grandes dimensiones en tiempos polinomicos.
Agradecimientos
El producto final que repres