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 utilizzando 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 possibili soluzioni da verificare.

La programmazione lineare diventa una programmazione lineare intero con l'aggiunta della restrizione intero.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 interate sono in atto, il problema di risolvere il sistema lineare è NP-completare.Ciò significa che il tempo necessario affinché un computer risolva il sistema è indeterminato.Con le restrizioni interi, i computer non possono utilizzare lo strumento del derivato perché non vi è alcuna garanzia che il punto zero del derivato cadrà 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 All Mdash;un processo che potrebbe richiedere un 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, questo può richiedere molto tempo.