Newsgroup: it.istruzione.universita.ingegneria
Titolo: problemino ricerca operativa..

Ciao a tutti, devo risolvere un classico problema di ricerca operativa:
The caterer problem, non so di preciso come e' tradotto nei libri
italiani. Ho trovato diverse fonti e libri ma tutti risolvono il quesito
introducendo la teoria delle code mentre noi dovremmo farlo semplicemente
applicando il metodo del simplesso, senza ulteriori conoscenze (di
programma siamo al metodo duale..). 
Se qualcuno mi puo' dare una mano lo ringrazio in anticipo.
Il problema e' questo: 
Un tizio (caterer) ha preso un contratto per una serie di cene per 4
giorni successivi. Deve comprare tovaglioli speciali per queste cene al
costo di £1 ciascuno, ha a disposizione 2 tipi di lavanderie: 30p al pezzo
per la fast (2 giorni) e 50p per l'altra (3 giorni). Formulare il problema
e trovare la soluzione ottima..
Grazie
-- 
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it

 Grazie
Credo che tu possa formularlo come un problema di trasporto, in un modo tipo 
questo. Tieni presente che la mia è soltanto un'idea, e che vado ad occhio 
cercando di ricordare le nozioni di RO.
Usi un grafo, dove i nodi rappresentano i giorni e gli archi tra i nodi il 
flusso di tovaglioli in arrivo ogni giorno. Il peso degli archi rappresenta 
il costo dei tovaglioli. Ovviamente, archi provenienti da giorni più lontani 
avranno peso maggiore, visto che ciò indicherebbe l'utilizzo della 
lavanderia a 50p. Inoltre, in ogni nodo può entrare un flusso ulteriore, 
proveniente da un altro nodo, che rappresenta l'eventuale acquisto di nuovi 
tovaglioli.
Il problema può essere risolto cercando il flusso a costo minimo. Ovviamente 
occorre il bilancio ai nodi, facendo in modo che il flusso di tovaglioli 
entrante sia sempre pari alle richieste per quel giorno.
Poi non so, io la vedrei così. Qualcun altro ha idee?
Padda 

Prima di tutto grazie per la risposta, si' in teoria cosi' dovrebbe andare
ma in realta' noi dovremmo risolverlo semplicemente con il simplesso e
qualche tabella, senza nozioni sui problemi di trasporto o grafi (li
dobbiamo ancora fare..). Risolverlo con un tabella applicando il simplesso
sembra abbastanza lungo come lavoro, ci sono molti vincoli (uno per ogni
grafo del problema dei trasporti credo..). 


 grafo del problema dei trasporti credo..).
Allora vediamo cosa si può fare. Uso l'indice i=1,2,3,4 per indicare il 
giorno.
Io definirei innanzitutto due variabili  a(i) e b(i) che indicano il numero 
di tovaglioli del servizio fast o del servizio lungo di lavanderia lavati 
nel giorno i-esimo. Notare che il lavaggio dei tovaglioli fast serve solo 
per i=1,2 e quello dei tovaglioli non-fast solo per il giorno 1 (perchè 
tanto ci vogliono due giorni per i fast e 3 per i long, e lavarli in giorni 
successivi non servirebbe perchè eccederebbero il giorno massimo imposto nel 
problema) Quindi, delle variabili c(i) e d(i) che indicano i tovaglioli del 
servizio fast e del servizio lungo usati nel giorno i-esimo (anche qui, 
osserva che c(i) servirà solo per il giorno 3 e 4 e d(i) solo per il giorno 
4, perchè nei giorni precedenti non arriva nulla dalla lavanderia!).
Poi definirei una variabile numerica che indica il numero di tovaglioli 
acquistati, per esempio t(i). C'è poi una variabile w(i) che indica il 
numero di tovaglioli richiesta nel giorno i-esimo.
A questo punto i vincoli da definire dovrebbero essere più o meno questi
1) c(i)+d(i)+t(i)>=w(i)   cioè il numero totale di tovaglioli nel giorno i 
dev'essere almeno pari a quelli richiesti per ogni i. Di questo tipo di 
vincoli ne hai ovviamente 4, uno per ogni giorno considerato.
2) Per il giorno 3: a(1)-c(3)>0   cioè il numero di tovaglioli lavati 
tramite il servizio fast due giorni prima deve essere superiore a quello 
richiesto quel giorno.
Analogamente, per il giorno 4: a(1)+a(2)-c(3)-c(4)>=0 cioè al giorno 4 
arrivano tovaglioli lavati al primo giorno e al secondo giorno, ma sono 
stati sottratti i tovaglioli eventualmente usati al giorno 3. Hai perciò due 
vincoli di questo tipo.
3) In maniera del tutto simile si opera sui vincoli relativi al servizio 
non-fast, che vale solo per il giorno 4: b(1)-c(4)>=0. Hai un solo vincolo 
di questo tipo.
4) Infine imposto le variabili in gioco come non-negative (ma possono essere 
nulle, nel caso nel giorno considerato non venga utilizzato o lavato alcun 
tovagliolo di quel particolare tipo): a(i),b(i),c(i),d(i)>=0, i=1,2,3,4, 
k=3,4. hai un totale di 12 vincoli di questo tipo. Potresti imporre vincoli 
più stringenti, annullando direttamente i valori delle variabili per i 
giorni in cui hai la certezza che la lavanderia non lavi nulla o che non 
giunga nulla dalla lavanderia (seguendo le considerazioni fatte 
nell'introduzione).
A queto punto la f.o. dovrebbe essere tale da minimizzare i costi totali di 
lavanderia e acquisto tovaglioli, cioè:
         MIN     sum[i=1..4] (30p*a[i]+50p*b[i]+w[i])
Ora, formulato così il problema dovrebbe essere corretto, e rappresenta un 
problema di P.L. risolvibile con il simplesso primale. Tuttavia, credo che 
non sia ottimizzato al massimo, perchè ci sarà sicuramente un altro modo per 
ridurne il numero di variabili e per abbassarne la complessità (facendo il 
conto, dovresti infatti impostare 19 vincoli totali, che mi sembrano in 
effetti tanti, però non si sa mai).
Se non altro però questa è una traccia, tu poi lavoraci su e vedi se ti 
convince. Ripeto, prendila con le pinze perchè ricerca operativa l'ho fatta 
due anni fa; però la cosa mi ha intrigato e ho provato a rispondere.
Magari fammi sapere se alla fine è giusta la soluzione che ti ho suggerito, 
tanto per avere un'idea se son ancora capace oppure se è meglio che mi dia 
all'ippica..... ^__^
Ciao!
Padda 

         MIN     sum[i=1..4] (30p*a[i]+50p*b[i]+w[i])
Ops! Nella formula va inserito t(i) al posto di w(i)!
Cioè
    MIN     sum[i=1..4] (30p*a[i]+50p*b[i]+t[i])
Padda 

 nell'introduzione).
Ciao
PS non è che qualcuno mi sa dire se il software TORA è free e dove si può
prendere (niente mulo qui all'uni!)


 di questo tipo.
ma non dovrebbe essere b(1)- d(4) >=0, poi non credo sia necessario
distinguere l'utilizzo dei tovaglioli fast e servizio lungo (quindi
differenziare c e d ) dato che d č usata solo nel giorno 4. Potrei mettere
solo c e nel giorno 4 imporre un solo vincolo del tipo:
a(1)+a(2)+b(1)-c(3)>=0
Non ci dovrebbero essere anche vincoli del tipo
t(i)-a(i)-b(i)>=0 (non posso lavare piů tovaglioli di quanti ne ho!) per i
primi due giorni (poi non si lava piů...)
t(i) indica i tovaglioli comprati per lo specifico giorno giusto?
Ho scritto velocemente spero di esser stato chiaro..


 variabili non negative?
lascia pure perdere i k, facevano parte di un'altra soluzione che avevo 
scritto e poi mi son dimenticato di toglierli... usa solo gli indici i, che 
bastano e avanzano!
Padda 

 t(i) indica i tovaglioli comprati per lo specifico giorno giusto?
Sì, è un vincolo che si potrebbe inserire.
Però t(i) indica soltanto i tovaglioli acquistabili, non quelli che 
veramente possiedi. Il vincolo dovrebbe essere scritto così:
t(i)+c(i)+d(i)>=a(i)+b(i)
a sin hai i tovaglioli totali che possiedi per il giorno i, mentre a dx hai 
i tovaglioli che si lavano in quel giorno. Ovviamente, sono vincoli che hai 
bisogno di imporre solo per i giorni in cui effettivamente lavi,cioè i primi 
2.
FAi attenzione all'indice i: se per esempio i vale 3 significa che nel 
giorno 3 hai un numero di tovaglioli pari a quelli di sin, e ne lavi *per i 
giorni successivi* un numero pari a quelli di dx.
Padda