Torna alla pagina di Ricerca Operativa
:: Ricerca Operativa - PL - Feriti - 16.04.09 ::
Testo del problema
In seguito ad un’esplosione si è verificata una situazione di emergenza. Numerosi feriti devono essere ricoverati al più presto presso gli ospedali della zona. Sono stati allestiti alcuni punti di triage, tutt’intorno alla zona dell’incidente e i feriti sono stati classificati in tre tipologie (traumi ortopedici, ustioni, intossicazione). Ciascuno degli ospedali della zona ha disponibilità per ricevere un numero limitato di feriti per ciascuna delle tipologie. L’assegnamento dei feriti agli ospedali deve essere fatto in modo tale da minimizzare il ritardo relativo medio, definito come il valor medio calcolato su tutta la popolazione dei feriti del ritardo relativo riferito ad ogni singolo ferito. Il ritardo relativo è il rapporto tra il tempo di percorrenza dal punto di triage dove il ferito è stato accertato all’ospedale a cui il ferito è stato assegnato ed il minimo tempo di percorrenza da quel punto di triage ad un ospedale compatibile con la tipologia del ferito. Il numeratore di questo rapporto misura il “livello di servizio” ricevuto dal ferito, mentre il denominatore indica il livello di servizio migliore possibile che quel ferito avrebbe potuto ricevere nel caso per lui più fortunato.
Formulare il problema, classificarlo e risolverlo con i dati del file FERITI.TXT. Discutere l’ottimalità della soluzione trovata.
Dati
I punti di triage sono 6, gli ospedali sono 8,
le tipologie di pazienti sono 3.
Tab. 1: Tempi di percorrenza [minuti]
Triage Ospedali
1 2 3 4 5 6 7 8
1 10 12 15 20 32 36 40 50
2 14 8 5 10 30 38 40 48
3 21 22 10 10 32 25 25 40
4 24 22 15 15 20 15 25 45
5 30 30 25 28 27 22 20 30
6 32 35 30 30 28 25 20 20
Tab. 2: Capacità (n.pazienti di ogni tipo ricevibili da ogni ospedale)
Tipo paz. Ospedali
1 2 3 4 5 6 7 8
1 12 10 8 10 15 20 20 20
2 5 0 2 0 8 0 0 10
3 15 8 11 5 20 18 13 0
Tab. 3: Triage (n. pazienti di ogni tipo per ogni punto di triage)
Triage Tipo pazienti
1 2 3
1 3 0 5
2 11 1 6
3 23 9 0
4 12 5 12
5 19 2 19
6 22 3 28
Totale 90 20 70
Formulazione del problema
Dati
- triage = 6 (numero punti di triage) i
- ospedali = 8 (numero di ospedali) j
- tipoPaz = 3 (numero di tipi di pazienti) k
- tPercij (tempo di percorrenza dal triage i=1..6 all'ospedale j=1..8) [minuti]
- capacitajk (numero pazienti di tipo k=1..3 che possono essere ospitati nell'ospedale j=1..8)
- nPazTik (numero pazienti di tipo k=1..3 nel triage i=1..6)
Variabili
- xijk (numero feriti di tipo k=1..3 trasportati dal triage i=1..6 all'ospedale j=1..8)
La variabile è continua e non negativa.
Funzione obiettivo
Ci viene chiesto di minimizzare il ritardo relativo medio, definito come da testo. Avremo però bisogno dei "minimi tempi di percorrenza dal punto di triage a un ospedale compatibile", che dobbiamo ricavarci dal testo. Prima di scrivere la funzione obiettivo scriviamo dunque questi dati:
Tempi minimi di percorrenza dal triage a un ospedale compatibile
al paziente di tipo k
Triage Tipo
1 2 3
1 10 10 10
2 5 5 5
3 10 10 10
4 15 15 15
5 20 25 20
6 20 20 20
Indichiamo questi tempi con tMinik e definiamo la funzione obiettivo:
min (somma)i (somma)j (somma)k (tPercij / tMinik) * xijk
Vincoli
- vincolo sulla capacità degli ospedali per ogni tipo di paziente:
(somma)i xijk <= capacitajk (per ogni j e per ogni k)
- vincolo che impone che la somma dei pazienti inviati agli ospedali sia pari a quelli che effettivamente si trovavano nei vari triage):
(somma)j xijk = nPazTik (per ogni i e per ogni k)
Linghizzazione del problema
! esercizio: feriti;
model:
sets:
triage /1..6/;
ospedale /1..8/;
tipoPaz /1..3/;
trasporto(triage,ospedale): tPerc;
degenza(tipoPaz,ospedale): capacita;
assegnamento(triage,tipoPaz): tMin, nPazT;
smistamento(triage,ospedale,tipoPaz): x;
endsets
data:
tPerc = 10 12 15 20 32 36 40 50
14 8 5 10 30 38 40 48
21 22 10 10 32 25 25 40
24 22 15 15 20 15 25 45
30 30 25 28 27 22 20 30
32 35 30 30 28 25 20 20;
capacita = 12 10 8 10 15 20 20 20
5 0 2 0 8 0 0 10
15 8 11 5 20 18 13 0;
tMin = 10 10 10
5 5 5
10 10 10
15 15 15
20 25 20
20 20 20;
nPazT = 3 0 5
11 1 6
23 9 0
12 5 12
19 2 19
22 3 28;
enddata
! funzione obiettivo;
min = @sum(smistamento(i,j,k): tPerc(i,j) / tMin(i,k) * x(i,j,k));
! vincoli sul numero totale di pazienti smistati;
@for(assegnamento(i,k): @sum(ospedale(j): x(i,j,k)) = nPazT(i,k));
! vincoli sulla capacità degli ospedali;
@for(degenza(k,j): @sum(triage(i): x(i,j,k)) <= capacita(k,j));
end
Altre domande
Considerare eventualmente il problema dal punto di vista degli ospedali, assumendo come funzione obiettivo l’equa distribuzione di tutti i feriti tra gli ospedali. Si vorrebbe in tal caso minimizzare il massimo sovraccarico, cioè il massimo tra i valori di sovraccarico riferiti ai singoli ospedali. Per sovraccarico di un ospedale si intende il rapporto tra il numero di feriti assegnati all’ospedale e il numero di feriti che sarebbero stati assegnati all’ospedale se tutti gli ospedali avessero ricevuto i feriti in ugual numero.
Cambia la funzione obiettivo, e dal momento che devo minimizzare il massimo sovraccarico dovrà introdurre una variabile ausiliaria z che andrà definita come nuovo vincolo. La funzione obiettivo diventa perciò:
min z
Mentre il nuovo vincolo in cui definisco z sarà:
z >= (somma)_ik x_ijk
---------------------------
[(somma)_ik capacita_ik]/8
Invece di dividere il denominatore per 8 posso moltiplicare la frazione per 8, ottenendo così:
z >= [(somma)i (somma)k xijk] / [(somma)i (somma)k nPazTik] * 8 (per ogni j)
Che in Lingo diventa:
!funzione obiettivo;
min = z;
! vincolo per definire il massimo sovraccarico;
@for(ospedale(j):
z >= @sum(assegnamento(i,k): x(i,j,k) /
@sum(assegnamento(i,k): nPazT(i,k)
* 8;
);
Torna alla pagina di Ricerca Operativa
