Compito di Ricerca Operativa del 11/04/2002 Esercizio 1 (11 punti)

Compito di Ricerca Operativa del 11/04/2002

Esercizio 1 (11 punti)

Sia dato il seguente problema di PL

max x

+ 5x

+ 3x

x

+ x

+ x

= 4 x

− x

+ x

= 2

x

+ x

≤ 3 x

≤ 2 x

, x

, x

≥ 0

1) Per ciascuno dei seguenti tre punti (1, 1, 2), (0, 1, 3) e (0, 0, 3) si stabilisca se

´

e un vertice della regione ammissibile S

oppure no.

2) Sulla base della risposta al primo quesito e sulla base dei vincoli del problema, si dica qual ´ e la forma di S

. Pu´ o succedere che S

= ∅? Quale delle seguenti affermazioni ´ e vera:

a) S

non contiene vertici.

b) S

contiene un solo vertice.

c) S

contiene almeno due vertici.

3) Si risolva il problema di PL.

4) Si scriva il duale del problema di PL e se ne fornisca una soluzione ottima. ´ e possibile modificare l’obiettivo del primale in modo tale che il duale non abbia soluzioni?

Esercizio 2 (11 punti)

Sia data la rete in Figura 1 con

b

= −8 b

= 3 b

= 4 b

= 3 b

= −2 e

c

= 2 c

= 1 c

= 8 c

= 1 c

= 2 c

= 6 c

= 4

1) Si formuli il problema di flusso a costo minimo su tale rete come problema di PLI con un numero minimo di vincoli e si scriva la matrice dei vincoli.

2) Gli archi (2, 1) e (4, 5) fanno certamente parte della base ottima e di ogni base ammissibile. Perch´ e?

3) Siano dati i seguenti insiemi di 4 archi

(2, 1) (3, 1) (3, 2) (4, 5) (2, 1) (1, 4) (4, 3) (4, 5) (2, 1) (3, 1) (4, 3) (4, 5)

1

Q Q

Q Q

Q











 T

T T

T T

T





































A A

A A

A A

A A

A A

1

2

3 4

5

Figura 1:

Per ciascuno dei tre insiemi stabilire se rappresenta o meno una base e, in caso di risposta affermativa, se sia ammissibile.

4) Usando la risposta del punto precedente si risolva il problema tramite il simplesso su rete.

5) Si scriva il duale del rilassamento lineare del problema e se ne determini una soluzione.

Esercizio 3 (6 punti)

Sia dato il grafo G = (V, A) rappresentato in Figura 2.

1) Verificare, applicando la procedura vista a lezione, che ´ e connesso.

2) Verificare, applicando la procedura vista a lezione, che ´ e bipartito ed indicare le due classi di bipartizione.

3) Usando la sola rappresentazione grafica mostrare che il grafo non ´ e topolo- gicamente planare ma ´ e planare. 3) Trovare una base di cicli del grafo.

Esercizio 4 (5 punti)

Si risponda alle seguenti domande.

1) Sia dato un insieme OGGET T I di tipi di oggetti. Ad ogni tipo di oggetto ´ e associato un peso ed un valore. Si deve decidere quanti oggetti di ciascun tipo portare tenuto conto che si vuole portare un valore complessivo non inferiore a valore minimo e che si vuole minimizzare il peso trasportato. Scrivere un modello AMPL per questo problema.

2) Scrivere un problema di PL in forma canonica con regione ammissibile non vuota il cui duale non abbia soluzioni ammissibili e poi modificare la funzione obiettivo del problema in modo che il duale ammetta soluzioni ammissibili.

2

A A

A A

A A

A A

A A

A A

A A

A Q

Q Q

Q Q

hhh hhh hhh

hhh hhh hhh hhh

hhh hhh h

a b

c d

h

g f e

Figura 2:

3