La programmazione lineare comporta la minimizzazione o la massimizzazione di una funzione obiettivo soggetta a limiti e vincoli di uguaglianza lineare e disuguaglianza. I possibili problemi includono il design optimization in ambito ingegneristico, la massimizzazione del profitto nella produzione, l'ottimizzazione di portafoglio nella finanza e la programmazione nel settore dell'energia e dei trasporti.
La programmazione lineare consiste nel trovare un vettore \(x\) che minimizzi la funzione:
\[\min_{x} \left\{f^{\mathsf{T}}x\right\}\]
Soggetti ai vincoli lineari:
\[\begin{eqnarray}Ax \leq b & \quad & \text{(vincolo di disuguaglianza)} \\A_{eq}x = b_{eq} & \quad & \text{(vincolo di uguaglianza)} \\lb \leq x \leq ub & \quad & \text{(vincolo di limite)}\end{eqnarray}\]
Per risolvere i problemi di programmazione lineare, vengono comunemente usati i seguenti algoritmi:
- Interior point - usa un algoritmo predittore-correttore primario-duale ed è particolarmente utile per problemi large scale definibili mediante matrici sparse;
- active-set - minimizza l'obiettivo a ciascuna iterazione di tutto il set attivo (un subset dei vincoli attivi localmente) fino a convergere in una soluzione;
- simplesso - usa una procedura sistematica per generare e testare le soluzioni candidate al vertice di un problema di programmazione lineare. L'algoritmo simplesso è quello maggiormente utilizzato per la programmazione lineare.
Per maggiori informazioni sugli algoritmi e sulla programmazione lineare, vedi Optimization Toolbox™.
