La programmazione lineare (PL) ottimizza una funzione obiettivo lineare soggetta a vincoli lineari. È il modello base della ricerca operativa: produzione, miscele, trasporti, allocazione di risorse. Questa scheda allena la formulazione del modello e la risoluzione grafica, dove la soluzione ottima sta sempre in un vertice della regione ammissibile.
1. Formulazione di un modello
Esercizio. Un’azienda produce due beni A e B. A rende 30 €/unità, B 40 €/unità. A richiede 2\ \text{h} macchina, B 4\ \text{h}; sono disponibili 100\ \text{h}. Formulare il modello di massimizzazione del profitto.
Variabili: x_A,x_B\ge0 quantità prodotte. Obiettivo e vincolo:
\max\ Z=30x_A+40x_B\quad\text{s.v.}\quad 2x_A+4x_B\le100,\ \ x_A,x_B\ge0.
Il modello traduce il problema reale in obiettivo + vincoli lineari + non negatività. È il passo decisivo: un modello mal posto dà soluzioni inutili.
2. Forma standard
Esercizio. Portare il vincolo 2x_A+4x_B\le100 in forma standard (uguaglianza).
Si introduce una variabile di scarto s\ge0 che assorbe la differenza:
2x_A+4x_B+s=100,\qquad s\ge0.
La variabile di scarto s rappresenta le ore macchina inutilizzate. La forma standard (vincoli di uguaglianza, variabili non negative) è il punto di partenza del metodo del simplesso.
3. Regione ammissibile e vertici
Esercizio. Per il modello \max Z=3x+2y con x+y\le4, x\le3, x,y\ge0, elencare i vertici della regione ammissibile.
I vertici sono le intersezioni dei vincoli (compresi gli assi):
- (0,0) — origine;
- (3,0) — su x=3 e y=0;
- (3,1) — su x=3 e x+y=4;
- (0,4) — su x=0 e x+y=4.
La regione ammissibile è un poligono convesso; l’ottimo di una PL sta sempre in un vertice (o su uno spigolo).
4. Ricerca dell’ottimo nei vertici
Esercizio. Per il modello del punto 3, trovare il vertice ottimo valutando Z=3x+2y.
Il massimo è Z=11 nel vertice (3,1). Per la PL basta valutare l’obiettivo nei vertici: il migliore è l’ottimo globale (nessun ottimo locale spurio).
5. Vincoli attivi
Esercizio. Nel punto ottimo (3,1) del punto 4, quali vincoli sono attivi?
Un vincolo è attivo (saturo) se vale come uguaglianza nell’ottimo:
- x\le3: x=3 → attivo (scarto nullo);
- x+y\le4: 3+1=4 → attivo;
- x,y\ge0: x=3>0, y=1>0 → non attivi.
I vincoli attivi sono quelli che “limitano” l’ottimo: rilassarli migliorerebbe Z. Sono la base dell’analisi di sensibilità e dei prezzi ombra.
6. Soluzione illimitata e infeasibile
Esercizio. Distinguere i casi patologici di una PL.
- Illimitata: la regione ammissibile è aperta nella direzione di crescita di Z → l’obiettivo cresce senza limite (es. \max x con solo x\ge0). Segnala spesso un vincolo dimenticato.
- Infeasibile (vuota): i vincoli si contraddicono e non esiste alcun punto ammissibile (es. x\le1 e x\ge3). Il modello va rivisto.
Una PL ben posta ha regione ammissibile non vuota e limitata nella direzione dell’obiettivo: allora l’ottimo esiste ed è in un vertice.
7. Modello con due risorse
Esercizio. Un reparto produce due prodotti x e y. Il profitto unitario è 5 per x e 4 per y. Ogni unità di x usa 2 ore macchina e 1 ora lavoro; ogni unità di y usa 1 ora macchina e 2 ore lavoro. Sono disponibili 100 ore macchina e 80 ore lavoro. Formulare il modello.
Variabili:
Funzione obiettivo:
Vincolo macchina:
Vincolo lavoro:
Modello completo:
La qualità della PL dipende dalla scelta delle variabili: qui x e y sono quantità fisiche, quindi la non negatività è parte del modello, non una formalità.
8. Risoluzione grafica del modello a due risorse
Esercizio. Risolvere il modello del punto 7 valutando i vertici.
I vincoli sono:
Gli intercetti sugli assi danno alcuni vertici:
Il vertice di intersezione tra i due vincoli si trova risolvendo:
Dalla prima:
Sostituendo nella seconda:
quindi:
Allora:
Valutiamo l’obiettivo:
L’ottimo è:
Entrambi i vincoli sono attivi: macchina e lavoro sono saturi nell’ottimo.
9. Ottimi multipli
Esercizio. Nel problema:
con vincoli:
individuare gli ottimi.
L’obiettivo può essere scritto:
Il vincolo limita:
Il valore massimo si ottiene quando:
Allora:
Tutti i punti del segmento:
sono ottimi. Non c’è un unico vertice: l’obiettivo è parallelo a un lato della regione ammissibile.
10. Vincolo di surplus
Esercizio. Portare in forma standard il vincolo:
Per un vincolo di tipo \geq si sottrae una variabile di surplus:
La variabile s misura l’eccesso rispetto al minimo richiesto:
Nei metodi tableau, un vincolo \geq richiede spesso anche una variabile artificiale per costruire una base iniziale ammissibile.
Errori comuni
- Dimenticare la non negatività. x,y\ge0 sono vincoli a tutti gli effetti: ometterli cambia la regione ammissibile.
- Cercare l’ottimo all’interno. L’ottimo di una PL è sempre su un vertice/spigolo, mai strettamente interno alla regione.
- Confondere scarto e surplus. I vincoli \le usano variabili di scarto (+s); i vincoli \ge usano variabili di surplus (-s).
- Non riconoscere l’illimitatezza. Se Z cresce senza limite, di solito manca un vincolo di capacità: è un errore di modello, non un risultato.
- Ignorare gli ottimi multipli. Se l’obiettivo è parallelo a un lato attivo, tutti i punti di quel lato possono essere ottimi.