• Non ci sono risultati.

Corso di Ottimizzazione Prova scritta dell’11 Gennaio 2013 Tempo a disposizione: ore 2:30.

N/A
N/A
Protected

Academic year: 2021

Condividi "Corso di Ottimizzazione Prova scritta dell’11 Gennaio 2013 Tempo a disposizione: ore 2:30."

Copied!
1
0
0

Testo completo

(1)

Corso di Ottimizzazione

Prova scritta dell’11 Gennaio 2013 Tempo a disposizione: ore 2:30.

Si ricorda che:

• Per quanto possibile, occorre scrivere in bella calligrafia (il testo illeggibile non verrà preso in considerazione).

• Su tutti i fogli che vi abbiamo consegnato occorre riportare cognome, nome e numero di matricola.

• Occorre riportare in modo chiaro tutti i passi che portano alla determinazione del risultato.

• Il numero dell’esercizio che si sta svolgendo va sempre riportato in modo chiaro.

• Non è consentita la consultazione di appunti, libri, etc.

• Non è consentito l’uso di calcolatrici, telefoni cellulari, etc.

• Non è concesso chiedere alcunché ai docenti e agli altri studenti.

• Occorre consegnare anche la brutta copia ai docenti.

Esercizio 1. (Punti 3, la risposta occupi al massimo 10 righe)

Si dia una definizione del concetto di preflusso, spiegandone brevemente il ruolo negli algoritmi per problemi di flusso visti durante il corso.

Esercizio 2. (Punti 8)

Un’azienda ha a disposizione n operai e ha bisogno di svolgere m attività diverse. Basta che un operaio si dedichi ad un’attività perché quest’ultima possa ritenersi completata. Diversi operai impiegano tempi diversi per svolgere la stessa attività; indichiamo quindi con cij il costo che l’azienda sostiene nel far svolgere l’attività j all’operaio i, dove i ∈ {1, . . . , n} e j ∈ {1, . . . , m}.

Occorre ovviamente che tutte le attività siano svolte. Inoltre, l’operaioi non può svolgere più di bi

attività diverse, per ragioni contrattuali. Si formuli il problema di minimizzare il costo complessivo sostenuto dall’azienda come problema PLI.

Esercizio 3. (Punti 8)

Si risolva tramite l’algoritmo del simplesso primale, il seguente problema di programmazione lin- eare:

max x1− 2x2

x2≥ x1− 2 x2≤ 6 − x1

x2≤ x1+ 2 x1≥ 1 x2≥ 1 Si parta dalla base ammissimileB = {4, 5}.

Esercizio 4. (Punti 8)

Si determini il flusso massimo tra s e t nel seguente grafo, utilizzando l’Algoritmo di Edmonds e Karp.

s t

6 7

1 2 2 8 3 3 5

Esercizio 5. (Punti 3, la risposta occupi al massimo 15 righe)

Si enunci il Teorema di decomposizione dei poliedri (o Teorema di Motzkin) e se ne descriva il ruolo nella geometria della programmazione lineare.

Riferimenti

Documenti correlati

Il costo di esecuzione di un lavoro i dipende da quanti lavori sono stati eseguiti prima di i: se i è il j-esimo lavoro ad essere eseguito, il suo costo è c ij , anche’esso

Per ragioni di mercato, infine, l’azienda vuole evitare che ciascuno dei tre modelli venga prodotto in un numero di unità superiore alla metà del numero totale dei PC prodotti..

• Occorre riportare in modo chiaro tutti i passi che portano alla determinazione del risultato.. • Il numero dell’esercizio che si sta svolgendo va sempre riportato in

Si determini, in PLI, come costruire i gruppi in modo tale che la media delle medie aritmetiche degli studenti di ogni gruppo sia inclusa tra 24 e 28, e che il numero di

Si ricorda che un tale cammino è nient’altro che una sequenza di archi adiacenti che connettano s a t, e il suo costo è la somma dei costi degli archi che lo compongono.

(Punti 3, la risposta occupi al massimo 10 righe) Si diano le definizioni di cono convesso e di cono finitamente generato..

Il Corso di Laurea Magistrale in Informatica di un certo Ateneo (certo non di quello bolognese!) è organizzato in modo molto liberale: vengono offerti n corsi 1,.. , n, gli elementi

Si formuli in PLI il problema di determinare da chi acquistare il carburante necessario ogni mese in modo da minimizzare il costo complessivo e da rispettare il requisito