Programmazione lineare: modelli e metodo grafico

La ricerca operativa studia modelli e algoritmi per prendere decisioni: quanto produrre, come distribuire le risorse, come far funzionare una rete elettrica al costo minimo. Il primo passo è sempre lo stesso: tradurre il problema reale in un modello matematico. Il caso più semplice è la programmazione lineare (PL).

Gli ingredienti di un modello

Ogni modello di ottimizzazione ha tre parti:

• le variabili decisionali: le scelte da fare, espresse come numeri;
• i vincoli: le condizioni che le scelte devono rispettare. In generale ammettono infinite combinazioni, che formano la regione ammissibile;
• la funzione obiettivo: il criterio per scegliere, tra le soluzioni ammissibili, quella migliore.

Esempio: quanto produrre

Un piccolo laboratorio assembla due prodotti per impianti solari: inverter e batterie. Ogni settimana ha 14 ore di collaudo: un inverter ne richiede 2, una batteria 1. Il fornitore consegna al massimo 6 moduli di celle a settimana, e ogni batteria ne usa uno. Il profitto è di 4 k€ per inverter e 3 k€ per batteria. Quanto produrre di ciascuno?

Le variabili. $x_1$ e $x_2$, gli inverter e le batterie prodotti a settimana. Non possono essere negativi, perché una produzione negativa non ha senso: $x_1 \ge 0$, $x_2 \ge 0$.

I vincoli. Il tempo di collaudo usato non può superare quello disponibile, e le batterie non possono superare i moduli consegnati:

$$2x_1 + x_2 \le 14 \qquad x_2 \le 6$$

L'obiettivo. Massimizzare il profitto settimanale, $\omega = 4x_1 + 3x_2$ (k€/settimana).

Il modello completo:

$$\begin{aligned} \max \ \omega &= 4x_1 + 3x_2 \\ 2x_1 + x_2 &\le 14 \\ x_2 &\le 6 \\ x_1,\ x_2 &\ge 0 \end{aligned}$$

La regione ammissibile

Con due variabili ogni soluzione è un punto del piano $(x_1, x_2)$, e ogni vincolo è un semipiano: per esempio $2x_1 + x_2 \le 14$ sono tutti i punti sotto la retta $2x_1 + x_2 = 14$. La regione ammissibile è l'intersezione dei semipiani: qui il quadrilatero di vertici O, A, B e C.

L'ottimo: le rette di livello

Fissato un valore del profitto, per esempio $\omega = 18$, i punti con quel profitto formano una retta, $4x_1 + 3x_2 = 18$. Cambiando $\omega$ si ottengono rette tutte parallele tra loro: ricavando $x_2$,

$$x_2 = -\tfrac{4}{3}\, x_1 + \tfrac{\omega}{3}$$

la pendenza è sempre $-4/3$, e $\omega$ sposta solo l'intercetta. Aumentare il profitto vuol dire spostare la retta verso l'alto. Conviene spingerla il più in alto possibile, finché tocca ancora la regione ammissibile.

L'ultimo punto toccato è il vertice B (4, 6), con $\omega = 4 \cdot 4 + 3 \cdot 6 = 34$ k€ a settimana. La soluzione ottima è quindi produrre 4 inverter e 6 batterie.

l'ottimo, se esiste, si trova in un vertice della regione ammissibile. È ciò che permette al metodo del simplesso di cercarlo saltando da un vertice all'altro, senza esplorare gli infiniti punti interni.

Numero di soluzioni

Non tutti i problemi hanno un unico ottimo. I casi possibili sono quattro:

Un solo ottimo, come nell'esempio.

Infinite soluzioni ottime. Se il profitto delle batterie scende da 3 a 2 k€, le rette di livello $4x_1 + 2x_2 = \omega$ diventano parallele al vincolo $2x_1 + x_2 = 14$. Spingendole verso l'alto, l'ultima tocca un intero lato della regione: tutti i punti del segmento tra A (7, 0) e B (4, 6) danno lo stesso profitto, 28 k€.

Nessuna soluzione ammissibile. I vincoli possono essere incompatibili, e allora la regione ammissibile è vuota. Il riquadro qui sotto mostra un esempio con vincoli di tipo diverso, una miscela di mangime, in cui basta cambiare un dato perché la regione sparisca. Torneremo su questo esempio nell'articolo sulla Fase 1 del simplesso.

Obiettivo illimitato. Se la regione ammissibile non è chiusa nella direzione in cui l'obiettivo migliora, non c'è un massimo. Per esempio, con i vincoli $-x_1 + x_2 \le 2$ e $x_1 - 2x_2 \le 2$ si può aumentare $4x_1 + 3x_2$ quanto si vuole, muovendosi lungo la direzione $x_1 = 2x_2$.

Un modello con vincoli di tutti i tipi: la miscela di mangime

Un allevamento prepara ogni giorno esattamente 10 kg di mangime mescolando due ingredienti, I1 e I2, che costano 2 € e 3 € al kg. Per ogni kg, I1 contiene 3 unità di fibra e 4 di proteine, I2 una di fibra e 2 di proteine. La miscela deve avere al massimo 22 unità di fibra e almeno 26 di proteine. Con $x_1$ e $x_2$ i kg dei due ingredienti:

$$\begin{aligned} \min \ \varphi &= 2x_1 + 3x_2 \\ 3x_1 + x_2 &\le 22 \\ 4x_1 + 2x_2 &\ge 26 \\ x_1 + x_2 &= 10 \\ x_1,\ x_2 &\ge 0 \end{aligned}$$

Qui ci sono un vincolo $\le$, uno $\ge$ e uno $=$. Il vincolo di uguaglianza è una retta, non un semipiano, quindi la regione ammissibile si riduce al segmento tra D (3, 7) e C (6, 4). L'ottimo è in C, con un costo di $\varphi = 24$ €.

Se la miscela da preparare scende a 6,5 kg, la regione si riduce a un solo punto, (6,5; 0). Se scende a 6 kg, la regione è vuota: con così poco mangime non si riescono a raggiungere le 26 unità di proteine.

Riepilogo

• Un modello di ottimizzazione ha variabili decisionali, vincoli e una funzione obiettivo. È di programmazione lineare se le variabili sono reali e le funzioni lineari.
• I vincoli definiscono la regione ammissibile; con due variabili si disegna come intersezione di semipiani.
• Le rette di livello dell'obiettivo sono parallele: si spingono nella direzione in cui l'obiettivo migliora fino all'ultimo punto della regione.
• L'ottimo, se esiste, sta in un vertice. Può però essere non unico (un lato intero), non esistere perché la regione è vuota, o non esistere perché l'obiettivo è illimitato.