Programmazione lineare — Metodo del simplesso e soluzione grafica

La programmazione lineare è un metodo per trovare il valore migliore di una funzione obiettivo lineare, come il profitto massimo o il costo minimo, soggetto a vincoli lineari. In un problema con due variabili, la soluzione grafica individua la regione ammissibile e ne controlla i vertici. Nei problemi più grandi, il metodo del simplesso usa algebricamente la stessa idea dei vertici.

Usa la programmazione lineare solo quando la funzione obiettivo e i vincoli sono lineari. Se la relazione si piega, è curva o dipende da prodotti come $xy$, il modello non è un problema di programmazione lineare.

Definizione di programmazione lineare

$$\text{maximize or minimize } z = c_1x_1 + c_2x_2 + \cdots + c_nx_n$$

soggetto a vincoli come

$$a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n \le b_1$$

più disequazioni lineari simili, insieme a condizioni come $x_i \ge 0$ quando i valori negativi non hanno senso.

L’insieme di tutti i punti che soddisfano ogni vincolo si chiama regione ammissibile. La programmazione lineare chiede: tra questi punti ammissibili, quale fornisce il miglior valore della funzione obiettivo?

Come funziona il metodo grafico

Se ci sono solo due variabili decisionali, puoi disegnare ogni vincolo nel piano $xy$. La sovrapposizione di tutte le regioni consentite è la regione ammissibile.

Ogni punto di quella regione è una soluzione valida. La funzione obiettivo assegna un valore a ciascuno di essi.

Per i problemi di programmazione lineare, un fatto fondamentale è questo: se esiste una soluzione ottima, allora almeno una soluzione ottima si trova in un vertice della regione ammissibile. Per questo il metodo grafico si concentra sui vertici invece di controllare ogni punto della regione ombreggiata.

Esempio svolto: risolvere graficamente un problema di programmazione lineare

Supponiamo che un’azienda produca due prodotti, $A$ e $B$.

• Profitto per unità di $A$: $3$
• Profitto per unità di $B$: $5$
• Limite di tempo macchina: ogni unità di $A$ usa $1$ ora, ogni unità di $B$ usa $2$ ore, e sono disponibili al massimo $8$ ore
• Limite di assemblaggio: ogni unità di $A$ usa $1$ ora, ogni unità di $B$ usa $1$ ora, e sono disponibili al massimo $5$ ore

Sia $x$ il numero di unità di $A$ e $y$ il numero di unità di $B$.

Massimizzare

$$P = 3x + 5y$$

soggetto a

$$x + 2y \le 8$$ $$x + y \le 5$$ $$x \ge 0,\quad y \ge 0$$

Trova i vertici

Dagli assi e dalle rette dei vincoli, i vertici ammissibili sono

• $(0,0)$
• $(5,0)$
• $(0,4)$
• $(2,3)$

Il punto $(2,3)$ si ottiene risolvendo le equazioni di frontiera

$$x + 2y = 8,\quad x + y = 5$$

Sottraendo si ottiene $y = 3$, e quindi $x = 2$.

Valuta l’obiettivo in ogni vertice

Calcola il profitto in ogni vertice:

• In $(0,0)$, $P = 0$
• In $(5,0)$, $P = 15$
• In $(0,4)$, $P = 20$
• In $(2,3)$, $P = 21$

Quindi il profitto massimo è

$$P = 21$$

in

$$(x,y) = (2,3)$$

Questo è il metodo grafico in una frase: rappresenta la regione ammissibile, trova i vertici e valuta lì la funzione obiettivo.

Intuizione del metodo del simplesso

Il metodo grafico è pratico solo quando ci sono due variabili, e talvolta tre se sei disposto a immaginare una regione tridimensionale. I problemi reali di ottimizzazione hanno spesso molte variabili, quindi disegnare la regione ammissibile non è più realistico.

Il metodo del simplesso mantiene la stessa logica dei vertici, ma la applica algebricamente. In termini generali, passa da un vertice ammissibile a un altro che migliora l’obiettivo, e si ferma quando nessuno spostamento adiacente produce un valore migliore.

Quindi un buon modello mentale è:

• Metodo grafico: vedere i vertici
• Metodo del simplesso: muoversi tra i vertici senza disegnarli

Questa descrizione dà l’intuizione, non l’algoritmo completo. La procedura effettiva del simplesso usa una tabella o una forma algebrica equivalente per decidere quale variabile entra ed esce a ogni passo.

Perché i vertici contano

Le funzioni obiettivo lineari generano rette di livello come

$$3x + 5y = k$$

per diversi valori di $k$. Se fai scorrere quella retta nella direzione di profitto crescente, l’ultimo punto in cui tocca ancora la regione ammissibile è dove si verifica il massimo.

In molti grafici, quest’ultimo contatto avviene in un singolo vertice. Se la retta dell’obiettivo è parallela a un lato di frontiera, più punti su quel lato possono essere tutti ottimali. Anche in quel caso, esiste comunque almeno un vertice ottimale.

Errori comuni

Confondere ammissibile con ottimale

Un punto può soddisfare tutti i vincoli e comunque non massimizzare o minimizzare l’obiettivo. Ammissibile significa solo consentito.

Dimenticare le condizioni di non negatività

Se $x$ e $y$ rappresentano quantità che produci o spedisci, i valori negativi di solito non hanno senso. Omettere $x \ge 0$ oppure $y \ge 0$ può cambiare il problema.

Supporre che ogni risposta debba essere un numero intero

La programmazione lineare standard ammette valori frazionari. Se le variabili devono essere intere, come il numero di camion o di lavoratori, serve un modello di programmazione intera o un’ulteriore condizione di integrità.

Supporre che ogni problema abbia una soluzione migliore

Alcuni problemi di programmazione lineare sono inammissibili, cioè nessun punto soddisfa tutti i vincoli. Altri sono illimitati, cioè l’obiettivo può migliorare senza limite. Si ottiene un ottimo finito solo quando i vincoli delimitano davvero abbastanza il problema.

Usare il metodo grafico quando ci sono troppe variabili

Quando le variabili sono molte, il grafico non è più lo strumento giusto. È qui che il simplesso o altri metodi di ottimizzazione diventano necessari.

Quando si usa la programmazione lineare

La programmazione lineare si usa quando decisioni diverse competono per risorse limitate e sia l’obiettivo sia i vincoli possono essere modellati linearmente. Esempi tipici includono pianificazione della produzione, trasporti, assegnazione del personale, miscelazione, schedulazione e allocazione del budget.

Il modello è valido solo quanto lo sono le sue ipotesi. Se la relazione reale non è abbastanza vicina a essere lineare, oppure se le variabili devono essere intere, un normale problema di programmazione lineare può essere solo un punto di partenza.

Prova un problema simile

Prendi un piccolo problema testuale con due prodotti, due limiti di risorse e una funzione di profitto. Scrivi le variabili, rappresenta i vincoli e verifica da solo i vertici. Quando questa idea diventa chiara, il metodo del simplesso è molto più facile da capire perché estende la stessa logica a dimensioni maggiori.