Quindi il punto ´e un vertice

(1)

Compito di Ricerca Operativa del 11/04/2002:

Soluzioni

Esercizio 1 (12 punti)

1) Il punto (1, 1, 2) appartiene a Sa e si trova sugli iperpiani generatori relativi ai primi tre vincoli, i quali per´o non sono tra loro linearmente indipendenti.

Infatti, la matrice dei coefficienti di questi tre vincoli:





1 1 1

1 −1 1

1 0 1





ha rango pari a 2. Quindi il punto non ´e un vertice. Il punto (0, 1, 3) appartiene a Sa e si trova sugli iperpiani generatori relativi ai primi tre vincoli e al vincolo x1≥ 0, tre dei quali sono tra loro linearmente indipendenti. Infatti, la matrice dei coefficienti di questi quattro vincoli:







1 1 1

1 −1 1

1 0 1

1 0 0







ha rango pari a 3. Quindi il punto é un vertice. Infine, il punto (0, 0, 3) non puó essere un vertice perché non appartiene a S_a (per esempio non soddisfa il primo vincolo).

2) La risposta al primo quesito ci dice che S_a 6= ∅ e contiene pi´u di un punto.

Inoltre, il primo vincolo, in cui tutti i coefficienti delle variabili e il termine noto sono strettamente positivi, ci mostra che Sa´e un insieme limitato. Quindi Sa ´e un poliedro convesso. Per il teorema di Weierstrass si deve avere che Sott 6= ∅.

Infine, ´e ovviamente falso che Sanon ha alcun vertice (abbiamo visto che (0, 1, 3)

´

e un vertice). É falso anche che ne abbia solo uno. Infatti, se ne avesse solo uno dovrebbe ridursi ad un singolo punto (ma abbiamo visto che contiene anche il punto (1, 1, 2)) oppure essere un troncone con un solo vertice (ma abbiamo visto che é un poliedro convesso). Quindi il vertice (0, 1, 3) deve avere almeno un vertice adiacente e l’affermazione vera é che Sa contiene almeno due vertici.

3) Per risolvere il problema utilizzeremo il metodo due fasi. Il problema di I fase si presenter´a nella seguente forma:

max t =−v1− v2= 2x₁+ 2x₃− 6 v1= 4− x1− x2− x3

v2= 2− x1+ x2− x3

u₃= 3− x1− x3

u4= 2− x2

x₁, x₂, v₁, v₂, u₃, u₄≥ 0

(2)

Tabella 1:

x1 x2 x3

v₁ -1 -1 -1 4

v2 -1 1 -1 2

u3 -1 0 -1 3

u4 0 -1 0 2

t 2 0 2 -6

z 1 5 3 0

Tabella 2:

v2 x2 x3

v₁ 1 -2 0 2

x₁ -1 1 -1 2

u3 1 -1 0 1

u4 0 -1 0 2

t -2 2 0 -2

z -1 6 2 2

A questo punto possiamo risolvere il problema di I fase partendo dalla base {x1, x₂, x₃} cui é associata la Tabella 1. La base é ammissibile ma non ottima per il problema di I fase (vi sono coefficienti di costo ridotto positivi nella riga t). Applicando le regole viste a lezione il cardine si trova nella posizione individuata dalla riga v2 e dalla colonna x1. Eseguendo l’operazione di cardine si ottiene la Tabella 2 relativa alla base{v2, x2, x3}. La base é ammissibile ma non ottima per il problema di I fase (vi sono coefficienti di costo ridotto positivi nella riga t). Applicando le regole viste a lezione il cardine si trova nella posizione individuata dalla riga v1 e dalla colonna x2. Eseguendo l’operazione di cardine si ottiene la Tabella 3 relativa alla base {v2, v1, x3}. Tale tabella é ottima per il problema di I fase, il cui valore ottimo é 0. Quindi il problema di II fase (il nostro problema originario) ha soluzioni ammissibili. Essendo tutte le variabili associate a vincoli di uguaglianza (v1 e v2) in base, possiamo ora partire con la

Tabella 3:

v₂ v₁ x₃ x2 1/2 -1/2 0 1 x1 -1/2 -1/2 -1 3

u3 1/2 1/2 0 0

u4 -1/2 1/2 0 1

t -1 -1 0 0

z 2 -3 2 8

(3)

Tabella 4:

v2 v1 x1

x₂ 1/2 -1/2 0 1

x3 -1/2 -1/2 -1 3

u3 1/2 1/2 0 0

u4 -1/2 1/2 0 1

z 1 -4 -2 14

soluzione del problema di II fase tralasciando la riga t dell’obiettivo di I fase.

Notiamo che il coefficiente di costo ridotto della variabile x3é positivo (pari a 2). Quindi non é soddisfatta la condizione di ottimalitá. Eseguo un’operazione di cardine con cardine nella posizione individuata dalla riga x1 e dalla colonna x3 (si ricordi che nella scelta della colonna del cardine non si prendono in considerazione le variabili v1 e v2). Si ottiene la Tabella 4 relativa alla base {v2, v1, x1}. Tale tabella é ottima (si ricordi che i coefficienti di costo ridotto delle variabili v1 e v2 non devono essere≤ 0). Quindi la soluzione ottima é il punto (0, 1, 3) con valore ottimo pari a 14.

4) Il duale del problema ´e il seguente

min 4v₁+ 2v₂+ 3u₃+ 2u₄ v1+ v2+ u3≥ 1 v₁− v2+ u₄≥ 5 v1+ v2+ u3≥ 3

u3, u4≥ 0, v1, v2 libere in segno

Una soluzione ottima del duale si pu´o leggere direttamente dalla Tabella 4 ottima per il primale. Nel duale le variabili u3e u4sono in base e quindi con valore 0, mentre il valore di v1 e v2 si legge nella riga z cambiando il segno. Quindi una soluzione ottima del duale ´e

u3= u4= 0 v1= 4 v2=−1,

con valore ottimo pari a 14 pari al valore ottimo del primale (come deve essere).

5) `E possibile. Se osservo il vincolo del duale relativo a x3, ovvero v1+ v2+ u3≥ 3

si vede che ogni soluzione ammissibile del duale deve avere

v₁+ v₂+ u₃> 1 (1)

cioè il vincolo relativo a x₁ non è mai soddisfatto come uguaglianza. Dalle condizioni di complementarità si deve avere

x₁∗ (v1+ v₂+ u₃− 1) = 0 il che in base a (1) `e possibile soltanto se x₁= 0.

(4)

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

min 2x14+ x21+ 8x31+ x32+ 2x43+ 6x45+ 4x51

x₁₄− x21− x31− x51=−8 x21− x32= 3 x31+ x32− x43= 4 x₄₃+ x₄₅− x14= 3

x14, x21, x31, x32, x43, x45, x51≥ 0 interi La matrice dei vincoli (a meno di permutazioni delle colonne) `e la seguente:







1 −1 −1 0 0 0 −1

0 1 0 −1 0 0 0

0 0 1 1 −1 0 0

−1 0 0 0 1 1 0







(2)

2) Il nodo 2 é un nodo sorgente in cui il prodotto viene realizzato (3 unitá di prodotto). L’unico arco in uscita da tale nodo e lungo il quale si puó quindi inviare il prodotto realizzato é l’arco (2, 1) e quindi questo arco deve far parte della base ottima e di ogni base ammissibile. Il nodo 5 é un nodo destinazione che deve ricevere 2 unitá di prodotto. L’unico arco entrante nel nodo 5 é l’arco (4, 5) e quindi le 2 unitá possono giungere al nodo 5 solo lungo questo arco che dovrá quindi far parte della base ottima e di ogni base ammissibile.

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

x14=−5 x21= 3 x43=−4 x45= 2

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

x₂₁= 3 x₃₁= 5 x₄₃= 1 x₄₅= 2 Quindi tale base `e ammissibile.

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

c14= c14+ c43+ c31= 2 + 2 + 8 = 12 c32= c32+ c21− c31= 1 + 1− 8 = −6 c₅₁= c₅₁− c31− c43+ c₄₅= 4− 8 − 2 + 6 = 0

(5)

Q Q

Q

T T

A A

1

2

3 4

5

Figura 1:

La base non è ottima (ci sono coefficienti di costo ridotto negativi). Prendo la variabile fuori base con coefficiente di costo ridotto più piccolo (quindi la x₃₂) e aggiungo il relativo arco all’albero di supporto (vedi Figura 2). Si forma un ciclo ma non è orientato e quindi non possiamo concludere che il problema è illimitato. Faccio crescere a ∆ il valore di x32. Per continuare a rispettare i vincoli dovrò avere

x32= ∆ x21= 3 + ∆ x31= 5− ∆ x43= 1 x45= 2

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

x₃₂= 5 x₂₁= 8 x₄₃= 1 x₄₅= 2 x₃₁= x₅₁= x₁₄= 0 Rifaccio la verifica di ottimalit`a calcolando i coefficienti di costo ridotto.

c₁₄= c₁₄+ c₄₃+ c₃₂+ c₂₁= 2 + 2 + 1 + 1 = 6 c31= c31− c21− c32= 8− 1 − 1 = 6

c51= c51− c21− c32− c43+ c45= 4− 1 − 1 − 2 + 6 = 6

Tutti i coefficienti di costo ridotto sono non negativi (in particolare sono positivi) e quindi la soluzione `e ottima, con valore ottimo pari a 27. Non esistono altre soluzioni ottime in quanto tutti i coefficienti di costo ridotto sono strettamente positivi.

5) Ricordando le regole viste per generare il duale di un generico problema di

(6)

Q Q

Q

T T

A A

1

2

3 4

5

Figura 2:

PL, avremo che il duale del nostro problema `e il seguente:

max −8w1+ 3w2+ 4w3+ 3w4

w₁− w4≤ 2 w2− w1≤ 1 w3− w1≤ 8 w₃− w2≤ 1 w4− w3≤ 2

w₄≤ 6

−w1≤ 4

w₁, w₂, w₃, w₄ 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:

w2− w1= 1 w₃− w2= 1 w4− w3= 2

w₄= 6

da cui la soluzione ottima del duale

w₁= 2 w₂= 3 w₃= 4 w₄= 6

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

(7)

Q Q

Q

T T

1

2

3 4

5

Figura 3:

1) Poniamo inizialmente il nodo a in C e T₁=∅. 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, e} T1={a}.

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

C ={c, e, d} T₁={a, b}.

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

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

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

C ={d, h, f} T₁={a, b, c, e}.

Alla quinta iterazione spostiamo un nodo, ad esempio d, da C in T1e mettiamo in C tutti i nodi legati a d con un arco che non siano gi´a in T1:

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

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

2) Si inizializzino C1 e T1 con un singolo nodo, ad esempio a, cio`e si ponga C1= T1={a}. Si ponga C2= T2=∅. Alla prima iterazione avremo

T₂={b, c, e} C2={b, c, e}

(8)

T₁={d, h, f} C1={a, d, h, f}

Non si ha C1∪ C2 = V e neppure C1∩ C2 6= ∅. Quindi si passa alla seconda iterazione dove avremo

T2={g} C2={b, c, e, g}

T1=∅ C1={a, d, h, f}

Si ha C1∪ C2 = V e C1∩ C2=∅ ma non ancora T2 =∅. Quindi si passa alla terza iterazione dove avremo

T2=∅ C2={b, c, e, g}

T₁=∅ C1={a, d, h, f}

Si ha C₁∪ C2= V , C₁∩ C2=∅ e T1= T₂=∅. Quindi il grafo ´e bipartito con le due classi di bipartizione

V1= C1={a, d, h, f} V2= C2={b, c, e, g}

3) Il grafo non ´e topologicamente planare (vedi, ad esempio, l’intersezione tra l’arco (a, c) e l’arco (h, g)) ma ´e planare in quanto ammette una rappresentazione topologicamente planare (si veda, ad esempio, la Figura 4).

1) Il problema ´e simile a quello dello zaino intero. Qui si richiede di trasportare un certo valore minimo minimizzando il peso trasportato. Abbiamo un insieme (OGGETTI), due vettore di parametri (peso e valore) con insieme indice OG- GETTI, un parametro singolo (valore minimo). Abbiamo un vettore di variabili x, con insieme indice OGGETTI, che possono assumere solo valori interi e non negativi. Il modello AMPL ´e il seguente:

set OGGETTI;

param peso{OGGETTI}>0;

param valore{OGGETTI}>0;

param valore minimo>0;

var x{OGGETTI}>=0, INTEGER;

subject to min val : sum{i in OGGETTI } valore[i]*x[i]>= valore minimo;

minimize peso totale : sum{i in OGGETTI } peso[i]*x[i];

(9)

Z Z

Z

"

a b

c d g

f e

h

Figura 4:

2) Per avere un duale privo di soluzioni ammissibili basta avere un primale con obiettivo illimitato. Un esempio molto semplice ´e il seguente:

max x1

−x1+ x2≤ 1 x₁, x₂≥ 0

Per avere soluzioni ammissibili nel duale basta cambiare l’obiettivo del primale in modo tale che esso abbia soluzioni ottime (in tal caso sappiamo che anche il duale ha soluzioni ottime). Nell’esempio basta cambiare segno all’obiettivo:

max −x1

−x1+ x₂≤ 1 x1, x2≥ 0