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)
- capij (capacità della via che collega il nodo i=1..10 al nodo j=1..10)
Variabili
- xij (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:
xij <= capij (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
