Investigació operativa dereminista. Apunts

EST 10D DIPLOMATURA D'ESTADÍSTICA INVESTIGA CIÓ OPERATIVA DETERMINISTA Practiques de programació no lineal amb el paquet GINO Esteve Codina Sancho ,- - . ·-- . -- ' UNIVERSITAT POLIT�CN/CA DE CATALUNYA . 1111111111111 1400295316 FACULTAT DE MATEMÁTIQUES I ESTADÍSTICA INVESTIGA CIÓ OPERATIVA DETERMINISTA Practiques de programació no lineal amb el paquet GINO Esteve Codina Sancho Títol: Investigació operativa determinista. Practiques de programació no lineal amb el paquet GINO Autor: Esteve Codina Sancho t Legal: B-37.593-1997 ,res per: ÁHLENS Sor Eulalia d' Anzizu, s/n 08034 Barcelona Investigació Operativa Determinista (Diplomatura d'Estadística) Practiques de programació no lineal amb el paquet G INO Esteve Codina Sancho Departament d' Estadística i lnvestigació Operativa Facultat de Materna.tiques i Estadística Universitat Politecnica de Catalunya Curs 97-98 O Introducció. Els excrcicis de lahoraLori consisLeixen en un conjunL de practiques a realiLzar sobre models assignaLs a cada ¡¡rup ,le ptacdques o be descrjts en aquesL ¡¡uió. Cada exerc.ici consLa el 'un A breu descripc.ió i d'un aparlal d'excmples que l'alumnc hanra de ressc¡¡uir amb alenció i reprodu'ir amb el paquel GINO previamc11L ,1 l'elabornció d'nn informe on es conLeslarn a un conjuhl de qüestions formuladcs al final de la clescripció de l'cxercici. Es sobre aquesL informe sobre el que s'eíectuara la valoració de IB practica. Aquests exercicis són: Exercici l. Resolució, magal.zemament i canvis de formulació. 2. Excrcici 2 \línim local d'1111a funció real scnse rest.riccions. 3 Exercici 3 ,\jusi per mí11ims quadral s, 4 Excrcici 4 \línim lornl d'una funció real amh resLriccions. 5 Exercici 5 MoJcls simples de fluxes en xarxes. 6. Exercicis addicionals. Problemes d'optimització amb resLriccions optatius. El programa Gl. 'O es Lroba insLal.lat a la xarxa de PC's de la Facultat de Materna.tiques i Estadística i de la FarnlLat d'lníormatica de la UPC. Per invocar-loés suficient situar-se al directori de treball i donar la coma ria GINO /\q11<:SL guió de pr�cti,p1<'s prcLen ser 11111.osuficienL i conté unn descripció del paq11et que ¡iermcl, cfecl unr les I nsques �sscuci1lls ele inlrorlucdó, mílg;,.Lzcrnament, modifiClltió i rcsolució d 'un model ,le la ío1h1n més scnzílla possihlc. El pa<111el GINO chsposa ele Lres comanes d'a_iut inlerarLives: HELP, COM)! ¡ CAT le,: ,¡,inls ¡,odcu rc,;11l1;ir \'al11oses 1l11ranL In 1calil.zació deis cxercicis. Pels est.11d.ian1.s habiLuals en el 1is del l""I"º' 1,11'' DO la nrnnip11lació clel pac¡uel GJ NO present.ara 11n esíor� c¡unsi 11111 jaque ambdos pat¡11el.s comparteixcn molles comanes i una filosofia ele Lreball identica. A cliíerenc.ia riel raque.L LINDO, GJNO no disposa d'un edilor prop! amh el c¡ue manirnlar l!D model i, Lal i com passa amb el paquet LINDO la forma més práctica de Lreball consisleix en fer ús d'un editor, tan per crear per primer cop el model com per fer canvis i manipulacions d'un model ja creal. Des-de GINO podreu Lenir facilmenL accés a qualse,·ol editor que estigui lnstal.lat en el PC amb el que es\eu Lreballant. Per tant, res11lln molL convenient, sino imprescindible, que coneixeu algún e<füor deis anomenaLs "de propi>sil genernl'' i1cs.t.al lnt en l'cntor-n en el qne ns movcu (pcr excmple, el Notton editor). 2 1 Exercici l. Resolució, magatzemament i canvis de formu• lació. J':11 r11111cst prinlcr cxercic, c11s linlllnron, n utiliLznr 1111 conjunt d coma11c" bi\.�11¡ues nmb les que poder trcl,nllnr cíldc11Ln1ent amh el GJNO l'ol-scr préviamcnt a q11alsevol descripcoó cal que s'invo,¡11i al pn1p1ct G I NO De�prcs cl'invotar-lo apareixcra ur1n caratula anuncian! el pac¡11el i finnlmeut, el prompt ': ', demn11n111-nos que introd11im unn comn11n i inicianl aixi una sessió. En aquestes contlicions podcm cxecuLnr la comano COMIIANDS. Aparelxcra en la panlalla el conjunl de comanes de GINO a¡¡rupacles per funcionnlitals comunes, Podem demanar informació sobre una romana determinada miLjan�ant la comnna HELP 'cnmana', la qnal ens dona unn írnse explicativa de la finalital de la comana en qiieslíó: : HELP GO GO COHHAND SOLVES THE CURRENT IIODEL. THE HODEL REMAINS INTACT THROUGH THE SOLUTION PROCESS. Ahans ele conlinnar cal dir que per sorlir ele GJNO ulilil.zarem comunmenl la coma na QUIT. Donarcm ara una descripció de les se¡¡üent.s comanes: SAVE, RETRIEVE, TAKE, LOOK, DIVERT, RVRT, SOLU, GO, OS, ALTER, EXT, KOOEL. 1.1 Carrega i comprovació d'un modeL S11poscm el se¡¡iie.11L problema cl'opl.imilzació: S.íl :r:� -:r:¡ 2'. (1 (OP) :r:1 + 2:1:2 - 2 � O (l) La forma en c¡ue es poL magalzemar en el clise dur del vosLre PC un model GINO consisLt.ix en filxers c¡11e r.0111.cncn una cle�cripció del modcl mitja.n�anl com11nes proples del GlNO, Aq11e.sLS fiLx.ers poden es.ser cclitals ílntb ecllt ors de proposil general del DOS. Suposem que disposcm en el clise dur d '1111 fiLxer HODEL.DAT q11c ,li:,�cri1, el problema (OP) mitjan�.ant comnnes del GJNO, Si des-de el DOS "feu un type KODEL. DAT" ,\quest apareixr.ria com: KODEL KIN = 3 •(x-2)·2 + 4•(y-1)·2 x·2 -y< O; X+ 2• y -2 < 0 ; END l,n sinl axl r¡11e haveu ele seguir per definir un modcl és mol!, simple: la parauln cla11 KODEL indica inici rle clcclararió d� moclcl i In pa-raulo END linnl ele declnració Entre les ducs paraulcs hi figme.n 11n conjunL de filrs cl'cxp1csíons mnlc1ni1Li<¡11cs. Ln scparnció entre fila i fila s'indica per '; ', Entre les diíerenles files pol e.�PH la corrcsponcut a la <lcfinició de In f1111ció objccLiu, Aquesta ve indicada per IIIN = (problema de 1111r11111i1zac1ó) o pcr KAX = (problcm;i de mnximiLzació). Els operndors aril.mctics elemenLals són: +, -, •, / i l'expo11e.nciar.ió /\. SIN(), COSO , EXP(), LOG() cles.•i¡¡ncn ni sinus, cosin11s, f11nció exponencial i lo¡¡mirme nnlural respcclivcrrenl,, (> , < Le11c11 iile111ic sii,:nificaL i fu11cions que nl LINDO), En cas de q11e rcspoui,:ueu IIODEL com resposl.a al':• int.crnclivcmc11L, GI 10 rcspo111lra nonl,, i c�p�rnti1 l'cntrad11 d'11nn elepressió maLemñlica finaliLzncla amh '; ', Per finalil.z�r l'ent.rnd,� d'un modd r.al ronlel=l,ar END al prompt ? 3 La comana RETRIEVE HOOEL.DAT carrega el model des-de el fitxer MODEL.DAT, mentre que la t mana TAKE HODEL.OAT executa les comanes GINO que contingui el fitxer MODEL.DAT (entre elles les que defineixcu el model). Per comprovar que el model s'ha carregat correctament utilit.zarem la comana LOOK_ La comana LOOK permct veure tot el model o tant sois una part d 'ell: LOOK ALL mostra per pantalla tot el model. :LOOK ALL HODEL: 1) HIN= 3 + ( X - 2) - 2 + 4 • ( Y - 1 ) - 2 2) X - 2 Y< o 3) X+ 2 + Y - 2 <O; END LOOK 'fila), fila2' Mostra només les files especificades dins del rang 'fila], fila2'. Per exemple: :LOOK 1,2 1) HIN= 3 • ( X - 2) - 2 + 4 • ( Y - 1) - 2 2) X - 2 - Y< O; 1.2 Modificacions d'un model. En cas de que fora nccessari efectuar modi/kadons cl'un model poclriem ut.ilitzar les e.amanes ALTER, DEL i EXT o bé modificar la definició del model mitjan�ant. un eclit.or del DOS. En cas de que t.rehallem amb models de pet.it tamany és recomanablc aquesta 1íltima opció Per acceclir a un fitxer en el disc dur c¡uan est.cm l.rehallanl. amh el GINO no és necessari abandonar la sessió ("sortir" ,lel paquel). La comana OS ens permel d'execular qualsevol comana del sistema operatiu en el que ens lrobem (el DOS). Si per exemple volem consultar quins fit.xers amb l'ext.ensio .DAT tenim al direclori en el que estem, senzillament fariem OS OIR • .DAT i apareixeria per pantalla el llistat de fitxers proporcional pel DOS. Analogamenl podriem invocar un editor pet modificar el fitxer l\1ODEL.DAT. Suposanl que tinguessim el Norton editor al nostre PC i que aquest s'invoques mítji\ntant la comana 'NE' podriem cridar-lo des-de el G!NO pcr motlific.ar el fitxer MODEL.DAT: OS NE HODEL.DAT Al sort.ir ne l'eclíLor l,ornMicm a estar eu cliilleg nmh el GINO {,,pnrcixcril : ). TomRriem a c..-irre¡;ar miLjantnnt In co111a11n TAKE o RETRIEVE el 11011 model c.011I lngut a MODEL.DAT. En cas rlc ,¡11n vol¡;uessim crear un fit.xer en el ,!tsc dur ;imb la dcsc-ripc1ó del noslre moclel 11Lilitzariem la r.onia11n SAVE 'nom de fil.xer'. Per modificar direclamenl des-de el GJNO un model, és a dlr sense editar un fitxer c¡11e contingui la seva definició, uLiliLzarem les comancs ALTER, EXT, DEL. La comana DEL serveix per eliminar unn l\1;1 de la clefinció del modcl. Per exemplc, DEL 2, esborraría la primera rcstricció del model (OP). La cornl\na EXT servcix per efegir una fila al nostre moclcl. Després de clonar la coma.na EXT GJNO ens demana la deflnció de l:t nova fila (110 ? apareix en pantalla). Per exemplc, si en el mocleJ ¡,el prohlem11 (OP) volem afcgir la rest.ricció x + y 2:: 1/2 clonariem la comann EXT :EXT ? X+ Y> .S; 4 la qua! seria afegida com fila número 4 al model. (Recordeu-vos d'acabar la línia amb '; ' per indicar finaliLzació de l'expressió). :LOOK ALL HODEL: 1) HIN= 3 • ( X - 2). 2 + 4 • ( Y - 1 ) . 2 2) X· 2 Y> O 3) X+ 2 • Y - 2 <O; 4) X+ Y> .5 ; END La comann ALTER 'rang de files' 'slringl 'slring2' snsl.ilueix a les files dins del rnng de files especifical el corijnnl. ele cnrilct.ers 'sLringl' pe] conjnnl del caracLers 'sLring2'. Per exemple, si volem canviar el terme de la drcl.11 de la reslricr.ió <¡lle expresa la fila 4), 0.5, per 1.1 donariem la comnna: ALTER 4 '.5'1.1' :ALTER 4 '.5'1.1' :LOOK ALL HODEL: 1) HIN= 3 • ( X - 2) - 2 + 4 • ( Y - 1) • 2 2) X· 2 Y> o 3) X+ 2 • Y - 2 <O; 4) X+ Y> 1.1 ; END 1.3 Resolució d'un model. Quan n 'esLem segnrs de que el model s'ha carreb'ñl corrccLamenL podem inleuLar resoldre'l. lnde pendcnLmenL del Lipu� de modcl, GINO inida la resol11ció del model amb la comana GO. Al finaliLzar l'execució GlNO proporciona la solució q11e ha Lrobal l dona un missatge informatiu ele les condic.ions pcr les que s'ha prochiít !'aturada. Una vegacla hem resolL un modcl sempre podcm fer r¡ue ens torni a clonar per pnnl,nlln la solucíó uLiliLzanL la comana SOLU sense invocar el proceclimenl, al¡;orismie q11e l'ha obl ing111 .. Pcr rcsol,lrc el moclel (OP): :LOOK ALL KODEL: 1) HIN= 3 • ( X - 2). 2 + 4 • ( Y - 1) . 2 :GO 2) X - 2 Y< O 3) X+ 2 • Y - 2 <O; END (con!. pág. segiicnl,) 5 2.2 Contingut de la Practica Per complimenlar la practica caldra que respongueu a les segiienls qiieslions adjunlanl els llislals de sorlida proporcionals per GINO i les definicions deis models emprals. Considereu les funcions: (8) 1. Delermineu miljan�anl l'ajut del GINO dos mínims locals de la funció Ji. 2. Comproveu que els dos punls proporciount.s per GINO verifiquen les c.o11dicio11s necessilriP.s de primer i segón ordre. 3. lnlenleu delerminar mitjan�anl el GINO un mínim local de la funció hQuina solució obt.eniu ? 4. Escriu les condicions de primer i segón ordre corresponenls al problema de la minimil.zació de la funció hPoden lrobar algtin punl que les verifü111i ?. Justifiqueu la resposli. 12 3 Exercici 3. Ajust per mínims quadrats. En moltcs ocasions se sap q11e un modcl malematic rcspon a una exprcssió del Lip11s y = J(:r:,, ... , :r:m, 01, •• , u¡), on :r:,, ... , :Z:m són variables que deLerminen el valor de la magniLucl y i a,, ... , at són paramNres <¡lle cal determinar. Si es cone1x un conjunl d'observacions :z:U = (:z:\;, ... , r!!:), i de \'alors de la magniL11cl yU, j = l, ... 1:., corresponenls a 11q11estes observacions, llavors poL int-entar-se determinar el valor deis parameLres a,, ... , a, de forma que es verifiquln les k igualLals: En general, deguL a que les k observacions y(j de la magnitud y venen afeclades d'errors de mesura les anteriors equacions no es compliran sino de forma aproximada per un valor de les "t, ... , a,. Pcr determinar un valor ele les a1, .. , 01 podem procedir per ajust. mínim quarlriitic, és adir, intentar clelermi11ar uns valors per a1, .•. , "' de forma que la suma deis (Jlli\!lral.s deis k errors: presenli el mínim valor possible. Es a dir, intentariem trobar el mínim de la funció: 3.1 Exemple El l.emps de CPU que dedica un compulador en l'exer.ució d'un delermi11al programa depen del volum n de clades d'cntrada al programa i se sap que el Lemps cl'execució ha rle VP.nir donaL per una expressió del tipus: t(n) = a+ bn (9) essent a,b constants que es vol ajustar mitjan�ant el criteri de mínims quadrats al disposar-se de les següents observacions: n; 10 20 35 50 60 75 t; 134.12 135.23 137.96 140.10 141.67 143.56 PlanLejariem el segiienL problema d'optimil.zació: Mín.,1 ,,.,(a,b) = ¿�=1(a+b•n;-t;)2 que descriuriem al GINO de la següent forma: 13 !)5 l 10 146.50 149 00 (10) (11) KODEL: 1) HIN= Yl . 2 + Y2 . 2 + Y3 . 2 + Y4 . 2 + YS . 2 + Y6 . 2 + Y7 . 2 + YB . 2 2) Y! A + B • 10 -134. 12 3) Y2 A + B • 20 -136,23 4) Y3 A + B • 36 -137.96 5) Y4 A + B • so - 140.10 6) YS = A + B • 60 -141. 67 7) Y6 = A + B • 76 -143.66 8) Y7 A + B • 96 -146.50 9) YB = A + B • 110 -149.00; END Al resol el re'] obt.indriem el valor de les variables Yl, ... YB que 1'micamenl proporcionen la diíerencia entre el valor observat i ]'ajustat i els valors eslirnals per les const.anls a, b qnc ve11e11 clonals per les variables A, B. : GO SOLUTION STATUS: DPTIHAL TO TOLERANCES. DUAL CONOITIONS: SATISFIED. OBJECTIVE FUNCTIOR VALUE 1) .246766 VARIABLE VALUE REDUCE□ COST Y1 -.061568 .000000 Y2 .313019 .000000 Y3 -.190112 .000000 Y4 -. 103231 .000000 Y5 -.188636 .000000 Y6 .148245 .000000 Y7 .177417 .000000 YB -.096702 .000000 A 132.573840 -.000074 B . 148459 .000005 ROW SLACK OR SURPLUS PRICE 2) .000000 .123136 3) ·ºººººº -.626037 4) .000000 .380224 S) .000000 .206461 6) .000000 .377271 7) .000000 -.296491 8) .000000 -.354834 9) .000000 ,191405 14 Fixem-nos en que una forma alternativa de descriure el model seria: HODEL: HIN= ( A + B • 10 -134 .12 2 + A + B • 20 -13S.23 - 2 + ( A + B • 3S -137.96 -2 + A + B • so - 140 .10 - 2 + ( A + B • 60 -141.67 -2 + A + B • 7S -143.S6 - 2 + ( A + B • 9S -146.SO -2 + A + B • 110 -149.00) - 2 END Així dones el model ajuslat vindra donat per t(n) = 132.5738 + 0.148459 · n. 15 3.2 Contingut de la Practica Per complimentar la practica caldra que resolgueu els segiienls problemes mitjan�ant l'ajut del GINO, aclj1111tanL un llist.at amb els result.ats proporcionals pe! paq11et. l. Un t.ecnic vol ohtenir una expressió per la distancia <le frenada cl'un vel1icle en funció de la velocitat a la que s'inicia el frenal .. Se sap que la distancia de frenada en funció de la velocilat ha de venir donada per una expressió del tipus: d(v) = o0 · v + a1 • vf!, i es disposa de les següenls observacions: v¡ 20 30 35 40 50 60 65 75 85 100 11 O d, 2.7 5.3 7.1 8.9 13.3 18.2 20.8 26.4 33.4 44.7 52.!J (12) • Planlejeu una funció objectiu ,p(o0, o1, /31) que expresi la suma deis quadrat s de les diferencies entre els valors observals d; i d(v;) = o0 • v + o1 · (v;)11'. • Del.crmine11 amb l'ajnt ele! GINO nn valor pels coeficienls o0, o1, /31 de manera que es minimitzi l'anl.erior fnnció rp(u·o,01,/31) 2. La quanLitat de camions ele transport que entren i surl.en del port d'11na ciut.nt. clepe.n directament del volum de mercaderies que arriba o surt embarcat del port. Les mercacleries esl an composades per: a) contenidors, b) mercadería pesada i e) mercaderia a clojo lleugera. Els tecnics del port estimen c¡ue la relació entre el volum de camions de transport i els diferents tipus de mercaderies respón a una expressió del tipus: on t(c,¡,, d) es la q11antitat de camions ele transport, e és la quantitat de cont.ainers, p és la quantitat de mcrcacleria pesada en tones i ,/ és la q11antitat de mercacleria a dojo lleugera també en tones i ª" ªr• lld són parilmelres a determinar. Es disposa del següenl conjunt cl'observacions: e, 210 810 205 300 350 160 704 45 45 170 p, 500 305 300 1080 300 105 58'5 81 75 340 d, 220 110 40 50 280 10 1080 30 35 365 (13) t, 15320 21307 10945 27810 13620 6510 25517 3735 3913 11502 Mit.jan�anL aj11st mínim q11adrat.ic delermine11, a parlir de les ohservacions. el valor deis parametres 11,, "¡;, Cid del mouel. 16 4 Exercici 4. Mínim local d 'una fundó real amb restriccions. Ac¡u,:sL exercici te com objecLiu l'analisi de les condiciona de primer ordre d'un problema de progra mació no lineal (PNL) amb resLriccions i la idenLificació deis mulLiplicadors de Lagrange de les resLriccions del problem;i Lal i com els proporciona GINO al presentar una saludó d'aquesL. Es recomana Lenir presenLs cls conccptes ex)'>osaLs a classe de Leoria. Per La! de faciliLar-ho presenlem al final de la practica un breu resum de Leoria pcr les condicions de 1" ordre d'un problema amb resLriccions i despres presenLcm un exemple numeric pcr il.lusLrar la forma en que GJNO presenLa una solució i com interpretar aquesta. 4.1 Un exemple. Significat de les columnes PRICE i REDUCED COST Mitjan�anl aquest exemplc es mostrara com GINO presenta els multiplicadors de les restriccions de desigualLaL d'un problema de programa.ció no lineal. Les condicions de Kuhn-Tucker esLablc.ixen que els mu!Liplicodors de les resLriccions de dcsignalLaL han de ser no negatius menlre que, pels multiplicadors de les restriccions d'lgualLaL no hi ha res dit. No obstanL pot semblar que GJNO no respecta aquesLes condicions. Amb el següenL exemple aclarirem aquest aspecLe: S.a Z2 -Zf � 0 Z¡ + 2:i:2 - 2 $ 0 (µ1, µ2 mulLiplicadors de Lagrange) (14) Obsé.rveu que no hi ha-n resLriccions d'igua!LaL presenLs. PreviamenLa aplicar de forma sisLematica les condicions de Kuhn-Tucker caldrá expresar Loles les restriccions de d.esigualtaL del problema en la forma g(:r) � O. Fixem-nos que la primera reslricció esla e.xpresada de la forma: z2- :i:1 � O. Si mullipliquem per -1 ambdos cosLa.Ls de la desiguallaL calclra canviar ? per $ i la resLricció s'expresara ll11vors segons :i:? - :i:2 � O, amb lo c¡ual lotes les rcsLriccions del nosr.re problema son del Lipus 9(:z:) � O. El lagrangia d'af¡uesL problema seria dones: Les condicions de Kuhn-1\1cker pel problema són: 6(:i:1 -2) + 2:i:¡µ¡ + µ2 8(:i:2 -1) -µ¡ + 2µ2 µ¡ ? o, µ2 ? 0 z2 -zf :i:¡ + 2:i:2 -2 µ¡(:i:2 -z?) + µ2(z1 + 2z2 - 2) = o = o (signes deis multipl.) � O (/ actibilitat) $ o ( " ) = O (com¡,lcmcntnrietnt) (16) Per La] de resoldre el model amb el paqneL GINO preparariem un filxer (per exemple, el HODEL. DAT) amb la definicio del problema PNL: HODEL HIN= 3 •(x-2)"2 + 4•(y-1)"2 :i:·2 - y< O; :r + 2• y -2 <O; END Cal dir que no es necessari r.onverLir Loles les resLricdons de desig11all.a.L a la forma � O per crear el fiLxer de definició del model (filxer HODEL. DAT). No obsLanL es molL convcnienL fer-he ¡>er procerlir 17 de forma ordenada, si cal plantejar les condiciona de Kuhn-Tucker i calcular ama els multiplicadors de Lagrange. Carregariem el fitxer MOOEL.DAT al paquet GINO miLjan�ant la comana TAKE MODEL.DAT. Després de comprovar que s'ha carregat correctament mitjan�ant la comana LOOK ALL el resoldriem (comana GO): :LODK ALL HDDEL: 1) KIN= 3 • ( X - 2). 2 + 4 • ( Y - 1) - 2 :GD 2) X - 2 Y< O 3) X+ 2 • Y - 2 <O; END SOLUTIDN STATUS: OPTIKAL TO TDLERANCES. DUAL CONOITIDNS: SATISFIED. OBJECTIVE FUNCTION VALUE 1) 5.069133 VARIABLE VALUE REDUCED COST X .780776 ·ºººººº y .609612 .000000 ROi/ SLACK DR SURPLUS PRICE 2) .000001 2.790982 3) .000000 2.957023 Savent que la solució proporcionada per GINO és la (xj, 1:;) ::::: (0.760776, 0.600612) calculeu a mil els valors deis multiplicadors (µj, µ2) i comproveu que són aproximadamenL (2.7!)0982, 2.957023) Carregueu ara el maLeix model pero expresant la primera restricció en la forma: 1:2 - :r.¡ 2'. O i resoleu-lo. Oblindreu la següent resposta de GINO: :LODK ALL KDDEL: 1) KIN= 3 • ( X - 2) - 2 + 4 • ( Y - 1 ) - 2 :GD 2) Y X - 2 > O 3) X+ 2 • Y - 2 <O; END SOLUTIOR STATUS: OPTIMAL TO TOLERARCES. DUAL CORDITIORS: SATISFIED. OBJECTIVE FUICTIOI VALUE 1) 5.069133 (cont. pag. segiienl) 18 VARIABLE VALUE REDUCED COST X .780776 ·ºººººº y .609612 .000000 ROII SLACK OR SURPLUS PRICE 2) .000001 -2.790982 3) .000000 2.957023 Obser11t11 nra com la entrada de la columna PRICE corrtsponenl a la restricció primera apareir can viadn de signe. GINO forma en aqnest cas el ll\grangia de la següent. forma.: moslranl-nos a la columna PRICE els 111, 112 que guarden la. segiient rela.ció a.mb els µ1, µ2: (18) Per tant podem veure que GINO presenta a la columna PRICE: •Sí la restríccíó s'expresa de la forma g¡(x) :S O llavors a la columna PRICE apareíx el multiplicador de Lagrange: µ¡. •Sí la restriccíó s'expresa de la forma g¡( x) � O llavors a la columna PRICE apareix el multiplicador de Lagrange canviat de signe: -µ;. Columna REDUCED COST. Al costal de la columna VALUE , on es dona el valor de cada variable a la solució del problema, apareix la columna REDUCED COST. Cada element d'aquesla columna es correspon amb un deis elemenls de 'ilr.C(:r1,r2,µ1,µ2). Pe) noslre problema d'exemple apareixen: a.e a¡ a(xi -:i:¡) a(:r1 + 2:r2 -2) ax1 = ax1 +111• éJ:r1 + 112' ax1 a.e a¡ a(z1 -:i:?) éJ(:r1 + 2:i:2 -2) (19) axi = ax2 +111 • 8:i:, + 112• ax, Eslant a.valuades les deriva.des pa.rcials * , ... etc. de forma aproximada. O sigui que la columna REDUCED COST ens proporciona una aproxima.ció al gradient del lagrangia respecte de :r del problema (el qua) és teoricamenL zero en un punL que verifiqui les condicions de Knhn-Tucker). Per aquesta causa si a la columna REDUCED COST no apareixen elements nnls o quasi n11ls ("" 10-6) s'acostuma a donar el missalge DUAL CONDITIONS UNSATISFIED. (Veure practica 1) 19 t.2 Resum de teoria. Donem a continuació un breu resum de les condicions de primer ordre d'un problema PNL. Suposem10s enfrontats a trobar un punt :r" E Ir' pel que una función /(:r) : R" ...... R presentí un valor mínim Jins d'un conjunt de punts de R" que venen expresats per un conjunt de igualLats en número finit del ;ipus h;(:r) = O, i = 1, ... mi/o un conjunt de desigualtats, també en número finit, del tipus 9i(x) S O, i = 1, ... L: Mín /(:r) S.11 /,(x) = 0 g(x) S O Definim el Lagrangia del problema (PNL) com: (PNL) Llavors tot óptim local del problema PNL verificara les condicions de Kuhn-Tucker: (20) (21) Condicions de Kuhn-Tucker (Kuhn i Tucker (l!l51)) Dir·em que x·, >.•, ¡1" verifiq11en les condicions de líttlin-Tttck<r si es compl<ixcn les tres cnndicions seg,icnls: l. g(:r") S O, /1(:r") = O. (factibililal} 2. µ· T g(x") = O,µ· ,:: O. (complementariet.at) 3. v'rl(x",>.",µ") = O ( v'rl(x" ,>.", µ") = v' f(x") + v' /1(:r") T )." + v'g(x") T¡,• ) (22) Cal remarcar que tot el que s'ha dit anteriorment és valid en els casos en que no hi estiguin presents restriccions d'ignaltat. 20 Za z g - - - - ------ ------ - Mín,; s.a Es demana: � ( f,2 + �Zi�I •� z.)1 ) ½ i=D ... a *1 Z¡ � O - /J • Z¡, (zo = Za, ZN = ZT, 6 = (rTÑr,)) X i=l, ... ,N-1 l. Resoldre el problema per "'ª = O, Za = 7, "'T = 1, ZT = 4.8, o = 61 /3 = 5.04, N = 15. (31) 2. Determinar una aproximació deis extrems de l'interval de punts de contacte de z(z) ambla recta z = 6 - 5.04 · "'· 3. Comparar la solució obtinguda amb la del problema sense restriccions (30) 27