Estratto del documento

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

Anteprima
Vedrai una selezione di 6 pagine su 22
Formulario con esercizi di Ricerca operativa  Pag. 1 Formulario con esercizi di Ricerca operativa  Pag. 2
Anteprima di 6 pagg. su 22.
Scarica il documento per vederlo tutto.
Formulario con esercizi di Ricerca operativa  Pag. 6
Anteprima di 6 pagg. su 22.
Scarica il documento per vederlo tutto.
Formulario con esercizi di Ricerca operativa  Pag. 11
Anteprima di 6 pagg. su 22.
Scarica il documento per vederlo tutto.
Formulario con esercizi di Ricerca operativa  Pag. 16
Anteprima di 6 pagg. su 22.
Scarica il documento per vederlo tutto.
Formulario con esercizi di Ricerca operativa  Pag. 21
1 su 22
D/illustrazione/soddisfatti o rimborsati
Acquista con carta o PayPal
Scarica i documenti tutte le volte che vuoi
Dettagli
SSD
Scienze matematiche e informatiche MAT/09 Ricerca operativa

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher gaio_milanista di informazioni apprese con la frequenza delle lezioni di Ricerca operativa e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Universitas Mercatorum di Roma o del prof Patella Sergio Maria.
Appunti correlati Invia appunti e guadagna

Domande e risposte

Hai bisogno di aiuto?
Chiedi alla community