• Non ci sono risultati.

Sistemi Organizzativi a.a. 2003-2004

N/A
N/A
Protected

Academic year: 2021

Condividi "Sistemi Organizzativi a.a. 2003-2004"

Copied!
2
0
0

Testo completo

(1)

Sistemi Organizzativi a.a. 2003-2004

prova scritta 17-12-2003

Esercizio 1 Dimostrare o confutare la seguente a®ermazione: l'algoritmo di Lawler calcola una soluzione ottima del problema 1=prec=

Pj

L

j

.

Esercizio 2 Calcolare una soluzione ottima della seguente istanza del problema 1=prec=

Pj

w

j

C

j

:

job 1 2 3 4 5 w

j

2 2 5 9 5 p

j

3 2 4 6 4 d

j

3 7 4 7 8 precedenze:

prec(1) = NIL; prec(2) = 1; prec(3) = 2; prec(4) = NIL; prec(5) = 2,4;

Descrivere in modo sintentico ma completo i vari passi dell'algoritmo utilizzato.

Esercizio 3 Si considerino i dati dell'esercizio 2 e si calcoli una soluzione ottima del problema 1=prec=L

max

.

Domanda 1 Descrivere un algoritmo di programmazione dinamica per il problema 1==

Pj

T

j

illustrando i risultati teorici su cui esso µe basato.

Domanda 2 Dimostrare il rapporto di approssimazione dell'algoritmo LPT (Longest

Processing Time) per il problema P

m

==C

max

.

(2)

Soluzione esercizio 1 Basta dimostrare che EDD non µe ottima per il caso senza precedenze. Controesempio:

job 1 2

p

j

1 9

p

j

10 9

Riferimenti

Documenti correlati

Inoltre, visto che il cilindro rotola senza strisciare, la velocit` a del centro di massa e la velocit` a angolare sono legate tra loro da v c

Il disco durante la rotazione non varia la sua energia potenziale quindi tutto si riduce alla variazione di energia potenziale della sferetta, ossia.. E f

L’energia cinetica del centro di massa alla fine del piano, sommata all’energia cinetica di rotazione appena ricavata dovr` a essere uguale all’energia potenziale

Con queste informazioni siamo in grado di calcolare il lavoro totale svolto sul gas durante il ciclo come la somma dei lavori sulle singole trasformazioni o, alternativamente,

Per calcolare la volocit` a un istante prima dell’impatto con il suolo possiamo considerare la conservazione dell’energia meccanica, tenendo conto che l’energia

(24) Per ricavare l’energia dissipata dopo un giro della puleggia ` e sufficiente calcolare il lavoro fatto dalla forza d’attrito sul blocco m 1 e sul blocco m 2 su uno spostamento

Possiamo ragionare nel modo seguente: se Mario raggiunge la sommit` a del suo salto nello stesso istante in cui il fungo inizia a cadere i due, nonostante le masse diverse,

Per poter fare il giro della morte due volte deve avere velocit` a v 0 (ricavata nel punto 1) dopo avere attraversato per due volte il tratto scabro di lunghezza L, una prima