problema del trasporto

[DarkSiDE]

mi trovo a realizzare un programma per la risoluzione del problema del trasporto (programmazione lineare)
sinceramente non ho idea da dove incominciare, mi potreste dare qualche consiglio o url (ovviamente in linea di max) per iniziare a impostare il programma?
posso risolverlo con un qualunque linguaggio, avevo pensato al c++, quale secondo voi è il più consono?

ciao

[cionci]

Rinfrescami un po' sul problema del trasporto... Sarebbe il rpoblema del commesso viaggiatore ? Devi usare il metodo del simplesso ?

[pjtaddei]

se devi usare il Simplesso ti basta solo creare le matrici dei coefficenti, temrini noti e costi e il gioco e fatto... poi il resto e una banale copiatura del metodo da un libro di R.Op.!

[DarkSiDE]

chiedo venia, effettivamente sono stato poco preciso e ho dato per scontato troppe cose :p
il problema del traporto consiste nel programmare il trasporto di prodotti da m punti di origine aventi una certa disponibilità a n destinazioni aventi delle capacità in modo che il costo totale sia minimo
sinceramente mi è stato imposto di evitare di risolverlo con il metodo del simplesso (che nemmeno conosco) e di usare metodi specifici più semplici, ma in extremis.. :D
dovrei risolverlo con il metodo di houthakker e poi applicare lo stepping stone di dantzig

[/\/\@®¢Ø]

La prima risposta che mi viene in mente e' "il linguaggio che conosci". In linea di massima qualunque linguaggio che permetta di eseguire agevolmente operazioni algebriche. Poi dipende cosa ci fai attorno... leggi i dati da tastiera e li scrivi su video ? Leggi e scrivi da file ? Fai una interfaccia grafica ? A seconda della scelta un certo linguaggio puo' essere piu' adatto (anche se in generale ce la fai con qualsiasi ).

Non conosco gli algoritmi che hai citato, solo il simplesso. Se vuoi comunque avere un programma per poter confrontare le soluzioni, qui (ftp://ftp.es.ele.tue.nl/pub/lp_solve) trovi lpsolve che e' un software semplice da utilizzare ( inolrte e' free softwar ) per la risoluzione dei problemi: gli dai le disequazioni che li descrivono e la funzione che vuoi massimizzare.

Se poi sei dedito al masochismo, in giro per la rete ci sono estensioni del linguaggio prolog per questo tipo di problemi :D.

[cionci]

Originariamente inviato da /\/\@®¢Ø
[B]Se poi sei dedito al masochismo, in giro per la rete ci sono estensioni del linguaggio prolog per questo tipo di problemi :D.
Ma proprio masochista !!! ;)

Abbasso il Prolog !!! :)

DarkSiDE : non conosco quegli algoritmi che hai nominato...

Secondo quello scritto sui miei appunti (perchè mi ricordo poco ;))per un problema del genere noi trovavamo una soluzione ammissibile del problema e poi passavamo al simplesso...

[bsummer]

Io lo risolverei usando un algoritmo di tipo Greedy (nel + banale dei casi) o trasformando il tutto in problema di flusso minimo, facendo le debite considerazioni.

Per il linguaggio da usare, beh va bene un po' di tutto, usa quello che conosci meglio.

Bye

[DarkSiDE]

vi ringrazio per i consigli ma qualcuno sarebbe così gentile da postare qualche link dove viene affrontato l'argomento (mi interessa sia dal lato teorico che informatico)
ciao e graze ancora

[bsummer]

Originariamente inviato da DarkSiDE
[B]vi ringrazio per i consigli ma qualcuno sarebbe così gentile da postare qualche link dove viene affrontato l'argomento (mi interessa sia dal lato teorico che informatico)
ciao e graze ancora

Beh, se ti va di leggere un po' posso spiegarti come funziona un algoritmo di tipo Greedy.

I Greedy sono una categoria di algoritmi (non ne esiste una sola versione) "voraci" in quanto si basano sulla scelta di un criterio (il migliore possibile) attraverso il quale ricavare il massimo beneficio. Per spiegarti bene come un algoritmo Greedy possa risolvere il problema del trasporto ti faccio vedere un esempio molto simile (per non dire identico) al tuo.

Ci sono F fabbriche che producono quantita' diverse di prodotti e M magazzini che servono a immagazzinarli.

Il costo del trasporto (per unita') e dato dal modulo della differenza degli indici delle fabbriche e dei magazzini (cioe' portare prodotti dalla fabbrica 1 al magazzino 1, ha costo 0, dalla fabbrica 1 al magazzino 5 ha costo 4, dalla fabbrica 3 al magazzino 1 ha costo 2, e cosi via...). Cio' forma un grafo che collega le fabbriche ai magazzini tramite archi.

L'algoritmo funziona cosi':

Tra gli archi che collegano una fabbrica ad un magazzino:

1- scegli quello di costo minore (nel caso di piu' archi aventi costo uguale scegline uno a caso, di solito il primo della lista)
2- dato l'arco,se la fabbrica ha disponibilita' di pezzi e il magazzino non e' pieno allora dai al magazzino un numero di pezzi pari al minimo tra i pezzi disponibili in fabbrica e il numero di pezzi che mancano affinche' il magazzino sia pieno
3- scarta l'arco appena analizzato e ricomincia da 1, se ci sono ancora archi da visitare.

Spero di essere stato d'aiuto.

Bye

[cionci]

Non vorrei dire una menata...ma gli algortimi Greedy solitamente non trovano la soluzione ottima...ma solamente una soluzione ammissibile...

[bsummer]

Si, e' vero, ma :

1) non mi sembra sia stata richiesta una soluzione ottima

2) se fosse stata richiesta una soluzione ottima allora bisogna andare con un bel flusso minimo

Spero di sapere quello che dico visto che lunedi' ho l'esame di Ricerca Operativa
:(

[cionci]

Invece mi sembra che abbia chiesto di risolverlo inmodo che il costo totale sia minimo...

Credo che comunque sia applicabile una specie di derivazione degli algoritmi Greedy fino ad esaurimento...

In pratica la cosa più semplice da fare con un programma (escludendo il simplesso) sia di "provare" tutti i vari flussi ammissibili ;) Il problema è enumerarli...

[bsummer]

Originariamente inviato da cionci
[B]Invece mi sembra che abbia chiesto di risolverlo inmodo che il costo totale sia minimo...


Attenzione! Non avevo notato la risposta dove lo specificava...:D
Beh, allora in questo caso ha ragione cionci, Greedy fornisce ottimalità locale e raramente globale...

Bye

[DarkSiDE]

Originariamente inviato da cionci
[B]Invece mi sembra che abbia chiesto di risolverlo inmodo che il costo totale sia minimo...


sì l'intento è quello, cmq domani vi posto come dovrei risolverlo
grazie ancora ragazzi