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.