Investigació Operativa Determinista : lnformació de l'assignatura

/ '--' '--' '--' '-' 001 \....; !S~ -...-' 6SEE~EOOP~ '--" llll llll 111111111111111111111111111111 1111111111111111111111 '-' e3a¡o1¡q19 '--' VANíllV!V8 30 V81N8~1110d 1Vl1Sl:J3/\1Níl VANíllVlVO 30 VOINO~lllOd lVJ_ISl::l3/\INíl '"-"' ...... '-' '-' '-" "-- " ·"'> Jli~1~5S21 Investigació Operativa Determinista lnformació de l'assignatura Curs 99-00 Diplomatura d'Estadística. FME • Prof essors. • Organització de les classes. • Programa de l'assignatura. • Bibliografia. • Normes d'avaluació. • Formularis oficials. • Transparencies. Departament d'Estadística i Investigació Operativa Secció Informtttica Títol: Investigació Operativa Determinista Informació de l'assignatura Autor: F.Javier Heredia Diposit Legal: B-9709-2000 Impres per: AHLENS Sor Eulalia d'Anzizu, s/n 08034 Barcelona r' Professors: • F. Javier Heredia Cervera (responsable). Departament d'Estadística i lnvestigació Operativa. * Despatx 408. FME. * Telf.: 401-73-35, e-mail: [email protected] * Horari de consultes: dilluns i dimarts de lüh a 13h, amb cita previa. • Jordi Castro Pérez. Departament d'Estadística i lnvestigació Operativa. * Despatx 218. FME. * Telf.: 401-58-54, e-mail: [email protected] * Horari de consultes: dimarts de 15h a 18h i divendres de 1 lh a 14h, amb cita previa. Organització de les classes: • Classes de teoria: prof. F. Javier Heredia, dimarts i divendres de 15h a 17h • Classes de problemes i laboratori: prof. Jordi Castro, divendres de 15h a l 7h • La classe del divendres es dedicara en setmanes alternes a teoria i problemes/laboratori. Programa l. INTRODUCCIÓ. Concepte d'Investigació Operativa. Formalització deis processos de presa de decisions. La presa de decisions quantitatives i els models de la Investigació Operativa. 2. PROGRAMACIÓ LINEAL. Formulació de models de Programació Lineal: Definició de model de programació lineal. Hipotesis de modelització. Models de programació lineal. Models de fluxos en xarxes. Definició de programes lineals mitjan~ant el paquet de modelització algebraica LINGO. Característiques deis models de Programació Lineal: solució grafica d'un programa lineal de dues variables, interpretacions. Regió factible i conjunts convexos. Solucions optimes. Problemes infactibles, no afitats i amb optims alternatius. Solucions basiques: formulació de Programes Lineals en forma estandard. Solucions basiques i punts extrems. Teorema fonamental de la Programació Lineal. Resolució de models de Programació Lineal: L'algorisme del Símplex: identificació de solucions optimes. Canvi de base. Algorisme del Símplex primal. Convergencia, degeneració. Forma tabular del Símplex. Calcul d'una solució factible inicial. Estudi computacional de I'algorisme del Símplex mitjan~ant el paquet LINGO. Dualitat i analisi post-optim: el problema dual. Relacions primal-dual. L'algorisme del Símplex Dual. Analisi de sensibilitat de la funció de costos i termes independents. Addició de variables i constriccions. Analisi post-optim mitjan~ant LINGO. 3. INTRODUCCIÓ A LA PROGRAMACIÓ ENTERA. Formulació de models de Programació Entera: Definició de model de Programació Entera. Hipotesis de modelització. Models de Programació Entera. Definició de Programes Enters mitjan~ant el paquet LINGO. Característiques deis Programes Enters: Solucions. Regió factible. Estrategies de resolució. Resolució de models de Programació Entera. Algorisme de Branch&Bound: Separació. Relaxació. Eliminació. Arbres d'exploració. Algorisme del Branch&Bound. Resolució de Programes Enters amb el paquet LINGO. 4. PROGRAMA CIÓ NO LINEAL. Formulació de models de Programació no lineal: Definició de model de Programació No Lineal. Hipotesis de modelització. Models de Programació No Lineal. Definició de Programes No Lineals mitjan~ant el paquet LINGO. Característiques deis models de Programació No Lineal i deis seus algorismes: propietats deis models de Programació No Lineal. Representació de la funció objectiu al llarg d'una direcció. Direccions factibles i de descens. Indentificació d'optims. Característiques i estructura general deis algorismes de la Programació No Lineal. Exploració Lineal: exploració lineal exacta i aproximada. Exploració lineal per avaluacions de la funció objectiu: metodes de Fibonacci i secció auria. Resolució de models de Programació No Lineal sense constriccions: condicions de primer i segon ordre de mínim. Convexitat. Calcul de direccions de denscens. Metode del Gradient. Metode de Newton. Resolució de problemes de Programació No Lineal sense constriccions amb LINGO. Resolució de models de Programació No Lineal amb constriccions: Condicions de mínim de primer i segon ordre: condicions de Kuhn i Tucker. Convexitat. Interpretació economica deis multiplicadors de Lagrange. Metode del Gradient Reduit Generalitzat. Resolució de problemes de Programació No Lineal amb constriccions amb LINGO. Bibliografia • Ref erencies basiques: * Winston, Wayne L.: Introduction to mathematical programming: applications and algorithms. PWS-KENT. Ed., Boston, 1991. * Luenberger, D.G.: Linear and Nonlinear Programming. Ed. Addison-Wesley Publ. Co. Reading, Mass, 1984. * Solver Suite: Lindo, Lingo, and What's Best. Lindo System Inc. Chicago. 1995. * Jordi Castro, F. Javier Heredia. Col.lecció de problemes resolts d'lnvestigació Operativa Detenninista. * Jordi Castro. Investigació Operativa Determinista: practiques amb LINGO. Referencies complementaries: * Bradley, S.P.; Hax, A.C. and Magnanti, T.L.: Applied mathematical programming. Ed. Addison-Wesley, 1977. * Peressini, AL., F.E. Sullivan, J.J. Uhl, Jr.: The Mathematics of Nonlinear Programming. Undergraduate Texts in Mathematics. Springer-Verlag. 1988. * Wagner H.M.: Principies of Operations Research. Prentice Hall 1975 * Liebman, J., Lasdon, L. and Waren, A.: Modeling and Optimization with GINO. Ed. The Scientific Press, San Francisco, CA, 1986. * Schrage, L.: User's Manual for Linear, lnteger and Quadratic Programming with LINDO,Release 5.0. Ed. The Scientific Press, San Francisco, CA, 1991. ~, .~ ·'"" - "" ....... -, ..... .... ..... """ .... ..... ~ - ...... ...._ ...... -.. ,...,. '"" .~ -, Normes d'avaluació: La nota final de l'assignatura (N) s'obté a partir de la nota de teoria (Nt) i de la nota de laboratori (NI) amb una ponderació del 70% i del 30% respectivament, és adir: N = 0.7*Nt + 0.3*Nl Per tal d'aprovar l'assignatura cal que: 1) la nota final N sigui~ 5. 2) les notes de teoría Nt i de Iaboratori NI siguin ~ 4. • Nota de teoria Nt: s'obté a partir de la nota de I'examen parcial (Np) i de l'examen final (Nf). L'examen parcial cobrira els punts 2 i 3 del temari. L'examen parcial és alliberatori a partir de Np ~ 4, Si Np < 4, l'alumne s'ha de presentar a l'examen final de tot el temari de l'assignatura. Si Np ¿ 4 Ilavors l'alumne té I'opció de presentar-se a I'examen final només de la segona part del temari (punt 4), tenint en compte que en aquest cas ha d'obtenir també una nota no inferior a 4 d'aquest segon examen. L'alumne sempre té l'opció de presentar-se a !'examen final per intentar millorar nota. La nota de teoría Nt es calcula a partir de les :notes Np i Nf de la següent forma: 1) Si l' alumne es presenta a 1' examen final de tot el temari, obtenint una nota Nf: Nt=Nf 2) Si l'alumne es presenta a l'examen final de la segona part del temari (només permes si Np~ 4) obtenint una nota Nf: Si Nf ~ 4 Ilavors Nt = (Np+Nf)/2. Si Nf < 4, Ilavors Nt = min{3.75, (Np+Nf)/2}. L'únic material que és permes als exámens són els formularis oficials i una calculadora. • Nota de laboratori NI: la nota de laboratori NI s' obté a partir de les notes de les practiques de modelització amb LINGO: Practiaues de modelitzacció amb LINGO Nom Títol Oblieatoria Ponderació Int Introducció. NO 0,1 MPL Model de Programació Lineal. SI 0,3 MPLE Model de Programació Lineal Entera. SI 0,3 MPNL Model de Programació No Lineal. SI 0,3 Les practiques es realitzaran en grups de dos alumnes. La nota de Laboratori NI s' obté a partir de la nota d'aquestes quatre practiques segons I'expressió: NI = 0.1*Intr+0.3*MPL + 0.3*MPLE + 0.3*MPNL La presentació deis informes de les practiques es realitzara dins del termini fixat a classe. El primer full de I'informe haura de contenir la següent informació: • Títol de la practica. • Nom i cognoms deis alumnes. • Número del grup de practiques. • Adrec;:a electronica deis alumnes. • Data de presentació. • Convalidació del laboratori: no es convalida la nota de laboratori de IOD obtinguda en cursos anteriors. • ConvocatOria extraordinaria: els alumnes suspesos a la convocatoria ordinaria s'hauran de presentar de tot el temari de l'assignatura a la convocatoria extraordinaria. Com a nota de laboratori es prendra la nota NI obtinguda a la convocatoria ordinaria. - ""' ,...., """ ...... ""' '"" '""" "' "' ...... "" ""' ""' ""' ...... ..... ..... -.. "' ......, ..... ..... ..... ..... """' ""' ...__ -, ''"" Formularis , FORMULAR! OFICIAL PROGRAMACIO LINEAL I ENTERA Algorisme del simplex primal : O) Trabar una s.b.f. primal : B. 1) Si r~ ~O : FI , B optima. 2) Seleccionar la variable d'entrada q EN l rq <O: 1'q = min¡e...v{ri} 3) Si Yiq ::; O i = 1, ... , m : FI problema (P) il.limitat. 4) Seleccionar la variable de sortida Bp E-B 1 Yvo/Yvq = mini=l, ... ,m{yiO/Yiq 1 Yiq >O} 5) Canvi de base Bp +-+ q (pivotació): B +- B \ {Bp} U {q} ; N +- N \ {q} U {Bp} 6) Anar a 1) Algorisme del simplex dual : O) Trabar una s.b.f. dual : B 1) Si X~ ~ o : FI ' B optima. 2) Seleccionar la variable de sortida Bp E B J xBp <O: xBp = mini=l, ... ,m{xBi} 3) Si Yvi ~O Vj EN: FI problema (D) il.limitat. 4) Seleccionar la variable d'entrada q EN 1 rg/Ypg = maxvje.N"{ri/Yvi 1 Yvi < O} 5) Canvi de base Bp +-+ q (pivotació): B +- B \ {Bp} U {q} ; N +- N \ {q} U {Bp} 6) Anar a 1) Algorisme de Branch& Bound : O) Inicialització: [, = {(PEl)}, z* = oo 1) Si [, = 0: FI, x?E .,.__ x*; zj,E .,.__ z* 2) Seleccionar un problema (PE j) de [,; 3) Relaxació: resoldre la relaxació lineal (PRj). 4) Eliminació: Si KPRj = 0 o si zPRj ~ z* o si xPRj E KPEj llavors: Eliminació de (P Ej) de C: [, +- [, \ {(P Ej)}. S. * IT . * .. 11 l X PRj E \.PEj l ZPRj < z avors: Actualització de la incumbent: x* +- xPRi' z* +- zPRj· Anada a 1) 5) Separació: Separació de (P Ej) en dos descendents (P Ej + 1) i (P Ej + 2). Actualització de C: [, +- [, \ {(P Ej)} u {(P Ej + 1)} u {(PEj + 2)} Anada a 1) ~ ¡ ...._ '"' '"' '""" '""" ...... ........ ""' Al\ .... .... .... ""' "" ""' ...._ ""' .... .... ...... ""' ...._ "'"" ~! '"""' F. Javier Heredia Dept. EIO EL MÉTODO DEL GRG 24 Algoritmo A2.1 : Algoritmo del Gradiente Reducido Generalitzado (GRG) 0 Sea X E nN RN : 0 0 Definición de la partición x = [; ] Cálculo de 'Vyf(y,z), \lzf(y,z), 'Vyh(y,z), 'Vzh(y,z) r'+- \lzf(y,z) -- 'Vyf(yiz)[\lyh(y,z))- 1 \1,)i(y,z) t1zi +- {O si Zi = lz¡ y r¡ > O o z¡ = U;q y r¡ < O -r¡ en otro caso Si bi.z = O entonces x punto estacionaria de (NRN): STOP en otro caso L\y +- -[Y'yh(y,z)]- 1 \lzh(y,z)L\z L\x +- [ ~~ l Fin si 0 iiy = max{a: ly ::S y+ al\y S uy}, iiz = max{a: lz ::S z + al\z ::S Uz} ii +- min { ii y, ii z} a* f-- argmin{f ( x + al\x) -O < a :S ii}. Si o:* = iiy entonces: intercambio zq t-t Yp [±] x +- x + a* L\x 0 Mientras h(fj, z) #O hacer L\fj +- -[\1yh(y,z)]- 1h(iJ,z) ii- +- max{a: l- <y-+ al\y- <u-} · a- +- min{l ii-} y Y- -y ' y 'y iJ +- iJ + O'.ylly Si ay = iiy entonces: intercambio Zq t-t Yp Fin mientras 0 x +- x. Actualizaciones de Vyf(y,z), Vzf(y,z), Vyh(y,z), Vzh(y,z), r Ira0 Bloc opta.tives 10 ' Interes de la 1.0. per als diplomats en Estadística. • Area característica de la DE de la UPC • Relació optimització-estadística. * Problemes d'optimització a !'estadística. * Tecniques estadístiques i de disseny d'experiments aplicades a la simulació. * Calcul dels parametres dels models d 'optimi tzació. • Entorn profesional. * Molts problemes habituals a les empreses/industria/admin. necessiten ser resolts amb tecniques mixtes Est/IO. * Models de presa de decisions complexos basats en recollides de dades. 2 ,...._ ,...._ ,..... ,..... ,...., - - ..... ..... ..... ..... - - - -- """' ,..... - - - - ,..... ,...., '"""" MODELITZACIÓ DE PROBLEMES DE PROGRAMACIÓ LINEAL. Problema de planificació de la producció. Una empresa fabrica dos tipus de productes, A i B. En el procés de fabricació s'utilitzen els següents recursos: fusta, plastic i ma d'obra. L'empresa disposa de les següents dades sobre la fabricació de tots dos productes: Consu~ Consum Consum Preu venda Ma d'obra Fusta Plastic unitari A lh 3Kg 2Kg 820 pts B 2h 2Kg -890 pts Costos 300 pts/h 20pts/Kg 80pts/Kg Disponibilitat 150h/dia 300Kg/dia lOOKg/dia L 'empresa vol coneixer la quantitat diaria de producte A i B que ha de produir per a obtenir el maxim benefici. P1·oblema de !a dieta. Experts en nutrició desitgen confeccionar una dieta basica. Decideixen confeccionar aquesta dieta a base de cinc aliments diferents: mm, peix, cereals fruita i pa. La dieta basica ha de proporcionar unes quantítats mínimes de nutrients necessaris: Vitamines (V), Hiclrats de Carboni (HC), Oligoelement (O) i Proteines ( P) La cmnposició deis diferents aliments, les quantitats mínimes necessaries de nutrients i el preu ele cada aliment es mostra a 1 següent taula: Contingut per Kg. Pre u V(u.i.) HC (u.i) O (u.i) P (u.i) (pts/Kg) Carn 25 20 10 150 1000 Peix 200 50 10 200 1200 Cereals 300 300 1 10 50 500 Fruita o lGO 50 20 150 Pa o 120 100 20 200 Quantitat mínima 600 u.i. 400 u.i. 1000 u.i. 1000 u.i. Formuleu el problema de prograrnació lineal que permeti calcular la composició de la dieta més barata que satisfa els requeriments de nutrients mínims necessaris. Problema de transport. Tres refineries produeixen gas per a subminitrar a quatre mercats. La consulta a la base de dades de la companyia proporciona la següent informació sobre costos de transport, demandes de mercats i capacitats de cada refineria: Cost (mil./Hm 3) Mercats Gas disponible Refineries 1 2 3 4 (Hm 3) 1 4 7 g 10 8 2 6 4 3 6 10 3 g 6 4 8 6 Demanda (Hm 3) 5 3 8 4 Determineu la política optima de transport entre refineries i mercats. PROBLEMA DE LA MOCHILA Proble1na de selección de inversiones Enunciado : Una firma comercial debe decidir qué proyectos poner en marcha a lo largo de un cierto periodo de tiempo : Variables no controlables: n proyectos. 1n periodos. r;i rendiiniento del proyecto j , j = 1, ... , n. ªii inversión requerida por el proyecto j en el periodo i, i = 1, ... , m. b¡ capital disponible durante el periodo i. Objetivo : maximizar el renclin1iento total teniendo en cuenta las limitaciones ele capital. Variables de decisión: x;{¿ Formulación : n maxLcjXj i=l s.a. : n si se invierte en proy. j si no se invierte en proy. j '"'a··x· <b· ~ lJ J -1 i=l, ... ,m j=l Xj E {0,1} '"' """ """ """ ....... ..... ""' .... .... .... ..... ""' """' ..... '"' ""' ""' ..... ...... ..... ..... ..... ..... ""' ,....., ,,...., " SET COVERING" (recubrimiento de conjuntos) Acceso a información Enunciado : Se quiere acceder a m unidades de información guardadas en un conjunto de n ficheros de diferente longitud. Cada unidad de información se encuentra como mínimo en un fichero. Variables no controlables: : I = {1, 2, ... , n} unidades de información. J = {1, 2, ... ,m} ficheros. Cj longitud del fichero j, j E J llij { 1 si la información i se encuentra en el fichero j O en caso contrario Objetivo: Acceder a todas las unidades de información minimizando la cantidad máxima de información leida. Variables de decisión: Formulación : { 1 si se lee el fichero j x· 1 O si no se lee Longitud máxima explorada: min Lcixi jEJ s.a. : Se accede toda la información L llijX j > 1 Vi E I jEJ Xj E {0,l}'v'j E J Ejemplo "Set covering" I = {1, 2, ... , 5} 5 unidades de información (Ji)· J = {1, 2, ... , 4} 4 ficheros (F¡) Longitud ficheros: e' = ( 1000 1500 1000 1200) '"' '"' ""' ""' ""' ...... ...... ...... , ...... Recubrimiento del conjunto 1 ...... ...... ...... Matriz de restricciones. : """ ....... F1 F2 F3 F4 ---- 11 1 o o o > 1 12 o 1 o o Cl) > 1 X2 > 1 ""' Ax= [3 o o 1 1 u """ [4 o o 1 1 X3 > """ f 5 o 1 1 o X4 > """ --- ..... """ '"' '"' ...., Ejemplo "Set covering" Formulación en LINDO: : min 100F1 + 1500F2 + 1000F3 + 1200F4 st: !1) F1 > 1 12) F2 > 1 I3) F3 + F4 > 1 I4) F3 + F4 > 1 IS) F2 + F3 > 1 end integer 4 Resolución con LINDO : : OBJECTIVE FUNCTION VALUE /•' 1) 2600.0000 VARIABLE VALUE REDUCED COST F1 1.000000 100.000000 ~I F2 1.000000 1500.000000 F3 1.000000 1000.000000 F4 .000000 1200.000000 ROW SLACK OR SURPLUS DUAL PRICES !1) .000000 .000000 !2) .000000 .000000 !3) .000000 .000000 14) .000000 .000000 IS) 1.000000 .000000 ,, PROBLEMA DE LOCALIZACION DE PLANTAS (problema de carga fija) Enunciado : Una empresa dispone de m ubicaciones posibles para la construcción de las plantas de producción desde donde se distribuirá un , cierto articulo a los diferentes mercados. Objetivo: decidir dónde localizar las plantas de producción de forma que se minimicen los costes de distribución y apertura de planta satisfaciendo las necesidades de los mercados y las capacidades de las plantas. Variables no contr0lables: : I = {1, 2, ... , n} inercados. J = {1, 2, ... , m} posibles localizaciones de las plantas. f i coste fijo de apertura de la planta j , j E J (carga fiija). bi capacidad máxima de la planta j, j E J. di demanda del mercado i , i E l. Cji coste unitario de distribución desde una planta situada en j al mercado i. Variables de decisión : x iii c8Wl.tid.a<l de artículo distribuido desde la planta j al mercado i y . { 1 si se abre un.a pla®ta em la ubicación j 3 © si mo se abre .~ ,,... .-- ,.... ,..._ ,._ .... "' ~ "' """ ""' .... ...... ..... '"' .-. '"' .... ..... "" ''"' .... --- . Ejemplo problema. de localización de plantas Esquema:: b~·300~ ·--- fil] lt( .too; ba. fj, =L1oa l Formulación en LINDO~: ain 10x11 + 12x12 + 20x13 + 5x21 + 10x22 + 15x23 + 100y1 + 750y2 st: d1) x11 + x21 d2) x12 + x22 d3) x13 + x23 c1) x11 + x12 + x13 c2) x21 + x22 + x23 end int y1 int yl Resolución con LINDO : : OBJECTIVE FUJICTION VALUE 1) 1225.0000 VJ.RI.lBLE YA.LOE REDUCED CDST T1 .000000 100.00000G T2 .000000 750.000000 111 .000000 5.000000 112 .000000 2.000000 I13 .000000 5.000000 121 50.000000 .000000 122 45.000000 .000000 123 35.000000 .000000 Y2 =•O jj X21 > 0 1! jj X:zL > 0 !! jj X2J > 0 !! e 50 = 45 • 35 < 300 < 200 Ejemplo problema de localización de plantas Formulación completa : : ma 10x11 + 12x12 + 20x13 + 5x21 + 1·0x22 + 15x23 + 100y1 + 750y2 st: d1) x11 + x21 .. 50 d2) x12 + x22 • 45 d3) :x13 + x23 • 35 c1) x11 + x12 + x13 < 300 c2) x21 + x22 + x23 < 200 r1) x11 + x12 + x13 -301y1 < o r2) x21 + x22 + x23 -201y2 < o ,....._ end int y1 int y2 Resolución con LINDO : : OBJECTIVE FUNCTION VALUE ,....._ 1) 1840.0000 ,..., """' VJ.RUBLE VALUE REDUCED COST ..... Y1 1.000000 100.000000 ..... T2 .000000 -255.000000 ""' 111 50.000000 .000000 ..... 112 45.000000 .000000 ""' 113 35.000000 .000000 - 121 .000000 .000000 122 .000000 3.000000 123 .000000 .00000() """ -. ""' ..... ,..., - .- --- " '"" '"" '"" "'"' '"" '"'\ '"" '"'\ '"' ,, ~ -, ~, , FORMULACION PROB. DE LOCALIZACION DE PLANTAS min LLcjiXji + Lf;Yi s.a. : iEI jEJ j€J Lx;¡ = d¡ , Vi E 1 jEJ Lx;¡<b; , 'v'jEJ iEI LX ji < M;Yi ~ V j E J iEI xi i > O Vi E I , Vj E J YiE{O,l}jEJ 1={1,2, ... , n} mercados. J = {1, 2, ... , m} posibles localizaciones de las plantas. f i coste fijo de apertura de la planta j , j E J (carga fija). b; capacidad máxima de la planta j j E J. di demanda del mercado i i E l. Cji coste unitario de distribución desde una planta situada en j al mercado i. xi i cantidad de airtícul0 distribuido desde la planta j al mercado i y. { 1 si se abre una planta en la ubicación j J O si no se abre ... ... .... ... .... .... .... .... .... ... ... ... .... .... ... ... ... .... .... .... ... .... ... .... ... .... .... .... ... .... ... ... ... .... -. .... .... ... ' .... ... ' ... ... .... .... ... ... ... ... .... ... .... .... .... .... ... ... .... .... ... .... .... .... ... .... .... ... f. i4& (J%, V$?iLW$1~ -M®&&JQt424,, Et • ... • ••• 1 ••• 1 .... .... ~ .. .•. ·'" • ••• 1 •••• ... .... • ••• ........ .... .... '''" 1 •• .., • ••• 50"' • • . .. • •• 1 ...... .... ... .... . . .... ' .... • • • • ... .... ..... .... .... 'V •• .· ...... ... ... • ••• . .... ~:::· . ..., ••• . .... .... • ••• ..:..· ... . ........ .... ... ... . . . .... ..... • • • • ... ... ..... .., .... '1.'. .... ... ... .... ... ... ... .... ... X* a c=aa1 ... ... ... ... ... .... ... .... ... ... .... .... .... ... ... o 75 .... ... ... .... ... .... .... ... ... ... .... X* b ... ... ... .... .... .... .... .... .... ... ... .... .... .... .... .... .... .... .... ... .... .... 50 50 ... ... .... .... .... .... .... .... ... ... .... .... ... ... ... .... ... .... ... ... ... ... .... ... ... .... .... .... .... u. . e. P '"ª , a _ ,. s .. xaw., MUS<~~·.;.; ... AP;tAt.. qzt;c x Jtt.o:c ,& a.tl4 M&t:pua;1 _"·- M<A;t}4Ji4J.Attk. J $2~& '-- v '--' 1,,,..- 1,,,..- 1,,,..- """ \,,,.; '-" e.t 8,,t S,,t l ,,t "' !x o=zx fx '-t '-' rx '-' ""' ~ """ 11 ...... ('l'J ~ """' ..:: lo.o ~ 11 """' ~ '"" ""' ""' - PROBLEMA LINEAL ENTERO Y SU RELA]ACION LINEAL 7 6 5 4 3 1 1 2 3 4 ••• 1181 ' ..... . • 1 ••••• . ... . . ' •• 1 •••• .. .... . . . .... . 8 ••••• ' 5 6 7 6 5 4 a 2 l PRIMERA RAMIFICACION variable x1 (PEl) (PE3) (PE2) xl 3 xl 4 * s XPR2 l a a 4 5 6 o KPE2 11 K PR2 ... '. ,,, KPE3 ....... KPR3 .... ' ... . .. .. .. .. . . ' ... .. . . . . . . . . . . '' . .. . . . . 1. • • Si • - - - - - ! .... 111 ,._ : ..... ..... - - - w - - .. .. - .. - 'W "" - - - ... - - - - - - - - - - - SEGUNDA RAMIFICACION : variable x 2 (PE2) 7 (PE4) 6~( 5 '""'!. ·-.. . . . . . . . 1 . , -r~, ······· a --.· .- ' .. : 1 \~ ... " ,•, ~ a.- .. (.· : ..... '~- ... · 'o . \ .... · .... \ .. - (PES) x2 ~ 1 1 ~:.(·: . . ·, .. · -., .. --.·~ .:::-' -·:.-llml! ~~ .._....__. Si i a s 4 s 6 KPE4 = • KPE5 95 - KPR5 TERCERA RAMIFICACION : Sa variable x 1 7 (PE7) 6 l~ · .. 5 """! '."- .. l .· .. 4 - - : ·. . . f \ xf~t ~ XP~1 8 --· .- \ .. ·: : : · .... 1 \~ ·. .··· \ ~ . . .•. a. :.l.~ : .... : ' ~·..... . . 'o \ ... . .. (PES) (PE6) x1 ~ 5 * XPR6 = 1 -:r .. :\ ~ .. - ~·· . -· - -------< l---+-~ ..•. · . ... . ... l a o KPE6 KPE7 • a - -4 5 6 KPR6 m KPR7 ·e '. •. '"""' !<.J""~- (!.# .f J . ~¿,¡ h'C/1 PUJ Her ~f f" r1'eJ d ?''°""t"" ~"/~ . 7 . [! ... U J f(t'nt'Nl<J '! /, j,, /.r 1° JllÍ llt'ut.í J1; ;! iJ {t;1!JJ • z;-1. c,,~,,,,,i'_/ JI r"1. "' ;,"'ºh r,,_,;/ d' ~¡¡ h¡,,,.p¿ 7' fld e/~& (Í'J J 1 /""J , · t?J · ~ '"'j c. ¿. & • P $ ..reut¡I~ i: ./ª j.,~ ,; u,,,.,,f ,.; ,¿ ,,.,,,~,-1: M4,( ,f..f_.(L f/IJ'_z -8 r ,,l• ÍJ'Z .¡ ~l <t (j, -1 J'z. )~ J S" 117·· ; : .l.t ~ Jí ~ S' .IJ! Ji ~ C1 * 127~~k- /"'Í.'~;~I el ¡I /'" Ít-J t/N~r/. /7,.....rh ,.{/ j"Q~k & : ~· ~ fe 14 ~f .. 20~ J.~f·27. Cal 6= t Optimum.rc,• t .rcz= ¡ IUnconstrained optimum .1'1=J~ X2•~) x, o (b) fe 50 \. -~f= SS 5 9 .. ¡ Optimum x 1 .. 2.5, Xz=2.5 cunconstrained optimum ., .. 3, x2 :3.5l 5 x, o , .. ,()() ' 6= ¡ Optimum111 c5, 11 2 =0 CUnconstrained optimum 11 1 .. 12, 11 2= 141 x, ~ · !1¡ ,u¡ 1 ere"",fe /f,,J In , 1 p I 1 trt ti« fi-vtJ r r I . . t fe"''"' l";Í~ : (~)E" u:' 1- / 1°,¿kn't>Y ¿ h "'/'"' f ,,/J/e lb)& .. /'"' l ¡r1.,kr; ,,{ .-$ "f ¡u/ f"''ªU:Jlf'f t~~ . ce.) e., g 1-/ a/....va & h ttf'"/",. ,{j le. UN!\'ERS1 TAT POLiTECNICA DE CATALUNYA A.SS·)' 1•.•; =i!f/7'./.-,,_h; f f'f _J;}' t?y-m p;/ _,,,/ -1 n1 '""' /""/ /f ~ ,.,,,, w;. e~f /," _1,~;71 r "'"" ( 7.#J') /?? /??,/ ~ /,;/ /" '11""/.I rlh>,/iJ ¡rmlt1 f %: (" 1 T ~ • 1 1 1 - 1 -· - .. _, ··- ... '.•3·: -• t CONCURSO TEU-711 MÉTODO DEL GRADIENTE 8 Tabla 1: resolución completa del ejemplo (programa GRAD) (e= 103) k f(x") X~ x" 2 gf ur 11g"11 o" o o.o o. o. o. 2. 2. 0.25 - 1 -0.5 o. -0.5 l. o. L 0.50 2 -0.75 -0.5 -0.5 o. l. l. 0.25 3 -0.875 -0.5 -0.75 0.5 o. 0.5 0.50 4 -0.9375 -0.75 -0.75 o. 0.5 0.5 0.25 5 -0.96875 -0.75 -0.875 0.25 o. 0.25 0.50 6 -0.984375 -0.875 -0.875 o. 0.25 0.25 0.25 7 -0.992188 -0.875 -0.9375 0.125 o. 0.125 0.50 8 -0.996094 -0.9375 -0.9375 o. 0.125 0.125 0.25 9 -0.998047 -0.9375 -0.9687.5 0.0625 o. 0.0625 0.50 10 -0.999023 -0.96875 -0.96875 o. 0.0625 0.0625 0.25 11 -0.999512 -0.96875 -0.984375 0.03125 o. 0.0313 0.50 12 -0.999756 -0.984375 -0.984375 o. 0.03125 0.0313 0.25 13 -0.999878 -0.984375 -0.992188 0.015625 o. 0.0156 0.50 14 -0.999939 -0.992188 -0.992188 o. 0.015625 0.0156 0.25 15 -0.999969 -0.992188 -0.996094 0.0078125 o. 0.0078 0.50 16 -0.999985 -0.996094 -0.996094 o. 0.0078125 0.0078 0.25 17 -0.999992 -0.996094 -0.99804 7 0.00390625 o. 0.0039 0.50 18 -0.999996 -0.99804 7 -0.99804 7 o. 0.00390625 0.0039 0.25 19 -0.999998 -0.998047 -0.999023 0.001953125 o. 0.0020 0.50 20 -0.999999 -0.999023 -0.999023 o. 0.001953125 0.0020 0.25 21 -1. -0.999023 -0.999512 0.000976563 o. 0.0001 0.50 A::::: 5.23607, a::::: 0.76393, {3 $ 0.55556 F. Javier Heredia Dept. EIO INTRODUCCIÓN 1 1 INTRODUCCIÓN. 1.1 Definición del problema: forma estándar del problema {NRN) .. min f ( x) ( 1.1 a) {NRN) suj. a : h(x) == O (1.lb) ' . ._ , l <X< U (l.lc) f: 1R n -+ 1R ' f E C2 h:lRn-+ IRm, g E C2 i··r:i1}'E 1Rn ' ' Definición 1.1 Conjunto factible {NRN) : - 'n~ :_ :". " ' {x E Iftnt. ¡ fi'(x) ==O l < x < u} NRN ' _ _ . ' \ -- -- - ....._ .-.. """ .... .... .... .... .... .... .... - ·"" .-, - ..... ....... ...... ..... ..... .-. ·'• 1' i' i F. Javier Heredia Dept. EIO INTRODUCCIÓN 2 1.2 El método del G·radiente Reducido Generalizado~ [!] @] ~ [IJ lliJ Dado X E nN.RN; Detern1inación de la optimalidad del iterado actual x. Obtención de una dirección de movimiento ~x a lo largo del plano tangente a la hipersu perficie S .definida por h(x) == O en x. Obtenc.ión :. de la longitud de paso a* rne~ <liante expioración lineal a partir de x a lo largo de ~x. Actualización .del p.unto iterado: x == x + a*~x. Puesto que.,:.en ¡general el punto iterado x será infactible:(h(x) #O), recuperación de la factibilidad de x. ' . : ~ :: ~ ~ F. Javier Heredia Dept. EIO INTRODUCCIÓN 3 1.3 Justificación de la elección del método del GRG. • Métodos alternativos de resolución del problema (NRN): * Lagrangianos Proyectados (MINOS). * Lagrangianos Aumentados (LANCELOT). * Gradiente Reducido Generalizado (GRG2, CONOPT). • Ventajas docentes del GRG: * Fundamento teórico más sencillo. * GINQ.usa el código GRG2. ... t; i r ···-. ; --- ,-._ -. ,..... ....... """ ..... """ .... ..... ..... ....... """ ,-._ ~ ~. ....... """ ...., ...... ""' ....... "'"" _, _, F. Javier Heredia Dept. EIO EL MÉTODO DEL GRG 4 "' 2 EL METODO DEL GRG. 2.1 Hipótesis de no degeneración. 2.2 Cálculo de la dirección de movimiento. 2 .. 3 Exploración Lineal. 2 .4 Factibilidad del punto iterado. 2.5 Algoritmo-- del GRG. 2.6 Cálculo de soluciones factibles. F. Javier Heredia Dept. EIO EL MÉTODO DEL GRG 5 2.1 Hipótesis de no degeneración. Hipótesis 2.1, Hipótesis de No De- . , generac1on : Sea el vector x E IRn y su matriz Jacobiana \7 h( x). Existe una partición x' == [y', z'] y E IR m (variables dependientes) z E IRn-m (variables independientes) tal que: i) \7 yh(y, z) E Rmxm es no singular sobre x' == [y', z'], es decir: det(\7 yh(y, z)) =F O ii) ly <y< Uy -- ...... ...... ...... ...... """' """ """ """ """ ""' ....... ..., ...... ...... ...... ...... """ ...... ...... ...... .,..._ F. Javier Heredia Dept. EIO EL MÉTODO DEL GRG 6 Ejemplo 1 : Consideremos el siguiente problema {NRN): mm SUJ. a: (NRN) y el punto factible x = [ 1 2 X1X3 -2 - x1x5 + 3x1 -- 6x2 -4x3 - 4x4 2 Xl -2- + X2 - X3 + 2X4X5 - X5 = -2 3xI 3x~ 7 --·· + X2X3 -2x2 + - + X5 = -- 2 2 2 o::;xs;[4 4 4 4 4]' o 3 1 1 X3 -2 \lh(x)= [;: 1 1/2]'. La matriz Jacobiana: -1 2xs 2x4 -1] X2 3X4 1 evaluada sobr~ x = [ 1 O 3 1 1/2 ]' proporciona: [ 1 1 \lh(x) = 3 1 -1 o 1 1 l 3 1 Variables dependientes: y = [ x1 X3 ]': [ 1 -1] \7 yh( x) = 3 0 , no singular Variables independientes: z=[x2 X4 xs]': Vzh(x)= [i ; i] - F. Javier Heredia Dept. EIO EL MÉTODO DEL GRG 7 2.2 Cálculo de la dirección de movimiento. Definición 2.1 Plano Tangente : ,...., T(x) == {x E 1Rn 1 h(x) + \lh(x)(x -x) ==O} ,...._ ....... -- ,...._ ~ " ,..... -- ""' "" "" ""' ""' ""' ""' ""' ,...._ ~ ~ X1 '"' ,...._ -. -. X2 -. -. ,... ,...._ ~ """"' Fº Javier Heredia Dept, EIO EL MÉTODO DEL GRG 8 • Consideremos los puntos x que se encuentran sobre el plano tangente T( x). h(x) + \lh(x)(x -x) =:O (2.1) • h(x) == O y el valor de \Jh(x) y x es conocido: \!h(x)(x -x) == \lh(x)x - \lh(x)x ==O \lh(x)x == \lh(x)x == k ==cte. • Aplicamos ahora .. la partición en variables dependientes y e independientes z definida sobre x: \lh(x )X = [V yh(y, z ), V zh(y, z )] [ ~] = == \lyh(y,z)y+ \lzh(y,z)z == k • Aislando y de la anterior expresión se obtiene: ; . · 1 y == k - [\7 yh(y, z )]- 1 \7 zh(y, z )z (2.2) donde k == [\7 yh(y, z)]- 1\i'h(x)x ==cte. F. Javier Heredia Dept. EIO EL MÉTODO DEL GRG 9 ·2.2.1 Gradiente Reducido. ,. Dado un vector cualquiera z E IRn-m el vector: X ( z) = [ Y~) ] = [ k - [\7 y h (y, z ~ -l \7 z h (y, z) Z l pertenece al plano tangente a h(x) sobre x. • ·Gradiente de j(x) respecto de z sobre x(z): J(x) ==f(iJ(z), z) == f(z) Vf (Z) =\7 zÍ (Y, Z) + \7 vf (Y, Z) ~; = ==\l zÍ (y, z)- - \7 yf (y' z) [\l yh(y, z )]-1 \7 zh(y, z) Definición 2.2 Gradiente Reducido : - Expresión de \lf(z) sobre x: r' == \7 zÍ (y, z)-\7 yf(y, z)[\l yh(y, z)]-1 \l zh(y, z) '"' ....... ....... '"" ....... -. """ """ """ """ """ -. ....... ....... ...... ....... ....... ....... ....... ....... ....... '"" ...... F. Javier Heredia Dept. EIO EL MÉTODO DEL GRG 10 Ejemplo 1 (continuación): determinemos el gradiente reducido sobre el punto x. Se había calculado ya el valor de todos los vectores y matrices implicados en la expresión de r: r' =Vzf(y,z) -Vyf(yjz)[Vyh(y,z)]- 1 \l;:h(yiz) Vyh(x)=[~ r i Vzh(x)=l1 -1 l o J 1 1 -J 3 1 Vyf(x) = [7 --1] 'Vzf(x) = (-6 -4 -1] Se procede primero al cálculo de>. = -\7yf(y,z)[\7yh(y,z)]- 1• La factorización LU de \7 y h( x) es: [l -1] [1 º] í1 -1] \7 y h( X) = 3 o = 3 1 Lo 3 Resolviendo el sistema Vyh(y·,z)'>. = -Vyf(y,z)' se obtiene el valor de>.: [1 3]>-=[1 ][1 3][>-1]=-[7]*{>.1=-l -1 O -1 3 1 >. 2 -1 >. 2 = -2 A continuación se procede al cálculo de r = \7 zf(y, z)' -\7 zh(y, z)' >. : r = [ =n + [ ~ ~ ][ = ~ l = [ ~~1] F. Javier Heredia Dept. EIO EL MÉTODO DEL GRG 17 • Interpretación geométrica de la actualización x == x + a*~x. Y1 X=X+ cx*l'.lx -=- Z1 Z2 '"" - -, ........ -. .... ... "" "" "" """" ""' - ""' '"' ...... ''"' ..., ..... ..... -- F. Javier Heredia Dept. EIO EL MÉTODO DEL GRG 18 0 ay tmin { ._ min { ly~- Yi 1 .6.yi <o} , ._ min { Uy~ - Yi 1 f:lyi >o}} z-1, .. .,m Yi z-1, .. .,m Yi . { . { lz· - Zi 1 A o} . { Uz¡ - Zi 1 A o}} Ó'z tm1n m1n ' uZi < , m1n --- LJ.Z¡ > i=l, .. .,(n-m) '6.zi í=l, ... ,(n-m) .Ó.Zi a t-- min{ Óyi Óz} a* t-- argmin{J(x + a.6.x): O< o:::=; a}. Si a* = &y entonces Selección de Zq apropiada para intercambiar con Yp associada a óy. Actualización de la partición x = [ ~] y cálculo de \7 yh(y, z) Fin si ITJ x tx + a* .6.x Ejemplo 1 (continuación): calculemos la longitud de paso máxima a. Teniendo en cuenta que l = O y u = [ 4 4 4 4 4 ]', aplicando las fórmulas (2.6-2.7) se tiene: [ 1 J , r-46 / 3 J y = 3 ' t!.y = 26/3 z = UJ . ~, = [ ~, l ay, = 46/3 _ . 3 3 3 - l } - - ( 4 - 3) => y - { 46' 26} - 46 a -min - - - - O'.y 2 - 26/3 ªz 1 = (4 - 0)/9 = 4/9 } ~Z2 = (4 -1)/11 = 3/11 => O'.z 3 = (4 - 1/2)/4 = 7 /8 - . 4 3 7 3 => O'.z =mm{ g' U' S} = U 3 3 3 a = min{ 46' u} = 46 F. Javier Heredia Dept. EIO EL MÉTODO DEL GRG 19 2.4 Factibilidad del punto iterado. • Sea el punto iterado x == x +a* ~x. • La factibilidad de x depende del tipo de restricciones. 2.4.1 Caso de restricciones lineales. Proposición 2.3 : Sea X E nNRN y considérese el vector iterado x == x +a* ~x, donde a* es la longitud de paso obtenida según las relaciones (2.6-2.9) y ~x es la dirección de movimiento definida por (2.4-2.5) . Supongamos que se satisface la hipótesis H2 .1 . Si las restricciones del problema (NRN) son lineales (Ax == b, A E IRnxm, b E IR/n-) entonces x es una solución factible del problema (NRN) -, ,__ ""' -, ,..... """ ""' .. - ..... - ..... ""' ""' ""' ""' ....... ""' ""' '"" ......, F. Javier Heredia Dept. EIO EL MÉTODO DEL GRG 20 - 2.4.2 Caso de restricciones no lineales. • x, en general, infactible: h(x) #- O • Se intenta recuperar la factibilidad mediante la aplicación del método de Newton: h(y1, Z) ~ h(fí, Z)+[\7 yh(fj, Z), \7 zh(fj, Z)] [ ~ 1 ~ i] = == h(y, z) + \7 yf(y, z)(y1 - y) ==o y1 == y - [\7 yh(f), z) ]- 1 h(f), z) 1 - - ~·~ y - y+ y ' ~Y == -[\7 yh(f), z)]-1 h(y, z) • Conservación de las cotas fj: y1 == y+ a:y~f) ! (2.10) ~Y== -[\7 yh(y, z)]- 1h(y, z); a:y == min{l, a:y} • Si a:y == a:y: actualización de la partición - - [-' -11 Xy,zJ . F. Javier Heredia Dept. EIO EL MÉTODO DEL GRG 21 • Representación geométrica del proceso de recuperación de factibilidad. Y1 [y',z-'] [y 1' ,z-' 1 [y2' ,z-'] Zz ....., F. Javier Heredia Dept. EIO 0 Mientras h(y, z) -j. O hacer 6.iJ +- -[\7yh(y,z)]- 1h(iJ,z) iiy +- max{ a : ly :S iJ + a6.fj :S u¡¡} fí +- fí + ay6.i) Si ªfJ = iiy entonces EL MÉTODO DEL GRG 22 ªfJ +- min{l, iiy} Selección de Zq apropiada para. i!ltercarnbiar con. f)p associada a a¡¡. Actualízacion de la partición x = [ f J y cálculo de \1 yh(y, z) [Vyh(y, z )J-1 +- [\7 yh(y, z)J1 Fin si Fin mientras 1.- En la práctica llh(fí, z)ll ~ Eh. 2. - Si las únicas restricciones presentes son lineales, h( x) = O y el proceso iterativo del paso 0 no se activaría. 9.- En el cálculo de 6.fí se toma [\7yh(y,z)J-1 en lugar de [\7yh(y,z)]-1• 4. - Si x es lo suficientemente cercano a x, el método de Newton converge. 5.- La aplicación del método de Newton puede fallar debido a diversas razones: 5.1.- Después de un numero prefijado de iteraciones el valor de llh(x)ll es superior Eh, o el valor de llh(y, z)ll aumenta. 5.2.- El valor de la función objetivo empeora: f(Y, z) > f(x, y). En estos casos se vuelve a realizar un movimiento a partir del punto original x a lo largo de 6.x con un valor de a* reducido (a* +- a* /2 o a* +- a* /10, por ejemplo) J..j F. Javier Heredia Dept. EIO EL MÉTODO DEL GRG 23 Ejemplo 1 (continuación): tomemos una longitud de paso arbitraria a* = ii/2 = 3/92 así pues., el punto iterado será: -46/3 1/2 x = x+a* .6.x = 1 o 3 1 3 +92 9 27/92 26/3 = 151/46 - 1/2 z = 125/92 [ 27 /92] ; y= [ 151/46 l ' 29/46 11 125/92 1/2 4 29/46 h(-) = [ 1.98488] -t. o X 3.26364 I .6.y = -[\7 yh(y, z)]-1 h(y, z) se calcula resolviendo \7 yh(y, z).6.fj = -h(y, z): [ 1 -1] .6. -= [ 1 ] [ 1 -1] [ .6.v1] = -hC _) = ¡-1.98488] { .6.v1 = -1.08788 3 o y 3 1 3 .6.f}2 y, z -3.26364 =?- .6.f}2 = 0.897 Teniendo en cuenta el valor de las variables y' = [ 1/2 151/46 ]' y las cotas uy = [ 4 4], ly = O, la longitud de paso máxima a lo largo de ..6.fj es: ªYi = -1~6J1ss = 0.4596 } - _ . - 4 - 151/46 =?- ªii -0.4595 ' ªii2 = () ~()7 = o. 7997 ªii = min{l, 0.4596} = 0.4596 d . - - A - [ O. l h(- -) ¡-0.3186] es ecir: Y+- Y+ nyuy ~ 3.6948 ; y, z = 0.3969 Puesto que a.y = iiy1, debemos intercambiar Y1 por una variable independiente Zq apropiada. El valor de \7 h( x) sobre el nuevo punto x = [f}', z'] es: - [ 1/2 1 -1 1.2608] \7h(x) = 3/2 1.2826 0.2934 4.0760 La variable .Z1 = x2 está entre cotas y, junto con ih, proporciona un nuevo \7 yh(y, z) no singular: [ 1 -1 l \7yh(y,z) = 1.2826 0.2934 det(Vyh(y, z)) = 1.57608 por lo tanto, podemos intercambiar fíi = x1 por z1 = x2. ""' ...... ,...... ...... ...... ,...... ...... ..... ""' ""' ""' ..... ...... ...... ...., ""' ...... ...... ...... ...... ...... - ,...., ....._ F. Javier Heredia Dept. EIO EL MÉTODO DEL GRG 24 Algoritmo A2.1 : Algoritmo del Gradiente Reducido Generalitzado (GRG) 0 Sea X E nN RN : 0 0 Definición de la partición x = [; ] Cálculo de "Vyf(y,z), 'V,J(y,z), "Vyh(y,z), "Vzh(y)z) r ~ 'Vzf(y,z)-"Vyf(y 1z)[\1yh(y,z)]-1\7zh(y1z) ~Zi ~ { O si Z¡ = lz¡ y ri > O o z¡ e::: Uz¡ y r¡ < O -r¡ en otro caso Si ~z = O entonces x punto estacionario de (NRN): STOP en otro caso ~y~ -["Vyh(y,z)]- 1 \lzh(y,z)~z [ ~y 1 ~X~ ~z J Fín si [TI Óy = max{ o: : ly :S: y+ o:~y :S: Uy} , Óz = max{ o: : lz :S: z + o:~z :S: Uz} ó ~ min{ óy, liz} a*~ argmin{f(x + o:~x): O< a :S: ó}. Si a* = ay entonces: intercambio Zq t-t Yp [±] x ~x+a*~x 0 Mientras h(y, z) f:. O hacer ~Y~ -["Vyh(y,z)J1 h(y,z) ªii ~ max{ a : ly :S: y+ a~fí :S: uy} ; ªii ~ min{l, ªii} ií ~ Y + o:ii~ií Si ªii = ªii entonces: intercambio zq t-t Yp Fin mientras · . 0 x ~ i. Actualizaciones de "Vyf(y,z), "Vzf(y,z), "Vyh(y,z), "Vzh(y,z), r Ira0 F. Javier Heredia Dept. EIO EL MÉTODO DEL GRG 25 2.5 Cálculo de soluciones factibles. Algoritmo A2.2: Fase 1 : algoritmo de cálculo de soluciones factibles (NRN) 0 Dado xº tf_ nNRN' se define el conjunto de restricciones violadas x+ i x-: I+ = {j 1 hi(xº) >O} , -r- = {j 1 hi(xº) <O} , I = I+ uI0 Se introduce una variable artificial Vj en cada restricción violada j E I: h ·(x) - V. =o VJ. Ex+ . V. >o J J ' ' J - h ·(x) + v · =O VJ. Ex- · v · >O J J ' ' J - 0 Se define el problema (NRN 1) asociado a la Fase 1: mm SUJ. a: (NRN1) f¡(v) = L Vj jEI hj(x) =0,jtf_I h j (X) -V j = 0 , j E I+ h j (X) + V j = Ü , j E I- [ ~X~ U O~v (2.lla) (2.llb) (2.llb) (2.llb) (2.llc) (2.llc) 0 Se define la solución inicial factible [xº',v0 '] E nNRN1' donde el valor de vJ se determina como: vJ = hj(xº) si j E -r+ , vJ = -hj(xº) si j Ex0 Se obtiene la solución óptima [x*',v*'] de (NRNi) a partir de lxº',v 0 '] E nNRN¡ mediante el algoritmo del GRG. Si f¡(v*) =O entonces x* es factible para (NRN). Si f¡( v*) > O entonces el problema (NRN) es infactible. ...... ....... ¡ ....... ....... ...... -. -. "' "' "' -. -. ...... ....... ...... ....... ...... -. -. ...... ....... ....... ""' --. F. Javier Heredia Dept. EIO EL MÉTODO DEL GRG 26 Ejemplo 1 (continuación): Formulación del problema (NRNi): Consideremos la solución xº = [o o o o o]' rt nN RN: hi(xº) = 2 ; h2(x) = -3.5 => 1+ = {1},:r- = {2} El problema {NRN 1) que obtendriamos sería: (NRN1) mm f¡(v) = v1 + v2 SUJ. a: x2 _l + Xz - X3 + 2X4X5 - X5 + 2 - V1 = Ü 2 3x 2 3x 2 7 _l + X2X3 - 2x2 + - 4 + X5 - - + V2 = Ü 2 2 2 O~x:S:[4 4 4 4 4]' o~ tJ Los valores inciales de v1 y v2 son: v~ = h1 (xº) = 2 , vg = -h 2(xº) = 3.5 La solución inicial factible {NRN 1) sería: [ :~ l = [o o o o o 2 3.5 ]' f¡(vº) = 2 + 3.5 = 5.5