Método Símplex de redes

El método símplex de redes es una versión muy simplificada del método símplex para resolver problemas de flujo de costo mínimo. Como tal, realiza los mismos pasos básicos en cada iteración (encontrar la variable básica entrante, determinar la variable básica que sale y obtener la nueva solución básica factible) con el fin de mover la solución básica factible actual a una adyacente mejor. No obstante, ejecuta estos pasos en una forma que explota la estructura especial de la red del problema sin necesidad alguna de la tabla símplex.

Se podrán observar algunas similitudes entre el método símplex de redes y el método símplex de transporte presentado en la sección 7.2.En realidad, ambos son versiones simplificadas del método símplex que proporcionan algoritmos alternativos para resolver problemas de transporte de manera parecida. El método símplex de transporte extende estas ideas para resolver además otros tipos de problemas del flujo de costo mínimo.

En esta sección se presenta una versión más o menos abreviada del método símplex de redes que centra la atención justo en los conceptos principales. Se omiten ciertos detalles necesarios para llevarlo a la computadora, entre otros, cómo construir una solución inicial básica factible  o cómo realizar ciertos cálculos (como el de encontrar la variable básica entrante) de  una manera eficiente. Estos detalles se proporcionan en otros libros más especializados, como las referencias 1,2,6,7,11,12 y 14.