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

(1)

Tabella 1:

x1 x2

u₁ 2 2 -3

u2 -2 -2 7

u3 -2 0 5

z 3 1 0

Compito di Ricerca Operativa del 27/03/2002:

Soluzioni

Esercizio 1 (12 punti)

1) In Figura 1 la regione ammissibile S_a del rilassamento lineare ´e il poliedro convesso ABCDE, mentre la regione ammissibile Za del problema di PLI ´e co- stituito 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 = {C}, C = (5/2, 1) con valore ottimo pari a 17/2, mentre Zott = {F }, F = (2, 1), con valore ottimo pari a 7.

2) Prima di iniziare a risolvere il problema con l’algoritmo di Gomory dobbia- mo scrivere il problema in forma canonica e quindi rendere interi i coefficienti e i termini noti dei vincoli ed introdurre le variabili associate ai vincoli e all’obiettivo:

max z = 3x₁+ x₂

u1=−3 + 2x1+ 2x2

u₂= 7− 2x1− 2x2

u3= 5− 2x1

x1, x2, u1, u2, u3≥ 0, x1, x2, u1, u2, u3∈ 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 (non ammissibile) corrispondente l’origine O. La base é non ammissibile. Applicando le regole viste a lezione per la fase di avvicinamento a Sa, il cardine si trova nella posizione individuata dalla riga u3 e dalla colonna x1. Eseguendo l’operazione di cardine si ottiene la Tabella 2 relativa alla base ammissibile{u3, x2}. Tale base ha come soluzione di base corrispondente il vertice B. 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 relativa alla base {u3, u₂}. Tale base ha come soluzione di base corrispondente il vertice C. Essa é ottima per il rilassamento lineare ma non ha coordinate tutte intere. Genero quindi un taglio

(2)

Tabella 2:

u3 x2

u₁ -1 2 2

u2 1 -2 2

x1 -1/2 0 5/2 z -3/2 1 15/2

Tabella 3:

u₃ u₂

u1 0 -1 4

x2 1/2 -1/2 1

x1 -1/2 0 5/2

z -1 -1/2 17/2

di Gomory utilizzando la prima riga con un β frazionario:

1/2u3− 1/2 ≥ 0,

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

u₄= 1/2u₃− 1/2 ≥ 0,

e ripartendo con la base ottima{u3, 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 u4 e colonna u3. L’operazione di cardine porta alla base {u2, u4} con la relativa Tabella 5 che é ottima ma non ha coordinate tutte 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 x₁+ x₂≤ 3 (si veda la rappresentazione grafica del taglio in Figura 3). Aggiungendo una variabile u₅ relativa al taglio:

Tabella 4:

u3 u2

u1 0 -1 4

x2 1/2 -1/2 1

x₁ -1/2 0 5/2

u₄ 1/2 0 -1/2

z -1 -1/2 17/2

(3)

Tabella 5:

u4 u2

u₁ 0 -1 4

x2 1 -1/2 3/2

x1 -1 0 2

u3 2 0 1

z -2 -1/2 15/2

Tabella 6:

u₄ u₂

u1 0 -1 4

x2 1 -1/2 3/2

x1 -1 0 2

u3 2 0 1

u₅ 0 1/2 -1/2 z -2 -1/2 15/2

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

e ripartendo con la base ottima{u4, 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 u5e colonna u2. L’operazione di cardine porta alla base{u5, u4} con la relativa Tabella 7 che é ottima. La soluzione ottima

x1= 2 x2= 1

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

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

3) Il primo taglio di Dantzig si ottiene dalla Tabella 3 che ´e ottima per il

Tabella 7:

u₄ u₅ u1 0 -2 3 x2 1 -1 1 x1 -1 0 2

u3 2 0 1

u4 0 2 1

z -2 -1 7

(4)

rilassamento lineare del problema. Il taglio ´e il seguente:

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

4x1+ 2x2≤ 11.

Dal momento che la soluzione ottima del problema di PLI, il punto F , non appartiene alla retta 4x1+ 2x2= 11 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) Non é possibile modificare la funzione obiettivo in modo che Z_ott=∅. Infatti Z_a, indipendentemente dalla funzione obiettivo, contiene un numero finito di punti ed il massimo su un insieme finito di punti esiste sempre. Si puó invece eliminare un vincolo in modo da rendere Z_ott = ∅. Basta togliere il vincolo x1+ x2≤ 7/2, il che rende il problema illimitato. Si può anche aggiungere un vincolo in modo tale che Sa6= ∅ ma Za=∅ e quindi anche Zott=∅. Un esempio di tale vincolo è x1≥ 9/4.

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

min x₁₂− 10x14+ 2x₂₃+ 3x₃₄+ 8x₃₅+ x₅₆+ 5x₆₄ x12+ x14= 5

x23− x12= 1 x34+ x35− x23= 4

−x14− x34− x64=−10 x₅₆− x35=−1

x12, x14, x23, x34, x35, x56, x64≥ 0 interi La matrice dei vincoli (a meno di permutazioni delle colonne) `e la seguente:







1 1 0 0 0 0 0

−1 0 1 0 0 0 0

0 0 −1 1 1 0 0

0 −1 0 −1 0 0 −1

0 0 0 0 −1 1 0







(1)

2) Gli archi (2, 3), (3, 5), (5, 6), (6, 4), (3, 4) non formano un albero di supporto e quindi non possono rappresentare una base. Gli archi (1, 2), (1, 4), (5, 6), (6, 4), (3, 4)

(5)

formano un albero di supporto ma ponendo a 0 le variabili relative agli altri archi si ottiene dai vincoli

x12=−1 x14= 6 x34= 4 x56=−1 x64= 0

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

x₁₂= 5 x₂₃= 6 x₃₄= 9 x₃₅= 1 x₆₄= 1 Quindi tale base `e ammissibile.

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

c14= c14− c34− c23− c12=−16 c56= c56+ c64− c34+ c35= 11

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 5). Si forma un ciclo ma non è orientato e quindi non possiamo concludere che il problema è illimitato. Faccio crescere a ∆ il valore di x14. Per continuare a rispettare i vincoli dovrò avere

x14= ∆ x12= 5− ∆ x23= 6− ∆ x34= 9− ∆ x35= 1 x64= 1 e, per mantenere le variabili non negative, posso far crescere ∆ fino a 5. A questo punto si annulla x₁₂ 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₁₄= 5 x₂₃= 1 x₃₄= 4 x₃₅= 1 x₆₄= 1

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

c12= c12+ c23+ c34− c14= 16 c₅₆= c₅₆+ c₆₄− c34+ c₃₅= 11

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

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 5w1+ w2+ 4w3− 10w4− w5

w₁− w2≤ 1

(6)

w₁− w4≤ −10 w2− w3≤ 2 w3− w4≤ 3 w₃− w5≤ 8

w5≤ 1

−w4≤ 5

w1, w2, w3, w4, w5 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− w4=−10 w2− w3= 2 w3− w4= 3 w₃− w5= 8

−w4= 5

da cui la soluzione ottima del duale

w1=−15 w2= 0 w3=−2 w4=−5 w5=−10

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

5) Per fare in modo che il problema non ammetta soluzioni ammissibili è, per esempio, sufficiente porre b₄ = 10. In tal caso infatti, essendoci solo archi in entrata nel nodo 4 non ci sarebbe alcuna possibilità di far uscire le 10 unità di prodotto dal nodo 4. Per rendere il problema illimitato è sufficiente invertire il verso dell’arco (1, 4). In tal modo infatti si avrebbe alla prima iterazione

c14= c14+ c34+ c23+ c12=−4 c56= c56+ c64− c34+ c35= 11

e l’aggiunta dell’arco (1, 4) creerebbe un ciclo orientato, che `e proprio la condi- zione di illimitatezza del problema.

1) 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

T2={b, d, e} C2={b, d, e}

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

(7)

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

T₂={g} C2={b, d, e, g}

T₁=∅ C1={a, c, 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, d, e, g}

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

Si ha C1∪ C2= V , C1∩ C2=∅ e T1= T2=∅. Quindi il grafo ´e bipartito con le due classi di bipartizione

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

2) Il grafo non pu`o certamente contenere una K5non avendo alcun nodo con un numero di archi incidenti su di esso pari almeno a 4. Per quanto riguarda la K33, si nota che di essa non possono far parte i nodi d e f che hanno due soli archi incidenti su di essi. Scartando tali nodi e gli archi incidenti su di essi anche i nodi a, c, e e g si ritrovano con due soli archi incidenti su di essi e possono essere scartati. A questo punto i soli nodi b e h non possono formare una K33

dal momento che questa contiene 6 nodi.

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 finite di una sua rappresentazione topologicamente planare. In Figura 7 abbiamo una rapprsentazione topologicamente planare del grafo, da cui si ricava immediatamente una base di cicli:

a→ b → c → d → a b→ h → e → a → b b→ c → g → h → b e→ h → g → f → e

1) Il vincolo deve dire che x₁ = 1 e x₂ = 1 implicano x₃ = 1. Il vincolo che esprime questo ´e:

x3≥ x1+ x2− 1.

2) Tutte e tre le frasi sono false. Per quanto riguarda la prima frase anche un grafo con soli nodi e nessun arco è bipartito (non contiene cicli di lunghezza dispari) ma non è connesso. Per quanto riguarda le seconda frase un grafo completo di 3 nodi è connesso ma contiene cicli dispari e quindi non è bipartito.

(8)

Infine la terza frase `e anch’essa falsa, basti pensare alla K₃₃ che `e un grafo bipartito, connesso ma non planare.

3) Si noti che il punto ottimo (3, 0) non soddisfa come uguaglianza il vincolo x1+ x2≤ 4. Quindi, in base alle condizioni di complementarit`a nella soluzione ottima del duale la variabile u1 corrispondente a tale vincolo deve avere valore 0.

(9)

@

B B

A B

C D

F E

Figura 1:

(10)

@

A B

C D

F E

Figura 2:

(11)

@

A B

C D

F E

Figura 3:

(12)

2

1

3

4

5

6

Figura 4:

2

1

3

4

5

6

Figura 5:

(13)

2

1

3

4

5

6

Figura 6:

(14)

HH HH

HH

c c

c A

A A

A

b

bb bb

b b

a

b

c

e g

h d

f

Figura 7: