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:

Per maggiori informazioni sugli algoritmi e sulla programmazione lineare, vedi Optimization Toolbox™.




Riferimenti software

Vedere anche: Optimization Toolbox, Global Optimization Toolbox, programmazione intera, programmazione quadratica, programmazione non lineare, ottimizzazione multiobiettivo, analisi predittiva

Optimization Techniques Training Course

In this course you’ll learn applied optimization techniques in the MATLAB® environment, focusing on using Optimization Toolbox™ and Global Optimization Toolbox.