Compito di Ricerca Operativa del 27/03/2002: Soluzioni

(1)

Tabella 1:

x1 x2

u₁ -2 0 5

u2 -4 -2 13

z 3 1 0

Tabella 2:

u1 x2

x₁ -1/2 0 5/2

u2 2 -2 3

z -3/2 1 15/2

Compito di Ricerca Operativa del 27/03/2002:

Soluzioni

Esercizio 1 (12 punti)

1) In Figura 1 la regione ammissibile Sa del rilassamento lineare ´e il poliedro convesso OABC, mentre Za ´e costituito dai punti a coordinate intere in tale poliedro (i quadratini nella figura). Una volta individuato il verso di crescita della funzione obiettivo si vede che Sott = {B} con valore ottimo pari a 9, mentre Zott={D}, D = (2, 2), con valore ottimo pari a 8.

2) Prima di iniziare a risolvere il problema con l’algoritmo di Gomory dobbiamo rendere interi i coefficienti e i termini noti dei vincoli ed introdurre le variabili associate ai vincoli e all’obiettivo:

max z = 3x1+ x2

u1= 5− 2x1

u₂= 13− 4x1− 2x2

x1, x2, u1, u2≥ 0, x1, x2, u1, u2∈ I

A questo punto possiamo risolvere il rilassamento lineare di tale problema partendo dalla base{x1, x2} cui é associata la Tabella 1. Tale base ha come soluzione di base (ammissibile e quindi un vertice) corrispondente l’origine O. La base é ammissibile ma non ottima (vi sono coefficienti di costo ridotto positivi nell’ultima riga). Applicando le regole viste a lezione il cardine si trova nella posizione individuata dalla riga u1 e dalla colonna x1. Eseguendo l’operazione di cardine si ottiene la Tabella 2 relativa alla base {u1, x2}. Tale base ha come soluzione di base corrispondente il vertice A. La base é ammissibile ma non ottima (vi sono coefficienti di costo ridotto positivi nell’ultima riga). Applicando le regole viste a lezione il cardine si trova nella posizione individuta dalla riga u₂e dalla colonna x₂. Eseguendo l’operazione di cardine si ottiene la Tabella 3

(2)

Tabella 3:

u1 u2

x₁ -1/2 0 5/2 x2 1 -1/2 3/2 z -1/2 -1/2 9

Tabella 4:

u₁ u₂ x1 -1/2 0 5/2 x2 1 -1/2 3/2

u3 1/2 0 -1/2

z -1/2 -1/2 9

relativa alla base {u1, u₂}. Tale base ha come soluzione di base corrispondente il vertice B. Essa ´e ottima per il rilassamento lineare ma non ha coordinate tutte intere. Genero quindi un taglio di Gomory utilizzando la prima riga con un β frazionario:

1/2u₁− 1/2 ≥ 0,

che nelle variabili originarie equivale a x1≤ 2 (si veda la rappresentazione grafica del taglio in Figura 2. Aggiungendo una variabile u3 relativa al taglio:

u3= 1/2u1− 1/2 ≥ 0,

e ripartendo con la base ottima{u1, u2} del problema precedente avremo come tabella relativa a tale base la Tabella 4 che é non ammissibile per il primale ma lo é per il duale. Posso quindi applicare il simplesso duale. Il cardine é nella posizione riga u3 e colonna u1. L’operazione di cardine porta alla base {u2, u₃} con la relativa Tabella 5 che é ottima ma non ha coordinate intere.

Genero quindi un taglio di Gomory utilizzando la prima (e unica) riga con un β frazionario:

1/2u₂− 1/2 ≥ 0,

che nelle variabili originarie equivale a 2x₁+ x₂≤ 6 (si veda la rappresentazione grafica del taglio in Figura 3). Aggiungendo una variabile u4 relativa al taglio:

Tabella 5:

u3 u2

x1 -1 0 2

x2 2 -1/2 5/2

u1 2 0 1

z -1 -1/2 17/2

(3)

Tabella 6:

u3 u2

x₁ -1 0 2

x2 2 -1/2 5/2

u1 2 0 1

u4 0 1/2 -1/2 z -1 -1/2 17/2

Tabella 7:

u3 u4

x₁ -1 0 2 x2 2 -1 2

u1 2 0 1

u2 0 2 1

z -1 -1 8

u4= 1/2u2− 1/2 ≥ 0,

e ripartendo con la base ottima{u3, u2} del problema precedente avremo come tabella relativa a tale base la Tabella 6 che é non ammissibile per il primale ma lo é per il duale. Posso quindi applicare il simplesso duale. Il cardine é nella posizione riga u4e colonna u2. L’operazione di cardine porta alla base{u3, u4} con la relativa Tabella 7 che é ottima. La soluzione ottima

x₁= 2 x₂= 2

ha coordinate tutte intere e quindi ´e soluzione ottima anche del problema di PLI con valore ottimo pari a 8.

3) La soluzione ottima del problema di PLI ´e unica in quanto nella Tabella 7 i coefficienti di costo ridotto sono tutti strettamente negativi.

4) Il primo taglio di Dantzig si ottiene dalla Tabella 3 che ´e ottima per il rilassamento lineare del problema. Il taglio ´e il seguente:

u1+ u2− 1 ≥ 0 che nelle variabili originarie diventa

6x1+ 2x2≤ 17.

Dal momento che la soluzione ottima del problema di PLI, il punto D, non appartiene alla retta 6x1+ 2x2= 17 e non appartiene a nessuno degli iperpiani generatori dei vincoli originari, allora si dovranno aggiungere, oltre a questo, almeno altri due tagli di Dantzig, mentre l’algoritmo di Gomory ha introdotto due soli tagli.

(4)

5) Non ´e possibile modificare la funzione obiettivo in modo che Z_ott=∅. Infatti Za, indipendentemente dalla funzione obiettivo, contiene un numero finito di punti ed il massimo su un insieme finito di punti esiste sempre. Si pu´o invece modificare il termine noto di un vincolo in modo da rendere Zott = ∅. Ad esempio, cambiando il primo vincolo in x1 ≤ −1/2 si ha che Za =∅ e quindi anche Zott=∅.

1)La formulazione del problema come problema di PLI `e la seguente:

min 2x12+ 10x13+ x14+ 3x23+ 4x42

x₁₂+ x₁₃+ x₁₄= 6 x23− x12− x42=−2

−x13− x23=−8

x₁₂, x₁₃, x₁₄, x₂₃, x₄₂≥ 0 interi

La matrice dei vincoli (a meno di permutazioni delle colonne) `e la seguente:





1 1 1 0 0

−1 0 0 1 −1

0 −1 0 −1 0



 (1)

2) Gli archi (1, 2), (1, 3), (1, 4) formano un albero di supporto ma ponendo a 0 le variabili relative agli altri archi si ottiene dai vincoli

x13= 8 x12= 2 x14=−4

e quindi la base non `e ammissibile. Gli archi (1, 2), (1, 3), (2, 3) non formano un albero di supporto e quindi non possono rappresentare una base. Infine, gli archi (1, 3), (2, 3), (4, 2) formano un albero di supporto e ponendo a 0 le variabili relative agli altri archi si ottiene

x₁₃= 6 x₂₃= 2 x₄₂= 4.

Quindi tale base `e ammissibile.

3) La base formata dagli archi (1, 3), (2, 3) e (4, 2) corrisponde all’albero di supporto in Figura 4. Partendo da tale base calcolo i coefficienti di costo ridotto delle variabili fuori base:

c₁₂= c₁₂+ c₂₃− c13= 2 + 3− 10 = −5 c₁₄= c₁₄+ c₄₂+ c₂₃− c13= 1 + 4 + 3− 10 = −2

La base non `e ottima (ci sono coefficienti di costo ridotto negativi). Prendo la variabile fuori base con coefficiente di costo ridotto pi`u piccolo (quindi la x₁₂)

(5)

e aggiungo il relativo arco all’albero di supporto (vedi Figura 5). Si forma un ciclo ma non è orientato e quindi non possiamo concludere che il problema è illimitato. Faccio crescere a ∆ il valore di x12. Per continuare a rispettare i vincoli dovrò avere

x12= ∆ x23= 2 + ∆ x13= 6− ∆ x42= 4

e, per mantenere le variabili non negative, posso far crescere ∆ fino a 6. A questo punto si annulla x13 e tolgo l’arco relativo. L’albero di supporto che mi rimane `e la nuova base (vedi Figura 6) con soluzione di base corrispondente

x₁₂= 6 x₂₃= 8 x₄₂= 4 x₁₃= x₁₄= 0.

Rifaccio la verifica di ottimalit`a calcolando i coefficienti di costo ridotto.

c13= c13− c23− c12= 10− 3 − 2 = 5 c14= c14+ c42− c12= 1 + 4− 2 = 3

Tutti i coefficienti di costo ridotto sono non negativi (in particolare sono positivi) e quindi la soluzione `e ottima, con valore ottimo pari a 52.

4) Ricordando le regole viste per generare il duale di un generico problema di PL, avremo che il duale del nostro problema `e il seguente:

max 6w1− 2w2− 8w3

w1− w2≤ 2 w₁− w3≤ 10

w1≤ 1 w₂− w3≤ 3

−w2≤ 4

w1, w2, w3 libere in segno

Per determinare la soluzione ottima del duale prendiamo come uguaglianza i vincoli del duale relativi agli archi dell’albero di supporto ottimo:

w1− w2= 2 w2− w3= 3

−w2= 4

da cui la soluzione ottima del duale

w1=−2 w2=−4 w3=−7

con valore ottimo pari a 52 (pari a quello del primale, come deve essere).

(6)

1) Poniamo inizialmente il nodo a in C e T1=∅. Alla prima iterazione spostiamo a in T1 e mettiamo in C tutti i nodi legati ad a con un arco che non siano gi´a in T1:

C ={b, c, d} T1={a}.

Alla seconda iterazione spostiamo un nodo, ad esempio b, da C in T₁e mettiamo in C tutti i nodi legati a b con un arco che non siano gi´a in T₁:

C ={c, d} T1={a, b}.

Alla terza iterazione spostiamo un nodo, ad esempio c, da C in T₁ e mettiamo in C tutti i nodi legati a c con un arco che non siano gi´a in T₁:

C ={d, e, f} T1={a, b, c}.

A questo punto notiamo che C∪ T1= V e quindi il grafo ´e connesso.

2) Il numero ciclomatico ´e dato dalla formula

ν(G) = card(A)− card(V ) + p = 11 − 6 + 1 = 6,

dove p `e il numero di componenti connesse (in tal caso pari a 1 in quanto il grafo

`

e connesso). 3) Possiamo ottenere una base di cicli o individuando un albero di supporto del grafo ed aggiungendo uno alla volta gli archi che non fanno parte dell’albero, oppure, essendo il grafo planare, attraverso le facce finit di una sua rappresentazione topologicamente planare. In Figura 7 abbiamo una rapprsen- tazione topologicamente planare del grafo, da cui si ricava immediatamente una base di cicli:

a→ b → c → a b→ d → c → b a→ b → d → a c→ e → f → c c→ d → e → c d→ e → f → d.

1) Il vincolo dice che x2 = 1 ´e possibile solo se x1 = 0. Quindi x1 e x2 non possono essere contemporaneamente uguali a 1. Il vincolo che esprime questo ´e:

x1+ x2≤ 1.

2) Un esempio ´e il seguente:

max x1

2x₁+ x₂≤ 3 x2≤ 1 x₁, x₂≥ 0, x1, x₂∈ I

(7)

dove Z_ott={(1, 0); (1, 1)} e Sott={(3/2, 0)}.

3) Il duale del problema ´e il seguente

max 4y1+ 3y2+ 3y3

5y₁+ 6y₂≤ 2 7y1+ 9y2+ y3≥ 3 y₂≥ 0, y1, y₃≤ 0

Per verificare che il punto (1/2, 0) é soluzione ottima del primale mentre il punto (0, 1/3, 0) é soluzione ottima del duale, si ricordi che se essi sono punti ammissibili rispettivamente del primale e del duale e i loro valori dell’obiettivo rispettivamente primale e duale coincidono, per un risultato visto a lezione essi sono soluzioni ottime dei rispettivi problemi. Si puó verificare che i punti sono ammissibili rispettivamente per il primale e per il duale e i loro valori dell’o- biettivo rispettivamente primale e duale sono entrambi pari a 1, quindi sono soluzioni ottime dei rispettivi problemi.

(8)

!!!!

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

x1 x2

13/2

O A 5/2

C

D

13/4 B

Figura 1:

(9)

!!!!

x1 x2

13/2

O A 5/2

C

E D

B

13/4

Figura 2:

(10)

!!!!

A A

A

x1 x2

13/2

O A 5/2

C

E D

B

13/4

Figura 3:

(11)

Z Z

Z

1 2

3 4

Figura 4:

Z Z

Z

1 2

3 4

Figura 5:

1 2

3 4

Figura 6:

(12)

!!

!

a b

c d

f e

Figura 7: