Programació llineal

La programació llineal (LP, també coneguda com a optimisació llineal) és el camp de la programació matemàtica dedicat a maximizar o minimisar (optimisar) una funció llineal, denominada funció objectiu, de tal forma que les variables de dita funció estiguen subjectes a una série de restriccions expressades per mig d'un sistema d'equacions o inecuaciones també llineals. El método tradicionalment usat per a resoldre problemes de programació llineal és el Método Simplex.

Els programes llineals són problemes que poden ser expressats en la seua forma canònica com

$\begin{array}{cc}\text{Encontrar un vector }& 𝐱\\ \text{que maximice }& {𝐜}^T𝐱\\ \text{sujeto a}& A𝐱\le 𝐛\\ \text{y}& 𝐱\ge \mathrm{𝟎}\end{array}$

a on $𝐱$ és el vector de variables que es desija determinar, $𝐜$ i $𝐛$ són vectores daus (en ${𝐜}^T$ indicant que els coeficients de $𝐜$ són usats com una matriu d'un sol rengló per a que el producte matricial estiga definit) i $A$ és una matriu donada. La funció el valor de la qual es va a maximizar o minimisar (en este cas $𝐱\mapsto {𝐜}^T𝐱$) és cridada funció objectiu. Les desigualtats $A𝐱\le 𝐛$ i $𝐱\ge \mathrm{𝟎}$ són les restriccions i formen la regió factible o també coneguda com a regió de factibilidad.

Història

Cronologia

Any	Acontenyiment
1826	Joseph Fourier anticipa la programació llineal. Carl Friedrich Gauss resol equacions llineals per eliminació "gaussiana".
1902	Gyula Farkas concep un método per a resoldre sistemes de inecuaciones.
1947	George Dantzig publica l'algoritme simplex i John von Neumann va desenrollar la teoria de la dualitat. Se sap que Leonid Kantoróvich també va formular la teoria en forma independent.
1984	Narendra Karmarkar introduïx el método del punt interior per a resoldre problemes de programació llineal.

El problema de la resolució d'un sistema llineal de inecuaciones es remonta, a lo manco, a Joseph Fourier, despuix de qui naix el método d'eliminació de Fourier-Motzkin. La programació llineal es planteja com un model matemàtic desenrollat durant la Segona Guerra Mundial per a planificar les despeses i les tornades, a fi de reduir els costs a l'eixèrcit i aumentar les pèrdues de l'enemic. Es va mantindre en secret fins a 1947. En la posguerra, moltes indústries ho varen usar en la seua planificació diària.

Els fundadors de la tècnica són George Dantzig, qui va publicar l'algoritme simplex, en 1947, John von Neumann, que va desenrollar la teoria de la dualitat en el mateix any, i Leonid Kantoróvich, un matemàtic d'orige rus, que utilisa tècniques similars en l'economia abans de Dantzig i va guanyar el premi Nobel en economia en 1975. En 1979, un atre matemàtic rus, Leonid Khachiyan, va dissenyar el cridat Algoritme de l'elipsoide, a través del com va demostrar que el problema de la programació llineal és resoluble de manera eficient, és dir, en temps polinomial. Més tart, en 1984, Narendra Karmarkar, un matemàtic d'orige indi, introduïx un nou método del punt interior per a resoldre problemes de programació llineal, lo que constituiria un enorme alvanç en els principis teòrics i pràctics en l'àrea.

L'eixemple original de Dantzig de la busca de la millor assignació de 70 persones a 70 llocs de treball és un eixemple de l'utilitat de la programació llineal. La potència de computació necessària per a examinar totes les permutació a fi de seleccionar la millor assignació és immensa (factorial de 70, 70!) ; el número de possibles configuracions excedix al número de partícules en l'univers. No obstant, pren només un moment trobar la solució òptima per mig del plantejament del problema com una programació llineal i l'aplicació de l'algoritme simplex. La teoria de la programació llineal reduïx dràsticament el número de possibles solucions factibles que deuen ser revisades.

Forma estàndar

La forma més usual i intuïtiva de descriure un problema de programació llineal és en la seua forma estàndar, el qual consistix de tres parts:

• Una funció llineal que es desija maximizar, per eixemple

$vrg$

• Restriccions llineals de la forma:

$\begin{array}{cc}{a}_{11}{x}_1+a_{12}{x}_2& \le b_1\\ a_{21}{x}_1+a_{22}{x}_2& \le b_2\\ a_{31}{x}_1+a_{32}{x}_2& \le b_3\end{array}$

• Variables no negatives, per eixemple

$\begin{array}{cc}{x}_1& \ge 0\\ x_2& \ge 0\end{array}$

El problema és usualment representat en forma matricial com

$\max \{{𝐜}^T𝐱:𝐱\in {ℝ}^n\wedge A𝐱\le 𝐛\wedge 𝐱\ge \mathrm{𝟎}\}$

que també pot ser escrit com

$\begin{array}{ccc}\max :& & {𝐜}^T𝐱\\ s.a:& & A𝐱\le 𝐛\\ & & 𝐱\ge \mathrm{𝟎}\end{array}$

o simplement com

$\{\begin{array}{ccc}\text{Maximizar}& & {𝐜}^T𝐱\\ \text{Sujeto a}& & A𝐱\le 𝐛\\ & & 𝐱\ge \mathrm{𝟎}\end{array}$

Atres formes, com a problemes de minimisació, problemes en restriccions d'una atra forma, aixina com problemes que involucren variables negatives poden s'escrits per mig d'un problema equivalent en la seua forma estàndar.

Variables

El vector $𝐱\in {ℝ}^n$ té com a entrades a les variables $x_i$ ($i=1,2,\dots ,n$) i estes són cridades variables de decisió; per a la forma estàndar d'un model de programació llineal, estes són número real majors o iguals a zero, és dir, $x_i\ge 0$.

En cas que es requerixca que el valor resultant de les variables siga un número entero llavors es tracta d'un problema de Programació Sancera i quan es requerixca que el valor resultant de les variables solament prenga dos valors, per eixemple, $0$ o $1$, llavors es tracta d'un problema de Programació Binaria

Forma aumentada (variables de chala)

Els problemes de programació llineal en la seua forma estàndar poden ser convertits a la seua forma aumentada per a aplicar l'algoritme símplex. Esta forma introduïx variables no negatives cridades variables de chala per a aixina reemplaçar en les restriccions les desigualtats en igualtats. Els problemes poden ser escrits en la següent forma matricial:

$\begin{array}{cc}\max & z\\ s.a:& \left(\begin{array}{ccc}1& -{𝐜}^T& 0\\ 0& 𝐀& 𝐈\end{array}\right)\left(\begin{array}{c}z\\ 𝐱\\ 𝐬\end{array}\right)=\left(\begin{array}{c}0\\ 𝐛\end{array}\right)\\ & 𝐱,𝐬\ge \mathrm{𝟎}\end{array}$

a on $𝐬$ són les variables de chala, $𝐱$ són les variables de decisió i $z$ és la variable a maximizar.

Forma no estàndar

La forma estàndar d'un model de programació llineal és quan es té el model

$\begin{array}{ccc}\max :& & {𝐜}^T𝐱\\ s.a:& & A𝐱\le 𝐛\\ & & 𝐱\ge 0\end{array}$

com a formes no estàndar, es tenen els següents casos

• Quan es desige minimisar la funció objectiu.

$\begin{array}{ccc}\min :& & {𝐜}^T𝐱\\ s.a:& & A𝐱\le 𝐛\\ & & 𝐱\ge \mathrm{𝟎}\end{array}$

• Quan les restriccions són de la forma:

$\begin{array}{ccc}\max :& & {𝐜}^T𝐱\\ s.a:& & A𝐱\ge 𝐛\\ & & 𝐱\ge \mathrm{𝟎}\end{array}$

o

$\begin{array}{ccc}\max :& & {𝐜}^T𝐱\\ s.a:& & A𝐱=𝐛\\ & & 𝐱\ge \mathrm{𝟎}\end{array}$

• Quan les variables són negatives o poden prendre qualsevol valor.

$\begin{array}{ccc}\max :& & {𝐜}^T𝐱\\ s.a:& & A𝐱\le 𝐛\\ & & 𝐱<\mathrm{𝟎}\end{array}$

o

$\begin{array}{ccc}\max :& & {𝐜}^T𝐱\\ s.a:& & A𝐱\le 𝐛\end{array}$

• Combinacions dels tres casos anteriors.

Teoria

Existència de solucions òptimes

Geomètricament, les restriccions llineals definixen la regió factible, que és un poliedre convexo. Una funció llineal és una funció convexa, per lo que un mínim local és un mínim global; una funció llineal és també una funció cóncava, aixina que tot màxim local és també un màxim global.

Com les funcions llineals no són ni estrictament convexas ni estrictament cóncaves, les solucions òptimes no són necessàriament úniques.

Si la regió factible és acotada i no buida, llavors existirà a lo manco una solució òptima, ya que una funció llineal és contínua i per lo tant alcança un màxim en qualsevol regió tancada i acotada. No obstant, pugues no existir una solució òptima en dos situacions. En primer lloc, si la regió factible és buida, és dir, si cap punt verifica totes les restriccions, llavors el problema és no factible. En segon lloc, si la regió factible no està acotada en la direcció del gradient de la funció objectiu, el problema és no acotat, i es poden trobar punts que verifiquen totes les restriccions i en un valor tan alt com vullgam de la funció objectiu.

Programació sancera

En alguns casos es requerix que la solució òptima es componga de valors sancers per a algunes de les variables. La resolució d'este problema s'obté analisant les possibles alternatives de valors sancers d'eixes variables en un entorn al voltant de la solució obtinguda considerant les variables reals.

Moltes voltes la solució del programa llineal truncat està llunt de ser l'òptim sancer, per lo que es fa necessari usar algun algoritme per a trobar esta solució de forma exacta. El més famós és el método de 'Ramificar i Acotar' o Branch and Bound pel seu nom en anglés. El método de Ramificar i Acotar part de l'adició de noves restriccions per a cada variable de decisió (acotar) que en ser evaluat independentment (ramificar) du a l'òptim sancer.

Aplicacions

La programació llineal constituïx un important camp de l'optimisació per vàries raons, molts problemes pràctics de l'investigació d'operacions poden plantejar-se com a problemes de programació llineal. Alguns casos especials de programació llineal, tals com els problemes de fluix de rets i problemes de fluix de mercaderies es varen considerar en el desenroll de les matemàtiques lo suficientment importants com per a generar per sí mateixos molta investigació sobre algoritmes especialisats en la seua solució. Una série d'algoritmes dissenyats per a resoldre atres tipos de problemes d'optimisació constituïxen casos particulars de la més àmplia tècnica de la programació llineal. Històricament, les idees de programació llineal han inspirat molts dels conceptes centrals de la teoria d'optimisació tals com la dualitat, la descomposició i l'importància de la convexidad i les seues generalisacions. De la mateixa manera, la programació llineal és molt usada en la microeconomía, l'ingenieria i l'administració d'empreses, ya siga per a aumentar al màxim els ingressos o reduir al mínim els costs d'un sistema de producció. L'aprenentage de la metodologia programació llineal és important en la formació de l'ingenier industrial i l'administrador perque li dona ferramentes per a millorar la presa de decisions en les empreses, lo que durà a millorar els processos de les mateixes. Alguns eixemples són la mescla d'aliments, la gestió d'inventaris, la cartera i la gestió de les finances, l'assignació de recursos humans i recursos de màquines, la planificació de campanyes de publicitat, etc.

Uns atres són:

• Optimisació de la combinació de sifres comercials en una ret llineal de distribució d'aigua.

• Aprofitament òptim dels recursos d'una conca hidrogràfica, per a un any en afluències caracterisades per correspondre a una determinada freqüència.

• Soport para pren de decisió en temps real, per a operació d'un sistema d'obres hidràuliques;

• Solució de problemes de transport.

Eixemple

Este és un cas curiós, en sol 6 variables (un cas real de problema de transport pot tindre fàcilment més de 1000 variables) en el qual s'aprecia l'utilitat d'este procediment de càlcul.

Existixen tres mines de carbó la producció diària del qual és:

• La mina "a" produïx 40 tonellades per dia;
• La mina "b" produïx 40 t/dia; i,
• La mina "c" produïx 20 t/dia.

En la zona hi ha dos centrals termoelèctriques que consumixen:

• La central "d" consumix 40 t/dia de carbó; i,
• La central "i" consumix 60 t/dia

Els costs de mercat, de transport per tonellada són:

• De "a" a "d" = 2 monedes
• De "a" a "i" = 11 monedes
• De "b" a "d" = 12 monedes
• De "b" a "i" = 24 monedes
• De "c" a "d" = 13 monedes
• De "c" a "i" = 18 monedes

Si es preguntara als pobladors de la zona cóm organisar el transport, tal volta la majoria opinaria que deu aprofitar-se el preu oferit pel transportiste que va de "a" a "d", perque és més convenient que els atres, degut a que és el de més baix preu.

En este cas, el cost total del transport és:

• Transport de 40 t de "a" a "d" = 80 monedes
• Transporte de 20 t de "c" a "i" = 360 monedes
• Transporte de 40 t de "b" a "i" = 960 monedes
• Total 1.400 monedes.

No obstant, formulant el problema per a ser resolt per la programació llineal es tenen les següents equacions:

• Restriccions de la producció:

$X_{a\to d}+X_{a\to e}\le 40$	$[\text{T/dia}]$
$X_{b\to d}+X_{b\to e}\le 40$	$[\text{T/dia}]$
$X_{c\to d}+X_{c\to e}\le 20$	$[\text{T/dia}]$

• Restriccions del consum:

$X_{a\to d}+X_{b\to d}+X_{c\to d}\ge 40$	$[\text{T/dia}]$
$X_{a\to e}+X_{b\to e}+X_{c\to e}\ge 60$	$[\text{T/dia}]$

• La funció objectiu serà:

$2X_{a\to d}+11X_{a\to e}+12X_{b\to d}+24X_{b\to e}+13X_{c\to d}+18X_{c\to e}=Min!$

La solució de cost mínim de transport diari resulta ser:

• X_b-d = 40 resultant un cost de 12 x 40 = 480 monedes
• X_a-i = 40 resultant un cost d'11 x 40 = 440 monedes
• X_c-i = 20 resultant un cost de 18 x 20 = 360 monedes
• Total 1.280 monedes.

120 monedes menys que abans.

Ara be, les aplicacions,per eixemple, en productes de combinacions convexas i desigualtats (de Kantorovich) poden ser retratades de la següent forma:

Siguen λi i μi (i = 1,2,…, N) constants reals i θi (i = 1,2,…, N) variables no negatives que satisfacen Σθi = 1. Es mostra que el problema de l'extrem (N - 1) -dimensional de trobar el màxim i mínim globals del producte (Σθiλi) (Σθiμi) es pot reduir a un problema unidimensional definit en el llímit del polígon convexo travessat pel parells ordenats (λi, μi). Per a un conjunt donat de λi′s positius (λ1⩾λ2⩾ ⋯ ⩾λN> 0), la desigualtat de Kantorovich establix que max {(Σθiλi) (Σθiμi)} = (λ1 + λN) 24λ1λN i min {(Σθiλi) (Σθiμi )} = 1 si μi = 1λi, i = 1,2,…, N. Es mostra que la nova tècnica anterior es pot utilisar per a identificar exactament quànt poden variar els μi dels valors de Kantorovich μi = 1 / λi sense invalidar els llímits de Kantorovich. Siga νmax = sup (x, x) = 1 {(x, Ax) (x, Bx)} i νmin = inf (x, x) = 1 {(x, Ax) (x, Bx)}, a on x és un vector complex N-dimensional, i A i B són dos matrius hermitianas definides positives N × N. Per al cas especial en el que B = A-1, la desigualtat de Kantorovich implica que νmaxνmin = [κ (A) +1] 24κ (A), a on κ (A) és el número de condició espectral de A. Es mostra que, en general, νmaxνmin⩾max {[κ (A) +1] 24κ (A), [κ (B) +1] 24κ (B)}.

Vore també

• Poliedre convexo
• Algoritme de pivot
• Algoritme simplex
• Conjectura de Hirsch
• Leonid Kantoróvich

Enllaços externs

• Programació llineal en Google OR-Tools
• Programació llineal sancera en Google OR-Tools
• Programació llineal mixta en Google OR-Tools
• Programació llineal en Solver
• Programació llineal en Tora
• Programació llineal en Lingo

Bibliografia

• Loomba, N.P. Linear Programming: An introductory analysis. McGraw-Hill, New York, 1964
• Universitat Peruana Unió - Biblioteca Central - lliure número 0.001245/f12 Programació llineal.