programacion dinamica

Problema Flujo Máximo
En algunas redes circula por los arcos un flujo (envío o circulación de unidades homogéneas de algún producto: automóviles en una red de carreteras, litros de petróleo en un oleoducto, bits por un cable de fibra óptica) desde el origen o fuente al destino, también denominado sumidero o vertedero. Los arcos tienen una capacidad máxima de flujo, y se trata de enviar desdela fuente al sumidero la mayor cantidad posible de flujo, de tal manera que:
El flujo es siempre positivo y con unidades enteras.
El flujo a través de un arco es menor o igual que la capacidad.
El flujo que entra en un nodo es igual al que sale de él.
En el caso de que el origen o el destino no existan en el problema, se añaden ficticiamente utilizando arcos unidireccionales de capacidadinfinita, como en grafo mostrado a continuación:

Corte: Un corte define una serie de arcos cuya supresión de la red causa una interrupción completa del flujo entre el origen y el destino. La capacidad de corte es igual a la suma de las capacidades de los arcos asociados. Entre todos los cortes posibles en la red , el corte con la menor capacidad proporciona el flujo máximo en la red.
El siguientegrafo ilustra 3 cortes: el Corte 1 con capacidad 60, el Corte 2 con capacidad 110 y el Corte 3 con capacidad 70. Todo lo que podemos obtener de los 3 cortes es que el flujo máximo en la red no excede de 60 unidades. No podemos saber cual es el flujo máximo hasta que se hayan enumerado todos los cortes en la red:

Las capacidades se identifican como sigue: por ejemplo, para el arco (3,4), el límitede flujo es de 10 unidades de 3 a 4 y de 5 unidades de 4 a 3.
5.5 Problema de Flujo de Costo Mínimo.
El problema de flujo de costo mínimo tiene una posición medular entre los problemas de optimización de redes; primero, abarca una clase amplia de aplicaciones y segundo, su solución es muy eficiente. Igual que el problema del flujo máximo, toma en cuenta el flujo de una red con capacidadeslimitadas en sus arcos. Igual que el problema de la ruta más corta, considera un costo (o distancia) para el flujo a través de un arco. Igual que el problema de transporte o el de asignación del capítulo 8, puede manejar varios orígenes (nodos fuente) y varios destinos (nodos demanda) para el flujo, de nuevo con costos asociados. De hecho, estos cuatro problemas son casos especiales del problema deflujo de costo mínimo, como se verá.
La razón por la que el problema de flujo de costo mínimo se puede resolver de modo tan eficiente es que se puede formular como un problema de programación lineal y es posible resolverlo con una versión simplificada del método simplex llamado método simplex de redes.
En la siguiente sección se describirá este algoritmo.
A continuación se describe el problema deflujo de costo mínimo.
La red es una red dirigida y conexa.
Al menos uno de los nodos es un nodo fuente.
Al menos uno de los nodos es un nodo demanda.
El resto de los nodos son nodos de trasbordo.
Se permite el flujo a través de un arco solo en la dirección indicada por la flecha, donde la cantidad máxima de flujo está dada por la capacidad del arco. (Si el flujo puede ocurrir en ambasdirecciones, debe de representarse por un par de arcos en direcciones opuestas).
La red tiene suficientes arcos con suficiente capacidad para permitir que todos los flujos generados por los nodos fuente lleguen a los nodos demanda.
El costo de flujo a través del arco es proporcional a la cantidad de ese flujo, donde se conoce el costo por unidad.
El objetivo es minimizar el costo total de enviar elsuministro disponible a través de la red para satisfacer la demanda dada. (Un objetivo alternativa es maximizar la ganancia total del envío).
Algunas Aplicaciones.
Tal vez el tipo más importante de aplicación del problema de flujo de costo mínimo es en la operación de la red de distribución de una compañía. Como se resume en el primer renglón de la tabla que se muestra a continuación, este...