Investigació Operativa

• Professorat
• Hores setmanals
• Competències
• Objectius
• Continguts
• Activitats
• Metodologia docent
• Mètode d'avaluació
• Bibliografia
• Web links
• Capacitats prèvies

Professorat

Responsable

• Esteve Codina Sancho ( )

Altres

• Albert Solà Vilalta ( )
• Joan Garcia Subirana ( )

Hores setmanals

Competències

Competències Tècniques de cada especialitat

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.

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.

Competències Transversals

Actitud adequada davant el treball

• G8 [Avaluable] - 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ó.

ús solvent dels recursos d'informació

• G6 [Avaluable] - 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.

Objectius

1. Conèixer la metodologia bàsica i l'àmbit d'aplicació de la Investigació Operativa
   Competències relacionades: CSI1, G8.3,
   Subcompetences:
   • 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
2. Conèixer models simples de I.O., les seves solucions i particularitats
   Competències relacionades: CCO2.4, CSI3.5, G8.3,
   Subcompetences:
   • Conèixer models simples de programació lineal: problemes de producció i de mescles
   • Coneixer models simples en programació no lineal: problema del volum màxim d'un cilindre.
   • Conèixer models simples de programació lineal entera: problema de la motxila i problemes de càrrega fixa
3. Conèixer i identificar els components d'un problema d'optimització
   Competències relacionades: CCO1.3, CCO2.4,
   Subcompetences:
   • 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ó
   • Conèixer el paper central de un problema de optimització com eina dins dels processos de decisió
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.
   Competències relacionades: CSI2.6, CSI1, CSI2.1,
   Subcompetences:
   • Formulació de constriccions lineals i no lineals en un model
   • Identificar els múltiples objectius que puguin intervenir en un model de presa de decisions i relació amb els models de programació lineal
   • Identificació de variables de decisió i paràmetres de un model
   • 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
   • Conèixer la formulació bàsica d'un problema multiobjectiu
   • 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,
5. Conèixer l'estructura i propietats dels problemes de programació lineal i no lineal
   Competències relacionades: CCO2.4, CSI1,
   Subcompetences:
   • Conèixer les característiques distintives dels problemes amb no linealitats
   • Conèixer models simples de programació lineal: problema de producció, problema de mescles
   • Ú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 la forma standard de un problema de programació lineal. Variables de folga i escreix
   • 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
6. Conèixer i saber aplicar el mètode del simplex per resoldre problemes de programació lineal
   Competències relacionades: CCO2.4,
   Subcompetences:
   • 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
   • Concepte de base factible. Conèixer i distingir entre variables bàsiques i no bàsiques
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.
   Competències relacionades: CCO2.4, CSI2.2,
   Subcompetences:
   • 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)
   • Conèixer la formulació de problemes de fluxos en grafs bipartits. Conèixer la formulació del problema de cost mínim.
   • Conèixer el paper de les matrius d'incidències nusos-arcs
   • Problemes de fluxos sobre xarxes amb capacitats asociades als arcs. Teorema del Flux-màxim Tall-mínim
8. Conèixer i aplicar tècniques bàsiques per resoldre problemes lineals amb variables enteres
   Competències relacionades: CCO1.3, CCO2.4,
   Subcompetences:
   • Conèixer i poder aplicar l'algoritme de Branch and Bound
   • Conèixer els models bàsics de recobriment en forma de problema de programació lineal entera
   • Saber formular condicions lògiques en forma de constriccions en un model de programació lineal entera
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.
   Competències relacionades: G6.3, CCO1.3, CSI1, CSI2.2, CSI3.5,
   Subcompetences:
   • 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.
10. Ser capaç d'aplicar mètodes heuristics per a problemes de programació lineal entera
    Competències relacionades: CSI2.6, CCO1.3, CCO2.4,
    Subcompetences:
    • Aplicar heurístiques d'intercanvi per al problema del viatjant de comerç
    • Aplicar heurístiques per problemes de localització de plantes
11. Conèixer i poder aplicar diferents tipus de metaheurístiques vistos en l'assignatura
    Competències relacionades: CSI2.6, CCO1.3, CCO2.4,
    Subcompetences:
    • 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
12. Ser capaç d'usar eficaçment els recursos d'informació en I.O.
    Competències relacionades: G6.3,
    Subcompetences:
    • 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)
13. Tenir actitud apropiada i motivació envers la feina
    Competències relacionades: G8.3,
    Subcompetences:
    • Motivació per la responsabilitat, la qualitat en la pròpia feina i la realització professional
    • Adaptació a la falta d'informació i a les restriccions materials i temporals
    • Capacitat d'adaptació als canvis organitzatius, tecnològics i treball en equip

Continguts

1. Introducció a la modelització en la presa de decisions:
   La modelització en el procés de presa de decisions. Models de la Investigació Operativa. El cicle metodològic de la investigació operativa
2. Programació continua. Propietats i métodes
   Característiques dels problemes d'optimització. Formulació de problemes d'optimització. Tècniques de programació matemàtica. Formulació de problemes de PL. Resolució de problemes de PL. La geometria de la PL. El mètode del símplex: solucions bàsiques factibles i punts extrems. Anàlisi de sensibilitat. Introducció a la presència de no linealitats en els models.
3. Models de programació continua i sistemes de suport a la presa de decisions
   Exemples de problemes de PL: planificació de la producció; problema d'inversió; problemes de transport; problemes de mescla; problemes d'inventari. Problemes de Fluxos sobre xarxes.
   Problemes multiobjectiu. Programació per objectius. Presencia de no linealitats en els models.
4. Programació Lineal Entera
   Propietats dels problemes de PLE. Alguns problemes de PLE: problema de la planificació de treballadors; problemes de routing problemes de cost fix i de localització, Algorismes de PLE: plans secants; algorisme del Branch&Bound
5. Mètodes Heurístics per a la resolució de problemes PLE
   Heurístiques constructives: Mètodes Greedy. Cerca local. Metaheurístiques: més enllà del òptim local. El mètode del recuit simulat. Cerca tabú, Algoritmes genètics. Altres mètodes. Aplicacions de heurístiques per a problemes de routing i d'altres.
   
6. Cerca i avaluació d'informació per la realització d'un treball en I.O.
   Cercadors acadèmics. Bases de dades i revistes electròniques. Avaluació de la informació
7. Motivació i actitud per la feina en I.O.
   Motivació per la responsabilitat, la qualitat en la pròpia feina i la realització professional. Capacitat d'adaptació als canvis organitzatius, tecnològics. Treball en equip. Adaptació a la falta d'informació i a les limitacions materials i temporals
   

Activitats

Activitat Acte avaluatiu

Metodologia docent

Mètode d'avaluació

Bibliografia

Bàsica:

• Mathematical Programming: operations research - Winston W.L; Venkataramanan, M, Brooks/Cole, 2003. ISBN: 0534359647
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991002747009706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• AMPL a modeling language for mathematical programming - Fourer, R.; Gay, D.M.; Kernighan, B.W, Thomson/Brooks/Cole, 2003. ISBN: 0534388094
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991002629329706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Model building in mathematical programming - Williams, H.P, John Wiley and Sons, 2013. ISBN: 9781118443330
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991003969709706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Introduction to operations research - Hillier, F.S.; Lieberman, G.J, McGraw Hill, 2010. ISBN: 9780073523453
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004036339706711&context=L&vid=34CSUC_UPC:VU1&lang=ca

Complementaria:

• Linear and integer programming: theory and practice - Sierksma, G, CRC , 2002. ISBN: 0824706730
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004001629706711&context=L&vid=34CSUC_UPC:VU1&lang=ca

Web links

• 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 http://ifors.org/web/
• Material Acadèmic del Professor Beasley J.E. al Imperial College de Londres http://people.brunel.ac.uk/~mastjjb/jeb/or/contents.html
• Pàgina del IBM CPLEX Optimization Studio. http://www-01.ibm.com/software/integration/optimization/cplex-optimization-studi
• Pàgina del Software de Modelització AMPL. http://www.ampl.com/
• Pàgina de la High School Operations Research http://www.hsor.org/

Capacitats prèvies