Apunts de Matemàtiques Empresarials III. Gonzalo Rodríguez Pérez


Save this PDF as:
 WORD  PNG  TXT  JPG

Tamaño: px
Comenzar la demostración a partir de la página:

Download "Apunts de Matemàtiques Empresarials III. Gonzalo Rodríguez Pérez"

Transcripción

1 Apunts de Matemàtiques Empresarials III Gonzalo Rodríguez Pérez

2 2

3 Índex 1 Programació no lineal 5 LescondicionsdeKuhn-Tucker 11 Programacióconvexa 14 Interpretació econòmica dels multiplicadors de Kuhn-Tucker 22 Exercicis 24 2 Programació lineal 31 L algorismedelsímplex:fonamentsmatemàtics 36 Modelseconòmicsdelaprogramaciólineal 51 Model de planificaciódelaproducció 51 Modeldeladieta 53 Modeldeltransport 55 Model input-output de Leontieff 56 Programaciólinealdual 57 Anàlisi de sensibilitat de la programació lineal 61 Exercicis 67 3 Equacions diferencials ordinàries 77 EDOdeprimerordre 81 EDOdevariablesseparades 82 EDOdevariablesseparables 83 EDOlinealsdeprimerordre 86 EDO de Bernouilli 88 EDO lineals d ordre superior a coeficients constants 91 Resolució de l EDO lineal d ordre superior homogènia 91 Resolució de l EDO lineal d ordre superior completa 93 Exercicis 97 4 Equacions en diferències finites 13 Funcionsdiscretesioperadorsdiscrets 15 Equacions en diferències finites 19 EDFlinealsdeprimerordre 11 EDF lineals de primer ordre a coeficients constants 116 EDF lineals d ordre superior a coeficients constants 12 3

4 4 ÍNDEX Exercicis 125 A El teorema fonamental de la programació convexa 129 B El teorema fonamental de la programació lineal 133 C Anàlisi qualitativa d una EDO de primer ordre 137 D Les EDF i la teoria del caos 141

5 Capítol 1 Programació no lineal En els darrers cinquanta anys, l augment de l escala i la complexitat de les organitzacions humanes ha portat com a conseqüència un augment en el nombre i la dificultat dels problemes derivats de la seva direcció i estratègia Amb l objectiu d ajudar a la resolució d aquests problemes, apareix al final de la Segona Guerra Mundial l anomenada recerca operacional i la programació matemàtica n és un dels seus instruments fonamentals En concret, la programació matemàtica té a veure amb aquelles situacions (processos industrials, tàctiques i estratègies militars, assumptes econòmics, etc) en què cal optimitzar (maximitzar o minimitzar) certes quantitats subjectes a diferentes restriccions Pensem, per exemple, en un empresari que vol maximitzar el seu benefici; és obvi que en la recerca d aquest benefici òptim haurà de tenir en compte com a restriccions la quantitat de maquinària que cal emprar, el nombre de treballadors o el capital monetari que cal invertir entre d altres En el camp econòmic i empresarial, és un lloc comú afirmar que l optimització permet assignar de manera eficient recursos escasos entre activitats alternatives Doncs bé, quan aquesta assignació la du a terme un únic subjecte decisori i els recursos són limitats ens trobem enfront de l optimització restringida o condicionada; si, a més, no estem obligats a emprar totes les disponibilitats associades als recursos, l optimització ho serà restringida per desigualtats Aquest fet reflecteix acuradament moltes de les circumstàncies sota les quals es desenvolupa l activitat econòmica Històricament, la programació no lineal no s inicia com a disciplina matemàtica fins el 1951 amb els treballs dehwkuhniawtucker,encaraqueelpreminobelhmarkowitz 5

6 6 Programació no lineal donà a conèixer una mica abans el seu model de selecció d inversions que passa per la resolució d un programa no lineal En aquest primer capítol estudiem els programes d optimització restringida per desigualtats no lineals i destaquem, sobre tot, les condicions necessàries de Kuhn-Tucker i la seva aplicació com a mètode de resolució efectiu per a programes convexos Començarem amb un exemple senzill de programa no lineal Exemple 1 Un empresari produeix i ven dos productes, A i B El procés productiu preveu tres fases de manera que una unitat de A necessita un temps de permanència en cadascuna d élles de 3, 6 i 5 hores, respectivament, mentre que una unitat de B necessita 6, 4 i 5 hores Si les disponibilitats horàries màximes de les tres fases són, en aquest ordre, de 54, 48 i 5 hores, plantegeu el programa d optimització que ens determina la producció de A i B que maximitza els ingressos generats per la seva venda, suposant que els seus preus de venda unitaris són p 1 =25 5x 1 i p 2 =3 2x 2, en què x 1 és el nombre d unitats produïdes i venudes de A, i x 2 el de B És evident que, sota aquestes hipòtesis, la funció d ingressos totals que cal maximitzar és z = f (x 1,x 2 )=p 1 x 1 + p 2 x 2 =25x 1 +3x 2 5x 2 1 2x 2 2 Segons l enunciat, les quantitats que cal produir estan subjectes a tres restriccions temporals Notem que el temps per unitat emprat en a- quests processos no depèn del nombre d unitats produïdes Com que 3x 1 +6x 1 és el temps que la primera fase necessita per a manipular x 1 unitats de A i x 2 unitats de B, la primera d aquestes restriccions s expressa formalment a partir de la desigualtat 3x 1 +6x 2 54, ja que 54 hores és el temps màxim disponible per a aquesta fase De manera anàloga, les altres dues desigualtats que afecten el temps emprat per la segona i la tercera fases serien 6x 1 +4x 2 48 i 5x 1 +5x 2 5 Així doncs, la solució del problema passa per determinar l òptim (màxim) x = x 1 x 2

7 Programació no lineal 7 de la funció d ingressos totals f (x 1,x 2 ) que satisfà les cinc desigualtats 3x 1 +6x 2 54, 6x 1 +4x 2 48, 5x 1 +5x 2 5, x 1 i x 2 El que cal, en definitiva, és resoldre el programa canònic d optimització restringida per desigualtats max z =3x 1 +2x 2 5x 2 1 2x 2 2 sota 3x 1 +6x x 1 +4x x 1 +5x 2 5 x 1,x 2 Notem que aquest programa no és lineal ja que la funció d ingressos totals no ho és En general, doncs, un programa canònic d òptims restringits per desigualtats és un problema d optimització de la forma max z = f (x 1,,x n ) min z = f (x 1,,x n ) sota g 1 (x 1,,x n ) b 1 sota g 1 (x 1,,x n ) b 1 g m (x 1,,x n ) b m x 1,,x n on la funció escalar o f : A R n R g m (x 1,,x n ) b m x 1,,x n és la funció objectiu, lesn variables x 1,,x n són les variables instrumentals, les m funcions escalars g 1,,g m : A R n R són les funcions de restricció ilesm constants b 1,,b m són les constants de restricció del programa És evident que tot programa canònic es pot expressar de manera abreujada en la forma en què x = x 1 x n max sota, g = z = f (x) g (x) b x n g 1 g m min z = f (x) o sota g (x) b, b = b 1 b m x n i n =,, R n

8 8 Programació no lineal El programa d òptims restringits per desigualtats de l exemple anterior és canònic ja que es tracta d un programa de màxim, amb tres restriccions de menor o igual i dues variables instrumentals x 1 i x 2 positives En aquest cas, la funció objectiu del programa és z = f (x) =f (x 1,x 2 )=3x 1 +2x 2 5x 2 1 2x 2 2 la funció vectorial de restricció i el vector de restricció són g (x) = g 1 (x) g 2 (x) = 3x 1 +6x 2 6x 1 +4x 2 i b = b 1 b 2 = g 3 (x) 5x 1 +5x 2 b 3 5 Notem que hi han dos tipus de restricció en un programa canònic: les m restriccions de caràcter instrumental i les n restriccions de positivitat de les variables instrumentals L important en la formulació canònica és el sentit de les desigualtats instrumentals: de menor o igual per a un programa de màxim, i de més gran o igual per a un de mínim En general, però, no tots els programes són canònics Tanmateix, tot programa no canònic es pot transformar en canònic seguint una sèrie de passos Vegem-ne un exemple Exemple 2 Suposem que, per raons d eficiència empresarial, el temps disponible per a la tercera fase en la producció de A i de B s ha d esgotar Sota aquesta nova hipòtesi determineu el nou programa canònic que maximitza els ingressos totals generats per la seva venda En aquest cas el nou programa que optimitza els ingressos seria max z =3x 1 +2x 2 5x 2 1 2x 2 2 sota 3x 1 +6x x 1 +4x x 1 +5x 2 =5 x 1,x 2 Com podem veure, aquest programa no és canònic ja que la tercera restricció és una igualtat Si volem obtenir un programa canònic equivalent a aquest hem de substituir la igualtat per les dues desigualtats associades Fent-ho així ens queda max z =3x 1 +2x 2 5x 2 1 2x 2 2 sota 3x 1 +6x x 1 +4x x 1 +5x 2 5 5x 1 +5x 2 5 x 1,x 2

9 Programació no lineal 9 i si canviem el sentit de la quarta desigualtat s obté, al final, el programa canònic max z =3x 1 +2x 2 5x 2 1 2x 2 2 sota 3x 1 +6x x 1 +4x x 1 +5x 2 5 5x 1 5x 2 5 x 1,x 2 Des d ara emprarem el qualificatiu de programa per referir-nos a un programa d òptims restringits per desigualtats sigui o no canònic; si cal fer la distinció, ho indicarem explícitament L objectiu que ens proposem és resoldre una bona part d aquests programes, és a dir, trobar els òptims (màxims o mínims) de la funció objectiu que estan sotmesos a les restriccions de desigualtat associades Iniciarem l estudi recordant un parell de resultats clàssics sobre l existència i la qualificació dels òptims de les funcions escalars Teorema 3 (Weierstrass) Tota funció escalar contínua definida sobre un compacte (tancat i acotat) de R n admet màxims i mínims globals Teorema 4 (Local-global) Si una funció escalar f (x) és convexa (còncava) sobre un subconjunt S de R n convex aleshores tot mínim (màxim) de f (x) sobre S és global, i si f (x) és estrictament convexa (còncava) el mínim (màxim) és únic A més, el conjunt format pels mínims (màxims) de f (x) és convex Enfront d un programa cal tenir en compte en primer lloc el conjunt de punts determinat precisament per les restriccions de desigualtat associades Anomenem conjunt factible d un programa el conjunt format pels punts del domini de la funció objectiu que satisfan les desigualtats associades Els elements del conjunt factible s anomenen punts factibles del programa Si un programa té punts factibles s anomena programa factible i, en cas contrari, infactible Enelnostrecas, elcon- junt factible associat al programa de l exemple introductori és el recinte de R 2 definit per ½ (x 1,x 2 ) R 2 : 3x 1 +6x 2 54, 6x 1 +4x 2 48, 5x 1 +5x 2 5, x 1,x 2 Així doncs, els òptims d un programa restringit per desigualtats són, en particular, punts factibles Això ens diu que, en general, aquests òptims no coincideixen amb els òptims lliures que la funció objectiu ¾

10 1 Programació no lineal pugui tenir Arribats a aquest punt és necessari fer la distinció següent en la definició d òptim d un programa En general, un òptim finit o acotat d un programa max sota és un punt factible z = f (x) g (x) b x n x = min z = f (x) o sota g (x) b x 1 x n R n x n que optimitza localment o globalment la funció objectiu sobre el conjunt factible associat En aquest cas, el valor que pren la funció objectiu en x, és a dir, z = f (x )=f x 1,,xn, és el valor òptim del programa en x Així mateix, diem que l òptim finit x satura la restricció i-èsima del programa quan g i x 1,,x n = bi Per contra, si la funció objectiu s optimitza indefinidament sobre el conjunt factible diem que el programa té un òptim infinit o no acotat En aquest cas el valor òptim és infinit Exemple 5 Determineu gràficament el conjunt factible associat al programa max z =3x 1 +2x 2 5x 2 1 2x 2 2 sota 3x 1 +6x x 1 +4x x 1 +5x 2 5 x 1,x 2 iproveu,almateixtemps,quetéunúnicmàximglobal Com que el conjunt factible associat a aquest programa és un subconjunt de R 2 podem representar-lo gràficament En aquest cas tenim

11 Programació no lineal 11 Deduïm, per tant, que el programa és factible Una simple inspecció visual ens permet afirmar que aquest conjunt és compacte i convex Així doncs, aplicant el teorema de Weierstrass, tenim que aquest programa té màxim global ja que la funció d ingressos totals a maximitzar, z = f (x 1,x 2 )=3x 1 +2x 2 5x 2 1 2x 2 2, és contínua Com que, en particular, aquesta funció és estrictament còncava 1 deduïm (aplicant el teorema local-global) que aquest màxim global és únic Hem raonat que el programa de l exemple econòmic inicial és factible i té un únic òptim finit global, però no sabem quin és Val a dir que les matemàtiques ens proporcionen mètodes formals de resolució que ens ajuden a determinar, de manera pràcticament mecànica, els òptims d una gran majoria de programes L associat a les condicions necessàries de Kuhn-Tucker que estudiem a continuació n és un Les condicions de Kuhn-Tucker El mètode de resolució de programes relacionat amb les condicions necessàries de Kuhn-Tucker requereix, entre d altres, que les funcions objectiu i de restriccions siguin de tipus C 2 sobre el seu domini de definició, és a dir, que admetin funcions derivades parcials segones contínues 2 Aquestes condicions són similars a l anul lació del vector gradientdelafunciódelagrangeperaòptimsrestringitsperigualtats Teorema 6 (Kuhn-Tucker) Si el punt x = x 1 x n R n és un òptim d un programa canònic de màxim max z = f (x 1,,x n ) sota g 1 (x 1,,x n ) b 1 g m (x 1,,x n ) b m x 1,,x n 1 Ho provem més endavant 2 En general, una funció escalar és de tipus C k si totes les seves funcions derivades parcials d ordre k són contínues

12 12 Programació no lineal amb funció objectiu f i funcions de restricció g 1,,g m de tipus C 2 sobre un domini obert de R n, existeix necessàriament un vector λ = de manera que 3 1 f (x ) mx µ λ gi (x ) i x j x i=1 j à f (x ) mx 2 λ i x j x j i=1 λ 1 λ m µ gi (x ) 3 g i (x ) b i, per a tot i =1,,m 4 x j, per a tot j =1,,n R m, per a tot j =1,,n 5 (g i (x ) b i ) λ i =, per a tot i =1,,m 6 λ i, per a tot i =1,,m! x j =, per a tot j =1,,n El vector λ = λ 1 R m λ m és el vector dels multiplicadors de Kuhn-Tucker λ 1,,λ m associats a l òptim x Notem, per exemple, que la tercera i la quarta condicions ens diuen que l òptim x és un punt factible del programa de màxim Malauradament, aquestes condicions són, en general, necessàries però no pas suficients; en altres paraules, que poden haver-hi punts que les satisfacin sense ser òptims (poden donar-se molts exemples en aquest sentit) Com a cas il lustratiu trobarem les sis condicions de Kuhn- Tucker del programa de l exemple 1 Exemple 7 Determineu les condicions de Kuhn-Tucker associades al programa max z =3x 1 +2x 2 5x 2 1 2x 2 2 sota 3x 1 +6x x 1 +4x x 1 +5x 2 5 x 1,x 2 3 Si el programa canònic fos de mínim, tindríem el mateix canviant el sentit de les desigualtats que apareixen en la primera i la tercera de les condicions del teorema

13 Programació no lineal 13 Com que el gradient de la funció objectiu és µ z z =, z =(3 x 1, 2 4x 2 ) x 1 x 2 i la matriu jacobiana de les restriccions és g 1 g 1 Jg = g x 1 x 2 1 g 2 g 2 g 2 = = , g x 3 1 x g 3 g 3 x 1 x 2 deduïm que les sis condicions de Kuhn-Tucker expressades per a un punt qualsevol (x 1,x 2 ), amb multiplicadors λ 1,λ 2 i λ 3 associats, són z 3X µ gi λ i =(3 x 1 ) (3λ 1 +6λ 2 +5λ 3 ) x 1 x i=1 1 1 z 3X µ gi λ i =(2 4x 2 ) (6λ 1 +4λ 2 +5λ 3 ) x 2 x i=1 2 Ã z 3X µ! gi λ i x 1 = x 1 x i=1 1 =(3 2 Ã x 1 3λ 1 6λ 2 5λ 3 ) x 1 = z 3X µ! gi λ i x 2 = x 2 x i=1 2 =(2 4x 2 6λ 1 4λ 2 5λ 3 ) x 2 = 3x 1 +6x x 1 +4x x 1 +5x 2 5 ½ x x 2 (3x 1 +6x 2 54) λ 1 = (6x 1 +4x 2 48) λ 2 = (5x 1 +5x 2 5) λ 3 = λ 1 λ 2 λ 3

14 14 Programació no lineal L estudi de les condicions suficients d optimalitat restringida per desigualtats és força complicat i no el farem El que sí que veurem, però, és el cas de la programació convexa en què les condicions necessàries de Kuhn-Tucker són també suficients L interès per aquests tipus de programes rau en les seves aplicacions econòmiques Programació convexa Sota certes hipòtesis de convexitat, les sis condicions necessàries de Kuhn-Tucker ens determinen tots els òptims dels programes Donarem, en primer lloc, la definició de programa convex i enunciarem, tot seguit, el teorema fonamental de la programació convexa 4 Diem que un programa de mínim (màxim) és convex si les funcions de restricció són convexes i, a més, la funció objectiu és convexa (còncava) o estrictament convexa (estrictament còncava) sobre el conjunt factible associat El programa de l exemple 1, max z =3x 1 +2x 2 5x 2 1 2x 2 2 sota 3x 1 +6x x 1 +4x x 1 +5x 2 5 x 1,x 2, és un programa convex ja que les tres funcions de restricció, per ser formes lineals, són convexes, 5 i la funció objectiu z =3x 1 +2x 2 5x 2 1 2x 2 2 és estrictament còncava ja que les matrius hessianes que hi té associades són iguals a la matriu µ 1 Hz (x 1,x 2 )= 4 queésdefinida negativa 6 Teorema 8 (Programació convexa) Tot punt que satisfà les sis condicions de Kuhn-Tucker associades a un programa canònic convex, amb funció objectiu i funcions de restricció de tipus C 2 sobre un domini obert i convex, és un òptim global del programa 4 Demostrem aquest teorema en l apèndix A 5 Les formes lineals són, alhora, funcions còncaves i convexes 6 Vegeu el teorema de caracterització de les funcions escalars convexes i/o còncaves que enunciem en l apèndix A

15 Programació no lineal 15 Exemple 9 Trobeu l òptim del programa max z =3x 1 +2x 2 5x 2 1 2x 2 2 sota 3x 1 +6x x 1 +4x x 1 +5x 2 5 x 1,x 2 aplicant el teorema anterior Com que el programa és convex, tot punt que satisfaci les sis condicions de Kuhn-Tucker serà automàticament un màxim global Recordem que, per a un punt (x 1,x 2 ) qualsevol amb multiplicadors λ 1,λ 2 i λ 3 associats, aquestes condicions eren 1 ½ 3 x1 3λ 1 6λ 2 5λ 3 2 4x 2 6λ 1 4λ 2 5λ ½ (3 x1 3λ 1 6λ 2 5λ 3 ) x 1 = (2 4x 2 6λ 1 4λ 2 5λ 3 ) x 2 = 3x 1 +6x x 1 +4x x 1 +5x 2 5 ½ x1 x 2 (3x 1 +6x 2 54) λ 1 = (6x 1 +4x 2 48) λ 2 = (5x 1 +5x 2 5) λ 3 = λ 1 λ 2 λ 3 Una manera d abordar el problema és veure, per exemple, si existeix algun punt (x 1,x 2 ) que les satisfà amb els tres multiplicadors de Kuhn- Tucker associats diferents de zero Així doncs, si (a) λ 1,λ 2,λ 3 6= deduïm, per la condició (5), el sistema d equacions lineals 3x 1 +6x 2 =54 6x 1 +4x 2 =48 5x 1 +5x 2 =5

16 16 Programació no lineal que és incompatible Per tant, un dels multiplicadors de Kuhn-Tucker, com a mínim, ha de ser necessàriament zero Suposem, per exemple, que (b) λ 1 = i λ 2,λ 3 6= En aquest cas, i de nou per la condició (5), s obté el sistema de Cramer ½ 6x1 +4x 2 =48 5x 1 +5x 2 =5, amb solució x 1 =4 i x 2 =6 Finalment, tenint en compte que els valors de les variables instrumentals obtinguts són diferents de zero, s arriba, aplicant la condició (2), al sistema de Cramer 6λ 2 +5λ 3 =26 4λ 2 +5λ 3 =176 Es pot comprovar fàcilment que el punt x 1,x 2 =(4, 6), ¾, amb solució λ 2 =42 i λ 3 =16 amb el vector de multiplicadors de Kuhn-Tucker associat λ 1,λ 2,λ3 =(, 42, 16) satisfà les sis condicions anteriors Conseqüentment, (4, 6) és l únic màxim global del programa Així doncs, cal produir i vendre 4 unitats de A i6unitatsdeb per maximitzar els ingressos totals El valor òptim d aquests ingressos serà de En particular, i com que z = z (4, 6) = 2248 u m 3x 1 +6x 2 =48< 54, 6x 1 +4x 2 =48 i 5x 1 +5x 2 =5, deduïm que, produint al nivell òptim, resten sis hores sense utilitzar en la primera fase i que s esgota el temps disponible per les altres dues, és a dir, que l òptim satura les restriccions associades a la segona i tercera fases Una aplicació important de la programació convexa la trobem en la resolució dels programes quadràtics Aquests programes solen aparèixer en molts models d optimització econòmica Diem que un programa és quadràtic si les funcions de restricció són formes lineals i la funció

17 Programació no lineal 17 objectiu s obté com a suma d una forma quadràtica i una forma lineal, ésadir,siésdelaforma nx f(x 1,,x n )= a ij x i x j + i,j=1 nx a i x i i=1 Com podem comprovar, el programa convex que acabem de resoldre és quadràtic ja que les tres restriccions instrumentals són formes lineals i la funció objectiu s obté com a suma de la forma lineal i la forma quadràtica f 1 (x 1,x 2 )=3x 1 +2x 2 f 2 (x 1,x 2 )= 5x 2 1 2x 2 2 El teorema següent ens diu quan un programa quadràtic és convex Teorema 1 (Programació quadràtica) Si a 11 a 1n A = a n1 a nn és la matriu associada a la forma quadràtica que apareix en la funció objectiu d un programa quadràtic de màxim (mínim) aleshores aquest programa és convex si, i només si, la matriu A és definidaosemidefinida negativa (positiva) Fixem-nos que la convexitat d un programa quadràtic depèn tan sols del signe de la forma quadràtica que hi apareix Vegem-ne una aplicació econòmica El model de selecció d inversions de Markowitz Suposem que volem invertir un cert capital monetari en la compra de n títols que cotitzen en Borsa sota la hipòtesi que la rendibilitat anual del títol i-èsim ve estimada per una variable aleatòria R i coneguda En conseqüència, si x i indica el tant per cent del capital destinat a la compra dels títols i-èsims, la rendibilitat total de la inversió vindrà donada per la variable aleatòria R = nx x i R i i=1

18 18 Programació no lineal Per tant, podem considerar com la rendibilitat total de la cartera l esperança de R, nx E (R) = a i x i, on a i denota l esperança de R i, i com a risc associat la variància Var(R) = i=1 a i = E (R i ), nx a ij x i x j, i,j=1 on a ij representalacovariànciader i ider j, a ij = Cov (R i,r j )=E (R i R j ) E (R i ) E (R j ) El model de selecció d inversions de Markowitz donat pel programa de mínim np min a ij x i x j i,j=1 np sota a i x i E i=1 np x i =1 i=1 x 1,, x n ens determina els tants per cent de la cartera destinats a la compra dels n títols que fan mínim el risc de la inversió de manera que la rendibilitat esperada sigui superior o igual a un cert valor prefixat E Pot provar-se que el programa quadràtic canònic equivalent np min a ij x i x j i,j=1 np sota a i x i E i=1 np x i 1 i=1 np x i 1 i=1 x 1,, x n és sempre convex Així doncs, tot punt que satisfaci les sis condicions de Kuhn-Tucker associades és un òptim global del programa Exemple 11 Suposem que tenim una cartera de renda variable de dos títols amb una rendibilitat mitjana anual respectiva del 18 % i del 14

19 Programació no lineal 19 %, i amb un risc esperat del 16 % i del 4 % Si la covariància dels dos títols és del 48 %, determineu els tants per cent a invertir en cada títol si es vol minimitzar el risc de la inversió amb una rendibilitat mínima del 15 % Com que la matriu de variancies i covariàncies dels dos títols és µ el risc esperat de la cartera serà V = µ (x 1,x 2 ) 48 4 = 16x x x 1 x 2 µ x1 = x 2 Per tant, el programa canònic associat al model de selecció d inversions de Markowitz que cal resoldre és min V =16x x x 1 x 2 sota 18x 1 +14x 2 15 x 1 + x 2 1 x 1 x 2 1 x 1,x 2 onlesvariablesinstrumentalsindiquenelstantspercentdelacartera que cal invertir en cada títol Aquest programa quadràtic és convex ja que la forma quadràtica V és definida positiva Per tant, tot punt que satisfaci les condicions de Kuhn-Tucker serà l òptim global que busquem Com que el gradient de V és µ V V =, V =(32x 1 96x 2, 8x 2 96x 1 ) x 1 x 2 i la matriu jacobiana de les restriccions és g 1 g 1 x 1 x 2 µ g1 g 2 g 2 Jg = = = g 2 x 1 x 2 g 3 g 3 x 1 x , 1 1 deduïm que les sis condicions de Kuhn-Tucker per a un punt (x 1,x 2 ) qualsevol, amb multiplicadors λ 1 i λ 2 associats, són

20 2 Programació no lineal V 3X µ gi λ i = x 1 x i=1 1 =32x x 2 18λ 1 λ 2 + λ 3 V 3X µ gi λ i = x 2 x i=1 2 = 96x 1 +8x 2 14λ 1 λ 2 + λ 3 Ã V 3X µ! gi λ i x 1 = x 1 x i=1 1 =(32x 2 Ã 1 96x 2 18λ 1 λ 2 + λ 3 ) x 1 = V 3X µ! gi λ i x 2 = x 2 x i=1 2 =( 96x 1 +8x 2 14λ 1 λ 2 + λ 3 ) x 2 = 18x 1 +14x x 1 + x 2 1 x 1 x 2 1 ½ x1 4 x (18x 1 +14x 2 15) λ 1 = (x 1 + x 2 1) λ 2 = ( x 1 x 2 +1) λ 3 = λ 1 λ 2 λ 3 Veurem que existeix un punt que satisfà aquestes sis condicions amb multiplicadors de Kuhn-Tucker associats λ 1 = λ 3 = i λ 2 6= D entrada, i per la segona desigualtat de la condició (5), tenim que x 1 + x 2 =1 En aquest punt cal obrir una discussió paral lela respecte els valors de x 1 idex 2 Si (a) x 1 = aleshores, per la igualtat anterior, x 2 =1

21 Programació no lineal 21 que no satisfà la segona desigualtat de la condició (3), ja que 18x 1 +14x 2 =14 < 15 En canvi, si (b) x 2 = aleshores x 1 =1 d on, aplicant la primera de les igualtats de la condició (2), deduïm que λ 2 =32 Tanmateix, aquests valors de x 1,x 2,λ 1,λ 2 i λ 3 no satisfan la segona de les desigualtats de la condició (1) ja que 96x 1 +8x 2 14λ 1 λ 2 + λ 3 = 416 Finalment, si (c) x 1,x 2 6= tindríem, per la condició (2) de nou, les equacions lineals ½ 96x1 +8x 2 λ 2 = 32x 1 96x 2 λ 2 = que, juntament amb l equació inicial x 1 + x 2 =1 formen un sistema de Cramer amb solució x 1 = 11 37, x 2 = i λ 2 = És trivial comprovar que aquests valors, amb λ 1 i λ 3 iguals a zero, satisfan les sis condicions de Kuhn-Tucker En altres paraules, l òptim del programa és el punt µ 11 (x 1,x 2)= 37, 26, amb µ λ 37 1,λ 2,λ 32 3 =, , Així doncs, cal invertir un x 1 = =2973 % de la cartera en títols del primer tipus i un x 2 = =727 % en el segon, amb un risc mínim esperat del V =138 % En aquest cas, la rendibilitat òptima esperada de la cartera serà superior al 15 % prefixat ja que 18x 1 +14x 2 =152 %

22 22 Programació no lineal Interpretació econòmica dels multiplicadors de Kuhn-Tucker És evident que l òptim i el valor òptim de la funció objectiu d un programa depèn, en darrera instància, de les constants de restricció La interpretació econòmica dels multiplicadors de Kuhn-Tucker ens diu que les variacions que es produeixen en el valor òptim de la funció objectiu són gairebé proporcionals a les variacions de les constants de restricció, actuant els multiplicadors de Kuhn-Tucker com a constants de proporcionalitat En altres paraules, i donat un programa canònic que satisfà les hipòtesis del teorema de Kuhn-Tucker, es pot demostrar que si la i-èsima constant de restricció b i varia lleugerament, la variació 4z que es produeix en el valor òptim de la funció objectiu és aproximadament igual al producte 4z ' λ i 4b i on 4b i és l increment que experimenta b i i λ i és l i-èsim multiplicador de Kuhn-Tucker associat a l òptim Veurem quines conseqüències econòmiques poden desprendre s d aquest fet Per assentar idees suposem que tenim un programa canònic de màxim associat a un procés productiu de n bens econòmics a partir de m recursos productius de manera que la variable x j denota la quantitat produïda del bé j-èsim, la constant b i és la disponibilitat màxima del recurs i-èsim i la funció objectiu f(x 1,,x n ) és la utilitat generada al nivell de producció x 1,,x n Suposem, per un altre cantó, que el nivell òptim de producció ve donat pel punt x = x 1 x n amb una utilitat òptima igual a z = f (x )=f x 1,,x n i amb vector de multiplicadors de Kuhn-Tucker associat λ = λ 1 λ m Si, en primer lloc, al nivell òptim de producció el i-èsim recurs s esgota, 7 és a dir, si (a) g i (x 1,,x n)=b i, 7 En altres paraules, que l òptim x satura la restricció i-èsima

23 Programació no lineal 23 volem saber si ens interessa augmentar la disponibilitat màxima d aquest recurs Com veurem, la resposta depèn de la relació entre el seu preu de mercat unitari p i ieli-èsim multiplicador de Kuhn-Tucker λ i En efecte, ja que el cost de 4b i unitats és c = p i 4b i deduïm, aplicant la quasigualtat de més amunt, que l increment net en la utilitat òptima seria aproximadament igual a 4 net z = 4z c ' λ i 4b i (pi 4b i )= λ i p i 4bi Per tant, sempre que el preu unitari de mercat p i sigui inferior a λ i interessarà augmentar la disponibilitat i-èsima Per un altre cantó, si el recurs i-èsim no s esgota, és a dir, si (b) g i (x 1,,x n) <b i, llavors λ i seria zero (és una conseqüència de la cinquena condició de Kuhn-Tucker) i, per l anterior, l increment en el valor òptim de la utilitat serà aproximadament zero En aquest cas, qualsevol increment 4b i en la disponibilitat del recurs i-èsim podria produir un decrement net en la utilitat òptima En conseqüència, i des d una perspectiva econòmica, els multiplicadors de Kuhn-Tucker són preus unitaris teòrics (anomenats preus ombra) que ens valoren els recursos en l àmbit de producció òptim ja que ens permeten decidir si val la pena augmentar-ne o no les seves disponibilitats màximes Per exemple, ja sabem que el programa de l exemple 1, max z =3x 1 +2x 2 5x 2 1 2x 2 2 sota 3x 1 +6x x 1 +4x 2 48, 5x 1 +5x 2 5 x 1,x 2 té un màxim global únic en el punt x 1,x 2 =(4, 6) amb multiplicadors de Kuhn-Tucker associats (preus ombra) λ 1 =, λ 2 =42 i λ 3 =16 i amb un valor òptim de la funció d ingressos totals igual a z = z (4, 6) = 2248 u m

24 24 Programació no lineal En conseqüència, si volem augmentar el valor òptim dels ingressos deduïm que no estaríem disposats a pagar res per a disposar de més temps per a la primera fase mentre que arribaríem a pagar, com a màxim, 42 i 16 u m per a disposar, respectivament, d una hora més per la segona i tercera fases Els increments que experimentarien els ingressos totals enfront de possibles increments en les disponibilitats horàries d aquests fases serien aproximadament iguals a 4z ' λ 2 4b 2 =42 4b 2 on 4b 2 denota l increment en el temps dedicat a la segona fase i 4z ' λ 3 4b 2 =16 4b 3 on 4b 3 denota l increment en el temps emprat en la tercera Cal tenir present sempre que els preus ombra són preus de valoració aproximats ja que depenen, en darrera instància, de la magnitud de l increment del recurs Per exemple, els increments reals i estimats del valor òptim dels ingressos totals en funció de cinc possibles variacions en la disponibilitat horària de la segona fase serien b 2 4b 2 4z estimat 4z real Error = = = = = Notem que, a mesura que l increment del recurs augmenta, també ho fa l error comès en prendre l increment estimat en lloc del real Exercicis 1 Sigui x un òptim de max sota z = f (x) g (x) b x n Aleshores x és un òptim de max sota z = f (x) g (x) b h (x) c x n

25 Programació no lineal 25 si, i només si, x és un punt factible d aquest programa Passa el mateix amb un programa canònic de mínim? Raoneu la resposta 2 Proveu que tot punt factible associat a un programa canònic de màxim que satisfà les hipòtesis del teorema de Kuhn-Tucker i que, a més, sigui òptim lliure de la funció objectiu és un màxim del programa canònic amb multiplicadors de Kuhn-Tucker iguals a zero Comproveu que l origen de coordenades és un òptim del programa max sota x + y 1 x, y z =(x 1) 2 y, amb un multiplicador de Kuhn-Tucker associat igual a zero i que, en canvi, no és un òptim lliure de la funció objectiu (això prova que el recíproc 8 de l anterior no sempre és cert) 3 Sigui U : R n R una funció d utilitat còncava associada a la compra de n bens econòmics amb uns preus de venda unitaris p 1,, p n Si el nivell de renda monetària disponible és de M u m, (a) Formuleu el programa d optimització que li permet al consumidor optimitzar-ne la seva utilitat És convex aquest programa? Raoneu la resposta (b) Si U (x 1,,x n ) és de tipus C 2, determineu les condicions de Kuhn-Tucker del programa anterior tot provant que si x = és un òptim amb un multiplicador de Kuhn-Tucker associat diferent de zero llavors x 1 x n p 1 x p n x n = M, és a dir, que la renda monetària disponible s esgota en l òptim Pot existir un òptim amb tots els multiplicadors de Kuhn- Tucker nuls? Raoneu la resposta (c) Proveu que si n =2iU (x 1,x 2 ) es la funció de Cobb-Douglas U (x 1,x 2 )=x a 1 x 1 a 2, amb <a<1 i A>, 8 El recíproc d una implicació de la forma A B és B A

26 26 Programació no lineal l òptim del programa és x 1,x 2 = µ am p 1, (1 a)m p 2 4 Donat el model de selecció d inversions per a dos títols min V (R 1 ) x V (R 2 ) x Cov (R 1,R 2 ) x 1 x 2 sota E (R 1 ) x 1 + E (R 2 ) x 2 E x 1 + x 2 1 x 1,x 2 amb E tant per cent fixat, (a) Proveu que es tracta d un programa convex tenint en compte que Cov (R 1,R 2 ) 1 + p V (R 1 ) V (R 2 ) 1 (b) Podem dir el mateix del model alternatiu max E (R 1 ) x 1 + E (R 2 ) x 2 sota V (R 1 ) x V (R 2 ) x Cov (R 1,R 2 ) x 1 x 2 V x 1 + x 2 1 x 1,x 2 on V és un tant per cent fixat? Raoneu la resposta (c) Proveu que si en el model de minim inicial tenim que Cov (R 1,R 2 )= aleshores, com a conseqüència de les condicions de Kuhn- Tucker associades,, E = E (R 1 ) x 1 + E (R 2 ) x 2 en què (x 1,x 2) és l òptim del programa En altres paraules, que si els dos títols de la cartera d inversions són independents, la rendibilitat òptima de la cartera és la mínima possible 5 Donat el programa no lineal canònic max z = x x 2 2 2x 1 x 2 sota x 1 + x 2 2 x 1 1 x 1,x 2,

27 Programació no lineal 27 (a) Proveu que es tracta d un programa quadràtic no convex amb òptim finit global (b) Troveu-ne l òptim global analitzant les condicions de Kuhn- Tucker És únic aquest òptim? Existeix algún òptim finit local i no global? Existeix algun punt factible que satisfagi les condicions de Kuhn-Tucker sense ser òptim? Raoneu les respostes 6 Una empresa que es dedica a la producció i distribució d aparells electrònics ha signat un contracte per a subministrar un mínim de 5 unitats d un determinat aparell A al mes, durant els pròxims 3 mesos, a una firma industrialconeguda Hom sap que el cost mensual de producció de q unitats és proporcional al quadrat d unitats produïdes en la forma C(q) =25 q 2 i que el cost unitari d emmagatzematge és de 2 u m al mes Aleshores, si no existeixen estocs de A al inici del primer mes, (a) Formuleu el programa matemàtic que determina la política òptima de producció i emmagatzematge que li permet a l empresa fer front al contracte de subministrament de A (b) Estudieu les condicions de Kuhn-Tucker associades i determineu la producció òptima de A tot provant que, en el nivell de producció òptim, la comanda especificada en el contracte se satisfà sense generar excedents mensuals (c) Si per condicionants del mercat l empresa hagués de subministrar durant l últim mes una unitat de més de A, analitzeu l efecte que produiria aquest increment en la producció sobre el valor dels costos totals anteriors (cal aplicar la interpretació econòmica dels multiplicadors de Kuhn-Tucker per a un programa canònic de mínim) 7 Hom sap que els preus de venda unitaris de 3 articles de consum alimentari que el mercat ofereix habitualment són p 1 =41u m, p 2 =2u m i p 3 =9u m si es venen 1 kg del primer, 15 kg del segon i 1 kg del tercer La pròpia evolució del mercat fa que, per cada 25 gr venuts de més de cadascun d ells, p 1 disminueixi en 2 u m, p 2 en 5 u m i p 3 en 8 u m Si els costos unitaris de transport del magatzem al mercat dels esmentats articles són, respectivament, de 34 u m, 156 u m i 28 u m, (a) Plantegeu el programa matemàtic que ens permet maximitzar la utilitat (benefici) de la venda dels tres articles sabent que la despesa total destinada al transport no pot ultrapassar les 438 u m

28 28 Programació no lineal (b) Resoleu el programa anterior tot determinant el benefici òptim Proveu que la despesa òptima del transport és exactament igual a u m i que qualsevol quantitat monetària de més destinada a aquest capítol no modifica el valor òptim del programa (c) Si la despesa monetària destinada a cobrir el cost total de transport no pot superar les 4283 u m, determineu el nou òptim, com també el nou benefici òptim associat (d) Si en les hipòtesis de l apartat anterior poguèssim destinar 5 u m més per a cobrir el cost total de transport dels tres articles, estimeu l increment que es produiria en el benefici òptim associat a la seva venda 8 L empresa X fabrica i ven tres productes P 1,P 2 i P 3 amb uns costos unitaris de producció de 17, 23 i 11 u m Pel que fa a les vendes, se sap que la funció de demanda de P 1 és bàsicament lineal i pren la forma p 1 = p 1 (q 1 )=a b q 1, amb a, b, en què p 1 denota el seu preu de venda unitari i q 1 la quantitat venuda Els paràmetres a i b són, en principi, desconeguts encara que la informació de què disposa X relacionada amb vendes precedents ens diu, per una banda, que p 1 (1) 5 i, per l altra, que es coneixen els valors de p 1 per a quatre valors concrets de q 1 donats per la taula En aquestes condicions, q p (a) Determineu el programa de mínims quadràtics que ens permet trobar els valors d a i b tenint en compte que l expressió que cal minimitzar és X (p 1 (a b q 1 )) 2 q 1 =1,18,35,5 i demostreu que aquest programa és convex (b) Determineu les condicions necessàries de Kuhn-Tucker del programa anterior i estudieu-les per al cas en què els multiplicadors associats siguin zero Amb les dades anteriors, calculeu el valor dels paràmetres a i b

29 Programació no lineal 29 (c) Suposem ara que les funcions de demanda de P 2 i P 3 són, respectivament, p 2 = q 2 i p 3 = q 3 Amb els valors de a i b obtinguts en l apartat anterior, determineu les quantitats de P 1,P 2 i P 3 que maximitzen l ingrés obtingut per la seva venda si, com a màxim, el cost de producció és de 2 u m i tot el que es produeix es ven (d) Proveu que, en aquest cas, no estaríem disposats a pagar res per augmentar la despesa monetària destinada a la producció de P 1,P 2 i P 3 9 Una empresa necessita un mínim de 6 milions d euros per dur a terme un nou projecte d inversió i tres bancs, B 1, B 2 i B 3, s han oferit a finançar-la Encara que cadascun d aquests bancs ha estipulat que el nominal del prèstec més el interessos siguin liquidats en sis anys, les cèdules de liquidació varien d un banc a l altres segons la taula Tant per cent sobre el nominal a pagar any1 any2 any3 any4 any5 any6 Banc1 Banc2 Banc Si el dessitg de l empresa és no pagar més de 4 milions d euros d interessos i el risc de la inversió ve mesurat per la forma quadràtica σ 2 =(x 1,x 2,x 3 ) en què x i denota la quantitat en milions d euros que aporta el banc B i al projecte, 9 (a) Formuleu el programa que ens dóna les quantitats monetàries a demanar a cadascun dels tres bancs És convex aquest programa? Raoneu la resposta (b) Trobeu l òptim del programa anterior tot indicant el nominal total del prèstec que l empresa ha de rebre per part dels tres 9 L empresa considera avantajós que el pagament anual als tres bancs sigui, any rere any, lo més semblant possible i aquesta forma quadràtica ens mesura la dispersió d aquets pagaments x 1 x 2 x 3

30 3 Programació no lineal bancs Quin és l interès total que ha de pagar l empresa al llarg dels sis anys? 1 1 Una botiga de formatges té 2 kg d una mescla de fruites d estació i 6 kg d un formatge car amb els quals es confeccionen dos tipus de formatge per a untar, fi i normal, que són molt populars durant les festes de Nadal Cada quilogram de formatge fi es composa de 2kgdemescladefruiteside8kgdeformatgecar,mentreque un quilogram de formatge per untar normal es composa de 2 kgdemescladefruites,de3kgdeformatgecaride5kgde formatge de farcit del qual es disposa en abundància Si a causa de les polítiques de preus emprades per la botiga en campanyes precedents, hom sap que la demanda en quilograms per a cada tipus de formatge per untar depèn del seu preu de venda en u m segons les funcions de demanda d 1 =19 25p 1 i d 2 =25 5p 2, (a) Formuleu el programa que maximitza els ingressos obtinguts per la venda dels dos formatges per untar tenint en compte de que es vol vendre tota la producció, i proveu que es tracta d un programa quadràtic no convex (b) Comproveu que l origen de coordenades satisfà les condicions de Kuhn-Tucker associades al programa anterior i que, en canvi, no és un òptim (c) Resoleu el programa anterior en el cas de que la demanda i la oferta d ambdós formatges per a untar siguin iguals tot provant que, en l òptim, s esgota la mescla de fruites però no així el formatge car Comproveu que l òptim obtingut satisfà també les condicions de Kuhn-Tucker associades al programa del primer apartat 11 1 Per simplificar, cal considerar l interès total com la suma aritmètica dels interessos anuals 11 Pot demostrar-se que aquest punt és l òptim d aquest programa

31 Capítol 2 Programació lineal El mètode de resolució per a programes convexos relacionat amb les condicions de Kuhn-Tucker és adient també per al cas en què el programa sigui lineal Tanmateix, però, existeix un mètode algebraic de resolució adaptable a processos informàtics, anomenat algorisme del símplex, que es mostra més eficaç a l hora de resoldre aquests programes A més, amb vista a les aplicacions econòmiques, aquest algorisme ens proporciona la informació necessària per a analitzar el comportament dels òptims enfront de possibles variacions en l estructura del programa lineal (és el que s anomena anàlisi de sensibilitat) Val a dir que l algorisme del símplex és una de les contribucions més importants de les matemàtiques en l àmbit de les tècniques de gestió Històricament, l algorisme del símplex va ser ideat per G B Dantzig (1947) per optimitzar la logística dels subministraments aeris durant el bloqueig soviètic de Berlín, 1 encara que el matemàtic i premi Nobel rus L Kantorovitch ja aplicava quelcom de semblant a l inici dels anys trenta del segle XX en l anàlisi dels plans quinquennals de la Unió Soviètica Com a trets característics d aquest capítol cal destacar una breu introducció als fonaments matemàtics de l algorisme del símplex i la seva implementació com a eina de resolució dels programes lineals, com també l estudi en detall de la programació lineal dual i de l anàlisi de sensibilitat Per començar, hom diu que un programa canònic d òptims restringits per desigualtats és lineal si la funció objectiu i les funcions de restricció són formes lineals, és a dir, si és de la 1 Tanmateix, els fonaments matemàtics de l algorisme del Símplex no van ser publicats fins el

32 32 Programació lineal forma max sota z = P n j=1 c j x j P n j=1 a 1j x j b 1 P n j=1 a mj x j b m x 1,,x n, obé min sota z = P n j=1 c j x j P n j=1 a 1j x j b 1 P n j=1 a mj x j b m x 1,,x n Exemple 12 Suposem que en l exemple 1 del capítol anterior els preus de venda unitaris són constants i iguals a p 1 =3u m i p 2 =2u m Sota aquesta hipòtesi, determineu el nou programa que maximitza els ingressos totals de la venda de A i B Ara, la funció objectiu d ingressos totals és z = p 1 x 1 + p 2 x 2 =3x 1 +2x 2 Així doncs, i atès que les restriccions de caràcter instrumental no varien, el nou programa que ens permet trobar els ingressos totals màxims generats per la venda de A i B és max z =3x 1 +2x 2 sota 3x 1 +6x x 1 +4x x 1 +5x 2 5 x 1,x 2 Aquest programa és lineal ja que la funció objectiu i les tres funcions de restricció són formes lineals Fixem-nos que tot programa lineal canònic es pot escriure matricialment en la forma max z = c t x min z = ct x sota A x b o sota A x b, x x en què x = x 1 x n R n

33 Programació lineal 33 és el vector de les variables instrumentals, c = c 1 c n R n és el vector de coeficients de la funció objectiu, a 11 a 1n A = M m n a m1 a mn és la matriu de restricció i b = b 1 b m R m és el vector de les constants de restricció Aquesta és l anomenada formulació matricial canònica d un programa lineal Notem, per exemple, que el vector de coeficients de la funció objectiu, la matriu de coeficients de restricció i el vector de les constants de restricció de la formulació canònica matricial del programa anterior són µ 3 c =, A = i b = En primer lloc, enunciarem el teorema fonamental de la programació lineal que relaciona els òptims finits d un programa lineal amb un tipus especial de punts factibles anomenats vèrtexs 2 Des d un punt de vista informal, els vèrtexs del conjunt factible d un programa lineal són els punts factibles que saturen almenys n de les m + n restriccions de desigualtat associades (m restriccions instrumentals i n restriccions de signe) 3 Com apuntem en el teorema fonamental, si un programa lineal té òptim finit almenys un dels vèrtexs del conjunt factible és òptim Exemple 13 Comproveu que els vèrtexs del conjunt factible del programa lineal anterior són (, ), (, 9), (2, 8), (4, 6) i (8, ) En aquest cas tenim que n =2 i m =3 2 Demostrem aquest teorema en l apèndix B 3 Aquestes n restriccions saturades han de formar un sistema d equacions lineals compatible i determinat

34 34 Programació lineal Per tant, els vèrtexs són els punts factibles que saturen, com a mínim, dues de les cinc restriccions del programa Hom pot comprovar fàcilment que (, ) saturalesduesrestriccionsdesigne,(, 9) satura la primera restricció de signe i la primera restricció instrumental, (2, 8) satura la primera i la tercera restriccions instrumentals, (4, 6) satura la segona i la tercera restriccions instrumentals i (8, ) satura la tercera restricció instrumental i la segona restricció de signe Qualsevol altre punt factible no pot ser vèrtex ja que només satura, com a màxim, una de les cinc restriccions posibles Teorema 14 (Programació lineal) Si un programa lineal té òptim finit, un dels vèrtexs del conjunt factible associat és un òptim global i, a més, qualsevol punt que pertanyi al segment que tingui per extrems dos òptims globals també ho és Aplicarem aquest teorema per resoldre el programa anterior Exemple 15 Determineu els òptims de max z =3x 1 +2x 2 sota 3x 1 +6x x 1 +4x x 1 +5x 2 5 x 1,x 2 Com que el conjunt factible associat és compacte (ho hem provat en el capítol anterior), deduïm, aplicant el teorema de Weierstrass, que el programa té òptim finit i global ja que la funció objectiu, per ser lineal, és contínua En conseqüència, i pel teorema anterior, un dels vèrtexs del conjunt factible és un òptim global Una simple avaluació del valor de la funció objectiu sobre cadascun dels vèrtexs ens mostra que (4, 6) i (8, ) són òptims Així doncs, hom dedueix que qualsevol punt del segment d extrems (4, 6) i (8, ) és un òptim global amb un valor òptim de la funció objectiu igual a z =24u m En conseqüència, si l objectiu és resoldre els programes lineals de la manera més senzilla i ràpida possible, el que cal és analitzar el valor de la funció objectiu sobre els vèrtexs del conjunt factible D això tracta precisament l algorisme del símplex Abans de veure-ho, però,

35 Programació lineal 35 necessitem introduir una nova formulació pels programes lineals Considerem de nou el programa que acabem de resoldre És evident que podem substituir les tres restriccions de desigualtat associades per equacions de manera que s obtingui el programa max z =3x 1 +2x 2 sota 3x 1 +6x 2 + s 1 =54 6x 1 +4x 2 + s 2 =48 5x 1 +5x 2 + s 3 =5 x 1,x 2,s 1,s 2,s 3 en què les noves variables s 1,s 2 i s 3, que ens mesuren la saturació de les restriccions inicials, són positives (si les desigualtats haguessin estat de més gran o igual, les variables s i s hi haurien introduït amb signe menys per respectar la restricció de positivitat) Fixem-nos que aquestes variables no apareixen en la funció objectiu (o, alternativament, apareixen multiplicades per zero); a causa d això, aquest programa d òptims restringits per equacions és equivalent a l anterior ja que genera les mateixes solucions per a les variables instrumentals De fet, els valors òptims que prenen les variables s i ens diuen si les restriccions estan saturades en l òptim del programa lineal inicial i, a més, ens donen el valor de la diferència en el cas que no ho estiguin Així doncs, i en general, la formulació matricial estàndard d un programa lineal és de la forma en què x = x 1 x n s 1 s m max (min) sota, c = z = c t x A x = b x c 1 c n, b = b 1 b m amb la matriu de restricció igual a a 11 a 1n ±1 A =, a m1 a mn ±1, i en què les variables s 1,, s m són les variables de separació del programa 4 Fixem-nos que en la formulació matricial estàndard del pro- 4 Els coeficients ±1 de la matriu de restricció A són +1 si la restricció associada és de menor o igual, i 1 si és de més gran o igual

36 36 Programació lineal grama anterior tenim que x 1 x 2 x = s 1 s 2, c = s 3 3 2, b = , i A = L algorisme del símplex: fonaments matemàtics L algorisme del símplex, que es basa en el fet de que els òptims finits d un programa lineal es troben en els vèrtexs del conjunt factible, presenta dos trets característics: en primer lloc, que no li cal avaluar el valor de la funció objectiu sobre tots els vèrtexs del conjunt factible sinó sobre aquells que l optimitzen més ràpidament; i, en segon, que és el propi algorisme el que ens indica explícitament si l òptim és finit (i en aquest cas ens en dóna el seu valor) o si és infinit Analitzarem, a continuació, els fonaments matemàtics de l algorisme del símplex per a un programa lineal matricial estàndard de màxim (a partir d ara PLM per abreujar) de la forma max sota z = c t x A x = b x n en què les n m primeres components del vector x 1 x x = n m R x n n m+1 x n són les variables instrumentals i les altres m les de separació Per tant, les n m primeres components del vector de coeficients c són els coeficients de la funció objectiu inicial i la resta són zero ja que estan

37 Programació lineal 37 associats amb les m variables de separació que no poden aparèixer Així doncs, la matriu de restricció de PLM serà de la forma a 11 a 1n m ±1 A = M m n a m1 a mn m ±1 en què les n m primeres columnes de A estan associades amb les n m variables instrumentals i les altres m estan associades amb les m variables de separació Com podem veure, la matriu A és de rang m ja que té per submatriu la matriu B = ±1 ±1 M m Aquest fet ens permet donar la primera definició: s anomena matriu bàsica de PLM tota submatriu quadrada invertible d ordre m Sigui, doncs, B M m una matriu bàsica de PLM i sigui D M m n m la matriu formada per les columnes de A que no són de B (les columnes de B i D poden estar barrejades en A) Com que cada columna de A està associada a una de les variables de x, les columnes de B, per ser columnes de A, també estaran associades a variables concretes de x Així doncs, B particiona el vector x de manera que µ xb x = R n en què x D x B R m i x D R n m són els vectors formats, respectivament, per les variables associades a les columnes de B i D Anàlogament, B particiona el vector de coeficients de manera que µ cb c = R n en què c D c B R m i c D R n m són els vectors formats, respectivament, pels coeficients de la funció objectiu associats a x B iax D Arribats a aquest punt, hom diu que

38 38 Programació lineal el vector x B és el vector de les variables bàsiques associades a la matriu bàsica B La noció de solució bàsica factible que donem a continuació desenvolupa un paper fonamental en l algorisme del símplex De fet, tota solució bàsica factible està associada a un vèrtex del conjunt factible de PLM Hom diu que un punt factible x de PLM és una solucióbàsicafactible(sbf, per abreujar) si existeix una matriu bàsica B de PLM de manera que les seves components no bàsiques associades són zero, és a dir, si x D = Cal fer notar que les components bàsiques d una SBF x associada a una matriu bàsica B són x B = B 1 b i que el valor que pren la funció objectiu sobre x és igual a z = c t B B 1 b No tota matriu bàsica dóna lloc a una SBF Es pot demostrar que una matriu bàsica B té una, i només una, SBF associada si B 1 b L interès per les SBF rau en el fet de que si PLM té òptim finit una d elles, com a mínim, ho és Això és el que ens diu el teorema següent Teorema 16 (SBF i òptims) Si PLM té òptim finit, existeix una matriu bàsica de manera que la SBF associada és un òptim Així doncs, el que cal és esbrinar les condicions que fan d una SBF un òptim de PLM Per això, ens cal la definició següent: si B és una matriu bàsica de PLM amb una SBF associada x, lescomponentsdel vector c t B Y c t D R n m on Y és la matriu Y = B 1 D M m n m són els coeficients de desplaçament 5 de x Cal fer notar que els coeficients de desplaçament estan associats a les variables no bàsiques de x L algorisme del símplex es basa en els dos teoremes que enunciem a continuació 5 Elsoposatsalscoeficients de desplaçament són els anomenats costos reduïts

TEMA 4 : Programació lineal

TEMA 4 : Programació lineal TEMA 4 : Programació lineal 4.1. SISTEMES D INEQUACIONS DE PRIMER GRAU AMB DUES INCÒGNITA La solució d aquest sistema és l intersecció de les regions que correspon a la solució de cadascuna de les inequacions

Más detalles

Sèrie 5. Resolució: 1. Siguin i les rectes de d equacions. a) Estudieu el paral lelisme i la perpendicularitat entre les rectes i.

Sèrie 5. Resolució: 1. Siguin i les rectes de d equacions. a) Estudieu el paral lelisme i la perpendicularitat entre les rectes i. Oficina d Accés a la Universitat Pàgina 1 de 11 Sèrie 5 1. Siguin i les rectes de d equacions : 55 3 2 : 3 2 1 2 3 1 a) Estudieu el paral lelisme i la perpendicularitat entre les rectes i. b) Trobeu l

Más detalles

Geometria / GE 2. Perpendicularitat S. Xambó

Geometria / GE 2. Perpendicularitat S. Xambó Geometria / GE 2. Perpendicularitat S. Xambó Vectors perpendiculars Ortogonal d un subespai Varietats lineals ortogonals Projecció ortogonal Càlcul efectiu de la projecció ortogonal Aplicació: ortonormalització

Más detalles

corresponent de la primera pàgina de l examen.

corresponent de la primera pàgina de l examen. Oficina d Accés a la Universitat Pàgina 1 de 5 PAU 017 SÈRIE PAUTES PER ALS CORRECTORS RECORDEU: - Podeu valorar amb tants decimals com considereu convenient, però aconsellem no fer ho amb més de dos.

Más detalles

TEMA 4 : Matrius i Determinants

TEMA 4 : Matrius i Determinants TEMA 4 : Matrius i Determinants MATRIUS 4.1. NOMENCLATURA. DEFINICIÓ Una matriu és un conjunt de mxn elements distribuïts en m files i n columnes, A= Aquesta és una matriu de m files per n columnes. És

Más detalles

FUNCIONS REALS. MATEMÀTIQUES-1

FUNCIONS REALS. MATEMÀTIQUES-1 FUNCIONS REALS. 1. El concepte de funció. 2. Domini i recorregut d una funció. 3. Característiques generals d una funció. 4. Funcions definides a intervals. 5. Operacions amb funcions. 6. Les successions

Más detalles

Optimització amb restriccions d igualtat. Multiplicadors de Lagrange

Optimització amb restriccions d igualtat. Multiplicadors de Lagrange Capítol 7 Optimització amb restriccions d igualtat Multiplicadors de Lagrange La realitat ens imposa models amb restriccions Per exemple, la producció d una empresa està condicionada, entre d altres factors,

Más detalles

1. SISTEMA D EQUACIONS LINEALS

1. SISTEMA D EQUACIONS LINEALS 1. SISTEMA D EQUACIONS LINEALS 1.1 Equacions lineals Una equació lineal està composta de coeficients (nombres reals) acompanyats d incògnites (x, y, z,t..o ) s igualen a un terme independent, i les solucions

Más detalles

ACTIVITATS. a) b) c) d) INS JÚLIA MINGUELL 2n Batxillerat. dv, 18 de març Alumne:

ACTIVITATS. a) b) c) d) INS JÚLIA MINGUELL 2n Batxillerat. dv, 18 de març Alumne: INS JÚLIA MINGUELL 2n Batxillerat Matemàtiques Tasca Continuada 4 «Matrius i Sistemes d equacions lineals» Alumne: dv, 18 de març 2016 LLIURAMENT: dm, 5 d abril 2016 NOTA: cal justificar matemàticament

Más detalles

Oficina d Organització de Proves d Accés a la Universitat Pàgina 1 de 10 PAU 2009 QÜESTIONS

Oficina d Organització de Proves d Accés a la Universitat Pàgina 1 de 10 PAU 2009 QÜESTIONS Oficina d Organització de Proves d Accés a la Universitat Pàgina 1 de 10 PAU 009 SÈRIE 4 QÜESTIONS 1. Considereu el sistema d inequacions següent: x 0, y 0 x+ 5y 10 3x+ 4y 1 a) Dibuixeu la regió de solucions

Más detalles

Polinomis i fraccions algèbriques

Polinomis i fraccions algèbriques Tema 2: Divisivilitat. Descomposició factorial. 2.1. Múltiples i divisors. Cal recordar que: Si al dividir dos nombres enters a i b trobem un altre nombre enter k tal que a = k b, aleshores diem que a

Más detalles

Matemàtiques 1 - FIB

Matemàtiques 1 - FIB Matemàtiques - FI 7--7 Examen Final F Àlgebra lineal JUSTIFIQUEU TOTES LES RESPOSTES. [ punts] Siguin E i F dos espais vectorials, f : E F una aplicació lineal. (a) Digueu què ha de satisfer f per tal

Más detalles

Oficina d Accés a la Universitat Pàgina 1 de 7 PAU 2015 Criteris de correcció Matemàtiques aplicades a les ciències socials

Oficina d Accés a la Universitat Pàgina 1 de 7 PAU 2015 Criteris de correcció Matemàtiques aplicades a les ciències socials Oficina d Accés a la Universitat Pàgina 1 de 7 PAU 015 SÈRIE 1. Un arbre té un volum de 0 m i, per la qualitat de la seva fusta, es ven a 50 per metre cúbic. Cada any l'arbre augmenta el volum en 5 m.

Más detalles

Un sistema lineal de dues equacions amb dues incògnites és un conjunt de dues equacions que podem representar de la manera:

Un sistema lineal de dues equacions amb dues incògnites és un conjunt de dues equacions que podem representar de la manera: Un sistema lineal de dues equacions amb dues incògnites és un conjunt de dues equacions que podem representar de la manera: ax + by = k a x + b y = k Coeficients de les incògnites: a, a, b, b. Termes independents:

Más detalles

Unitat 2 TEOREMA DE TALES. TEOREMA DE PITÀGORES. RAONS TRIGONOMÈTRIQUES UNITAT 2 TEOREMA DE TALES.

Unitat 2 TEOREMA DE TALES. TEOREMA DE PITÀGORES. RAONS TRIGONOMÈTRIQUES UNITAT 2 TEOREMA DE TALES. Unitat 2 TEOREMA DE TALES. TEOREMA DE PITÀGORES. RAONS TRIGONOMÈTRIQUES 41 42 Matemàtiques, Ciència i Tecnologia 8. TRIGONOMETRIA UNITAT 2 QUÈ TREBALLARÀS? què treballaràs? En acabar la unitat has de ser

Más detalles

10 Àlgebra vectorial. on 3, -2 i 4 són les projeccions en els eixos x, y, y z respectivament.

10 Àlgebra vectorial. on 3, -2 i 4 són les projeccions en els eixos x, y, y z respectivament. 10 Àlgebra vectorial ÀLGEBR VECTORIL Índe P.1. P.. P.3. P.4. P.5. P.6. Vectors Suma i resta vectorial Producte d un escalar per un vector Vector unitari Producte escalar Producte vectorial P.1. Vectors

Más detalles

Examen Final 17 de gener de 2013

Examen Final 17 de gener de 2013 MATEMÀTIQUES FIB-UPC Examen Final 7 de gener de 03 a) Representeu gràficament la corba definida per l equació y = x 5x. b) Determineu si el conjunt C = { x R x 5x 6 } és fitat superiorment inferiorment)

Más detalles

VECTORS I RECTES AL PLA. Exercici 1 Tenint en compte quin és l'origen i quin és l'extrem, anomena els següents vectors: D

VECTORS I RECTES AL PLA. Exercici 1 Tenint en compte quin és l'origen i quin és l'extrem, anomena els següents vectors: D VECTORS I RECTES AL PLA Un vector és un segment orientat que és determinat per dos punts, A i B, i l'ordre d'aquests. El primer dels punts s'anomena origen i el segons es denomina extrem, i s'escriu AB.

Más detalles

UNITAT 3: SISTEMES D EQUACIONS

UNITAT 3: SISTEMES D EQUACIONS UNITAT 3: SISTEMES D EQUACIONS 1. EQUACIONS DE PRIMER GRAU AMB DUES INCÒGNITES L equació x + y = 3 és una equació de primer grau amb dues incògnites : x i y. Per calcular les solucions escollim un valor

Más detalles

Oficina d Accés a la Universitat Pàgina 1 de 12 PAU 2015

Oficina d Accés a la Universitat Pàgina 1 de 12 PAU 2015 Oficina d Accés a la Universitat Pàgina 1 de 12 Sèrie 5 Responeu a CINC de les sis qüestions següents. En les respostes, expliqueu sempre què voleu fer i per què. Cada qüestió val 2 punts. Podeu utilitzar

Más detalles

FUNCIONS EXPONENCIALS I LOGARÍTMIQUES. MATEMÀTIQUES-1

FUNCIONS EXPONENCIALS I LOGARÍTMIQUES. MATEMÀTIQUES-1 FUNCIONS EXPONENCIALS I LOGARÍTMIQUES. 1. Funcions exponencials. 2. Equacions exponencials. 3. Definició de logaritme. Propietats. 4. Funcions logarítmiques. 5. Equacions logarítmiques. 1. Funcions exponencials.

Más detalles

Problemes de programació lineal de la sele.

Problemes de programació lineal de la sele. Problemes de programació lineal de la sele. 1. En un taller de confecció es disposa de 80 metres quadrats de tela de cotó i de 120 metres quadrats de tela de llana. Es fan dos tipus de vestits, A i B.

Más detalles

TEMA 4: Equacions exponencials i logarítmiques

TEMA 4: Equacions exponencials i logarítmiques TEMA 4: Equacions exponencials i logarítmiques 4.1. EXPONENCIALS Definim exponencial de base a i exponent n:. Propietats de les exponencials: (1). (2) (3) (4) 1 (5) 4.2. EQUACIONS EXPONENCIALS Anomenarem

Más detalles

Tema 2: Equacions i problemes de segon grau.

Tema 2: Equacions i problemes de segon grau. Tema : Equacions i problemes de segon grau..1. Les equacions de n grau. Equacions del tipus x + 5x - 3 0, on la incògnita x es troba elevada al quadrat, diem que són equacions de segon grau. Exemples:

Más detalles

c) C = (c ij ) de tres files i tres columnes per a) u r = (1, 2, 3, 4), c) u r = (1, 1, 1), v r = (2, 4, 8) i w r = (3, 9, 27)

c) C = (c ij ) de tres files i tres columnes per a) u r = (1, 2, 3, 4), c) u r = (1, 1, 1), v r = (2, 4, 8) i w r = (3, 9, 27) SOLUCONAR Unitat 8 Comencem Cada 100 g de producte d un determinat aliment conté 0,06 g de vitamina A, 0,3 g de vitamina B i 0, g de calci. Anàlogament, un altre aliment conté 0,1 g de vitamina A, 0, g

Más detalles

1. Continuïtat i ĺımit de funcions de vàries variables

1. Continuïtat i ĺımit de funcions de vàries variables Càlcul 2 1. Continuïtat i ĺımit de funcions de vàries variables Dept. de Matemàtica Aplicada I www.ma1.upc.edu Universitat Politècnica de Catalunya 12 Febrer 2012 Copyleft c 2012 Reproducció permesa sota

Más detalles

4. EQUACIONS DE PRIMER GRAU AMB UNA INCÒGNITA

4. EQUACIONS DE PRIMER GRAU AMB UNA INCÒGNITA Definició d'equació. Equacions de primer grau amb una incògnita 1. EQUACIONS: DEFINICIONS Equació: igualtat entre dues expressions algebraiques. L'expressió de l'esquerra de la igualtat rep el nom de PRIMER

Más detalles

Vector unitari Els vectors unitaris tenen de mòdul la unitat. Calculem el vector unitari del vector següent manera: ( ) ( )

Vector unitari Els vectors unitaris tenen de mòdul la unitat. Calculem el vector unitari del vector següent manera: ( ) ( ) GEOMETRIA EN L ESPAI VECTORS EN L ESPAI OPERACIONS AMB VECTORS Un vector és un segment orientat en l espai que té un mòdul, una direcció i un sentit coneguts: té un extrem i un origen (Exemple: vector

Más detalles

XXXV OLIMPÍADA MATEMÀTICA

XXXV OLIMPÍADA MATEMÀTICA XXXV OLIMPÍADA MATEMÀTICA Primera fase (Catalunya) 10 de desembre de 1999, de 16 a 0h. 1. Amb quadrats i triangles equilàters de costat unitat es poden construir polígons convexos. Per exemple, es poden

Más detalles

1.- Elements d una recta Vector director d una recta Vector normal d una recta Pendent d una recta

1.- Elements d una recta Vector director d una recta Vector normal d una recta Pendent d una recta .- Elements d una recta..- Vector director d una recta..- Vector normal d una recta.3.- Pendent d una recta.- Equacions d una recta..- Equació ectorial, paramètrica i contínua..- Equació explícita.3.-

Más detalles

GEOMETRIA ANALÍTICA DEL PLA. MATEMÀTIQUES-1

GEOMETRIA ANALÍTICA DEL PLA. MATEMÀTIQUES-1 GEOMETRIA ANALÍTICA DEL PLA. 1. Vectors en el pla.. Equacions de la recta. 3. Posició relativa de dues rectes. 4. Paral lelisme de rectes. 5. Producte escalar de dos vectors. 6. Perpendicularitat de rectes.

Más detalles

Examen FINAL M2 FIB-UPC 11 de gener de 2017

Examen FINAL M2 FIB-UPC 11 de gener de 2017 Examen FINAL M FIB-UPC 11 de gener de 017 1. (3 punts) Sigui {a n } la successió tal que: a 1 = 56 i a n+1 = a n per a tot n > 1. a) Proveu que 1 a n 56, per a tot n 1. b) Proveu que {a n } és decreixent.

Más detalles

Oficina d Accés a la Universitat Pàgina 1 de 6 PAU 2016 Criteris de correcció

Oficina d Accés a la Universitat Pàgina 1 de 6 PAU 2016 Criteris de correcció Oficina d Accés a la Universitat Pàgina 1 de 6 Criteris de correcció Matemàtiques aplicades a les ciències socials SÈRIE 3 1. Una fàbrica de mobles de cuina ven 1000 unitats mensuals d un model d armari

Más detalles

Cognoms i Nom: Examen parcial de Física - CORRENT CONTINU 3 d Octubre del 2013

Cognoms i Nom: Examen parcial de Física - CORRENT CONTINU 3 d Octubre del 2013 Examen parcial de Física - COENT CONTINU Model Qüestions: 50% de l examen cada qüestió només hi ha una resposta correcta. Encercleu-la de manera clara. Puntuació: correcta = 1 punt, incorrecta = -0.25

Más detalles

= 1+ β, essent α i β paràmetres reals. a la recta r 2. i el pla Π d equació

= 1+ β, essent α i β paràmetres reals. a la recta r 2. i el pla Π d equació Problema A Setembre 0 + y z = En l espai es té la recta r i el pla Π d equacions r x + mz = 0, on x y z = 0 m és un paràmetre real a) Un vector director de la recta r b) El valor de m per al qual la recta

Más detalles

3. FUNCIONS DE RECERCA I REFERÈN- CIA

3. FUNCIONS DE RECERCA I REFERÈN- CIA 1 RECERCA I REFERÈN- CIA Les funcions d aquest tipus permeten fer cerques en una taula de dades. Les funcions més representatives són les funcions CONSULTAV i CONSULTAH. Aquestes realitzen una cerca d

Más detalles

Nom i Cognoms: Grup: Data:

Nom i Cognoms: Grup: Data: n BATX MA ) Raoneu la certesa o falsedat de les afirmacions següents: a) Si A és la matriu dels coeficients d'un sistema d'equacions lineals i Ampl és la matriu ampliada del mateix sistema. Rang(A) Rang

Más detalles

Unitat 2 EQUACIONS DE PRIMER GRAU. Matemàtiques, Ciència i Tecnologia 5. TRANSFORMACIONS D EXPRESSIONS ALGEBRAIQUES UNITAT 2 EQUACIONS DE PRIMER GRAU

Unitat 2 EQUACIONS DE PRIMER GRAU. Matemàtiques, Ciència i Tecnologia 5. TRANSFORMACIONS D EXPRESSIONS ALGEBRAIQUES UNITAT 2 EQUACIONS DE PRIMER GRAU Unitat 2 EQUACIONS DE PRIMER GRAU 37 38 Matemàtiques, Ciència i Tecnologia 5. TRANSFORMACIONS D EXPRESSIONS ALGEBRAIQUES UNITAT 2 QUÈ TREBALLARÀS? què treballaràs? En acabar la unitat has de ser capaç

Más detalles

AVALUACIÓ DE QUART D ESO

AVALUACIÓ DE QUART D ESO AVALUACIÓ DE QUART D ESO FULLS DE RESPOSTES I CRITERIS DE CORRECCIÓ Competència matemàtica FULL DE RESPOSTES VERSIÓ AMB RESPOSTES competència matemàtica ENGANXEU L ETIQUETA IDENTIFICATIVA EN AQUEST ESPAI

Más detalles

Oficina d Organització de Proves d Accés a la Universitat Pàgina 1 de 11 PAU 2005

Oficina d Organització de Proves d Accés a la Universitat Pàgina 1 de 11 PAU 2005 Oficina d Organització de Proves d Accés a la Universitat Pàgina 1 de 11 PAU 005 SÈRIE. Avalueu cada pregunta en punts i mitjos punts, però no en altres decimals. Ara bé, dins de cada pregunta podeu utilitzar

Más detalles

INTERACCIÓ GRAVITATÒRIA

INTERACCIÓ GRAVITATÒRIA INTERACCIÓ GRAVITATÒRIA REPÀS FÓRMULES DE MOVIMENT MRU MRUA CAIGUDA LLIURE MRUA on MCU LLEIS DE KEPLER 1ª. Tots els planetes es mouen al voltant del sol seguint òrbites el líptiques. El Sol està a un dels

Más detalles

Oficina d'organització de Proves d'accés a la Universitat Pàgina 1 de 8 PAU 2004

Oficina d'organització de Proves d'accés a la Universitat Pàgina 1 de 8 PAU 2004 Oficina d'organització de Proves d'accés a la Universitat Pàgina de 8 PAU 004 SÈRIE 3 Avalueu cada pregunta en punts i mitjos punts, però no en altres decimals (ara bé, dins de cada pregunta podeu utilitzar

Más detalles

UPF, Curs Trimestre 1 Probabilitat i Estadística, Examen Primer Trimestre, Probabilitat

UPF, Curs Trimestre 1 Probabilitat i Estadística, Examen Primer Trimestre, Probabilitat UPF, Curs 2015-16 Trimestre 1 Probabilitat i Estadística, Examen Primer Trimestre, Probabilitat Professors: Albert Satorra, Christian Brownlees, Mireia Besalú Nom i Cognoms: DNI: Grup: Signeu aquí 1. Ompliu

Más detalles

Geometria / GQ 2. Invariants euclidians de les còniques S. Xambó

Geometria / GQ 2. Invariants euclidians de les còniques S. Xambó Geometria / GQ 2. Invariants euclidians de les còniques S. Xambó,, Classificació de còniques mitjançant invariants Obtenció de les equacions reduïdes i canòniques a partir dels invariants Exemple: àrea

Más detalles

Resolucions de l autoavaluació del llibre de text

Resolucions de l autoavaluació del llibre de text Pàg. 1 de 1 Tenim els vectors u(3,, 1), v ( 4, 0, 3) i w (3,, 0): a) Formen una base de Á 3? b) Troba m per tal que el vector (, 6, m) sigui perpendicular a u. c) Calcula u, ì v i ( u, v). a) Per tal que

Más detalles

Districte Universitari de Catalunya

Districte Universitari de Catalunya Proves d Accés a la Universitat. Curs 2012-2013 Matemàtiques Sèrie 4 Responeu a CINC de les sis qüestions següents. En les respostes, expliqueu sempre què voleu fer i per què. Cada qüestió val 2 punts.

Más detalles

3.1 EL SEGON PRINCIPI DE LA TERMODINÀMICA

3.1 EL SEGON PRINCIPI DE LA TERMODINÀMICA 3.1 EL SEGON PRINCIPI DE LA TERMODINÀMICA Els processos termodinàmics Un procés és espontani quan un sistema evoluciona des d un estat inicial fins a un estat final sense cap tipus d intervenció externa.

Más detalles

DIAGRAMA DE FASES D UNA SUBSTANCIA PURA

DIAGRAMA DE FASES D UNA SUBSTANCIA PURA DIAGRAMA DE FASES D UNA SUBSTANCIA PURA Que es una fase? De forma simple, una fase es pot considerar una manera d anomenar els estats: sòlid, líquid i gas. Per exemple, gel flotant a l aigua, fase sòlida

Más detalles

SOLUCIONS DE LES ACTIVITATS D APRENENTATGE

SOLUCIONS DE LES ACTIVITATS D APRENENTATGE SOLUCIONS DE LES ACTIVITATS D APRENENTATGE 55 Activitat 1 Dels nombres següents, indica quins són enters. a) 4 b) 0,25 c) 2 d) 3/5 e) 0 f) 1/2 g) 9 Els nombres enters són: 4, 2, 0 i 9. Activitat 2 Si la

Más detalles

Matemàtiques. Proves d accés a la Universitat per a més grans de 25 anys. Sèrie. el polinomi 2. Solució: tercera arrel. i , i.

Matemàtiques. Proves d accés a la Universitat per a més grans de 25 anys. Sèrie. el polinomi 2. Solució: tercera arrel. i , i. Pàgina 1 5 Proves d accés a la Universitat per a més grans 5 anys Abril 015 Sèrie Exercicis Opció A A1.- Consireu el polinomi 7 6. Justifiqueu que 1 i són dues arrels l polinomi. Determineu la tercera

Más detalles

h.itkur MD- Grafs 0-1/6

h.itkur MD- Grafs 0-1/6 h.itkur MD- Grafs 0-1/6 Grafs Concepte de graf. Vèrtexs i arestes. Entendrem per graf a un parell ordenat G=(V,A), on V és un conjunt no buit d'elements que en diem vèrtexs i A és un subconjunt de parells

Más detalles

Derivació Funcions Vàries Variables

Derivació Funcions Vàries Variables Derivació Funcions Vàries Variables Jordi Villanueva Departament de Matemàtica Aplicada I Universitat Politècnica de Catalunya 24 de febrer de 2016 Jordi Villanueva (MA1) Derivació Funcions Vàries Variables

Más detalles

Manual per a consultar la nova aplicació del rendiment acadèmic dels Graus a l ETSAV

Manual per a consultar la nova aplicació del rendiment acadèmic dels Graus a l ETSAV Manual per a consultar la nova aplicació del rendiment acadèmic dels Graus a l ETSAV Versió: 1.0 Data: 19/01/2017 Elaborat: LlA-CC Gabinet Tècnic ETSAV INDEX Objectiu... 3 1. Rendiment global dels graus...

Más detalles

Resultat final, sense desenvolupar, dels exercicis i problemes proposats de cada unitat i de l apartat Resolució de problemes. En queden exclosos

Resultat final, sense desenvolupar, dels exercicis i problemes proposats de cada unitat i de l apartat Resolució de problemes. En queden exclosos DE S L U S RE S I V I C LES Resultat final, sense desenvolupar, dels exercicis i problemes proposats de cada unitat i de l apartat Resolució de problemes. En queden exclosos aquells exercicis que requereixen

Más detalles

Tema 1: TRIGONOMETRIA

Tema 1: TRIGONOMETRIA Tema : TRIGONOMETRIA Raons trigonomètriques d un angle - sinus ( projecció sobre l eix y ) sin α sin α [, ] - cosinus ( projecció sobre l eix x ) cos α cos α [ -, ] - tangent tan α sin α / cos α tan α

Más detalles

CARTES DE FRACCIONS. Materials pel Taller de Matemàtiques

CARTES DE FRACCIONS. Materials pel Taller de Matemàtiques CARTES DE FRACCIONS Aquesta proposta és adequada pel primer cicle d ESO perquè permet recordar mitjançant un joc, una sèrie de conceptes que ja s han treballat a l Educació Primària. Per això resulta una

Más detalles

APUNTS DE MATEMÀTIQUES II

APUNTS DE MATEMÀTIQUES II APUNTS DE MATEMÀTIQUES II Gonzalo Rodríguez Departament de Matemàtica Econòmica, Financera i Actuarial Graus d ADE i d Economia PRÒLEG Aquests Apunts de Matemàtiques II dels graus d ADE (Administració

Más detalles

MATEMÀTIQUES Versió impresa ESTADÍSTICA

MATEMÀTIQUES Versió impresa ESTADÍSTICA MATEMÀTIQUES Versió impresa ESTADÍSTICA 1. RepÀs d estadística unidimensional 1.1. Freqüències absoluta i relativa Si ho recordeu, una de les primeres magnituds que es calcula en un estudi estadístic és

Más detalles

2.1 ELS POTENCIALS ESTÀNDARDS DE REDUCCIÓ

2.1 ELS POTENCIALS ESTÀNDARDS DE REDUCCIÓ 2.1 ELS POTENCIALS ESTÀNDARDS DE REDUCCIÓ Es construeix una pila amb els elèctrodes següents: un elèctrode de zinc en una solució de sulfat de zinc i un elèctrode de coure en una solució de sulfat de coure.

Más detalles

UNITAT TAULES DINÀMIQUES

UNITAT TAULES DINÀMIQUES UNITAT TAULES DINÀMIQUES 3 Modificar propietats dels camps Un cop hem creat una taula dinàmica, Ms Excel ofereix la possibilitat de modificar les propietats dels camps: canviar-ne el nom, l orientació,

Más detalles

Cognoms i Nom: Examen parcial de Física - CORRENT CONTINU 5 d octubre de 2017

Cognoms i Nom: Examen parcial de Física - CORRENT CONTINU 5 d octubre de 2017 xamen parcial de ísica - CONT CONTINU Model Qüestions: 50% de l examen cada qüestió només hi ha una resposta correcta. ncercleu-la de manera clara. Puntuació: correcta = 1 punt, incorrecta = -0.25 punts,

Más detalles

Guia docent. 1. Estimació puntual de paràmetres a. Característiques desitjables dels estimadors 2. Estimació per intervals dels paràmetres

Guia docent. 1. Estimació puntual de paràmetres a. Característiques desitjables dels estimadors 2. Estimació per intervals dels paràmetres Guia docent 1. Estimació puntual de paràmetres a. Característiques desitjables dels estimadors 2. Estimació per intervals dels paràmetres 1 1. Estimació puntual de paràmetres a. Característiques desitjables

Más detalles

TEMA 5: La competència perfecta 1

TEMA 5: La competència perfecta 1 TEMA 5: La competència perfecta 1 1. Que en l equilibri a llarg termini en competència perfecta no hi hagi beneficis extraordinaris ni pèrdues es deu a: a) Que el preu és constant. b) La lliure concurrència.

Más detalles

NOVES MILLORES EN LA CARPETA DEL CIUTADÀ

NOVES MILLORES EN LA CARPETA DEL CIUTADÀ NOVES MILLORES EN LA CARPETA DEL CIUTADÀ ÍNDEX 1. LA MEVA CARPETA... 3 2. DADES DEL PADRÓ... 4 2.1. Contextualització... 4 2.2. Noves Millores... 4 3. INFORMACIÓ FISCAL... 6 3.1. Contextualització... 6

Más detalles

Tema 2. Els aparells de comandament elèctrics.

Tema 2. Els aparells de comandament elèctrics. 2 ELS APARELLS DE COMANDAMENT Els aparells de comandament són elements presents en qualsevol circuit o instal lació i que serveixen per governar-los. En aparença, alguns aparells de comandament poden semblar

Más detalles

EXERCICIS - SOLUCIONS

EXERCICIS - SOLUCIONS materials del curs de: MATEMÀTIQUES SISTEMES D EQUACIONS EXERCICIS - SOLUCIONS AUTOR: Xavier Vilardell Bascompte [email protected] ÚLTIMA REVISIÓ: 21 d abril de 2009 Aquests materials han estat realitzats

Más detalles

Oficina d Organització de Proves d Accés a la Universitat Pàgina 1 de 10 PAU 2006 Matemàtiques aplicades a les ciències socials

Oficina d Organització de Proves d Accés a la Universitat Pàgina 1 de 10 PAU 2006 Matemàtiques aplicades a les ciències socials Oficina d Organització de Proves d Accés a la Universitat Pàgina 1 de 10 PAU 006 SÈRIE 1 Avalueu cada pregunta en punts i mitjos punts, però no en altres decimals. Ara bé, dins de cada pregunta podeu utilitzar

Más detalles

Equacions de primer i segon grau

Equacions de primer i segon grau Equacions de primer i segon grau Les equacions de primer i segon grau Equacions de primer grau amb una incògnita Exemple 3x 5 = x + 5 és una equació de primer grau amb una incògnita: és una equació perquè

Más detalles

SOLUCIONS DE LES ACTIVITATS D APRENENTATGE

SOLUCIONS DE LES ACTIVITATS D APRENENTATGE 30 SOLUCIONS DE LES ACTIVITATS D APRENENTATGE Activitat 1 Completa la taula següent: Graus Minuts Segons 30º 30 x 60 = 1.800 1.800 x 60 = 108.000 45º 2.700 162.000 120º 7.200 432.000 270º 16.200 972.000

Más detalles

Les funcions que apliquen a tots els elements del domini la mateixa imatge es diu funció constant, evidentment han d ésser del tipus f(x) = k (k R)

Les funcions que apliquen a tots els elements del domini la mateixa imatge es diu funció constant, evidentment han d ésser del tipus f(x) = k (k R) 1 1 3 FUNCIONS LINEALS I QUADRÀTIQUES 3.1- Funcions constants Les funcions que apliquen a tots els elements del domini la mateixa imatge es diu funció constant, evidentment han d ésser del tipus f(x) k

Más detalles

OLIMPÍADA DE FÍSICA CATALUNYA 2011

OLIMPÍADA DE FÍSICA CATALUNYA 2011 QÜESTIONS A) Dos blocs es mouen per l acció de la força F sobre un terra horitzontal sense fregament tal com es veu a la figura, on T és la tensió de la corda que uneix els dos cossos. Determineu la relació

Más detalles

POLINOMIS. p(x) = a 0 + a 1 x + a 2 x a n x n,

POLINOMIS. p(x) = a 0 + a 1 x + a 2 x a n x n, POLINOMIS Un monomi és una expressió de la forma ax m, on el coeficient a és un nombre real o complex, x és una indeterminada i m és un nombre natural o zero. Un polinomi és una suma finita de monomis,

Más detalles

El perfil es pot editar: 1. des de la llista de participants 2. fent clic sobre el nostre nom, situat a la part superior dreta de la pantalla

El perfil es pot editar: 1. des de la llista de participants 2. fent clic sobre el nostre nom, situat a la part superior dreta de la pantalla MOODLE 1.9 PERFIL PERFIL Moodle ofereix la possibilitat que els estudiants i professors puguin conèixer quines són les persones que estan donades d alta a l assignatura. Permet accedir a la informació

Más detalles

UNITAT LES REFERÈNCIES EN L ÚS DELS CÀLCULS

UNITAT LES REFERÈNCIES EN L ÚS DELS CÀLCULS UNITAT LES REFERÈNCIES EN L ÚS DELS CÀLCULS 1 Introducció de fórmules El programa Ms Excel és un full de càlcul que permet dur a terme tota mena d operacions matemàtiques i instruccions lògiques que mostren

Más detalles

Aquesta eina es treballa des de la banda de pestanyes Inserció, dins la barra d eines Il lustracions.

Aquesta eina es treballa des de la banda de pestanyes Inserció, dins la barra d eines Il lustracions. UNITAT ART AMB WORD 4 SmartArt Els gràfics SmartArt són elements gràfics que permeten comunicar informació visualment de forma molt clara. Inclouen diferents tipus de diagrames de processos, organigrames,

Más detalles

Perquè Teoria de Sistemes

Perquè Teoria de Sistemes Perquè Teoria de Sistemes La Terra ha estat sotmesa a un procés de canvi ininterromput. Un procés de canvi que va començar molt abans de l aparició de la vida a la Terra. Canvis naturals -continus o catastròfics-

Más detalles

La creació de qualsevol llista es fa amb l operador list. En el cas de crear una llista buida la sintaxi és

La creació de qualsevol llista es fa amb l operador list. En el cas de crear una llista buida la sintaxi és ETSEIB PROGRAMACIÓ Grau en Estadística UB-UPC, març 2016 Prof: Robert Joan-Arinyo Llistes 1 Definició En el llenguatge de programació R, una llista és un conjunt d informacions ordenades i no necessàriament

Más detalles

Oficina de Coordinació i d'organització de les PAU de Catalunya Pàgina 1 de 8 PAU SÈRIE 3 Pautes de correcció (PAU 2002) MATEMÀTIQUES

Oficina de Coordinació i d'organització de les PAU de Catalunya Pàgina 1 de 8 PAU SÈRIE 3 Pautes de correcció (PAU 2002) MATEMÀTIQUES Oficina de Coordinació i d'organització de les PAU de Catalunya Pàgina 1 de 8 SÈRIE 3 () MATEMÀTIQUES Avalueu cada pregunta en punts i mitjos punts, però no en altres decimals (ara bé, dins de cada pregunta

Más detalles

FLUX DE CAIXA I COST FINANCER A PARTIR DEL

FLUX DE CAIXA I COST FINANCER A PARTIR DEL FLUX DE CAIXA I COST FINANCER A PARTIR DEL PRESSUPOST I LA PLANIFICACIÓ PROCÉS Realitzar el pressupost i la planificació amb la mateixa codificació d unitats d obra i activitats. 1. Donar d alta a Presto

Más detalles

Veure que tot nombre cub s obté com a suma de senars consecutius.

Veure que tot nombre cub s obté com a suma de senars consecutius. Mòdul Cubs i nombres senars Edat mínima recomanada A partir de 1er d ESO, tot i que alguns conceptes relacionats amb el mòdul es poden introduir al cicle superior de primària. Descripció del material 15

Más detalles

Tema 11. La maximització de beneficis. Montse Vilalta Microeconomia II Universitat de Barcelona

Tema 11. La maximització de beneficis. Montse Vilalta Microeconomia II Universitat de Barcelona Tema 11. La maximització de beneficis Montse Vilalta Microeconomia II Universitat de Barcelona 1 Factors de producció K, L Producte Procés de producció (Funció de Producció) En auest tema estudiarem com

Más detalles

Química 2n de Batxillerat. Gasos, Solucions i estequiometria

Química 2n de Batxillerat. Gasos, Solucions i estequiometria Gasos, Solucions i estequiometria Equació d Estat dels gasos ideals o perfectes Equació d Estat dels Gasos Ideals. p V = n R T p és la pressió del gas; es mesura habitualment en atmosferes o Pascals en

Más detalles

Oficina d Organització de Proves d Accés a la Universitat Pàgina 1 de 10 PAU 2010

Oficina d Organització de Proves d Accés a la Universitat Pàgina 1 de 10 PAU 2010 Oficina d Organització de Proves d Accés a la Universitat Pàgina 1 de 10 SÈRIE 1 Pregunta 1 3 1 lim = 3. Per tant, y = 3 és asímptota horitzontal de f. + 3 1 lim =. Per tant, = - és asímptota horitzontal

Más detalles

TEMA 2: Múltiples i Divisors

TEMA 2: Múltiples i Divisors TEMA 2: Múltiples i Divisors 4tESO CB Concepte de múltiple 6 és múltiple de 2 perquè 2 3 = 6 24 és múltiple de 8 perquè 8 3 = 24 25 NO és múltiple de 3 perquè no hi ha cap nombre que multiplicat per 3

Más detalles

Llista 1. Probabilitat. (Amb solució)

Llista 1. Probabilitat. (Amb solució) Llista 1 Probabilitat (Amb solució 1 Descriu l espai mostral (Ω associat als següents experiments aleatoris: a Tirem dos daus distingibles i observem els números de les cares superiors b Tirem dos daus

Más detalles

Criteris generals per a la correcció:

Criteris generals per a la correcció: Oficina d Accés a la Universitat Pàgina de Sèrie Responeu a CINC de les sis qüestions següents. En les respostes, epliqueu sempre què voleu fer i per què. Cada qüestió val punts. Podeu utilitzar calculadora,

Más detalles

Cognoms i Nom: Examen parcial de Física - ELECTRÒNICA 1 de desembre de 2016

Cognoms i Nom: Examen parcial de Física - ELECTRÒNICA 1 de desembre de 2016 1 de desembre de 016 Model A Qüestions: 50% de l examen A cada qüestió només hi ha una resposta correcta. Encercleu-la de manera clara. Puntuació: correcta = 1 punt, incorrecta = -0.5 punts, en blanc =

Más detalles

Taller de creació de videojocs amb Scratch

Taller de creació de videojocs amb Scratch Taller de creació de videojocs amb Scratch Frank Sabaté i Carlota Bujons Escola Projecte Av. Tibidabo, 16. 08022 Barcelona Telèfon: 93 417 03 21 [email protected] [email protected] 1. Descripció

Más detalles

ESPECIAL LABORATORI TURISME ESTIMACIÓ DEL PIB TURÍSTIC EN LES MARQUES I COMARQUES DE LA PROVÍNCIA DE BARCELONA

ESPECIAL LABORATORI TURISME ESTIMACIÓ DEL PIB TURÍSTIC EN LES MARQUES I COMARQUES DE LA PROVÍNCIA DE BARCELONA ESPECIAL LABORATORI TURISME ESTIMACIÓ DEL PIB TURÍSTIC EN LES MARQUES I COMARQUES DE LA PROVÍNCIA DE BARCELONA 2005-2008 * A partir de l informe Estimació del PIB turístic per Catalunya 2005-2008 realitzat

Más detalles

PROVA D APTITUD PERSONAL ACCÉS ALS GRAUS EDUCACIÓ INFANTIL I EDUCACIÓ PRIMÀRIA

PROVA D APTITUD PERSONAL ACCÉS ALS GRAUS EDUCACIÓ INFANTIL I EDUCACIÓ PRIMÀRIA Nom i cognoms DNI / NIE PROVA D APTITUD PERSONAL ACCÉS ALS GRAUS EDUCACIÓ INFANTIL I EDUCACIÓ PRIMÀRIA COMPETÈNCIA LOGICOMATEMÀTICA 1. Està prohibit l ús de la calculadora o de qualsevol altre aparell

Más detalles

COM DONAR D ALTA UNA SOL LICITUD EN L APLICACIÓ WEB DEL BONUS

COM DONAR D ALTA UNA SOL LICITUD EN L APLICACIÓ WEB DEL BONUS COM DONAR D ALTA UNA SOL LICITUD EN L APLICACIÓ WEB DEL BONUS Introducció Mitjançant aquest document s explica breument la forma de procedir per donar d alta o modificar una sol licitud. Per poder emplenar

Más detalles

Oficina d Accés a la Universitat Pàgina 1 de 6 PAU z y 2

Oficina d Accés a la Universitat Pàgina 1 de 6 PAU z y 2 Oficina d Accés a la Universitat Pàgina 1 de 6 PAU 014 SÈRIE 3 1. En Pol, la Júlia i la Maria han comprat un regal. La Júlia ha gastat la meitat que la Maria, i en Pol n ha gastat el triple que la Júlia.

Más detalles

UNITAT TIPUS DE DIAPOSITIVES PER A DISPOSAR INFORMACIÓ

UNITAT TIPUS DE DIAPOSITIVES PER A DISPOSAR INFORMACIÓ UNITAT TIPUS DE DIAPOSITIVES PER A DISPOSAR INFORMACIÓ 5 Diapositiva amb taula Les diapositives d objectes permeten inserir una taula dins la presentació. S entén per taula una quadrícula que es compon

Más detalles

ÍNDEX 1 DEFINICIÓ 2 PER A QUÈ SERVEIX 3 COM ES REPRESENTA 4 PRIMER CONCEPTE 5 ESCALA DE REDUCCIÓ I ESCALA D AMPLIACIÓ 6 PROCEDIMENT DE CÀLCUL

ÍNDEX 1 DEFINICIÓ 2 PER A QUÈ SERVEIX 3 COM ES REPRESENTA 4 PRIMER CONCEPTE 5 ESCALA DE REDUCCIÓ I ESCALA D AMPLIACIÓ 6 PROCEDIMENT DE CÀLCUL Francesc Sala, primera edició, abril de 1996 última revisió, desembre de 2007 ÍNDEX 1 DEFINICIÓ 2 PER A QUÈ SERVEIX COM ES REPRESENTA 4 PRIMER CONCEPTE 5 ESCALA DE REDUCCIÓ I ESCALA D AMPLIACIÓ 6 PROCEDIMENT

Más detalles

QUÍMICA 2 BATXILLERAT. Unitat 3 CINÈTICA QUÍMICA

QUÍMICA 2 BATXILLERAT. Unitat 3 CINÈTICA QUÍMICA QUÍMICA 2 BATXILLERAT Unitat 3 CINÈTICA QUÍMICA La velocitat de les reaccions La VELOCITAT d una reacció es mesura per la quantitat d un dels reactants que es transforma per unitat de temps. Equació de

Más detalles

UNITAT CREAR UNA BASE DE DADES AMB MS EXCEL

UNITAT CREAR UNA BASE DE DADES AMB MS EXCEL UNITAT CREAR UNA BASE DE DADES AMB MS EXCEL 1 Crear una base de dades i ordenar Una base de dades és un conjunt d informació homogènia organitzada de forma sistemàtica. El contingut d una base de dades

Más detalles

3.1 LA SOLUBILITAT. K ps [ions] reacció desplaçada a l esquerra

3.1 LA SOLUBILITAT. K ps [ions] reacció desplaçada a l esquerra 3.1 LA SOLUBILITAT La solubilitat d una substància és la concentració de la dissolució saturada a una temperatura determinada. Es tracta d una propietat característica que s acostuma a expressar com la

Más detalles

f =. El pendent de la recta tangent

f =. El pendent de la recta tangent Oficina d'organització de Proves d'accés a la Universitat Pàgina 1 de 11 PAU 004 SÈRIE. Avalueu cada pregunta en punts i mitjos punts, però no en altres decimals. Ara bé, dins de cada pregunta podeu utilitzar

Más detalles

Matemàtiques Sèrie 1. Instruccions

Matemàtiques Sèrie 1. Instruccions Proves d accés a cicles formatius de grau superior de formació professional inicial, d ensenyaments d arts plàstiques i disseny, i d ensenyaments esportius 2011 Matemàtiques Sèrie 1 Dades de la persona

Más detalles

Tema 4. Competència imperfecta. Monopoli i oligopoli

Tema 4. Competència imperfecta. Monopoli i oligopoli Classe 8 Tema 4. Competència imperfecta. Monopoli i oligopoli L oligopoli Característiques: - Pocs venedors oferint productes similars o idèntics (menys de 10 empreses) - Empreses independents. Les estratègies

Más detalles