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.