RICERCA OPERATIVA GRUPPO A prova scritta del 7 luglio 2011

RICERCA OPERATIVA GRUPPO A prova scritta del 7 luglio 2011

1. Movida

a. Un sistema di trasporto (ad esempio, una linea metropolitana) si sviluppa lungo un’arteria unidirezionale di capacità q che connette 4 punti: per capacità si intende il numero di persone, uguale per tutti i tratti ij, che possono essere trasportate su ciascun tratto. Indichiamo con xij l’utenza (numero di persone) che richiede il servizio tra i e j, e sia cij il prezzo pagato per il servizio corrispondente. Supponiamo poi che sul sistema gravitino in tutto p utenti, cioè che il loro numero sommato su tutti i tratti sia pari a p. Come dovrebbero distribuirsi le loro richieste di servizio (cioè quali valori dovrebbero assumere le xij) per essere soddisfatte con un valore minimo di capacità q restituendo al gestore una somma non inferiore a un certo valore c? Formulate il problema come programmazione lineare a partire dai i valori seguenti.

c12 c13 c14 c23 c24 c34 c p 2 6 8 2 5 2 120 60

b. Supponiamo ora che la capacità q sia invece un dato del problema, ad esempio q = 20, e chiediamoci quale sia una distribuzione delle richieste di servizio xij che massimizzi il profitto complessivo del gestore. Formulate il problema come programmazione lineare mantenendo il vincolo che la somma delle utenze valga esattamente p. Costruite quindi un’opportuna rete conservativa che lo descriva come problema di flusso ottimo, indicando in corrispondenza a ogni nodo la componente del vettore domanda.

a. Gli utenti del tratto 12 sono tutti quelli che vanno da 1 a 2, più tutti quelli che vanno da 1 a 3, più tutti quelli che vanno da 1 a 4. In generale quindi:

x12 + x13 + x14 < q x23 + x24 < q x34 < q

Inoltre il numero totale di utenti è pari a p, e il profitto da essi generato dev’essere almeno c. Con i dati della tabella si ha:

x12 + x13 + x14 + x23 + x24 + x34 = 60 2x12 + 6x13 + 8x14 + 2x23 + 5x24 + 2x34 > 120 L’obiettivo si scrive:

min q

e tutte le variabili sono vincolate a valori non negativi.

b. L’obiettivo del problema diventa

max 2x12 + 6x13 + 8x14 + 2x23 + 5x24 + 2x34 e i vincoli si scrivono

x12 + x13 + x14 < 20 x23 + x24 < 20 x34 < 20 x12 + x13 + x14 + x23 + x24 + x34 = 60 xij > 0

1 2 3 4

x₁₃

x₁₃

x₂₄

x24

Cambiando di segno alle prime 3 disequazioni e aggiungendo variabili di surplus u, v, z i vincoli si riscrivono

– x12 – x13 – x14 – u = 20 – x23 – x24 – v = 20 – x34 – z = 20 x₁₂ + x₁₃ + x₁₄ + x₂₃ + x₂₄ + x₃₄ = 60 x_ij > 0

Sommando le quattro equazioni scritte e cambiando di segno si ottiene la quinta (ridondante):

u + v + z = 3q – p = 0

Risulta dunque chiaro che le variabili possono considerarsi flussi associati alla rete conservativa di figura, dove ogni nodo corrisponde a un vincolo e ogni variabile a un arco (il numero associato a ciascun arco è il profitto ottenuto al passaggio di un’unità di flusso per quell’arco: dove assente si intende pari a zero; gli archi tratteggiati denotano nodi sorgente e nodi pozzo).

2. Risolvete il seguente problema con il metodo del simplesso:

min 2x1 + 4x2 – x3 x1 – x2 + x3 < 5 2x1 + 3x3 = 6 x1, x2 > 0

Portiamo il problema in forma standard aggiungendo una variabile di slack s alla prima disequazione e ponendo x3 = u – v, con u, v > 0.

min 2x1 + 4x2 – u + v

x₁ – x₂ + u – v + s = 5 2x1 + 3u – 3v = 6 x1, x2, u, v > 0

Riportiamo i dati in tabella:

x₁ x₂ u v s

2 4 –1 1 0

1 –1 1 –1 1 5

2 0 3 –3 0 6

e osserviamo che non è canonica. Aggiungiamo una variabile al secondo vincolo e procediamo con la risoluzione del problema ausiliario:

–q = –20

1 2

2 3

3 4

t –q = –20

3q – p = 0 –q = –20

t’

6 8 2

2

5 2

p = 60

x1 x2 u v s w

0 0 0 0 0 1

1 –1 1 –1 1 0 5

2 0 3 –3 0 1 6

x₁ x₂ u v s w

–2 0 –3 3 0 0 –6

1 –1 1 –1 1 0 5

2 0 3 –3 0 1 6

x1 x2 u v s w

0 0 0 0 0 1

1/3 –1 0 0 1 –¹/3 3

2/₃ 0 1 –1 0 ¹/₃ 2

La variabile ausiliaria w è uscita dalla base, quindi quella trovata è una soluzione di base ammissibile del problema iniziale. Eliminando la colonna w e ripristinando la funzione obiettivo originale si ha

x1 x2 u v s

2 4 –1 1 0

1/₃ –1 0 0 1 3

2/3 0 1 –1 0 2

La tabella non è canonica, per renderla tale occorre sommare la riga 2 alla riga 0:

x1 x2 u v s

8/3 4 0 0 0 2

1/3 –1 0 0 1 3

2/₃ 0 1 –1 0 2

Il criterio di ottimalità risulta soddisfatto. Una soluzione ottima, di valore –2, è pertanto x1 = x2 = 0, x3 = u – v = 2.

3. Il vettore w = (¹/₂, ¹/₂¹/₂) è combinazione convessa o solamente conica dei vettori v1 = (1, ¹/2, ¹/2), v2 = (¹/2, 1, ¹/2), v3 = (¹/2,¹/2, 1)?

4. Scrivete il duale del seguente problema: min 2x1 – x3 max – 2y1 + y2

x₁ – x₂ + x₃ = –2 y₁ – 2y₂ – y₃ < 2 –2x1 + x2 > 1 – y1 + y2 = 0 x1 + x3 < 0 y1 – y3 < –1 x1, x3 > 0 y2, y3 > 0 5. Applicando il metodo di Fourier-Motzkin, risolvete il seguente problema esibendo una soluzione ottima

o classificandolo come inammissibile o illimitato: min z = 2x2 + 3x3 – x1 + x2 + x3 > 1 –3 x1 + 2x2 > 2

x1, x2, x3 > 0

Il valore minimo di z è 2. In corrispondenza, le variabili assumono i valori: x1 = x3 = 0, x2 = 1.

RICERCA OPERATIVA GRUPPO B prova scritta del 7 luglio 2011

1. Movida

Vedi testo e soluzione del corrispondente esercizio proposto al Gruppo A.

2. Risolvete il seguente problema con il metodo del simplesso:

min 2x₁ – 4x₂ + x₃ x1 – x2 + x3 < 5 2x1 + 3x3 = 6 x1, x2 > 0

Per riformulare il problema in forma standard si procede come nel corrispondente esercizio del Gruppo A. Il poliedro del problema è il medesimo, così come il problema ausiliario: quella trovata è quindi una soluzione di base ammissibile. Eliminando la colonna w e ripristinando la funzione obiettivo originale si ha

x1 x2 u v s

2 –4 1 1 0

1/3 –1 0 0 1 3

2/3 0 1 –1 0 2

La tabella non è canonica, per renderla tale occorre sottrarre la riga 2 dalla riga 0:

x1 x2 u v s

4/3 –4 0 –2 0 –2

1/₃ –1 0 0 1 3

2/₃ 0 1 –1 0 2

Il criterio di illimitatezza risulta soddisfatto in corrispondenza della colonna v. Il problema è dunque illimitato inferiormente.

3. Il vettore w = (1, 1, 1) si ottiene combinando v1 = (2, ¹/2, ¹/2), v2 = (¹/2, 2, ¹/2), v3 = (¹/2,¹/2, 2) con coefficienti λ1 = λ2 =λ3 = ¹/₃ > 0. Poiché la loro somma è 1, la combinazione è convessa.

4. Scrivete il duale del seguente problema: min –x₁ + 2x₃ max 2y₁ + y₂ x₁ – x₂ + x₃ = –2 y₁ +y₃ = 1 x₂ – 2x₃ > 1 y₁ + y₂ < 0 x1 + x3 < 0 –y1 – 2y2 – y3 < 2 x2, x3 > 0 y2, y3 > 0

5. Applicando il metodo di Fourier-Motzkin, risolvete il seguente problema esibendo una soluzione ottima o classificandolo come inammissibile o illimitato: min z = 3x1 + 2x3

x1 – x2 + x3 > 1 –3 x2 + 2x3 > 2

x₁, x₂, x₃ > 0

Il valore minimo di z è 2. In corrispondenza, le variabili assumono i valori: x1 = x2 = 0, x3 = 1.