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

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 complets de Matemàtiques II per a ADE i Economia (UB): mètode 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. Formalització del programa amb restriccions d'igualtat 2. Mètode gràfic: corbes de nivell i gradients 3.

Mètode directe o per substitució 2 Mètode de Lagrange i condicions d'optimalitat Fonament i formulació de la funció de Lagrange Condició necessària de primer ordre: punts crítics La matriu hessiana restringida i les condicions de segon ordre 3 Interpretació econòmica i aplicacions Sensibilitat del valor òptim i preus ombra Interpretació del signe del multiplicador de Lagrange Model de carteres d'inversió de Markovitz Aplicacions a la producció, el benefici i el condicionament de superfícies 4 Optimització amb restriccions de desigualtat — Formes canòniques i mètode gràfic Formulació general i formes canòniques Geometria del conjunt factible: semiplans i polígons convexos Tipologia de solucions: òptims finits i infinits Mètode gràfic: corbes de nivell i vectors gradient Restriccions saturades i restriccions amb folgança Programació lineal 5 Teorema fonamental i resolució gràfica Estructura del programa lineal canònic Teorema fonamental de la programació lineal Mètode algebraic-geomètric de resolució i avaluació de vèrtexs Casos particulars: arestes òptimes i programes no acotats 6 Models econòmics d'assignació, transport i dieta Model de planificació de la producció Model del transport Model de la dieta i mescles Resolució computacional i anàlisi de solucions 7 Càlcul integral — Primitiva, integral indefinida i integrals immediates Concepte de primitiva i la constant d'integració Apunts de Matemàtiques II: Optimització i Anàlisi Dinàmica 1 Integral indefinida i interpretació geomètrica Taula fonamental d'integrals immediates Linealitat, integració logarítmica i integrals quasi immediates 8 Mètodes d'integració — Canvi de variable i integració per parts Diferencial d'una funció en un punt Fórmula d'integració per parts Tipologies clàssiques d'integració per parts Mètode d'integració per substitució o canvi de variable 9 Integral definida — Teorema fonamental del càlcul i càlcul d'àrees planes Definició i interpretació geomètrica de la integral definida Propietats fonamentals de la integral definida Funció integral i Teorema Fonamental del Càlcul Avaluació d'integrals: la Regla de Barrow Càlcul d'àrees planes 10 Aplicacions econòmiques de la integració — Marginalitat, excedents i acumulació temporal Reconstrucció de funcions totals a partir de magnituds marginals Càlcul d'àrees per trams en corbes econòmiques Equilibri de mercat i excedents del consumidor i del productor Acumulació temporal de demanda i esgotament de reserves 11 Equacions diferencials ordinàries — Fonaments i equacions de primer ordre 1.

Concepte d'equació diferencial ordinària i ordre 2. Tipus de solucions i interpretació geomètrica 3. Formes d'expressió d'una equació diferencial de primer ordre 4.

Variables separades i variables separables 12 Equacions diferencials de primer ordre — Lineals i equacions de Bernouilli Equacions diferencials lineals de primer ordre Mètode de descomposició del producte u · v L'equació de Bernouilli Aplicació: model logístic de creixement poblacional 13 Equacions diferencials lineals de segon ordre a coeficients constants Estructura de l'equació lineal de segon ordre Resolució de l'equació reduïda i equació característica Càlcul de la solució particular de terme constant Problemes de condicions inicials 14 Models dinàmics en economia — Acumulació de capital i ajust del preu de Walras Model d'acumulació instantània de capital Apunts de Matemàtiques II: Optimització i Anàlisi Dinàmica 2 Model dinàmic d'ajust del preu de Walras Estabilitat asimptòtica del preu d'equilibri Aplicació addicional: Llei de refredament de Newton 15 Models macroeconòmics avançats — Model de creixement de Solow i corba de Phillips Model de creixement de Solow Resolució de l'equació de Solow com a equació de Bernouilli Model dinàmic de la corba de Phillips Deducció de l'equació de segon ordre per a la inflació esperada Trajectòries temporals d'inflació efectiva i atur 16 Formulari 1.

Optimització amb restriccions d'igualtat 2. Optimització amb restriccions de desigualtat i Programació Lineal 3. Càlcul integral de funcions d'una variable 4. Equacions diferencials ordinàries (EDO) Constants i errors típics 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 Anàlisi Dinàmica 3 1 Fonaments i mètodes gràfic i directe EN ACABAR SABRÀS Formular formalment un programa d'optimització condicionat per igualtats identificant els seus elements.

Trobar la solució d'un programa de dues variables mitjançant el mètode gràfic i la proporcionalitat de gradients. Aplicar el mètode directe de substitució de variables en programes amb restriccions lineals. PENSA-HI ABANS DE LLEGIR 1 Per què el màxim o mínim d'una funció sobre una corba no sol coincidir amb el seu extrem absolut sense restriccions? L'optimització matemàtica constitueix una eina fonamental per a la presa de decisions en l'àmbit econòmic i empresarial. El seu propòsit principal és distribuir recursos escassos entre diverses opcions d'una manera eficient.

Quan aquests recursos s'han d'esgotar amb exactitud, sorgeixen els problemes d'optimització condicionats per restriccions d'igualtat. Optimització amb restriccions d'igualtat 1 Fonaments i mètodes gràfic i directe 2 Mètode de Lagrange i condicions d'optimalitat 3 Interpretació econòmica i aplicacions Apunts de Matemàtiques II: Optimització i Anàlisi Dinàmica 4 ESQUEMA Optimització amb restriccions d'igualtat 1. Formalització del programa amb restriccions d'igualtat Un problema matemàtic on es busca extremar una funció sota condicions obligatòries rep el nom de programa d'òptims restringits per igualtats.

L'estructura analítica general s'escriu: Els elements que configuren aquesta formulació són: La funció objectiu escalar , que descriu la magnitud que volem maximitzar o minimitzar (per exemple, un cost, un benefici o una utilitat). Les variables de decisió o instrumentals , sobre les quals podem triar els valors. En aplicacions econòmiques habitualment prenen valors no negatius. Les funcions escalars de restricció (amb ). Les constants de restricció , que fixen el nivell exacte exigit.

DEFINICIÓ El conjunt factible (o regió admissible) d'un programa, habitualment denotat per , és la intersecció de tots els punts que satisfan simultàniament les equacions de restricció: Qualsevol vector que compleix aquesta condició s'anomena punt factible. Un punt factible és un òptim del programa si fa màxima o mínima la funció objectiu comparat amb la resta de punts de . La imatge correspon al valor òptim. La presència de restriccions modifica substancialment l'òptim d'una funció: el màxim o mínim lliure rarament coincideix amb el màxim o mínim condicionat, ja que aquest darrer queda limitat a la superfície de la restricció.

Fonaments i mètodes Formulació, mètode gràfic i substitució directa Mètode de Lagrange Condicions d'optimalitat de primer i segon ordre Aplicacions econòmiques Preu ombra i decisions de producció o carteres 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 f : A R n R n (x , … , x ) 1 n m g : j A R n R j = 1, … , m m b , … , b 1 m R B Rn m B = {(x , … , x ) 1 n A : g (x , … , x ) = j 1 n b , j = j 1, … , m} x = 0 (x , … , x ) 1 0 n 0 B B z = 0 f(x ) 0 Apunts de Matemàtiques II: Optimització i Anàlisi Dinàmica 5 Gràfica de la diferència entre un extrem lliure i un extrem restringit.

COMPROVA-HO 2 Quina diferència conceptual existeix entre el domini de definició de la funció objectiu i el conjunt factible del programa? 2. Mètode gràfic: corbes de nivell i gradients Quan el programa té dues variables de decisió ( ) i una única restricció d'igualtat ( ), es pot abordar geomètricament: El procediment gràfic es fonamenta en les propietats diferencials del vector gradient: 1. La direcció del vector gradient és perpendicular a la recta tangent de la corba de nivell que travessa el punt . 2. El sentit del gradient indica la direcció de màxim creixement instantani de la funció.

Així, en el punt òptim , la corba de nivell de la funció objectiu ha de ser tangent a la corba que descriu la restricció . En cas de tallar-se transversalment, sempre seria possible desplaçar- se sobre la restricció augmentant o disminuint el valor de la funció objectiu. n = 2 m = 1 Optimitzar s.a z = f(x, y) g(x, y) = b f(a, b) (a, b) (x , y ) 0 0 g(x, y) = b Apunts de Matemàtiques II: Optimització i Anàlisi Dinàmica 6 Esquema del punt de tangència entre corbes de nivell i restricció. Com que totes dues corbes comparteixen la mateixa recta tangent en el punt de contacte, els seus respectius vectors gradients han de tenir la mateixa direcció ortogonal.

Per tant, els gradients són proporcionals: Per a aprofundir en el sentit i propietats analítiques d'aquest escalar, vegeu «Optimització amb restriccions d'igualtat — Mètode de Lagrange i condicions d'optimalitat». EXEMPLE Considerem el problema de minimitzar el cost de contractar dos factors de producció, amb preus unitaris de 2 i 8 unitats monetàries, subjecte a produir 32 unitats mitjançant una funció de Cobb- Douglas : La restricció equival a , una hipèrbola equilàtera en el primer quadrant. Les corbes de nivell del cost són rectes de pendent negatiu . L'òptim s'assoleix al punt de tangència: Substituint a la corba factible: .

L'òptim és (16, 4), el multiplicador val i el cost mínim és C = 64. f(x , y ) = 0 0 λ g(x , y ), λ 0 0 R Q(x, y) = 4x y 0,5 0,5 min s.a C(x, y) = 2x + 8y 4x y = 32 0,5 0,5 x y = 64 2x + 8y = k C = (2, 8), g(x, y) = xy 64 g = (y, x) { 2 = λy 8 = λx λ = = y 2 x 8 x = 4y (4y)y = 64 4y = 2 64 y = 4 x = 16 λ = 2 Apunts de Matemàtiques II: Optimització i Anàlisi Dinàmica 7 Gràfica de la tangència entre la recta de cost i la hipèrbola. COMPROVA-HO 3 Quina condició geomètrica han de satisfer els vectors gradients en el punt de solució gràfica d'un problema amb igualtats? 3.

Mètode directe o per substitució El mètode directe (també denominat per substitució o eliminació de variables) consisteix a aïllar una o més variables a partir de les equacions de restricció per inserir-les directament a la funció objectiu. D'aquesta manera, el problema restringit original es transforma en un problema d'optimització sense restriccions amb menor dimensió. Aïllar una variable en funció de les altres a partir de l'equació de restricció. 1 Substituir l'expressió obtinguda a la funció objectiu per obtenir una funció reduïda. 2 Calcular els punts crítics de la funció reduïda igualant a zero les seves primeres derivades parcials.

3 Classificar el punt crític mitjançant la matriu hessiana ordinària. 4 Recuperar el valor de la variable eliminada i determinar el valor extrem. 5 Apunts de Matemàtiques II: Optimització i Anàlisi Dinàmica 8 EXEMPLE Volem descompondre el número 120 en tres sumands de manera que la suma dels seus productes binaris sigui màxima: Aïllem la variable i la substituïm a la funció objectiu: Calculem les derivades parcials i igualem a zero: La matriu hessiana és constant: Com que i el determinant és , la matriu és definida negativa, confirmant un màxim. La tercera variable és . L'òptim absolut és . ERROR FREQÜENT Intentar aplicar el mètode de substitució quan les restriccions no són lineals.

Aïllar variables en equacions no lineals pot resultar impossible analíticament o pot introduir arrels que amaguin solucions o n'alterin el domini real. Quan la restricció és no lineal, cal recórrer al mètode dels multiplicadors de Lagrange (vegeu «Optimització amb restriccions d'igualtat — Mètode de Lagrange i condicions d'optimalitat»).

Mètode Àmbit d'aplicació Avantatges Inconvenients Gràfic variables i restricció Comprensió intuïtiva de la tangència i relació entre gradients No aplicable a problemes amb tres o més dimensions Directe Restriccions lineals on l'aïllament és immediat Redueix la dimensió i permet utilitzar càlcul sense restriccions Fracassa o es complica greument amb restriccions no lineals x, y, z max s.a P (x, y, z) = xy + xz + yz x + y + z = 120 z = 120 x y P (x, y) = xy + (x + y)(120 x y) = x 2 y 2 xy + 120x + 120y { = 2x y + 120 = 0 x P = x 2y + 120 = 0 y P (x, y) = (40, 40) H (40, 40) = ( 2 1 1 2 ) 2 < 0 ( 2)( 2) ( 1) = 2 3 > 0 z = 120 40 40 = 40 (40, 40, 40) n = 2 m = 1 Apunts de Matemàtiques II: Optimització i Anàlisi Dinàmica 9 IDEES CLAU Un programa d'optimització amb igualtats busca extrems sobre el conjunt factible determinat per les restriccions.

El vector gradient d'una funció escalar és perpendicular a la recta tangent de la corba de nivell corresponent. En el mètode gràfic, l'òptim es localitza en el punt de tangència entre la corba de restricció i una corba de nivell. En el punt de tangència, els gradients de la funció objectiu i de la restricció són proporcionals: . El mètode directe només és recomanable amb restriccions lineals fàcilment aïllables. COMPROVA EL QUE HAS APRÈS 4. Per què el vector gradient de la funció objectiu i el de la restricció han de ser proporcionals en l'òptim gràfic? 5. Quin inconvenient principal presenta el mètode directe o de substitució davant restriccions no lineals?

OPTIMITZACIÓ AMB RESTRICCIONS D'IGUALTAT 2 Mètode de Lagrange i condicions d'optimalitat EN ACABAR SABRÀS Formular correctament la funció de Lagrange associada a un programa d'optimització amb restriccions d'igualtat. Determinar els punts crítics del programa mitjançant la resolució del sistema de derivades primeres. Construir la matriu hessiana associada a les variables instrumentals i determinar el subespai tangent. Classificar rigorosament els extrems relatius condicionats avaluant el signe de la forma quadràtica restringida. PENSA-HI ABANS DE LLEGIR 6 Per què no podem descartar que un punt crític sigui un màxim si la seva matriu hessiana és indefinida a tot l'espai?

f = λ g Apunts de Matemàtiques II: Optimització i Anàlisi Dinàmica 10 Fonament i formulació de la funció de Lagrange Quan un problema d'optimització presenta restriccions d'igualtat no lineals o un nombre elevat de variables, el mètode directe de substitució (vegeu «Optimització amb restriccions d'igualtat — Fonaments i mètodes gràfic i directe») esdevé impracticable. En aquests escenaris s'aplica el mètode dels multiplicadors de Lagrange, el qual transforma un problema d'optimització condicionada en un problema operativament anàleg a un d'optimització lliure mitjançant una funció auxiliar.

DEFINICIÓ Considerem un programa general amb variables instrumentals i restriccions d'igualtat ( ): La funció de Lagrange o lagrangiana associada al programa és la funció escalar de variables definida com: Les noves variables auxiliars reben el nom de multiplicadors de Lagrange. Aquesta expressió incorpora directament el compliment de les restriccions dins la funció objectiu ponderades per cada coeficient .

EXEMPLE Volem plantejar la lagrangiana del següent programa amb dues restriccions d'igualtat ( ): Com que tenim dues restriccions, introduïm dos multiplicadors de Lagrange, i : COMPROVA-HO 7 Quantes variables té la funció de Lagrange d'un programa amb 4 variables instrumentals i 2 restriccions d'igualtat? Condició necessària de primer ordre: punts crítics Per identificar els candidats a extrems relatius d'un programa condicionat cal establir una condició necessària. Suposem que la funció objectiu i les funcions de restricció són de classe (tenen derivades parcials segones contínues). n m m < n Optimitzar z = f(x , … , x ) 1 n s.a g (x , … , x ) = b , i = 1, … , m i 1 n i 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 λ i m = 2 max f(x, y, z) = xy + 2xz + yz s.a { x + y + z = 6 x y = 1 λ 1 λ 2 L(x, y, z, λ , λ ) = 1 2 (xy + 2xz + yz) λ (x + 1 y + z 6) λ (x 2 y 1) f g i C2 Apunts de Matemàtiques II: Optimització i Anàlisi Dinàmica 11 DEFINICIÓ Un punt crític restringit o punt estacionari és qualsevol punt que anul·la simultàniament totes les derivades parcials de primer ordre de la lagrangiana.

Segons el teorema de la condició necessària de primer ordre, si un punt interior és un extrem del programa, han d'existir multiplicadors que verifiquin el sistema homogeni del gradient: Les últimes equacions garanteixen estrictament que el punt sigui un punt factible per al problema inicial. EXEMPLE Calculem els punts crítics de la funció . Igualem les primeres derivades a zero: Sumant la primera i la segona equació s'obté , d'on . Igualant aquest resultat a la tercera equació ( ): Combinant aquesta relació amb les dues restriccions ( i ), obtenim el sistema lineal que condueix a la solució única: Així doncs, hem determinat l'únic punt crític d'aquest programa.

COMPROVA-HO 8 Per què la condició necessària de primer ordre reprodueix exactament les restriccions originals del programa? (x , λ ) = 0 0 (x , … , x , λ , … , λ ) 1 0 n 0 1 0 m 0 x = 0 (x , … , x ) 1 0 n 0 m λ = 0 (λ , … , λ ) 1 0 m 0 (x , λ ) x j L 0 0 (x , λ ) λ i L 0 0 = 0, j = 1, … , n = (g (x ) b ) = 0, i = 1, …

, m i 0 i m L(x, y, z, λ , λ ) = 1 2 xy + 2xz + yz λ (x + 1 y + z 6) λ (x 2 y 1) x L y L z L λ 1 L λ 2 L = y + 2z λ λ = 0 1 2 = x + z λ + λ = 0 1 2 = 2x + y λ = 0 1 = (x + y + z 6) = 0 = (x y 1) = 0 x + y + 3z 2λ = 1 0 λ = 1 2 x+y+3z λ = 1 2x + y = 2 x + y + 3z 2x + y 3x + y 3z = 0 x + y + z = 6 x y = 1 (x, y, z) = , , , λ = ( 5 11 5 6 5 13 ) 1 , λ = 5 28 2 5 4 Apunts de Matemàtiques II: Optimització i Anàlisi Dinàmica 12 La matriu hessiana restringida i les condicions de segon ordre Un cop localitzats els punts crítics, cal determinar si corresponen a màxims, mínims o punts d'inflexió. La classificació requereix analitzar les derivades segones de la funció de Lagrange.

DEFINICIÓ La matriu hessiana restringida respecte a les variables instrumentals, denotada com o , és la matriu simètrica d'ordre formada exclusivament per les segones derivades parcials respecte a les variables de decisió : Per avaluar l'òptim, no cal que la matriu sigui definida sobre tot l'espai .

L'estudi del signe es limita a les direccions factibles al voltant del punt, és a dir, sobre el subespai tangent definit pels gradients de les restriccions anul·lats: La condició suficient de segon ordre classifica el punt crític mitjançant la forma quadràtica associada : Signe de per a tot Classificació del punt crític Definida positiva ( ) Mínim relatiu condicionat Definida negativa ( ) Màxim relatiu condicionat ERROR FREQÜENT Un error greu habitual és calcular els menors principals de la matriu hessiana i concloure que el punt no és ni màxim ni mínim si resulta indefinida a tot .

La matriu hessiana sovint és indefinida globalment; el caràcter d'extrem depèn exclusivament del signe de la forma quadràtica restringida als vectors del subespai tangent . H L(x, λ) x H L(x, λ) x …x 1 n n × n x , … , x 1 n H L(x, λ) = x x 1 2 L 2 x x 2 1 L 2 x x n 1 L 2 x x 1 2 L 2 x 2 2 L 2 x x n 2 L 2 … … … x x 1 n L 2 x x 2 n L 2 x n 2 L 2 H L x Rn T = v R g (x ) v = 0, i = 1, … , m { n i 0 } x0 Q(v) = v t H L(x , λ ) x 0 0 v Q(v) v T {0} x0 Q(v) > 0 Q(v) < 0 H L x Rn T Apunts de Matemàtiques II: Optimització i Anàlisi Dinàmica 13 PROCÉS Procediment d'optimització pel mètode de Lagrange EXEMPLE Classifiquem el punt crític de l'exemple anterior.

La matriu hessiana respecte a les variables instrumentals és: Aquesta matriu és indefinida sobre (té zeros a la diagonal principal i determinant no nul). Trobem el subespai tangent calculant els gradients de les restriccions i : D'aquest sistema lineal homogeni deduïm immediatament que i . Per tant, els vectors no nuls del subespai tangent són de la forma amb . Avaluem la forma quadràtica sobre aquests vectors: Com que per a qualsevol , la forma quadràtica és definida negativa sobre el subespai tangent. Per tant, el punt crític és un màxim relatiu condicionat.

Formulació de la lagrangiana Construir L restant les restriccions ponderades per lambda a l'objectiu 1 Sistema de primer ordre Anul·lar les derivades parcials respecte a x i lambda per trobar punts crítics 2 Càlcul de la hessiana Construir la matriu de derivades segones respecte a les variables instrumentals 3 Subespai tangent Determinar les direccions factibles que anul·len els gradients de les restriccions 4 Classificació de l'òptim Avaluar el signe de la forma quadràtica sobre el subespai tangent 5 , , ( 5 11 5 6 5 13 ) H L = xyz 0 1 2 1 0 1 2 1 0 R3 g (x, y, z) = 1 x + y + z g (x, y, z) = 2 x y g = (1, 1, 1) 1 g = (1, 1, 0) 2 v + v + v = 0 1 2 3 v v = 0 1 2 v = 2 v 1 v = 3 2v 1 v = (v , v , 2v ) 1 1 1 t v = 1 0 Q(v) = (v 1 v 1 2v 1) 0 1 2 1 0 1 2 1 0 v 1 v 1 2v 1 = = 3v v 6v = 10v (v 1 v 1 2v 1) 3v 1 v 1 3v 1 1 2 1 2 1 2 1 2 10v < 1 2 0 v = 1 0 Apunts de Matemàtiques II: Optimització i Anàlisi Dinàmica 14 COMPROVA-HO 9 Si una matriu hessiana H_x L és indefinida a R^n, pot correspondre a un màxim relatiu condicionat?

IDEES CLAU La funció de Lagrange sintetitza la funció objectiu i les restriccions d'igualtat mitjançant multiplicadors auxiliars. Els punts crítics restringits s'obtenen anul·lant el gradient complet de la funció de Lagrange respecte a totes les seves variables. La matriu hessiana restringida només conté les derivades parcials segones preses respecte a les variables instrumentals. La condició suficient de segon ordre requereix avaluar la curvatura exclusivament sobre el subespai tangent definit per les restriccions. El signe de la forma quadràtica sobre el subespai tangent determina si el punt crític és un màxim relatiu (negativa) o un mínim relatiu (positiva). COMPROVA EL QUE HAS APRÈS 10.

Com es defineix formalment el subespai tangent en què cal analitzar la matriu hessiana? 11. Quin paper compleixen les derivades parcials de la lagrangiana respecte als multiplicadors en el sistema de primer ordre? OPTIMITZACIÓ AMB RESTRICCIONS D'IGUALTAT 3 Interpretació econòmica i aplicacions EN ACABAR SABRÀS Calcular la variació aproximada del valor extrem davant pertorbacions en les constants de restricció mitjançant els preus ombra. Interpretar el signe del multiplicador de Lagrange per avaluar la conveniència d'ampliar o reduir recursos en decisions empresarials. Formular i analitzar el model de carteres de Markovitz aplicant la sensibilitat marginal del risc respecte al rendiment.

PENSA-HI ABANS DE LLEGIR 12 Si una fàbrica vol augmentar la seva quota de producció en una sola unitat, cal resoldre de nou tot el problema per conèixer el sobrecost? λ i Apunts de Matemàtiques II: Optimització i Anàlisi Dinàmica 15 Sensibilitat del valor òptim i preus ombra En els problemes d'optimització condicionada, les constants de restricció representen sovint límits de recursos disponibles, quotes de producció o pressupostos fixos. Quan aquests paràmetres canvien lleugerament, el valor òptim del programa experimenta una variació sense necessitat de resoldre de nou tot el sistema d'equacions.

Considerem el programa general d'optimització amb restriccions d'igualtat formulat mitjançant la funció de Lagrange (vegeu «Optimització amb restriccions d'igualtat — Mètode de Lagrange i condicions d'optimalitat»): Si el vector constitueix l'òptim del programa i n'és el valor extrem associat, una petita alteració en la constant de la -èsima restricció genera una modificació aproximada en el valor objectiu: DEFINICIÓ: PREU OMBRA Els multiplicadors de Lagrange mesuren la sensibilitat del valor extrem respecte a pertorbacions marginals en els recursos o requeriments del sistema. Per aquesta raó, en la teoria econòmica reben el nom de preus ombra.

Aquest càlcul permet quantificar l'impacte immediat d'una unitat addicional de recurs sobre el resultat final (cost mínim o benefici màxim). PROCÉS Avaluació econòmica d'una variació marginal 1 Pertorbació de la restricció Modificació del terme independent en una quantitat petita Δb. 2 Multiplicador de Lagrange Identificació del preu ombra λ associat a la restricció. 3 Aproximació marginal Càlcul de l'impacte estimat mitjançant el producte λ · Δb. 4 Decisió empresarial Determinació de la viabilitat financera segons el signe i magnitud. COMPROVA-HO 13 Si el multiplicador associat a una restricció de pressupost val 3,5, quant variarà el benefici màxim en incrementar el pressupost en 2 unitats?

Interpretació del signe del multiplicador de Lagrange El signe de dicta com respon l'objectiu en augmentar o disminuir la capacitat del recurs : L(x , … , x , λ , … , λ ) = 1 n 1 m f(x , … , x ) 1 n λ i=1 m i (g (x , … , x ) i 1 n b ) i (x , … , x ) 1 0 n 0 z = 0 f(x , … , x ) 1 0 n 0 Δb i i Δz 0 λ i 0 Δb i λ i 0 b i Apunts de Matemàtiques II: Optimització i Anàlisi Dinàmica 16 Signe del multiplicador Variació de la restricció ( ) Comportament del valor òptim ( ) Avaluació de la decisió empresarial Augmenta ( ) Disminueix ( ) Augmenta ( ) Disminueix ( ) En maximització de beneficis, ampliar el recurs resulta favorable. En minimització de costos, incrementar el requisit encareix el procés.

Augmenta ( ) Disminueix ( ) Disminueix ( ) Augmenta ( ) L'ampliació del terme independent redueix el valor final. Augmenta o disminueix Es manté constant ( ) El recurs no és limitant a nivell marginal; modificar-lo no altera l'òptim assolit. ERROR FREQÜENT Confondre la variació del valor de la funció ( ) amb el desplaçament de les coordenades del punt òptim ( ). L'aproximació marginal prediu exclusivament el canvi en el resultat final assolit (el cost o el benefici), mai la nova combinació exacta d'inputs o quantitats que cal fabricar.

Vegem la decisió de producció d'una empresa que vol minimitzar els costos totals d'operació sota una quota de fabricació: EXEMPLE: AMPLIACIÓ DE PRODUCCIÓ INDUSTRIAL Suposem que es resol el programa de minimització de costos: El punt crític restringit s'obté a amb un multiplicador i un cost mínim de 64 u.m. Si la direcció planteja fabricar una unitat més ( ): Com que , fabricar una unitat addicional encarirà el cost mínim en unes 2 u.m. Per tant, no és rendible augmentar el volum exigit a menys que l'ingrés obtingut per la venda superi aquest cost marginal addicional.

COMPROVA-HO 14 En un problema de mínim cost, si el multiplicador de Lagrange d'una restricció val zero, què passa si s'exigeix una unitat menys d'aquest requeriment? Δb i z 0 λ > i 0 0 Δb > i 0 Δb < i 0 Δz > 0 0 Δz < 0 0 λ < i 0 0 Δb > i 0 Δb < i 0 Δz < 0 0 Δz > 0 0 λ = i 0 0 Δz 0 0 Δz 0 Δx i 0 Δz 0 λ i 0 Δb i min C = 2x + 8y s.a 4x y = 0,5 0,5 32 (x, y) = (16, 4) λ = 2 Δb = 1 ΔC λ Δb = 2 1 = 2 u.m. λ = 2 > 0 Apunts de Matemàtiques II: Optimització i Anàlisi Dinàmica 17 Model de carteres d'inversió de Markovitz Una aplicació financera fonamental és la construcció de carteres eficients proposada per Harry Markowitz.

L'objectiu consisteix a minimitzar el risc global de la cartera (mesurat a través de la variància o dispersió dels rendiments) subjecte a assolir un determinat nivell prefixat de rendibilitat esperada. EXEMPLE: SELECCIÓ DE CARTERA DE DOS ACTIUS Considerem dos títols financers amb rendibilitats esperades del 18 % i del 14 %. Designem per i les proporcions invertides en cadascun. El risc total de la cartera respon a l'expressió: Fixem l'exigència d'aconseguir una rendibilitat mitjana del 15 %: COMPROVA-HO 15 Per què la variància d'una cartera creix quan s'exigeix una rendibilitat més gran si λ > 0?

Aplicacions a la producció, el benefici i el condicionament de superfícies La sensibilitat marginal intervé directament en la planificació empresarial d'articles conjunts i en l'assignació d'instal·lacions de superfícies: x y σ(x, y) = 0,0016x + 2 0,0004y 2 0,00096xy min σ(x, y) s.a 0,18x + 0,14y = 0,15 Plantejament lagrangià: . 1 L(x, y, λ) = 0,0016x + 2 0,0004y 2 0,00096xy λ(0,18x + 0,14y 0,15) Càlcul de condicions de primer ordre: 2 = x L 0,0032x 0,00096y 0,18λ = 0 = y L 0,0008y 0,00096x 0,14λ = 0 = λ L (0,18x + 0,14y 0,15) = 0 Resolució del sistema: S'obté la composició òptima (30,47 % en el primer títol) i (67,96 % en el segon títol), amb un multiplicador i una variància mínima de .

3 x 0,3047 y 0,6796 λ 0,00179 σ = 1,345 10 4 Anàlisi de sensibilitat davant un increment de rendibilitat: Si es desitja elevar la rendibilitat objectiu al 15,5 %, la variació de la fita és . L'increment aproximat del risc serà: 4 Δb = 0,5% = 0,005 Δσ λ Δb = 0,00179 0,005 8,95 10 6 Apunts de Matemàtiques II: Optimització i Anàlisi Dinàmica 18 EXEMPLE: RESTRICCIÓ EN EL VOLUM DE FABRICACIÓ Una empresa comercialitza dos articles i amb funció de costos totals . Si la capacitat tècnica limita la producció total a 100 articles ( ), l'assignació òptima és de 81 unitats de i 19 unitats de , generant un benefici màxim de 129.220 u.m. En aquest punt, el multiplicador val aproximadament 1.100.

En conseqüència, poder produir una unitat addicional ( ) incrementaria els beneficis globals en unes 1.100 u.m. EXEMPLE: DISTRIBUCIÓ DE PAVIMENTS EN INSTAL·LACIONS Una signatura instal·la mosaic ( ), moqueta ( ) i parquet ( ), amb marges respectius de 2.000, 2.400 i 2.800 u.m./m², subjectes a la condició física . El màxim benefici s'aconsegueix col·locant 25 m² de mosaic, 30 m² de moqueta i 55 m² de parquet, assolint 276.000 u.m. amb . Si la restricció es redueix a , tenim . El guany diari patirà una reculada estimada de: IDEES CLAU El multiplicador de Lagrange quantifica la taxa marginal de variació del valor extrem davant canvis en les constants de restricció.

L'aproximació bàsica de sensibilitat s'expressa mitjançant la relació lineal . Els multiplicadors actuen com a preus ombra que reflecteixen la valoració interna dels recursos escassos o límits tècnics. El signe positiu, negatiu o nul de assenyala si incrementar la fita augmenta, redueix o manté invariable el valor òptim. En el model de Markovitz, el paràmetre mesura el cost en unitats de risc associat a demanar una rendibilitat esperada més exigent. COMPROVA EL QUE HAS APRÈS 16. Com s'aproxima la variació del valor òptim davant un canvi en la constant de restricció? 17. Què representa econòmicament un preu ombra? 18.

Si en minimitzar costos s'obté un multiplicador per a una quota de 32 unitats, com afecta fabricar 33 unitats? A B C(x, y) = 5x + 2 10y + 2 50000 x + y = 100 A B Δb = 1 x y z x + 2 y + 2 70z = 5375 λ = 40 x + 2 y + 2 70z = 5374 Δb = 1 Δz 0 λ Δb = 40 ( 1) = 40 u.m. Δz 0 λ i 0 Δb i λ i 0 λ λ = 2 Apunts de Matemàtiques II: Optimització i Anàlisi Dinàmica 19 Test Encercla la resposta correcta. Les solucions són al final. 19. Quina és la relació geomètrica entre el gradient d'una funció i la seva corba de nivell? 20. Com es defineix el conjunt factible d'un programa d'optimització? 21. Quin és l'òptim del programa de minimitzar 2x + 8y amb .5 .5 = 32? 22.

Quan és especialment aconsellable utilitzar el mètode de resolució directe? 23. Com es construeix la funció de Lagrange associada a un programa? 24. Quines dimensions té la matriu hessiana d'un programa amb n variables i m restriccions? 25. Sobre quin domini s'avalua el signe de la hessiana per classificar un punt crític? 26.

Si la forma quadràtica restringida al subespai tangent és definida positiva, el punt crític és: Depèn del signe de les variables a) Són estrictament paral·lels b) Són perpendiculars entre ells c) Tenen un angle de 45 graus d) Punts que satisfan totes les restriccions a) Domini complet de la funció objectiu b) Punts on el gradient s'anul·la c) Regió on la funció és sempre positiva d) 4x0 y0 (4, 16) a) (32, 2) b) (8, 8) c) (16, 4) d) Amb restriccions lineals fàcils d'aïllar a) Amb funcions objectiu discontínues b) Quan les restriccions són hipèrboles c) Sempre que hi hagi més de tres restriccions d) Multiplicant la funció objectiu per cadascuna de les restriccions a) Dividint el gradient de l'objectiu entre el gradient de les restriccions b) Restant a l'objectiu les restriccions multiplicades pels seus multiplicadors c) Sumant les restriccions multiplicades per cada variable instrumental d) Ordre (n + m) x (n + m) a) Ordre m x m b) Ordre n x n c) Ordre m x n d) Exclusivament sobre el subespai tangent a les restriccions a) Únicament sobre el vector format pels multiplicadors b) Sobre tot l'espai vectorial Rn c) Sobre el conjunt de punts on la funció objectiu s'anul·la d) Un màxim relatiu condicionat a) Un mínim relatiu condicionat b) Un punt de sella no factible c) Un punt no concloent d) Apunts de Matemàtiques II: Optimització i Anàlisi Dinàmica 20 27.

Quin concepte econòmic mesura directament el valor del multiplicador de Lagrange en un òptim? 28. Si λ = 0 en una restricció, com varia el valor òptim davant una petita ampliació de b? 29. A què fa referència exactament l'aproximació Δz λ · Δb en una empresa? 30. En el model de Markovitz, què s'optimitza per a un llindar determinat de rendibilitat esperada? 4 Optimització amb restriccions de desigualtat — Formes canòniques i mètode gràfic EN ACABAR SABRÀS Transformar qualsevol programa d'optimització amb desigualtats en la seva forma canònica equivalent. Construir gràficament la regió factible identificant semiplans, polígons convexos i vèrtexs.

Trobar la solució òptima d'un model mitjançant corbes de nivell i la direcció del vector gradient. Classificar les restriccions d'un problema en saturades o no saturades en el punt d'òptim. PENSA-HI ABANS DE LLEGIR 31 Per què en una planificació empresarial d'estoc o maquinària no sempre convé utilitzar el 100% dels recursos disponibles? En molts contextos de gestió i presa de decisions, la utilització dels recursos disponibles no és imperativa sinó limitativa: l'empresa pot consumir una part dels seus mitjans o la totalitat d'aquests, sense superar un llindar determinat.

A diferència dels problemes tractats amb restriccions d'igualtat, la El preu ombra del recurs a) El preu de venda al consumidor b) El cost fix amortitzat de producció c) L'elasticitat de la corba de demanda d) Disminueix de manera sobtada a zero a) Augmenta en proporció al cub del terme b) Es duplica automàticament c) No experimenta cap variació apreciable d) Al nombre exacte de treballadors a contractar a) Al canvi en el valor de la funció objectiu b) A la taxa d'interès del mercat de deute c) A les noves quantitats d'inputs de l'òptim d) Es minimitza la taxa de dividend cobrat a) Es minimitza el risc o variància b) Es maximitza el volum d'accions emeses c) Es maximitza el deute acumulat d) Apunts de Matemàtiques II: Optimització i Anàlisi Dinàmica 21 introducció de desigualtats permet reflectir situacions reals en què no cal exhaurir les hores de maquinària, el pressupost o les matèries primeres.

ESQUEMA Optimització amb desigualtats Formulació general i formes canòniques Un problema d'optimització condicionat per desigualtats cerca extremar una funció objectiu escalar sotmesa a un conjunt de límits que defineixen una regió admissible o conjunt factible (vegeu «Optimització amb restriccions d'igualtat — Fonaments i mètodes gràfic i directe»). En aquest entorn, els models es classifiquen en funció del sentit de l'optimització i de les desigualtats associades.

DEFINICIÓ Un programa canònic d'optimització amb desigualtats adopta de manera estàndard una de les dues estructures següents: Forma canònica de màxim: totes les restriccions tecnològiques són del tipus «menor o igual»: Forma canònica de mínim: totes les restriccions tecnològiques són del tipus «major o igual»: On és la funció objectiu, són les variables instrumentals o de decisió, representen les funcions de restricció i són els termes constants. Qualsevol model formulat amb sentits de desigualtat no homogenis o sentits d'optimització oposats es pot transformar en un programa equivalent. Dos programes són equivalents si comparteixen el mateix conjunt de solucions òptimes.

Formulació canònica Estructura estàndard de màxims i mínims Transformació d'equivalència Canvis de signe de funció i restriccions Geometria factible Intersecció de semiplans i polígons convexos Compacitat i Weierstrass Garantia d'existència de solucions finites Mètode gràfic Desplaçament de nivell i gradient Classificació de restriccions Diferenciació entre saturades i folgances max s.a z = f(x , … , x ) 1 n g (x , … , x ) b , i = 1, … , m i 1 n i min s.a z = f(x , … , x ) 1 n g (x , … , x ) b , i = 1, … , m i 1 n i A R n f R x , …

, x 1 n g : A i R b i Apunts de Matemàtiques II: Optimització i Anàlisi Dinàmica 22 Element a transformar Operació algebraica Efecte obtingut Objectiu: canvi de màxim a mínim Multiplicar la funció per -1 Restricció: canvi de sentit de desigualtat Multiplicar ambdós membres per -1 EXEMPLE Considerem el programa de maximització: Per expressar-lo en forma canònica de mínim, canviem el signe de la funció objectiu i homogeneïtzem les restriccions al sentit : La primera restricció es multiplica per -1, obtenint . La segona ja compleix el sentit requerit.

El programa canònic equivalent resulta: COMPROVA-HO 32 Quina transformació s'ha d'aplicar a la restricció 4x - 2y 10 per integrar-la en un programa canònic de mínim? Geometria del conjunt factible: semiplans i polígons convexos En el pla , cada restricció lineal de desigualtat defineix una recta frontera que divideix el pla en dos semiplans. El conjunt factible és la intersecció dels semiplans que compleixen simultàniament totes les restriccions del problema, incloent-hi les condicions de no-negativitat de les variables ( ). Quan la intersecció d'aquests semiplans delimita una regió tancada per segments de recta, es genera un polígon convex.

Els punts d'encreuament entre les rectes de restricció que formen la frontera de constitueixen els seus vèrtexs o punts extrems. maxf(x) min[ f(x)] g (x) i b i g (x) i b i max s.a u = 27z x 3y 2 2 x y + z 0 y x 1 max u min( u) = x + 2 3y 2 27z x y + z 0 y x z 0 min s.a ( u) = x + 3y 27z 2 2 y x z 0 y x 1 R2 B x 0, y 0 B Apunts de Matemàtiques II: Optimització i Anàlisi Dinàmica 23 Gràfica del polígon convex factible delimitat per restriccions lineals i eixos. Per determinar analíticament les coordenades d'aquests vèrtexs, es resolen els sistemes lineals formats per les equacions de les rectes que s'intersequen a cada cantonada del polígon.

Tipologia de solucions: òptims finits i infinits Dins de l'anàlisi de resolució, un programa pot presentar diferents comportaments segons les propietats topològiques del conjunt factible i la naturalesa de la funció objectiu: Òptim finit (o solució acotada): existeix un punt factible que maximitza o minimitza la funció sobre el domini admès. El valor de la funció en aquest punt rep el nom de valor òptim. Òptim infinit (o solució no acotada): la funció objectiu creix (en maximització) o decreix (en minimització) indefinidament sense trobar cap cota finita dins del conjunt factible.

L'existència d'un extrem global està garantida si es compleixen les condicions establertes pel teorema de Weierstrass: tota funció contínua definida sobre un conjunt compacte (tancat i acotat) assoleix tant un màxim com un mínim globals sobre aquest conjunt. Apunts de Matemàtiques II: Optimització i Anàlisi Dinàmica 24 Esquema d'acotació del conjunt factible mitjançant una bola oberta. Un polígon factible és tancat perquè conté tota la seva frontera poligonal (les desigualtats són no estrictes, o ). És acotat si és possible inscriure'l completament a l'interior d'una bola oberta centrada en un punt de radi finit .

Si les funcions de beneficis o costos associades són contínues, la compacitat del domini garanteix l'existència d'una solució finita. ERROR FREQÜENT Un error molt habitual és assumir que qualsevol regió no acotada manca necessàriament de solució òptima. Encara que el conjunt factible sigui infinit cap a una direcció, si el vector gradient de la funció empeny cap a una frontera tancada del polígon, el programa pot assolir perfectament un òptim finit. COMPROVA-HO 33 Quines dues propietats geomètriques ha de complir el conjunt factible per assegurar, via teorema de Weierstrass, l'existència d'òptims finits en funcions contínues?

Mètode gràfic: corbes de nivell i vectors gradient Per a problemes amb dues variables de decisió, el mètode gràfic permet identificar la solució sense necessitat de procediments algebraics complexos. Aquest enfocament es basa en la representació conjunta del polígon factible i de la família de corbes de nivell de la funció objectiu. El vector gradient té una propietat fonamental: és perpendicular a la recta tangent a la corba de nivell que passa pel punt avaluat i assenyala la direcció i sentit de màxim creixement de la funció. r c k f(x, y) Apunts de Matemàtiques II: Optimització i Anàlisi Dinàmica 25 Gràfica de corbes de nivell i vectors gradient sobre el polígon.

El procediment per determinar l'òptim mitjançant desplaçament gràfic segueix aquests passos: Dibuixar amb precisió el conjunt factible a partir de les rectes de restricció i els eixos de coordenades. 1 B Traçar una corba de nivell testimoni per a un valor arbitrari de la constant . 2 f(x, y) = k k Calcular el vector gradient en un punt d'aquesta corba per conèixer el sentit de creixement de la funció. 3 Desplaçar la corba de nivell de forma paral·lela en el sentit del gradient si es maximitza, o en sentit oposat si es minimitza. 4 Localitzar l'últim punt (o punts) del conjunt factible que està en contacte amb la corba de nivell abans de sortir completament de la regió admissible.

5 B Apunts de Matemàtiques II: Optimització i Anàlisi Dinàmica 26 PROCÉS Procediment de resolució gràfica Restriccions saturades i restriccions amb folgança Un aspecte determinant de la solució òptima és l'anàlisi de l'estat en què queden els recursos disponibles. DEFINICIÓ Una restricció de desigualtat (o ) es diu saturada o activa en un punt si aquest punt compleix la condició amb igualtat estricta, és a dir, . Si pel contrari es compleix amb desigualtat estricta ( o ), la restricció és no saturada o presenta folgança. L'existència de saturació té una clara interpretació: indica que el recurs associat s'ha esgotat totalment en el pla de producció o consum òptim.

Quan un recurs presenta folgança, en sobra una quantitat que no ha estat necessària per assolir l'objectiu màxim.

Dibuixar regió factible Intersecar rectes de restricció en el pla 1 Traçar corba de nivell Dibuixar f(x, y) = k per a un valor testimoni 2 Calcular gradient Identificar el sentit de creixement perpendicular 3 Desplaçar corba Avançar paral·lelament fins a l'últim punt de contacte 4 Identificar òptim Determinar coordenades i comprovar saturació de recursos 5 g (x) i b i g (x) i b i x g (x ) = i b i g (x ) < i b i g (x ) > i b i Apunts de Matemàtiques II: Optimització i Anàlisi Dinàmica 27 EXEMPLE Considerem un procés productiu amb dues restriccions tècniques de temps en minuts: i , amb .

Si la funció de beneficis és lineal, , el desplaçament de les rectes de nivell condueix a l'òptim en el vèrtex . Avaluant les restriccions en aquest punt: Tots dos recursos s'exhaureixen completament en l'òptim. El valor màxim de benefici és unitats monetàries. Si la funció d'ingressos és no lineal, expressada per la circumferència , el punt òptim de màxim benefici s'assoleix per tangència a la coordenada amb un benefici de unitats monetàries. Comprovant les restriccions: En aquest cas, l'òptim només satura la primera restricció. COMPROVA-HO 34 Què significa econòmicament que una restricció de matèria primera de tipus no estigui saturada en el punt d'òptim benefici?

IDEES CLAU Els programes amb restriccions de desigualtat modelen situacions en què l'exhauriment complet dels recursos no és obligatori. La forma canònica exigeix que totes les desigualtats tinguin el mateix sentit: per a problemes de màxim i per a problemes de mínim. Un programa es converteix en equivalent canviant el signe de la funció objectiu ( ) o multiplicant les restriccions per -1. El teorema de Weierstrass garanteix l'existència de solucions finites sempre que la funció sigui contínua i el conjunt factible sigui compacte (tancat i acotat). El vector gradient indica la direcció de màxim creixement i és perpendicular a la tangent de la corba de nivell en cada punt.

Una restricció està saturada o activa en l'òptim si es compleix amb igualtat estricta, representant el consum íntegre del recurs. 6x + 10y 600 9x + 3y 720 x, y 0 z = 25x + 30y (75, 15) 6(75) + 10(15) = 450 + 150 = 600 (primera restricci saturada) o ˊ 9(75) + 3(15) = 675 + 45 = 720 (segona restricci saturada) o ˊ z = 25(75) + 30(15) = 2325 z = 9825 0,5(x 100) 2 0,5(y 102)2 (55, 27) k = 6000 6(55) + 10(27) = 330 + 270 = 600 (saturada) 9(55) + 3(27) = 495 + 81 = 576 < 720 (no saturada, hi ha folgan a de 144 minuts) ç max f = min[ f] Apunts de Matemàtiques II: Optimització i Anàlisi Dinàmica 28 COMPROVA EL QUE HAS APRÈS 35.

Com s'obté un programa canònic de màxim equivalent a partir d'un problema de minimització amb restriccions ? 36. Com s'identifica gràficament el punt de màxim d'una funció sobre una regió poligonal? 37. En què es diferencia un punt d'òptim que satura dues restriccions d'un que només en satura una? Test Encercla la resposta correcta. Les solucions són al final. 38. Com és el vector gradient respecte a la recta tangent de la corba de nivell? 39. Quan es considera saturada una restricció de desigualtat en el punt òptim? 40. Quin requisit garanteix segons Weierstrass l'existència d'òptim finit per a una funció contínua? 41.

Per convertir un problema de mínim en forma canònica de màxim cal: g(x) b Forma un angle de 45 graus a) Perpendicular a la recta tangent b) Té la mateixa direcció que la recta c) Paral·lel a la recta tangent d) Quan el valor de la funció és zero a) Quan el punt és interior al polígon b) Quan presenta folgança estrictament positiva c) Quan es compleix amb igualtat estricta d) Fronteres formades per nombres enters a) Conjunt factible convex i obert b) Conjunt factible tancat i acotat c) Funció objectiu exclusivament lineal d) Dividir la funció objectiu per dos a) Multiplicar la funció per -1 b) Canviar el signe de les variables c) Invertir els coeficients tecnològics d) Apunts de Matemàtiques II: Optimització i Anàlisi Dinàmica 29 5 Teorema fonamental i resolució gràfica EN ACABAR SABRÀS Expressar un programa lineal canònic en la seva notació matricial estàndard identificant la matriu tecnològica.

Aplicar el teorema fonamental de la programació lineal per localitzar els òptims globals en els vèrtexs. Resoldre programes lineals de dues variables mitjançant el càlcul i avaluació analítica dels vèrtexs. Identificar i interpretar geomètricament els casos de solucions òptimes múltiples i programes no acotats. PENSA-HI ABANS DE LLEGIR 42 Si una funció objectiu lineal no té cap curvatura, per què sabem amb certesa que el màxim s'assolirà a la vora de la regió factible i no en un punt interior? Estructura del programa lineal canònic La programació lineal estudia problemes d'optimització on tant la funció objectiu com les restriccions funcionals són combinacions lineals de primer grau.

Quan totes les restriccions presenten el mateix sentit de desigualtat i s'afegeixen condicions de no-negativitat per a cadascuna de les variables, el model rep el nom de programa lineal canònic. Programació lineal 5 Teorema fonamental i resolució gràfica 6 Models econòmics d'assignació, transport i dieta Apunts de Matemàtiques II: Optimització i Anàlisi Dinàmica 30 DEFINICIÓ Un programa canònic lineal adopta formalment una de les dues modalitats duals següents: amb coeficients . Les condicions s'anomenen restriccions de no-negativitat de les variables de decisió.

Aquestes condicions garanteixen que les magnituds econòmiques associades, com ara la producció física, el consum de recursos o la inversió financera, mantinguin un sentit coherent en el món real.

En forma compacta o matricial, aquests models s'escriuen definint el vector de costos o beneficis , el vector d'incògnites , el vector de termes independents o disponibilitats i la matriu tecnològica , que agrupa els coeficients de consum per unitat d'activitat: EXEMPLE Considerem el programa de producció següent: La seva expressió matricial s'obté identificant els vectors i matrius següents: COMPROVA-HO 43 Quina condició sobre el sentit de les desigualtats han de complir les restriccions funcionals en la forma canònica de maximització?

Teorema fonamental de la programació lineal El conjunt factible determinat per les restriccions d'un programa lineal és una regió convexa definida per la intersecció de semiespais: un polígon en el pla bidimensional, un políedre en l'espai tridimensional o un polítop en dimensions superiors (vegeu «Optimització amb restriccions de desigualtat — Formes canòniques i mètode gràfic»). Forma de maximitzaci : o ˊ 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 x , … , x 0 1 n Forma de minimitzaci : o ˊ minz = 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 x , …

, x 0 1 n c , a , b j ij i R x j 0 c x b A max z = s.a A , c t x x b x 0 minz = s.a A , c t x x b x 0 max s.a z = 25x + 30y 6x + 10y 600 9x + 3y 720 x, y 0 = c , = ( 25 30 ) x , A = ( x y ) , = ( 6 9 10 3 ) b , = ( 600 720 ) 0 ( 0 0 ) Apunts de Matemàtiques II: Optimització i Anàlisi Dinàmica 31 PER RECORDAR-HO El teorema fonamental de la programació lineal estableix dues propietats fonamentals per a qualsevol programa lineal: Aquest teorema localitza els punts candidats a solució òptima, però no garanteix per si sol que un programa lineal tingui solució finita, ja que la regió podria ser no acotada i permetre que la funció objectiu creixi o decreixi sense límit.

Per garantir l'existència d'un òptim finit cal introduir la condició de compacitat geomètrica: DEFINICIÓ Un programa lineal és acotat si el seu conjunt factible associat és un conjunt acotat a l'espai euclidià. Com que les restriccions lineals defineixen un conjunt tancat, un programa lineal acotat té sempre un conjunt factible compacte. Com a conseqüència directa, un programa lineal acotat té sempre solució òptima finita en almenys un dels vèrtexs del polígon o políedre factible. Esquema del polígon factible i la localització del seu vèrtex extrem.

A diferència dels problemes d'optimització no lineal, on la curvatura de les corbes de nivell pot situar els punts òptims a l'interior d'una aresta o cara sense tocar cap vèrtex, la linealitat de obliga que el màxim o mínim absolut s'assoleixi sempre en un extrem geomètric de la regió. Tot programa lineal que admeti una solució finita té necessàriament un òptim global situat en un dels vèrtexs (o punts extrems) del seu conjunt factible. 1 Si dos vèrtexs contigus resulten ser òptims globals finits amb el mateix valor de la funció objectiu, aleshores qualsevol punt del segment que els uneix és també un òptim global.

2 z Apunts de Matemàtiques II: Optimització i Anàlisi Dinàmica 32 ERROR FREQÜENT Assumir que un programa lineal sempre assoleix l'òptim en un únic punt vèrtex. Si la funció objectiu té el mateix pendent que una de les restriccions actives que delimiten la regió factible, existiran infinits punts òptims repartits al llarg de tot el segment que uneix dos vèrtexs contigus. COMPROVA-HO 44 Quina diferència hi ha entre la posició dels òptims en un problema lineal i en un problema no lineal?

Mètode algebraic-geomètric de resolució i avaluació de vèrtexs Per resoldre gràficament un programa lineal de dues variables amb conjunt factible acotat, se segueix un procediment seqüencial d'avaluació en vèrtexs: PROCÉS Mètode d'avaluació de vèrtexs en programació lineal Alternativament, es pot analitzar l'evolució de les rectes de nivell de la funció objectiu, desplaçant- les en la direcció de creixement o decreixement fins a abandonar la regió factible. Representar gràficament les rectes límit associades a cadascuna de les desigualtats del problema. 1 Determinar el conjunt factible verificant la intersecció dels semiplans permesos i el primer quadrant definit per .

2 B x 0, y 0 Calcular analíticament les coordenades de tots els vèrtexs de la regió resolent els sistemes d'equacions lineals lineals formats per les rectes que s'intersequen en cadascun d'ells. 3 Avaluar el valor numèric de la funció objectiu a cadascun dels vèrtexs determinats. 4 z Seleccionar com a màxim el valor més gran obtingut, o com a mínim el valor més petit.

5 Traçar restriccions Dibuixar les rectes frontera de cada desigualtat 1 Determinar regió factible Identificar el polígon d'intersecció i no-negativitat 2 Calcular els vèrtexs Resoldre els sistemes d'equacions lineals d'encreuament 3 Avaluar la funció z Substituir les coordenades de cada vèrtex a z 4 Identificar l'òptim Triar el vèrtex amb valor extrem (o segment) 5 c k Apunts de Matemàtiques II: Optimització i Anàlisi Dinàmica 33 Gràfica de les rectes de nivell assolint l'òptim al vèrtex (75,15).

Quan tracem les rectes de nivell sobre el polígon factible amb vèrtexs , , i , observem com el nivell passa successivament per , , i culmina al punt extrem amb el benefici màxim de 2325 unitats monetàries. En aquest punt òptim es produeix la saturació simultània de la primera i la segona restricció de capacitat tecnològica. Aquesta situació contrasta clarament amb els problemes no lineals sobre el mateix conjunt , tal com es mostra a la figura següent: Gràfica de corbes de nivell no lineals tangents a l'aresta (55,27).

B (0,0) (0,60) (75,15) (80,0) c = 0 0 c = 1800 1800 c = 2000 2000 (75,15) B Apunts de Matemàtiques II: Optimització i Anàlisi Dinàmica 34 Quan la funció objectiu és estrictament no lineal (com ara ), les corbes de nivell adopten forma circular. En aquest context no lineal, el punt de tangència que maximitza la funció és amb un valor de , situat sobre l'aresta i saturant exclusivament la primera restricció, sense coincidir amb cap vèrtex del polígon. COMPROVA-HO 45 Per què és suficient avaluar només els vèrtexs del conjunt factible si aquest és acotat?

Casos particulars: arestes òptimes i programes no acotats Durant el procés d'avaluació de vèrtexs i de línies de nivell, poden sorgir dues configuracions estructurals particulars: 1. Solucions òptimes alternatives sobre segments Si dues solucions extremes contigües assoleixen exactament el mateix valor òptim, la recta de nivell de la funció objectiu és estrictament paral·lela a l'aresta que les connecta. Per tant, el programa lineal presenta òptims alternatius, i qualsevol punt sobre el segment que uneix aquests dos vèrtexs satisfà les condicions d'optimalitat.

EXEMPLE Analitzem el programa lineal sobre el conjunt factible acotat : Determinem els vèrtexs del polígon factible calculant les interseccions corresponents: , , , i . A continuació, avaluem el valor de en cadascun d'aquests punts extrems: Vèrtex Avaluació de Valor resultant Tipus de punt 9 Mínim global (extrem 1) 9 Mínim global (extrem 2) 23 Punt ordinari 37 Punt ordinari 44 Màxim global únic Com que representa el valor mínim de la funció, deduïm que el mínim global és qualsevol punt del segment d'extrems i . Per la seva banda, el màxim global finit és únic i s'assoleix al vèrtex amb un valor de 44.

z = 0,5x 2 0,5y + 2 100x + 102y 337 (55,27) k = 6000 B Optimitzar s.a z = 7x + 14y 5 x + 3y 9 2x + y 8 x + 2y 2 x 0, y 0 (0,1) (2,0) (4,0) (3,2) (0,3) z (x, y) z = 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 (0,1) (2,0) (3,2) Apunts de Matemàtiques II: Optimització i Anàlisi Dinàmica 35 2. Programes no acotats i absència de solució finita Quan la regió factible no és fitada en la direcció cap a on millora la funció objectiu, les rectes de nivell poden avançar indefinidament sense abandonar mai l'interior del conjunt.

En aquests supòsits, el programa lineal no té solució finita, ja que la funció objectiu pot créixer sense límit (en problemes de maximització) o decréixer indefinidament (en problemes de minimització). COMPROVA-HO 46 Com es detecta analíticament que tota una aresta és un conjunt d'òptims globals? IDEES CLAU Un programa lineal canònic exigeix que totes les restriccions funcionals tinguin el mateix sentit de desigualtat i que les variables de decisió compleixin la condició de no-negativitat. El teorema fonamental de la programació lineal garanteix que qualsevol solució òptima finita s'ubica necessàriament en un vèrtex del conjunt factible.

Si dos vèrtexs contigus comparteixen el valor òptim global, tots els punts del segment que els uneix són també solucions òptimes. Un programa lineal acotat compta sempre amb com a mínim una solució òptima finita. Si la regió factible és no fitada en el sentit de millora de la funció objectiu, el problema no té solució finita. COMPROVA EL QUE HAS APRÈS 47. En què consisteix la condició necessària per poder afirmar l'existència assegurada d'un òptim finit en un programa lineal? 48. Si per a la funció s'obté i com a valor mínim sobre un polígon acotat, quina és la solució òptima?

PROGRAMACIÓ LINEAL 6 Models econòmics d'assignació, transport i dieta EN ACABAR SABRÀS Formular analíticament problemes reals de producció, transport i dieta en forma de programes lineals. Identificar les variables de decisió, les restriccions funcionals i el sentit d'optimització de cada model econòmic. Interpretar solucions numèriques i reconèixer quan una restricció és saturada o activa. z = 7x + 14y 5 z(0,1) = 9 z(2,0) = 9 Apunts de Matemàtiques II: Optimització i Anàlisi Dinàmica 36 PENSA-HI ABANS DE LLEGIR 49 Com pot una empresa trobar la millor combinació d'enviaments entre diversos magatzems i botigues si hi ha desenes de rutes possibles amb costos diferents?

Model de planificació de la producció El problema clàssic de planificació productiva busca determinar la quantitat exacta de diferents béns que una empresa ha de manufacturar per maximitzar el benefici net global, respectant el límit de recursos disponibles. Considerem una organització que fabrica productes diferents a partir de recursos productius (com matèries primeres, hores d'operari o capacitat de maquinària). Definim els paràmetres tecnològics i econòmics bàsics: : coeficient tecnològic que indica la quantitat del recurs necessària per elaborar una unitat del bé . : disponibilitat màxima existent del recurs .

: marge unitari d'utilitat o guany aportat per la venda d'una unitat del producte . : variable instrumental de decisió que representa el volum de producció del bé . Com que l'empresa no pot utilitzar més recursos dels que té en estoc, l'ús conjunt de cada factor productiu no superarà la seva disponibilitat. Així, la quantitat total consumida del factor és , generant inequacions de tipus menor o igual.

El programa lineal canònic (vegeu «Programació lineal — Teorema fonamental i resolució gràfica») de planificació de la producció s'expressa de la forma següent: n m a ij 0 i j b i 0 i c j 0 j x j 0 j i a x + i1 1 + a x in n max s.a z = c x + + c x 1 1 n n a x + + a x b 11 1 1n n 1 a x + + a x b m1 1 mn n m x , … , x 0 1 n Apunts de Matemàtiques II: Optimització i Anàlisi Dinàmica 37 EXEMPLE Un fabricant produeix dos articles, P i Q, utilitzant ferro, fusta i plàstic.

Els requeriments per unitat i les existències totals disponibles es recullen a continuació: Material P Q Disponibilitat 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) Cada unitat de P genera un marge de 22 u.m., cada unitat de Q genera 18 u.m. i les despeses administratives fixes són de 100.000 u.m. Assignant a la quantitat de P i a la quantitat de Q, plantegem: El conjunt factible resulta acotat i tancat. Avaluant la funció d'objectiu en els vèrtexs del polígon factible: u.m. u.m. u.m. u.m. u.m. El valor òptim absolut correspon a fabricar…