Programma lineare

Un programma lineare è una procedura per risolvere un problema di ottimizzazione vincolata con funzione obiettivo e vincoli lineari. Un problema lineare è esprimibile mediante un sistema di equazioni e/o disequazioni lineari. Ad esempio la funzione obiettivo di un problema lineare può consistere nella massimizzazione di un risultato finale ed essere scritta nel seguente modo.

max b₁x₁ + ... + b_nx_n

Allo stesso modo la funzione potrebbe consistere nella minimizzazione di un risultato. I vincoli del problema consistono in un sistema di equazioni/disequazioni.

a₁₁x₁ + ... a_1nx_n < v₁

...

a_m1x₁ + ... a_mnx_n > v_m

I dati a_mn sono numeri reali che rappresentano i parametri del problema. Il programma lineare è in grado di individuare i vettori X di valori nelle variabili x₁, ... , x_n, in grado di soddisfare tutti i vincoli del problema ( soluzioni ammissibili ). Tra tutte le soluzioni ammissibili il programma lineare seleziona quella in grado di massimizzare ( o minimizzare ) la funzione obiettivo del problema lineare ( soluzione ottima ).