RICERCA OPERATIVA

Esercizio del 4 marzo 2003

Cognome: |__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|

Nome: |__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|

Matricola: |__|__|__|__|__|__|

Dati i seguenti vettori di IR³

| 1 | | 0 | | 2 |

a₁ = |–4 | a₂ = | 1 | a₃ = | 0 |

| 0 | |–1 | | 1 |

calcolare attraverso il Metodo di Fourier-Motzkin le disequazioni che individuano il loro involucro conico (vale a dire l’insieme dei punti di IR³ ottenibili come combinazione conica dei punti dati).

Risoluzione

I punti dell’involucro conico sono quegli x Î IR³ per i quali esistono tre moltiplicatori l₁, l₂, l₃ tali che

x₁ = l₁ + 2l₃

x₂ = –4l₁ + l₂

x₃ = –l₂, + l₃

l₁, l₂, l₃ > 0

Il problema consiste quindi nell’individuare la proiezione di questo poliedro nello spazio delle variabili x₁, x₂, x₃.

Tabella iniziale: x₁ x₂ x₃ l₁ l₂ l₃

1| 1 0 0 –1 0 –2 0

2| –1 0 0 1 0 2 0

3| 0 1 0 4 –1 0 0

4| 0 –1 0 –4 1 0 0

5| 0 0 1 0 1 –1 0

6| 0 0 –1 0 –1 1 0

7| 0 0 0 –1 0 0 0

8| 0 0 0 0 –1 0 0

9| 0 0 0 0 0 –1 0

Eliminiamo la colonna relativa al moltiplicatore l₁:

Z₁ = {5, 6, 8, 9} P₁ = {2, 3} N₁ = {1, 4, 7}

Proiezione in IR⁵: x₁ x₂ x₃ l₁ l₂ l₃

1| 0 0 1 0 1 –1 0 | 5

2| 0 0 –1 0 –1 1 0 | 6

3| 0 0 0 0 –1 0 0 | 8

4| 0 0 0 0 0 –1 0 | 9

5| 4 1 0 0 –1 –8 0 | 1,3

6| –4 –1 0 0 1 8 0 | 4,2

7| –1 0 0 0 0 2 0 | 7,2

8| 0 1 0 0 –1 0 0 | 7,3

dove abbiamo cancellato le righe nulle in quanto corrispondenti a diseguaglianze non significative. Eliminando ora la colonna relativa al moltiplicatore l₂ otteniamo:

Z₂ = {4, 7} P₂ = {1, 6} N₂ = {2, 3, 5, 8}

Proiezione in IR⁴: x₁ x₂ x₃ l₁ l₂ l₃

1| 0 0 0 0 0 –1 0 |4

2| –1 0 0 0 0 2 0 |7

3| 0 0 1 0 0 –1 0 |1,3

4| 4 1 1 0 0 –9 0 |1,5

5| 0 1 1 0 0 –1 0 |1,8

6| –4 –1 –1 0 0 9 0 |6,2

7| –4 –1 0 0 0 8 0 |6,3

8| –4 0 0 0 0 8 0 |6,8

Rispetto alla colonna l₃ si ha ora

Z₃ = Æ P₃ = {2, 6, 7, 8} N₃ = {1, 3, 4, 5}

per cui la successiva (e ultima) proiezione fornisce

Proiezione in IR³: x₁ x₂ x₃ l₁ l₂ l₃

1 | –1 0 0 0 0 0 0 |2,1

2 | –1 0 2 0 0 0 0 |2,3

3 | –1 2 2 0 0 0 0 |2,4

4 | –1 2 2 0 0 0 0 |2,5

5 | –4 –1 –1 0 0 0 0 |6,1

6 | –4 –1 8 0 0 0 0 |6,3

7 | –4 8 8 0 0 0 0 |6,5

8 | –4 –1 0 0 0 0 0 |7,1

9 | –4 –1 8 0 0 0 0 |7,3

10 | –4 –1 8 0 0 0 0 |7,4

11 | –4 7 8 0 0 0 0 |7,5

12 | –4 0 0 0 0 0 0 |8,1

13 | –4 0 8 0 0 0 0 |8,3

14 | –4 8 8 0 0 0 0 |8,4

15 | –4 8 8 0 0 0 0 |8,5

Osserviamo che le righe 1 e 12 esprimono la medesima condizione, e quindi una delle due può essere soppressa. Lo stesso dicasi per le righe 2 e 13, per le righe 6, 9 e 10, e per le righe 3, 4, 7, 14 e 15. Eseguendo le semplificazioni e rinumerando le righe si ottiene

Proiezione in IR³: x₁ x₂ x₃ l₁ l₂ l₃

1 | –1 0 0 0 0 0 0 |2,1

2 | –1 0 2 0 0 0 0 |2,3

3 | –1 2 2 0 0 0 0 |2,4

4 | –4 –1 –1 0 0 0 0 |6,1

5 | –4 –1 8 0 0 0 0 |6,3

6 | –4 –1 0 0 0 0 0 |7,1

7 | –4 7 8 0 0 0 0 |7,5

In conclusione il poliedro cercato ha la seguente espressione

Diseguaglianze di cone({a₁, a₂, a₃}):

x₁ > 0

x₁ – 2x₃ > 0

x₁ – 2x₂ – 2x₃ > 0

4 x₁ + x₂ + x₃ > 0

4 x₁ + x₂ – 8x₃ > 0

4 x₁ + x₂ > 0

4 x₁ – 7x₂ – 8x₃ > 0