Investigació Operativa

Esteu aquí

Crèdits
6
Tipus
Complementària d'especialitat (Sistemes d'informació)
Requisits
  • Prerequisit: PE
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.

Professors

Responsable

  • Esteve Codina Sancho ( )

Altres

  • Elena Fernández Areizaga ( )

Hores setmanals

Teoria
2
Problemes
1
Laboratori
1
Aprenentatge dirigit
0.4
Aprenentatge autònom
5.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 - 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 - 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
    Related competences: 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
    Related competences: CCO2.4, CSI3.5, G8.3,
    Subcompetences:
    • Coneixer models simples en programació no lineal: problema del volum màxim d'un cilindre.
    • 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
  3. Conèixer i identificar els components d'un problema d'optimització
    Related competences: CCO1.3, CCO2.4,
    Subcompetences:
    • 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ó
  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.
    Related competences: CSI2.6, CSI1, CSI2.1,
    Subcompetences:
    • 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
    • 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,
    • Conèixer i interpretar els resultats i la informació proporcionada per un model amb multiples objectius
    • Identificació de variables de decisió i paràmetres de un model
    • Formulació de constriccions lineals i no lineals en un model
  5. Conèixer l'estructura i propietats dels problemes de programació lineal i no lineal
    Related competences: CCO2.4, CSI1,
    Subcompetences:
    • 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
  6. Conèixer i saber aplicar el mètode del simplex per resoldre problemes de programació lineal
    Related competences: CCO2.4,
    Subcompetences:
    • 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
  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.
    Related competences: CCO2.4, CSI2.2,
    Subcompetences:
    • 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
  8. Conèixer i aplicar tècniques bàsiques per resoldre problemes lineals amb variables enteres
    Related competences: CCO1.3, CCO2.4,
    Subcompetences:
    • 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
  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.
    Related competences: 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.
    • 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.
    • 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ó.
  10. Ser capaç d'aplicar mètodes heuristics per a problemes de programació lineal entera
    Related competences: CSI2.6, CCO1.3, CCO2.4,
    Subcompetences:
    • Aplicar heurístiques per problemes de localització de plantes
    • Aplicar heurístiques d'intercanvi per al problema del viatjant de comerç
  11. Conèixer i poder aplicar diferents tipus de metaheurístiques vistos en l'assignatura
    Related competences: 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.
    Related competences: G6.3,
    Subcompetences:
    • 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)
    • Saber utilitzar i reconèixer la informació adequada per a la realització d'un treball
  13. Tenir actitud apropiada i motivació envers la feina
    Related competences: G8.3,
    Subcompetences:
    • 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
    • Motivació per la responsabilitat, la qualitat en la pròpia feina i la realització professional

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
Tipus: examen de laboratori
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
Tipus: examen de laboratori
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
Tipus: examen de laboratori
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
4h
Problemes
3h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
7h

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
Tipus: entrega
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
Tipus: examen de teoria
Teoria
2h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
4h

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
4h
Problemes
2h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
6h

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
Tipus: examen de laboratori
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
Tipus: examen de laboratori
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
Tipus: entrega
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
2h
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
Tipus: examen de laboratori
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
Tipus: examen de teoria
Teoria
2h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
4h

Examen Final

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

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ó

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àsica:

Complementaria:

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