Programació lineal

Amb el terme Programació Lineal ens referim a les tècniques matemàtiques encarades a esbrinar els valors màxim o mínim d'una funció lineal (funció objectiu). La funció objectiu es representa gràficament per una recta en el pla (si es treballa amb dues variables) i està sotmesa a un sistema de restriccions (condicions entre les variables) les quals s'expressen algèbricament mitjançant un sistema de desigualtats lineals. El valor o valors de les variables del problema per a les quals la funció estudiada es fa màxima o mínima s'anomena solució òptima. Treballant en dues dimensions, el sistema de desigualtats delimita una regió del pla que té contorn poligonal. Aquesta regió del pla s'anomena regió factible perquè és entre els seus punts que trobarem aquells que fan que la funció objectiu prengui un valor òptim. Un problema de Programació Lineal consisteix, precisament, a determinar aquests punts i, de retruc, els valors màxim o mínim de la funció lineal a optimitzar. George Dantzig generalitzà el problema (l'any 1947) a un nombre arbitrari de variables i dissenyà un algorisme que en dóna solucions. També van fer importants contribucions al desenvolupament i generalització d'aquestes tècniques matemàtiques importants matemàtics i físics teòrics com ara John von Neumann així com matemàtics i economistes com Leonid Kantórovich. Aquest algorisme es coneix amb el nom d'algorisme simplex. L'algorisme simplex s'implementa en programes d'ordinador. Sobre el tema, ben recentment, s'han fet valuoses aportacions teòriques (vegeu: conjectura de Hirch). Aquí, però, no ens n'ocuparem de l'algorisme simplex: tan sols aprendrem a optimitzar funcions lineals de dues variables i, per això, n'hi ha prou a resoldre el problema de forma gràfica. Podem assegurar que hi ha solució sempre i quan la regió factible tingui contorn poligonal convex. Necessitarem paper quadriculat, regle, i escaire o cartabó per traçar rectes paral·leles a una de donada.