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™.
