Optimització de Models No Lineals amb MINOS. Estimació d'estat d'una xarxa de transport d'energia electrica
Full text
EST APNL STICA APLICACIONS DE / LA PROGRAMACIO NO LINEAL (Estimació d'estat d'una xarxa de transport d'energia electrica) F. Javier Heredia UNIVERSITAT POLITECNICA DE CATA L UNYA Bibliote ca ll ll llllll ll lllllllllllllllllllllllllllllllll ll lll l ll llll ll l 1400210506 IAIH.STI<
Optimització de Models No Lineals amb MINOS Estimació d'estat d'una xarxa de transport d'energia electrica F. Ja vier He redia Cervera Depart an 1e nt d' Estadí s tica i In ves ti gació Opera t iva Secció d'Inforn1atica UPC
Índex Índex 1 Estimació d'estat d'una xarxa de transport d'energia electrica. l. l. Pr ese nta ció del prob le ma . . . . . . . . . . . . . . . . . . . . . . . . ... .. . .. . 1 1.1. Equac i ons el ect riques de la tra nsmi ss ió d' energia . . . . . . . . . . . . . . . . . 1.2. Form ula ció del pro blem a. l.2.l. Variables ..... 1 3 3 4 G 6 1.2.1 l. Variables d' estat i variab l es dependents. . . . . . .. . . . . .. . . . . . . .. 6 1.2.2. Fun ció object iu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3. 1.4. 1.5. 1.6. l. 7 1.2 .3. Co nstriccions. 1. 2.:3 . 1. Con s tri ccio ns d'in jecc ió de potencia nul·l a. 1.2.3.2. Constr iccions de mesura de tensió. 1. 2.3.3. Angl es de fa se . ....... . 1.2.4. Formulació final. Dades necess aries per a l'execució del problema. Codifi cació del problema. Comprova ció de les rutines d'usuari FUNOBJ i FUN CON Sol u ció obt i ng ud a en e xe c utar el prob le ma. Info r me de la pr ácti ca. . . ... 2 Introducció al paquet Minos. 2. l. Da des g en e ra ls. 2.2. Prob le ma es tandard. 2 3 '.\l e tod e de tr ebal l de \lin os . . .. . . . . ... . 2.4. Rutin es i fitxers d'us uari 2.''i . Le ctura i escr ipt . ura de dad es a les rutin es FFSODJ i FU N' CON. 2.G. Ap a rt at. SPECS . 2 .7 . . -'lp ana t. :..rrs . 2.8. Ex e mp le de cod ifi cació cl\rn proble ma en formal l\IPS 2.0. \ l untatge i ex•'cucio. í í 7 7 7 7 8 g 10 12 lFi . . . . . . . 17 17 18 18 19 20 21 24 25
1 Estimació d'e stitl dºuna xorxa. de rransport d'energia electrica 3 1 Estimació d'estat d'una xarxa de transport d'energia electrica. 1.1 Presentació del problema El problema que es vol resoldre intenta determinar el valor d' un conjunt de variables anomenades d'est.at i representades pe! vector x. Aquestes variables caracteritzen la situació en que es troba una xarxa el e transport d'energ ia electrica com la representada a la figura Fig. 1.1. 12 b¡ b2 b4 ~ 1 !./ /5 /4 Is Is -/9 ....__ bs b7 Figura 1.1 : Represem a ció el 'una xarxa ele tran sport el 'energia elec tri ca. La xarxa re pr ese nt ada té set nusos o barres indi ca ts amb b; , i deu línies, indicades amb /;. La det.ermin ac ió de les rnr i ab les d'e stat x es fa a pa rtir d' un conjunt de mesur es cl ' un es a ltr es q riables : de h xarxa eléctrica. Les variables z es pod en express ar anal ít i cam e nt, a través de ks lleis cl'O hm co ma funció el e les variables cl 'estat x: :¡ (X) z2 ( x) : 3(x) :p(x) z E ~(P X E ~n Les component.s del , ·ec t. or : poden ser ele dos tipus dif erents: (11) • com pone nts associades a mesures normals, que estan af ect ades per un e rr or considerable
4 Dept.EIO / U PC / Optimització de models no lineals amb el paquet MINOS degut a l es imprecisions deis aparells de mesura . Es cons iderara que es tenen en t.ot.al s compon en ts d ·aquest ti pus , i que es traben agrupades al comen~ament del vector =. Aquestes .> component .s formaran el vector . e n-· r . er r 1 • J .. err = '" º = ·2: _e rr ., s<p (12) • components associad es a "pseudo-mesures" , qu e són mesures absolutam ent e xactes. Ano - me narem :'" al vector de pse ud o-mesu res, que ocuparan les p - s darrer es compone nt s del vector z: (U) Degut a ! 'error en les mesures z'rr no resulta possib le d'est im ar el valor de les n variables d'e sta t. si hom no disposa d'un nombre redundant de mesures. Així cal efectuar un n ombre de m es ur es de les ,·ari ab l es z''"r > n - p, pr e nent -se, en general, 2(n -p). Dºaqu est.a forma l'estirnació d'estat. efect ua un filtratge estadístic deis errors de les mesures per a determinar el valor "m és probabl e ·· de les rnriables d'estat x. H om plant e jara el problema de la s egüent forma: min .rE:Rn L[ z~rr -:;(x)]2 i=l subj a: =1 (x) =zj" =Z" . - fk:::: fi.(xJ:::: =Z ". + fk j=l, .. . ,p kEK ( l .4a) (l.4b) (14c) ele forma qu e l"o p tim del problema x· correspongui a un est.at. qu e, tot respectan!. els valors de l es pseudo-m es ur es e xact .es z":, miuimitzi la suma deis quad r ats de les diferencies (error qu a dráti c mig) de les mesures amb error , i que pera un cert subconjunt K d'aqu estes m esures l' est.at .r · sigui tal que el ,·alor calcul at :¡.(x) corresponent a la mesura zf"'" estigui dins dºun mar ge ±q. prefixat del valor mes urat .. En el problema el ect ric que con siderem les mesures amb e rr or dºaqu es t. con.iunt A." no s·acos tum en a inclo ur e en la func ió obj ect.iu. 1.1.1 Eq11acions el ec triqu es de la trausmissió d 'energ ia. El transpon d·energia eléctrica es fa primordialment amb co rren! altcrn i a alta tensió. Les ,·ariables qu <" carnner itz en el corren t. a ltern poden repr esentar-se en el pla compl e x. tant . a ni\·ell de tensi ons i corre nts. coma 1ii\· e ll d ·impedancies i po téncies. li>rn " ' "" ,, ' " "" ": • dG 0 rx· · •_ ' ,,' ' ' , ;,;• "" '' wmp°""'" t; = e; +.if; e; s ent e; i _: , ""' L a . :::::: :.-:-:.~ 1'k / i UJlG ::~:- 3 una pa :- i : :-.::....... _ l"::c; - ' mod e:'::é~:;. - f ig. ~ :=
r"''<-"e ' .\/J.NOS ·-:e::~:: en tot.al - ~· 'ecto r : ( 12 ) ~;;::; . .\no- " ...:::-::-:;·:::~c:; .o del : :3) -""e c. \c.;:abLº . ::..: • ..::::. r::·:nJ re _ . i.:::-::~:~ ~: : :r:a c. .:.::=:.~:: Li:: =...: ;. 1 Estimació d ' estat d'una xarxa de transport d ' energía eJ ectdca 5 sent e; i f; les components real i imaginaria de la tensió i j la unitat imaginariaj = .J=T. La impedancia d 'una línia electrica entre el nus k i el nus 1 tindra així una resistencia (real) rkl i una reactancia (imaginaria) Xk/· La potencia electrica Sk/ que transporta una línia tindra una part real Pkl (potencia activa), i una part imaginaria Qk1 (potencia reactiva): "' lz '" = '" : j'" "' )7 '" = p., ~ "" ~/ ~/ U na línia qualsevol d ' una xarxa electrica com la representada a la figura Fig. 1.1 pot ser modelitzada per un circuit en forma de lletra " II " tal com mostra el diagrama de la figura Fig. 1.2. nus k (ek,fk) (pkl, qkl) 1'k/ Xkf nus 1 ,-,,.1,llW,. e • (e1,f1) (Plk , q¡¡.) bkl/2! lbk1/2 -- -- (terra) - Figura 1.2 : Esquema electric d'una linea (k, /)de la xarxa electrica. rk1 i Xkf són Ja resistencia i la reactancia. bk1 és la susceptancia a terra (recíproc de la reactancia). (q, Jk) i (e¡, f1) són les tensions, real i imaginaria, als dos extrems de la línia (barres). (pkl , Qk1) i (P1k, q1k) són les components real i imaginaria de la potencia als dos extrems de la línia. Cada línia d ' una xarxa electrica té unes característiques de resistencia, reactancia i susceptancia a terra diferents, segons la longitud, tipus i disposició espacial deis concluctors que les formen. Aquestes característiques seran una dacia del problema a resolclre. El flux de potencia activa Pkl i reactiva Q kf, eles ele la barra "k" a la barra'·] ", val, en funció ele l es components ele les tensions, i deis parametres ele la línia que uneix les barres: . . [ (e¡.+jfk)-(e1+jf1) . bu] p¡.¡-J1k1=(ek-Jfk) . . +( e k+Jfi.)J- 1·k1 + JXkf 2 igualant les part s rea ls i imaginitria ele (J.:)), hom pot clecluir les següents expression s: 1 p¡.¡=-[ e ¡. 2 1 qu=2[ek e¡ e¡ f¡. f¡. 2c ¡,¡ [~: o -c s o !1 J ¡(y ) o s 2c -c -s o -c o ~si ¡ :: l -c f¡. o f¡ c l [ ek l (2s-b) ~s ~: - c o -s ( 1.5) ( 1.60) (l.Gb )
6 Depr .E/O / UPC / Optimització de mode/s no /inea/s amb el paquet MINOS on e= ~ és l'anomenada conductizncia, s = ~ és la susceptancia. S'ha de fer 1'k1 + x¡:¡ rkl + x¡;, notar que els valors de potencies actives i reactives calculats (i mesurats) als extrems oposats de la linia (k, /) seran, en general. diferents. 1.2 Formulació del problema. 1.2.1 Variab les . 1.2.1.1 Variables d'estat i variables dependents. Com a variables d'estat x es prenen les components reals i imaginaries de les tensions als nusos de la xarxa (també anomenats "barres ", degut a la forma de la seva estructura). Així dones, si es treballa en una xarxa de .\o barres, les variables d ' estat són: e;} i = 1,. . ., !Vb f; (1.7) Coma variables dependents :;(x) associades a mesures amb error :err es consideraran dos magnituds físiques diferents: 1.- La primera consisteix en els Yalors de potencia activa Pkl i reactiva qkl mesurats sobre certs punts de la xarxa. S'indicara amb ¡ \¡( i amb PZÍr i qÍcír el conjunt de parells ordenats (k , /) on s' han realitzat. l es mesures de potencia i els seus valors numérics respectivament. Pkl} (k,I) E M qkl ( 1.8) 2. - La segona magnitud física considerada coma variable dependent sera la magnitud de tensió l.; = J ef + Jl per a un cert conjunt de barres JC , indicant-se amb t¡rr el valor mesurat .. t; i E JC ( 1.9) Comja s'ha vist anteriorment, les equacions (1.6a) i (l.6b) contenen l'expressió de les variables p¡.¡ i qkl en funció de les variables d' estat e; i f;. Donat que les mesures amb aparells estan afectades d'error. aquestes variables corresponen, com ja s' ha dit. a les components :er" de l'expressió (l. 2) . Com a variables dependents :; ( i·) associades a le s pseudo-mesures es consideraran les injeccions de pot.éncia activa P; i reactiYa Q; en les barres i d'un cert subconjunt. de barres :1 /: P; =_ LjEC, p;j } iEJV Q; - LiEc. qu (JJO) on C; representa el co njunt de barres connectades a la barra i. El conjunt ;V esta formal. per les barres on no bi ha ni consum ni generació d 'elect.ricitat., de forma que es pot. assegurar que P; = Q; = O exactament. Per aquesta raó el vect. or de pseudo-mesures : 'x de ( 1.3) és. en aquest. cas, :" = [O J. 1 E sl ima - .:. ~ 1.2.2 [s·a:=. :: a cliY a : ::;=.:: de te n ~ .: ;..: - :.;: i. 2.3 e i. 2 .3 . ~ e 5: .. "-;; : - i e_...._ •. -:: -::-::. a -· __ 2.J .:: e 1.2 .3 . - 1.2 ...
;:.o.:;-_:.: . \II.'1 05 3 :.a de fer ~~:::..s c;m sat s ""' ~~-::::.s als -- - ~ Així :.1) ~::~:~a...::i ¿ _ .. ;: ~=·= ::: ..:~:-t 3 :.:-=--=-::.::.:s e ' ~---;..- . - - ~ 1 Estimació d 'e stat d 'una xarxa de t.ransport d 'energia eJectrica 7 1.2.2 Funció objectiu. Estará formada per la suma al quadrat deis residus de les mesures deis valor de poténcia activa i reactiva a les barres del conjunt M. No es consideran els residus deguts a les mesures de tensió sobre les barres K: · ' ( err )2 ' ( ,,., )2 111111 ¿ Pk1 -Pk1 + ¿ q¡.¡ -qk1 e,,f,,t=I, .. ,Nb (k , l)EM ( k,l)E , "1 (1.11) 1.2 .3 Constriccions. 1.2.3.1 Constriccions d' injecció de potencia nul·la. Són les obtingudes igualant les expression (1.10) a zero: P¡ = LjEC, Pij =o} i E .V Q¡ = LjEC, q¡j =o (1.12) i equivalen a les constriccions (1.4b) 1.2.3.2 Constriccions de mesura de tensió. Són les equivalents a les constriccions ( l.4c) de la formulació general. Confinen el valor de la tensió t¡ di ns d 'un interval centrat sobre el valor mesurat tj" i de radi é¡ > O: (tf"' - E;) 2 :::; el + Jl:::; (tf"' + E) 2 i E K (1.13) 1.2.3.3 Augles de fase Donat que els angles fl de fase de les tensions (i per extensió llurs parts imagináries) són rel at.i us ent re barres, podem prendre l 'a ngle de fase d' una de l es barres i coma zero: pera una barre 1 donada , que anomenarem barra de referencia s'imposará: f¡ =o 1.2.4 Formulació final. L'expressió final del problema d' optimització a resoldre és: 111111 e ,.}, ' en )º ' UT )º L (p¡.¡ - Pkl -+ L ('Ju -q k1 - •=-!. .. . .'\J, ¡ k .l)E.1 \.-1 ( k ,l IE."1 Subj.a · P¡ = LjEC, Pij : o} i E A' Q; = LjEC, q,J -o (/f"' -f;)2 :::; el+ J/ :::; (l f" + !f f¡ =o (l.14) ( l.11) (l.12) i E K (1.13) ( 1.14)
8 Dept.E/O / U PC / Optimització de models no lineals amb el paquet MINOS 1.3 Dades necessaries per a l'execució del problema. El probl e ma d'estimació d' estat es plantajera sobre una xarxa com la de la figura Fig. 1.1 amb 10 línies i 7 barres. Les dades associades a cada alumne es poden generar amb el programa eexegprob. Aquest programa només necessit.a el número d ºidentificació num , diferent per a cada alumne , i creara, en el directori on s'executi, un fit.xer anomenat eexenum.dat similar al que mostra la figura Fig. 1.3. Els valors de les característiques de les línies es donen en unes unitat.s especials anomenades tant per u (p.u.). Aquestes unitats són el resultat de dividir el valor en Ohmns (11) , o en Ohms- 1, de les impedanci es, o admitáncies , per una imp eda ncia base Z 8 o a dmitancia base }e. Z B i Y8 es defineixen en fnnció d 'u na tensió base TB i d 'una potencia base PB segons l'expressió: ZB=TJ/PB }e= l /ZB Es molt. recome nable , per raó del bon escalat que en resulta. dºefectuar t.ots els cálculs eléctrics en tant per u. Caldra , dones, convertir les mesures de poténcia p'rr i q'rr i de tensió t' rr i € a p.u. 1.4 Codificació del problema. Per tal de resoldre el problema pla.ntejat amb Minos. s·hauran de codificar les rutines d'usuari FUNOB.J i FUNCON, i s'haura de crear un fitxer eexe.dat que contingui els apartats SPECS i MPS , cl 'acord amb les especificacions del manual ele Minos. Els apartats SPECS i MPS del fitxer e ex e. dat corresponent a les da.des de la figura Fig. 1.3 es mostra a les figures Fig . 1.4 i Fig. 1.5 respect.ivarnent. Ca l destacar dos aspectes de l 'ap artat . MPS : J.- Observant la figura Fig. 1.5 es pot comprovar que tant els ,·a!ors deis terme s incl epe nde nt. s corn el se u r ang de variació com els valors ini cia. Is de les vari ab les estan expressats en p.u. ,j El grup ele valors cleclarats com a FX INITIAL a l' apartat BOUNDS indica a Minos que comenci el procés d 'op timitz ació a partir de la solució e; = 1, J, =O. , i = 1, ... , lvv . El nom i ordr e de les variables és import a nt en el pac¡uet !\linos. L ºordre en que !\linos considera les variables és el mateix amb el que apareixen declarades a l° apartat COLUMNS cl ins de l°:\IPS. i l° ord re de les constriccions és l°indicat. a J' apa rtat R Ql.IS del mateix fitxer. Així dones , l'ordr e de les variables dins el v ec tor X (N) a les s ubrutin es FF.\"OB.J i FUNCON ha de ser el m ate ix inclicat. a COLUMNS, i l 'o rdr e de les constriccions no li n ea ls dins del vector F (N) a la s11brutina FU 1\"CO.I\' ha ele coincidir amb l"incli cat. a l"apartat RDWS. Lºordre i nom suggerit. per a l es Yariables del problema r ep resenta t. la figura Fig. 1. 3, amb una xarxa amb se t. barres. seria: e; j,J'=[E1 F1 E2 F2 E7 F7 ]' ( l.l5) Pe! qu e fa referencia a les con st ri cc ions, es proposa declarar primer les co nst riccions el 'injecció nul ·la ( 1.12) i cl es pr és les de mes ur a de tensió ( 1. 13) En el cas de les el acles represe nt ades a Fig. 1. :3. arnb N = {l. :3 . 6} i K = { 6. 2} l" ordre i n om su ggerits serien: F( A) = [P1 t~ ,, tn' = [P1 Q1 P3 Q3 P6 Q6 TS 6 TS2 J' ( l.16) El nom suggerit. no t. é cap mena d' imp o rt anci a, pero si que és aconse ll ab le de respect. ar ]'orclre 1 Es r im a c,ó d es:.a_ =-- - :..: ~~ = ~ - :. .: .. ~ = .. .!. =~ =~ sug gent ~..:. :- ~ Lº ex em~.~ _·: .?:'. 1.5 : =--== - La comv : ·"-=: ~
.::~~« .\l/SOS ::=u=..:::::l elO Ew ':s" =. :.:;:;.!lexió de : ;;.:-_ !a milla r :.:c,.,,-:...-:n a pa rtir ~c:np rove u =-- ;:;ou punt. --' · - ...... / 2 lntrodu cció al paquet ;\!inos 15 Verificatio n of con straint gradie n ts returned by subroutine FUNCON. The Jac obian seems to be OK . XXX The largest díscrepancy was 1. 18E- 07 in const ra 1 nt Co l umn X (J) DX(J) El ement n o. Row J ac o bian v al ue Diff erence approxn 1 1 . OOO OOOOO E+ OO 4. 77E - 07 1 1 2.13600858E +Ol 2. 13600960E +O 1 2 2 1 . 70 593840E + 02 1. 70593921 E+02 2 O OOOOO OOOE+ OO 2 . 38E-07 9 1 1 . 70 660940E + 02 1. 70660945E + 02 10 2 - 2 . 13600858E+OI - 2 . 13 600452E + OI . OOOOOOOO E+OO 4. 7 7E-07 17 1 - l .36781895E + Ol -1. 36781895E +Ol 18 2 -1 . 10668988E + 02 - 1 . 10668988E+02 19 3 -3 . 598086 17E+OO - 3. 59808617E + OO 20 4 - 2 . 15233616E+O l -2 . 1 5233616E +Ol 23 7 2 . OO OOOOOOE+OO 2. 000000 48E+OO 4 O. OOOO OOOOE +OO 2. 38 E -07 25 1 -l .10668 9 88E + 02 - 1 . 10 6 68988E + 02 26 2 1 . 36781895E+Ol 1. 3678189 5E+Ol 27 3 - 2 .1 52336 16E+Ol -2 .152 33616E +Ol 28 4 3. 59808617E+OO 3 . 5980 8617E+OO 31 7 O. OO OOOOOOE + OO 2. 38418579E - 07 . O OOO OOOOE + OO 4 77E - 07 35 3 2 .1 8944756 E+ Ol 2 .189 44 860 E+Ol 36 4 1 . 33 439823E+02 1. 334 39887 E+ 02 O OOO O OOOO E+OO 2 38E -07 43 3 1 . 3401 4023E+02 1. 34014028 E+ 02 44 4 -2 . 18944 756E+ Ol - 2 .18944437 E+OI OOOOOOOO E+OO 4 77E - 07 51 3 -7 .68 189 633E + OO -7 . 68189 6 33E +OO 52 4 -5 999 1952 3 E+Ol - 5 99919 5 23E+Ol O OOOO OOOOE+OO 2 . 38E -0 7 59 3 -5 99 91 9523 E+OI - 5.999195 23E+ Ol 60 4 7 68 1 8963 3 E+OO 7 . 68 1 89633E + OO 9 1 . OOOOO OOOE + OO 4 . 77E-07 65 1 -7 68 189633E+OO -7 . 68189633E + OO 66 2 - 5 999 1 952 3E+OI - 5.9 9919 523E + Ol 69 5 -8. 94 454383E+ OO - 8. 94454383E + OO 70 6 - 4 47227 191E+ OI -4 . 47227191E + Ol 10 O. OOOOO OOOE + OO 2 . 38E- 07 73 1 - 5 9 9919 523E+OI -5. 999 l 9 523E +O1 74 2 7 . 68 189633E+OO 7. 68 l 89633E +OO 77 5 -4 472 27191E + OI - 4 . 472 27 191E+OI 78 6 8 9 445 4 383E + OO 8 94454383E + OO 11 1 . OOOO OOOOE + OO 4. 77 E- 07 85 5 1. 8 4468063E + Ol l .84 46 8151E+Ol 86 6 9 . 1 21295 40E+Ol 9 . 12 129975 E+OI 88 8 2 OO OOOOOOE + OO 2 000000 48E+OO 12 O. OOOO OOOOE + OO 2. 38 E- 07 93 5 9 .13290540E+ Ol 9 . 1329 058 4E +OI 94 6 - l .8 446 8063E + Ol - 1. 8446 7 845E +Ol 96 8 O OOOOOOOO E+ OO 2 38418579E - 07 13 1. OOOOOOOO E+ OO 4 . 77E-07 99 3 - l . 06 144931E+Ol -1. 06 144 9 31E+OI 100 4 -5 2 4987090E+O I - 5 2498 70 90E +OI 1 01 5 - 9 50226 244E +OO - 9 50226 2 44E + OO 1 02 6 -4 660633 4 8E+OI - 4 66 0633 48E + OI 14 O. OOOOOOOO E+OO 2 . 38E - 07 10 7 3 -5 2 49 87 09 0E+OI - 5 2498 7 090E + Ol 1 08 4 1 . 06 144 93 1E+Ol 1. 061 449 31E+OI 109 5 - 4 66 0 633 4 8E + Ol -4 660633 48 E+OI 110 6 9. 5 0226244E+OO 9 5022624 4E+ OO 112 Jacobian eleme nts in cols 1 thru 14 seem t o be OK. XXX The larges t r el at i ve erro r was 1. 82E -0 6 in r ow 2, co lumn Fi gura 1.8 : Comprovació del J a cobia a mb VER IF Y pe! prob lema d ºest.rnació dºest.at. La comprov ac ió s'e fect. ua so bre el prim er pun t. consider at per Min os. OK OK OK OK OK OK OK OK OK OK OK OK OK OK OK OK OK OK OK OK OK o;; OK OK OK OK OK OK Qll or. OK OK OK OK OK OK º" º" o;: OK DK OY. o; : º'
16 Dept .El O/ UPC / Optimiizació de models no /inea/s amb el paquet MINO S EXIT -- OPTIMAL SOLUTION FOUND N'"'' 3ASIS FILE saved on flle 11 Itn 35 No. of iter a tions 35 Objective value .1038919728E-03 OOOOOOOOOOE+OO .1038919728E-03 No. of maj or i t erat ions Penalty parameter No. of calls to FUNOBJ No. of su perb asics No. of bas ic nonlinears No. of degen erate steps Norm of X Norm of X (un scaled) Const raint vi olatio n NAME: EEXE num o 000000 83 1. 949E+OO 1. 949E+OO 2 . 087E-15 Status OPTIMAL SOLN OBECTIVE RHS RANGES BOUNDS FUNOBJ RHS R ANG FITE S S EC TION 1 - RO: - :s (MIN) Linear objective Nonlinear objective No. of calls to FUNCON Norm of reduce d gradient Norm RG / Norm PI Percentage Norm of PI Norm of PI (unsc aled) No rma lized 83 5.020E-0 9 5. 020E-09 o. 00 l.OOOE+ OO l.OOOE+OO 7 . 076E-16 Objective value .1038919728E-03 It erat ion 35 Superbasics NUMBE:R ... ROW . . STA TE ... ACTIVITY .. . SLACK ACTIVITY . . LOWER LIMIT . .. UPPER LIMIT . . DUAL ACTIVITY .. I 15 p 1 16 QI 17 P3 18 Q3 19 P6 20 Q6 21 TS5 22 TS2 EQ EQ EQ EQ EQ EQ SBS SBS SECTION 2 - COLUMNS o. 00 000 00 000 00000 00000 o 00000 o 00000 1. 02675 l. 01631 o. 00000 o. 00000 o. 00000 o. 00000 o 00000 o. 00000 -o. 0 2290 -o. 01131 000 00 00000 00000 00000 o. 00000 o. 00000 . 00385 . 00500 00000 00000 00000 00000 0 .0 0000 0.00000 1. 06593 1.06715 -o 0025 0 -o 003 65 -o 00828 -o 0044 5 -o 00365 -o 0 2202 0000 0 o. 00000 2 3 4 5 6 lilJM 3 E: 'l . COLU)IN STA TE ... A CTIVITY ... . OB J GRADIEl/T . . LO WER L! MIT ... UPP ER LIMIT RED U CED GRADN T M+ J El Fl E2 F2 E3 E4 F4 ES : O FS 1 1 E5 :2 f 6 !3 E7 14 F7 BS BS BS BS BS SBS SBS SBS BS BS BS A EQ SBS SBS FU!Ko:: called wi th llSTATE FU!l G3J c all ed with N ST AT E .0 1251 00515 1.01 328 o 00422 . 00951 -o 00 4 67 . 00777 -o 00 545 .0 1 053 0 0693 .0 08 12 00000 1. 00 4 58 -o 0 0639 -o 68309 -o 3570 4 570 25 39 546 -o 78924 "1.01632 o. 33621 o . 46564 . 26631 09068 - 2 09398 0 .074 11 1. 39625 0.350 15 NONE NDNE NO NE NON E NOllE NONE l/ONE liOliE NON E NON E NOl/E 00000 NONE NOl/E NONE ll ONE NONE NOllE NONE NONE NO NE N ONE NONE NONE N ONE o 00000 NONE NO NE Figura 1.9 : Jnform ac ió a l' o ptim del probl ema d'estimac ió d'e stat. La so lució represent ada corres po n a J' opt im del pr oblema de la fi gura Fi g. 1.3. o 00000 9 000 00 10 00000 11 00 000 12 00000 13 0 000 0 14 0000 0 15 o 00000 16 o 00000 17 00000 18 o 00000 19 o 000 00 20 o 0000 0 21 o 00000 22 2 ln c r od~:c: J:... = 2 In ro [ 1: "-~-""'· se t oi s e..s :::-- p roble~;:;; :;...::: sig ui a :: :._~ ha, ·e: : : ~-:;.,,.:;,.· - 2.1 Da - 2.2 P: __
,=;,.;:;-<' .\11.\"0 S -:.~.::-::: : .. :,.::-:.: :·:; !..- :: :::.;:.:. - :·: =-~~ - :-= ::=- .! . ::":~' ::: !' . I : :::2.SJ ::-2f :i .: :- s2s - -, .:..:. s -: -: ::;~s = ~ =-=- 1.2: : :::..: =·~. !. ~ :;-:- M+J - - ~)OCO = CJOCO 10 coooo 11 . JOCO) 12 . 0000·) 13 "ºººº 14 , . 00000 15 00000 16 0000 17 00000 18 . 00000 19 J 0000 0 20 . 00000 21 "::E ~ 00000 22 2 Inrroduc ció al pa quet lvlinos 17 2 Introducció al paquet Minos. En aqu est capíto l cl esc riur em el paquet Minos cl ' optimit zació, amb el qu a! pod en solucinarse tots els problemes ant erio rment plante jats. Val a cli r que, per la pe t.i ta miela cl 'aque st s p ro blemes, alt re s paqu ets més "' amicables" poclrien ser u sa t .s . Tanmateix , el fet el e qu e Minos sigui ac tu a lm e nt un deis millors pa qu ets comercials (p e rno dir el millor), fa qu e sigui convenie nt haver tre ballat a mb ell i coneixer-lo mínim ament. 2.1 Dades generals. ;..¡in os és un sistema inforrnatic esc ri t en Fo rtran dissenyat per resol el re p ro bleme s el ' op timit zació el e gra ns elimensions (problemes li nea ls i no lineals, tant p e] que fa a la funció o bj ectiu com a les cons tr i cc ions). El nom és un acrónim i signifi ca M od ular In -core Nonlin e ar O pt imization Sy ste m. Els se us a utor s són Bru ce A. ;..J u rta gh i Michel A. Sa und ers (Sy ste ms Optimization Labor ato ry, Departme nt of Op era tions Re sea rch, St. anforel lin iversity, Ca lifo rnia) . 2.2 Problema estandard. on: El pr ohlema e stá nel a rel amb que l\linos treba lla té l'expressió: • i · ect, ors cons t. an t. s: cE ITT ." ' d E lR o: m rn . F (x) +c' x + d'y subj . 11 S f (x ) + A ¡y S U¡ / '.! S A '.!x + A3 y S v '.! 1s (:) sv 11 1. / 1 E lR "'' : u; / '.! E IR ~' /, u E IR"' +n , • .\Jatri11s constan t.s : A1 E (m 1 x n '.! ) A'.!E ( m'.!x n1) A:i E ( m'.! x n" ) • i'aria bl es i foncions: F (x ): fu nc ió escalar el e ,· ar iable \ ecto ria l. ( 2 .1)
18 Dept.E/O / UPC / Optimització de mode/s no Jinea/s amb el paquet MINOS 2.3 f(x): funció vectorial de variable vectorial. J(x ) = {f(x)¡}, i = 1 ... m1. x E IR» ': variabl es no lineals. y E IR'": variables lin ea ls. 11 ::::'. f( :r) + A1y ::::'. u1: constricc i ons no lin ea ls. /2 ::::'. .chr + A3y ::::'. 112: constriccions lineals. Metode de treball de Minos. Pe ra re sold re un problema amb constriccions d'igual tat no lineals Minos efectua una serie d'iteracions majors (MAJOR ITERATIONS). Dins de cada iteració major es resol un subproblema amb constr iccions lin ea ls ( :'1110\0R ITERATIO NS). Aquest subproblema esta format per les const riccions l in ea ls i fites del problema original i per una lin ea lització de les cons triccions no lineals. Aquest procés de linealització consisteix en substituir la funció vectorial f(x) de (1) per una aproximació de primer ordre f(x) fent servir el jacobia de les constriccions no lineals en el punt :r¡. (denotar em el jacobia amb h): on: El s ubproblema resolt a cada it e ra ció maj or k és: mm. F(x) + c'x + d'y- ,\L(f- Ík) + ~p(f - Íd(J- Ík) subj. j¡. + A1y = b1 A2x + .43y = b2 1 ~ (:)~11 • La funció o bjectiu de (2) s·anomena Lagrangia augmentat .. (2.2) • ,\¡. és un a est imació al punt :r¡. deis multiplicadors de Lagrange de les cons tri ccions no line als. • ~p(f - j¡. ) '(f - j¡.) és el que es coneix coma fonció de penalit zació quadraticn. amb param et re de penalització p. 2.4 Rutines i fitxers d 'usuari. La informa ció que '\lin os necessi ta per a reso ldre el pr ob l ema se li ha de subm inist rar mitjan~ant du es rutines i dos fitxers amb informació (dos fitxers qu e es poden co 11\' eriir en un que contingui la inforrnació deis dos a nt. eriors): rutina fliNOB.J } juntes en un sol fit xe r EXE . MPLE . FOR o EXE!v!PLE.C: rutina fl'NCOI'í fitxcr SPECS } junts. i en aquest ordre , en un sol fitxer EXEJ\IPLE.DAT fit.x er !\ IPS 2 l ntr od~=-;_~ _.!.,., : del clus:<o : =~ :;. i EX D lP :::..::: ::. a mb \ !;:::~ ;;,:e varia bl~ :::... - o can\" ia :-- .: Minos e:;;- :::;.:: en For;:;o:. .' - Els ;"-=":-~ F CS Q3; F u:.:.: :::: Pe.:: ~~-.--: FCS CO.\. Fu ::::- . ::: P a : ~--:-~ ~
~ · " ~ = ~ " .\ !/ SOS ~ ::-:; .• - ~ i;ca se ne :-3: ·~ !!L subpro- .:;. =:;;a '. :: : !":1a ¡ per : ::::;; :ciccions :: éie l ) per : : 1.. :::=< t ls en el f '.! . '.!) ~~:.:~ . :: . ;n o __ · ;,;i:?.. arnh ~ -::~::~. ;:1.;;:t r a. r _ . .... ~-=-=· .:.:- -: n un !: ( 2 Introducció al paquet Minos 19 Hi ha unes plantilles d'aquest.s fitxers al directori: DIR EIO:[ONLC] del cluster de la Fa c ultat d'Informatica de Barcelona. Els fitxers s'anomenen EXEMPLE.DAT i EXEMPLE.FC. Al fitxer EXEMPLE.FC hi ha un possible main de programes per treballar amb Minos, així com la cap~alera de les rutin es FUNOBJ i FUNCON amb la de cl aració de variables. El main és recomanable que estiguí esc rít en Fortran (es pot mant enír el que hí ha o canvíar-lo). Aixo perm et poder gestionar els fitxers d'e ntrada i sortida de dades, donat que Minos es ta escrit en Fortran. Les funcions FUNOBJ i FUNCON poden ser codificades en C o en Fortran. Al fitxer EXEMPLE.FC hi ha la declaració de variables pels dos llenguatges. Els parametr es partículars de cada rutina són: FUNOBJ. Funció : Codifica la funció objectiu í el seu gradient. Parametres: FUNCON: Entrada: Sortida: N: nombre de variables no lineals X: vector de dimensíó N que conté el valor de les variables a ca da passa. L'ordre en que estan emmagatzemades les variables ha de coincidir amb el declara! a l' apartat COLUlV!NS d el fitxer MPS. F: valor de la funcíó obj ectiu corresponent a la X actual. G: vector de dim ensié Nper emmagatzemarel gradie nt de F (ésa dír G(i) = BF) ax, -. Funció: Co difica les constríccíons no lineals i els seus gradie nts (jacobía). Paramet .res: Entrada: N: n ombre de variables no lineals. 1VI: nombre de co nstr iccíons no lineals (només s' usa sí el ja cobia es codifica de forma den sa ). NJA.C: nombr e d'elements no nuls del jacobia (només s'usa si el ja co bía es codifica de forma esparsa). Son.ida: X: vector de dimensió N que conté el valor de les variables no lineals a cada it.eració. F: vector de dimensíó !vl la component i del qua! correspon al valor el e la constricció no lineal núm ero i pels rnlors de les variables no linea Is de la iteració actua l (e mmagatz emades a X) . G: si el ja cobiá act ual s' emmaga tzema dens. és la matriu (:\1 x 1 \' ) que correspon al jacob iá de F. Si el ja cobia s' e mm agat zema es par s, és el vec tor de dim ensió NJAC que conté els eleme nt s no nuls d el jacobia en el mateix ordre que l'indic at a l' aparta t COLUMNS del fi tx er l\.IPS.
20 Depl .. EJO / tPC / Op1imització de models no lineals amb el paquet MINOS 2.5 Lectura escriptura de dades a les rutines FUNOB.J FUNCON. <! > l\ ' linos té declarada un zona COMMON anomenada MlFILE amb les variables IREAD , IPRINT. ISUMM. Ens interessa el contingut de les dues primeres: IREAD: unitat logica de lectura assignada al fitxer d'entrada de dades (per exemple, EXEMPLE . DAT). IPRINT: unitat logica d'escriptura assignada al fitxer de sortida de resultats (per exemple, EXEMPLE .LIS) És a dir, sí des de les rutin es FUNOB.J i FUN C ON s' acc ede ix a la zona C OMMON MlFILE af e gínt al codi: COMl\!ON / l\llFILE/ IREAD,IPRINT,ISUMM aleshores es poden llegir dades afegides del fitxer d'entrada .DAT i afegir informació al fitxer el e sortida .LIS. Aixo darrer pot ser útil, per exemple, per escriure a la darrera iterac ió el valor de les rn.riables a l' optim amb tot es les xifres significatives desit jades. 2.6 Apartat SPECS. L'apartat SPECS (o fitxer si esta separat de l'altre apartat anomenat l\1PS) defineix els diferents parame tres sobre el funcionament del paquet Minos i sobre les característ i ques del problema. El format d'entrada de dades és lliure, i l'aspecte ge neral de l'apartat SPECS és: BE G !i\ PARAUL ;L C LAlU [ PARA UL·LCLAU_2] [VALOR_NU MERIC] END De la prim era pa raula clau nornés són significatius els tres primers caráct er s: de la segona (si n'hi ha sego 11a) només són signifi ca tius els 4 primers c ar ác t.e rs . Vegem a conti nu ac ió una part del paramet es qu e p oden ser indi cat a l'apart at SPE CS. Pan\m ctres t¡11e depenen de les dades del pr oblem a: COLl.ll\INS k: amb k indique rn el no mbre so bree s tim at de column es de la matriu de constriccions (nombre sobre e stimat . de variabl es). ROWS k: amb ~ · denotem el nombr e so br ee stimat de fil es de la m at riu de constricions (nombre s obr ee stirnat de co nstr iccions lineals i no lineals). ELE MENTS k: k és el no mbr ee so br eestimat. d'elem en ts no nu ls a les rn atrius A1 . A ~. A3 i al j aco biá. NONLINEAR. C ONSTR . k : on k és el nom bre de cons tri cc ions no lin ea ls. NONLIN L\R VARIABL ES k : on l· és el nombr e de varia bles no lin ea ls. < 1 > El dit en a qu e st a partat, pe! qu e fa a les zones COMl'vlON, només té se ntit si les rntin es FUNOB.J i FUNC ON est.an programade s en Fortr an. 2.7 RH S _._ ... _ - -- RA! IG :: S BO · ~: .... s zz = .o =. E ND D .:. -:- .;
•' ,,,: _ :¿:; ce: .\ /l.\"05 · : T.-. -cos. ,- ~ '.READ, x=::::~=- E.\E:\1- ..:; ( ~= e exempl e, !G\ \!l flLE :..-;:;i;..:16 al fi t xer -~::6 el valor ::: ' c-=:--"e1x els ,,..,,-;:..;o:.::.:es del :i~ .::?::es és: ,._-;¡: ,:_.:- .~ 37_;ona ·...::_=.::ó una .;....;;;: :::.aa1 us --' . "' .~ :...:.t1ne:3 2 Inrrodu cc ió al paqu et .'!\:fino s 21 Parametres que no depenen de les dades del problema: JACOBIAN SPARSE: indica que el jacobia s'emmagatzemara de forma espa rs a, és a dir , només es guardaran els elements no nuls del jacobia. Es diu que una mat riu és esparsa si té una gran quantitat d'ele ments nuls. Si el jacobia és e spars resu lt a convenient tri ar a questa opc i ó. Si es volgués ernm a ga tzemar dens no ca l dria espec ifi ca r res, dona t qu e aquesta és l' opció per defecte. DER.IVAT IVE LEVEL k: contro la el calcul del gra di e nt de la funció o bj e cliu i de l j acobia de les constriccions: k =l: Minos calcula el jaco bia i el gradient s' ha de codificar a la FUN OB J. k =2: Minos ca lcula el gradient i el j aco bia s' ha de codificar a la FUNCON. k= 3: S' ha de codificar gra dient i ja co bia. Aquesta és l 'opció amb que ha ur eu de resol dr e el pr oble ma. VER.IFY: Provoca la comprova ció per d if erencies finites de to ts els elements del gradient i del ja cobia c alculats per les rutin es FUNOBJ i FUNCON. LOG FREQUENCY k: controla la fre qüen c ia a mb la que s'e scriu inforrnació al fitxcr de sortida. S' imprimir a u na línia d' inform ació per cada k it erac 1ons menors. 2.7 Apartat MPS. Especifica els no rn s de les con st ri cci ons i variables, indica co rn im e rv é cada \'ariable dins ca da const.ricció, i defineix els terme s in depe nd en ts de les con st ricci ons i els límits de les variables. Ac¡uest forrnat. no és propi de fllinos; és un formal es t. irndarcl d'especificació de prob lemes u sat ¡ wr div er sos paq ue ts d 'o ptirn il zac ió. El formal d" entr ada no és lliure i cada pa rau la clau ha d"estar e ntr e unes colu mnes deterrnin ades al fitxer. L "aspecte genera l de l'apa rl at MPS és: 12345 6789 0123456789b123456789~1234567890123456789~12 345 6789~123456 78 9b NAME n omu problema ROWS ww constricció CO LU MNS varia b le constru l coeficient ul cons tr u2 coeficient'-'2 RH S nomuindp cons tru u terme ui nd ependen t RANGES nomu rang construu valor udel u rang BOU!ID S zz nomuboun :;r_ariable valor udel u lírnit ENDD ATA
22 D ept.EIO / UPC / Optimització de model s no Jineals amb el paqu et f\JINOS Al MPS ant e rior en majúscula apareixen les paraule s clau i en minúscu la l es da des que varien d 'tm probl e ma a l'altr e (i subratllats hi ha el nombr e de c aract ers maxim qu e pot ocupar cada nom). Els camps qu e s'han marca t com 1111, nomuindp, nomurang, zz i nom ubo un indiqu en el t ipu s de co nstri cció (11w) , el nom donat al co njun t de term es ind epen dents ( nomuindp), el nom donat al conjunt de rangs (nomurang) , el tip us de límit de la variable ( zz ) i el nom donat al conjunt de límits (nomuboun). Descriurem a continuació cadascuna de les secc ions del MPS. Secció NA.ME: S'usa per donar un nom al problema que s'esta codificant. El format que hem d' utilitz ar és: 1234567890123456789612 NAME .......... problema on problema és el nom que donem al problema i els pun ts i ndique n espa is en bl anc. Secció ROWS. · Declara el nom i ti pus de les const riccions (i de la part lin ea l de la funció objectiu si n 'hi ha) . S'h an de posar primer les no lin ea ls i a cont in uac ió les lineals. El format que hem d'utilitzar és: 123456789012 ROWS .1111.constric on els punts indiquen espa is en blan c, constri c és el n om de la constricció i ww ens ind ica el tipus de con str icció que pot ser: { E G' ww = 1 L N > ::; fun ció obj ec tiu o constricció lliur e Se cc ió COL UMI\'S.· Aquest.a secció del I\ J PS se rveix per: 1. De cla r ar els nom s de l es variab les. 2. Donar va l ors als coefici ent s amb els que int e rv en en les \·aria bl es di ns de cada const.ricció lin ea l. :3. Si el j aco bia s'e mmag at. ze ma espa rs, indica quina és la posició deis elern ents no nuls del jacobiá. En a que st cas , el valor num eric indi cat no té importancia (p ot ser zero. per e xemp le). Si hi h a. \'ari ab l es lin ea ls i no lin ea ls. prim er s'han de d e clarar l es no linca ls. F ins qu e no s' han int.roduú . tot.s els coe fi cie nt. s que afecte n a un a. varia ble no es p ot co m e n ~ar a mb un a nova v ar i ab le. L 'o rdr e en qu e es d ecla rin les variables no linea ls h a. de coinc idir anil.i lºordre usat. 2 ln1 al vec o: :: - fins a . · :: E ·- ·- · on els ;:-n·s - ta: ~ : . :::.3-::::c_: e e :: ~::~ : _: ca.:a :: ..=-- - - on els :~--~ - - RHS. c::.=::::c:::c_: del te:::.-: corn. c .. e -, _ - a ques; ,,,.:- :· S ecc1 ó ?...;.:· -:::::: és :
~Jet .\/l .\"05 ,.._ l :e;; ::ades que - -=:== ;: :i ; oc up ar ::._:~_"::-0':..n ind i- ~ -.~ ::.;:;::._indp). = 1 el nom -• ::::; :;.,--:cions del 1 >- ;o:::; d"militz ar . - :> •:; ;:; ;;o:;íu si n ºhi -'"--r:::=.:. <. we hen1 ,..- ;o::.• !:::: '. :a el _ · ::_~3 consnul-; : ~n .5 que ·-::: 3. ~ 3 u na · ==c :e usat 2 Intmducció al paquet Minos 23 al vector X de les funcions FUNOBJ i FUNCON. Així , comen~ant amb X(l) i continuant fins a X(N) haurem de declarar: l. el nom triat pera la variable X(i). 2. si el jacobia s' e mmagatz e ma en forma esparsa , els eleme nts no nuls de la columna i-éss ima del jacobia , indic ant el nom de la constricció no lineal corr esponent i un valor numéric fi ctici. 3. els coeficients no nuls de la co lumn a i-éssima de la matr iu de constriccions lineals. indicant el nom de la constricció lin ea l i el valor numéric del coeficient. El formal d"escriptura d 'aquesta secció és: 1234567890123456789b123456789b123456789Ó123456789~123456789~1 COLUMNS . . .. variable .. constr ul . . coeficientu1 .. . constru2 .. coeficientu2 011 els punts indiquen espais en blanc, variable és el nom de la variable que estem tra ctant, construl i constru2 són noms de constriccions on in te rvé la variable en qüestió, i coeficientul i coeficientu2 indiqu en els valors amb que la variable que tract em afecta a cada cons tr ic ció (si la constricció és no li neal es pot posar qualsevol valor). Ca l tenir en co mpte que en aques t. apartat han d'aparéixer els no ms de tetes les variab les, lineals i no lineals, fins i tot si no tenen c ap co e fi c ient associa t. Secció RHS : Declara els termes independents de tates les constriccions (lineals i no lineals). Poden anar en c¡ualscvol or dre . El format d'esc riptura és: 1234567890123456789b123456789b123456 RHS .. . . nomuindp .. constr uí . . terrneuindept on els punts indiquen espais en blanc, nornui ndp indi ca el nom que donem al con junt de ter me s RHS. constr ui indi ca el nom de la con str icció que tractem i terrneu indept represe nta el valor del terme independe nt . El n om norn u in dp és ar bitrari pero ha de ser el m ate ix per a totes les compone nts c1·u n mat eix vector de term es ind epen dent s, i no més serveix per a donar 11 0 111 a a c¡u est vector. Secció RA : YGES : és: s·u sa p er d efi nir cons tr iccions del tipu s 1 S: f; S: 11 . El format d' escrip tura c1 ·aqu esta secció 1234567890123456789b123456789 b12 3 456 RANGES ... . nornurang .. co nstrui . . terrneuranges on els punts indiquen espais en bl anc, nornurang indi ca el n om que donem al con junt . de rangs.
24 Dept.E/O / UPC / Optimització de mode/s no lineals amb el paquet MINOS construi indica el nom de la constricció que tractem i terme u ranges representa el valor del rang. El nom nornurang té la mateixa funció que el nom nornuindp. Si a l'apart at RHS s' ha definit F(i·) :S 11 i Yoiem tenir 1 :S F(x) :Su el valor del rang ha der ser rang = 11 . - l. Secció BOUNDS: Declara les lites de les variables. El seu format és: 12345678901234567B9n123456789~123456 BOUNDS .zz.nornuboun .. variable .. terrneubounds on els punts indiqu en espais en blanc, nomuboun indi ca el nom que donem al conjunt. de lit.e s, variable indica el nom de la variable que tractem i termeubounds representa el valor de la lita. El nom no rnuboun té la mateixa funció que als dos apartats anteriors. El camp zz ens indica el t.ipus de lita i pot prendre els valors: ¡LO zz= UP FR FX :s 2: variable lliure Existeix la poss ibilitat de fixar dins d'aquest apartat el punt inicial a partir del qua] Minos comenc;ara la cerca del punt inicial factible. Per defec te Minos inicialitza les variables a zero o a la lit a més pro pera a zero, la qua! cosa pot provocar problemes en certes con st. riccions no lineal s. Per fix ar el valor inicial d'una variable ca l incioure a l'ap arta t BO UNDS la següent línia: 1234567890123456789n123456789~123456 .FX.INITIALu .. variable . . valorinicial 2.8 Exemple de codificació d'un problema en format MPS Sigui el problema: 1n · 1n . (x¡ +x:> +x3)'.' subj. ? + .i:~ = 2 x¡ x3 = 4 x 4 1 +x3 2: o 2x 1 +4x:> - X3 :s 1 X¡ 2: O, X2 2: O, X3 :S 1 El fitxer J\ · JP S associat a aquest problema amb e mmagat ze mam e nt dens del jacobiá seria: NAKS R DllS E :E T.:: .. : E :¡;, ¡- :.::...: G : :rg -- = L :: ¡ ;:_: J: COLffi! 3S RES -:--,,_: __ J:: .:: ':-E :?--:I: .:: -=-~ ....:i: .:: -:- c=..... : :c .:: ~¡~~~ ?:C " iS E c:I.óJ::...: E :::ET::..:: G c:E.=..: L ::1,,-_: :L COL~5 RHS I2 x: X3 -:-.::..~ _v_:i:: 80 T:!S o :..: :w:5: _,. LO :..:~t :::_,. ? :.. =~ ~=~