Quindi il punto ´e un vertice

(1)

Compito di Ricerca Operativa del 19/09/2002:

Soluzioni

Esercizio 1 (11 punti)

1) Il punto (1, 2, 1/2) appartiene a Sae 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 −2

1 1 2

1 1 0





ha rango pari a 2. Quindi il punto non ´e un vertice. Il punto (0, 3, 1/2) appartiene a S_a 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 −2

1 1 2

1 1 0

1 0 0







ha rango pari a 3. Quindi il punto é un vertice. Infine, il punto (3, 0, 1/2) non puó essere un vertice perché non appartiene a Sa (non soddisfa il quarto vincolo).

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

Inoltre, il secondo vincolo, in cui tutti i coefficienti delle variabili e il termine noto sono strettamente positivi, ci mostra che S_aé un insieme limitato. Quindi S_a é un poliedro convesso. Per il teorema di Weierstrass si deve avere che S_ott6= ∅. Infine, é ovviamente falso che Sa non ha alcun vertice (abbiamo visto che (0, 3, 1/2) é 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, 2, 1/2)) oppure essere un troncone con un solo vertice (ma abbiamo visto che é un poliedro convesso). Quindi il vertice (0, 3, 1/2) deve avere almeno un vertice adiacente e l’affermazione che Sa contiene almeno due vertici é vera. Infine é ovviamente falso che Sa contiene uno spigolo illimitato visto che Saé un insieme limitato.

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= 2x1+ 2x2− 6 v1= 2− x1− x2+ 2x3

v₂= 4− x1− x2− 2x3

(2)

Tabella 1:

x1 x2 x3

v₁ -1 -1 2 2

v2 -1 -1 -2 4

u3 -1 -1 0 3

u4 -1 0 1 2

t 2 2 0 -6

z 3 2 4 0

Tabella 2:

v1 x2 x3

x₁ -1 -1 2 2

v₂ 1 0 -4 2

u3 1 0 -2 1

u4 1 1 -1 0

t -2 0 4 -2

z -3 -1 10 6

u₃= 3− x1− x2

u4= 2− x1+ x3

x1, x2, v1, v2, u3, u4≥ 0

A questo punto possiamo risolvere il problema di I fase partendo dalla base {x1, x2, x3} cui ´e associata la Tabella 1. La base ´e 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 v1e dalla colonna x1. Eseguendo l’operazione di cardine si ottiene la Tabella 2 relativa alla base{v1, x2, x3}. La base ´e 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 u₄e dalla colonna x₃. Eseguendo l’operazione di cardine si ottiene la Tabella 3 relativa alla base{v1, x₂, u₄}. La base ´e 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 v₂e dalla colonna x₂. Eseguendo l’operazione di cardine si ottiene la Tabella 4 relativa alla base{v1, v2, u4}. Tale tabella é ottima per il problema di I fase, il quale ha valore ottimo pari a 0. Quindi la tabella é anche ammissibile per il problema di II fase. Ma essa é giá anche ottima per il problema di II fase (si ricordi che i coefficienti di costo ridotto delle variabili v1 e v2 non devono essere ≤ 0). Quindi la soluzione ottima é il punto (5/2, 1/2, 1/2) con valore ottimo pari a 21/2.

(3)

Tabella 3:

v1 x2 u4

x₁ 1 1 -2 2

v2 -3 -4 4 2

u3 -1 -2 2 1

x3 1 1 -1 0

t 2 4 -4 -2

z 7 9 -10 6

Tabella 4:

v1 v2 u4

x₁ 1/4 -1/4 -1 5/2 x₂ -3/4 -1/4 1 1/2

u3 1/2 1/2 0 0

x3 1/4 -1/4 0 1/2

t -1 -1 0 0

z 1/4 -9/4 -1 21/2

4) Il duale del problema ´e il seguente

min 2v₁+ 4v₂+ 3u₃+ 2u₄ v1+ v2+ u3+ u4≥ 3

v1+ v2+ u3≥ 2

−2v1+ 2v₂− u4≥ 4 u3, u4≥ 0, v1, v2 libere in segno

Dal momento che nella soluzione ottima del primale la variabile x1 ha valore strettamente positivo, le condizioni di complementarit´a ci dicono che la soluzione ottima del duale deve soddisfare come uguaglianza il vincolo del duale corrispondente a x1.

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

min −x12+ x13+ 2x23− 3x34+ x41+ 4x42

x₁₂+ x₁₃− x41= 4 x23− x12− x42=−7

x34− x13− x23= 1

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

(4)

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





1 1 0 0 −1 0

−1 0 1 0 0 −1

0 −1 −1 1 0 0



 (1)

2) Il nodo 2 é un nodo destinazione in cui il prodotto viene ricevuto (7 unitá di prodotto) ma l’arco (2, 3) é in uscita dal nodo 2 e quindi lungo esso non si riceve ma si invia prodotto. Qunidi, non puó essere l’unico arco incidente sul nodo 2 in una base ammissibile.

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

x12= 4 x42= 3 x34= 1

Quindi tale base `e ammissibile. Gli archi (4, 1), (1, 3), (2, 3) formano un albero di supporto ma ponendo a 0 le variabili relative agli altri archi si ottiene ad esempio x₂₃=−7 e quindi la base non `e ammissibile.

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

1 2

3 4

Figura 1:

delle variabili fuori base:

c₁₃= c₁₃+ c₃₄+ c₄₂− c12= 2 c₂₃= c₂₃+ c₃₄+ c₄₂= 3

(5)

c₄₁= c₄₁+ c₁₂− c42=−4

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 x41) e aggiungo il relativo arco all’albero di supporto (vedi Figura 2). Si forma un

Z Z

1 2

3 4

Figura 2:

ciclo ma non è orientato e quindi non possiamo concludere che il problema è illimitato. Faccio crescere a ∆ il valore di x41. Per continuare a rispettare i vincoli dovrò avere

x41= ∆ x12= 4 + ∆ x42= 3− ∆ x34= 1

e, per mantenere le variabili non negative, posso far crescere ∆ fino a 3. A questo punto si annulla x₄₂ 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₄₁= 3 x₁₂= 7 x₃₄= 1 x₄₂= x₁₃= x₂₃= 0.

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

c13= c13+ c34+ c41=−1 c23= c23+ c34+ c41+ c12=−1

c42= c42− c12− c41= 4

Ci sono due coefficienti di costo ridotto negativi e pari a -1. Prendo come variabile da far entrare in base x13e aggiungo il relativo arco all’albero di supporto

(6)

Z Z

1 2

3 4

Figura 3:

(vedi Figura 4). Si forma un ciclo orientato e quindi possiamo concludere che il problema `e illimitato.

5) 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 4w1− 7w2+ w3

w1− w2≤ −1 w₁− w3≤ 1 w2− w3≤ 2 w₃≤ −3

−w1≤ 1

−w2≤ 4

w1, w2, w3 libere in segno

Se il primale ´e illimitato, la teoria della dualit´a ci dice immediatamente che il problema duale non ha soluzioni ammissibili.

1) Si inizializzino C1 e T1 con un singolo nodo, ad esempio a. Si ponga C2 = T2=∅. Alla prima iterazione avremo

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

T₁={e, c, g, i} C1={a, e, c, g, i}

(7)

Z Z

1 2

3 4

Figura 4:

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

T2={f} C2={b, d, h, f}

T1=∅ C1={a, e, c, g, i}

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

T2=∅ C2={b, d, h, f}

T1=∅ C1={a, e, c, g, i}

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

V₁= C₁={a, e, c, g, i} V₂= C₂={b, d, h, f}

2) Il grafo non contiene una K5in quanto ha due soli nodi (h ed e) con almeno quattro archi incidenti su di essi. Per la K3,3, i nodi i e g, con due soli archi incidenti non possono essere in una K3,3. Escludendo tali nodi e i relativi archi incidenti anche i nodi d e f rimangono con due soli archi incidenti e possono quindi essere esclusi. A questo punto rimangono solo 5 nodi che sono insufficienti per formare una K3,3.

3) Per ottenere un albero di supporto possiamo utilizzare la procedura vista a

(8)

lezione, cio´e ordinare gli archi ed aggiungerli solo se non formano cicli con quelli gi´a inseriti. Prendendo gli archi nell’ordine seguente:

(a, b) (a, d) (a, h) (b, c) (b, e) (c, f ) (c, h) (d, e) (d, g) (e, f ) (e, h) (f, i) (g, h) (h, i)

si ottiene l’albero di supporto in Figura 5. Aggiungendo uno alla volta gli archi

J J

a b c

d e f

g h i

Figura 5:

che non fanno parte dell’albero si ottengono i seguenti 6 cicli:

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

1)

set PRODOTTI;

param costo{PRODOTTI}>0;

param budget >0;

var x{PRODOTTI} BINARY;

(9)

subject to max spesa : sum{i in PRODOTTI } costo[i]*x[i]<= budget;

2) Il vincolo ´e

x2≥ 1 − x1− x3

3) La prima affermazione ´e falsa: nel problema max −x1− x2

x1, x2≥ 0

Sa é un troncone ma Sott contiene la sola origine. Lo stesso esempio mostra che anche la seconda é falsa. La terza affermazione é falsa: nel problema

max x1

x₁≤ 1 x2≤ 1 x1, x2≥ 0

Sott contiene l’intero segmento tra i punti (1, 0) e (1, 1) e tale segmento non é un insieme finito. La quarta affermazione é falsa perché il numero di vertici é sempre finito.