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. Agosto 2006

2

Contents
1 Introducción 1.1 1.2 1.3 1.4 1.5 1.6 1.7 Introducción al Modelamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ¿Qué es un modelo? . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . ¿Por qué se construyen modelos? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Modelos de Programación Matemática . . . . . . . . . . . . . . . . . . . . . . . . . . Caracterización de puntos extremos de una función . . . . . . . . . . . . . . . . . . . Existencia de solución óptima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Problemas Equivalentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.7.1 1.7.2 1.7.3 1.7.4 1.7.5 1.7.6 1.7.7 1.8 1.8.1 1.8.2 1.8.3 1.9 Equivalencia I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 2 3 4 5 6 9 9

Equivalencia II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Equivalencia III . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . 12 Equivalencia IV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 Equivalencia V . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Equivalencia VI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 Equivalencia VII . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22Conjuntos Convexos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 Funciones Convexas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 Criterios prácticos de convexidad de funciones . . . . . . . . . . . . . . . . . . 31

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

Problemas resueltos . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . 34 45

2 Programación No lineal 2.1 2.1.1 2.1.2 2.2 2.2.1 2.2.2 2.2.3 2.3 2.3.1

Optimización de una función sin restricciones . . . . . . . . . . . . . . . . . . . . . . 45 Condiciones Necesarias y suficientes para extremos . . . . . . . . . . . . . . . 45 Métodos de búsqueda de soluciones . . . . . . . . . . . . . . . . . . . . . . . . 49 Caso1: Problema Unidimensional . . . . . . . . . . . . . . . . . . . . . . . . 54 Caso 2: Restricciones de igualdad . . . . . . . . . . . . . . . . . . . . . . . . . 58 Caso 3: Restricciones de desigualdad . . . . . . . . . . . . . . . . . . . . . . . 70 Optimización de una función sin restricciones . . . . . . . . . . . . . . . . . . 79 3

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

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

4 2.3.2

CONTENTS Optimización de una función con restricciones . . . . . . . . . . . . . . . . . . 86 105 . 105 . 112 . 115 . 121 . 126 . 131 . 134 . 134 . 136 . 137 . 138 . 141 . 142 . 144 . 144 . 150 . 166

3 Programació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 Geometría de PL . . . . . . . . . . . . . . . 3.5.2 Método...