Variados
Páginas: 114 (28480 palabras)
Publicado: 22 de julio de 2012
´ ´ METODOS DE OPTIMIZACION
´ ´ Jose Manuel Gutierrez
2010
Esta monograf´ se publica en acceso abierto en el Repositorio Cient´ ıa ıfico de la Universidad de Salamanca, de acuerdo a las normas sobre propiedad intelectual acordadas por la Universidad de Salamanca.
PREFACIO
“Quid accedere perfecto potest? nihil, aut perfectum non erat, cui accessit”. (S´neca, Epistolae morales adLucilium, 66) e
La presente monograf´ es una introducci´n a los M´todos de Optimizaci´n, ıa o e o con una selecci´n de material orientada hacia las aplicaciones empresariales. La o exposici´n est´ imbricada con el desarrollo de los elementos de teor´ de la como a ıa putaci´n necesarios para el desarrollo del aspecto algor´ o ıtmico de las matem´ticas. a El contenido propiamente de optimizaci´n secentra en la optimizaci´n lineal. o o El lector puede quiz´s criticar lo inusual del tratamiento, en un libro introductorio a como ´ste. En el caso del m´todo del s´ e e ımplex, se parte de la sencilla idea de desarrollar el m´todo del s´ e ımplex como caso particular de los m´todos de direcciones e de mejora. El autor quiere agradecer a su colega Jos´ Manuel Casc´n los comentarios e o aportados, ysu generosa disposici´n a hacerse cargo de la edici´n final del texto. o o
1
2
´ Indice
1. PRIMERA PARTE: NOCIONES SOBRE TEOR´ DE LA COMIA ´ PUTACION 5 1. Algunos conceptos b´sicos de computaci´n . . . . . . . . . . . . . . . . a o 5 1.1. Algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2. Arquitectura de un ordenador . . . . . . . . . . . . . . . . 6 1.3. Lenguajes. . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2. Programaci´n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o 8 2.1. Instrucciones . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2. Instrucciones de asignaci´n . . . . . . . . . . . . . . . . . . o 9 2.3. Instrucciones de secuenciaci´n . . . . . . . . . . . . . . . . 10 o 2.4. Instrucciones alternativas . . . . .. . . . . . . . . . . . . . 12 2.5. Instrucciones repetitivas . . . . . . . . . . . . . . . . . . . 13 2.6. Instrucciones de entrada y salida . . . . . . . . . . . . . . 16 2.7. Subrutinas . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.8. Variables matriciales . . . . . . . . . . . . . . . . . . . . . 17 2.9. Ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.Eficiencia y complejidad . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.1. Eficiencia . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.2. Complejidad . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4. Ejercicios sobre computaci´n . . . . . . . . . . . . . . . . . . . . . . . . 35 o ´ 2. SEGUNDA PARTE: METODOS DE MEJORA 1. Generalidades sobre optimizaci´n . . . . . . . . . . . . o1.1. Introducci´n . . . . . . . . . . . . . . . . . o 1.2. Resultados generales . . . . . . . . . . . . 2. M´todos de mejora . . . . . . . . . . . . . . . . . . . . e 2.1. M´todos de mejora . . . . . . . . . . . . . e 2.2. Algoritmo de mejora simple . . . . . . . . 2.3. M´todos de direcciones de mejora . . . . . e 3 39 39 39 41 42 42 43 45
. . . . . . .
. . . . . . .
. . . . . . .
. .. . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
3. El algoritmo del s´ ımplex . . . . . . . . . . . . . . . 3.1. El problema de optimizaci´n lineal . . o 3.2. Preliminares . . . . . . . . . . . . . . . 3.3. Fundamentos del m´todo del s´ e ımplex . 3.4. Ejecuci´n de la mejora . . . . . . . . . o 3.5. M´todo del s´ e ımplex . . . . . . . . . . .3.6. Cuestiones de eficiencia y complejidad 4. Flujos en redes . . . . . . . . . . . . . . . . . . . . 4.1. Conceptos generales . . . . . . . . . . 4.2. Problemas cl´sicos . . . . . . . . . . . a 5. Planificaci´n de actividades . . . . . . . . . . . . . o 5.1. Introducci´n . . . . . . . . . . . . . . . o 5.2. El CPM . . . . . . . . . . . . . . . . . 5.3. El CPS . . . . . . . . . . . . . . . . . 6....
´ ´ Jose Manuel Gutierrez
2010
Esta monograf´ se publica en acceso abierto en el Repositorio Cient´ ıa ıfico de la Universidad de Salamanca, de acuerdo a las normas sobre propiedad intelectual acordadas por la Universidad de Salamanca.
PREFACIO
“Quid accedere perfecto potest? nihil, aut perfectum non erat, cui accessit”. (S´neca, Epistolae morales adLucilium, 66) e
La presente monograf´ es una introducci´n a los M´todos de Optimizaci´n, ıa o e o con una selecci´n de material orientada hacia las aplicaciones empresariales. La o exposici´n est´ imbricada con el desarrollo de los elementos de teor´ de la como a ıa putaci´n necesarios para el desarrollo del aspecto algor´ o ıtmico de las matem´ticas. a El contenido propiamente de optimizaci´n secentra en la optimizaci´n lineal. o o El lector puede quiz´s criticar lo inusual del tratamiento, en un libro introductorio a como ´ste. En el caso del m´todo del s´ e e ımplex, se parte de la sencilla idea de desarrollar el m´todo del s´ e ımplex como caso particular de los m´todos de direcciones e de mejora. El autor quiere agradecer a su colega Jos´ Manuel Casc´n los comentarios e o aportados, ysu generosa disposici´n a hacerse cargo de la edici´n final del texto. o o
1
2
´ Indice
1. PRIMERA PARTE: NOCIONES SOBRE TEOR´ DE LA COMIA ´ PUTACION 5 1. Algunos conceptos b´sicos de computaci´n . . . . . . . . . . . . . . . . a o 5 1.1. Algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2. Arquitectura de un ordenador . . . . . . . . . . . . . . . . 6 1.3. Lenguajes. . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2. Programaci´n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o 8 2.1. Instrucciones . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2. Instrucciones de asignaci´n . . . . . . . . . . . . . . . . . . o 9 2.3. Instrucciones de secuenciaci´n . . . . . . . . . . . . . . . . 10 o 2.4. Instrucciones alternativas . . . . .. . . . . . . . . . . . . . 12 2.5. Instrucciones repetitivas . . . . . . . . . . . . . . . . . . . 13 2.6. Instrucciones de entrada y salida . . . . . . . . . . . . . . 16 2.7. Subrutinas . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.8. Variables matriciales . . . . . . . . . . . . . . . . . . . . . 17 2.9. Ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.Eficiencia y complejidad . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.1. Eficiencia . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.2. Complejidad . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4. Ejercicios sobre computaci´n . . . . . . . . . . . . . . . . . . . . . . . . 35 o ´ 2. SEGUNDA PARTE: METODOS DE MEJORA 1. Generalidades sobre optimizaci´n . . . . . . . . . . . . o1.1. Introducci´n . . . . . . . . . . . . . . . . . o 1.2. Resultados generales . . . . . . . . . . . . 2. M´todos de mejora . . . . . . . . . . . . . . . . . . . . e 2.1. M´todos de mejora . . . . . . . . . . . . . e 2.2. Algoritmo de mejora simple . . . . . . . . 2.3. M´todos de direcciones de mejora . . . . . e 3 39 39 39 41 42 42 43 45
. . . . . . .
. . . . . . .
. . . . . . .
. .. . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
3. El algoritmo del s´ ımplex . . . . . . . . . . . . . . . 3.1. El problema de optimizaci´n lineal . . o 3.2. Preliminares . . . . . . . . . . . . . . . 3.3. Fundamentos del m´todo del s´ e ımplex . 3.4. Ejecuci´n de la mejora . . . . . . . . . o 3.5. M´todo del s´ e ımplex . . . . . . . . . . .3.6. Cuestiones de eficiencia y complejidad 4. Flujos en redes . . . . . . . . . . . . . . . . . . . . 4.1. Conceptos generales . . . . . . . . . . 4.2. Problemas cl´sicos . . . . . . . . . . . a 5. Planificaci´n de actividades . . . . . . . . . . . . . o 5.1. Introducci´n . . . . . . . . . . . . . . . o 5.2. El CPM . . . . . . . . . . . . . . . . . 5.3. El CPS . . . . . . . . . . . . . . . . . 6....
Leer documento completo
Regístrate para leer el documento completo.