Programacion lineal

Problema de Transporte
El problema general es una clase especial de programación lineal que tiene que ver con trasportar un artículo desde sus fuentes hasta sus destinos. El objetivo es determinar el programa de trasporte que minimice el costo total del trasporte y que al mismo tiempo satisfaga los límites de la oferta y la demanda. En el modelo se supone que el costo de transporte esproporcional a la cantidad de unidades transportadas en determinada ruta. En general se puede ampliar el modelo de transporte a otras áreas de operación, entre otras el control de inventario, programación de empleos y asignación de personal. Aunque el modelo de transporte se puede resolver como una programación lineal normal, su estructura especial permite desarrollar un algoritmo de cómputo, basado en elsimplex, que usa las relaciones primal-duales para simplificar los cálculos como lo muestra la tabla 8.6.

Preparación para el método simplex de transporte.
El algoritmo de transporte se basa en la hipótesis de que el modelo está balanceado, y eso quiere decir que la demanda total es igual a la oferta total. Si el modelo estaba desbalanceado siempre se podrá aumentar con una fuente ficticia oun destino ficticio para restaurar el equilibrio o balance.
Para hacer hincapié en la simplificación lograda por el método simplex de transporte, se revisará primero la forma en que el método simplex general (simplificado) establecería el problema de transporte en forma tabular. Después de construir la tabla de los coeficientes de restricción; de convertir la función objetivo a la forma demaximización y usar el método de la gran M para introducir artificiales Z1, Z2,…, Zm+n en las m+n ecuaciones de restricción respectivas, se ve que las columnas de la tabla simplex tendrían la forma que se muestra en la tabla siguiente:

Aquí todos los elementos que no se muestran en estas columnas son ceros. (El único ajuste que queda por hacer antes de la primera iteración es eliminaralgebraicamente los coeficientes distintos de cero de las variables básicas iniciales (artificiales) en el renglón 0.
Después de cualquier iteración subsecuente, el renglón 0 tendría la forma que se muestra en la siguiente tabla, debido al patrón de ceros y unos que siguen los coeficientes en la tabla anterior

Ui: múltiplo del renglón i original que se restó (directa o indirectamente) del renglón 0original en todas las iteraciones del método simplex que llevaron a la tabla actual.
Vj: múltiplo del renglón m + j original que se restó (directa o indirectamente) del renglón 0 original en todas las iteraciones del método simplex que dan la la tabla actual.
Ui y Vj: Son variables duales
Con el fin de sentar las bases que permitan la simplificación, hay que recordar la información que senecesita para el método simplex. En el paso inicial, debe obtenerse una solución BF inicial, lo que se hace en forma artificial introduciendo variables artificiales para que constituyan el conjunto de variables básicas iniciales. Para llevar a cabo la prueba de optimalidad y el paso 1 de la iteración (seleccionar una variable básica entrante) se requiere conocer el renglón 0 actual, que se obtienerestando del renglón 0 anterior algún múltiplo de otro renglón. El paso 2 (determinar la VB que sale) debe identificar la variable básica que llega primero a cero cuando aumenta el valor de la variable básica entrante. El paso 3 debe determinar la nueva solución BF, que se encuentra restando algunos múltiplos en un renglón, de otros renglones de la tabla simplex actual.
Para el método simplex detransporte; primero, no se necesitan variables artificiales, otro aspecto es que el renglón 0 actual se puede obtener sin usar ningún otro renglón con solo calcular los valores de Ui y Vj directamente. Segundo, como cada variable básica debe tener coeficiente cero en el renglón 0, estos valores se pueden obtener si se resuelve el sistema de ecuaciones y tercero la variable básica que sale se puede...