Añgoritmo De Red Capacitada

Casos especiales del modelo de red capacitada

Se puede demostrar que el modelo de red con capacidad modificada, o red capacitada,
comprende los siguientes modelos como casos especiales:

1. El modelo de transporte, el de asignación y el de transbordo.
2. El modelo de la ruta más corta.
3. El modelo de flujo máximo.

El modelo con capacidad modificada se puede especializar para describirel modelo de
transporte (o el de asignación) efectuando los cambios siguientes:

1. Los nodos fuente se conectan directamente a los nodos destino.
2. La capacidad de todas las ramas de cota inferior se hacen igual a cero.
3. La capacidad de todas las ramas de cota superior se hacen igual a infinito.
41 El modelo de transbordo exige los mismos cambios que el modelo de transporte, excepto quelas unidades transportadas pueden enviarse desde una fuente a un destino, a través de uno o más nodos de transbordo.

El modelo de la ruta más corta, es un caso especial del modelo de red con capacidad
modificada en la forma siguiente:

1. El nodo fuente envía (+1) unidad y el nodo destino recibe (-1) unidad.
2. Todas las ramas tienen capacidades de cota inferior a cero y de cota superiorinfinita.
3. El costo por unidad de flujo en cada rama debe representar ahora la distancia
entre nodos.

El objetivo del modelo de la ruta más corta es enviar 1 unidad de flujo desde la fuente
destino, a un costo (distancia) mínima.

Finalmente, el modelo de flujo máximo se puede expresar como una red capacitada, de la
manera siguiente:

1. La capacidad de cota superior de una rama seutiliza para representar el flujo
máximo en la rama (la cota inferior se hace igual a cero).
2. Se supone que todas las ramas tienen costo cero por unidad de flujo.
3. La cantidad enviada desde el nodo fuente y la cantidad recibida en el nodo destino
se hacen igual a [+F] y [-F] unidades, respectivamente. El valor de F se debe
escoger suficientemente grande para permitir que se establezca elflujo máximo en
la red.
4. Se usa una rama directa para conectar el nodo fuente con el nodo destino. El
propósito de esta rama es llevar la cantidad de exceso de F, que no fluye a través
de la red. La capacidad de esta rama no se debe modificar. Además, se le debe
asignar un costo de flujo unitario suficientemente alto, forzando así a que el
proceso de optimización envíe todo el flujo posiblea través de las ramas de la red
original. Tal procedimiento lograra que se establezca el flujo máximo en la red
capacidad, modificada.

Método del costo mínimo

Características

. Es más elaborado que el método de la esquina noroeste . Tiene en cuenta los costos para hacer las asignaciones . Generalmente nos deja alejados del óptimo

Algoritmo
1. Construya una tabla dedisponibilidades, requerimientos y costos
2. Empiece en la casilla que tenga el menor costo de toda la tabla, si hay empate, escoja
arbitrariamente (Cualquiera de los empatados).
3. Asigne lo máximo posible entre la disponibilidad y el requerimiento (El menor de los dos).
4. Rellene con ceros (0) la fila o columna satisfecha y actualice la disponibilidad y el
requerimiento, restándoles lo asignado.Nota: Recuerde que no debe eliminar ó satisfacer fila y columna al mismo tiempo, caso
en que la oferta sea igual a la demanda, en tal caso recuerde usar laε (Epsilon).
5. Muévase a la casilla con el costo mínimo de la tabla resultante (Sin tener en cuenta la
fila o columna satisfecha).
6. Regrese a los puntos 3,4,5 sucesivamente, hasta que todas las casillas queden asignadas.
En nuestroejemplo, la tabla queda así:

0 20 | | | | | 40 |
0 15 | | | | | 60 |
0 18 | | | | | 70 |
0 30 | | | | | 5020 |
30 0 | 40 | 50 | 40 | 60 | |

Fíjese que el menor costo de toda la tabla es cero (0), pero hay 5 celdas con costo cero (0), Escogemos al azar la fila 4, columna 1 y asignamos lo máximo posible entre 50 y 40 o sea 30, rellenamos la columna 1 con...