Teorema de Weierstrass y optimización convexa
Teorema de Weierstrass
Siga f: S ⊆ Rn // Si S és compacte (tancat i acotat) i no buit (almenys un punt interior factible) i f és contínua en S, llavors f assoleix almenys un màxim i un mínim global a l'interior o la frontera de S.
-continua és perquè la F(X) és un polinomi
-tancat és perquè el S està definit mitjançant restriccions =,=,amb funcions continues (polinomis)
per resoldre
-un conjunt S(Rn és convexe si al unir 2 qualsevol de els seus punts amb un segment aquest no surt del conjunt.
els hiperplans i semiespaços són conjunts convexos (cx+cx = @)
Kuhn y Tucker: 1. Factibilitat: (almenys un punt interior). 2. Punt crític: (parcial i ,=0) 3. Signe: MAX-> r.cano g(x)=0->¡=0 // no canònica g(x)=0->¡=0 . ((en MIN tot al revés) 4. Holgura complementària: a partir de L igualem a 0 restriccions amb multiplicadors.
-Si et donaren un punt els passos serien: factibilitat, holgura, punt crític, signe
-CONDICIÓ SUFICIENT DE K.T: problema tal que totes les f(x) siguin de classe c2 i S convex :
- f convexa (min) = tot punt kt és mínim global
- f estrictament convexa (min) = tot punt kt és un mínim global únic
- f concava (max) = tot punt kt és un màxim global
- f estrictament concava (max) = tot punt kt és un màxim global únic
-TEOREMA LOCAL-GLOBAL: (S=CONVEXE, SI ÉS LINEAL SMP)
- Si la F(X) és convexa, tot mínim local del problema és un mínim global.
- si la F(X) és concava, tot màxim local del problema és un màxim global.
ESTUDIO CONCAVIDAD O CONVEXIDAD FUNCIÖN.- Tota funció lineal és a la vegada concava i convexa - Si la funció és no lineal, calcularem la seua hessiana.- si la hessiana dóna matriu diagonal :
- si els coeficients de la diagonal de H són = 0 tots, la funció f és còncava (i si són tots < 0 és estrictament còncava)
- si els coeficients de la diagonal de H són =0 tpts, la funció f és convexa (i si són tots >0 és estrictament convexa)
-si no es tracta d'una matriu diagonal:primerament calcularem el determinant de la matriu hessiana :
- si és diferent de 0 basta con calcular els menors principals conduents de la matriu (H1,H12,H123..)
- si tots els menors principals condu són > 0, entonces H és definida positiva i la funció és estrictament convexa.
- si els menors principals conduents alternen el signe començant en negatiu (H1<0,H12<0..) entonces H és definida negativa i la funció és estrictament còncava.
- si és igual a 0 el det de H calcularem tots els menors principals de la matriu.
- si tots els menors principals són =0 entonces H és semidefinida positiva i la funció és convexa
- si els menors de orden 1 són =0, els de orden 2 (taxes els de la diagonal en 3*3) són =0, els de orden 3=0...
- començant amb negatiu, entonces H és semidefinida negativa i la funció és còncava
Solució bàsica aquella que té com a màxim m variables no nul·les que verifiquen Ax=b
Solució factible bàsica és tota solució que a més de ser bàsica és factible, és a dir, solució bàsica que compleix x≥0
Teoremes Fonamentals
Teorema 1 Si la funció objectiu assoleix un òptim, aquest òptim s'obté sempre en un punt extrem
Teorema 2 Si la funció objectiu assoleix l'òptim en més d'un punt extrem, llavors també són solució totes les combinacions lineals d'aquests punts extrems
Teorema de Equivalència entre SFB i punt extrem Un punt x és punt extrem del conjunt d'oportunitats sii x és una solució factible bàsica
Teorema fonamental de la programació lineal
a) Si hi ha una solució factible, hi ha un solució factible bàsica.
b) Si hi ha una solució factible òptima, hi ha una solució factible bàsica òptima.
Teorema 1 Si la funció objectiu assoleix un òptim, aquest òptim s'obté sempre en un punt extrem
Teorema 2 Si la funció objectiu assoleix l'òptim en més d'un punt extrem, llavors també són solució totes les combinacions lineals d'aquests punts extrems
Teorema de Equivalència entre SFB i punt extrem Un punt x és punt extrem del conjunt d'oportunitats sii x és una solució factible bàsica
Teorema fonamental de la programació lineal
a) Si hi ha una solució factible, hi ha un solució factible bàsica.
b) Si hi ha una solució factible òptima, hi ha una solució factible bàsica òptima.
SIMPLEX
y=B-1*A ,XB= B-1*b, F=CtB * XB , Z=CtB * Y , Wj = en ma tenen q ser menors q 0 per a una SFB optima i en min al reves.
VB-> Wj=0 VNB -> WJ= Variació que experimenta la f obj. si la variable passa a ser bàsica amb valor unitari.
PER A Q SIGA OPTIMA LA SOLUCIO. vnb=0 i vb mirem xb q tenen q ser positius.
-En el cas que no siga optima la solucio aplicarem 2 criteris:
CRITERI D'ENTRADA: elegir una vnb per a q passe a ser vb i millore el valor de la funcio obj.
- per max. entra la variable amb major rendiment marginal positiu
- per a min entra la variable amb menor rendiment marginal negatiu
CRITERI EIXIDA: elegir una vb per a que passe a ser vnb i millore el valor de la f obj.
- sols poden deixar de ser vb les v que tinguin un nº positiu en la corresponent columna de la v que entra.
- ix la variable que fa mínim el coeficient entre el seu valor i el número positiu que hi ha en la columna
TIPOS DE SOLUCIONES
- SOLUCION UNICA: tabla és òptima i en wj les vnb són diferents a 0
- SOLUCION DE ARISTA FINITA: tabla òptima però en wj alguna vnb =0 (faríem criteri entrada e eixida i podria
- SOLUCION DE ARISTA INFINITA : tabla sfb òptima però alguna vnb=0 (faríem criteri entrada però no podria eixir cap
- PROBLEMA NO ACOTADO : si en qualsevol tabla alguna vnb compleix criteri d'entrada i cap pot eixir