Programació lineal, tècnica de modelatge matemàtic en què es maximitza o minimitza una funció lineal quan se sotmet a diverses limitacions. Aquesta tècnica ha estat útil per guiar decisions quantitatives en planificació empresarial, en enginyeria industrial i, en menor mesura, en ciències socials i físiques.
optimització: programació lineal
Tot i que ara s’utilitza àmpliament per resoldre problemes de decisió quotidians, la programació lineal era comparativament desconeguda abans del 1947. No hi ha cap obra de cap importància
La solució d’un problema de programació lineal es redueix a trobar el valor òptim (el més gran o el més petit, segons el problema) de l’expressió lineal (anomenada funció objectiu)
subjecte a un conjunt de restriccions expressades com a desigualtats:
Les a, s i c són constants determinades per les capacitats, necessitats, costos, beneficis i altres requisits i restriccions del problema. La suposició bàsica en l’aplicació d’aquest mètode és que les diverses relacions entre demanda i disponibilitat són lineals; és a dir, cap de les x i no s’eleva a una potència diferent de 1. Per obtenir la solució d’aquest problema, és necessari trobar la solució del sistema de desigualtats lineals (és a dir, el conjunt de n valors de les variables x i que alhora satisfan totes les desigualtats). A continuació, s'avalua la funció objectiu substituint els valors de x i en l'equació que defineix f.
A finals de la dècada de 1930, el matemàtic soviètic Leonid Kantorovich i l'economista nord-americà Wassily Leontief van ser intentats seriosament aplicats pel mètode de programació lineal, però el seu treball va ser ignorat durant dècades. Durant la Segona Guerra Mundial, la programació lineal es va utilitzar àmpliament per tractar el transport, la programació i l'assignació de recursos sotmesos a certes restriccions com ara els costos i la disponibilitat. Aquestes aplicacions van fer molt per establir l’acceptabilitat d’aquest mètode, que va obtenir un impuls més el 1947 amb la introducció del mètode simplex del matemàtic americà George Dantzig, que va simplificar molt la solució de problemes de programació lineal.
No obstant això, a mesura que es van intentar problemes cada cop més complexos amb més variables, el nombre d'operacions necessàries es va expandir exponencialment i va superar la capacitat computacional dels fins i tot dels ordinadors més potents. Aleshores, el 1979, el matemàtic rus Leonid Khachiyan va descobrir un algoritme de temps polinòmic, en el qual el nombre de passos computacionals creix com una potència del nombre de variables més que exponencialment, permetent així la solució de problemes fins ara inaccessibles. Tanmateix, l'algorisme de Khachiyan (anomenat mètode elipsoide) era més lent que el mètode simplex quan s'aplicava pràcticament. El 1984, el matemàtic indi Narendra Karmarkar va descobrir un altre algoritme de temps polinòmic, el mètode de punt interior, que va resultar competitiu amb el mètode simplex.
