|
Abstract:
|
Aquest projecte és una eina pedagògica per explicar conceptes de programació matemàtica des d'una vessant pràctica. Partim del problema del viatjant de comerç asimètric, del qual hem descrit i comentat diverses formulacions. Hem escollit la formulació de C. E. Miller, A. W. Tuker, i R. A. Zemlin, posteriorment millorada per M. Desrochers, i G. Laporte (DL). L'hem resolt mitjançant el mètode subgradient aplicat a la relaxació Lagrangiana de les constriccions proposades per DL. Hem expressat el problema com la suma de dos subproblemes independents més una constant. Un dels subproblemes l'hem resolt de forma directa i l'altre hem utilitzat el mètode del Simplex.Hem implementat l'ATSP EDU amb el llenguatge de programació Java i ens hem ajudat de la llibreria de funcions GLPK per implementar parts de la formulació i la resolució. Degut a la complexitat de l'algoritme hem desenvolupat un prototipus de la formulació i el mètode de resolució utilitzant el llenguatge modelització matemàtica AMPL i el resolutor CPLEX. Per determinar les característiques de l'aplicació hem fet un disseny previ. Hem fet servir jocs de dades de diferents dimensions per testar l'aplicació i el prototipus. Per acabar, hem fet una descripció del funcionament de l'aplicació a nivell d'usuari, un anàlisi dels resultats que genera ATSP EDU, i una relació de possibles ampliacions futures. |