Capitolo 1 Esercizi di Programmazione Linearetiziano19661.interfree.it/tracce/esercizi.pdf ·...

Capitolo 1

Esercizi di Programmazione

Lineare

1.1 Il metodo del simplesso

Esercizio. Risolvere il seguente problema utilizzando il metodo del simp-lesso:

max Z = 2x1 + x2 + x3

x1 +3x2 +x3 ≤ 62x1 −x2 +x3 ≤ 5x1 +x2 +4x3 ≤ 10

x1, x2, x3 ≥ 0.

Svolgimento. Scriviamo innanzitutto il problema in forma aumentata

max Z = 2x1 + x2 + x3

x1 +3x2 +x3 +x4 = 62x1 −x2 +x3 +x5 = 5x1 +x2 +4x3 +x6 = 10

x1, x2, x3, x4, x5, x6 ≥ 0.

Le equazioni da risolvere sono:

(0) Z −2x1 −x2 −x3 = 0(1) x1 +3x2 +x3 +x4 = 6(2) 2x1 −x2 +x3 +x5 = 5(3) x1 +x2 +4x3 +x6 = 10

1

CAPITOLO 1. ESERCIZI DI PROGRAMMAZIONE LINEARE 2

Iterazione 0

Var.base Eq. Z x1 x2 x3 x4 x5 x6 bi

Z

x4

x5

x6

(0)

(1)

(2)

(3)

1

0

0

0

−2

1

2

1

−1

3

−1

1

−1

1

1

4

0

1

0

0

0

0

1

0

0

0

0

1

0

6

5

10

Iterazione 1


Z

x4

x1

x6

(0)

(1)

(2)

(3)

1

0

0

0

0

0

1

0

−2

7

2

−1

2

3

2

0

1

2

1

2

7

2

0

1

0

0

1

−1

2

1

2

−1

2

0

0

0

1

5

7

2

5

2

15

2

Iterazione 2


Z

x2

x1

x6

(0)

(1)

(2)

(3)

1

0

0

0

0

0

1

0

0

1

0

0

2

7

1

7

4

7

23

7

4

7

2

7

1

7

−3

7

5

7

−1

7

3

7

−2

7

0

0

0

1

7

1

3

6

Soluzione ottima e (3, 1, 0, 0, 0, 6), con Z = 7.


Esercizio. Risolvere il seguente problema utilizzando il metodo del simples-so:

max Z = 3x1 + x2 + 6x3

2x1 +x3 ≤ 10x1 +x2 −2x3 ≤ 43x1 +x2 ≤ 5

x1, x2, x3 ≥ 0.

Svolgimento. Scriviamo il problema in forma aumentata

max Z = 3x1 + x2 + 6x3

2x1 +x3 +x4 = 10x1 +x2 −2x3 +x5 = 43x1 +x2 +x6 = 5

x1, x2, x3, x4, x5, x6 ≥ 0.


(0) Z −3x1 −x2 −6x3 = 0(1) 2x1 +x3 +x4 = 10(2) x1 +x2 −2x3 +x5 = 4(3) 3x1 +x2 +x6 = 5

Iterazione 0


Z

x4

x5

x6

(0)

(1)

(2)

(3)

1

0

0

0

−3

2

1

3

−1

0

1

1

−6

1

−2

0

0

1

0

0

0

0

1

0

0

0

0

1

0

10

4

5


Iterazione 1


Z

x3

x5

x6

(0)

(1)

(2)

(3)

1

0

0

0

9

2

5

3

−1

0

1

1

0

1

0

0

6

1

2

0

0

0

1

0

0

0

0

1

60

10

24

5

Iterazione 2


Z

x3

x5

x2

(0)

(1)

(2)

(3)

1

0

0

0

12

2

2

3

0

0

0

1

0

1

0

0

6

1

2

0

0

0

1

0

1

0

−1

1

65

10

19

5

Soluzione ottima e (0, 5, 10, 0, 19, 0), con Z = 65.Esercizio. Risolvere il seguente problema utilizzando il metodo del simp-lesso:

max Z = 7x1 + x2 + 8x3

3x1 −x2 +x3 +x4 ≤ 6x2 +3x3 +4x4 ≤ 9

x1, x2, x3, x4 ≥ 0.


max Z = 7x1 + x2 + 8x3

3x1 −x2 +x3 +x4 +x5 = 6x2 +3x3 +4x4 +x6 = 9

x1, x2, x3, x4, x5, x6 ≥ 0.


(0) Z −7x1 −x2 −8x3 = 0(1) 3x1 −x2 +x3 +x4 +x5 = 6(2) x2 +3x3 +4x4 +x6 = 9


Iterazione 0


Z

x5

x6

(0)

(1)

(2)

1

0

0

−7

3

0

−1

−1

1

−8

1

3

0

1

4

0

1

0

0

0

1

0

6

9

Iterazione 1


Z

x5

x3

(0)

(1)

(2)

1

0

0

−7

3

0

5

3

−4

3

1

3

0

0

1

32

3

−1

3

4

3

0

1

0

8

3

−1

3

1

3

24

3

3

Iterazione 2


Z

x1

x3

(0)

(1)

(2)

1

0

0

0

1

0

−13

9

−4

9

1

3

0

0

1

89

9

−1

9

4

3

7

3

1

3

0

17

9

−1

9

1

3

31

1

3

Iterazione 3


Z

x1

x2

(0)

(1)

(2)

1

0

0

0

1

0

0

0

1

13

3

4

3

3

47

3

5

3

4

7

3

1

3

0

10

3

1

3

1

44

5

9

Soluzione ottima e (5, 9, 0, 0, 0, 0), con Z = 44.


Esercizio. Risolvere il seguente problema utilizzando il metodo del simp-lesso:

max Z = 5x1 + 2x2 + 2x3 + 4x4

3x1 +x2 −x3 +2x4 ≤ 92x1 +5x2 −2x3 −x4 ≤ 8

x1, x2, x3, x4 ≥ 0.


max Z = 5x1 + 2x2 + 2x3 + 4x4

3x1 +x2 −x3 +2x4 +x5 = 92x1 +5x2 −2x3 −x4 +x6 = 8

x1, x2, x3, x4, x5, x6 ≥ 0.


(0) Z −5x1 −2x2 −2x3 −4x4 = 0(1) 3x1 +x2 −x3 +2x4 +x5 = 9(2) 2x1 +5x2 −2x3 −x4 +x6 = 8

Iterazione 0


Z

x5

x6

(0)

(1)

(2)

1

0

0

−5

3

2

−2

1

5

−2

−1

−2

−4

2

−1

0

1

0

0

0

1

0

9

8

Iterazione 1


Z

x1

x6

(0)

(1)

(2)

1

0

0

0

1

0

−1

3

1

3

13

3

−11

3

−1

3

−4

3

−2

3

2

3

−7

3

5

3

1

3

−2

3

0

0

1

15

3

2

Poiche non c’e nessuna variabile candidata ad uscire dalla base significa chela regione ammissibile e illimitata e quindi

Z = +∞.


1.2 Il metodo del simplesso a due fasi

Esercizio. Risolvere il seguente problema utilizzando il metodo del simplessoa due fasi:

min Z = 3x1 + x2 + x3

x1 +x2 +x3 ≤ 32x1 +x2 +x3 ≥ 42x1 +3x2 +x3 = 6

x1, x2, x3 ≥ 0.

Svolgimento. Scriviamo il problema nella forma aumentata introducendo unavariabile slack, una variabile surplus e due variabili artificiali:

min Z = 3x1 + x2 + x3

x1 +x2 +x3 +x4 = 32x1 +x2 +x3 −x5 +x6 = 42x1 +3x2 +x3 +x7 = 6

x1, x2, x3, x4, x5, x6, x7 ≥ 0.

Scriviamo ora i problemi che risolve il metodo del simplesso a due fasi:

I Fasemin Z = x6 + x7

x1 +x2 +x3 +x4 = 32x1 +x2 +x3 −x5 +x6 = 42x1 +3x2 +x3 +x7 = 6

x1, x2, x3, x4, x5, x6, x7 ≥ 0.

II Fasemin Z = 3x1 + x2 + x3

x1 +x2 +x3 +x4 = 32x1 +x2 +x3 −x5 = 42x1 +3x2 +x3 = 6

x1, x2, x3, x4, x5 ≥ 0.

Poiche il problema e di minimo dobbiamo trasformarlo in un problema dimassimo cambiando il segno ai due membri della funzione obiettivo in en-


trambi i problemi:

I Fasemax −Z = −x6 − x7

x1 +x2 +x3 +x4 = 32x1 +x2 +x3 −x5 +x6 = 42x1 +3x2 +x3 +x7 = 6

x1, x2, x3, x4, x5, x6, x7 ≥ 0.

II Fasemax −Z = −3x1 − x2 − x3

x1 +x2 +x3 +x4 = 32x1 +x2 +x3 −x5 = 42x1 +3x2 +x3 = 6

x1, x2, x3, x4, x5 ≥ 0.

Le equazioni della I fase sono

(0) −Z +x6 +x7 = 0(1) x1 +x2 +x3 +x4 = 3(2) 2x1 +x2 +x3 −x5 +x6 = 4(3) 2x1 +3x2 +x3 x7 = 6.

Per porre in problema in forma canonica bisogna prima sottrarre dall’e-quazione (0) l’equazione (2), ottenendo le nuove equazioni

(0) −Z −2x1 −x2 −3x3 +x5 +x7 = −4(1) x1 +x2 +x3 +x4 = 3(2) 2x1 +x2 +x3 −x5 +x6 = 4(3) 2x1 +3x2 +x3 +x7 = 6

e poi sottrarre dall’equazione (0) l’equazione (3), ottenendo le equazioni finaliper la I fase:

(0) −Z −4x1 −4x2 −2x3 +x5 = −10(1) x1 +x2 +x3 +x4 = 3(2) 2x1 +x2 +x3 −x5 +x6 = 4(3) 2x1 +3x2 +x3 +x7 = 6.

Adesso possiamo scrivere il tableau del metodo del simplesso:


Iterazione 0

Var.base Eq. Z x1 x2 x3 x4 x5 x6 x7 bi

Z

x4

x6

x7

(0)

(1)

(2)

(3)

−1

0

0

0

−4

1

2

2

−4

1

1

3

−2

1

1

1

0

1

0

0

1

0

−1

0

0

0

1

0

0

0

0

1

−10

3

4

6

Iterazione 1


Z

x4

x1

x7

(0)

(1)

(2)

(3)

−1

0

0

0

0

0

1

0

−2

1

2

1

2

2

0

1

2

1

2

0

0

1

0

0

−1

1

2

−1

2

1

2

−1

2

1

2

−1

0

0

0

1

−2

1

2

2

Iterazione 2


Z

x4

x1

x2

(0)

(1)

(2)

(3)

−1

0

0

0

0

0

1

0

0

0

0

1

0

1

2

1

2

0

0

1

0

0

0

0

1

4

−3

4

1

2

−1

4

3

4

−1

2

1

−1

4

−1

4

1

2

0

1

2

3

2

1

Soluzione ottima della prima fase e (3/2, 1, 0, 1/2, 0). Dal tableau finale dellaprima fase dobbiamo eliminare le colonne relative alle variabili artificiali, so-stituire la funzione obiettivo e porre il sistema di equazioni in forma canonica.Il tableau relativo alle prime due operazioni e il seguente:


II Fase-Tablaeu preliminare

Var.base Eq. Z x1 x2 x3 x4 x5 bi

Z

x4

x1

x2

(0)

(1)

(2)

(3)

−1

0

0

0

3

0

1

0

1

0

0

1

1

1

2

1

2

0

0

1

0

0

0

1

4

−3

4

1

2

0

1

2

3

2

1

II Fase-Eliminazione coeff. di x1


Z

x4

x1

x2

(0)

(1)

(2)

(3)

−1

0

0

0

0

0

1

0

1

0

0

1

−1

2

1

2

1

2

0

0

1

0

0

9

4

1

4

−3

4

1

2

−9

2

1

2

3

2

1



Z

x4

x1

x2

(0)

(1)

(2)

(3)

−1

0

0

0

0

0

1

0

0

0

0

1

−1

2

1

2

1

2

0

0

1

0

0

7

4

1

4

−3

4

1

2

−11

2

1

2

3

2

1


II Fase-Iterazione 0


Z

x4

x1

x2

(0)

(1)

(2)

(3)

−1

0

0

0

0

0

1

0

0

0

0

1

−1

2

1

2

1

2

0

0

1

0

0

7

4

1

4

−3

4

1

2

−11

2

1

2

3

2

1

II Fase-Iterazione 1


Z

x3

x1

x2

(0)

(1)

(2)

(3)

−1

0

0

0

0

0

1

0

0

0

0

1

0

1

0

0

1

2

−1

0

2

1

2

−1

1

2

−5

1

1

1

Esercizio. Risolvere il seguente problema utilizzando il metodo del simplessoa due fasi:

max Z = x1 + 5x2

x1 −x2 ≤ 35x1 −2x2 = 8−x1 +3x2 ≥ 1

x1, x2, x3 ≥ 0.

Svolgimento. Scriviamo il problema nella forma aumentata introducendo unavariabile slack, una variabile surplus e due variabili artificiali:

max Z = x1 + 5x2

x1 −x2 +x3 = 35x1 −2x2 +x4 = 8−x1 +3x2 −x5 +x6 = 1

x1, x2, x3, x4, x5, x6 ≥ 0.


Scriviamo ora i problemi che il metodo a due fasi deve risolvere:

I Fasemax Z = −x4 − x6

x1 −x2 +x3 = 35x1 −2x2 +x4 = 8−x1 +3x2 −x5 +x6 = 1

x1, x2, x3, x4, x5, x6 ≥ 0.

II Fasemax Z = x1 + 5x2

x1 −x2 +x3 = 35x1 −2x2 = 8−x1 +3x2 −x5 = 1

x1, x2, x3, x5 ≥ 0.


(0) Z +x4 +x6 = 0(1) x1 −x2 +x3 = 3(2) 5x1 −2x2 +x4 = 8(3) −x1 +3x2 −x5 +x6 = 1.

Per porre in problema in forma canonica bisogna prima sottrarre dall’equa-zione (0) l’equazione (2), ottenendo le nuove equazioni

(0) Z −5x1 +2x2 +x6 = −8(1) x1 −x2 +x3 = 3(2) 5x1 −2x2 +x4 = 8(3) −x1 +3x2 −x5 +x6 = 1


(0) Z −4x1 −x2 +x5 = −9(1) x1 −x2 +x3 = 3(2) 5x1 −2x2 +x4 = 8(3) −x1 +3x2 −x5 +x6 = 1.



I Fase-Iterazione 0

Var.base Eq. Z x1 x2 x3 x4

x5 x6 bi

Z

x3

x4

x6

(0)

(1)

(2)

(3)

1

0

0

0

−4

1

5

−1

−1

−2

−2

3

0

1

0

0

0

0

1

0

1

0

0

−1

0

0

0

1

−9

3

8

1

I Fase-Iterazione 1


x5 x6 bi

Z

x3

x1

x6

(0)

(1)

(2)

(3)

1

0

0

0

0

0

1

0

−13

5

−3

5

−2

5

13

5

0

1

0

0

4

5

−1

5

1

5

1

5

1

0

0

−1

0

0

0

1

−13

5

7

5

8

5

13

5

I Fase-Iterazione 2


x5 x6 bi

Z

x3

x1

x2

(0)

(1)

(2)

(3)

1

0

0

0

0

0

1

0

0

0

0

1

0

1

0

0

1

− 2

13

3

13

1

13

0

− 3

13

− 2

13

− 5

13

1

3

13

2

13

5

13

0

2

2

1

Terminata la I Fase del metodo del simplesso si devono eliminare le colonnerelative alle variabili artificiale e deve essere sostituita la funzione obiettivo.


Tableau Finale I Fase con la funzione obiettivo della II Fase

Var.base Eq. Z x1 x2 x3 x5 bi

Z

x3

x1

x2

(0)

(1)

(2)

(3)

1

0

0

0

−1

0

1

0

−5

0

0

1

0

1

0

0

0

− 3

13

− 2

13

− 5

13

0

2

2

1

II Fase-Eliminazione coefficiente di x1


Z

x3

x1

x2

(0)

(1)

(2)

(3)

1

0

0

0

0

0

1

0

−5

0

0

1

0

1

0

0

− 2

13

− 3

13

− 2

13

− 5

13

2

2

2

1

II Fase-Eliminazione coefficiente di x2


Z

x3

x1

x2

(0)

(1)

(2)

(3)

1

0

0

0

0

0

1

0

0

0

0

1

0

1

0

0

−27

13

− 3

13

− 2

13

− 5

13

7

2

2

1

A questo punto non e verificato il test di ottimalita in quanto esiste un coeffi-ciente negativo nell’equazione (0), tuttavia nessuna variabile in base soddisfail test del minimo rapporto perche nella colonna relativa a x5, variabile en-trante in base, tutti i coefficienti sono negativi. Questa situazione si verificaquando il problema non ha soluzione, cioe la funzione obiettivo e illimitata (il


valore di x5, e quindi della funzione obiettivo, puo crescere indefinitamentesenza che alcuna altra variabile assuma valore zero).Esercizio. Risolvere il seguente problema utilizzando il metodo del simplessoa due fasi:

min Z = 6x1 + 3x2 + 4x3

−4x1 +3x2 +3x3 ≥ 27x1 +x2 −2x3 ≥ 6

x1, x2, x3 ≥ 0.

Svolgimento. Scriviamo il problema nella forma aumentata introducendo duevariabili surplus e due variabili artificiali:

min Z = 6x1 + 3x2 + 4x3

−4x1 +3x2 +3x3 −x4 +x5 = 27x1 +x2 −2x3 −x6 +x7 = 6

x1, x2, x3, x4, x6, x5, x7 ≥ 0.



−4x1 +3x2 +3x3 −x4 +x5 = 27x1 +x2 −2x3 −x6 +x7 = 6

x1, x2, x3, x4, x6, x5, x7 ≥ 0.

II Fasemin Z = 6x1 + 3x2 + 4x3

−4x1 +3x2 +3x3 −x4 = 27x1 +x2 −2x3 −x6 = 6

x1, x2, x3, x4, x6 ≥ 0.

Poiche il problema e di minimo dobbiamo trasformarlo in un problema dimassimo cambiando il segno ai due membri della funzione obiettivo in en-trambi i problemi:


−4x1 +3x2 +3x3 −x4 +x5 = 27x1 +x2 −2x3 −x6 +x7 = 6

x1, x2, x3, x4, x6, x5, x7 ≥ 0.


II Fasemax −Z = −6x1 − 3x2 − 4x3

−4x1 +3x2 +3x3 −x4 = 27x1 +x2 −2x3 −x6 = 6

x1, x2, x3, x4, x6 ≥ 0.


(0) −Z +x5 +x7 = 0(1) −4x1 +3x2 +3x3 −x4 +x5 = 2(2) 7x1 +x2 −2x3 −x6 +x7 = 6.


(0) −Z +4x1 −3x2 −3x3 +x4 +x7 = −2(1) −4x1 +3x2 +3x3 −x4 +x5 = 2(2) 7x1 +x2 −2x3 −x6 +x7 = 6


(0) −Z −3x1 −4x2 −x3 +x4 +x6 = −8(1) −4x1 +3x2 +3x3 −x4 +x5 = 2(2) 7x1 +x2 −2x3 −x6 +x7 = 6.


Iterazione 0

Var.base Eq. Z x1 x2 x3 x4 x5

x6 x7 bi

Z

x5

x7

(0)

(1)

(2)

−1

0

0

−3

−4

7

−4

3

1

−1

3

−2

1

−1

0

0

1

0

1

0

−1

0

0

1

−8

2

6


Iterazione 1


x6 x7 bi

Z

x2

x7

(0)

(1)

(2)

−1

0

0

−25

3

−4

3

25

3

0

1

0

3

1

−3

−1

3

−1

3

1

3

4

3

1

3

−1

3

1

0

−1

0

0

1

−16

3

2

3

16

3

Iterazione 2


x6 x7 bi

Z

x2

x1

(0)

(1)

(2)

−1

0

0

0

0

1

0

1

0

1

13

25

− 9

25

0

− 7

25

1

25

1

7

25

− 1

25

0

− 4

25

− 3

25

1

4

25

3

25

0

38

25

16

25

Soluzione ottima della prima fase e (16/25, 38/25, 0). Dal tableau finale dellaprima fase dobbiamo eliminare le colonne relative alle variabili artificiali, so-stituire la funzione obiettivo e porre il sistema di equazioni in forma canonica.Il tableau relativo alle prime due operazioni e il seguente:



Z

x2

x1

(0)

(1)

(2)

−1

0

0

6

0

1

3

1

0

4

13

25

− 9

25

0

7

25

1

25

0

− 4

25

− 3

25

0

38

25

16

25




Z

x2

x1

(0)

(1)

(2)

−1

0

0

6

0

1

0

1

0

61

25

13

25

− 9

25

21

25

7

25

1

25

12

25

− 4

25

− 3

25

−114

25

38

25

16

25



Z

x2

x1

(0)

(1)

(2)

−1

0

0

0

0

1

0

1

0

23

5

13

25

− 9

25

3

5

− 7

25

1

25

6

5

− 4

25

− 3

25

−42

5

38

25

16

25

Poiche e verificato il test di ottimalita la BFS trovata trovata al termine dellaprima fase e soluzione ottima del problema. Il valore della funzione obiettivonella soluzione ottima e Z = 42/5.Esercizio. Risolvere il seguente problema utilizzando il metodo del simplessoa due fasi:

min Z = 3x1 + 2x2 + 4x3

x1 −2x2 +2x3 = 33x1 +x2 −3x3 ≥ 6

x1, x2, x3 ≥ 0.

Svolgimento. Scriviamo il problema nella forma aumentata introducendo unavariabile surplus e due variabili artificiali:

min Z = 3x1 + 2x2 + 4x3

x1 −2x2 +2x3 +x4 = 33x1 +x2 −3x3 −x5 +x6 = 6

x1, x2, x3, x5, x4, x6 ≥ 0.




x1 −2x2 +2x3 +x4 = 33x1 +x2 −3x3 −x5 +x6 = 6

x1, x2, x3, x5, x4, x6 ≥ 0.

II Fasemin Z = 3x1 + 2x2 + 4x3

x1 −2x2 +2x3 = 33x1 +x2 −3x3 −x5 = 6

x1, x2, x3, x5 ≥ 0.

Poiche il problema e di minimo dobbiamo trasformarlo in un problema dimassimo cambiando il segno ai due membri della funzione obiettivo in en-trambi i problemi:


x1 −2x2 +2x3 +x4 = 33x1 +x2 −3x3 −x5 +x6 = 6

x1, x2, x3, x5, x4, x6 ≥ 0.

II Fasemax −Z = −3x1 − 2x2 − 4x3

x1 −2x2 +2x3 = 33x1 +x2 −3x3 −x5 = 6

x1, x2, x3, x5 ≥ 0.


(0) −Z +x4 +x6 = 0(1) x1 −2x2 +2x3 +x4 = 3(2) 3x1 +x2 −3x3 −x5 +x6 = 6.


(0) −Z −x1 +2x2 −2x3 +x6 = −3(1) x1 −2x2 +2x3 +x4 = 3(2) 3x1 +x2 −3x3 −x5 +x6 = 6



(0) −Z −4x1 +x2 +x3 +x5 = −9(1) x1 −2x2 +2x3 +x4 = 3(2) 3x1 +x2 −3x3 −x5 +x6 = 6.


Iterazione 0


x5 x6 bi

Z

x4

x6

(0)

(1)

(2)

−1

0

0

−4

1

3

1

−2

1

1

2

−3

0

1

0

1

0

−1

0

0

1

−9

3

6

Iterazione 1


x5 x6 bi

Z

x4

x1

(0)

(1)

(2)

−1

0

0

0

0

1

7

3

−7

3

1

3

−3

3

−1

0

1

0

−1

3

1

3

−1

3

4

3

−1

3

1

3

−1

1

2

Iterazione 2


x5 x6 bi

Z

x3

x1

(0)

(1)

(2)

−1

0

0

0

0

1

0

−7

9

−4

9

0

1

0

1

1

3

1

3

0

1

9

−2

3

1

−1

9

2

9

0

1

3

7

3

Soluzione ottima della prima fase e (7/3, 0, 1/3). Dal tableau finale dellaprima fase dobbiamo eliminare le colonne relative alle variabili artificiali, so-stituire la funzione obiettivo e porre il sistema di equazioni in forma canonica.Il tableau relativo alle prime due operazioni e il seguente:




Z

x2

x1

(0)

(1)

(2)

−1

0

0

3

0

1

2

−7

9

−4

9

4

1

0

0

1

9

−2

9

0

1

3

7

3



Z

x2

x1

(0)

(1)

(2)

−1

0

0

0

0

1

10

3

−7

9

−4

9

4

1

0

2

3

1

9

−2

9

−7

1

3

7

3



Z

x2

x1

(0)

(1)

(2)

−1

0

0

0

0

1

58

9

−7

9

−4

9

0

1

0

2

9

1

9

−2

9

−25

3

1

3

7

3

Poiche e verificato il test di ottimalita la BFS trovata trovata al termine dellaprima fase e soluzione ottima del problema. Il valore della funzione obiettivonella soluzione ottima e Z = 25/3.Esercizio. Determinare i prezzi ombra del seguente problema di program-mazione lineare:

max Z = x1 + 3x2

4x1 +x2 ≤ 244x1 +3x2 ≤ 32

x2 ≤ 8x1 ≥ 0, x2 ≥ 0.


Svolgimento. Introduciamo tre variabili slack (una per ogni vincolo) e ri-solviamo il problema aumentato:

max Z = x1 + 3x2

4x1 +x2 +x3 = 244x1 +3x2 +x4 = 32

x2 +x5 = 8xi ≥ 0, i = 1, 2, 3, 4, 5.

Iterazione 0


Z

x3

x4

x5

(0)

(1)

(2)

(3)

1

0

0

0

−1

4

4

0

−3

1

3

1

0

1

0

0

0

0

1

0

0

0

0

1

0

24

32

8

Iterazione 1


Z

x3

x4

x2

(0)

(1)

(2)

(3)

1

0

0

0

−1

4

4

0

0

0

0

1

0

1

0

0

0

0

1

0

3

−1

−3

1

24

16

8

8


Iterazione 2


Z

x3

x1

x2

(0)

(1)

(2)

(3)

1

0

0

0

0

0

1

0

0

0

0

1

0

1

0

0

1

4

−1

1

4

0

9

4

2

−3

4

1

26

8

2

8

Avendo raggiunto la soluzione ottima (2, 8, 8, 0, 0), con Z = 26, sono deter-minati anche i relativi prezzi ombra

y∗

1= 0, y∗

2=

1

4, y∗

3=

9

4.

Capitolo 2

Problemi di Trasporto e

Assegnamento

2.1 Il problema del trasporto

Esercizio. Risolvere il problema del trasporto con 2 sorgenti, con offertarispettivamente 80 e 40 e 3 destinazioni con domanda 25, 50 e 30 e conmatrice dei costi

C =

[

10 40 1520 25 30

]

.

determinando le quantita di merci da inviare dalle sorgenti alle destinazioniaffinche il costo sia minimo.Svolgimento. Innanzitutto osserviamo che e necessario introdurre una desti-nazione fittizia, 4D, poiche

∑

i

si = 120 6=∑

j

dj = 105

che serva ad assorbire l’offerta eccedente pari a 15. I costi relativi a taledestinazione saranno posti tutti uguali a zero, quindi la matrice dei costidiviene:

C =

[

10 40 15 020 25 30 0

]

.

Scriviamo la tabella dei dati e applichiamo la regola di Nord-Ovest per trovarela BFS iniziale:

24

CAPITOLO 2. PROBLEMI DI TRASPORTO E ASSEGNAMENTO 25

10 40 15 0

20 25 30 0

1 2 3 4D si ui

1

2

dj 25 50 30 15

vj

80

40

25 50 5

25 15

Z = 3075

La BFS iniziale e:(25, 50, 5, 0, 0, 0, 25, 25)

per la quale il valore della funzione obiettivo e Z = 3075. Applichiamo orail metodo del simplesso partendo dal seguente tableau:

10 40 15 0

20 25 30 0

1 2 3 4D si ui

1

2

dj 25 50 30 15

vj

80

40

25 50 5

25 15

10 40 15 −15

0

15

Z = 3075

+15

−5 −30

Variabile entrante x22, variabile uscente x23, celle riceventi x22 e x13, celledonatrici x12 e x23, quantita donata 25.

10 40 15 0

20 25 30 0

1 2 3 4D si ui

1

2

dj 25 50 30 15

vj

80

40

25 25 30

25 15

10 40 15 15

0

−15

Z = 2625

−15

+25 +30



10 40 15 0

20 25 30 0

1 2 3 4D si ui

1

2

dj 25 50 30 15

vj

80

40

25 10 30

40

15

10 40 15 0

0

−15

Z = 2400

+15+25 +30

Soluzione ottima e il vettore (25, 10, 30, 15, 0, 40, 0, 0) ed il valore minimo delcosto e Z = 2400.Esercizio. Risolvere il problema del trasporto con 2 sorgenti, con offertarispettivamente 60 e 40 e 4 destinazioni con domanda 25, 15, 28 e 32 ematrice dei costi

C =

[

20 40 20 1030 20 60 10

]

.

Svolgimento. Scriviamo la tabella dei dati e applichiamo la regola di Nord-Ovest per trovare la BFS iniziale:

20 40 20 10

30 20 60 10

1 2 3 4 si ui

1

2

dj 25 15 28 32

vj

60

40

25 15 20

8 32

20 40 20 −30

0

40

Z = 2300

+40

−30 −60



20 40 20 10

30 20 60 10

1 2 3 4 si ui

1

2

dj 25 15 28 32

vj

60

40

25 7 28

8 32

20 40 20 30

0

−20

Z = 1820

−20

+30 +60


20 40 20 10

30 20 60 10

1 2 3 4 si ui

1

2

dj 25 15 28 32

vj

60

40

25

15

28

25

7

20 20 20 10

0

0

Z = 1680

+20

+10 +40

La soluzione ottima e il vettore (25, 0, 28, 7, 0, 15, 0, 25) ed il valore minimodel costo e Z = 1680.Esercizio. Si vuole risolvere il problema del trasporto con tre sorgenti, conofferta rispettivamente 20, 60 e 30 e tre destinazioni con domanda 15, 50 e10. La matrice dei costi e la seguente

C =

4 3 21 5 −1 2 4

.

Si vogliono determinare le quantita di merci da inviare dalle sorgenti alledestinazioni affinche il costo sia minimo.Svolgimento. Innanzitutto osserviamo che

∑

i

si = 110,∑

j

dj = 75,


quindi e necessario introdurre una destinazione fittizia, 4D, che serva adassorbire l’offerta eccedente pari a 35. I costi relativi a tale destinazionesaranno posti tutti uguali a zero. Inoltre si deve mettere in evidenza che lasorgente 2 non deve inviare merce alla destinazione 3, pertanto dobbiamointrodurre una penalizzazione per la variabile x23 ponendo c23 = M. Lamatrice dei costi diviene pertanto la seguente:

C =

4 3 2 01 5 M 01 2 4 0

.

Scriviamo la tabella dei dati e applichiamo la regola di Nord-Ovest per trovarela BFS iniziale:

4 3 2 0

1 5 M 0

1 2 4 0

1 2 3 4D si ui

1

2

3

dj 15 50 10 35

vj

20

60

30

15 5

45 10 5

30

6 5 M 0

−2

0

0

−5

−5 −3

4 − M

4 − M

+2

Z = 300 + 10M



4 3 2 0

1 5 M 0

1 2 4 0

1 2 3 4D si ui

1

2

3

dj 15 50 10 35

vj

20

60

30

15 5

45

10

15

20

6 5 4 0

−2

0

0

−5

−5 −3

0

M − 4

+2

Z = 340


4 3 2 0

1 5 M 0

1 2 4 0

1 2 3 4D si ui

1

2

3

dj 15 50 10 35

vj

20

60

30

15

20

30

10

15

20

1 5 4 0

−2

0

0

+5

0 −3

0

M − 4

+2

Z = 265



4 3 2 0

1 5 M 0

1 2 4 0

1 2 3 4D si ui

1

2

3

dj 15 50 10 35

vj

20

60

30

15

20

10

20 10

35

1 5 7 0

−2

0

−3

+5

+3

−3

M − 7

+6

+3

Z = 205


4 3 2 0

1 5 M 0

1 2 4 0

1 2 3 4D si ui

1

2

3

dj 15 50 10 35

vj

20

60

30

15

10

10

30

10

35

1 5 4 0

−2

0

−3

+5

+3

M − 4

+3

+2

+3

Z = 175

La soluzione ottima e il vettore (0, 10, 10, 0, 15, 10, 0, 35, 0, 30, 0, 0) ed il valoreminimo del costo e Z = 175.Esercizio. Si consideri un problema del trasporto con 3 nodi sorgente, cias-cuno con offerta pari a 20 e 3 destinazioni con domanda 10, 15 e 35. Lamatrice dei costi e la seguente

C =

1 3 25 4 11 2 3

.


Si vuole determinare le quantita di merci da inviare dai nodi sorgente a quellidestinazione affinche il costo sia minimo.Svolgimento.

1 3 2

5 4 1

1 2 3

1 2 3 si ui

1

2

3

dj 10 15 35

20

20

20

vj

10 10

5 15

20

Z = 135

1 3 0

0

1

3

+3

−3 −4

+2


1 3 2

5 4 1

1 2 3

1 2 3 si ui

1

2

3

dj 10 15 35

20

20

20

vj

10 10

5

20

15

Z = 115

1 3 4

0

−3

−1

+1

+1

+4

−2



1 3 2

5 4 1

1 2 3

1 2 3 si ui

1

2

3

dj 10 15 35

20

20

20

vj

10

15

10

20

5

Z = 95

1 1 2

0

−1

1

+5

−1

+2

+4


1 3 2

5 4 1

1 2 3

1 2 3 si ui

1

2

3

dj 10 15 35

20

20

20

vj

5

5 15

15

20

Z = 90

1 2 2

0

−1

0

+5

+1

+1

+3

La soluzione ottima e il vettore (5, 0, 15, 0, 0, 20, 5, 15, 0) ed il valore minimodel costo e Z = 90.Esercizio. Risolvere il problema del trasporto con 3 origini, 4 destinazioni,definito dalla seguente matrice dei costi:

C =

4 2 1 35 1 2 23 2 1 3

.

con offerta pari rispettivamente a 30, 40 e 30 e domanda 20, 30, 40 e 10,ed utilizzando il metodo di approssimazione di Russell per trovare la BFS


iniziale.Svolgimento.

4 2 1 3

5 1 2 2

3 2 1 3

1 2 3 4 si ui

1

2

3

dj 20 30 40 10

vj

30

40

30

−5

−5

−5

−4

−6

−3

−5

−5

−5

−4

−6

−3

5 2 2 3

4

5

3

Scegliamo x24 = 10 e cancelliamo la quarta colonna.

4 2 1

5 1 2

3 2 1

1 2 3 si ui

1

2

3

dj 20 30 40

30

30

30

vj

−5

−5

−5

−4

−6

−3

−5

−5

−4

5 2 2

4

5

3

Scegliamo x22 = 30 e cancelliamo la seconda riga.


4 2 1

3 2 1

1 2 3 si ui

1

2

dj 20 0 40

30

30

vj

−4

−4

−4

−3

−4

−3

4 2 1

4

3

Scegliamo x13 = 30 e cancelliamo la prima riga, cosicche le altre variabili inbase sono quelle restanti, cioe x31 = 20, x32 = 0 e x33 = 10.La BFS trovata applicando il metodo di Russell e (0, 0, 30, 0, 0, 30, 0, 10, 20, 0, 10, 0),ora risolviamo il problema del trasporto con il metodo del simplesso.

4 2 1 3

5 1 2 2

3 2 1 3

1 2 3 4 si ui

1

2

3

dj 20 30 40 10

vj

30

40

3020

30

0

30

10

10

3 2 1 3

0

−1

0

+1

+3

0

+2

0

0

Z = 150

La BFS trovata con il metodo di Russell coincide con la soluzione ottima.Esercizio. Trovare la BFS iniziale del problema di trasporto definito dallaseguente matrice dei costi

C =

1 6 55 4 13 3 4

.

e con offerte pari rispettivamente a 10, 50 e 20 e domande 30, 40 e 10,utilizzando i metodi di Vogel e di Russell.Svolgimento. Applicando il metodo di Vogel si ha la seguente situazioneiniziale


Destinazioni1 2 3 si Differ. Righe

Sorgenti 1 1 6 5 10 42 5 4 1 50 33 3 3 4 20 0dj 30 40 10

Diff. Col. 2 1 3

Si sceglie come variabile in base x11, si pone x11 = 10 e si cancella la primariga.


Sorgenti 2 5 4 1 50 33 3 3 4 20 0dj 20 40 10

Diff. Col. 2 1 3

Si sceglie come variabile in base x23, si pone x23 = 10 e si cancella la terzacolonna.

Destinazioni1 2 si Differ. Righe

Sorgenti 2 5 4 40 13 3 3 20 0dj 20 40

Diff. Col. 2 1

Si sceglie come variabile in base x31, si pone x31 = 20 e si cancella la primacolonna.

Destinazioni2 si Differ. Righe

Sorgenti 2 4 40 −3 3 0 −dj 40

Diff. Col. −

Le restanti variabili in base sono x22 = 40 e x32 = 0.La BFS trovata con il metodo di Vogel e:

(10, 0, 0, 0, 40, 10, 20, 0, 0).


Per applicare il metodo di Russell scriviamo la consueta tabella:

1 6 5

5 4 1

3 3 4

1 2 3 si ui

1

2

3

dj 30 40 10

10

50

20

vj

−10

−5

−6

−6

−7

−7

−6

−9

−5

5 6 5

6

5

4

Scegliamo x11 = 10 e cancelliamo la prima riga.

5 4 1

3 3 4

1 2 3 si ui

2

3

dj 20 40 10

50

20

vj

−5

−6

−5

−5

−8

−4

5 4 4

5

4

Scegliamo x23 = 10 e cancelliamo la terza colonna.

5 4

3 3

1 2 si ui

2

3

dj 20 40

40

20

vj

−5

−5

−5

−4

5 4

5

3


Scegliamo x31 = 20, cancelliamo la prima colonna, in modo tale che le vari-abili rimaste sono entrambe in base: x22 = 40 e x32 = 0.La BFS trovata con il metodo di Russell e:

(10, 0, 0, 0, 40, 10, 20, 0, 0).

Osserviamo che i due metodi hanno fornito la stessa soluzione iniziale.Esercizio. Trovare la BFS iniziale del problema di trasporto definito dallaseguente matrice dei costi

C =

4 5 74 4 54 4 4

.

e con offerte pari rispettivamente a 100, 110 e 90 e domande 95, 85 e 120,utilizzando i metodi di Vogel e di Russell.Svolgimento. Applicando il metodo di Vogel si ha la seguente situazioneiniziale


Sorgenti 1 4 5 7 100 12 4 4 5 110 03 4 4 4 90 0dj 95 85 120

Diff. Col. 0 0 1

Si sceglie come variabile in base x33, si pone x33 = 90 e si cancella la terzariga.


Sorgenti 1 4 5 7 100 12 4 4 5 110 0dj 95 85 30

Diff. Col. 0 1 2

Si sceglie come variabile in base x23, si pone x23 = 30 e si cancella la terzacolonna.


Destinazioni1 2 si Differ. Righe

Sorgenti 1 4 5 100 12 4 4 80 0dj 95 85

Diff. Col. 0 1

Si sceglie come variabile in base x11, si pone x11 = 95 e si cancella la primacolonna, quindi le restanti variabili in base sono x12 = 5 e x22 = 80.La BFS trovata con il metodo di Vogel e:

(95, 5, 0, 0, 80, 30, 0, 0, 90).

Per applicare il metodo di Russell scriviamo la tabella:

4 5 7

4 4 5

4 4 4

1 2 3 si ui

1

2

3

dj 95 85 120

100

110

90

vj

−7

−7

−4

−7

−6

−5

−7

−7

−7

4 5 7

7

5

4

Scegliamo x11 = 95 e cancelliamo la prima colonna.

5 7

4 5

4 4

2 3 si ui

1

2

3

dj 85 120

5

110

90

vj

−7

−6

−5

−7

−7

−7

5 7

7

5

4


Scegliamo x33 = 90 e cancelliamo la terza riga.

5 7

4 5

2 3 si ui

1

2

dj 85 30

5

110

vj

−7

−6

−7

−7

5 7

7

5

Scegliamo x23 = 30, cancelliamo la terza colonna, in modo tale che le variabilirimaste sono entrambe in base: x24 = 80 e x12 = 5.La BFS trovata con il metodo di Russell e:

(95, 5, 0, 0, 80, 30, 0, 0, 90).

2.2 Il problema di assegnamento

Esercizio. Trovare l’assegnamento ottimo per il problema definito dallaseguente matrice dei costi, usando il metodo ungherese:

C =

8 8 5 79 7 3 89 8 4 86 6 5 6

.

Svolgimento.

8

9

9

6

8

7

8

6

5

3

4

5

7

8

8

6

Tabella iniziale

3

6

5

1

3

4

4

1

0

0

0

0

2

5

4

1

Si sottrae il minimo da ogni riga


2

5

4

0

2

3

3

0

0

0

0

0

1

4

3

0

Si sottrae il minimo da ogni colonna

2

5

4

0

2

3

3

0

0

0

0

0

1

4

3

0

Gli elementi uguali a zero cono coperti da due linee

1

4

3

0

1

2

2

0

0

0

0

1

0

3

2

0

Si sottrae 1 da tutti gli elementi non copertiSi aggiunge 1 all’elemento coperto da due linee

1

4

3

0

1

2

2

0

0

0

0

1

0

3

2

0

Gli elementi uguali a zero cono coperti da tre linee


1

2

1

0

1

0

0

0

2

0

0

3

0

1

0

0

Si sottrae 2 da tutti gli elementi non copertiSi aggiunge 2 agli elementi coperti da due linee

1

2

1

0

1

0

0

0

2

0

0

3

0

1

0

0

Gli elementi uguali a zero cono coperti da 4 lineeL’assegnamento ottimo e possibile

1

2

1

0

1

0

0

0

2

0

0

3

0

1

0

0

Poniamo x14 = 1

1

2

1

0

1

0

0

0

2

0

0

3

0

1

0

0

Poniamo x41 = 1


1

2

1

0

1

0

0

0

2

0

0

3

0

1

0

0

Poniamo x22 = 1 e x33 = 1.

Il valore della funzione obiettivo nella soluzione ottima e

Z = 7 + 7 + 4 + 6 = 24.

Esercizio. Risolvere il problema di assegnamento definito dalla seguentematrice dei costi:

C =

6 4 2 1 −3 − 4 4 2− 6 6 4 27 4 5 1 16 3 2 2 26 4 5 6 4

.

Svolgimento. Innanzitutto dobbiamo aggiungere una colonna alla matricedei costi ed inserire il valore M per i costi non definiti:

C =

6 4 2 1 M 03 M 4 4 2 0M 6 6 4 2 07 4 5 1 1 06 3 2 2 2 06 4 5 6 4 0

.

Applichiamo il metodo ungherese a tale problema:


6

3

M

7

6

6

4

M

6

4

3

4

2

4

6

5

2

5

1

4

4

1

2

6

M

2

2

1

2

4

0

0

0

0

0

0

Tabella iniziale

3

0

M

4

3

3

1

M

3

1

0

1

0

2

4

3

0

3

0

3

3

0

1

5

M

1

1

0

1

3

0

0

0

0

0

0

Matrice ottenuta sottraendo ilminimo da tutte le colonne

Il numero minimo di linee che coprono gli elementi uguali a zero e 5, comesi evince dalla seguente figura:

3

0

M

4

3

3

1

M

3

1

0

1

0

2

4

3

0

3

0

3

3

0

1

5

M

1

1

0

1

3

0

0

0

0

0

0

Eseguiamo quindi un’altra iterazione, sottraendo 1 dagli elementi non copertie sommandolo agli elementi coperti da due linee:


3

0

M

4

3

2

1

M

2

1

0

0

0

2

3

3

0

2

0

3

2

0

1

4

M

1

0

0

1

2

1

1

0

1

1

0

Ora e possibile effettuare l’assegnamento ottimo:

3

0

M

4

3

2

1

M

2

1

0

0

0

2

3

3

0

2

0

3

2

0

1

4

M

1

0

0

1

2

1

1

0

1

1

0

x21 = 1

3

0

M

4

3

2

1

M

2

1

0

0

0

2

3

3

0

2

0

3

2

0

1

4

M

1

0

0

1

2

1

1

0

1

1

0

x13 = 1

3

0

M

4

3

2

1

M

2

1

0

0

0

2

3

3

0

2

0

3

2

0

1

4

M

1

0

0

1

2

1

1

0

1

1

0

x52 = 1

3

0

M

4

3

2

1

M

2

1

0

0

0

2

3

3

0

2

0

3

2

0

1

4

M

1

0

0

1

2

1

1

0

1

1

0

x66 = 1


3

0

M

4

3

2

1

M

2

1

0

0

0

2

3

3

0

2

0

3

2

0

1

4

M

1

0

0

1

2

1

1

0

1

1

0

x35 = 1

3

0

M

4

3

2

1

M

2

1

0

0

0

2

3

3

0

2

0

3

2

0

1

4

M

1

0

0

1

2

1

1

0

1

1

0

x44 = 1

La soluzione ottima e la seguente

X =

0 0 1 0 0 01 0 0 0 0 00 0 0 0 1 00 0 0 1 0 00 1 0 0 0 00 0 0 0 0 1

mentre il costo minimo e

Z = 3 + 2 + 3 + 2 + 1 = 11.

Esercizio. Risolvere il problema di assegnamento con 5 task e 5 risorsedefinito dalla seguente matrice dei costi:

C =

5 4 6 5 43 7 4 6 35 2 3 2 36 4 4 3 27 3 2 3 3

.

Svolgimento. Applichiamo il metodo ungherese a tale problema:


5

3

5

6

7

4

7

2

4

3

6

4

3

4

2

5

6

2

3

3

4

3

3

2

3

Tabella iniziale

1

0

3

4

5

0

4

0

2

1

2

1

1

2

0

1

3

0

1

1

0

0

1

0

1

Matrice ottenuta sottraendo ilminimo da tutte le righe

Non si procede a togliere il minimo da ogni colonna in quanto tale valore ezero. Inoltre poiche il numero minimo di linee che coprono gli elementi ugualia zero e uguale a cinque allora si puo procedere all’assegnamento ottimo.

1

0

3

4

5

0

4

0

2

1

2

1

1

2

0

1

3

0

1

1

0

0

1

0

1

x21 = 1

1

0

3

4

5

0

4

0

2

1

2

1

1

2

0

1

3

0

1

1

0

0

1

0

1

x53 = 1

1

0

3

4

5

0

4

0

2

1

2

1

1

2

0

1

3

0

1

1

0

0

1

0

1

x45 = 1

1

0

3

4

5

0

4

0

2

1

2

1

1

2

0

1

3

0

1

1

0

0

1

0

1

x12 = 1


1

0

3

4

5

0

4

0

2

1

2

1

1

2

0

1

3

0

1

1

0

0

1

0

1

x34 = 1


X =

0 1 0 0 01 0 0 0 00 0 0 1 00 0 0 0 10 0 1 0 0


Z = 4 + 3 + 2 + 2 + 2 = 13.

Esercizio. Risolvere il problema di assegnamento definito dalla seguentematrice dei costi:

C =

6 3 − 4 5 64 2 1 6 5 67 4 3 3 2 42 1 10 8 4 57 5 6 4 3 2

.

Svolgimento. Innanzitutto dobbiamo aggiungere una colonna alla matricedei costi ed inserire il valore M per i costi non definiti:

C =

6 3 M 4 5 64 2 1 6 5 67 4 3 3 2 42 1 10 8 4 57 5 6 4 3 20 0 0 0 0 0

.

Applichiamo il metodo ungherese a tale problema:


6

4

7

2

7

0

3

3

4

1

5

0

M

1

3

10

6

0

4

6

3

8

4

0

5

5

2

4

3

0

6

6

4

5

2

0

Tabella iniziale

3

3

5

1

5

0

0

2

2

0

3

0

M

0

1

9

4

0

1

5

1

7

2

0

2

4

0

3

1

0

3

5

1

4

0

0

Matrice ottenuta sottraendo ilminimo da tutte le righe

Non si procede a togliere il minimo da ogni colonna in quanto tale valore ezero. Inoltre poiche il numero minimo di linee che coprono gli elementi ugualia zero e uguale a cinque, come risulta dalla seguente figura

3

3

5

1

5

0

0

2

2

0

3

0

M

0

1

9

4

0

1

5

1

7

2

0

2

4

0

3

1

0

3

5

1

4

0

0

allora e necessario procedere ad un’altra iterazione.


2

2

4

0

4

0

0

2

2

0

3

1

M

0

1

9

4

1

0

4

0

6

1

0

2

4

0

3

1

1

3

5

1

4

0

1

Poiche il numero minimo di linee che coprono gli elementi uguali a zero euguale a sei allora e possibile effettuare l’assegnamento ottimo.

2

2

4

0

4

0

0

2

2

0

3

1

M

0

1

9

4

1

0

4

0

6

1

0

2

4

0

3

1

1

3

5

1

4

0

1

x56 = 1

2

2

4

0

4

0

0

2

2

0

3

1

M

0

1

9

4

1

0

4

0

6

1

0

2

4

0

3

1

1

3

5

1

4

0

1

x35 = 1

2

2

4

0

4

0

0

2

2

0

3

1

M

0

1

9

4

1

0

4

0

6

1

0

2

4

0

3

1

1

3

5

1

4

0

1

x23 = 1

2

2

4

0

4

0

0

2

2

0

3

1

M

0

1

9

4

1

0

4

0

6

1

0

2

4

0

3

1

1

3

5

1

4

0

1

x12 = 1


2

2

4

0

4

0

0

2

2

0

3

1

M

0

1

9

4

1

0

4

0

6

1

0

2

4

0

3

1

1

3

5

1

4

0

1

x41 = 1

2

2

4

0

4

0

0

2

2

0

3

1

M

0

1

9

4

1

0

4

0

6

1

0

2

4

0

3

1

1

3

5

1

4

0

1

x64 = 1


X =

0 1 0 0 0 00 0 1 0 0 00 0 0 0 1 01 0 0 0 0 00 0 0 0 0 10 0 0 1 0 0


Z = 3 + 1 + 2 + 2 + 2 = 10.

Capitolo 3

L’algoritmo di

Branch-and-Bound

3.1 Problemi di programmazione binaria

Esercizio. Risolvere il seguente problema di programmazione lineare bina-ria:

max Z = 9x1 + 5x2 + 6x3

−x1 +3x3 ≤ 12x2 −x3 ≤ 1

xj variabile binaria per j = 1, 2, 3.

Svolgimento. Il primo passo dell’algoritmo e quello di risolvere il rilassamentolineare del problema completo:

max Z = 9x1 + 5x2 + 6x3

(1) −x1 +3x3 ≤ 1(2) 2x2 −x3 ≤ 1(3) x1 ≤ 1(4) x2 ≤ 1(5) x3 ≤ 1

x1, x2, x3 ≥ 0.

Applichiamo il metodo del simplesso introducendo 5 variabili slack.

51

CAPITOLO 3. L’ALGORITMO DI BRANCH-AND-BOUND 52

Iterazione 0

Var.base Eq. Z x1 x2 x3 x4 x5 x6 x7 x8 bi

Z

x4

x5

x6

x7

x8

(0)

(1)

(2)

(3)

(4)

(5)

1

0

0

0

0

0

−9

−1

0

1

0

0

−5

0

2

0

1

0

−6

3

−1

0

0

1

0

1

0

0

0

0

0

0

1

0

0

0

0

0

0

1

0

0

0

0

0

0

1

0

0

0

0

0

0

1

0

1

1

1

1

1

Iterazione 1


Z

x4

x5

x1

x7

x8

(0)

(1)

(2)

(3)

(4)

(5)

1

0

0

0

0

0

0

0

0

1

0

0

−5

0

2

0

1

0

−6

3

−1

0

0

1

0

1

0

0

0

0

0

0

1

0

0

0

9

1

0

1

0

0

0

0

0

0

1

0

0

0

0

0

0

1

9

2

1

1

1

1


Iterazione 2


Z

x3

x5

x1

x7

x8

(0)

(1)

(2)

(3)

(4)

(5)

1

0

0

0

0

0

0

0

0

1

0

0

−5

0

2

0

1

0

0

1

0

0

0

0

2

1

3

1

3

0

0

−1

3

0

0

1

0

0

0

11

1

3

1

3

1

0

−1

3

0

0

0

0

1

0

0

0

0

0

0

1

13

2

3

5

3

1

1

1

3

Iterazione 3


Z

x3

x2

x1

x7

x8

(0)

(1)

(2)

(3)

(4)

(5)

1

0

0

0

0

0

0

0

0

1

0

0

0

0

1

0

0

0

0

1

0

0

0

0

17

6

1

3

1

6

0

−1

6

−1

3

5

2

0

1

2

0

−1

2

0

71

6

1

3

1

6

1

−1

6

−1

3

0

0

0

0

1

0

0

0

0

0

0

1

103

6

2

3

5

6

1

1

6

1

3

Soluzione e (1, 5/6, 2/3, 0, 0, 0, 1/6, 1/3) con valore della funzione obiettivoZ = 103/6 = 17 + 1/6. Poiche la funzione obiettivo deve assumere un valorereale, possiamo assumere Z = 17 come valore ottimo del rilassamento lineare.


Consideriamo x1 come variabile di branching e definiamo i due sottoproblemi:

Sottoproblema 1

Fissiamo x1 = 1max Z = 5x2 + 6x3 + 9

3x3 ≤ 22x2 −x3 ≤ 1

x2, x3 variabili binarie

eSottoproblema 2

Fissiamo x1 = 0max Z = 5x2 + 6x3

3x3 ≤ 12x2 −x3 ≤ 1

x2, x3 variabili binarie

Poiche nella soluzione ottima del rilassamento lineare del problema completoil valore della variabile di branching x1 e 1, si puo naturalmente dedurre chela soluzione ottima del sottoproblema 1 e la stessa di quello completo.Per risolvere il sottoproblema 2 consideriamo che il primo vincolo viene sod-disfatto solo se x3 = 0, per cui deve essere necessariamente x2 = 0. In questocaso la soluzione ottima e (0, 0, 0), soluzione binaria, quindi il sottoproblemaviene tagliato applicando il terzo criterio di fathoming e Z∗ = 0 diviene lasoluzione incombente. Poiche esiste un sottoproblema che non e stato taglia-to allora scegliamo la successiva variabile di branching, cioe x2, e definiamoi seguenti sottoproblemi.

Sottoproblema 3

Fissiamo x2 = 1max Z = 6x3 + 14

3x3 ≤ 2−x3 ≤ −1

x3 variabile binaria,

eSottoproblema 4

Fissiamo x2 = 0max Z = 6x3 + 9

3x3 ≤ 2−x3 ≤ 1

x3 variabile binaria.


Il sottoproblema 3 non ammette soluzione ammissibile quindi viene taglia-to applicando il secondo criterio di fathoming. Il sottoproblema 2 inveceammette x3 = 0 come soluzione ammissibile cui corrisponde il valore dellafunzione obiettivo Z = 9. Soluzione completa e (1, 0, 0), con valore dellafunzione obiettivo Z = 9, che diventa la nuova soluzione incombente. Il sot-toproblema viene quindi tagliato applicando il terzo criterio di fathoming e,non essendoci alcun altro sottoproblema da risolvere la soluzione incombentee quella ottima. Riassumiamo la soluzione del problema nel seguente alberodelle soluzioni.

Completo Z = 17(1, 5/6, 2/3)

1 0 Z∗ = 0(0, 0, 0)

F(3)

1 0

x1

x2

F(2) F(3)

Z = 17(1, 5/6, 2/3)

Z∗ = 9(1, 0, 0)

Esercizio. Cosndiderara il seguente vincolo su variabili binarie:

5x1 + 4x2 + 2x3 + 9x4 ≤ 10.

Individuare i vertici ammissibili e l’insieme delle coperture minime che i ver-tici ammissibili soddisfano come uguaglianze.Svolgimento. I possibili vertici sono 16, elencandoli e verificando se sod-disfano o meno il vincolo assegnato si scopre che quelli ammissibili sono


8:vertici ammissibili vertici non ammissibili

(0, 0, 0, 0) (0, 0, 1, 1)(0, 0, 0, 1) (0, 1, 0, 1)(0, 0, 1, 0) (0, 1, 1, 1)(0, 1, 0, 0) (1, 0, 0, 1)(0, 1, 1, 0) (1, 0, 1, 1)(1, 0, 0, 0) (1, 1, 0, 1)(1, 0, 1, 0) (1, 1, 1, 0)(1, 1, 0, 0) (1, 1, 1, 1)

Considerando prima gli insiemi composti da due variabili e poi quelli com-posti da tre, si scopre che i seguenti insiemi sono coperture minime

{x1, x4} {x2, x4} {x3, x4} {x1, x2, x3}.

Di conseguenza i vincoli sono i seguenti:

x1 + x4 ≤ 1 x2 + x4 ≤ 1x3 + x4 ≤ 1 x1 + x2 + x3 ≤ 2.

Verifichiamo ora che i vertici ammissibili appartengono alla frontiera di al-meno uno dei quattro vincoli definiti dalle coperture minime, come si evincedalla presente tabella:

Vertici Appartenenza ai Vincoliammissibili x1 + x4 ≤ 1 x2 + x4 ≤ 1 x3 + x4 ≤ 1 x1 + x2 + x3 ≤ 2(0, 0, 0, 0) no no no no(0, 0, 0, 1) si si si no(0, 0, 1, 0) no no si no(0, 1, 0, 0) no si no no(0, 1, 1, 0) no si si si(1, 0, 0, 0) si no no no(1, 0, 1, 0) si no si si(1, 1, 0, 0) si si no si


3.2 Problemi di programmazione intera e mista

Esercizio. Risolvere il seguente problema di programmazione lineare interamista:

max Z = 3x1 + 5x2 + x3

2x1 +x3 ≤ 6x1 +2x2 +x3 ≤ 8

x1, x2, x3 ≥ 0x1, x2 variabili intere.

Svolgimento. Poniamo innanzitutto Z∗ = −∞ come prima soluzione in-combente. Il primo passo dell’algoritmo e quello di risolvere il rilassamen-to lineare del problema completo, cancellando il vincolo di interezza delleviariabili.

Tableau iniziale


Z

x4

x5

(0)

(1)

(2)

1

0

0

−3

2

1

−5

0

2

−1

1

1

0

1

0

0

0

1

0

6

8

Iterazione 1


Z

x4

x2

(0)

(1)

(2)

1

0

0

−1

2

2

1

2

0

0

1

3

2

1

1

2

0

1

0

5

2

0

1

2

20

6

4


Iterazione 2


Z

x1

x2

(0)

(1)

(2)

1

0

0

0

1

0

0

0

1

7

4

1

2

1

4

1

4

1

2

−1

2

5

2

0

1

2

43

2

3

5

2

Soluzione e (3, 5/2, 0) mentre il valore della funzione obiettivo e Z = 43/2.Scegliamo x2 come variabile di branching in quanto e la prima variabile interaa non avere un valore intero nella soluzione del rilassamento lineare. La parteintera del valore di x2 e 2 quindi definiamo due sottoproblemi, uno con ilvincolo:

x2 ≤ 2

e l’altro conx2 ≥ 3.

Riscriviamo i due sottoproblemi:

Sottoproblema 1

max Z = 3x1 + 5x2 + x3

2x1 +x3 ≤ 6x1 +2x2 +x3 ≤ 8

x2 ≤ 2

x1, x2, x3 ≥ 0

eSottoproblema 2

max Z = 3x1 + 5x2 + x3

2x1 +x3 ≤ 6x1 +2x2 +x3 ≤ 8

x1, x3 ≥ 0, x2 ≥ 3.

Risolviamo il Sottoproblema 1 con il metodo del simplesso introducendo 3variabili slack.


Iterazione 0


Z

x4

x5

x6

(0)

(1)

(2)

(3)

1

0

0

0

−3

2

1

0

−5

0

2

1

−1

1

1

0

0

1

0

0

0

0

1

0

0

0

0

1

0

6

8

2

Iterazione 1


Z

x4

x5

x2

(0)

(1)

(2)

(3)

1

0

0

0

−3

2

1

0

0

0

0

1

−1

1

1

0

0

1

0

0

0

0

1

0

5

0

−2

1

10

6

4

2

Iterazione 2


Z

x1

x5

x2

(0)

(1)

(2)

(3)

1

0

0

0

0

1

0

0

0

0

0

1

1

2

1

2

1

2

0

3

2

1

2

−1

2

0

0

0

1

0

5

0

−2

1

19

3

5

2

2

Soluzione e (3, 2, 0) mentre il valore della funzione obiettivo e Z = 19. Ilproblema soddisfa il terzo criterio di fathoming e viene tagliato, mentre ilvalore della funzione obiettivo diventa la nuova soluzione incombente:

Z∗ = 19.


Per risolvere il sottoproblema 2 si deve effettuare il seguente cambio divariabile

x′

2= x2 − 3 ⇒ x2 = x′

2+ 3, x′

2≥ 0,

cosicche il sottoproblema puo essere riscritto nel seguente modo:

max Z = 3x1 + 5(x′

2+ 3) + x3

2x1 +x3 ≤ 6x1 +2(x′

2+ 3) +x3 ≤ 8

x1, x′

2, x3 ≥ 0,

ovveromax Z = 3x1 + 5x′

2+ x3 + 15

2x1 +x3 ≤ 6x1 +2x′

2+x3 ≤ 2

x1, x2, x′

3≥ 0.

Applichiamo il metodo del simplesso introducendo due variabili slack.

Iterazione 0

Var.base Eq. Z x1 x′

2x3 x4 x5 bi

Z

x4

x5

(0)

(1)

(2)

1

0

0

−3

2

1

−5

0

2

−1

1

1

0

1

0

0

0

1

15

6

2

Iterazione 1


2x3 x4 x5 bi

Z

x4

x′

2

(0)

(1)

(2)

1

0

0

−1

2

2

1

2

0

0

1

3

2

1

1

2

0

1

0

5

2

0

1

2

20

6

1


Iterazione 2


2x3 x4 x5 bi

Z

x4

x1

(0)

(1)

(2)

1

0

0

0

0

1

1

−4

2

2

−1

1

0

1

0

3

−1

2

21

4

2

Soluzione e (2, 0, 0), cioe (2, 3, 0), mentre il valore della funzione obietti-vo e Z = 21. Il problema soddisfa il terzo criterio di fathoming e vienetagliato mentre il valore della funzione obiettivo diventa la nuova soluzioneincombente:

Z∗ = 21.

Inoltre poiche non ci sono altri sottoproblemi da risolvere la soluzione in-combente appena trovata e anche quella ottima. Possiamo scrivere pertantoil seguente albero delle soluzioni:

Completo Z = 21.5(3, 5/2, 0)

x2 ≤ 2 x2 ≥ 3Z∗ = 19(3, 2, 0)

F(3)

Z∗ = 21(2, 3, 0)

F(3)

Capitolo 4

Esercizi di Ottimizzazione su

Reti

4.1 Il problema di minimo albero ricoprente

Esercizio. Sia assegnata una rete non orientata composta da 7 nodi indi-viduati con lettere da A a G, tale che le distanze tra i questi sono riportatenella seguente tabella:

A B C D E F GA 10 8 6 4 4 5B 10 11 10 4 5C 7 4 10 6D 3 7 2E 8 5F 6

Svolgimento. Identifichiamo innanzitutto il collegamento piu breve, cioeDG, quindi questo e il primo arco dell’albero che stiamo cercando

62

CAPITOLO 4. ESERCIZI DI OTTIMIZZAZIONE SU RETI 63

D

G

2

Il nodo piu vicino a D o a G e in nodo E, quindi l’arco DE viene aggiuntoall’albero.

D

G

E

2

3

I nodi piu vicini sono C e A, entrambi connessi a E, scegliamo l’arco EC.


D

G

E

C

2

3 4

E adesso scegliamo l’arco EA:

D

G

E A

C

2

3

4

4

Adesso si sceglie il nodo F , connesso al nodo A da un arco di lunghezza 4.


D

G

E A

C

F

2

3

4

4

4

Resta il nodo B il cui collegamento piu vicino e con il nodo F .

D

G

E A

C

F

B

2

3

4

4

4

4

4.2 Il problema di cammino minimo

Esercizio. Determinare il cammino minimo della seguente rete che unisce inodi O e T :


F

D

E

C

A

B

O H

G

I

T8 2 6 8

3 4

7 6

5

6

2

3

1

39

5

2

2

5

4

4

6


k

Nodi sceltidirettamente

connessi ai nodinon scelti

Nodicandidati

Distanzatotale

k−esimonodovicino

Distanzaminima

Ultimoarco

1 O B 4 B 4 OB

2 O A 5 A 5 OAB C 4 + 5 = 9

3 O C 8 C 8 OCA D 3 + 5 = 8 D ADB C 4 + 5 = 9

4 B E 4 + 7 = 11 F 10 CFC F 8 + 2 = 10D F 8 + 3 = 11

5 B E 4 + 7 = 11 E 11 BEC E 8 + 6 = 14D G 8 + 4 = 12F G 10 + 2 = 12

6 D G 8 + 4 = 12 G 12 DGF G 10 + 2 = 12 FGE H 11 + 2 = 13

7 F H 10 + 6 = 16 H 13 EHE H 11 + 2 = 13

G H 12 + 3 = 15

8 E I 11 + 6 = 17 I 17 EIG T 12 + 9 = 21H T 13 + 8 = 21

9 G T 12 + 9 = 21 T 21 GTH T 13 + 8 = 21 HTI T 17 + 5 = 22

Abbiamo trovato tre possibili cammini minimi di lunghezza 21:

O −→ A −→ D −→ G −→ TO −→ C −→ F −→ G −→ TO −→ B −→ E −→ H −→ T.


Esercizio. Determinare il cammino minimo della stessa rete dell’esercizioprecedente supponendo che gli archi non siano orientati:

F

D

E

C

A

B

O H

G

I

T8 2 6 8

3 4

7 6

5

6

2

3

1

39

5

2

2

5

4

4

6


k



Nodicandidati

Distanzatotale

k−esimonodovicino

Distanzaminima

Ultimoarco

1 O B 4 B 4 OB

2 O A 5 A 5 OAB C 4 + 5 = 9

3 O C 8 C 8 OCA D 3 + 5 = 8 D ADB C 4 + 5 = 9

4 B E 4 + 7 = 11 F 10 CFC F 8 + 2 = 10D F 8 + 3 = 11

5 B E 4 + 7 = 11 E 11 BEC E 8 + 6 = 14 FED G 8 + 4 = 12F E 10 + 1 = 11

6 D G 8 + 4 = 12 G 12 DGF G 10 + 2 = 12 FGE H 11 + 2 = 13

7 F H 10 + 6 = 16 H 13 EHE H 11 + 2 = 13

G H 12 + 3 = 15

8 E I 11 + 6 = 17 I 15 HIG T 12 + 9 = 21H I 13 + 2 = 15

9 G T 12 + 9 = 21 T 20 ITH T 13 + 8 = 21I T 15 + 5 = 20

Abbiamo trovato due possibili cammini minimi di lunghezza 20:

O −→ B −→ E −→ H −→ I −→ TO −→ C −→ F −→ E −→ H −→ I −→ T

Rispetto all’esercizio precedente osserviamo che il cammino minimo ha lunghez-za inferiore ma attraversa un numero di archi superiore.



D

C

E

A

B

O

F

G

T

3

2

8

6

7

5

4

4

2

3

4

3

3

3

5

6

k



Nodicandidati

Distanzatotale

k−esimonodovicino

Distanzaminima

Ultimoarco

1 O B 2 B 2 OB

2 O A 3 A 3 OAB C 2 + 5 = 7

3 A D 3 + 4 = 7 D 7 ADA E 3 + 4 = 7 E AEB C 2 + 5 = 7 C BC

4 C F 7 + 3 = 10 G 9 DGD G 7 + 2 = 9E F 7 + 3 = 10E G 7 + 3 = 10

5 C F 7 + 3 = 10 F 10 CFD F 7 + 3 = 10 DFE F 7 + 3 = 10 EFG T 9 + 5 = 14

6 F T 10 + 6 = 16 T 14 GTG T 9 + 5 = 14


Abbiamo trovato un unico cammino minimo di lunghezza 14:

O −→ A −→ D −→ G −→ T.


O

A

B

C

D

E

F

T

3

4

46

5

2

6

2

2

2

7

5

5

2

3

k



Nodicandidati

Distanzatotale

k−esimonodovicino

Distanzaminima

Ultimoarco

1 O A 3 A 3 OA

2 O B 4 B 4 OBC 4 C 4 OC

A D 3 + 2 = 5E 3 + 2 = 5

3 A D 3 + 2 = 5 D 5 ADE 3 + 2 = 5 E 5 AE

B E 4 + 2 = 6C E 4 + 2 = 6

4 C F 4 + 6 = 10 F 8 EFE F 5 + 3 = 8D T 5 + 5 = 10

5 D T 5 + 5 = 10 T 10 DTF T 8 + 5 = 13


Abbiamo trovato un unico cammino minimo di lunghezza 10:

O −→ A −→ D −→ T.

4.3 Il problema di massimo flusso

Esercizio. Determinare il massimo flusso nella seguente rete:

O

A

B

C

D

E

F

G

H

T6

7

9

4

5

8

8

6

3

6

2

5

6

5

6

5

Innanzitutto riscriviamo la medesima rete evidenziando il flusso residuo in-iziale su ogni arco (che scriviamo all’inizio di ciascun arco), e che inizialmentecoincide con la capacita massima dell’arco stesso, con il flusso utilizzato (chescriviamo al termine di ciascun arco), e che inizialmente e uguale a zero pertutti gli archi.

O

A

B

C

D

E

F

G

H

T6

7

9

0

0

0

53

6

2

5

4

0

0

0

0

0

0

65

6

5

0

0

0

0

8

8

60

0

0


I Iterazione: Cammino aumentante: O − C − H − T , c∗ = min{9, 4, 8} = 4:

O

A

B

C

D

E

F

G

H

T6

7

5

0

0

4

53

6

2

5

0

0

0

0

0

4

0

65

6

5

0

0

0

0

8

4

60

4

04 4

II Iterazione: Cammino aumentante: O−C−E−H−T , c∗ = min{5, 5, 5, 4} =4:

O

A

B

C

D

E

F

G

H

T6

7

1

0

0

8

53

6

2

1

0

0

0

0

4

4

0

65

6

1

0

0

0

4

8

0

60

8

08 8

III Iterazione: Cammino aumentante: O−C−E−F−T , c∗ = min{1, 1, 6, 6} =1:


O

A

B

C

D

E

F

G

H

T6

7

0

0

0

9

53

6

2

0

0

0

0

0

5

4

0

65

5

1

0

0

1

4

8

0

50

8

19 9

IV Iterazione: Cammino aumentante: O−B−E−F−T , c∗ = min{6, 2, 5, 5} =2:

O

A

B

C

D

E

F

G

H

T4

7

0

2

0

9

53

6

0

0

0

0

0

2

5

4

0

65

3

1

0

0

3

4

8

0

30

8

311 11

V Iterazione: Cammino aumentante: O−B−D−F−T , c∗ = min{3, 6, 6, 3} =3:


O

A

B

C

D

E

F

G

H

T1

7

0

5

0

9

53

3

0

0

0

0

3

2

5

4

0

35

3

1

3

0

3

4

8

0

00

8

614 14

VI Iterazione: Cammino aumentante: O−B−D−G−T , c∗ = min{1, 3, 5, 8} =1:

O

A

B

C

D

E

F

G

H

T0

7

0

6

0

9

53

2

0

0

0

0

4

2

5

4

0

34

3

1

3

1

3

4

7

0

01

8

615 15

VII Iterazione: Cammino aumentante: O−A−G−T , c∗ = min{7, 5, 7} = 5:


O

A

B

C

D

E

F

G

H

T0

2

0

6

5

9

03

2

0

0

0

0

4

2

5

4

5

34

3

1

3

1

3

4

2

0

06

8

620 20

VIII Iterazione: Cammino aumentante: O−A−D−G−T , c∗ = min{2, 3, 4, 2} =2:

O

A

B

C

D

E

F

G

H

T0

0

0

6

7

9

01

2

0

0

0

2

4

2

5

4

5

32

3

1

3

3

3

4

0

0

08

8

622 22

Il flusso trovato e ottimo perche esiste un taglio (esattamente OA−OB−OCche ha flusso residuo zero), anzi per la verita ne esiste anche un altro (cioeGT − FT − HT ) che ha flusso residuo nullo.Esercizio. Determinare il massimo flusso nella seguente rete:


O

A

B

C

D

E

F

G

T2

7

8

9

4

4

3

5

3

5

8

3

1

3

5

7

Riscriviamo la rete evidenziando il flusso residuo che, inizialmente coincidecon la capacita massima degli archi.

O

A

B

C

D

E

F

G

T2

7

8

9

5

4

3

3

4

5

8

7

3

1

3

5

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0


I Iterazione: Cammino aumentante: O − B − G − T , c∗ = min{8, 3, 5} = 3:

O

A

B

C

D

E

F

G

T2

7

5

9

5

4

3

0

4

5

8

7

3

1

3

2

0

0

3

0

0

0

0

3

0

0

0

0

0

0

0

3

3 3

II Iterazione: Cammino aumentante: O−B−D−G−T , c∗ = min{5, 3, 3, 2} =2:


O

A

B

C

D

E

F

G

T2

7

3

9

5

4

1

0

4

5

8

7

1

1

3

0

0

0

5

0

0

0

2

3

0

0

0

0

2

0

0

5

5 5

III Iterazione: Cammino aumentante: O−B−D−T , c∗ = min{3, 1, 7} = 1:

O

A

B

C

D

E

F

G

T2

7

2

9

5

4

0

0

4

5

8

6

1

1

3

0

1

0

5

0

0

0

2

3

0

0

0

0

3

0

0

6

6 6


IV Iterazione: Cammino aumentante: O − D − T , c∗ = min{2, 6} = 2:

O

A

B

C

D

E

F

G

T0

7

2

9

5

4

0

0

4

5

8

4

1

1

3

0

3

0

5

0

0

0

2

3

0

0

0

2

3

0

0

6

8 8

V Iterazione: Cammino aumentante: O −A−D − T , c∗ = min{7, 4, 4} = 4:

O

A

B

C

D

E

F

G

T0

3

2

9

5

0

0

0

4

5

8

0

1

1

3

0

7

0

5

0

0

0

2

3

0

0

4

2

3

0

4

6

12 12


VI Iterazione: Cammino aumentante: O−A−F −T , c∗ = min{3, 5, 3} = 3:

O

A

B

C

D

E

F

G

T0

0

2

9

2

0

0

0

4

5

8

0

1

1

0

0

7

3

5

0

3

0

2

3

0

0

4

2

3

0

7

6

15 15

Capitolo 1 Esercizi di Programmazione Linearetiziano19661.interfree.it/tracce/esercizi.pdf ·...

Documents

Transcript of Capitolo 1 Esercizi di Programmazione Linearetiziano19661.interfree.it/tracce/esercizi.pdf ·...