metodo de penalizaciom

INVESTIGACIÓN OPERATIVA.
Teoría, Ejercicios y Prácticas con Ordenador

Rosa Rodríguez Huertas

Antonio Gámez Mellado

10 de Septiembre de 2002

2

Índice General
Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

I

TEORÍA

9

11

1 Introducción a la teoría de optimización
1.1 Orígenes y desarrollo . . . . . . . . . . . . . .
1.1.1 Orígenesde la Investigación operativa
1.1.2 La Teoría de Juegos . . . . . . . . . .
1.1.3 La Programación Lineal . . . . . . . .
1.1.4 La Investigación Operativa . . . . . .
1.2 Modelización de un problema de P. L. . . . .
1.2.1 Formulación de los modelos . . . . . .
1.3 Modelización de diversos problemas de I.O. .
1.4 Modelos de programación matemática . . . .
1.5 El método geométrico . . . . .. . . . . . . .
1.5.1 Descripción del método geométrico . .
1.5.2 Resumen del método geométrico . . .

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
..
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

2 Programación Lineal
2.1 Modelo general de programación lineal . . . . . . . . . . . . . . . . .
2.2 Nociones previas . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Definicionessobre las soluciones de un problema . . . . . . . . . . .
2.4 Algunos resultados sobre las soluciones . . . . . . . . . . . . . . . . .
2.5 El algoritmo del Simplex . . . . . . . . . . . . . . . . . . . . . . . . .
2.6 Algoritmo del Simplex en forma de tabla (max) . . . . . . . . . . . .
2.7 Algoritmo del Simplex en forma de tabla (min) . . . . . . . . . . . .
2.8 Búsqueda de solucionesiniciales . . . . . . . . . . . . . . . . . . . . .
2.8.1 Método de las Penalizaciones . . . . . . . . . . . . . . . . . .
2.9 Algoritmo del Simplex en forma matricial . . . . . . . . . . . . . . .
2.9.1 Método del Simplex en forma matricial (caso maximizante) .
2.10 Adaptación algebraica del algoritmo del Simplex . . . . . . . . . . .
2.10.1 Algoritmo del Simplex (enfoque algebraico) . . . . . . . .. .
2.10.2 Método del Simplex en forma de tabla (Usando zj − cj en la
última fila) . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.11 Otros algoritmos de programación lineal . . . . . . . . . . . . . . . .
2.11.1 Método de las dos fases . . . . . . . . . . . . . . . . . . . . .
3

13
13
14
16
16
17
18
19
20
25
26
28
32
33
33
38
39
43
48
51
55
57
62
64
6667
68
72
76
77

4

ÍNDICE GENERAL
2.11.2 Algoritmo revisado del Simplex (Caso maximizante) . . . . .

3 Dualidad en programación lineal
3.1 Formas de la dualidad . . . . . . . . . . . . . . . .
3.1.1 Forma canónica maximizante de la dualidad
3.1.2 Forma estándar maximizante de la dualidad
3.1.3 Reglas para escribir el problema dual . . . .
3.1.4 Forma canónica minimizante de ladualidad
3.2 Propiedades de la relación de dualidad . . . . . . .
3.3 Interpretación económica de la dualidad . . . . . .
3.4 Algoritmo Dual del Simplex. (Caso maximizante) .

79

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
..
.
.
.
.

85
85
85
88
91
92
94
105
107

4 Análisis de sensibilidad
4.1 Introducción gráfica . . . . . . . . . . . . . . . . . . .
4.2 Cambios discretos . . . . . . . . . . . . . . . . . . . .
4.2.1 Variación en un coste de una variable no básica
4.2.2 Variación en un coste de una variable básica . .
4.2.3 Cambios en los recursos . . . . . . . . . . . . .
4.2.4 Cambios en...