Programació lineal Ll1

Aquesta lliçó és una introducció completa presumint certa base a etapes anteriors.

Introducció

Principalment centrada en la definició de funcions, representació, resolució d'equacions i inequacions.

La funció

Resum característic i descriptiu de les funcions:

Abstracta	Taula
${\begin{matrix}f:&X&\longrightarrow &Y\\&a&\longmapsto &b\\&c&\longmapsto &d\end{matrix}}$	${\begin{array}{c|c}X&Y\\\hline a&b\\c&d\end{array}}$

• La columna de X és el domini de la funció f(x), Dom(f), i són tots els valors que accepta f.

• La columna de Y és el recorregut de f(x), Rec(f), i són tots els possibles valors als que arriba f.

Quadrants del pla

Normalment el domini s'utilitza sobre l'eix de les abscisses X i el recorregut sobre l'eix de les ordenades Y

• Punts de tall amb les abscisses si busquem f(x)=0

• Punts de tall amb les ordenades si y=f(0)

• La gràfica és simètrica respecte l'eix d'ordenades si f(x)=f(-x) a tot el domini, serà una funció parella.

• La gràfica és simètrica respecte l'origen d'ordenades si f(x)=-f(-x) a tot el domini, serà una funció imparella.

• Una funció és periòdica si es repeteix contínuament al seu domini i per tant f(x)=f(x+p), i si p és el més petit possible en direm període de f.

Funcions polinòmiques

Són les funcions definides per un polinomi com $f(x)=x^{5}-3x^{2}+x-10.$

• Dom(f) és tots els nombres reals.

• Si tots els exponents són parells, 0, 2, 4, ..., llavors la funció és parella.

• Si tots els exponents són imparells, 1, 3, 5, ..., llavors la funció és imparella.

• Són contínues i derivables al seu domini.

• Si el terme d'exponent més gran que 1 és d'exponent imparell, llavors el recorregut són tots els nombres reals, una branca va a infinit i l'altre a menys infinit.

• Si el terme d'exponent més gran que 1 és positiu llavors les dues branques van a infinit.

• Si el terme d'exponent més gran que 1 és negatiu llavors les dues branques van a menys infinit.

Funcions racionals

• Dom(f) és tots els reals menys el punts on s'anul·la el denominador.

• Són continues al seu domini.

• Poden aparèixer noves branques als punts on s'anul·la el denominador.

• Pot perdre les branques associades al numerador.

Funcions irracionals

Sigui $f(x)={\sqrt[{n}]{x}}$

• Si n és un nombre natural parell major o igual a 2:

• Dom(f) és el conjunt dels valors on x>0.

• Només té una branca.

• Si n és un nombre natural imparell major o igual a 3:

• Dom(f) és el conjunts dels nombres reals.

• Té dues branques.

Nota:

• ${\sqrt {x\,\,}}^{2}=x,$ amb $x>0$

• ${\sqrt {x^{2}\,\,}}=|x|$

Funció exponencial

Sigui $f(x)=a^{x}$ on a>0.

• Dom(f) és el conjunt dels nombres reals.

• Si 0<a<1 la funció és decreixent.

• Si 1<a la funció és creixent.

• Rec(f) és el conjunt dels valors reals positius sense incloure el zero.

Funcions a trossos

Aquestes funcions tenen totes les peculiaritats possibles segons la definició de cada tros.

Exercicis

1) Determina el domini, el recorregut i els punts de tall amb els eixos de les funcions següents

a) $f(x)=0$ Per qualsevol valor de x, la funció diu que la y és zero, que representada es una recta horitzontal. $Dom(f)=\{-\infty ,+\infty \}=\mathbb {R}$ $Rec(f)=\{0\}$ Talla amb l'eix Y al (0,0) i no és que talli a tot arreu sinó, més ben dit, està sobre l'eix X	b) $f(x)=-1$
c) $f(x)=x+1$	d) $f(x)={\frac {1}{x}}$
e) $f(x)={\frac {1}{x-3}}$	f) $f(x)={\sqrt {x+1}}$
g) $f(x)={\sqrt {-x}}$	h) $f(x)={\sqrt {2-x}}$

Vectors i rectes

Vectors

El concepte de vector a la geometria està lligat a dos punts.

Definició i notació:

Donat dos punts A i B de $\mathbb {R} ^{2}$, direm que un vector amb origen $A=(a_{1},\;a_{2})$ i destí $B=(b_{1},\;b_{2})$ és i està format de la següent forma:

${\vec {v}}={\vec {AB}}=B-A=(b_{1}-a_{1},\;b_{2}-a_{2})$

Donat dos punts A i B de $\mathbb {R} ^{3}$, direm que un vector amb origen $A=(a_{1},\;a_{2},\;a_{3})$ i destí $B=(b_{1},\;b_{2},\;b_{3})$ és i està format de la següent forma:

${\vec {v}}={\vec {AB}}=B-A=(b_{1}-a_{1},\;b_{2}-a_{2},\;b_{3}-a_{3})$

Observació

Respectant la idea de resta de matrius files obtenim un nou element, que segueix sent una matriu fila, l'anomenarem vector. Dels valors que té ja no en direm coordenades sinó components. Tenim doncs les propietats següents: Si tenim un origen i un vector llavors tenim el destí. Si tenim un origen i un destí llavors tenim el vector. Si tenim un vector i un destí llavors tenim l'origen. Podem utilitzar algebraicament els punts i vectors com: ${\vec {v}}=B-A$ ${\vec {v}}+A=B$ $A=B-{\vec {v}}$

Per utilitzar vectors necessitem les principals operacions que definim tot seguit i fixeu-vos la semblança amb les operacions de matrius:

Suma de vectors

Donats dos vectors ${\vec {u}}=(u_{1},\;u_{2})$ i ${\vec {v}}=(v_{1},\;v_{2})$ en $\mathbb {R} ^{2}$ la suma és:

${\vec {w}}={\vec {u}}+{\vec {v}}=(u_{1}+v_{1},\;u_{2}+v_{2}).$

Donats dos vectors ${\vec {u}}=(u_{1},\;u_{2},\;u_{3})$ i ${\vec {v}}=(v_{1},\;v_{2},\;v_{3})$ en $\mathbb {R} ^{3}$ la suma és:

${\vec {w}}={\vec {u}}+{\vec {v}}=(u_{1}+v_{1},\;u_{2}+v_{2},\;u_{3}+v_{3}).$

Representació de sumes:

Per definició u+v produeix un altre vector w, és com encadenar, sempre visualment, un vector u i després un v.

1) Dir que u+v=v+u, vol dir que la suma és commutativa. Degut a això aquest fet se'n diu regla del paral·lelogram.

2) Dir que u+(v+w)=(u+v)+w, vol dir que la suma té la propietat associativa.

3) Dir que existeix un vector zero tal que u+0=u, és equivalent a demanar l'existència de l'element neutre es a dir que no pot fer cap modificació sobre els vectors.

4) Dir que u+(-u)=0, és parlar de l'existència de l'element oposat , -u, que sumat a u és zero.

Producte per escalar

Donat un vectors ${\vec {u}}=(u_{1},\;u_{2})$ en $\mathbb {R} ^{2}$ i un escalar $\lambda$ de $\mathbb {R}$ el seu producte és:

${\vec {w}}=\lambda \cdot {\vec {u}}=(\lambda \cdot u_{1},\;\lambda \cdot u_{2}).$

Donat un vectors ${\vec {u}}=(u_{1},\;u_{2},\;u_{3})$ en $\mathbb {R} ^{3}$ i un escalar $\lambda$ de $\mathbb {R}$ el seu producte és:

${\vec {w}}=\lambda \cdot {\vec {u}}=(\lambda \cdot u_{1},\;\lambda \cdot u_{2},\;\lambda \cdot u_{3}).$

Exercicis:

1) Estic en el punt $A=(5,\;5),$ casa meva està en el punt $B=(2,\;3).$ Si camino en línia recta 5 vegades més arribaria a la biblioteca. ¿En quin lloc està la biblioteca? El camí que va a casa meva ve determinat pel vector: ${\vec {AB}}$ $=B-A$ $=(2,\;3)-(5,\;5)$ $(-3,\;-2).$ Per tant si camino, des d'on estic i en línea recta, 5 vegades més, estic fent aquesta operació: $A+5\cdot {\vec {AB}}$ $=(5,\;5)+5\cdot (-3,\;-2)$ $=(5,\;5)+(5\cdot (-3),\;5\cdot (-2))$ $=(5,\;5)+(-15,\;-10)$ $=(-10,\;-5)$ Solució: La biblioteca està al punt $C=(-10,\;-5).$ 2) Dos arbres estan en els punts $A=(2,\;3)$ i $B=(4,\;1),$ però a mig camí hi ha un tresor. ¿On? El camí de A a B és: ${\vec {AB}}$ $=B-A$ $=(4,\;1)-(2,\;3)$ $=(2,\;-2).$ Per trobar el punt mig del camí de A a B només cal fer la meitat del recorregut, és a dir: ${\frac {\vec {AB}}{2}}$ $={\frac {(2,\;-2)}{2}}$ $={\tfrac {1}{2}}(2,\;-2)$ $=({\tfrac {1}{2}}2,\;{\tfrac {1}{2}}(-2))$ $=(1,\;-1).$ Solució: el punt que busquem és $C$ $=A+{\frac {\vec {AB}}{2}}$ $=(2,\;3)+(1,\;-1)$ $=(3,\;2)$

Producte a escalar

Donats dos vectors ${\vec {u}}=(u_{1},\;u_{2})$ i ${\vec {v}}=(v_{1},\;v_{2})$ en $\mathbb {R} ^{2}$ el seu producte és:

$k={\vec {u}}\cdot {\vec {v}}=(u_{1},\;u_{2}){\begin{pmatrix}v_{1}\\v_{2}\end{pmatrix}}=u_{1}\cdot v_{1}+u_{2}\cdot v_{2}.$

Donats dos vectors ${\vec {u}}=(u_{1},\;u_{2},\;u_{3})$ i ${\vec {v}}=(v_{1},\;v_{2},\;v_{3})$ en $\mathbb {R} ^{3}$ el seu producte és:

${\vec {u}}\cdot {\vec {v}}=(u_{1},\;u_{2},\;u_{3}){\begin{pmatrix}v_{1}\\v_{2}\\v_{3}\end{pmatrix}}=u_{1}\cdot v_{1}+u_{2}\cdot v_{2}+u_{3}\cdot v_{3}=3+0+15=18.$

Exemple:

Sigui ${\vec {u}}=(3,\;4,\;5)$ i ${\vec {v}}=(1,\;0,\;3)$ llavors el producte és: $k={\vec {u}}\cdot {\vec {v}}=(3,\;4,\;5){\begin{pmatrix}1\\0\\3\end{pmatrix}}=3\cdot 1+4\cdot 0+5\cdot 3.$

Longitud d'un vector

Donat un vector ${\vec {u}}=(u_{1},\;u_{2})$ en $\mathbb {R} ^{2},$ la seva longitud és:

$l_{\vec {u}}={\sqrt {{\vec {u}}\cdot {\vec {u}}}}={\sqrt {(u_{1},\;u_{2}){\begin{pmatrix}u_{1}\\u_{2}\end{pmatrix}}}}$ $={\sqrt {u_{1}\cdot u_{1}+u_{2}\cdot u_{2}}}$ $={\sqrt {u_{1}^{2}+u_{2}^{2}}}.$

Donat un vector ${\vec {u}}=(u_{1},\;u_{2},\;u_{3})$ en $\mathbb {R} ^{3},$ la seva longitud és:

$l_{\vec {u}}={\sqrt {{\vec {u}}\cdot {\vec {u}}}}={\sqrt {(u_{1},\;u_{2},\;u_{3}){\begin{pmatrix}u_{1}\\u_{2}\\u_{3}\end{pmatrix}}}}$ $={\sqrt {u_{1}\cdot u_{1}+u_{2}\cdot u_{2}+u_{3}\cdot u_{3}}}$ $={\sqrt {u_{1}^{2}+u_{2}^{2}+u_{3}^{2}}}.$

Exemples:

1) Longitud del vector ${\vec {u}}=(1,\;1),$ aplicant la fórmula tenim: $l_{\vec {u}}={\sqrt {1^{2}+1^{2}}}={\sqrt {2}}$ Observem que la longitud del vector és la hipotenusa del triangle rectangle dibuixat, i per tant, és equivalent al teorema de Pitàgores. 2) Longitud del vector ${\vec {w}}=(1,\;-1,\;0),$ aplicant la fórmula tenim: $l_{\vec {w}}={\sqrt {1^{2}+(-1)^{2}+0^{2}}}={\sqrt {2}}$

Tipus de sistemes

Per tancar l'estudi de sistemes lineals només cal classificar aquests sistemes donant una interpretació geomètrica per entendre el que es cuina al seu interior.

Interpretació geomètrica d'una única equació.

Una equació lineal amb una incògnita pot determinar un únic punt sobre la recta real. Una equació lineal amb dos incògnites pot determinar una única recta sobre el pla real. Una equació lineal amb tres incògnites pot determinar un pla sobre l'espai real. Cada equació pot determinar elements amb una dimensió menys que l'espai on es troba.

Buscar les solucions d'un sistema d'equacions lineals és buscar punts comuns que satisfan totes les equacions a la vegada, és a dir que busquem el lloc de trobada de tots els objectes de cada equació.

Direm que un sistema té rang=r quan en la seva triangulació es simplifiquen les equacions quedant només r equacions.

Direm que una matriu té rang=r quan en la seva triangulació es simplifiquen les files quedant només r files.

Direm que la matriu associada a un sistema lineal és ampliada si s'afegeix una nova columna corresponent als termes independents de les equacions, per parlar del rang d'una matriu ampliada escriurem que rang=r*.

Sistema ${\begin{matrix}a_{1\,1}\cdot x_{1}&\cdots &a_{1\,n}\cdot x_{n}&=b_{1}\\\vdots &&\vdots &\vdots \\a_{m\,1}\cdot x_{1}&\cdots &a_{m\,n}\cdot x_{n}&=b_{m}\end{matrix}}$

$\leftrightarrow$

Matriu del sistema ${\begin{pmatrix}a_{1\,1}&\cdots &a_{1\,n}\\\vdots &\ddots &\vdots \\a_{m\,1}&\cdots &a_{m\,n}\end{pmatrix}}$

$\leftrightarrow$

Matriu ampliada ${\begin{pmatrix}a_{1\,1}&\cdots &a_{1\,n}&b_{1}\\\vdots &\ddots &\vdots &\vdots \\a_{m\,1}&\cdots &a_{m\,n}&b_{m}\end{pmatrix}}$

Exemple

Donat el següent sistema, calculeu el seu rang: ${\begin{cases}\;\;\;x-y\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;+2u=2\\\;\;\;\;\;\;\;\;\;\;y+2z-t\;\;\;\;\;\;\;\;\;=2\\\;2x-2y\;\;\;\;\;\;+2t+5u=7\\\;\;\;\;\;\;\;\;-y-2z+t\;\;+u=-1\\-x+y\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;u=1\end{cases}}$ $\xrightarrow {\;eq_{3}-2\cdot eq_{2}\;\;} {\begin{cases}\;\;\;x-y\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;2u=2\\\;\;\;\;\;\;\;\;\;\;y+2z-t\;\;\;\;\;\;\;=2\\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;2t+u=3\\\;\;\;\;\;\;\;\;-y-2z+t+u=-1\\-x+y\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;u=1\end{cases}}$ $\xrightarrow {\;eq_{5}+eq_{1}\;\;} {\begin{cases}x-y\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;2u=2\\\;\;\;\;\;\;\;y+2z-t\;\;\;\;\;\;\;=2\\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;2t+u=3\\\;\;\;\;\;-y-2z+t+u=-1\\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;3u=3\end{cases}}$ $\xrightarrow {\;eq_{4}+eq_{2}\;\;} {\begin{cases}x-y\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;2u=2\\\;\;\;\;\;\;\;y+2z-t\;\;\;\;\;\;\;=2\\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;2t+u=3\\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;u=1\\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;3u=3\end{cases}}$ $\xrightarrow {\;eq_{5}-3\cdot eq_{4}\;\;} {\begin{cases}x-y\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;2u=2\\\;\;\;\;\;\;\;y+2z-t\;\;\;\;\;\;\;=2\\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;2t+u=3\\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;u=1\end{cases}}$ $\leftarrow$ rang = 4.

Classificació dels sistemes lineals amb n incògnites.

$Sistema\;\;lineal={\begin{cases}{\begin{matrix}Sistema\;\;Compatible\;\;SC\\r=r*\end{matrix}}{\begin{cases}{\begin{matrix}Sistema\;\;Compatible\;\;Determinat\;\;SCD\\r=n\end{matrix}}\\\\{\begin{matrix}Sistema\;\;Compatible\;\;indeterminat\;\;SCI\\r<n\end{matrix}}\end{cases}}\\\\{\begin{matrix}Sistema\;\;Incompatible\;\;SI\\r<r*\end{matrix}}\end{cases}}$

SCD: Una única solució, un punt.

SCI: Conjunt de solucions formant objectes de dimensió n-r.

SI: Sense solucions, segurament perquè alguns dels objectes és paral·lel a un altre o interseccions d'altres objectes.

Ara sí podem estudiar les situacions que ens trobarem més sovint al batxillerat.

Sistemes lineals de dos incògnites

Si un sistema lineal de dos incògnites és SCD, llavors vol dir que totes les equacions són rectes concurrents en un únic punt i es podran simplificar fins a restar-ne només dos equacions.

Una interpretació geomètrica seria imaginar tan rectes secants com rectes perpendiculars en un mateix punt que podem o no veure, d'això se'n diu feix de rectes:

Si un sistema lineal de dos incògnites és SCI, llavors vol dir que totes les equacions són idèntiques excepte un múltiple que les simplifica totalment fins a restar-ne només una equació.

Si un sistema lineal de dos incògnites és SI, llavors la simplificació genera contradiccions o situacions impossibles.

Una interpretació geomètrica seria imaginar rectes que no tenen punts en comú a totes les rectes a la vegada: o bé almenys un parell de rectes són paral·leles o bé en el punt on concorren les rectes manca almenys una recta.

Sistemes lineals de tres incògnites

Si un sistema lineal de tres incògnites és SCD, llavors vol dir que totes les equacions són plans que passen per un sol punt i es podran simplificar fins a restar-ne només tres equacions.

Si un sistema lineal de tres incògnites és SCI, llavors vol dir que podria ser desde equacions idèntiques excepte un múltiple que les simplifica totalment fins a restar-ne només una equació o també a més a més podria ser que tenim un feix de plans, es a dir que tots es tallen sobre una recta i per tant les seves equacions simplifiquen en només dues equacions.

Si un sistema lineal de tres incògnites és SI, llavors la simplificació genera contradiccions o situacions impossibles.

Exercicis

1) Analitza quin tipus de sistema és i després resol si es pot.

a) ${\begin{cases}-3x&+3y&=1\\\,\,\,\,\,\,\,x&\,\,\,-y&=5\end{cases}}$

b) ${\begin{cases}x&+y&=0\\x&-y&=0\end{cases}}$

c) ${\begin{cases}\,\,\,x&+3y&=5\\7x&\,\,\,-y&=2\end{cases}}$

d) ${\begin{cases}-x&+y&=0\\\,\,\,\,x&\,\,\,-y&=0\end{cases}}$

e) ${\begin{cases}2x&+3y&=10\\4x&-3y&=2\end{cases}}$

f) ${\begin{cases}2x&+3y&+z&=10\\4x&-3y&-z&=2\\x&+2y&+z&=0\end{cases}}$

g) ${\begin{cases}\,\,\,x&+2y&+3z&=0\\2x&-y&+5z&=0\\\,\,\,x&-3y&+2z&=0\end{cases}}$

h) ${\begin{cases}\,\,\,5x&-2y&+z&=0\\-5x&+2y&-z&=1\\10x&-4y&+2z&=-1\end{cases}}$

i) ${\begin{cases}\,\,\,2x&\,\,\,-y&+5z&=1\\-5x&+2y&-z&=-2\\-3x&\,\,\,+y&+4z&=-1\end{cases}}$

Inequacions

Les inequacions lineals o afins són del tipus:

$ax+by+c\leq 0$

$ax+by+c<0$

$ax+by+c>0$

$ax+by+c\geq 0$

Equació associada a les inequacions anteriors que delimita dos semiplans:

$ax+by+c=0$

La inequació divideix el pla en dos semiplans i cada inequació només es refereix a un d'ells.

¿Quin és el semiplà d'una equació?

Si hem representat l'equació associada, per trobar el semiplà tenim dos eines:

Primer mètode estàndard:

• Sondeig: valorar el punt $(0,0)$ amb la inequació per comprovar que estigui dins i en cas afirmatiu vol dir que aquell semiplà és el buscat. En cas de dubte valorar el punt $(0,1)$ o per últim $(1,0)$ que comprovin la inequació. Per cercar-lo més ràpid hem de procurar simplement que el punt no estigui sobre la recta que divideix el pla.

Segon mètode:

• Aïllem totalment la y a la inequació i la mateixa desigualtat ens indica si és el pla que està per sobre o per sota. Amb exemples es veu ràpidament:

$y>ax+c$	$y\geqslant ax+c$
$y<ax+c$	$y\leqslant ax+c$

Una lectura és que si surt $y\geqslant$ o $y>$ llavors es tracta del semiplà que està per sobre la recta associada.

Per altra banda si surt $y\leqslant$ o $y<$ llavors es tracta del semiplà que està per sota de la recta associada.

És gràcies a la y, segona coordenada dels punts del pla, que permet visualitzar-ho.

Determinació de regions del pla

Els sistemes d'inequacions determinen una regió convexa anomenada regió de factibilitat que és el resultat de fer intersecció de tots els semiplans donats.

Exemples:

Funció objectiu

La funció objectiu que utilitzarem és del tipus:

$f(x,y)=c_{1}x+c_{2}y+c$

Aquesta funció assigna un valor a cada punt de la regió de factibilitat.