1. Che cos'è un problema di ottimizzazione
Un problema di ottimizzazione è una ricetta numerica per prendere una decisione: fissiamo alcune variabili decisionali, una funzione obiettivo che misura quanto è buona una scelta, e una lista di vincoli che rappresentano limiti o requisiti.
scegliere x per minimizzare f(x)
soggetto a vincoli su x (uguaglianze e disuguaglianze).
Esempi: decidere quante unità produrre di ciascun prodotto, come allocare un budget tra diversi progetti, come scegliere i parametri di un modello di ML per ridurre una funzione di perdita.
2. Programmazione lineare: esempio di produzione
Nella programmazione lineare sia la funzione obiettivo che i vincoli sono espressi con formule lineari. Consideriamo un piccolo esempio di produzione con due prodotti, A e B.
- x_A = numero di unità del prodotto A da produrre;
- x_B = numero di unità del prodotto B da produrre.
profitto = 30 x_A + 20 x_B.
I vincoli descrivono le risorse limitate. Ad esempio, se abbiamo al massimo 100 ore di macchina e 80 ore di manodopera, e se A richiede 2 ore di macchina e 1 di manodopera, mentre B richiede 1 ora di macchina e 1 di manodopera, possiamo scrivere:
- 2 x_A + 1 x_B ≤ 100 (ore macchina disponibili)
- 1 x_A + 1 x_B ≤ 80 (ore manodopera disponibili)
- x_A ≥ 0, x_B ≥ 0 (non ha senso produrre quantità negative)
Questo è un tipico problema di programmazione lineare: esistono algoritmi standard (come il simplesso) che trovano una soluzione ottima, e librerie software che lo fanno automaticamente.
3. Leggere funzione obiettivo e vincoli
La parte importante nella pratica non è tanto la soluzione numerica (che il computer può trovare), ma sapere leggere e costruire bene la funzione obiettivo e i vincoli.
- La funzione obiettivo deve rappresentare davvero ciò che vogliamo massimizzare o minimizzare (profitto, qualità, consumo di energia, errore di previsione...).
- I vincoli devono codificare limiti fisici, logistici o normativi (capacità, budget, requisiti di qualità).
- Spesso conviene partire da una versione semplice del modello e poi raffinarlo se non è abbastanza realistico.
In sistemi complessi (come un controller fuzzy o un modello di ML) la funzione di costo può combinare più obiettivi: ad esempio penalizzare sia l'errore che l'uso eccessivo di risorse, con pesi che esprimono le priorità del progettista.
4. Collegamento con il machine learning
Molti problemi di machine learning supervisionato si possono vedere come problemi di ottimizzazione: scegliamo i parametri di un modello per minimizzare una funzione di perdita sui dati osservati.
trovare i parametri θ che minimizzano L(θ; D),
dove D è il dataset e L misura quanto il modello sbaglia sulle osservazioni.
Algoritmi come la discesa del gradiente (gradient descent) o le sue varianti stocastiche sono metodi di ottimizzazione numerica che cercano un minimo della funzione L muovendosi lungo la direzione di discesa più ripida.
5. Impostare un problema di ottimizzazione in Python
In pratica, per risolvere problemi di ottimizzazione usiamo librerie Python che si occupano degli algoritmi. Il nostro lavoro principale è tradurre il problema reale in termini di variabili, funzione obiettivo e vincoli.
In una pagina successiva possiamo mostrare uno script Python concreto che risolve un piccolo problema di programmazione lineare e confronta diverse scelte di funzione obiettivo o di vincoli.