Optimització contínua. Pràctiques

en w ::, o - ten ,_ en w en w :::, a - z o ,w t- - U) w - o z ,w - u z w � => 1- <( - u z w [ LLCTE oc PRACTIQUES OPTIMITZACIO " CONTINUA Narcís Nabona Francisco Javier Heredia Departament d'Estadística i lnvestigació Operativa UNIVEASITAT POLITÉCNICA DE CATALUNYA Blblioteca 1111111 �11111111 lm 11111111111�11 11�1 I� lllll 1111 llll 1400431615 -� Facultat de Matematiques i Estadística UNIVERSITAT POLITÉCNICA DE CATALUNYA PRACTIQUES D'OPTIMITZACIÓ CONTÍNUA I N arcís N abona UPC, Departament d'Estadística i Investigació Operativa OCl (FME) versió: 3/2/2003 Continguts: pag. Practiques a efectuar i ponderacions ................................................... 1 Elements basics d'UNIX/LINUX ....................................................... 2 Programes, rutines i dades disponibles ................................................. 8 PROGRAMES PER A FUNCIONS QUADRÁTIQUES Utilització dels programes que tracten funcions quadratiques .......................... 12 Arxiu de dades per a les funcions quadratiques ........................................ 14 Programa funq d'analisi de funcions quadratiques i triangularització ................... 16 Funcions quadratiques i triangularització amb el programa fun.q ....................... 17 Programa qrad de minimització d'una quadratica pel metode del gradient ............. 18 Exercici de minimització d'una quadratica pel metode del gradient usant qrad ......... 19 Programa dirc de minimització d'una quadratica per direccions Q-conjugades ......... 20 Exercici de minimització d'una quadratica per direccions Q-conjugades usant dirc ..... 21 Programa qrac de minimització d'una quadratica pel metode del gradient conjugat .... 22 Exercici de minimització d'una quadratica pel metode del gradient conjugat usant qrac.23 PROGRAMES PER A FUNCIONS QUALSSEVOL Muntatge i utilització dels programes per a exercicis amb funcions qualssevol. ......... 2G Arxius de dades per a funcions qualsevol. ............................................. 29 Funció qualsevol: Estimació d'estat en una xarxa electrica ............................. 31 Programa fghee de verificació del codi desenvolupat propi. f ......................... 37 Programa nelm de minimització pel metode de Nelder-Mead ........................... 38 Exercici de minimització usant el metode de Nelder-Mead amb programa nelm ......... 40 Sortida escrita deguda a les rutines d'exploració lineal. ................................ 41 Programa grad de minimització pel metode del gradient .............................. 44 Exercici de minimització usant el metode del gradient amb programa grad ............ 4G Programa grac de minimització pel metode del gradient conjugat ..................... 47 Exercici de minimització usant el metode del gradient conjugat amb programa grac ... 49 Programa newt de minimització pel metode de Newton ................................ 50 Exercici de minimització usant el metode de Newton amb programa newt .............. G2 EXERCICI DE MÍNIMS QUADRATS Ús de la rutina dhfti del paquet SLATEC. ........................................... G4 MODELITZACIÓ AMB AMPL I RESOLUCIÓ DE PROBLEMES AMB CONSTIUCCIONS Problema de la pagesa usant el paquet CPLEX. ...................................... G8 Problema dels molins d'oli usant el paquet CPLEX i XPRESS ......................... (j1 Problema de l'estimació d'estat amb constriccions usant MINOS ....... ................ 67 BIBLIOGRAFIA Referencies ........................................................................... 70 Prnc. Optimització Contínua I Practi onderacions PRACTIQUES A EFECTUAR I PONDER.ACTONS Dins de l'assignatura Optimització Contínua I, les practiques representen un 30% de la qnalificació. Hi ha un conjunt de 11 practiques de les quals n'hi ha 4 de presentació obligatoria i que cal aprovar per separat per tenir opció a aprovar l'assignatura. La resta de practiques poden no presentar-se. Cada practica té uns punts assignats. Aquests punts, multiplicats per la respectiva quali ficació (de O a 10) de cada practica presentada dóna, per a cada equip de practiques, uns punts t.otals. La qualificació maxima en practiques es donara als equips que arribin o superin els 24 punts totals. Els qui no hi arribin seran qualificats, en practiques, proporcionalment. (Cada equip ha d'aprovar per separat cada practica obligatoria, independentment de la qualifició de practiques, per poder aprovar l'assignatura.) practica tipus qrad; gradient fun. quad. dirc dir. conj. fun. quad. qrac grad. conj. fun. quad. nelm Nelder-Mead fun. quals. grad gradient fun. quals. grac grad. conj. fun. quals. newt Newton fun. quals. dhfti SLATEC mínims quadrats pagesa AlvIPL+CPLEX modelitz. i rcsolució olí AMPL+ CPLEX modelitz. i resolució estim. estat Alvf PL+ MINOS modelitz. i resolució punts 1 1 2 3 4 4 6 4 1 2 4 32 obligatorietat obligatoria obligatoria obligatoria obligatoria La previsió de continguts de sessions de practiques i el lliurament més tarda acceptable seran: sessió 1� -D2� 3� 4.!l 5.!l (5.<:!: continguts LINUX funq qrad propi.f (vfun, grun) nelm dirc qrac grad grac (hssf) newt dhfti SLATEC pagesa, olí AMPL estim. estat AlVIPL lliurament sessió 2� sessió 4� -0-z_ L/. 0.3 OL-f sessió 5� -·:..: :: : o3 ú l.J sessió 6� sessió 6� data a convenir. A vís important sobre presentació de resultats: Heu de limitar el nombre de pagines que presenten de cada practica a un maxim de 12 pagines (llistats inclosos). Podeu editar els llistats de sortida deixant només la informació relevant. No es corregiran les practiques que excedeixin aquest límit. Prac. Optimització Contínua I 2 Elements basics d'UNIX/LINUX ELEMENTS BASICS D'UNTX/LTNUX Les Practiques d'OCl es realitzaran en el sistema operatiu LINUX, del qual es donen aquí els elements basics següents: *Finestra i signe "promt" *Llistar continguts d'un directoriy *Crear/desfer un directori o subdirectori *Canviar de directori *Copiar/esborrar un arxiu dins del mateix directori *Copiar o traslladar un arxiu a un altre directorí *Veure contínguts d'un arxíu *Editor emacs *Compilació de programes amb makefile *Execucíó de programes l. Finestra i signe "promt" El sistema operatiu UNIX/LINUX treballa amb finestres (hi ha una icona per crear-les). Dins de cada finestra hi ha un cursor amb un prompt ($ en la versió de LINUX que usarem, peto pot ser >, %, o altres signes, en altres versions). A partir del prompt hem d'introduir les instruccions. Tota instrucció s'executa prement la tecla retorn. (No s'indicara aquest detall en cap de les instruccions següents.) La finestra original no té sistema d'ascensor per recuperar sortida anterior que ja no veiem. Podem proporcionar un ascensor a la finestra prement simultaniament la teda df-\ control i el botó del mig del ratolí ({ctrl O\ 0 \O}), o els dos laterals -si només n'hi ha dos - { ctrl 0 \ 0}). Aixo fa sortir un menú on es pot activar enable scrollbar (ascensor). Aquest ascensor es fa pujar o baixar posant el cursor sobre ell i, amb el botó del mig del ratolí ({O\ 0 \0}), o els dos laterals -si només n'hi ha dos -({0 \ 0}) premuts, es fa anar el ratolí amunt i avall. 2. Llistar continguts d'un directori Per veure els continguts del directori on estem podem fer o bé: $ 1s obé: $ 11 La forma primera ens dona la simple llista de continguts en forma compacta. La forma amb 11 ens dona detalls de la mida i data de creacio de cada arxiu. 3. Crear/ desfer un directori o subdirectori Per crear un directori fill ( de nom dirmeu) a partir d'un directori (pare) on s1guem, farem: Prac. Optimització Contínua I 3 Elements basics d'UNIX/LINUX $ rnkdir dirmeu Per es borrar un directori fill existent ( de nom dirmeu) previament buitat de contingut, farem des del directori pare: $ rmdir dirmeu 4. Canviar de directori Per anar des de qualsevol directori al directori arrel (pare de tots els nostres directoris), basta fer: $ cd Per anar des de qualsevol directori al directori pare de !'actual directori: $ Podem fer $ .. / .. per baixar dos nivells de directori. Per anar des de qualsevol directori a un directori fill de nom dirmeu: $ cd dirmeu Cal notar que el prompt ens notifica a quin directori estem, ja que en comptes de simplcment $ ens donad. dirmeu $. També podem demarrar al sistema operatiu que ens digui a quin directori som executant la instrucció: $ pwd (print working directory). 5. Copiar/esborrar un arxiu dins del mateix directori Per copiar l'arxiu arxmeu. dat en un altre que anomenarem arxmeu2. dat, fem: $ cp arxmeu.dat arxmeu2.dat Si volem es borrar arxrneu. dat, basta fer: $ rm arxmeu.dat (remove) 6. Copiar o traslladar un arxiu a un altre directori Pr.r copiar l'arxiu arxmeu. dat en un altre, pero que estigui en un altre directori, ( con cret.amcnt en un directori fill anomenat meudir): -- primer caldra posar-nos al directori destí -- des del directori destí fem la copia usant cp i el camí fins on es traba l'arxiu a copiar: $ cd dirmeu $ cp .. /arxmeu.dat Suposem que al directori anomenat meudir hi ha l'arxiu arxmeu. dat i el que volem és passar-lo al directori pare ( treint-lo de meudir). Farem: PROGRAMES PERA FUNCIONS QUADRATIQUES Prac. Optimització Contínua I 12 Progs. per a func. quadratiques UTILITZACIÓ DELS PROGRAMES QUE TRACTEN FUNCIONS QUADRATIQUES Es descriu aquí la forma d'operar amb els programes preparats per tractar funcions quadratiques. D'aquests programes ja hi ha un executable disponible i només cal tenir un arxiu de dades amb nom generic arxi. dat i amb un format específic descrit més endavant. Els executables estan al directori: -opco/oc1/disponible/pr_fun_quad i suposarem que n'hi hagi un de nom: prog. L'heu de copiar a un directori o subdirectori vostre utilitzant una instrucció tal com: $ cp -opco/oc1/disponible/pr_fun_quad /prog . (per copiar el programa prog). El programa s'executa (en el directori on el teniu, ion hi ha l'arxiu de dades que hagueu preparat) fent simplement: $ prog (i prement retorn). El programa respondra pel terminal amb el nom del programa cridat i amb la demanda dels valors a atorgar a un cert nombre de claus de funcionament i unitats logiques, entre les quals n'hi ha de generals -iguals per a tots els programes - i d'específiques de cada programa. Les claus generals són: kse : unitat lógica d'escriptura de resultats, (si poseu 6 els escriura pel terminal). els pro grames tenen assignada la unitat lógica 3 per a escriure els resultats sobre un arxiu creat pel propi programa, de nom prog.res, que podeu manipular com un arxiu vostre; si poseu altres valors, p.e., 1, 2, 4, ... es crea un arxiu de nom fort .1, fort. 2, fort. 4, ... inf : clau que indica la quantitat d'informació que desitjeu que constitueixi la sortida del programa. Aquesta quantitat és més alta com més alt sigui el valor donat a inf ( amb un límit). Les informacions aparegudes per a cada valor de inf s'especifiquen a la documentació de cada programa ni t : nombre maxim d'iteracions desitjat La forma d'entrar aquests parametres és posant els valors desitjats sota la indicació de cada parametre apareguda al terminal, fent coincidir el derrer caracter de cada valor amb la derrera lletra del nom del parametre, així, en apareixer per exemple: ////prog kse nit inf? al terminal, cal entrar 5, 25, i O, tal com s'indica tot seguit ////prog kse nit inf? 6 25 O si volem sortida per la 6, 25 iteracions com a molt, i la informació corresponent a inf=O . Altres parametres o claus específiques poden ser demanades alhora i han de ser entrades pel mateix procediment, trobant-se l'explicació a la descripció de cada programa. En c:ornpt.es de O es poden deixar blancs, i si esta a la dreta de la fila, no cal ni posar els blanc,. El programa demarra a continuació l'arxiu de lectura de dades (vegeu l'apartat ARXIU DE DADES PERA LES FUNCIONS QUADRÁ.TIQUES) fent apareixer sobre el terminal la indicació arled? Cal aleshores entrar el nom de l'arxiu on hi ha amagatzemades les dades del programa. Prac. O Jtimitzacíó Contínua I 13 era func. Sigui per exemple arxi. dat aquest arxiu. Cal escriure aquest nom partint de la primera columna tal corn s'indica arled? arxi.dat Un cop premuda la tecla retorn, el programa comenc;a l'execució. Prac. Opti..mització Contínua I 11 Darles per a func. guadratiques ARXIU DE DADES PERA LES FUNCIONS QUADRÁTIQUES Cal disposar d'un arxiu de dades per a utilitzar els programes que tracten funcions quadratiques. Aquest arxiu té la mateixa estructura per a tots els programes d'aquest grup, de manera que un mateix arxiu pot ser utilitzat per tots aquests programes. Cada programa d,aquest gru_p d-mana int ractivament (p l erminal) el nom dl'arxiu en comern;ar l'execució (v-'geu apartat UTILITZA 'IÓ DEL, PR GRAMES QUE TR.A 'TEN FUNCIONS QUADRÁ..TIQUES). Els únics formats utilitzats són: 10i6 (per a variables i vectors de variables enteres) 5e 13 . 7 (per a variables i vectors de variables reals). Sempre fent referencia a la funció quadratica d'ordre n ( ) 1 ' ' qX =-XQX-BX 2 els continguts de l'arxiu són, seguint l'ordre que s'indica, els següents: 1) n , nombre que indica la dimensió de la funció quadratica a tractar (format 10i6) 2) elements sobrediagonals de la matriu Q de la funció quadratica, per files, en forma de vector, i en format 5e13. 7, és a dir la seqüencia q12, q13, q¡4, • • •,, qln, q23, q24, · · ·, q2n , q34 , · · ·, q3n, · · ·, qn-2 n-l, qr,.-2 n, qn-ln 1 d. d' , d 1 1 , n ( n - 1) a 1men 10 e a qua es 2 3) elements diagonals de la matriu Q en forma de vector i en format 5e13. 7 , és a dir la seqüencia 4) elements del vector B de constants en forma de vector i en format 5E13. 7 , és a dir la seqüencia 5) elements del vector X0 inicial, pres com a punt de partern;a en l'optimització, en forma de vector i en format 5E13. 7 , és a dir la seqüencia 6) grau de tolerancia amb la que es resol el problema i altres parametres reals espc'.cífics, indicats, si cal, a la documentació dels programes que ds utilitzen, tots en format 5E13. 7 La tolerancia normal és O . 1 e-9 7) elements, en format 5E13. 7 , requerits específicament per alguns progranws, sq_i;ous es detalla en llur descripció. És important no ometre cap d'aquestes set parts constituents de l'arxiu, encara qne algun programa no n'utilitzi alguna. En cas de que alguna part no sigui utilitzacla pcr un cert programa, pot omplir-se aquesta part amb qualsevol informació respectant d format corresponent, pero no pot ni ometre's la part ni deixar d'ornplir-la fins a la dimensió indicada. Prac. O timització Contínua I 15 Dades er a func. om Jl. _e_xemple es dona eUlistaJ_ d -1 'arx:iu q n _corrn_s_pnn a_, o o x,] l � �3] mi 12 6 -[ -11 q(X) =2 [x1 X2X3 6 19 .o .1 .1 -.11 .o 4 e e e e e o 1 1 2 o .1 e-09 -3 .o e0-.3 .2 e 1 .19 .22 e2 .73 .o eo.o o 1 30 amb Xº = m e 1 .6 e 1 e2 .3 e2 e2 .12 e2 eo.o e o .1 e 1 .2 e 1 .3 e 1 .4 e 1 1 .o 22 73 12]l�;l mcom a part 7): eo A l'element 1) la dimensió n de la funció quadratica pot anar seguida d'altres nombres enters (segons format 10i6) amb el significat que es detalla a la descripció dels programes que els utilitzin. Igualment a l'element 6) la tolerancia pot anar seguida d'altres parametres reals (segons format 5e13. 7) amb el significat que es detalla a la descripció dels programes que els utilitzin. Prac. Optimització Contínua I 16 Programa fung PROGRAMA funq D'ANALISI DE FUNCIONS QUADRÁTIQUES I TRIANGULARITZACIÓ DE MATRIUS SIMETRIQUES N om del programa i execució: funq Claus i parametres comuns: kse (vegeu apartat UTILITZACIÓ DELS PROGRAMES QUE TRACTEN FUNCIONS QUADRATIQUES) Claus i parametres especifics: Cap Elements utilitzats d l arxiu ddad s: 1), 2), 3) i 7) (vegeu apartat ARXIU DE DADES PER A LES FUNCIONS QUADRATIQUES) Funcions que realitza: -troba els valors propis de la matriu simetrica Q - amb Q i X* (element 7) d l'apartat ARXIU DE DADES PER A LES FUNCIONS QUADRATIQUES) forma el prodncte QX*=B -triangularitza Q -amb la factorització de Q i el vector B trobat, retroba, per substitucio directa i inversa, el vector X* Quantitat de sortida escrita segons valor atorgat a inf: Sempre surt la mateixa independentment del valor donat a inf. Apareix: -el vector X* entrat corn a part 7) ( vegeu aparLaL ARXIU DE DAD ES PER A LES FUNCIONS QUADRATIQUES) -la matriu Q ( en forma subtriangular) -la llista de valors propis -el vector B trobat -la taula de factors ( en forma subtriangular) -el vector X* solució del sistema d'equacions lineals QX*=B Prac. Optimització Contínua I 17 Func. quad. i triang. amb funq FUNCIONS QUADRÁTIQUES I TRIANGULARITZACIÓ DE MATRIUS SIMETRIQUES AMB EL PROGRAMA funq Aquest programa només és un ajut per comprovar les funcions quadratiques que hagueu de minimitzar en altres practiques, i una forma de comprovar la triangularització de la matriu Q. Podeu, amb l'ajut del programa funq, efectuar les tasques següents: a) amb una copia modificada de l'arxiu de dades de que disposeu, introdu"iu un punt X* com a element 7) (vegeu apartat ARXIU DE DADES PER A LES FUNCIONS QUADRA.TI QUES) b) executeu el programa funq segons s'especifica a l'apartat UTILITZACIÓ DELS PRO GRAMES QUE TRACTEN FUNCIONS QUADRA.TIQUES, amb l'arxiu creat e) ompleneu als arxius corresponents el vector B (part 4)) amb el vector B obtingut pel programa d) observeu la similaritat entre la relació de més gran a més petit valor propi, i la de més gran a més petit valor diagonal de la taula de factors, i també observeu la correspondencia de signes de valors propis i d'elements diagonals de les taules de factors f) obtingueu els límits superior i inferior dels valors propis de la matriu pel metode de Gerxgorin, i comproveu que tots els valors propis queden dins d'aquests límits g) obtingueu a ma per eliminació gaussiana la factorització de Q, efectueu la prova de que T DT' =Q (sent T la matriu subdiagonal de factors obtinguda), i comproveu que el vostre resultat coincideix amb el del programa. Esteu invitats a emprar el programa funq sempre que volgueu. Prac. Optimització Contínua I 18 Programa qrad PROGRAMA qrad DE MINIMITZACIÓ D'UNA FUNCIÓ QUADRÁTICA PEL METODE DEL GRADIENT Nom del programa i execució: qrad Claus i parametres comuns: kse, nit i inf (vegeu apartat UTILITZACIÓ DELS PRO GRAMES QUE TRACTEN FUNCIONS QUADRA.TIQUES) Claus i parametres especifics: Cap Elements utilitzats de l'arxiu de dades: 1), 2), 3) 4), 5), i 6) (vegeu apartat ARXIU DE DADES PERA LES FUN IONS QUADRA.TIQUES) Funcions que realitza: -Troba el mínim d'una funció quadratica pel metode del gradient a base de: a) calcular analíticament el gradient de la funció quadratica al punt considerat b) calcular la norma del vector gradient c) trobar analíticament la passa optima en la direcció contraria al gradient d) actualitzar el punt considerat fent-lo igual al punt resultant d'aplicar la passa optima en al direcció contraria al gradient e) tornar a a) -L'algorisme finalitza quan: *s'exhaureix el nombre d'iteracions fixat (nit) *la norma al quadrat del gradient, calculada a b), és més petita que la tolerancia entrada a les dades com a part 6). Quantitat de sortida escrita segons valor atorgat a inf: La quantitat de sortida escrita <lepen del valor donat a la clau inf, així: *per a un inf qualsevol surt: •la X sol u ció tro bada •el vector gradient calculat a la solució *per a tot inf>-1 , surt a més: •la Xk trabada a cada iteració *per a tot inf >0 , surt a més: •el vector gradient calculat a cada iteració *per a tot inf > 1 , surt a més: •la passa optima en la direcció contraria al gradient a cada iteració •el valor de la funció calculat a cada iteració Prac. Optimització Contínua I 19 Met. gradient per quad. amb grad EXERCICI DE MINIMITZACIÓ D'UNA FUNGIÓ QUADRATICA PEL METODE DEL GRADIENT Amb l'ajut del programa qrad i dels arxius de dades corresponents a funcions quadrati ques, minimitzeu la funció quadratica emmmagatzemada en cada arxiu tot observant la con vergencia de l'algorisme. Caldra efectuar, per a cada arxiu, les tasques següents: a) donant nombres d'iteracions (nit) succesivament creixents (20, 50, 100, 300, ... ) com proveu si hi ha o no convergencia (és a dir, si l'algorisme acaba o no perque la norma del gradient és més petita que la tolerancia, abans d'assolir el nombre d'iteracions entrat) b) amb inf>0 comproveu la taxa de convergencia de l'algorisme, calculant-la a partir de vectors Xk corresponents a dues iteracions successives, i compareu-la amb el valor límit de la taxa de convergencia calculat analíticament a partir dels valors propis de la matriu Q de la funció quadratica (trobats al programa funq) Per a complimentar l'exercici heu de lliurar un dels llistats de sortida obtinguts partint del punt inicial qualsevol adjuntant un full indicant, per a cada funció quadratica *el nombre d'iteracions necessaries per a convergencia, (part a)) *el detall del calcul de la taxa de convergencia a partir de dos vectors Xk d'iteracions successives, el calcul del límit teoric de la taxa, i la comprovació del valor amb el límit (part b)) *els vostres comentaris sobre les convergencies observades i llur relació amb l'estructura de valorn propiR, i lP.R anomalies (si n'hi han) que observeu en el funcionament del programa i la vostra interpretació Esteu invitats a emprar el programa qrad sempre que volgueu. Prac. O Jtimització Contínua I 26 Munt. ualsevol MUNTATGE I UTILITZACIÓ DELS PROGRAMES PER A LA REALITZACIÓ D'EXERCICIS AMB FUNCIONS QUALSSEVOL 14. Preparació i muntatge Es descriu aquí el procediment a seguir per a muntar programes per tal de minimitzar una funció qualsevol definida tal com es detalla tot seguit, utilitzant el programa principal i les subrutines subministrades. Al directori -opco/oc1/disponible/pr_sen_const hi ha els objectes dels programes principals i els objectes dels conjunts de subrutines accessibles als usuaris. Els objectes tenen el mateix nom que el programa principal amb el tipus . o , i les rutines estan agrupades en set arxius amb noms: ea07cd.o sonlcc.o sonlcd.o sonlcq.o sonlct.o sonlcu.o sonlcz.o Per a resoldre un programa amb una funció qualsevol l'usuari haura de crear un arxrn font en FORTRAN, p.e.: propi.f, per a una certa funció a minimitzar, on hi hagi: *una funció de nom vfun de calcul del valor de la funció, arnb parametres: function vfun (ndi,xex,naf,frf) implicit none integer*4 ndi,naf real*8 xex(ndi),frf vfun=frf+ naf=naf+1 return end amb: ndi dimensió n del vector de variables X xex vector X de variables ( de dimensió xex (ndi)) naf enter al qual s'afegira una unitat (naf=naf+1) cada vegada que sigui cridada vfun frf valor de referencia real constant a afegir al valor calculat de la funció (norrnalrne11I O) *una subrutina de nom grun de calcul del vector gradient de la funció, amb paduuet.n\s: Prac. Optimitzacíó Contínua I 27 subroutine grun (ndi,xex,gra,nag) irnplicit none integer*4 ndi,nag real*8 xex(ndi),gra(ndi) nag=nag+1 return end amb: ndi 1 xex: d'igual significat que a vfun Munt. prog. func. gualsevol gra : vector (de dimensió gra(ndi)) amb els elements del gradient calculat a xex (ndi) nag : enter al qual s'afegira una unitat (nag=nag+1) cada vegada que sigui cridada grun *una subrutina de nom hssf de calcul de la matriu hessiana de la funció, amb parametres: subroutine hssf (ndi,nnd,xex,dih,bth,nah) irnplicit none integer*4 ndi,nnd,nah real*8 xex(ndi),dih(ndi),bth(nnd) nah=nah+1 return end amb: ndi i xex: d'igual significat que a vfun nnd =(ndi*(ndi-1))/2 (el calcul del valor nnd ja el fa el programa principal subminis trat) dih : vector (de dimensió dih(ndi)) amb els elements diagonals de l'hessiana calculada a xex(ndi) bth : vector ( de dimensió bth (nnd)) amb els elements sobrediagonals de l'hessiana or denats per files i d'esquerra a dreta (segons l'ordre: h12 , h13, h14, · · · , , hin , h23, h24, · • · , h2n, h3 4, • · · , h3n, • • • , hn-2n-l, hn-2n, hn-ln nah : enter al qual s'afegira una unitat (nah=nah+1) cada vegada que sigui cridada hssf Cal tenir en compte el següent: l'usuari liaura de treballar només amb variables que s'ajustin a les precisions: integer*4 real*8 per als enters per als reals l'usuari haura de compilar-se l'arxiu font, amb el qual es crea l'objecte amb nom, p.e.: propi. o , per a la funció que utilitzi, usant la instrucció rnake newt (si vol crear-se el programa newt), en el directori on tingui els arxius: propi. f (preparat per l'usuari) newt. o (subministrat) sonlcO.o, sonlc1.o, sonlc2.o, sonlc3.o, sonlc4.o, sonlc5.o ( subministrats) makefile (subministrat) Prac. Optimització Contínua I 28 Munt. prog. func. qualsevol cal crear a més uns arxius de dades propis de cada programa i funció segons els principis expressats a l'apartat ARXIUS DE DADES PERA FUNCIONS QUALSEVOL. Hi haura disponible al directori indicat una codi font incomplet, anomenat propi . f, amb !'estructura basica de la funció i rutines que heu de desenvolupar. 14.1. Compilació amb llistat de possibles errors Alguns errors de codificació a l'arxiu propi. f poden donar lloc a series de missatges d'errors que són molt més llargues que el que cap a la pantalla del terminal. És llavors útil poder transferir la sortida d'errors per pantalla a un arxiu, per tal de consultar-lo amb calma per determinar quina és la causa dels missatges d'error. Si volguessiu anomenar propi. err l'arxiu on voleu posar els missatges d'error, hauriau de compilar i muntar un programa com el del metode de Newton (newt) amb l'instrucció: $ make newt 2>propi.err (i premer retorn). 15. Utilització El programa s'executa (en el directori on el teniu, ion hi ha els arxius de dades generic i específic que hagueu preparat) fent simplement, per a un programa que suposem que s'anomeni prog: $prog (i prement retorn). El programa respondra pel terminal amb el nom del programa cridat i amb la demanda dels valors a atorgar a un cert nombre de claus de funcionament i unitats logiques, entre l�s quals n'hi ha de generals -iguals per a tots els programes -i d'específiques de cada programa. Les claus generals són (igual que per als programes per a funcions quadratiques kse, inf i ni t i la forma d entrar-les és la mateixa ( ve�eu l'apartat UTILITZACIÓ DELS PROGRAMES QUE TRACTEN FUN TON' JUADRATIQUES). Altres parametres o claus específiques poden ser demanades alhora i han de ser entrades pel mateix procediment, trobant-se l'explicació a la descripció de cada programa. El programa demarra a continuació l'arxiu de dades generic (vegeu l'apartat ARXIUS DE DADES PERA LES FUNCIONS QUALSEVOL) fent apareixer sobre el terminal la indicació arx. gen.? Cal aleshores entrar el nom de l'arxiu on hi ha emmagatzemades les dades del programa. Sigui per exemple fee10. dat aquest arxiu. Cal escriure aquest nom partint de la primera columna tal com s'indica arx. gen.? fee10.dat Un cop premuda la tecla retorn, el programa comell(;a l'execució i, en arribar a la prinwrn avaluació de la funció, demarrara l'arxiu de dades específic (vegeu l'apartat AR.XIUS DE DADES PERA LES FUNCIONS QUALSEVOL) en la forma com ho hagueu codificat eu el ".'ostre codi propi . f Prac. Optimització Contínua I 29 Dades per a func. gualsevol ARXIUS DE DADES PER A FUNCIONS QUALSEVOL Per a la minimització de funcions qualsevol cal disposar de dos arxius de dades. El primer és generic i té la mateixa estructura per a tots els programes a utilitzar ( amb algun petit canvi en algun d'aquests). El segon arxiu de dades és específic de la funció a minimitzar i conté les dades i parametres relatius a aquesta funció. 16. Arxiu de dades generic Aquest arxiu té la mateixa estructura per a tots els programes d'aquest grup, llevat d'algunes partícularitats, de manera que amb modificacions mínimes, si calen, un mateix arxiu pot ser utilitzat per a tots els programes que prepareu. Cada programa demarra interactivament (pel terminal) el nom de l'arxiu en comenc:;ar l'execució (vegeu la secció anomenada Utilització de l'apartat MUNTATGE I UTILITZA CIÓ DELS PROGRAMES PER A LA REALITZACIÓ D'EXERCICIS AMB FUNCIONS QUALSEVOL). Els formats utilitzats dins de l'arxiu de dades són: 10i6 5e13.7 per a variables i vectors de variables enteres, i per a variables i vectors de variables reals. Sigui n el nombre de variables de la funció qualsevol a tractar, aleshores els continguts de l'arxiu són, seguint l'ordre que s'indica, els següents: 1) n nombre que indica la dimensió de la funció qualsevol a tractar (format 10i6) 2) elements del vector X0 inicial, pres com a punt de partenc:;a en l'optimització, en forma de vector i en format 5e13. 7, és adir, la seqüencia 3) grau de tolerancia amb la que es resol el problema i altres parametres reals específics, in dicats, si cal, a la documentació dels programes que els utilitzen, tots en format 5e13. 7 . La tolerancia normal és O. 1e-8 4) un o més vectors addicionals en format 5e13. 7, requerits específicament per alguns programes, segons es detalla en llur descripció. És important no ometre cap d'aquestes set parts constituents de l'arxiu, encara que algun programa no n'utilitzi alguna. A l'element 1) la dimensió n del vector de variables de la funció qualsevol pot anar s<�guida d'altres nombres enters (segons format 10i6) amb el significat que es detalla a la <lescripció dels programes que els utilitzin. Igualment a l'element 3) la tolerancia pot anar seguida d'altres parametres reals (segons format 5e13. 7) amb el significat que es detalla a la descripció dels programes que els utilitzin. 17. Arxiu específic de la funció a minimitzar Conté les dades i parametres relatius a la funció a minimitzar. Sera llegit la primera vegada que es vol avaluar la funció (parametre naf=O de la funció vfun dins del vostre codi propi. f). La codificació de vfun ha de contenir dones al principi nn grnp <l'instruccions del tipus: Prac. O timització Contínua I30 Darles er a func. ualsevol e llegim aqui les dades i parametres de la funcio e fi de lectura endif A més, aquestes dades i parametres han d'estar disponibles cada vegada que el programa cridi la funció vfun o rutines grun o hssf (del codi propi.f). Per aquesta raó tant dins de vfun com de les rutines grun i hssf hi ha d'haver un common amb etiqueta que contingui les dades i parametres que convingui conservar: common /dadparam/ dad1,dad2,param1,param2, ... El format de l'arxiu de dades específic és de la vostra elecció perque el codi de lectura l'heu d'elaborar vosaltres dins del vostre codi propi. f ,H., Prac. O timització Contínua I 31 Funció ualsevol: estimació d 'estat FUNCIÓ QUALSEVOL: ESTIMACIÓ D' ESTAT EN UNA XARXA ELECTRICA Aquest és un problema real que correspon a una regressió no lineal. 18. Presentació del problema Les companyies electriques disposen d'una xarxa de transmissió de potencia a alta tensió per fer arribar l'energia generada a les distintes centrals (hidrauliques o termiques) als consum idors particulars o industrials. Aquesta xarxa transmet corrent altern en sistema "trifasic" ( en tres fases) mitjarn;ant un conjunt de tres conductors, tal com mostra la Fig. l. En condicions de funcionament normal l'energia tramesa es divideix equitativament entre les tres "fases" o conductors. Fig. l. Línia de transmissió d 'electricitat en corrent altern mostrant els tres conductors corresponents a les tres "fases". Les xarxes de transmissió s'acostumen a representar per un diagrama unifilar (represen tant el conductor d'una sola de les "fases") tal com mostra l'exemple de la Fig. 2. Els punts on conflueixen dues o més línies s'anomenen "subestacions" o "barres", els quals constitueixen els nusos de la xarxa. A la Fig. 2 es poden veure sis "subestacions" o "barres", les quals distingirem amb una lletra majúscula: T, S, I, P, M, i A. Per tal de coneixer com s'esta comportant la xarxa a cada instant, les companyies electri ques prenen mesures de certes variables a la xarxa. Aixo es fa instal· lant sistemes computer i tzats de captació i transmissió de mesures en diverses "subestacions" des d'on es transmet la informació recollida -corresponent a un instant de temps únic predeterminat - a un ordinador central. Un cop rebuda des de les distintes "subestacions" el conjunt de mesures corresponents a un instant donat, es processa la informacíó per tal de determinar el valor de certes variables de la xarxa que en caracteritzen l'estat. Aquest procés s'anomena Estimació d 'Estat i consisteix en una optimització que pot ser sense o amb constriccions. 'La practica consisteix en realitzar l'Estimació d1 Estat a partir d'un conjunt de mesures de finx de potencia activa i reactiva per línies de transmissió i d'una mesura de tensió en la Prac. Optimització Contínua I 32 Funció qualsevol: estimació d'estat T Ip l) 2) M A 1 mesura de potencia activa � mesura de potencia reactiva <y mesura de tensió Fig. 2. Diagrama unifilar d'una xarxa de transmissió. A les subestacions corresponents a les barres S, I, P, M i A es prenen algunes mesures de potencia activa, reactiva i tensió. "barra" o nus corresponent a una certa "subestació". (S'hi poden afegir constriccions per tal de forc;ar que la solució respecti les magnituds de la tensió mesurada en més d'un nus.) 19. Modelització de les variables i parametres del corrent altern En regim de funcionament normal totes les variables que intervenen en una xarxa de corrent altern varíen sinuso:idalment amb la "freqüencia" única de 50 Hz ( una oscil · lació completa en lo de segon). Representem a la Fig. 3a) l'evolució en el temps de la tensió en dos nusos d'una xarxa: el nus k i el nus m. Sent la "freqüencia" sempre la mateixa, es pot caracteritzar totalment una certa variable per la magnitud ( o alc;ada de l'ona sinuso:idal) i per l'angle de "fase" o decalatge mesurat en graus (una oscil-lació completa: 360º) respecte a un origen de temps arbitrari. A la Fig. 3b) es representen les tensions tk i tm de la Fig. 3a) sobre el pla complex, mostrant llur magnitud i angle de fase (avanc;at 36º el de tk i retardat 18º d de tm. També es veuen les components rectangulars complexes ek+jfk i em+jfm (.i=.J=l) equivalents a la magnitud i angle de "fase" de les dues tensions. (Les variables electriques en cadascun dels tres conductors o "fases" de la Fig. 1 són iguales llevat d'un decalatge en angle de fase de 120°). En el planteig i resolució d'aquesta practica s'utilitzaran tant els parametres com les variables en coordenades rectangulars complexes. 19.1. Potencies, impedancies i admitancies en coordenades rectangulars A part de les tensions, mesurades en volt (V) o Kilovolt (KV), i els corrents, mesurats en ampers (A), cadascun amb la seva component real i imaginaria, hi ha també les potencies qne circulen per les línies. La part real de la potencia s'anomena potencia activa i es representa amb la lletra p i la part imaginaria, anomenada potencia reactiva amb la q. Així la potencia que surt des del nus k d'una xarxa cap el nus l a través de la línia que uneix els nusos k i lés Pk1+jqkl· Les potencies actives es mesuren en megawatt (MW=106.W) i les reactives en megavolt-amper-reactiu (MVAr). S'anomena "potencia aparent" la combinació de la potencia activa i la reactiva, així entre k i l la "potencia aparent" fóra a+ qil' i es mesura en megavolt-amper (MVA). L 'oposició z ( o "impediment") que presenta un conductor al pas d 'un corren t. altern s'anomena impedancia. Té una part real r anomenada resistencia i una part imaginaria :1 anomenada reactancia. Així per a la línia entre els nusos k i l de la xarxa Zkl =rkl +_j:i: kl. L Prac. 'Jtimització Contínua I 33 Funció ualsevol: estimació d 'estat tensió a) .-·•. tm . -. Fig. 3. a) Tensions alternes en els nusos k i m en el temps. b) Representació de la magnitud i l'angle de fase, i de les components rectangulars de les tensions a k i m en el pla complex. J b) reactancia x pot ser inductiva (corresponent al que és un bobinat) quan x>0, o capacitiva (corresponent a un condensador) quan x<0. Tant la resitencia com la reactancia es mesuren en ohm (n). La inversa de la impedancia és la "admissibilitat" y del corrent altern per part d'un conductor, i s'anomena admitancia. Per a la línia entre k i l: 1 1 Ykl = - = Zkl 1'kt + J. ;kl (1) sent Ckt l'anomenada conductancia i Skt la susceptancia. La conductancia i la susceptancia es mesuren en ohm1 (n1). Quan la reactancia és capacitiva (x<0) la susceptancia també és negativa i s'acostuma a representar per la lletra b. (Resumint: impedancia= resistencia+j reactancia, admitancia= conductancia-j susceptancia sent admitancia=l/ impedancia). 19.2. Utilització del sistema p.u. en xarxes electriques Per resoldre problemes de xarxes electriques s'acostuma a fer un escalat que proporciona alhora magnituds de variables relativament properes a u i una forma efectiva de poder fer calculs sense conversió d'unitats. Aquest escalat recolza en una potencia base PE per a tota la xarxa, per exemple 100 MVA, i una tensió base TE per a cada nivell de tensió que hi hagi a la xarxa, per exemple 220KV en el cas de la xarxa de la Fig. 2, que es l'únic nivell de tensió que hi ha ( no hi ha transformadors). Havent triat una potencia base i una tensió base, hi ha automaticament un corrent base i una impedancia base que es poden determinar. Per exemple amb PE=lO0 MVA i TE=220 KV, lc1, impedancia base ZB és: To tes les potencies ( actives i rei-tctives) es divideixen per la potencia base PE, totes les tensions perla tensió base Tn totes les impedancies per ZB, etc., i aleshores tots els calculs s'efectuen <�11 tant per u (p. u.) siguin corrents, potencies, etc. i les magnituds dels resultats es poden passar a unitats nonuals multiplicant per la quantitat-base corresponent. Prac. Optimització Contínua I34 Funció gualsevol: estimació d 'estat 20. Model d'una línia de transmissió en corrent altern En Electrotecnia es veu que una línia de transmissió en corrent alt.ern pot ser modelitzada adequadament mitjanc;ant el circu'it "en II", de parametres concentrats, que representa la Fig. 4. /k17: 2�j0) Fig. 4. Model en 7r de la línia de transmissió en corrent altern entre els nusos k i l, indicant para.metres i tensions ( entre paren tesis). La línia entre el nus k i el l es caracteritza per la resistencia rkt, la reactancia Xkt (inductiva) i una susceptancia a terra ( capacitiva) bkt subdividida en dues mitats i ubicada als extrems del circu'it equivalent. 21. Corrent i potencia que circula des del nus k cap el nus l per una línia El corrent ikt que surt de k cap a l té dues parts, segons la Fig. 4, la que va pel cirClút horitzontal que uneix k i l i la que va a terra a través de la mitja susceptancia capacitiva de la línia. Aplicant la llei d'Ohm: corrent=( diferencia de potencial)/ (impedancia)=( diferenciFt de potencial)x(admitancia) i tenint en compte que el terra esta a tensió zero (O+jü). . ( k + j j¡_) -(.e¡ + .i .f1) + ( + . f ) . b kl ikt = . ek J k J - '1'kt + OI, 'kl 2 (2) En Electrotecnia es mostra que la potencia conjugada Pk1-jqkl que surt del nus Á: en direcció al nus l equival al producte de la tensió conjugada al nus k (ek-jfk) pel corrent i1.:1 Tenint en compte (2) i separant la part real de la part imaginaria s'obté: 1 Pkl = 2 [ ek 1 qkl = - [ ek e¡ Ík 2 e¡ Ík [ 2Cki t, l :�:: [ 2s., -bk1 ft] -;kl Ckt -Skt o -Ckt o -Ckt o -�•11 [ P-k] oSkt �; 2ckl Skt -Ckt o -Ckt o o c., ] [ Ck] -Ckt + e¡ 2Skt -bkl .h: -Skt h (3) (4) sent ck1= 2 '+·1.· 1::r la conductancia, Skt= .2 "�' 2 la susceptancia i bkt la susceptancia a terra de rkl x,_, t k/ X¡,¡ la línia. (Noti's que bkt influeix en la potencia reactiva pero no en la activa). Prac. , timització Contínua I 35 22. Funció objectiu de l'Estimació d'Estat Funció ualsevol: estimació d 'estat Siguin E i F els vectors que contenen les parts reals ei i les parts imaginaries Íi de l s tensions als nns s i de la xarxa. En l'estimació d'estat que plantegem hi ha un nus, fü d r f ren ·ia1 d l 1ual t nim la w :::nll'a de la magnitud de la seva tensió: tref· Donat ¡u·, 1 rigen ele t mps n la r·pres utació de tensions és arbitrari (vegi's Fig. 3a)), podem c;on id rar qu aqu st origcm és tcctl que l'angl · de fase de tref és zero, és a dir: eref=tref, frf.f=Ü. L s compon nts tl" les t 1 si ns n els nusos que no són el de referencia són in ·ognit s X·.1. dt�t rminar. Així ( , , F)=( ref Í;rcf), bé si Nn és el nombre de nusos, X =(ei, Íi Ji= 1, ... , Nn, i =f. ref), XEIR2(Nn-l)_ L'estimació d'estat plantejada considera un conjunt de Nm parelles de mesures de poten cia activa i reactiva, de forma que 2Nm>2(Nn-l). Representarem les mesures d'acti'va i de reactiva per Pkl i Qkl, sent Pkt (E, F) i qkl (E, F) els valors calculats segons les expressions ( 4). La funció objectiu de l'estimació d'estat és: Nm minil]litzeu ¿ { (Pkt(E, F) -Pki)2 + (qk1(E, F) -Qkz)2} (5) i=l on suposem que la parella de mesures de activa i reactiva i correspon a les de l'extrem k de la línia entre els nusos k i l. Plantejada així, l'estimació d'estat és una minimització sense constriccions que corres pon a uns mínims quadrats no lineals. Pot ser resalta per qualsevol dels procediments de minimització de funcions (sensc constriccions). ( Cal notar que si no hi hagués una mesura de tensió la matriu hessiana fóra singular i no es podría fer l'optimització). 23. Parametres i mesures a considerar El que segueix és un possible exemple de dades d'un problema. Es donen en p. u. els parametres i mesures a considerar pe� al problema. (S'ha pres PB=lO0 MVA i TB=220 KV). pt ram ,tr 8 de línies entre mesures de potencia nus knus lrkl Xkl bkl k l Pkl qkl (p.u.) (p.u.) (p.u.) (p.u.) (p.u.) T s 0,0011 0,0089 0,0244 s T -0,2655 0,5855 S(l I(l 0,0182 0,0885 0,2475 S(l I(l 0,1252 -0,0716 S(2 I(2 0,0118 0,0921 0,2330 I(2 S(2 -0,1170 -0,1753 I p 0,0021 0,0164 0,0427 I A -0,6081 -0,6910 I A 0,0037 0,0183 0,0510 p I 0,5294 0,4914 p A 0,0019 0,0209 0,0519 p A -0,0711 -0,2615 T M 0,0185 0,0890 0,0510 M T -0,2613 0,2375 A M 0,0042 0,0206 0,0571 M A -1,0581 0,4619 A M 1,0627 -0,4964 A I 0,6080 0,6536 A p 0,0704 0,2068 Prac. Optimització Contínua I 42 Sortida escrita per rutines exploració c) *la indicació del nou punt obtingut, amb passa (PAS=) i valor <le la funció (F=) *les indicacions de les successives accions que emprendra la rutina, junt amb les causes que les motiven, junt amb la passa realitzada (PAS=) i el valor de la funció (F=), segons la taula següent: situació PAS ... AJUST IRR -- 1/2 PAS EXCESSIU 1/2 PAS EXCESSIU ACD PAS EXCESSIU ACU PAS EXCESSIU AJQ PAS EXCESSIU AJQ PAS MASSA CURT-- DUP per a tot inf>O , surt a més: SI CONVEX acció propera / comentari es reduira la passa a la meitat ja que el punt obtingut per ajust no millora, o no es pot fer l'ajust es reduira la passa a la meitat es fara ajust cúbic per no haver millorat amb una passa doble es fara ajust cúbic es fara ajust quadratic es fara ajust quadratic si amb la mitja passa tenim convexitat es duplicara la passa ja que s'ha observat reducció en el valor de la funció *la passa mínima (PMN=) que en aplicar-la en la direcció DIR dona una variació més gran que EPS en al menys un component de X ( ·) *les coordenades del nou punt obtingut XAC (.) 27.1. Glossari de !'organigrama de la subrutina elqc DIR: direcció d'exploració lineal a partir de Xa (dada) f ( ·): funció respecte a la qual hom fa exploració lineal ( donada per una funció de nom vfun) KAS: codi intern de la subrutina ( diversos casos) PAD: passa que separa Xd de Xa PAU: passa que separa Xu de Xa PCU: passa acumulada actual PIN: passa inicial (dada) VAC: f(Xa) (dada sobreescrita pel resultat final) VFD: f(Xd) VFU: J(Xu) Xa: punt actual origen de l'exploració lineal (dada sobreescrita pel resultat final) Xd: punt utilitzat com a espai de treball Xu: punt utilitzat com a espai de treball Prac. O timització Contfnua I 43 Sortida escrita er rutines ex loració Prac. Optimització Contínua I 44 Elements basics d'UNIX/LINUX PROGRAMA grad DE MINIMITZACIÓ DE FUNCIONS QUALSEVOL PEL METODE DEL GRADIENT Nom del programa i execució: grad Muntatge: Cal procedir al muntatge tal com indica l'apartat MUNTATGE I UTI LITZACIÓ DELS PROGRAMES PER A LA REALITZACIÓ D'EXERCICIS AMB FUNCIONS QUALSEVOL. Només cal tenir completada la funció vfun i rutina grun (ja que el procediment emprat no utilitza l'hessiana). El programa pero, quan ja ha arribat a la solució avalua l'hessiana per trobar els valors propis d'aquesta al punt trobat, (a efectes de verificar la taxa de convergencia). Per aixo convé tenir també la rutina hssf programada. Claus i parametres comuns: kse, ni t i inf (vegeu apartat MUNTATGE I UTILITZA CIÓ DELS PROGRAMES PER A LA REALITZACIÓ D'EXERCICIS AMB FUN CIONS QUALSSEVOL) Claus i parametres específics: nfi, sent: *nfi: (entrat per pantalla, segons demanda) nombre d'avaluacions de la funció per a l'exploració lineal pel metode de Fibonacci Elements utilitzats de l'arxiu de dades generic: 1), 2), i 3) format per: *eps: tolerancia, *aln: passa inicial en la cerca del interval d'incertesa (p.e.: 0.5), i *frf: valor de referencia en l'avaluació de la funció (O normalment). Funcions que realitza: Troba el mínim d'una funció qualsevol pel metode del gradient, a base de: a) calcular per crida a la subrutina grun el gradient de la funció al punt considerat b) calcular la norma al quadrat del vector gradient c) trobar per exploració lineal (metode de Fibonacci) una passa d'exploració e11 la direcció contraria a la del gradient d) actualitzar el punt considerat fent-lo igual al punt resultant d'aplicar la passa d'exploració en al direcció contraria a la del gradient calculat e) tornar a a) -L'algorisme finalitza quan: *s'exhaureix el nombre d'iteracions fixat (ni t) *la norma al quadrat del gradient, calculada a b)) és més peti ta que la tolerancia entrada a les da�es com a part 3). -En finalitzar l'algorisme, si inf < 1 es calcula l'hessiana al punt final obtingut ( cridant lc:1 subrutina hssf) i s'escriuen els valors propis d'aquest. Quantitat de sortida escrita segons valor atorgat a inf: La quantitat de sortida escrita correspon a l'expressada tot seguit més la qlw cor respon a les subrutines ciif i fibf (vegeu apartat SORTIDA ESCRITA PER LE5 RUTINES D'EXPLORACIÓ LINEAL), i <lepen del valor donat a la clau inf, així *per a un inf qualsevol surt: •la passa (pas= ) i el valor de la funció (vfu= ) resultat de l'explorac:ió li11eal : cada iteració Prac. ptímització Contínua I 45 •la X solució trabada •el vector gradient calculat a la solució *per a tot inf>-1, surt a més: •la Xk trabada a cada iteració *per a tot inf>O, surt a més: •el vector gradient a cada iteració Elements basics d'UNIX/LINUX •per a cada iteració, els vertex de mínim i maxim valor de la funció, valor mig de la funció als vertexs, i valor a cada vertex, tal com sortia cada 10 passes per a tot inf>-2 *per a tot inf<l, apareix, junt amb la solució final: •l'hessiana calculada en aquest punt, i els valors propis de l'hessiana. Prac. O timitza.ció Contínua I 46 Met. radient amb rad EXERCICI DE MINIMITZACIÓ D'UNA FUNGIÓ QUALSEVOL PEL METODE DEL GRADIENT Amb l'ajut del programa grad muntat amb la funció a minimitzar, i dels corresponent arxiu de dades generic i específic, efectueu la minimitzacó de la funció tot observant la con vergencia de l'algorisme. Caldra que efectueu les tasques següents, i que respongueu les qüestions proposades: a) donant nombres d'iteracions (ni t) succesivament creixents (20, 50, 100, 300, ... ) com proveu si hi ha o no convergencia (es adir, si l'algorisme acaba o no perque la norma del gradient és més petita que la tolerancia, abans d'assolir el nombre d'iteracions entrat) b) comproveu l'efecte de l'exploració lineal no exacta sobre l'actuació del metode del gra dient, utilitzant valors diversos de nfi (p.e.: 3 i 8) comprovant per al mateix nombre d'iteracions, el valor assolit de la de la funció objectiu Per complimentar l'exercici heu de lliurar un llistat de sortida obtingut, adjuntant un full amb: *el nombre d'iteracions necessari per convergir *una taula comparativa de valors de la funció, per al mateix nombre d'iteracions, utilitzant diverses precisions en l'exploració lineal pel metode de Fibonacci Esteu invitats a emprar el programa grad sempre que volgueu. Prac. ptimització Continua I 47 Programa grac PROGRAMA grac DE MINIMITZACIÓ DE FUNCTONS QUALSEVOL PEL METODE DEL GRADIENT CONJUGAT Nom del programa i execució: grac u11tatg : Cal procedir al muntatge tal com indica l'apartat MUNTATGE 1 UTI LITZACIÓ DELS PROGRAMES PER A LA REALITZACIÓ D'EXERCICIS AMB FUNCI )N Q ALSEVOL. Nom's cal tenir completada la funció vfun i rutina grun (ja que el J rocecliu ent emprat no utilitza l'hessiana). Claus i parametres comuns: kse, nit i inf (vegeu apartat MUNTATGE I UTILITZA CIÓ DELS PROGRAMES PER A LA REALITZACIÓ D'EXERCICIS AMB FUN CIONS QUALSSEVOL) Claus i parametres específics: nfi, sent: *nfi: ( entrat per pantalla, segons demanda) té ací ultra el significat habitual, també la funció següent: •si nfi>O nombre d'avaluacions de la funció en l'exploració lineal pel metode de Fibonacci osi nfi�O l'exploració lineal s'efectua mitjarn;ant la subrutina elqc Elements utilitzats de l'arxiu de dades g ueric: 1), 2), i 3) format per: *eps: tolerancia, *aln: passa inicial en la cerca del interval d'inr,ert.P.sa (p.e.: 1.0), i *frf: valor de referencia en l'avaluació de la funció (O normalment) Funcions que realitza: -Troba el mínim d'una funció qualsevol pel metode del gradient conjugat, a base de: a) calcular per crida a la subrutina grun el gradient de la funció al punt considerat b) calcular la norma al quadrat del vector gradient c) calcular la direccide minimització, a base d'afegir a la negativa del gradient la di recció de minimització anterior multiplicada per un coeficient {3 funció dels vectors gradient actual i anterior d) trobar per exploració lineal una passa d'exploració en la direcció trobada a c), per Fibonacci si nfi>O, o a través de la rutina si nfi�O e) actualitzar el punt considerat fent-lo igual al punt resultant d'aplicar la passa d 'exploració en al direcció del punr c) f) tornar a a) -L'algorisme finalitza quan: *s'exhaureix el nombre d'iteracions fixat (ni t) *la norma al quadrat del gradient, calculada a b), és més petita que la tolerancia entrada a les dad es com a part 3). Qnantitat de sortida escrita · -•�ons valor ator¡.pt. a inf: La quantitat de sortida escrita correspon a l'expressada tot seguit més la que cor respon a les subrutines o bé ciif i fibf, o bé elqc (vegeu apartat SORTIDA ES CRITA PER LES RUTINES D?EXPLORACIÓ LINEAL), i <lepen del valor donat a la clau inf, així: Prac. Optimització Contínua I 48 *per a un inf qualsevol surt: •la X solució trobada •el vector gradient calculat a la solució *per a tot inf>-1, surt a més: •la Xk trobada a cada iteració *per a tot inf>O, surt a més: •el vector gradient a cada iteració *per a tot inf>l, surt a més: Programa grac •el factor f3 (amb la indicaci bet= ) calculat al pas c), el qual multiplica la direcci anterior, per a afegir-la a la contraria del gradient, definint així la nova direcci •la nova direcció de minimització calculada al pas c) de cada iteració. EXERCICI DE MINIMITZACIÓ D'UNA FUNGIÓ QUALSEVOL PEL METODE DEL GRADIENT CONJUGAT Amb l'ajut del programa grac muntat amb la funció a minimitzar, i dels corresponent arxiu de dades generic i específic, efectueu la minimitzacó de la funció tot observant la con vergencia de l'algorisme. Caldra que efectueu les tasques següents, i que respongueu les qüestions proposades: a) donant nombres d'iteracions (nit) succesivament creixents (20, 50, 100, 300, ... ) com proveu si hi ha o no convergencia (es adir, si l'algorisme acaba o no perque la norma del gradient és més petita que la tolerancia, abans d'assolir el nombre d'iteracions entrat) b) comproveu l'efecte de l'exploració lineal no exacta sobre l'actuació del metode del gra dient, utilitzant valors diversos de nfi (p.e.: 3 i 8) comprovant per al mateix nombre d'iteracions, el valor assolit de la de la funció objectiu, i observeu el nombre requerit d'avaluacions de la funció i del gradient c) executeu el programa entrant nfis;0 (rutina elqc) i observeu i compareu amb els resul tats de b) el nombre requerit d'avaluacions de la funció i del gradient (podeu comprovar l'efecte de variar el parametre aln) Per complimentar l'exercici heu de lliurar un llistat de sortida obtingut, adjuntant un full amb: *el nombre d'iteracions necessari per convergir *una taula comparativa de valors de la funció, per al mateix nombre d'iteracions, utilitzant divcrscs prccisions en l'exploració lineal pel rneLude <le Fibonacci i la comparació del mateix quan s'utilitza la rutina elqc *una comparaci de la convergencia amb altres metodes (gradient, ... , etc.) Esteu invitats a emprar el programa grac sempre que volgueu. Prac. Optimització Contínua I 50 Programa newt PROGRAMA newt DE MINIMITZACIÓ DE FUNCIONS QUALSEVOL PEL METODE DE NEWTON EN LA VERSIÓ DE DENNIS-SCHNABEL UTILITZANT TRIANGULARITZACIÓ DE GILL-MURRAY Nom del programa i execució: newt Muntatge: Cal procedir al muntatge tal com indica l'apartat MUNTATGE I UTI LITZACIÓ DELS PROGRAMES PER A LA REALITZACIÓ D'EXERCICIS AMB FUNCIONS QUALSEVOL. Claus i parametres comuns: kse, ni t i inf (vegeu apartat MUNTATGE I UTILITZA CIÓ DELS PROGRAMES PER A LA REALITZACIÓ D'EXERCICIS AMB FUN CIONS QUALSSEVOL) Claus i parametres específics: nfi, sent: *nfi: (entrat per pantalla, segons demanda) té ací ultra el significat habitual, també la funció següent: •si nf i>0 nombre d'avaluacions de la funció en l'exploració lineal pel metode de Fibonacci osi nfi:s;0 l'exploració lineal s'efectua mitjarn;ant la subrutina elqc Elements utilitzats de l'arxiu de dades generic: 1), 2), i 3) format per: *eps: Lolerancia, *aln: passa inicial en la cerca del interval d'incertesa (p.e.: 1.0), i *frf: valor de referencia en l'avaluació de la funció (O normalment) Funcions que realitza: Traba el mínim d'una funció qualsevol pel metode de Newton (en la variant propasada per Dennis-Schnabel utilitzant la triangularització de Choleski modificada per Gill-Murray), a base de: a) calcula per crida a la subrutina grun el gradient en el punt considerat, traba la norma (al quadrat) del gradient i acaba si la norma d'aquest gradient és més petit que la tolerancia eps b) calcula per crida a la subrutina hssf l'hessiana de la funció en el punt considerat i en calcula els límits superior i inferior als seus valors propis utilitzant el teorema de Gerxgorin c) efectua la triangularització i factorització de Choleski de l'hessiana pel metode mod ificat de Gill-Murray, trobant la correcció (si cal) a la diagonal, i la posició (si n'h: ha) de l'element diagonal no corregit mes negatiu ( el qual es dona si l'hessiana é� indefinida) d) si a través de la triangularizació de Gill-Murray hom detecta que l'hessiana és in definida, es calcula, nomes per a ser comparada pels usuaris amb la direcció util itzada, la direcció de corbatura negativa calculada pel procediment de Gill-Murnt) i hom calcula pel procediment de Dennis-Schnabel, la correcció lineal a la diaµ;orn1 de l'hessiana, i es torna a triangularitzar í factoritzar e) hom calcula per substitució directa i inversa amb l'hessiana (modificada i-:ii <-:ra. il definida) triangularitzat, la direcció en la que fer exploració Prac. Optimització Contínua I 51 Programa newt f) s'efectua exploració lineal en la direcció calculada a la passa e) per un <lels procedi ments següents segons el valor entrat de nfi: nfi>O : Fibonacci amb nf i avaluacions nfi::;O : Exploració amb retrocés quadratic 1 cúbic per la subrutina elqc 1 actualització del punt utilitzat g) anada a a) L'algorisme finalitza quan: •s'exhaureix el nombre d'iteracions fixat (nit), o •el quadrat de la norma del gradient calculada a a), és més petita que la tolerancia entrada a la part 3) de les dades. Quantitat de sortida escrita segons valor atorgat a inf: La sortida que apareix és la descrita a continuació més la deguda (si nfi>O) a les sub rutines de cerca d'interval d'incertesa ciif i d'exploració lineal fibf pel metode de Fibonacci, o (si nfi�O) la de la ruti11a d expl ració amb retro és quadratic i cúbi elqc (v geu apartat SORTIDA ESCRITA PERLE RUTINES DE PLORACIÓ LINEAL). Per a un inf qualsevol surt •la X solució trabada, i el valor de la funció en aquest punt •el vector gradient G calculat a la solució •l'hessiana calculada al punt solució i els seus valors propis, detallant el nombre d'avaluacions de la fundó (naf) efectuat, el de gradients (nag), i el d'hessianes (nah) •si l'hessiana en un punt és indefinia, surt també *l'hessiana triangularitzada modificada, *la posició 'ICN' del més negatiu element diagonal no corregit obtingut en la triangulari tzació, *el vector 'DEX' de correccions aplicades a la diagonal, i *la direcció 'DCN' de corbatura negativa calculada (pero no utilitzada) Per a tot inf2:0 , surt •el punt Xk a cada iteració, amb el valor de la funció en aquest punt, i •la direcció d'exploració obtinguda per substitució directa i inversa a la passa e) Per a tot inf>O , surt a més •el vector gradient G a cada iteració, •l'hessiana calculada a cada iteració amb els límits superior 'TSP' i inferior 'TFP' de Gerxgorin als seus valors propis, i •si l'hessiana en un punt és indefinida, surt també l'hessiana modificada amb la correcció lineal aplicada a tots els elements diagonals Prac. O timització Contínua I58 roblema de la a esa usant CPLEX Una pagesa té un camp on produeix pata.tes, carabasses, kiwis i maduixes. Té també una furgoneta que admet 1400 Kg de carrega en un volum útil per a mercaderies de 5 m3. Cada tarda recull productes del seu camp (amb un cert límit) i ho carrega a la furgoneta. Cada matinada transporta al mercat la seva collita exposant-la en una parada de la seva propietat amb 10 m2 de superficie d'exposició. Malhauradament amb el transport es fa malbé part del que transporta i ho ha de llen<;ar. Pero el que li queda vendible és de tan alta qualitat i fa tant de goig que sempre al migdia ja ho ha venut tot. Aixo sí, cal tenir els productes convenientment exposats a la parada, i cada producte ocupa una certa superficie per unitat de pes. Si la pagesa sabés programació lineal podria optimitzar les quantitats que hauria de collir cada tarda de cada producte del seu camp (xp Kg de patates, Xc Kg de carbasses, x�, Kg de kiwis i Xm Kg de maduixes) per tal de maximitzar el guany de la seva venda tenint en compte els preus de mercat i les limitacions que té en la collita, el transport i l'exposició. Donada la taula següent que expressa les dades específiques de cada producte, podrieu plantejar el problema que hauria de resoldre la pagesa cada tarda? producte preu de volum per desperdici superf. en expos. collita max. mercat unit. pes en transport per unitat de pes per día -€/kg m3/kg m2/kg kg patata 0.5 0.003375 2% 0.01 900 carbassa 0.78 0.0062 5% 0.06 400 kiwi 1.55 0.003 8% 0.008 600 maduixa 1.3 0.0022 18% 0.004 350 MODELITZACIÓ DE LA FUNCIÓ OBJECTIU Volem maximitzar el guany de venda que efectua la pagesa al mercat. El productc de la venda son les quantitats venudes pel preu de mercat. Les quantitats venudes són les quantitats transportades menys el desperdici originat pel transport. Aixís cal maximitzar: .max 0.5 X (1 -0.02)xp + 0.78 X (1 -0.05)xc + 1.55 x (1 -0.08)xk + 1.3 x (1 -0.l8);i:111. o, el que és el mateix: el qual equival a maximitzeu 0.49xp + 0.741xc + l.426xk + l.006xm minimitzeu -0.49xp -0.741xc -l.426x¡¡; -l.006xm CONSTRICCIONS DE PES I VOLUM A LA FURGONETA El pes maxim que admet la furgoneta són 1400 Kg: El volum maxim que admet la furgoneta són 5 m3 0.003375xp + 0.0062:cc + 0.003:ck + 0.0022xm ::=; 5 Prac. O Jtimització Contínua I 59 roblema de la a esa usant CPLEX CONSTRICCIÓ DE SUPERFÍCIE D'EXPOSICIÓ La pagesa només exposa el producte vendible, no el desperdici, i la superficie maxima d'exposició son 10 m2 0.01 X (1 -0.02)xp + 0.06 X (1 -0.05)xc + 0.008 X (1 -0.08)xk + 0.004 X (1 -0.18)x-m � 10 o, el que és el mateix: 0.0098xp + 0.057xc + 0.00736xk + 0.00328xm � 10 LÍMITS EN LA COLLITA COMPENDI DEL PROBLEMA A RESOLDRE minimitzeu -0.49xp -0.741xc -l.426xk -l.006xm subject Xp + Xc + Xk + Xm � 1400 0.003375xp + 0.0062xc + 0.003xk + 0.0022xm � 5 0.0098xp + 0.057xc + 0.00736xk + 0.00328xm � 10 Xp � 900 Xc � 400 Xk � 600 Xm � 350 Xp 2 0 Xc 2 0 Xk 2 0 Xm 2 Ü SOLUCIÓ DEL PROBLEMA La solució del probl •ma anterior és: .r7J=44 .45 Kg , Xc=0.55 Kg (és a dir, g ns de carbassa a la practica), Xk=G00 Kg i Xm=J:-0 Kg amb un valor del guany de la pagesa de 1449.34 �- Les constriccions de pes de mercaderia a la furgoneta (1400 Kg) i de superficie cl'exposició (10 m2) són actives a la solució. No ho és la de capacitat de volum transportat a la furgoneta. Co lifica.c:i '.¡ i sohtció amb �l{PL ### pagesa.dat # set PROD := patata carbassa kiwi maduixa; param: preu volu_pes desperd supexp patata 0.5 0.003375 carbassa 0.78 0.0062 kiwi 1.55 0.003 maduixa 1.3 0.0022 param maxpes := 1400; param maxvol := 5; param maxparada := 10; 0.02 0.01 0.05 0.06 0.08 0.008 O .18 0.004 max_dia .- 900 400 600 350 ; Prac. O timització Contínua I ### pagesa.mod # set PROD; param preuPROD; param volu_pesPROD; param desperdPROD; param supexpPROD; param max_diaPROD; param maxpes; param maxvol; param maxparada; var collita j in PROD <= max_dia[j); # maximitzacio de la venda tenint en compte el desperdici 60 maximize venda: sum j in PROD preu[j]*(1-desperd[j))*collita[j); subject to pesmaxim: sum j in PROD collita[j]<=maxpes; roblema de la a esa usant CPLEX subject to volmaxim: sum j in PROD volu_pes[j)•collita[j]<=maxvol; subject to parada: sum j in PROD supexp[j]*(1-desperd[j])+collita[j]<=maxparada; ### pagesa.res 11 collita [*] := carbassa 0.550847 kiwi 600 maduixa 350 patata 449 .449 venda = 1449.338263 PRACTICA A REALITZAR Tindreu disponible al directori -opco/oc1/disponible/pr_ampl els arxius pagesa. dat, pagesa. mod i pagesa. run, amb el qual podreu resoldre el problema anterior usant AMPL [1] i el resolutor CPLEX. Modifiqueu l'arxiu pagesa. dat amb un producte addicional (p.e., tomaquet) del qual haureu d'introduir uns parametres raonables de preu, volu_pes, desperd, etc., i tornen a resoldre el problema. Cal que presenteu un full que contingui l'arxiu modificat pagesa. dat, i el nou arxiu <lf resultats obtinguts pagesa. res. Prac. Optimització Contínua I 61 pb. molins oli usant CPLEX i XPRESS Els molins d'oli (trulls) utilitzats des de temps immemorials a moltR pohles del Rud de Catalunya han de ser clausurats per raons medi-ambientals, ja que no disposen d'un sistema adequat de recollida i tractament dels residus del premsat de les olives. Han de se substitui:ts per uns quants macro-molins situats en punts estrategics on s'hauran de transportar les olives i eles d'on s'haura de transportar l'oli i on s'hi pot deixar emmagatzemat. Els productors d'oli de les cooperatives de sis comarques adjacents (Segria, Urgell, Gar rigues, Priorat, Baix Camp i Conca de Barbera) han acordat finarn;ar conjuntament la construcció i explotació dels macro-molins que les serveixin, havent establert els principis següents: *Cada comarca propasara una o dues localitats del seu territori, que estiguin ben comu nicades i amb els serveis necessaris a l'abast, com a possible seu d'una instal-lació de macro-molí. La llista de seus candidates és: Castelldans, Falset, Golmés, Mont blanc, Reus, Tarrega i Vinaixa *Tots els productors d'una certa comarca enviaran a tractar llurs olives al mateix macro molí. *S'avaluara el cost anual de transportar les olives i de retornar l'oli des de cada comarca a cada possible macro-molí considerant la producció total de la comarca. *Tenint en compte les despeses anuals d'explotació més amortització de cada macro-molí, caldra determinar quants macro-molins caldria construir i on, per tal de satisfer tots els productors amb cost mínim. *A més, atenent que a la comarca de les Garrigues es produeix un ter� del total conjunt de les comarques implicades, s'acorda que al macro-molí on envii: olives aquesta comarca no n'hi envii:n les altres. Plantegeu el programa enter a resoldre tenint en compte les dades següents: PRODUCCIÓ, PREU DEL TRANSPORT I COST EXPLOT.-AMORTITZ. DELS MACRO-MOLINS produc. preu de trnasport des de comarques d'oli Castell. Falset Golmés Montb. Reus Tarrg. Vinaixa comarca (tm/any) (:€/tm) (:€/tm) (:€/tm) (:€/tm) (:€/tm) (:€/tm) (:€/tm) Baix Camp 1800 930 600 950 590 310 920 700 C. Barbera 1400 600 725 500 290 610 420 400 Garrigues 4000 300 610 480 390 750 410 315 Priorat 1100 630 300 855 830 600 1020 700 Segria 1200 505 550 320 750 885 420 460 Urgell 2500 625 970 570 395 600 325 400 explt.-amort. (€/any) l.le6 l.0e6 l.2e6 l.le6 0.8e6 l.3e6 l. le6 VARIABLES BINÁRIES A CONSIDERAR Considerarem dos grups de variables binaries, corresponents a dos tipus de decisions: es construeix un macro-molí a la població "p" no s 'hi construeix amb pE{ e, f, g, 111, r, t, v} respectivament per designar Castelldans, Falset, Golmés, Montblanc, Prac. Optimització Contínua I 62 pb. molins oli usant CPLEX i XPRESS R.eus, Tarrega i Vinaixa. { 1 la comarca CO envia les olives al macro-molí de la població "p" XCOp =O no les hi envia amb COE{BC, CB, GA, PR, SE, UR} indicant respectivament Baix Camp, Conca de Barbera, Garrigues, Priorat, Segria i Urgell, i pE{ c,f, g, m, r, t, v} com abans. MODELITZACIÓ DE LA FUNCIÓ OBJECTIU Els costos anuals a minimitzar es composen del transport i de les despeses d'explotació més amortització dels macro-molins constru'its. El cost del transport entre entre una comarca i un macro-molí és el producte de la producció i el preu de transport per tona; p.e., entre la comarca del Segria i el macro molí de Vinaixa costaria 0.552e6xsEv (0.552e6=1200x460). L'explotació-amortització del macro-molí de Vinaixa costaría l.le6yv, En conseqüencia la funció objectiu fóra, comptant. en mili o ns d '-€: minimitzeu l.674XBCc + l.08XBCf + l.71XBCg + l.062XBCm + 0.558xBcr+ XCOp ,Yp veo \>'p l.656XBCt + l.26XBCv + 0.84xcBc + 1.015xcBf + 0.7XcBg+ 0.406xcBm + 0.854xcBr + 0.588xcBt + 0.56xcBv + l.2xcAc+ 2.44XGAf + 1.92XGAg + l.56XGAm + 3.ÜXGAr + l.64XGAt+ 1.26XGAv + Ü.693xpnc + Ü.33Xpn.f + Ü.935XPRg + Ü.913XPRm+ 0.66xpRr + l.122xpRt + 0.77XPRv + 0.606xsEc + 0.66xsEr+ 0.384xsEg + 0.9xsEm + l.062xsEr + 0.504xsEt + 0.552xsEv+ l.5625xuRc + 2.425xuR.f + 1.425xuRg + 0.9875xuRm + l.6xun.r+ 0.8125xuRt + l.0xuRv + l.lyc + l.Oyf + 1.2yg + l.lym+ 0.8yr + l.3yt + 1. lyv CONSTRICCIONS D'ENVIAMENT A UN SOL MACRO-MOLÍ Des de cada comarca s'enviaran totes les olives a un sol macro-molí: XBCc + XBCf + XBCg + XBCm + XBCr + XBCt + XBCv = 1 XCBc + XcBf + XCBg + XCBm + XCBr + XCBt + ;CCBv = 1 XGAc + XGAf + XGAg + XGAm + XGAr + ,'rGAt + ,'rGAv = 1 XPRc + XpRf + XPRg + XPRm + XpRr + XpRt + XPRv = 1 XSEc + XSEf + XSEg + XSEm + XSEr + :csEt + XSEv = 1 XURc + XURf + XURg + XURm + XURr + XURt + ;¡;URv = 1 CONSTRICCIONS D'EXISTENCIA DEL MACRO-MOLÍ AL QUAL ENVIEl\ LES COMARQUES Si el macro-molí de la població "p" no es construeix, no s'hi poden enviar olives des d la comarca "CO", és a dir, ho podem expressar com a: xcop::=::Yr \ICO\lp Prac. Optimització Contínua I63 pb. molins oli usant CPLEX i XPRESS pero aixo som moltes constriccions (6x7). Una forma alternativa més compacta és una constricció per macro-molí de la forma: XBCc + XCBc + XGAc + XPRc + XSEc + XURc :'.S 6yc XBCf + XcBf + XGAf + XpRf + XSEf + XURf :S 6yr XBCg + XCBg + XGAg + XPRg + XSEg + XURg :'.S 6yg XBCm + XCBm + XGAm + XPRm + XSEm + XURm :'.S 6ym XBCr + XCBr + XGAr + XPRr + XSEr + XURr :'.S 6yr XBCt + XcBt + XGAt + XPRt + XsEt + XURt :S 6yt XBCv + XCBv + XGAv + XPRv + XSEv + XURv :'.S 6yv estant el 6 dels t•rmes de la dreta motivat per si es construís un sol macro-molí i tates les e nia.rques hi envi ·.si:ün les olives. És clar que les constriccions anteriors forcen que si yp=O aleshores xcop=Ü V CO. CONSTRICCIÓ DE MACRO-MOLÍ EN EXCLUSIVA PER A LA COMARCA DE LES GARRIGUES Aixo implica que si de les Garrigues s'envia al macro-molí de la població "p", les altres comarques no hi envien, el qual requereix plantejar una disjuntiva, la qual pot ser modelitzada amb una variable binaria extra zpE{O, 1} i dues constriccions del tipus: XGAp :'.S 1 -Zp XHCp + XCBp + XPRp + XSEp + XURp S 5zp estant el 5 del terme de la dreta justificat per si les cinc comarques que no són les Garrigues envien tates a "p". La variable binaria zp, O o 1, impedeix que puguin enviar simultaniament els productors de les Garrigues o els de qualsevulla altra comarca perque sempre una de les dues constriccions tindra el terme de la dreta zero, i l'altra no. Per al conjunt de tots els possibles macro-molins: XGAc :'.S 1 - Zc XBCc + XCBc + XPRc + XSEc + XURc :'.S 5zc XGAf :'.S 1 -Zf XBCf + XCBf + XpRf + XSEf + XURf :S 5zr XGAg :'.S 1 - Zg XBCg + XCBg + XPRg + XSEg + XURg :'.S 5zg XGAm :'.S 1 - Zm XBCm + XCBm + XPRm + XSEm + XURm :'.S 5zm XGAr :'.S 1 - Zr XBCr + XCBr + XpRr + XSEr + XURr :'.S 5zr XGAt :'.S 1 - Zt XBCt + XCBt + XpRt + XSEt + XURt :'.S 5Zt XGAv '.S 1 - Zv :DBCv + :EcBv + XPRv + XSEv + XURv :'.S 5zv Prac. O timització Contínua I 64 b. molins oli usant CPLEX i XPR.ESS COMPF,NDT DF,l, PROBLEMA A RESOLDRE minimitzeu l.674XBCc + l.08XBCf + l. 71XBCg + l.062XBCm + 0.558xBcr+ xcop ,Yp ,zp v'CO v'p l.656XBCt + l.26XBCv + Ü.84XcBc + l.015XcBf + Ü.7XCBg+ 0.406xcBm + 0.854xcBr + 0.588xcBt + 0.56xcBv + l.2xcAc+ 2.44xcAf + l.92xcAg + l.56xcAm + 3.0xcAr + l.64xcAt+ l.26xcAv + 0.693xPRc + 0.33XpRf + 0.935XpRg + 0.913XpRrn+ 0.66xpRr + l.122xpRt + 0.77xPRv + 0.606xsEc + 0.66xsEf+ 0.384xsEg + 0.9xsEm + 1.062xsEr + 0.504xsEt + 0.552xsEv+ 1.5625xuRc + 2.425xuRf + l.425xuRg + 0.9875xuRm + l.6xuRr+ 0.8125xuRt + 1.0xuRv + l.lyc + l.Oyf + l.2yg + l.lym+ 0.8yr + l.3yt + l.lyv subjecte a XBCc + XBCf + XBCg + XBCm + XBCr + XBCt + XBCv = 1 XCBc + XCBf + XCBg + XCBm + XCBr + XcBt + XcBv = 1 XGAc + XGAf + XGAg + XGAm + XGAr + XGAt + XGAv = 1 XPRc + XpRf + XPRg + XPRm + XpRr + XpRt + XPRv = 1 XSEc + XSEf + XSEg + XSEm + XSEr + XS8t + XS8v = 1 XURc + XURf + XURg + XURm + XURr + XURt + XURv = 1 XBCc + XCBc + XGAc + XPRc + XSEc + XURc -6yc s; Ü XBCf + XCBf + XGAf + XpRf + XSEf + XURf -6yf s; Ü XBCg + XCBg + XGAg + XPRg + XSEg + XURg -6yg s; Ü XBCm + XCBm + XGAm + XPRm + XSEm + XURm - 6ym s; Ü XBCr + XCBr + XGAr + XpRr + XSEr + XURr -6yr s; Ü XBCt + XCBt + XGAt + XpRt + XSEt + XURt -6yt s; Ü XBCv + XCBv + XGAv + XPRv + XSEv + XURv -6yv s; Ü XGAc + Zc s; l XBCc + XCBc + XPRc + XSEc + XURc -5zc s; Ü XGAf + Zf s; 1 XBCf + XCBf + XpRf + XSEf + XURf -5Zf s; Ü XGAg + Zg s; 1 XBCg + XCBg + XPRg + XSEg + XURg - 5zg :S Ü XGAm + Zm s; l XBCm + XCBm + XPRm + XSEm + '.CURm -5Zm s; Ü XGAr + Zr s; 1 XBCr + XCBr + .TpRr + :1:SEr + :1:uRr -5zr s; Ü XGAt + Zt s; l XBCt + :ccBt + XpRt + XSEt + :cuRt -5Zt S O Prac. O timització Contínua I65 b. molins oli usant CPLEX i XPRESS XGAv + Zv '.S 1 XBCv + XCBv + XPRv + XSEv + XURv - 5zv '.S Ü xcop E {O, l}, Yp E {O, l}, Zp E {O, l} VCO Vp SOLUCIÓ DEL PROBLEMA La solució del problema anterior diu de construir tres macro-molins: el de Castelldans (yc=l), al servr.i exclosiu d k�s Garrigues (:i;GA .=1), el de R.cus (yr=l), al servei del Baix Camp i del riontt (xa r=�r.PRr=l), i el de Tm·r ga (Yt=l), lonant servei a la Conca de Bar bera, a la Segarra i a l'Urgell (xcBt=XsEt=XuRt=l). Per raó de les constriccions disjuntives tenim Zr=Zt=l. Totes les altres variables són zero. La funció de cost a l'optim val 7.5225 (7522500€). difica 'ió i · l utió amb Al\lIPL ### oli.dat # set NCOM := Baix_C Conca...B Garrigues Priorat Segria Urgell set NPOB := Castelldans Falset Golmes Montblanc Reus Tarrega Vinaixa param: prodoli := Baix_C 1800 Conca_B 1400 Garrigues 4000 Priorat 1100 Segria 1200 Urgell 2500 param: cexamor := Castelldans 1.le+6 Falset 1.0e+6 Golmes 1.2e+6 Montblanc 1.le+6 Reus 0.8e+6 Tarrega 1.3e+6 Vinaixa 1.1e+6 param preutra Castelldans Falset Golmes Montblanc Reus Tarrega Vinaixa Baix_C Conca_B Garrigues Priorat Segria Urgell ### oli.mod # set NCOM; set NPOB; 930 600 300 630 505 625 param neo := card(I/COM); param prodoli !IICOM}; param cexamor _N!'OB} ; param preutra -NCOM, NPOB} ; var yp {NP□B} binary; 600 725 610 300 550 970 var zp { NPOB} binary; var xcop {Nc□M, NP□B} binary; 950 590 310 920 500 290 610 420 480 390 750 410 855 830 600 1020 320 750 885 420 570 395 600 325 # minimitzacio del transport + explot, + amort. dels macromolins minimize transp_exfl_amort: sum { k in NPOB J ( sum { j in NCOM} prodoli [j] *preutra [j , k] * xcop [j , k] +cexamor [k] * yp [k)) ; 700 400 315 700 460 400 := Prac. O_ timització Contínua I 8ubject to conUumic..moli {j in NCOM}: sum {k in NP□B} xcop[j,k]=1; subject to exist�li { k in NPOB}: sum {j in NCOM) xcop[j ,k] -nco•yp[k] <=O; subject to nomes_garr_a..moli {k in NPOB}: xcop["Garrigues" ,k] + zp[k] <=1; 66 h. molins oli usant CPLEX i XPRESS subject to no_garr -�..molí { k in NPOB}: (sum {j in NCOM) xcop[j ,k]) -xcop["Garrigues" ,k] -(nco-1)• zp[k] <=O; ### ali.res # yp [•] := Castelldans 1 Falset O Golmes O Montblanc O Reus 1 Tarrega 1 Vinaixa O xcop [•,•] (tr) Baix_C Conca...B Garrigues Priorat Segria Urgell := Castelldans O O 1 O O O Falset O O O O O O Golmes o o o o o o Montblanc o o o o o o Reus 1o o 1 o o Tarrega o1 o o 1 1 Vinaixa o o o o o o transp_expl_amort = 7522500 PRACTICA A REALITZAR Tindreu disponible al directori -opco/oc1/disponible/pr _ampl els arxius oli. dat i oli. mod amb el qual, i un arxiu oli. run, que haureu de codificar de la forma que s'indicara a classe de practiques, podreu resoldre el problema anterior usant AMPL [1] i el resolutor CPLEX, reproduint els resultats donats anteriorment. A més, haureu de modificar els arxius oli. dat i oli. mod per introduir un nou pararnetre, de nom maxcapac que expressi que la capacitat maxima de processament d'un macromolí és dE 5000 tones i una constricció de nom capac_moli que expressi que cap molí rebi una quantitat d'olives per processar que excedeixi rnaxcapac. Feu un arxiu . run que resolgui el problemc usant CPLEX i que a l'arxiu . res hi aparegui, a més dels resultats presentats més amunt.  ali. res, la diferencia entre maxcapac i el total d'olives processades a cada macrornolí . Quan us funcioni tot també haureu de fer una versió modificada del vostre arxiu . run de la forma indicada a classe de practiques, per enviar a resoldre el mateix problema ami el resolutor XPRESS al servidor NEOS a la pagina web http: / /www-neas. mes. anl. gov, usant els vostres arxius ali. dat i oli. mad. Cal que presenteu els vostres arxius modificats oli. dat i ali. mad, l'arxiu creat ali. ru i l'arxiu de resultats obtinguts oli. res, tots ells amb la modificació deguda a maxcapac i l nova constricció capac_moli, i també la resposta obtinguda amb XPRESS al servidor NEO� \ Prac. Optimització Continua I 67 ph. estiro. d'estat amb const. MINOS L'estima •j' d' stat ja coi siderada coma problema ª\;!nse conRf,ricdcms a l'apartat FUN CIÓ QUALSEVOL: ESTINIA 1Ó DE TAT EN UNA XARXA ELECTRI A1 es transforma en un problema amb ons ricci ns quan tenim en compte uns possibles aspectes addicionals que pot tenir el problema, descrits a continuació. CONSTRICCIONS EN L'ESTIMACIÓ D'ESTAT Una possible constricció sorgeix quan es considera més d'una mesura de magnitud de tensió en nUsos de la xarxa. La mesura d'un dels nusos és la tensió de referencia, ja considerada. Tata altra mesura de magnitud de tensió constitueix una constricció (no lineal) d'igualtat. Sigui j un nus ( que no és el de referencia) del que disposem d'una mesura de magnitud de tensió ti. La relació d'aquesta mesura amb les variables del problema és la constricció: eJ + JJ = t;. A les xarxes hi pot haver nusos on no hi hagi cap consum ni cap generació connectats. Tata la potencia, activa i reactiva, que arriba per una de les línies connectades, ha de sortir per una altre línia. Aquests tals nusos s'anomenen d'injecció nul-la, i aquesta d'injecció es pot expressar analíticament com la suma de les potencies de tates les línies que hi estan connectades. Les injeccions nul-les constitueixen una mesura perfecta, ja que no comporta error i, a més, la tenim a cost zero. (Les altres mesures tenen un error de mesura associat i costen diners en aparells de mesura i equips de transmissió de dades.) Sigui k un nus d'injecció nul-la. Sigui Ik el conjunt de nusos connectats directament a k. Les constriccions d'injecció nul·la referides al nus k són: I:Pki = 0 iElk Tenint en compte ( 4) podriem expressar les constriccions anteriors com a constriccions no lineals (de segon ordre) en les variables del problema (ek, Ík, k = l, ... , Nn). En aquesta practica es vol trabar la solucó de l'estimació d'estat tenint en compte diverses mesures nagnitud de tensió, i un o mes nusos d'injecció nul•la. SOLUCIÓ DEL PROBLEMA Tot. seguit es donen les dades utilitzades i la solució del problema obtinguda amb AMPL cridant a MINOS. Coclific::a ·ió de les dadcfi i soln .i > amb Ltv1PL ### estestnO.dat # set NUS0S := A BCD E F pararn Nlin := 8 ; pararn: respu reapu sutpu .- 1 .0011 .0089 .0244 2 .0042 .0206 .0571 3 .0019 .0209 .0519 4 .0037 .0183 .0510 5 .0021 .0164 .0427 6 .0182 .0885 .2475 7 .0118 .0921 .2330 8 .0185 .0890 .0510