Compito di Ricerca Operativa del 11/07/2002: Soluzioni

(1)

Compito di Ricerca Operativa del 11/07/2002:

Soluzioni

Esercizio 1 (11 punti)

1) Si ricordi che un vertice per definizione deve appartenere ad almeno 4 iperpiani generatori. Ora, essendo gli iperpiani generatori i seguenti

x₁+ x₂+ x₃+ x₄= 2 2x₁+ 3x₂+ x₃+ 4x₄= 4 x1= 0 x2= 0 x3= 0 x4= 0

almeno due iperpiani generatori che generano il vertice ottimo devono trovarsi tra gli iperpiani xi= 0, i = 1, 2, 3, 4.

2) Il duale del problema `e il seguente

max 2u₁+ 4u₂ u1+ 2u2≤ 4 u1+ 3u2≤ 2 u1+ u2≤ 1 u1+ 4u2≤ 6

u₁, u₂≥ 0

In Figura 1 `e mostrata la regione ammissibile (il poliedro convesso OABC) e la funzione obiettivo del problema duale, da cui si ricava che la soluzion ottima di tale problema `e il punto B di coordinate

u^∗₁= 1/2 u^∗₂= 1/2 con valore ottimo pari a 3.

3) `E possibile affermare che nella soluzione ottima del primale si ha x₁= 0. Si nota che il vincolo associato a x₁, ovvero u₁+ 2u₂ ≤ 4 non potr`a mai essere soddisfatto come uguaglianza nella regione ammissibile del duale. Infatti dal secondo vincolo u1+ 3u2≤ 2 e da u2≥ 0 si ha

u1+ 2u2≤ u1+ 3u2≤ 2 < 4.

Quindi, per le condizioni di complementarit`a si deve avere x₁= 0.

4) Per risolvere il problema lo trasformiamo prima in forma canonica:

− max z =−4x1− 2x2− x3− 6x4

u₁=−2 + x1+ x₂+ x₃+ x₄ u2=−4 + 2x1+ 3x2+ x3+ 4x4

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

(2)

Tabella 1:

x1 x2 x3 x4

u₁ 1 1 1 1 -2

u2 2 3 1 4 -4

z -4 -2 -1 -6 0

Tabella 2:

u₁ x₂ x₃ x₄

x1 1 -1 -1 -1 2

u2 2 1 -1 2 0

z -4 2 3 -2 -8

A questo punto possiamo risolvere il problema partendo dalla base non ammissibile {x1, x₂, x₃, x₄} cui ´e associata la Tabella 1. La base ´e non ammissibile.

Applicando le regole viste a lezione per la fase di avvicinamento a S_a, il cardine si trova nella posizione individuata dalla riga u₁ e dalla colonna x₁. (NB Dal momento che la base `e ammissibile per il duale, essendo tutti gli elementi dell’ultima riga non positivi, va altrettanto bene se applicate il simplesso duale). Eseguendo l’operazione di cardine si ottiene la Tabella 2 relativa alla base {u1, x2, x3, x4}. La base ´e ammissibile ma non ottima (vi sono coefficienti di costo ridotto positivi nella riga z). Applicando le regole viste a lezione il cardine si trova nella posizione individuata dalla riga u2e dalla colonna x3. Eseguendo l’operazione di cardine si ottiene la Tabella 3 relativa alla base {u1, x2, u2, x4}.

Tale tabella non é ottima (vi sono coefficiente di costo ridotto positivi). Eseguo un’operazione di cardine con cardine nella posizione individuata dalla riga x1e dalla colonna x2. Si ottiene la Tabella 4 relativa alla base{u1, x1, u2, x4}. Tale tabella é ottima (i coefficienti di costo ridotto sono tutti negativi). Quindi la soluzione ottima é il punto (0, 1, 1, 0) con valore ottimo pari a 3 (nella tabella appare il valore ottimo -3 ma nella trasformazione in forma canonica del problema abbiamo messo un segno - davanti a max, quindi il valore -3 va invertito di segno per ottenere il valore ottimo del problema originario).

Tabella 3:

u₁ x₂ u₂ x₄

x1 -1 -2 1 -3 2

x3 2 1 -1 2 0

z 2 5 -3 4 -8

(3)

Tabella 4:

u1 x1 u2 x4

x₂ -1/2 -1/2 1/2 -3/2 1 x3 3/2 -1/2 -1/2 1/2 1 z -1/2 -5/2 -1/2 -7/2 -3

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

min −3x15+ x₂₁+ 2x₃₂− 5x34+ 7x₄₁+ 4x₄₅+ 3x₅₂+ 2x₅₃ x15− x21− x41= 1

x21− x32− x52=−5 x32+ x34− x53= 4 x41+ x45− x34= 2

x₁₅, x₂₁, x₃₂, x₃₄, x₄₁, x₄₅, x₅₂, x₅₃≥ 0 interi La matrice dei vincoli (a meno di permutazioni delle colonne) `e la seguente:







1 −1 0 0 −1 0 0 0

0 1 −1 0 0 0 −1 0

0 0 1 1 0 0 0 −1

0 0 0 −1 1 1 0 0







(1)

2) Il nodo 1 é un nodo sorgente in cui il prodotto viene realizzato (1 unitá di prodotto). L’unico arco in uscita da tale nodo e lungo il quale si puó quindi inviare il prodotto realizzato é l’arco (1, 5) e quindi questo arco deve far parte della base ottima e di ogni base ammissibile.

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

x₅₃=−6 x21=−5 x34=−2 x15=−4

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

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

x53= 1 x32= 5 x41= 2 x15= 3 Quindi tale base `e ammissibile.

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

(4)

ridotto delle variabili fuori base:

c21= c21+ c15+ c53+ c32= 2 c34= c34+ c41+ c15+ c53= 1

c45= c45− c15− c41= 0 c52= c52− c32− c53=−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 x52) e aggiungo il relativo arco all’albero di supporto (vedi Figura 3). Si forma un ciclo ma non è orientato e quindi non possiamo concludere che il problema è illimitato. Faccio crescere a ∆ il valore di x₅₂. Per continuare a rispettare i vincoli dovrò avere

x₅₂= ∆ x₃₂= 5− ∆ x53= 1− ∆ x41= 2 x₁₅= 3

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

x52= 1 x32= 4 x41= 2 x15= 3

(le altre variabili sono uguali a 0). Rifaccio la verifica di ottimalit`a calcolando i coefficienti di costo ridotto.

c21= c21+ c15+ c52= 1 c₃₄= c₃₄+ c₄₁+ c₁₅+ c₅₂− c32= 0

c₄₅= c₄₅− c15− c41= 0 c₅₃= c₅₃+ c₃₂− c52= 1

Tutti i coefficienti di costo ridotto sono non negativi e quindi la soluzione `e ottima, con valore ottimo pari a 16. Essendoci ben due coefficienti di costo ridotto nulli possono esserci altre soluzioni ottime.

5) Per avere un problema illimitato basta porre, per esempio, c34 = −8. A questo punto alla prima iterazione i coefficienti di costo ridotto delle variabili fuori base sono:

c21= c21+ c15+ c53+ c32= 2 c34= c34+ c41+ c15+ c53=−2

c₄₅= c₄₅− c15− c41= 0 c₅₂= c₅₂− c32− c53=−1

(5)

e si seleziona l’arco (3, 4), il quale forma un ciclo orientato con quelli della base e quindi il problema `e illimitato.

6) 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 w₁− 5w2+ 4w₃+ 2w₄ w1≤ −3 w2− w1≤ 1 w3− w2≤ 2 w3− w4≤ −5

w₄− w1≤ 7 w4≤ 4

−w2≤ 3

−w3≤ 2

w1, w2, w3, w4 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=−3 w3− w2= 2 w₄− w1= 7

−w2= 3

da cui la soluzione ottima del duale

w1=−3 w2=−3 w3=−1 w4= 4

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

1) Si inizializzino C₁ e T₁ con un singolo nodo, ad esempio a, cio`e si ponga C₁= T₁={a}. Si ponga C2= T₂=∅. Alla prima iterazione avremo

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

T1={b, c, d, e, g, i} C1={a, b, c, d, e, g, i}

Si ha C₁∩ C26= ∅ quindi possiamo immediatamente concludere che il grafo non

`

e bipartito.

2) Il grafo non pu`o certamente contenere una K₅ avendo solo 4 nodi (b, c, d, g)

(6)

con un numero di archi incidenti su di essi pari almeno a 4. Per quanto riguarda la K33, si nota che di essa non possono far parte i nodi e, f, i che hanno due soli archi incidenti su di essi. Scartando tali nodi e gli archi incidenti su di essi anche il nodo h si ritrova con due soli archi incidenti su di essi e pu`o essere scartato.

A questo punto rimangono i soli 5 nodi a, b, c, d, g che non possono formare una K33dal 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 rappre- sentazione topologicamente planare. In Figura 5 abbiamo una rapprsentazione topologicamente planare del grafo, da cui si ricava immediatamente una base di cicli:

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

1) Abbiamo due insiemi (DEP OSIT I e N EGOZI) e due vettori di variabili (uno con insieme indice DEP OSIT I e l’altro con insieme indice N EGOZI) che possono assumere solo valori non negativi. Il modello AMPL ´e il seguente:

set DEPOSITI;

set NEGOZI;

var x{DEP OSIT I}>=0;

var y{NEGOZI}>=0;

subject to vincolo uguaglianza : sum{i in DEPOSITI } x[i]= sum{j in NE- GOZI} y[j];

2) Per avere un duale con pi`u soluzioni ottime basta avere un primale con un vertice ottimo degenere. Ad esempio:

max x1− x2

x1+ x2≤ 1 x1≤ 1 x₁, x₂≥ 0 ha come duale

min u₁+ u₂

(7)

u₁+ u₂≥ 1 u1≥ −1 u1, u2≥ 0

che ha come soluzioni ottime l’intero segmento tra (0, 1) e (1, 0).

La prima frase è FALSA. Un problema di PL o ha una sola soluzione ottima o ne ha infinite ma non ne può avere, per esempio, due sole. La terza frase è VERA. Infatti, dato l’intero non negativo N , il problema

max x1

x1≤ 1 x₂≤ N

x1, x2≥ 0 x1, x2∈ I

ha N + 1 soluzioni ottime (0, i), i = 0, . . . , N . La seconda frase `e VERA.

Infatti, rimuovendo il vincolo x2 ≤ N si ha che il problema visto sopra ha infinite soluzioni ottime (0, i), i = 0, . . .. Infine, la quarta frase `e VERA come mostra il seguente esempioin cui tutti i punti del segmento tra (0, 1) e (1, 0) sono soluzioni ottime:

max x₁+ x₂ x1+ x2≤ 1

x₁, x₂≥ 0

(8)

H HH H HH HH HH HH H HH HH HH HH HH H HH HH HH H

@

XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX

PP PP PP PP PP PP PP PP P HH

HH HH

HH H

HH HH

u1 u2

O A

B 1

1 2

2/3 C

Figura 1:

(9)

"

1 2

4 3

5

Figura 2:

"

b b

b

1 2

4 3

5

Figura 3:

"

b b

b

1 2

4 3

5

Figura 4:

(10)

bb b

bb bb

b

%

% e

e e

e

@

A A

a b

c d

f

g

h

e i

Figura 5: