Página principal

Investigación Operativa I


Descargar 35.13 Kb.
Fecha de conversión18.07.2016
Tamaño35.13 Kb.

Investigación Operativa I


Carrera/Plan:

Licenciatura en Informática Plan 90

Licenciatura en Informática

Plan 2003/07

Licenciatura en Sistemas

Plan 2003/07

APU Plan 2007

Año 2012


Año: 4to,5to.



Régimen de Cursada : Semestral ( 1º.)




Carácter: Optativa




Correlativas: Análisis Matemático II, Algebra Lineal, Matemática III.




Profesor a Cargo: Nélida Echebest




Hs. Semanales: 6 hs.



FUNDAMENTACIÓN
La Investigación de Operaciones es un conjunto de técnicas matemáticas que permiten brindar criterios objetivos para decidir analíticamente sobre situaciones que requieren optimizar resol-tados en diversas áreas del conocimiento y con aplicaciones a la industria, economía, etc.


OBJETIVOS GENERALES


Capacitar al alumno para modelizar y resolver distintos problemas utilizando técnicas de la Investigación Operativa tales como: Programación Lineal y Programación Entera, así como aprender los fundamentos de dichas técnicas. Introducir al alumno en el uso de métodos determinísticos y análisis de sensibilidad y postoptimalidad.



CONTENIDOS MINIMOS


  • Introducción a la Investigación Operativa (I.O.). Principios de Modelización.

  • Modelos de programación lineal y aplicaciones. Formulación de modelos en programación lineal y aplicaciones. Resolución gráfica e interpretación.

  • Fundamentos del método del simplex. Indicadores del simplex. Método del símplex. Consideraciones prácticas.Dualidad y Análisis de sensibilidad. Relaciones en dualidad. Algoritmo del símplex dual. Cambios discretos.

  • Problemas de transporte y asignación. Modelos especiales en programación lineal. Modelos de transporte. Modelos de asignación.

  • Análisis de redes de flujo. Problemas del camino crítico. Redes de proyectos (CPM). Flujo en redes.

 


PROGRAMA ANALÍTICO
1.- Introducción a problemas de Programación Lineal.

Problemas que pueden modelarse como un problema de Programación Lineal.

Formulaciones.

2.- Resultados de Álgebra Lineal y Análisis Convexo.

Soluciones básicas. Bases factibles. Conjuntos Convexos. Funciones convexas.

Conjuntos y conos poliédricos. Teorema de Representación.

3.- Programación Lineal. Definiciones y Resultados Fundamentales

Forma estándar del problema de Programación Lineal. El conjunto de soluciones y

su relación con los poliedros convexos. Caracterización algebraica de los puntos

extremos. Teorema de optimalidad en un punto extremo o existencia de soluciones

no acotadas. Caracterización de bases factibles y soluciones básicas optimales.

4.- Resolución del problema de Programación Lineal

El algoritmo Primal Simples. Condiciones para la Convergencia finita.

Problemas con regeneramiento. Reglas para evitar el regeneramiento.

Determinación de la existencia de solución. Búsqueda de una solución inicial. El

Método de las dos Fases. Complejidad algorítmica. Simplex revisado.

Condiciones de optimalidad: la condición de Karush-Kuhn-Tucker y su relación

con el método Simplex.

5.- Teoría de Dualidad

Formulación del Problema Dual.Relación entre el problema Primal y Dual.

Condiciones de Holgura Complementaria.

Condición de Karush-Kuhn-Tucker y su relación con las variables del Problema

Dual- Variables duales y costos marginales. Interpretación económica del Dual.

Método Dual Simplex. Método Primal- Dual.

Análisis de Sensibilidad y Post-optimalidad.

6.- Introducción a Métodos de Punto Interior.

Centro Analítico. El camino central. Estrategias de Resolución.

7.- El Problema de Transporte

Definición del problema- Propiedades de la matriz de restricciones- El método

Simplex para el Problema de Transporte. El problema de Asignación.

8.- Flujo en Redes. Definiciones básicas de la teoría de grafos- Matrices asociadas a

un grafo. Grafos asociados a algunos problemas especiales.

El problema del camino más corto en un grafo. Definiciones. Condiciones de

Optimalidad. Algoritmos.

El Problema de Flujo Máximo en una red de Transporte. El algoritmo de caminos

aumentables. Teorema del Flujo Máximo y corte de capacidad mínima.

Corte de Capacidad Mínima. Su relación con el problema dual.

Flujo Máximo con costo Mínimo. Algoritmo Simplex. Algoritmo Primal- Dual

Convergencia. Complejidad. Administración de proyectos por análisis de Redes.

Camino Crítico

9.- Introducción a Programación Lineal Entera. Relajación y desigualdades válidas.

Algoritmos de corte. Método Branch and Bound.



METODOLOGÍA DE ENSEÑANZA

Cantidad de horas de clase Teórico- Prácticas: 6

Práctica en Laboratorio de Computación: 3 horas

Período: primer semestre (16 semanas de clase).

Metodología : Durante las clases el profesor desarrolla todos los temas básicos de la asignatura. Se complementa con actividades prácticas que motiven a los alumnos a ejercitarse en los conceptos y algoritmos desarrollados. Preparación de seminarios por parte de los alumnos. Entrega periódica y exposición de problemas propuestos. Además, los alumnos, con el soporte de un software de Optimización y rutinas de la asignatura practican y analizan las técnicas numéricas estudiadas, poniendo énfasis especial en la temática de su mayor interés.
EVALUACIÓN

Aprobación por promoción: Los alumnos deben completar y entregar en forma satisfactoria los trabajos solicitados a lo largo del curso. Preparación de seminarios por parte de los alumnos. Entrega periódica y exposición de problemas propuestos.

Evaluaciones: Un examen parcial, seguido de la aprobación de un trabajo final sobre uno de los temas de la asignatura. Los alumnos deben preparar y exponer satisfactoriamente el trabajo monográfico sobre un tema especial del curso (extensiones de temas desarrollados y/o análisis de de trabajos recientemente publicados).
BIBLIOGRAFÍA OBLIGATORIA

1.- Bazaraa M., Jarvis J., Sherali J.. Linear Programming and Networks Flows, John Wiley & Son, 1990. Spanish version: Limusa- Noriega Editores (México), 1993.


2. Bazaraa, Mokhtar S., "Programacion lineal y flujo en redes", Mexico Limusa 1998
3.- Gondran, Minoux. Graphs and Algorithms. John Wiley & Son, 1984.
4.- Hillier, Frederick S., "Investigación de operaciones", Madrid[etc.] McGraw-Hill imp.2001


BIBLIOGRAFÍA COMPLEMENTARIA
1.- Gonzaga Clovis. Path – Following Methods for Linear Programming. SIAM Review, Vol.34, No.2 (1992), 167-224.

2.- Luenberger, David G., "Programación lineal y no lineal ", Buenos Aires Addison-Wesley- Iberoamericana 1989


3.- Nemhauser, Rinnooy Kan, - Optimization- M.J.Tod, Editors - North Holland-1991
4.- Nemhauser G. and Wolsey L. Integer and Combinatorial Optimization, J. Wiley &Sons Inc., New York, 1999.

CRONOGRAMA DE CLASES Y EVALUACIONES


Clases
1-28

Contenidos/Actividades

Evaluaciones previstas

Contenidos de los módulos 1-8

Evaluación parcial sobre los contenidos de 1-8


29-36

Contenidos de 9 y temas especiales desarrollados por alumnos

Evaluación final: exposición trabajo final

Contacto de la cátedra :

e-mail: opti@mate.unlp.edu.ar

Departamento de Matemática. Facultad de Ciencias Exactas.UNLP

http: www.mate.unlp.edu.ar/catedras/Investigacion OperativaI



Firma del profesor responsable:


La base de datos está protegida por derechos de autor ©espanito.com 2016
enviar mensaje