Che cos'è la programmazione lineare intera?

I problemi di programmazione lineare integer sorgono quando si cerca di risolvere sistemi lineari specificando che tutte le variabili sconosciute devono essere numeri interi o numeri interi. I sistemi lineari sono insiemi di equazioni che descrivono una situazione per la quale il programmatore sta cercando di trovare una soluzione. Di solito sono costituiti da un'equazione che deve essere ingrandita o minimizzata e da una o più equazioni restrittive che pongono limiti a variabili sconosciute. Perché il sistema sia lineare, ogni restrizione deve essere un'equazione lineare; cioè, non deve contenere istanze della variabile sconosciuta con esponenti maggiori di uno.

I normali sistemi lineari possono essere risolti facilmente usando un computer. Il programma può identificare una soluzione trovando la derivata e impostandola uguale a zero. Può quindi verificare che il punto sia massimo o minimo controllando la sua vicinanza immediata alla funzione. Finché la derivata è definita in ciascun punto lungo la funzione, il computer ha solo un numero limitato di possibili soluzioni da verificare.

La programmazione lineare diventa programmazione lineare intera con l'aggiunta della restrizione intera. Ciò significa che il problema rimane lo stesso, ma la risposta deve consistere in valori interi per i valori sconosciuti: devono essere numeri interi. A volte, ciò significa che la soluzione non sarà ottimale rispetto al caso in cui sono consentite le frazioni; riflette tuttavia il mondo reale, in cui gli oggetti spesso arrivano in unità discrete e indivisibili. Ciò rende la programmazione lineare intera importante per le applicazioni aziendali, poiché le aziende vogliono massimizzare il più possibile i profitti ma non possono scegliere di vendere una frazione di un prodotto.

Una volta messe in atto le restrizioni sui numeri interi, il problema di risolvere il sistema lineare è NP-completo. Ciò significa che il tempo necessario a un computer per risolvere il sistema è indeterminato. Con le restrizioni sui numeri interi, i computer non possono utilizzare lo strumento della derivata perché non esiste alcuna garanzia che il punto zero della derivata cada su un numero intero. La soluzione sarà l'intero con il valore più alto o più basso tra tutti gli interi, quindi il computer dovrebbe controllarli tutti - un processo che potrebbe richiedere un tempo infinito.

I programmatori hanno sviluppato l'euristica, o metodi di risoluzione dei problemi, per far fronte alla complessità di questi problemi. Un metodo per risolvere i problemi di programmazione lineare intera è l'algoritmo branch and bound, in cui il computer risolve una serie di problemi relativi a quello originale per restringere l'intervallo di valori disponibile a una soluzione. Per problemi complessi, tuttavia, ciò può richiedere molto tempo.