Saltar al contingut Menu
Mapa
  • Inici
  • Informació
  • Contacte
  • Mapa

Models d'Investigació Operativa per a la Presa de Decisions (MIOPD)

Crèdits Dept.
7.5 (6.0 ECTS) EIO

Professors

Responsable:  (-)
Altres:(-)

Objectius Generals

L'assignatura presenta alguns dels mètodes fonamentals de la investigació operativa. La investigació operativa és una disciplina basada en la formulació de models, desenvolupament i aplicació d'algorismes per a la resolució de problemes de presa de decisions. L'assignatura introdueix també els llenguatges de modelització i el software necessaris per a la resolució efectiva de problemes. El curs té una orientació pràctica. Es presentaran diferents aplicacions dels models i algorismes introduïts a problemes complexos que l'estudiant pot trobar-se en el futur, tant de tipus tècnic com a nivell de gestió.

Objectius Específics

Coneixements

  1. Concepte de model. Models lineals, de fluxos en xarxes, enters i no lineals.
  2. Algorisme del simplex per a programació lineal.
  3. Algorisme del simplex per al problema de cost mínim en fluxos en xarxes.
  4. Algorismes per al problema de camins mínims amb costos positius (Dijkstra) i qualsevols ("label-correcting").
  5. Algorismes per al problema de flux màxim.
  6. L'algorisme de branch-and-bound per a programació entera.
  7. Propietats bàsiques dels problemes no lineals.
  8. Mètodes heurístics per a problemes de seqüenciació, disseny de xarxes, itineraris...
  9. Programació dinàmica.
  10. Formulació i resolució de problemes utilitzant software de modelització i optimització.

Habilitats

  1. Saber identificar problemes de Programació Matemàtica/Optimització.
  2. Donat un problema, realitzar la seva modelització, determinant si és lineal, no lineal o enter.
  3. Solucionar un model mitjançant el software de modelització i algorisme apropiats. Interpretar la solució.
  4. Conèixer i saber usar software de modelització i paquets d'optimització.

Competències

  1. Solucionar problemes de presa de decisions, amb l'ajut de computadors.
  2. Capacitat de síntesi, raonament lògic, i resolució de problemes a través de tècniques quantitatives.
  3. Formular i solucionar (encara que aproximadament) problemes difícils computacionalment (NP-complets).
  4. Utilitzar bibliografia i software en anglès.

Continguts

Hores estimades de:

T P L Alt L Ext. Est A Ext.
Teoria Problemes Laboratori Altres activitats Laboratori extern Estudi Altres hores fora d'horari fixat

1. Introducció.
T      P      L      Alt    L Ext. Est    A Ext. Total 
1,0 0 0 0 0 0 0 1,0
- Investigació Operativa, Programació Matemàtica i Optimització. Models.
- Classificació dels problemes i algorismes de resolució.

2. Modelització i llenguatges de modelització.
T      P      L      Alt    L Ext. Est    A Ext. Total 
8,0 4,0 10,0 0 10,0 10,0 0 42,0
- Models lineals, enters i no lineals. Exemples i estudis de cas.
- Modelització amb fulls de càlcul
- El llenguatge de modelització AMPL.

A les sessions de laboratori es mostraran els entorns de modelització Excel i AMPL.
A les sessions de teoria i laboratori i es presentaran 5 estudis de cas:
- Gestió de projectes amb limitacions de temps (programació lineal).
- Flux màxim concurrent en una xarxa de transmissió multiarticle (fluxos en xarxes).
- Problema d'itineraris: TSP (programació entera).
- Disseny de xarxes (programació entera).
- Optimització d'una Support Vector Machine (programació no lineal, quadràtica)

Dos d'aquests casos s'usaran per a la nota de pràctiques.

3. Programació lineal.
T      P      L      Alt    L Ext. Est    A Ext. Total 
8,0 2,0 2,0 0 0 8,0 0 20,0
- Propietats bàsiques de la programació lineal.
- Complexitat computacional de la programació lineal.
- L'algorisme del simplex (versió primal, forma matricial).

4. Problemes lineals amb estructura de xarxa: fluxos en xarxes.

T      P      L      Alt    L Ext. Est    A Ext. Total 
10,0 4,0 4,0 0 0 12,0 0 30,0
A les sessions de teoria es veuran:
- Propietats bàsiques dels problemes amb estructura de xarxa.
- Tipus de models de fluxos en xarxes. Exemples.
- Algorisme del simplex per al problema de cost mínim en fluxos en xarxes.
- Algorismes per al problema de camins mínims amb costos positius (Dijkstra) i qualsevols ("label-correcting").
- Algorisme per al problema de flux màxim.

5. Programació Entera.
T      P      L      Alt    L Ext. Est    A Ext. Total 
4,0 1,0 1,0 0 0 4,0 0 10,0
L'algorisme de branch and bound.

6. Programació no lineal
T      P      L      Alt    L Ext. Est    A Ext. Total 
4,0 2,0 0 0 0 4,0 0 10,0
Propietats bàsiques de la programació no lineal.

7. Mètodes heurístics
T      P      L      Alt    L Ext. Est    A Ext. Total 
6,0 2,0 0 0 0 6,0 0 14,0
- Heurístiques per a problemes de seqüenciació de tasques.
- Heurístiques per a problemes de disseny de xarxes.
- Heurístiques per a problemes d'itineraris.

8. Programació dinàmica.
T      P      L      Alt    L Ext. Est    A Ext. Total 
2,0 0 0 0 0 1,0 0 3,0


Total per tipus T      P      L      Alt    L Ext. Est    A Ext. Total 
43,0 15,0 17,0 0 10,0 45,0 0 130,0
Hores addicionals dedicades a l'avaluació 5,0
Total hores de treball per l'estudiant 135,0

Metodologia docent

Hi haurà sessions de teoria, problemes i laboratori. A teoria s'introdueixen els coneixements bàsics de l'assignatura. A les sessions de problemes se solucionaran exercicis directament basats en la teoria. A les sessions de laboratori es resoldran casos reals de mida petita, on l'estudiant formularà i solucionarà un problema amb l'ajut de software de modelització i els "solvers" apropiats.

Mètode d'avaluació

La nota final NF es calcularà com NF= 0.7*NT+0.3*NP, essent NT la nota de teoria i NP la de pràctiques.

NT: Hi haurà un examen parcial a meitat del quadrimestre, alliberatori de matèria de cara a l'examen final per als estudiants que tinguin nota superior o igual a 4. Aquest parcial, per als qui tinguin nota superior o igual a 4, puntua sobre NT/2. L'examen final puntua sobre NT/2 per als qui hagin superat el parcial amb nota superior o igual a 4, i NT per als qui no.

NP: Hi haurà dues pràctiques que es realitzaran en horari de classe a les sessions de laboratori. Cada una consistirà en la modelització i resolució d'un cas usant el software de modelització-optimització AMPL. Cada pràctica puntua 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 complementària

  • 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.

Enllaços web

  1. http://www-neos.mcs.anl.gov/
    Servidor gratuit per a la solució remota de problemes d'optimització amb diferentes algorismes.


  2. http://www.ece.northwestern.edu/OTC/
    Pàgina del Optimization Technology Center amb software, demos, exemples de cas, etc. Inclou les FAQ de Programació Lineal i No Lineal.


  3. http://plato.la.asu.edu/guide.html
    Decision Tree for Optimization software: guia de software lliure d'optimització.


Capacitats prèvies

Es requereix un mínim de coneixements que l'estudiant ja ha adquirit en assignatures prèvies. En particular, s'usen nocions bàsiques de:

- programació
- àlgebra (operacions amb matrius i vectors)
- estructures de dades per a grafs
- algorismes bàsics per a grafs.


Compartir

 
logo FIB © Facultat d'Informàtica de Barcelona - Contacte - RSS
Aquest web utilitza cookies pròpies per oferir una millor experiència i servei. En continuar amb la navegació entenem que acceptes la nostra política de cookies.
Versió clàssica Versió mòbil