Programmazione lineare

Minimizzare le funzioni lineari soggette a vincoli

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:

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.


Introduzione alla programmazione lineare


Riferimenti software


Descrizione degli algoritmi

Vedere anche: Optimization Toolbox, Global Optimization Toolbox, programmazione quadratica, programmazione non lineare, ottimizzazione multiobioettivo, algoritmo genetico, ricottura simulata