• Non ci sono risultati.

 Matricola: |__|__|__|__|__|__| Nome: |__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__| |__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__| 1Cognome: RICERCA OPERATIVAGRUPPO Dprova scr

N/A
N/A
Info
Scarica
Protected

Academic year: 2021

Condividi " Matricola: |__|__|__|__|__|__| Nome: |__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__| |__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__| 1Cognome: RICERCA OPERATIVAGRUPPO Dprova scr"

Copied!
1
0
0

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

Scarica adesso ( 1 pagine )

Testo completo

(1)

RICERCA OPERATIVA GRUPPO D

prova scritta del 13 luglio 2004 FOGLIO 1

Cognome: |__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|

Nome: |__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|

Matricola: |__|__|__|__|__|__|

Rispondere alle seguenti domande marcando a penna la lettera corrispondente alla risposta ritenuta corretta (una sola tra quelle riportate).

Ogni risposta esatta vale 2 punti, ogni risposta sbagliata vale –1 punto.

1. Dato un grafo asimmetrico G = (V, E), si consideri la famiglia  costituita da tutti gli insiemi di archi A per i quali ogni u  V è origine di al più un arco in A. La coppia (E, )

[A] costituisce un matroide. Si associ infatti a G un grafo bipartito B = (V, V, F) dove uv  F se e solo se uv  E. Evidentemente ogni A   corrisponde a un insieme di archi di E che è un assegnamento.

[B] è subclusiva ma non costituisce un matroide [C] non è subclusiva

2. Dato un grafo simmetrico costituito da un numero k di cicli per complessivi n nodi è sempre possibile aggiungere a esso n – 3k archi in modo che il grafo risultante

[A] sia una clique

[B] non contenga cicli dispari [C] sia cordale

Risolvere i seguenti esercizi. La soluzione di ogni esercizio viene valutata fino a 5 punti.

1. Dato un grafo simmetrico G = (V, E), sia c: E  IR

+

una funzione peso associata agli archi. Per ogni Y  E si definisca poi il peso di Y come c(Y) = min{c(uv): uv  Y}. Consideriamo il caso in cui Y è un matching perfetto (si noti che tale insieme potrebbe non esistere). Formulare come programmazione lineare intera il problema di determinare un siffatto insieme Y di peso massimo.

Soluzione:

variabili di decisione y

uv

= 1 se e solo se uv  Y z = peso dell’insieme ottimo vincoli 

v:uvE

y

uv

= 1 per ogni u  V

z < c

uv

y

uv

per ogni uv  E y

uv

 {0, 1} per ogni uv  E z  IR

obiettivo max z

2. Data una scacchiera 33 si formuli il problema di calcolare il massimo numero di cavalli che non si diano scacco reciproco come problema di ottimizzazione combinatoria su di un opportuno grafo G = (V, E).

Soluzione

V = insieme delle caselle della scacchiera, |V| = 9

uv  E se e solo se un cavallo in posizione u e uno in posizione v si dànno scacco U = V

 = {X  U: X è stabile}

c(X) = |X| per ogni X  

(2)

3. Applicando il metodo di Fourier-Motzkin, determinare il poliedro che rappresenta l’involucro convesso dei punti (3, 0, 2) e (0, 1, 4).

Soluzione

Per definizione di involucro convesso deve aversi 3 

1

= x

1

2

= x

2

2 

1

+ 4 

2

= x

3

con 

1

+ 

2

= 1

1

, 

2

> 0

In altri termini si tratta di eliminare le variabili 

1

, 

2

dal poliedro di IR

5

: 3 

1

– x

1

= 0

2

– x

2

= 0 2 

1

+ 4 

2

– x

3

= 0

1

+ 

2

= 1

1

, 

2

> 0

Riportando il sistema in termini di disuguaglianze possiamo scrivere la seguente tabella dei coefficienti:

1

2

x

1

x

2

x

3

3 –1 0

–3 1 0

1 –1 0

–1 1 0

2 4 –1 0

–2 –4 1 0

1 1 1

–1 –1 –1

1 0

1 0

Rispetto alla colonna 1 si ha Z = {3, 4, 10}, N = {2, 6, 8}, P = {1, 5, 7, 9}. Pertanto

1

2

x

1

x

2

x

3

12 2 –3 0

3 1 3

1 0

1 –1 0

–1 1 0

–12 –2 3 0

–2 2

–4 1 0

–3 1 –3

2 –1 –2

–1 –1

1 0

11 12 13

21 22 23

31 32 33

(3)

Rispetto alla colonna 2 si ha Z = {3}, N = {5,6,7,8,9,11}, P = {1, 2, 4, 10,12}. Pertanto

1

2

x

1

x

2

x

3

2 12 -3 0

2 0 -3 12

2 0 0 0

2 0 1 -12

2 0 -3 -12

1 3 0 3

2 0 3 12

2 0 0 12

4 0 3 12

1 0 1 0

1 0 0 0

-2 -12 3 0

0 2 0 2

0 -4 1 0

0 -3 1 -3

0 2 -1 -2

0 -1 0 -1

0 2 -1 -2

0 1 0 0

-2 0 -3 -12

-2 0 3 0

0 0 -1 0

0 0 -1 -4

0 0 -1 -12

0 0 1 -3

0 0 -1 -4

Rimuovendo tutte le disuguaglianze dominate dal sistema precedente, si ottiene una soluzione del sistema

iniziale.

(4)

RICERCA OPERATIVA GRUPPO D

prova scritta del 13 luglio 2004 FOGLIO 2

Cognome: |__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|

Nome: |__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|

Matricola: |__|__|__|__|__|__|

Rispondere alle seguenti domande marcando a penna la lettera corrispondente alla risposta ritenuta corretta (una sola tra quelle riportate).

Ogni risposta esatta vale 2 punti, ogni risposta sbagliata vale –1 punto.

1. Il duale del problema max 2x

1

– 3x

2

– x

3

x

1

– x

2

> 2 x

3

x

2

+ x

3

= 2 x

1

– x

3

< – 1

x

2

, x

3

> 0

è il problema

(A) min 2y

2

– y

3

(B) min 2y

2

– y

3

(C) min 2y

2

– y

3

y

1

– y

3

> – 2 – y

1

+ y

3

= 2 y

1

– y

3

= –2 y

1

+ y

2

> – 3 y

1

+ y

2

> – 3 y

1

+ y

2

> – 3

2y

1

+ y

2

– y

3

> – 1 2y

1

+ y

2

– y

3

> – 1 2y

1

+ y

2

– y

3

> – 1 y

1

,y

3

> 0 y

1

> 0 y

1

,y

3

> 0 2. Sia dato il problema

P : min c

T

x Ax > b

Si supponga che ! y

n

tale che A

T

y = c, con y = (0, …, -1, 0). Allora:

(A) P è illimitato

(B) P ammette un’unica soluzione ottima (C) P non ammette soluzione

La soluzione corretta è (A) oppure (C) pertanto la risposta non è stata considerata nella valutazione del compito.

Riservato al docente Risposte corrette |__|

Risposte inesatte |__|

Risposte mancanti |__|

Valutazione |__|__|

(5)

RICERCA OPERATIVA GRUPPO D

prova scritta del 13 luglio 2004 FOGLIO 3

Cognome: |__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|

Nome: |__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|

Matricola: |__|__|__|__|__|__|

Risolvere il seguente esercizio. La soluzione viene valutata fino a 5 punti.

1. Un enologo che voglia ottenere un buon prodotto deve rispettare precise condizioni. Ad esempio, per produrre la quantità di Dolcione Amaretto corrispondente a 100 kg di uva occorrono almeno 40 kg di uve Benvasia e e Corvot, mentre non bisogna superare le quantità di 20 kg di Sanmartese e di 18 kg di Verde d’Ovola. Se i prezzi al kg dei suddetti vitigni sono quelli riportati in tabella, in che proporzione occorre miscelarli per rispettare le specifiche al costo minimo?

Vitigno 1: Benvasia 2: Sanmartese 3: Corvot 4: Verde d’Ovola

Prezzo (€/kg) 30 20 18 15

Determinare una prima base e una base ottima mediante il metodo del simplesso.

Prima base:

x

1

x

2

x

3

x

4

w

1

w

2

w

3

12 2 0 –3 0 0 0 –1800

1 0 1 1 0 0 60

1 1 1 1 0 0 0 100

1 0 0 1 0 20

0 1 0 0 1 18

Base ottima:

x

1

x

2

x

3

x

4

w

1

w

2

w

3

12 2 0 0 0 0 3 –1746

1 0 0 1 0 0 42

1 1 1 0 0 0 –1 82

1 0 0 0 1 20

0 1 0 0 1 18

Soluzione

Il problema si formula tramite le variabili di decisione x

1

, x

2

, x

3

, x

4

associate ai 4 vitigni nell’ordine, imponendo i vincoli

x

1

+ x

2

+ x

3

+ x

4

= 100

x

1

+ x

3

> 40, 0 < x

2

< 20, 0 < x

4

< 18

L’obiettivo consiste nel minimizzare f(x) = 30x

1

+ 20x

2

+ 18x

3

+ 15x

4

. Per determinare una base iniziale si scriva anzitutto il problema equivalente in forma standard introducendo due variabili di surplus e due di slack

min 20x

1

+ 30x

2

+ 28x

3

+ 12x

4

x

1

+ x

2

+ x

3

+ x

4

= 100 x

1

+ x

3

– w

1

= 40 x

2

+ w

2

= 20 x

4

+w

3

= 18

x

i

, w

i

> 0 per i = 1, …, 4

(6)

Per portare tale problema in forma canonica occorre aggiungere tre variabili ausiliarie z

1

, z

2

, z

3

associate ai primi 3 vincoli:

x

1

x

2

x

3

x

4

w

1

w

2

w

3

z

1

z

2

1 1 0

1 1 1 1 1 100

1 1 –1 1 40

1 1 20

1 1 18

Sottraendo le righe 1e 2 alla riga 0 si ottiene la base iniziale:

x

1

x

2

x

3

x

4

w

1

w

2

w

3

z

1

z

2

–2 –1 –2 –1 1 0 0 0 0 –140

1 1 1 1 1 100

1 1 –1 1 40

1 1 20

1 1 18

Operando un pivot in posizione (2, 3) si ha quindi

x

1

x

2

x

3

x

4

w

1

w

2

w

3

z

1

z

2

0 –1 0 –1 –1 0 0 0 +2 –60

0 1 0 1 1 0 0 1 –1 60

1 1 –1 0 0 0 1 40

0 1 0 1 0 0 20

0 0 1 0 1 0 18

Passando infine a un pivot in posizione (1, 5) si ricava una prima base del problema iniziale

x

1

x

2

x

3

x

4

w

1

w

2

w

3

z

1

z

2

0 0 0 0 0 0 0 1 1 0

0 1 0 1 1 0 0 1 –1 60

1 1 1 1 0 0 0 1 100

0 1 0 0 1 0 0 20

0 0 1 0 0 1 0 18

Eliminando le variabili ausiliarie e ripristinando la funzione obiettivo del problema iniziale si ha

x

1

x

2

x

3

x

4

w

1

w

2

w

3

30 20 18 15 0 0 0 0

0 1 0 1 1 0 0 60

1 1 1 1 0 0 0 100

0 1 0 0 1 0 20

0 0 1 0 0 1 18

Sottraendo poi alla riga 0 la riga 2 moltiplicata per 18 si ottiene

(7)

x

1

x

2

x

3

x

4

w

1

w

2

w

3

12 2 0 –3 0 0 0 –1800

0 1 0 1 1 0 0 60

1 1 1 1 0 0 0 100

0 1 0 0 1 0 20

0 0 1 0 0 1 18

che corrisponde alla soluzione ammissibile x

1

=x

2

= 0, x

3

= 100, x

4

= 0 il cui costo è 20100 = 2000€. Si può ora operare un pivot in posizione (4, 4):

x

1

x

2

x

3

x

4

w

1

w

2

w

3

12 2 0 0 0 0 3 –1746

0 1 0 0 1 0 0 42

1 1 1 0 0 0 –1 82

0 1 0 0 0 1 0 20

0 0 0 1 0 0 1 18

Riservato al docente Valutazione |__|__|

Riferimenti

Scarica adesso ( DOC - 1 pagine - 242.50 KB )

Documenti correlati

1 Grafo non orientato

liste di adiacenza: una lista di tutti i nodi e, per ciascuno di essi, una lista dei nodi

4) Scrivere un algoritmo per trovare una clique di k vertici in un grafo di n vertici

3) Scrivere un algoritmo di verifica per il problema di decidere se un grafo di n vertici, rappresentato con una matrice binaria M, contiene una clique di k

In un grafo non orientato due nodi sono adiacenti se esiste un arco che li unisce

Grafo particolare è quello &#34;euleriano&#34;, dal matematico Eulero, che nel 1736 lo utilizzò per risolvere il problema dei ponti di Königsberg: un cammino o percorso è detto di

Si assegnino costi positivi agli archi del grafo di figura 1.22 in modo che l’accoppiamento indicato non sia massimo rispetto ai costi

Assegnando costo 2 agli archi tratteggiati in figura 1.22, e costo 1 agli archi accoppiati, si ottiene, ad esempio, il seguente accoppiamento massimo di costo 6 (contro il costo

2.10 Esercizio. Si dimostri che contraendo un grafo partizionato secondo una coloratura minima (numero cromatico) si ottiene un grafo completo.

Se valesse anche nel senso opposto esisterebbe un algoritmo estremamente semplice (e polinomiale) per colorare in modo minimo un grafo (si colora arbitrariamente e si vede se il

1 Numero di cammini in un grafo

Come applicazione della matrice d’adiacenza, ricaviamo alcune formule per il calcolo del numero di cammini e cicli di lunghezza fissata. 1 Numero di cammini in

  ,       Matricola: |__|__|__|__|__|__| Nome: |__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__| |__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__| 1Cognome: RICERCA OPERATIVAG

Dato un grafo simmetrico costituito da un numero pari k di cicli dispari è sempre possibile aggiungere a esso k archi in modo che il grafo risultante1. [A] ammetta sempre un

0011001011011010Notiamo che la diagonale è tutta formata da valori 0 (perché in un grafo non orientato non sonopermessi cappi).Dato il grafo orientato con 4 vertici x

Date 2 matrici booleane M,N tali che M sia una matrice nxm ed N sia una matrice mxt, definiamo prodotto booleano MxN la matrice booleana ottenuta calcolando il prodotto righe