Programació lineal: diferència entre les revisions
Contingut suprimit Contingut afegit
→Vegeu també: Problema del recobriment |
|||
Línia 3:
La '''programació lineal''' és una tècnica [[matemàtica]] bastant recent que és emprada en àmbits sobretot de resolució de problemes socials. Ens centrarem en aquest tema però només amb problemes simples que consten només de 2 variables, són anomenats problemes bidimensionals.
==
La programació lineal és un mètode o algoritme matemàtic que s’utilitza per optimitzar una funció lineal subjecta a ''M'' restriccions que s’expressen en forma de sistema d’inequacions.
Aquest sistema va ser ideat als anys 40 George Dantzig, [[John Von Neumann]], que va desenvolupar la teoria de la dualitat, i [[Leonid Kantoròvitx]] durant la segona Guerra Mundial. L’objectiu d’aquesta tècnica era reduir (minimitzar) els costos de l’exèrcit dels Estats Units aconseguint incrementar (maximitzar) la posició envers l’enemic.
El sistema de la programació lineal s’utilitza sobretot en l’àmbit econòmic per maximitzar beneficis o reduir costos assumint els recursos com a béns limitats.
== Mètode gràfic ==
Els problemes que es plantegen consten de:
*''N'' variables: incògnites del problema
*''M'' restriccions: limitacions dels béns i recursos a les que estan subjectes les variables
*Funció objectiu que obtenim a partir de les N variables que voldrem maximitzar o minimitzar
*Regió factible: conjunt solució determinat per les M restriccions. Qualsevol punt fora de la regió no serà admès com a solució del problema.
Per iniciar la resolució del problema s’han de dibuixar les restriccions al pla i determinar la regió factible, on hi trobarem el punt solució. El punt solució sempre estarà dins la regió factible.
'''
Existeixen 3 mètodes de resolució gràfica:'''
'''1. Anàlisi dels vèrtex i les fronteres de la regió factible'''
Una vegada s’ha dibuixat la regió factible, amb aquest procediment cal analitzar els vèrtex i les fronteres. Seleccionem els diversos punts i substituïm els valors (x,y) a la funció objectiu. Si volem minimitzar la funció agafem el punt amb el valor menor, i si volem maximitzar la funció agafem aquell amb el major valor.
'''2. Corbes de nivell'''
En aquest procediment es tracen diverses corbes de nivell per analitzar quines toquen els vèrtex. Una vegada estan dibuixades, s’analitza quina és la més alta o la més baixa, depenent de si la funció objectiu ha ser un màxim o un mínim.
'''3. Gradient'''
En aquest mètode s’ha de traçar la corba de nivell 0, que passa pel punt (0,0), per tal de traçar-hi el gradient. El gradient indica la direcció de màxim creixement. Si optimitzem amb un màxim buscarem el vèrtex en la direcció del gradient i si optimitzem amb un mínim agafarem el vèrtex en la direcció contrària al gradient [-(f'<sub>x</sub>(x<sub>0</sub>,y<sub>0</sub>), f’<sub>y</sub>(x<sub>0</sub>,y<sub>0</sub>)].
== Exemple d'un problema de programació lineal ==
'''Enunciat'''
Es demana maximitzar el benefici de la següent funció (funció objectiu):
'''F(x,y)= 8x + 9y'''
Subjecte a les següents restriccions:
'''x + 2y <= 8'''
'''2x + 3y <= 13'''
'''x + y <= 6'''
'''x , y >= 0'''
Per resoldre aquest problema utilitzarem la programació lineal, de manera que resoldrem l'exercici mitjançant els 3 mètodes explicats anteriorment.
'''Mètode 1:'''
Un cop dibuixada la regió factible en el gràfic x, y, busquem els punts on s'interseccionen les restriccions, és a dir, els vèrtex d’aquesta regió factible.
*Sabem, observant el gràfic, que dos d’ells són (0,4) i (6,0) que es corresponen amb la intersecció de dues de les restriccions amb els eixos de coordenades.
Els altres dos punts els trobem resolent el sistema resultant de la intersecció de les dues rectes corresponents.
*En el cas del punt (2,3) es correspondria amb la intersecció de les rectes '''2x + 3y = 13''' i '''x + 2y = 8'''.
*En quant del punt (5,1), aquest es correspon amb la intersecció de les rectes '''2x + 3y = 13''' i '''x + y = 6'''.
Seguidament estudiarem el valor de la funció objectiu que pretenem maximitzar en els punts candidats:
'''F(0,4) = 8•0 + 9•4 = 36'''
'''F(2,3) = 8•2 + 9•3 = 43'''
'''F(5,1) = 8•5 + 9•1 = 49'''
'''F(6,0) = 8•6 + 9•0 = 48'''
Podem observar que mitjançant el procediment d’anàlisi dels vèrtex candidats, la funció objectiu assoleix el seu màxim (en la regió factible) en el punt (5,1), amb un valor de '''49'''.
'''Mètode 2'''
Un cop dibuixada la regió factible i trobats els vèrtex d’aquesta, un altre mètode consisteix en dibuixar les corbes de nivell (f(x,y)=k) corresponents a la funció objectiu. Com podem comprovar en el gràfic, el punt (5,1) és el punt de la regió factible intersecat per la corba de nivell més alta (línia groga ), per tant, podem afirmar que la funció assoleix el seu valor màxim en el punt (5,1). Per trobar aquest valor substituirem les coordenades del punt a la funció objectiu, tal com hem fet en el mètode 1:
'''F(5,1) = 8•5 + 9•1 = 49'''
'''Mètode 3'''
El mètode 3 és molt similar al mètode 2, però més senzill i pràctic. Consisteix en representar en el gràfic una de les corbes de nivell (generalment la corba de nivell F(x,y)=k=0) i mitjançant les derivades parcials, representar també el gradient de F(x,y). El gradient indica la direcció de màxim creixement de la funció, per tant, no caldrà representar totes les corbes de nivell. Com podem observar en el gràfic, la corba de nivell més alta que talla la regió factible es troba en el punt (5,1).
== Resolució de problemes ==
| |||