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: