Obtención de todas las soluciones básicas óptimas en los problemas de flujos en redes

Abstract

SE PRESENTA UN METODO EFICAZ PARA LA OBTENCION DE TODAS LAS SOLUCIONES BASICAS OPTIMAS (S,B.O.) DE LOS PROBLEMAS DE FLUJOS EN REDES. SE DEMUESTRA QUE DADA UNA S.B.O. INICIAL X0 LA EXISTENCIA DE SOLUCIONES OPTIMAS ALTERNATIVAS ES EQUIVALENTE A LA EXISTENCIA DE CIRCUITOS ELEMENTALES DE COSTE CERO Y LONGITUD MAYOR QUE DOS EN EL GRAFO AUMENTADOR DE FLUJO ASOCIADO A X0: G(X0). A PARTIR DE ESTA CARACTERIZACION Y POR MEDIO DE LA APLICACION REITERADA DEL ALGORITMO DEL CAMINO MAS CORTO A LOS SUCESIVOS GRAFOS AUMENTADORES DE FLUJO. SE CONSTRUYE UN ALGORITMO PARA LA OBTENCION DE TODAS LAS S.B.O. DE LOS MENCIONADOS PROBLEMAS. SE DEMUESTRA QUE ES SUFICIENTE APLICAR EL ALGORITMO PROPUESTO A LAS COMPONENTES FUERTEMENTE CONVEXAS DE LOS GRAFOS AUMENTADORES DE FLUJO REDUCIDOS. SE DESCRIBE UN CODIGO FORTRAN DEL ALGORITMO Y SE PRESENTAN RESULTADOS COMPUTACIONALES.