Conclusione: La regione X è definita dal sistema:
1) 3x₁ + x₂ ≤ 2
2) 3x₁ - x₂ ≤ 1
3) x₁ + 2x₂ ≤ 1
Risultato: ✅ La risposta corretta è: **Opzione 1**.
Esercizio 9 – Scheduling: Confronto tra Job j e k
Abbiamo una sequenza parziale di job S(h), che termina al tempo T.
Due job non ancora schedulati sono j e k, con:
- r_j: tempo di rilascio del job j
- r_k: tempo di rilascio del job k
- p_k: tempo di esecuzione del job k
È dato che:
r_j ≥ max{T, r_k} + p_k
→ cioè j non sarà disponibile nemmeno al termine del job k, anche se k fosse
schedulato subito dopo S(h).
Interpretazione: non ha senso mettere j prima di k nella sequenza finale,
poiché j non sarebbe comunque disponibile.
Risultato: ✅ Possiamo escludere che all'ottimo il job j preceda il job k.
Risposta corretta: **Opzione 3**.
Esercizio 10 – Metodo di Wagner-Whitin:
Interpretazione dell'Espressione Ricorsiva
L'immagine seguente mostra una formula tipica del metodo di Wagner-Whitin
per la programmazione della produzione:
Questa espressione rappresenta una formula ricorsiva che calcola il costo
minimo per soddisfare la domanda dal periodo 1 al periodo k. L'algoritmo
valuta tutte le possibili date di produzione t (da 1 a k), e per ciascuna di esse
computa:
- Il costo ottimo fino al periodo precedente (C(t−1))
- Il costo di produzione nel periodo t per soddisfare la domanda fino a k
- I costi di giacenza derivanti dall'anticipo di produzione rispetto alla domanda
Tra tutte le possibili scelte di t, si prende quella che **minimizza** il costo
totale.
Questa formula quindi fornisce il **valore ottimo** per soddisfare la domanda
nell’intervallo {1, ..., k}.
Risultato: ✅ La risposta corretta è: **Opzione 3** – Il valore ottimo
nell’orizzonte temporale {1, ..., k}.
Esercizio 11 – Risoluzione di un Problema di PL
Dato il seguente problema di programmazione lineare (PL):
Minimizzare: -x₁ - (3/2)x₂ + x₃
Soggetto a:
x₁ + 2x₂ - x₃ = 7
x₂ + x₄ = 4
con x₁, x₂, x₃, x₄ ≥ 0
✅ Proviamo a scegliere come variabili base: x₂ e x₃. Poniamo le altre variabili a
zero:
x₁ = 0, x₄ = 0
Sostituiamo nei vincoli:
Vincolo 1: 0 + 2x₂ - x₃ = 7 ⇒ x₃ = 2x₂ - 7
Vincolo 2: x₂ + 0 = 4 ⇒ x₂ = 4
Sostituiamo x₂ = 4 nel vincolo 1:
x₃ = 2×4 - 7 = 1
Otteniamo la soluzione ammissibile:
x₁ = 0, x₂ = 4, x₃ = 1, x₄ = 0
Verifica: Tutte le variabili sono ≥ 0 ⇒ soluzione ammissibile.
Calcoliamo la funzione obiettivo:
-x₁ - (3/2)x₂ + x₃ = -0 - (3/2)×4 + 1 = -6 + 1 = -5
✅ Risultato: la funzione obiettivo all’ottimo vale: **−5**
Risposta corretta: **Opzione 2**
Esercizio 12 – Derivata Parziale rispetto a x₃
Data la funzione:
f(x₁, x₂, x₃) = x₁ − x₃ + 3x₃^{2/3} + x₂²
Punto P = (1, 0, 8)
Calcoliamo la derivata parziale rispetto a x₃:
∂f/∂x₃ = d/dx₃ (−x₃ + 3x₃^{2/3}) = −1 + 3 × (2/3)x₃^{−1/3} = −1 +
2x₃^{−1/3}
Valutiamo in x₃ = 8:
x₃^{−1/3} = 1 / (8)^{1/3} = 1/2
Quindi:
∂f/∂x₃ = −1 + 2 × (1/2) = −1 + 1 = 0
✅ Risultato: La derivata parziale di f rispetto a x₃ nel punto P è **0**
Risposta corretta: **Opzione 4**
Esercizio 13 – Individuazione della matrice A di un PL
Dato il seguente problema di Programmazione Lineare (PL), si richiede di
individuare la matrice A del sistema di vincoli.
Le quattro possibili risposte sono rappresentate graficamente. Analizzando i
coefficienti dei termini nelle equazioni vincolari, si osserva che la matrice A è
formata dai coefficienti delle variabili decisionali presenti nei vincoli del
problema.
La matrice A è quindi la matrice dei coefficienti dei vincoli, esclusi i termini
noti e la funzione obiettivo.
✅ La matrice A corretta è la seguente:
Risposta corretta: **Opzione 1**
Esercizio 14 – Condizione di Wolfe
La condizione di Wolfe è una delle due condizioni comunemente utilizzate
nella line search per determinare un passo α accettabile lungo una direzione
di discesa. Insieme alla condizione di sufficiente diminuzione (o Armijo), serve
a garantire la convergenza del metodo del gradiente.
Le due condizioni sono:
1. Sufficiente diminuzione (Armijo):
f(x + αd) ≤ f(x) + c₁ α ∇f(x)^T d
2. Curvatura (Wolfe):
∇f(x + αd)^T d ≥ c₂ ∇f(x)^T d
La seconda condizione impone che la derivata direzionale dopo aver
effettuato il passo α lungo la direzione d non sia troppo negativa rispetto a
quella iniziale. Questo significa che si cerca un α tale per cui si assista a un
'aumento' in valore assoluto della derivata direzionale, se questa è negativa.
✅ Risposta corretta: **Opzione 3 – Un aumento in valore assoluto della
derivata direzionale φ'(α) se questa non è positiva**
Esercizio 15 – Knapsack Problema Classico
Dato il seguente problema del Knapsack (zaino), non capacitivo, con capacità
massima B = 9, si vuole massimizzare il profitto totale dato dalla somma dei
profitti degli oggetti selezionati, nel rispetto del vincolo di peso massimo.
Tabella dei dati:
i | pᵢ | wᵢ
1 | 4 | 3
2 | 2 | 4
3 | 3 | 2
4 | 5 | 5
Obiettivo: max ∑ pᵢ xᵢ, con ∑ wᵢ xᵢ ≤ 9 e xᵢ ∈ {0, 1}
Strategia: proviamo tutte le combinazioni ammissibili, dato che il numero di
oggetti è piccolo (4).
Le combinazioni valide (peso ≤ 9) e relativi profitti sono:
- Oggetti 1 + 3 + 4: peso = 3+2+5 = 10 ✅
- Oggetti 1 + 2 + 3: peso = 3+4+2 = 9 → profitto = 4+2+3 = **9**
- Oggetti 1 + 3 + 2: stesso caso → 9
- Oggetti 3 + 4: peso = 2+5 = 7 → profitto = 3+5 = 8
- Oggetti 1 + 4: peso = 3+5 = 8 → profitto = 4+5 = 9
- Oggetti 1 + 3: peso = 3+2 = 5 → profitto = 4+3 = 7
- Oggetti 2 + 4: peso = 4+5 = 9 → profitto = 2+5 = 7
- Oggetti 3 + 1 + 4: peso = 2+3+5 = 10 ✅
- Oggetti 1 + 4 + 3: ✅
- Oggetti 2 + 3 + 4: peso = 4+2+5 = 11 ✅
- Oggetti 3 + 4: 7, profitto = 8
- Oggetti 1 + 3 + 4: peso 10 ✅
- Oggetti 1 + 3: profitto = 7
- Oggetti 2 + 3 + 1: 4+2+3 = 9 → profitto = 2+3+4 = **9**
- Oggetti 3 + 1 + 2: idem
- Oggetti 2 + 4: profitto = 7
L’unica combinazione che porta al profitto massimo **senza superare il peso
massimo di 9** è:
✅ Oggetti 1 + 3 + 4 = peso 3+2+5 = 10 ✅ (non valida)
✅ Oggetti 1 + 2 + 3 = peso 9, profitto = 9
Ma meglio: Oggetti 1 + 3 + 4 ✅ troppo peso
Verifica: Oggetti 1 + 4 = 3+5 = 8 → profitto = 4+5 = 9
Oggetti 3 + 4 = 2+5 = 7 → profitto = 3+5 = 8
✅ Ma se scegliamo oggetti 1 + 3 + 4? Peso = 3+2+5 = 10 ✅ → non
ammissibile.
✅ Oggetti 2 + 3 + 4 = 4+2+5 = 11 ✅
✅ Oggetti 1 + 4 = 3+5 = 8 → profitto = 4+5 = **9**
✅ Dopo analisi esaustiva, si trova che la combinazione migliore è **Oggetti 1
+ 4**, con **FO = 9**
✅ Risposta corretta: **non tra le opzioni date**. Nessuna dà 9. Ma **verifica
combinazione 1 + 3 + 4 = 3+2+5 = 10 ✅**.
Se invece prendiamo Oggetti 1 + 3 = 3+2 = 5 → profitto = 7
Oppure Oggetti 3 + 4 = 2+5 = 7 → profitto = 8
Meglio Oggetti 1 + 4 = 3+5 = 8 → profitto = **9**
✅ Nessuna opzione coincide perfettamente col valore massimo ottenuto.
Forse il testo ha un errore.
Esercizio 16 – Rilassamento del problema 1/r_j/L_max
Dati i seguenti job, con tempi di elaborazione (p_j), tempi di disponibilità (r_j)
e scadenze (d_j):
j | p_j | r_j | d_j
1 | 4 | 0 | 8
2 | 5 | 3 | 12
3 | 3 | 5 | 10
Nel rilassamento del problema 1/r_j/L_max, si rimuove il vincolo dei tempi di
disponibilità r_j, ottenendo una stima ottimistica (lower bound) per il ritardo
massimo L_max.
Applichiamo lo scheduling anticipato, eseguendo i job nell’ordine 1 → 2 → 3:
• C₁ = 4 → L₁ = 4 - 8 = -4
• C₂ = 9 → L₂ = 9 - 12 = -3
• C₃ = 12 → L₃ = 12 - 10 = **2**
Il massimo ritardo è quindi L_max = 2, che rappresenta il valore del
rilassamento (z*_{RLX}).
✅ Conclusione: z*_{INT} ≥ z*_{RLX} = 2
Risposta corretta: **Opzione 2**
Esercizio 17 – Valore della funzione obiettivo
all'ottimo (PL)
Problema di programmazione lineare (PL):
Minimizzare: z = -x₁ - (3/2)x₂ + x₃
Soggetto a:
1) x₁ + 2x₂ - x₃ = 7
2) x₂ + x₄ = 4
con x₁, x₂, x₃, x₄ ≥ 0
Dal secondo vincolo: x₄ = 4 - x₂ ⇒ x₂ ∈ [0, 4]
Dal primo vincolo: x₃ = x₁ + 2x₂ - 7
Sostituendo nella funzione obiettivo:
z = -x₁ - (3/2)x₂ + x₃ = -x₁ - (3/2)x₂ + (x₁ + 2x₂ - 7)
⇒ z = (1/2)x₂ - 7
Poiché z(x₂) è crescente, il minimo si ottiene per x₂ = 0:
⇒ z = (1/2)·0 - 7 = -7
Verifica ammissibilità:
- x₂ = 0 ⇒ x₄ = 4
- x₁ + 0 - x₃ = 7 ⇒ x₃ = x₁ - 7
→ x₁ = 7 ⇒ x₃ = 0 ⇒ soluzione ammissibile: (x₁, x₂, x₃, x₄) = (7, 0, 0, 4)
✅ Risposta corretta: Opzione 1 – z = -7
Esercizio 18 – Knapsack 0-1 non frazionabile
Dati i seguenti oggetti con pesi wᵢ e profitti pᵢ, e una capienza dello zaino B =
9:
i | pᵢ | wᵢ
1 | 4 | 3
2 | 2 | 4
3 | 3 | 2
4 | 5 | 5
Il problema consiste nel determinare la combinazione di oggetti che
massimizza il profitto, senza superare la capacità di 9.
Analizzando tutte le combinazioni possibili (0-1 knapsack):
- 1 + 2 + 3: peso 9, profitto 9
- 1 + 3: peso 5, profitto 7
- 1 + 4: peso 8, profitto 9
- 3 + 4: peso 7, profitto 8
- 2 + 4: peso 9, profitto 7
- 1 + 2: peso 7, profitto 6
La combinazione ottima con peso ≤ 9 è: oggetti 1 + 2 + 3 (peso 9, profitto
9).
✅ Nessuna combinazione porta a un profitto di 13 restando sotto la capacità B
= 9.
✅ Risposta corretta: **2 – 11** (se frazionabile); **9** se 0-1
Esercizio 19 – Condizione sufficiente per minimo locale
Domanda:
Affinché x* sia un punto di minimo locale di una funzione f due volte
continuamente differenziabile è sufficiente che:
1) ∇f(x*) = 0 e ∇²f(x*) è semidefinita positiva ✅
2) ∇f(x*) ≠ 0 e ∇²f(x*) è semidefinita positiva ✅
3) ∇f(x*) = 0 e ∇²f(x*) è definita positiva ✅
4) ∇f(x*) ≥ 0 e ∇²f(x*) è semidefinita positiva ✅
✅ Risposta corretta: Opzione 1
Spiegazione:
Per determinare se x* è un punto di minimo locale per una funzione f : ℝⁿ → ℝ
due volte continuamente differenziabile, si verifica che:
- il gradiente si annulla: ∇f(x*) = 0 (punto stazionario),
- la matrice Hessiana
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.