Combinatòria i Optimització

Objectius

En la part de combinatòria:
1) repassar les fórmules enumeratives elementals (i algunes de llurs aplicacions més usuals) atenent els dos factors clau: repetició i ordre
2) treballar la formulació i la resolució de funcions generadores
3) treballar la formulació i la resolució d'equacions lineals recurrents.

En la part de programació lineal:
1) descobrir les propietats bàsiques del problema clàssic, tant en la formulació geomètrica com en l'algebraica
2) a través de l'algorisme del símplex i d'algunes variacions possibles obtenir una panoràmica força completa dels aspectes més importants relacionats amb la resolució de programes lineals
3) conèixer la programació lineal entera; identificar les aplicacions principals en la resolució de problemes d'optimització.

Programa

COMBINATÒRIA I (tres setmanes)
- Regla de la suma i regla del producte
- Permutacions
- Combinacions i nombres binomials
- Teorema binomial i teorema multinomial
- Principi d'inclusió/exclusió. Desarranjaments
COMBINATÒRIA II (quatre setmanes)
- Funcions generadores ordinàries
- Funcions generadores exponencials
- Equacions lineals recurrents
  - Plantejament
  - Resolució iterativa
  - Mètode de les arrels
FONAMENTS DE LA PROGRAMACIÓ LINEAL (dues setmanes)
- Orígens de la programació lineal
- Formulació i trets del model
- Interpretació geomètrica del model
- Forma estàndard del problema
- Solucions factibles i solucions bàsiques
- Teorema de convexitat
- Teorema dels punts extrems
- Teorema d'optimalitat
ALGORISME DEL SÍMPLEX (tres setmanes)
- Taula estàndard
- Taula canònica
- Millora d'una solució factible bàsica
- Algorisme del símplex (fases I i II)
- Degeneració i cicles
- Representació matricial del símplex
- Algorisme del símplex dual
PROGRAMACIÓ LINEAL ENTERA (dues setmanes)
- Introducció i característiques
- Exemples de formulació de problemes
- Algorisme de Gomory
- Algorisme de bifurcar i limitar
- Aplicacions de la programació lineal 0/1

Bibliografia

Bàsica

BASART, J.M. (2000) [1998]. Programació lineal.
Col·lecció Materials de la UAB, n. 58. ISBN 84-490-1443-3.
GRIMALDI, R.P. (1989). Matemàticas discreta y combinatoria.
Addison-Wesley Iberoamericana. ISBN 0-201-64406-1.
MURTY, K.G. (1983). Linear Programming.
John Wiley & Sons. ISBN 0-471-09725-X.
THIE, P.R. (1988). An Introduction to Linear Programming and Game Theory.
John Wiley & and Sons. ISBN 0-471-62488-8.

Complementària

BASART, J.M.; RIFÀ, J.; VILLANUEVA, M. (1997). Fonaments de matemàtica discreta. Elements de combinatòria i d'aritmètica.
Col·lecció Materials de la UAB, n. 36. ISBN 84-490-0855-7.
DANTZIG, G.B. (1963). Linear Programming and Extensions.
Princeton University Press. ISBN 0-691-08000-3.
NASH, S.G.; SOFER, A. (1996). Linear and Nonlinear Programming.
McGraw-Hill. ISBN 0-07-046065-5.
ROBERTS, F.S. (1984). Applied Combinatorics.
Prentice-Hall Inc. ISBN 0-13-039313-4.
SULTAN, A. (1993). Linear Programming. An Introduction with Applications.
Academic Press. ISBN 0-12-676350-X.
TUCKER, A. (1984). Applied Combinatorics.
John Wiley & Sons. ISBN 0-471-63579-0.

Avaluació

La qualificació final es basa en la prova escrita que es durà a terme un cop acabada la docència.