Investigació Operativa

Crèdits
6
Tipus
  • GRAU: Complementària d'especialitat (Computació)
  • GCED: Optativa
Requisits
Departament
EIO
En l'entorn d'organitzacions complexes d'abast mitjà i gran en la indústria, l'administració i els negocis, els resultats de la presa de decisions que poden incidir en el seu funcionament/rendiment és de la màxima importància per als seus responsables. La Investigació Operativa és una disciplina orientada a proporcionar eines d'elaboració, d'anàlisi i de resolució eficient de models d'aquests sistemes mitjançant les quals es pot mesurar quantitativament els resultats de les decisions de la direcció de les organitzacions. Avui en dia resulta clau la integració d'aquesta classe de sistemes d'ajut a la presa de decisions dins dels diferents sistemes de informació que poden operar en les organitzacions. El curs s'inicia presentant un cas d'estudi amb el que il·lustrar aquests conceptes i continua amb l'exposició de models assentats en la Investigació Operativa i les seves tècniques de resolució eficient. Al llarg del curs els estudiants desenvoluparan i resoldran un d'aquests models adaptat a les necessitats del cas real d'una organització i s'avaluarà i discutirà la seva interacció amb els sistemes d'informació presents en ella.

Professorat

Responsable

Altres

Hores setmanals

Teoria
2
Problemes
1
Laboratori
1
Aprenentatge dirigit
0
Aprenentatge autònom
6

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


    Bloc 1. Presentació d'objectius i de models bàsics de I.O.

    Seguiment de les exposicions i revisió del material proprocionat per les corresponents sessions. Assimilació del paper dels problemes d'optimització com a font de modelització.
    • Teoria: Descripció dels objectius de la Investigació Operativa com disciplina. Descripció de les etapes del procés metodològic de formulació de un model. Validació de un model. Presentacio de un cas d'estudi. Descripció i anàlisi de diversos casos d'estudi implicats
    • Aprenentatge autònom: Lectura i estudi de material previ a les sessions de teoria
    Objectius: 1 3 2
    Continguts:
    Teoria
    1h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    1h

    Anàlisi de fonts d'informació

    Anàlisi i avaluació de la informació proporcionada de determinades referències (paquets de software/referències que poden aportar solucions al Treball de Curs.
    • Teoria: Avaluació del valor i mancances de la informació sel.leccionada.
    • Aprenentatge autònom: Identificació del valor i de les llacunes de informació envers la finalitat del Treball de Curs
    Objectius: 12
    Continguts:
    Teoria
    0.5h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    6h

    Bloc 2. Models d'Optimització Continua i sistemes d'ajut a la presa de decisions

    Seguiment dels models exposats en les sessions de teoria. Resolució individual i monitoritzada d'exercicis de modelització. A les sessions de laboratori, entrenament en l'ús de llenguatges de representació algebràica.
    • Teoria: Descripció de models en programació lineal i presencia de no linealitats. Exposició del principi d'optimalitat Pareto. Minimització de la norma L1. Exposició de la programació per objectius i del pitjor cas possible
    • Problemes: Formulació de problemes i modelització de casos d'estudi
    • Aprenentatge autònom: Lectura i estudi de material previ a sessions de teoria. Preparació i lectura del material per a exercicis de laboratori
    Objectius: 1 3 4
    Continguts:
    Teoria
    4h
    Problemes
    2h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    6h

    Ús de cercadors de referències, de B.D. i de Revistes Electròniques

    Cerca de publicacions de determinats autors en relació al Treball de Curs. Visionat de vídeos http://bibliotecnica.upc.edu/habilitats/eines-de-cerca-dinformacio#4 http://bibliotecnica.upc.edu/habilitats/l039estrategia-de-cerca
    • Teoria: Es proporcionen determinats autors i temes en relació al Treball de Curs
    • Aprenentatge autònom: Ús de cercadors i primer anàlisi de referències
    Objectius: 12
    Continguts:
    Teoria
    0.5h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    4h

    Avaluació de la cerca de referències en relació al Treball de Curs

    Entrega de informe amb les 5 referencies més significatives i amb detall de les eines de cerca usades per trobar-les
    Objectius: 12
    Setmana: 4
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Bloc 3. Problemes de Programació Continua

    Seguiment de classes de teoria amb el suport de material docent elaborat específicament. Assimilació dels conceptes de base factible, base òptima, òptim local i global. Capacitat per efectuar passes de l'algoritme del símplex. Resolució individual de problemes i seguiment de sessions de problemes. Capacitat de definir problemes de programació lineal i no lineal usant llenguatges algebraics i de resoldre'ls a les sessions de laboratori
    • Teoria: Caracterització de problemes de programació lineal. Propietats bàsiques dels problemes de programació lineal. Concepte de regió factible. Òptims únics i alternatius. Concepte de vèrtex d'una regió polièdrica. Exemples. Bases i solucions bàsiques algoritme del simplex. Desenvolupament a les sessions de teoria de la formulació algebràica básica. Exemples de iteracions amb l'algoritme del símplex. Mètode de les variables artificials. Presència de no linealitats. Característiques de les solucions.
    • Problemes: Resolució de problemes gràficament en dues dimensions. Iteracions amb l'algoritme del simplex. Resolució de problemes simples amb llenguatges algebraics i avenç de conceptes per a classes de laboratori
    • Aprenentatge autònom: Treball per part de l'estudiant amb material docent i col.lecció de problemes. Preparació de sessions de laboratori. Exercicis per compta pròpia.
    Objectius: 5 6
    Continguts:
    Teoria
    5h
    Problemes
    3h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    8h

    Actitud i motivació envers el treball. A1

    Els estudiants evaluen exercicis de laboratori lliurats d'acord a directrius recollides en una rúbrica.
    • Laboratori: Avaluació de la qualitat d'exercicis
    • Aprenentatge autònom: Preparació i assimilació per part de l'estudiant
    Objectius: 13
    Continguts:
    Teoria
    0h
    Problemes
    0h
    Laboratori
    1h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    3h

    Avaluació de les fonts d'informació

    Lliurament d'un informe fent l'avaluació
    Objectius: 12
    Setmana: 6
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Avaluació actitud i motivació envers el treball. A1

    Ús de rúbriques
    Objectius: 13
    Setmana: 7
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Bloc 4. Problemes de fluxos en xarxes

    Efectuar iteracions del simplex per al problema de min-cost. aplicació de algoritmes de camins mínims. aplicació de l'algoritme de max-flow min.cut
    • Teoria: Exposició del model de min-cost. Aplicació de l'algoritme del símplex. Exposició i derivació dels algoritmes de camins mínims. Ilustració del teorema de max-flow min-cut
    • Problemes: Exercicis i tests de seguiment dels mètodes i algoritmes exposats
    • Aprenentatge autònom: Revisió del material presentat a clases de teoria i preparació de tests de seguiment. Exercicis per compta pròpia.
    Objectius: 1 7
    Continguts:
    Teoria
    3h
    Problemes
    4h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    8h

    Avaluació de la pràctica de laboratori 1

    S'entregarà un qüestionari emplenat al final de la sessió. Aquest qüestionari serà puntuable.
    Objectius: 3 5 6 4 7 2
    Setmana: 8
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Parcial 1

    Prova consistent en problemes per als blocs 1,2,3 i 4 de l'assignatura i la part corresponent del bloc 8 relacionada amb els blocs 1,2,3 i 4
    Objectius: 1 3 5 6 4 7 2
    Setmana: 8
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Bloc 5. Modelització en Programació Lineal Entera

    Adquirir capacitat de modelitzar usant variables binàries condicions de tipus lògic. Tenir com referencia els models presentats a les sessions de teoria per a poder emprendre desenvolupaments i modelitzacions pròpies
    • Teoria: Exposició dels models de recobriment i partició de conjunts i de la metodologia per reflectir condicions de tipus lògic amb variables enteres. Exposició dels models de càrrega fixa.
    • Problemes: Modelització de problemes amb variables enteres/binàries dins d'una col.lecció de problemes
    • Laboratori: Formulació, implementació i resolució de un model prèviament especificat en un guió de pràctiques de laboratori i de variants proposades. Anàlisi dels resultats
    • Aprenentatge autònom: Lectura i estudi del material presentat a les sessions de teoria. Resolució individual, d'exercicis de modelització. Resolució de les modelitzacions usant llenguatges algebràics de modelització. Preparació i lectura del material per a les sessions de laboratori
    Objectius: 1 9
    Continguts:
    Teoria
    2h
    Problemes
    2h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    8h

    Actitud i motivació envers el treball. A2

    Anàlisi dels canvis proposats pel professor en el Treball de Curs i proposta de canvis a realitzar en un periode de temps limitat. Discusió amb altres grups de treball de l'adequació de les solucions adoptades
    • Laboratori: Sessio d'aprenentatge col.laboratiu
    • Aprenentatge autònom: Anàlisi dels canvis proposts el professor en el treball de curs. Preparació prèvia a la sessió
    Objectius: 13
    Continguts:
    Teoria
    0h
    Problemes
    0h
    Laboratori
    2h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    5h

    Avaluació actitud i motivació envers el treball. A2

    Entrega de informe al final de sessió d'parenentatge col.laboratiu
    Objectius: 13
    Setmana: 11
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Bloc 6. Problemes de Programació Lineal Entera

    Assimilació del conceptes de ramificació i acotació. Efectuar iteracions de l'algoritme de Branch and Bound amb problemes petits.
    • Teoria: Exposició de propietats bàsiques dels problemes de programaciói lineal entera i del concepte de relaxació lineal. Ilustració del funcionament de l'algoritme de branch and bound.
    • Problemes: Resolució de petits problemes de programació lineal entera.
    • Aprenentatge autònom: Lectura i estudi del material de les sessions de teoria. Preparació d'exercicis per classe de problemes
    Objectius: 8
    Continguts:
    Teoria
    2h
    Problemes
    2h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    4h

    Actitud i motivació envers el treball. A3

    Presentació oral del treball de curs en un temps limitat (10min per grup de treball)
    • Laboratori: Presentació de treballs de curs i discusió
    • Aprenentatge autònom: Preparació per part de l'estudiant
    Objectius: 13
    Continguts:
    Teoria
    0h
    Problemes
    0h
    Laboratori
    2h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    5h

    Avaluació actitud i motivació envers el treball. A3

    Presentació oral
    Objectius: 13
    Setmana: 12
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Bloc 7. Mètodes heurístics per a problemes de Programació Lineal Entera. Metaheurístiques

    Conèixer els principals principis de construcció heurística de solucions. Saber construir algoritmes basats en metaheurístiques descrites. Mètode del recuit simulat, cerca tabu, cerca greedy.
    • Teoria: Métodes heuristics per als problemes de localització de plantes i del viatjant de comerç. Mètodes de intercanvi. Construcció de solucions. Heuristica de Christofides. Mètode del recuit simulat. Cerca tabú, Cerca Greedy
    • Problemes: Resoldre a mà casos de petita dimensió, aplicant les heurístiques vistes.
    • Aprenentatge autònom: Seguiment del material exposat i preparació de material per a les sessions de laboratori
    Objectius: 9
    Continguts:
    Teoria
    4h
    Problemes
    2h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    6h

    Avaluació de la pràctica de laboratori 2

    S'entregarà un qüestionari emplenat al final de la sessió. Aquest qüestionari serà puntuable.
    Objectius: 4 8 9 10 11 2
    Setmana: 13
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Pràctiques de laboratori 1 i 2

    Lectura prèvia del questionari i preparació de la pràctica. Execució de l'exercici i lliurament del qüestionari emplenat
    • Laboratori: Realització de les pràctiques en sessions de aula PC. Modelització usant llenguatges de representació algebràica. Resolució i anàlisi de les solucions Construcció d'un algoritme basat en un procediment metaheuristic vist a classe
    • Aprenentatge dirigit: Elaboració guiada de les pràctiques
    • Aprenentatge autònom: Preparació prèvia pel estudiant
    Objectius: 3 5 6 7 8 10
    Continguts:
    Teoria
    0h
    Problemes
    0h
    Laboratori
    4h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    4h

    Bloc 8. Treball de curs.

    Assimilar les diferentes etapes de formulació, anàlisi i assaig d'un model de optimització orientat a formar part de un sistema de suport a la presa de decisions. Anàlisi del rendiment computacional de les eines emprades i de les prestacions del model desenvolupat. Desenvolupament de les competències transversals associades a l'assignatura. El Treball de Curs es desenvoluparà en grups de dos estudiants.
    • Teoria: Sessions de suport i aclaració de conceptes necessaris per a les tasques de formulació i resolució d'un cas d'estudi. Desenvolupament de competencies transversals associades a l'assignatura.
    • Laboratori: Sessions per a la implementació de les formulacions del models. Desenvolupament de competències transversals de l'assignatura
    • Aprenentatge autònom: Preparació de material. Estudi i anàlisi d'un petit cas d'estudi. Estudi i reforçament de conceptes vistos als continguts de l'assignatura
    Objectius: 1 3 4 7 9 10 11
    Continguts:
    Teoria
    2h
    Problemes
    0h
    Laboratori
    6h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    8h

    Avaluació del Treball de curs

    Es plantejarà als estudiants el desenvolupament d'un model. Es dedicaran sessions de laboratori per al seu seguiment. Objectius específics: - Desenvolupament de un model basat en problemes d'optimització com part integrant de un sistema d'ajut a la presa de decisions. - Analitzar les prestacions computacionals del model desenvolupat per al seu ús correcte en l'entorn dels sistemes d'ajut a la presa de decisions.
    Objectius: 1 3 4
    Setmana: 14
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Parcial 2

    Prova consistent en problemes per als blocs 5,6 i 7 de l'assignatura i la part corresponent del bloc 8 relacionada amb els blocs 5,6 i 7.
    Objectius: 8 9 10 11
    Setmana: 14
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Examen Final

    Prova consistent per a tots els blocs de l'assignatura
    Objectius: 2 1 3 5 6 4 7 8 9 10 11
    Setmana: 15 (Fora d'horari lectiu)
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Metodologia docent

    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,).

    Mètode d'avaluació

    Veure l'Addenda per al cas del curs 2020-21

    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

    Bibliografia

    Bàsic

    Complementari

    Web links

    Capacitats prèvies

    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