Obtención de todas las soluciones básicas óptimas en los problemas de flujos en redes
- Valls Verdejo, Vicente
- Marco A. López Cerdá Zuzendaria
Defentsa unibertsitatea: Universitat de València
Defentsa urtea: 1982
- Marco A. López Cerdá Presidentea
- Rafael Infante Macías Idazkaria
- Segundo Gutiérrez Cabria Kidea
- Francisco José Cano Sevilla Kidea
- Ramiro Melendreras Gimeno Kidea
Mota: Tesia
Laburpena
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.