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.
| Identifer | oai:union.ndltd.org:TDX_UPC/oai:www.tdx.cat:10803/6509 |
| Date | 12 September 1995 |
| Creators | Castro Pérez, Jordi |
| Contributors | Nabona, Narcís, Universitat Politècnica de Catalunya. Departament d'Estadística i Investigació Operativa |
| Publisher | Universitat Politècnica de Catalunya |
| Source Sets | Universitat Politècnica de Catalunya |
| Language | Catalan |
| Detected Language | Spanish |
| Type | info:eu-repo/semantics/doctoralThesis, info:eu-repo/semantics/publishedVersion |
| Format | application/pdf |
| Source | TDX (Tesis Doctorals en Xarxa) |
| Rights | ADVERTIMENT. L'accés als continguts d'aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d'investigació i docència en els termes establerts a l'art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l'autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s'autoritza la seva reproducció o altres formes d'explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d'un lloc aliè al servei TDX. Tampoc s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs., info:eu-repo/semantics/openAccess |
Page generated in 0.0022 seconds