Apunts de Matemàtiques II: Optimització i Dinàmica

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

Text del document

APUNTS MATEMÀTIQUES II Grau en Economia Universitat de Barcelona AprenAI 2026-2027 Resum complet de Matemàtiques II per a Economia a la UB: multiplicadors de Lagrange, programació lineal, càlcul integral i equacions diferencials ordinàries. APREN.AI Índex Optimització amb restriccions d'igualtat 1 Fonaments i mètodes gràfic i directe 1. Estructura d'un programa d'optimització condicionada per igualtats 2. Conjunt factible, punts factibles i naturalesa dels òptims 3. Mètode gràfic de resolució ( ) 4.

Mètode directe o de substitució de variables 2 Multiplicadors de Lagrange i anàlisi econòmica Funció de Lagrange i condicions de primer ordre Matriu hessiana restringida i condició suficient de segon ordre Interpretació econòmica dels multiplicadors: preus ombra i anàlisi de sensibilitat Aplicacions a la minimització de costos i al model de Markowitz 3 Optimització amb restriccions de desigualtat — Programes canònics i resolució gràfica 1. Formulació de programes canònics i equivalència formal 2. Geometria del conjunt factible i existència d'òptims 3.

Resolució gràfica mitjançant corbes de nivell i restriccions saturades Programació lineal 4 Teorema fonamental i anàlisi de sensibilitat Estructura del programa lineal canònic Teorema fonamental i mètode d'inspecció de vèrtexs Anàlisi de sensibilitat de la funció objectiu Anàlisi de sensibilitat de les restriccions de recursos 5 Models de planificació de la producció i del transport Model de planificació de la producció Resolució d'un model de producció i anàlisi de sensibilitat Model clàssic del transport Preus ombra i alteració de condicions Càlcul integral d'una variable 6 Primitives, integrals immediates i propietats Primitives i caracterització de la integral indefinida Taula canònica d'integrals immediates Propietats de linealitat i integració logarítmica 7 Mètodes d'integració per parts i per canvi de variable n = 2, m = 1 Apunts de Matemàtiques II: Optimització i Dinàmica 1 El concepte de diferencial d'una funció El mètode d'integració per parts Integrals cícliques mitjançant doble integració per parts Mètode d'integració per substitució o canvi de variable 8 Integral definida, teorema fonamental i regla de Barrow Integral definida d'una funció contínua Propietats fonamentals de la integral definida La funció integral i el teorema fonamental del càlcul Avaluació pràctica: la regla de Barrow 9 Càlcul d'àrees planes i aplicacions geomètriques Àrea delimitada per una corba i l'eix d'abscisses Determinació d'àrees compreses entre dues corbes Càlcul d'àrees per a funcions definides a trossos Sistematització general del procediment de càlcul 10 Aplicacions econòmiques de la integració Reconstrucció de funcions totals a partir de magnituds marginals Equilibri de mercat i càlcul dels excedents Demanda acumulada i esgotament de recursos 11 Equacions diferencials ordinàries — Conceptes fonamentals i models de primer ordre Fonaments de les equacions diferencials ordinàries Solució general, solució particular i corbes integrals Formes d'expressió d'una EDO de primer ordre Equacions de variables separades Equacions de variables separables 12 Equacions diferencials de primer ordre — Lineals i equacions de Bernouilli Equacions diferencials lineals de primer ordre: reduïdes i completes Resolució de la lineal completa mitjançant factor d'integració L'equació diferencial de Bernouilli i el canvi linealitzador 13 Equacions diferencials lineals de segon ordre a coeficients constants Estructura de l'equació diferencial lineal de segon ordre L'equació característica i la solució de la reduïda Càlcul de la solució particular constant i solució general Determinació de les constants mitjançant condicions inicials 14 Dinàmica econòmica i demogràfica — Aplicacions d'equacions diferencials de primer ordre Model financer d'acumulació instantània de capital Dinàmica de preus: el model lineal de Walras Apunts de Matemàtiques II: Optimització i Dinàmica 2 Model demogràfic i difusió: la corba logística 15 Dinàmica de mercat de segon ordre i problemes d'anàlisi dinàmica Modelització de mercat amb expectatives de preu Models de variació temporal: llei de refredament de Newton Deducció de corbes de demanda a partir de l'elasticitat puntual Síntesi d'equacions diferencials i mètodes d'anàlisi dinàmica 16 Formulari Optimització amb restriccions d'igualtat Optimització amb restriccions de desigualtat i programació lineal Càlcul integral de funcions d'una variable Equacions diferencials ordinàries (EDO) Errors típics i precaucions per a l'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. Apunts de Matemàtiques II: Optimització i Dinàmica 3 1 Fonaments i mètodes gràfic i directe EN ACABAR SABRÀS Formular analíticament un programa d'optimització condicionada identificant funció objectiu, variables i restriccions. Determinar gràficament la posició de l'òptim mitjançant la condició de tangència entre corbes de nivell i restriccions. Resoldre programes d'optimització amb restriccions lineals mitjançant el mètode directe de substitució.

PENSA-HI ABANS DE LLEGIR 1 Per què el màxim d'una funció sobre una recta sol donar un valor diferent al màxim absolut d'aquesta mateixa funció a tot el pla? L'optimització matemàtica constitueix una eina fonamental en l'economia per assignar recursos escassos de manera eficient entre diferents alternatives. Quan aquests recursos s'han d'esgotar amb precisió o s'ha d'assolir un nivell fixat de producció, els problemes incorporen restriccions en forma d'igualtat. Optimització amb restriccions d'igualtat 1 Fonaments i mètodes gràfic i directe 2 Multiplicadors de Lagrange i anàlisi econòmica Apunts de Matemàtiques II: Optimització i Dinàmica 4 ESQUEMA Optimització matemàtica i anàlisi dinàmica 1.

Estructura d'un programa d'optimització condicionada per igualtats Un problema de decisió sota condicions d'igualtat busca maximitzar o minimitzar una magnitud sotmesa a un conjunt de regles rígides que no admeten marge per sobre ni per sota. DEFINICIÓ: PROGRAMA D'OPTIMITZACIÓ CONDICIONAT PER IGUALTATS Un programa d'òptims restringits per igualtats és un problema formulat de la forma: Els elements formals que el constitueixen són: Funció objectiu : funció escalar que es pretén fer màxima o mínima. S'assumeix que compta amb derivades parcials segones contínues. Variables instrumentals o de decisió : les magnituds que l'agent econòmic pot escollir de manera directa.

Funcions de restricció : les relacions escalars que vinculen les variables. Constants de restricció : els valors numèrics fixats per a cadascuna de les condicions.

Optimització restringida Problemes amb condicions de contorn Restriccions d'igualtat Mètode gràfic, directe i Lagrange Restriccions de desigualtat Mètode gràfic i programació lineal Càlcul integral Integració i càlcul d'àrees i excedents Mètodes d'integració Primitives, canvi de variable i parts Aplicacions econòmiques Excedent del consumidor i productor Anàlisi dinàmica Equacions diferencials i evolució temporal EDO de 1r ordre Variables separables, lineals i Bernouilli EDO de 2n ordre Coeficients constants i dinàmica de mercat 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 z = f(x , … , x ) 1 n (x , … , x ) 1 n n g (x , …

, x ) j 1 n m b j m Apunts de Matemàtiques II: Optimització i Dinàmica 5 Per regla general, el nombre de restriccions és estrictament inferior al nombre de variables ( ). Si , el conjunt de condicions determinaria una solució única (o un conjunt discret) sense marge per optimitzar. EXEMPLE: MINIMITZACIÓ DE COSTOS DE PRODUCCIÓ Un fabricant utilitza dos factors per elaborar un producte segons una tecnologia Cobb-Douglas , amb costos unitaris de 2 i 8 unitats monetàries. Per produir exactament 32 unitats al menor cost possible, planteja: Aquí (factors i ) i (quota de producció requerida).

COMPROVA-HO 2 Què ocorreria si en un programa d'optimització el nombre d'equacions de restricció independents fos exactament igual al nombre de variables instrumentals? 2. Conjunt factible, punts factibles i naturalesa dels òptims L'espai d'elecció d'un programa condicionat no és tot el domini de la funció objectiu, sinó exclusivament la regió que compleix les restriccions imposades. DEFINICIÓ: CONJUNT FACTIBLE I PUNT FACTIBLE El conjunt factible (o conjunt d'oportunitats) és el subconjunt de punts del domini de que satisfan simultàniament totes les equacions de restricció: Tot element que pertany a aquest conjunt s'anomena punt factible.

En el cas de la funció Cobb-Douglas anterior, la restricció equival a , que elevat al quadrat dóna . Amb variables positives ( ), el conjunt admissible és la branca positiva de la hipèrbola equilàtera . El punt és factible perquè . La resolució consisteix a trobar un punt factible que assoleixi el valor extrem de la funció objectiu sobre . Aquest valor rep el nom de valor òptim . Tipus d'òptim Domini de comparació Condició analítica estàndard Òptim lliure Tot l'espai o un obert sense restriccions Anul·lació del gradient: Òptim restringit Exclusivament sobre el conjunt factible Tangència entre nivells de i el conjunt factible m < n m = n 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 f A = {(x , … , x ) 1 n R : n g (x , … , x ) = j 1 n b , j = j 1, … , m} 4x y = 0,5 0,5 32 x y = 0,5 0,5 8 xy = 64 x > 0, y > 0 A y = x 64 (16, 4) 4 16 = 4 4 4 2 = 32 x = 0 (x , … , x ) 1 0 n 0 A A z = 0 f(x ) 0 Rn f(x) = 0 A f A Apunts de Matemàtiques II: Optimització i Dinàmica 6 EXEMPLE: DIVERGÈNCIA ENTRE ÒPTIM LLIURE I RESTRINGIT Considerem el problema de maximitzar : Sense restriccions (òptim lliure), el màxim s'assoleix al punt amb un valor de . Si s'afegeix la restricció lineal , el punt deixa de ser factible ( ). El màxim condicionat es troba al punt factible , que ofereix un valor inferior: .

COMPROVA-HO 3 Pot coincidir l'òptim lliure d'una funció objectiu amb el seu òptim restringit per igualtats? 3. Mètode gràfic de resolució ( ) Per a problemes de dues variables i una única restricció d'igualtat, el comportament de la solució s'interpreta mitjançant la geometria de les corbes de nivell de la funció objectiu ( ) i la corba de restricció ( ). REGLA GEOMÈTRICA DE TANGÈNCIA L'òptim d'un programa amb dues variables i una restricció d'igualtat se situa en el punt de tangència entre la corba de restricció i la corba de nivell més favorable de la funció objectiu.

Si la corba de restricció tallés transversalment una corba de nivell, existirien punts sobre la mateixa restricció que permetrien augmentar o disminuir el valor de la funció, descartant la condició d'òptim. z = 1 x 2 y2 (0, 0) z = 1 x + y = 1 (0, 0) 0 + 0 = 1 , (2 1 2 1 ) z = 1 (2 1 ) 2 = (2 1 ) 2 2 1 n = 2, m = 1 f(x, y) = c k g(x, y) = b Apunts de Matemàtiques II: Optimització i Dinàmica 7 Gràfica de la tangència entre corbes de nivell i la paràbola de restricció. Com s'observa a la figura superior per al programa: La restricció defineix la paràbola . Les corbes de nivell de la funció objectiu són rectes paral·leles de pendent -1 descrites per .

El valor màxim sobre la paràbola s'assoleix exactament en el punt de tangència , on la corba de nivell tangent és , donant un valor òptim . PER RECORDAR-HO En el punt de tangència geomètrica, els vectors gradients de la funció objectiu i de la restricció són col·lineals (paral·lels), base fonamental del mètode que s'estudia a «Optimització amb restriccions d'igualtat — Multiplicadors de Lagrange i anàlisi econòmica». 4.

Mètode directe o de substitució de variables El mètode directe consisteix a aïllar variables a partir de les equacions de restricció per introduir-les directament dins de la funció objectiu, convertint el problema condicionat inicial en un programa d'optimització lliure amb menys dimensions. { max s. a: z = x + y x + y = 1 2 y = 1 x2 x + y = c k y = x + c k , (2 1 4 3 ) c 1,25 z = 0 1,25 Apunts de Matemàtiques II: Optimització i Dinàmica 8 ERROR FREQÜENT Intentar aplicar el mètode de substitució quan les restriccions són altament no lineals pot introduir complicacions greus com indeterminacions, arrels de múltiples signes o pèrdua de solucions.

El mètode directe és especialment indicat i operatiu quan les restriccions són lineals. El procediment sistemàtic d'aplicació consta dels passos següents: Aïllar variables: A partir de les equacions de restricció, aïllar variables instrumentals en funció de les restants. 1 m m n m Construir la funció auxiliar: Substituir les expressions obtingudes dins de la funció objectiu original , generant una funció d'optimització lliure en variables independents. 2 f n m Càlcul de punts crítics: Imposar la condició de primer ordre igualant a zero totes les derivades primeres de la funció auxiliar.

3 Classificació de l'òptim: Determinar si el punt crític és màxim o mínim analitzant la matriu hessiana (o la segona derivada en el cas univariable). 4 Recuperació de variables i valor òptim: Obtenir les variables prèviament aïllades i avaluar la funció per calcular . 5 z 0 Apunts de Matemàtiques II: Optimització i Dinàmica 9 EXEMPLE: PROGRAMA AMB TRES VARIABLES I UNA RESTRICCIÓ LINEAL Resolem mitjançant substitució el problema: Aïllem de la restricció lineal: .

Substituint a la funció objectiu obtenim la funció auxiliar en dues variables: Calculem les derivades primeres i igualem a zero: Recuperem el valor de : Construïm la matriu hessiana de la funció auxiliar per verificar la naturalesa del punt: El primer menor principal és i el determinant és . La matriu és definida negativa, confirmant que el punt és un màxim. El valor màxim és . { max s.

a: u = xy + 2yz + xz x + 2y + 3z = 1 x 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 ) 4 < 0 ( 4)( 6) ( 3) = 2 24 9 = 15 > 0 u = 0 u , , = (5 2 5 1 15 1 ) 15 2 Apunts de Matemàtiques II: Optimització i Dinàmica 10 EXEMPLE: PROGRAMA AMB RESTRICCIÓ AÏLLABLE DIRECTA Resolem el problema: Aïllant , la funció auxiliar resultant d'una sola variable és: Derivem i cerquem els punts crítics: Analitzem la segona derivada : Per a : . La segona derivada és (mínim relatiu), amb valor òptim . Per a : .

La segona derivada és (màxim relatiu), amb valor òptim . EXEMPLE: PROGRAMA AMB DUES RESTRICCIONS LINEALS Considerem el problema de tres variables amb dues condicions lineals: De la segona equació obtenim . Substituint a la primera: . Substituint ambdues variables a la funció objectiu: Imposem la condició de primer ordre: Com que , es tracta d'un màxim. Els valors restants són i , resultant en el màxim amb valor òptim . COMPROVA-HO 4 Quantes variables té la funció auxiliar generada pel mètode directe si el problema original té 4 variables i 2 restriccions d'igualtat independents? { Opt s.

a: z = 2xy x + y = 3 2 y = 3 x2 z(x) = 2x(3 x ) = 2 6x 2x3 = dx dz 6 6x = 2 0 x = 2 1 x = ±1 = dx2 d z 2 12x x = 1 y = 3 ( 1) = 2 2 12( 1) = 12 > 0 z = 0 2( 1)(2) = 4 x = 1 y = 3 (1) = 2 2 12(1) = 12 < 0 z = 1 2(1)(2) = 4 max s. a: 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 = dx2 d u 2 10 < 0 y = 3 6 = 3 z = 8 2(3) = 2 (x, y, z) = (3, 3, 2) u = 0 3 Apunts de Matemàtiques II: Optimització i Dinàmica 11 IDEES CLAU Un programa d'optimització condicionada per igualtats maximitza o minimitza una funció objectiu sotmesa a equacions que han de complir-se estrictament.

El conjunt factible està format per tots els punts que satisfan simultàniament totes les restriccions d'igualtat del programa. Els òptims lliures i els restringits generalment divergeixen, atès que el punt que optimitza lliurement la funció sovint no pertany al conjunt factible. Geomètricament, per a dues variables i una restricció, l'òptim es localitza al punt de tangència entre una corba de nivell de la funció objectiu i la corba de restricció. El mètode directe o de substitució aïlla variables a partir de les restriccions i les substitueix a la funció objectiu, resultant especialment operatiu quan les restriccions són lineals. COMPROVA EL QUE HAS APRÈS 5.

En què es diferencia formalment el conjunt factible d'un problema lliure respecte d'un problema condicionat per igualtats? 6. Per què el mètode directe de resolució és especialment aconsellable quan les restriccions són lineals? OPTIMITZACIÓ AMB RESTRICCIONS D'IGUALTAT 2 Multiplicadors de Lagrange i anàlisi econòmica EN ACABAR SABRÀS Formular la funció de Lagrange i resoldre el sistema de condicions necessàries de primer ordre. Determinar la naturalesa dels punts crítics mitjançant la matriu hessiana restringida i el subespai tangent. Interpretar el concepte econòmic de preu ombra per avaluar la sensibilitat del valor òptim.

PENSA-HI ABANS DE LLEGIR 7 Com podem saber quant milloraria el benefici màxim d'una fàbrica si disposés d'una hora addicional de maquinària sense haver de tornar a resoldre tot el problema d'optimització des de zero? Funció de Lagrange i condicions de primer ordre Per superar les limitacions del mètode gràfic o la dificultat d'aïllar variables en el mètode directe (vegeu «Optimització amb restriccions d'igualtat — Fonaments i mètodes gràfic i directe»), s'utilitza el mètode dels multiplicadors de Lagrange.

Aquest enfocament permet transformar un problema amb m A m Apunts de Matemàtiques II: Optimització i Dinàmica 12 restriccions d'igualtat en un problema anàleg a l'optimització lliure incorporant les restriccions directament a la funció objectiu mitjançant unes noves variables anomenades multiplicadors. DEFINICIÓ Donat un programa d'optimització amb funció objectiu i restriccions d'igualtat (on ), la funció de Lagrange és la funció escalar de variables definida com: Els paràmetres reben el nom de multiplicadors de Lagrange. La recerca dels òptims s'inicia amb la condició necessària de primer ordre.

Tot òptim local que sigui un punt interior del domini de la funció objectiu ha de complir que el vector gradient de la funció de Lagrange sigui completament nul: Aquesta expressió condueix a un sistema de equacions amb incògnites: Les darreres equacions asseguren directament que la solució compleixi totes les restriccions del programa. Un punt factible que anul·la el gradient de la funció de Lagrange s'anomena punt crític o estacionari. COMPROVA-HO 8 Quina funció tenen les derivades de la funció de Lagrange respecte dels multiplicadors λ?

Matriu hessiana restringida i condició suficient de segon ordre Haver trobat un punt crític no permet discernir directament si es tracta d'un màxim, d'un mínim o d'un punt de sella. Per determinar el seu caràcter cal recórrer a la condició suficient de segon ordre, basada en la matriu hessiana calculada respecte a les variables instrumentals. f(x , … , x ) 1 n m g (x , … , x ) = j 1 n b j j = 1, … , m n + m L(x , … , x ; λ , … , λ ) = 1 n 1 m f(x , … , x ) 1 n λ j=1 m j (g (x , … , x ) j 1 n b ) j λ , … , λ 1 m R L(x , … , x ; λ , … , λ ) = 1 0 n 0 1 0 m 0 0 n + m n + m = 0, x i L = (g (x , … , x ) b ) = 0, λ j L j 1 n j i = 1, … , n j = 1, …

, m m Apunts de Matemàtiques II: Optimització i Dinàmica 13 DEFINICIÓ La matriu hessiana restringida d'un programa és la matriu quadrada i simètrica de mida formada per les derivades parcials segones de la funció de Lagrange respecte de les variables de decisió : Si la forma quadràtica associada a aquesta hessiana avaluada al punt crític ja és definida en tot l'espai, el caràcter de l'òptim queda determinat immediatament. No obstant això, en la majoria dels casos resulta indefinida o semidefinida, per la qual cosa cal avaluar el seu signe únicament sobre les direccions permeses per les restriccions: el subespai tangent homogeni.

Aquest subespai vectorial ve definit per l'anul·lació dels productes escalars entre els gradients de cadascuna de les restriccions i el vector de desplaçament instrumental: Quan les restriccions són lineals, aquest sistema homogeni coincideix amb les mateixes equacions de restricció però fixant tots els termes independents a zero. Signe de la forma quadràtica sobre el subespai tangent Classificació del punt crític Definida positiva ( ) Mínim local restringit Definida negativa ( ) Màxim local restringit n × n x , … , x 1 n H L(x; λ) = x …x 1 n x 1 2 L 2 x x n 1 L 2 x x 1 n L 2 x n 2 L 2 g (x , … , x ) j 1 0 n 0 (x , … , x ) = 1 n x = i=1 n x i g (x ) j 0 i 0, j = 1, …

, m Q(v) > 0, v = 0 Q(v) < 0, v = 0 Apunts de Matemàtiques II: Optimització i Dinàmica 14 PROCÉS Procediment de resolució amb multiplicadors de Lagrange Funció de Lagrange Plantejar L incorporant restriccions i multiplicadors 1 Condició de 1r ordre Resoldre el sistema de gradients nuls 2 Hessiana restringida Construir la matriu de derivades segones 3 Subespai tangent Projectar sobre el sistema homogeni de gradients 4 Classificació de l'òptim Determinar si és màxim o mínim segons el signe 5 Apunts de Matemàtiques II: Optimització i Dinàmica 15 EXEMPLE Considerem el programa següent: La funció de Lagrange associada és: Igualant les derivades parcials a zero: Sumant la primera i segona equació obtenim .

Igualant amb la tercera expressió ( ), resulta . Resolent el sistema de tres equacions lineals amb tres incògnites, trobem el punt crític únic amb multiplicadors i . La matriu hessiana restringida és constant: Com que els menors principals d'ordre 1 són nuls i el determinant val , la matriu és indefinida. Estudiem el signe de la forma quadràtica sobre el subespai definit pels gradients de les restriccions: Substituint en la forma quadràtica: Com que és definida negativa sobre el subespai tangent, el punt és un màxim restringit amb valor òptim .

max s.a: 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) = y + 2z λ λ = 0 x L 1 2 = x + z λ + λ = 0 y L 1 2 = 2x + y λ = 0 z L 1 x + y + z = 2 x y = 6 λ = 1 2 x+y+3z λ = 1 2x + y 3x + y 3z = 0 (x, y, z) = (3, 3, 2) λ = 1 3 λ = 2 2 H L = xyz 0 1 2 1 0 1 2 1 0 4 = 0 { (1,1,1) (x, y, z) = x + y + z = 0 (1, 1,0) (x, y, z) = x y = 0 y = x, z = 2x Q(x, x, 2x) = 2x(x) + 4x( 2x) + 2x( 2x) = 2x 2 8x 2 4x = 2 10x < 2 0 ( x = 0) (3, 3, 2) u = 0 3( 3) + 2(3)(2) + ( 3)(2) = 3 Apunts de Matemàtiques II: Optimització i Dinàmica 16 ERROR FREQÜENT Classificar el punt crític analitzant el caràcter de la matriu hessiana en tot en lloc de restringir- la al subespai tangent.

Si la matriu és indefinida en el conjunt global, el punt encara pot ser un extrem vàlid si la forma quadràtica adopta un signe constant sobre les direccions factibles que compleixen . COMPROVA-HO 9 Què cal concloure si la matriu hessiana restringida és indefinida en l'espai complet ? Interpretació econòmica dels multiplicadors: preus ombra i anàlisi de sensibilitat A més de permetre el càlcul matemàtic de l'òptim, els multiplicadors tenen un significat econòmic fonamental. Mesuren la sensibilitat del valor objectiu òptim davant petits increments o decrements en la disponibilitat dels recursos o exigències imposades per les constants de restricció.

DEFINICIÓ Si la constant de restricció experimenta una petita alteració , la variació aproximada del valor òptim ve donada per la fórmula diferencial de sensibilitat: Per aquest motiu, els multiplicadors s'anomenen preus ombra, ja que quantifiquen la valoració marginal interna de cada recurs en l'òptim. Aquesta expressió permet predir el comportament de la funció objectiu segons la combinació de signes: Si i , o bé i : el valor òptim augmenta aproximadament en . Si i , o bé i : el valor òptim disminueix aproximadament en . Si : una modificació infinitesimal de la cota no altera el valor objectiu assolit.

PER RECORDAR-HO La fórmula només estima el canvi en el valor òptim de la funció objectiu, no el desplaçament de les coordenades del punt crític . COMPROVA-HO 10 Si el multiplicador d'una restricció de producció val λ = 4, com canvia el cost mínim si augmentem la fita en 2 unitats? Rn g (x ) j 0 v = 0 b j Δb j z 0 Δz 0 λ j 0 Δb j λ > j 0 0 Δb > j 0 λ < j 0 0 Δb < j 0 z 0 λ j 0 Δb j λ > j 0 0 Δb < j 0 λ < j 0 0 Δb > j 0 z 0 λ j 0 Δb j λ = j 0 0 b j Δz 0 λ Δb (x , …

, x ) 1 n Apunts de Matemàtiques II: Optimització i Dinàmica 17 Aplicacions a la minimització de costos i al model de Markowitz Minimització de costos de producció Cobb-Douglas Considerem l'optimització del cost total subjecte a assolir una producció requerida de 32 unitats mitjançant una tecnologia de tipus Cobb-Douglas . La funció lagrangiana associada és: Les derivades parcials de primer ordre generen el sistema: Igualant ambdues expressions de s'obté la relació tècnica d'expansió . Substituint a la restricció de producció: El multiplicador associat és . La matriu hessiana restringida avaluada en resulta: Com que el seu determinant és nul ( ), és semidefinida positiva.

Estudiant el subespai tangent determinat pel gradient de producció : Substituint a la forma quadràtica: És definida positiva sobre el subespai tangent; per tant, el punt crític és un mínim de cost amb Atès que , un increment d'una unitat de producte ( ) suposarà un augment estimat del cost de Model de selecció de carteres de Markowitz En el model financer d'inversió de Markowitz, es pretén minimitzar el risc total d'una cartera subjecte a obtenir una rendibilitat objectiu fixada. Considerem dos actius amb rendibilitats esperades del 8 % i del 4 %, amb una funció de risc mesurada per la variància conjunta: on i representen les proporcions invertides en cada actiu.

Si s'exigeix una rendibilitat mitjana del 5 % ( ), plantegem el lagrangià: C(x, y) = 2x + 8y 4x y = 0,5 0,5 32 L(x, y; λ ) = 1 2x + 8y λ (4x y 1 0,5 0,5 32) = 2 λ (2x y ) = 0 λ = x L 1 0,5 0,5 1 y0,5 x0,5 = 8 λ (2x y ) = 0 λ = 4 y L 1 0,5 0,5 1 x0,5 y0,5 4x y = 32 0,5 0,5 λ 1 x = 4y 4(4y) y = 0,5 0,5 32 8y = 32 y = 4, x = 16 λ = 1 2 (16, 4; 2) H L(16,4; 2) = xy = ( λ x y 1 1,5 0,5 λ x y 1 0,5 0,5 λ x y 1 0,5 0,5 λ x y 1 0,5 1,5 ) ( 1/16 1/4 1/4 1 ) 1/16 1/16 = 0 g(16,4) = (1, 4) (1, 4) (x, y) = x + 4y = 0 x = 4y Q( 4y, y) = ( 4y) + 16 1 2 y 2 ( 4y)(y) = 2 1 y + 2 y + 2 2y = 2 4y > 2 0 ( y = 0) C = 0 2(16) + 8(4) = 64 u.m. λ = 1 2 > 0 Δb = 1 1 ΔC 0 2 1 = 2 u.m.

σ(x, y) = 0,0016x + 2 0,0004y 2 0,00096xy x y 0,08x + 0,04y = 0,05 L(x, y; λ ) = 1 0,0016x + 2 0,0004y 2 0,00096xy λ (0,08x + 1 0,04y 0,05) Apunts de Matemàtiques II: Optimització i Dinàmica 18 Les condicions de primer ordre condueixen al sistema lineal: La resolució ofereix els percentatges òptims d'inversió: El risc mínim assolit és . Si l'inversor exigeix elevar la rendibilitat esperada al 5,5 % ( ), el risc de la cartera augmentarà aproximadament en: COMPROVA-HO 11 Quina interpretació financera té el multiplicador λ en el model de carteres de Markowitz?

IDEES CLAU La funció de Lagrange sintetitza la funció objectiu i les restriccions d'igualtat en una sola expressió mitjançant els multiplicadors . La condició de primer ordre exigeix l'anul·lació de tot el gradient de la funció lagrangiana per localitzar els punts crítics. La classificació dels extrems s'efectua avaluant el signe de la forma quadràtica hessiana sobre el subespai tangent generat pels gradients de les restriccions. El multiplicador de Lagrange actua com a preu ombra segons la relació de sensibilitat . En carteres d'inversió, el multiplicador quantifica el cost en termes de risc associat a exigir un rendiment més elevat. COMPROVA EL QUE HAS APRÈS 12.

Com es defineix formalment el subespai vectorial tangent on cal estudiar la condició de segon ordre? 13. En un problema de maximització de beneficis, si un recurs té i es redueix la seva disponibilitat en , quin és l'efecte esperat sobre l'òptim? = 0,0032x 0,00096y 0,08λ = 0 x L 1 = 0,0008y 0,00096x 0,04λ = 0 y L 1 0,08x + 0,04y = 0,05 x = = 16 5 0,3125 (31,25%), y = = 8 5 0,625 (62,5%), λ = 1 = 200 1 0,005 σ(5/16, 5/8) = 1,25 10 4 Δb = 1 0,005 Δσ λ 1 Δb = 1 0,005 0,005 = 25 10 6 λ j Δz 0 λ j 0 Δb j λ = 15 Δb = 3 Apunts de Matemàtiques II: Optimització i Dinàmica 19 Test Encercla la resposta correcta. Les solucions són al final. 14.

Com s'anomena el conjunt de punts que compleixen totes les restriccions d'igualtat d'un programa? 15. Quina condició geomètrica defineix l'òptim en un programa amb dues variables i una restricció d'igualtat? 16. Quantes variables independents té la funció auxiliar obtinguda pel mètode directe a partir de n variables i m restriccions? 17. Per què un òptim lliure no sol coincidir amb l'òptim restringit d'un mateix problema? 18. Com s'obtenen els punts crítics en el mètode de Lagrange? 19. On s'ha d'analitzar el signe de la hessiana restringida? 20. Què representa econòmicament un multiplicador de Lagrange?

Conjunt de multiplicadors a) Subespai tangent de nivell b) Conjunt factible o d'oportunitats c) Domini no restringit d'elecció d) Intersecció perpendicular de les corbes a) Tangència entre corba de nivell i restricció b) Tall en l'origen de coordenades c) Punt on el pendent és nul d) m variables a) n · m variables b) n - m variables c) n + m variables d) Perquè el valor òptim sempre és zero a) Perquè les corbes de nivell es cancel·len b) Perquè la matriu hessiana canvia de signe c) Perquè l'òptim lliure rarament compleix les restriccions d) Aïllant totes les variables instrumentals directament a) Igualant a zero exclusivament la funció objectiu b) Calculant el determinant de la matriu de restriccions c) Anul·lant el gradient de la funció de Lagrange d) A tot l'espai vectorial de les variables a) Exclusivament sobre el conjunt de multiplicadors b) Només en l'origen de coordenades del problema c) Sobre el subespai tangent a les restriccions d) El cost fix de l'estructura organitzativa a) La taxa marginal de canvi de l'òptim b) El percentatge de desviació estàndard de la funció c) La quantitat màxima de producte que es ven d) Apunts de Matemàtiques II: Optimització i Dinàmica 20 21.

En el model de Markowitz, quin és l'efecte de demanar més rendibilitat? 3 Optimització amb restriccions de desigualtat — Programes canònics i resolució gràfica EN ACABAR SABRÀS Expressar problemes d'optimització en forma canònica de màxim o mínim mitjançant transformacions equivalents. Construir geomètricament el conjunt factible convex a partir de la intersecció de semiplans en el pla. Aplicar el teorema de Weierstrass per justificar l'existència d'òptims finits sobre conjunts compactes. Resoldre gràficament problemes de dues variables mitjançant corbes de nivell i identificar les restriccions saturades.

PENSA-HI ABANS DE LLEGIR 22 Què diferencia treballar amb restriccions de desigualtat en lloc d'igualtats a l'hora d'administrar recursos en una empresa? A diferència dels problemes amb lligams rígids estudiats a Optimització amb restriccions d'igualtat — Fonaments i mètodes gràfic i directe, en què calia consumir de manera estricta els recursos disponibles, la formulació amb desigualtats descriu situacions reals on podem gastar menys d'un límit o produir per sobre d'un mínim requerit.

El risc mínim augmenta segons el multiplicador a) La cartera passa a ser totalment invariable b) Els costos marginals de capital es redueixen c) El coeficient lambda esdevé exactament negatiu d) Apunts de Matemàtiques II: Optimització i Dinàmica 21 ESQUEMA Optimització amb restriccions de desigualtat 1. Formulació de programes canònics i equivalència formal Un problema d'optimització amb desigualtats s'estructura a partir d'un conjunt de variables sobre les quals s'avalua una funció objectiu subjecta a uns límits operatius.

DEFINICIÓ Un programa canònic de màxim s'expressa de la forma: De manera anàloga, un programa canònic de mínim presenta totes les restriccions orientades com a desigualtats de tipus major o igual: En aquestes expressions, és la funció objectiu, el vector conté les variables de decisió o instrumentals, són les funcions de restricció i són els termes independents o constants de restricció. Qualsevol model que contingui desigualtats invertides o operadors contraris es pot transformar en una forma canònica equivalent multiplicant la funció objectiu o les desigualtats per -1.

Formulació del programa Estructura canònica de màxim o mínim Canònic de màxim Restriccions de tipus menor o igual Canònic de mínim Restriccions de tipus major o igual Geometria factible Intersecció de semiplans i polígons Regió compacta Existència d'òptims per Weierstrass Regió no acotada Possibilitat d'òptims infinits Resolució gràfica Desplaçament de corbes de nivell Restricció saturada Verificació en igualtat estricta max s. a: z = f(x , … , x ) 1 n g (x , … , x ) b 1 1 n 1 g (x , … , x ) b m 1 n m min s. a: z = f(x , … , x ) 1 n g (x , … , x ) b 1 1 n 1 g (x , … , x ) b m 1 n m z = f(x , … , x ) 1 n (x , … , x ) 1 n n g (x , …

, x ) i 1 n m b i Apunts de Matemàtiques II: Optimització i Dinàmica 22 EXEMPLE Transformem a format canònic de mínim el següent problema: Com que , la nova funció a minimitzar és . Multiplicant la primera restricció per -1 invertim el sentit de la desigualtat a . El programa canònic resultant és: L'òptim d'ambdós sistemes coincideix en el punt . COMPROVA-HO 23 Com es converteix la restricció 2x - 5y 12 al format requerit per un programa canònic de mínim? 2. Geometria del conjunt factible i existència d'òptims El conjunt factible (o regió d'oportunitats) agrupa tots els punts del domini que satisfan simultàniament totes les restriccions de desigualtat.

Si aquest conjunt no és buit, el programa s'anomena factible; si no conté cap punt, és infactible. En el pla cartesià ( ), cada restricció lineal de desigualtat delimita un semiplà tancat. La intersecció de diversos semiplans defineix un polígon convex, determinat pels seus vèrtexs o punts extrems. Esquema del conjunt factible convex definit per semiplans lineals. max s. a: u = 27z x 3y 2 2 x y + z 0 y x 1 max(u) = min( u) u = x + 2 3y 2 27z x + y z 0 min s.

a: u = x + 3y 27z 2 2 x + y z 0 y x 1 ( 13,5, 4,5, 18) n = 2 Apunts de Matemàtiques II: Optimització i Dinàmica 23 Tipus de solució Condició de la funció objectiu Geometria del conjunt factible Òptim finit (acotat) Assoleix un valor numèric extrem en punts de la regió. Conjunt factible compacte (tancat i acotat) o funció afitada en la direcció de creixement. Òptim infinit (no acotat) Creix (en màxim) o decreix (en mínim) sense límit cap a . Conjunt factible necessàriament no acotat en la direcció favorable del gradient.

PER RECORDAR-HO Si la funció objectiu és contínua i el conjunt factible és un polígon tancat i fitat (compacte), el teorema de Weierstrass garanteix l'existència tant d'un màxim com d'un mínim global finits. COMPROVA-HO 24 Un conjunt factible no acotat implica forçosament que el programa tingui una solució infinita? 3. Resolució gràfica mitjançant corbes de nivell i restriccions saturades El mètode geomètric per a dues variables consisteix a dibuixar les corbes de nivell i avaluar com evoluciona la constant en creuar la regió admissible. Gràfica de desplaçament de corbes de nivell sobre el polígon factible.

Per determinar la solució òptima d'un programa en el pla se segueix aquest procediment ordenat: k R ± c = k {(x, y) R : 2 f(x, y) = k} k Apunts de Matemàtiques II: Optimització i Dinàmica 24 Una restricció de desigualtat s'anomena restricció saturada o activa en l'òptim quan es verifica amb igualtat estricta ( ), indicant que el recurs s'ha esgotat totalment. Si es compleix amb desigualtat estricta ( ), la restricció és no saturada. Gràfica de l'òptim lineal obtingut en el vèrtex extrem. Representar les rectes associades a cada restricció considerant la igualtat estricta.

1 Identificar el semiplà que compleix cada desigualtat i trobar la regió d'intersecció comuna juntament amb els seus vèrtexs. 2 A Traçar les corbes de nivell per a diversos valors de referència i determinar la direcció en què augmenta el valor de . 3 f(x, y) = k k Desplaçar la corba de nivell paralel·lament en el sentit d'augment (si maximitzem) o de reducció (si minimitzem) fins a l'últim punt de contacte amb el conjunt factible. 4 Llegir les coordenades del punt òptim i calcular el valor numèric extrem corresponent.

5 g (x ) = i b i g (x ) < i b i Apunts de Matemàtiques II: Optimització i Dinàmica 25 EXEMPLE Considerem el problema de producció amb recursos limitats en temps de manipulació: El conjunt factible és el quadrilàter tancat amb vèrtexs a , , i . Com que és compacte i és contínua, Weierstrass assegura un màxim finit. Les línies de nivell són rectes paral·leles de pendent negatiu. En augmentar , l'últim contacte amb la regió admissible es produeix en el vèrtex , on el benefici assoleix el valor òptim de 2325. Comprovem que satisfà simultàniament amb igualtat i ; per tant, totes dues restriccions queden saturades.

Si en canvi maximitzem una funció no lineal com ara , les corbes de nivell són circumferències concèntriques centrades a . El contacte òptim es troba per tangència en el punt amb un valor màxim de 6000. En aquest punt, (primera restricció saturada), mentre que (segona restricció no saturada). ERROR FREQÜENT No suposeu sempre que l'òptim es troba als vèrtexs del polígon: aquesta propietat només és vàlida per a funcions lineals. En problemes amb funció objectiu no lineal (com ara superfícies quadràtiques), les corbes de nivell poden fer tangència sobre un segment de la frontera o fins i tot assolir un màxim a l'interior sense saturar cap restricció.

COMPROVA-HO 25 Què significa econòmicament i matemàticament que una restricció estigui saturada en la solució trobada? IDEES CLAU Un programa canònic de màxim conté exclusivament restriccions de tipus , mentre que el de mínim en requereix de tipus . Qualsevol programa es pot transformar a format canònic invertint el signe de les funcions objectiu o de les restriccions mitjançant multiplicació per -1. Si el conjunt factible és un polígon compacte i la funció objectiu és contínua, el teorema de Weierstrass garanteix l'existència d'un màxim i un mínim globals finits.

Una restricció està saturada o activa en el punt òptim si es compleix amb igualtat estricta, fet que denota l'esgotament ple de la capacitat o recurs disponible. En problemes lineals l'òptim s'assoleix com a mínim en un vèrtex, mentre que en problemes no lineals pot produir-se per tangència al llarg d'una aresta o a l'interior. max s. a: z = 25x + 30y 6x + 10y 600 9x + 3y 720 x 0, y 0 (0, 0) (0, 60) (75, 15) (80, 0) z k (75, 15) 6(75) + 10(15) = 600 9(75) + 3(15) = 720 z = 100x + 102y 0,5x 2 0,5y 2 377 (100, 102) (55, 27) 6(55) + 10(27) = 600 9(55) + 3(27) = 576 < 720 Apunts de Matemàtiques II: Optimització i Dinàmica 26 COMPROVA EL QUE HAS APRÈS 26.

Per quina raó una funció objectiu quadràtica pot tenir el seu màxim en un punt d'una aresta i no en un vèrtex? 27. Com influeix el teorema de Weierstrass sobre el conjunt factible d'un problema de decisió? Test Encercla la resposta correcta. Les solucions són al final. 28. Quina orientació tenen les desigualtats en un programa canònic de màxim? 29. Com es converteix un problema de maximització en un de minimització equivalent? 30. Quan es considera que una restricció de desigualtat està saturada en l'òptim? 31. Què garanteix el teorema de Weierstrass si el conjunt factible és compacte i f és contínua?

Totes de tipus major o igual a) Totes de tipus menor o igual b) Combinació d'igualtats i desigualtats c) Desigualtats estrictes de menor d) Intercanviant les constants b pels coeficients a) Invertint les variables de signe b) Multiplicant la funció objectiu per -1 c) Dividint les restriccions per la constant d) Quan el terme independent b és nul a) Quan pren valor estrictament positiu b) Quan la variable associada val zero c) Quan la desigualtat es compleix amb igualtat d) Que cap restricció queda saturada a) Que l'òptim només és a l'origen b) L'existència d'òptims finits globals c) Que l'òptim sempre serà infinit d) Apunts de Matemàtiques II: Optimització i Dinàmica 27 4 Teorema fonamental i anàlisi de sensibilitat EN ACABAR SABRÀS Identificar i formular l'estructura algebraica d'un programa lineal canònic i la seva matriu tecnològica.

Aplicar el teorema fonamental de la programació lineal mitjançant el mètode d'inspecció de vèrtexs. Interpretar informes de sensibilitat de Solver per predir l'estabilitat del vèrtex davant canvis en coeficients objectiu. Calcular mitjançant preus ombra la modificació exacta del valor òptim davant variacions permissibles en recursos. PENSA-HI ABANS DE LLEGIR 32 Si el preu de venda d'un producte estrella puja un 5 %, cal canviar immediatament el pla de producció òptim de la fàbrica? Estructura del programa lineal canònic Un problema d'optimització s'anomena programa lineal quan tant la funció objectiu com les restriccions funcionals presenten exclusivament relacions lineals.

Els orígens formals d'aquesta disciplina es remunten a les taules d'entrada-eixida desenvolupades per V. Leontieff, als treballs del premi Nobel L. Kantorovich durant els anys 30 aplicats a la planificació soviètica, i a la formulació del transport als anys 40. A principis de la dècada de 1950, el matemàtic G. B. Dantzig va sistematitzar la resolució d'aquests problemes mitjançant el conegut mètode del símplex. Programació lineal 4 Teorema fonamental i anàlisi de sensibilitat 5 Models de planificació de la producció i del transport Apunts de Matemàtiques II: Optimització i Dinàmica 28 DEFINICIÓ Un programa lineal canònic de maximització o de minimització s'expressa de la forma següent: on .

Les variables de decisió han de complir estrictament condicions de no- negativitat. La matriu que agrupa els coeficients de les restriccions tècniques s'anomena matriu tecnològica i es denota habitualment com a d'ordre . EXEMPLE Considerem el programa econòmic: Aquest model presenta la matriu tecnològica . COMPROVA-HO 33 Quina condició sobre el sentit de les desigualtats han de complir les restriccions d'un programa canònic de maximització? Teorema fonamental i mètode d'inspecció de vèrtexs El conjunt de punts que satisfan totes les restriccions defineix una regió tancada que en dues dimensions és un polígon convex, en tres un políedre i en dimensions superiors rep el nom de politop.

El comportament geomètric dels extrems es formalitza mitjançant el teorema fonamental de la programació lineal: o b max z = c x + + c x 1 1 n n s.a: a x + + a x b 11 1 1n n 1 a x + + a x b m1 1 mn n m s.a: x , … , x 0 1 n e ˊ min z = c x + + c x 1 1 n n s.a: a x + + a x b 11 1 1n n 1 a x + + a x b m1 1 mn n m s.a: x , … , x 0 1 n c , a , b j ij i R M = (a ) ij m × n max z = 25x + 30y s.a: { 6x + 10y 600 9x + 3y 720 s.a: x, y 0 M = ( 6 9 10 3 ) Tot programa lineal amb solució finita assoleix el seu òptim global en com a mínim un dels vèrtexs del conjunt factible associat. 1 Qualsevol punt situat sobre el segment que uneix dos òptims globals finits és també un òptim global.

2 Tot programa lineal acotat (aquell el conjunt factible del qual és compacte i no buit) té garantida l'existència d'un mínim i d'un màxim globals finits. 3 Apunts de Matemàtiques II: Optimització i Dinàmica 29 Gràfica del conjunt factible amb solució òptima al vèrtex (75,15). En l'exemple anterior de beneficis , la resolució condueix a un polígon de vèrtexs , , i . Comprovant el valor de la funció en aquests punts, l'òptim s'assoleix de manera única al vèrtex . Per trobar l'extrem d'un conjunt acotat sense recórrer a mètodes iteratius complexos, n'hi ha prou d'avaluar la funció objectiu directament sobre tots els vèrtexs extrems del recinte factible.

Polígon factible acotat per a la inspecció d'extrems als vèrtexs. z = 25x + 30y (0,0) (80,0) (0,60) (75,15) (75,15) Apunts de Matemàtiques II: Optimització i Dinàmica 30 EXEMPLE Resolem el programa acotat següent: El recinte generat és un polígon acotat amb vèrtexs a , , , i . Avaluant cadascun: Per comparació directa: . Per tant, el màxim global és únic al vèrtex amb valor . En canvi, el mínim global val i s'assoleix en qualsevol punt del segment d'extrems i . COMPROVA-HO 34 Què passa si dos vèrtexs adjacents proporcionen el mateix valor màxim de la funció objectiu?

Anàlisi de sensibilitat de la funció objectiu L'anàlisi de sensibilitat examina com es modifica la solució òptima d'un programa quan canvien els coeficients del model sense necessitat de reiniciar el càlcul des de zero. En els informes de sensibilitat generats per aplicacions com el Solver d'Excel, la informació es divideix en la taula de cel·les canviants i la taula de restriccions.

Nom Valor final Gradient reduït Coeficient objectiu Augment permissible Decrement permissible 75 0 25 65 7 15 0 30 11,66 21,66 Aquesta sortida indica que el punt òptim inicial correspon a fabricar i , generant un benefici òptim inicial: Mentre la variació d'un coeficient es mantingui dins l'interval d'augment i decrement permissible, el punt òptim (vèrtex) no varia.

Per tant, la combinació de variables continua sent : Optimitzar z = 7x + 14y 5 s.a: x + 3y 9 2x + y 8 x + 2y 2 s.a: x, y 0 (0,1) (2,0) (4,0) (3,2) (0,3) z(0,1) z(2,0) z(4,0) z(0,3) z(3,2) = 7(0) + 14(1) 5 = 9 = 7(2) + 14(0) 5 = 9 = 7(4) + 14(0) 5 = 23 = 7(0) + 14(3) 5 = 37 = 7(3) + 14(2) 5 = 44 z(0,1) = z(2,0) = 9 < z(4,0) = 23 < z(0,3) = 37 < z(3,2) = 44 (3,2) z = 44 z = 9 (0,1) (2,0) x y x = 0 75 y = 0 15 z = 0 25 75 + 30 15 = 1875 + 450 = 2325 (75,15) Apunts de Matemàtiques II: Optimització i Dinàmica 31 Per a : l'augment màxim tolerat és de 65 i el decrement de 7. L'interval de validesa és . Si es redueix 5 unitats ( ), l'òptim es manté a i el nou benefici és .

Si la variació depassa aquests marges (com ara una disminució de 10 unitats, deixant ), el vèrtex òptim canvia i la taula no permet predir la nova solució sense recalcular. Per a : l'interval permissible s'estén entre i . PROCÉS Avaluació d'alteracions en la funció objectiu 1 Comprovar l'interval Verificar si la variació de c_j cau dins els marges permissibles. 2 Mantenir el vèrtex Si és permissible, les coordenades de la solució òptima no canvien. 3 Recalcular el benefici Avaluar la nova funció objectiu directament sobre el mateix vèrtex. COMPROVA-HO 35 Si el coeficient c1 augmenta en 40 unitats (passant de 25 a 65), quines seran les coordenades del nou punt òptim?

Anàlisi de sensibilitat de les restriccions de recursos La segona part de l'informe analitza la disponibilitat dels recursos (termes independents del costat dret): Nom Valor final Preu ombra Restricció del costat dret Augment permissible Decrement permissible R1 600 2,708 600 1800 120 R2 720 0,972 720 180 540 El preu ombra ( ) mesura quant augmenta la funció objectiu per cada unitat addicional del recurs corresponent.

A diferència de l'optimització no lineal general (vegeu «Optimització amb restriccions d'igualtat — Multiplicadors de Lagrange i anàlisi econòmica»), en la programació lineal la variació del valor òptim associada a un canvi permissible en la constant de restricció és exactament z = b. PER RECORDAR-HO Dins dels límits permissibles: Variació en coeficients de la funció objectiu: el vèrtex es manté fix, el valor canvia només pels nous preus. Variació en recursos ( ): el vèrtex es desplaça, però el guany unitari marginal ( ) és constant i l'ajust de és purament proporcional ( ).

c = 1 25 [25 7, 25 + 65] = [18, 90] c 1 c = 1 20 (75,15) z = (25 5) 75 + 30 15 = 1950 c = 1 15 < 18 c = 2 30 30 21,66 = 8,34 30 + 11,66 = 41,66 b i λ i Δ λ Δ z b i λ i z Δz = λ Δb i i Apunts de Matemàtiques II: Optimització i Dinàmica 32 Avaluem un increment de disponibilitat de 600 minuts en el procés 1 ( ). Com que l'augment permissible arriba a 1800 minuts, el preu ombra és plenament operatiu: ERROR FREQÜENT Confondre l'efecte d'una alteració en un coeficient objectiu amb un canvi en la restricció. Si canvia el costat dret d'una restricció ( ), el punt òptim original sí que canvia perquè el polígon es deforma, encara que estiguem dins del rang permissible.

El que roman inalterat en aquest rang és el preu ombra , la qual cosa permet emprar l'equació lineal exacta . Si la disminució sobrepassa el límit (per exemple, reduir en 300 minuts quan el decrement permissible és 120), el preu ombra canvia i la fórmula deixa de ser vàlida. COMPROVA-HO 36 Quina és la variació de la funció objectiu si la restricció R2 augmenta en 100 minuts? IDEES CLAU Un programa lineal canònic exigeix linealitat estricta tant a la funció objectiu com a les restriccions, acompanyades de restriccions de no-negativitat a les variables.

El teorema fonamental assegura que la solució òptima d'un programa lineal finit sempre es localitza en almenys un dels vèrtexs del conjunt factible. Els programes lineals acotats amb regió factible no buida tenen garantida l'existència de màxim i mínim globals finits. Mentre la modificació d'un coeficient de la funció objectiu romangui dins l'interval d'augment i decrement permissible, el vèrtex òptim no varia. Dins l'interval permissible de les constants de recursos, la variació del valor òptim és lineal i exacta mitjançant l'expressió . COMPROVA EL QUE HAS APRÈS 37. Per què en un programa lineal acotat és suficient avaluar exclusivament els vèrtexs per identificar el màxim o mínim global?

38. Quina diferència conceptual hi ha entre l'interval permissible d'un coeficient de la funció objectiu i el d'un terme independent de restricció? PROGRAMACIÓ LINEAL Δb = 1 600 λ = 1 2,708 Comprovem que (estem dins del rang permissible). 1 Δb = 1 600 1800 Calculem la variació exacta del benefici: unitats. 2 Δz = 0 λ 1 Δb = 1 2,708 600 = 1624,8 Determinem el nou valor òptim sumant la variació al valor base: unitats.

3 z = 0 z + 0 Δz = 0 2325 + 1624,8 = 3949,8 b i (x , y ) 0 0 λ i Δz = λ Δb i i b 1 Δz = λ Δb Apunts de Matemàtiques II: Optimització i Dinàmica 33 5 Models de planificació de la producció i del transport EN ACABAR SABRÀS Formular el programa lineal clàssic de planificació de la producció a partir de recursos limitats. Formular el model clàssic del transport amb restriccions d'oferta i de demanda mínima. Calcular les variacions en el benefici o cost òptim aplicant preus ombra davant alteracions permissibles. PENSA-HI ABANS DE LLEGIR 39 Com pot una empresa calcular el cost d'un augment de demanda sense haver de refer tot el càlcul d'optimització?

Model de planificació de la producció El problema clàssic de planificació de la producció determina quantes unitats s'han d'elaborar de cada producte per fer màxima la utilitat o el benefici net global, sense sobrepassar la quantitat de factors productius disponibles a l'empresa. Suposem una organització que fabrica i comercialitza béns diferents a partir de recursos o matèries primeres: La quantitat de recurs necessària per produir una unitat del bé és constant i val (coeficients tècnics). La disponibilitat límit del factor és una fita constant . El rendiment o benefici unitari net obtingut per la venda del producte és una constant .

Les variables d'actuació representen el volum de fabricació de cada producte . Com que elaborar unitats consumeix del recurs , la despesa total d'aquest recurs és el sumatori de tots els productes, el qual no pot superar el màxim . DEFINICIÓ El model de planificació de la producció se sintetitza com un programa lineal canònic de màxim: (vegeu «Programació lineal — Teorema fonamental i anàlisi de sensibilitat») També existeixen variants d'aquest model orientades a la minimització de despeses operatives, o bé models que incorporen costos d'administració fixos sostrets directament de la funció d'ingrés net. n m i j a ij 0 i b i 0 j c j 0 x j j x j a x ij j i b i max s.a.

z = c x j=1 n j j a x b , i = 1, … , m j=1 n ij j i x 0, j = 1, … , n j Apunts de Matemàtiques II: Optimització i Dinàmica 34 PROCÉS Estructura del model de producció 1 Recursos limitats Fites de disponibilitat de matèries primeres 2 Matriu tecnològica Consums unitaris de cada factor 3 Producció òptima Quantitats x que maximitzen benefici Resolució d'un model de producció i anàlisi de sensibilitat Quan disposem de dues variables de decisió, el conjunt de solucions admissibles esdevé una regió poligonal continguda en el primer quadrant.

Segons el teorema fonamental de la programació lineal (vegeu «Programació lineal — Teorema fonamental i anàlisi de sensibilitat»), l'òptim d'un programa lineal acotat es troba sempre en un dels seus vèrtexs extrems. Apunts de Matemàtiques II: Optimització i Dinàmica 35 EXEMPLE Una empresa produeix dos articles, P i Q, a partir de tres recursos: ferro, fusta i plàstic. Els requeriments per unitat, la disponibilitat límit i els beneficis unitaris són els següents: Recurs Producte P ( ) Producte Q ( ) Disponibilitat màxima Ferro 3 kg 6 kg 54 tones (54.000 kg) Fusta 6 kg 4 kg 48 tones (48.000 kg) Plàstic 5 kg 5 kg 50 tones (50.000 kg) Els beneficis unitaris són de 22 u.m. per a P i de 18 u.m.

per a Q, amb uns costos fixos d'administració de 100.000 u.m. Plantegem el programa: Gràfica de la regió factible amb vèrtex òptim a (4.000, 6.000). El conjunt factible delimitat pels semiplans té com a vèrtexs , , , i . Avaluant la funció d'utilitat en cada vèrtex, comprovem que l'òptim s'assoleix al punt: El benefici òptim és: x y max s.a. z = 22x + 18y 100.000 3x + 6y 54.000 6x + 4y 48.000 5x + 5y 50.000 x, y 0 (0, 0) (8.000, 0) (4.000, 6.000) (2.000, 8.000) (0, 9.000) (x , y ) = (4.000, 6.000) Apunts de Matemàtiques II: Optimització i Dinàmica 36 Un cop conegut el vèrtex òptim, podem avaluar alteracions en els marges mitjançant l'anàlisi de sensibilitat lineal.

Si l'increment d'un coeficient de la funció objectiu no supera l'augment permissible, les coordenades del vèrtex òptim romanen inalterades. Per exemple, si el marge del producte P té un augment permissible de 5 u.m. i s'incrementa en 4 u.m., el pla de producció continuarà sent i el nou guany serà: COMPROVA-HO 40 Què passa amb el punt de producció òptim si el marge de guany d'un bé s'incrementa per sota del límit permissible? Model clàssic del transport El model de transport distribueix un producte homogeni des d'un conjunt de centres subministradors (magatzems o fàbriques) cap a diversos centres consumidors (mercats o minoristes), amb l'objectiu de minimitzar el cost logístic total.

Considerem orígens amb existències i destinacions amb quotes de demanda . El cost d'enviar una unitat des de l'origen fins a la destinació és una quantitat coneguda . Definim la variable de decisió com el volum de mercaderia traslladat de l'origen a la destinació . L'import total del transport d'un centre emissor és: El programa complet ha de satisfer tant els sostres d'estoc dels magatzems com les demandes mínimes dels clients: DEFINICIÓ El model clàssic del transport és un programa lineal de mínim expressat per: z = 0 22(4.000) + 18(6.000) 100.000 = 96.000 u.m. (4.000, 6.000) z = 0 (22 + 4) 4.000 + 18 6.000 100.000 = 112.000 u.m. m s , … , s 1 m 0 n d , …

, d 1 n 0 i j c > ij 0 x ij i j i c x = j=1 n ij ij c x + i1 i1 + c x in in min s.a. z = c x i=1 m j=1 n ij ij x s , i = 1, … , m (restriccions d'oferta) j=1 n ij i x d , j = 1, … , n (restriccions de demanda) i=1 m ij j x 0, i, j ij Apunts de Matemàtiques II: Optimització i Dinàmica 37 PROCÉS Flux del model de transport 1 Orígens i existències Centres emissors amb fita màxima d'oferta 2 Distribució logística Variables x_ij a cost c_ij 3 Destinacions i demanda Centres receptors amb requeriment mínim Preus ombra i alteració de condicions Atès l'elevat nombre de variables ( ), la resolució d'aquests problemes es du a terme mitjançant eines computacionals d'optimització com ara SOLVER d'Excel.

Davant d'oscil·lacions en la disponibilitat o en les comandes, recorrem al valor del preu ombra de la restricció (vegeu «Optimització amb restriccions d'igualtat — Multiplicadors de Lagrange i anàlisi econòmica»). Sempre que la pertorbació es mantingui dins de l'interval permissible, la taxa marginal roman fixa i es compleix estrictament la relació: m × n Δz = 0 λ k Δb k Apunts de Matemàtiques II: Optimització i Dinàmica 38 EXEMPLE Dos magatzems, M i N, proveeixen tres establiments comercials, A, B i C.

La taula de costos unitaris de transport, existències i demandes és la següent: Costos (u.m.) Client A Client B Client C Existències Magatzem M (1) 2 3 5 500 unitats Magatzem N (2) 3 4 7 700 unitats Demandes 200 unitats 250 unitats 200 unitats — Formulem el programa amb (enviament del magatzem al minorista ): La resolució ofereix el vector òptim: El cost mínim és de Si la demanda de l'establiment A (tercera restricció, ) té un augment permissible de 550 unitats amb un preu ombra associat , i la seva comanda creix en unitats: El nou cost logístic mínim serà ERROR FREQÜENT Quan la capacitat d'un recurs o una demanda varia, l'expressió només s'aplica si el canvi està contingut dins de l'interval permissible de variació.

Si la variació supera aquesta tolerància, el preu ombra pot canviar de valor i la fórmula deixa de ser exacta. COMPROVA-HO 41 Per què un increment en la demanda d'un centre provoca un increment en el cost total mínim del transport? x ij i j min s.a. z = (2x + 3x + 5x ) + (3x + 4x + 7x ) 11 12 13 21 22 23 x + x + x 500 11 12 13 x + x + x 700 21 22 23 x + x 200 11 21 x + x 250 12 22 x + x 200 13 23 x 0 ij (x , x , x , x , x , x ) = 11 12 13 21 22 23 (50, 250, 200, 150, 0, 0) z = 0 2.300 u.m. b 3 λ = 3 3 u.m. Δb = 3 130 Δz = 0 λ 3 Δb = 3 3 130 = 390 u.m. z = 0 2.300 + 390 = 2.690 u.m.

Δz = 0 λ Δb Δb Apunts de Matemàtiques II: Optimització i Dinàmica 39 IDEES CLAU Els models de planificació de la producció maximitzen el rendiment net sotmès a les fites màximes de disponibilitat de factors. El model del transport busca minimitzar el cost logístic global cobrint demandes mínimes sense excedir la capacitat dels magatzems. Mentre la modificació d'un guany unitari romangui dins de l'interval permissible, les quantitats òptimes a fabricar es mantenen inalterades. L'impacte sobre el valor òptim provocat per una alteració permissible en els recursos o demandes es calcula amb la relació exacta . COMPROVA EL QUE HAS APRÈS 42.

Com s'expressa la restricció d'oferta del magatzem en el model de transport? 43. Si una restricció té un preu ombra de 3 u.m. i el seu terme independent creix en 130 unitats de manera permissible, quant varia la funció objectiu? Test Encercla la resposta correcta. Les solucions són al final. 44. On es troba sempre l'òptim d'un programa lineal amb solució finita segons el seu teorema fonamental? 45. Què succeeix amb el punt òptim si un coeficient objectiu varia dins del seu interval permissible? 46. Com es calcula la variació del valor òptim en PL davant d'un canvi permissible del terme de restricció Δb?

Δz = λ Δb i En el punt de gradient nul a) En com a mínim un dels vèrtexs b) En el centre de gravetat del polígon c) En un punt interior del conjunt d) Es desplaça al llarg de la vora a) El gradient reduït augmenta b) El punt òptim no varia c) Canvia a un vèrtex adjacent d) Δz no es pot determinar sense recalcular a) Δz = λ · Δb de forma exacta b) Δz λ · Δb només aproximada c) Δz = (λ)² · Δb d) Apunts de Matemàtiques II: Optimització i Dinàmica 40 47. Si el decrement permissible del recurs b és 120 i es redueix en 300 unitats, què podem concloure? 48. Quin sentit tenen les restriccions d'oferta en el model de transport? 49.

Si un coeficient de la funció objectiu canvia dins del marge permissible: 50. Com es quantifica la variació de l'òptim davant un canvi permissible a la restricció k? 51. En el model de producció, els coeficients a_ij representen: El nou valor és z - 300·λ a) El preu ombra canvia i no sabem el nou valor directament b) El valor òptim no canvia c) El programa esdevé automàticament infactible d) Són restriccions de cost nul. a) Són fites mínimes de recepció. b) Són igualtats d'equilibri financer. c) Són fites màximes de capacitat. d) El vèrtex òptim canvia de lloc. a) El vèrtex òptim es manté idèntic. b) El preu ombra es fa zero. c)…