Risoluzione dei problemi di ottimizzazione lineare
Per programmazione lineare (PL) si intende la minimizzazione o la massimizzazione di una funzione obiettivo lineare soggetta a limiti, uguaglianza lineare e vincoli di disuguaglianza. I problemi di esempio includono il blending nelle industrie di processo, la pianificazione della produzione nel settore manifatturiero, il cash flow matching in ambito finanziario e la pianificazione nei settori dell’energia e dei trasporti.
La programmazione lineare è il problema matematico di trovare un vettore x in grado di minimizzare la funzione:
\[\min_{x} \left\{f^{\mathsf{T}}x\right\}\]
Soggetta ai vincoli:
\[\begin{eqnarray}Ax \leq b & \quad & \text{(inequality constraint)} \\A_{eq}x = b_{eq} & \quad & \text{(equality constraint)} \\lb \leq x \leq ub & \quad & \text{(bound constraint)}\end{eqnarray}\]
È possibile utilizzare MATLAB® per implementare i seguenti algoritmi comunemente utilizzati per risolvere problemi di ottimizzazione lineare:
- Interior point: utilizza un algoritmo predittore-correttore primale-duale ed è particolarmente utile per programmi lineari su larga scala che hanno una struttura o possono essere definiti utilizzando matrici sparse.
- Simplesso: usa una procedura sistematica per generare e testare le soluzioni candidate al vertice di un programma lineare. L’algoritmo del simplesso e il relativo algoritmo del simplesso-duale sono gli algoritmi più diffusi per la programmazione lineare.
Gli algoritmi per alcuni casi particolari di programmi lineari, in cui i vincoli hanno una struttura di rete, sono in genere più veloci degli algoritmi interior-point generici e simplessi. I casi particolari includono:
- Flusso massimo su rete: utilizza algoritmi augmenting-path e push-relabel.
- Percorso minimo: utilizza algoritmi Dijkstra, Bellman-Ford e di ricerca.
- Assegnazione lineare: utilizza un algoritmo di corrispondenza bipartito.
Per maggiori informazioni sugli algoritmi e sulla programmazione lineare, vedi Optimization Toolbox™.
Esempi e consigli pratici
Casi d’uso
Riferimenti software
Vedere anche: Optimization Toolbox, Global Optimization Toolbox, programmazione intera, programmazione quadratica, programmazione non lineare, ottimizzazione multiobiettivo, analisi predittiva
Corso formativo sulle tecniche di ottimizzazione
In questo corso scoprirai quali sono le tecniche di ottimizzazione applicate nell’ambiente MATLAB®, con particolare attenzione all’uso di Optimization Toolbox™ e Global Optimization Toolbox.