PROGRAMACIÓN MATEMÁTICA

Carácter: Optativa, 1er Cuatrimestre.

Nº de créditos totales: 9 créditos. Distribución : 6 créditos de aula y 3 créditos de ordenador.

OBJETIVOS

Los alumnos que cursen esta asignatura deben comprender la teoría en la que se basa la programación lineal, la programación entera y la programación cuadrática y deben aprender a resolver este tipo de problemas con los algoritmos diseñados que se exponen a lo largo del cuatrimestre. Además, deben saber programar en fortran o C con las subrutinas de optimización OSL (Optimization Subroutine Library) de IBM con el objetivo de encontrar soluciones a problemas del tipo estudiado teóricamente.

PROGRAMA TEÓRICO

Tema 1.- Programación Lineal

  1. Fundamentos.
  2. Degeneración y ciclos.
  3. Método Simplex primal.
  4. Método Simplex revisado.
  5. Variables artificiales.
  6. Método Simplex revisado para variables acotadas superiormente.
  7. Método Simplex para un problema de red.
  8. Ejercicios resueltos.

Tema 2.- Dualidad

  1. Introducción.
  2. Teoremas fundamentales.
  3. Relaciones con el método Simplex.
  4. Teoremas de la Holgura Complementaria.
  5. Métodos simplex dual y simplex primal-dual.
  6. Análisis de la sensibilidad.
  7. Ejercicios resueltos.

Tema 3.- Programación entera

  1. Algunos problemas representativos.
  2. Métodos de cortes.
  3. Métodos de bifurcación y acotación.
  4. Programación entera 0-1.
  5. Ejercicios resueltos.

Tema 4.- Algoritmos Particulares.

  1. Algoritmo de Dijkstra.
  2. El problema del transporte.
  3. El problema de asignación.
  4. El algoritmo de Ford Fulkerson.
  5. Ejercicios resueltos.

Tema 5.- Programación Dinámica.

  1. Programación dinámica determinística.
  2. Programación dinámica probabilística.
  3. Ejercicios resueltos.

Tema 6.- Programación No Lineal

  1. Funciones convexas y cóncavas.
  2. Criterios de optimalidad para problemas sin restricciones.
  3. Criterios de optimalidad para problemas con restricciones.
  4. Casos particulares.
  5. Métodos de programación no lineal con restricciones.
  6. Ejercicios resueltos.

Tema 7.- Software y rutinas científicas.

  1. STORM.
  2. OSL, Optimization Subroutine Library.

 

BIBLIOGRAFÍA BÁSICA

  1. D.E.Luenberger. Programción lineal y no lineal. Editorial Addison Wesley (1984).
  2. Hiller, Frederich y Lieberman. Introducción a la investigación de operaciones. Editorial McGraw-Hill (1997). Sexta Edición.
  3. L.Nemhauser. Integer and combinatorial optimization. Editorial Wiley (1988).

 

CRITERIOS DE EVALUACIÓN

Examen escrito y obligatoriedad de las prácticas con las subrutinas OSL.