Cos'è la programmazione lineare intera?

I problemi di programmazione lineare interi sorgono quando si tenta di risolvere i sistemi lineari mentre si specifica 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 tentando di trovare una soluzione. Di solito consistono in un'equazione che deve essere massimizzata o ridotta al minimo e una o più equazione di limitazione che pone limiti su variabili sconosciute. Affinché il sistema sia lineare, ogni restrizione deve essere un'equazione lineare; Cioè, non deve contenere istanze della variabile sconosciuta con esponenti superiori a uno.

I sistemi lineari regolari possono essere risolti facilmente usando un computer. Il programma può identificare una soluzione trovando il derivato e impostandolo uguale a zero. Può quindi verificare che il punto sia massimo o minimo controllando il suo quartiere immediato sulla funzione. Finché il derivato è definito in ciascun punto lungo la funzione, il computer ha solo un numero limitato di PossiblE soluzioni da controllare.

La programmazione lineare diventa una programmazione lineare intero 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 sarà non ottimale rispetto al caso in cui sono consentite le frazioni; È riflessivo, tuttavia, del mondo reale, in cui gli articoli sono spesso disponibili in unità discrete e indivisibili. Ciò rende importante la programmazione lineare intero 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 che le restrizioni intero sono in atto, il problema di risolvere il sistema lineare è completo NP. Ciò significa che il tempo necessario affinché un computer risolva il sistema è indeterminato. Con restrizioni interi, computerS non può usare lo strumento del derivato perché non vi è alcuna garanzia che il punto zero del derivato cade su un numero intero. La soluzione sarà l'intero con il valore più alto o più basso tra tutti gli numeri interi, quindi il computer dovrebbe controllarli tutti: un processo che potrebbe richiedere un periodo di tempo infinito.

I programmatori hanno sviluppato euristica o metodi di risoluzione dei problemi, per affrontare la complessità di questi problemi. Un metodo per risolvere i problemi di programmazione lineare interi è l'algoritmo di ramo e rilegato, in cui il computer risolve una serie di problemi relativi a quello originale per restringere la gamma disponibile di valori a una soluzione. Per problemi complessi, tuttavia, può richiedere molto tempo.