Programmazione lineare

La programmazione lineare ( PL ) è lo studio degli algoritmi di risoluzione dei problemi lineare. I problemi lineari sono problemi aventi una funzione obiettivo lineare e un insieme di vincoli lineari. È conosciuta anche con il termine inglese Linear Programming ( LP ) o con gli acronimi LP e PL. Dato un problema lineare, la programmazione lineare consente di trovare la migliore soluzione ammissibile del problema qualora questa esista. L'insieme delle soluzioni ammissibili del problema lineare è un insieme convesso ( poliedro ) e la soluzione ottima di un problema lineare è sempre uno dei punti estremi del poliedro. Essendo un poliedro caratterizzato da un numero finito di punti estremi, il problema lineare può essere risolto mediante una generica enumerazione completa oppure, in modo più efficiente, mediante opportune tecniche di calcolo ( algoritmi ) specializzate a risolvere una particolare struttura del problema. La programmazione lineare è una branca della ricerca operativa e dell'informatica ( algoritmica ).