Problema lineare

Un problema lineare è caratterizzato da obiettivi e vincoli rappresentabili mediante delle funzioni lineari. Un problema lineare è rappresentato mediante un sistema di equazioni/disequazioni e variabili. Le soluzioni ammissibili del problema lineare, nel caso esistano, sono sempre comprese in un insieme detto poliedro. Le soluzioni ottime del problema sono sempre localizzate nei punti estremi dell'insieme poliedro. L'insieme poliedro del problema lineare può essere rappresentato sul piano anche mediante una struttura combinatoria fondamentale detta grafo ( teoria dei grafi ). Lo studio dei problemi lineari è oggetto della ricerca operativa e della programmazione lineare. I problemi lineari possono essere classificati nei seguenti tipi:

• Problemi lineari continui. I problemi lineari continui sono problemi lineari le cui variabili possono assumere ogni valore continuo ( variabili continue ) del relativo dominio di esistenza. I problemi lineari continui sono oggetto di studio della Linear Programming ( LP ).
• Problemi lineari interi. I problemi lineari interi sono problemi lineari le cui variabili possono assumere soltanto i valori interi ( variabili intere ) del relativo dominio di esistenza. I problemi lineari interi sono oggetto di studio di una branca della programmazione lineare detta Integer Linear Programming ( ILP ).
• Problemi lineari misto-interi. I problemi lineari misto-intero sono problemi lineari le cui variabili possono assumere sia valori continui ( variabili continue ) e sia valori interi ( variabili intere ) del relativo dominio di esistenza.