Guia docent 2006_07 Escola Tècnica Superior d`Enginyeria Química

1. Donat qualsevol problema d'optimització, escriure el corresponent model matemàtic que inclourà una funció objectiu, una o més variables de disseny, les variables accessòries que s'escaiguin, i diferents restriccions de tipus igualtat i/o desigualtat. Aquest model ha de ser matemàticament consistent, raonablement escalat, i resoluble a la pràctica (amb els mitjans disponibles). Caldrà especificar també el tipus de variables utilitzades (reals, senceres, binàries, etc.) i els seus límits (positives, negatives, restringides, etc.).

A8
A10
A15

B1
B3
B8
B17

2. Escriure els programes corresponents amb el llenguatge de programació propi del curs (GAMS) per a resoldre els models matemàtics referits a l'objectiu anterior.

B1
B3
B4
B9

C2

3. Interpretar la solució numèrica obtinguda amb el software GAMS en termes de les variables i equacions d'interès.

B3
B8

C2

4. Determinar la sensibilitat de la solució obtinguda amb GAMS a les variacions dels diferents paràmetres, o a possibles variacions introduïdes en el model matemàtic.

B3
B8

C2

AP1. Els alumnes treballen en un projecte de disseny (a nivell d'estudi preliminar). Cal dissenyar la millor planta i els millors equipaments possibles per a assolir els objectius de producció establerts, tot respectant una sèrie de criteris. El disseny òptim sovint implica una maximització dels guanys, o una minimització dels costs, de la despesa energètica, de la generació de residus tòxics i nocius per l'ambient, dels riscs d'operació, o bé una maximització de la producció i/o de la qualitat dels productes, etc. Tenint això en compte, cada grup negociarà amb el professor de l'assignatura a quins elements del seu projecte aplicaran els conceptes i la metodologia de treball propis del disseny òptim, tenint en compte que la feina a realitzar ha de ser (aproximadament) equivalent a un 25% de l'assignatura.

B1
B2
B3
B4
B5
B6
B7
B8
B9
B12
B17

C2

Tema 2.1. Escriure la funció de Lagrange corresponent a qualsevol model matemàtic d'optimització algebraica, és a dir, el conjunt format per una funció objectiu i les diferents restriccions del tipus igualtat o desigualtat. Aquesta formulació inclourà un multiplicador de Lagrange per a cada restricció, i podria també incloure les variables artificials necessàries per a convertir les restriccions de tipus desigualtat en restriccions del tipus igualtat.

B8

Tema 2.2. Donat un problema d'optimització sense restriccions, utilitzar els criteris de condició necessària i condició suficient per a cercar els diferents mínims i màxims locals de la funció.

B8

Tema 2.3. Donada una funció d’una o més variables, dir si en un determinat punt la funció és còncava o si és convexa.

B8

Tema 2.5. Donat un model d’optimització multivariable amb restriccions, determinar els possibles òptims del problema mitjançant les condicions de Karush-Kuhn-Tucker. Donades les coordinades d’un punt determinat, utilitzar les condicions de Karush-Kuhn-Tucker per a comprovar si el problema presenta un òptim local en aquest determinat punt.

B3
B8

Tema 3.1. Identificar si un determinat problema d’optimització es pot caracteritzar com un model matemàtic de programació lineal. Si és així, escriure el corresponent model matemàtic.

B3
B8
B17

Tema 3.2. Per un model de programació lineal amb dues variables, determinar la solució del problema amb l’ajut de la representació gràfica corresponent.

B3
B9

Tema 3.3. A partir d’un model de programació lineal en format no estàndard, escriure el corresponent model en format estàndard (la funció s’ha de minimitzar, totes les restriccions són del tipus major o igual, i existeix com a mínim un límit inferior o superior per a cada variable depenent del signe del seu coeficient a la funció objectiu).

B3

Tema 3.4. Per un model de programació lineal en forma estàndard, amb n variables i m restriccions, calcular el nombre màxim de solucions bàsiques factibles.

B8

Tema 3.5. Donat un model de programació lineal de petita grandària, determinar la solució (sense l’ajut de l’ordinador) utilitzant l’algoritme símplex.

B8

Tema 3.6. Donat un model matemàtic de programació lineal, escriure el corresponent model dual, i viceversa.

B8

Tema 4.1. Per funcions d’una sola variable, determinar numèricament els òptims de la funció utilitzant (sense ajut de l’ordinador) algun dels mètodes tractats a l’assignatura (bisecció, raó àuria, cerca quadràtica, i Newton).

B1
B3
B8

Tema 4.2. Per problemes amb funcions de més d'una variable sense restriccions, determinar numèricament els òptims de la funció utilitzant (sense l'ajut de l'ordinador) el mètode de Newton (s'entén que s'aplicarà a problemes de petita grandària, amb 2 o 3 variables com a molt).

B8

Tema 4.3. Avaluar l’efecte dels valors inicials assumits en la solució obtinguda al problema d’optimització no lineal (car diferents valors inicials poden portar a diferents òptims locals). Per problemes resolts amb l’ordinador (GAMS), comparar també els resultats obtinguts utilitzant els diferents paquets (solvers) de programació no lineal.

B1
B2
B3
B4
B8
B9
B17

C2

Tema 5.1. Per models de programació lineal mixta (amb variables senceres), utilitzar l’algoritme de branch and bound per a resoldre, sense l’ajut de l’ordinador, problemes de petita grandària.

B8

Tema 5.2. Identificar, a partir de l’enunciat, un problema de programació mixta i escriure el model matemàtic corresponent, introduint les variables de decisió (binàries) que s’escaiguin.

B3
B17

Tema 6.1. Identificar, a partir de l’enunciat, un problema del camí més curt.

B17

Tema 6.2. Representar simbòlicament els problemes del camí més curt en forma de graf.

B3
B8
B9
B17

Tema 6.3. Resoldre, sense l’ajut de l’ordinador, problemes de camí més curt de petita grandària utilitzant algun dels algoritmes específics tractats a l’assignatura (algorisme de Dijkstra i algorisme per a digrafs acíclics; correcció d’etiquetatge amb implementació FIFO).

B1
B8
B9

Tema 6.4. Plantejar els diagrames CPM i els problemes de programació dinàmica discreta com a problemes del camí més curt i resoldre’ls.

A3

B3
B8
B9

Tema 6.5. Escriure el model de programació lineal corresponent als problemes del camí més curt.

B8

Tema 7.1. Identificar, a partir de l’enunciat, un problema de xarxa de flux, i dir si es tracta d’un problema de transport, d’assignació, de transbord, de flux màxim, o de flux de cost mínim.

B17

Tema 7.2. Representar simbòlicament els problemes de xarxa de flux en forma de graf.

B3
B8
B9
B17

Tema 7.3. Resoldre, sense l’ajut de l’ordinador, problemes de xarxa de flux de petita grandària utilitzant l’algoritme símplex per a xarxes de flux.

B3
B8
B9

Tema 7.4. Escriure el model de programació lineal corresponent als problemes de xarxa de flux enumerats a l’objectiu 7.1.

B8

Tema 2.4. Donat un problema d'optimització multivariable amb restriccions, determinar si es tracta o no d'un problema de Programació Convexa

B8

Competències	Objectius d'aprenentatge	Continguts
Planificació	Metodologies	Atenció personalitzada
Avaluació	Fonts d'informació	Recomanacions

Objectius	Competències
1. Donat qualsevol problema d'optimització, escriure el corresponent model matemàtic que inclourà una funció objectiu, una o més variables de disseny, les variables accessòries que s'escaiguin, i diferents restriccions de tipus igualtat i/o desigualtat. Aquest model ha de ser matemàticament consistent, raonablement escalat, i resoluble a la pràctica (amb els mitjans disponibles). Caldrà especificar també el tipus de variables utilitzades (reals, senceres, binàries, etc.) i els seus límits (positives, negatives, restringides, etc.).	A8 A10 A15	B1 B3 B8 B17
2. Escriure els programes corresponents amb el llenguatge de programació propi del curs (GAMS) per a resoldre els models matemàtics referits a l'objectiu anterior.		B1 B3 B4 B9	C2
3. Interpretar la solució numèrica obtinguda amb el software GAMS en termes de les variables i equacions d'interès.		B3 B8	C2
4. Determinar la sensibilitat de la solució obtinguda amb GAMS a les variacions dels diferents paràmetres, o a possibles variacions introduïdes en el model matemàtic.		B3 B8	C2
AP1. Els alumnes treballen en un projecte de disseny (a nivell d'estudi preliminar). Cal dissenyar la millor planta i els millors equipaments possibles per a assolir els objectius de producció establerts, tot respectant una sèrie de criteris. El disseny òptim sovint implica una maximització dels guanys, o una minimització dels costs, de la despesa energètica, de la generació de residus tòxics i nocius per l'ambient, dels riscs d'operació, o bé una maximització de la producció i/o de la qualitat dels productes, etc. Tenint això en compte, cada grup negociarà amb el professor de l'assignatura a quins elements del seu projecte aplicaran els conceptes i la metodologia de treball propis del disseny òptim, tenint en compte que la feina a realitzar ha de ser (aproximadament) equivalent a un 25% de l'assignatura.		B1 B2 B3 B4 B5 B6 B7 B8 B9 B12 B17	C2
Tema 2.1. Escriure la funció de Lagrange corresponent a qualsevol model matemàtic d'optimització algebraica, és a dir, el conjunt format per una funció objectiu i les diferents restriccions del tipus igualtat o desigualtat. Aquesta formulació inclourà un multiplicador de Lagrange per a cada restricció, i podria també incloure les variables artificials necessàries per a convertir les restriccions de tipus desigualtat en restriccions del tipus igualtat.		B8
Tema 2.2. Donat un problema d'optimització sense restriccions, utilitzar els criteris de condició necessària i condició suficient per a cercar els diferents mínims i màxims locals de la funció.		B8
Tema 2.3. Donada una funció d’una o més variables, dir si en un determinat punt la funció és còncava o si és convexa.		B8
Tema 2.5. Donat un model d’optimització multivariable amb restriccions, determinar els possibles òptims del problema mitjançant les condicions de Karush-Kuhn-Tucker. Donades les coordinades d’un punt determinat, utilitzar les condicions de Karush-Kuhn-Tucker per a comprovar si el problema presenta un òptim local en aquest determinat punt.		B3 B8
Tema 3.1. Identificar si un determinat problema d’optimització es pot caracteritzar com un model matemàtic de programació lineal. Si és així, escriure el corresponent model matemàtic.		B3 B8 B17
Tema 3.2. Per un model de programació lineal amb dues variables, determinar la solució del problema amb l’ajut de la representació gràfica corresponent.		B3 B9
Tema 3.3. A partir d’un model de programació lineal en format no estàndard, escriure el corresponent model en format estàndard (la funció s’ha de minimitzar, totes les restriccions són del tipus major o igual, i existeix com a mínim un límit inferior o superior per a cada variable depenent del signe del seu coeficient a la funció objectiu).		B3
Tema 3.4. Per un model de programació lineal en forma estàndard, amb n variables i m restriccions, calcular el nombre màxim de solucions bàsiques factibles.		B8
Tema 3.5. Donat un model de programació lineal de petita grandària, determinar la solució (sense l’ajut de l’ordinador) utilitzant l’algoritme símplex.		B8
Tema 3.6. Donat un model matemàtic de programació lineal, escriure el corresponent model dual, i viceversa.		B8
Tema 4.1. Per funcions d’una sola variable, determinar numèricament els òptims de la funció utilitzant (sense ajut de l’ordinador) algun dels mètodes tractats a l’assignatura (bisecció, raó àuria, cerca quadràtica, i Newton).		B1 B3 B8
Tema 4.2. Per problemes amb funcions de més d'una variable sense restriccions, determinar numèricament els òptims de la funció utilitzant (sense l'ajut de l'ordinador) el mètode de Newton (s'entén que s'aplicarà a problemes de petita grandària, amb 2 o 3 variables com a molt).		B8
Tema 4.3. Avaluar l’efecte dels valors inicials assumits en la solució obtinguda al problema d’optimització no lineal (car diferents valors inicials poden portar a diferents òptims locals). Per problemes resolts amb l’ordinador (GAMS), comparar també els resultats obtinguts utilitzant els diferents paquets (solvers) de programació no lineal.		B1 B2 B3 B4 B8 B9 B17	C2
Tema 5.1. Per models de programació lineal mixta (amb variables senceres), utilitzar l’algoritme de branch and bound per a resoldre, sense l’ajut de l’ordinador, problemes de petita grandària.		B8
Tema 5.2. Identificar, a partir de l’enunciat, un problema de programació mixta i escriure el model matemàtic corresponent, introduint les variables de decisió (binàries) que s’escaiguin.		B3 B17
Tema 6.1. Identificar, a partir de l’enunciat, un problema del camí més curt.		B17
Tema 6.2. Representar simbòlicament els problemes del camí més curt en forma de graf.		B3 B8 B9 B17
Tema 6.3. Resoldre, sense l’ajut de l’ordinador, problemes de camí més curt de petita grandària utilitzant algun dels algoritmes específics tractats a l’assignatura (algorisme de Dijkstra i algorisme per a digrafs acíclics; correcció d’etiquetatge amb implementació FIFO).		B1 B8 B9
Tema 6.4. Plantejar els diagrames CPM i els problemes de programació dinàmica discreta com a problemes del camí més curt i resoldre’ls.	A3	B3 B8 B9
Tema 6.5. Escriure el model de programació lineal corresponent als problemes del camí més curt.		B8
Tema 7.1. Identificar, a partir de l’enunciat, un problema de xarxa de flux, i dir si es tracta d’un problema de transport, d’assignació, de transbord, de flux màxim, o de flux de cost mínim.		B17
Tema 7.2. Representar simbòlicament els problemes de xarxa de flux en forma de graf.		B3 B8 B9 B17
Tema 7.3. Resoldre, sense l’ajut de l’ordinador, problemes de xarxa de flux de petita grandària utilitzant l’algoritme símplex per a xarxes de flux.		B3 B8 B9
Tema 7.4. Escriure el model de programació lineal corresponent als problemes de xarxa de flux enumerats a l’objectiu 7.1.		B8
Tema 2.4. Donat un problema d'optimització multivariable amb restriccions, determinar si es tracta o no d'un problema de Programació Convexa		B8