Compito di Ricerca Operativa del 27/03/2002 Esercizio 1 (12 punti)

Compito di Ricerca Operativa del 27/03/2002

Esercizio 1 (12 punti)

Sia dato il seguente problema di PLI

max 3x

+ x

x

≤ 5/2 x

+ 1/2x

≤ 13/4 x

, x

≥ 0, x

, x

∈ I

1) Si risolva graficamente il rilassamento lineare di tale problema ed il problema stesso.

2) Si determini una soluzione ottima del problema di PLI tramite l’algoritmo di Gomory rappresentando graficamente i vincoli via via ottenuti.

3) Oltre a quella trovata esistono altre soluzioni ottime?

4) Si scriva il primo taglio generato dall’algoritmo di Dantzig. Sulla base del risultato ottenuto e aiutandosi con la risoluzione grafica, ´ e possibile affermare che l’algoritmo di Dantzig introdurr´ a per questo esempio un numero di tagli superiore rispetto all’algoritmo di Gomory?

5) ´ E possibile modificare la funzione obiettivo in modo tale da rendere l’insieme delle soluzioni ottime del problema di PLI Z

= ∅? ´ E possibile modificare il termine noto di uno dei vincoli in modo da rendere Z

= ∅? In caso di risposta affermativa mostrare come.

Esercizio 2 (10 punti)

Sia data la rete in Figura 1 con

b

= 6 b

= −2 b

= −8 b

= 4 e

c

= 2 c

= 10 c

= 1 c

= 3 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

Z Z

Z Z

Z Z

Z Z

Z Z

Z Z

Z

























1 2

3 4

Figure 1:

si scriva la matrice dei vincoli.

2) Siano dati i seguenti insiemi di 3 archi

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

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

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

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

1

a a a a

a a a a

a a a a

a

 

 

 

 

 

 

a a a a

a a a a

a a a a

 

 

 

 

 

 



a b

c d

f e

Figure 2:

Esercizio 3 (5 punti)

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

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

2) Trovare il numero ciclomatico del grafo. 3) Trovare, con uno dei metodi visti a lezione, una base di cicli del grafo.

Esercizio 4 (6 punti)

Si risponda alle seguenti domande.

1) Siano x

(i = 1, 2) variabili binarie con valore 0 se si decide di non svolgere l’attivit´ a i e con valore 1 altrimenti. Si esprima con un singolo vincolo il fatto che ´ e possibile (ma non necessario) svolgere l’attivit´ a 2 solo se non si svolge l’attivit´ a 1.

2) Scrivere un esempio di problema di PLI con pi´ u di una soluzione ottima il cui rilassamento lineare abbia soluzione ottima unica.

3) Scrivere il duale del seguente problema di PL

min 2x

+ 3x

5x

+ 7x

≤ 4 6x

+ 9x

≥ 3

x

≤ 3 x

≥ 0, x

≤ 0

e verificare che il punto (1/2, 0) ´ e soluzione ottima del primale mentre il punto (0, 1/3, 0) ´ e soluzione ottima del duale (senza applicare l’algoritmo del simplesso o risoluzioni grafiche).

2