apuntes optimizacion

Apuntes de Optimización
Prof. Juan Carlos Ferrer, Departamento de Ingeniería Industrial y de Sistemas, P.U.C.
Prof. Juan Carlos Muñoz, Departamento de Ingeniería de Transporte, P.U.C.
Marzo 2006

2

Contents
1 Introducción

1

1.1

Introducción al Modelamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.2

¿Qué es un modelo? . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . .

2

1.3

¿Por qué se construyen modelos? . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.4

Modelos de Programación Matemática . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.5

Caracterización de puntos extremos de una función . . . . . . . . . . . . . . . . . . .

5

1.6
1.7

Existencia de soluciónóptima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Problemas Equivalentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6
9

1.7.1

Equivalencia I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

1.7.2

Equivalencia II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.7.3

Equivalencia III. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.7.4

Equivalencia IV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

1.7.5
1.7.6

Equivalencia V . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Equivalencia VI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

1.7.7

Equivalencia VII. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

1.8

Nociones Básicas de Convexidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.8.1
1.8.2

1.9

Conjuntos Convexos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
Funciones Convexas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

1.8.3 Criterios prácticosde convexidad de funciones . . . . . . . . . . . . . . . . . . 31
Problemas resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

2 Programación No lineal
2.1

45

Optimización de una función sin restricciones . . . . . . . . . . . . . . . . . . . . . . 45
2.1.1
2.1.2

2.2

Condiciones Necesarias y suficientes para extremos . . . . . . . . . . . . . . .45
Métodos de búsqueda de soluciones . . . . . . . . . . . . . . . . . . . . . . . . 49

Optimización de una función con restricciones . . . . . . . . . . . . . . . . . . . . . . 54
2.2.1
2.2.2

Caso 2: Restricciones de igualdad . . . . . . . . . . . . . . . . . . . . . . . . . 58

2.2.3
2.3

Caso 1: Problema Unidimensional . . . . . . . . . . . . . . . . . . . . . . . . 54
Caso 3:Restricciones de desigualdad . . . . . . . . . . . . . . . . . . . . . . . 70

Problemas resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
2.3.1

Optimización de una función sin restricciones . . . . . . . . . . . . . . . . . . 79
3

4

CONTENTS
2.3.2

Optimización de una función con restricciones . . . . . . . . . . . . . . . . . . 86

3Programación Lineal
3.1 Introducción . . . . . . . . . . . . . . . . . . . . . .
3.2 El Método Simplex . . . . . . . . . . . . . . . . . .
3.2.1 Pasos en el método Simplex . . . . . . . . .
3.2.2 Solución inicial factible básica . . . . . . . .
3.2.3 Análisis Matricial del Método Simplex . . .
3.2.4 Casos especiales en el desarrollo de Simplex
3.3 Análisis de Sensibilidad de los Resultados . . . . .3.3.1 Rango de variación de los costos . . . . . .
3.3.2 Rango de variación del nivel de recursos . .
3.3.3 Ejemplo . . . . . . . . . . . . . . . . . . . .
3.4 Dualidad . . . . . . . . . . . . . . . . . . . . . . .
3.4.1 Relaciones Primal-Dual . . . . . . . . . . .
3.4.2 Análisis Matricial del problema dual . . . .
3.5 Problemas resueltos . . . . . . . . . . . . . . . . .
3.5.1...