Tesina di ricerca operativa
Sistema di collocamento dei libri in una biblioteca
(Utilizzando l’interfaccia testuale per NETFLO)
Prof. Paola Zuddas
A.A. 1999/2000
Elisa Elisabetta
IL PROBLEMA
BIBLIOTECA NUOVI LIBRI
LIBRERIA CON NUMERO LIMITATO DI RIPIANI
CRITERI DI COLLOCAMENTO
FREQUENZA DI RICHIESTA
LIBRI PIU’ RICHIESTI
RIPIANI PIU’ ACCESSIBILI
LIBRI MENO RICHIESTI
RIPIANI MENO ACCESSIBILI
IL MODELLO MATEMATICO
PROBLEMA DI TRASPORTO
min ∑j=1
n
∑ c ij x ij
∑j∈S i
x ij− ∑k∈P i
x ki=bi i=1,. . . , nm
x ij≥0
¿¿
{¿ ¿¿¿
min ∑j=1
n
∑ c ij x ij
∑j∈S i
x ij− ∑k∈P i
x ki=bi i=1,. . . , nm
x ij≥0
¿¿
{¿ ¿¿¿
bi
NODI DI OFFERTA>0
<0 NODI DI DOMANDA
LIBRI
RIPIANI
I COSTI
• TEMPO
• FATICA• FREQUENZA DI RICHIESTA
PIU’ GETTONATI
COSTO PIU’ ALTO
ALTEZZA DEI RIPIANI
LE NOSTRE DIFFICOLTÀ
UN SOLO COSTO PER OGNI RAMO
COME DETERMINARLO ?
LA NOSTRA SCELTA
Ck= li + rj
COSTO RAMO=FREQUENZA+ACCESSIBILITÀ
i =1….m
j=1….n
k=1….p
m=# classi libri
n=# ripiani
p=# rami
ESEMPIO :
i =1
j=1….n
k=i*j
c1=l1+r1
c2=l1+r2
….
ck=l1+rn
•SCRITTO IN FORTRAN
•RISOLVE PROBLEMI DI MINIMO COSTO SU RETI
•IL FILE DI INGRESSO E’ DIFFICILE DA COSTRUIRE E DA LEGGERE
•IL FILE DI USCITA E’ PIU’ LEGGIBILE
IL SOFTWARE: NETFLO
INTERFACCIA TESTUALE (C)
• Makeinp.exe
Guida alla creazione di un file di ingresso per Netflo.exe
• Output.exe Mostra a video i risultati
SCOPO DELLA TESINA:
TESTARE L’INTERFACCIA
• 70 LIBRI E 70 POSTI
• 70 LIBRI E 95 POSTI
• 95 LIBRI E 70 POSTI
• BIBLIOTECA VATICANA
• CONFRONTO TRA I RISULTATI DI OUTPUT.EXE E DI NETFLO.OUT
Ipotesi iniziale: SISTEMA IN EQUILIBRIO
S di+ S oj =0
per i=1..m e j=1..nDomanda = offerta Ipotesi verificata
Domanda > offerta
Domanda < offerta
Ipotesi non verificata
l6l1 l2 l3 l4 l5
r1 r2 r3 r4 r5
Domanda uguale all’offerta
Output.exe 14 iterazioni costo minimo 197Netflo.out 14 iterazioni costo minimo 197
Domanda maggiore dell’offerta (95 posti, 70 libri)
NODO FITTIZIO
7 nodi di domanda 5 nodi di offerta
TUTTI GLI ARCHI CHE PARTONO DAL NODO l7 AVRANNO UN COSTO MOLTO ALTO (1000)
l1 l2 l3 l4 l5 l6 l7
r1 r3r2 r4 r5
Output.exe e Netflo.out
18 iterazioni costo 25102
Costo effettivo 25102 - 25000 = 102
Domanda minore dell’offerta (70 posti, 95 libri)
NODO FITTIZIO
6 nodi di domanda 6 nodi di offerta
TUTTI GLI ARCHI CHE ARRIVANO AL NODO r6
AVRANNO UN COSTO MOLTO ALTO (1000)
l1 l2 l3 l4 l5 l6
r1 r3r2 r4 r5
Output.exe e Netflo.out
13 iterazioni costo 25137
Costo effettivo 25137 - 25000 = 137
r6
BIBLIOTECA VATICANA (domanda uguale all’offerta)
•2500 LIBRI Output.exe c=23442
Netflo.out c=23442
•7000 LIBRIOutput.exe c=-4214
Netflo.out c=61322
•12000 LIBRIOutput.exe c=-24659
Netflo.out c=106413
LIBRI=POSTI Output.exe Netflo.out 2500 23442 23442
3000 29042 29042
3300 32142 32142 3400 -31894 33642
CONFRONTO TRA OUTPUT.EXE E NETFLO.OUT
mincosto= Ck*Xk Ck costo unitario Xk flusso sul ramo
OUTPUT.EXE HA UN BUG NETFLO.OUT LAVORA BENE
PROBLEMI DI ASSEGNAZIONE AD UNA VARIABILE DI UN VALORE
LETTO DA UN FILE
INTERFACCIA
Top Related