Investigació Operativa ( IO )

• ÚS SOLVENT DELS RECURSOS D'INFORMACIÓ

• G6 - Gestionar l'adquisició, l'estructuració, l'anàlisi i la visualització de dades i d'informació de l'àmbit de l'enginyeria informàtica, i valorar de forma crítica els resultats d'aquesta gestió.
  
• G6.3 - Planificar i utilitzar la informació necessària per a un treball acadèmic (per exemple, per al treball de final de grau) a partir d'una reflexió crítica sobre els recursos d'informació utilitzats. Gestionar la informació de manera competent, independent i autònoma. Avaluar la informació trobada i identificar-ne les llacunes.
  

• ACTITUD ADEQUADA DAVANT EL TREBALL

• G8 - Tenir motivació per a la realització professional i per a afrontar nous reptes, tenir una visió àmplia de les possibilitats de la carrera professional en l'àmbit de l'enginyeria en informàtica. Sentir-se motivat per la qualitat i la millora contínua, i actuar amb rigor en el desenvolupament professional. Capacitat d'adaptació als canvis organitzatius o tecnològics. Capacitat de treballar en situacions de carència d'informació i/o amb restriccions temporals i/o de recursos.
  
• G8.3 - Estar motivat pel desenvolupament professional, per a afrontar nous reptes i per la millora contínua. Tenir capacitat de treball en situacions de falta d'informació.
  

• ESPECIALITAT COMPUTACIÓ

• CCO1 - Tenir un coneixement profund dels principis fonamentals i dels models de la computació i saber-los aplicar per a interpretar, seleccionar, valorar, modelar i crear nous conceptes, teories, usos i desenvolupaments tecnològics, relacionats amb la informàtica.
  
• CCO1.3 - Definir, avaluar i seleccionar plataformes de desenvolupament i producció hardware i software per al desenvolupament d'aplicacions i serveis informàtics de diversa complexitat.
  
• CCO2 - Desenvolupar de forma efectiva i eficient els algorismes i el software apropiats per a resoldre problemes complexos de computació.
  
• CCO2.4 - Demostrar coneixement i desenvolupar tècniques d'aprenentatge computacional; dissenyar i implementar aplicacions i sistemes que les utilitzin, incloent les que es dediquen a l'extracció automàtica d'informació i coneixement a partir de grans volums de dades.
  

• ESPECIALITAT SISTEMES D'INFORMACIÓ

• CSI2 - Integrar solucions de Tecnologies de la Informació i les Comunicacions, i processos empresarials per a satisfer les necessitats d'informació de les organitzacions, permetent que assoleixin els seus objectius de forma efectiva.
  
• CSI2.1 - Demostrar comprensió i aplicar els principis i les tècniques de gestió de qualitat i d'innovació tecnològica a les organitzacions.
  
• CSI2.2 - Concebre, desplegar, organitzar i gestionar sistemes i serveis informàtics, en contextos empresarials o institucionals, per a millorar-ne els processos de negoci; responsabilitzar-se'n i liderar-ne la posada en marxa i la millora contínua; valorar el seu impacte econòmic i social.
  
• CSI2.6 - Demostrar coneixement i capacitat d'aplicació dels sistemes d'ajuda a la presa de decisions i de bussines intelligence.
  
• CSI3 - Determinar els requisits dels sistemes d'informació i comunicació d'una organització, atenent als aspectes de seguretat, compliment de la normativa i de la legislació vigent.
  
• CSI3.5 - Proposar i coordinar canvis per a millorar l'explotació del sistema i de les aplicacions.
  
• CSI1 - Demostrar comprensió i aplicar els principis i les pràctiques de les organitzacions, de manera que puguin exercir d'enllaç entre les comunitats tècnica i de gestió d'una organització, i participar activament en la formació dels usuaris.
  

1. Conèixer la metodologia bàsica i l'àmbit d'aplicació de la Investigació Operativa
   
   SubObjectius
   • Distingir les diferents etapes en que consisteix un projecte d'Investigació Operativa
   • Paper dels models de Investigació Operativa dins dels sistemes de suport a les decisions
   • Etapa de presa de dades i tractament de la informació necesaria per a formular un model d'Investigació Operativa
   
   Competències relacionades
   • G8.3,
   • CSI1
2. Conèixer models simples de I.O., les seves solucions i particularitats
   
   SubObjectius
   • Conèixer models simples de programació lineal: problemes de producció i de mescles
   • Conèixer models simples de programació lineal entera: problema de la motxila i problemes de càrrega fixa
   • Coneixer models simples en programació no lineal: problema del volum màxim d'un cilindre.
   
   Competències relacionades
   • CSI3.5,
   • G8.3,
   • CCO2.4
3. Conèixer i identificar els components d'un problema d'optimització
   
   SubObjectius
   • Conèixer el paper central de un problema de optimització com eina dins dels processos de decisió
   • Distingir entre variables de decisió i paràmetres de un problema de optimització
   • Conèixer i saber utilitzar llenguatges de representació algebràica de problemes de optimització per a la definició i resolució de models basats en l'optimització
   
   Competències relacionades
   • CCO1.3,
   • CCO2.4
4. Identificació d'objectius en un procés de decisió. Saber expresar com constriccions, tant lineals com no lineals, les condicions a complir per les variables de decisió del model. Formular models multiobjectiu i de programació per objectius.
   
   SubObjectius
   • Identificar els múltiples objectius que puguin intervenir en un model de presa de decisions i relació amb els models de programació lineal
   • Conèixer la formulació bàsica d'un problema multiobjectiu
   • Per a problemes amb dos objectius saber determinar la frontera d'optimalitat Pareto
   • Conèixer i interpretar els resultats i la informació proporcionada per un model amb multiples objectius
   • Ser capaç de definir models de programació lineal adequats per a un sistema de suport a la decisió i traduir-los usant llenguatges de manipulació algebraics,
   • Identificació de variables de decisió i paràmetres de un model
   • Formulació de constriccions lineals i no lineals en un model
   
   Competències relacionades
   • CSI2.1,
   • CSI2.6,
   • CSI1
5. Conèixer l'estructura i propietats dels problemes de programació lineal i no lineal
   
   SubObjectius
   • Conèixer la forma standard de un problema de programació lineal. Variables de folga i escreix
   • Conèixer models simples de programació lineal: problema de producció, problema de mescles
   • Conèixer i saber calcular les solucions bàsiques factibles d'un problema de programació lineal
   • Conèixer els tipus de solucions que pot tenir un problema de programació lineal: solucions úniques, solucions alternatives, problemes infactibles, problemes no fitats
   • Ús de llenguatges de manipualció algebraics i fulls de càlcul. Identificar els tipus de solucions proporcionats pels llenguatges de manipulació algebraics per a problemes de programació lineal
   • Conèixer la diferència entre òptims locals i globals
   • Conèixer les característiques distintives dels problemes amb no linealitats
   
   Competències relacionades
   • CCO2.4,
   • CSI1
6. Conèixer i saber aplicar el mètode del simplex per resoldre problemes de programació lineal
   
   SubObjectius
   • Concepte de base factible. Conèixer i distingir entre variables bàsiques i no bàsiques
   • Objecte dels costs reduïts. Reconèixer una solució bàsica com solució òptima d'un problema de programació lineal. Reconèixer quan hi han òptims alternatius
   • Efectuar iteracions del mètode del simplex. Concepte de canvi de base. Càlcul dels costs reduïts
   
   Competències relacionades
   • CCO2.4
7. Conèixer i saber resoldre problemes de programació lineal en els que les variables estan asociades a un graf. Problemes de fluxos sobre xarxes.
   
   SubObjectius
   • Conèixer el paper de les matrius d'incidències nusos-arcs
   • Conèixer la formulació de problemes de fluxos en grafs bipartits. Conèixer la formulació del problema de cost mínim.
   • Conèixer l'estructura de les solucions bàsiques del problemes de fluxos sobre xarxes. Costs associats als nusos dels arbres i variables duals. Càlcul dels coeficients de costs reduïts. Casos amb un o més articles.
   • Aplicació dels algoritmes de camins mínims. (Dijkstra i correctors d'etiquetes)
   • Problemes de fluxos sobre xarxes amb capacitats asociades als arcs. Teorema del Flux-màxim Tall-mínim
   
   Competències relacionades
   • CSI2.2,
   • CCO2.4
8. Conèixer i aplicar tècniques bàsiques per resoldre problemes lineals amb variables enteres
   
   SubObjectius
   • Conèixer i poder aplicar l'algoritme de Branch and Bound
   • Saber formular condicions lògiques en forma de constriccions en un model de programació lineal entera
   • Conèixer els models bàsics de recobriment en forma de problema de programació lineal entera
   
   Competències relacionades
   • CCO1.3,
   • CCO2.4
9. Conèixer i identificar els inputs i els outputs dels models d'Investigació Operativa subjacents a diversos sistemes d'informació i d'ajut a la presa de decisions vistos en les sessions pràctiques.
   
   SubObjectius
   • Conèixer les propietats dels models d'Investigació Operativa vistos en les sessions pràctiques.
   • Davant de un conjunt de necessitats de una organització, analitzar si els models de Investigació Operativa vistos en les sessions pràctiques són suficients per a satisfer aquestes necessitats. Identificar deficiències i absències en la modelització.
   • Donats determinats requeriments de una organització en relació a un sistema d'ajut a la presa de decisions, adaptar i/o ampliar els models d' Investigació Operativa vistos en les sessions pràctiques per tal de satisfer els requeriments.
   
   Competències relacionades
   • CSI2.2,
   • CSI3.5,
   • G6.3,
   • CCO1.3,
   • CSI1
10. Ser capaç d'aplicar mètodes heuristics per a problemes de programació lineal entera
    
    SubObjectius
    • Aplicar heurístiques per problemes de localització de plantes
    • Aplicar heurístiques d'intercanvi per al problema del viatjant de comerç
    
    Competències relacionades
    • CSI2.6,
    • CCO1.3,
    • CCO2.4
11. Conèixer i poder aplicar diferents tipus de metaheurístiques vistos en l'assignatura
    
    SubObjectius
    • Saber aplicar la tècnica de recuit simulat per a resoldre problemes de routing
    • Saber aplicar la tècnica de tabú search per resoldre problemes de programació lineal entera
    
    Competències relacionades
    • CSI2.6,
    • CCO1.3,
    • CCO2.4
12. Ser capaç d'usar eficaçment els recursos d'informació en I.O.
    
    SubObjectius
    • Saber utilitzar i reconèixer la informació adequada per a la realització d'un treball
    • Saber el tipus de informació que pot proporcionar una font
    • Anàlisi i síntesi d'una determinada font d'informació i valor en relació a la consecució d'un objectiu (realització d'un treball, tasca o projecte)
    
    Competències relacionades
    • G6.3
13. Tenir actitud apropiada i motivació envers la feina
    
    SubObjectius
    • Motivació per la responsabilitat, la qualitat en la pròpia feina i la realització professional
    • Capacitat d'adaptació als canvis organitzatius, tecnològics i treball en equip
    • Adaptació a la falta d'informació i a les restriccions materials i temporals
    
    Competències relacionades
    • G8.3

Llegenda

L'aprenentatge es farà seguint la metodologia dels casos, a partir de problemes en l'entorn de la Investigació Operativa. A partir d'aquests problemes es desenvoluparan els coneixements formals necessaris en classes de teoria, presencials i expositives, i la seva aplicació en les classes de laboratori, de tal manera que reforçarà l'assimilació dels diferents conceptes. S'utilitzarà software disponibles a la UPC (AMPL,OPL/Studio, excel,).

Tipus d'avaluació

NT = Nota de Teoria
NL = Nota de Laboratori. La nota de laboratori estarà formada per les notes de les dues pràctiques al 50% cada una
NTC = Nota del Treball de Curs
NC = Nota relativa a les competències.

N= 0.45*NT + 0.2*NL + 0.25*NTC + 0.1*NC

Si 0.5*NExP1 + 0.5NExP2 >= 5 llavors no cal presentar-se a l'examen final

NT = Max (NExF, 0.5*NExP1 + 0.5*NExP2)

NExF = Nota de l'examen final
NExP1, NExP2 = Notes dels examens parcials 1 i 2.

La nota NC dependrà del grau assolit en les competències transversals pròpies de l'assignatura
i es repartirà a parts iguals entre aquestes. ( hi ha dues competències C1, C2; la nota
NC serà NC = 0.5*NC1 + 0.5*NC2

Per a una competència determinada hi ha la següent correspondència entre la valoració (A,B,C,D)
de la competència i la nota NC1 (o NC2) que passa a formar part de la nota final.


Un nivell A equival a una nota NC1 (o NC2) que estarà entre 8.5 i 10
Un nivell B equival a una nota NC1 (o NC2) que estarà entre 6,5 i < 8,5
Un nivell C equival a una nota NC1 (o NC2) que estarà entre 5 i < 6.5
Un nivell D equival a una nota NC1 (o NC2) que estarà entre 0 i <5

Les notes de les competències s'obtenen a partir d'activitats associades al Bloc 8 (Treball de Curs)
i de les pràctiques de laboratori.

La nota NC1, NC2 de les competències assignades a l'assignatura obeirà a la següent expressió:

NCi = 0.25 * NTC + 0.10*NL + Activitats específiques de la competència; i=1,2

Pes de les competències transversals en l'avaluació de la part específica de l'assignatura

• 5.0 % - Planificar i utilitzar la informació necessària per a un treball acadèmic (per exemple, per al treball de final de grau) a partir d'una reflexió crítica sobre els recursos d'informació utilitzats. Gestionar la informació de manera competent, independent i autònoma. Avaluar la informació trobada i identificar-ne les llacunes.
• 5.0 % - Estar motivat pel desenvolupament professional, per a afrontar nous reptes i per la millora contínua. Tenir capacitat de treball en situacions de falta d'informació.

• Winston W.L. , Mathematical Programming. Applications and algorithms , PWS Kent Publishing Company , 1991 .



• Fourer, R, Gay, D.M. . Kernighan, B.W , AMPL a modeling language for mathematical programming , Thomson/Brooks/Cole , 2003 .



• Williams, H.P. , Model building in mathematical programming , John Wiley and Sons , 1999 .



• Hillier, Frederick S. , Introduction to Operations Research , McGraw Hill .

• Sierksma, G. , Linear and integer programming : theory and practice , Marcel Dekker , 1999 .

1. http://www.hsor.org/
   Pàgina de la High School Operations Research
2. http://www.ampl.com/
   Pàgina del Software de Modelització AMPL.
3. http://people.brunel.ac.uk/~mastjjb/jeb/or/contents.html
   Material Acadèmic del Professor Beasley J.E. al Imperial College de Londres
4. http://ifors.org/web/
   Pàgina de la Federació Internacional de Societats Professionals d' Investigació Operativa. Es possible mitjançant ella accedir a les pàgines de les Societats Europees, USA etc i les corresponents Societats Nacionals
5. http://www-01.ibm.com/software/integration/optimization/cplex-optimization-studi
   Pàgina del IBM CPLEX Optimization Studio.

Els alumnes han de tenir els coneixements suficients d'àlgebra per poder assimilar els mètodes algoritmcs exposats També han de ser capaços de llegir anglès a nivell tècnic