Investigacion operativa para ing

Pilar Tormos Juan Antonio Lova Ruiz

INVESTIGACIÐN OPERATIVA PARA INGENIEROS

EDITORIAL UNIVERSITAT POLITÈCNICA DE VALÈNCIA

Primera edición 2003 Ȼ Reimpresión, 2016

© Pilar Tormos Juan Antonio Lova Ruiz

© 2003 de la presente edición: Editorial Universitat Politècnica de València

Distribución: Telf. 963 877 012 / www.lalibreria.upv.es / Ref. 0591B02B01B03

Imprime: Byprint Percom, sl.

Depósito Legal: V 3439 2003 ISBN: 978.84.9705.430.0

Queda prohibida la reproducción, la distribución, la comercialización, la transformación y, en general, cualquier otra forma de explotación, por cualquier procedimiento, de la totalidad o de cualquier parte de esta obra sin autorización expresa y por escrito de los autores.

Impreso en España

ÍNDICE

1. INTRODUCCIÓN A LA INVESTIGACIÓN OPERATIVA ...................... 5

1.1. LA TOMA DE DECISIONES................................................................... 7

1.2. RESEŃA HISTÓRICA DE LA INVESTIGACIÓN OPERATIVA ............. 7

1.3. DEFINICIÓN DE INVESTIGACIÓN OPERATIVA.................................. 10 1.4. CARACTERÍSTICAS DE LA INVESTIGACIÓN OPERATIVA............... 11

1.5. TÉCNICAS DE INVESTIGACIÓN OPERATIVA: APLICACIONES....... 12

1.6. FASES DE LA APLICACIÓN DE LAS TÉCNICAS DE

INVESTIGACIÓN OPERATIVA.............................................................. 16

1.7. LA INGENIERÍA INFORMÁTICA Y LA INVESTIGACIÓN

OPERATIVA ........................................................................................... 22 1.8. BIBLIOGRAFÍA ...................................................................................... 23

ANEXO 1: ANTECEDENTES DE LA INVESTIGACIÓN OPERATIVA ........ 24

2. FORMULACIÓN DE MODELOS .............................................................. 31

2.1. DEFINICIÓN DE MODELO..................................................................... 33 2.2. FORMA GENERAL DE UN MODELO MATEMÁTICO.......................... 33 2.3. MODELOS MATEMÁTICOS: CLASIFICACIÓN.................................... 35 2.4. RECOMENDACIONES PARA LA FORMULACIÓN DE MODELOS .... 36 2.5. ALGUNOS MODELOS........................................................................... 37 2.6. BIBLIOGRAFÍA ...................................................................................... 40 2.7. CASOS PRÁCTICOS ............................................................................. 41 ANEXO 1: INVESTIGACIÓN OPERATIVA: ENTREVISTA CON

GEORGE B. DANTZIG.............................................................. 43

3. CONCEPTOS BÁSICOS DE PROGRAMACIÓN LINEAL: EL

MÉTODO GRÁFICO................................................................................... 45

3.1. EJEMPLO PROTOTIPO: UN PROBLEMA DE PRODUCCIÓN ........... 47 3.1.1. VARIABLES..................................................................................... 47 3.1.2. FUNCIÓN OBJETIVO Y RESTRICCIONES........................................ 48

3.2. REGIÓN FACTIBLE Y SOLUCIÓN GRÁFICA ...................................... 50 3.3. VARIABLES DE HOLGURA ................................................................. 54 3.4. ANÁLISIS DE SENSIBILIDAD ............................................................... 56 3.4.1. A.S. COEFICIENTES DE LA FUNCIÓN OBJETIVO (Ci) ...................... 56 3.4.2. A.S. VECTOR RECURSOS (bi) ......................................................... 59

INVESTIGACIÓN OPERATIVA PARA INGENIEROS

2

3.5. RESOLUCIÓN DE MODELOS CON EL SOFTWARE DE

OPTIMIZACIÓN LINGO ....................................................................... 62 3.6. BIBLIOGRAFÍA ................................................................................... 63 3.7. EJERCICIOS PROPUESTOS .............................................................. 64 3.8. CASOS PRÁCTICOS .......................................................................... 66

4. SOLUCIÓN DE PROBLEMAS DE PROGRAMACIÓN LINEAL:

MÉTODO SIMPLEX ............................................................................ 69

4.1. CONCEPTOS BÁSICOS DE PROGRAMACIÓN LINEAL .................. 71 4.2. SOLUCIÓN: CONCEPTOS IMPORTANTES....................................... 74 4.3. EL MÉTODO SIMPLEX: CONCEPTOS BÁSICOS ............................. 76 4.4. EL MÉTODO SIMPLEX MEDIANTE ECUACIONES

SIMULTÁNEAS .................................................................................... 77 4.5. CRITERIOS DEL MÉTODO SIMPLEX: VARIABLE QUE ENTRA

Y VARIABLE QUE SALE DE LA BASE.............................................. 82 4.6. EL MÉTODO SIMPLEX EN FORMA DE TABLAS.............................. 84 4.7. ALGORITMO SIMPLEX REVISADO ................................................... 89 4.8. ADAPTACIÓN A OTRAS FORMAS DE MODELO: VARIABLES

ARTIFICIALES ..................................................................................... 100 4.8.1. MÉTODO SIMPLEX PENAL O DE LA ‘M’ GRANDE......................... 101 4.8.2. MÉTODO DE LAS 2 FASES........................................................... 107 4.8.3. COMPARACIÓN ENTRE EL MÉTODO DE LA M Y DE LAS 2

FASES.......................................................................................... 113

4.9. REDUCCIÓN DEL ESFUERZO COMPUTACIONAL: TÉCNICA

DE LAS COTAS ................................................................................... 114 4.9.1. TÉCNICA DE LA COTA INFERIOR.................................................. 115 4.9.2. TÉCNICA DE LA COTA SUPERIOR ................................................ 117 4.10. SITUACIONES ESPECIALES EN LA TABLA SIMPLEX.................... 125

4.11. OTROS ALGORITMOS DE PROGRAMACIÓN LINEAL .................... 126 4.11.1. COMPARACIÓN CON EL MÉTODO SIMPLEX .............................. 128 4.12. LA PROGRAMACIÓN LINEAL Y EL SOFTWARE DE

OPTIMIZACIÓN.................................................................................... 128

4.13. BIBLIOGRAFÍA .................................................................................... 130

4.14. CASOS PRÁCTICOS ........................................................................... 130

5. DUALIDAD Y ANÁLISIS DE SENSIBILIDAD ........................................ 137

5.1. INTRODUCCIÓN .................................................................................... 139

5.2. EL PROBLEMA DUAL Y LAS RELACIONES DE DUALIDAD............. 141

ÍNDICE5.3. INTERPRETACIÓN ECONÓMICA DE LAS VARIABLES DUALES EN EL ÓPTIMO....................................................................................... 143 5.4. ALGORITMO SIMPLEX DUAL .............................................................. 144 5.5. ANÁLISIS POST0ÓPTIMO..................................................................... 147 5.6. ANÁLISIS DE SENSIBILIDAD............................................................... 148

5.6.1 ANÁLISIS DE SENSIBILIDAD DE COEFICIENTES DE LA

FUNCIÓN OBJETIVO..................................................................... 150 5.6.2 ANÁLISIS DE SENSIBILIDAD DE SEGUNDOS MIEMBROS DE

LAS RESTRICCIONES................................................................... 153 5.6.3 INTRODUCCIÓN DE UNA NUEVA VARIABLE................................. 156

5.7. PROGRAMACIÓN PARAMÉTRICA...................................................... 158

5.7.1 PROGRAMACIÓN PARAMÉTRICA DE COEFICIENTES EN LA

FUNCIÓN OBJETIVO..................................................................... 158 5.7.2 PROGRAMACIÓN PARAMÉTRICA DEL SEGUNDO MIEMBRO

DE LAS RESTRICCIONES.............................................................. 162

5.8. BIBLIOGRAFÍA...................................................................................... 168

5.9. CASOS PRÁCTICOS............................................................................. 168

6. PROGRAMACIÓN ENTERA..................................................................... 175

6.1. INTRODUCCIÓN .................................................................................... 177 6.2. UN PROBLEMA ENTERO SENCILLO .................................................. 178 6.3. ALGUNAS APLICACIONES DE PROGRAMACIÓN ENTERA............. 179 6.4. TÉCNICAS DE PROGRAMACIÓN ENTERA: ALGORITMO DE

BIFURCACIÓN Y ACOTACIÓN............................................................. 182 6.4.1. INTRODUCCIÓN.............................................................................. 182 6.4.2. RESOLUCIÓN GRÁFICA.................................................................. 183 6.4.3. RESOLUCIÓN ALGEBRAICA............................................................ 188 6.4.4. CRITERIOS DE SELECCIÓN DEL NODO A BIFURCAR..................... 193 6.4.5. CRITERIOS DE SELECCIÓN DE LA VARIABLE A ACOTAR............... 194

...