Optimització de Models No Lineals Amb Constriccions. Càlcul de la posició d'equilibri d'una cadena

EST APNL A D'ESTADI APLICACIONS DE LA , PROGRAMACIO NO LINEAL "Calcul de la posició d'equilibri d'una cadena" F. Javier Heredia ''C~ >S .. - UNIVERSITAT POLITECNICA DE CATALUNYA Biblioteca 111111111111111111111111111111111111111111111111111111111111 1400210673 rcr T\I DE Df, \l \I I"\lÁTIQLE~ I EST,\DÍSTICA Aplicacions de la Programació No Lineal Optimització de Models No Lineals Amb Constriccions Calcul de la posició d'equilibri d'una cadena F. Javier Heredia Cervera Departament d'Estadística i Investigació Operativa Secció d'Informatica UPC Índex 1 Índex 1 Calcul de la posició d'equilibri d'una cadena . ... . ... ... 3 l. l. Presentació del problema .... .. .. .... .. .... . . .. .................... 3 1.2. Formulació del Problema . . .. ...... . . ... . . ... . .. .......... ... .... . . 3 1.2.1. Variables. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.2. Funció Objectiu . .. . . ............... . ..... . .. ... ..... . ... . ... 5 1.2.2.1. Energía potencial gravitatória . . .......... ... .. . .. .. .. 5 1.2.2.2. Energía potencial e la s tica . .. . ..... ...... . ...... . . ... . 5 1.2.3. Constriccions .. . ...... .... ... ....... . .. . . .... . . ..... . . . . .... 6 1.2.3.1. Sumatori de les y; . .. . . .... . . . . .. . .. . ... .... .. . ..... . 6 1.2.3. 2. Sumatori de les x;: .. . . .. . .... .. . . ... . .. . .. .. . . . ... . . 6 1.2.3.3. Longitud maxima i mínima de les baules e lastique s ... 7 1.2.4. Fites a les variables . . ........ ... .. . ......... .. ............ . . 7 1.2 .5. Formulació final. . . . ... .... . .. ............. .. . ........ ... .. .. 7 1.3. Dades necessaries pera l'execució del problema . ..... . ... ..... ..... 8 1.4. Codificació del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.4.1. Comprovació de les rutines d'usuari FUNOB.J i FUNCON . . 10 1.5. Solució obtinguda en executar el problema .. . ... . ..... . ..... . ... . . 11 2 Introducció al paquet Minos ... .. .... ... .. . ..... .. ...... ... 15 2.1. Dar1 ° ~ generals ....... .... .. .. . .. . ...... ..... .... . ... . ............ 15 2.2. Problema es tandard ...... . ......... .. . . . . .. . . ..... . . ..... .... .... 15 2.3. Metode de treball de Minos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.4. Rutines i fitxers d'usuari . . ..... .. .... ... ..... . . ... .... . ... ..... . . 17 2.5. Lectura i esc riptu ra de dades a les rutines FUNOB.J i FUNCON. . 18 2.6. Apartat SPECS .... . .. . ... ... . .. .. . ...... .. .. . .... . . ... . ..... . . . . 19 2. 7. Apartat MPS .... . . . . .. . .. . .. . .... .. . . .. . .. ... ...... .. . .. . .. .... . 20 2.8. Ex e mp le de coclificació d'un probl e ma en format MPS ..... .. . . . . . 24 2.9. Muntatg e i execucio .. .... ..... ....... . . . .... . .... . .. . .. .. . .. .. . .. 26 3 Informe de la practica ... ... . ... ... ......... .. ... .......... .. 29 1 Calcul de la posició d ' equilibri d'una cadena 3 1 Calcul de la posició d'equilibri d'una cadena. 1.1 Presentació del problema. Tenim una cadena formada per n baules lineals de dos tipus: rígides i elastiq1i,es. Cadascuna té una llargaria /;, on l'índex i indica la posició de la baula dins la cadena, comen.,ant per !'esquerra. N' hi ha tres baules e!astiques, amb índexs i = e1, e2, e3. Es definira el conjunt d 'indexs de les baules e!astiques [ = {e¡, e2, e3 }. Els coeficients d'elasticitat seran, respectivament k1, k2 i k3. Per aquestes baules, la longitud l; correspon a la l'estat en repós (longitud en repós ). Quan la cadena arribi a la seva posició d'equilibri, les baules elastiques s' hauran estirat fins a la seva longitud en equilibri), que anomenarem Z;. Considerarem, a més, que aquestes baules es poden estirar com a maxim fins a una longitud l;. Totes les baules estan fabricades amb el mateix material, de densitat lineal.\= (1/9.S)Kgr/m. Així dones, la massa de les baules és proporcional a la seva longitud en repós, amb constant de proporcionalitat .\. La cadena es penja pels seus extrems, separats una distancia horitzontal Lx y vertical Ly. L' objectiu de la practica és trobar la forma exacta de la cadena penjada de la forma indicada. 1.2 Formulació del Problema. 1.2.1 Variables. Considerem que la baula i-éssima, degut a la seva orientació dins la cadena, augmenta la longitud d'aquesta en una quantitat x;, horitzontalment, i y; verticalment: Les x; són sempre positives, pero les y; poden ser positives, si apunten cap a dalt, o negatives, si apunten cap a baix. 4 y Dept.EIO / UPC / Optimització de models no lineals amb el paquet MINOS Longitud en re pós b. e. o o /¡ Longitud maxima b.e. o () l; Figura 1.2 : Esquema d'una cadena amb deu baules en posició d'equilibri. En aquest cas E= {1,5,6}. Yi-1 Figura 1.1 : Expansió de la longitud de la cadena Coneix em les l; de totes les ba ul es rígides , raó per la qua! nom és ens cal coneixer o X¡ o y¡ p er a sab er l 'o rie ntació de la baula dins la ca de na. Agafar em com a var i ables del probl e ma l es y ¡, Vi E E. De les baules el as tiqu es no c on e ixem X 1 Calcu l de ~ la se va long:: :._ probl ema _ .: :: 1.2.2 F uac · El si < e=a : energi a po: _e ;;.. la en ergi a p<i-e:::. 1.2.2.1 Ene1 Si fix eI::! punt d' on ~ _ seu pu nt ui.~ és: on h; és la ci::-.; . .:: del pun t de ~ ~ -:'! l'accel er aci o ·"' ~ const ant ). P ::~ aques ta i gc;~ - ¿  potencial g-:-c.·-: -- 1.2.2.2 E n e::- La for~c. :·~-;: de la seva :o::.~ - .! / .... r. .... ~ =-c¿iJ ri e e-ci.:..ii!ori . En ?l. :comés e ns ca l :K!e::a. A gafa rem --.:.""" :: 10 cont'lxem X 1 Calcul de /a posició d'equi/ibri d'una cadena 5 la seva longitud en equilibri, la qua] cosa implica considerar coma variables del probl e ma les x¡ i y¡ Vi E E. Així don es, les variables del nostre problema serim: y¡ X¡ 1.2.2 Funció Objectiu . i = 1, ... , n Vi E E (1.1 ) (1.2) El sistema format perla cade na p en jacla es trobara en equilibri quan la seva energia potencial total sigui mínima. L'energia potencial total sera la suma ele la ene rgia pot en cia l gravitatór ia Ua i de l' en erg ia pot e ncial e lastic a Us: Ur = Ua + Us (1.3) 1.2.2.1 Energia potencial gravitatória. Si fixem coma punt de ref erencia, a mb energ ia poten cia l nul·la, !'altura del punt d'on es pe nja la primera baula, i la m assa de cada baula concentrada en el seu punt mig (centre el e masses C.M. ), l'en ergia potencial ele la ba ula i-éss ima és: Ua, = m.;gh¡ (1.4) on h¡ és la distancia vertical que separa el centr e de masses de la baula i-éssima del punt de referencia (amb valor negatiu, si esta per sota). g = 9.8m./ s2 és l'acceleració ele la gravetat prop de la superficie de la te rra (que es pot cons iderar constant ). Podem expressar les h¡ en funció ele les y¡ a través de l 'exp re ssió: 1 1 i-1 h; = y¡ + Y2 + . .. + 2y¡ = 2y¡ + L Yi j=I (1.5) aq u esta igualtat permet expressar Ua, en funció de les variables y¡. L 'energ ia po te ncial gravitator ia total sera la suma de totes les Ua,: n Ua = ¿ua, i= l 1.2.2.2 Energia potencial elast i ca . (: .6) La fon ;a feta per una molla coma resp osta a una va ria ció !:::.l (amb sig n e) ele la seva longit ud res pecte ele la seva posició en repós és: Fs = - k · !:::.l (1.7) 6 Dept.EIO / UPC / Optimització de models no lineals amb el paquet MINOS Podem calcu lar !' energía potencial d'una molla sotmesa a un estirament L\l amb la fórmula: · ¡ Ll.l ¡Ll.I 1 Ll.I 1 UE(t..l)=- -k·x·dx=k x ·dx=-· k·[x 2]0 =-·k ·t..12 (1.8) o o 2 2 Per a cada una de les baules elastiques [ tindrem: 1 2 UE· = - · k · t..l ' 2 1 (1.9) on t..li és l' increm en t de longitud respecte de la longitud en repós de la baula elastica quan la cadena es troba en equilibri: t..l; = i; -l; Vi E E (1.10) Tant la longitud en repós l; com el coeficient d'elasticidad k; són dad es de l'enunciat . Z; és la longitud de la baula i quan la cadena esta en equilibri. Pot ser expressada en funció de les x; i y¡: (1.11) de forma qu e: L\l; = j x; + Y7 - l; (1.12) s ubstituint (1.12) a (1.9) obtindrem l'express ió de !'energía potencial elastica de la baula i amb i E [ en funció de les dades del probl e ma i les variables. L'energia potencial ela stica total sera, evidentment , la suma de U E, peri E[: 1.2.3 Constriccions u E= l::uE, iEf 1.2.3.1 Sumatori de les y;. (1.13) La suma deis valors le les variables y; ha de ser igual a la distancia ve rtical entre els dos punts de suspensió ( hem de tenir en compte el conveni de signes: n ega tiu cap a baix, positiu cap a dalt): n (1.14) 1 Cii.l cul ée a - - 1.2.3.2 m La u.::::a ..:=. zontal em:-e -¿ Les variab:e:s -- constri cció : 1.2.3.3 Loe;: Com a maxim a r.. ?-:::- ¡¡ no es c on ~~a=: sera/;: 1.2.4 Fi _ S'h ¿·==:: i hori tzom <L.:=:-::_ S'ha de fer ::: -;;.:: i E [ ja es~a.:. ..:: - 1.2.5 Form L 'exp: .:o_ == ~ ,;;;aquer .\HNOS _,-~-~e::i : _:i. ¡ amb !'~ : .8) ( ~ . 9 ) -, - ée La baula ( 110) 1 ~- dades de e::: ~ci!.ib ri. Pot (1.11) (1.12) 1 :;:; 1J · encial elastica i::::.o : :es \a.riables. ce CE, pe r i E[: (1.13) -Cis :3..::icia ve rtical :::;-eni de signes: ( 1.14) 1 Ca/cu/ de la posició d'equilibri d'una cadena 7 1.2.3.2 Sumatori de les x;: La suma dels valors de les variables x¡ ha de ser igual a la distancia horitzontal entre els dos punts de suspensió: LX¡= Lx (1.15) i=l Les variables del nostre problema són les y¡, i = 1, . .. , n i les x ¡, i E E. La constricció (1.15) es pot s'expressa en funció d'aquestes variables coma: ~X + ~ Jl2 -y2 = L ¿_, t ¿_, t t X (1.16) iEf if/.f 1.2.3.3 Longitud maxima i mínima de les baules eiastiques. Com a dade del problema s'impossa a cada baula elastica una longitud maxima l;. Per altre banda, degut a com es penja la cadena, aquestes baules no es contrauran (per que?), la qua! cosa vol dir que la seva longitud mínima sera {¡: l· < Jx 2 + y2 < r t - t l - t Vi E E (1.17) 1.2.4 Fites a les variables. S'han d'imposar fites a les longituds en que la cadena és expandida, vertical i horitzontalment, per cada baula: -{¡::;:y¡::;:/¡ Ü ::;: X¡ Vi rf. E Vi E E (1.18) (1.19) S'ha de fer notar que les fites -l¡ :S: y¡ :S: l; i x¡ ::;: l; per a les baules elastiques i E [ja_ estan incloses a les constriccions (1.17) . 1.2.5 Formulació final. L'expressió final del problema d'optimització a resoldre és: 8 Dept.EIO / UPC / Optimització de models no lineals amb el pa<¡uet MINOS rn1n x;,i E E y¡, 'Vi Subj.a: n Ua +U E = L Ua, + L U E, i= l iEt: i=J iEt: i~t: Vi E E -/; :::; y¡ :::; /; Vi 't E o:::; X¡ 'Vi E E (1.6) ,(1.13) (1.14) (1.16) ( 1.17) (1.18) (1.19) on n, E, Lx, Ly, l;, l;, i els valors clels coeficients cl'elastic itat k; que intervenen a les expressions ele U E, són clacles conegucles. 1.3 Dades necessaries per a l'execució del problema. Les clacles associacles a ca da alumne es poden generar amb el programa cadegprob. Aqu e st programa només necessita el número d'identificac ió el e l'alumne num , i cr eara , en el directori on s'executi, un fitxer anomenat cadenanum. dat similar al que mostra la figura Fig. 1.3. Si la baula més alta és !'última, la situació en que ens trobem correspon a la representada a la Fig . 1.2. Si la baula més alta és la primera, llavors, prenent com a criteri arbituri que la primera baula es penja sempre de l'o.ig,c;n de coo rd e nad es, el valor de Ly s'haura ele cons iderar negatiu. L es dades del problemes estan ex pr essacles en unitats del Sist em a Inter - nacional: longituds en metres, masses en quilograms, forc es en Newtons, etc . D'aquesta forma el valor ele l'energia total del sistema calculada a la funció objectiu del nostre problema estara expressacla en Joules. 1.4 Codificació del problema. Per ta l ele resolclre el probl e ma plantejat amb Minos, s'hauran ele co dificar les rutin es cl'us uari FUNOB.T i FUNCON, i s'haura de cr e ar un fitx er 1 Calcul de la ~~ PROBLE:!U DAD ES . r:s:: :: • e:::::: :::::r 1 = 3 . 2 1 7 = 1.9 : ~ = Figura 1.3 : E x~=:- cadena.da t q e - ::·_ ficacions del ma::·· - DIR$EIO: [0~1- = _ - ' RDWS del ma e '..x :: a les subru i n~: _· l 'ordre de l es co::.::--': co·N L1 dr -:l '.::".:....: - X(N) =[y1 • ?d'luet \HNOS ' :-;;e:: == : :a:>X .....;:~- .. !~::;: . 1 ;;;..;r. K• J == ::OXC : .. XO:.C : :Q:l.."'C .: . :-:ucc !O := :1 : ,:i'.J_-;::c !1 : :o:co 13 : .JXfOC " :COJO !5 : :0000 ! 6 :OJOO 17 : :c.:icJC !8 : xo:io 19 ·-c.ce::.a. Corres pon a 2 Introducció al paquet Minos 15 2 Introducció al paquet Minos. En aquest capítol descriurem el paquet Minos d'optimització, amb el qua! poden solucinar -se tots els problemes anteriorment plantejats. Val adir que, per la petita mida d'aqu e sts problemes, altr es paquets m és "amicables" podrien ser usats. Tanmateix, el fet de que Minos sigui actualment un dels millors paquets comercials (per no dir el millor ), fa que sigui co nvenient haver treballat amb ell i cone ixer-lo mínimament. 2.1 Dades generals . Minos és un sistema informatic escrit en Fortran dissenyat per resoldre problem es d'optimització de grans dimensions (problemes lineals i no lin eals, tant pel que fa a la funció objectiu coma les constriccions). El nom és un ac ronim i significa Modular In-core Nonlinear Optimization System . Els seus autors són Bruce A. Murtagh i Michel A. Saunders (Systems Optimization Laboratory , Department of Op e rations R esea rc h, Stanford University , California) . 2.2 Problema estandard. on : El problema est anda rd a mb qu e Minos tr e balla té l'expressió : mm. F(x) + c1x + d1y subj . 11 S f(x) + A1y S 1l¡ 12 S A2x + A3y S 112 • Vectors consta nts : cE ffin1; dEffi; 1s (~) s u (2.1) 16 Dept.EIO / UPC / Optimització de models no lineals amb el paquet MINOS U1, /¡ E ffim¡ i U2, 12 E IR;' l, u E IR,"1+n2 • Matrius constants: A1 E (m1 x n2) A2 E (m2 x n1) A3 E (m2 x n2) • Variables i funcions: F( x ): funció escalar de variable vectorial. J(x): funció vectorial de variable vectorial. f(x) = {f(x);}, i l ... m1. 2.3 x E IR, n,: variables no lineals. y E ffi"': variables lineals. 11 S f(x) + A¡y S 111: constriccions no lineals. 12 S Azx + A3y S u2: constriccions lineals. Metode de treball de Minos. Per a re soldr e un problema amb constriccions d'igualtat no lineals Minos efec tua una serie d'iteracions majors (MAJOR ITERATIONS) . Dins de c ada iterac ió major es resol un subproblema amb constriccions lineals (MINOR ITERATIONS). Aquest subprobl e ma esta format perles constriccions lineals i fites del problema original i per una linealització ele les constriccions no lineals. Aquest procés de linealització consisteix en substituir la fun c ió vectorial f(x) ele (1) per una aproximació de prim er orclre f(x) fent s ervir el jacobia ele les constriccions no lin eals en el punt Xk (cl e notarem el jacobi a amb Jk) : El subprobl e ma resolt a cada iter ac ió majo r k ~s : min. t t t - ) 1 - t( - F(x) +ex + d Y ->.k(! - Ík + 2.p(f - Ík) f - Ík ) Ík + A1y = b1 A2x + A3y = b2 subj. (2.2) zs G) su 2 Intr oduc aá .._ - on: •L a:':;.:::._ • >., -= ~ con stri ccio~- - - • ~ p ;- __, - quadr a¡i c;_ ~'- ~: 2.4 Ru · r uti a ? ~ _ - .: r utina fitx er fitxer Hi ha de] clu ster cie ~ ?;:..-_ cadena. da: : ~a:::=.=. p rogr am es e- --~- ~ . N OBJ i H _ - (-c) --:-:" estigui ese · e= ? ~ me t p od er g _· :o0 -_ = esta escr it en F o:-::-- - en e u en :-0::-:::-~ Els par fil!::p· :=- ~ =-- FUN OB J· ParB.me.:- _ -: E=·::- c. ·c. i >=-= · ec I yaquet ~HNOS -: _: (I ) ,}. i == - · ·:i.· ::o :..ine als Minos . _ :·::: . Dins de cada ~_,.0 ~11 ;-;0R ITE- -:;:.:: ... -:~::!5 lineals i fites -:io:::.5 ::io lineals. -= ~ :':mció v ectorial !:: =e:-.-:r el j acobia de --".-:a a:nb h ): - J e I -X k ) j'1 .C f - jk) (2.2) 2 lntroducció al paquet Minos 17 on : • La funció objectiu de (2) s'anomena Lagrangia augmentat. • Ak és una estimació al punt Xk dels multiplicadors de Lagrange de les constriccions no lineals. • tPU -}k)1 (j -}k) és el que es coneix com a !unció de penalítzacíó quadratíca, amb parametre de penalització p. 2.4 Rutines i fitxers d'usuari. La informació que Minos necessita per a resoldre el problema se li ha de subministrar mitjarn;ant dues rutines i dos fitxers amb informació (dos fitxers que es poden convertir en un que contingui la informació dels dos anteriors): rutina FUNOBJ } juntes en un sol fitxer cadena. for o cadena. c rutina FUNCON fitxer SPECS } junts, i en aquest ordre, en un sol fitxer cadena. dat fitxer MPS Hi ha unes plantilles d'aquests fitxers al directori: DIR$EIO:[ONLC] del cluster de la Facultat d'Informatica de Barcelona. Els fitxers s'anomenen cadena. dat i cadena. for . Al fitxer cadena. for hi ha un possible main de programes per treballar amb Minos, així com la capc;alera de les rutines FUNOBJ i FUNCON amb la declaració de variables . El main és recomanable que estigui escri t en Fortran (es pot mantenir el que hi ha o can vi ar-lo). Aixo permet poder gestionar els fitxers d'entrada i sortida de dades, donat que Minos esta escrit en Fortran. Les funcions FUNOBJ i FUNCON poden ser codificades en e u en :ortran. Els parametres particulars de cada rutina són: FUNOBJ: Funcíó: Codifica la funció objectiu i el seu gradient. Parametres: Entrada: N: nombre de variables no lineals X: vector de dimensió N que conté el valor de les variables 18 Dept.EIO / UPC / Optimització de models no lineals amb el paquet MINOS Sortida: a cada passa. L'ordre en que estan emmagatzemades les variables ha de coincidir amb el declarat a l'apartat COLUMNS del fitxer MPS. F: valor de la funció objectiu corresponent a la X actual. G: vector de dimensió N per emmat;atzemar el gradient de F (ésa dir G(i) = :~ ). FUNCON: Funció: Codifica les constriccions no linea ls i els seus gradients (jacobia). Paramet res: Entrada : N: nombre de variables no lineals. M: nombre de constriccions no lineals (només s'usa si el jacobia es codifica de forma densa) . NJAC: nombre d'elements no nuls del jacobia (només s'usa si el jacobia es codifica de forma esparsa). Sortida : X : vector de dimensió N que conté el valor de les variables no lineals a cada iteració . F: vector de dimensió M la component i del qua! correspon al valor de la constricció no lineal número i pels valors de les variables no lineals de la iteració actual ( emma - gatzemades a X). G: si el jacobia actual s'emmagatzema dens, és la matriu (M x N) que correspon al jacobia de F. Si el jacobia s'emmagatzema espars, és el vector de dimensió NJAC que conté els elements no nuls del jacobia en el mateix or - dre que l'indicat a l'apartat COLUMNS del fitxer MPS. 2.5 Lectura i escriptura de dades a les rutines FUNOBJ i FUNCON. < I> Minos té declarada un zona COMMON anomenada MlFILE ambles varia - bles IREAD, IPRINT, ISUMM . Ens interessa el contingut de les dues primeres: <I> El <lit en aquest apartat, pel que fa a les zones COMMON, només té sentit si les rutin es FUNOBJ i FUNCON estan programa.des en Fortran . 2 In troducc io;;... ::;.- IREAD : :.:=..:.-- - exe::::::~ IPRI.\T :.:=:-"' ~ Es a 6:- ~ -~ CO!vüIO_ -? ~ :- ~ =.: aleshor es es gir in formac:-o a.: ::-· exempl e. pe:- _ -·- tates les~ 2 ~ 2.6 Aparra· L'apa:-·a· ;: _ _=.: defineix e s c:E : f'~"":: Jes cara cte:¡s·: 1'aspecte g ene:-¡ BEGf.\- - - ~ -- --- E.\"D De Ja pri::::e:-a -- de la segona 5; = ~ :::::; Vegem a co SPECS . Param etres q:;e ;:>aqu et ).HNOS =::::ag atze mades ~a~ a 1 º apart at ~ a ~a X actu al. e::.a.= el gradie nt de ~ d-:e :: n s ( jacob ia ). ::!e sºu sa si el ja- ::o::nés s ' usa si el : cie les variables · : ce'. qual co rrespon :: .:::::e:-o i pe ls valors ~·-:ó act ual (emma- :.e::l-S. és la matriu :e F. Si el jacobia :.e dim ensió NJAC . b:á en el mateix orl_~.!> S del fitxer MPS. • :S ruti nes FUNOBJ !:. ?~S amb les varia- ¡-_::; ce '. es dues primeres: __ _ ~O :\" . només té sentit :: : o: n an. 2 Introducció al paquet Minos 19 IREAD: unitat logica de lectura assignada al fitxer d'entrada de dades (per exemple, cadena. dat ). IPRINT: unitat logica d'escriptura assignada al fitxer de sortida de resultats (per exemple, cadena. lis ). És adir, si des de les rutines FUNOBJ i FUNCON s'accedeix a la zona COMMON MlFILE afegint al codi: COMMON /MlFILE/ IREAD,IPRINT,ISUMM aleshores es poden llegir dades afegides del fitxer d 'entrada cadena. dat i afegir informació al fitxer de sortida cadena. lis . Aixo e arrer pot ser útil, per exemple, per escriure a la darrera iteració el valor de les variables a l'optim amb totes les xifres significatives desitjades. 2.6 Apartat SPECS. L'apartat SPECS (o fitxer si esta separat de l'altre apartat anomenat MPS) defineix els diferents parametres sobre el funcionament del paquet Minos i sobre les característiques del problema. El format d'entrada de dades és lliure, i l'aspecte general de l'apartat SPECS és: BEGIN PARAULA_CLAU_l [PARAULA_CLAU_2] [VALOR_NUMERIC] END De la primera paraula clau només són significatius els tres primers caracters; de la segona (si n'hi ha segona) només són significatius els 4 primers caracters. Vegem a continuació una part del parametes que poden ser indicat a l'apartat SPECS . Parametres que depenen de les dades del problema: COLUMNS k: amb k indiquem el nombre sobreestimat de columnes de la matriu de constriccions (nombre sobreestimat de variables). ROWS k: amb k denotem el nombre sobreestimat de files de la matriu de constricions (nombre sobreestimat de constriccions lineals i no lineals ). 20 Dept.EIO / UPC / Optimització de models no lineals amb el paquet MINOS ELEMENTS k: k és el nombree sob reestimat d'elements no nuls a les matrius A1, A2, A3 i al jacobia. NONLINEAR CONSTR. k : on k és el nombre de constriccions no lineals. NONLINEAR VARIABLES k : on k és el nombre de variables no lineals. Parametres que no depenen de les dades del problema: JACOBIAN SPARSE: indica que el jacobia s'emmagatzemara de forma esparsa, ésa dir, només es guardaran els elements no nuls del jacobia. Es diu que una ma - triu és esparsa si té un a gran quantitat d'elements nuls. Si el jacobia és espars resulta convenient triar aquesta opció. Si es volgués emmagatzemar dens no caldria especificar res, donat que aquesta és l' opció per defecte. DERIVATIVE LEVEL k: controla el calcul del gradient de la funció objectiu i del jacobia de les constriccions: 2.7 k=l: Minos calcula el jacobia i el gradient s'ha de codificar a la FUNOB.J. k=2: Minos calcula el gradient i el jacobia s ' ha de codificar a la FUNCON. k=3: S'ha de codificar gradient i jacobia. Aquesta és l 'o pció amb que haureu de resoldre el problema. VERIFY : Provoca la comprovació per diferencies finites de tots els elements del gradient i del jacobia. calculats per les rutines FUNOBJ i FUNCON. LOG FREQUENCY k: controla la freqüe ncia amb la que s'escriu in - formació al fitxer de sortida . S'imprimira una línia d'informa ció per cada k iteracions menors. Apartat MPS. Especifi ca els noms de les constriccions i variables, indica com intervé cada variable din s cada constricció, i defineix els termes inclependents de les constriccions i els límits de les variables. Aquest format no és propi de Minos; és un format estandard d'especificació de problem es usat per diversos paquets 2 Intr oducc 10 "-' -- d 'optimi tza.c:: o El forr!:!é. - :: columnes de -= - 123456 789 :¿~~-=~ NAME ROWS CDLUMNS vari2 : :.e RHS RANGES BOUNDS -- zz no _b ou=_ ~ ENDDATA Al :\f P a::: -__ • les dade s que -- -:~ ca ra cters max:.:::: vw, nom u indo - - ~ ~ el nom do na - ;;_ ;-'-' -~ c onjunt de <i::!Z~ .:. ~  donat a] conj - _ _ les secci on de~ ; .2 .=- Secció 1 YA.\IE: S 'u sa per co::.c.:: - hem d'uti lirzar :: 1234.:::-.:=: llA..~ . on problema és e: ::. blanc . paquet ~ H N OS ~; ¿·el ements no _.;.3 : al j acob ia. no line- ~-::::.3:e:: ::o lineal s. ;;.g¡;.~zem ara de for- "' es piard aran els ele- :::.:= C.:.i: que una ma - ::a:::• i ta t d ' elements :-~.::ta convenient ~ ~es e mroagatze - . ..::. :.G:" :: e:. donat que ~ - 5="adie nt i el ja- - a- ::3car a la FUN- =.--z.::- grad ient i jaco- <. e: :·opció amb que ::-esú: :: e el prob lema . ?""~ ci:e rencies finites :::c-W:e-:it i del jacobia : c:o BJ i FUNCON. :a que s'esc riu in5 · im prim ira una -< i¡eraci ons menors. ca com intervé cada e::.cents de les cons- ::. o é:; pro pi de Minos; .sz• ::ie:- diversos paquets 2 Introducció al paquet Minos 21 d'optimitz ació. El format d'entrada no és lliure i cada paraula clau ha d'estar entre unes columnes determinades al fitxer. L'aspecte general de l'apartat MPS és: 123456789Ó1234567896123456789~123456789~123456789g123456789812345 NAME nomuproblema ROWS ww constricció COLUMNS variable constru1 coeficientu1 constru2 coef icientu2 RHS nomuindp construu termeuindependent RANGES nomurang construu valorudelurang BOUNDS zz nomuboun variable valorudelulimit ENDDATA Al MPS anterior en majúscula apareixen les paraules clau i en minúscula les dades que varien d'un problema a l'altre (i subratllats hi ha el nombre de caracters maxim que pot ocupar cada nom). Els camps que s'han marcat com ww, nomuindp, nomurang, zz i nomuboun indiquen el tipus de constricció (ww), el nom donat al conjunt de termes independents (nomuindp), el nom donat al conjunt de rangs (nomurang) , el tipus de límit de la variable (zz) i el nom donat al conjunt de límits (nomuboun). Descriurem a continuació cadascuna de les seccions del MPS . Secció N AME: S'usa per donar un nom al problema que s'esta codificant. El format que hem d'utilitzar és: 123456789Ó123456789612 NAME . ......... problema on problema és el nom que donem al problema i els punts indiquen espais en blanc . 22 Dept.EIO / UPC / Optimítzació de models no Jinea/s amb el paquet MINOS Secció ROWS: Declara el nom i tipus de les constriccions (i de la part lineal de la funció objectiu si n'hi ha) . S'han de posar primer les no lineals i a continuació les lineals. El format que hem d'utilitzar és: 123456789012 ROWS .w w.constric on els punts indiquen espais en blanc, constric és el nom de la constricció i ww ens indica el tipus de constricció que pot ser: Secció COLUMNS: > < funció objectiu o constricció lliure Aquesta secció del MPS serveix per: l. D eclarar els noms ele les variables. 2. Donar valors als coeficients amb els que intervenen les variables dins de cada constricció lineal. 3. Si el ja co bia s'emmagatzema espars, indica quina és la posició dels elements no nuls del jacobia. En aquest cas, el valor numeric indicat no té importancia (pot ser zero, per exemple ). Si hi ha variables lineals i no lineals, primer s'han de declarar les no lineals. Fins que no s'han introdult tots els coeficients que afecten a una variable no es pot comen<;;ar amb una nova variable. L'ordre en que es declarin les variables no lineals ha de coincidir amb l'ordre usat al vector X de les funcions FUNOB.J i FUNCON. Així , com e n<;;ant amb X(l) i continuant fins a X(N) haurem de declarar: l. el nom triat per a la variable X( í). 2. si el jacobia s' e mmagatzema en forma esparsa, els ele ments no nul s de la colum ,a i-essima del jacobia, indicant el nom de la const ricció no lineal corresponent i un valor numeric fictici. 3. els coeficients no nuls de la co lumna iessima de la matriu de constriccions lineals, indicant el nom de la constricció lineal i el va lor numeric del coeficient. 2 Introducc ió a. - - _ El for ma · ¿·_ 1 234:-- :_ _: ce:.... :: on els pun s '..::! • _ -= estem tra er ar:·. ::~-, variable en q:::e:-- que la \ a.r i ab~e _ ~ lineal es po ~~ _ han d ' apar el.~e:- e¿~ no tenen cap c __ ~ Secció RHS : Decl ara e:S --==-=. neals). Poder: a...~-"'::: 2 ~.:::-.:.: RHS ---- - Secció RA..\"Gi:S S'us a per ée=-== d'aq u esta seccio é;, 123455- :: : :_ RA!i:;~ on els p un s i_é: a·-=~ _ al co nju nt de ra:::.;0 . paquet , \HNOS - ~ea. de la funció i a co::;i:luació les - ~ c;:. co:istricció i vv _...., :._.-,,..:.:e ~~ '.es variab les dins ..::E. es !a pos ició dels _ .-.,.:o : ::m me ric indicat e :;;.an de declarar les ' ~:~ q:..ie afecten a una :2e e:i q ue es declar in >=.~,; ~ ·;ector X de les _•: L ~ '. co ntinua nt fins '.: eleme nts no nul s , ,.,. 1 ::ü:I! de la constricció ~ re '.a mat riu de cons- . ó lineal i el valor 2 lntroducció al paquet Minos El format d'escriptura d'aquesta secció és: 1234ss1a9~1234ss1a901234ss1a9n1234ss1a9~1234ss1a9~1234ss1a9í1 COLUMNS .. .. variable .. constru 1 . . coeficientu1 . . . c onstru2 .. coeficientu2 23 on els punts indiquen espais en blanc, variable és el nom de la variable que estem tractant, constru 1 i constru2 són noms de constriccions on intervé la variable en qüestió, i coeficient u1 i coeficientu2 indiquen els valors amb que la variable que tractem afecta a cada constricció (si la constricció és no lineal es pot posar qualsevol valor). Cal ten ir en compte que en aquest apartat han d 'a par eixer els nom s de totes les variables, lineals i no lineals, fins i tot si no te nen ca p coeficient assoc iat . Secció RHS : Declara els termes independents de totes les constr iccions (lineals i no lin ea ls ). Poden ai;ar en qu alsevol ordre. El format d' e scriptura és: 123456789d123456789d1234567a9cr1234s6 RHS .... nomuindp . . construi .. termeuindept on els punts indiqu en espais en blanc, nomuindp indi ca el nom que donem al co njunt de te rmes RHS, construi indica el nom de la constricció que tractem i termeuindept repres e nta el valor del terme indep e ndent. El nom nomuindp és arbitrari p er o ha de ser el m ate ix pe ra totes les components d'un mateix vector de t er mes ind epe nd ents, i només se rv e ix pera donar noma a que st v ect or. Secció RANGES: S'usa per definir constriccions del tipus l S f; S u. El format d'es c riptura d'aquesta secció és: 123456789d12345678961234s61a9cr123456 RANGES . . .. nomurang . . construi . . ter me uranges on els punts indiqu en espais en blanc, nomurang indi ca el nom qu e donem al con junt de rangs , constr ui indi ca el nom de la con str icció que tractem i 24 Dept.EIO / UPC / Optimització de models no linea!s amb el paquet MINOS termeuranges representa el valor del rang. El nom nomurang té la matei xa funció que el nom nomuindp . Si a l'apartat RHS s'ha definit F(x) ~u i volem tenir l ~ F( x) ~ u el valor del rang ha der ser rang = u -l. Secció BOUNDS: Declara les fites de les variables . El seu format és: 12345678901234567896123456789S123456 BOUNDS . zz.nomuboun . . variable . . termeubounds on els punts indiquen espais en blanc, nomuboun indica el nom que donem al conjunt de fites, variab l e indica el nom de la variable que tractem i termeubounds representa el valor de la fita. El nom nomuboun té la mateixa funció que als dos apartats anteriors. El camp zz ens indica el tipus ele fita i pot prenclre els valors: {LO zz = UP FR FX ~ :'.". variable lliure Existeix la possibilitat ele fixar clins d'aquest apartat el punt inicial a partir del qual Minos com em ;ara la cerca del punt ini cia l factible. Per defecte Minos inicialitza l es va riab l es a zero o a la fita més propera a zero, la qua! cosa pot provocar problemes en certes constri cc ions no lineals . Per fixar el valor inicial cl ' una variable cal incloure a l 'apa rtat BOUNDS la següent línia: 2.8 12345678901234567896123456789~123456 .FX.INITIALu . . variable .. valori~i ci al Exemple de codificació d'un problema en format MPS Sigui el problema: 2 Introdu c ció a. El fitxer ~ . _ .::: ::..; jacobia seria: 123456789 ¿123~=~-~ NAME ROWS E CONS N L: E CONS N0:.2 G CONSN 3 L CONSL -111 COLUMNS Xl RHS X2 X3 TERM !b' DE TERM!li'" ) =: TERMH T E TERMili :" BOUNDS - LO LIMSIMP LO LIMSI M? UP TIMS MP ENDDATA I : i am b emm aga ·z ~ - NAME ROWS E COI/Sii E COllS/I :.2 G COl/Sli :_ 3