Pronto se ilustrará el método símplex de redes completo, con este mismo ejemplo, comenzando con yAB = 0(XAB = 10) como variable no básica y utilizando la figura 10.15. Una iteración posterior motrará que xCE alcanza su cota superior de 80 y es sustituida por XCE = 80 - yCE, etc. y entonces, en la siguiente iteración ocurre que yAB alcanza su cota superior de 10. Se podrá observar que estas operaciones se realizan directamente sobre la red, así que no será necesario utilizar las etiquetas xij o yij para los flujos en los arcos y ni siquiera se tendrá que saber qué arcos son arcos reales y cuáles son inversos (excepto uando se registre la solución final).
El uso de esta técnica de la cota superior deja las restricciones de lo nodos (el flujo que sale menos el flujo que entra = bi) como las únicas restricciones funcionales. Los problemas del flujo de costo mínimo tienden a tener mucho más arcos que nodos, por lo que el número de restricciones funcionales que resulta es por lo general una pequeña fracción de lo que sería, si se incluyeran las restricciones de las capacidades de los arcos. El tiempo de cálculo para el método símplex crece relativamente rápido conforme crece el número de restricciones funcionales, pero crece despacio con el número de variables (o el número de restricciones de acotamiento sobre esta variable). Por lo tanto, al incorporar la técnica de la cota superior se tiene a proporcionar ahorros considerables en el tiempo de cálculo.
No obstante, no se necesita esta técnica para problemas del flujo de costo mínimo con arcos no capacitados (incluyendo los primeros cuatro casos especiales que se consideraron en la sección anterior), en donde no existen las restricciones de capacidad de arco.
No hay comentarios.:
Publicar un comentario