Investigació Operativa Determinista : Problemes resolts

EST 100 / INVESTIGACIO OPERATIVA DETERMINISTA Problemes resolts F. Javier Heredia Cervera UNIVERSITA T POLITECNICA DE CATA LUNYA " Bibliote ca l llllll ll l ll lll ll lllll lllll lllll lllll lllll lllll llll l l lll / 11 1 1400253745 B' Col·lecció de problemes resolts d 'lnvestigació Operativa Determinista. F. J av ier Heredia Cervera. Dept. d 'Estadística i Investigació Operativa Secció d 'Informatica Universitat Politecnica de Catalunya /ntroducció lll Introd ucció Es present.a en aquest llibre una col·lecció de problemes. la rnajor part d'ells resolts, d'lnvestigació Operativa Determinista. El problemes s' han dividit en quatre apartats: problemes de modelització, problemes de programació lineal, problemes de programació lineal entera i problemes de programació no lineal. Aquests problemes han eslat elaborats. o adaptats d 'a ltres textes, al llarg deis set anys de docencia de !'autor a les assignatures d'Optimització (Llicenciatura d'lnformática , ami en dia inexistent), Mcdels Deterministes de la lnvestigació Operativa (Enginyeria I nformática) i lnvestigació Operativa Determinista (Diplomatura d'Estadística). tates elles assignatures de la Universitat Politecnica de Catalunya. Una part impo rtan! d'aquests problemes han aparegut als enunciats d'examens d'aquestes tres assignatures. El símbol "*" al co s tat . del nom del problema indica que es pot. trobar resolt arnb detall, mentre que el simbo! "t" indica que s 1ha in el os la se va solució. Barcelona. febrer de 1908. Índex V Índex 1 Problemes de modelització. ........... .. .. ................ .. 2 Problemes de programació lineal. ............. ... . ... ...... 13 3 Problemes de programació lineal entera ....... .. . .... ... .. ..... ... . 25 4 Problemes de programació no lineal. ............. .. ...... 31 5 Solucions deis problemes de modelització. ........... ...... 39 6 Solucions deis problemes de programació lineal. 51 7 Solucions deis problemes de programació lin ea l entera . 77 8 Solucions deis problemes de programació no lineal. . . . . . . 87 ' 1 Probl e me s de modelhzació 1 1 Problemes de modelització. l. Líni es Aeries Condor· . La compa nyia aéria "Línies Aeries Cimdor" (LAC) es dedica a la distribució de mercaderies amb la sern fl ota d'avions. Aques ta flota esta formada per 8 avi ons del tipus 1, 15 avions del tipus 2 i 11 avions del tipus 3. La capac it at, en milers de tones (Kt), deis tres tipus d'avions és de 45 per a cada avió tipus 1, 7 per a cada avió tipus 2 i 5 pe] tipus 3. El programa de vols del día d'arni indica que s'han d'enviar 20 Kt a la ciuta t A i 28 Kt a la ciutat B. Tenint en compte la distancia ent re la base de LAC i les dues ciutats, ca da avió pot fer només un vol diari. Els costos (en milers de pessetes) de vol d'un avió a cada ciut. at só n: Tipus 1 Tipus 2 Tipus 3 Ciutat A 230 150 20 Ciu tat B 580 200 38 Aquests costos no varien si )' avió as s ignat no transporta la seva ca.pa c itat m3.x im a. La torre de control de l'aeród rom base de la companyia LAC té una capacitat de control de transit aeri li mitada. El temps total que la t.orre té reserYat a LA C permet comrolar l'e nlairament i at.err atge d'un maxim de 5 avions tipus l. El temps de control d'un avió tipus 2 és la meitat del d' un avió tipus I, i el t emps de control d'un avió tipus 3 és de 1/3 el d"un avió tipus l . Formuleu el (PLE) que permet obtenir el nombre d'avions de cada tipus a enviar a c ada ciutat que min imitza els costos de vol. 2. Balan ~ racial~. La ciutat de Middletown té tres escales de secundaria, dos d'elles amb major ia d'estudiants de rao;a blanca i una amb majoria d'estudiants de ra<;a neg ra . La coordinado ra d'escoles d'aqu esta c iutat ha decidit modi fic ar l'assignació d'est ud iants a escoles per tal de recluir l 'a lllament racia l existent. L 'a juntam e nt disposa de la següent informació sobre els deu districtes en que es divideix la ciu tat: • Per a cada di st rict e, i = 1, ... , 10 : • n¡': nombre d'a lumn es de ra<;a neg ra al barrí i. • n f: no mbr e d'alumnes de r a<;a blanca al barrí i. • dj , j = 1, 2, 3: distancia des de cada barrí als tr es instituts . • Per a cada inst itut , j = 1, 2, 3: • c1: ca pa c itat escolar de cada in stitut . 2 CoHecció de problemes resolrs d'lm•estig ació Operatfra Determjnista. La r eassignació d'estudiants a escoles es vol fer de forma que la suma de les di stancies a recórrer pe r cada alumne sigui el més petita po ssible. L ·ajuntament . su posa que el no mbr e <l'estudiants blanc i negres del barrí i assigna ts a l'i nstitu t j guarda la proporció de races exist.ent al barri d'origen. La nova assignació ha de satisfer un cert balan<; racial que pron1ogui la convivencia entre els alumnes de les dues races a la mateixa esca la. Per tal d'aconseguir-ho es decideix que la fracció d' estudiants d1una ra~a qualsevol a cada esco la es mantingui ent re certs límits. Es co nsidera ideal u na propo rció de 1/2 per a cada ra<;a a cada escola, pero es permet una certa de sv iació B respecte d'aquesta proporció ideal Així dones. s' exigeix que la nova <listribució sigui tal que la fracció d'estudiant.s d'u na ra1a do nada a cada escola est.igui e ntre 1 /2 + B i 1/2 - B. Formuleu aquest problema com un problema de programa ció mat e matica. 3. Indu st ri es Alden • Les Industries Alelen fabriquen dos productes . Cada producte pot ser fabricat a la máquina 1 o a la máquina 2. El temps de fabricació que necessita cada prod ucte en funci ón de la má q uina on es fabriqui es mostra a la següent taula: MAQUINA 1 MAQUINA 2 PRODUCTE 1 PRODUCTE 2 4 h 7 h 3 h 4h Cada mes es di sposa de 500 h de cadascuna de les maquines. S'est.ima que el mercat. pot absorbir qualsevol quan tit at de produ cte 1 i 2 fins a un cert. Jím it (demanda maxima) , per sobre del qual es pe rd la producció. Els valors de la demanda maxima i el preu de v enda de c ada pro<lucte, pe r als proxims dos mess os, s'ind i ca en la següent tau la : DEMANDA MÁXIMA PRE U (unitat s) ( cente nars pt as ) Mes 1 Mes 2 \ les 1 Mes 2 Product e 1 1 00 190 55 12 Producte 2 140 130 65 ~2 L 'ob je ctiu de les Industries A ld en és maximitzar el benefici obtingut per Ja venda deis dos prpodu ctes durant els pr óxims d os mesos. Formu leu un pro gra ma lin ea l que pe rm e ti re so l dre aquest . prob l ema. 4. Estació de bombers L' Ajuntam e nt de Barc e lona té prevista la construcció d'una nova estació de bombers qu e cubreixi els dist ri ctes d' Horta-Guinardó, St. Andreu i Grac ia. L' Ajuntament disposa de is valors del temps de resposta (e n minuts) a una al arma produid a en un d'aquests tres districtes en funció de la ubicació final de l'estació de bombers , i del v alo r esperat del nombre d' alarmes 1 Pr oblt:rr.~ ~ - ~ di aries c. :=o. ... =. - E ls ¡€-:::. ~ ~-= --!._ :o :- :-r.a ~-=- ,._ 5. P:Z:.: for rr . .a ;-!- ~ ~= sin dica¿ . ~ - pro gra..o;:.?..:...: - 6. P laxa:....a rna :.~:-.s. :..s. dia de~;:..~ -.uc ;~5::-: , ~ o. . ~:::::...::?. ::.-?_ ":e..5- ::::::; - . ~~=-'"'e :.c:a:. ~ ~ e i:F:•:S:. : . ~ ~· ::::5-J.::es ~ - ·=· i...3... -=:es 1 Problemes de modelització 3 diaries a cada districte. Aq uestes dades es mostren a la següent taul a: Alar ma a Harta Guin. St. Andreu Grácia Estac ió a Harta Guin. 5 12 30 St. Andreu 15 ~ 15 Gr B.c ia 20 20 6 Prom ig alarmes : 2 1 3 Els técnics de l'Ajun tame nt han de decidir a quin districte construir l'estació de bombers de forma que el valor esperat del te mp s de resposta a totes les alarmes diaries dels tres distri ctes sigui mínim . F or muleu el proble ma de programació mat emática que per met resoldre aquest problema. 5, Pl a ntill a compa n yia Hi nde rnis• La companyia Hindernis dona f ei na a tres tipus diferents de treballadors, segons la seva qualificació: treballad ors de classe A, B i C. L 'act ivitat d'aquesta empr esa consisteix en la realització de dos tasques, la tasca tipus 1 i la tipus II. Cada tr eballa do r esta assignat a un únic tipus de tasca. La tasca tipus 1 pot ser rea li tzada només per treballadors de cla.s se A, treball ant sois. o per equips constitu"its pe r un tr e ba ll ador de cl asse A i do s treballadors de la classe B. La tasca II pot ser rea litzada per tr eba ll ado r de la classe A. t reba ll ant sois, de la classe B, treba ll ant sois, o per equips co nst itu"its per un treballador de la classe B i tr es treba ll adors de la classe C. Els treball adors de les classes A, B i C cobren 1000. 500 i 200 ptas/ho ra respectivamen t. Per ta l de cubrir les seves quotes de producció la compa nyia necessita assegurar cada setmana 1000 hores de producció assignades a la tasca 1 i 2000 hores de producció assignades a la tasca 11 . Tots els treba ll adors treba ll en 40 hores setmanals, pero en termes de producció, un tr e ba ll ador de classe A equiYal a 40 hores de producció s et mana ls, un de classe B a 30 hores de prod ucció setmanals i un de classe e a 20 hores. Per restriccions sindicals, es pot co ntract ar un maxim de 30 tr eba ll ad ors de classe A i 40 de classe B. A més. els treba ll ado rs de la classe C no poden representar més d'un 25% del total de treballadors contracta ts. La companyia Hindernis vol sa ber quan ts treballadors de cada cl asse ha de cons tr ac tar de forma que s'assegurin les hores de producció de les tasques 1 i II, es sati sfacin les condici ons sindicals i es minim itzin els costos de la nomina de la plant illa. Formuleu un proble ma de programació mat e mática que permeti resoldre aquest proble ma . 6. P l ant ill a compa n yia de correus · Una o fi c ina de correus necessi ta un nombr e difere nt d'e mp leats a te mps compl et (8h) ca da dia de la se tman a. El nom br e d' emp le ats a te mp s complet necessaris ca da dia es mostra en la 4 CoHecció de problemes resolis d ' IrH"es rigació Operati va Determin ista. següe nt taula : billuns JI Dimarts !'' .) Dimecres 1) Dijous 19 Divendres ] .] Dissabte lG Diumenge 11 L'ofic ina de correus pot sa tisfer la seva dema nd a diaria de treballadors amb t r eba ll ad ors a temps complet. ( TT C) o a t emps parcial (TTP). Le s normativos laborals es t. ableixen el segiient 1.- Cada treball ador (ja sigui TTC o TTP ) ha de treballar durant cinc dies consecutius i d esca nsar els dos dies següents. AixO Yol dir que . per exemple , un empleat . que tre balli :..~ de dissabte a dimecres ha de descansar dijous i di,·endres. Un treballador fa semp re el mateix torn) és adir. si una setmana comew;a a treballar el dimart s, cada setn1ana c omen~ara el dimarts. 2. -Els TTC fan una jornada de vuit hores di aries mentr e que els TTP fan una jornada de quatr e hores diaries. 3. -No mé s un 25% del tota l d'hores tr eballades dura nt. la set.mana poden ser cobertes amb TTP. 4 .- Els so us són de 1500 pt s/ ho ra pels TTC i 10 00 pts /hora pels TTP. Formuleu un problema de programació lineal per t rabar 1 'estratég ia de contracta ció que mini-mitzi els cos tos laborals se t manals de l'oficina de correus satisfent les seves necessitats !abarai s di aries d 'acord amb les no rma tives laborals. 7. Composició de disolvents• Qu at.re diso}v en ts han de se r comb inats pera obtenir cert comp o st c¡ uími c. Ca da litre d' aquest compost ha de contenir, coma mínim , 90ml de clor i el seu conting ut en amoníac no pot excedir els 4m l. E1 co ntinu gut en clo r i amoníac de cada di so l ve n t. ai xí co m el cos t. es most.ren en la se gü en t. tau la: disolvents 1 2 3 ~ Clor (mi/!) 180 120 90 60 Amoníac (mi/!) 3 2 6 5 Cost (pt as/ l) 16 12 10 11 Formuleu un problema de programació matem ati ca la sol u ció del qua! proporcioni les pro porci ons en que s' han de mesclar els quatre disolvents per tal d·aconsseguir el co mpo st químic de cost mínim qu e cumpleixi les condicions de contingut en cl or i am oníac indicades a l'enunciat. 8. P aper reciclat• Una planta de reciclat de paper t ra nsfo rm a paper residual en paper r ec iclat. El paper residual pot consi st ir en caixes de ca rtr ó, paper seda, pap er contznu i pape r de /lib res. La palpa pro du ºida s' u sa en la fa br icació de tres ti pus de paper r ec icl at, dit.s de clas se 1,classe 2 i classe 3. Els C1as.--;.c : C!.as-'E : C~as:;_~: Forr.: :.:..ie-- - -= - -: ;=- els cos:.~ ::~ ;:-: :._ 9. P I=:~-~ CSL es ~, se:ve ::~ ~~--= qua!i:::z.;¿ ~ --- ~··- .~ l .... _,,, ~ ; -;;. ~·=:;=e •=;_::_; - ~-= ~ ~ ~=~::.. : '="' '" .::e ~ : ..:al :.J. : :-=·:: ... ;Ca "" .; L !s ,) 1 Pr ob l em es de modelització preus per tona i el contingut en polpa deis quatr e tipus de paper residual són : Caixes cartró Paper seda Paper continu Paper llibres pts / Tm 500 600 80 0 1000 Contingut en po l pa 1 5'7c 20 '7c 30'7c 40 '7c 5 El pap er residual es pot reciclar mitjani;ant dos processos diferents. dits destintat i dispersió d 'asfalt. Les ca ra cte rístiques deis dos pro cessos si ndiquen an la següe nt taula , on la colu mna Polpa pe rduda in dica la proporció de la pol pa con tinguda al paper residual que es pe rd dur a nt el procés, i el pr eu pe r tona pro cessada és el mateix per a qual sern l tipus de paper residual : pts/Tm Palpa Capacitat proc és paper pracessat perduda (Tm / m es ) Destintat 2 000 10% . 3000 Dispersió d ' asfalt 1500 15 % 3000 Les pulpes ob tin gu des a p ar tir deis dif ere nt s tipus de paper residual nom és són aptes per prod u'ir ce rtes cl asses de pap er reciclat. El tipus de paper residual apt e per a cada cl asse de p aper reciclat s indi ca en la següent ta ula , junt amb la quantit at mensual de p olpa apte necessária per a satisfer la dem an da de cada classe de pap er recicl at : Caix es Paper Paper Pap er De manda Cartró Seda continu llibr es (Tm palpa/mes) Classe 1 Apt e Apt e 50 0 Classe 2 Apte Apt e Apt e 50 0 Cl as se 3 Apte 60 0 Formuleu un programa lineal per ta l d 'assolir la de manda mens ua l de pa per reciclat minimi tzant els costos de p rodu cció. 9. Plantilla mobilº C SL és un a ca de na de botigue s de servei té cnic d 'ordinadors. La previsió de demand a de serveis de r epa ra ció pels cinc primers mesas de l 'any, mesurada en hores de treball de tecnic qualificats, s'indi ca en la següent taula : Gen er 1 Fe br er 1 M ar~ Abril Mai g Dem an da (h) 6 000 1 7000 1 8000 9500 11 000 ( Pr evisió demanda reparacions ) Al comern;ament de fe br er tr eba llen a C SL 50 técnics qualificats. Ca da técnic qualificat pot 12 CoHecció de problemes resoles d'lnvestigació Operativa Determinista. • 1.0. · rnaternatiques y 1.0. • Estructures de Dades : programació i matematiques. • Estadistica : matematiques i 1.0. • Simulació: 1.0. i programació. Programació : programació. • Optirnizació : 1.0 . i rnaternatiques. Forrnuleu un problema de prograrnació lineal entera que minirnitzi el nombre d'assignatures necessaries per a obtenir l'especialitat. 25. Models de programació lineal entera . Una empresa esta considerant la possibilitat d'obrir magatzems a quatr e ciutats Nova York, Los Angeles, Chicago i Atlanta. Cada magatzem té una capacitat de 10 0 unitats. El cost fix setmanal de mantenir cada magatzem obert és de 40000pts pera N.Y., 50000pts pera L.A., 30000pts pe ra Ch icago i 15000pts pera Atlanta. La regió 1 del país necessi ta 80 unitats se tman als de producte, la regió 2 70 unitats i la regió 3 40 unitats . El cost unitar i Cij (que inclou la produ cc ió i el transport) de distribució desde el magatzem de la c iut at i fi ns a la regió j és: Reg 1 Reg. 2 Reg. 3 N.Y. 2000 4000 5000 L.A. 4800 15 00 2600 Chicago 2600 3500 1800 Atlanta 2400 5000 3500 Formuleu un proble ma de prograrnació entera que pu gu i ser usat per a satisfer la d ema nda tot minimit z ant els costos se tm anals. 26. Mod e ls de pr o gramació lineal en tera. El tecnic de sistemes del Laboratori de Calcul de la F~lE vol accedir a cinc fitxers diferents. Hi ha copia d'aquests fitxers a diverses cintes de backup tal com rnostra la segü ent taula: Cl:"ITES 3 4 .) 6 7 8 9 10 Fitxer 1 X X X X X X X Fitxer 2 X X Fitxe r 3 X X X X F itx er 4 X X X Fit xer 5 X X X X X X X Tarnany (Mb) 30 50 10 20 10 40 30 10 20 20 Per tal de recuper ar els fitxers primer s'ha de fer un vo lc at de les cintes a clis e dur. Aquest volcat ha de ser de la c int a comple ta , no podent-se co piar només una part de la ci nt a. Formuleu un proble ma de prograrnació lineal ente ra qu e determini el co njunt de c int es a volcar de forma que s'oc upi el mínim espa i en clis e i es poguin recuperar tots els fitxers. 2 Pr o bleme5 ~- :r.:::I!= 2 Pr ob E 27. Resol u ció a) Tr oh~ ~-- b) Tr obec ;::•" e) Tr ob(- e , - infac: :=-= 28. R es oluch5 =C"'"~.-==st.a - . ~:: .. :e: - :'"~~:.:E _ : -=- = _ .1~ ~~ es:t -~ .?= .:=':; eu ! . .:::;¡,,,: =--~ :"::=la 2 Problemes de programació Jjneal 2 Problemes de programació lineal. 27. Resolució grafica de problemes (PL)" Considereu el següent problema de programació lineal (PL): (PL}r z:::: c'x -X¡ +3x2::::: 6 X¡+ X2 :'.'. J 2x¡ - X2 ::::'. 10 x:'.'.0 a) Trobeu graficarnent la solució de (PL) per e'= [ -3 1 J. Classifiqueu el problema. 1 ). Classifiqueu el problema. b) Trobeu graficarnent la solució de (PL) per e'= [-2 13 e) Trobeu el valor del terme independent de la segona constricció a partir del qua! (PL) seria infactible. 28. Resolució grafica de problemes (PL)' Considereu el següent problema de programació lineal (PL): (PL}r z = c1x1 +xz -X¡+ 3x2 ::::: 6 X¡+ X2 :'.'. J 2X¡ -X2 ::::'. JQ X:'.'. Ü / Trobeu graficament la solució del problema (PL) per als diferentes valors possibles de c1. CoHecóó de problemes resolts d'lnvestigació Operatfra Determinista. 29. Transformació a la forma estimdar ' . Tr ¡msformeu el següent problema lineal a la forma eslandar: X¡ -3x2 = -5 6 S x 1 + x2 -5x4 '.S 7 3x, +(X? > 4 ----:rx;- - x1 lliure . x2 ? O, X3 S O 30. Solucions basiques· Considereu el següe nt problema de programació lineal: l mm z = 5x¡ + 3x2 + X3 s a ( PL ) X¡+ x2 + 3x3 S 6 5x1 + 3x2 + 3x3 S 15 x;::-o a) Trobeu tetes les soluciones basiqu es factibles de (PL). b) Tr obeu totes les solucions basiques no factibles de (PL) . 31. Solu cions basique s' Trobeu tot es les solucions basiques factibles deis següents problemes: a) ( PL) 1 m~na. :x~ :x~2-=x: X¡+ X2 '.S 4 X¡+ 2X2 '.S 5 x?O 32. Fase I' b) (PL) min z = -4 x1 + x2 s.a.: 3X¡ + Xz = 6 - X¡+ 2Xz $ 4 X¡+ 2xz '.S 5 x?O Considereu un cert pro bl ema d'optimització am b una regió factible definida per les constricci ons : 2 Prob lemes :;_ !' - Ca lcule:_ : 33 . Sim pl ex _ . ::=.i Sigui el -:-: - ~ a) Resoleu P:. in cial fac :. - ~ := b) Conside:ó_ ~ :- de la :o:::=:-.. fase 1 y :=::""' 34. Sim plex p= Resoleu ic. ~- (P _ 35. Anhl isi de -- - Cer ta i nri~ --:!. ~ con su meixen C:e · demanda D no c.:~ s ón , r es pectiva::::.:s. _ =~~-:::w:us !a . ) ~~ cons2 Probl em es de prog r am a.c ió line al X¡ + 3/ 2x2 $ J2 4x 1 + 2 x2 $ 8 X¡ + X2 2: 5 X¡ , X 2 2: 0 Calculeu, si existei x. una solució factible d'aquest problema. 33. Simplex primal en forma matricial i fase r Si g ui el problema (PL) se gü e nt : (PL) x: : '. ¡ m ax Z = X¡ + 2x2 2x1+ x2 :::; 3 X¡+ X2 $ 2 X 2: 0 15 a) Resoleu (PL) apli ca nt l'algorisme del simplex primal en forma ma tricial a pa rt ir de la base incial factible Bº = {! , 2). b) Considereu el prob le ma (PL) que s'o bt é a partir de (PL) substituint la desigua lta t "$"' de la pr imera con str i cc ió per " 2:" . Ca lculeu una base in ic ial factible de (PL) aplica nt la fase 1 del símplex primal en forma tab ular. 34. Simplex primal en forma matricial• Resoleu el segü ent problema amb l'algorisme del simplex primal en forma ma tri cia l: max z= 14x1 + 12x2 + 3x3 subj.a : ~ X ¡ + X2 + jx3 $ 11 25 (PL) { X¡ :::; 1000 X 2 $ 500 X3 $ 1500 X¡ Xz X3 2: o 35. Anhlisi de solucions • Cer ta indú stria fa br ica els productes A, B i C. En la fabricació d'aquests tr es produ ctes es co nsumeixen dos ti pus de recursos, Rl i R2. A més, !'empre sa s' ha compr om es a sa tis fe r una de ma nda D no inferi or a 15 unitats. Els costos de fabricació d'una unit at de producte A, By C són, respec ti v am e nt , 10, 2 i 3 milions de pessetes. El probl ema lineal (PL) que per me t calcular 16 CoHecció de problemes resolts d'lnvestigació Operativa Determfoista. l es quantitats de producte A (x1 ), B (x 2) i C (x 3) que minimitzen els costos de producció és: min z= l0x 1 + 2 x2 + 3x3 sub j.a: 3x 1 + 2.r2 + .t3 ::; 20 RI (PL) X¡ + X7 + Zx3 ::; 40 RZ X¡ + x, + X3 ::'.'. 15 D X¡ x, X3 ::'.'. o a) Sense realitzar cap iteració del metode del simplex. comproveu que la producció óptima correspón a la base B = {2 , 3, 5) , sent x5 la folga de la re str icció R2. La inversa de la base és: 31 = [~1 ~ ~ 1 ] 1 -3 b) Formuleu el dual de (PL). Calculeu el ,·alor de les variables duals i comproveu que el seu signe coincideix amb el que apareix en la formulació del problema dual. c) Suposseu que, per problemas economics, hem de reduir les despesses de fabricació en 10 milions de pessetes. Si la disponibilitat deis recursos no pot ser modificada, Quina repercussió té aquesta mesura en la demanda que podem satisfer? d) Quant hauria de disminuir el cost de fabricació del producte A per tal que íos convenie nt la seva producció?. e) Formuleu el tableau optim de (PL) sense realitzar cap iteració del simplex. f) Suposeu que hem aconseguit reduir els costos de producció de A fins a un valor c1 = 1/2. A partir de la solució optima de (PL) , reoptimitzeu per al nou valor de C¡ 36. Anhlisi de solucions • Una certa industria fabrica els productes A, B, C i D. En la fabricació d'aquests tres product es es consumeixen tres ti pus de recursos, Rl, R2 i R3. El benefici unitari deis productes A, B, C i D és, respectivament, de 200, 400. 100 i 100 pessetes. El problema lineal (PL) que permet calcular les quantitats optimes deis productes A (x¡) B (x2), C (x 3) i D (x 4) que maximi tzen els beneficis és: min z= 2x1 4x 2 X3 X4 subj.a: X¡ + 3x2 + X4 ::; 8 Rl (PL) 2x1 + x, ::; 6 R2 x, + 4x3 + X4 ::; 6 R3 X¡ x2 X3 X4 ::'.'. o 2 Probl emes e~~ La bas e opt :;:;: " - ' a) b) Constru l:.: -:.• =- c) Dins de q,_:, -J base s· e~ ? :_ d) L'empr esc"' ~ 1 variable = s ::- recursos ;:--e-: - a 8 = [10 - ~~ E? 37. Ana lis i dE ;._ En el p e e : .~ r ( P:. el valor a ro;::.;;:¡ =-~ a) Quines va.:¿_: _.,, b) Qui ns vC.:c,.; : : l c) Si a les e"'=> - una c ol~i ..:el' Op t im e=:: - _:l'~ 38 . Carb oas Certes =::-~ 1 mescla puh ·== es dedica a la ;:-=•.:- Hulla , Antrc c: : so/re 1 m es u ::- a: ~ per tona de e.a : :·: següent ta ula ~ ~~-..ii~.o.:. . n,a. _ ~-"""::·.::::-.: :.¡e =:;; ..) e :: ;. ¡~ _ ::-ia :---:: _.=_ :a.se =-;;:: <:;,.;= -- !:. : : m1 - ~-===~=6 ==.!-:- ::Ji 2 PL) qt:e \ 2 Pro blemes de programació lineal La base óptima d 'aq uest problema és s· = { 1, 3, 2}, i la inversa de la matriu basica és: [ -1 /5 B·- 1 = - 1/ 10 2/5 3/5 1/20 - 1/5 +J 17 a) Enun ci eu el teorema de la folga complementária. Use u aquest teorema per a dem ostrar la op timalitat de la base s·. b) Co nsidereu un nou proble ma lineal (PL) ex act am e nt igual al problema (PL) pero amb totes les constriccions formulades coma con str i cc ions d'igualtat. Formuleu (sense resoldre) el probl ema art.ificial (PLa) que pe rm et obtenir una solució basica factible inicial de (PL) . Const ru 'iu -ne el tabl eau del simplex inicial de (PL 0) c) Dins de quin marge de valors de b2 (disponibi li t at del recurs R2) continua sent ópt i ma la base B' de (PL) ? Quina és la solució óp tima si b2 = 20. d) L'e mpresa es plan te ja la possibilitat de produir un nou producte E, que associarem a la variable xg . El bene fici unita ri per ve nda d'aq uest producte és de 800p tas . El co ns um de recursos per unit at de producte produi't depén d'un cert parámetre e i ve dona t pe! ve c tor as = [ 1028 208 1 - 58]'. A partir de quin valor del parametre 8 interessa produir E? 37. Analisi de so luci ons • En el problema de programació lineal: min z= 2x 1 + c 2x 2 + 4x3 + C4 X4 subj.a : X¡ -2x2 ::; g (PL) ~ 3x 1 + 2x2 - X3 + 6x4 '.S 2 X¡ + Xz + X3 + X4 = 6 X¡ Xz X3 X4 2'. o el valor a l'óptim de les variables és xj = 2, x2 = O. xj = 4, x4 = O. a) Quines variables formen part de la solució basica optima de (PL), i quin és el seu valor? b) Qu i ns valors poden tenir c2 i c4 per tal que la sol u ció indicada sigui opti ma? e) Si a les constriccions i funció objectiu hi ha gués una nova variable x5 de co st c5 = 3 i a mb una co lumn a de coe fi cients a5 = [ 8 O 1 ]', determineu si aqu esta variable seria basica a l 'optim del nou proble ma plantejat. 38. Carbons d'Espanya S.A.• Certes centrals te rm iques de producció d'energia electrica usen com a combustible una me scla pu lve rit zada de diferents classes de carbons. L'empresa Carbons d'Espanya S.A. (CESA) es dedica a la produ cció de carbons mesclats a partir de quat.re tipus de carbons basics, Ligni t , Hulla , Antracit a i Torba . Le s característiques pr in cipals d'aquests carbons són el c on ti ngut en so/ re , mesurat en ta nt per ce nt de la massa, i la capac it at energetica , mesurada en quil otérmi es per to na de ca rbó. Les caracteristiques deis quatr e carbons basics. i el seu pr eu s'indiquen a la següe nt taula : 18 CoHecció de problem(".S resolts d'Investigació Op e rativa Determinista. Contingut Capacita t Pre u Tipus de Sofr e energ€tica compra Carbó (%) (Kth / Tru) (10·1 pts/Tm) Lignit 2.0 4 o 25 Hulla 3 o 2.0 30 Antracita 05 0.8 20 Torba 7.5 0.5 10 ( Ca ra cte rí st iques de is carbons basics ) Les característiques ex igides al carbó de mes cl a <l epen de les normatives de cada estat. Fer a la Com unitat Económica Europea (CEE), Estats l" nits (EUA), i Japó són les següents Contingut Capa ci tat Sofr e energ€t i ca Estat (%) ( Kth / Tm) CEE ::; 1.5 2'. 2 o EU A ::; 1.1 2'. 1. 5 Japó < 2.0 > 2.5 ( Normatives estatals del carbó de mescla) El mercat de CESA es re st ringeix de moment a la CEE. EL programa lineal plantejat pel departa ment d'lnvestigació Operativa d'aquesta empre sa per trobar la proporció de mescla óptima és : mm z= 25x 1 + 30 x2 + 20x3 + l0x4 s ubj .a : 2x1 + 3x2 + 0.5x3 + 7.5x 4 ::; 1. 5 (PL) 4x1 + 2x2 + 0.8x3 + 0.5X4 2'. 2 X¡ + X2 + X3 + X4 x, Xz X3 X4 2'. o a) Ac tualment, les proporcions de mescla que CESA fa servir són x, = 0.290323, x2 0.225806, x3 = 0.483871, x4 =O. Demostreu als responsa bl es de producció qu e aquesta no és la millor proporció po ssible. La inver sa de la base 8 = { 3, 1, 2} és: [ -032258 -0 .1935 0.5161 - 0.16129 0.40322 -0 .24193 1.29032 ] -0 .22580 - 0.06451 b) Usa nt un paquet de programació lineal heu resolt el pr oblema (PL). obtenint el següent tablea u óptim : se nt la ;;:-.7--: :l. A par u: ::~ 1. 5sí rn plex pa garien :::: :-;:: - int ernac:::=.=-. -=' ha u r ia c·ex; :- !.: 39. I nd ust rial ::.: - Industria, :.• ' fo r ma tge u~-~=· de ca bra i de :,.: - :::.< t.aula: Ll et cabra Llet º'·ella A m és . pe 1 ~ a mínim. sba.:: :. ~ la produ cci ó e~- - ' ~.....UU.S td . .J · :.;¡.,:.,~ ~:~: Per J,,,rfó.==.:.o a.~.-a.. ::¿__:_:ejat : :.= :::,,;.da < .: 7 = -· =.. sey;:!ent / 2 Problemes de programadó lineal 19 X¡ Xo - X3 X4 - X5 X6 o 0.328 1 o -0.153 0.241 0.558 r· = 1 0.400 o o 0.013 -0.306 0.381 o 0.271 o 1 0. 1 40 o 066 0. 061 o 10.711 o o 1.335 2.188 -21 .291 se11t la inversa de la base opt i ma B· - 1 = 0.01312 0.30634 -0.251 64 [- 0. 15317 -0 .24070 1.26914 ] 0.14004 - O 06564 -0.01750 A partir de la solució de l 'a pa r tat a) arribeu a aq uesta solució iterant amb l 'a lgorisme del símplex. e) Cenyint.-nos a la produ cc ió p era la CEE, si CESA tingués l'opció de comprar a 150000 pt s/ Tm un nou tipus de carbó basic amb un 1% de contingut en sofre i l Kth/Tm, int eressaria canv iar la proporció de mescla Opti ma co rrespone nt a T* per incloure aquest n ou carbó? Just.ifiqueu la resposta. d) CESA vol ampliar el seu mer cat i es planteja exporta r als EUA i al Japó , acomodant les característiques del carbó de mescla a la legislació d 'aqu est estats. Tots dos paissos pagarien a CESA el mateix preu per tona de ca rbó de mescla. Si , per raons d'estrat .égia internacional, només es vol exporta r a un d'aquests dos pa!ssos, a quin deis dos pa .issos hauria d'e xp or ta r CESA? Just ifiqueu la respos ta . 39 . Industr ial de Formatges S.A.• in dust rial de Formatges S.A. (IFSA) és una e mpr esa que es dedi ca a elaborar tr es tipus de formatge uti ll itzant ll et de cabra i d'ovella. Per al proxim mes es disposa de 850 li tr es de llet de cabra i de 900 de !! et d'ovella. Els coe fi cients tecnologics i els costos s'indiquen a la següent tau la: Fo r matge 1 (x¡) For matge 2 (x2) Formatge 3 (x 3) Quant. Cost Quant. Cost Qu ant. Cost Pts. /litre ( l. /formatg e) (Pts) (1./formatge) (Pts) (1. /formatge) (Pts) Ll et cabra 20 5 100 2 40 1 20 Ll et ove ll a 10 1 10 2 20 4 40 Altres cos to s 50 50 100 Total cos tos unit . 160 1 10 160 Preu venda uni t. 190 170 180 Bene fi ci unitari 30 60 20 A mé s, per a ga r antir els !loes de tr eball que té !'empr esa, la dire cc ió ha dec idit que, com a mín im, s'han d' elabo r ar un total de 400 formatges. El programa lin ea l que permet ca lcular la producció optima és: 20 CoHecció de probl em es resoles d'lnl'estigació Operatfra Determinista. min z= 30x1 60,-, 20.r3 subj.a: 5x 1 + 21·~ + X3 ::; 850 (PL) X¡ + 2r :,i + 4x3 ::; 900 X¡ + J.':_¡ + X3 2: 400 "1 ,. , X3 2: o La resolució de (P L) proporciona la planificació de producció óptima que es dedueix de la següent taula: X¡ x2 X3 X4 X5 J. ' I) 3/ 2 o -1 /2 1/2 o 1 25 -4 o 3 -1 1 o 50 5/2 1 1 /2 1/2 o o 425 120 o 10 30 o o 25500 a) Ens of ereixen la poss ibilitat de co mp rar ll et de cabra per sobre deis 8501 inicials a 60 pt s/ li tre. Estariem disposats a comprar ?. Qu in és el pr eu m 3.xi m qu e est arien1 disposats a pagar per un litre addicional de llet de éabra? b) Es modificaria d 'a lguna forma la planificació de la pr od uc ció si no es tingués en co mpt e la tercera constricció? Raoneu la vostra resposta. e) Si el preu de venda del formatge 1 passes a ser de 320pts, quina se ri a la nova pl anificació de pro du cció óptima? d) Sot a quina ci rcu mstancia es podria obtenir una planificació óptima on es produissin conjuntament el formatge de tipus 2 i el de ti pus 3 sense que es modifiques el ben efic i total de la solució actual? 40. Cornpanyia petrolífera ASPEC. • Una companyia petrolífera ASPEC ha de determinar la producció ópt ima diaria, en dm3 /di a, de pe tr oli cru (xi), fue! de qüal it at baixa (x2) i fue! de qüal itat alta (x 3) . Per a obtenir els valors ópt ims de X¡ , x2 i x3, el depa rt ament d'lnvestigació Operativa d'ASPEC ha formulat i definit dins del programa LINDO el següent programa li neal: MIN - O. 5 XI - 2. 5 X2 - 3 X3 SU BJECT TO END REF.) EMB.) DEM.) X I+ 0 . 75 X2 + X3 <= 12 -+- 1.5 X3 <= X2 + X3 = 20 10 on REF. té en compte la capacitat maxima diaria de la planta de refin at de la companyia, en hor es/dia, EMB . indica la ca pacita t, també en hor es/ dia , de la pl anta d'embassat deis productes. Fi nalm e nt, DEM. indica la de man da diaria conju nt a deis tr es productes. El valor de la funció objectiu represe nta els beneficis diaris de ASPEC, canviats de signe, en milions de pt.s. La solució que proporciona LINDO a aque st problema é s: 2 Pr oble mes é~ ~ LP x; ~' :rJ.: '"'' e~ .., N O. r:~~ :::::i:::" THE. H.3:.....;.J. 7 RO 'ri ' ~~ 1 .t.:. : REF . ~ E M3 . o:..I l DEM . a) ASPEC "' ; ,_ ref\!,at 0" :i seva - ca;:a:..~ · = de pes:..¿ ;::; ::_ E: fu e! pro;~:: -- - refin at ~ : :. .: ~ 10 dm3 ::...>. - 4 1. For mul acié :::.: Formule_=.. - a) 42. F as e I i ,~- - Cons ide._~- .,.. ""1 .=e'"...c:-__..¡:_ut a. ·--=-=-=~ ¿tla ) ..:...:::.L5 a 60 ~:..:----;-::c.2.ts a ~ :::::;::~e la ::..a. ~!s - : -~~ ;.:Xx::cr.es. ~ 2. :'::nció 2 Problemes de programació lineal LP OPT!MUM FOUND AT STEP OBJECTIVE FUNCTION VALUE 1) -28 000000 VARIABLE VALUE REDUCED COST Xl . 000000 . 500000 X2 4. 000000 . 000000 X3 6. 000000 . 000000 ROW SLACK OR SURPLUS DUAL PRICES REF. ) . 000000 2. 000000 EMB.) 7 . 000000 . 000000 DEM.) . 000000 1. 000000 NO. ITERATIONS• i el tableau associat a aquesta solució és: THE TABLEAU ROW (BASIS) Xl X2 X3 SLK 2 SLK 3 1 ART . 500 .000 .000 2 .000 .000 REF. X3 -3 000 . 000 1. 000 4 000 .000 EMB. SLK 3 .soo .000 .000 -2 000 1. 000 DEM. X2 4.000 1.000 .000 -4 000 ·ººº 28. 000 6.000 7 000 4 .000 21 a) ASPEC es planteja la possibilitat d'invertir en millores en una de les dues plantes, la de refinat (REF.) o la d'embassat (EMB.). L'ampliació de la planta de refinat augmentaria la seva capacitat del valor actual 9 h/dia a 9.5 h/dia i necessitaria una inversió de 1.5 milions de pessetes. L'ampliació de la planta d' embassat també requereix 1.5 milions de pessetes i augmentaria la seva capacitat del valor actual 20 h/ dia a 22 h/ dia. Indiqueu a quina planta interessa realitzar la rnillora i per quina raó. b) ASPEC es planteja la producció d'un nou fuel de molt alta qüalitat. La venda d 'aquest fuel proporcionaria uns beneficis de 6 milions de pessetes per dm 3 venut, necessitant 2h de refinat i 1.5 d'embassat. La demanda conjunta deis quatre productes continuaria sent de JO dm 3 /dia. Interessa la producció d'aquest nou fuel? 41. Formulació de problemes dualsº. Formuleu el problema dual deis primals següenls: a) (PL) ¡ ~':. z = 2x1 + x2 X¡+ X2 = 2 2x1 - X2 2'. 3 X¡ - X2 '.:Ó J X1 2'. Ü b) (PL) 42. Fase I i simplex primal i dualº mm s.a.: z = 2x 1 + 4x2 + 6x3 X¡+ X2 + X3 2'. 2 X¡ - X3 2'. J X2 + X3 = J 2X¡ + X2 '.:Ó 3 Xz , X3 ~ Ü Considereu el següent problema de programació lineal : ~~.t.errni n i st - a. \ \ !!Xplora nt .::L=:: '. e u 1 es 3 Problemes de programació lin ea l entera 29 51. Resolnció amb el simplex dual • Consid e reu el següe nt prob l ema de programa ció e nt era: ¡ m i" z= - X¡ - Xz X3 (PLE) subj. a: ~XJ x2 ~ ~X2 + X3 ~ X¡ X2 • X3 2'. O. ente r as Resoleu el problema (PE). El tabl ea u ópt im de la rel axació lineal de ( PE ) és: X¡ X 2 X3 J.' .1 X 5 1 o 4/3 2 4/3 34/ 3 o J 2/3 o 2/3 8/ 3 o o J 2 2 14 52 . Resolució amb el simp l ex dual • Resol eu el s eg ü ent pr ob lema de prog r ama ció e nt era : min X¡ x , s.a. : X¡ + X2 ~ 5 (PLE) { 5 x1 + x2 ~ 15 X¡ + X2 ~ 3 X¡ 2: Ü Xz 2: Ü enteres El tabl ea u ópt im de la re laxa ció lin ea l de (PLE) és : X1 X "> X3 X4 X5 ~ o 1 5/ 4 - 1/4 o 5/2 T?RI 1 o - 1/4 1 /4 o 5/2 o o - 3/2 1 /2 1 3 o o 1 o o 5 Escolliu co m a variable de ramificació la variable r ea l amb valor no e nt er d'índ ex menor. R eso leu l es re lax acio ns lin ea ls amb l 'algorism e del s ímpl ex dual. \ 4 Pro bl em es de progr ama óó no lineal 31 4 Problemes de programació no lineal. 53 . Mínim a nalític• Trobeu analíti ca me nt la solució deis següents problemes d'optimització sense constriccions. ln diqueu si existeix sol u ció, si aq ue sta és única, i el seu carácter {minim l oca l, gl oba l, estr ic te , ... ): a) mi nf(x) = xi+ X ~+ X~ -X¡ X2 + X2X3 -X ¡X3 b) minf(l :) = e.ri-.ri + er 2 -r 1 + e .ri + x5 c) minf( x) = e•i -r , + e•2 -r1 d) minf(x) = e•,-r, + e•1 +•0 54 . Dir ecc ions de d esce ns Considereu el probl ema d'optimització no lineal amb con st riccions següent : {PNL) min f( x1 ,x2) = x1 x2+{x1-x2) 3 s.a: x1 2: O, x2 2: O Dieu si les direccions d1 = [ -1 1 ]', d2 = [ 1 2 ]', d3 = [ 3/2 2 ]' són factibles i de descens a partir del punt xº = [O 1 ]' pe! proble ma {PNL) . Justifiqueu la vostra resposta. 55. Dir ecc ions de d escen s• Co nsidereu el probl ema d' optim ització no lin ea l amb constriccions següe nt : {PNL) min f{x1 ,x2) = {x¡ - 1) 2x2 + (x2 - x¡) 2 s.a : x1 2: O, x2 2: O Dieu si les d ir e cc ions d1 = [2 ü]', d2 = [ -2 !]', d3 = [2 2]'. són factibles i de descens a partir del punt xº = [ 1 O]' pe! problema (PN2). Ju stifiqueu la v ost ra resposta. 56. M et ode del grad i ent i e xpl oració lin eal de Fibona cc i R ea li t ze u la primera it eració del métod e del gra dient apli cat a la resolució del pro ble ma : {PNL) min f(x¡ , x 2, X3 ) =xi+ X ~ - X ~+ X¡X 2 X3 32 CoHecció de problemes resolts d'Investigació Operativa Determinista. Preneu coma punt inicial x0 = [~],coma tolerancia de detecció d'optim e= 0. 1 i feu exploració lineal aproximada per Fibonacci amb N = 4 i interval d'incertessa inicial [0,1]. 57. Metode del gradient i exploració lineal de Fibonacci' Realitzeu la primera iteració del métode del gradient aplicat a la resolució del problema: (PNL) min f(x) =xi+ x~ - (xz -x3)3 + x1 x2r3 Preneu com a punt inicial x0 = [ ~:] , com a tolerancia de det.ecció d ' optim < = 0 .1 i feu explo ra ció lineal aproximada per Fibonacci amb N = 4 a l'interval inicial d' incertessa [0,0 .. 5]. 58. Metode del gradient i e xplor ació lineal de Fib onacci Co nsidereu el següent problema d 'optimització no lineal sense constriccions : (PNL) min f(x1.x2) = X¡X2 + (x¡ - X2) 3 Feu la primera iteració de 1 'algorisme del gradient aplicat sobre el problema ( PNL) , pren ent co m a punt inicial xº = [ 1 1 ]', com a tolerancia de det ecc ió d'optim < = 0.5 i feu exploració lineal aproxim ada per Fibonacci amb N = 3 i interval inicial d'incert.esa (0,3]. 59. Metode del gradien t i exp lora ció lineal de Fibonaccil Considereu el següent probl ema d 'optimització no lineal sense constriccions : (PNL) min f(x¡ , x2) = (x¡ -1}2 x2 + (x2 -x1 )2 Feu la primera iteració de l' algorisme del gradient aplicat sobre el problema (PNL) , prenent com a punt inicial x0 = [ 1 2 ]' , com a to lerancia de detecció d 'opt im < = 0.5 i feu exploració lineal aproximada per Fibonacci amb N = 3 i int erval inicial d'incertesa (0,1/2]. 60 . Metode del gradient i exp lora ció lin eal exacta i per Fibonacci• Donat el següent probl ema d' optimit zació no lin ea l sense constriccins: (PNL) min f( x) =xi+ ~x~ + 2x1x2 - 2x1 -2x2 a) Efectueu una passa compl eta del metode del gradient, partint de x0 = [ -1 O]' , amb tolerancia de detecció d'opt im e= 0.5 i fent exploració lineal exacta. b) Feu exploració lineal de fibonacci a partir del punt x = ( - 1 O]' en la direcció d = [ 4 4 ]' amb N= 4. 61. Metod e del gradient i taxa de convergencia! Co nsidereu el proble ma ( PNL) co nsistent en la minimització de la funció f(x) = 2xi - 4 Proble mes ~ xi+ r ¡r 3 - 3 =: \ =• a) Efectuec _:¿ - ' li neal ex ,,. :;.;.. b) C ons ié e : ~- Cc on\ · e:-seés la c) Ca lc ule~ (P. ºLJ 62 . Cor bes <!!.::.. C ons ide : ~- i objectiu f :r = ? = J diferencia ble ~ ~ -- - - a) A qu in ;:_ ::.; = ~ b) Ca lc ulec ~ c) A la v io:"-= ~ 63. F or mul aci · - -<' Form ! e _ . ~ d' optim itza :i : ::_: amb f : :=:' -E 64. Cond icio ns Cr Conside:e_ ~ a) b) Formuleu :"" -- • c) ~·".:-~ ~=~mi s1.-a . ,..... ' = (\ 1 i íeu liil..:n;;.:-_:.... -· ,_ ,_ .. ;::.::¡:: rema: - < = é 1 i feu ...,,..~:c.P .. oL ?:\L) . pre- = : ::, i feu =- :: 3: ~~!$! \ •)' ?IEfeu a:nb ~ •I ·' - -= ~ ·- 4 Prnblemes de progra.maóó no lineal 33 x; + X1X3 - 3x'> + X3. ~) Efectueu u-na passa de l métode del gradient a partir de x0 = [ 1 1 1 ]' amb exploraci ó lin ea l exacta. b) Considereu que l'aplicació del métode del grad i ent en Ja resolució de ( PNL) a pa rti r de x0 convergeix a un punt extre m x· . És x· la solució del problema (PNL)? Per qu e? Quina és la solució del prob lema (PNL)? c) Calcu leu la lita supe rior a la taxa de convergen cia (3 del mé tod e del gr ad ie nt ap li ca t s obre ( PNL). 62. Corbes d ifer enciab l es '. Consider eu la constricció no linea l d'igual tat h(x~ = O amb h(x ) = xi - x2 i la funció objec tiu f(x) = ex,¡r, + ll. Sigui S la superficie de IR. - definida per h(x) =O i x(I) la co rb a diferenciable de S que té x1 (t) =t. a) A quín punt de IR. 2 corr espon x(O)? d b) Calcu leu el valor de dtf(x(t)) pe ra t =O. { rnin f(x) e) A la vista del resultat anterior , pot ser x (O) un punt est ac i onar i del pr oblema ? s. a: h(x) = O 63 . Formula c ió de les co ndicions de Kuhn i Tucker' Fo rmuleu les condicions neces sá ries de p rimer ordre de mínim l oca l del següent problema d' op timit zac ió no lin ea l : minf(x1, xz) s.a. :9 ¡ (x¡, x2) S b1 9z(x1, x2);::: b, X¡,Xz;::: Ü amb f : IR. 2 -IR, 91 : IR. 2 ~ IR i 9 2: IR. 2 ~IR 64. Condicions de Kuhn i Tu ck er' Co nsidereu el següe nt probl e ma de pr og r amac ió no lin ea l: r" f(x) = (x 1 -1)2 + (x 2 -2)2 (PNL) s ubj . a: - X¡ + X2 X¡ + Xz X¡ x, ;::: - 1 ::; 2 ;::: o a) Supos em que s' ha trobat una so lució fa ctible (PNL) qu e sat isfa les cond ici ons n ecessá ries de p rim er or dr e (c ondicions de Kuhn i Tucker). Qu e podem d ir so bre el ca r áct er de mí nim l oca l o global d' a questa so luci ó? Ju stifiqueu la vostra res po s ta . b) Fo rmuleu les cond icions de Khun i Tuck er del pr ob le ma (PN L ). c) Resoleu el pr ob lema (PNL) usant les condici ons de Kuhn i Tucker, s abe nt que a l' opt im CoHecció de prob/eme s res olts d 'Investigació Operati\'a Determinista. es sa tisfá qu e x1 > O i x 2 > O. 65 . Condicions de Kuhn i Tuéker• Considereu el següent proble ma de programació no linea l: { min (PNL) s.a: f(x ) = (X ¡X2 - 3)2 - 4x1X2 + 2(X ¡ X3 -1)3 - lfx 2 + 5 x3 6x1 -3x2x3 - x5 -5 '.S O x1 + 1x2 + .r~ -4 :S O a) Formuleu Is condicions de Khun i Tucker pe! proble ma (PNL) . b) Comproveu si el vector x' =[O -2 l] pot ser un míni rn local del proble ma (PNL). 66. Condicions de Kuhn i Tucker Considereu el següent problema de programació no lin ea l arnb constriccions : (PNL) min f( X ¡, x2) = X¡X2 + (x ¡ - X2) 3 s.a : (x1 +l)(x 2+ l ):S3 X¡ :'.'. Ü, X 2 :'.'. Ü a) Comproveu, a partir de les condicions de Kuhn-Tucker si el punt xº = [ 1 1/2 ]' és un rnínim local del problema (PNL) . b) Tenint en compte la regió factible de (PNL) , podem dir que es tracta d'un proble ma de program ac ió convexa? J ustifiqueu la vostra resposta. 67. Condi c ions de Kuhn i Tu cker i programació convexa · Cons idereu el següe nt problema de program ac ió no lineal amb constricci on s : J min (PNL) l s .a: /(x1,x2) = (x , - lf x2 + (x 2 - x, )2 (x1 + J)(x2 + !) + 2xf + 2x~ :S 4 X¡ :'.'. Ü, X2 :'.'. Ü a) Formu le u les co ndicions de Kuhn-Tucker pel probl ema (PNL) . b) Comp roveu, a partir de les condicions de Kuhn-Tucker si el punt x0 = [O 1 ]' és un mínim local del probl ema (PNL) . c) És (PNL) un problema de programació convexa? Just ifiqueu la vostra resp ost a. 68 . Condicions de Kuhn i Tu ck er i pla tan gent • Considereu el problema d' opt imització no lineal següent : min s.a. f(x) = e' •(r,+1) xi -X 2 $ -Q 2xf - 2xf -x2 + 1 '.S O Prnble mes d !' ,;::.-:::~ a) Co nsider !:' _ : V A P .: ~ ~ :2 .. ~- b) Us a nt la:.::::::- és un :=:.::: .: -.:..... - e) Tr obeu u.::~ :.>...""' • - 69. Con di cio ::i ~ ::.= '°" Co nsid e-ce~ =· : 70. Co n di ci oru O:;; - - Consi de r e:.. !:'. ~f La solució =· grange as socia: ,I' 71. As su mp c ió e<= ?' Considereu e. "'T'"' ~...-a :kl.ermini st a. - :.- ...:.. , ::, .: ;:_ P :\ L}. ~-;:.~ ~~, és un - ; c:>tle:na de \ - ~..:: . ::.:J"!Í:lim l ;:5:~ . :.¿_ 4 Problemes de programació no lineal 35 a) Formuleu les condidicions necessaries de primer ordre de (PNL). lndiqueu el procediment que s'hauria de seguir si es volgués resoldre (PNL) a partir d 'a questes condicions. Quina seria la dificultat més rellevant d'aquest procés? Considereu que GINO mostra la següent informació associada al punt i: OBJECTIVE FUNCTION VALUE 1) . 529462 VARIABLE VALUE REDUCED COST Xl -.455418 .000000 X2 .396285 -.000007 RO\I SLACK OR SURPLUS ?RICE 2) .188880 .000000 3) -.000009 -.241119 b) Usant la informació proporcionada per GINO, indiqueu si el punt i = [ -.455418 .396285 ]' és un mínim local de (PNL). c) Trobeu una base del subespai tangent de les constriccions actives sobre i. 69. Condicions de segon ordre" Considereu el problema d'optimització no lineal següent : (PNL) s.a. ¡ mm J(x) = e'''''+lJ xi -xz ~O 2xy - 2xi - x2 + 1 2: O Comproveu si el punt x· = [-1/2 1/4] és solució del problema (PNL) . 70. Condicions de segon ordre· Considereu el segent problema d 'optimització amb constriccions: (PNL) { min xElR.3 subj. a; j(x) = X¡X2 x3+ 1 h(x) =xi+ xlX3 -1 =O La sol u ció x· = [ 1 1 1 ]' és un punt estacionari de (PNL) amb multiplicador de Lagrange associat >,• = [-1/4]. Comproveu si x• és maxim. mínimo punt de sella de (PNL). 71. Assumpció de complementarietat estricte Considereu el següent problema d'optimització no lineal de dos variables: (PNL} { mm .rER 2 subj. a: 1 ? ? f(x) = 2(x¡ -x2) x2 ~O .36 Col-lecció de problemes resolts d'lnvestigació Operativa Determfoista. Comproveu que x .. = (O O]' i µ .. = O satisfan l es condicions suficients de segon ordre de n1inim local, excepte l'assumpció de complementarietat estricte. És x• un minim local de (PNL) ? 72 . Gradient redult generalitzat' Considereu el següent problema d'optimització amb constriccions: nlm subj. a: (PNL) ? X1X- -Tx,xs + 3x, - 6x2 - 4x 3 - 4x• xi -f + X2 - X3 + 2X4X5 - X5 = - 2 3xT 3x~ 7 2 + X2X3 - 2 x 2 + 2 + X5 = 2 0$X$ [4 4 4 4]' Efectueu un pas complet del métode del gradient reduit generalitzat a partir del punt X0 = [ 1 O 3 1 1/2]', trobant: el gradie nt reduit, la direcció d' exploració, la passa máxima i, prenent coma passa optima la meitat de la passa máx ima , un nou punt . A continuació efectueu una pas sa de projecció del nou punt sobre al hipersuperfície de les constriccions, segons el procediment del metode. Comproveu que la direcció d'exploració obtinguda és de descens. 73. Gradient redult generalitzat. Considereu el següent problema d'optimització no lineal: i la sol u ció factible x0 = [ 1 1 ]'. j(x ) = X¡X2 X3 -1 xi+ X~ - X3 = 1 3x 1 + ~ < 5 2x3 - a) Comproveu si el punt X0 pot ser un optim local de (PNL}. b) Ca lculeu la direcció de descens a partir de Xo segons el métode del Grad i ent ll ed uú Gene ralitzat (GRG) . c) Si s' it e ra a partir de x0 segons el metode del GRG prenent a· = ó/2 sºobté el punt x1 = (1 5/4 15/8 1 /2]'. Realitzeu una passa del procés de projecció de x1 sobre la hipersuperficie de les constriccions que ap li ca el metode GRG. 74. Gradient redult generalitzat . Considereu el següent problema d'optimització no lineal: f(x) = X¡Xz X3 +] xi+ X ~ - X3 = 1 3x 1 + ~ < 5 2x3 - 4 Probleme.s de ;:--.:~ a) En un cieu .a -:.. veu aques:~ .:_ b) Si s ·aplica - - '- lon g i t ud::~-:=..:. Ef ectuec variables :~:~ - Je<:~""CJni sL.a . · - _:..~::e :i~ínim . ~ P:"L )? ¡::-..i:ssa ==~"t!:-:1a i. ~- ·-:.,,: ~:e-ctueu ·---_... ~::. ::i~ el ~:e~=-~ . ~ - "- . e~ ~\"·""- -- •, :.:. ~e. ;.:.:m :!" :: · >==:-e la 4 Problemes de programació no lineal a) Enuncieu la condició d' aturada de l'algorisme del Gradient Reduú Generalitzat. veu aquesta condició pe! problema (PNL) sobre la solució factible x• = [ 1 1 b) Si s'aplica una passa del metode del GRG a part ir del punt factible x• = [O 2 longitud de pas o• = 2 s' ob té el punt it era\ : x1+1 "" [- 0.11419 1.98611 2 .9 4444]' 37 Compro- ! ]' 3]' amb Efectueu una i 1e ra ció del procés de re torn a la regió factible a pa rtir de 3x . El vect or de variables dependents a xk és yk = [ x1 k x/ ] 5 Solucions deis problemes de modehtzació 5 Solucions deis problemes de modelització. Solució del problema l. • Variables: • xl.4: quantitat d·aYions tipus 1 que vols a la ciutat A. • 2· 1 a: quantitat d·a,·ions tipus 1 que vols a la ciutat B. • xzA: quantitat d·a,·ions tipus 2 que vols a la ciutat A. • 2·2a: quantitat d·avions tipus 2 que vols a la ciutat B. • x3 A: quantitat d'aYions tipus 3 que vols a la ciutat A. • x3a: quantitat d·aYions tipus 3 que vols a la ciutat B. • Funció objectiu: : = 23x1.• + 58x1b + ... + 38x3a Constriccions: * Nombre mcixim d'a vio 11 s: * Demanda: X¡A + X¡B $ 8 xu + xza :S 15 X3A + X3B $ 11 45x1A + 7xz.< + 5x3A :::>: 20 45x 1a + 7x2B + 5x3a :::>: 28 1 1 1 1 * Capacitat torre de control: XJA + X!B + 3x2A + 3x2a + 3x3A + 3x3a :S 5 • Formulació final: (P) mm z = 23x1A + 58x1b + ... + 38x3a s.a.: X¡A + X¡B $ 8 XzA + X2B $ 15 X3A + X3B $ IJ 45x1A + 7X2A + 5x3.4 :::>: 20 4-5x1a + 7xza + 5x3a :::>: 28 1 1 1 1 X¡A + X¡a + 3x2A + 3x2B + 3X3A + 3x3B ::; 5 X1A , XlB 1 X2A,X2B·X3A 1XJB ~ Q enteres 39 40 Coflecóó de problemes resolts d'Investigació Op _eratil'a Determinista. Solució del problema 2. • Variables: x;;: nre. d'alurnnes del districte i assignat.s al centre j (x;; ~ O, enteres). No cal distingir entre estudiants blancs i negres ja que. segons l'enunciat. es mantenen les rnat eixes proporcions que existeixen als district.es. Si es defineixen dues variables diferents pera distingir entre rac es (x1; i x?;) aleshores cal imposar la constricció: xi; ni [ ( ni ) l b -, ---n = -.,--b -l - -.,-- b .I¡j - xij + xij n¡ + n. 1 n¡ + n¡ 10 3 • Funció objectiu: min z = L L d¡ jXij i=I j=l • Constriccions 3 * Escolarització de tots els alumnes: L X¡j = nf +ni J=l 10 * Capacitat de les escales: L Xij ~ Cj j=l.2,3 j=l -- 71 -'- x'- 1. -O ( b ) n7 + n~ 'J - i = 1,2 ... , 10 • Bala119 racial: la proporció d'alumnes blancs i negres al centre j és: f(~)Xij ! ~ _ t;;l n¡ + n¡ ) -10 ~(-n? )x ·· 2i ni+ n~ fJ !;" = ~~-1-0 ___ _ LXij i=l Le s constriccions de balan<; racial imposen: 1 b 1 ) --O<J <-+O 2 - } - 2 !-e<J"<!+e 2 - } - 2 j = 1,2 ,3 (1) Donat que s' ha de satisfer que JJ + f;" = l, el conjunt de constriccions (1) és re dundant , Ja que: ! - B < J' => J' < ! + B ) 2 - } } - 2 1 1 j = 1, 2, 3 --O<T"=>J'<-+B 2 _Jj J-2 Així dones, nornés cal imposar les prirneres desigualtats de les constriccions (1 ). Tal com s)han expressat aquestes constriccions són no lineals. Cal expressar-les com a 5 Solucio:rJ 3-~ • F orm t:.!..a -..: So lu ció del :;:- • Vari ab leo - =~~~ t..a . (1) (2) (3) ~~~....::::.=:::c ada ~~ca..:_~ mes. ? :;.:::~ ~ ~=·={! _ ~ h produida 5 Solucions deis problemes de mod elit zaóó per la me scla: yo $ 0. 3x, + 0.15x2 y¡ $ 0.4.r¡ + 0.35x2 • Formulació final (P) Solució del problema 11. • V ar iabl es: min z =500 0x 1 + 7000x2 + 2500yo + 2500y , s. a: 0.4x¡ + 0.35 .r2 + 0.30yo -; 0.4y ¡ ? 3000 0.3x 1 + 0.50x2 + 0.05yo + 0.4y¡ ? 2000 .t· 1 + .r2 + Yo + Y1 $ 20000 0. 3x1 + O.J5x2 -yo$ O 0.4x¡ + 0.35x2 -y1 $O x1 ,x2,Yo , Y1 ~O enteras * :t'A. 1 XB, x c: nre. de peces diarias a fab ri car. * X p, X3: nre. de premses j maquines de soldar a insta}.}ar. * Yp· y,, Y a: nr e d'obrers de cada categoria. t.otes le s variables són enteres i no ne gat iv es . 47 • Funció objec tiu : max: = (250 -150)xA + (350 - 300).rB + (300 -200)xc - 8(550yp + 650y, + 360ya) • Const ri cc ion s: * Limit de venda: XA $ 10000, XB $ 5000, xc $ 12000 • Límit d'espai: lOxp + 12x, $ 10000/ 4 = 2500 • Lim ita ció de la prod uc c ió : XA XB XC 500 + 1800 + 150 $ Bx p XA XB XC 15 + 8iJ + 30 $ Bx .• • Li mi t ació del nombr e d 'obr er s: Yp ? Xp y, ? x, y0?xp/ 4+x, Yp + y, + Yo $ 400 (no seria correcte Ya= xp/4 + x, dones Ya és entera). 48 • Formulació final: max s.a.: (P) Solució del problema 13 . CoHecció de problemes r esolts d'lnvesligació Operativa Determinista. : = IOOxA + 50xa + IOOxc - 44 00yr -5200y, -2880y. 10.rr + 12.i:, :S 2500 5un + mu+ ffu :::: s.rl' TI-+ M + %- :::: s.r, Yr;::: xi' YJ ~ .r .• Ya ;::: Xr / 4+ x .• Yr +Y.• +Ya :S 400 0 :S XA :S 10000 0 :S XB :S :j000 o :S xc :S 12000 J..'p1X" ,yp, y,,.!Ja ~ Ü XA , x s, .te, x1 ,, x", yJ' , Y.• , Ya ent eres S'introdueixen els escreixos x52 i x53 i una co nstric ció addicional associada al nus que equi lib ra la xarxa · min z= 3x12 + 4 x13 + 3.r23 + 5 x24 + :t41 + 7x43 s.a.: X12 + a·13 X4¡ 1 - X12 + J_ ' :'.!3 + X24 .r . :i2 - 3 (P) -X24 + X4¡ + X43 o - X¡3 r23 X.13 .l.' 53 -4 X52 + .r53 6 Xij ;::: Ü 'v'(i, j) EA Solució del problema 14 . a) Problem a de flux máx im . b) Xa r xa e) Formu lació : 5 Solu c10~ ::;)e..:! Solu ci ó d8 -~ S' han ~ ,:,,.,,_ar ti fi cial 'l-" -= nus l nu s 2 nus 3 nus 4 nus 5 , a::= La xar xa 35$ : - .li..:.i. on s'indica e:: -a ::~ • .e.~n1 st a . -· · :t _?. ::?..! ;:: _s que 5 So lu cions de is prob lem es de m ode lit zació 49 X41 min X4¡ s.a. : X4¡ + X J? + X ¡3 + X¡4 = o X1:? + J.'24 -o X¡3 + X34 = o X4¡ X24 X3 4 X14 -o 0 '.S X;j '.S 300 , \1( i, j) op { (J. 4 ), ( 4, 1 )} X 14 ~ 600 0 '.S X¡4 '.S 600 ; 0 '.S X4¡ Solució de l problema 15 . S'han d 'a fegir va riables de fo l ga i incorporar una nova cons1ricció, corresponent a un nus artificiaL que sigui su ma de to tes les const ri ccions, amb signe can,·iat: folgues nus 1 1 1 o o o o 1 o o nus 2 -1 o - 1 1 1 o o o o nus 3 o - 1 1 - 1 o 1 o 1 o nus 4 o o o o -1 - 1 o o nus 5 (ar tificial) o o o o o o -1 - 1 - 1 La xar xa associada a les equacio ns de xarxa (1 ) és: ,., ·3 \ • • -- ;8 ----- ... .. { s .. ---... 2 ,, . .. - - -·':r: g on s 'indi ca en línea pu ntejada els ar es i nus ficticis. X¡ X2 X3 X4 X5 X6 X7 xs Xg 10 o -3 -5 - 2 (1) 6 Solucions deis problemes de programació lineal 6 Solucions deis problemes de programació lineal. Solució del problema 27. Representem gráficament la regió factible Kpc: X, '1 ~ X¡ JO a) La solució es troba al vertex determinat per la intersecció de les rectes r1 i r3: r1 . r3: -xi.+ 3x.; = 6} r,,. = [36/5). 2x¡ -X2 = 10 I" 22/5 El problema és factible amb solució única. b) En aquest cas, !'ares ta del polítop associada a la recta r3 és una aresta optima: [ 36/5] [5] X"={xEKPclx=a 2215 +(1-a) O , 1 foE [O , I]} (PL) és un problema factible amb optims alternatius. 51 c) Hem de trobar el valor del terme independent b2 que fa que la recta rz passi pe! punt intersecció X de les rectes r1 i r3: r2 : X¡ + X2 ::::::: bi lb2 =~+~= ~I 52 CoHecóó de problemes resolts d ' lnvestigació Operativa De te rmjnista . Solució del problema 28. Representem graficament la regió factible KPL: '2 • C¡ < O: problema jJ.Jimi tat: x· = 0 • C¡ = O: l'are sta assoc iada a la constricció X¡ ;::: o és optima. És un problema amb optims alternat ius: Ü < C¡ < 2: x• = [ 20 ). • C¡ = 2 J' aresta associada a Ja re cta r1 és Op tima (opt ims a}ternatius): X-= {x 1 x =o[~]+ (1 - o) [~] , 'fo[O, !]} H¡ > 2 x• = [~] Solució del problema 29. Prime r tr ansformarem les constriccions. La prim era constricció té el term e independe nt negatiu: es canv ia el signe del dos membres: -X¡+ 3x2 = 5 La segona constricció está doblement afilada. Aquesta constricció es pot tran s formar en una constricció d'igualtat afegi nt una folga x5 amb fita superior: 6 s X 1 + Xz - 5x4 s 7 ._. X¡ + X 2 -5x4 + X5 = 7 Ü '.Ó X5 '.Ó 7 - 6 = J La forma estandar no consid era fites superiors a les variables: x5 S 1 es t ra nsforma en un a 6 Solu aac:s ===::.!!I cons tric ~= .: _ La ;..e : :=:-.i. d'ig ua lta' 3=: --=: 3:, E l~:-::::.~ L ·ere.: , - - - de I3 ir:: : :: -- Ara elim'::.""- :~ 3x2 -5 -~ D'a ques"-Z ::-:=...?. cons ta nt .:,..: ;. form ula cé ::- ::5 X3 =-= 3i =_= .:~ -: ~--m:i nist a. ~=· Opt ims e nden t ..;., ~:. imar en := ~ :~ a en una 6 So lu cions del s probl emes de progr ama ci ó lineal 53 constricció d 'igualtat: X5 :::; 1 - J'5 + Xó = 1 X6 2: Ü La terce ra cons tricci ó, no lineal. es pat. tr asformar facilme nt en un a constr icció li neal d'i g ualtat : 3x , +íx2 _ - 3:;:;-- 2: 4 ~ 3x 1 + 1x, -12.r3 $O - 3x1 + 1x , -12x3 + x; = O El problema que ten im fins ara , passant la funció objectiu de min a max, és: (PL) min : = -6x 1 - 5x, - 3x 4 s.a: - X¡+ 3x2 = 5 X¡ + Xz - 5X4 + X5 = 7 X5 +x6 = ) 3x1+7x,- l 2x3+x ; =O X2 , X4,X5,X6 , Xi ~ Ü x1 11iur e, X3 $O X; 2: Ü L ' únic qu e qu e da per fer és tra cta r les variab les x1 i X3 . Pr imer canviem el sig ne de la ti ta de X3 introduin t el canvi de variable i3 = - x3: (PL) mm z = -6x 1 -5 x2 - 3x4 s.a.: -X ¡ + 3x2 = 5 X¡+ X¡ - 5X4 + X5 = 7 X5 + X5 = ) 3x, + 7x2+ l2x3+x1 = O 2. ' 21.i3, X4 , 1'5 1 X s 1 X ¡ 2:: Ü x1l liur e Ara e limin em de la fo rmula ció la va r iab le lliure x1. De la primera con stricc ió tenim que X¡ 3x 2 -5. Sub st itu im x1 p er aq u esta express ió a to t el prob lema: ¡ min s.a.: (PL) : = -23x2 -3x4 4X¡ - 5X4 + X5 = J 2 X5 + X5 = 1 l6x2 + ]2x 3 + X;= ]5 X2 , i3,X4,X5 ,X 6, Xi 2:: Ü D 'a qu es ta for ma obtenim un pr obl ema amb una variable i co ns tri cció de me nys . Noti's qu e la con sta nt 30 prov i nent de la su bst it ució x1 = 3x 2 -5 a la funció obj ect iu s'ha e limi na\ de la formu l ació, d ones no afecta al result. at . Un cap reso lt el pr ob l ema an terior l es tr an sformac io ns x3 = - x3 i x 1 = 3x2 -5 ens pr oporc iona ran el val or ópt im de l es variabl es orig inals. 54 CoH ecció de prnb lem es resolts d'lm•estigaóó Operativa De terminista. Solució del problema 30. Representem graficament la regió factible Kp i els vértexs associats a les solucions basiques: X3 xJ o so luc ió bilsica factibl e. e so{ uci ó ba s ica infa c tibl e. Introduim les varibles de folga x4 i Xs: (PL} a) Solucions básiques factibles: s .a . l min X 1 + Xz + 3x3 + X4 = 6 5x ¡ + 3J:2 + 3x3 + .rs = 15 X 2': Ü * x~ B = {1.4} .r~ = [::] = B1& = [~ ~r [1 6 5] [!] :1 = 15 x; : 8={2,4} x; = [::] =B1 b= [~ ~ r [1 6 5] = ¡n :2= 15 •x 1: B = {2 , 3} x1= .(: : ] = B - 1 b = [~ !r [1 6 5] [ ~] z3= 10 * x!: B = {3 , 5} .r! = [: : ] = s-1b = [! ~r L 6 5] [ ~ ] =4 = 2 *X~ B = {1 ,3} X~ =[::]= s-1b = [~ !r L 6 5] [ 5~3 ] z5 = 20/3 •x~ : B={4 ,. 5} x ~= [x•]=B - 1 b= [ 1 º]- 1[6 ]=[ 6] z6= 0 X5 Ü 1 15 15 Veiem com ens trobe rn devant d'un cas d\ma so lu ció a mb Op tims alternatiu s: el conjunt solució .r és el segme nt de rec ta defi nit per les so lucions basiques x~ i x~, és a dir : . . r = {x E IR 3 1 x = ox~ + (1 - o )x~, V o. E [ O, I ]} 6 So luciocs ::.:.e:5 - b) Sob:.:::..; : ~ 5= 5 = 5 = Solu ció de ;:. on •: ~ cons:: :: .J:- - les f o!~-5 :¿ és el oe~~- -= 5= -- : = b) R ep r ~:."- A~.--m in is t a . :c.: b~iq ues: ~ .j ].) .:. .: = ? :º = 20/ 3 ='=o ~ · :--l conjunt ~ .· ~ :=.Gn : 6 So lucions dels problemes de programació lineal 55 b) Solucions básiques infactibles: *X~ B = {2,5} x~ = [ :: ] = B1b = [ 1 º )- l [ 6 ] = [ 6 ] 3 1 15 -3 l. o *X~ B = {3,4} x ~ = [ :: ] = B -l b = [3 1)-l [6] [ 2.5] 6 o 15 = -1.5 l. o • x~: B= {1,5} x~ = [: :] = B1b = [~ ~r [1 6 5) = l- ~ 5 ] 'f.O So lució de l probl e ma 31. a) Represe ntem gráfic ame nt la regió factib le Kp : Xl X¡ r¡ r2 r3 on r1 és la r ecta associada a la primera constriccó, r2 la rec ta associada a la segona constricció i r3 la r ecta associada a la tercera constricció. Les variables x3 i x4 representaran les folg ue s de la segona i terce ra cons tri cció respectivament. En aquest cas, el po lítop Kp és el segment de rec ta en tre els dos únic punts extre ms x1 i x ~ : * x ~: 8 = {1,2,3}, XI - s - r :: J [2 1 º]-! [ 6] = B1b= : ~ ~ : [1/3] 4/3 , z1 = 31/3 1 /3 * x~ : [ X¡ ] [2 Ü º] -! [6] [3] B = { l , 3,4),x~= :: =B -1b= : ~ ~ : = ~ , z1= 15 b) Re pre se ntem gráfic am e nt la regió fa c tib le Kp : 56 CoHecció de problemes resolrs d'lnvestigació Operati,·a Determinista. X1 r¡ r¡ r3 on r· 1 és la recta associada a la primera constriccó. 1·2 la recta associada a la segona const.ricció i r3 la recta associada a la tercera constricció. Les variables X3 i x4 repressent.aran, respectivament, les folgues de la segona i tercera constricció. En aquest cas es produeix degeneració sobre el v€rtex situat a !'origen de coordenades: n' hi ha tres solucions b3siques (x1ª ,x1b i x~c) associades a aquest vertex: *X1ª B = {3 ,2}, x1ª = [::] = B1& = [~ ~r [~] [~] . z1ª =O •x1bB={3,1},x1b=[::J=B - 1 &=[~ :S 1 [~] [~] ,z'b =o * x1': B= {3,4}, x1'= [::] =B1 b= [~ ~r [~] = [~] , z1 '=0 * x~: 8 = {1 , 4} , x~ = [::] = B1& = [ :l ~l-I [~] [~] . z" = -8 *X~ B={l,2},x~= [::] =B1 b= [:1 ~r [~] = [ 1 6 2 /:J ' =3=-6 Solució del problema 32. Per calcular una sol u ció factible apliquem la fase 1 del simplex. Passem a la forma estandar, introdu.im una variable artificial a la tercera constricció i iterem amb una funció objectiu z = x6, on x6 és la variable artificial : X1 - 1 3/2 1 o o o 12 o 1 1 -1/4 o o 10 Tº - a - GJ 2 o 1 o o 8 T1ª -1 [illJ o 1/4 o o 2 1 1 o o -1 1 8 o 1/2 o -1/4 -1 1 3 -1 -1 o o 1 o -8 o -1/2 o 1/4 1 o -3 6 Sol uc1 oru ~ Dona: ~--:: -, ~ l'op tim de·':-'-"'.' solució fac .. :: .:: Soluci ó dE:~ ;:. a) Passe::: =· : Es re c.. .. :.:==. • Pri m er-a~: J.. Detec c;:ó o== 2.- Selec c1 ó ce r. 3.- Dete cc1 ¿ ;::- · l 4.. Selecc 1ó ce · '" Yr o = -~ ! Yp q i= ::.: . J da. 5.- Can"i de º-'-"" ri .=~-:.e:-m1ni st a. :1 ~;::.2. co ns- :"!"::~-e::;.a r an. -·?_¿ ~ : :- -::du eix - :e:.: ::~!q ues = -! ,2 =s;andar , --:·~=··~.::: = l' 6, J. = ~ 1 Hl 2 3 f3 6 So luci ons del s proble mes de programació lin eal 57 J'¡ X2 ; J.:3 X4 X5 X6 - -2 o 1 -3/ 4 o o 6 T>. 2 1 o 1/2 o o 4 -1 o o -1/2 -1 1 1 1 o o 1/ 2 1 o -1 Donat que rN 2 O, T;I és el tableau óptim del problema arti fi cial de la fase l. Hem assolit l' óp tim de la fase 1 sense e li min ar les i nfactibilitats (x6 cont inua sent bii.sica) ~n o exist eix cap solució factible. Solució del problema 33. a) Pass em el proble ma a Ja forma es tánd ar in trod uú1t les variabl es de fol ga X3 i X4 : ¡ min z = x1 + x, s.a (P L) 2x1 + x2 + x3 = 3 X ¡ + X2 + X4 = 2 x20 Es realitzen els cá lculs pr evis a l'aplica ció de l'algorisme del s impl ex: [2 l l [ 1 - 1 i Bº = {l.2) ~ B= 1 1 ; s - '= - 1 2 r · ~ = c ~ - c ~B - 1 .N = [O 0) - [-1 -2 J [~ l - 2 1 ][~ ~] = [ - 1 3) x8 = B1 b= [ ~J -n [~] = [:] =Y O Primera iteració : J.- Detecció d' óptim : rN = [-1 3] "f. O ~ no ó ptim . 2. - Selecció de la variable d' e ntr ad a: 1·3 = - 1 ~ x3 v.n.b. d'e ntrad a. 3Detecc1ó pr ob. illin11ta t.y 3= B1a 3= [~ 1 ~ 1 ] [ ~ ] = [~ 1 ] f O 4- -Selecció de Ja variable de so rt ida: Ypo . { Yio I } . { / } Y10 - = . m;n -y;q > O = mm 1 1 = 1 = - ~ p = 1, Bp = 1 ~ x1 v.b. Ypq i =l, - ,3,4 Yiq Y13 da . 5.- Canvi de base: B - {3 , 2} N -{1, 4} B = [ 1 l l . si = [ 1 - 1] o 1 • o 1 r ~ = [ - 1 O] - [O - 2] [~ ~ l][ ~ ~ ] = [ ! 2] X B = st b = [ ~ l de sorti- 64 CoHecóó de problemes resolts d' lnl'estig ac ió Operativa Determinista. Solució del problema 36. [ -1 /5 a) LasolucióbasicaassociadaalabaseE"és: x~=B"- 1 b = -1 /10 2/5 La solució dual associada ax~ és : 3/5 1 /20 -1 /5 [ -1/5 -4] -1/10 2/ 5 3 /5 1/ 20 - 1 /5 +J = [- 11 / 10 -9/ 20 Comprovem ara el teorema de la folga complementaria: x;(c; -A'aj) =O i = l, ... ,m X¡= 2 => C¡-A'O¡ = 0 -2-lx(=rb1)-2x (~) - Ox( f) = -2+ 2 =O=> x2 = 2 => C2-A'a2 = 0 x3=l=>c3-A'a3=0 , A; ( bj - aix) =O -4-3 X ( =rb1 )-1 X( ~ ) -1 X (f) = - 4+4 = 0 => -l-Ox(=rb1)-0 x (~ ) -4 x (.::;¡l) = - 1+1 =O => A1 = -11/10 => xs = b¡ -a1x =O : Xs no básica => correcte. A2 = -9/20 => X6 = b2 -a2x =O: X6 no básica=> correcte. A3 = -1/4 => x7 = b3 -a3x = O: x7 no básica=> correcte. b) La formulació del problema artificial {PL 0) és: r·" Za= X5 + X6 + X7 (PLa) subj.a: X¡ + 3x2 + 2x 1 + x2 x 2 + 4x3 + X¡ , X2 , X3, X4 , X5 , X6, i el tablau del simplex incial per a (PL 0) és: 1 3 o 1 1 o o 2 1 o o o 1 o o 1 4 1 o o l -3 -5 -4 -2 o o o c) Calcul de l'interval d'es tabilit at de b2: X4 + X5 X6 X4 + X7 X7, 2: 8 6 6 - 20 -1/4] co rr ee te corree te corree te 8 Rl 6 R2 6 R3 o x8 = 3• -1 [b 8 2] = r~~; ~b~l 2: O int erval d'es tabilitat : ~ < b2 < 16 3 - - 6 16 .b,¡ O - D b2 = 20 > 16 => es perd la factibilitat prima l. En una iter a ci ó del simplex dual s' ob té el 6 Sol uc io . iu ¿e!5 _- - nou Opt im X¡ ,. , I3 l o o o o 1 o 1 o o o o S ol ució 0~:1::-=. º d) lnteressa ;;:-:: :.__: : r8 = e - ; .::!. = - - lnter es.sa F~--= : . ._ Soluci ó de l pro .~ : - a) La base eo::..:=. ::-;-~ són no nu~es . ::=.:.-_ les folgues: * .l'5 = g - :: . - -=-- = • .r..; = -: - -= - -=- -- Si rores dce:s :: "-"" b Asi ca 6. ~i~:.. ~ :.:r La ma triu h~.3. b) Si x ~ = [ :: _ ~ s: - .p::c ·:"?C" atil ·a Dete rminist a. o 1~4 ] [: J = [~] - .. ::;. · - ~ ; 2 0 -1 /4] = -: - ·2 = O =;> correcte = ~ - ~ =O =;- correcte =- -: - : = O =:. corre cte ·- ~ :; = 8 Rl Zs = 6 R2 -~ --= 6 R3 2'. o ~ 8 :.ic -~ ·¿ · : 3 $ b2 $ 16 : ::"'- o::_-.:plex dua l s'o bté el 6 So luc ion s del s probl emes de programació line al nou Opt.im: X¡ !''l .l.'3 X4 X5 X5 xX ¡ Xo X3 X4 ------ 1 o o -1/5 -1 /5 3/5 o 52/5 1 3 o 1 o o l 3/2 0 -1/10 1/20 1 /4 17 / 10 o 1/ 4 1 1/ 4 o 1 o 2/5 2/5 R75l o -4/ 5 o -5 o -2 o o o 7 /2 0 11/10 9/20 1/4 193 / 10 o 9/4 o 5/4 Solució optima associada a b2 = 20 : X~ = [ X¡ X3 X5 ]' = [ 8 3/ 2 4 ]' d) lnter essa prod uir x8 si el seu cost red uü és negatiu: r8 =e s - >.'as= -8 - [ ~ - 9 -w- [ 10 - 28 ] .:¡f. ] 20 -B = ~ _ 78 1 - 5B 4 We <O Jnteressa prod uir Xg a partir de B = w Solució de l probl e ma 37 . X•. - 1 o -2 2 :} 65 X5 - X7 o o o 1/4 1 o o 1/4 B > 245 78 a) La base e sta rá forma da per tres var iab les. De les v ariab les del nostre pr oblema la X¡ i la X3 só n no nules i, conseqüentment, basiques. La te r ce ra variable ba.si ca s)ha de bu sca r entre les folgu es: * x5 = 9 - .r 1 - 2x 2 = 9 - 2 = 7 > O =:. bilsi ca . * >' 6 = 2 - 3x 1 - 2x 2 + X3 -6x4 = O =:. no bilsica. Si toles dues folgues haguessin estat nul·l es la solució bilsica seria degenerada. La solu ci ó b ils ic a op t.ima és dones: X~ = [: :J = [ ~ ] La matr iu bii.s ica i la seva inv er sa són: [ 1 o 1] B" = 3 - 1 O 1 1 o [o 1/4 s--1 = o - 1/4 1 - 1 /4 1/4 ] 3/4 - 1/ 4 b) Si x~ = [ :: ] és solució op tima , ll avors els vector de costos re duü s és no n egat iu: r2 2: O 8 3/ 2 4 35 / 2 66 CoHecció de problemes resolts d'lnvestigaóó Operativa Deter minista. i , .• 2: O: >.' =c~B1 = [2 4 O][~ !{;4 ~ j! ] = [O -1/2 7 /2] . 1 -1/4 -1 /4 r2 = c2 ->.'a2 = c2- [O -1/2 7/2] [~ 2 ] = c2-5/2 2: O =:- h 2: )/ 2[ 1·4 =c. - >.'a4 = C4 -(0 -1/2 7/2] [~] = C4 - 1/2 2: 0 ::O lc4 2: 1/ 2[ e) La nova variable x5 (no confondre-la ambla folga de la primera constricció) sera basica si el seu cost reduit associat és negatiu (r 5 < O) i si és possible fer la pivotació amb alguna variable básica (Ys = w1 a5 i O): rs=cs->.'as=3-[0 - 1 /2 7/2] [~] = -1/2 < 0 [o 1/4 1 /4 ] [8] [ 1 /4 ] Ys =B"- 1 as .= O -1/4 3/4 O = 3/4 i_Q 1 -1/4 -1 /4 1 31/4 Així dones, x5 esdevindra varible básica al nou óptim. Solució del problema 38 . a) Pera demostrar que una solució no és la millor possible s'han de co mprovar l es co ndicions d'optimalitat. Donat que x1 :f O, x2 :f O i x3 :f O, aquestes s'han de prendre coma variabl es básiques. L'enunciat ens dona la inversa de la matriu básica corresponent a l'ordenació B = {3, 1, 2} [ -03225 8 -0.16129 1.29032 ] B1 = -0.1935 0.40322 -0.22 580 0. 5161 -0 .24193 - 0.06451 • Factibilitat primal: es comprova la condició de factibilitat primal x8 2: O: [-032258 -0.16129 1.29032] [1.5] [0.4830] x8 = B1b = -0 .1935 0.403 22 -0. 22580 2 = 0.2903 2: O=:- [factible primal[ 0.5161 -0.2419 3 -0 .06451 1 0.2258 • Factibilitat dual: es comprova la condició de factibilitat dual r' = e~ - c~B1 N 2: O. Es calcula previament el v ec tor >. = c~B - 1 : [ -0 32258 >.' = c~B - 1 = [20 25 30] -0.1935 0 .5 161 -0.1 61 29 1.29032 ] 0.40322 -0.22580 = [4.1 93 -0 .4032 -0. 24 19 3 - 0. 06451 18 .2258] 6 S o! uov:--5 - - .. = b) s = •J - - Pri m era=- = 1.- D ei~::.:' : _ 2 .- Sele .::::ó .: 6- : T" e) lnteressa .;.- _: ;~ = ::; - Si x5 e::: :-- ::s .::.. i.. a la base Aixi don::s · ~ 2 ~term in i sta. ~ ~ ,_ .:.e:?. ba.s ica si -.: a....-:--:b alguna : L~ :;:ndicions .. ~ a \-a riables .:; • :: :denació >'" . -. ?: : = !fac tib le prima !I -~,3-: .\"?: 0 . - 0.4032 18 .2258 J 6 So lucions deis p ro bl em es de programació lineal i, segui dament, els costos re duú . s: r;,= c;, -A 'N= [IO O 0] -[ 4193 -0.4032 [7.5 1 18 2258] 0.5 o 1 o 67 ~I] = = [- 39.4758 -4.193 -0.4032] l O=} li nfact ible dua!I b) B = {3, 1,2} ,N = {4, 5,6 } Primera it eració : J .• Detecció d' opt . im :i· ;, = [ -39.4 75 8 -4 . 193 -0 .4032] l O =}n o opt im 2.· Selecció variable d'entrada :i·, = minje .d''i } = 1·4 = - 39.475 =} x4variable d'e ntrada 3.- Detecció pb . il.Jimit. at : [- 1. 2096] Y• = s-1 a, = -1 .4758 f. O 3.6854 no il.limitat [0 4830 ] [-1. 2096] 4. -Selecció variable de sor tida : x8 = 0.29 03 ; y4 = -1.4758 0.2258 3.6854 Ypo . { y; o I } . { 0.2258) Y 3o . - = . mm -:- y;, >O = mm 3 68_ = - =} x 83 = x2 v.b. de sor t1d a Yr4 i = t ,2,3 y,4 . ;:>4 Y34 5.- Ga m• i de base : pi vot ació x4 - .r 2: B - B\ {2} U { 4) = {3, 1, 4}: aquesta base ja corres pó n a la so l u ció optima del tabl ea u T": [x3] [ 0558] X~ = X1 = 0.381 X4 0. 061 [ 10.7 11] 1·~ = 1.335 2.188 z" = 21.291 e) lnt eres sa introd uir el nou carbó a la me scla opt ima si el seu cost r ed u "it és n egat iu: r5 = c5 -A' [ ~] = 15 - 19.7702 = -4 .7702 < O =} lmillora la fu nció objec tiu 1 Si x5 e ntr és a la base milloraria la funció object iu. Ca l comprovar pero que Xs pot entrar a la bas e: [ 0.8753] y5 = B" _, a5 = 0.0678 i O =} jpot e ntrar a la bas e! 0.0569 Així dones, int eressa canvi ar Ja propor ció de mescla introdu"int el nou carbó. d) Co mprovem si les no rm ativ es deis EUA i Jap ó fan vari ar J' opt imalit at de B" = { 3,2,4 ): 68 CoHecóó de problemes resolts d'Investjgació Operativa Determinista. • EUA: [O.í396] 0.2223 ? O ~les conserva la factibilitat primaJI. 0.3807 [ 2.0] [0 . 3610] • Japó: i:8 = B"- 1& = B"- 1 2.5 = 0.54 05 ? O ~les conserva la factibilitat primaJI. 1 0.0985 Calculem ara la variació en la funció objectiu deguda a l'adequació de les proporcions optimes a la legislació de cada pais. Haurem de fer ús del preus ombra >,: ),' = c8° B"- 1 = [-1.335 2.1882 18.9168] * EUA: t..:=>.' t..b = [-1.335 2.1882 [-O 4] 18.9168] -~.5 -0.5602 < O ~ millora els costos de producció. • J apó: Áz = ),' Ab = [ - l_.335 [ 0.5] 2.1882 18.9168] 0~5 = 0.4267 > O ~ millora els costos de producció. Decidim exportar als EUA, dones la seva legislació admet unes proporcions optimes am b uns costos de producció més baixos (20.7308·104 pt s /Tm) que al Japó (21.íl i7·10 4 pts / Tm ). Solució del problema 39. a) S'analitza la variació de la funció objectiu per increment del terme indepe ndent b1 (llet de cabra): Áz = >. 1Ab1. De la taula optima s' obté >. 1 = -r 4 = -30~ un litre addicional de llet de cabra provoca un incrementen el benefici total de t..z = 30pts~ el preu maxim que estariem disposats a pagar per un litre addicional de llet de cabra searia !'original (20pts) més Áz = 30 : j50pts/II~ lno comprariem a 60pts/Ii. b) La tercera constricció no és activa, com mostra el fet que la seva variable d'excés x6 sigui básica. Així dones, si s'eliminés no afectaria la planificació optima. e) Si el preu venda del formatge 1 passes de 190pts a 320pts llavors el cost c1 passaria de c1 = -30 a c1 = -160. Calculem els cost reduú de la variable x1: r1 = -160 - [-30 O O] [:J = -10 < O~ perdua de la factibilitat dual: es reoptimitza amb el simplex primal: X¡ @El o -1/2 1/2 o 1 25 -4 o 3 -1 1 o 50 5/2 1 1/2 1/2 o o 425 -10 o 10 30 o o 25500 6 So/uc 1om c::..:f = d ) Si C3 = - qu e le. :·_ - - - Yo = : :: mi n{ ~ : Solu ció del p. - a) P ri me: .,, -:- : perd :- e ; :;- -, • 6' = l - - ~I e - nni nista. :...::-=•lttat prima l!. ,.;::=•fliat primal[. ~ ;. ~ o po rcio ns 1. __ < _ =:imillo ra = millora els ,:·~ =?:imes amb · - ~ - • J' pt s/ Tm ). _ : o=: b, (llet de := ,_.:iicio na l de ,. . ;.~ .: ::i 3x .i m que =,::: _::- - al (20 pts) :... : ~=és xs sigui ~ -=~- e: passaria :: · - = - 160 - __ =! :za am b el 6 Solucions deJs prob/emes de programació lineal 69 X1 X:! J'3 X4 ..Z:5 J.' Q 1 o -1/3 1/3 o 2/6 50/:l o o 5/3 1/3 1 8/ 6 350/ 3 o 1 4/3 -1 /3 o -5/ 3 1150¡:3 o o 20/3 12 /3 o 2 0/3 77000/:l Nova planificaci6 óptima: lx~ = [x 1 X5 x,J' = [50/3 350/3 1150/3J'I d) Per tal que els formatges 1 i 2 entressin a formar part conjuntament de la planificació optima haurien d' entrar a la base. Per tal que aquest can,·i de base no afectés al benefici total caldria que es produís una situació on t.ant la base actual 6 = {6, 5, 2} com la nova base. amb x3 com a variable básica fossin solucions óptimes alternatives. Aixó es pot aconsseguir portant. el coeficient c3 fins a un deis seus e xtr ems del seu interval d'estabilitat: • lnterval d'estabilitat de c3: r3 = C3-)/a3 = c3- [-30 O O][~] = c3 + 30 2'. O. L'interval d'estabilitat de C3 és h > -301. Si C3 = -30 s' obté r3 = O=:> opt.ims alternatius. Podem entrar X3 a la base sense que la funció objectiu augmenti. De la taula óptima sobté y3 = [ -1 /2 3 1/2]' i Yo = [25 50 425]'. La variable de sortida correspon al min15;53{~ly;3 > O} = min{40/3 , 2 x 425} = 40/3 => x5 variable básica de sortida =>nova base: B = {6, 3, 2} Solució del problema 40. a) Primer es comprova si les modificacions introdu.ides al vector de termes ind ependents fan perdre l" optimalita t de la base: * s· = {3,5, 2}. s·- 1 es pot obt enir de les columnes del tableau optim associades a les dues folgues SLK 2 i SLK 3 i a la variable Xt, dones aquesta variable té columna [ ~] al tableau inicial: SLK 2 s·-1 = [ ~2 -4 [ 1/2] * fi.bR = ~ [4 o -3] [9 5] XB = B°- 1 (b+flbR) = -2 1 1/2 20 -4 o 4 10 SLK 3 o 1 o i·¡ -3] 1~2 [ ~] 2'. O => [es conserva l 'opt imalitat de s· [ 70 CoHecció de problemes resolts d'lm'esügació Operativa De terminista . * AbE = [ º~] x8 =B·- 1(b+AbE) = [~!O ~~] [f ~ ] [~] 2:0::;.l es conser val 'opt imalitatd eB"I Es calculen ar a els cos to s marginals o pr eus o mbr a >. : - 3] 1~2 =[-2 o -1 ] Ampliació planta de refiuat: ll: = >. 1Ab1 = -2 x 1/2 = -1 milions. S' obté un increme nt de beneficis d'un milió de pessetes amb una inversió de 1.5 milions: no interessa. Amplia c ió de la planta d' embassat: la co n str i cc ió d'embassat no és activa. Aixó implica que un canvi de b2 que conser vi la factibi litat primal de s· no afectará mai al val or de la funció obj ect iu (els preus ombra de les constri cc ions inactives són sernpre nuls ). Així dones, tampo c interessa invertir en aquesta plan ta. b) Addició de x6 amb c6 = -6 , a6 = [2 1.5 1 ]'. Hem de comprovar la conservació de la fe c tibilitat dual: 1·6 = c6 - >.'a 6 = - 6 - [-2 O -1] [ 1: 5] = -1 < O::;. linteressa produir x61 Solu c ió del probl e ma 41. a) (PL) min . s. a.: (D) s. a.: r 2x 1 X ¡ 2x ¡ X ¡ X¡ 2: Ü JJ. a\..\ 2: C¡ 2,\¡ ..1, ..1 , +x2 =2 ::;. ..1 1 lliure -X2 2:3 ::;> ..\ 2 so - x2 s 1 ::;> ,.\ 3 2: o JJ. a;A = c2 3 ..1 2 ,.\3 2 ..1 2 ,.\3 2: 2 -..\ 2 -..\3 = 1 ..1 2 S O, ,.\ 3 2: o 6 S ol~- .... b) : So lu ció del ;:-- - a) B8 = ·: :.::: .. T"~ - - r', = :: P rirne=:2. - J.- 0<-;e': •• :i! 2. - Se l ~ = ::: 3. - De:e-::. - - De term ini sta. :;;;,.. ~ '"o pt imalitat de s· ¡ :"' S'o bté un :e;::: :-~o interessa. ~ E:::ti \'a. Aixó o:-;; ~ m ai al valor =;:e nuls ). Així ==.:_~r· ;ació de la ;:::;=:_ir x 6 I 6 Solucions dei s problemes de programació line al 71 b) min 2x1 +4x 2 +6 x3 s.a.: X1 +x2 +x3 22 ~ ..\1 2 O X1 - X3 2 1 ~ ..\2 2 o (PL) { x2 + x3 = 1 ~ ..\ 3 lliure 2x1 +x2 $ 3 ~ ,\4 $O X2 2 Ü, X3 2 Ü JJ JJ JJ a~). = Ct a~>.$ c2 a~,\ $ C3 (D) ¡ ':•:. 2..\1 + ..\2 +..\3 +3 ..\ 4 ..\1 +..\2 +2,\4 =2 ..\1 +..\3 + ..\ 4 $4 ..\ 1 -..\2 +..\3 $6 ..\1 2 O, ..\2 2 O, ,\4 $o Solució del problem a 42. a) Bº = { l,3,7 } [ 1 o o] [ 17 ] [ 17 ] • Factibilitat p ri mal: x~ = ~ 2 ~ ~] 3 8 6 = ~ 2 O~ factible primal * Factibilitat dual : r ~ 1 =c~ - >.. 1 N ,\' = c ~(B 0 ) - 1 = (28 [ 1 o o ] 12 O) - 2 1 O =[ 4 12 O) 1 o - 1 ~l ] = [- 1 7 4 12) l. O ~ jinfactible Duall [2 1 -] 1·~=[6 7 35 O 0] -[4 12 O) 5 2 O 1 3 o Algo ri sme del simplex primal : Primera i teració : 1.- Detecció de op tim: r~ = [- 1 7 4 1 2) l. O ~no optim 2.- Selecció variable d'entrada: r2 = - 1 <O~ x2variable d'e ntra da . 3. -Detec ci ó pb . il. Jim itat : y2 = 31a2 = [2 1 1 ]' l. O no il.lim itat 4 -Sele cc ió variable de sortida : x 8 = [J i] ; Y2 = [ :J 72 CoHecció de problemes resolts d'lnvestigació Operati,·a Determinista. Ypo = . min { YiD /Yiq >O}= min{ .'...?., ~. ~} = ~ => .r3 v.b. de salida Ypq •=1,2,3 Yiq 2 1 1 l 5.- Canvidebase:l3={1 , 2,7) s1 =[~2 -2 ~] 3 -1 -1 Segona iteració: 6. -Detecció d 'optim : r~ = e~ - e~ s1 N = [ 1 7 6 11 J 2: O => optim x~=B1 b=[x1 x2 x7J'=[13 2 7]' b) Problema artificial de Ja fase 1 : x., x6 i x1 són els escreixos de la forma estándar i x8 i x9 les variables artificials de la fase l. min Xg + Xg s.a.: X1 + 2x2 + X4 X5 + Xg 2: 17 2x1 + 5x2 + X3 + 2x 4 X5 2: 36 X1 + x2 + 3x4 X7 + Xg 2: 8 x; 2: O Vi X1 Xz X3 X4 X5 X6 X; Xg Xg 1 2 o 1 -1 o o 1 o 17 Tº - a -2 5 1 2 o -1 o o o 36 1 1 o 3 o o -1 o 1 8 -2 -3 o -4 1 o 1 o o -25 C) X8 = s•-lb = [13 2 -1]' => perdua de la factibiJitat primal de {3" => reüptimitzacÍÓ amb l'algorisme del simplex dual : 1 o -2 1 -5 2 o 13 T' = o 1 1 o 2 -1 o 2 o o ~ -2 -3 1 1 -1 o o 1 7 6 11 o -498 Xl X2 X3 X4 X5 X6 X7 1 o o 5 o -2 15 t1= o 1 o -2 -1 o o o 1 2 3 -1 -1 o o o 5 3 12 -499 6 S olua-~.::,dsS olu ció e~ ;:. a) L a':;•? b) e l ) ;e::··~ y; = s - =-= -"' c.2) A :.e.-mi nis ta. -"" .s;:__..~a ~::a : i .ra i X9 :::·! ? JI ? 36 -. ? 8 ~ ~ :-=c;:.:i .mitzac ió 6 So/uóons dels problem es de programac ió lineal So luci ó del problema 43. a) La folga de la prime ra constricció és bilsica =:. l.\ 1 = ül. b) X3 # Ü :} .\2 - .\3 = C3 J'.l # Q :} .\ 2 + 2.\3 = C1 { - 1.\ -, -= --~5 / ~ 3 I .\0 -.\3=-l :} .1, + 2.\3 = - 3 1.\3 = -2 /31 T 14 13 55 Z¡ p¡ = C :r = C1J'.1 + C3 l'.3 = - 33 - 3 = -3 T 5 2" 55 Z ¡D) = .\ b= .\2b2 +.\3 b3 = -393v= - 3 c.!) :r; entrará. a la base si 1) r¡ <O i 2) 3 i t.q. y ;¡ > O. 1'7 = C7 - .\ T Q7 = - 1 - Q [ Ü 1 ,., = 3Q -1 <o x7 entra ra a la ba se ~ 3 it.q. y1; > O : 5 -3 -~ l [:] 3 =:.a < 7 í = -1 + 3ª 73 Y1 = B1a1 = B1 = [ ~ 1/3 2/3 1 /3 ] [Q ] [ 2Cl'/3 ] - ¿3 : = ic,3 =:.Va>O y71> 0 i=l ,2,3 lo <ª :di c.2) r - 1 -1 ~] [º 1 /3 1/3 ] B= 1 1 B1 = O 2/3 -¿ 3 2 -1 1 1 [º 1/3 1/3 2/9] Y =B -1N = 1 2/ 3 -1/3 1/9 . 3 1 o 2/3 ,. ,. = CN - ), T N = [ 3 5/3 2/3 -2/9] z = c8 B1b = - 55/3 .L~ st a . ==-' =.o: = ) 2]' =_:_:x: :.:;-;plic a que --=-.,, el nade ~ .. -.: . - = vegi 1s la 7 Solucions dels problemes de programació lineal entera 81 , . . . .. . • {x1$2 (PE2) :,eparac10: variable de ram1ficac10 x1 = 2.:) :=:> ); L = {(PE2) ,(PE3)) X¡ ?. 3 (PE3 Segona iteració: s'explora la branca x1 $ 2 (PE2) Relarnció: Es resol (PR2) : s'afegeix la restricció x¡ $ 2 a (PE!) i es reoptimitza a partir de T¡,RI X¡ Xo X3 X4 X5 /¡ X1 X2 X3 X4 X5 /i 1 1/2 1/2 o o o 5/2 1 o o T~R2 = o 1/2 -1/2 1 o o 25/2 o 7/2 1/2 o 1 o 11 /2 Tj,R2 = o 1 o o 3 o o -1/2 -1 /2 o o 1 -1 /2 o 1 1 o 3/2 1 /2 o o o 5/2 o 1 o XpR,=[2 ü]' ZpR' = -2 Eliminació : • J{pR2 # 0, • xpR 2 = xpE 2 :::} es pot eliminar: • lnicialització de la incumbent : z" := z¡,E, = -2 , x· := xf>E 2 = (2, O)' • Actualització de la llista: L := {(PE3)} Tercera iteració: s'explora la branca x1 ?. 3 (PE3) o o 1 1 o -1 o 1 1 o o -2 o o 1 Relaxació : Es resol (PR3) : s'afegeix la restricció x1 ?. 3 a (PE!) i es reoptimitza a partir de T¡,RI X1 X2 X3 - 1 1/2 1 /2 T~R3 = o 1/2 -1 /2 o 7 /2 1/2 o 1/2 1/2 o 3/2 1/2 Problema (D) il.limitat :=;. (PR3) infactible Eliminació: • KPR3 = 0,=:. s'elimina (PE3) : L := 0 X4 X5 /¡ o o o 5/2 1 o o 25/2 o 1 o 11/2 o o 1 -1 /2 o o o 5/2 Quarta iteració: L = 0 :=;. la solució óptima és l'associada a la incumbent : lxPE := ;~ = [2 ü]' 'PE := z• = -21 Solució del problema 51. • Inicialització: L := {(P El)} • Primera iteració: es processa (PE!) 2 13 5 1 2 82 CoHecció de problemes resolts d'lnvestigació Operativa De terminista . • Relaxació: Es resol (PRI) : XJ X2 X3 X4 X5 Tj,Rl = 1 o 4/3 2 4/3 34/3 o 2/3 o 2/3 8/3 o o 1 2 2 14 xj,Rl = [ 34/3 8/3 o] ' ZpRl = -J4 • Eliminació: KPR1 # 0.x¡,Rl # x¡,EI =} no es pot eliminar. * Separació: es selecciona coma variable de ramificació x1, creant-se els subproblemes (PE2) (x 1 :::; 11) y (PE3) (.r1 2:11): L = {(P E2), (PE3)) • Segona iteració: s'explora la branca i: 1 :=:;JI (PE2) • Relaxació: Es resol (PR2) : s'introdueix la constricció x1 :::: 11 i es reoptimitza a partir de T¡,Rl aplicant l'algorisme del simplex dual. X¡ X2 X3 X4 X5 Ít X1 X2 X3 X4 X5 f ¡ 1 o o o o 4/3 2 4/3 o 34/3 1 o o o o 1 11 1 2/3 o 2/3 o 8/3 TPR2 = o 1 o -1 o 1 /2 5/2 o R731 -2 -4/3 1 -1/3 o o 1 3/2 1 - 3/4 1/4 o 1 2 2 o 14 o o o 1/2 o 3/ 4 55/4 xj,R2 = [ 11 .)/2 11 /4]' ZpRZ = -13.75 Eliminació: no es pot eliminar. • Separació: es selecciona coma variable de ramificació x2, creant-se els subproblemes (PE4) (x2:::; 2) y (PE5) (x2 2: 3). L = {(P E4), (P E5), (P E3)}. • Tercera iteració: s'explora la branca r2:::; 2 (PE4) • Relaxació: Es resol (PR4) : s'introdueix la constricció Xz :=:; 2 i es re optimitza a partir de T¡,R2 ap li cant l'algorisme del simpl ex dual. f¡ h 1 o o o o 1 o JI 1 o o 2 o o 2 10 o 1 o -1 o 1 /2 o 5/2 o 1 o o o o 1 2 o o 1 3/2 1 - 3 /4 o 1/4 o o 1 o 1 o -3 / 2 1 o o o 1 o 8721 1 -1/2 o o o -2 o 1 -2 1 o o o 1/2 o 3/4 o 55/4 o o o 2 o o 3/ 2 13 xj,R4=[10 2 !]' • Eliminació: xj,R4 enter a=} solució de (PE4). Hem obt in gut la primera incumbe nt. z• := zj,R4, x• := x¡,R4. S'elimina (PE4) de la !lista: L = {(P E5), (P E3)}. • Quarta iteració: s'explora la branca r2 2: 3 (PE5) • Relaxació: Es resol (PR5) : s'introdueix la constricció Xz 2: 3 i es reoptimitza a partir de T¡,R2 aplica nt l'algorisme del simplex dual. S ol uooc:.s - Sol u ció dél - - • Ini ciali:..:i • P ri m E:'d. - ;e =~umi nista. >-'.:;:> oob le mes ~ ~;ai m it za a 11 5/ 2 1/4 55/ 4 ~ oo': ;:irob lemes '!S :-=c ·; :H imitza a h 2 10 1 2 - 3/ 2 1 - 2 1 3/2 13 ·~ ~ rn cumbent. :: .=:-3 . }. ~ ~?ti m itza a 7 Solucíons deis problemes de programació lineal entera 83 X¡ X2 X3 X4 X5 f¡ h .. ·- 1 o o o o 1 o JI o 1 o -1 o 1/2 o 5/ 2 o o 1 3/2 1 -3/4 o 1/4 o o o -1 o 1/2 1 -1 / 2 o o o 1/2 o 3/4 o 5.) /4 Variable basica de sortida XB, = h Y<i :'.'. O \fj E N =} dual il.limitat. primal infactible : f{PR5 = 0 • Eliminació: (PR5 ) no factible=} s'elimina (PE5). L = {(PE3)} • Quinta iteració: s'explora Ja branca x1 :'.'. 12 (PE3) • Relaxació: Es resol (PR3) s'introdueix Ja constricció x2 :'.'. 12 i es reoptimitza a partir de Tj,RI aplicant ]'algoritmo del simplex dual. X¡ X2 X3 1 o 473 o 1 2/3 o o 4/3 o o 1 X4 X5 /¡ 2413 o o 2/3 o 2 4/3 1 2 2 o 34 / 3 8/ 3 -2/3 14 Variable basica de sortida · xB , f¡. Y3 i :'.'. O \fj E N =} dual il.limitat. primal infactible: /{PR3 = 0 • Eliminació: (PR3) no factible=} s'elimina (PE3). L = 0 • Sisena iteració : L = 0 =>la solució Optima és l'associada a la incumb ent : lx?E =x"=[lO 2 1J'I lz?E - z" = -13 1 L 'arbre d 'exploració d 'aquest problema és: x, ~ 12 S z;.,= -1 3.75 x:.,=( 11,2.5,0.25)' x 2 ~2/ \~ 3 PE4) z,:_,= -13 § @ K~ , = ¡zj x:,,= ( 10, 2, 1 )' K~, = ¡zj z* = Z~, Solució del problema 52. • Inicialització L :={(PE!)} • Primera iteració es processa (PE!) 84 CoHecdó de problemes re.solts d ' lnvestigaóó Operativa Determinista . • Re laxa ci ó: Es resol (PRl) : X¡ ;r.., - o 1 5/4 -1 /4 o 5/2 l o -1 /4 1/4 o 5/2 o o - 3/2 1/2 l 3 o o l o o 5 xj,Rl = [ 5/2 5/2 o]' =?m = -5 • Eliminació: I<pm # 0, xj,Rl # x¡,El =:>no es pot eliminar. . . .. _ {.r1<2 (PE2) • Separació: variablederam1ficac1ox1=2.15 =:> - ); L = {(P E2) ,( PE3 )) X¡ 2'. 3 (PE3 • Se gon a it eració s'explo ra la branca x1 $ 2 (PE2) • Relaxació: Es resol (PR2) : s'afegeix la restricció x1 $ 2 a (PE!) i es reoptimitza a partir de Tj,Rl X5 f¡ o 1 5/4 -1 /4 o o 5/2 1J.n2 = 1 o -1 /4 1/4 o o 5/2 o o - 3/2 1 /2 1 o 3 o o 1/4 1-1741 o 1 -1 /2 o o 1 o o o 5 o 1 1 o o - 1 3 T ], R2 = 1 o o o o 1 2 o o - 1 o l - 2 2 o o -1 l o - 4 2 o o l o o o 5 xj,R2=[2 3]' • El im i nació : !> l<pR2 # 0, t> x¡,R2 = xj, E2 =:> es pot eliminar. t> Inicialització de la incumben! : zº := z¡,E2 = -5, x• := x¡,E 2 = [2 3]' t> Actualit.zació de la !lista : L := { ( P E3) } ( ATEN CIÓ : z¡,E2 = Z pni , i sabem q ue z¡,Rl és una fita inferior de z'j,E. Així dones, pode m assegurar que x¡, E = xj,E 2 i no caldria explorar el nus (PE3)). • Te rcera it e ració s'explora la branca x1 2'. 3 (PE 3) • Relaxació: Es resol (PR3): s'afegeix la restricció x1 2'. 3 a (PEJ) i es r eopt im itza a 5o J L ~~ ~_.;nis ta. ?E"2).( PE3)) ~ ~ -= ;.:llli tz a a = =": ;-: = [:2 3]' :; =- . :....Ji dones, ~ ~;ümi tza a Solucions dels prob lem es de programació lineal entera 85 pa rt. ir de T;,Rl X¡ X"I - X3 -X4 l'5 f¡ -- o 1 5/4 -1/4 o o 5/ 2 T~R3 = 1 o -1 / 4 1/4 o o 5/2 o o - 3/2 1 /2 1 o 3 o o l-i74l 1 /4 o 1 - 1 /2 o o 1 o o o 5 X ¡ X2 X3 X4 X5 f¡ o 1 o 1 o 5 o Tj,R3 = 1 o o o o -1 3 o o o - 1 1 -6 6 o o 1 -1 o -4 2 o o o 1 o 4 3 XpR3 =[ 0 3 ]' ZpR2 = -3 * E li minació: C> l\pR3 # 0. <> xf>R 3 = xf>E 3 =:>es pot el im inar. C> A ctua lit zació de la inc umbe n \: z'PE 3 = -3 f z• = - 5 =:>no s 'a ct u al it za. e> A ct ualit zació de la lli sta : L := 0. • Sis ena it er ació L = 0 => la so lu ció óptima és l'associada a la in cu mbent : [xf>E := x· = [2 3]' L ' arbre d 'ex plor ació és : x1 ~ 2 PE2) z~ , =- 5 X,= 2 x,= 3 z* = z* =- 5 l'<1 z¡,E := z• = - 5] Z! 1 =-5 x1 ~ 3 §z~, = - 3 X,= Ü x,= 3 Z.::C ,= -3 ~ 8 Solucions deis problemes de programaóó no lineal 87 8 Solucions dels problemes de programació no lineal. Solució del probl e ma 53 . a) Ca lcularem primer e ls punts estacionaris: [ 2x ¡ - X2 - X3 ] [ 2 -1 -1] [ xi ] [º] \if(x)= -x1+2x2 + xa \f(x") = [O] -1 2 ~ :~ = ~ -x 1 + x2 + 2xa -1 1 [ 2 -1 ~¡] #o=} x" = m únic punt estacionari. det -1 2 -1 1 Estudiem ara la convexitat de f(x) sobre el punt trobat: [ 2 -1 -1] \1 2 f(x)= -1 2 1 -1 1 2 la matriu Hessiana és constan\: es tracta d'una funció quadratica. Comprovem la definició de 1 'Hessiana: .Ó.¡ = 2 >o [ 2 -1 i , -"'2=det _1 2 =3>0 , .ó. 3 =detv·f(x)=4>0 .Ó.k > O, k = 1, 2, 3 =} v2 f(x) def + 'lx E IR 3 l'Hessia na és definida positiva arreu (f(x) est ri ctament convexa): el punt x• = [~] és un mínim global estricte de f(x). b) Punts estacionaris de f(x): [ er¡ -X i _ er~ - I¡ + 2xer2 \lf(x)= - e'' - ''+e'>-'> ] 2xa 88 CoHecció de prnblemes resolts d 'Investigació Operativa Determinista. Comprovem la definició de la .Hessiana sobre x·: '} 2 2 0 [er1-.r2 + er2-r1 + 4XjCx 1 + 2er1 -ex 1 -x 2 _ ex 2 -:r 1 v-/(J:) = -[X¡-X;'l _ e.r:;¡-X¡ fr¡-X2 + eX2-X¡ o o ~] ti.1 > O dones és suma de termes positius il:i = (ex1 -r2 +er2-.r1 )2+(er 1 -r2+er2-r1 )(ex1 -r2 +er2-x1 +4 xi e.r i +2exi )-(er 1 -x :i +t.r 2 -r 1 )2 = = (eX¡ -r2 + fX2-X1 )(é.t'¡ -.r 2 + EX:¡-X¡ + 4xieri + 2exi) > Q Ll.3 = 2Ci.2 >o ti.k >0, k= 1,2 ,3 =:>\12 /(x) def+VxEIR 3 b) l'Hessiana és definida positia arreu (f(x) estrictament convexa): el punt x· = [~] és un mínim global estricte de f(x). e) Es calculen els punts estacionaris de /(x): En aquest cas ens trobem amb un conjunt de punts estacionaris .Y" determina\ pels punts de IR2 amb x1 = x2. Comprovem ara la definició de la matriu Hessiana: [ ex1 -x 2 + ez-2-r1 V2 f(x) = -e.t"J -X2 _ eX2-X¡ il1 = eX¡ -x z + ex;i-x¡ > \lx E IR.2 .ó. 2 = (ex 1 -x 2 + er2-r1 )2 _ (ex1 -r2 + ex:i-x 1 )2 = O Ci.1 >O , Ci.2 =O=> \12 f(x) semidef + \lx E IR 2 La matriu Hessiana és semidefinida positiva arreu (f(x) és convexa): el conjunt de punt .:r · són mínims global febles. La següent figura mostra la respresentació grafica de la funció f(x) i del conjunt .r: 8 S oluooo. ~ d) Cá.:c... -~ = [:l G~-~ _.:-.. no r.é s.: - : í n::.: : ::~ ~=--- ... Sol u ci ó ceo :;:. - - • d: = ::::::..~ -~ . Du:•- .:"!' . : ~ mi nis ta. : = ='.= o¡ f:-:. - =: -tJ" 2- .r1 )2:::::::: :~,: ¡ - 2, ';) >o -o --O 1 és un -º :· = z;¡ - -~• pels punts -~-...;:¡de pu nt _,.::w ::e la funció 8 So lu cio ns deis prob l emes de programa.ció no l ineal x, X 2 d) Calcul de punts estacionaris: V f( x ·) =[O]:} \lf(x) = [ ~,~~:~ º + e'•+r, l e · +ex 1 -x':! { ex1 +r 2 = eX 1- :r:i • XJ + .l'? = XJ - l' ?. X?= -X?:::;, e x 1 - x2 :::::::: - er1 +x 2 } :::;. tri :::::::: - ex i :::;. l ,ll x " 1 X2 = Ü 89 l x2 = ül En aquest cas no existeixen punts estacionaris, i el conjunt solució x· és buit (el pr oblema no té solució). La funció f(x) no esta afitada inferiorment: pera un valor d ona t de x2, la funció objectiu decreix a mida que ho fa x1. Solució del problema 55 . oc11 = [ ~ ] La representació grafica d'aquest primer cas és: x, xº d1 x, Vj(x? • Factibilitat: Els punts a pa rt ir de x0 al llarg de d1 es represe nt en pe r: x(o)=x º+o d¡= ¡1+ 0 20] donat que x(o) ;::: Opera tot o:'.'. O la direcció és factible. • Descens: Fem el prod ucte escal ar amb el vector gradie nt : \lf(x 0)d1 = [2 -2 ] [~] = 4 > O donat que V f(x º)d1 > O, la direcció no és de descens. oc1 2= [~2] . 90 CoHecció de problemes resolts d'lnvestigació Operatfra Determinjsta. " J' Vfix? • Factíbilitat: x(a) = xº +ad' = [ 1 -a 20 ]. Per a qualssevol valor de a entre zero i a= 1/2 es satisfa x(a);::: O, sent dones d1 factible. • Descens: Vf(xº)d 2 = [2 -2] ¡- 12] = -6 <O . d2 és de descens. d3 = [~] Vfl.t 9 * Factibilitat: x(a) = [ 1 ;:a] ;::: O\lo >O, sent dones factible. • Descens: V f(xº)d' = [2 -2] [~] =O. En aquest cas, per tal de saber si d3 és de deseens hem d'estudiar les segones derivades de f(x) al llarg de d3: V2 f(xº) = [ 2 -2] -2 2 La corbatura de f(x) al llarg de d3, g"(a) ens pot indicar, si la direcció és de descens (g"(a) <O) o d'ascens (g'.'(a) >O). En el nostre cas és: g"(a) = d3 'Vf(xº)d 3 = [2 2) [ ~ 2 ~ 2 ] [~]=O Així dones, l'estudi de la eorbatura tampoc ens permet dir si la direcció és de descens. Solució del problema 57. Calcul de la direcció de decens:: Es calcula en primer !loe la direcció de moviment del metode del gradient: 8 Sol :.a:;c:s Dire::.: :;:; -: E ls va.::-5: :::-- ~ i les i:e :;,: .:::.: • P ri=~-~ _ .... - ~- = .::: = ... • Se0 ona ::e::ac !)1 = :::t: - ~,-:¡, Jete rmi n ís t a. '-e :t ent re zero i --:r si d3 és de ~ _ e:sde descens :::.::. ~ de descens. 8 Solucions deis problemes de pr ogramaóó no li nea l f(x) =xi+ X~ - (x2 - X3) 3 + X¡ X2 X3 [ 2X¡ + X2X3 ] V' f(x )' = 2x2 -3(x2 - ~3)2 + X ¡ X3 3(x2 - X3) -+ X¡X2 xº = [ ~:] vf (x 0) = [~d Direcció de moviment del metode del gradient: Idº = -v f(x º ) = [ ~ 3 ] Exp lo ra c ió lin e al: : 91 A continu ació es re alitza e xplorac ió lineal per Fib onacci a mb N = 4 i interva l d ' in certessa [O, 0.1], de l on ditud inicial d1 = 0.1. La fun c ió univalu ada s obre la que s'aplica ra Fibo nacci és: g(o) =f(x 0 +od 0) = J(-3o+ l,3o - J,o - l) g( o) = - 17 03 + 33o2 - 190 + 3 Els valors deis núm er os de Fibonacci que s' u saran són: F0 = F1 = 1 i les iteracions de l pro cés són: • Prin1era iterac ió: F2 = 2 F3 = 3 * O¡ = 0 + &d¡ = ~0.5 = 0.3 g(0.5) = -0.189 Fs ·) • 02 = 0.5 - Psd ¡ = 0.5 - 0.3 = 0.2 g(0.2) = 0.384 F4 = 5 • g(0 .2) > g(0.5): es descarta [O, 0.2[. El nou interval d' incer tessa és [0.2, 0. 5] . g(<J) 0.384 0.3 (J .2 a .5 - 'ó .189 • Segona i t erac ió: • 03 =(}o+ !;;Ld, = 0.4 g(0.4) = -0 .408 - r s * g(0.4) < g(0 .5 ): es desc arta [0.2, 0.3[. El nou int erval d'inc ertessa és [0 .3, 0.5] 98 CoHecció de problemes resolts d'lnvestigació Operativa Determinista. La dimensió del subespai M és dim(M) =l. llavors qualsevol vector de M serveix coma base d'aquest subespai: Solució del problema 69. Per tal de comprovar si x• és optim de (PNL) hem de comprovar les condicions suficients de segon ordre (que inclouen, recordeu, a les de primer ordre). El primer pas és trobar els multiplicadors de Lagrange µ1 i µ2 associats a x·, si es que aquests existeixen. Per tal de calcular aquests multiplicadors usarem les condicions necessaries de primer ordre (co ndicions de Khun i Tucker). Calculem el gradient i la matriu Ja cob iana sobre el punt x": I • , _ [ 0.6691 ] V f(x ) - -O 2675 [ 2x 1 "Vg(x) = ? 6x; - 4x 1 "Vg(x")= [ -1 -1] 3.5 -1 S'observa que la matriu Jacobiana és de rang complet, sent dones x· regul ar . Les dues constriccions són actives sobre x•. Si plantejem la prim era con di ció de Khun i Tucker tenim: "Vf(x·)+ [µj µ2)"Vg(x") =O 0· 6691 - µj + 3-5 µ2 =o} 1 • = -0.05947 • = - 0.208161 -0.2676 -µj - µ; =o _µ, ' µ2 . Les constriccions del probl ema (PNL) estan plautejades com de 2: O. Aixó implica que la condició de signe sobre els multiplicador (tercera condició de Kuhn i Tucker) és µ" ~O, que és satisfeta pe! vector trobat. Així dones, el par ell x• = [- 1/2 1/4]', µ• = [ -0 .05947 -0.20816] sat isfan les condicions necessáries de primer ordre. Com provem ara les de segon ordre, calcul ant la definició de la matriu Hessiana de la funció Lagrangiana sobre el subespai tangent M. Ca!culem primer v;.c(x·' µ•): "V2f(x·) = [0 .8363 0.2007] v2 (x") = ¡2 º] v2 (x") = ¡-1 0 º] 0.2007 0.1338 ' 91 o o , 92 o o 2 v;.c(x',µ·) = "V 2 f(x·) + ¿µ;"V 2 g;(x·) = j=l = [º 8363 0-2007 )-0.05947 [2 º]-0.20816 ¡- 10 0.2007 0.1338 o o o = def + º] [ 2.799 0.2007] Ll1 = 2.799 > o} o 0.2007 0.13 38 Ll2 =o 334 >o Donat que v;,.C(x•, µ•) és def +sobre JR.2, també ho sera sobre qualsevol subespai de JR -2. En part icul ar, sera def + sobre el subespai tangent M. Així dones, el punt x· és un mínim local estricte de (PNL). Solució del problema 70 . S' ha de comprovar la definició de l'Hess ia na de la funció Lagrangiana s obr e x·, Á0, "Vi,.C(x• , Á") 8 : Dona: ~-~:: no es; :· ~.: S olució -=.,, ;:. B= =~ Es ca.:~:~~ L ~ ..... ? .. .:.;...: ! selecc:: :-:- ··==..JI ~u nnin ista. ~co m a base ,=• ::E su fic ients ::.;¿ !:5 crobar els = Per ta l de condicio ns :..es dues cons_.. ;~n im: ...:3 que la con di- .;-: és sa tisfeta - : ?GS16 ] sat is- = alc ulan t la · ~1 . C alc ulem -. ~ o .:. , = 2.799 > º} def + .:. - = 0.334 >o <=~de IR?. En r..::: :::ín im l oca l ~[( x " , ,\,") 8 Soluó ons deis problemes de program ac ió no lineal sob re el subespai M: v;c( x" .>:)=v 2 /(>:")+.\·'vh(x")= [ 1~2 - 1/4 1/2 o - 1/4 -1/4] [2 - 1/4 + (-1/ 4) o 1/4 o [ -1/ 2 = 1/2 -1/4 99 o º] 2 o o 1/2 -1 /4 ] - 1/2 -1/4 -1 /4 1/4 La matriu v;C(x", .\") és ind efi nida. Hem de comprovar la definició de Z'v;[(x ", .\")Z on Z és una base del s ubespa i M = {y 1 vh (x")y =O}. S' han de trabar dos vectors z1 i z2 pertanyents a M i lin ea lm e nt independents . La condició de pertinen<;a a M és: vh(x " )=[ 2 2 -1] vh(x ")y =o=} 2y¡ + 2y2 -y3 =o Tro b em ara dos ve ct ors v ec tors lin ea lm ent indepe nd e nt qu e sat isfac in (1): Y3 =O Y1 = 1 =;. Y2 = - 1 Y3 = 1 Y1 = O=;. Y2 = 1/2 ; Ca lul em Z'v;C(>: ", .\")Z i la se va definició: Z¡ = [ ~l] ) l ,, . [ ·H z . [ ~· 1~2] Z'v; c(x "Y) Z = ¡- 2 1 /2 ] t!.1 = -2 < º} . 1 /2 - 1/8 [!.2 = 0 sem 1 def- (1) Donat que Z'v; C(x", .\ " )Z és sem idef - , el punt estacionari x· pot s er m axim local, tot i que no es pot asseg ur ar. So lució del probl e ma 72 . Hem de come n<¡ ar rea lit zant la selecció de les variables dependents i independents sobre x. Es calcula préviament la ma triu Jaco biana vh(x): x 2 [ ::,¡. + Xz - X3 + 2x4 X5 - X5 + 2 ] h( x) = 3x2 3x2 7 T + x2X3 - 2x2 + T + xs - 2' [ x1 1 -1 2xs 2x4-l] \lh(x) = 3x1 X3 -2 x2 3x4 1 que. ava lu ada sob re x = [ 1 O 3 1/ 2]' propo rciona: vh(x) = [ ~ - 1 o 3 : ] La variable X2 no hauria de ser ind ep e ndent, dones es traba a fita inferior. Una possible selecció de variable s depe nd ents seria y = [X¡ X3 ]' ja que ambdu es es traben e ntr e fites i la 100 CoHecció de problemes resolts d'lnvestigaó ó Operativa De terminista. ma t. ri u: [ 1 - 1] 'Vyh(x) = 3 O és no singular. Les variables independients serien z = [x 2 x4 x5 ]' , y la ma triu \, h( i·): 'V,h(x) = [: 1 1] 3 1 Si calculem l 'expressió del gra diente: 'V f (x)=[;i-xs+3 - 6 2 x2x 3_ 4 - 4 -x 1] i l'avaluem sobre x = [ 1 O 3 'V f(x)=[7-6-l-4-IJ 1/2]' s'obté: 'Vyf(x)=[7 -1 ] 'V,f(x) = [- 6 - 4 -1 J Determ in em el gradient re duit sobre el punt x. A la practica, el calcul del gradient redu'it es duu a terrne en dues passes. A la primera es calcula el producte >.' = 'V yf(y , z)['Vyh (y , :)J1 mitja n<;a nt la resolu ci ó del sistema d'equacions 'V y h(y ,z)' ).. = 'Vy f( y,z)'. La raó d' aque st procedim ent és que és mé s estable i eficie nt tr eba llar amb la factorització LU de la matriu 'Vyh(y . : ) que amb la seva inversa: La factorització LU de Vyh(x) és : [l -Ji ¡1 º] ¡1 -li 'Vyh (x) = 3 O = 3 1 O 3 Resole nt el sistema s' obté el val or de Á: [l 3] [¡ ][ l 3 ][ ;.,1 ] [ 7] {).. 1=-1 - 1 o )., = - 1 3 1 ;.. , = - - 1 =;> ;.. , = - 2 A continuació es procedeix al calcul de r = 'V , f(y , z )' - 'V , h(y , z )').. : Tenint en compte que z = [O 1/2] i les lites 1, =O i u, = [ 4 4 4], s'obté .C. := - 1· : Un cop determin ada llz (i després de comprobar que és diferent de ze ro), es procedeix al calcul de .C.y . En la practica, aquest calcules fa a través de la resolució del sistema d'equacions 'Vyh( y, z) D.y = -'V ,h(y, z) fl z: 3 [ -24 ) =;> { .C.y ¡ = -46/3 - 46 t. y, = 26/3 3 Te:1 i=: =-= ::: :: la 1 ::g::; _: ~ ::• El c::.L; ; _ _;,;_;. ~ 5 oc ;_gj::a.'. C.:- _ El ,- e: ::' - - = ~ ~~:nn inis ta. -:;, c- ,h• r): - 1] c ·~: en r re duú ; :- ,h( y. :W1 ~ :"'° d' aque st ··-:-e la matriu ..?- ~.:- = -r : .,, :~:xede ix al :. equ ac1ons = - 46/3 ..:.. ,, = 26/3 8 So l uc i ons de ls problemes de programa.ció no li neal 1 01 [-46/3) Ay = 26/ 3 Calcul em ara la longi tud de pas maxim a ó. Tenint en compte que I = O i 11 = [4 4 4 4 4 ]' tenim que: y = [ ~)',Ay = [- 46/3 ) 26/3 - 1 } 3 a,, = 46,73 - . 3 3 - - _ _ (4 -3) =>o,=mm {45, 25} -46 ay, -'f613 z = UJ , Az = [ 1: 1] &,, = (4 - 0)/ 9 = 4/9 } 4 3 7 3 &,, = (.j - 1) / 11 = 3/11 => &, = min{ 9" 11 ' 8} = ]] &,, = (.j -1/2)/4 = 7/8 - . { 3 / } 3 a = mm 46 , 3 11 = 46 Prenem a ra una longitud de pas arbit rária a · = &/2 = 3 /9 2. El punt iterat serit: 1 - 4 6/3 1 /2 o 9 2i /9 2 1 [ 27 /92 ] x = x +a· Ax = 1 3 3 26/ 3 151/46 ; f¡ = [ 1 1/2 ] , i = 12 5/92 + 92 = 1 11 125/92 5 /45 29/46 1/2 4 29/46 e - . 'bl . _) [ 1.984 88) . om e ra d'e sperar, el punt x no es fach e. Jª que h(x = 3.26364 i O. Aphqu em una passa del procés it e ratiu de r ec upera ció de factibilitat a partir de i . El calcul de Af¡ -['V yh(y , z Ji1 h(f¡, i) es realit za resolent el siste ma \7 ,h(y , z)A f¡ = - h( f¡, i): [ 1 -1 i -= [ 1 l [ 1 3 O A y 3 1 - 1 i [ Af/1 l = -h(f¡ i) = [ -1.9 8488] => { Af¡1 = -1.08788 3 A f¡ 2 ' -3 .26364 A fJ2 = 0.897 Ten i nt en co mp te el valor de les vari ab les Y' = [ 1 /2 la l ongitud de pas máxima al llarg de Af¡ és: &y, = ~ = 0.4596 } - - - 4 - 1 51/ 46 - => ª" -0·4596 ª"' = 0.89 1 = 0.7 991 és adir: f¡ -Y +oyAf¡"' [ 3 . ~~48) 151/46]' i les fites u, = [ 4 4], ly = O, o; = min{ 1, 0.459 6} = 0.4596 [ -0 .3186] h(y, i) = 0.3969 El nou punt i esta més a prop de la hipersuper fí cie S de les constriccions h( x) =O que el punt original. Com que a y = &y,, hem d'inter ca nviar f¡ 1 a mb una variable independent i, aprop iada. El valor de 'V h( x) sobre el nou punt i = [Y', -''] és: \7 x _ [ 1 /2 1 - 1 1.2608] f( ) - 3/2 1.2826 0. 293 4 4.0760 102 CoHecció de problemes resolts d'lnvestigaóó Operativa Determfoista. La variable z1 = x2 esta entre lites i, junt amb ji2, proporciona un nou 'Vyh(y , z) no singular: [ 1 -1 ] V yh(y,:) = 1.2 826 0.2934 det('Vyh(y, z)) = 1.57608 així dones, es por intercanviar fj 1 = x1 per i1 = x2.