Saltar al contingut Saltar a navegacio
Mapa
  • Inicio
  • Información
  • Contacto
  • Mapa

Modelos de la Investigación Operativa para la Toma de Decisiones (MIOPD)

Créditos Dept. Tipo Requisitos
7.5 (6.0 ECTS) EIO
  • Optativa para la EI
  • Optativa para la ETIG
AL - Prerequisito para la EI , ETIG
PRED - Prerequisito para la EI , ETIG

Profesores

Responsable:  (-)
Otros:(-)

Objectivos Generales

La asignatura presenta algunos de los métodos fundamentales de la investigación operativa. La investigación operativa es una disciplina basada en la formulación de modelos, el desarrollo y la aplicación de algoritmos para la resolución de problemas de toma de decisiones. La asignatura introduce también en los lenguajes de modelización y el software necesarios para la resolución efectiva de problemas. El curso tiene una orientación práctica. Se presentarán diferentes aplicaciones de los modelos y algoritmos introducidos en problemas complejos que el estudiante puede encontrarse en el futuro, tanto de tipo técnico como relativos a la gestión.

Objectivos Específicos

Conocimientos

  1. Concepto de modelo. Modelos lineales, de flujos en redes, enteros y no lineales.
  2. Algoritmo simplex para programación lineal.
  3. Algoritmo simplex para el problema de coste mínimo en flujos en redes.
  4. Algoritmos para el problema de caminos mínimos con costes positivos (Dijkstra) y cualquier otros ("label-correcting").
  5. Algoritmos para el problema de flujo máximo.
  6. El algoritmo de branch-and-bound para programación entera.
  7. Propiedades básicas de los problemas no lineales.
  8. Métodos heurísticos para problemas de secuenciación, diseño de redes, itinerarios...
  9. Programación dinámica.
  10. Formulación y resolución de problemas utilizando software de modelado y optimización.

Habilidades

  1. Saber identificar problemas de Programación Matemática/Optimización.
  2. Dado un problema, realizar su modelado, determinante si es lineal, no lineal o entero.
  3. Solucionar un modelo mediante el software de modelado y algoritmo apropiados. Interpretar la solución.
  4. Conocer y saber usar software de modelado y paquetes de optimización.

Competencias

  1. Solucionar problemas de toma de decisiones con la ayuda de computadores.
  2. Capacidad de síntesis, razonamiento lógico y resolución de problemas a través de técnicas cuantitativas.
  3. Formular y solucionar (aproximadamente) problemas difíciles computacionalmente (NP-completos).
  4. Utilizar bibliografía y software en inglés.

Contenidos

Horas estimadas de:

T P L Alt L Ext. Est O. Ext.
Teoria Problemas Laboratorio Otras actividades Laboratorio externo Estudio Otras horas fuera del horario fijado

1. Introducción.
T      P      L      Alt    L Ext. Est    O. Ext. Total 
1,0 0 0 0 0 0 0 1,0
- Investigación Operativa, Programación Matemática y Optimización. Modelos.

- Clasificación de los problemas y algoritmos de resolución.

2. Modelado y lenguajes de modelado.
T      P      L      Alt    L Ext. Est    O. Ext. Total 
8,0 4,0 10,0 0 10,0 10,0 0 42,0
- Modelos lineales, enteros y no lineales. Ejemplos y estudios de caso.

- Modelado con hojas de cálculo.

- El lenguaje de modelado AMPL.





En las sesiones de laboratorio se mostrarán los entornos de modelado Excel y AMPL.

En las sesiones de teoría y laboratorio y se presentarán 5 estudios de caso:

- Gestión de proyectos con limitación de tiempo (programación lineal).

- Flujo máximo concurrente en una red de transmisión multiartículo (flujos en redes).

- Problema de itinerarios: TSP (programación entera).

- Diseño de redes (programación entera).

- Optimización de una Support Vector Machine (programación no lineal, cuadrática)



Dos de estos casos se usarán para la nota de prácticas.

3. Programación lineal.
T      P      L      Alt    L Ext. Est    O. Ext. Total 
8,0 2,0 2,0 0 0 8,0 0 20,0

4. Problemas lineales con estructura de red: flujos en redes.
T      P      L      Alt    L Ext. Est    O. Ext. Total 
10,0 4,0 4,0 0 0 12,0 0 30,0
En las sesiones de teoría se verán:



- Propiedades básicas de los problemas con estructura de red.

- Tipo de modelos de flujos en redes. Ejemplos.

- Algoritmo simplex para el problema de coste mínimo en flujos en redes.

- Algoritmos para el problema de caminos mínimos con costes positivos (Dijkstra) y cualquier otros ("label-correcting").

- Algoritmo para el problema de flujo máximo.

5. Programación Entera.
T      P      L      Alt    L Ext. Est    O. Ext. Total 
4,0 1,0 1,0 0 0 4,0 0 10,0
El algoritmo de branch and bound.

6. Programación no lineal
T      P      L      Alt    L Ext. Est    O. Ext. Total 
4,0 2,0 0 0 0 4,0 0 10,0
Propiedades básicas de la programación no lineal.

7. Métodos heurísticos
T      P      L      Alt    L Ext. Est    O. Ext. Total 
6,0 2,0 0 0 0 6,0 0 14,0

8. Programación dinámica.
T      P      L      Alt    L Ext. Est    O. Ext. Total 
2,0 0 0 0 0 1,0 0 3,0


Total por tipo T      P      L      Alt    L Ext. Est    O. Ext. Total 
43,0 15,0 17,0 0 10,0 45,0 0 130,0
Horas adicionales dedicadas a la evaluación 5,0
Total horas de trabajo para el estudiante 135,0

Metodología docente

Habrá sesiones de teoría, problemas y laboratorio. En la teoría se presentan los conocimientos básicos de la asignatura. En las sesiones de problemas se solucionarán ejercicios directamente basados en la teoría. En las sesiones de laboratorio se resolverán casos reales pequeños, donde el estudiante formulará y solucionará un problema con la ayuda de software de modelado y los "solvers" apropiados.

Método de evaluación

La nota final NF se calculará como NF= 0.7*NT+0.3*NP, siendo NT la nota de teoría y NP la de prácticas.

NT: habrá un examen parcial a mitad del cuatrimestre, liberando materia de cara al examen final para los estudiantes que tengan nota superior o igual a 4. Este parcial, para los que tengan nota superior o igual a 4, puntúa sobre NT/2. El examen final puntúa sobre NT/2 para quienes hayan superado el parcial con nota superior o igual a 4, y NT para los que no.



NP: habrá dos prácticas que se realizarán en horario de clase en las sesiones de laboratorio. Cada una consistirá en el modelado y resolución de un caso usando el software de modelado-optimización AMPL. Cada práctica puntúa sobre NP/2.

Bibliografía básica

  • Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin Network flows : theory, algorithms, and applications, Prentice Hall, 1993.
  • Robert Fourer, David M. Gay, Brian W. Kernighan AMPL : a modeling language for mathematical programming, Thomson/Brooks/Cole, 2003.
  • Jorge Nocedal, Stephen J. Wright Numerical optimization, Springer,, 1999.
  • Wayne L. Winston Operations research : applications and algorithms, Brooks/Cole - Thomson Learning, 2004.
  • L.A. Wolsey Integer programming, John Wiley & Sons, 1998.

Bibliografía complementaria

  • Dimitris Bertsimas, John N. Tsitsiklis Introduction to linear optimization, Athena Scientific, 1997.
  • Cliff T. Ragsdale Spreadsheet modeling and decision analysis : a practical introduction to management science, South-Western Publishing, 2001.

Capacidades previas

Se requiere un mínimo de conocimientos que el estudiante haya adquirido en asignaturas previas. En particular, se usan nociones básicas de:

- Programación
- Álgebra (operaciones con matrices y vectores)
- Estructuras de datos para grafos
- Algoritmos básicos para grafos.


Compartir

 
logo FIB © Facultad de Informática de Barcelona - Contacto - RSS