Investigacion de operaciones

Introduccion a la Investigacion de Operaciones

2

´ INDICE

3

´ Indice
1. Introducci´n o 2. La Investigaci´n Operativa o 2.1. El modelado en Investigaci´n Operativa o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 6 7 9 9 9 15 16 1822 23 24 27 28 29 32 32 34 36 40 42 43 43 44 44 46 47 52 53 54 56 59 59 59 60 60 61 62 62 63

3. Programaci´n Lineal o 3.1. Hip´tesis de la Programaci´n Lineal . . . . . . . . . . . . . o o 3.2. Ejemplos de modelado de sistemas en Programaci´n Lineal o 3.3. Forma can´nica del problema de Programaci´n Lineal . . . o o 3.4. Variables de Holgura. Forma Aumentada . . . . . . . . . . 3.5.Interpretaci´n geom´trica. Conjuntos Convexos . . . . . . o e 3.6. Algoritmo Simplex B´sico . . . . . . . . . . . . . . . . . . a 3.6.1. Soluciones Factibles y B´sicas . . . . . . . . . . . . a ´ 3.6.2. Algebra del Algoritmo Simplex . . . . . . . . . . . 3.6.3. Forma tabular . . . . . . . . . . . . . . . . . . . . . 3.6.4. Situaciones especiales . . . . . . . . . . . . . . . . . 3.6.5. Introducci´n al An´lisisPos´ptimo . . . . . . . . . o a o 3.7. Modificaciones del algoritmo Simplex . . . . . . . . . . . . 3.7.1. Formas no can´nicas. Variables artificiales . . . . . o 3.7.2. M´todo de Penalizaci´n o de la M . . . . . . . . . . e o 3.7.3. M´todo de las dos fases . . . . . . . . . . . . . . . . e 3.7.4. Algoritmo Simplex Revisado . . . . . . . . . . . . . 3.7.5. Algoritmo Simplex Lexicogr´fico . . . . . .. . . . . a 3.8. Otras Casos Reducibles . . . . . . . . . . . . . . . . . . . . 3.8.1. Optimizaci´n con M´ltiples Objetivos . . . . . . . . o u 3.8.2. Objetivos Lineales por Tramos . . . . . . . . . . . . 3.9. Teor´ de la Dualidad . . . . . . . . . . . . . . . . . . . . . ıa 3.9.1. Forma can´nica de los problemas Primal/Dual . . . o 3.9.2. Relaciones entre las variables y soluciones Duales .3.9.3. Algoritmo Simplex Dual . . . . . . . . . . . . . . . 3.10. An´lisis Pos´ptimo . . . . . . . . . . . . . . . . . . . . . . a o 3.10.1. An´lisis de la Sensibilidad . . . . . . . . . . . . . . a 3.10.2. Programaci´n Lineal Param´trica . . . . . . . . . . o e 4. Programaci´n Entera o 4.1. Modelado con variables enteras . . . . . . . 4.1.1. Problema de la Mochila . . . . . . . 4.1.2. Problema de losCostes Fijos . . . . . 4.1.3. Problema de Cobertura de Conjuntos 4.1.4. Restricciones O-Bien . . . . . . . . . 4.1.5. K de N restricciones . . . . . . . . . 4.1.6. Funci´n de N valores posibles . . . . o 4.1.7. Restricciones Si-Entonces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

´ INDICE4.2. Algoritmo de los Planos de Corte . . . . . . . . . . . . . . . . . . . . . . 4.3. Algoritmo de Bifurcaci´n y Acotaci´n . . . . . . . . . . . . . . . . . . . . o o 63 64 65 65 67 69 69 72 75 78 81 81 84 85 86 88 90 93 94 99 99 100 102 104 105 106 106 113 117 118 120 121 121 122 123 125 127

5. Introducci´n a la Programaci´n No Lineal o o 5.1. An´lisis de Funciones . . . . . . . . . . . . . . .. . . . . a 5.2. Problemas con una Variable. B´squeda Dicot´mica . . . u o 5.3. Problemas con M´ltiples Variables . . . . . . . . . . . . u 5.3.1. Problema sin Restricciones. M´todo del Gradiente e 5.3.2. Problemas con Restricciones. Condiciones KKT . 5.3.3. Programaci´n Cuadr´tica . . . . . . . . . . . . . o a 5.3.4. Ajuste de Curvas. Casos linealizables. . . . . . . . 6. Problemas del...