<marco />
← Tutti gli articoli
11 min di lettura

Programmazione lineare: esercizi con soluzioni

ottimizzazione

Questi esercizi ripassano la serie sulla programmazione lineare: modelli e metodo grafico, il simplesso passo per passo, il simplesso con le matrici, la Fase 1, la dualità e l'analisi di sensitività. Sono in ordine di difficoltà. Ogni soluzione è nascosta: aprila solo dopo averci provato.

Modelli e metodo grafico

Esercizio 1: costruire il modello

Una fabbrica produce due articoli in tre reparti. L'articolo 1 richiede 1 ora nel reparto A e 2 ore nel reparto C; l'articolo 2 richiede 2 ore nel reparto B e 3 ore nel reparto C. Ogni settimana sono disponibili 6 ore nel reparto A, 16 nel B e 30 nel C. Il profitto è di 4 k€ per l'articolo 1 e 3 k€ per l'articolo 2. Scrivi il modello di programmazione lineare.

Soluzione

Variabili: x1x_1 e x2x_2, le unità prodotte a settimana dei due articoli, con x1,x2≥0x_1, x_2 \ge 0. Un vincolo per reparto, e il profitto come obiettivo:

max⁡ ω=4x1+3x2x1≤62x2≤162x1+3x2≤30x1, x2≥0\begin{aligned} \max \ \omega &= 4x_1 + 3x_2 \\ x_1 &\le 6 \\ 2x_2 &\le 16 \\ 2x_1 + 3x_2 &\le 30 \\ x_1,\ x_2 &\ge 0 \end{aligned}

Esercizio 2: risolvere con il metodo grafico

Risolvi graficamente il modello dell'esercizio 1.

Soluzione

La regione ammissibile ha cinque vertici. Basta calcolare l'obiettivo in ognuno:

Vertice (x1,x2)(x_1, x_2) ω=4x1+3x2\omega = 4x_1 + 3x_2
origine (0, 0) 0
(6, 0) 24
(6, 6) 42
(3, 8) 36
(0, 8) 24

L'ottimo è in (6, 6), con ω=42\omega = 42 k€. È l'incrocio dei vincoli dei reparti A e C, che sono quindi attivi: in quei reparti non avanzano ore. Nel reparto B invece se ne usano 12 su 16.

Esercizio 3: che tipo di soluzione?

Per ciascun problema, dì se ha un ottimo unico, infiniti ottimi, nessuna soluzione ammissibile, oppure un obiettivo illimitato. In tutti x1,x2≥0x_1, x_2 \ge 0.

  1. max⁡ x1+x2\max\ x_1 + x_2 con x1+x2≤4x_1 + x_2 \le 4.
  2. max⁡ x1+x2\max\ x_1 + x_2 con x1−x2≤1x_1 - x_2 \le 1.
  3. max⁡ x1+2x2\max\ x_1 + 2x_2 con x1+x2≤2x_1 + x_2 \le 2 e x1+x2≥3x_1 + x_2 \ge 3.
Soluzione
  1. Infiniti ottimi. Le rette di livello sono parallele al vincolo x1+x2=4x_1 + x_2 = 4: tutto il segmento tra (4, 0) e (0, 4) dà ω=4\omega = 4.
  2. Obiettivo illimitato. Si può aumentare x2x_2 quanto si vuole: il vincolo x1−x2≤1x_1 - x_2 \le 1 resta soddisfatto, e ω\omega cresce senza limite.
  3. Nessuna soluzione ammissibile. x1+x2x_1 + x_2 non può essere insieme al massimo 2 e almeno 3.

Il simplesso

Esercizio 4: il simplesso a mano

Porta il modello dell'esercizio 1 in forma standard e risolvilo con il simplesso partendo dall'origine. Al primo passo fai entrare la variabile con il coefficiente più negativo.

Soluzione

Forma standard, con φ=−ω\varphi = -\omega:

x1+s1=62x2+s2=162x1+3x2+s3=304x1+3x2+φ=0\begin{aligned} x_1 + s_1 &= 6 \\ 2x_2 + s_2 &= 16 \\ 2x_1 + 3x_2 + s_3 &= 30 \\ 4x_1 + 3x_2 + \varphi &= 0 \end{aligned}

Iterazione 1. φ=−4x1−3x2\varphi = -4x_1 - 3x_2: entra x1x_1, che ha il coefficiente più negativo. Rapporti: 6/1=66/1 = 6 per s1s_1 e 30/2=1530/2 = 15 per s3s_3, mentre s2s_2 non dipende da x1x_1. Il minimo è 6: esce s1s_1. Nuovo vertice (6, 0), φ=−24\varphi = -24.

Iterazione 2. Con x1=6−s1x_1 = 6 - s_1 l'obiettivo diventa φ=−24−3x2+4s1\varphi = -24 - 3x_2 + 4s_1: entra x2x_2. Rapporti: s2=16−2x2s_2 = 16 - 2x_2 dà 8, s3=18−3x2+2s1s_3 = 18 - 3x_2 + 2s_1 dà 6. Esce s3s_3. Nuovo vertice (6, 6), φ=−42\varphi = -42.

Iterazione 3. Ora φ=−42+2s1+s3\varphi = -42 + 2s_1 + s_3: nessun coefficiente negativo, quindi la soluzione è ottima. x1=6x_1 = 6, x2=6x_2 = 6, ω=42\omega = 42.

Esercizio 5: soluzioni di base

Per il sistema

x1+x2+s1=4x1+s2=3\begin{aligned} x_1 + x_2 + s_1 &= 4 \\ x_1 + s_2 &= 3 \end{aligned}

elenca tutte le scelte di due variabili di base. Per ciascuna, calcola la soluzione di base e dì se è ammissibile.

Soluzione
Variabili di base Soluzione di base Ammissibile?
s1,s2s_1, s_2 s1=4s_1 = 4, s2=3s_2 = 3 sì: punto (0, 0)
x1,s1x_1, s_1 x1=3x_1 = 3, s1=1s_1 = 1 sì: punto (3, 0)
x1,x2x_1, x_2 x1=3x_1 = 3, x2=1x_2 = 1 sì: punto (3, 1)
x2,s2x_2, s_2 x2=4x_2 = 4, s2=3s_2 = 3 sì: punto (0, 4)
x1,s2x_1, s_2 x1=4x_1 = 4, s2=−1s_2 = -1 no
x2,s1x_2, s_1 nessuna non è una base: colonne dipendenti

Nell'ultimo caso le colonne di x2x_2 e s1s_1 sono entrambe (1,0)(1, 0), e con x1=s2=0x_1 = s_2 = 0 la seconda equazione direbbe 0=30 = 3.

Esercizio 6: impostare la Fase 1

min⁡ φ=x1+x2x1+2x2≥4x1+x2=3x1, x2≥0\begin{aligned} \min \ \varphi &= x_1 + x_2 \\ x_1 + 2x_2 &\ge 4 \\ x_1 + x_2 &= 3 \\ x_1,\ x_2 &\ge 0 \end{aligned}

L'origine è ammissibile? Scrivi il problema ausiliario della Fase 1 ed esprimi Ψ\Psi in funzione delle sole variabili non di base.

Soluzione

L'origine non è ammissibile: violerebbe entrambi i vincoli. Si aggiungono uno scarto con il meno al vincolo ≥\ge e una variabile artificiale a ciascuno dei due vincoli:

x1+2x2−s1+t1=4x1+x2+t2=3\begin{aligned} x_1 + 2x_2 - s_1 + t_1 &= 4 \\ x_1 + x_2 + t_2 &= 3 \end{aligned}

Il problema ausiliario è min⁡ Ψ=t1+t2\min\ \Psi = t_1 + t_2, con base iniziale {t1,t2}\{t_1, t_2\}. Ricavando t1t_1 e t2t_2 dalle equazioni e sommando:

Ψ=7−2x1−3x2+s1\Psi = 7 - 2x_1 - 3x_2 + s_1

La Fase 1 arriva a Ψ=0\Psi = 0, perché esistono punti ammissibili: per esempio (2, 1), che è anche l'ottimo del problema originale.

Dualità

Esercizio 7: scrivere il duale

Scrivi il duale di

max⁡ ω=3x1+x2+2x3x1+x3=52x1+x2+x3≤8x1≥0,x2≤0,x3≥0\begin{aligned} \max \ \omega &= 3x_1 + x_2 + 2x_3 \\ x_1 + x_3 &= 5 \\ 2x_1 + x_2 + x_3 &\le 8 \\ x_1 \ge 0, \quad x_2 \le 0, &\quad x_3 \ge 0 \end{aligned}
Soluzione

Con le regole per un primale di massimo:

  • il primo vincolo è un'uguaglianza, quindi y1y_1 è libera;
  • il secondo è ≤\le, quindi y2≥0y_2 \ge 0;
  • x1≥0x_1 \ge 0 e x3≥0x_3 \ge 0 danno vincoli ≥\ge;
  • x2≤0x_2 \le 0 dà un vincolo ≤\le.
min⁡ φD=5y1+8y2y1+2y2≥3y2≤1y1+y2≥2y1 libera,y2≥0\begin{aligned} \min \ \varphi_D &= 5y_1 + 8y_2 \\ y_1 + 2y_2 &\ge 3 \\ y_2 &\le 1 \\ y_1 + y_2 &\ge 2 \\ y_1 \text{ libera}, &\quad y_2 \ge 0 \end{aligned}

Controprova: il primale ha ottimo x=(5; −2; 0)x = (5;\ -2;\ 0) con ω=13\omega = 13, il duale y=(1; 1)y = (1;\ 1) con φD=13\varphi_D = 13. Coincidono, come vuole la dualità.

Esercizio 8: limitare l'ottimo senza risolvere

Per il problema dell'esercizio 1, usa il punto x=(1,1)x = (1, 1) e i prezzi duali y=(4,0,1)y = (4, 0, 1) per trovare un intervallo che contiene l'ottimo, senza risolvere il problema.

Soluzione

Il duale è min⁡ 6y1+16y2+30y3\min\ 6y_1 + 16y_2 + 30y_3 con y1+2y3≥4y_1 + 2y_3 \ge 4, 2y2+3y3≥32y_2 + 3y_3 \ge 3 e y≥0y \ge 0.

  • x=(1,1)x = (1, 1) è ammissibile per il primale (1 ≤ 6, 2 ≤ 16, 5 ≤ 30) e vale ω=7\omega = 7: è un limite inferiore.
  • y=(4,0,1)y = (4, 0, 1) è ammissibile per il duale (4+2≥44 + 2 \ge 4, 0+3≥30 + 3 \ge 3) e vale φD=24+30=54\varphi_D = 24 + 30 = 54: è un limite superiore.

Per la dualità debole, 7≤ω∗≤547 \le \omega^* \le 54. L'ottimo vero, 42, sta nell'intervallo.

Analisi di sensitività

Esercizio 9: leggere il tableau finale

Riprendi il problema delle vernici dell'articolo sull'analisi di sensitività: ottimo con 50 hl di V2 e 50 hl di V3, 5.500 €, prezzi ombra 10 € per un'ora di miscelazione e 30 € per un'ora di confezionamento.

  1. Conviene acquistare un'ora di confezionamento in più a 25 €?
  2. Una nuova vernice richiede 2 ore di miscelazione e 0,5 ore di confezionamento per ettolitro. Da quale profitto in su conviene produrla?
Soluzione
  1. Sì, finché le ore di confezionamento restano tra 100 e 200: un'ora in più fa guadagnare 30 € e ne costa 25, quindi rende 5 € netti. Oltre le 200 ore la base ottima cambia, e il prezzo ombra non vale più.
  2. Le risorse che la nuova vernice consumerebbe valgono, ai prezzi ombra, 10⋅2+30⋅0,5=3510 \cdot 2 + 30 \cdot 0{,}5 = 35 €/hl. Conviene produrla solo se rende più di 35 €/hl. Sotto quella soglia, spostare risorse da V2 e V3 farebbe perdere più di quanto si guadagna.