Un problema di programmazione lineare può essere definito come il problema di massimizzare o minimizzare una funzione lineare soggetta a un sistema di vincoli lineari. I vincoli possono essere uguaglianze o disuguaglianze. La funzione lineare è chiamata funzione obiettivo, della forma f (x , y ) = a x + b y + c . L’insieme di soluzioni del sistema di disuguaglianze è l’insieme di soluzioni possibili o fattibili , che sono della forma ( x , y ) .,
Se un problema di programmazione lineare può essere ottimizzato, si verificherà un valore ottimale in uno dei vertici della regione che rappresenta l’insieme di soluzioni fattibili.
Quando il grafico di un sistema di disuguaglianze forma una regione chiusa, si dice che la regione sia delimitata. A volte un sistema di disuguaglianze forma una regione aperta. In questo caso, la regione è chiamata illimitata.
Per risolvere un problema di programmazione lineare, attenersi alla seguente procedura.
• Grafico della regione corrispondente alla soluzione del sistema di vincoli.,
• Trova le coordinate dei vertici della regione formata.
• Valutare la funzione obiettivo a ciascun vertice per determinare quali valori x e y, se presenti, massimizzano o minimizzano la funzione.