Models Deterministes de la I.O. II (MDIO2)
| Professors Responsables: |
ESTEVE CODINA SANCHO (esteve eio.upc.edu)
|
|
Crèdits: 4.5 (3.0 T 1.5 P 0.0 L)
| |
Departament:
EIO
|
Tipus d'assignatura
Optativa per la EI
Requisits de l'assignatura
|
MDIO1
- Pre-requisit per la EI
|
|
Objectius docents
L'assignatura Models Deterministes de lnvestigació Operativa I ha
familiaritzat l'alumne amb la pràctica de la construcció de models
matemàtics i la seva utilització com a components de sistemes
d'ajut a la presa de decisions quantitatives, l'assignatura Models Deterministes
de la Investigació Operativa II té com a objectius introduir nous
models i algorismes de tipus determinista, i en particular els de la important
familia d'optimització no lineal, i obrir la perspectiva dels procediments
heurístics i de les situaciosn amb mes d'un objectiu tan freqüents
en la pràctica de l'optimització. El curs té una
orientació eminentment pràctica amb l'objectiu que els alumnes
adquireixen el coneixemnts i l'experiència per a foremaular i resoldre
els models objecte de l'assignatura mitjançant l'us d'alguns dels paquets
de programes estàndard de mes àmplia utilització.
Programa
1. Programació entera en variables 0-1.
Teoria:
Exemples de problemes 0-1: Seqüenciació i ordenació,
càrrega fixa Knapsack, localització de plantes, viatjant de
comerç, itineraris de vehicles, etc.. Refinaments del Branch and Bound.
Mètodes d'enumeració implícita. Constriccions
vàlides. Subrogació de constriccions. Mètodes
d'identificació de constriccions.
Pràctiques:
Exercicis de formulació de problemes de programació entera en
variables 0-1. Resolució amb les opcions del paquet LINDO.
2. Models no lineals.
Teoria:
2.1. La formulació de models no lineals. Exemples de models no
lineals amb i sense constriccions. Diferencies entre models
lineals i no lineals.
2.2. Repàs de conceptes d'anàlisi. Optimització de funcions
diferenciables d'una variable. Màxims i mínims locals. Màxims i
mínims globals. Condicions necessaries i suficients per a la
existència d'un extrem. Optimització de funcions de varies
variables. Condicions necessaries i suficients per a la
existencia d'extrems. Optimització de funcions convexes.
Optimització de funcions amb constriccions: Multiplicadors de
Lagrange. Condicions de Kuhn i Tucker. Interpretació dels
multiplicadors óptims.
2.3. Caracteristiques generals dels algorismes d'optimització no
lineal: direccions factibles i de descens. Estructura general
dels algorismes de descens.
2.4. Optimització no lineal sense constriccions: Mètodes de
gradients i de Newton. Mètodes d'exploració lineal exacta i
aproximada.
2.5. Optimització no lineal amb constriccions lineals: Mètodes de
direccions factibles i d'aproximacions lineals.
2.6. Optimització no lineal amb constriccions qualsevol: idea del
mètode de gradient reduït generalitzat.
Pràctiques:
Exercicis de formulació de models no lineals amb i sense constriccions.
Utilització de les llibreries POPNOLC, HARWELL, etc. per a trobar
solucions i per a comprovar empiricament resultats teorics. Interpretació
de les solucions.
Utilització dels paquet GINO per a la comporvació de les condicions
d'optim i resolució dels problemes. Interpretació de les solucions.
3. Resolució heurística de problemesd'optimització.
Teoria:
El paper de les heurístiques a la Investigació Operativa:
problemes ben estructurats i problemes pobrement estructurats.
Característiques generals dels procediments heurístics.
Exemples de heurístiques, per a problemes de sequenciació, de
localització de plantes, de viatjant de comerç, etc...
Pràctiques:
Resolució d'un problema d'optimització per implementació del
programa de la heurística adient.
4. Introducció als métodes de decisiómulti-objectiu.
Teoria:
Exemples de problemes multiobjectiu. Panoràmica de les técniques
de decisió multi-objectiu. El mètode del simplex i la
programació per objectius. La programació lineal multi-objectiu i
els mètodes minisum i nminimax.
Pràctiques:
Utilització dels paquets LINDO I GINO per a resoldre problemes
multi-objectiu.
Avaluació
Realització d'una pràctica per cada punt de l'assignatura.
Qualificació Final: ponderació de les qualificacions dels exercicis pràctics.
Bibliografia
Bibliografia bàsica
- Ahuja, R.K.; Magnanti, T.L.; Orlin, J.B. Network Flows Prentice Hall, 1993
- Daellenbach, H.G., George, J.A. and D.C. McNickle Intruduction to Operations
Research Techniques Allyn and Bacon, 1938
- Garfinkel, R.S.; Nemhauser, G.L. Integer Programming John Wiley, 1972
- Syslo, M.M, Deo, N.and Kowalik, J Discrete Optimization Algorithms Prentice-Hall, 1983
- Taha, H.A Operations Research: An Introduction Mc Millan, 1987
Bibliografia complementària
- Dennis, J.E. AND Schnabel, R.B Numerical Methods for Non Linear Equations
and Unconstrained Minimization Prentice Hall, 1983
- Liebman, J., Lasdon, L. and Waren, Al Modelling and Optimization with
GINO The Scientific Press, San Francisco, 1986
- Luenberger, D.E Programación Lineal y No Lineal Addison-Wesley
Iberoamericana, 1989
- Schrage, L User's Manual for Linear, Integer and Quadratic Programming with
LINDO, Release 5.0 The Scientific Press, San Francisco, 1991
|
