Programació lineal: diferència entre les revisions
Contingut suprimit Contingut afegit
m →Història: desamb |
m →Història: ort |
||
Línia 27:
El problema consistent en resoldre un sistema de [[inequació|desigualtat]]s lineals data, com a mínim, de l'època de [[Joseph Fourier|Fourier]], en honor al qual s'anomena el mètode de l'[[eliminació de Fourier-Motzkin]]. La primera programació lineal fou desenvolupada per [[Leonid Kantoròvitx]] el 1939<ref>Vegeu el seu treball de 1940 llistat més avall.</ref> 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 el 1947, quan [[George Dantzig]] va publicar el [[algorisme símplex|mètode símplex]] i [[John von Neumann]] va desenvolupar la teoria de la [[#Dualitat|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.
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]], 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
L'exemple original de Dantzig consistia en 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.
| |||