Pla docent de l'assignatura

 

 

Tanca imatge de maquetació

 

Imprimeix

 

Dades generals

 

Nom de l'assignatura: Programació Lineal i Entera

Codi de l'assignatura: 361226

Curs acadèmic: 2021-2022

Coordinació: F. JAVIER HEREDIA CERVERA

Departament: Facultat d'Economia i Empresa

crèdits: 6

Programa únic: S

 

 

Hores estimades de dedicació

Hores totals 150

 

Activitats presencials i/o no presencials

60

 

-  Teoricopràctica

Presencial

 

37.5

 

(Classes de teoria i problemes.)

 

-  Pràctiques d'ordinadors

Presencial

 

22.5

 

(Laboratoris computacionals amb SAS/OR.)

Treball tutelat/dirigit

38

(Realització i seguiment dels exercicis de teoria i laboratori proposats a classe.)

Aprenentatge autònom

52

 

 

Recomanacions

 

Tenir els coneixements i habilitats bàsiques d’anàlisi, àlgebra lineal, programació, investigació operativa i SAS de les assignatures següents:

  • Introducció al Càlcul, Àlgebra Lineal, Càlcul de Diverses Variables, Mètodes Numèrics.
  • Introducció a la Informàtica, Programació.
  • Software Estadístic (SAS).
  • Introducció a la Investigació Operativa

 

 

Competències que es desenvolupen

 

   -

Capacitat per detectar, formular i donar solució mitjançant models d'investigació operativa a problemes de presa de decisió de les diferents organitzacions, integrant, si és necessari, els resultats de les anàlisis estadístiques.

   -

Capacitat per aplicar les tècniques estadístiques i la investigació operativa en la millora de la qualitat i la productivitat en diferents entorns (tecnològics, industrials, etc.).

   -

Capacitat per identificar els principals models de la investigació operativa i conèixer-ne les propietats i l'àmbit d'aplicació.

   -

Capacitat per utilitzar el mètode d'optimització apropiat per als diferents models d'investigació operativa.

   -

Capacitat d'utilitzar llenguatges de programació per a la implementació d'algoritmes i de sistemes de gestió de bases de dades.

   -

Capacitat per seleccionar el mètode més adequat en la realització d'un estudi estadístic, d'avaluar les possibles alternatives i, si és procedent, incloure-hi l'anàlisi de costos i de recursos disponibles.

Objectius d'aprenentatge

 

Referits a coneixements

— Conèixer els models de presa de decisió més importants de la investigació operativa en diversos camps d’aplicació.

 

— Analitzar problemes de presa de decisió amb l’objectiu de formular i resoldre computacionalment el model d’optimització més adient.

 

— Comprendre les propietats matemàtiques dels problemes de programació lineal i dels seus algorismes de resolució, així com de les tècniques d’anàlisi de sensibilitat.

 

— Comprendre les propietats matemàtiques dels problemes de programació lineal entera i dels seus algorismes de resolució.

 

Referits a habilitats, destreses

— Aplicar sense ajut computacional els algorismes estudiats de programació lineal a problemes acadèmics de dimensió reduïda.

 

— Resoldre problemes pràctics mitjançant l’aplicació de tècniques d’anàlisi de sensibilitat a models de programació lineal.

 

— Aplicar, sense ajut computacional, els algorismes estudiats de programació lineal entera a problemes acadèmics de dimensió reduïda.

 

— Resoldre problemes reals de presa de decisió mitjançant l’ús d’algun programari d’optimització de referència corresponent als diferents algorismes d’optimització estudiats al llarg del curs.

 

 

Blocs temàtics

 

1. Introducció a la programació lineal (PL)

1.1. Formulació de problemes de programació lineal

1.2. Representació gràfica i solució de problemes de programació lineal

1.3. Repàs de conceptes d’àlgebra lineal. Complexitat algorísmica

1.4. Implementació i resolució computacional de problemes de programació lineal amb el procediment OPTMODEL de SAS/OR (laboratori 1)

2. Teoria de programació lineal i algorisme del símplex

2.1. Geometria en programació lineal: poliedres i conjunts convexos, punts extrems, vèrtexs i solucions bàsiques, degeneració, existència i optimitat dels punts extrems

2.2. L’algorisme del símplex: condicions d’optimitat, desenvolupament de l’algorisme del símplex, implementacions del mètode del símplex, càlcul de solucions inicials factibles, eficiència computacional de l’algorisme del símplex

2.3. Estudi computacional de l’algorisme del símplex: procediment OPTLP de SAS/OR (laboratori 2)

3. Dualitat en programació lineal i anàlisi de sensibilitat

3.1. Teoria de dualitat: motivació del problema dual, teorema de dualitat i de folga complementària, variables duals i costos marginals, l’algorisme del símplex dual

3.2. Anàlisi de sensibilitat: anàlisi de sensibilitat local, anàlisi de sensibilitat global, programació paramètrica

3.3. Anàlisi de sensibilitat global amb SAS/OR: programació amb el procediment OPTMODEL (laboratori 3)

4. Models de programació lineal entera (PLE)

4.1. Definició i formulació de problema de PLE i PLE mixta

4.2. Formulacions vàlides, fortes i ideals de problemes de programació entera

4.3. Implementació de problemes PLE amb SAS/OR (PROC OPTMODEL) i enllaç amb bases de dades SAS (laboratori 4)

5. Algorismes de programació lineal entera

5.1. Introducció: repàs de l’algorisme de ramificació i poda (branch-and-bound); classificació dels mètodes de programació lineal entera

5.2. Algorismes de plans de tall: algorisme genèric, talls de Gomory, algorisme de plans de tall de Gomory

5.3. Algorismes de ramificació i tall (branch-and-cut): algorisme genèric de ramificació i tall (branch-and-cut)

5.4. Resolució eficient de les relaxacions lineals: reoptimització amb el símplex dual

5.5. Implementació i resolució computacional de problemes PLE amb SAS/OR: procediment OPTMILP (laboratori 5)

 

 

Metodologia i activitats formatives

 

Classes de teoria (2h setmanals): sessions on es desenvolupen els aspectes més formals de l’assignatura, il·lustrats amb nombrosos exemples. Com a material de suport els alumnes disposen del següent material:

  • Apunts de l’assignatura, en forma de diapositives, que es presenten a cada sessió.
  • Videos amb l’explicació detallada de totes les lliçons de l’assignatura.
  • Qüestionaris moodle que es proposen a cada sessió de teoria i es resolen a la sessió de la setmana següent.
  • La Col·lecció d’Exercicis de Teoria, amb més de 100 exercicis completament resolts.


Sessions de laboratori (2h setmanals): sessions participatives destinades a la formulació matemàtica, la implementació computacional i l’anàlisi de les solucions dels problemes d’optimització estudiats a l’assignatura, amb el programari de modelització i optimització SAS/OR. Cada setmana es proposen uns exercicis de la Col·lecció d’Exercicis de Laboratori de l’assignatura, que es resolen i discuteixen a la sessió següent. Per a les sessions de laboratori, es desdobla el grup en dos grups de laboratori que imparteixen simultàniament dos professors.

 

 

Avaluació acreditativa dels aprenentatges

 

Proves d’avaluació continuada

  • Controls de teoria: dues proves fetes a classe amb l’objectiu de fer el seguiment dels aprenentatges relacionats amb les propietats dels models i algorismes d’optimització. NCT és la mitjana aritmètica de les notes sobre 10 dels dos controls de teoria. El primer control compren els temes 1 i 2 i el segon els temes 3 i 4.
  • Controls de laboratori: dues proves fetes a classe amb l’objectiu de fer el seguiment dels aprenentatges relacionats amb la formulació matemàtica, implementació i resolució computacional de problemes d’optimització. NCL és la mitjana aritmètica de les notes sobre 10 dels dos controls de laboratori.  El primer control compren els temes 1 i 2 i el segon els temes 3 i 4.
  • Examen d’avaluació final: prova per acreditar l’adquisició de les habilitats teoricopràctiques de l’assignatura. Consta de dues parts, teoria i laboratori, amb notes NAT i NAL, respectivament.


Nota d’avaluació continuada: s’obté a partir de les notes dels controls NCT, NCL i de l’examen d’avaluació final NAT i NAL, aplicant l’expressió:

NAC = 0.6*min{ 10, FCT*NAT } + 0.4*min{ 10, FCL*NAL }

on FCT i FCL són factors entre 1 i 1.2 que s’obtenen a partir de les notes dels controls NCT i NCL segons les fórmules

FCT = 1 + 0.2*(NCT/10)
FCL = 1 + 0.2*(NCL/10)

Alliberament de matèria pel resultat dels controls:
  • L’alumnat amb una NCT ≥ 7 i cap nota de control de teoria < 4 o amb una NCL ≥ 7 i cap nota de control de laboratori < 4 queda alliberat de l’obligació de fer la prova d’avaluació final corresponent.
  • En cas d’alliberar matèria, a l’expressió on es calcula NAC, es substitueix min{ 10, FCT*NAT } per NCTmin{ 10, FCL*NAL } per NCL respectivament.
  • Si algú que pot alliberar matèria es presenta a la prova d’avaluació final, per tal de calcular la NAC es pren la millor nota entre els controls i la prova final, és a dir, 0.6*max{ min{ 10, FCT*NAT }, NCT } per a teoria i 0.4*max{ min{ 10, FCL*NAL }, NCL } per a laboratori.


Nota mínima: per aprovar l’avaluació continuada cal que NAC ≥ 5 i que NAT i NAL ≥ 4.

 

Avaluació única

Prova d’avaluació única
L’alumnat que vulgui renunciar a l’avaluació continuada i acollir-se a l’avaluació única ha de fer-ho abans de la data que s’estableixi, la qual es fa pública amb antelació suficient.

La prova d’avaluació única és el mateix examen final de l’avaluació continuada. Consta de les parts següents:

  • Teoria, en què s’avaluen els aprenentatges relacionats amb les propietats dels models i algorismes d’optimització. Consta d’un test (sense apunts) i un conjunt d’exercicis teòrics (amb transparències de classe).
  • Laboratori, en què s’avaluen els aprenentatges relacionats amb la formulació matemàtica, implementació i resolució computacional de problemes d’optimització. Consta d’un exercici pràctic a l’aula d’informàtica amb el programari usat durant el curs i les transparències de classe.


La nota d’avaluació única s’obté aplicant l’expressió NAU = 0.6*NAT + 0.4*NAL, en què NAT i NAL són, respectivament, la nota sobre 10 de la prova d’avaluació de teoria i de laboratori. Per aprovar l’avaluació única cal que NAU ≥ 5 i que NAT i NAL ≥ 4. La data de la prova d’avaluació única és la fixada pel Consell Docent.

Priova de reavaluació

La reavaluació consisteix en un examen de les mateixes característiques que la prova de l’avaluació única.
  • NRT serà la Nota de Reavaluació de Teoria.
  • NRL serà la Nota de Reavaluació de Laborarori.


i es regirà per la següent normativa:
  1. Només els alumnes que hagin suspès l’avaluació final (NAC< 5 o NAU < 5) poden presentar-se a l’examen de reavaluació.
  2. Les notes NAT i NAL es guarden a la reavaluació si són ≥ 4, és a dir:
    • Si NAT ≥ 4 llavors la NRT = NAT.
    • Si NAL ≥ 4 llavors la NRL = NAL.
  3. Només es pot examinar de les parts suspeses (NRT< 5 o NRL < 5). No es pot usar la reavaluació per millorar nota.
  4. La nota de la reavaluació, NR, es calcula com NR = 0.6*NRT+0.4*NRL.
  5. Per tal d’aprovar l’assignatura cal que NR ≥ 5, NRT ≥ 4 i NRL ≥ 4.

 

 

Fonts d'informació bàsica

Consulteu la disponibilitat a CERCABIB

Llibre

BERTSIMAS, Dimitris, et. al. Introduction to linear optimization. Belmont (Mass.): Athena Scientific,1997

Catàleg UB  Enllaç

Text electrònic

HEREDIA F.Javier.Transparències de Teoria de Programació Lineal i Entera.

  PDF disponible mitjançant el Campus Virtual.

HEREDIA, F. Javier, Transparències de Laboratori de Programació Lineal i Entera amb SAS/OR.

HEREDIA, F. Javier, Exercicis de Teoria de Programació Lineal i Entera.

  PDF disponible mitjançant el Campus Virtual.

HEREDIA, F. Javier, Exercicis de Laboratori de Programació Lineal i Entera amb SAS/OR.

  PDF disponible mitjançant el Campus Virtual.

SAS/OR 9.3 User’s Guide. Mathematical Programming.

Recurs electrònic extern  Enllaç