Programació lineal
mètode de programació per aconseguir el mateix resultat d'un model matemàtic / From Wikipedia, the free encyclopedia
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:
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 és la matriu transposada. L'expressió que es vol maximitzar o minimitzar s'anomena funció objectiu, en aquest cas cTx. 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.