Iteración 3 Terminacion del ejemplo Prueba de optimalidad (II)

Para identificar los flujos a través de los arcos reales, y no de inversos, para esta solución óptima, la red ajustada actual (Fig. 10.25) se debe comparar con la red original (Fig. 10.9). Obsérvese que cada uno de estos arcos tiene la misma dirección en las dos redes, con la única excepción del arco entre los nodos C y E. ESto significa que el único arco inverso en la figura 10.25 es el arco E→C, para el que el flujo está dado por la variable yCE. Entonces, se calcula xCE = uCE - yCE = 80 - yCE. Resulta que el arco E→C es un arco no básico, entonces, yCE = 0 y xCE = 80 es el flujo a través del arco real C→E. Todos los demás flujos a través de los arcos reales son los flujos dados en la figura 10.24. Por lo tanto, la solución óptima es la que se muestra en la figura 10.26

Iteración 3 Terminacion del ejemplo Prueba de optimalidad (I)

En este punto, el algoritmo intentará usar las figuras 10.24 y 10.25 para encontrar la siguiente variable básica entrante con los cálculos normales que se muestran la tabla 10.5. Sin embargo, ninguno de los arcos no básicos da un valor negativo de ΔZ, de manera que no puede lograrse una mejroa en el valor de Z introduciendo un flujo a través de ninguno de ellos. ESto significa que la solución básica factible actual que se muestra en la figura 10.24 pasa la prueba de optimalidad y el algoritmo se detiene.

Iteración 3 Terminacion del ejemplo Selección de la variable básica que sale y la nueva solución básica factible (III)

Igual que en la iteración 2, la variable básica que sale (yAB) se obtuvo con la variable que alcanzó su cota superior. Además, existen otros dos puntos de interés especial respecto a esta elección particular. Uno es que la variable básica entrante yAB también se vuelve la variable básica que sale en la misma iteración! ESto ocurre muy pocas veces con la técnica de la cota superior siempre que al aumentar el valor de la variable básica entrante, ésta alcance su cota superior antes que lo haga ninguna otra de las variables básicas con alguna de sus cotas.

El otro punto de interés es que el arco B→A que es necesario cambiar por un arco inverso A→B (porque la variable básica que sale alcanza una cota superior) ya es un arco inverso!. Esto no causa problema ya que el arco inverso de un arco inverso es simplemente el arco real original. Por lo tanto, el arco B→A (con cBA =  -2 y uBA =10) en la figura 10.23 se sustituye por el arco A→B (con cAB = 2 y uAB =10), que es el arco entre los nodos A y B en la red original de la figura 10.9 y e cambia un flujo generado de 10 del nodo B (bB = 50 → 40) al nodo A (bA = 40 →50). Al mismo tiempo, la variable yAB = 10 se sustituye por 10 - xAB, con xAB = 0 como la nueva variable no básica.

En la figura 10.25 se muestra la red ajustada que resulta.

Iteración 3 Terminacion del ejemplo Selección de la variable básica que sale y la nueva solución básica factible (II)

La variable yAB impone la cota superior más pequeña (10) sobre θ, por lo que se convierte en la variable básica que sale. Haciendo θ = 10 en estas expresiones para xAC y XBC (junto con los valores que no cambian de xAC = 10 y xED =20) se obtiene la siguiente solución básica factible que se muestra en la figura 10.24

Iteración 3 Terminacion del ejemplo Selección de la variable básica que sale y la nueva solución básica factible (I)

Iteración 3: para iniciar la siguiente iteración se usan las figuras 10.22 y 10.23. La tabla 10.4 muestra los cálculos que llevan a la elección de yAB (inverso del arco B→ A), como la variable básica entrante. Después se agrega tanto flujo θ como sea posible al arco B→ A, sin que viole las siguientes cotas para los flujos:

Iteración 2 Terminacion del ejemplo Selección de la variable básica que sale y la nueva solución básica factible (II)

Como XCE impone la menor cota superior (20) sobre θ, xCE se convierte en la variable básica que sale. Si se sustituye θ =20 en las expresiones anteriores, para xED, XAD y xAC, se obtiene el flujo a través de los arcos básicos para la siguiente solución factible básica (con xBC = 50 sin quedar afectado por θ), como se muestra en la figura 10.22

De interés especial aqui es que la variable básica que sale XCE se obtuvo con la variable que alcanzó su cota superior (80). Por lo tanto, al usar la técnica de la cota superior, xCE se sustituye C → E con cCE = 1 y uCE = 80 se sustituye por el arco invertido E→ C con cEC = -1 y uEC = 80. Los valores bE y bC también se ajustan agregando 80 a bE y restando 80 a bC. La red ajustada que resulta se muestra en la figura 10.23, en donde los arcos no básicos se muestran con líneas punteadas y los números junto a todos los arcos son los costos unitarios.

Iteración 2 Terminacion del ejemplo Selección de la variable básica que sale y la nueva solución básica factible (I)

Comenzando con el árbol de expansión factible que se muestra en la figura  y haciendo referencia a la figura  para los costos unitarios (cij), los cálculos para seleccionar la variable básica entrante se dan en la tabla 10.3. La segunda columna identifica el ciclo no dirigido único que se crea al agregar el arco no básico en la primera columna a este árbol de expansión, y la tercera columna muestra el efecto incremental sobre los costos debido a los cambios en los flujos de este ciclo causados al agregar un flujo de θ =1 al arco no básico. El arco E → D tiene el mayor valor negativo (en términos absolutos) de ΔZ, de manera que xED es la variable básica entrante.

Ahora se hace el flujo θ en el arco E → D  tan grande como sea posible, sin violar las siguientes cotas sobre los flujos:

Terminacion del ejemplo Selección de la variable básica que sale y la nueva solución básica factible

Para las dos iteraciones que faltan para llegar a la solución óptima, la atención se centrará sobre algunas características de la técnica de la cota superior.

El patrón para encontrar la variable básica entrante, la que sale y la siguiente solución factible, será muy parecido al que se describió en la primera iteración, así que sólo se resumirán brevemente estos pasos.

Selección de la variable básica que sale y la nueva solución básica factible (III)

El árbol de expansión factible correspondiente se muestra en la figura 10.21.

Si la variable básica que sale hubiera alcanza su cota superior, entonces en este punto se habrían necesitado los ajustes presentados para la técnica de la cota superior (como se verá ejemplificado en las siguientes dos iteraciones). Sin embargo, como la cota inferior de 0 fue la que se alcanzó, no es necesario hacer más.

Selección de la variable básica que sale y la nueva solución básica factible (II)

Los arcos cuyo flujo no cambia con θ (por ejemplo, aquellos que no forman parte del ciclo no dirigido), que en este caso es sólo arco B→ C en la figura 10.17, se pueden ignorar ya que no llegarán a ninguna de sus cotas al aumentar θ.

Para los cinco arcos de la figura 10.17 la conclusión es que xDE debe ser la variable básica que sale, puesto que alcanza su cota para el valor más pequeño θ (10). Si se establece θ = 10 en esta figura, se obtienen los flujos a través de los arcos básicos de la siguiente solución básica factible:

Selección de la variable básica que sale y la nueva solución básica factible (I)

Después de elegir la variable básica entrante, sólo se necesita un paso rápido más para determinar simultáneamente la variable básica y obtener la nueva solución básica factible. En la primera iteración del ejemplo, la clave es la figura 10.17. Como xAC es la variable básica entrante, se aumenta el flujo θ a través del arco A→C lo más posible, hasta que una de las variables básicas llegue a su cota inferior (0) o bien a su cota superior (uij). Para aquellos arcos cuyo flujo aumenta con θ en la figura 10.17 (los arcos A→C y C→E), sólo es necesario considera las cotas superiores (uAC = ∞ y uCE = 80):

Selección de la variable básica entrante (V)

En lugar de identificar ciclos no dirigidos, etc. el método símplex de redes obtiene estos valores de ΔZ mediante un procedimiento algebraico que es mucho más eficiente (en especial para redes grandes).El procedimiento es análogo al que se usa para el método símplex de transporte. El procedimiento es análogo al que se usa para el método símplex de transporte para resolver las ui y vj, con el fin de obtener el valor de (cij -ui-vj) para cada variable no básica xij. no se describirá este procedimiento con más detalle, por lo que el lector deberá usar el método de los ciclos no dirigidos al resolver los problemas del final del capítulo.

Selección de la variable básica entrante (IV)

El hecho de que Z aumente, en lugar de disminuir, cuando yAB (flujo a través del arco inverso B→ A) se incremente, elimina esta variable como candidato ser la variable básica entrante. (Recuérdese que al aumentar el valor de yAB en realidad significa disminuir xAB, el flujo a través del arco real A→ B desde su costa superior de 10.

Para el último arco no básico E→ D se obtiene un resultado similar. Al agregar este arco con flujo de θ al árbol de expansión factible inicial, se crea un ciclo no dirigido ED-DE que se muestra en la figura 10.20, por lo que el arco también se incrementa en θ en el arco D→E y no se afecta ningún otro arco. Por lo tanto,  entonces el valor negativo de xAC implica que xAC  se convierta en la variable básica entrante para la primera iteración. En caso de que haya más de una variable no básica con un valor negativo de ΔZ, se elige la que tiene el mayor valor absoluto.

Selección de la variable básica entrante (III)

Como el objetivo es minimizar Z, esta tasa grande de disminución en Z al aumentar xAC es muy deseable; asi, xAC se convierte en un candidato de primer orden para ser la variable básica entrante.

Ahora es necesario realizar el mismo análisis para las otras variables no básicas antes de hacer la última selección de la variable básica entrante. Las únicas otras variables no básicas son yAByxED correspondientes a los otros dos arcos no básicos, B→A y E→D, en la figura 10.15.

La figura 10.19 muestra el efecto incremental sobre los costos al agregar el arco B→A con flujo θ al árbol de expansión dado en la figura 10.16. Al agregar este arco se crea un ciclo no dirigido BA-AD-DE-CE-BC, con lo que el flujo aumenta en θ para los arcos A→D y D→E, pero disminuye en θ para los dos arcos en la dirección opuesta sobre este ciclo, C→E y B→C. Estos incrementos de flujo θ y -θ son multiplicandos de los valores de los costos cij en la figura. Por tanto:

Selección de la variable básica entrante (II)

Ahora, Cuál es el efecto incremental sobre Z (costo total del flujo) si se agrega el flujo θ al arco A →C, etc? La figura 10.18 muestra la mayor parte de la respuesta dando el costo unitario multiplicado por el cambio en el flujo para cada arco en la figura 10.17. Por lo tanto, el incremento global en Z es

Selección de la variable básica entrante (I)

Para comenzar una iteración del método símplex de redes, recuérdese que el criterio del método símplex estándar para elegir la variable básica entrante es escoger la variable no básica que, al aumentar su valor, mejore el valor de Z más rápido. Ahora se verá cómo se hace esto sin tener tabla símplex.

A manera de ilustración, considérese la variable no básica xAC en la solución inicial básica factible, es decir, el arco no básico A→C. Aumentar xAC a algún valor θ significa que debe agregarse a la red el arco A→C con flujo θ que se muestra en la figura 10.16. Si se agrega un arco no básico a un árbol de expansión, siempre se crea un ciclo no dirigido único; el ciclo en este caso se ve en la figura 10.17 como AC-CE-DE-AD. La figura 10.17 muestra también el efecto de agregar el flujo θ al arco A→C sobre los otros flujos en la red. En particular, el flujo aumenta en  θ en los arcos que tienen la misma dirección que A→C  en el ciclo (el arco C→E), mientras que el flujo neto disminuye en θ para otros arcos cuya dirección es opuesta a    A→C en el ciclo (los arcos D→E y A→D). En este último caso, el nuevo flujo, en efecto, cancela un flujo de θ en la dirección opuesta. El nuevo flujo θ no afecta los arcos que no están en el ciclo (B→C).

Correspondencia entre soluciones básicas factibles y árboles de expansión factibles (IV)

Como los valores de todas estas variables satisfacen las restricciones de no negatividad y la única restricción relevante de capacidad de arco (xCE ≤ 80), el árbol de expansión es un árbol de expansión factible, por lo que se tiene una solución básica factible.

Se usará esta solución. La figura 10.16 muestra su representación como una red, a saber, el árbol de expansión, factible y su solución. Entonces, los números dados junto a los arcos ahora representan flujos (valores de las xij) en lugar del costo unitario cij dado antes. (Como ayuda para distinguirlos, los flujos se pondrán entre paréntesis, pero no los costos).

Correspondencia entre soluciones básicas factibles y árboles de expansión factibles (III)

Para ilustrar la aplicación de este teorema fundamental, considérese la red que se muestra en la figura 10.15 que resulta al sustituir xAB = 10 por xAB = 10 - yAB, en el ejemplo de la figura 10.9. En la figura 10.3e se muestra un árbol de expansión en esta red, en el que los arcos son A→D, D→E, C→E y B→C. Con éstos como arcos básicos el proceso de encontrar un árbol de expansión se muestra en seguida. En el lado izquierdo se encuentra las restricciones de los nodos dadas en la sección 10.6 después de sustituir xAB por (10-yAB), en donde las variables básicas aparecen en negritas. En el lado derecho, de arriba hacia abajo, se encuentran los pasos para establecer o calcular los valores de las variables.

Torema fundamental para el método símplex de transporte

Las soluciones básicas son soluciones de árbol de expansión (y a la inversa). Las soluciones básicas son soluciones de árboles de expansión factibles (y a la inversa).

Un árbol de expansión factible

Es un árbol de expansión cuya solución, a partir de las restricciones de nodos, también satisface todas las demás restricciones (0 ≤xij ≤ uij o 0 ≤ yij ≤ uij).

Con estas definiciones, ahora es posible resumir nuestra conclusión clave como sigue en el siguiente post.

Correspondencia entre soluciones básicas factibles y árboles de expansión factibles (II)

Entonces, las soluciones básicas factibles se pueden obtener "resolviendo" árboles de expansión como se resume a continuación:

una solución de árbol de expansión se obtiene como sigue:

1. Para los arcos que no están en un árbol de expansión (los arcos no básicos), se igualan a cero las variables correspondientes (xij o yij).
2. Para los arcos que si están en el árbol de expansión (los arcos básicos), se obtienen los valores de las variables correspondientes (xij o yij) en el sistema de ecuaciones lineales dado por las restricciones de los nodos.

(En realidad, el método símplex de redes obtiene los valores de la nueva solución básica factible a partir de la actual de una manera mucho más eficiente, sin resolver este sistema de ecuaciones desde el principio.) Nótse que este proceso de solución no considera ni las restricciones de no negatividad de árbol de expansión que se obtiene puede o no ser factibles respecto a estas restricciones; esto lleva a la siguiente definición.

Correspondencia entre soluciones básicas factibles y árboles de expansión factibles (I)

El concepto más importante que apoya el método símplex de redes es su representación como red de soluciones básicas factibles. Recuérdese que en la sección 10.6 se estableción que con n nodos, toda solución básica factible tiene (n-1)variables básicas, donde cada variable básica xij representa el flujo a través del arco i→ j. Se hace referencia a estos (n-1) como arcos básicos (De igual manera, los arcos corresponderan a variables no básicas, xij =0 o yij = 0, se llaman arcos no básicos.)

Una propiedad de los arcos básicos es que nunca forman ciclos no dirigidos. (Esta propiedad evita que la solución que se obtiene sea un promedio ponderado de otro par de soluciones factibles, lo que violaría una de las propiedades generales de las soluciones básicas factibles). Sin embargo, cualquier conjunto de (n-1) arcos que no contiene ciclos no dirigidos forma un árbol de expansión. Por lo tanto, cualquier conjunto de arcos básicos forma un árbol de expansión.

Incorporación de la técnica de la cota superior (III)

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.

Incorporación de la técnica de la cota superior (II)

Para ilustrar este proceso, considérese el problema del flujo de costo mínimo que se muestra en la figura 10.9. Mientras que el método símplex de redes genera una sucesión de soluciones básicas factibles, supóngase que en alguna iteración, xAB se convirtió en la variable básica que sale al alcanzar su cota superior de 10. En consecuencia, xAB =10 se sustituye por xAB =10 - yAB, de manera que yAB = 0 se convierte en la nueva variable no básica. Al mismo tiempo, el arco B → A sustituye al arco A → B (con yAB como su flujo), y se asigna a este nuevo arco una capacidad de 10 y un costo unitario de -2. Para tomar en cuenta xAB =10 también se disminuye bA de 50 a 40 y se aumenta bB de 40 a 50. En la figura 10.9 se muestran los ajustes que resultan

Incorporación de la técnica de la cota superior (I)

El primer concepto es incorporar la técnica de la cota superior presentada enla sección 9.1, para manejar con eficiencia las restricciones de capacidad de arco xij ≤ uij. Así, ej lugar de tratar estas restricciones como restricciones funcionales, se manejan como restricciones de no negatividad. Por lo tanto, se toman encuenta sólo al determinar la variable básica que sale. En particular, conforme se hace crecer la variable básica entrante, la variable básica que sale es la primera variable básica que llega, ya sea a su cota inferior (0) o bien a su cota superior (uij). xij = uij - yij, sustituye a una variable no básica en su cota superior xuj = uij, de manera que yij = 0 se convierte en la variable no básica. Véanse en la sección 9.1 más detalles.

En el contexto actual, yij tiene una interpretación interesante en la red. Siempre que yij se convierta en una variable básica con valor estrictamente positivo (≤ uij), se puede pensar en este vapor como en un flujo del nodo j al nodo i (o sea en la dirección "equivocada', a través del arco i→j) que en la actualidad cancela la cantidad del flujo previamente asignado (xij =uij) del nodo i al nodo j. Así, si xij = uij - yij sustituye a xij = uij, también se está sustituyendo el arco real i→j por su arco inverso j→i, en donde este nuevo arco tiene capacidad uij (la cantidad máxima del flujo xij= uij que se puede cancelar) y costo unitario -cij (ya que cada unidad de flujo cancelada ahorra cij). Para reflejar el flujo de xij = uij a través del arco eliminado, se cambia esta cantidad de flujo neto generada del nodo i al nodo j disminuyendo bi en uij unidades e incrementando bi en uij unidades. Después, si la yij se convierte en la variable básica que sale llegando a su cota superior, yij = uij se reemplaza por yij = uij - xij, con xij = 0 como la nueva variable no básica, con lo que el proceso anterior se invierte (el arco  j→i se sustituye por el arco i→j, etc. ) para regresar a la configuración original.

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.

Comentarios finales Casos especiales

Cuando sepresentaron por primera vez cada uno de estos problemas, se describieron (o almenos se hizo referencia a ellos) como algoritmos especializados para resolverlos de manera muy eficiente. Entonces, no es necesario reformular estos casos especiales para que se ajusten al problema del flujo de costo mínimo a fin de resolverlos. No obstante, cuando no se dispone de un paquete de computadora para el algoritmo especializado, resulta razonable utilizar el método símplex de redes. DE hecho, algunas aplicaciones recientes de este algoritmo han sido tan poderosas que ahora proporcionan a una alternativa excelente en lugar de los algoritmos especializados. Esto es verdad en especial para el problema de trasbordo (sin capacidades) y, en alguna medida, para el problema de transporte.

El hecho de que estos cinco problemas sean casos espciales del problema del flujo de costo mínimo también es de interés por otras razones. Una es que la teoría que soporta el problema del flujo del costo minimo y el método símplex de redes proporcionan una teoría unificadora para todos estos casos especiales. Otra es que algunas aplicaciones del problema del flujo de costo mínimo incluyen características de uno o más casos especiales, así que es importante saber cómo reformular estas características dentro del contexto más amplio del problema general.

Casos especiales - Problema del flujo máximo

El último caso especial que se considerará es el problema del flujo máximo descrito en la sección 10.5. En este caso, la red ya tiene un nodo origen y un nodo destino y varios nodos de trasbordo, al igual que varios arcos y capacidades en los arcos. Sólo se necesitan tres ajustes para que este  problema quede en el formato del problema del flujo de costo mínimo. Uno es hacer cij = 0 para todos los arcos existentes para reflejar la ausencia de costos en el problema del flujo máximo. Otro es elegir una cantidad F que sea una cota superiro segura sobre el flujo factible máximo a través de la red y después asignar una cantidad  de recursos y de demanda a F en los nodos de recursos y de demanda, respectivamente. El tercero es agregar un arco que va directamente del nodo de recursos al nodo de demanda y asginarle un costo unitario arbitrariamente grande cij=M y una capacidad de arco ilimitado (uij = ∞ ). Debido a este costo tan alto, el problema del flujo de costo mínimo mandará el máximo flujo factible a través de los otros arcos, lo que logra el objetivo del problema de flujo máximo

La aplicación de esta formulación al problema del flujo máximo en Seervada Park que se muestra en la figura 10.5, conduce a la red dada en la figura 10.14.

Casos especiales - El Problema de la ruta mas corta

Ahora se considerará la versión del problema de la ruta más corta presentada en la sección 10.3 (encontrará la ruta más corta desde un origen a un destino a través de una red no dirigida). Para formular este problema como un problema del flujo de costo mínimo se establece el origen como un nodo de recursos con una cantidad de 1, el destino como un nodo de demanda con una demanda de 1 y el restode los nodos son nodos de trasbordo. DEbido a que la red para el problema de la ruta m;as corta es no dirigida, mientras que se supone que el problema del flujo de costo mínimo tiene una red dirigida, cada ligadura se sustituye por un par de arcos dirigidos en direcciones opuestas (dibujados como una sola línea con cabezas de flechas en ambas terminales). Las únicas expceciones son que no hay necesidad de preocuparse por aros que llegan al nodo origen ni que salen de nodo destino. La distancia entre los nodos i y j se convierten en unidades de costo cij o cji para el flujo, en cualquier dirección entre estos nodos. Igual que con los casos especiales anteriores no se imponen capacidades a los arcos por lo que todo uij = ∞.

La figura 10.13 muestra que esta formulación para el problema de la ruta más corta, para Seervada Park que se presentó en la figura 10.1, en donde los números cerca de las líneas ahora representan el costo unitario del flujo en cualquier dirección.

Casos especiales - El Problema de Asignación

Como el problema de asignación presentado en la sección 7.4 es un tipo especial de problema de transporte, su formulación como un problema del flujo de costo mínimo se ajusta al formato que se ilustra 10.10. Los cambios adicionales son que 1) el número de nodos de recursos es igual al número de nodos de demanda, 2) bi = 1 para cada nodo de recursos y 3) bi =-1 para cada nodo de demanda.

La figura 10.12 muestra esta formulación para el problema de asignación de la Job Shop Co., que se presento en la tabla 7.27.

Casos especiales - El Problema de Trasbordo

Recuérdese que el problema de trasbordo presentado en la sección 7.3 es la generalización del problema de transporte, en donde las unidades distribuidas de un origen a un destino pueden pasar primero por puntos intermedios que pueden ser puntos de trasbordo y otros orígenes o destinos. Por lo tanto, la formulación del problema de trasbordo como un problema de flujo de costo mínimo es la misma que para el problema de transporte, excepto que ahora se pone un nodo de trasbordo por cada punto de trasbordo y se agregan arcos por cada viaje intermedio factible desde un punto (origen, punto de trasbordo o destino) a otro.

Con estas conversiones, la formulación en realidad incluye todas las características generales del problema del flujo de costo mínimo, excepto por no tener capacidades (finitas) en los arcos. Por esta razón, algunas veces se hace referencia al problema de flujo de costo mínimo como el problema de trasbordo capacitado.

Utilizando esta formulación para el problema de trasbordo de la P&T Co., presentado en la tabla 7.24 se llega a la red que se muestra en la figura 10.11 Como cada arco tiene un arco que lo acompaña en la dirección opuesta entre el mismo par de nodos, se ha simplificado el dibujo de esta red poniendo una sola ligadura con cabezas de flecha en las dos terminales para representar los dos arcos. También se quitaron los valores de las cij pero se incluyen todos en la tabla 7.27.

Casos especiales - El Problema de Transporte

Para formular el problema de transporte que se presentó en la sección 7.1  como un problema de flujo de costo mínimo, se proporciona un nodo de recursos para cada origen y un nodo de demanda para cada destino pero no se incluyen nodos de trasbordo en la red. Todos los arcos son dirigidos, desde el nodo de recursos hacia el nodo de demanda, en donde distribuir xij unidades del origen i al destino j corresponde a un flujo de xij a través del arco i→j. El costo cij por unidad distribuida se convierte en el costo cij por unidad de flujo. Como el problema de transporte no impone restricciones de cota superior sobre las xij individuales, todas las uij = ∞ .

Utilizando esta formulación para el problema de transporte de la P&T Co. presentado en la sección 7.2 se llego a la red que se muestra en la figura 10.10

Propiedad de soluciones enteras (III)

Ahora obsérvese el patrón de coeficientes para  cada variable en el conjunto de cinco restricciones de arco. Cada variable tiene exactamente dos coeficientes distintos de cero, uno es +1 y el otro es -1. Este patrón aparece en todos los problemas de flujo de costo mínimo y es esta estructura especial la que lleva a la propiedad de soluciones enteras.

Otra consecuencia de esta estructura especial es que una (cualquiera) de las restricciones de arco es redundante. La razón es que si se suman todas estas ecuaciones sólo se obtienen ceros en ambos lados (suponiendo que existen soluciones factibles para que las bi sumen cero), por lo que el negativo de cualquier ecuación es igual a la suma de las demás. Con (n-1) restricciones de arco no redundantes, estas ecuaciones proporcionan exactamente (n-1) variables básicas para una solución básica factible. En la siguiente sección se verá que el método símplex de redes trata las restricciones xij ≤ uij como simétricas de las restricciones  de no negatividad; así, el número total de variables básicas es (n-1). Esto conduce a una correspondencia directa entre los (n-1) arcos de un árbol de expansión y las (n-1) variables básicas. Se hablará más sobre esto más adelante.

Pronto se resolverá este ejemplo aplicando el método simplex de transporte. Pero ahora se analizará la manera en que los cinco casos especiales mencionados se ajustan al formato del problema del flujo de costo mínimo. Para cada caso, se mostrará cómo formular su ejemplo prototipo en esta forma más general.

Propiedad de soluciones enteras (II)

Los valores de bi se muestran dentro de paréntesis cuadrados cerca de los nodos,entonces, los nodos origen (bi>0) son A y B,los nodos destino (bi<0
El modelo de programación lineal para este ejemplo es

Propiedad de soluciones enteras (I)

Para los problemas del flujo de costo mínimo en donde todo bi y uij tienen un valor entero, todas las variables básicas en cada solución factible (incluyendo la óptima) tendrán también valores enteros.

En la figura 10.9 se muestra un ejemplo del problema de flujo de costo mínimo. Esta es la misma que la de la figura 10.2, excepto que ahora se agregaron los valores de bi, cij, y uij.

Formulación (III)

Si los valores de bi que se dan en alguna aplicación violan esta condición, la interpretación más común es que los recursos  o las demandas (el que tenga exceso) representan en realidad cotas superiores y no cantidades exactas. Cuando esta situación surgió en el problema de transporte en la sección 7.1, se aumentaba un destino ficticio para recibir los recursos que sobraban o bien se aumentaba un origen ficticio par mandar en exceso de demanda. El paso análogo en este caso es que debe agregarse un nodo de demanda ficticio para absorber el exceso de recurso (agregando arcos con cij =0 desde todos los nodos de origen hasta este nodo), o bien debe agregarse un nodo de origen ficticio para generar un flujo equivalente al exceso de demanda (agregando arcos con cij=0 desde todos los nodos origen hasta este nodo), o bien debe agregarse un nodo origen ficticio para generar un flujo equivalente al exceso de demanda (agregando arcos con cij = 0 desde este nodo hasta todos los nodos de demanda).

En la práctica, con frecuencia las cantidades bi y uij tendrán valores enteros y la solución requerirá que las cantidades de flujo (las xij) sean también enteros. Por fortuna, igual que para el problema de transporte, este tipo de solución está garantizado sin tener que establecer restricciones enteras en forma explicita sobre las variables. Esto se debe a la siguiente propiedad.

Formulación (II)

La primera suma en las restricciones de los nodos representa el flujo total que sale del nodo i, mientras que la segunda suma representa el flujo total que entra al nodo i; así, la diferencia es el flujo neto generado en este nodo.

En algunas aplicaciones, es necesario tener una cota inferior Lij > 0 para el flujo por cada arco i→ j. Cuando esto ocurre se hace una traslación de variables , xij = xij - Lij, donde xij se sustituye por (x'ij + Lij) en todo el modelo, con el fin de ajustar el modelo al formato anterior con restricciones de no negatividad.

No se garantiza que el problema posea soluciones factibles; esto depende en parte de que arcos se tienen en la red y de sus capacidades. De cualquier manera, para una red diseñada razonablemente, la condición necesaria más importante es la siguiente:

Formulación (I)

Considérese una red conexa dirigida en la que los n nodos incluyen al menos un nodo origen y al menos un nodo destino. Las variables de decisión son:

Problema del flujo de costo mínimo

El problema del flujo de costo mínimo tiene una posición medular ente los modelos de optimización de redes; primero,  porque abarca una clase muy amplia de aplicaciones y segundo, porque su solución es en extremo eficiente. Al igual que el problema del flujo máximo, toma en cuenta un flujo a través de una red con capacidades limitadas en sus arcos. Al igual que el problema de la ruta más corta, considera un costo (o distancia) para el flujo a través de un arco. Al igual que el problema de transporte o el problema de asignación del capítulo 7, puede manejar varios orígenes (nodos fuente) y varios destinos (nodos demanda) para el flujo, también con costos asociados. Al igual que el problema de trasbordo del capítulo 7, puede considerar varios puntos de conexión (nodos de trasbordo) entre los orígenes y los destinos para este flujo. De hecho, estos cinco problemas estudiados son casos especiales del problema del flujo de costo mínimo, como se verá enseguida.

La razón por al que el problema del flujo de costo mínimo se puede resolver de manera tan eficiente es que se puede formular como un problema de programación lineal, y por tanto, se puede resolver mediante una versión simplificada del método símplex llamada método símplex de redes. En la siguiente sección se describirá este algoritmo.

Ejemplo Algoritmo para el problema del flujo máximo (V)

Aunque el procedimiento de la figura 10.7 es relativamente sencillo, será útil poder reconocer cuándo se tiene un patrón óptimo sin tener que buscar de manera exhaustiva una ruta que no existe. A veces es posible esto con el resultado de un teorema importante de teoría de redes, conocido como el teorema del flujo máximo cortadura mínima. Una cortadura se puede definir como cualquier conjunto de arcos dirigidos que contienen al menos un arco de cada tayectoria dirigida que va del nodo origen al nodo destino. El valor de la cortadura es la suma de las capacidades de los arcos (en las dirección específica) de la cortadura. El teorema del flujo máximo-cortadura mínima establece que para cualquier red con un solo nodo origen y un solo nodo destino, el flujo máximo factible del origen al destino es igual al valor de la cortadura mínima para todas las cortaduras de la red. Así, si F denota la cantidad de flujo del origen al destino para cualquier patrón de flujo factible, el valor de cualquier cortadura proporciona una cota superior para F, y el menor de los valores de las cortaduras es igual al máximo valor de F. Entonces, si se puede encontrar, en la red original, una cortadura cuyo valor sea igual al valor actual de F encontrado con el procedimiento de solución, el patrón de flujo actual debe ser óptimo. Eventualmente se alcanza la optimalidad siempre que exista una cortadura cuyo valor sea cero en la red residual.

Para ilustrar esto, considérese en la figura 10.5 la cortadura que se indica en la figura 10.8. Nótese que el valor de la cortadura es (3+4+1+6) =14 que, según se había encontrado , corresponde al máximo el valor de F, por lo que se tata de una cortadura mínima. Nótese también que en la red residual obtenida en la iteración 7, en donde  = 14, la cortadura correspondiente tiene el valor cero. Si estos se hubiera observado, no habría sido necesario buscar trayectorias aumentadas adicionales.

Ejemplo Algoritmo para el problema del flujo máximo (IV)

La parte más difícil de este algoritmo, cuando se trabaja con redes muy grandes, es encontrar una trayectoria aumentada. ESta tarea se puede simplificar con un procedimiento sistemático. Se comienza por determinar todos los nodos que se pueden alcanzar desde el origen con un sólo arco con capcidad residual positiva. Después, para caa uno de estos nodos alcanzados, se determinan todos los nuevos nodos (entre los que no han sidos alcanzados) a los que se puede llegar desde este nodo con un solo arco con capacidad residual positiva. Esto se repite con los nuevos nodos conforme se van alcanzando. El resultado será la identificación de un árbol con todos los nodos a los que se puede llegar desde el origen, a lo largo de una trayectoria con capcidad de flujo residual positiva. ESte procedimiento de abanico siempre identificará una trayectoria aumentada, si existe el origen al destino con una capacidad de flujo positivo. En la figura 10.7 se ilustra esto para la red que se obtiene en la iteración 6 del ejemplo anterior.

Ejemplo Algoritmo para el problema del flujo máximo (III)

Si se emplea este último método, existe un flujo a través de un arco si la capacidad residual final es mejor que la capacidad original. La magnitud de este flujo es igual a la diferencia entre estas capacidades. En la figura 10.6 se muestra el patrón de flujo óptimo que resulta al comparar la red que se obtuvo en la última iteración con la figura 10.5.

Este ejemplo ilustra en forma sencilla la razón para sustituir el arco i →j en la red residual y después aumentar en c* la capacidad residual de éste último cuando se asigna un flujo de c* al arco i →j. Sin este refinamiento, las primeras seis iteraciones no cambian, pero en ese momento pareceria que ya no quedan trayectorias aumentadas (ya que la capacidad de flujo real sin usar de E → B es cero). El refinamiento permite agregar la asignación de un flujo de 1 para O→C→E→B→D→T en la iteración 7. En efecto, esta asignación adicional cancela una unidad de flujo asignada en la iteración 1 (O→B→E→T) y la sustituye por las asignaciones de una unidad a las dos rutas O→B→D→T y O→C→E→T.

Ejemplo Algoritmo para el problema del flujo máximo (II)

El patrón de flujo actual se puede identificar ya sea al acumular las asignaciones de flujo o al comparar las capacidades residuales con las capacidades de flujo originales

Ejemplo Algoritmo para el problema del flujo máximo (I)

A continuación se resume la aplicación de este algoritmo al problema de Seervada Park (véase en la figura 10.5 la red original). En cada iteración se muestra la red residual después de completar los tres pasos, en donde se usa una sola línea para representar el par de arcos dirigidos en direcciones opuestas entre cada par de nodos. La capacidad residual del arco i→j se muestra junto al nodo i, mientas que la capacidad residual del arco j→i se muestra junto al nodo j. Utilizando este formato, la red que se muestra en la figura 10.5 es en realidad la red residual antes de asignar ningún flujo. Después de algunas iteraciones, se muestran en negritas (junto a los nodos O y T)la cantidad total del flujo que se logra.

Algoritmo para el problema del flujo máximo (II)

Al realizar el paso 1, con frecuencia habrá varias alternativas de trayectorias aumentadas entre las cuales se podrá escoger. Aunque la estrategia algorítmica para elegir tiene alguna importancia para la eficiencia en las aplicaciones a gran escala, no se profundizará en este tema relativamente especializado. (Más adelante en esta sección, se describe un procedimiento sistemático para encontrar una trayectoria aumentada.) Entonces, para el siguiente ejemplo (y los problemas al final del capítulo), la selección se hará en forma arbitraria.

Algoritmo para el problema del flujo máximo (I)

1. Se identifica una trayectoria aumentada encontrando alguna trayectoría dirigida del nodo origen al nodo destino en la red residual tal que cada arco sobre esta trayectoria tiene capacidad residual estrictamente positiva. (Si no existe una, los flujos netos ya asignados constituyen un patrón de flujo óptimo).
2. Se identifica la capacidad residual c* de  esta trayectoria aumentada encontrando el mínimo de las capacidades residuales de los arcos sobre esta trayectoria. SE aumenta en c* el flujo de esta trayectoria.
3. Se disminuye en c* la capacidad residual de cada arco en esta trayectoria aumentada. Se aumenta en c* la capacidad residual de cada arco en la dirección opuesta en esta trayectoria. Se regresa al paso 1.

Una trayectoria aumentada

Es una trayectoria dirigida del nodo fuente al nodo destino en la red residual, tal que todos los arcos en esta trayectoria tienen capacidad residual estrictamente positiva. El mínimo de estas capacidades residuales se llama capacidad residual de la trayectoria aumentada porque representa la cantidad de flujo que es factible aumentar en toda la trayectoria. Por lo tanto, cada trayectoria aumentada proporciona una oportunidad de aumentar más el flujo a través de la red original.

El algoritmo de la trayectoria aumentada selecciona repetidas veces algunas trayectoria aumentada y agrega un flujo igual a su capacidad residual en la red original. Este proceso continúa hasta que ya no hay trayectorias aumentadas, con lo que el flujo del nodo fuente al nodo destino no se puede aumentar. La clave para asegurar que la solución final es necesariamente óptima es el hecho de que las trayectorias aumentadas pueden cancelar flujos asignados con anterioridad en la red original; así, una selección indiscriminada de trayectorias para asignar flujos no puede evitar el uso de una combinación mejor de asignaciones de flujos.

Para resumir, cada iteración del algoritmo consiste en los tres pasos siguientes.

Problema del Flujo Máximo (III)

En principio, la red residual difiere de la red original sólo en que cada arco dirigido (i→ j) que no tiene arco dirigido en la dirección opuesta (j → i) ahora se le agrega con capacidad cero. Después, las capacidades de los arcos en la red residual (llamadas capacidades residuales) se ajustan de la siguiente manera. Cada vez que se agrega una cantidad de flujo Δ a un arco i → j en la red original, la capacidad residual del arco i→ j se disminuye en Δ, pero la capacidad residual de arco j →i se aumenta en Δ. Así, la capacidad residual representa la capacidad del arco que no se usa en la red original o la cantidad de flujo en la dirección opuesta en esta red que se puede cancelar (o una combinación de ambas, si la re original tiene arcos en las dos direcciones). Así, después de asignar los diferentes flujos a la red original, la red residual muestra que tanto más se puede hacer ya se aumentando más lo flujos o cancelado los que se asignaron antes.

Problema del Flujo Máximo (II)

Para hacer que el problema de Seervada Park se ajuste formalmente a este formato con una red dirigida, cada ligadura 10.5 con 0 en un punto terminal se sustituirá por un arco dirigido en la dirección factible. Por ejemplo, la ligadura entre los nodos O y A se sustituye por un arco dirigido del nodo O al nodo A con una capacidad de 5. Las dos ligaduras con un 1 en los extremos (AB y DE) se sustituyen por un par de arcos dirigidos en direcciones opuestas, cada uno con capacidad de 1. Considerando que estos cambios se llevan a cabo, se seguirá operando sobre la red que se muestra en la figura 10.5

Como el problema de flujo máximo se puede formular como un problema de programación lineal (véase el problema 11),se puede resolver con el método símplex. Sin embargo, se dispone de un algoritmo de trayectorias aumentadas mucho más eficiente. Este algoritmo se basa en dos conceptos intuitivos, el de una red residual y el de una trayectoria aumentada.

Problema del Flujo Máximo (I)

Recuérdese que el tercer problema al que se enfrenta el administrador de Seervada Park (véase la sección 10.1) durante la temporada pico es determinar las rutas de algunos viajes de tranvía desde la entrada del parque (estación O en la figura 10.1) al mirador (estación T), de manera que el número de viajes diarios sea mínimo. (Cada tranvía regresará por la misma ruta que tomó de ida, por lo que el análisis se hará sólo sobre los viajes de ida.) Se impusieron límites superiores estrictos sobre el número de viajes de ida permitidos en cada dirección para cada ruta individual. Los límites se muestran en la figura 10.5, en la que los números que aparecen al lado de cada estación sobre los caminos dan el límite superior para ese camino en la dirección de salida de la estación. Por ejemplo, sólo se permite un viaje al día de la estación A a la estación B, pero también se permite otro de la estación B a la estación A. Dados los límites, una solución factible es mandar siete tranvias al día, cinco por la ruta O→ B→ E→ T, uno por la ruta O→ B→ C→ E→ T y otro por O→ B→ C→ E→ D→ T. Pero esta solución bloquea el uso de cualquier ruta que comience con O→ C (porque las capacidades de E→ T y E→ D están saturadas) Es sencillo encontrar mejores soluciones factibles. Es necesario considerar muchas combinaciones o rutas (y el número de viajes asignados a cada una) para encontrarla o las que maximicen.

Con la terminología que se introdujo en la sección 10.2, el problema del flujo máximo se puede describir formalmente como sigue. Considérese una red dirigida y conexa que tiene un solo nodo fuente y un solo nodo destino, y el resto son nodos de trasbordo. Dada la capacidad en los arcos, el objetivo es determinar el patrón factible que fluye a través de la red que maximiza el flujo total, desde el nodo fuente al nodo destino.

Ejemplo Algoritmo para el problema del árbol de mínima expansión (III)

Todos los nodos han quedado conectados, por lo que ésta es la solución (óptima) que se buscaba. La longitud total de las ramas es 14 millas.

Aunque con este procedimiento a primera vista puede parecer que la elección del nodo inicial afectaría la solución final (y la longitud total de las ligaduras), en realidad no es así. Se sugiere que se verifique este hecho en el ejemplo, aplicando de nuevo el algoritmo, pero iniciando en un nodo distinto de O.

Se considera que dentro de este capítulo el problema del árbol de expansión mínima es el que cae dentro de la amplia categoría de diseño de redes. En esta categoría, el objetivo es diseñar la red más apropiada para el problema dado (con frecuencia se trata de sistemas de transporte) y no analizar una red ya diseñada. La referencia selecta 10 proporciona una investigación en esta importante área.

Ejemplo Algoritmo para el problema del árbol de mínima expansión (II)

En forma arbitraria, se selecciona el nodo O para comenzar. El nodo no conectado más cercano a O es el nodo A. Se conecta el nodo A al nodo O.

Ejemplo Algoritmo para el problema del árbol de mínima expansión (I)

La administración de Seervada Park (véase la sección 10.1) necesita determinar los caminos bajo los cuales se deben tener líneas telefónicas para conectar todas las estaciones con una longitud total de cable mínima. Se describirá paso a paso la solución de este problema con base en los datos que se dan en la figura 10.1.

Los nodos y distancias para el problema se resumen enseguida, en donde las líneas delgadas ahora representan ligaduras potenciales.

Algoritmo para el problema del árbol de mínima expansión

1. Se selecciona, de manera arbitraria, cualquier nodo y se conecta (es decir se pone una ligadura) al nodo más cercano distinto de éste.
2. Se identifica el nodo no conectado más cercano a un nodo conectado, y se conectan estos dos nodos (es decir, se agrega una ligadura entre ellos). Este paso se repite hasta que se hayan conectado todos los nodos.

Empates: los empates para el nodo más cercano distinto (paso 1) o para el nodo no conectado más cercano (paso 2), se pueden romper en forma arbitraria y el algoritmo todavía debe llevar a una solución óptima. No obstante, estos empates son señal de que pueden existir (pero no necesariamente) soluciones óptimas múltiples. Todas esas soluciones se pueden identificar si se buscan las demás formas de romper los empates hasta el final.

La manera más rápida de ejecutar este algoritmo en forma manual es el enfoque gráfico que se ilustra en seguida.

Problema del árbol de expansión mínima (II)

Este problema tiene muchas aplicaciones prácticas importantes. Por ejemplo, puede ser útil en la planeacion de redes de transporte que no se transmitirán mucho y en las que la inquietud principal es proporcionar algún tipo de conexión entre todos los pares de nodos de la manera más ecónomica. Los nodosserán las localidades que requieren acceso a otras localidades, las ligaduras serían las líneas de transporte (carreteras, vias de ferrocarril, vias aereas, etc.) y las "distancias" (valores de las ligaduras) serían los costos de proporcionar la comunicación. En este contexto, el problema del árbol de mínima expansión tiene como  objetivo determinar cuáles serián las líneas de comunicación que darían servicio a todas las localidades con un costo total mínimo. Otros ejemplos en los que surge una decisión parecida incluyen la pleanación de redes de comunicación y redes de distribución de gran escala. Ambos representa áreas de aplicación importantes.

El problema del árbol de mínima se puede resolver de una forma bastante directa, pues ocurre que se trata de uno de los pocos problemas de investigación de operaciones el que la codicia en cada etapa del procedimiento de solución iconduce al final a una solución óptima. Así, con el inicio en cualquier nodo, la primera etapa consiste en elegir la rama más corta posible a otro nodo, sin preocuparse del efecto que esta elección pueda tener en las decisiones posteriores. En la segunda etapa se trata de identificar el nodo no conectado que esté más cerca de cualquiera de los dos que se acaban de conectar y después agregar la ligadura correspondiente la red. Este proceso se repetirá, según el resumen que se da a continuación, hasta que se hayan conectado todos los nodos. Se garantiza que la red resultante es un árbol de mínima expansión.

Problema del árbol de expansión mínima (I)

El problema del árbol de expansión mínima tiene algunas similitudes con la versión principal del problema de la ruta más corta que se presentó en la sección anterior. En ambos casos se considera una red no dirigida, en la que la información dada incluye los nodos y las distancias entre pares de nodos. Sin embargo, la diferencia crucial para el problema del árbol de expansión mímina es que las ligaduras (arcos no dirigidos) ya no se especifican. Entonces, en lugar de encontrar la ruta más corta a través de una red completamente definida, el problema elige las lugaduras en la red que tenga la longitud total más corta al mismo tiempo que proporciona una trayectoria ente cada par de nodos. Es necesario que las ligaduras se elijan de tal manera que la red resultante forme un árbol (según la definición dada en la sección ) que se expande (conecta) todos los nodos dados. En resumen, el programa es encontrar el árbol de expansión con la longitud total mínima de sus ligaduras.

La figura ilustra el concepto de árbol de expansión para el problema de Seervada Park. La sección a no es un árbol de expansión, pues los nodos (O,A, B, C) no están conectados con los nodos (D,E,T). Se necesita una rama más para hacer esta conexión. En realidad esta red consiste en dos árboles, uno para cada conjunto de nodos. Las ligaduras de la figura 10.4b si  se expanden por toda la red (esto es,  es una gráfica conexa según la definición de la sección 10.2) pero no es un árbol porque tiene dos ciclos (0-A-B-C-O Y D-T-E-D). Tiene demasiadas ligaduras. El problema de Seervada Prak tiene n=7 nodos, y coo se indicó en la sección 10.2, una red debe tener justo (n-1)= 6 ligaduras y no tener ciclos para calificar como un árbol de expansión. Esta condición se logra en la figura 10.4c, por lo que esta red es una solución factible (con una longitud total de 24 millas en las ramas) para el problema del árbol de mínima expansión.

Otras aplicaciones (II)

Otra versión del problema de la ruta más corta es encontrar las rutas más cortas del origen a todos los demás nodos de la red. Nótese que el algoritmo obtiene las rutas más cortas a cada nodo que está más cerca del origen que el destino. Entonces, si todos los nodos son destinos potenciales, la única modificación que se necesita es que el algoritmo no se detenga, hasta que todos los nodos se hayan resuelto.

Otra versión aún más general del problema de la ruta más corta es encontrar la ruta más corta desde todos los nodos a todos los demás nodos. Otra opción es eliminar la restricción de que las "distancias" (valores de los arcos) sean no negativas. Se pueden poner también restricciones sobre las trayectorias que se pueden seguir. Todas estas variaciones surgen en ocasiones  en la práctica y por esto han sido estudiadas por los investigadores.

Los algoritmos para una gran variadad de problemas de optimizanción de análisis combinatorio - como los problemas de diseño de ruta de vehículos- con frecuencia utlizan como parte de sus subrutinas, la solución de un gran número de problemas de la ruta más corta. Aunque no se dispone de espacio suficiente para profundizar en este tema, tal vez esta aplicación sea una de las más importantes de este algoritmo.

Otras aplicaciones (I)

Antes de concluir con la presentación del problema de la ruta más corta, es necesario hacer hincapié en un punto. Hasta aquí, se ha descrito el problema en términos de minimizar la distancia de un origen a un destino. Sin embargo, en realidad el problema de redes que se estudia es el de encontrar cuál es la ruta que conecta a dos nodos específicos que minimiza la suma de los valores de las ligaduras sobre esa ruta. Por ejemplo, las ramas pueden corresponder a actividades de algún tipo y los valores asociados a cada una pueden representar el costo de esa actividad entonces, el problema sería encontrar qué secuencia de actividades logra el objetivo específico de minimizar el costo total relacionado. (Véase el problema 2.) Otra  posibilidad consiste en que el valor asociado a cada ligadura sea el tiempo requerido para realizar esa actividad. En este caso se desearía encontrar la secuencia de actividades que logra el objetivo específico de minimizar el tiempo total requerido. (véase el problema 6). Así, algunas de las aplicaciones más importantes del problema de la ruta más corta no tienen nada que ver con caminos en el sentido normal de la palabra.

Muchas aplicaciones requieren encontrar la trayectoria dirigida del origen al destino de una red dirigida. El algoritmo que acaba de presentarse se puede modificar con facilidad para que maneje trayectorias dirigidas en cada iteración. En particular, cuando se identifican candidatos para el n-ésimo nodo más cercano, sólo se considerarán los arcos dirigidos desde un nodo resuelto a un nodo no resuelto.

Problema Algoritmo de la ruta más corta

La administración de SEervada Park necesita encontrar la ruta más corta desde la entrada del parque (nodo O) al mirador (nodo T) a través del sistema de caminos que se muestra en la figura 10.1. En la tabla 10.2 se encuentran los resultados obtenidos al aplicar el algoritmo anterior a este problema (en donde el empate para el segundo nodo más cercano). La primera columna (n) indica el número de la iteración. La segunda columna da una lista de los nodos resueltos para comenzar la iteración actual, después de quitar los que no sirven (aquellos que no tienen conexión directa con nodo no resueltos). La tercera columna da los candidatos para el n-ésimo nodo más cercano (los nodos no resueltos con la ligadura más corta  al nodo resuelto). La cuarta columna calcula la distancia de la ruta más corta desde el origen a cada uno de los estos candidatos (esto es, la distancia al nodo resuelto más la distancia de la ligadura que va al candidato). El candidato con la suma de distancias más pequeñas es el n-ésimo nodo más cercano al origen, el cual se indica en la quinta columna. Las dos últimas columnas resumen la información de este último nodo resuelto necesaria para pasar las iteraciones siguientes (a saber, la distancia de la ruta más corta desde el origen a este nodo y la última rama en esta ruta más corta).

La ruta más corta desde es el nodo destino hasta el origen se puede rastrear hacia atrás en la última columna de la tabla 10., con lo que se obtiene T→D→E→B→A→O o bien T→D→B→A→O. Por tanto,, se identificaron las dos opciones para la ruta más corta desde el origen hasta el destino como las cadenas O→A→B→E→D→T y O→A→B→D→T, con una distancia total de 13 millas en cualquiera de las dos rutas.

Algoritmo de la ruta más corta (II)

Candidatos para el n-ésimo nodo más cercano: cada nodo resuelto que está conectado directamente por una ligadura con uno o más nodos no resueltos proporciona un candidato, y éste es el nodo no resuelto que tiene la ligadura más corta.

Cálculo del n-ésimo nodo más cercano: para cada nodo resuelto y sus candidatos, se suma la distancia entre ellos y la distancia de la ruta más corta desde el origen a este nodo resuelto. El  candidato con al distancia total más pequeña es el n-ésimo nodo más cercano (los empates proporcionan nodos resueltos adicionales), y su ruta más corta es la que genera esta distancia.

Algoritmo de la ruta más corta (I)

Objetivo de la n-ésima iteración: encontrar el n-ésimo nodo más cercano al origen. (Este paso se repetira para n = 1,2....., hasta que el n-ésimo nodo más cercano sea el nodo destino).

Datos para la n-ésima iteración: (n-1) nodos más cercanos al origen (encontrados en las iteraciones previas), y también su ruta más corta y la distancia desde el origen. (Estos nodos y el origen se llamarán nodos resueltos; el resto son nodos no resueltos)

Problema de la ruta más corta

Aunque al final de la sección se mencionan otras versiones del problema de la ruta más corta (incluyendo algunas para redes dirigidas), la atención se centrará en la siguiente versión sencilla. Considérese una red conexa y no dirigida con dos nodos especiales llamados origen y destinos. A cada una de las ligaduras (arcos no dirigidos) se asocia una distancia no negativa. El objetivo es encontrar la ruta más corta (la trayectoria con la mínima distancia total) que va del origen al destino.

Se dispone de un algoritmo relativamente sencillo para este problema. La esencia de este procedimiento es que analiza toda la red a partir del origen, identificando sucesivamente la ruta más corta a cada uno de los nodos en orden ascendente de sus distancias (más cortas), desde el origen, quedando resuelto el problema en el momento de llegar al nodo destino. Primero se describirá el método y después se ejempleficara con la solución del problema de la rauta más corta que enfrenta la administración de Seervada Park en la sección 10.1

Terminología de redes (V)

Considérese un conjunto de n nodos (por ejemplo, n=5 nodos en la figura 10.2) sin arcos. Se puede entonces "hacer crecer" un "árbol" agregando un arco (o rama) a la vez de cierta manera. El primer arco puede ir a donde sea para conectar algún par de nodos. De ahí en adelante, cada arco nuevo debe agregarse entre un nodo que haya sido conectado a otros nodos y a un nuevo nodo no conectado. Si se agregan arcos de esta manera, se evita que se forme un ciclo y además se asegura que el número de nodos conexos es uno más que el número de arcos. Cada nuevo arco crea un árbol más grande, que es una red conexa (para algún subconjunto de n nodos) que no contiene ciclos no dirigidos. Una vez que se ha agregado el (n-1)-ésimo arco, el proceso se detiene porque el árbol resultante se expande (conecta) a todos los n nodos.

Este árbol se llama árbol de expansión, y es una red conexa para los n nodos que no contiene ciclo no dirigidos. Todo árbol de expansión tiene exactamente (n-1) arcos, ya que este es el mínimo número de arcos necesarios para tener una red conexa y el máximo número posible para que no hay ciclos no dirigidos.

La figura 10.3 muestra los cinco nodos y algunos de los arcos de la figura 10.2 para ilustrar este proceso de hacer crecer un árbol poniendo un arco (rama) a la vez, hasta que se obtiene un árbol de expansión. En cada etapa se tienen varias alternativas para el nuevo arco,por lo que la figura 10.3 muestra sólo una de las muchas formas de construir un árbol de expansión en este caso. Ahora bien, obsérvese cómo cada nuevo arco que se agrega satisface las condiciones especificadas en el párrafo anterior. Los árboles de expansión se estudiarán más a fondo en la sección 10.4.

Los árboles de expansión juegan un papel clave en el análisis de muchas redes. Por ejemplo, forman la base del problema del árbol de mínima expansión que se presenta en la sección 10.4. Otro ejemplo es que los árboles de expansión (factibles) corresponden a las soluciones básicas factibles en el método símplex de redes que se analiza en la sección 10.6.

Por último, será necesario introducir la terminología adicional sobre los flujos en redes. La cantidad máxima de flujo (quizá infinito) que puede circular en un arco dirigido se conoce como capacidad del arco. Entre los nodos, se pueden distinguir aquellos que son generadores de flujo, absorbedores netos o ninguno de los dos. Un nodo fuente (o nodo de origen) tiene la propiedad de que el flujo sale del nodo excede el flujo que entra a él. El caso inverso es un nodo demanda (o nodo destino), en el que el flujo que llega excede al que sale del nodo. Un nodo de trasbordo (o nodo intermedio)satisface la conservación del flujo, así el flujo que entra es igual al que sale.

Terminología de redes (IV) - Ciclo y nodos están conectados

Un ciclo es una trayectoria que comienza y termina en el mismo nodo. En una red dirigida un ciclo puede ser dirigido o no dirigido, según si la trayectoria en cuestión es dirigida o no dirigida. (como una trayectoria dirigida también es no dirigida, un ciclo dirigido es un ciclo no dirigido, pero en general el inverso no es cierto). Por ejemplo, en la figura 10.2, DE-ED es un ciclo dirigido. Por el contrario, AB-BC-AC es un ciclo no dirigido puesto que la dirección del arco AC es opuesta a la de lo arcos AB y BC. Por otro lado, AB-BC-AC es un ciclo no dirigido por que A→B→C→A es una trayectoria no dirigida. En la red no dirigida que se muestra en la figura 10.1 existen muchos ciclos, por ejemplo, OA-AB-BC-CO. DE cualquier forma, nótese que la definición de trayectoria (una sucesión de arcos distintos) elimina la posibilidad de retroceder al formar un ciclo. Por ejemplo, OB-BO en la figura 10.1 no califica como ciclo, porque OB y BO son dos etiquetas para el mismo arco (ligadura). Por otra parte, en la figura 10.2, DE-ED es un ciclo (dirigido) por que DE y ED son arcos distintos.

Se dice que dos nodos están conectados si la red contiene al menos una trayectoria no dirigida entre ellos. (nótese que no es necesario que la trayectoria sea dirigida aun cuando la red es dirigida) Una red conexa es una red en la que cada para de nodos está conectado. Entonces, la redes de las figuras 10.1 y 10.2 son ambas conexas. La última red no sería conexa si se eliminaran los arcos AD y CE.

Terminología de redes (III)

Cuando dos nodos no están unidos por un arco surge la pregunta natural de si están conectados por una serie de arcos. Una trayectoria entre dos nodos es una sucesión de arcos distintos que conectan estos nodos. Por ejemplo, una de las trayectorias que conectan a los nodos O y T en la figura 10.1 es la sucesión de arcos OB-BD-DT (O → B → D → T), y viceversa. Cuando algunos o todos los arcos de una red son arcos dirigidos, se hace la distinción entre trayectorias dirigidas y trayectorias no dirigidas. Una trayectoria dirigida del nodo i al nodo j es una sucesión de arcos cuya dirección (si la tienen) es hacia el nodo j, de manera que el flujo del nodo i al nodo j a través e esta trayectoria sea factible. Una trayectoria no dirigida del nodo i al nodo j es una sucesión de arcos cuya dirección (si la tienen) puede ser hacia o desde el nodo j. (obsérvese que una trayectoria dirigida también satisface la definición de trayectoria no dirigida, pero el inverso no se cumple.) Con frecuencia una trayectoria no dirigida tendrá algunos arcos dirigidos hacia el nodo j y otros desde él (es decir, hacia el nodo i). En las secciones 10.5 y 10.6 se verá que, tal vez de manera sorprendete, las trayectorias no dirigidas juegan un papel muy importante en el análisis de la redes dirigidas.

Para ilustrar estas definiciones, la figura 10.2 muestra una red dirigida común, la sucesión de arcos AB-BC-CE (A→ B→ C→ E) es una trayectoria dirigida del nodo A al nodo E, ya que el flujo hacia el nodo E a lo largo de toda esta trayectoria es factible. Por otro lado, BC-AC-AD (B→ C→ A→ D) no es una trayectoria dirigida al nodo B al nodo D, porque la dirección del arco AC es desde el nodo D (sobre su trayectoria). No obstante, B→ C→ A→ D es una trayectoria no dirigida del nodo B al nodo D. Como ejemplo de la relevancia des esta trayectoria no dirigida, supóngase que 2 unidades del flujo del nodo A al nodo C se habían asignado antes del arco AC. dada esta asignación previa, ahora es factible asignar un flujo más pequeño, D, ya que esto implica reducir el flujo sobre el arco AC en 1 unidad. La reducción de un flujo asignado antes "en la dirección equivocada" cuando se agrega un flujo a una trayectoria no dirigida será un concepto medular en las secciones 10.5 y 10.6

Terminología de redes (II)

Si el flujo a través de  un arco se permite en ambas direcciones (como en calles de dos sentidos), se dice que el arco es un arco no dirigido. Para ayudar a distinguir entre los dos tipos de arcos, con frecuencia se hará referencia a los arcos no dirigidos con el sugestivo nombre de ligadura.

Una red que tiene sólo arcos dirigidos se llama red dirigida. De igual manera, si todos sus arcos son no dirigidos, se dice que se trata de una red no dirigida. Una red con una mezcla de arcos dirigidos y no dirigidos (o incluso una con todos sus arcos no dirigidos) se puede convertir en una red dirigida, si se desea, sustituyendo cada arco no dirigido por un par de arcos dirigidos en direcciones opuestas.

Terminología de redes (I)

Se ha desarrollado una terminología relativamente extensa para describir los tipos de redes y sus componentes. Aunque se ha evitado en lo posible el uso del vocabulario específico, es necesario introducir un número considerable de términos que se usarán en este capítulo.  Se sugiere al lector que lea la sección completa una vez para entender las definiciones y panee después regresar a refrescar la memoria conforme se usen los términos en las secciones subsecuentes. Como ayuda, se resalta el nombre de cada términoen negritas en el punto en que se define.

Una gráfica consiste en un conjunto de puntos y un conjunto de líneas que unen ciertos pares de puntos. Los puntos se llaman nodos (o vértices); por ejemplo, la red de la figura 10.1 tiene siete nodos representados por siete círculos. Las líneas se llaman arcos (o ligaduras, aristas o ramas); por ejemplo, la red de la figura 10.1 tiene 12 arcos que corresponden a los 12 caminos del sistema del parque. Los arcos se etiquetan dando nombre a los nodos en sus puntos terminales; por ejemplo AB es el arco entre los nodos A y B en la figura 10.1

Los arcos de una red pueden tener flujo de algún tipo que pasa por ellos, por ejemplo, el flujo de tranvías sobre los caminos de Seervada Park en la sección 10.1. La tabla 10.1 proporciona varios ejemplos de flujo en redes. Si el flujo a través de un arco se permite sólo en una dirección (como en una calle de un sentido), se dice que el arco es un arco dirigido. La dirección se indica agregando una cabeza de flecha al final de la línea que representa el arco. Al etiquetar un arco con el nombre de los nodos que une, siempre se pone primero el nodo de donde viene y despues el nodo a donde va, esto es, un arco dirigido del nodo A al nodo B debe etiquitarse como AB y no como  BA. Otra manera de etiquetarlo es  A→B

Ejemplo Prototipo de Redes (II)

El segundo problema reside en que deben instalarse líneas telefónicas subterráneas para establecer comunicación entre todas las estaciones (inclusive la entrada). Como la instalación ese cara y perturba la ecología, se instalarán líneas que siguen sólo los caminos necesarios para obtener comunicación entre cualquier par de estaciones. La pregunta es por dónde deben tenderse las líneas para lograr esto con el mínimo número total de millas de cable instalado.

El tercer problema es que, durante al temperada pico, hay más personas que quieren tomar el tranvía a la estación T de las que se pueden acomodar. Para evitar la perturbación indebida de la ecología y de la vida silvestre de la región, se ha impuesto un racionamiento estricto en el número de viajes al día que pueden hacer las tranvías en cada camino. Así,durante la temporada pico, se pueden seguir varias rutas sin tomar en cuenta la distancia, para aumentar el número de viajes de travía diarios. La pregunta es cómo panear las rutas para los distintos viajes, de manera que se maximice el número total de viajes que se pueden hacer cada día, sin violar los límites individuales impuestos sobre cada camino.

Ejemplo Prototipo de Redes (I)

En fecha reciente se reservó el área de SERVADA PARK para paseos y campamentos. Nose permite la entrada de automóviles pero existe un sistema de caminos angostos para tranvías y "jeeps" conducidos por los guardabosques. En la figura 10.1 se muestra este sistema de caminos (sin las curvas), en donde O es la entrada al parque; las otras letras representan la localización de las casetas de los guardabosques (y otras instalaciones de servicio). Los números son las distancias en millas de estos caminos sinuosos.

El parque contiene un mirador a un hermoso paisaje en la estación T. Unos cuantos tranvías transportan a los visitantes desde la entrada a la estación T y de regreso.

En este momento el administradro del parque se enfrenta a tres problemas. Uno consiste en determinar qué ruta, desde la entrada del parque a la estación T, es la que tiene la distancia total más corta para la operación de los tranvías.

La planeación y control de proyectos

Es el último tipo de problemas que se ha resuelto por medio de las técnicas de redes, en especial el PERT ("Program Evaluation and Review Technique"  o técnica de evaluación y revisión de programas) y el CPM ("Critical Path Method" o método de la ruta crítica). Aunque limitados a su área de aplicación el PERT y el CPM han demostrado ser herramientas invaluables. De hecho, desde su desarrollo a finales de la década de 1950, el PERT y el CPM han sido (y probablemente seguirán siendo) las técnicas de redes más ampliamente usadas en la investigación de operaciones.

La primera sección introduce un ejemplo prototipo que se usará más adelante para ilustrar los fundamentos de los primeros tres tipos de problema. En la sección 10.2 se presenta la terminología básica para redes. La sección 10.7 está dedicada al método símplex de redes y la sección 10.8 presenta el último tipo de problemas.

El problema del flujo de costo mínimo

El cuarto tipo, el problema del flujo de costo mínimo, proporciona un enfoque unificador de muchas otras aplicaciones pro su estructura mucho más general. De hecho, esta estructura es tan general que incluye como casos especiales el problema de la ruta más corta  y el flujo máximo, al igual que los problemas de transporte, de trasbordo y de asignación del capítulo 7. Lo mismo que muchos otros modelos de optimización de redes, el problema del flujo de costo mínimo se puede formular como un problema de programación lineal y se puede resolver en forma eficiente mediante una versión simplificada del método símplex llamada método símplex de redes.

Análisis de redes, incluyendo PERT-CPM (III)

En este capítulo sólo se podrán plantear las bases de la metodología de redes actual. Sin embargo, se dará una introducción a cinco tipos importantes de problemas de redes y algunas ideas básicas sobre cómo resolverlos (sin profundizar en los aspectos de bases de datos, etc., tan vitales para ponerlos en práctica con éxito en la gran escala). Los tres primeros tipos de problemas, el problema de la ruta más corta, el problema del árbol de la mínima expansión y el problema del flujo máximo, tienen una estructura específica que surge con frecuencia en la práctica.

Análisis de redes, incluyendo PERT-CPM (II)

Un ejemplo de una aplicación reciente es un estudio que ha sido objeto de premios (véanse las referencias selectas 8 y 9) llevado a cabo a mediados de la década de 1980 por la Citgo Petroleum Corporation. EStá dedicado a las operaciones de refinamiento y comercialización del petróleo y tiene ventas de varios millones de millones de dólares. Cuando en 1983 la Southland Corporation (conocida por sus tiendas 7-Eleven) adquirió Citgo, la alta administración vio la necesidad urgente de un sistema de modelado para ayudar a Citgo a superar las presiones de los precios cambiantes de petróleo crudo y un aumento de 30 veces los costos de capital de trabajo. El equipo de investigación de operaciones desarrolló un sistema para apoyar las decisiones basados en la optimización, utilizando la metodología de redes y lo unió a la base de datos corporativa. El modelo toma en cuenta todos los aspectos del negocio, ayuda a la administración en todas las decisiones, desde la producción en las refinerías, hasta los precios que debe pagar o cobrar. Es esencial la representación de redes debido al flujo de bienes a través  de las distintas etapas: la compra de petróleo crudo de los proveedores, el embarque a las refinerías, el refinamiento de los diferentes productos y el embarque de estos productos a los centros de distribución y terminales de almacenamiento para su venta posterior. El sistema de modelado ha permitido a la compañia reducir su inventario en $116 millones de dólares. Esto ha significado un ahorro en los intereses anuales de $14 millones de dólares y mejoras en las decisiones de coordinación, costeo y compra, equivalentes  a otros $2.5 millones de dólares anuales.

En este estudio para Citgo, el modelo que se usa para para cada producto se ajusta al modelo del problema del flujo de costo mínimo que se presenta en al sección 10.6. Cada modelo tiene cerca de 3000 ecuaciones (nodos) y 15 000 variables (arcos), que es un problema de tamaño modesto para los estándares actuales de aplicación de los modelos de optimización de redes.