Obtención de todas las soluciones básicas óptimas en los problemas de flujos en redes
- Valls Verdejo, Vicente
- Marco A. López Cerdá Director
Universidade de defensa: Universitat de València
Ano de defensa: 1982
- Marco A. López Cerdá Presidente/a
- Rafael Infante Macías Secretario/a
- Segundo Gutiérrez Cabria Vogal
- Francisco José Cano Sevilla Vogal
- Ramiro Melendreras Gimeno Vogal
Tipo: Tese
Resumo
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.