Programació lineal

La programació lineal (PL) és un mètode matemàtic per determinar una manera d'aconseguir el millor resultat (com, per exemple, el benefici màxim o el cost mínim) d'un cert model matemàtic donats una sèrie de requisits (restriccions) representats com relacions lineals. La programació lineal és un cas específic de la programació matemàtica (optimització matemàtica).

Més formalment, la programació lineal és una tècnica per l'optimització d'una funció objectiu lineal, subjecta a una igualtat lineal i restriccions en forma de desigualtats lineals. La seva regió factible és un políedre convex, que és un conjunt definit com la intersecció de molts (finits) semiespais, cadascun dels quals és definit per una desigualtat lineal. La seva funció objectiu és una funció afí de valors reals definida en aquest políedre. Un algorisme de programació lineal troba un punt del políedre en el qual aquesta funció té el menor (o major) valor, si existeix tal punt.

Els programes lineals són problemes que es poden expressar en la següent forma canònica:

{\begin{aligned}&{\text{maximitzar}}&&\mathbf {c} ^{\mathbf {T} }\mathbf {x} \\&{\text{amb la restricció}}&&A\mathbf {x} \leq \mathbf {b} \\&{\text{i}}&&\mathbf {x} \geq \mathbf {0} \end{aligned}}

x representa el vector de variables que es volen determinar; c i b són vectors de coeficients coneguts; a és una matriu de coeficients coneguts; i $(\cdot )^{\mathrm {T} }$ és la matriu transposada. L'expressió que es vol maximitzar o minimitzar s'anomena funció objectiu, en aquest cas c^Tx. Les desigualtats Ax ≤ b són les restriccions que configuren un polítop convex sobre el qual s'optimitza la funció objectiu. En aquest context, dos vectors són comparables quan tenen les mateixes dimensions. Si cada component del primer és menor o igual a la component corresponent del segon, llavors es pot dir que el primer vector és menor o igual al segon vector.

La programació lineal es pot aplicar a diversos camps d'estudi. Es fa servir en negocis i economia, però també es pot fer servir per resoldre alguns problemes de l'enginyeria. Algunes indústries que utilitzen models de programació lineal són, per exemple, la del transport, energia, telecomunicacions i fabricació. La programació lineal s'ha demostrat útil per modelar diversos tipus de problemes que tracten la planificació, el disseny de rutes, la programació d'horaris, l'assignació i el disseny.

Història

El problema consistent a resoldre un sistema de desigualtats lineals data, com a mínim, de l'època de Fourier,^[1] en honor del qual s'anomena el mètode de l'eliminació de Fourier-Motzkin. La primera programació lineal fou desenvolupada per Leonid Kantoròvitx el 1939^[2] per planejar les despeses i ingressos durant la Segona Guerra Mundial, per així reduir els costos de l'exèrcit i incrementar les pèrdues de l'enemic. El mètode fou mantingut en secret fins al 1947,^[3] quan George Dantzig va publicar el mètode símplex i John von Neumann va desenvolupar la teoria de la dualitat com una solució de l'optimització lineal, i l'aplicà en el camp de la teoria de jocs. Durant la postguerra, moltes indústries li van trobar utilitat per planejar el seu treball diari.

Kantoròvitx i Koopmans van compartir l'any 1975 el Premi Nobel d'Economia.^[1] El 1941, Frank Lauren Hitchcock també va formular els problemes de transport com a problemes de programació lineal i va donar una solució molt similar a la del mètode símplex posterior.^[2] Hitchcock va morir el 1957, i el premi Nobel mai no es dona pòstumament.

Des de 1946 a 1947 George B. Dantzig va desenvolupar independentment la formulació general de la programació lineal per utilitzar-la en problemes de planificació en les Forces Aèries. Al 1947, Dantzig també va inventar el mètode símplex que, per primer cop de forma eficient, resolia el problema de la programació lineal en la majoria de casos. Quan Dantzig va reunir-se amb John von Neumann per discutir el seu mètode símplex, Neumann de seguida va conjecturar la teoria de la dualitat notant que el problema en què havia estat treballant en teoria dels jocs era equivalent.^[4] Dantzig va proporcionar una demostració formal en un estudi no publicat sota el títol «A Theorem on Linear Inequalities» («Un teorema de desigualtat lineals») el 5 de gener de 1948.^[3] L'obra de Dantzig es va fer pública el 1951. En els anys de postguerra, moltes empreses van aplicar el seu mètode en la planificació diària.

El problema de la programació lineal es provà que era resoluble en un temps polinòmic per primer cop el 1979 gràcies a Leonid Khachiyan,^[5] però l'assoliment teòric i pràctic més gran en aquest camp va arribar el 1984, quan Narendra Karmarkar va introduir el mètode de punts interiors per resoldre problemes de programació lineal.^[6]

L'exemple original de Dantzig consistia a trobar la millor assignació per 70 persones en 70 treballs (oficis). La potència de computació necessària per provar totes les permutacions i poder escollir la millor assignació és gegant; el nombre de configuracions possibles excedeix el nombre de partícules de l'Univers observable. Tanmateix, només cal un moment per trobar la solució òptima si es planteja el problema com un problema de programació lineal i s'aplica l'algorisme símplex. La teoria darrere la programació lineal redueix dràsticament el nombre de possibles solucions òptimes que cal comprovar.

Ús

La programació lineal es considera del camp de l'optimització per diverses raons. Molts problemes pràctics en investigació operativa es poden expressar en forma de problemes de programació lineal. Certs casos especials de programació lineal, tals com els problemes de flux de xarxes, són considerats importants, ja que han generat molta recerca en algorismes especialitzar en la seva resolució. Alguns algorismes per altres tipus de problemes d'optimització fan servir problemes de PL per la seva resolució. Històricament, les idees al voltant de la programació lineal han inspirat molts dels conceptes centrals de la teoria d'optimització, tals com la dualitat, la descomposició i la importància de la convexitat. De la mateixa manera, la programació lineal es fa servir a bastament en microeconomia i organització d'empresa en temes com la planificació, producció, transport, tecnologia, etc.

Forma estàndard

La «forma estàndard» és la manera més intuïtiva i usual de descriure un problema de programació lineal. Consisteix en les següents tres parts:

Funció lineal que es vol maximitzar
per exemple, $f(x_{1},x_{2})=c_{1}x_{1}+c_{2}x_{2}$
Un cert nombre de restriccions
per exemple,
${\begin{matrix}a_{11}x_{1}+a_{12}x_{2}&\leq b_{1}\\a_{21}x_{1}+a_{22}x_{2}&\leq b_{2}\\a_{31}x_{1}+a_{32}x_{2}&\leq b_{3}\\\end{matrix}}$
Variables no negatives
per exemple,
${\begin{matrix}x_{1}\geq 0\\x_{2}\geq 0\end{matrix}}$

El problema se sol expressar en forma matricial, i llavors esdevé:

\max\{c^{\mathrm {T} }x\;|\;Ax\leq b\land x\geq 0\}

Altres formes tals com problemes de minimització, problemes amb restriccions de formes alternatives o problemes que comprenen variables negatives sempre es poden reescriure en una forma estàndard equivalent.

Exemple

Un agricultor té una extensió de terra d'una superfície de L km², i hi vol plantar blat, ordi o una combinació dels dos. L'agricultor té una quantitat limitada de fertilitzant, F quilograms, i també d'insecticida, P quilograms. Cada quilòmetre quadrat de blat requereix F₁ quilograms de fertilitzant, i P₁ quilograms d'insecticida; d'altra banda, cada quilòmetre quadrat d'ordi requereix F₂ quilograms de fertilitzant, i P₂ quilograms d'insecticida. Sigui S₁ el preu de venda del blat per quilòmetre quadrat, i S₂ el preu de venda de l'ordi per quilòmetre quadrat. Si es denota la superfície de terra plantada amb blat i ordi com x₁ i x₂ respectivament, llavors es pot maximitzar el benefici si s'escullen els valors òptims per x₁ i x₂. Aquest problema es pot expressar mitjançant el següent problema de programació lineal, en forma estàndard:

Maximitzar:	S₁x₁ + S₂x₂	(maximitzar els ingressos; els ingressos són la "funció objectiu")
Restriccions:	0 ≤ x₁ + x₂ ≤ L	(limitació de l'àrea total)
	0 ≤ F₁x₁ + F₂x₂ ≤ F	(limitació de fertilitzant)
	0 ≤ P₁x₁ + P₂x₂ ≤ P	(limitació d'insecticida)
Variables no negatives:	x₁ ≥ 0, x₂ ≥ 0	(no es pot plantar una àrea negativa)

En forma matricial, això esdevé:

Maximitzar

{\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}

Amb les restriccions

{\begin{bmatrix}0\\0\\0\end{bmatrix}}\leq {\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq {\begin{bmatrix}0\\0\end{bmatrix}}.

Mètode gràfic

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èrtexs i les fronteres de la regió factible

Una vegada s'ha dibuixat la regió factible, amb aquest procediment cal analitzar els vèrtexs 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 valor més gran.

2. Corbes de nivell

En aquest procediment es tracen diverses corbes de nivell per analitzar quines toquen els vèrtexs. 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'_x(x₀,y₀), f’_y(x₀,y₀)].

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èrtexs 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 veure que mitjançant el procediment d'anàlisi dels vèrtexs 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èrtexs d'aquesta, un altre mètode consisteix a 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 a 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).

Referències

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Programació lineal

↑ ^1,0 ^1,1 Sierksma, Gerard; Zwols, Yori. Linear and Integer Optimization: Theory and Practice, Third Edition (en anglès). Taylor & Francis, 2015-05-01, p. 1. ISBN 978-1-4987-1016-9.
↑ ^2,0 ^2,1 Schrijver, Alexander. Theory of Linear and Integer Programming (en anglès). John Wiley & Sons, 1998-06-11, p. 221-222. ISBN 978-0-471-98232-6.
↑ ^3,0 ^3,1 Dantzig, George B. «Reminiscences about the origins of linear programming». Operations Research Letters, 1, 2, 4-1982, pàg. 43–48. Arxivat de l'original el 20 maig 2015. DOI: 10.1016/0167-6377(82)90043-8.
↑ Dantzig, George B.; Thapa, Mukund Narain. Linear programming (en anglès). Nova York: Springer, 1997, p. xxvii. ISBN 0387948333. OCLC 35318475.
↑ Khachiyan, Leonid G. «Polynomial algorithms in linear programming» (en anglès). USSR Computational Mathematics and Mathematical Physics, 20, 1, 1-1980, pàg. 53–72. DOI: 10.1016/0041-5553(80)90061-0.
↑ Karmarkar, Narendra «A new polynomial-time algorithm for linear programming» (en anglès). Combinatorica, 4, 4, 12-1984, pàg. 373–395. DOI: 10.1007/BF02579150. ISSN: 0209-9683.

Vegeu també

[SierksmaZwols2015-1] 1,0 ^1,1 Sierksma, Gerard; Zwols, Yori. Linear and Integer Optimization: Theory and Practice, Third Edition (en anglès). Taylor & Francis, 2015-05-01, p. 1. ISBN 978-1-4987-1016-9.

[Schrijver1998-2] 2,0 ^2,1 Schrijver, Alexander. Theory of Linear and Integer Programming (en anglès). John Wiley & Sons, 1998-06-11, p. 221-222. ISBN 978-0-471-98232-6.

[dantzig1982-3] 3,0 ^3,1 Dantzig, George B. «Reminiscences about the origins of linear programming». Operations Research Letters, 1, 2, 4-1982, pàg. 43–48. Arxivat de l'original el 20 maig 2015. DOI: 10.1016/0167-6377(82)90043-8.

[:0-4] Dantzig, George B.; Thapa, Mukund Narain. Linear programming (en anglès). Nova York: Springer, 1997, p. xxvii. ISBN 0387948333. OCLC 35318475.

[khachiyan79-5] Khachiyan, Leonid G. «Polynomial algorithms in linear programming» (en anglès). USSR Computational Mathematics and Mathematical Physics, 20, 1, 1-1980, pàg. 53–72. DOI: 10.1016/0041-5553(80)90061-0.

[karmarkar84-6] Karmarkar, Narendra «A new polynomial-time algorithm for linear programming» (en anglès). Combinatorica, 4, 4, 12-1984, pàg. 373–395. DOI: 10.1007/BF02579150. ISSN: 0209-9683.

[1]

[2]

[3]

[4]

[5]

[6]