Investigacion De Operaciones

´ ´ Formulacion y Resolucion de Modelos ´ ´ de Programacion Matematica en Ingenier´ y Ciencia. ıa

Enrique Castillo, Antonio J. Conejo, Pablo Pedregal, Ricardo Garc´ y Natalia Alguacil ıa 20 de febrero de 2002

DEDICATORIA A Alfonso Fern´ndez Canteli a por su constante animo y apoyo ´

´ Indice General
Prefacio xi

I

Modelos
. . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1
3 3 4 6 9 11 13 15 18 22 25 25 25 27 29 32 35 39 44 47 47 47 47 48 48 50 50

1 Programaci´n lineal o 1.1 Introducci´n . . . . . . . . . . . . . . . . . . . . . o 1.2 El problema del transporte . . . . . . . . . . . . 1.3 El problema de la planificaci´n de la producci´n o o 1.4 Elproblema de la dieta . . . . . . . . . . . . . . 1.5 El problema del flujo en una red . . . . . . . . . 1.6 El problema de la cartera de valores . . . . . . . 1.7 El sistema de vigas y cuerdas . . . . . . . . . . . 1.8 El problema del despacho econ´mico . . . . . . . o Ejercicios . . . . . . . . . . . . . . . . . . . . . .

2 Programaci´n lineal entera-mixta o 2.1 Introducci´n . . . . . . . . . . . .. . . . . . . . . . . o 2.2 El problema de la mochila . . . . . . . . . . . . . . . 2.3 Identificaci´n de s´ o ıntomas relevantes . . . . . . . . . 2.4 El problema de la Academia de Ingenier´ . . . . . . ıa 2.5 El problema del horario . . . . . . . . . . . . . . . . 2.6 Modelos de localizaci´n de plantas productivas . . . o 2.7 Programaci´n de centrales t´rmicas de producci´n de o e o Ejercicios .. . . . . . . . . . . . . . . . . . . . . . . 3 Programaci´n no lineal o 3.1 Introducci´n . . . . . . . . . . o 3.2 Algunos ejemplos geom´tricos e 3.2.1 El paquete postal . . . 3.2.2 La tienda de campa˜a n 3.2.3 La bombilla . . . . . . 3.2.4 La superficie . . . . . 3.2.5 El transporte de arena

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . electricidad . . .. . . .

. . . . . . . v

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

vi 3.3 Algunos ejemplos mec´nicos . . . . . .. a 3.3.1 El voladizo . . . . . . . . . . . . 3.3.2 La estructura de dos barras . . . 3.3.3 La columna sometida a pandeo . 3.3.4 El sistema de vigas y cuerdas . . Algunos ejemplos de ingenier´ el´ctrica ıa e 3.4.1 Estimaci´n de estado en sistemas o 3.4.2 Reparto optimo de carga . . . . ´ El problema de la matriz equilibrada . . El problema de la asignaci´n de tr´fico . o a Ejercicios . . . . . . .. . . . . . . . . .

´ INDICE GENERAL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . el´ctricos e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 51 52 53 54 56 56 58 62 66 69

3.4

3.5 3.6II

M´todos e

73

4 Introducci´n a la programaci´n lineal o o 75 4.1 Introducci´n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 o 4.2 Formulaci´n del problema . . . . . . . . . . . . . . . . . . . . . . 75 o 4.3 Problema de programaci´n lineal en forma est´ndar . . . . . . . 80 o a 4.3.1 Transformaci´n a la forma est´ndar . . . . . . . . . . . . 81 o a 4.4 Solucionesb´sicas . . . . . . . . . . . . . . . . . . . . . . . . . . 83 a 4.5 Sensibilidades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 4.6 Dualidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 4.6.1 Obtenci´n del dual a partir del primal en forma est´ndar 87 o a 4.6.2 Obtenci´n del problema dual . . . . . . . . . . . . . . . . 88 o 4.6.3 Teoremas de dualidad . . . . ....