Esercizi per il corso di ricerca operativa 1

Testo completo

(1)Esercizi per il corso di ricerca operativa 1. Ultimo aggiornamento: 8 gennaio 2004.

(2) 2.

(3) Indice I. Esercizi. 5. 1 Programmazione lineare. 7. 2 Dualita. 13. 3 Analisi di sensitivita. 17. 4 Programmazione intera. 21. 5 Introduzione ai grafi. 25. 6 Problemi di flusso a costo minimo. 27. 7 Problema del massimo flusso. 31. 8 Problema del trasporto. 33 8.1 Esercizi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33. II. Soluzioni. 35. 1 Programmazione lineare. 37. 2 Dualita. 51. 3 Analisi di sensitivita. 61. 4 Programmazione intera. 65. 5 Introduzione ai grafi. 73. 6 Problemi di flusso a costo minimo. 77. 7 Problema del massimo flusso. 83. 8 Problema del trasporto.. 87. III. 93. Un esercizio di riepilogo. 3.

(4) 4. INDICE.

(5) Parte I. Esercizi. 5.

(6)

(7) Capitolo 1. Programmazione lineare Porre in forma canonica i seguenti programmi lineari.. ESERCIZIO 1.1.. min 3x1 + 4x2 − 2x3 soggetto a x1 + 2x2 − x3. ≥5. 2x1 + 4x3 x1 + x 2 + x 3. = 12 ≤ 15. (a). x1 , x2 ≥ 0, x3 libera. max 4x1 − x2 soggetto a x1 + x 2 − x 3 3x1 + x3. =8 ≤7. (b). x1 ≥ 0, x2 libera, x3 ≤ 0. min 8x1 − x2 + x3 soggetto a x1 + x 3. ≥4. x2 − x 3 x1 − x 2. ≤7 ≤2. (c). x1 , x2 ≥ 0, x3 ≤ 0. max 4x1 − x2 soggetto a x1 + 2x2. ≤2. 2x1 + 7x2. =8. (d). x1 ≥ 0, x2 ≤ 0. min 4x1 + 5x2 − x3 + 2x4 7.

(8) 8. CAPITOLO 1. PROGRAMMAZIONE LINEARE. soggetto a x1 + x 2. ≥4. x2 + x 3 x3 − x 4. ≤7 ≤2. x1 − x 4. = 12. (e). x1 , x2 .x3 ≥ 0, x4 libera. max 2x1 + 4x3 soggetto a x1 + x 2 + x 3. ≤ 12. x1 − x 2 x2 + x 3. ≥2 ≤4. (f ). x1 ≥ 0, x2 libera, x3 ≤ 0.. Porre in forma standard i programmi lineari dell’eser-. ESERCIZIO 1.2.. cizio 1.1. ESERCIZIO 1.3.. Risolvere i seguenti programmi lineari utilizzando il metodo. del simplesso. max 3x1 + 2x2 − 5x3 soggetto a 4x1 − 2x2 + 2x3. ≤4. 2x1 + x2 + x3. ≤1. (a). x1 , x2 , x3 ≥ 0. max x1 − 2x2 + 3x3 soggetto a x1 − 2x2 + x3. ≤2. 3x1 − x2 − 2x3. ≤6. (b). x1 , x 2 , x 3 ≥ 0 max 2x1 + x2 + 3x3 soggetto a x1 + x 2 + x 3 2x1 + 3x2 + 8x3. ≤2 ≤ 12. x1 , x2 , x3 ≥ 0. min 3x1 + x2 − 2x3 − x4. (c).

(9) 9 soggetto a 2x1 + x2 − x3 + 3x4 − x1 + 2x2 − 2x3 + 2x4. ≤8 ≤4. x1 + x 3. ≤ 10. (d). x1 , . . . , x4 ≥ 0. max x1 + 3x2 − x3 soggetto a 2x1 + x2 x1 + x2 + 3x3. ≤3 ≤6. 2x1 + x2 + 3x3. ≤8. (e). x1 , x2 , x3 ≥ 0. max 4x1 + x2 + 5x3 soggetto a − x1 + x2 2x2 − x3. ≤1 ≤2. x1 + x 3. ≤1. (f ). x1 , x2 , x3 ≥ 0.. ESERCIZIO 1.4.. Risolvere i seguenti programmi lineari utilizzando il metodo. del simplesso. min 6x1 + x2 + 3x3 soggetto a 10x1 − 2x2 + 5x3. ≥ 15. x1 − x2 + 3x3. ≥6. (a). x1 , x2 , x3 ≥ 0. min 7x1 + 2x2 − 5x3 − x4 soggetto a 4x1 + 3x2 + 2x4 − 5x1 − 3x2 + x3 − x4 x1 , . . . , x4 ≥ 0. min 2x1 + x2 + 4x3. ≥2 ≤1. (b).

(10) 10. CAPITOLO 1. PROGRAMMAZIONE LINEARE. soggetto a x1 + x2 + 2x3. =3. 2x1 + x2 + 3x3. =5. (c). x1 , x2 , x3 ≥ 0. max x1 + x2 + x3 soggetto a − x1 − 2x2 + x3 + x4. =5. 4x2 + x3 + 2x4 3x2 − 2x4. =2 ≤6. (d). x1 , . . . , x4 ≥ 0. max 4x1 + 3x2 − x3 + 2x4 soggetto a − x1 + 2x2 + x3 − x4. ≥2. 2x1 − x2 + x3 − 5x4. ≤ −3. (e). x1 , . . . , x4 ≥ 0. min x1 + x2 − 2x3 soggetto a 2x1 + x2 + x3. =2. 3x1 + x2 + 2x3 x1 + 2x2 + x3. =5 =4. (f ). x1 , x2 , x3 ≥ 0.. ESERCIZIO 1.5. Per i programmi lineari dell’esercizio 1.3, dire se le basi finali risultano ottime cambiando l’obiettivo come segue.. (a) max 7x1 + x2 (b) min 4x1 + 5x2 − x3 (c) min x1 + x2 + x3. (d) (e) (f ). min 5x1 + 3x2 − 2x3 − x4 max 5x1 + 3x2 min x1 + 2x2 − x3. Per ognuno dei programmi lineari dell’esercizio 1.3, identificare la matrice A−1 B .. ESERCIZIO 1.6.. Risolvere i seguenti programmi lineari utilizzando il metodo grafico. Confrontare i risultati con quelli forniti dal simplesso.. ESERCIZIO 1.7.. max x1 + x2.

(11) 11 soggetto a 2x1 − x2 x1 + 4x2. ≥4 ≤ 10. x2. ≥1. (a). x1 , x2 ≥ 0. min 2x1 + x2 soggetto a x1 + 4x2 x1. ≥8 ≥2. − 2x1 + x2. ≤4. (b). x1 , x2 ≥ 0. max 2x1 − x2 soggetto a x1 + 4x2 x1. ≥8 ≥2. − 2x1 + x2. ≤4. (c). x1 , x2 ≥ 0. max. 2 8 x1 + x2 3 3. soggetto a x1 + 4x2. ≤9. x1 x2. ≤8 ≤2. x1 , x2 ≥ 0.. (d).

(12) 12. CAPITOLO 1. PROGRAMMAZIONE LINEARE.

(13) Capitolo 2. Dualita ESERCIZIO 2.1. Partendo dalla forma standard, determinare i duali dei programmi lineari dell’esercizio 1.3. ESERCIZIO 2.2. Partendo dalla forma standard, determinare i duali dei programmi lineari dell’esercizio 1.4. ESERCIZIO 2.3.. Dato il seguente programma lineare in forma standard. max cx soggetto a Ax = b. (P). x ≥ 0, ed il suo duale min ub soggetto a uT A ≥ c,. (D). con x ∈ Rn , A ∈ Rm×n , λ ∈ Rm , c ∈ Rn , b ∈ Rm + rispondere, utilizzando i concetti di dualit` a, alle seguenti domande. (a) Se (P) ammette soluzione ottima finita (Sot 6= ∅), sostituendo il vettore b con un vettore perturbato b + θ, θ ∈ Rm , è possibile ottenere un programma lineare con obiettivo illimitato? (b) Se (P) ammette soluzione ottima finita, sostituendo il vettore c con un vettore perturbato c + θ, θ ∈ Rm e ≤ 0, è possibile ottenere un programma lineare con obiettivo illimitato? (c) Se gli elementi della matrice A sono tutti ≥ 0, (P) pu` o essere un programma lineare con obiettivo illimitato? ESERCIZIO 2.4. Dati (P) e (D) come nell’esercizio 2.3, ed una soluzione ammissibile duale u ¯, sia S = {j : u ¯aj = cj , 1 ≤ j ≤ n}, dove a1 , . . . , an sono le. 13.

(14) 14. CAPITOLO 2. DUALITA. ` possibile affermare che se per il seguente programma lineare colonne di A. E (detto primale ristretto) esiste una soluzione ammissibile x ¯ allora x ¯ e u ¯ sono soluzioni ottime per (P) e (D) rispettivamente? X max c j xj j∈S. soggetto a Ax = b. (PR). xj = 0, ∀j ∈ /S x≥0. ESERCIZIO 2.5. Risolvere i seguenti programmi lineari, senza impostare il problema di prima fase.. min 3x1 + x2 + 3x3 soggetto a x1 + x 2 2x1 + x2 − x3. ≥4 ≥8. (a). x1 , x2 , x3 ≥ 0. min 2x1 + 3x2 + x3 soggetto a x1 + x 2 − x 3 2x1 + x3. ≥6 ≥4. x1 + x2 − 2x3. ≤2. (b). x1 , x2 , x3 ≥ 0.. ESERCIZIO 2.6. Partendo dalla riformulazione rispetto alla base ottima, introdurre nell’esercizio 2.5(a) il vincolo supplementare. x1 + 2x3 ≥ 1 e riottimizzare il programma, senza ricominciare da capo (come si pu` o fare?). ESERCIZIO 2.7.. vincolo x1 + x2 ≤ 5.. Come l’esercizio percedente, ma introducendo in 2.5(b) il.

(15) 15 ESERCIZIO 2.8. Per ognuno dei programmi lineari dell’esercizio 1.3, determinare il valore ottimo delle variabili duali se l’ottimo esiste (considerare i duali formulati rispetto alle forme standard), e quando non esiste dire cosa pu` o accadere nel duale.. Come l’esercizio precedente, con riferimento ai programmi lineari dell’esercizio 1.4.. ESERCIZIO 2.9.. Senza passare per la forma standard, scrivere i duali dei programmi lineari dell’esercizio 1.4.. ESERCIZIO 2.10..

(16) 16. CAPITOLO 2. DUALITA.

(17) Capitolo 3. Analisi di sensitivita Per ognuno dei seguenti programmi lineari, per i quali sono specificate la base ottima Bot , la AB −1 e la riformulazione associata, verifiot care se ammissibilit` a ed ottimalit` a sono conservate a fronte delle perturbazioni specificate per i singoli ci , bi .. ESERCIZIO 3.1.. max −3x1 − 4x2 + 2x3 soggetto a x1 + 2x2 − x3 − x4. =4. 2x1 − x2 + x5. =5. (a). x1 , . . . , x5 ≥ 0, A−1 Bot. Bot = {x2 , x5 }, max. =. 1. 0 , 1. 2 1 2. z = −8 −x1 − 2x4 x2 = 2 − 21 x1 x5 = 7 − 25 x1 x1 , . . . , x5 ≥ 0,. ∆b2 = −8, ∆c3 = 1, ∆c5 = −. + 12 x3 + 12 x3. + 21 x4 + 21 x4. 1 5. max 4x1 − x2 + 2x4 soggetto a x2 + x 3 + x 5. =6. x1 + 2x3 − x4 2x1 + 4x2. =7 =8. (b). x1 , . . . , x5 ≥ 0, Bot = {x1 , x3 , x4 },. A−1 Bot. . 0 0  = 1 0 2 −1 17. 1 2. .  0 , 1 2.

(18) 18. CAPITOLO 3. ANALISI DI SENSITIVITA max. z x1 x3 x4. = 34 −17x2 = 4 −2x2 = 6 −x2 = 9 −4x2 x1 , . . . , x5 ≥ 0,. −4x5 −x5 −2x5. ∆b3 = −1, ∆c2 = 1, ∆c4 = −1.. max −3x1 + x2 − x3 + 2x4 soggetto a 3x1 − 2x2 + x4 x2 + 5x3 − x5. =7 =8. x2 + x 3. =6. (c). x1 , . . . , x5 ≥ 0, Bot = {x2 , x3 , x4 }, max. z x2 x3 x4. = = = =. 41. A−1 Bot −9x1. . 0 − 14  1 = 0 4 1 − 12. 11 2 1 2. 18 −3x1 x, . . . , x5 ≥ 0,. − 23 x5 − 41 x5 + 41 x5 − 21 x5. 5 4. .  − 14  , 5 2. ∆b2 = −3, ∆c1 = 9, ∆c2 = −8.. max x1 − 2x2 − 5x3 + 2x4 soggetto a − 5x1 + 2x3 + 3x4 2x2 − 4x3 + 2x5. =7 =8. x2 + x 4. =6. (d). x1 , . . . , x5 ≥ 0, Bot = {x1 , x4 , x5 }, max. z x1 x4 x5. = = = =. 71 5 11 5. . − 51   0 0. − 23 5 x2 − 53 x2 6 −x2 4 −x2 x1 , . . . , x5 ≥ 0,. ∆b2 = 1, ∆c2 = 5, ∆c1 = −2.. 0 0 1 2. 3 5. .  1 , 0. − 23 5 x3 + 25 x3. +2x3.

(19) 19. max 3x1 − 2x2 + x3 − x5 soggetto a − 5x1 − 2x3 + x4 x2 − 2x3 + 2x5. =6 =9. x3 + x 4 + x 5. =6. (e). x1 , . . . , x5 ≥ 0, Bot = {x2 , x4 , x5 }, max. z x2 x4 x5.  2 1 −2  1 0 0 , −1 0 1 . = −18 −12x1 = 9 +10x1 = 6 +5x1 = 0 −5x1 x1 , . . . , x5 ≥ 0.. −12x3 +8x3 +2x3 −3x3. ∆b1 = 1, ∆c1 = −1, ∆c4 = 3.. max 3x1 − 4x2 − x4 soggetto a 2x1 − 2x3 + x4 − x2 + x3 + 2x5. =7 = 10. 3x1 + 3x3 − 2x4 + x5. =6. (f ). x1 , . . . , x5 ≥ 0, Bot = {x1 , x4 , x5 },. . 2 7 3 7. 1 − 14. 0. max. z x1 x4 x5. = = = =. 15 7 15 7 19 7. − 61 14 x2 1 − 14 x2 + 17 x2 + 21 x2. 5 x1 , . . . , x5 ≥ 0.. 1 7 1 2. 1 7. .  − 27  , 0. 13 − 14 x3 3 + 14 x3 3 + 14 x3 − 21 x3. ∆b2 = 2, ∆c1 = 1, ∆c2 = 1. ESERCIZIO 3.2. Per ognuno dei programmi lineari dell’esercizio 3.1 calcolare per ogni termine noto bi il massimo ed il minimo valore della perturbazione ∆bi ∈ R che non compromette l’ammissibilit` a della base specificata. Per ogni coefficiente di costo ci , calcolare il minimo e massimo valore della perturbazione ∆ci ∈ R che non compromette l’ottimalit` a della base specificata..

(20) 20. CAPITOLO 3. ANALISI DI SENSITIVITA. ESERCIZIO 3.3. Per ognuno dei programmi lineari dell’esercizio 3.1, verificare se le seguenti perturbazioni ∆aij dei coefficienti aij (coefficiente di xj nel vincolo i) specificati causano perdita di ottimalit` a.. (a) (b). ∆a14 = 2; ∆a25 = −1;. (c) (d). ∆a25 = −1; ∆a23 = 5;. (e) (f ). ∆a31 = −5; ∆a32 = 1..

(21) Capitolo 4. Programmazione intera Risolvere i seguenti programmi lineari interi per mezzo dell’algoritmo di Gomory.. ESERCIZIO 4.1.. max 2x1 − x2 − x3 soggetto a 2x1 + x2. ≤5. 4x2 + x3 x1 − x 3. ≤5 ≥2. (a). x1 , . . . , x3 ≥ 0, intere. max −2x1 + 3x2 − x3 soggetto a x1 + 3x2 + x4 x2 + 2x3 + x5. =8 =9. x1 − x 2 + x 6. =7. (b). x1 , . . . , x5 ≥ 0, intere. max 2x1 + 3x2 − x3 soggetto a 2x1 + x2 − x3 + x4. =5. 2x2 + x3 + x5. =3. (c). x1 , . . . , x5 ≥ 0, intere. max −x1 + 2x2 − 3x3 21.

(22) 22. CAPITOLO 4. PROGRAMMAZIONE INTERA. soggetto a x2 − x3 − 2x4 2x1 + x3 + 3x4 + x5. =3 =7. (d). x1 , . . . , x5 ≥ 0, intere. max 3x1 − x2 + x3 soggetto a 2x1 − x2 + x3. =1. 3x1 + 2x2 + x4. =3. (e). x1 , . . . , x4 ≥ 0, intere. max 2x2 + x3 soggetto a 3x1 + 3x2 + x3 x2 + x 3. =2 =1. x1 + x 4. =1. (f ). x1 , . . . , x4 ≥ 0, intere.. Risolvere i seguenti programmi lineari con il metodo del. ESERCIZIO 4.2.. branch and bound. max −x1 − x2 soggetto a 2x1 + x2. ≥5. x1 x2. ≤3 ≤6. (a). x1 , x2 ≥, intere. max −x1 + 2x2 soggetto a 3x1 − 2x2. ≥6. x1 x1. ≤5 ≥2. x1 , x2 ≥ 0, intere. max 3x1 + 4x2. (b).

(23) 23 soggetto a 2x1 2x1 + 3x2. ≤5 ≤7. (c). x1 , x2 ≥ 0, intere. max −3x1 − x2 soggetto a x1 x1 + 3x2. ≤5 ≥4. (d). x1 , x2 ≥ 0, intere.. ESERCIZIO 4.3. Risolvere i programmi a variabili intere dell’esercizio 4.1 con. il metodo del branch and bound..

(24) 24. CAPITOLO 4. PROGRAMMAZIONE INTERA.

(25) Capitolo 5. Introduzione ai grafi ESERCIZIO 5.1. Per ognuno dei seguenti grafi orientati G(V, A), rappresentati come lista di adiacenze, determinare se G è connesso o meno utilizzando l’algoritmo visto a lezione, e determinare le sue componenti connesse.. (a). a :(b, e),. b :(c),. c :∅,. d :(e, f ), e :∅. f :(c),. g :(e, f ).. (b) (c). a :(c), a :(g),. b :(d), b :∅,. c :(e), c :(b, d),. d :(f ), d :(e),. f :(g), f :(b),. g :(b), h :(a), g :(a, h), h :(a).. (d) (e). a :(b), b :(c), a :(c, f ), b :(a),. c :(d, f ), d :(a, e), c :(b), d :(e, g),. e :(a, b), f :∅. e :(d, g), f :∅,. (f ). a :(c, d),. c :(f ),. e :(d),. b :(g),. d :∅,. e :(h), e :(b).. g :(d, e).. f :(h), g :(e, h),. ESERCIZIO 5.2. Per ognuno dei grafi dell’esercizio 5.1, determinare se G ` e bipartito utilizzando l’algoritmo visto a lezione.. Le seguenti matrici wij rappresentano i pesi degli archi di altrettanti grafi G(V, A). Quando wij = ∞, l’arco corrispondente non esiste; se la matrice è triangolare alta, si intende riferita ad un grafo non orientato. Per ogni grafo, determinare uno spanning tree di peso totale minimo utilizzando entrambi gli algoritmi visti a lezione.. ESERCIZIO 5.3.. a b c d e  a ∞ 5 1 8 15  b  9 ∞ 7 ∞ ∞  c  3 2 ∞ 4 ∞  d∞ 7 ∞ ∞ 8  e 7 12 4 ∞ ∞ (a). a a ∞ b ∞ c  6 d 9 e ∞. b c d 4 7 ∞ ∞ 1 5 ∞ ∞ 8 ∞ ∞ ∞ ∞ 4 2 (b). e  4 3   8   7  ∞. a  a ∞ b  c  d e. a b c d  a ∞ 12 9 4 b ∞ 3 2  c ∞ ∞  d ∞ e (d). e  3 ∞  6   4  ∞. . b c 7 8 ∞ 12 ∞. (c). . d e  4 12 1 2   5 3   ∞ 1  ∞ 25. h :∅.. i :(d)..

(26) 26. CAPITOLO 5. INTRODUZIONE AI GRAFI a  a ∞ b  5 c ∞ d ∞ e ∞ f ∞. b c d e f  10 7 ∞ ∞ ∞ ∞ 2 4 3 9   ∞ ∞ 5 8 ∞  9 8 ∞ ∞ 7   7 ∞ ∞ ∞ 2  ∞ ∞ 4 ∞ ∞ (e). a  a ∞ b ∞ c  5 d ∞ e 3 f ∞. b c d e f ∞ 4 3 8 ∞ ∞ 5 2 ∞ 7 ∞ ∞ 6 2 9 ∞ 5 ∞ 1 ∞ 4 11 2 ∞ 5 12 ∞ ∞ 4 ∞ (f ).        .

(27) Capitolo 6. Problemi di flusso a costo minimo Nel problema del flusso a costo minimo si considera un grafo G(V, A), con costi cij associati ad ogni arco (ij) ∈ A. Ai nodi i ∈ V sno associati valori bi che identificano nodi sorgente (bi > 0, il flusso viene generato a tali nodi), nodi destinazione (bi < 0, il flusso viene “consumato”) e nodi di transito (bi = 0). Il modello di Programmazione Lineare del problema è il seguente. X min cij xij (i,j)∈A. soggetto a X. xij −. j : (i,j)∈A. xij ≥ 0,. X. ∀i ∈ A,. xji = bi. (I). j : (j,i)∈A. ∀(i, j) ∈ A.. I vincoli (I) esprimono la conservazione del flusso nella rete. Per ognuno dei grafi di Figura 6.1, dire se i seguenti insiemi di archi identificano basi del problema, ed in caso affermativo calcolare, quando possible, i valori dei flussi nelle soluzioni ammissibili ad essi associate.. ESERCIZIO 6.1.. (a) B1 = {(1, 2), (2, 3), (2, 6), (4, 5), (5, 6), (6, 7), (7, 8)}, B2 = {(1, 3), (1, 4), (2, 3), (3, 6), (3, 5), (5, 8), (7, 8)}, B3 = {(1, 2), (1, 4), (2, 6), (4, 5), (5, 6), (5, 8), (6, 7)}. (b) B1 = {(2, 1), (3, 6), (4, 1), (4, 5), (5, 7), (6, 2)}, B2 = {(1, 3), (3, 5), (3, 6), (4, 1), (6, 2), (6, 7)}, B3 = {(1, 3), (3, 5), (3, 6), (4, 5), (5, 7), (6, 2)}. (c) B1 = {(1, 2), (2, 3), (2, 4), (4, 5), (5, 6)}, B2 = {(1, 2), (2, 4), (3, 4), (4, 5), (5, 6)}, B3 = {(1, 2), (2, 3), (2, 4), (3, 4), (5, 6)}. (d) B1 = {(1, 2), (2, 6), (3, 4), (5, 4), (6, 3)}, B2 = {(1, 2), (3, 2), (5, 3), (5, 4), (5, 6)}, B3 = {(1, 2), (1, 6), (3, 2), (3, 4), (5, 3)}. 27.

(28) 28. CAPITOLO 6. PROBLEMI DI FLUSSO A COSTO MINIMO. (e) B1 = {(1, 2), (1, 3), (2, 4), (3, 5), (4, 8), (6, 3), (8, 7)}, B2 = {(1, 2), (2, 4), (3, 2), (5, 7), (6, 3), (6, 5), (8, 7)}, B3 = {(1, 2), (1, 3), (2, 4), (3, 5), (5, 7), (6, 3)}. (f ) B1 = {(1, 2), (2, 5), (3, 6), (4, 2), (4, 7), (5, 3)}, B2 = {(1, 2), (3, 2), (3, 6), (4, 7), (5, 3), (5, 7)}, B3 = {(1, 2), (3, 2), (3, 6), (4, 2), (5, 3), (5, 7)}. Per ognuno dei grafi di Figura 6.1 determinare un flusso a costo minimo applicando il simplesso su rete, partendo dalla base B0 specificata.. ESERCIZIO 6.2.. (a) B0 = {(1, 2), (1, 4), (2, 3), (4, 5), (5, 6), (5, 8), (6, 7)}; (b) B0 = {(1, 3), (1, 6), (3, 5), (4, 1), (5, 7), (6, 2)}; (c) B0 = {(1, 2), (2, 3), (3, 4), (4, 5), (5, 6)}; (d) B0 = {(1, 2), (2, 6), (3, 4), (4, 6), (5, 4)}; (e) B0 = {(1, 2), (1, 3), (1, 6), (2, 4), (3, 5), (4, 8), (8, 7)}; (f ) B0 = {(1, 2), (2, 5), (3, 6), (4, 2), (5, 3), (5, 7)}. ESERCIZIO 6.3. Commentare il risultato dell’esercizio precedente, punto (e). La presenza di soluzioni illimitate implica la possibilit` a di assegnare ad alcune variabili valori arbitrariamente grandi, mentre la rete dispone di una quantit` a b1 = −(b7 + b8 ) = 10 limitata di flusso da mettere in circolazione. La conservazione del flusso sembra quindi, intuitivamente, violata. Giustificare questo (apparente) paradosso. ESERCIZIO 6.4. Si consideri la particolare variante del problema del flusso a costo minimo dove bi = 0, ∀ i ∈ V : X cij xij min (i,j)∈A. soggetto a X. xij −. xji = 0. ∀i ∈ A,. (II). j : (j,i)∈A. j : (i,j)∈A. xij ≥ 0,. X. ∀(i, j) ∈ A.. Dire se e quando il modello (II) possiede soluzioni ammissibili non nulle (suggerimento: considerare un flusso ∆ > 0 instradato lungo un circuito, se il grafo ne possiede uno. . . ). ESERCIZIO 6.5. Discutere la forma della regione di ammissibilit` a del modello. di flusso a costo minimo: quando è un politopo (o poliedro) convesso? E quando è un poliedro illimitato (troncone)? ESERCIZIO 6.6. Applicare sui grafi di Figura 6.2 la procedura per determinare una soluzione ammissibile di base iniziale.. Si consideri la procedura per la determinazione di una soluzione ammissibile di base iniziale nel problema del flusso a costo minimo. Dire quando la soluzione di base finale prodotta da questa procedura è degenere.. ESERCIZIO 6.7..

(29) 29. 8. 2 2 3. b1 = 5 1. 6. 2. 5. 1. 4. 3. 7. b7 = −7 9 7 2 2. 5. 8 b8 = −4. 4. 4 b4 = 6 (a) b2 = −1 2 2 b1 = 5 1. 4. 5 b5 = −1. 3 b3 = −1. b1 = 10 1. 6 b6 = −1 (c). 6 b6 = −10. 4. b8 = −5 1 8 8. 1 -3. 3. 4. 4. 5. 2 -5. 6 (e). b7 = −8 7. 3. 4 2. 3. 5. 1. 2. 7 b7 = −5. 2. -2 b1 = 8. 1. 4. 1 1. 4. 3. 4 b4 = −10. 3 5 b5 = 10. (d) b4 = 8 3 4. -2. 1. 4 3 1. b3 = 8 3 2 3. 1. 2 10. 2. 2. b1 = 12 1. 1. 7. 2 3. b2 = −10 2 7. 8. 3. 7. 6. 4 b4 = 6 (b) b4 = −1 4 2. 3. 2. b2 = −8 4 2 9 4 2 b1 = 10 1 1. 3 1. 5. 6 b6 = −10 (f ). Figura 6.1: Reti di flusso. I costi unitari di trasporto cij sono indicati sugli archi, i termini noti bi accanto ai nodi (si assume bi = 0 quando non indicato).. 3. 7 b7 = −6.

(30) 30. CAPITOLO 6. PROBLEMI DI FLUSSO A COSTO MINIMO. 2. b3 = −10 3 b1 = 10 1. 2. 5. 3. 4 b4 = −10. b1 = 10 1 4 (a). 5 (b). Figura 6.2: Reti di flusso (bi = 0 quando omesso)..

(31) Capitolo 7. Problema del massimo flusso Nel problema del massimo flusso sono dati un grafo orientato G(V, A) con capacit` a cij > 0 specificate per ogni arco (i, j) ∈ A, un nodo sorgente s ed un nodo destinazione d, e si richiede di determinare il massimo flusso che pu` o transitare sulla rete tra s e d rispettando le capacit` a degli archi. Il modello in Programmazione Lineare del problema è X max xsi i : (s,i)∈A. soggetto a X. xij −. j : (i,j)∈A. X. i ∈ V − {s, d},. xji = 0,. j : (j,i)∈A. xij ≤ cij , ∀(i, j) ∈ A xij ≥ 0, ∀(i, j) ∈ A. ESERCIZIO 7.1. Per ognuno dei grafi di Figura 7.1, determinare il massimo flusso tra la sorgente s e la destinazione d, partendo dal flusso iniziale indicato. Determinare anche un taglio di capacit` a minima. (a) xs1 = 3, x12 = 2, x13 = 1, x24 = 1, x26 = 1, x6d = 1, x43 = 1, x3d = 2 (tutte le altre xij = 0). (b)–(e) Flusso nullo.. Dire se e quando la regione di ammissibilit` a del problema del massimo flusso pu` o essere un poliedro illimitato (troncone).. ESERCIZIO 7.2.. ESERCIZIO 7.3. Si supponga di avere un problema di massimo flusso con capacit` a associate ai nodi anzichè agli archi; si suppone cioè che gli archi abbiano capacitr` a infinita, ma in ogni nodo i possa transitare al massimo una quantit` a ci di flusso. Proporre una procedura per risolvere tale problema. ` possiESERCIZIO 7.4. Scrivere il duale del problema del massimo flusso. E bile affermare che in ogni soluzione di base di tale duale le variabili assumeranno solo valori interi? Motivare la risposta.. 31.

(32) 32. CAPITOLO 7. PROBLEMA DEL MASSIMO FLUSSO. 2 1. 1 3 s. 7. 4. 1. 3. 2. 2. 3. 3. 1 4. 4. 2. 6. 6. 8. 1. 2. 2. 5. s. d. 4. 4 5. 1. 2 6 4. 5. 4. 8. 2 5. 2 (a). 1. 2. 4. 2. 3. 1 6. 4. 3. 2 s. 8. 10. 5. 4. 3. 2 (d). (c) 1 2 s. 2 9 3. 5. 9. 2 1 3. 4. 1. 5. d. 4. 6. 7. 2 1 8. 7 1. 4 6. 4. 2. 4. 3. 4. 1. 6. 8. 8 2. 3 2. 5. 1. 1. s. d. 2 4. (b) 4. 8 8. 8. d. 7. 6 (e). Figura 7.1: Reti di flusso con archi capacitati. ESERCIZIO 7.5. Si consideri il duale del problema del massimo flusso formato nell’esercizio precedente, con variabili ui (i ∈ V − {s, d}) e wij ((i, j) ∈ A). Verificare che, ad ogni taglio indotto da un insieme U ⊆ V (con s ∈ U ), é possibile associare una soluzione ammissibile duale, definita da ( ( 1, se i ∈ U , j ∈ / U, −1, se i ∈ U , wij = ui = 0, altrimenti. 0, se i ∈ / U,. d.

(33) Capitolo 8. Problema del trasporto. 8.1. Esercizi.. Nel problema del trasporto sono dati m “depositi” con disponibilit` a a 1 , a2 , . . . , am ed n “negozi” con domande b1 , b2 , . . . , bn . Inoltre per ogni “collegamento” deposito-negozio (i, j) è specificato un costo unitario di trasporto cij . Si richiede di determinare un piano di trasporto a costo minimo per rifornire i negozi rispettando le disponibilit` a dei depositi, cioè. min. m X n X. cij xij. i=1 j=1. soggetto a. n X. j=1 m X. xij = ai. i = 1, . . . , m, (IV). xij = bj. j = 1, . . . , n,. i=1. xij ≥ 0,. ∀ i = 1, . . . , m,. ∀j = 1, . . . , n.. Pn Pm Si assume i=1 ai = j=1 bj , eventualmente dopo l’applicazione della procedura di bilanciamento. Le tabelle seguenti riportano i costi di trasporto cij e, a margine, i valori di ai e bj . Risolvere i problemi di trasporto corrispondenti. ESERCIZIO 8.1.. 33.

(34) 34. CAPITOLO 8. PROBLEMA DEL TRASPORTO.. (applicare la procedura di bilanciamento quando necessario). 1 2 3 bj. 1 2 3 4 ai 8 5 8 9 90 4 6 10 4 50 2 11 4 3 60 80 60 30 50 (a). 1 2 3 ai 1 2 8 4 20 2 3 4 9 20 3 8 7 10 40 bj 20 30 20 (b). 1 2 3 bj. 1 2 3 4 ai 4 7 12 8 50 9 2 6 11 50 7 9 2 1 20 40 60 10 30 (c). 1 2 3 4 ai 1 5 8 15 9 50 2 7 4 2 2 60 3 4 2 3 1 20 bj 50 40 30 10 (d). 1 2 3 4 1 10 8 4 3 2 7 9 8 8 3 9 9 7 8 4 4 2 1 9 bj 50 50 60 40. ai 40 20 80 60. (e). 1 2 3 4 ai 1 10 7 2 15 150 2 4 8 9 8 50 3 2 3 4 6 50 bj 100 100 25 25 (f ). ESERCIZIO 8.2. Considerare il punto (f ) dell’esercizio precedente. Data una quantit` a 0 < δ ≤ 25, formulare il problema di trasporto con gli stessi costi ed i seguenti termini noti.. a1 = 150,. a2 = 50 + δ,. a3 = 50,. b1 = 100,. b2 = 100,. b3 = 25 + δ,. b4 = 25.. Confrontare le soluzioni ottime dei due problemi. Calcolare il costo totale per le due soluzioni ottime, confrontare e giustificare i risultati..

(35) Parte II. Soluzioni. 35.

(36)

(37) Capitolo 1. Programmazione lineare 1.1. (a) Per giungere alla forma canonica occorre: • invertire il segno della funzione obiettivo e passare ad un programma di massimo; • moltiplicare per −1 il primo vincolo; • sostituire il terzo vincolo con la coppia 2x1 + 4x3 ≤ 12,. −2x1 − 4x3 ≤ −12;. • trasformare la x3 libera mediante x3 = u − v,. u, v ≥ 0.. Quindi si ottiene − max −3x1 − 4x2 + 2u − 2v soggetto a − x1 − 2x2 + u − v. ≤ −5. 2x1 + 4u − 4v − 2x1 − 4u + 4v. ≤ 12 ≤ −12. x1 + x 2 + u − v. ≤ 15. x1 , x2 , u, v ≥ 0. (b) Sostituendo x3 con −y3 e x2 libera con u − v, u, v ≥ 0, e rimpiazzando il vincolo di uguaglianza con la coppia di disuguaglianze che esso induce si ottiene max 4x1 − u + v soggetto a x1 + u − v + y 3 − x1 − u + v − y 3. ≤8 ≤ −8. 3x1 − y3. ≤7. x1 , y3 , u, v ≥ 0. 37.

(38) 38. CAPITOLO 1. PROGRAMMAZIONE LINEARE. (c) Forma canonica: − max −8x1 + x2 + y3 soggetto a − x1 + y 3 ≤. −4. x2 + y 3 x1 − x 2. ≤7 ≤2. x1 , x2 , x3 ≥ 0. (d) Forma canonica: max 4x1 + y2 soggetto a x1 − 2y2. ≤2. 2x1 − 7y2. ≤8. − 2x1 + 7y2. ≤ −8. x1 , y2 ≥ 0. (e) Forma canonica: − max −4x1 − 5x2 + x3 − 2u + 2v soggetto a − x1 − x2 x2 + x 3. ≤ −4 ≤7. x3 − u + v x1 − u + v. ≤2 ≤ 12. − x1 + u − v. ≤ −12. x1 , x2 .x3 , u, v ≥ 0. (f ) Forma canonica: max 2x1 − 4y3 soggetto a x1 + u − v − y 3. ≤ 12. − x1 + u − v u − v − y3. ≤ −2 ≤4. x1 , u, v, y3 ≥ 0. 1.2. (a) In base alla definizione di forma canonica, è necessario effettuare le seguenti trasformazoni:.

(39) 39 • invertire il segno della funzione obiettivo e passare ad un programma di massimo; • sostituire la variabile libera x3 = u − v, dove u, v ≥ 0; • introdurre una variabile di surplus nel primo vincolo per scriverlo in forma di uguaglianza; • introdurre una variabile di slack nel terzo vincolo per scriverlo in forma di uguaglianza. Si ottiene quindi − max −3x1 − 4x2 + 2u − 2v soggetto a x1 + 2x2 − u + v − x4 2x1 + 4u − 4v. =5 = 12. x1 + x 2 + u − v + x 5. = 15. x1 , x2 , u, v, x4 , x5 ≥ 0. (b) Forma standard, con x4 variabile di slack: max 4x1 − u + v soggetto a x1 + u − v + y 3. =8. 3x1 − y3 + x4. =7. x1 , u, v, y3 , x4 ≥ 0. (c) Forma standard: − max −8x1 + x2 + y3 soggetto a x1 − y 3 − x 4. =4. x2 + y 3 + x 5 x1 − x 2 + x 6. =7 =2. x1 , . . . , x6 , y3 ≥ 0. (d) Forma standard: max 4x1 + y2 soggetto a x1 − 2y2 + x3. =2. 2x1 − 7y2. =8. x1 , y2 , x3 ≥ 0..

(40) 40. CAPITOLO 1. PROGRAMMAZIONE LINEARE. (e) Forma standard: − max −4x1 − 5x2 + x3 − 2u + 2v soggetto a x1 + x 2 − x 5. =4. x2 + x 3 + x 6 x3 − u + v + x 7. =7 =2. x1 − u + v. = 12. x1 , . . . , x7 , u, v ≥ 0. (f ) Forma standard: max 2x1 − 4y3 soggetto a x1 + u − v − y 3 + x 4. = 12. x1 − u + v − x 5 x2 − y 3 + x 6. =2 =4. x1 , x2 , x4 , x5 , x6 , y3 , u, v ≥ 0. 1.3. (a) Come prima cosa occorre sempre porre il problema in forma standard, quindi: max 3x1 + 2x2 − 5x3 soggetto a 4x1 − 2x2 + 2x3 + x4 2x1 + x2 + x3 + x5. =4 =1. x1 , . . . , x5 ≥ 0, dove sono state aggiunte le due variabili di slack x4 , x5 ≥ 0. La presenza di queste due variabili permette di ottenere una riformulazione immediata rispetto alla base B0 = {x4 , x5 }. max. z = 0 +3x1 +2x2 −5x3 x4 = 4 −4x1 +2x2 −2x3 x5 = 1 −2x1 −x2 −x3 x1 , . . . , x 5 ≥ 0 ,. corrispondente alla soluzione ammissibile di base x4 = 4, x5 = 1, x1 , x2 , x3 = 0. L’esame dei costi ridotti indica che questa soluzione non è ottima, in quanto γ1 , γ2 > 0. Si sceglie quindi x1 come variabile entrante (criterio del massimo costo ridotto) nella prossima base. La variabile uscente viene scelta in base al criterio βi β2 4 1 min − =− = min , , αi1 αi1 <0 4 2 α21.

(41) 41 quindi la variabile uscente è x5 (cardine=−2). La riformulazione rispetto alla nuova base B1 = B0 ∪ {x1 } − {x5 } = {x4 , x1 } si ottiene applicando l’operazione di cardine sull’elemento individuato. max. z= x4 = x1 =. 3 2. − 23 x5 + 12 x2 2 +2x5 +4x2 1 − 21 x5 − 21 x2 2 x1 , . . . , x5 ≥ 0,. − 13 2 x3 − 21 x3. poichè γ2 > 0, si effettua l’operazione di cardine sull’elemento 21 evidenziato — scelto con gli stessi, noti criteri — e si passa alla base B2 = B1 ∪ {x2 } − {x1 }. max. z = 2 −2x5 x4 = 6 −2x5 x2 = 1 −x5. −x1 −8x1 −2x1. −7x3 −4x3 −x3. Poiché γ5 , γ1 , γ3 ≤ 0, la soluzione ammissibile di base x2 = 1, x4 = 6, x1 , x3 , x5 = 0 risulta ottima, con valore di funzione obiettivo z = 2; essendo tutti i costi ridotti strettamente negativi, questa è anche l’unica soluzione ottima. (b) Riscrivendo il programma in forma standard si ottiene max x1 − 2x2 + 3x3 soggetto a x1 − 2x2 + x3 + x4 3x1 − x2 − 2x3 + x5. =2 =6. x1 , . . . , x5 ≥ 0, con x4 , x5 variabili di slack. La base iniziale — disponibile immediatamente — è B0 = {x4 , x5 }, corrispondente alla seguente riformulazione. max. z = 0 +x1 −2x2 x4 = 2 −x1 +2x2 x5 = 6 −3x1 +x2 x1 , . . . , x5 ≥ 0.. +3x3 −1x3 +2x3. Avendo γ1 , γ3 > 0, si identifica l’elemento cardine evidenziato, che corrisponde al cambio di base B1 = B0 ∪ {x3 } − {x4 }, cioè alla riformulazione max. z = 6 −2x1 +4x2 x3 = 2 −x1 +2x2 x5 = 10 −5x1 +5x2 x1 , . . . , x5 ≥ 0.. −3x4 −x4 −2x4. A questo punto, avendo γ2 > 0 ma nessun coefficiente negativo nella colonna corrispondente, si conclude che il problema è illimitato (e quindi Sot = ∅) e non si procede oltre. Si pu` o infatti osservare che lungo la semiretta x3 = 2 + 2x2 x5 = 10 + 5x2 x2 = t. t ∈ [0, +∞).

(42) 42. CAPITOLO 1. PROGRAMMAZIONE LINEARE. si trovano soluzioni con z → +∞ per t → +∞. (c) Base ottima Bot = {x1 , x3 } con x1 = 23 , x3 = 34 , z = (d) Ricavata la forma standard. 16 3 .. − max −3x1 − x2 + 2x3 + x4 soggetto a 2x1 + x2 − x3 + 3x4 + x5 − x1 + 2x2 − 2x3 + 2x4 + x6. =8 =4. x1 + x 3 + x 7. = 10. x1 , . . . , x7 ≥ 0, con x5 , x6 , x7 variabili di slack, l’applicazione del simplesso porta a determinare la base ottima Bot = {x4 , x6 , x3 }, x3 = 10, x4 = 6, x6 = 12. (e) Il programma in forma standard risulta max x1 + 3x2 − x3 soggetto a 2x1 + x2 + x4. =3. x1 + x2 + 3x3 + x5 2x1 + x2 + 3x3 + x6. =6 =8. x1 , . . . , x6 ≥ 0, con x4 , x5 , x6 variabili di slack. L’applicazione del simplesso porta a determinare la base ottima Bot = {x2 , x5 , x6 } con x2 = 3, x5 = 3, x6 = 5. (f ) Dalla forma standard max 4x1 + x2 + 5x3 soggetto a − x1 + x2 + x4. =1. 2x2 − x3 + x5 x1 + x 3 + x 6. =2 =1. x1 , . . . , x6 ≥ 0, (x4 , x5 , x6 variabili di slack) si perviene tramite l’applicazione del simplesso alla base ottima Bot = {x2 , x5 , x3 }, con x2 = x3 = x5 = 1. 1.4. (a) Il programma in forma standard è − max −6x1 − x2 − 3x3 soggetto a 10x1 − 2x2 + 5x3 − x4. = 15. x1 − x2 + 3x3 − x5. =6. x1 , . . . , x5 ≥ 0..

(43) 43 Le colonne di x4 , x5 risultano linearmente indipendenti, (e quindi {x4 , x5 } è una base) ma si verifica facilmente che non corrispondono ad una soluzione ammissibile di base. Occorre quindi procedere alla soluzione del problema di prima fase, formulato come segue. max −s1 − s2 soggetto a 10x1 − 2x2 + 5x3 − x4 + s1. = 15. x1 − x2 + 3x3 − x5 + s2. =6. x1 , . . . , x5 ≥ 0. Le variabili s1 , s2 sono anche dette artificiali in quanto non appartengono al programma originale. La riformulazione associata alla base iniziale B0 = {s1 , s2 } è max. z = −21 +11x1 −3x2 +8x3 s1 = 15 −10x1 +2x2 −5x3 s2 = 6 −x1 +x2 −3x3 x1 , . . . , x5 , s1 , s2 ≥ 0.. −x4 +x4. −x5 +x5. Nota: nella riformulazione sono state eliminate, come dovuto, le variabili in base s1 , s2 dall’espressione della funzione obiettivo z = −s1 − s2 , per sostituzione dalle relazioni vincolari. Procedendo ora normalmente, risulta B1 = B0 ∪ {x1 } − {s1 }, e quindi max. 11 z = − 29 − 10 s1 − 54 x2 + 25 x3 1 3 − 10 s1 + 51 x2 − 21 x3 x1 = 2 9 1 4 s2 = − 52 x3 2 10 s1 + 5 x2 x1 , . . . , x5 , s1 , s2 ≥ 0.. 1 + 10 x4 1 + 10 x4 1 − 10 x4. −x5 +x5. con il cardine selezionato si effettua quindi il cambio di base B2 = B1 ∪ {x3 } − {s2 }. max. z= x1 = x3 =. −s1 −s2 3 1 − 25 s1 + 25 x2 + 51 s2 1 8 + 25 s1 + 25 x2 − 52 s2 x1 , . . . , x5 , s1 , s2 ≥ 0. 0. 3 5 9 5. 3 + 25 x4 1 − 25 x4. − 51 x5 + 52 x5. Poiché la prima fase è terminata con z = 0, si conclude che il programma lineare iniziale ammette soluzioni ammissibili. La base B2 = {x1 , x5 } ottenuta non contiene variabili artificiali e pu` o essere utilizzata come punto di partenza per l’applicazione del simplesso al programma iniziale. Si possono quindi eliminare s1 , s2 e le colonne associate e scrivere la riformulazione − max. z = −9 − 11 − 53 x4 5 x2 1 3 3 + 25 x2 + 25 x4 − 51 x5 x1 = 5 9 8 1 x3 = + 25 x2 − 25 x4 + 52 x5 5 x1 , . . . , x5 , s1 , s2 ≥ 0..

(44) 44. CAPITOLO 1. PROGRAMMAZIONE LINEARE. Come sopra, nella funzione obiettivo si è provveduto ad eliminare le variabili in base, sostituendo in essa le relazioni vincolari. Non si procede oltre in quanto γ2 , γ4 , γ5 ≤ 0, e quindi la base corrente è gi` a ottima. Nota: la funzione obiettivo originale e quella artificiale sono completamente scorrelate, quindi la prima fase non d` a in generale alcuna garanzia di ottimalit` a sulla soluzione ammissibile trovata, che potrebbe essere anche molto lontana dall’ottimo. (b) Il problema in forma standard risulta − max −7x1 − 2x2 + 5x3 + x4 soggetto a 4x1 + 3x2 + 2x4 − x5. =2. − 5x1 − 3x2 + x3 − x4 + x6. =1. x1 , . . . , x6 ≥ 0, con x5 variabile di surplus e x6 variabile di slack. Non avendo una base ammissibile immediatamente disponibile, occorre risolvere il problema di prima fase max −s1 soggetto a 4x1 + 3x2 + 2x4 − x5 + s1. =2. − 5x1 − 3x2 + x3 − x4 + x6. =1. x1 , . . . , x6 , s1 ≥ 0. In questo caso solo una variabile artificiale s1 è strettamente necessaria, in quanto si vede che B0 = {s1 , x6 } forma gi` a una base ammissibile. Procedendo si ottiene max. z = −2 +4x1 +3x2 s1 = 2 −4x1 −3x2 x6 = 1 +5x1 +3x2 x1 , . . . , x6 , s1 ≥ 0.. −x3. +2x4 −2x4 +x4. −x5 +x5. Facendo cardine sul coefficiente −4 si ottiene B1 = B0 ∪ {x1 } − {s1 }, e quindi max. z= x1 = x6 =. −s1 − 41 s1 − 43 x2 − 45 s1 − 43 x2 −x3 x1 , . . . , x6 , s1 ≥ 0. 0. 1 2 7 2. − 12 x4 − 32 x4. + 41 x5 + 45 x5. Poiché z = 0 nella prima fase, si pu` o passare alla riformulazione rispetto a B 1 del programma iniziale ed applicare il simplesso. − max. z = − 72 + 13 +5x3 4 x2 3 1 − 4 x2 x1 = 2 7 x6 = − 43 x2 −1x3 2 x1 , . . . , x6 ≥ 0.. + 92 x4 − 12 x4 − 32 x4. − 47 x5 + 41 x5 + 45 x5.

(45) 45 Facendo cardine sul −1 si cambia B2 = B1 ∪ {x6 } − {x3 }, ottenendo − max. z = 14 − 21 x2 −5x6 x1 = 12 − 43 x2 x3 = 72 − 43 x2 −x6 x1 , . . . , x6 ≥ 0.. −3x4 − 12 x4 − 23 x4. + 29 x5 + 14 x5 + 54 x5. A questo punto sulla colonna di x5 si riconosce la condizione di illimitatezza e non si procede oltre. Lungo la semiretta 1 1 + x5 2 4 7 5 x3 = + x5 2 4 x5 = t x1 =. t ∈ [0, +∞]. si trovano soluzioni con z → +∞ per t → +∞. (c) La forma standard è − max −2x1 − x2 − 4x3 soggetto a x1 + x2 + 2x3. =3. 2x1 + x2 + 3x3. =5. x1 , x2 , x3 ≥ 0. Il problema di prima fase risulta max −s1 − s2 soggetto a x1 + x2 + 2x3 + s1. =3. 2x1 + x2 + 3x3 + s2. =5. x1 , x2 , x3 , s1 , s2 ≥ 0. Risolvendo il problema di prima fase si trova la base ammissibile B = {x3 , x1 }, e da qui la base ottima Bot = {x2 , x1 } (x2 = 1, x1 = 2). (d) Il programma in forma standard è (aggiungendo una variabile di slack x5 ≥ 0) max x1 + x2 + x3 soggetto a − x1 − 2x2 + x3 + x4 4x2 + x3 + 2x4. =5 =2. 3x2 − 2x4 + x5. =6. x1 , . . . , x5 ≥ 0,.

(46) 46. CAPITOLO 1. PROGRAMMAZIONE LINEARE. ed il relativo problema di prima fase risulta come segue. max −s1 − s2 soggetto a − x1 − 2x2 + x3 + x4 4x2 + x3 + 2x4 + s2. + s1 = 5 =2. 3x2 − 2x4 + x5. =6. x1 , . . . , x5 , s1 , s2 ≥ 0. Partendo dalla base B0 = {s1 , s2 , x5 } (s1 = 5, s2 = 2, x5 = 6) si ottiene quanto segue. max. z s1 s2 x5. = −7 −x1 −6x2 +2x3 = 5 +x1 +2x2 −x3 = 2 −4x2 −x3 = 6 −3x2 x1 , . . . , x5 , s1 , s2 ≥ 0;. +3x4 −x4 −2x4 +2x4. B1 = B0 ∪ {x4 } − {s2 }, max. z s1 x4 x5. = −4 −x1 + 21 x3 = 4 +x1 +4x2 − 21 x3 = 1 −2x2 − 21 x3 = 8 −7x2 −x3 x1 , . . . , x5 , s1 , s2 ≥ 0;. − 23 s2 + 21 s2 − 21 s2 −s2. B2 = B1 ∪ {x3 } − {x4 }, max. z s1 x3 x5. = −3 −x1 −2x2 −x4 = 3 +x1 +6x2 +x4 = 2 −4x2 −2x4 = 6 −3x2 +2x4 x1 , . . . , x5 , s1 , s2 ≥ 0.. −2s2 +s2 −s2. Il problema di prima fase è stato risolto all’ottimo, con valore di funzione obiettivo non nullo, quindi per il programma lineare iniziale non esiste soluzione ammissibile. (e) La forma standard del programma è max 4x1 + 3x2 − x3 + 2x4 soggetto a − x1 + 2x2 + x3 − x4 − x5 − 2x1 + x2 − x3 + 5x4 − x6. =2 =3. x1 , . . . , x6 ≥ 0. Dal problema di prima fase si ottiene la base ammissibile B = {x2 , x4 }, e successivamente, applicando il simplesso alla riformulazione del programma iniziale rispetto a B, si verifica che questo è illimitato. (f ) Non esiste soluzione ammissibile..

(47) 47 1.5. (a) Dalla riformulazione rispetto alla base finale {x4 , x2 } si hanno le relazioni x4 = 6 −2x5 x2 = 1 −x5. −4x3 , −x3 .. +8x1 −2x1. Utilizzando queste relazioni per eliminare le variabili in base dall’obiettivo z = 7x1 + x2 + 4x3 si riformula quest’ultimo come max z = 1 −x5. +5x1. −x3 ,. dove il costo ridotto γ1 > 0 indica che la base {x2 , x4 } non è ottima. (b) Tenendo presente che min 4x1 + 5x2 − x3 equivale a max −4x1 − 5x2 + x3 nella forma standard, riformulando rispetto alla base finale {x3 , x5 } si ottiene max. z = 2 −5x1 x3 = 2 −x1 x5 = 10 −5x1. −3x2 +2x2 +5x2. −x4 −x4 −2x4 .. I costi ridotti γ1 , γ2 , γ4 ≤ 0 indicano che la base {x3 , x5 } è ottima per il nuovo obiettivo. (c) Non ottima. (d) Ottima. (e) Ottima. (f ) Non ottima. 1.6. (a) La A−1 B si legge nella riformulazione finale, sotto le colonne che nella formulazione iniziale rappresentavano la matrice identit` a. Quindi, riscrivendo il sistema finale: max z =. 2 −x1 6 = −8x1 1= 2x1. +x2. −7x3 +4x3 +x3. +x4. +2x5 +x5 .. La matrice identit` a appariva, nella riformulazione iniziale, sotto le colonne di x4 , x5 , quindi 1 2 . A−1 = B 0 1 (b) Analogamente, riscrivendo la riformulazione finale si ha max z =. 6 −2x1 2= x1 10 = 5x1. +4x2 −2x2 −5x2. +x3. −3x4 +x4 +2x4. +x5. e risulta, tenendo conto che sotto x4 , x5 appariva la matrice identit` a, A−1 B (c). A−1 B. =. = . 4 3. 1 0 . 2 1. − 31. − 16 1 6. . ..

(48) 48. CAPITOLO 1. PROGRAMMAZIONE LINEARE . 1 3. − 2 (d) A−1 B = 3 0  1 −1 (e) AB = −1 −1  1 −2 (f ) A−1 = B 0. 0 1 0 0 1 0 0 1 0. 1 3 4 3 .. . 1  0 0. 1  0 1. 1. 1.7. La Figura 3.1 illustra le regioni Sa per i programmi lineari in esame. Si possono fare le seguenti considerazioni. (a) Il punto (x1 = 6, x2 = 1) è il punto di Sa pi` u lontano dalla retta z = 0, quindi è l’unica soluzione ottima. u vicino alla retta z = 0. (b) Il punto (x1 = 2, x2 = 32 ) è il punto di Sa pi` (c) Lungo la semiretta x1 ≥ 8, x2 = 0 che appartiene ad Sa si pu` o osservare che si trovano punti con valore di funzione obiettivo grande a piacere, quindi il problema è illimitato. (d) Il punto (x1 = 1, x2 = 2) è a distanza massima dalla retta z = 0, e con esso tutti i punti del segmento che lo congiunge a (x1 = 8, x2 = 41 )..

(49) 49. x2. 16 B( 26 9 , 9 ). A( 25 , 1). C(6, 1). Sa. x1 (a) x2. Sa. B(2, 23 ) x1 (b) − (c) x2. A(1, 2) Sa B(8, 41 ) x1 (d) Figura 1.1: Regioni di ammissibilit` a per l’esercizio 1.7..

(50) 50. CAPITOLO 1. PROGRAMMAZIONE LINEARE.

(51) Capitolo 2. Dualita 2.1. Riferendosi alle forme standard ottenute per l’esercizio 1.3 si ottengono i seguenti programmi duali. min 4u1 + u2 soggetto a 4u1 + 2u2. ≥3. − 2u1 + u2. ≥2. 2u1 + u2. ≥ −5. (a). u1 , u2 ≥ 0. min 2u1 + 6u2 soggetto a u1 + 3u2 − 2u1 − 2u2. ≥1 ≥ −2. u1 − 2u2. ≥3. (b). u1 , u2 ≥ 0. Nota: sommando il secondo e terzo vincolo, si ottiene −u1 − 4u2 ≥ 1, che è incompatibile con i vincoli u1 , u2 ≥ 0. Quindi il programma duale (b) non ha soluzione ammissibile. Questo è coerente con quanto ricavato per il primale nell’esercizio 1.3 (programma illimitato). min 2u1 + 12u2 soggetto a u1 + 2u2 u1 + 3u2. ≥2 ≥1. u1 + 8u2. ≥3. (c). u1 , u2 ≥ 0 min 8u1 + 4u2 + 10u3 51.

(52) 52. CAPITOLO 2. DUALITA. soggetto a 2u1 − u2 + u3 u1 + 2u2. ≥ −3 ≥ −1. − u1 − 2u2 + u3 3u1 + 2u2. ≥2 ≥1. (d). u1 , u2 , u3 ≥ 0. min 3u1 + 6u2 + 8u3 soggetto a 2u1 + u2 + 2u3 u1 + u 2 + u 3. ≥1 ≥3. 3u2 + 3u3. ≥ −1. (e). u1 , u2 , u3 ≥ 0. min u1 + 2u2 + u3 soggetto a − u1 + u3. ≥4. u1 + 2u2 − u2 + u3. ≥1 ≥5. (f ). u1 , u2 , u3 ≥ 0. 2.2. Partendo dalle forme standard ricavate per l’esercizio 1.4 si ottengono i seguenti programmi duali. min 15u1 + 6u2 soggetto a 10u1 + u2. ≥ −6. − 2u1 − u2 5u1 + 3u2. ≥ −1 ≥ −3. (a). u1 , u2 ≤ 0. min 2u1 + u2 soggetto a 4u1 − 5u2. ≥ −7. 3u1 − 3u2. ≥ −2. u2 2u1 − u2. ≥5 ≥1. u1 ≤ 0, u2 ≥ 0. min 3u1 + 5u2. (b).

(53) 53 soggetto a u1 + 2u2 u1 + u 2. ≥ −2 ≥ −1. 2u1 + 3u2. ≥ −4. (c). min 5u1 + 2u2 + 6u3 soggetto a − u1. ≥1. − 2u1 + 4u2 + 3u3 u1 + u 2. ≥1 ≥1. u1 + 2u2 − 2u3. ≥0. (d). u3 ≥ 0 min 2u1 + 3u2 soggetto a − u1 − 2u2 2u1 + u2. ≥4 ≥3. u1 − u 2 − u1 + 5u2. ≥ −1 ≥2. (e). u1 , u2 ≤ 0. min 2u1 + 5u2 + 4u3 soggetto a 2u1 + 3u2 + u3. ≥ −1. u1 + u2 + 2u3 u1 + 2u2 + u3. ≥ −1 ≥2. (f ). 2.3. (a) Formando il duale del programma perturbato max cx soggetto a Ax = b + θ x ≥ 0, si ottiene min u(b + θ). (P0 ).

(54) 54. CAPITOLO 2. DUALITA. soggetto a uT A ≥ c.. (D0 ). Si noti che l’insieme delle soluzioni ammissibili duali Da = {u : uA ≥ c} è lo stesso, sia per (D) che per (D0 ). Se (P0 ) fosse illimitato, (D0 ) non dovrebbe avere soluzioni ammissibili, e quindi Da = ∅ anche per (D0 ). Ma è impossibile, in quanto (P) ha soluzione ottima finita, e quindi il suo duale (D) deve avere regione di ammissibilit` a non vuota (vedi Osservazione 14, sugli appunti). Quindi (P0 ) non pu` o essere illimitato. (b) Il duale del problema perturbato questa volta è min ub soggetto a uA ≥ c + θ.. (D00 ). Considerando una qualunque soluzione ammissibile u di (D), risulta uA ≥ c ≥ c + θ. (θ ≤ 0).. Quindi u è ammissibile anche per (D00 ), e questo impedisce che il primale perturbato sia illimitato. (c) Si pu` o osservare che ponendo ui =. max{c1 , . . . , cn } min{aij , i = 1, . . . , n, j = 1, . . . , m}. si ottiene un u che soddisfa uA ≥ c, e quindi una soluzione ammissibile duale. Quindi (P) non pu` o essere illimitato. 2.4. Considerando il prodotto (¯ uA − c)¯ x=. n X. [(¯ uaj − cj )¯ xj ]. j=1. per ogni termine (¯ uaj − cj )¯ xj risulta che: • se u ¯aj − cj > 0 allora x¯j = 0 per come è definito (PR); • se x ¯j > 0, allora deve essere (¯ uaj − cj ) = 0, sempre per come è stato definito (PR). Queste condizioni garantiscono che (¯ uA − c)¯ x = 0, quindi x ¯eu ¯ rispettano le condizioni di complementariet` a, e sono soluzioni ottime per (P) e (D) rispettivamente..

(55) 55 2.5. (a) Come sempre, occorre riportare il programma alla sua forma standard, che risulta, con x4 , x5 variabili di surplus: max −3x1 − x2 − 3x3 soggetto a x1 + x 2 − x 4. =4. 2x1 + x2 − x3 − x5. =8. x1 , . . . , x5 ≥ 0. ` possibile considerare la riformulazione rispetto alla base B0 = {x4 , x5 }, che E sebbene non risulti ammissibile, risulta ammissibile per il duale. max. z= 0 −3x1 −x2 −3x3 x4 = −4 +x1 +x2 x5 = −8 +2x1 +1x2 −x3 x1 , . . . , x 5 ≥ 0. In queste condizioni è possibile applicare il metodo del simplesso duale. In primo luogo si sceglie la variabile da portare fuori base: questa deve essere sempre una variabile che crea inammissibilit` a (cioè < 0). In questo caso, si pu` o scegliere arbitrariamente x5 . La scelta dell’elemento cardine (e quindi della variabile entrante) avviene in base al criterio 3 γ2 γi = min ,1 = − . min − α2i α2i >0 2 α22 Eseguendo quindi la solita operazione di cardine sull’elemento selezionato, si effettua il cambio di base B1 = B0 − {x5 } ∪ {x2 }, ottenendo max. z = −8 −x1 −x5 −4x3 x4 = 4 −x1 +x5 +x3 x2 = 8 −2x1 +x5 +x3 x1 , . . . , x 5 ≥ 0 .. La base cos`ı ottenuta risulta ottima, in quanto γ1 , γ5 , γ3 ≤ 0 e x2 , x4 ≥ 0 (base ammissibile ed ottima). (b) La forma standard, che usa variabili di surplus x4 , x5 ed una variabile di slack x6 rislta max −2x1 − 3x2 − x3 soggetto a x1 + x 2 − x 3 − x 4 2x1 + x3 − x5. =6 =4. x1 + x2 − 2x3 + x6. =2. x1 , . . . , x6 ≥ 0..

(56) 56. CAPITOLO 2. DUALITA. Applicando il metodo del simplesso duale a partire dalla base ammissibile per il duale e non ammissibile per il primale B0 = {x4 , x5 , x6 } risulta quanto segue. max. z x4 x5 x6. = 0 −2x1 −3x2 −x3 = −6 +1x1 +x2 −x3 = −4 +2x1 +x3 = 2 −x1 −x2 +2x3 x1 , . . . , x6 ≥ 0,. B1 = B0 ∪ {x1 } − {x4 } max. z x1 x5 x6. = −12 −2x4 −x2 −3x3 = 6 +x4 −x2 +x3 = 8 +2x4 −2x2 +3x3 = −4 −x4 +1x3 x1 , . . . , x6 ≥ 0,. B2 = B1 ∪ {x3 } − {x6 } max. z x1 x5 x3. = −24 −5x4 −x2 −3x6 = 10 +2x4 −x2 +x6 = 20 +5x4 −2x2 +3x6 = 4 +x4 +x6 x1 , . . . , x6 ≥ 0,. con B2 ottima ed ammissibile. ` possibile procedere nel seguente modo. Si considera la riformulazione del 2.6. E programma rispetto alla base ottima trovata in precedenza max. z = −8 −x1 −x5 −4x3 x4 = 4 −x1 +x5 +x3 x2 = 8 −2x1 +x5 +x3 x1 , . . . , x 5 ≥ 0 .. A questo punto si introduce il nuovo vincolo x1 +2x3 ≥ 1 direttamente nella formulazione, procedendo come segue: si scrive il vincolo in forma di uguaglianza, introducendo una nuova variabile di surplus s: x1 + 2x3 − s = 1, e si eliminano se necessario le variabili in base x4 , x2 ; la variabile s viene portata nella base, che diventa B = {x4 , x2 , s}. max. z = −8 −x1 −x5 −4x3 x4 = 4 −x1 +x5 +x3 x2 = 8 −2x1 +x5 +x3 s = −1 +1x1 +2x3 x1 , . . . , x 5 ≥ 0 .. Si nota che il nuovo vincolo causa inammissibilit` a (s < 0 in base), ma non si perde ammissibilit` a duale. Quindi, anziché ricominciare da capo si pu` o.

(57) 57 procedere con il simplesso duale: max. z x4 x2 x1. = −9 −s −x5 −2x3 = 3 −s +x5 +3x3 = 6 −2s +x5 +5x3 = 1 +s −2x3 x1 , . . . , x 5 ≥ 0 ,. trovando la base {x4 , x2 , x1 } ammissibile ed ottima. 2.7. Si procede in modo analogo all’esercizio precedente: si considera la formulazione finale max. z x1 x5 x3. = −24 −5x4 −x2 −3x6 = 10 +2x4 −x2 +x6 = 20 +5x4 −2x2 +3x6 = 4 +x4 +x6 x1 , . . . , x6 ≥ 0;. il nuovo vincolo si scrive come x1 + x 2 + s = 5 ed eliminando la x1 e portando in base s si ottiene max. z = −24 −5x4 −x2 −3x6 x1 = 10 +2x4 −x2 +x6 x5 = 20 +5x4 −2x2 +3x6 x3 = 4 +x4 +x6 s = −5 −2x4 −x6 x1 , . . . , x6 ≥ 0.. Infine, avendo β4 = −5 < 0, costi ridotti ≤ 0 e nessun coefficiente positivo sulla riga di s si conclude che il duale è illimitato, cioè il primale non possiede pi` u soluzione ammissibili. 2.8. (a) I vincoli del duale sono associati alle variabili del primale; le condizioni di complementariet` a primale-duale si scrivono come (uA − c)x = 0, quindi per j = 1, . . . , n xj > 0. implica. uaj = cj ,. dove uaj ≥ cj è il vincolo duale corrispondente. In questo caso il duale è min 4u1 + u2 soggetto a 4u1 + 2u2. ≥3. (x1 ). − 2u1 + u2 2u1 + u2. ≥2 ≥ −5. (x2 ) (x3 ). u1 u2. ≥0 ≥0. (x4 ) (x5 ).

(58) 58. CAPITOLO 2. DUALITA. e quindi data la base ottima {x2 , x4 } si pu` o impostare il sistema − 2u1 + u2. =2. u1. =0. =⇒ u1 = 0, u2 = 2.. (b) Il duale non è ammissibile, come gi` a verificato. u1 + 2u2 u1 + 8u2. (c). − u1 − 2u2 + u3 (d). 3u1 + 2u2 u2. (e). u1 + u 2 + u 3 u2. 2.9. (a). =2. 7 1 = 1 =⇒ u1 = , u2 = 0, u3 = . 3 3 =0. =3 = 0 =⇒ u1 = 3, u2 = 0, u3 = 0. =0. u3. (f ). =2 10 1 =⇒ u1 = , u2 = . 6 6 =3. u1 + 2u2. =1. − u2 + u3 u2. = 5 =⇒ u1 = 1, u2 = 0, u3 = 5. =0. 10u1 + u2 5u1 + 3u2. = −6 3 =⇒ u1 = , u2 = 0. 5 = −3. (b) Il duale non ha soluzioni ammissibili. (c). u1 + 2u2 u1 + u 2. = −2 =⇒ u1 = 0, u2 = −1. = −1. (d) Poiché il primale non ha soluzioni ammissibili, il duale pu` o essere illimitato o avere regione ammissibile vuota. (e) Non esiste soluzione ammissibile perché il primale è illimitato. (f ) Il duale è illimitato o ha regione ammissibile vuota in quanto il primale non ha soluzioni ammissibili. 2.10. max 15u1 + 6u2 soggetto a 10u1 + u2 − 2u1 − u2. ≤6 ≤1. 5u1 + 3u2 u1 , u2 ≥ 0.. ≤3. max 2u1 + u2. (a).

(59) 59 soggetto a 4u1 − 5u2 3u1 − 3u2. ≤7 ≤2. u2 2u1 − u2. ≤ −5 ≤1. (b). u1 ≥ 0, u2 ≤ 0. max 3u1 + 5u2 soggetto a u1 + 2u2. ≤2. u1 + u 2 2u1 + 3u2. ≤1 ≤4. (c). min 5u1 + 3u2 + 6u3 soggetto a − u1. ≥1. − 2u1 + 4u2 + 3u3 u1 + u 2. ≥1 ≥1. u1 + 2u2 − 2u3 u3. ≥0 ≥ 0.. (d). min 2u1 − 3u2 soggetto a − u1 + 2u2. ≥4. 2u1 − u2 u1 + u 2. ≥3 ≥ −1. − u1 − 5u2. ≥2. (e). u1 ≤ 0, u2 ≥ 0. max 2u1 + 5u2 + 4u3 soggetto a 2u1 + 3u2 + u3 u1 + u2 + 2u3. ≤1 ≤1. u1 + 2u2 + u3. ≤ −2. (f ).

(60) 60. CAPITOLO 2. DUALITA.

(61) Capitolo 3. Analisi di sensitivita 3.1. (a) Perturbando il termine noto b2 della quantit` a ∆b2 = −8 si ottiene il nuovo vettore dei termini noti x2 ¯b = 2 , ¯b = 4 = A−1 da cui B −1 x5 −3 non ammissibile (richiede x5 < 0). Nota: ¯b2 = −3 non implica la perdita di ammissibilit` a, in quanto il problema pu` o facilmente essere riportato ad una forma standard cambiando segno al secondo vincolo; l’ammissibilit` a si valuta ¯ sempre su A−1 B b ≥ 0. Perturbando c3 (x3 ∈ / Bot ) con un ∆c3 = 1 i costi ridotti si ottengono sommando il contributo ∆c3 della variazione al costo ridotto fuori base; la funzione obiettivo riformulata rispetto a Bot sotto questa perturbazione è max z = −8 − x1 + x3 − 2x4 , quindi la perturbazione causa perdita di ottimalit` a. Perturbando c5 con ∆c5 = − 51 (x5 ∈ Bot ), sommando il contributo 5 1 1 ∆c5 x5 = 7∆c5 − ∆c5 x1 + ∆c5 x3 + ∆c5 x4 2 2 2. (∆c5 =. 1 ) 5. la funzione obiettivo riformulata risulta max z = −. 1 21 47 1 − x1 − x3 − x4 , 5 2 10 10. senza perdita di ottimalit` a (γ1 , γ3 , γ4 ≤ 0); si pu` o osservare che la perturbazione causa una variazione della funzione obiettivo pari a ∆z = ∆c5 x∗5 = − 75 . (b) La perturbazione di b3 non causa perdita di ammissibilit` a; si pu` o osservare che, poiché la soluzione ottima del duale non cambia, dal valore delle variabili duali   1 0 0 2   0 0  = 4 −2 3 u∗ = u∗1 u∗2 u∗3 = cB A−1 B = 4 0 2 1 2 −1 12 61.

(62) 62. CAPITOLO 3. ANALISI DI SENSITIVITA. si pu` o dedurre che la perturbazione ∆b3 = −1 induce una variazione nel valore della funzione obiettivo ∆z = u∗3 ∆b3 = −3. Le perturbazioni di c2 e c4 non causano perdita di ottimalit` a; le variazioni nel valore di funzione obiettivo sono rispettivamente ∆z = 0 per c2 e ∆z = c4 x∗4 = −9. (c) La perturbazione di b2 causa perdita di ammissibilit` a; la perturbazione di c1 non causa perdita di ottimalit` a (e ∆z = 0), mentre la perturbazione di c2 causa perdita di ottimalit` a. (d) La perturbazione di b2 non causa perdita di ammissibilit` a (risulta inoltre ∆z = 0 in quanto si verifica u∗2 = 0); la perturbazione di c2 causa perdita di ottimalit` a, mentre la perturbazione di c1 no (e risulta ∆z = − 22 5 ). (e) La perturbazione di b1 causa perdita di ammissibilit` a; la perturbazione di c1 non causa perdita di ottimalit` a e non cambia il valore ottimo, mentre quella di c4 causa perdita di ottimalit` a. (f ) La perturbazione di b2 non causa perdita di ammissibilit` a (risulta inoltre a ∆z = u∗2 ∆b2 = − 75 ); la perturbazione di c1 non causa perdita di ottimalit` ), mentre la perturbazione di c non causa perdita di (risulta ∆z = ∆c1 x∗1 = 15 2 7 ottimalit` a ed il valore dell’ottimo non cambia. 3.2. (a) La perturbazione di un termine noto compromette l’ammissibilit` a della ¯ base B = {x2 , x5 } se la condizione A−1 B b ≥ 0 cessa di valere per il vettore perturbato ¯b = b + ∆b. Quindi, se il termine noto b1 viene perturbato di una quantit` a (incognita) ∆b1 , l’insieme di valori di ∆b1 che non compromettono l’ammissibilit` a della base è definito dalle disuguaglianze A−1 B (b + ∆b) ≥ 0. =⇒. −1 A−1 B ∆b ≥ −AB b. e, nel caso di b1 , 1. 0 4 + ∆b1 ≥ 0, 5 1. 1. 0 −2 ∆b1 ≥ . 0 −7 1. 2 1 2. cioè 2 1 2. Considerando le componenti, si scrive il sistema lineare 1 ∆b1 ≥ −2 2 1 ∆b2 ≥ −7 2. =⇒. −4 ≤ ∆b1 ≤ +∞.. Analogamente, per il termine noto b2 si impostano le condizioni 1 0 0 −2 2 ≥ , 1 ∆b −7 1 2 2.

(63) 63 cioè 0 ≥ −2 ∆b2 ≥ −7. =⇒. −7 ≤ ∆b2 ≤ +∞.. Per quanto riguarda i coefficienti di costo della funzione obiettivo, si procede in modo analogo, ricordando che la base B è ancora ottima rispetto ad un vettore di costi perturbato c¯ = c + ∆c se c¯N − c¯B A−1 B N ≤ 0 (costi ridotti non positivi). Nel caso di c1 (x1 ∈ / Bot ) la variazione ∆c1 si ripercuote direttamente sul costo ridotto γ1 , trasformando la funzione obiettivo riformulata in max z = −8 + (∆c1 − 1)x1 − 2x4 , e per l’ottimalit` a occorre avere ∆c1 − 1 ≤ 0. =⇒. −∞ ≤ ∆c1 ≤ 1.. Perturbando il coefficiente c2 (x2 ∈ Bot ) con un ∆c2 e sommando il contributo 1 1 1 ∆c2 x2 = 2∆c2 − ∆c2 x1 + ∆c2 x3 + ∆c2 x4 2 2 2 la funzione obiettivo riformulata diventa 1 1 1 max (2∆c2 − 8) − (1 + ∆c2 )x1 + ∆c2 x3 + ( ∆c2 − 2)x4 , 2 2 2 e, per conservare le condizioni di ottimalit` a, la ∆c2 deve soddisfare le condizioni 1 − ∆c2 − 1 2 1 δc2 2 1 ∆c2 − 2 2. ≤0 ≤0. =⇒. −2 ≤ ∆c2 ≤ 0.. ≤0. Analogamente, si ottengono i seguenti risultati −∞ ≤ ∆c3 ≤ 0,. −∞ ≤ ∆c4 ≤ 2,. −. 2 ≤ ∆c5 ≤ 0. 5. (b) 9 ≤ ∆b1 ≤ +∞, 2 17 − ≤ ∆c1 ≤ +∞, 2 −2 ≤ ∆c4 ≤ +∞, −. −∞ ≤ ∆b2 ≤ 9,. −8 ≤ ∆b3 ≤ +∞,. −∞ ≤ ∆c2 ≤ 17,. −4 ≤ ∆c3 ≤ +∞,. −∞ ≤ ∆c5 ≤ 4.. (c) −18 ≤ ∆b1 ≤ +∞, −∞ ≤ ∆c1 ≤ 9, −3 ≤ ∆c4 ≤ +∞,. −2 ≤ ∆b2 ≤ 22, −6 ≤ ∆c2 ≤ +∞, 3 −∞ ≤ ∆c5 ≤ . 2. 22 ≤ ∆b3 ≤ 2 5 −∞ ≤ ∆c3 ≤ 6,. −.

(64) 64. CAPITOLO 3. ANALISI DI SENSITIVITA. (d) −∞ ≤ ∆b1 ≤ 11,. −8 ≤ ∆b2 ≤ +∞,. 23 23 ≤ ∆c1 ≤ , 3 2 23 − ≤ ∆c4 ≤ +∞, 5. 23 , 5 23 23 − ≤ ∆c5 ≤ . 5 10. 9 ≤ ∆b1 ≤ 0, 2. −9 ≤ ∆b2 ≤ +∞,. −. −∞ ≤ ∆c2 ≤. 11 ≤ ∆b3 ≤ +∞ 3 23 −∞ ≤ ∆c3 ≤ , 5. −. (e) −. −∞ ≤ ∆c1 ≤ 12, −∞ ≤ ∆c4 ≤. −∞ ≤ ∆c2 ≤. 12 , 5. −. 6 , 5. 0 ≤ ∆b3 ≤. 9 , 2. −∞ ≤ ∆c3 ≤ 12,. 12 ≤ ∆c5 ≤ +∞. 5. (f ) 19 ≤ ∆b1 ≤ +∞, 3 13 −61 ≤ ∆c1 ≤ , 3 13 , −∞ ≤ ∆c4 ≤ 22. −. −10 ≤ ∆b2 ≤ 30, 61 , 14 13 61 − ≤ ∆c5 ≤ . 7 7 −∞ ≤ ∆c2 ≤. 19 2 13 −∞ ≤ ∆c3 ≤ , 14. −15 ≤ ∆b3 ≤. 3.3. Tutte le variazioni riguardano colonne associate a variabili non appartenenti alla base ottima. (a) Il valore delle variabili duali all’ottimo è dato da u∗1 u∗2 = cB A− Bot 1 = −2 0 . La variazione ∆a14 impatta sul costo ridotto di x4 con un contributo pari a −u1 ∆a14 = 4. =⇒. γ¯4 = −2 + 4 = 2 > 0. Quindi la perturbazione specificata compromette l’ottimalit` a della base {x2 , x5 }. (b) Le variabili duali all’ottimo valgono u∗1 u∗2 u∗3 = cB A− Bot 1 = 4 −2 3 , quindi il contributo a γ5 della variazione ∆a25 specificata è −u∗2 ∆a25 = −2. =⇒. γ¯5 = −4 − 2 = −6 < 0,. quindi non c’è perdita di ottimalit` a. (c)–(d) Non si ha perdita di ottimalit` a. (e) Si ha perdita di ottimalit` a. (f ) Non si ha perdita di ottimalit` a Si pu` o osservare che le perturbazioni che non compromettono l’ottimalit` a non alterano la soluzione ottima (ed il valore) sia per il primale che per il duale..

(65) Capitolo 4. Programmazione intera 4.1. (a) Il problema in forma standard risulta max 2x1 − x2 − x3 soggetto a 2x1 + x2 + x4 4x2 + x3 + x5. =5 =5. x1 − x 3 − x 6. =2. x1 , . . . , x6 ≥ 0 intere, con x4 , . . . , x6 variabili di slack (la cui interezza segue dall’interezza di tutti i coefficienti e termini noti). Rilassando il vincolo di interezza ed applicando l’algoritmo del simplesso si perviene alla seguente riformulazione ottima. max. z x6 x5 x1. = = = =. −2x2 − 21 x2 5 −4x2 5 − 21 x2 2 x1 , . . . , x 6 5. 1 2. −x3 −x3 −x3 ≥ 0.. −x4 − 21 x4 − 12 x4. Poiché la soluzione prodotta non è intera, si seleziona una riga k con βk non intero e si genera il taglio di Gomory ad essa associato. Il taglio in questione per la riga della x6 è 1 1 1 − + x2 + x4 ≥ 0, 2 2 2 che inserito nella precedente riformulazione produce max. z x6 x5 x1 y1. = 5 −2x2 1 − 21 x2 = 2 = 5 −4x2 5 − 21 x2 = 2 1 = − 2 + 21 x2 x1 , . . . , x 6 , y 1. −x3 −x3 −x3. −x4 − 21 x4 − 21 x4 + 12 x4. ≥ 0. 65.

(66) 66. CAPITOLO 4. PROGRAMMAZIONE INTERA. dalla quale, con un passo di simplesso duale si ottiene max. z x6 x5 x1 x4. = = = = =. 4 −x2 0 5 −4x2 2 1 −x2 x1 , . . . , x 6 , y 1. −x3 −x3 −x3. −2y1 −y1 −y1 +2y1. ≥ 0.. La soluzione con x1 = 2, x4 = 1, x5 = 5, x2 = x3 = x6 = 0 è intera ed ottima per il programma lineare intero iniziale, con valore ottimo z = 4. (b) Applicando l’algoritmo del simplesso si pu` o determinare la seguente riformulazione ottima. max. z x2 x5 x6. = = = =. 8 −3x1 −x4 1 1 8 − x − 3 3 1 3 x4 1 1 19 + x + 3 3 1 3 x4 4 1 29 − x − 3 3 1 3 x4 x1 , . . . , x6 ≥ 0.. −x3 −2x3. La soluzione non è intera; generando il taglio sulla riga di x2 (− 23 + 31 x1 + 31 x4 ≥ 0) si ha max. z x2 x5 x6 y1. = 8 −3x1 −x4 8 1 1 = − x − 1 3 3 3 x4 1 1 19 + x + = 1 3 3 3 x4 4 1 29 − x − = 1 3 3 3 x4 1 1 2 = − 3 + 3 x1 + 3 x4 x1 , . . . , x6 , y1 ≥ 0,. z x2 x5 x6 x4. = = = = =. −x3 −2x3. da cui max. 6 −2x1 −3y1 2 −y1 7 +y1 9 −x1 −y1 2 −x1 +3y1 x1 , . . . , x6 , y1 ≥ 0.. −x3 −2x3. La soluzione x2 = 2, x5 = 7, x6 = 9, x4 = 2, x1 = x3 = 0 è intera ed ottima per il programma originale, con valore ottimo z = 6. (c) Soluzione ottima con x1 = 2, x2 = 1, x5 = 1, x3 = x4 = 0, con valore ottimo z = 7. (d) Soluzione ottima con x2 = 7, x4 = 2, x5 = 1, x1 = x3 = 0, con valore ottimo z = 14. (e) Soluzione ottima con x1 = 0, x3 = 1, x4 = 3, x2 = 0, valore ottimo z = 1. Esiste una soluzione alternativa con x1 = 0, x2 = 1, x3 = 2, x4 = 1, stesso valore ottimo. (f ) Il problema è in forma standard; dopo l’applicazione della fase 1 si perviene.

(67) 67 alla seguente riformulazione max. z x2 x3 x4. = = = =. − 23 x1 − 23 x1 + 23 x1 1 −x1 x1 , . . . , x4 ≥ 0, 3 2 1 2 1 2. e, generando il taglio dalla riga di x2 : max. z x2 x3 x4 y1. 3 = − 23 x1 2 1 − 23 x1 = 2 1 + 23 x1 = 2 = 1 −x1 = − 21 + 21 x1 x1 , . . . , x4 , y1 ≥ 0,. max. z x2 x3 x4 x1. = 0 −3y1 = −1 −3y1 = 2 +3y1 = 0 −2y1 = 1 +2y1 x1 , . . . , x4 , y1 ≥ 0.. quindi. La riga di x2 presenta la condizione di illimitatezza duale, quindi il programma originale non ammette soluzione intera. 4.2. (a) La Figura 4.1(a) riporta la regione di ammissibilit` a del rilassamento lineare del problema (Nodo 0), costituita dalla figura ABCDE; l’ottimo frazionario è localizzato nel punto C(x1 = 25 , x2 = 0). Si ha quindi LB = −∞, UB = − 52 . Eseguendo l’operazione di branch sulla variabile x1 si ottengono i due nodi 1 (x1 ≤ 2) e 2 (x1 ≥ 3). I rispettivi sottoproblemi hanno regioni di ammissibilit` a delimitate dal trapezio DEHF (Nodo 1) con ottimo intero in F (x1 = 2, x2 = 1) e dal segmento AB, con ottimo intero in B(3, 0) (Nodo 2). Entrambi i nodi possono essere quindi cancellati subito, e l’ottimo del problema iniziale è nel punto F (z = −3) — nota: anche B è ottimo. (b) La Figura 4.1(b) riporta la regione di ammissibilit` a del problema (triangolo ABC); l’ottimo (frazionario) è localizzato in B(x1 = 5, x2 = 92 ); quindi si ha LB = −∞, e UB = 4 al nodo 0. Effettuando il branch su x2 si ottengono i nodi 1 (x2 ≤ 4) e 2 (x2 ≥ 5). Di questi, il 2 risulta immediatamente con regione ammissibile vuota e viene cancellato; il nodo 1 ha invece la regione di ammissibilit` a delimitata dal trapezio ADF C, con ottimo in D(x1 = 14 3 , x2 = 4). Occorre quindi effettuare un nuovo branch su x1 , generando i nodi 3 (x1 ≤ 4) e 4 (x1 ≥ 5). Le regioni di ammissibilit` a per i due nuovi sottoproblemi associati ai nodi sono rispettivamente il triangolo AEG, con ottimo intero in E(4, 3), UB = 2 =⇒ LB = 2 ed il solo segmento CF , con ottimo intero in F (5, 4), UB = 3 =⇒ LB = 3. Entrambi i nodi vengono quindi cancellati, ed il processo si arresta con soluzione ottima x1 = 5, x2 = 4, z = 3. (c) Soluzione ottima con x1 = 2, x2 = 1, valore ottimo z = 10. (d) Soluzione ottima con x1 = 0, x2 = 2, valore ottimo z = −2..

(68) 68. CAPITOLO 4. PROGRAMMAZIONE INTERA. 4.3. Per lavorare con pi` u di due variabili, è vantaggioso utilizzare il simplesso duale per gestire i vincoli addizionali in modo incrementale (analogamente al metodo di Gomory). (a) Come primo passo si risolve il rilassamento lineare (o continuo) del problema, partendo dalla forma standard max 2x1 − x2 − x3 soggetto a 2x1 + x2 + x4 4x2 + x3 + x5. =5 =5. x1 − x 3 − x 6. =2. x1 , . . . , x6 ≥ 0. Risolvendo il problema di prima fase ed applicando il simplesso si perviene alla riformulazione ottima max. z x6 x5 x1. = = = =. −2x2 − 21 x2 5 −4x2 5 − 21 x2 2 x1 , . . . , x 6 5. 1 2. −x3 −x3 −x3 ≥ 0.. −x4 − 12 x4. (Nodo 0). − 12 x4. Il nodo radice 0 ha quindi UB = 5. La soluzione trovata non è intera, quindi si assume LB = −∞. A questo punto si sceglie una variabile con valore frazionario per eseguire l’operazione di branch. In questo caso si è scelto x1 , generando i branch x1 ≤ 2 e x1 ≥ 3 (nodi 1 e 2 rispettivamente). Disponendo della riformulazione ottima del nodo radice, i rilassamenti lineari associati ai nodi figli possono essere risolti in modo incrementale, facendo uso del simplesso duale come accade nel metodo di Gomory. In particolare facendo uso dell’uguaglianza relativa ad x1 si possono esprimere i due vincoli addizionali come 5 1 − x2 − 2 2 5 1 x1 ≥ 3 ⇐⇒ − x2 − 2 2 x1 ≤ 2 ⇐⇒. 1 x4 ≤ 2 2 1 x4 ≥ 3 2. 1 1 1 ⇐⇒ − x2 − x4 + y1 = − , 2 2 2 1 1 1 ⇐⇒ − x2 − x4 − y2 = , 2 2 2. facendo uso della variabile di slack y1 e della variabile di surplus y2 rispettivamente. Nota: questi vincoli non sono tagli di Gomory, ma per la forma in cui sono stati posti possono essere introdotti nella riformulazione e la riottimizzazione dei sottoproblemi avviene tramite il simplesso duale; questo evita di riavviare il simplesso da zero per risolvere i nuovi nodi. Per il nodo 1, inserendo y1 nella riformulazione ottima del nodo padre 0 si ottiene allora max. z x6 x5 x1 y1. = 5 −2x2 1 = − 12 x2 2 = 5 −4x2 5 − 12 x2 = 2 1 = − 2 + 12 x2 x1 , . . . , x 6 , y 1. −x3 −x3 −x3. ≥ 0.. −x4 − 12 x4 − 21 x4 + 21 x4.

(69) 69 e quindi max. z x6 x5 x1 x4. = = = = =. 4 −x2 0 5 −4x2 2 1 −x2 x1 , . . . , x 6 , y 1. −x3 −x3 −x3. −2y1 −y1 −y1 +2y1. ≥ 0.. Il nodo 1 viene quindi chiuso per ottimalit` a, e si ha LB = 4. Per il nodo 2, aggiungendo il vincolo x1 ≥ 3 si ottiene la riformulazione max. z x6 x5 x1 y2. = 5 −2x2 1 − 21 x2 = 2 = 5 −4x2 5 − 21 x2 = 2 1 = − 2 − 21 x2 x1 , . . . , x 6 , y 2. −x3 −x3 −x3. −x4 − 21 x4 − 21 x4 − 12 x4. ≥ 0,. che presenta la condizione di illimitatezza duale; quindi il sottoproblema associato a questo nodo ha regione ammissibile vuota ed il nodo viene chiuso. Non essendoci altri nodi da processare, l’algoritmo si arresta con la soluzione ottima trovata al nodo 1. L’albero di branch è riportato in Figura 4.2(a). (b) Soluzione ottima con x2 = 2, x5 = 7, x6 = 9, x4 = 2, x1 = x3 = 0, con valore ottimo z = 6. (c) La soluzione del rilassamento lineare fornisce la riformulazione max. z= x1 = x2 =. −x5 + 41 x5 − 21 x5 x1 , . . . , x5 ≥ 0. 8. 7 4 3 2. −x4 − 21 x4. −x3 + 43 x3 − 21 x3. (Nodo 0). Effettuando il branch su x1 si generano i nodi 1 (x1 ≤ 1) e 2 (x1 ≥ 2). Per il nodo 1, inserendo il vincolo x1 ≤ 1 si ha max. z x1 x2 y1. = 8 7 = 4 3 = 2 = − 43. z x1 x2 x4. = = = =. −x4 − 21 x4 + 21 x4. −x5 + 41 x5 − 21 x5 − 41 x5. −x3 + 34 x3 − 12 x3 − 34 x3. x1 , . . . , x5 , y1 ≥ 0.. da cui max. 13 2. − 23 x5. − 52 x3. 3 − 12 x5 2 3 +2y1 + 21 x5 2 x1 , . . . , x5 , y1 ≥ 0.. − 12 x3 + 32 x3. 1. −2y1 −y1. Per il nodo 2 si ha max. z x1 x2 y2. = 8 −x4 −x5 1 1 7 − x + = 4 4 2 4 x5 1 3 − = 2 2 x5 1 1 1 = − 4 − 2 x4 + 4 x5 x1 , . . . , x5 , y2 ≥ 0.. −x3 + 34 x3 − 12 x3 + 43 x3. (Nodo 1).

(70) 70. CAPITOLO 4. PROGRAMMAZIONE INTERA. da cui max. z x1 x2 x3. = = = =. 23 3. 2. − 35 x4. − 23 x5. 4 − 31 x4 − 13 x5 3 1 + 32 x4 − 13 x5 3 x1 , . . . , x 5 , y 2 ≥ 0. − 34 y2 +y2 − 32 y2 + 34 y2. (Nodo 2). Nessuno dei due nodi presenta una soluzione intera, pertanto si assume ancora LB = −∞. Uno dei nodi deve quindi essere selezionato per effettuare un branch. Operando sul nodo 2, si generano i nodi 3 (x2 ≤ 1) e 4 (x2 ≥ 2). Per il nodo 3, procedendo in modo analogo a prima si introduce il vincolo x2 ≤ 1 ⇐⇒. 1 2 1 1 2 1 4 1 − x4 − x5 − y2 ≤ 1 ⇐⇒ − x4 − x5 − y2 + y3 = − , 3 3 3 3 3 3 3 3. nella riformulazione ottima del nodo padre 2 e si ha max. z x1 x2 x3 y3. = 23 3 = 2 4 = 3 1 = 3 = − 31. z x1 x2 x3 x5. = = = = =. − 53 x4. − 23 x5. − 13 x4 + 23 x4 + 13 x4. − 13 x5 − 13 x5 + 31 x5. − 34 y2 +y2 − 32 y2 + 34 y2 + 32 y2. x1 , . . . , x5 , y2 , y3 ≥ 0,. e quindi max. 7 −x4 −2y3 2 1 −y3 0 +x4 −y3 1 −x4 +3y3 x1 , . . . , x5 , y2 , y3 ≥ 0.. +y2 +2y2 −2y2. (Nodo 3). Avendo soluzione intera, il nodo 3 è chiuso per ottimalit` a; inoltre si imposta LB = 7, ed in base a questo si pu` o cancellare il nodo 1 che ha un upper bound a. di 13 2 . Infine, si verifica facilmente che il nodo 4 viene chiuso per inammissibilit` L’albero di branch è riportato in Figura 4.2(c). (d) Soluzione ottima con x2 = 7, x4 = 2, x5 = 1, x1 = x3 = 0, valore ottimo z = 14. (e) Soluzione ottima con x1 = 0, x3 = 1, x4 = 3, x2 = 0, valore ottimo z = 1. (f ) Non ha soluzioni intere..

(71) 71. x2 E(0, 6) H(2, 6). A(3, 6). D(0, 5). F (2, 1) 0. B(3, 0) C( 25 , 0). x1 ≤ 2. x1. x1 ≥ 3. 1. 2. (a) x2. D( 14 3 , 4). B(5, 92 ) F (5, 4). E(4, 3). 0 x2 ≤ 4. x2 ≥ 5. 1 A(2, 0). G(4, 0). x1 ≤ 4. x1 C(5, 0). 3 (b) Figura 4.1: Regioni di ammissibilit` a e alberi di branch.. 2 x1 ≥ 5 4.

(72) 72. CAPITOLO 4. PROGRAMMAZIONE INTERA. 0 x1 ≤ 2. x1 ≥ 3. 1. 2 (a) 0. x1 ≤ 1. x1 ≥ 2. 1. 2 x2 ≤ 1. x2 ≥ 2. 3. 4 (c) Figura 4.2: Alberi di branch..

(73) Capitolo 5. Introduzione ai grafi 5.1. (a) Seguendo l’algoritmo noto per la determinazione delle componenti connesse, si parte con un insieme di nodi W = V = {a, b, c, d, e, f, g}. Si pone S = {a}, T1 = ∅, quindi si procede iterativamente come segue. 1. S := S − {a} ∪ {b, e} = {b, e}; T1 := {a}; 2. S := S − {b} ∪ {c} = {e, c}; T1 := T1 ∪ {b} = {a, b}; 3. S := S − {e} ∪ {c, d, g} = {c, d, g}; T1 := T1 ∪ {e} = {a, b, e}; 4. S := S − {c} ∪ f = {d, g, f }; T1 := T1 ∪ {c} = {a, b, e, c}; 5. S := S − {d} ∪ {f } = {g, f }; T1 := T1 ∪ {d} = {a, b, e, c, d}; 6. S := S − {g} ∪ {f } = {f }; T1 := T1 ∪ {g} = {a, b, e, c, d, g}; 7. S := S − {f } ∪ ∅ = ∅; T1 := T1 ∪ {f } = {a, b, e, c, d, g, f }; infine, essendo S = ∅, si calcola W := W − T1 = ∅, e quindi l’algoritmo termina con una singola componente connessa T1 , quindi G è connesso. (b) Ponendo W = V = {a, b, c, d, e, f, g, h, i}, si procede dapprima alla ricerca della prima componente connessa T1 . Sia S = {a}, T1 = ∅, quindi 1. S := S − {a} ∪ {c, h} = {c, h}; T1 := T1 ∪ {a} = {a}; 2. S := S − {c} ∪ {e} = {h, e}; T1 := T1 ∪ setc = {a, c}; 3. S := S − {h} ∪ {e} = {e}; T1 := T1 ∪ h = {a, c, h}; 73.

(74) 74. CAPITOLO 5. INTRODUZIONE AI GRAFI 4. S := S − {e} ∪ ∅ = ∅; T1 := T1 ∪ {e} = {a, c, h, e};. quindi T1 = {a, c, h, e} è una componente connessa di G; ricalcolando W := W − T1 = {b, d, f, g, i} 6= ∅, si conclude che esistono altre componenti connesse da identificare. Quindi si pone s = {b}, T2 = ∅ e si ha 1. S := S − {b} ∪ {d, g} = {d, g}; T2 := T2 ∪ {b}; 2. S := S − {d} ∪ {f, i} = {g, f, i}; T2 := T2 ∪ {d} = {b, d}; 3. S := S − {g} ∪ {f } = {f, i}; T2 := T2 ∪ {g} = {b, d, g}; 4. S := S − {f } ∪ ∅ = {i}; T2 := T2 ∪ {f } = {b, d, g, f }; 5. S := S − {i} ∪ ∅ = ∅; T2 := T2 ∪ {i} = {b, d, g, f, i}; essendo W − T2 = ∅, l’algoritmo termina. Sono state identificate le componenti connesse T1 = {a, c, e, h} e T2 = {b, d, g, f, i}, quindi G non è connesso. (c) Si hanno T1 = {b, c, d, e, f } e T2 = {a, g, h}, quindi G non è connesso. (d) Si ha T1 = {a, b, c, d, e, f } = V , quindi G è connesso. (e) Si hanno T1 = {a, b, c, f } e T2 = {d, e, g}, quindi G non è connesso. (f ) Si ha T1 = {a, b, c, d, e, f, g, h} = V , quindi G è connesso. 5.2. (a) Applicando l’algoritmo per il riconoscimento dei grafi bipartiti, si ponga W = V e si proceda come segue. C1 : a C2 :. T2 = {b, e}. C1 : a C2 : b, e. T1 = {g, d, c};. C1 : a, g, d, C2 : b, e. c. C1 : a, g, d, C2 : b, e, f. c. T2 = {f }; T1 = ∅, T2 = ∅.. Poiché T1 = T2 = ∅ e C1 ∩ C2 = ∅, W = W − (C1 ∪ C2 ) = ∅, il grafo G risulta bipartito, con V1 = {a, c, d, g} e V2 = {b, e, f }. (b) Si ponga W = V , T1 = {a} e si ottiene C1 : a C2 :. T2 = {c, h}. C1 : a C2 : c, h. T1 = {e}. C1 : a, C2 : c,. T2 = ∅, T1 = ∅.. e h.