Swappa : Uni / Ricerca Operativa - PLI - Sfilata

Torna alla pagina di Ricerca Operativa

 :: Ricerca Operativa - PLI - Sfilata - 20.01.03 ::

Testo del problema

Mentre il carnevale impazza, l’assessore alle attività culturali impazzisce. Egli deve pianificare il percorso dei carri mascherati per le vie della città. Le due piazze principali saranno il punto di partenza e di arrivo dei carri, ed un limitato numero di vie sono percorribili da essi. Ognuna delle vie ha una capacità nota e limitata, misurata in numero di carri all’ora, la quale dipende dalla larghezza della via e da altri fattori che influenzano la velocità che i carri possono tenere lungo di essa.
L’assessore naturalmente vuole massimizzare il numero di carri che sfileranno nel limitato tempo disponibile, perché questo gli frutterà un proporzionale numero di voti alle prossime elezioni.
Formulare il problema, classificarlo e risolverlo con i dati del file SFILATA.TXT.

Dati

Le due piazze di partenza e di arrivo sono indicate rispettivamente 
da "s" e da "t".
Le vie percorribili sono le seguenti. Di ciascuna è indicata la 
capacità ossia il massimo numero di carri che la possono attraversare 
in un'ora. Inoltre è indicato anche il costo di allestimento.
Ovviamente la sfilata è a senso unico in ogni via.

 Via     Capacità  Costo
s -> 1      15       30
s -> 2      15       60
s -> 3      20      500
1 -> 3      15       10
1 -> 4      28      180
2 -> 3      20      250
2 -> 5      18       40
3 -> 6      20      200
4 -> 5       9       10
4 -> 7       8       50
5 -> 4       9       50
5 -> 8       8       10
6 -> 7       7      340
6 -> 8       7      410
6 -> t      10      200
7 -> t      10      270
8 -> t      10      290

Formulazione del problema

Dati

n = 10 (numero nodi stradali)
cap_ij (capacità della via che collega il nodo i=1..10 al nodo j=1..10)

Variabili

x_ij (numero di carri che percorrono la via che collega il nodo i=1..10 al nodo j=1..10) (nota: non tutti gli i sono collegati a tutti gli j)
y (numero totale di carri sui vari percorsi tra il nodo di partenza e quello di arrivo)

Le variabili sono intere e non negative.

Funzione obiettivo

Vogliamo massimizzare il flusso di carri per le vie cittadine: max y

Vincoli

vincoli di capacità per ogni via:
x_ij <= cap_ij (per ogni via i->j)
vincoli che regolino il flusso in ogni nodo, facendo in modo che il numero di carri in entrata sia uguale a quello in uscita. Ci sono due casi particolari in corrispondenza dei nodi estremi, in cui si sostituisce il numero di carri in entrata (o in uscita) con quello totale (la variabile y)

Lindizzazione del problema

! esercizio - sfilata

! variabili: x(i,j) = numero di carri che percorrono la via che collega il 
!		      nodo i al nodo j
! 	     y = numero totale di carri sui vari percorsi tra il nodo di 
!		 partenza e quello di arrivo
! le variabili sono intere

! funzione obiettivo
max y

st

! vncoli di capacità di ogni via
vias1) xs1 <= 15
vias2) xs2 <= 15
vias3) xs3 <= 20
via13) x13 <= 15
via14) x14 <= 28
via23) x23 <= 20
via25) x25 <= 18
via36) x36 <= 20
via45) x45 <=  9
via47) x47 <=  8
via54) x54 <=  9
via58) x58 <=  8
via67) x67 <=  7
via68) x68 <=  7
via6t) x6t <= 10
via7t) x7t <= 10
via8t) x8t <= 10

! vincoli per ogni nodo
nodos) xs1 + xs2 + xs3 - y = 0
nodo1) xs1 - x13 - x14 = 0
nodo2) xs2 - x23 - x25 = 0
nodo3) xs3 + x13 + x23 - x36 = 0
nodo4) x14 + x54 - x45 - x47 = 0
nodo5) x25 + x45 - x54 - x58 = 0
nodo6) x36 - x67 - x68 - x6t = 0
nodo7) x47 + x67 - x7t = 0
nodo8) x58 + x68 - x8t = 0
nodot) x6t + x7t + x8t - y = 0

end

! definiamo le 18 variabili intere
gint 18

Torna alla pagina di Ricerca Operativa