• Non ci sono risultati.

Prova Totale di

N/A
N/A
Info
Scarica
Protected

Academic year: 2021

Condividi "Prova Totale di"

Copied!
2
0
0

Caricamento.... (Visualizza il testo completo ora)

Scarica adesso ( 2 pagine )

Testo completo

(1)

Prova Totale di Ottimizzazione Combinatoria 2 31 gennaio 2008

Cognome __________________

Nome __________________

Matricola __________________

Esercizio 1

Si consideri la seguente formulazione P di un certo problema di PL-{0,1}:

8 ,..., 1 1

0

3 2 1

1 1 1 1 1 1

8 6 5 3 2 1

8 7 1

8 7 6

8 6 5

8 5 4

8 4 3

8 3 2

8 2 1

=

!

"

"

"

+ + + + +

"

+ +

"

+ +

"

+ +

"

+ +

"

+ +

"

+ +

"

+ +

i x

x x x x x x

x x x

x x x

x x x

x x x

x x x

x x x

x x x

i

Date le disuguaglianze

3 : x

1

+ x

2

+ x

3

+ x

4

+ x

5

+ x

6

+ x

7

!

I e

3 : x

1

+ x

2

+ x

3

+ x

4

+ x

5

+ x

6

+ x

8

!

J ,

dimostrare o confutare le seguenti affermazioni:

1. I e J sono valide per conv(S) (dove S = P I { 0 , 1 }

8

).

2. I e J inducono facce massimali di conv(S).

Esercizio 2

Si consideri il seguente problema di Programmazione Lineare Intera:

!

min "2x

1

" x

2

"x

1

+ 3x

2

+ x

3

= 3 8x

1

+ x

2

+ x

4

= 28

x # Z

+4

Ricavare la soluzione ottima del rilassamento lineare e per ogni componente frazionaria ottenere un taglio di Gomory.

Facoltativo: Rappresentare geometricamente la regione ammissibile del rilassamento lineare, la sua soluzione ottima e i tagli di Gomory.

Esercizio 3

Preprocessare il seguente problema di Programmazione Lineare:

(2)

Prova Totale di Ottimizzazione Combinatoria 2 31 gennaio 2008

Cognome __________________

Nome __________________

Matricola __________________

!

max6x

1

" x

2

+ 4 x

3

s.t.

6x

1

" 3x

2

+ 9x

3

# 12 3x

1

+ 4 x

2

+ 3x

3

# 6 5x

1

+ 8x

2

" 2x

3

$ 7 0 # x

1

# 5

0 # x

2

# 1 2 # x

3

Esercizio 4 Dato il problema:

!

max12x

1

+ 8x

2

+ 7x

3

+ 15x

4

+ 21x

5

+ 22x

6

+ 14 x

7

s.t.

14 x

1

+ 8x

2

+ 6x

3

+ 12x

4

+ 15x

5

+ 18x

6

+ 9x

7

" 30 x # {0,1}

7

1. calcolare il rilassamento lineare e i costi ridotti

2. sapendo che il problema ammette la soluzione (0, 0, 1, 0, 1, 0, 1) di valore 42, verificare se è possibile fissare a 0 oppure a 1 le variabili del rilassamento lineare.

Esercizio 5

Un certo problema P ammette la seguente formulazione:

!

15x

1

+ 24 x

2

+ 14 x

3

+ 13x

4

+ 16x

5

+ 34 x

6

+ 17x

7

" 72 x # {0,1}

7

1. Dimostrare che la disequazione

!

x

2

+ x

3

+ x

4

" 2 è valida nel sottospazio x

1

=0, x

5

=0, x

6

=1, x

7

=0

2. Estendere la validità della disequazione all’intero spazio tramite la procedura di lifting sequenziale

Esercizio 6

Dato il problema di PL-{0,1}

!

max13x

1

+ 16x

2

+ 25x

3

+ 35x

4

s.t.

6x

1

+ 3x

2

+ 4 x

3

" 12 9x

2

+ 4 x

3

+ 8x

4

" 16 9x

1

+ 16x

4

" 22

x # 0,1 { }

4

Risolverlo con l’algoritmo di cut-and-branch.

Riferimenti

Scarica adesso ( PDF - 2 pagine - 260.18 KB )

Documenti correlati

Esercizio facoltativo

Quindi il problema di trovare A si riconduce a calcolare le radici terze

Esercizio facoltativo

[r]

Esercizio facoltativo

[r]

SOLUZIONE ESERCIZIO 1

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

SOLUZIONE ESERCIZIO 1

(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

SOLUZIONE ESERCIZIO 1

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,

SOLUZIONE ESERCIZIO 1

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

Soluzione Esercizio 2

Poich´ e l’attrito tra il carrello e il binario ` e trascurabile, la risultante delle forze esterne agenti sul sistema carrello-persona ` e nulla lungo la componente parallela