Matematica di programmazione lineare

Programmazione lineare, tecnica di modellistica matematica in cui una funzione lineare è massimizzata o minimizzata quando soggetta a vari vincoli. Questa tecnica è stata utile per guidare le decisioni quantitative nella pianificazione aziendale, nell'ingegneria industriale e, in misura minore, nelle scienze sociali e fisiche.

ottimizzazione: programmazione lineare

Sebbene ampiamente utilizzato ora per risolvere i problemi di decisione di tutti i giorni, la programmazione lineare era relativamente sconosciuta prima del 1947. Nessun lavoro di alcun significato

La soluzione di un problema di programmazione lineare si riduce alla ricerca del valore ottimale (più grande o più piccolo, a seconda del problema) dell'espressione lineare (chiamata funzione obiettivo)

soggetto a una serie di vincoli espressi come disuguaglianze:

Le a, le b e le c sono costanti determinate dalle capacità, dai bisogni, dai costi, dai profitti e da altri requisiti e restrizioni del problema. L'assunto di base nell'applicazione di questo metodo è che le varie relazioni tra domanda e disponibilità sono lineari; cioè, nessuna delle x _i viene elevata a una potenza diversa da 1. Per ottenere la soluzione a questo problema, è necessario trovare la soluzione del sistema di disuguaglianze lineari (ovvero l'insieme di n valori di le variabili x _i che contemporaneamente soddisfano tutte le disuguaglianze). La funzione obiettivo viene quindi valutata sostituendo i valori di x _i nell'equazione che definisce f.

Le applicazioni del metodo di programmazione lineare furono tentate seriamente per la prima volta alla fine degli anni '30 dal matematico sovietico Leonid Kantorovich e dall'economista americano Wassily Leontief rispettivamente nelle aree dei programmi di produzione e dell'economia, ma il loro lavoro fu ignorato per decenni. Durante la seconda guerra mondiale, la programmazione lineare è stata ampiamente utilizzata per gestire il trasporto, la programmazione e l'allocazione delle risorse soggette a determinate restrizioni quali costi e disponibilità. Queste applicazioni fecero molto per stabilire l'accettabilità di questo metodo, che acquistò ulteriore slancio nel 1947 con l'introduzione del metodo simplex del matematico americano George Dantzig, che semplificò notevolmente la soluzione dei problemi di programmazione lineare.

Tuttavia, poiché sono stati tentati problemi sempre più complessi che coinvolgono più variabili, il numero di operazioni necessarie si è espanso esponenzialmente e ha superato la capacità computazionale anche dei computer più potenti. Quindi, nel 1979, il matematico russo Leonid Khachiyan scoprì un algoritmo del tempo polinomiale - in cui il numero di passaggi computazionali cresce come potenza del numero di variabili anziché esponenzialmente - permettendo così la soluzione di problemi finora inaccessibili. Tuttavia, l'algoritmo di Khachiyan (chiamato metodo ellissoide) era più lento del metodo simplex quando praticamente applicato. Nel 1984 il matematico indiano Narendra Karmarkar scoprì un altro algoritmo del tempo polinomiale, il metodo dei punti interni, che si dimostrò competitivo con il metodo simplex.