Programmazione lineare

coins

La programmazione lineare è una parte molto importante della ricerca operativa. Si ha un problema di programmazione lineare ogni qual volta è possibile tradurre un problema reale in uno matematico in cui sia la funzione (da massimizzare o minimizzare) sia i vincoli sono lineari, cioè rappresentati da equazioni o disequazioni in cui tutte le variabili compaiono al più al primo grado. Riassumendo dunque, si ha un programma lineare quando il modello matematico:

– è costituito da una funzione lineare di n variabili;
– i vincoli sono espressi da un sistema di equazioni o disequazioni lineari nelle n variabili della funzione di cui sopra;
– tra i vincoli è presente la non negatività delle variabili, rappresentando queste quantità economiche che, pertanto, non possono essere negative.

vincolo lineare
Esempio di vincolo lineare: l’area del poligono è espressa da un sistema di disequazioni di primo grado

 

Vincolo non lineare
Esempio di vincolo non lineare: l’area del semicerchio è individuata da un sistema di disequazioni di cui una di secondo grado.

Generalmente, quindi, un problema di programmazione lineare si riconduce allo studio di un problema di massimi e minimi vincolati di una funzione lineare in più variabili con vincoli lineari. I problemi in due variabili si risolvono generalmente con il metodo grafico, altrimenti si utilizza un metodo più generale detto metodo del simplesso.