Optimizacion Lineal - No Lineal 6n701c

OPTIMIZACIÓN LINEAL Y NO LINEAL 4º INGENIERÍA INDUSTRIAL CURSO 2003-2004 Profesores: Fco. Javier Faulin y María Luisa Eraso Departamento de Estadística e Investigación Operativa Universidad Pública de Navarra Objetivos: En esta asignatura se estudian algunos modelos y métodos de la Investigación Operativa que ayudan a determinar la mejor estrategia de actuación, con el fin de mejorar el funcionamiento de un sistema industrial. El alumno será capaz de reconocer distintos problemas en el contexto de la Ingeniería Industrial, plantear dichos problemas mediante modelos de programación matemática, resolverlos utilizando programas informáticos de optimización, así como interpretar y valorar los resultados. Prácticas: Los modelos que se estudian en esta asignatura se ilustrarán con ejemplos prácticos y con la discusión de situaciones reales en el contexto de la Ingeniería Industrial. Parte de la asignatura se dedicará a la realización de prácticas de ordenador en las que el alumno aprenderá a utilizar paquetes informáticos de optimización. Criterios de Evaluación: La evaluación de la asignatura se realizará mediante un examen final teóricopráctico con la ayuda del ordenador. Además, se valorará la realización de trabajos durante el curso.

1

ÍNDICE DE LOS TEMAS Tema 1: Introducción a las Técnicas de Optimización. -

Técnicas de Optimización e Investigación Operativa. Aspectos históricos. Modelos matemáticos. Clasificación de las técnicas de optimización. Nociones sobre algoritmos.

Tema 2: Fundamentos Matemáticos de la Programación Lineal. -

Formulación general y estandar de un problema de programación lineal. Soluciones Factibles Básicas. Teorema fundamental de la programación lineal. Conjuntos convexos. Puntos extremos y direcciones extremas. Teoremas de caracterización y de representación. La optimalidad en programación lineal. La noción de algoritmo.

Tema 3: Introducción a la Programación Lineal. -

Introducción. Formulación de problemas. Hipótesis asumidas por la programación lineal. Formulaciones alternativas de un problema de programación lineal. Resolución gráfica de problemas con dos y tres variables. Solución única, soluciones alternativas, no acotación e infactibilidad.

Tema 4: Método del Simplex. - Puntos extremos adyacentes. Regla para la variable que deja la base. - Mejora de una solución factible básica. Regla de entrada en la base. Criterio de optimalidad y de no acotación. - Obtención de la primera solución factible básica. Variables de holgura y variables artificiales. - Método de penalización. Problemas infactibles. - Método del simplex en forma de tabla.

2

Tema 5: Dualidad. - Introducción a la dualidad. Ejemplo. Obtención del problema dual. - Definición de problema dual en general. - Propiedades de los problemas duales. Teorema fundamental de la dualidad. Teorema de la holgura complementaria. - Interpretación económica de la dualidad. - El algoritmo dual del simplex.

Tema 6: Análisis Postóptimo y Programación Paramétrica. - Introducción. Importancia del análisis postoptimal. - Cambios en la disponibilidad de recursos, en el vector de costos y en los coeficientes tecnológicos. - Adición de una variable. Adición de una restricción. - Programación paramétrica.

Tema 7: Problemas de Transporte. - El problema del transporte. Propiedades de la matriz de coeficientes tecnológicos. - El algoritmo del transporte. - Problema de Transbordo. - Problema de asignación. Algoritmo Húngaro.

Tema 8: Programación Entera. - Introducción a la programación lineal entera. Técnicas de resolución. - Método Branch and Bound. - Formulación de problemas de P.L.E. Aplicaciones.

Tema 9: Programación Multiobjetivo. -

Introducción a la programación multiobjetivo. Ejemplos. Solución eficiente y conjunto eficiente. Método gráfico. Métodos generadores: método de las ponderaciones, método de las ε-

restricciones, método simplex multiobjetivo. - Programación por metas y programación por compromiso. - Introducción a los métodos interactivos.

3

Tema 10: Optimización No Lineal sin restricciones. -

Introducción a la programación no lineal. Ejemplos. Condiciones para la optimalidad de primer y segundo orden. Optimización de funciones convexas. Métodos de descenso. Búsqueda lineal. Otros métodos.

Tema 11: Optimización No Lineal con restricciones. - Restricciones de igualdad: Condiciones para la optimalidad de primer orden y de segundo orden. Interpretación económica de los multiplicadores de Lagrange. Método del gradiente reducido. Otros métodos. - Restricciones de desigualdad: Condiciones para la optimalidad de primer orden y de segundo orden. Interpretación económica de los multiplicadores de Lagrange. Métodos generales de resolución. - Problemas con estructura especial: Programación lineal fraccional, cuadrática, separable y geométrica.

Tema 12: Aplicaciones y Paquetes Informáticos de Optimización. - La Investigación Operativa y la Ingeniería Industrial. - Análisis de casos reales. - QSB; LINDO; LINGO; ADBASE.

4

Bibliografía Básica ANDERSON, D.; SWEENEY, D.; WILLIAMS, T. (1997): “An introduction to Management Science: quantitative approaches to decision making”, West Publishing Company, 8ª Ed. AVRIEL, M.; GOLANY. B. (Eds.) (1996): "Mathematical Programming for Industrial Engineers", Dekker. BAZARAA, M.S.; SHERALI, H.D.; SHETTY, C.M. (1993): "Nonlinear Programming. Theory and Algorithms", Wiley, 2ª Ed. HILLIER, F.S.; LIEBERMAN, G.J. (2002): "Introducción a la investigación de operaciones". McGraw Hill. 7ª Ed. LAWRENCE, A.L. y PASTERNACK, B.A. (2002): “Applied Management Science. A Computer Integrated Approach for Decision Making”. Ed. Wiley. LUENBERGER, D. E. (1989): "Programación Lineal y no Lineal". Addison-Wesley Iberoamericana. OZAN, T. M. (1986): "Applied Mathematical Programming for Production and Engineering Management". Prentice Hall. RIOS INSUA, S. (1988): "Investigación Operativa. Optimización". Centro de Estudios Ramón Areces. ROMERO, C. (1993): "Teoría de la decisión multicriterio: conceptos, técnicas y aplicaciones". Alianza Editorial. TAHA, H.A. (1992): “Operations Research. An Introduction. McMillan Publishing Company”. (Existe versión en español) WINSTON, W.L. (1994): "Investigación de operaciones. Aplicaciones y algoritmos". Grupo Editorial Iberoamérica. 2ª Ed. (versión original en inglés del año 1991).

5