Tema 5: Optimització lineal amb restriccions de desigualtat (2014)

Apunte Catalán
Universidad Universidad Rovira y Virgili (URV)
Grado Administración y Dirección de Empresas - 1º curso
Asignatura Matemàtiques 2
Año del apunte 2014
Páginas 25
Fecha de subida 02/09/2014
Descargas 8
Subido por

Descripción

Descripció del problema,Mètode gràfic,L'algoritme del símplex,Anàlisi de sensibilitat

Vista previa del texto

Tema 5: Optimització lineal amb restriccions de desigualtat 5.1 Descripció del problema L’optimització amb restriccions de desigualtat és molt més recent, comparat amb l’optimització vista fins ara. Aquest tipus de problemes ens permeten aproximar-nos matemàticament més a la realitat, ja que no limiten tant intensament les restriccions de les nostres variables.
Per exemple, podem emplenar un magatzem amb diversos béns, però, pot ser que l’espai d’aquest no estigui del tot ocupat; és més, l’ocupació total dels béns pot ser des d’estar buit fins a la seva màxima capacitat.
Hi ha molts tipus de funcions, unes més complexes que d’altres. En aquest apartat, ens centrarem amb l’optimització de funcions lineals, en el que s’anomena programació lineal.
La programació lineal s’empra per assignar recursos, planificar-ne la producció, l’horari de treballadors, la cartera d’inversions, i per formular estratègies de mercat (i militars). La versatilitat i l’impacte econòmic de la programació lineal en el món industrial actual són realment impressionants. (E. Lawler, 1980) Així doncs, el tipus de problema a tractar serà el següent: on les funcions f, funció objectiu i g, restriccions, estan definides de R n a R, i les b són constants de R.
53 Llúcia Mauri Masdeu Matricialment aquest problema s’expressa de la manera següent: Opt. CX s.a. AX )b X *0 On C i b són vectors, A és una matriu i X representa les n variables.
Per solucionar aquest tipus de problemes hi ha molts mètodes diversos, tots igualment vàlids.
5.2 Mètode gràfic Aquest mètode és molt senzill i visual. Funciona molt bé en problemes de programació lineal amb dos variables, però, si aquestes en són més, ja no és tan eficient.
Vegem-ne un exemple per poder contrastar-ho: Exemples: 1) Imatge 24 54 Matemàtiques II Imatge 25 Vèrtexs (a,b) Valor de la funció f(x,y) (0,0) (40,0) (20,30) (0,40) 0 800 850 600 Veiem que el màxim s’assoleix al punt (20,30).
2) Imatge 26 55 Llúcia Mauri Masdeu Imatge 27 Vèrtexs (a,b) Valor de la funció f(x,y) (0,0) 0 (10,0) 30 Veiem que el mínim s’assoleix al punt (0,0).
5.3 L'algoritme del símplex ALGORITME DEL SÍMPLEX FASE D'INICIACIÓ FASE D'ITERACIÓ FASE DE DETENCIÓ 56 (5,5) 40 (0,20/3) 100/3 Matemàtiques II Conceptes previs Regió admissible, conjunt factible o regió de solucions possibles: És el conjunt de tots els punts factibles d’un problema de programació lineal.
Punt factible: Un punt (x1,...xn) és factible si aquest es troba en la regió admissible o conjunt factible. És a dir, compleix totes les restriccions i, a més a més, totes les seves components són positives.
Vèrtex o vèrtex factible: Un punt (x1,...xn) factible que es troba en un dels vèrtexs de la regió admissible o conjunt factible. És a dir, compleix totes les desigualtats i almenys dues donant lloc a la igualtat i, a més a més, les seves components són positives.
Solució òptima: Un punt (x1,...xn) és solució òptima quan compleix totes les restriccions i, a més a més, és un màxim o mínim global de la funció objectiu.
Valor òptim: És el valor que s’obté quan s’avalua la solució òptima en la funció objectiu.
Vèrtex òptim: Un punt (x1,...xn) que és un vèrtex o vèrtex factible i, a més a més, és solució òptima del problema.
Propietats dels problemes lineals t El conjunt de solucions possibles d’un problema de programació lineal és convex.
t La funció objectiu és contínua i amb totes les seves derivades parcials de tots els ordres contínues. A més a més, és una funció còncava i convexa alhora.
t Es verifica que els òptims d’un problema de programació lineal sempre són globals, tant en els problemes de maximització com de minimització. A més a més, el conjunt de solucions òptimes és un conjunt convex.
t Les condicions necessàries d’optimitat també són suficients.
Fase d’iniciació En aquesta fase es transforma el problema donat en la forma estàndard o ampliada.
El problema a resoldre és el següent: Opt. f(x) s.a. g(x) )b x DRn 57 Llúcia Mauri Masdeu Per estandarditzar el problema: t&MQSPCMFNBIBEFTUBSFYQSFTTBUDPNVOQSPCMFNBEFNBYJNJU[BDJØ4JFMQSPblema inicial és de minimització, el que farem és maximitzar l’oposat; és a dir, canviar de signe la funció objectiu.
Exemples: 1) Aquest problema ja està llest per maximitzar. Per tant, no caldria fer-li cap modificació, de moment.
2) Aquest problema és de minimització. Per tant, per estandarditzar-lo hem de maximitzar l’oposat: t&MUFSNFJOEFQFOEFOUEFDBEBSFTUSJDDJØIBEFTFSQPTJUJV&ODBTRVFOPIPTJHVJ IFNEFNVMUJQMJDBSQFS¦MBSFTUSJDDJØ Exemples: 1) 58 Matemàtiques II Observem que el terme independent de la primera restricció és negatiu. Per tant, IFNEFNVMUJQMJDBSQFS¦ TPMBNFOUBRVFTUBSFTUSJDDJØ 2) Fixem-nos que en aquest exemple hem de maximitzar l’oposat i hem de multipliDBSQFS¦MBTFHPOBSFTUSJDDJØ1FSUBOU FOTRVFEBSË t$POWFSUJSMFTSFTUSJDDJPOTEFEFTJHVBMUBUFOJHVBMUBU UPUBGFHJOUWBSJBCMFTEFTFQBració o addicionals (folgances), aquestes sempre positives. S’afegiran sumant o restant segons sigui la restricció ) o *, respectivament. També cal tenir en compte que aquestes variables de separació s’afegiran a la funció objectiu amb coeficient zero.
Exemples: 1) 59 Llúcia Mauri Masdeu Observem que el problema ja compleix els dos punts anteriors. Per tant, anem a convertir les desigualtats en igualtats: 2) 'JYFNOPTRVFIFNEFNBYJNJU[BSMPQPTBU BNÏTIFNEFNVMUJQMJDBSQFS¦MB primera restricció i, posteriorment, haurem de convertir les desigualtats en igualtats.
Així doncs, ens quedarà: t-FTWBSJBCMFTOFHBUJWFT xi ) 0) les substituirem de la manera següent: xi = –x'i , on x'i * 0. (Això tant a les restriccions com a la funció objectiu.) Exemple: 1) Observem que hem de convertir les desigualtats en igualtats i, posteriorment, hem de substituir la variable negativa per una de positiva canviada de signe. Per tant, ens quedarà: 60 Matemàtiques II t-FTWBSJBCMFTRVFOPUJOHVJOSFTUSJDDJØEFTJHOFTFTVCTUJUVJSBOEFMBNBOFSBTF, on . (Això tant a les restriccions com a la funció objectiu.) güent: Exemple: 1) Observem que hem de convertir les desigualtats en igualtats i, posteriorment, .
hem de substituir la variable y, que no té restricció de signe per t6ODPQFTDSJUFMQSPCMFNBFOGPSNBFTUËOEBSE TFHVJOUUPUTFMTBQBSUBUTBOUFSJPST  es busca a les restriccions una base canònica de R m , on m és el nombre de restriccions.
Normalment aquesta base canònica vindrà donada per les variables de separació. Si no tenim aquesta base canònica, s’afegiran noves variables, que les anomenarem variables artificials, tot sumant-les a la restricció necessària per tal d’obtenir la base canònica.
Aquestes s’inclouen a la funció objectiu amb coeficient –w, on w > 0 i arbitràriament gran per tal que no afecti el màxim.
(Aquest punt es reflecteix més clarament amb els exemples de continuació.) Finalment, posem totes les dades en forma de taula: Coef v.b.
x1 ....
xj ....
xs B c1 x2 a11 ...
a1j ...
a1s b1 c2 x2 a21 ....
a2j ...
a2s b2 Ӈ Ӈ Ӈ Ӈ Ӈ Ӈ Ӈ Ӈ cm xm am1 ....
...
ams bm z1–c1 ...
...
zs–cs z* zj–cj 61 Llúcia Mauri Masdeu On: t Les c són els coeficients de les variables x a la funció objectiu.
t Les a són els coeficients de les variables x a les restriccions.
t Les b són els termes independents de cadascuna de les restriccions.
t La z* és el valor de la funció objectiu en el punt solució, quan es maximitza i –z* quan es minimitza.
t La columna v.b. és la columna de les variables bàsiques.
t La columna Coef és la columna dels coeficients de les variables bàsiques.
t Les z segueixen l’expressió següent: És a dir, el producte del coeficients de les variables bàsiques v.b. en la funció objectiu (primera columna Coef) pels coeficients de la columna de la xj corresponent.
Vegem-ho amb dos exemples: Exemples: 1) Estandarditzem el programa: Emplenem la taula del símplex: 62 Matemàtiques II Observem que: Càlcul dels termes zj–cj : Tenim una base canònica de R2 a les restriccions.
El valor z* és el següent: 63 Llúcia Mauri Masdeu I tota la resta de variables amb valor 0.
Per tant, z* = O directament multiplicant els Coef amb els elements de B i, posteriorment, sumar-los.
2) Estandarditzem el programa: Emplenem la taula del símplex: Càlcul dels termes zj–cj : 64 Matemàtiques II  2  z3 c 3 =  c k ak 3 c 3 = w 0 + 0 1 5 = 5   k =1  Tenim una base canònica de R 2 a les restriccions, ja que hem afegit una variable artificial c i ho hem inclòs a la funció objectiu amb coeficient –w.
El valor z* és el següent: I tota la resta de variables amb valor 0.
Per tant, z* = O directament multiplicant els Coef amb els elements de B i, posteriorment, sumar-los.
Fase d’iteració Un cop tenim el programa estandarditzat i la taula del símplex emplenada, procedim a efectuar recursivament una sèrie de càlculs fins complir unes certes condicions.
65 Llúcia Mauri Masdeu 1. Determinació de la variable no bàsica que passarà a ser bàsica.
A l’última fila de la taula del símplex, busquem el menor nombre negatiu.
(Si n’hi ha dos d’iguals qualsevol d’aquests anirà bé.) Això ens determina la selecció d’una columna k i, per tant, la variable no bàsica que passarà a ser bàsica.
2. Determinació de la variable bàsica que passarà a ser no bàsica.
t Considerem tots els coeficients positius de la columna k seleccionada ai k 0.
.
t Calculem els quocients t El menor d’aquests quocients ens indicarà la fila h, aquesta ens determina la variable bàsica que passarà a ser no bàsica.
L’element ah k, corresponent a l’encreuament de la fila h i la columna k seleccionades s’anomena pivot (sempre positiu).
3. Gauss.
L’objectiu serà convertir el pivot en el nombre 1 i la resta de coeficients de la columna amb zeros.
Per fer-ho, dividirem per ah k tots els coeficients de la fila on es trobi el pivot. A continuació, modificarem les altres files de la manera següent: Coeficient de la fila – Constant · Coeficient de la nova fila pivot.
Tal que la constant serà la que ens faci zero l’expressió anterior en tota la columna del pivot. És a dir, serà el coeficient ai k.
Mentre no es doni cap condició de detenció tornarem a començar el procés.
Fase de detenció L’algoritme finalitzarà quan: t Tots els elements de l’última fila siguin no negatius (els zi–ci * 0), o bé, t en el cas que algun element de l’última fila sigui negatiu (zk–ck  0); llavors, la resta de valors de la seva columna són negatius o zero (els ai k )0).
66 Matemàtiques II Interpretació de la taula del símplex Les variables bàsiques prenen el valor corresponent de la columna B. La resta de variables prenen el valor zero. I d’aquí extraiem el punt òptim.
El valor de la funció objectiu en el punt òptim es troba a la casella z* en cas de maximitzar i –z* en cas de minimitzar.
Vegem aquestes dues fases seguint els dos exemples anteriors: Exemples: Prenent el programa estandarditzat: Taula del símplex: Coef v.b.
x y z t u B 0 t 3 1 ¦ 1 0 10 0 u 1 1 ¦ 0 1 50 ¦ ¦ 40 0 0 0 &MNFOPSOPNCSFOFHBUJVEFMÞMUJNBmMBÏTFM¦J QFSUBOU DPOTJEFSFNUPUT els coeficients positius de la columna seleccionada. Tot seguit, calculem el quocient següent i escollim el mínim: Per tant, el pivot serà el 3.
67 Llúcia Mauri Masdeu Coef v.b.
x y z t u B 0 t 3 1 ¦ 1 0 10 0 u 1 1 ¦ 0 1 50 ¦ ¦ 40 0 0 0 Ara dividim el 3 entre 3 per tal de transformar-lo en un 1. I, per tant, també haurem de dividir tota la fila entre 3. I la variable no bàsica que passarà a ser bàsica serà la x, i la bàsica que passarà a ser no bàsica serà la t.
Ara farem zero tots els coeficients de la columna de la variable x: 'JMB'JMB¦  r'JMB Evidentment, això afectarà tots els coeficients de la fila. I, posteriorment, els càlculs de l’última fila, els zi–ci.
Segona taula del símplex: Coef v.b.
x y 36 x 1 1 3 0 u 0 2 3 0 ¦ z t u 1 3 0  2 3 140 3 1 140 3 28 12 0 120  – B Observem que no compleix cap condició de detenció. Per tant, tornem a la fase d’iteració: &MNFOPSOPNCSFOFHBUJVEFMÞMUJNBmMBÏTFM¦J QFSUBOU DPOTJEFSFNUPUTFMT coeficients positius de la columna seleccionada. Tot seguit, calculem el quocient següent i escollim el mínim: 68 Matemàtiques II Per tant, el pivot serà el 1 .
3 Coef v.b.
x y 36 x 3 1 3 0 u 0 2 3 0 ¦ 1 z t  28 u B  0  140 3 1 140 3 12 0 120 1 Ara dividim el entre (que és el mateix que multiplicar per 3), per tal de trans3 3 1 formar-lo en un 1. I, per tant, també haurem de dividir tota la fila entre (o multiplicar 3 per 3). I la variable no bàsica que passarà a ser bàsica serà la y i la bàsica que passarà a ser no bàsica serà la x: Ara farem zero tots els coeficients de la columna de la variable y: Fila 2 = Fila 2   Fila 1 Evidentment, això afectarà tots els coeficients de la fila. I, posteriorment, els càlculs de l’última fila, els zi–ci.
Tercera taula del símplex: Coef v.b.
x y z t u B 20 y 3 1 ¦ 1 0 10 0 u ¦ 0 0 ¦ 1 40 24 0 20 20 0 200 Observem que compleix la primera condició de detenció. Per tant, ja haurem acabat.
Per tant, el punt òptim serà el y = 10, u = 40 i la resta de variables, zero. Per tant, el punt (0,10,0) és el màxim global i el valor de la funció en aquest punt és z* = 200.
69 Llúcia Mauri Masdeu 2) Prenem el programa estandarditzat: Taula del símplex: Coef v.b.
x y z t u c B ¦X c 1 2 0 ¦ 0 1 6 0 u 1 1 1 0 1 0 10 ¦X¦ ¦X¦ -5 w 0 0 ¦X &MNFOPSOPNCSFOFHBUJVEFMÞMUJNBmMBÏTFM¦X¦ MB w és una constant positiva arbitràriament gran) i, per tant, considerem tots els coeficients positius de la columna seleccionada. Tot seguit, calculem el quocient següent i escollim el mínim: Per tant, el pivot serà el 2.
Coef v.b.
x y z t u c B ¦X c 1 2 0 ¦ 0 1 6 0 u 1 1 1 0 1 0 10 ¦X¦ ¦X¦ ¦ w 0 0 ¦X Ara dividim el 2 entre 2 per tal de transformar-lo en un 1. I, per tant, també haurem de dividir tota la fila entre 2. I la variable no bàsica que passarà a ser bàsica serà la y i la bàsica que passarà a ser no bàsica serà la c.
70 Matemàtiques II Ara farem zero tots els coeficients de la columna de la variable y: 'JMB'JMB¦  r'JMB Evidentment, això afectarà tots els coeficients de la fila. I, posteriorment, els càlculs de l’última fila, els zi–ci.
Segona taula del símplex: Coef v.b.
x y z t u 2 y 1 2 1 0 0 u 1 2 0 1 1 2 1 ¦ 0 ¦ ¦ 0 c B  0 3 7 1+w 6 Observem que no compleix cap condició de detenció. Per tant, tornem a la fase d’iteració: &MNFOPSOPNCSFOFHBUJVEFMÞMUJNBmMBÏTFM¦J QFSUBOU DPOTJEFSFNUPUTFMT coeficients positius de la columna seleccionada, fixem-nos que sols n’hi ha un. Per tant, no caldrà efectuar-lo.
el càlcul del mínim del quocient Per tant, el pivot serà l’1.
Coef v.b.
x y z 2 y 1 2 1 0 0 u 1 2 0 1 1 2 1 ¦ 0 ¦ ¦ 0 71 t 1 2 u c B 0 1 2 3 7 1+w 6 Llúcia Mauri Masdeu Ara ja tenim el pivot 1; per tant, no caldrà fer res. I la variable no bàsica que passarà a ser bàsica serà la z i la bàsica que passarà a ser no bàsica serà la u.
Tampoc caldrà fer zero tots els coeficients de la columna de la variable z, perquè ja està.
Posteriorment, sí que caldrà calcular l’última fila, els zi–ci.
Segona taula del símplex: Coef v.b.
x y z t u 2 y 1 2 1 0 5 z 1 2 0 1 1 2 1 3 2 0 0 3 2 5 c B  0 3 7 ¦ 3 +w 2 41 Observem que compleix la primera condició de detenció. Per tant, ja haurem acabat.
Per tant, el punt òptim serà el y = 3, z = 7 i la resta de variables, zero. Per tant, el QVOU    ÏTFMNÓOJNHMPCBMJFMWBMPSEFMBGVODJØFOBRVFTUQVOUÏT¦z ¦ Tipologia de solucions Després d’aplicar l’algoritme del símplex en un problema de programació lineal, ens podem trobar amb aquestes situacions: Inexistència de solució factible: Si hi ha alguna variable artificial bàsica; és a dir, amb valor positiu. Gràficament tindríem la regió admissible buida, ja que cap punt verificaria totes les restriccions.
Inexistència de solució òptima (solució no limitada): Si en obtenir una solució bàsica (sense cap variable artificial bàsica), per a alguna columna zj – cj 0 i aij )0, és a dir, compleix la segona condició de la fase de detenció.
Gràficament tindríem la regió admissible no buida, però la solució no estaria fitada. Tot i que pot passar no tenir la regió admissible limitada, però la solució sí.
72 Matemàtiques II Solució òptima múltiple no fitada: Si obtenim la solució complint la primera condició de la fase de detenció, però, alguna variable no bàsica té associat el valor zk – ck =0 i tots els valors aik )0 en la seva columna. Gràficament tots els punts d’una aresta de la regió admissible tenen el mateix valor objectiu, i en el cas que la regió admissible no estigui limitada, aquests punts seran òptims.
Solució òptima múltiple fitada: Si obtenim la solució complint la primera condició de la fase de detenció, però, alguna variable no bàsica té associat el valor zk – ck =0 i hi ha algun valor aik 0 en la seva columna. Si haguéssim introduït aquesta variable en la nostra base canònica obtindríem un altre punt òptim (amb el mateix valor en la funció objectiu que l’anteriorment trobat). Gràficament obtindríem dos punts com a òptims amb el mateix valor en la funció objectiu; llavors, l’òptim de la funció objectiu s’assoliria en tots els punts del segment que uneix aquests dos punts. Per tant, tindríem tantes solucions com punts en el segment.
Solució òptima única: Quan no es dóna cap dels casos anteriors, és a dir, obtenim la solució complint la primera condició de la fase de detenció i no tenim cap variable artificial com a bàsica. A més a més, la quantitat de zj – cj =0 coincideix exactament amb el nombre de restriccions.
5.4 Anàlisi de sensibilitat A més a més de resoldre la problemàtica de maximitzar o minimitzar una funció amb restriccions de desigualtat, ens interessa saber com li afecten petites variacions en el terme independent de cadascuna de les restriccions.
Si tenim un problema d’optimització amb restriccions de desigualtat com el següent: 73 Llúcia Mauri Masdeu Llavors, la fórmula que ens relaciona la variació del valor de la funció objectiu amb la variació (variacions petites) del terme independent i-èsim és la següent: Per estudiar aquesta sensibilitat en els diferents problemes d’optimització plantejats fent ús de l’algoritme del símplex necessitarem saber el valor dels multiplicadors de Lagrange. Però com trobar-los? Vegem-ho amb dos exemples.
Per no perdre homogeneïtat, prendrem els dos exemples tractats en aquesta unitat.
Exemples: 1) Tenim el problema següent: Aplicant l’algoritme del símplex havíem obtingut la solució: Coef v.b.
x y z t u B 20 y 3 1 ¦ 1 0 10 0 u ¦ 0 0 ¦ 1 40 24 0 20 20 0 200 per al qual determinàvem que el màxim global era el punt (0,10,0) amb valor a la funció objectiu 200.
Com trobar els multiplicadors de Lagrange respectius a cada restricció? Recordem quines eren les primeres variables bàsiques (les de la base canònica): Fixem-nos que la variable bàsica de la primera línea, la t, serà la que ens ajudarà a obtenir el multiplicador de Lagrange de la primera restricció.
74 Matemàtiques II Conseqüentment, la variable bàsica de la segona línea, la u, serà la que ens ajudarà a obtenir el multiplicador de Lagrange de la segona restricció. I així tantes línies com restriccions, seguint l’ordre establert.
Així doncs, prenent l’última taula de l’algoritme del símplex: hi = zi hi = –zi (Quan es tracta d’un problema de maximització) (Quan es tracta d’un problema de minimització) Per tant: i .
Llavors, si augmentem el terme independent de la primera restricció una unitat (11), el valor de la funció objectiu al màxim serà 220 i si el disminuïm una unitat (9), el valor de la funció objectiu al màxim serà 180. En canvi, qualsevol variació del terme independent de la segona restricció no afectarà el valor de la funció objectiu en el màxim.
2) Tenim el problema següent: 75 Llúcia Mauri Masdeu Aplicant l’algoritme del símplex havíem obtingut la solució: Coef v.b.
2 y 5 z x y z 1 0 1 2 0 1 1 2 1 3 2 0 0 3 2 5  t u c B 0 1 2 3 7 3 ¦ +w 2 41 pel qual determinàvem que el mínim global era el punt (0,3,7) amb valor a la funció PCKFDUJV¦ Com trobar els multiplicadors de Lagrange respectius a cada restricció? Recordem quines eren les primeres variables bàsiques (les de la base canònica): Fixem-nos que la variable bàsica de la primera línea, la c, serà la que ens ajudarà a obtenir el multiplicador de Lagrange de la primera restricció.
Conseqüentment, la variable bàsica de la segona línea, la u, serà la que ens ajudarà a obtenir el multiplicador de Lagrange de la segona restricció.
I així tantes línies com restriccions, seguint l’ordre establert.
Així doncs, prenent l’última taula de l’algoritme del símplex: hi = zi hi = –zi (Quan es tracta d’un problema de maximització) (Quan es tracta d’un problema de minimització) 76 Matemàtiques II Per tant: i .
Llavors, si augmentem el terme independent de la primera restricció una unitat (7) el valor de la funció objectiu al mínim serà valor de la funció objectiu al mínim serà , i si el disminuïm una unitat (5) el . En canvi, si augmentem el terme inde- QFOEFOUEFMBTFHPOBSFTUSJDDJØVOBVOJUBU  FMWBMPSEFMBGVODJØPCKFDUJVTFS˦J TJFMEJTNJOVÕNVOBVOJUBU  FMWBMPSEFMBGVODJØPCKFDUJVBMNÓOJNTFS˦ 77 ...