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

Professors

Responsable:	Jordi Castro Pérez (jordi.castroupc.edu).
Altres:	Esteve Codina Sancho (esteve.codinaupc.edu).

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:

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

• R.K. Ahuja, T.L. Magnanti, and J.B. Orlin Network Flows, Prentice-Hall, 1993.
• R. Fourer, D.M. Gay, B.W. Kernighan AMPL a modeling language for mathematical programming, 2nd ed., Thomson/Brooks/Cole, 2003.
• J. Nocedal and S.J. Wright Numerical Optimization, Springer, 1999.
• W.L.Winston Operations Research; Applications and Algorithms 2nd ed. , Duxbury Press, 1994.
• L.A. Wolsey Integer programming, John Wiley & Sons, 1998.

Bibliografía complementària

• D. Bertsimas, J. N. Tsitsiklis Introduction to linear optimization, Athena Scientific, 1999.
• C.T. Ragsdale, Spreadsheet modeling and decision analysis. A practical introduction to management science 3rd. Ed, 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.