Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB)

I 0 flashcards i 15 preguntes més al document.

Text del document

APUNTS MATEMÀTIQUES II Grau en Administració i Direcció d'Empreses Universitat de Barcelona AprenAI 2026-2027 Apunts de Matemàtiques II (ADE i Economia, UB): optimització restringida, programació lineal, càlcul integral, EDO i aplicacions econòmiques resoltes. APREN.AI Índex Optimització amb restriccions d'igualtat 1 Fonaments i mètodes de resolució elemental 1. Formulació del programa d'optimització amb restriccions d'igualtat 2. Conjunt factible i concepte d'òptim restringit 3. Resolució geomètrica: mètode gràfic de tangència 4.

Mètode directe o de substitució de variables 2 Mètode dels multiplicadors de Lagrange Funció de Lagrange i multiplicadors Condició necessària de primer ordre i punts crítics Matriu hessiana restringida i condició de segon ordre Estudi de la forma quadràtica sobre el subespai tangent 3 Interpretació econòmica i aplicacions Interpretació econòmica del multiplicador de Lagrange Minimització de costos amb tecnologia Cobb-Douglas Model financer de selecció de carteres de Markowitz 4 Optimització amb restriccions de desigualtat — Formulació i resolució gràfica 1. Estructura general i programa canònic de desigualtats 2. Geometria del conjunt factible i existència d'òptims 3.

Resolució pel mètode gràfic: línies de nivell i tangència 4.

Comparativa pràctica: cas lineal i cas quadràtic sobre el mateix recinte Programació lineal 5 Teorema fonamental i resolució de models bàsics Estructura del programa lineal canònic El teorema fonamental de la programació lineal Programes lineals acotats i existència d'òptims Procediment de resolució per avaluació de vèrtexs Solucions òptimes alternatives i casos especials 6 Anàlisi de sensibilitat amb informes de Solver Fonaments de l'anàlisi de sensibilitat post-òptima Interpretació de la taula de cel·les canviants Interpretació de la taula de restriccions i preus ombra 7 Formulació de models econòmics clàssics Model de planificació de la producció Model clàssic del transport Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB) 1 Model lineal de selecció de carteres financeres Càlcul integral 8 Primitives, integrals immediates i mètodes d'integració 1.

Concepte de primitiva i la integral indefinida 2. Integrals immediates, linealitat i integració logarítmica 3. Mètode d'integració per parts 4. Mètode de canvi de variable (substitució) 9 Integral definida, teorema fonamental i càlcul d'àrees 1. La integral definida: concepte geomètric i propietats 2. Teorema fonamental del càlcul i regla de Barrow 3.

Càlcul d'àrees: canvis de signe, regions entre corbes i funcions a trossos 10 Aplicacions econòmiques de la integral Reconstrucció de funcions totals a partir de magnituds marginals Equilibri de mercat i excedents del consumidor i del productor Fluxos continus acumulats i esgotament de recursos naturals Equacions diferencials 11 Concepte, ordre i tipologia de primer ordre Fonaments de les equacions diferencials ordinàries Solucions d'una equació diferencial Formes d'expressió d'una EDO de primer ordre Equacions de variables separades Equacions de variables separables 12 Equacions lineals de primer ordre i de Bernouilli Estructura de l'equació diferencial lineal de primer ordre Resolució de l'equació lineal reduïda Resolució de l'equació lineal completa de primer ordre L'equació diferencial de Bernouilli Transformació a equació lineal mitjançant canvi de variable 13 Equacions lineals de segon ordre a coeficients constants Estructura de l'equació de segon ordre L'equació característica i la solució homogènia Càlcul de la solució particular pel mètode de coeficients indeterminats El problema de valors inicials: determinació de i 14 Models dinàmics en economia — Creixement exponencial i ajust de preus Model de creixement exponencial i capitalització instantània Model lineal d'ajust del preu de Walras Estabilitat dinàmica de mercat i convergència C 1 C 2 Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB) 2 Model de difusió i corba logística Model de mercat amb expectatives de preus de segon ordre 15 Equacions diferencials — Aplicacions addicionals i llei de refredament Modelització tèrmica: la llei de refredament de Newton Aplicació forense: cronologia de la mort a partir de mesures tèrmiques Propietats diferencials geomètriques de corbes planes Funcions de demanda amb elasticitat-preu constant Limitacions analítiques: presència d'integrals no elementals 16 Resolució pràctica d'exercicis seleccionats d'optimització i anàlisi dinàmica Criteris de selecció del mètode de resolució Optimització amb multiplicadors de Lagrange en models de tres variables Programació lineal amb polígons irregulars i solucions múltiples Càlcul d'integrals definides amb punts de tall i canvis de signe Resolució de problemes de valor inicial per a equacions diferencials de segon ordre 17 Formulari 1.

Optimització amb restriccions d'igualtat 2. Optimització amb desigualtats i programació lineal 3. Càlcul integral de funcions reals d'una variable 4. Equacions diferencials ordinàries (EDO) Errors típics d'examen Solucions de les preguntes de repàs Aquests apunts poden contenir errors o omissions. Són un material de suport i no substitueixen el temari oficial ni el professorat: contrasta la informació important. Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB) 3 1 Fonaments i mètodes de resolució elemental EN ACABAR SABRÀS Formular formalment un programa d'optimització amb restriccions d'igualtat identificant la funció objectiu i el conjunt factible.

Distingir geomètricament i analíticament entre un extrem lliure i un extrem restringit. Trobar i representar la solució d'un model de dues variables mitjançant la tangència de corbes de nivell. Resoldre analíticament programes d'optimització mitjançant el mètode de substitució de variables. PENSA-HI ABANS DE LLEGIR 1 Si busquem el mínim d'una funció sobre una corba concreta, per què no n'hi ha prou amb trobar on les seves derivades parcials valen zero? L'optimització matemàtica constitueix una eina fonamental en la gestió empresarial i l'economia, ja que permet distribuir de forma eficient recursos que són escassos entre diferents finalitats possibles.

Quan aquests recursos o condicions tecnològiques s'han de complir de manera exacta, sorgeixen els problemes d'optimització amb restriccions d'igualtat. Optimització amb restriccions d'igualtat 1 Fonaments i mètodes de resolució elemental 2 Mètode dels multiplicadors de Lagrange 3 Interpretació econòmica i aplicacions Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB) 4 ESQUEMA Optimització amb restriccions d'igualtat 1. Formulació del programa d'optimització amb restriccions d'igualtat Un programa d'òptims condicionats per igualtats consisteix a trobar el valor màxim o mínim d'una funció escalar sotmesa a un conjunt d'equacions que les variables han de satisfer estrictament.

DEFINICIÓ De forma general, un programa d'optimització restringit per igualtats s'expressa de la manera següent: on: és la funció objectiu (escalar). són les variables de decisió o instrumentals. són les funcions escalars de restricció. són les constants associades a cada restricció. L'abreviació «s. a:» significa «subjecta a» o «restringida a». Perquè el problema tingui graus de llibertat i sentit d'optimització, habitualment el nombre de restriccions és menor que el de variables ( ). A més, s'assumeix que totes les funcions implicades tenen derivades parcials segones contínues.

Fonaments i conceptes Funció objectiu i conjunt factible Mètodes elementals Resolució gràfica i substitució Mètode de Lagrange Multiplicadors i condicions d'extrem Interpretació econòmica Preus ombra i assignació de recursos m Optimitzar s. a: z = f(x , x , … , x ) 1 2 n g (x , x , … , x ) = b 1 1 2 n 1 g (x , x , … , x ) = b m 1 2 n m z = f(x , … , x ) 1 n x , … , x 1 n n g (x , … , x ) i 1 n m b , … , b 1 m m < n Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB) 5 EXEMPLE Una empresa elabora un producte emprant dos factors productius mitjançant una tecnologia Cobb-Douglas donada per . Els costos unitaris de compra d'aquests factors són de 2 i 8 u.m., respectivament.

Si es volen fabricar exactament 32 unitats de producte amb el mínim cost possible, el programa es planteja com: En aquest cas disposem de variables instrumentals ( i ) i equació de restricció. COMPROVA-HO 2 Quina condició sobre el nombre de variables n i restriccions m ha de donar-se en general perquè existeixi elecció possible en un programa restringit? 2. Conjunt factible i concepte d'òptim restringit Abans d'avaluar la funció objectiu, cal delimitar quins punts de l'espai estan permesos pel programa.

DEFINICIÓ El conjunt factible (o conjunt d'oportunitats/admissible) és la regió de punts del domini de la funció objectiu que compleixen totes les restriccions d'igualtat alhora: Qualsevol element que pertany a rep el nom de punt factible. En el problema de minimització de costos de la funció Cobb-Douglas anterior, la restricció equival a . Elevant al quadrat ambdós costats s'obté la hipèrbola equilàtera en el primer quadrant ( ). El punt és factible perquè satisfà . Un punt factible és un òptim del programa si fa que la funció objectiu assoleixi el seu valor extrem (màxim o mínim) sobre el conjunt . La imatge corresponent, , és el valor òptim restringit.

Tipus d'òptim Domini sobre el qual s'optimitza Exemple amb Òptim lliure Tot el domini natural de la funció a Màxim absolut a amb valor Òptim restringit Només sobre el conjunt factible (subconjunt de ) Amb restricció , el màxim és a amb valor Com es comprova a la taula comparativa, l'òptim restringit i l'òptim lliure gairebé mai coincideixen, ja que l'òptim lliure rarament compleix de forma espontània les restriccions imposades. Q(x, y) = 4x y 0,5 0,5 { min s. a: C(x, y) = 2x + 8y 4x y = 32 0,5 0,5 n = 2 x y m = 1 A = {(x , … , x ) 1 n R : n g (x , … , x ) = i 1 n b , i = i 1, … , m} A 4x y = 0,5 0,5 32 x y = 0,5 0,5 8 xy = 64 x > 0, y > 0 (16, 4) 4 16 = 4 4 4 2 = 32 (x , …

, x ) 1 0 n 0 A A z = 0 f(x , … , x ) 1 0 n 0 z = 1 x 2 y2 Rn (0, 0) z = 1 A Rn x + y = 1 , (2 1 2 1 ) z = 2 1 Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB) 6 COMPROVA-HO 3 Pot un punt que no satisfà una de les equacions de restricció ser considerat l'òptim del programa? 3. Resolució geomètrica: mètode gràfic de tangència Per a problemes amb dues variables instrumentals ( ) i una equació de restricció ( ), la solució es pot trobar de forma visual representant la geometria del model en el pla. La restricció descriu una corba al pla.

Per la seva banda, la funció objectiu genera una família de corbes de nivell , on cada corba recull les combinacions de punts que assoleixen el mateix valor de funció . En la gran majoria de casos, l'òptim restringit es troba en el punt de tangència entre la corba de restricció i la corba de nivell més avantatjosa. Gràfica de tangència entre corbes de nivell i la paràbola de restricció. Considerem el programa següent: La restricció és la paràbola . Les corbes de nivell de la funció objectiu són rectes paral·leles amb pendent negatiu, . Si desplacem la recta cap amunt (augmentant el nivell ) mentre manté contacte amb la paràbola, l'últim punt de contacte és el punt de tangència.

Aquest punt és , on s'obté el valor màxim . n = 2 m = 1 g(x, y) = b f(x, y) = c k c k { max s. a: z = x + y x + y = 1 2 y = 1 x2 x + y = c k y = x + c k c k , = (2 1 4 3 ) (0,5; 0,75) k = 0,5 + 0,75 = 1,25 Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB) 7 COMPROVA-HO 4 Quina és la interpretació geomètrica de la condició d'òptim en el mètode gràfic per a dues variables? 4. Mètode directe o de substitució de variables El mètode directe (o eliminació de variables) consisteix a aïllar una o diverses variables d'entre les equacions de restricció per substituir-les directament dins de la funció objectiu.

Això redueix el programa restringit original a un problema d'optimització lliure d'ordre menor. Aïllar variables: Aïllar variables en funció de les restants a partir de les equacions de restricció. 1 m n m Substituir: Inserir aquestes expressions a la funció objectiu per definir una funció auxiliar que només depèn de les variables no aïllades. 2 Calcular punts crítics: Trobar la condició necessària derivant la funció auxiliar respecte a cadascuna de les seves variables i igualant les derivades parcials a zero. 3 Classificar els punts: Utilitzar la matriu hessiana o la segona derivada per determinar si el punt crític és un màxim o un mínim.

4 Recuperar la solució completa: Trobar el valor de les variables que s'havien aïllat inicialment i avaluar el valor òptim. 5 Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB) 8 EXEMPLE Resolem el programa següent amb restricció lineal: De l'equació de restricció aïllem . Substituint a la funció objectiu obtenim la funció auxiliar: Apliquem la condició necessària de primer ordre: Recuperem la variable : Analitzem la matriu hessiana d'aquesta funció auxiliar: Com que i , la matriu hessiana és definida negativa a tot arreu. Per tant, el punt és un màxim estricte amb valor òptim: { max s.

a: u = xy + 2yz + xz x + 2y + 3z = 1 x = 1 2y 3z u(y, z) = (1 2y 3z)y + 2yz + (1 2y 3z)z = 2y 2 3z 2 3yz + y + z = 4y 3z + 1 = 0 y u = 6z 3y + 1 = 0 z u (y, z) = , ( 5 1 15 1 ) x x = 1 2 ( 5 1 ) 3 = ( 15 1 ) 1 5 2 = 5 1 5 2 Hu(y, z) = = y2 u 2 z y u 2 y z u 2 z2 u 2 ( 4 3 3 6 ) H = 1 4 < 0 H = 2 ( 4)( 6) ( 3) = 2 24 9 = 15 > 0 , , (5 2 5 1 15 1 ) u = 0 u , , = ( 5 2 5 1 15 1 ) 15 2 Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB) 9 EXEMPLE Considerem ara dos casos addicionals: Cas 1: Optimitzar subjecte a . Aïllem fàcilment , la qual cosa dóna la funció auxiliar d'una sola variable . Derivant: Per a tenim ; per a tenim . La segona derivada és : En : és un mínim amb valor .

En : és un màxim amb valor . Cas 2: Maximitzar subjecte a dues restriccions: i . De la segona equació obtenim . Substituint a la primera: . La funció auxiliar resultant és: Imposant primera derivada nul·la: . D'aquí resulta i . Com que , el punt és un màxim amb valor màxim . ERROR FREQÜENT El mètode directe és idoni per a restriccions lineals on aïllar una variable és immediat. Quan les restriccions són no lineals, aïllar una variable sovint introdueix arrels quadrades, pèrdua de solucions (signes positius o negatius omesos) o dominis d'indefinició.

Per a aquests escenaris o quan l'aïllament algebraic no és possible, el procediment general que cal emprar és el mètode dels multiplicadors (vegeu «Optimització amb restriccions d'igualtat — Mètode dels multiplicadors de Lagrange»).

z = 2xy x + 2 y = 3 y = 3 x2 z(x) = 2x(3 x ) = 2 6x 2x3 = dx dz 6 6x = 2 0 x = ±1 x = 1 y = 3 ( 1) = 2 2 x = 1 y = 3 1 = 2 2 = dx2 d z 2 12x x = 1 = dx2 d z 2 12 > 0 ( 1, 2) z = 0 4 x = 1 = dx2 d z 2 12 < 0 (1, 2) z = 1 4 u = xy + 2xz + yz x + y + z = 2 x y = 6 y = x 6 x + (x 6) + z = 2 z = 8 2x u(x) = x(x 6) + 2x(8 2x) + (x 6)(8 2x) = 5x + 2 30x 48 = dx du 10x + 30 = 0 x = 3 y = 3 6 = 3 z = 8 2(3) = 2 = dx2 d u 2 10 < 0 (3, 3, 2) u = 0 3 Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB) 10 IDEES CLAU Un programa d'òptims amb restriccions d'igualtat maximitza o minimitza una funció objectiu sobre el conjunt factible de punts que verifiquen les equacions.

El conjunt factible o d'oportunitats està format pels punts del domini de la funció objectiu que compleixen estrictament totes les restriccions del model. L'òptim lliure i l'òptim restringit solen diferir, ja que el màxim o mínim global de la funció rarament satisfà les condicions imposades per les restriccions. Geomètricament, per a dues variables i una restricció, l'òptim es troba habitualment en el punt de tangència entre la corba de restricció i una de les corbes de nivell. El mètode de substitució consisteix a aïllar variables en la restricció per transformar el problema restringit en un d'extrem lliure, sent especialment indicat quan les restriccions són lineals.

COMPROVA EL QUE HAS APRÈS 5. Com es defineix formalment el conjunt factible d'un programa d'optimització amb restriccions d'igualtat? 6. Per què sol exigir-se que el nombre de restriccions d'igualtat m sigui menor que el de variables n? 7. Quina limitació principal presenta el mètode de substitució directa quan les restriccions no són lineals? OPTIMITZACIÓ AMB RESTRICCIONS D'IGUALTAT 2 Mètode dels multiplicadors de Lagrange EN ACABAR SABRÀS Construir la funció de Lagrange associada a un programa amb restriccions d'igualtat. Resoldre el sistema de condicions de primer ordre per determinar els punts crítics. Formar la matriu hessiana restringida respecte a les variables instrumentals.

Classificar els punts crítics analitzant la forma quadràtica sobre el subespai tangent. PENSA-HI ABANS DE LLEGIR 8 Com podem utilitzar el càlcul diferencial per optimitzar una funció quan les variables no es poden moure lliurement sinó que estan lligades per equacions? Quan un problema d'optimització presenta múltiples variables o diverses restriccions d'igualtat, el mètode de substitució directa pot resultar impracticable (vegeu «Optimització amb restriccions d'igualtat — Fonaments i mètodes de resolució elemental»).

En aquest context, el mètode dels Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB) 11 multiplicadors de Lagrange permet transformar un problema condicionat en un sistema analític equivalent al d'extrems lliures mitjançant una funció auxiliar. Funció de Lagrange i multiplicadors Considerem el programa general amb variables instrumentals i restriccions d'igualtat (on ): DEFINICIÓ La funció de Lagrange (o lagrangiana) associada al programa és una funció escalar de variables definida com: Els paràmetres auxiliars s'anomenen multiplicadors de Lagrange. Aquesta expressió incorpora cada restricció igualada a zero, ponderada pel seu multiplicador respectiu.

La funció substitueix la funció objectiu original en tot el procediment d'optimització. EXEMPLE Plantegem la funció de Lagrange per a tres programes diferents: Per a minimitzar subjecte a : Per a maximitzar subjecte a : Per a maximitzar subjecte a i : COMPROVA-HO 9 Quantes variables i quantes equacions conté la lagrangiana d'un programa amb 4 variables i 2 restriccions d'igualtat? Condició necessària de primer ordre i punts crítics Per identificar els candidats a extrem relatiu en un punt interior del domini, s'estableix la condició de primer ordre. n m m < n Optimitzar s.a: z = f(x , … , x ) 1 n g (x , … , x ) = b 1 1 n 1 g (x , … , x ) = b m 1 n m n + m L(x , … , x ; λ , …

, λ ) = 1 n 1 m f(x , … , x ) 1 n λ i=1 m i (g (x , … , x ) i 1 n b ) i λ , … , λ 1 m R z = 2x + 8y 4x y = 0,5 0,5 32 L(x, y; λ ) = 1 2x + 8y λ (4x y 1 0,5 0,5 32) u = xy + 2yz + xz x + 2y + 3z = 1 L(x, y, z; λ ) = 1 xy + 2yz + xz λ (x + 1 2y + 3z 1) u = xy + 2xz + yz x + y + z = 2 x y = 6 L(x, y, z; λ , λ ) = 1 2 xy + 2xz + yz λ (x + 1 y + z 2) λ (x 2 y 6) Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB) 12 DEFINICIÓ Un punt crític restringit (o estacionari) és tot punt factible que, juntament amb un vector de multiplicadors , anul·la el vector gradient de la funció de Lagrange associada.

El sistema d'anul·lació del gradient consta de equacions: Observem que derivar respecte a cada multiplicador recupera directament l'equació de la restricció -èsima, garantint que qualsevol solució del sistema sigui necessàriament factible. (x , … , x ) 1 0 n 0 (λ , … , λ ) 1 0 m 0 n + m = 0, x j L = (g (x , … , x ) b ) = 0, λ i L i 1 n i j = 1, … , n i = 1, … , m λ i i Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB) 13 EXEMPLE Trobem els punts crítics del programa: Construïm el sistema de derivades parcials primeres: El programa té un únic punt crític: amb multiplicadors i .

COMPROVA-HO 10 Per què la derivada parcial de la lagrangiana respecte a un multiplicador assegura la factibilitat del punt? max s.a: u = xy + 2xz + yz x + y + z = 2 x y = 6 = y + 2z λ λ = 0 x L 1 2 = x + z λ + λ = 0 y L 1 2 = 2x + y λ = 0 z L 1 (x + y + z 2) = 0 (x y 6) = 0 Sumem la primera i la segona equació per eliminar : . 1 λ 2 x + 2y + 3z 2λ = 1 0 λ = 1 2 x + y + 3z Substituïm a la tercera equació: . 2 λ 1 2x + y = 2 x + y + 3z 0 3x + y 3z = 0 Formem el sistema lineal de 3 equacions amb les restriccions: La resolució d'aquest sistema de Cramer dóna el punt . 3 3x + y 3z = 0 x + y + z = 2 x y = 6 (x, y, z) = (3, 3, 2) Recuperem els multiplicadors: , i de la primera equació obtenim .

4 λ = 1 = 2 3 + ( 3) + 3 2 3 λ = 2 y + 2z λ = 1 3 + 4 3 = 2 (3, 3, 2) λ = 1 3 λ = 2 2 Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB) 14 PROCÉS Mètode dels multiplicadors de Lagrange Matriu hessiana restringida i condició de segon ordre Havent obtingut els punts crítics, cal determinar si corresponen a un màxim, un mínim o cap dels dos. La classificació requereix analitzar la curvatura mitjançant les derivades segones.

DEFINICIÓ La matriu hessiana restringida d'un programa, denotada per , és la matriu quadrada i simètrica d'ordre formada per les derivades parcials segones de la funció de Lagrange respecte exclusivament a les variables instrumentals: Aquesta matriu pot dependre tant dels valors de les variables com dels multiplicadors . En l'exemple anterior: Estudi de la forma quadràtica sobre el subespai tangent A diferència de l'optimització lliure, el signe de la forma quadràtica no s'ha d'exigir a tot l'espai , sinó únicament sobre les direccions permeses per les restriccions. Aquestes direccions defineixen el subespai tangent.

Formulació de la lagrangiana Restar a la funció objectiu cada restricció multiplicada per lambda. 1 Condició de primer ordre Igualar a zero totes les derivades primeres per trobar punts crítics. 2 Construcció de la hessiana Calcular la matriu de segones derivades respecte a les variables x. 3 Definició del subespai tangent Establir el sistema homogeni amb els gradients de les restriccions. 4 Classificació de l'extrem Determinar el signe de la forma quadràtica sobre el subespai. 5 H L n × n H (x; λ) = L x 1 2 L 2 x x n 1 L 2 … …

x x 1 n L 2 x n 2 L 2 x λ H L(3, 3, 2; 3, 2) = xyz 0 1 2 1 0 1 2 1 0 Q(v) = v H v T L Rn Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB) 15 PER RECORDAR-HO El subespai tangent conté els vectors desplaçament ortogonals als gradients de totes les restriccions en el punt crític : Quan les restriccions són lineals, aquest sistema homogeni manté exactament els mateixos coeficients de les restriccions originals, igualant el terme independent a zero.

La condició suficient d'extrem restringit permet classificar el punt crític avaluant la forma quadràtica sobre aquest subespai tangent: Signe de sobre el subespai tangent Classificació del punt crític Definida positiva ( ) Mínim relatiu restringit Definida negativa ( ) Màxim relatiu restringit Indefinida (pren valors positius i negatius) Punt de sella (no és extrem relatiu) Si la matriu ja és definida positiva (o negativa) a tot l'espai , també ho serà sobre el subespai tangent i no caldrà fer la projecció. Ara bé, si resulta indefinida a , és imprescindible restringir-la al subespai tangent.

ERROR FREQÜENT Un error clàssic que fa perdre punts és descartar un punt crític en veure que la matriu hessiana és indefinida a . Molts màxims i mínims condicionats tenen una matriu hessiana globalment indefinida, però esdevenen definits negatius o positius quan es limiten a les direccions factibles del subespai tangent. No classifiqueu mai sense projectar sobre el subespai tangent. v = (x , … , x ) 1 n x0 g (x ) k 0 v = 0 x = j=1 n x j g (x ) k 0 j 0, k = 1, … , m Q Q x0 Q(v) > 0, v = 0 Q(v) < 0, v = 0 H L Rn H L Rn H L Rn Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB) 16 EXEMPLE Classifiquem el punt crític del programa anterior.

La forma quadràtica associada a és: Els menors principals d'ordre 1 són nuls (0) i el determinant de la matriu és , de manera que la forma quadràtica és indefinida a . Determinem el subespai tangent a partir dels gradients de les restriccions i : D'aquest sistema lineal homogeni deduïm directament: Substituïm aquestes relacions dins la forma quadràtica : Com que per a tot , la forma quadràtica restringida és definida negativa. Concloem que el punt és un màxim relatiu restringit del programa, amb un valor òptim igual a: COMPROVA-HO 11 Si una matriu hessiana restringida té determinant no nul i elements diagonals nuls, és necessàriament un punt de sella en el problema condicionat?

IDEES CLAU La funció de Lagrange sintetitza la funció objectiu i les restriccions d'igualtat mitjançant multiplicadors auxiliars. Els punts crítics s'obtenen igualant a zero totes les derivades parcials primeres de la lagrangiana, fet que garanteix simultàniament la factibilitat. La matriu hessiana restringida conté únicament les segones derivades respecte a les variables instrumentals. La condició suficient de segon ordre exigeix avaluar el signe de la forma quadràtica sobre el subespai tangent definit per . Un signe definit negatiu (o positiu) sobre el subespai tangent garanteix l'existència d'un màxim (o mínim) relatiu condicionat.

(3, 3, 2) H L Q(x, y, z) = 2xy + 4xz + 2yz 4 = 0 R3 g (x, y, z) = 1 x + y + z g (x, y, z) = 2 x y { g (3, 3, 2) (x, y, z) = (1, 1, 1) (x, y, z) = x + y + z = 0 1 g (3, 3, 2) (x, y, z) = (1, 1, 0) (x, y, z) = x y = 0 2 y = x i z = 2x Q Q(x, x, 2x) = 2x(x) + 4x( 2x) + 2x( 2x) = 2x 2 8x 2 4x = 2 10x2 10x < 2 0 x = 0 (3, 3, 2) u = 0 u(3, 3, 2) = 3 ( 3) + 2 3 2 + ( 3) 2 = 9 + 12 6 = 3 g (x ) k 0 v = 0 Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB) 17 COMPROVA EL QUE HAS APRÈS 12. Com s'obté el sistema d'equacions que defineix el subespai tangent en un punt crític? 13. Quina dimensió té la matriu hessiana restringida d'un problema amb variables instrumentals i restriccions?

OPTIMITZACIÓ AMB RESTRICCIONS D'IGUALTAT 3 Interpretació econòmica i aplicacions EN ACABAR SABRÀS Interpretar el multiplicador de Lagrange com a preu ombra i taxa marginal de sensibilitat. Calcular la variació aproximada del valor òptim davant canvis en les restriccions mitjançant aproximació diferencial. Formular i resoldre el problema de minimització de costos de Cobb-Douglas i el model de selecció de carteres de Markowitz. PENSA-HI ABANS DE LLEGIR 14 Si una empresa disposa de 100 hores de treball i sap que el multiplicador de Lagrange d'aquesta limitació és 15, com pot saber quant milloraria el seu benefici si aconseguís una hora addicional sense tornar a calcular tot el problema?

Interpretació econòmica del multiplicador de Lagrange En resoldre un programa d'òptims restringits per igualtats mitjançant la funció de Lagrange (vegeu «Optimització amb restriccions d'igualtat — Mètode dels multiplicadors de Lagrange»), cada multiplicador no és només un paràmetre auxiliar de càlcul. El multiplicador de Lagrange té un significat fonamental: quantifica la taxa marginal de variació del valor òptim restringit davant d'alteracions en les fites o termes independents de les restriccions. DEFINICIÓ: PREU OMBRA S'anomena preu ombra al valor del multiplicador de Lagrange en l'òptim.

Mesura el grau de sensibilitat de la funció objectiu davant d'una petita pertorbació en el recurs disponible o constant de la restricció . Considerem el programa general d'optimització restringida següent: Si la constant de la restricció experimenta una lleugera desviació , la repercussió sobre el valor extrem s'obté mitjançant l'aproximació diferencial de Lagrange: H L n m λ i b i { Optimitzar s. a: z = f(x , … , x ) 1 n g (x , … , x ) = b , i = 1, … , m i 1 n i b i Δb i z = 0 f(x , …

, x ) 1 n Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB) 18 Aquesta expressió permet avaluar marginalment si resulta convenient ampliar o reduir un determinat recurs disponible sense haver de recalcular tot el problema des de l'inici.

PROCÉS Mecanisme de transmissió de la variació d'un recurs 1 Pertorbació del recurs Modificació marginal de la constant de restricció Δb 2 Ponderació per preu ombra Multiplicació pel factor de sensibilitat λ* 3 Impacte en la funció Alteració del valor òptim restringit segons Δz λ* · Δb Signe de Variació del recurs ( ) Efecte sobre el valor òptim ( ) Comportament de (increment) Augmenta aproximadament (reducció) Disminueix aproximadament (increment) Disminueix aproximadament (reducció) Augmenta aproximadament Qualsevol valor Es manté invariant (recurs no limitant) ERROR FREQÜENT No confongueu la variació del valor de la funció objectiu ( ) amb el desplaçament de les coordenades del punt òptim ( ).

L'aproximació estima exclusivament la variació del resultat òptim final, no la nova combinació d'inputs o variables instrumentals. COMPROVA-HO 15 Si en un problema de minimització de costos el multiplicador de la quota de producció és λ = 5, què succeeix si s'augmenta la fita de producció en 2 unitats? Minimització de costos amb tecnologia Cobb-Douglas Una aplicació clàssica en teoria de la producció consisteix a trobar la combinació de factors que redueix al mínim la despesa necessària per assolir un nivell determinat d'unitats de producte.

Δz 0 λ i Δb i λ i Δb i Δz 0 z 0 λ > i 0 Δb > i 0 Δz > 0 0 λ i Δb i λ > i 0 Δb < i 0 Δz < 0 0 λ i Δb i λ < i 0 Δb > i 0 Δz < 0 0 λ i Δb i λ < i 0 Δb < i 0 Δz > 0 0 λ i Δb i λ = i 0 Δz 0 0 Δz 0 Δx Δz 0 λ i Δb i Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB) 19 Analitzem una empresa amb una funció de producció de tipus Cobb-Douglas donada per . Els costos unitaris d'adquisició dels factors i són respectivament 2 i 8 unitats monetàries. Es vol determinar la despesa mínima per produir exactament una fita de 32 unitats i avaluar l'impacte d'ampliar dita fita: Formulem la funció lagrangiana associada: Q(x, y) = 4x y 0,5 0,5 x y { min s.

a: C(x, y) = 2x + 8y 4x y = 32 0,5 0,5 L(x, y, λ) = 2x + 8y λ(4x y 0,5 0,5 32) Plantejament de les condicions necessàries de primer ordre: 1 x L y L λ L = 2 λ 2x y = 0 λ = ( 0,5 0,5 ) y0,5 x0,5 = 8 λ 2x y = 0 λ = 4 ( 0,5 0,5 ) ( x0,5 y0,5 ) = 4x y 32 = 0 ( 0,5 0,5 ) Resolució del sistema per aïllar el punt crític restringit: Igualant ambdues expressions de : Substituint a la restricció de producció: D'on obtenim i el multiplicador = 2. El punt crític restringit és .

2 λ = y0,5 x0,5 4 x0,5 y0,5 x = 4y x = 4y 4(4y) y = 0,5 0,5 32 4 2y = 32 8y = 32 y = 4 x = 4(4) = 16 λ (x , y ) = (16, 4) Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB) 20 COMPROVA-HO 16 Quina condició sobre el subespai tangent garanteix que un punt crític amb matriu hessiana semidefinida positiva sigui realment un mínim? Model financer de selecció de carteres de Markowitz Una altra aplicació essencial del mètode s'esdevé en l'àmbit financer en el model de carteres de Markowitz. L'objectiu consisteix a minimitzar la variància del rendiment (mesura del risc global) subjecta a la consecució d'una rendibilitat mínima esperada pel conjunt d'actius.

Comprovació de la condició suficient d'extrem restringit: Calculem la matriu hessiana restringida de les derivades de segon ordre de la funció lagrangiana respecte a les variables instrumentals: Avaluant al punt crític amb : Aquesta matriu té determinant nul ( ), per la qual cosa és semidefinida positiva. Procedim a analitzar el subespai tangent a la restricció: Els vectors direccionals del subespai tangent satisfan , és a dir, . Projectant la forma quadràtica sobre aquest subespai: En ser definida positiva sobre el subespai tangent, queda confirmat que el punt constitueix un mínim estricte.

3 H L = xy ( λx y 1,5 0,5 λx y 0,5 0,5 λx y 0,5 0,5 λx y 0,5 1,5 ) (16, 4) λ = 2 H L(16, 4; 2) = xy = ( 2(16) (4) 1,5 0,5 2(16) (4) 0,5 0,5 2(16) (4) 0,5 0,5 2(16) (4) 0,5 1,5 ) ( 1/16 1/4 1/4 1 ) (1/16)(1) ( 1/4) = 2 0 g(16, 4) = 2(16) (4) , 2(16) (4) = ( 0,5 0,5 0,5 0,5 ) (1, 4) v = (h , h ) 1 2 g(16, 4) v = 0 h + 1 4h = 2 0 h = 1 4h 2 Q( 4h , h ) = 2 2 ( 4h ) + 16 1 2 2 h 2 2 ( 4h )(h ) = 2 1 2 2 h + 2 2 h + 2 2 2h = 2 2 4h > 2 2 0 ( h = 2 0) (16, 4) Càlcul del cost mínim i anàlisi de sensibilitat: El cost mínim assolit és C(16, 4) = 2(16) + 8(4) = 64 unitats monetàries.

Com que , un augment unitari en la fita productiva ( ) implicarà un increment aproximat del cost total de: Per tant, produir una unitat addicional encarirà la despesa en aproximadament 2 unitats monetàries. 4 λ = 2 > 0 Δb = +1 ΔC 0 λ Δb = 2 1 = 2 u.m. Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB) 21 EXEMPLE: SELECCIÓ ÒPTIMA DE DOS ACTIUS Es disposa de dos títols financers amb rendibilitats esperades individuals del 8 % i del 4 %. El risc de la cartera es troba modelitzat per la funció de variància: on i representen les proporcions invertides en cadascun dels actius. Es desitja fixar una rendibilitat mitjana global del 5 % (és a dir, 0,05).

El programa es formula com: Construïm la funció lagrangiana: I resolem el sistema de derivades igualades a zero: La resolució algebraica d'aquest sistema lineal condueix directament a: El valor mínim del risc (dispersió) de la posició resultant és: Si l'inversor exigeix incrementar la rendibilitat objectiu fins al 5,5 % ( ), l'increment requerit és (un 0,5 %). Fent ús del preu ombra obtingut: El risc de la cartera creixerà aproximadament en a conseqüència d'haver exigit un retorn superior.

PER RECORDAR-HO En el model de Markowitz, el signe positiu del multiplicador associat a la restricció de rendibilitat reflecteix la relació clàssica de trade-off en finances: a major rendibilitat exigida ( ), major serà el risc assumit en la cartera ( ). COMPROVA-HO 17 Quin significat té un valor de λ = 0,005 en el model de selecció de carteres de Markowitz? σ(x, y) = 0,0016x + 2 0,0004y 2 0,00096xy x y { min s.

a: σ(x, y) = 0,0016x + 0,0004y 0,00096xy 2 2 0,08x + 0,04y = 0,05 L(x, y, λ) = 0,0016x + 2 0,0004y 2 0,00096xy λ(0,08x + 0,04y 0,05) = 0,0032x 0,00096y 0,08λ = 0 x L = 0,0008y 0,00096x 0,04λ = 0 y L 0,08x + 0,04y = 0,05 x = = 16 5 0,3125 (31,25%), y = = 8 5 0,625 (62,5%), λ = = 200 1 0,005 σ , = ( 16 5 8 5 ) 1,25 10 4 b = 1 0,055 Δb = 1 0,055 0,05 = 0,005 Δσ λ Δb = 1 0,005 0,005 = 25 10 6 2,5 10 5 λ Δb > 0 Δσ > 0 Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB) 22 IDEES CLAU El multiplicador de Lagrange actua com a preu ombra mesurant la variació del valor òptim davant canvis marginals en les restriccions. La relació bàsica d'aproximació diferencial respon a la fórmula .

Si el signe de i el de coincideixen, el valor de la funció objectiu experimentarà un increment. En la producció Cobb-Douglas, el preu ombra associat a la quota de producció quantifica directament el cost marginal per unitat fabricada. En la gestió de carteres de Markowitz, el paràmetre de Lagrange quantifica el cost en termes de variància o risc associat a exigir un major retorn esperat. COMPROVA EL QUE HAS APRÈS 18. En què es diferencia la interpretació econòmica d'un multiplicador de Lagrange positiu versus un de nul? 19. Com s'obté l'estimació de la nova despesa en un problema de mínim cost si es relaxa el requisit productiu en dues unitats ( ) i tenim ? Test Encercla la resposta correcta.

Les solucions són al final. 20. Què representa el conjunt factible en un programa amb restriccions d'igualtat? 21. En resolució gràfica de dues variables, on sol trobar-se l'òptim restringit? 22. En què consisteix el mètode de resolució directa o per substitució?

Δz 0 λ i Δb i λ i Δb i Δb = 2 λ = 3 Els punts on la matriu hessiana és negativa a) Tots els punts que verifiquen les restriccions b) El conjunt de punts on el gradient s'anul·la c) L'espai on la funció objectiu és positiva d) Al tall de la restricció amb els eixos a) En el punt de tangència amb una corba de nivell b) A l'origen de coordenades sempre c) On la corba de nivell té pendent zero d) Igualar directament la funció objectiu a zero a) Assignar valors arbitraris a les constants b) Calcular la matriu hessiana de la restricció c) Aïllar variables per transformar-lo en optimització lliure d) Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB) 23 23.

Quin és l'òptim del programa Cobb-Douglas Q(x,y)= ,5 ,5 amb costos 2 i 8 i fita 32? 24. Quin paper compleixen les derivades parcials de la lagrangiana respecte als multiplicadors? 25. D'on prové la matriu hessiana restringida d'un problema d'optimització condicionada? 26. Si la forma quadràtica de la hessiana és indefinida a Rn, com procedim? 27. Quan és un punt crític un màxim relatiu restringit segons la condició de segon ordre? 28. Què expressa conceptualment el preu ombra associat a una restricció? 29. Si λ = -4 i el recurs es redueix (Δb < 0), quin efecte s'obté sobre el valor extrem z? 30. En el problema Cobb-Douglas analitzat, quin cost mínim s'assoleix per produir 32 unitats?

4x0 y0 (x, y) = (8, 8) amb cost 80 a) (x, y) = (4, 16) amb cost mínim 136 b) (x, y) = (32, 2) amb cost mínim 80 c) (x, y) = (16, 4) amb cost mínim 64 d) Calculen la matriu hessiana del programa a) Defineixen el subespai tangent del punt b) Recuperen les equacions de les restriccions c) Determinen la concavitat de la funció d) De les segones derivades respecte a x a) Dels menors orlats de la funció objectiu b) Dels gradients de les funcions de restricció c) De les segones derivades respecte a lambda d) S'avalua sobre el subespai tangent a) Es conclou que és punt d'inflexió b) El punt es descarta com a extrem c) Es canvien els signes dels multiplicadors d) Quan la forma quadràtica tangent és semidefinida a) Quan la forma quadràtica tangent és definida negativa b) Quan la forma quadràtica tangent és definida positiva c) Quan el determinant de la hessiana és nul d) El preu d'adquisició dels factors a) El canvi marginal del valor òptim b) La coordenada del nou extrem c) El pendent del subespai tangent d) L'efecte serà indefinit a) El valor de z creixerà b) El valor de z decreixerà c) El valor de z romandrà constant d) 128 unitats monetàries a) 64 unitats monetàries b) 16 unitats monetàries c) 32 unitats monetàries d) Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB) 24 31.

Al model de Markowitz presentat, quin efecte té augmentar la rendibilitat esperada requerida? 4 Optimització amb restriccions de desigualtat — Formulació i resolució gràfica EN ACABAR SABRÀS Transformar qualsevol programa d'optimització amb desigualtats a la seva forma canònica equivalent. Construir geomètricament el conjunt factible al pla i determinar si és compacte per aplicar el teorema de Weierstrass. Trobar la solució òptima mitjançant el desplaçament de corbes de nivell i identificar les restriccions saturades. PENSA-HI ABANS DE LLEGIR 32 Per què en un problema empresarial sovint és més realista formular restriccions amb desigualtats en comptes d'igualtats estrictes?

A diferència dels models clàssics on les limitacions obliguen a esgotar estrictament els recursos mitjançant igualtats, els problemes d'optimització amb desigualtats reflecteixen amb més fidelitat els processos de decisió reals, en què els recursos disponibles funcionen com a cotes superiors o inferiors que no necessàriament s'han de consumir del tot. Anul·lar la proporció invertida en actius a) Reduir la dispersió de la cartera b) Mantenir invariable la variància global c) Incrementar el risc mínim assumit d) Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB) 25 ESQUEMA Estructura de l'optimització amb restriccions de desigualtat 1.

Estructura general i programa canònic de desigualtats Un programa d'optimització restringit per desigualtats cerca determinar els valors de les variables de decisió que maximitzen o minimitzen una funció objectiu subjecta a un conjunt de restriccions expressades mitjançant desigualtats. DEFINICIÓ Un programa canònic d'òptims restringits per desigualtats és un problema d'optimització que adopta exactament una de les dues estructures següents: on és la funció objectiu, són les variables instrumentals o de decisió, representen les funcions de restricció i són les constants de restricció associades.

Per conveni de la forma canònica, un programa de maximització exigeix restriccions del tipus , mentre que un de minimització requereix restriccions del tipus . Tot programa que no presenti aquesta disposició es pot transformar en un d'equivalent aplicant dues propietats elementals: Formulació del programa Forma canònica de màxim i mínim Geometria factible Polígons convexos i condicions de compacitat Mètodes de resolució Anàlisi gràfica i tècniques de programació Resolució gràfica Desplaçament de corbes de nivell al pla Saturació de restriccions Identificació de cotes actives i no actives Programació lineal Algorismes i teoremes fonamentals Forma can nica de m xim: o ˋ a ˋ { max z = f(x , …

, x ) 1 n s. a: g (x , … , x ) b , i = 1, … , m i 1 n i Forma can nica de m nim: o ˋ ı ˊ { minz = f(x , … , x ) 1 n s. a: g (x , … , x ) b , i = 1, … , m i 1 n i f(x , … , x ) 1 n x , … , x 1 n g (x , … , x ) i 1 n b i Inversió de l'objectiu: Maximitzar una funció equival a minimitzar (i recíprocament), ja que . 1 u u max u = min( u) Inversió del sentit de la desigualtat: Multiplicar una restricció per -1 inverteix el sentit de la desigualtat, de manera que .

2 g (x) i b i g (x) i b i Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB) 26 EXEMPLE Considerem el programa següent: Per transformar-lo en un programa canònic de mínim equivalent, invertim el signe de la funció objectiu i de la primera desigualtat: Aquests dos programes són equivalents i assoleixen el mateix punt òptim . COMPROVA-HO 33 Com es converteix la restricció 2x - 3y 8 en una restricció canònica per a un problema de maximització? 2. Geometria del conjunt factible i existència d'òptims El conjunt de totes les solucions admissibles condiciona completament la resolubilitat del programa matemàtic.

DEFINICIÓ El conjunt factible (també anomenat recinte admissible o d'oportunitats) d'un programa d'òptims restringits per desigualtats és el conjunt de punts del domini que verifiquen simultàniament totes les restriccions del problema. Si aquest conjunt no és buit, el programa és factible; altrament, s'anomena infactible. A l'espai bidimensional , les restriccions lineals determinen semiplans la intersecció dels quals conforma una regió poligonal. Si el segment que uneix qualsevol parell de punts del recinte està contingut completament dins d'aquest, diem que el conjunt factible és un polígon convex, els vèrtexs del qual s'obtenen mitjançant la intersecció de les rectes frontera.

max u = 27z x 3y 2 2 s. a: x y + z 0 s. a: y x 1 min u = x + 3y 27z 2 2 s. a: x + y z 0 s. a: y x 1 ( 13,5, 4,5, 18) R2 Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB) 27 Gràfica del conjunt factible convex i els seus quatre vèrtexs. L'existència d'extrems globals depèn de les propietats topològiques d'aquest conjunt, fonamentades en el teorema de Weierstrass: PER RECORDAR-HO Segons el teorema de Weierstrass, tota funció contínua definida sobre un conjunt compacte (tancat i acotat) assoleix de manera garantida un màxim i un mínim absoluts. En els polígons tancats i acotats de , la presència d'un òptim finit està sempre assegurada si la funció objectiu és contínua.

Distingim així dos tipus essencials de solucions: Òptim finit (o solució acotada): Existeix un punt factible que maximitza o minimitza la funció objectiu prenent un valor real determinat anomenat valor òptim. Òptim infinit (o solució no acotada): La funció objectiu creix o decreix indefinidament dins del conjunt factible, sense assolir cap cota superior o inferior finita (per exemple, quan el recinte s'estén cap a l'infinit seguint una direcció en què la funció augmenta sense límit). COMPROVA-HO 34 Quines dues condicions han de complir-se per garantir l'existència d'un òptim finit mitjançant el teorema de Weierstrass? 3.

Resolució pel mètode gràfic: línies de nivell i tangència Quan el programa compta amb dues variables instrumentals ( ), podem aplicar el mètode de resolució gràfica. El procediment consisteix a dibuixar el recinte factible i representar la família de corbes de nivell associades a diferents valors de la constant . R2 n = 2 A c = k {(x, y) : f(x, y) = k} k R Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB) 28 Esquema del desplaçament de corbes de nivell sobre el recinte. A mesura que desplacem la corba de nivell augmentant el paràmetre (en maximització) o disminuint- lo (en minimització), identifiquem l'últim punt de contacte amb el conjunt factible abans d'abandonar-lo completament.

Tipus de programa Geometria de les corbes de nivell Localització habitual de l'òptim Lineal Rectes paral·leles amb pendent constant Vèrtex del recinte o segment frontera sencer No lineal (quadràtic, etc.) Circumferències, el·lipses o corbes còniques Punt de tangència a la frontera o vèrtex DEFINICIÓ Diem que una restricció de desigualtat està saturada (o és activa) a l'òptim si en el punt de solució es compleix la igualtat estricta corresponent ( ). Si pel contrari es compleix amb desigualtat estricta ( o bé ), la restricció és no saturada o inactiva.

k g (x ) = i b i g (x ) < i b i > b i Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB) 29 ERROR FREQÜENT Suposar que l'òptim sempre se situa en un vèrtex del polígon. En programació lineal això és cert pel que fa als vèrtexs, però en programació no lineal la corba de nivell pot ser tangent a un segment interior de la frontera sense tocar cap vèrtex. En aquest cas, l'òptim satura només una restricció en lloc de dues. COMPROVA-HO 35 Quina diferència geomètrica hi ha entre la solució d'un programa lineal i la d'un programa quadràtic amb corbes de nivell circulars? 4.

Comparativa pràctica: cas lineal i cas quadràtic sobre el mateix recinte Analitzem la resolució d'un mateix conjunt factible de producció sotmès a dues funcions objectiu de naturalesa diferent. Una empresa disposa de dos processos i per fabricar dos béns i , amb requeriments temporals i capacitats donades per: Procés Temps unitari bé A Temps unitari bé B Disponibilitat total P 6 minuts 10 minuts 10 hores (600 minuts) Q 9 minuts 3 minuts 12 hores (720 minuts) El recinte factible comú definit per les variables no negatives és: Aquest polígon convex posseeix quatre vèrtexs: , , el punt d'intersecció (75,15) i .

Cas A: Model lineal de màxim benefici Amb beneficis unitaris constants de 25 i 30 u.m. respectivament, la funció objectiu és . Desplaçant les rectes paral·leles de nivell en el sentit de creixement de , el valor màxim dins del recinte s'assoleix al vèrtex . P Q A B x, y 0 A = {(x, y) R : 2 6x + 10y 600, 9x + 3y 720, x 0, y 0} (0,0) (0,60) (80,0) z = 25x + 30y k (75,15) Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB) 30 Gràfica de la resolució lineal amb òptim al vèrtex (75, 15). En aquest punt, el valor màxim és z = 2325 u.m. L'òptim satura simultàniament la primera i la segona restricció de recursos, ja que les dues s'esgoten amb igualtat estricta.

Cas B: Model no lineal amb funcions de demanda Quan el preu depèn de la quantitat segons les funcions de demanda inverses , i amb costos conjunts , el benefici adopta una forma quadràtica: Les corbes de nivell són circumferències concèntriques centrades al punt . El radi es redueix a mesura que augmenta el nivell de benefici . La circumferència amb major nivell de benefici que arriba a tocar el polígon és tangent al segment de la recta en el punt (55,27). Aquest extrem s'obté resolent el problema d'igualtat sobre la frontera (vegeu «Optimització amb restriccions d'igualtat — Fonaments i mètodes de resolució elemental»). En aquest punt de tangència, el valor òptim és z = 6000 u.m.

i l'òptim satura únicament la primera restricció de capacitat, deixant marge excedentari en el procés . COMPROVA-HO 36 Al punt òptim (55, 27) del cas no lineal, per què diem que només se satura la primera restricció? p = A 103 0,5x p = B 107 0,5y C(x, y) = 3x + 5y + 377 z = 100x + 102y 0,5x 2 0,5y 2 377 = 9825 (x 2 1 100) 2 (y 2 1 102)2 (100, 102) k 6x + 10y = 600 Q Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB) 31 IDEES CLAU Un programa canònic de desigualtats adopta restriccions de tipus si és de màxim, i de tipus si és de mínim. Qualsevol programa no canònic es pot transformar en canònic invertint el signe de la funció objectiu o multiplicant per -1 les desigualtats.

El teorema de Weierstrass garanteix l'existència d'òptims finits quan la funció objectiu és contínua sobre un conjunt factible compacte. En els models lineals l'òptim es troba sobre la frontera del recinte i habitualment en un vèrtex, mentre que en models no lineals s'assoleix sovint per tangència interna a una aresta. Una restricció està saturada a l'òptim quan es verifica amb igualtat matemàtica estricta. COMPROVA EL QUE HAS APRÈS 37. Com s'expressa en forma canònica de màxim un problema amb restricció ? 38. Què implica geomètricament que un programa presenti un òptim infinit? 39. En el problema introductori de producció, quines restriccions satura la solució lineal ?

Test Encercla la resposta correcta. Les solucions són al final. 40. Quina forma tenen les restriccions d'un programa canònic de maximització? 41. Si un programa compta amb un recinte factible buit, com es classifica? 42. Què garanteix el teorema de Weierstrass en un programa d'optimització? 43. Com s'anomena una restricció que a l'òptim es compleix amb igualtat estricta?

3x + 2y 12 (75, 15) Exclusivament d'igualtat estricta a) Sempre de tipus major o igual b) Combinades de menor i major alhora c) Sempre de tipus menor o igual d) Programa degenerat a) Programa no canònic b) Programa amb òptim infinit c) Programa infactible d) La linealitat de les corbes de nivell a) La unicitat de la solució òptima b) Que l'òptim sigui sempre un vèrtex c) L'existència d'extrems globals si el conjunt és compacte d) Restricció saturada o activa a) Restricció inconsistent b) Restricció redundant c) Restricció folgada d) Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB) 32 5 Teorema fonamental i resolució de models bàsics EN ACABAR SABRÀS Identificar els elements algebraics d'un programa lineal canònic i construir la seva matriu tecnològica.

Aplicar el teorema fonamental de la programació lineal per localitzar els òptims globals en els vèrtexs. Resoldre models lineals plans avaluant la funció objectiu sobre els vèrtexs del recinte factible. Reconèixer solucions alternatives en segments d'aresta i caracteritzar la compacitat dels programes acotats. PENSA-HI ABANS DE LLEGIR 44 Per què en un problema lineal no cal explorar l'interior del conjunt factible per trobar el valor màxim? Estructura del programa lineal canònic La programació lineal estudia problemes d'optimització on tant el criteri d'avaluació com les condicions imposades són de naturalesa exclusivament lineal.

Els seus antecedents formals inclouen les taules input-output de Wassily Leontief, els treballs de Leonid Kantorovich als anys trenta aplicats a la planificació soviètica i la formulació del transport als anys quaranta, consolidant-se definitivament el 1950 amb l'algorisme del símplex proposat per George Dantzig. En la seva expressió matemàtica estàndard, un programa lineal canònic de maximització s'escriu matricialment com: Desplegat per components per a variables de decisió i restriccions funcionals: Programació lineal 5 Teorema fonamental i resolució de models bàsics 6 Anàlisi de sensibilitat amb informes de Solver 7 Formulació de models econòmics clàssics max z = c x s.

a Ax T b, x 0 n m Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB) 33 De manera anàloga, la forma canònica de minimització planteja sotmès a i , amb coeficients reals . DEFINICIÓ La matriu d'ordre formada pels coeficients tecnològics de les restriccions lineals s'anomena matriu tecnològica del programa. Representa les taxes de consum de cada recurs per unitat d'activitat. EXEMPLE Considerem el model productiu elemental definit per: La matriu tecnològica associada a les disponibilitats de recursos és . COMPROVA-HO 45 Quina funció tenen les condicions de no-negativitat x 0 en la definició canònica?

El teorema fonamental de la programació lineal El conjunt de punts que verifiquen simultàniament totes les restriccions lineals forma un políedre convex tancat, anomenat polígon de factibilitat en el pla bidimensional (vegeu «Optimització amb restriccions de desigualtat — Formulació i resolució gràfica»). A diferència de l'optimització no lineal, on els màxims o mínims poden aparèixer a l'interior del conjunt per tangència interna, la linealitat estricta de la funció objectiu i dels seus hiperplans de nivell genera un comportament rígid i determinista. max s.

a z = c x + c x + + c x 1 1 2 2 n n a x + a x + + a x b 11 1 12 2 1n n 1 a x + a x + + a x b 21 1 22 2 2n n 2 a x + a x + + a x b m1 1 m2 2 mn n m x , x , … , x 0 1 2 n minz = c x T Ax b x 0 c , a , b j ij i R A = (a ) ij m × n max s. a z = 25x + 30y 6x + 10y 600 9x + 3y 720 x, y 0 M = ( 6 9 10 3 ) Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB) 34 PER RECORDAR-HO L'enunciat del teorema fonamental de la programació lineal assegura dues propietats decisives: 1. Si un programa lineal admet una solució finita, almenys un òptim global es troba en un vèrtex del conjunt factible. 2.

Qualsevol combinació lineal convexa de dos òptims finits (el segment que els uneix) és també un òptim global. Tot òptim finit obtingut en un programa lineal és necessàriament un extrem absolut o global. Cal notar, tanmateix, que el teorema fonamental per si sol no en garanteix l'existència; tan sols especifica la seva ubicació geomètrica en el cas que el problema disposi efectivament de solució finita. Gràfica del conjunt factible amb òptim en el vèrtex (75, 15). En l'exemple introductori anterior, les rectes límit delimiten el recinte amb vèrtexs a l'origen i sobre els eixos.

L'avaluació de la funció objectiu identifica que el màxim s'assoleix exactament en el vèrtex d'intersecció (75, 15), generant un benefici òptim de . COMPROVA-HO 46 Si un programa lineal admet òptim finit, pot aquest ser exclusivament un òptim local que no sigui global? Programes lineals acotats i existència d'òptims Quan la regió factible no s'estén indefinidament cap a l'infinit, el comportament analític del programa queda plenament determinat. A z = 25x + 30y z = 2325 Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB) 35 DEFINICIÓ Un programa lineal és un programa lineal acotat si el seu conjunt factible associat és acotat.

Atès que les desigualtats lineals generen semiplans tancats, aquest recinte és estrictament compacte (tancat i acotat). La compacitat del domini garanteix, mitjançant el teorema de Weierstrass en optimització, que la funció objectiu lineal assoleix tant un màxim com un mínim globals finits. En conseqüència, tot programa lineal acotat té garantida l'existència d'òptims globals finits en els seus vèrtexs extrems. ERROR FREQÜENT Pensar que un recinte no acotat implica immediatament l'absència de solució.

Si el sentit d'optimització (mínim o màxim) empeny les corbes de nivell cap a les vores tancades de la regió, el problema pot tenir solució finita malgrat que el polígon sigui indefinit en altres direccions. COMPROVA-HO 47 Quina condició assegura l'existència d'un mínim i d'un màxim globals finits en un programa lineal?

Procediment de resolució per avaluació de vèrtexs Per a models de dues variables ( ), el procediment algebraic i geomètric d'avaluació directa consta dels passos següents: PROCÉS Algorisme de resolució gràfica de programes lineals 1 Representar restriccions Dibuixar semiplans i identificar el polígon factible 2 Determinar vèrtexs Trobar interseccions resolent els sistemes d'equacions lineals 3 Avaluar l'objectiu Calcular z(x, y) en cadascun dels vèrtexs obtinguts 4 Seleccionar extrem Escollir el valor màxim o mínim segons el criteri del problema x, y Dibuixar el recinte factible: Traçar les rectes frontera associades a cadascuna de les desigualtats funcionals i identificar el semiplà d'intersecció juntament amb el primer quadrant definit per .

1 x 0, y 0 Calcular les coordenades dels vèrtexs: Resoldre els sistemes d'equacions lineals que formen les parelles de rectes secants delimitadores del recinte. 2 2 × 2 Avaluar la funció objectiu: Substituir les coordenades de cada extrem calculat a la funció . 3 z(x, y) Identificar els valors extrems: Triar el vèrtex amb major valor numèric per a problemes de maximització, o el de menor valor per a models de minimització.

4 Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB) 36 EXEMPLE Considerem el programa lineal definit sobre un recinte acotat: El domini factible és un polígon tancat i acotat que compta amb cinc vèrtexs: Polígon factible acotat i determinació dels seus cinc vèrtexs extrems. Avaluem la funció objectiu en cadascun d'aquests punts extrems: Vèrtex Càlcul de Valor resultant 9 9 23 37 44 De la comparació directa s'obté: El màxim global únic es troba al vèrtex (3, 2) amb un valor òptim de 44. Optimitzar s.

a z = 7x + 14y 5 x + 3y 9 2x + y 8 x + 2y 2 x, y 0 A (x, y) z(x, y) = 7x + 14y 5 (0, 1) 7(0) + 14(1) 5 (2, 0) 7(2) + 14(0) 5 (4, 0) 7(4) + 14(0) 5 (0, 3) 7(0) + 14(3) 5 (3, 2) 7(3) + 14(2) 5 z(0, 1) = z(2, 0) = 9 < z(4, 0) = 23 < z(0, 3) = 37 < z(3, 2) = 44 Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB) 37 Solucions òptimes alternatives i casos especials A l'exercici anterior, la funció objectiu assoleix el valor mínim de 9 de manera coincident en dos vèrtexs contigus: i . Segons el teorema fonamental, quan dos vèrtexs comparteixen el valor òptim, tot punt intermedi del segment que els uneix és també solució òptima del programa lineal.

Aquest fenomen de múltiples solucions òptimes succeeix geomètricament quan el vector de pendents de les corbes de nivell de la funció objectiu és exactament paral·lel a una de les arestes actives del polígon factible. Si el problema fos no acotat en la direcció de millora de , la funció creixeria indefinidament sense assolir cap extrem finit. Els canvis marginals en aquests models i l'impacte de modificacions sobre els recursos independents s'analitzen mitjançant el concepte de preu ombra (vegeu «Programació lineal — Anàlisi de sensibilitat amb informes de Solver»). COMPROVA-HO 48 Com s'interpreta geomètricament que un programa lineal tingui infinites solucions òptimes?

IDEES CLAU Un programa lineal canònic està format per una funció objectiu lineal, restriccions de desigualtat lineals i condicions de no-negativitat per a les variables. La matriu tecnològica concentra els coeficients de consum o de relació tècnica de les variables dins de les restriccions. El teorema fonamental assegura que, si hi ha solució finita, almenys un òptim global es troba en un dels vèrtexs del recinte factible. Si dos vèrtexs contigus comparteixen el valor òptim extrem, qualsevol punt del segment que els uneix representa una solució òptima alternativa. Un programa lineal amb conjunt factible acotat és compacte i té garantida l'existència de màxim i mínim globals finits.

COMPROVA EL QUE HAS APRÈS 49. On s'ubiquen sempre els òptims globals finits d'un programa lineal? 50. Què succeeix amb la solució d'un problema si dos vèrtexs diferents assoleixen el mateix valor màxim extrem?

(0, 1) (2, 0) z Matemàtiques II: Optimització i Anàlisi Dinàmica (ADE UB) 38 PROGRAMACIÓ LINEAL 6 Anàlisi de sensibilitat amb informes de Solver EN ACABAR SABRÀS Interpretar correctament les dades de les taules de cel·les canviants i de restriccions d'Excel Solver Calcular el nou valor de la funció objectiu davant d'alteracions en els beneficis unitaris dins del rang permissible Determinar l'impacte exacte d'un canvi en la disponibilitat de recursos mitjançant el preu ombra Identificar quan un informe de sensibilitat deixa de ser vàlid per superar els límits admissibles PENSA-HI ABANS DE LLEGIR 51 Si augmentem la disponibilitat d'un recurs crític en una empresa, el benefici addicional es pot predir exactament o cal tornar a calcular tota la planificació?

Fonaments de l'anàlisi de sensibilitat post-òptima Quan resolem un programa lineal acotat (vegeu «Programació lineal — Teorema fonamental i resolució de models bàsics»), obtenim una solució òptima per a uns paràmetres concrets. No obstant això, en l'entorn econòmic real, els beneficis unitaris o les…