Cosa si intende per programmazione lineare?

Per programmazione lineare, anche come ottimizzazione lineare, 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}\]

Programmazione lineare con MATLAB

È possibile utilizzare MATLAB^® per implementare i seguenti algoritmi comunemente utilizzati per risolvere problemi di programmazione 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: utilizza 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.

Il solutore linprog in Optimization Toolbox™ implementa queste tecniche di ottimizzazione lineare.

Casi particolari di 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.