Responsable: | (-) |
Altres: | (-) |
Crèdits | Dept. |
---|---|
7.5 (6.0 ECTS) | EIO |
Responsable: | (-) |
Altres: | (-) |
L'assignatura presenta alguns dels mètodes fonamentals de la investigació operativa. La investigació operativa és una disciplina basada en la formulació de models, desenvolupament i aplicació d'algorismes per a la resolució de problemes de presa de decisions. L'assignatura introdueix també els llenguatges de modelització i el software necessaris per a la resolució efectiva de problemes. El curs té una orientació pràctica. Es presentaran diferents aplicacions dels models i algorismes introduïts a problemes complexos que l'estudiant pot trobar-se en el futur, tant de tipus tècnic com a nivell de gestió.
Hores estimades de:
T | P | L | Alt | L Ext. | Est | A Ext. |
Teoria | Problemes | Laboratori | Altres activitats | Laboratori extern | Estudi | Altres hores fora d'horari fixat |
|
T | P | L | Alt | L Ext. | Est | A Ext. | Total | ||
---|---|---|---|---|---|---|---|---|---|---|
8,0 | 4,0 | 10,0 | 0 | 10,0 | 10,0 | 0 | 42,0 | |||
- Models lineals, enters i no lineals. Exemples i estudis de cas.
- Modelització amb fulls de càlcul - El llenguatge de modelització AMPL. A les sessions de laboratori es mostraran els entorns de modelització Excel i AMPL. A les sessions de teoria i laboratori i es presentaran 5 estudis de cas: - Gestió de projectes amb limitacions de temps (programació lineal). - Flux màxim concurrent en una xarxa de transmissió multiarticle (fluxos en xarxes). - Problema d'itineraris: TSP (programació entera). - Disseny de xarxes (programació entera). - Optimització d'una Support Vector Machine (programació no lineal, quadràtica) Dos d'aquests casos s'usaran per a la nota de pràctiques. |
|
T | P | L | Alt | L Ext. | Est | A Ext. | Total | ||
---|---|---|---|---|---|---|---|---|---|---|
8,0 | 2,0 | 2,0 | 0 | 0 | 8,0 | 0 | 20,0 | |||
- Propietats bàsiques de la programació lineal.
- Complexitat computacional de la programació lineal. - L'algorisme del simplex (versió primal, forma matricial). |
|
T | P | L | Alt | L Ext. | Est | A Ext. | Total | ||
---|---|---|---|---|---|---|---|---|---|---|
10,0 | 4,0 | 4,0 | 0 | 0 | 12,0 | 0 | 30,0 | |||
A les sessions de teoria es veuran:
- Propietats bàsiques dels problemes amb estructura de xarxa. - Tipus de models de fluxos en xarxes. Exemples. - Algorisme del simplex per al problema de cost mínim en fluxos en xarxes. - Algorismes per al problema de camins mínims amb costos positius (Dijkstra) i qualsevols ("label-correcting"). - Algorisme per al problema de flux màxim. |
|
T | P | L | Alt | L Ext. | Est | A Ext. | Total | ||
---|---|---|---|---|---|---|---|---|---|---|
4,0 | 1,0 | 1,0 | 0 | 0 | 4,0 | 0 | 10,0 | |||
L'algorisme de branch and bound.
|
|
T | P | L | Alt | L Ext. | Est | A Ext. | Total | ||
---|---|---|---|---|---|---|---|---|---|---|
4,0 | 2,0 | 0 | 0 | 0 | 4,0 | 0 | 10,0 | |||
Propietats bàsiques de la programació no lineal.
|
|
T | P | L | Alt | L Ext. | Est | A Ext. | Total | ||
---|---|---|---|---|---|---|---|---|---|---|
6,0 | 2,0 | 0 | 0 | 0 | 6,0 | 0 | 14,0 | |||
- Heurístiques per a problemes de seqüenciació de tasques.
- Heurístiques per a problemes de disseny de xarxes. - Heurístiques per a problemes d'itineraris. |
|
T | P | L | Alt | L Ext. | Est | A Ext. | Total | ||
---|---|---|---|---|---|---|---|---|---|---|
2,0 | 0 | 0 | 0 | 0 | 1,0 | 0 | 3,0 |
Total per tipus | T | P | L | Alt | L Ext. | Est | A Ext. | Total |
43,0 | 15,0 | 17,0 | 0 | 10,0 | 45,0 | 0 | 130,0 | |
Hores addicionals dedicades a l'avaluació | 5,0 | |||||||
Total hores de treball per l'estudiant | 135,0 |
Hi haurà sessions de teoria, problemes i laboratori. A teoria s'introdueixen els coneixements bàsics de l'assignatura. A les sessions de problemes se solucionaran exercicis directament basats en la teoria. A les sessions de laboratori es resoldran casos reals de mida petita, on l'estudiant formularà i solucionarà un problema amb l'ajut de software de modelització i els "solvers" apropiats.
La nota final NF es calcularà com NF= 0.7*NT+0.3*NP, essent NT la nota de teoria i NP la de pràctiques.
NT: Hi haurà un examen parcial a meitat del quadrimestre, alliberatori de matèria de cara a l'examen final per als estudiants que tinguin nota superior o igual a 4. Aquest parcial, per als qui tinguin nota superior o igual a 4, puntua sobre NT/2. L'examen final puntua sobre NT/2 per als qui hagin superat el parcial amb nota superior o igual a 4, i NT per als qui no.
NP: Hi haurà dues pràctiques que es realitzaran en horari de classe a les sessions de laboratori. Cada una consistirà en la modelització i resolució d'un cas usant el software de modelització-optimització AMPL. Cada pràctica puntua sobre NP/2.
Es requereix un mínim de coneixements que l'estudiant ja ha adquirit en assignatures prèvies. En particular, s'usen nocions bàsiques de:
- programació
- àlgebra (operacions amb matrius i vectors)
- estructures de dades per a grafs
- algorismes bàsics per a grafs.