Investigación de Operaciones

´ n y Resolucio
´ n de Modelos
Formulacio
´ n Matema
´tica
de Programacio
en Ingenier´ıa y Ciencia.

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

DEDICATORIA
A Alfonso Fern´andez Canteli
por su constante a´nimo y apoyo

´Indice General
Prefacio

I

xi

Modelos

1

1 Programaci´
on lineal
1.1 Introducci´
on . . . . . . . . . . .. . . . . . . . . .
1.2 El problema del transporte . . . . . . . . . . . .
1.3 El problema de la planificaci´
on de la producci´
on
1.4 El problema 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´
omico . . .. . . .
Ejercicios . . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.

3
3
4
6
9
11
13
15
18
22

2 Programaci´
on lineal entera-mixta
2.1 Introducci´
on . . . . . . . . . . . . . . . . . . . . . . .
2.2 El problema de la mochila . . . . . . . . . . . . . . .
2.3 Identificaci´
on de s´ıntomas relevantes . . . . . . . . .
2.4 El problema de la Academia de Ingenier´ıa . . . . . .
2.5 Elproblema del horario . . . . . . . . . . . . . . . .
2.6 Modelos de localizaci´on de plantas productivas . . .
2.7 Programaci´
on de centrales t´ermicas de producci´on de
Ejercicios . . . . . . . . . . . . . . . . . . . . . . . .

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

25
25
25
27
29
32
35
39
44

3 Programaci´
on no lineal
3.1Introducci´
on . . . . . . . . . .
3.2 Algunos ejemplos geom´etricos
3.2.1 El paquete postal . . .
3.2.2 La tienda de campa˜
na
3.2.3 La bombilla . . . . . .
3.2.4 La superficie . . . . .
3.2.5 El transporte de arena

.
.
.
.
.
.
.

47
47
47
47
48
48
50
50

.
.
.
.
.
.
.
v

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
..
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

´INDICE GENERAL

vi
3.3

3.4

3.5
3.6

II

Algunos ejemplos mec´anicos . . . . . . .
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´ıa el´ectrica
3.4.1 Estimaci´
on de estado en sistemas
3.4.2 Reparto o´ptimo de carga . . . .
El problema de la matriz equilibrada . .
El problema de la asignaci´
on de tr´
afico .
Ejercicios . . . . . . . . . . . . . . . . .

. .. . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
el´ectricos
. . . . . .
. . . . . .
. . . . . .
. . . . . .

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

M´
etodos

51
51
52
53
54
56
56
58
62
66
69

73

4 Introducci´
on a la programaci´
onlineal
75
4.1 Introducci´
on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.2 Formulaci´
on del problema . . . . . . . . . . . . . . . . . . . . . . 75
4.3 Problema de programaci´
on lineal en forma est´
andar . . . . . . . 80
4.3.1 Transformaci´
on a la forma est´
andar . . . . . . . . . . . . 81
4.4 Soluciones b´
asicas . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.5Sensibilidades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
4.6 Dualidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
4.6.1 Obtenci´
on del dual a partir del primal en forma est´
andar 87
4.6.2 Obtenci´
on del problema dual . . . . . . . . . . . . . . . . 88
4.6.3 Teoremas de dualidad . . . . . . . . . . . . . . . . . . . . 89
Ejercicios . . . . . . . . . . ....