Mètodes eficients per a la resolució de problemes de fluxos multiarticle

Resumen

Tal i com indica el seu títol, la present memòria de tesi té com objecte d'estudi el desenvolupament d'algorismes i implementacions eficients per resoldre el problema conegut dins del món de l'Optimització i Investigació Operativa com a problema de fluxos multiarticle en xarxa. Com es desprèn del seu nom, és un problema d'optimització en xarxa on, a diferència del problema clàssic uniarticle, diversos productes (els articles) comparteixen el mateix canal físic (la xarxa) sense poder ser combinats entre ells. Això provoca que sigui necessària una replicació de les variables -fluxos en cada arc- de la xarxa original, tantes vegades com articles hi ha, el qual incrementa considerablement el nombre de variables i constriccions a ser tractades. L'optimització de fluxos en xarxes multiarticle és un problema ben conegut, i durant anys diverses aplicacions reals han estat modelitzades mitjançant aquesta tècnica. Alhora, és un problema molt costós des d'un punt de vista computacional, donat el gran nombre de variables i equacions que intervenen com abans s'ha esmentat. Aquest doble fet (el seu interès per solucionar problemes reals i el seu elevat cost) ha motivat l'estudi i desenvolupament de tècniques per tractar-lo de forma específica. Sovint, però, aquest esforç ha conduït a la formulació de diversos algorismes però rarament ha donat lloc a implementacions de caràcter pràctic. Amb això que acabem de dir queda clar que suposarem que hi ha una clara distinció entre el que és algorisme i el que és implementació, tot i que sovint és difícil decidir on hi ha la frontera entre un i altre concepte. En general, per algorisme entendrem la seqüència de processos que s'han de seguir per tal d'aconseguir un cert objectiu, mentre que la implementació fa referència a com, en última instància, s'han dut a la pràctica. Des d'aquest punt de vista es podria dir que un algorisme té moltes implementacions, però que una implementació només respon a un únic algorisme. S'ha cregut convenient fer una breu discussió sobre els conceptes d'algorisme i implementació, donat que al treball aquí presentat ambdós tenen un pes específic. Al treball desenvolupat no s'ha pretès només detallar com modificar, ampliar o obtenir algorismes per solucionar el problema de fluxos multiarticle, sinó que a més s'ha plantejat com objectiu prioritari l'obtenció d'implementacions el més eficients i robustes possibles. Vista així, la tasca desenvolupada es troba a cavall entre dos camps com ara la Investigació Operativa i la Informàtica. També cal tenir present que en aquesta memòria es presentarà detalladament tot el que faci referència a la part algorísmica però no tant a nivell d'implementació. Això implicaria haver de descriure una gran quantitat d'estructures de dades i una gran quantitat de rutines desenvolupades i altres usades de llibreries numèriques estàndard. Tanmateix, això no ha de fer oblidar que la major part de l'esforç necessari ha estat dedicat a l'obtenció i disseny d'aquestes rutines i estructures de dades. I el fet de que tot aquest treball quedi plasmat en només l'obtenció d'una sèrie de taules amb valors numèrics no ha de fer oblidar la gran quantitat de feina no descrita que hi ha darrera d'aquests resultats. Un cop s'ha definit el marc on es troba el treball realitzat, procedirem a definir amb més detall els objectius que s'han perseguit i les aportacions que representa respecte el que fins ara s'havia fet. Finalitzarem la introducció amb una breu descripció sobre com ha estat estructurada aquesta memòria.