Problema de trasbordo (I)

Uno de los requisitos del problema del transporte es que se conozca de antemano la forma en que se van a distribuir las unidades de cada origen i a cada destino j para poder determinar el costo por unidad (cij). No obstante, en ocasiones no es evidente cual es el mejor medio de distribución, pues existe la posibilidad de trasbordos en los que los embarques pasarian por puntos de transferencia intermedios ( que a su vez pueden ser otros orígenes o destinos). Por ejemplo, en lugar de mandar un embarque especial del puerto 1 directo al puerto 3, puede ser más barato incluirlo en los embarques especales del puerto 1 al puerto 2 y de ahí mandarlo al puerto 3.

Resumen del método símplex de transporte (IV)

Segundo, en la tercera tabla urge otra variable básica degenerada (x34), ya que dos variables básicas en dos celdas donadoras de la segunda tabla, la (2,1) y la (3,4) están empatadas al tener el mismo valor más pequeño (30). (Este empate  se rompe de manera arbitraria al elegir x21 como la variable básica que sale; si se hubiera seleccionado x34, entonces x21 se habría convertido en la variable básica degenerada). Parece que esta variable básica degenerada crea algunas complicaciones subsecuentes, por que la celda (3,4) se convierte en celda donadora en la tercera iteración, pero no tiene nada que donar! Por fortuna, no hay que preocuparse. Como la cantidad que se va a sumar y restar en las celdas receptoras y donadoras es cero, las asignaciones no cambian. Sin embargo, la variable básica degenerada sí se vuelve la variable básica que sale, y se sustituye por la variable básica entrante con una asignación de cero, como se muestra en la cuarta tabla. Este cambio en el conjunto de variables básicas  cambia los valores de ui y vj. Si cualquiera de las (cij-ui-vj) habría sido negativa en la cuarta tabla, el algoritmo  hubiera seguido adelante para hacer cambios reales en las asignaciones (siempre que todas las celdas donadoras tuvieran variables básicas  no degeneradas).

Tercero, como ninguna de las (cij-ui-vj) resultó negativa en la cuarta tabla, el conjunto equivalente de asignaciones de la tercera iteración también es óptimo. Así, el algoritmo realizó una iteración más de las necesarias. Esta iteración adicional es un defecto que surge ocasionalmente tanto en el método símplex como en el transporte debido a la degeneración, pero no es tan grave como para justificar algún ajuste a los algoritmos.

Resumen del método símplex de transporte (III)

Al continuar la aplicación de este procedimiento al problema del Distrito Metro, se llega al conjunto completo de tablas símplex de transporte que se muestra en la tabla 7.23. Como en la cuarta tabla todas las (cij-ui-vj) son no negativas, la prueba de optimalidad identifica este conjunto de asignaciones como óptimo, lo cual concluye el algoritmo.

Sería una buena práctica para el lector obtener los valores de las ui y vj que se dan en la segunda, tercera y cuarta iteraciones. Trate esto trabajando directamente en la tabla. También verifique las reacciones en cadena de la segunda y tercera iteraciones, que son un poco más complicadas que la que se vio en la tabla 7.21.

Deben obsrvarse los tres puntos importantes que se ilustran en este ejemplo. Primero, la solución inicial básica factible es degenerada, ya que la variable básica x31 = 0; pero esto no causa complicaciones, pues la celda (3,1) se que las cantidades dise convierte en receptora en la segunda tabla y x31 aumenta a un valor mayor que cero.

Resumen del método símplex de transporte (II)

Parte 3:  se determina la nueva solución factible sumando el valor de la variable básica que sale a las asignaciones de las celdas receptoras y restando este valor a las asignaciones de las celdas donadoras.

3. Prueba de optimalidad: Se obtiene ui y vj tras elegir el renglón con el mayor número de asignaciones y establecer su ui = 0, y después se resuelve el sistema de ecuaciones cij= ui + vj para cada (i,j) tal que xij es básica. Si (cij-ui-vj) ≥ 0 para toda (i,j) tal que xij es no básica, entonces la solución actual es óptima. De lo contrario, habrá que regresar al paso iterativo.

Resumen del método símplex de transporte (I)

1. Paso Inicial:  se construye una solución básica factible con el procedimiento descrito antes en esta sección. Se realiza la prueba de optimalidad.

2. Paso iterativo: 

Parte 1: se determina la variable básica entrante al elegir la variable no básica xij que tiene el valor negativo más grande (en términos absolutos) para (cij-ui-vj).

Parte 2: se determina la variable básica que sale identificando la reacción en cadena que se necesita para conservar la factibilidad cuando se aumenta el valor de la variable básica entrante. Entre las celdas donadoras se selecciona la variable básica que tiene el menor valor.

Paso Iterativo - Parte 3 (II)

Así, el efecto de aumentar el valor de la variable básica entrante x25 fue un cambio en el costo a una tasa de -2 por unidad de aumento. Nótese ahora que (c25-u2-v5) = -2 según la tabla 7.20; no es una conincidencia el que se haya obtenido el mismo valor. De hecho, otra manera (menos eficiente) de obtener (cij -ui-vj) para cada variable no básica xij es identificar la reacción en cadena que causaría un aumento de una unidad en esta variable y después calcular el cambio en el costo. Algunas veces es útil esta interpretación intuitiva para verificar los cálculos durante la prueba de optimalidad.

Antes de completar la solución del problema del Distrito Metro, se hará un resumen las reglas del método símplex de transporte.

Técnica de la cota superior (I)

Al final de la sección 7.5 se estableció que es común que algunas o todas las variables individuales xj tengan restricciones de cota superior.

xj ≤ uj

en donde uj es una constante positiva que representa el máximo valor factible de xj. (El lado derecho de la figura 7.32 muestra la estructura especial de las restricciones funcionales que se obtiene.) También se puso de relieve en la sección 4.8 que el factor determinante en cuanto al tiempo de computadora al correr el método símplex es el número de restricciones funcionales, mienras que el número de restricciones de no negatividad casi carece importancia. Entonces, un número grande de restricciones de cota superior incluidas las restricciones funcionales incrementa mucho el esfuerzo computacionales.

La técnica de la cota superior evita este mayor esfuerzo al eliminar las restricciones de cota superior del conjunto de restricciones funcionales y al tratarlas por separado, en esencia, como restricciones de no negatividad. Hacer esto no causa problemas siempre y cuando ninguna de las variables adquiere un valor mayor que su cota superior. La única vez que el método símplex incrementa alguna de las variables en cuando las variables básica entrante aumenta su valor para obtener la nueva solución básica factible. La técnica de la cotas superior, simplemente aplica el método símplex al resto del problema ( es decir, sin las restricciones de cota superior) pero con la restricción adicional de que cada nueva solución básica factible debe satisfacer las restricciones de cota superior además de las normas de cota inferior (no negatividad)

Paso Iterativo - Parte 3 (I)

la nueva solución básica factible se identifica con sólo sumar el valor (antes de los cambios) de la variable básica que sale a las asignaciones de cada celda receptora y restar esta misma cantidad a las asignaciones de cada celda donadora. En la tabla 7.21 se observa que el valor de la variable básica que sale x15 es 10, por lo que esta porción de la tabla símplex de transporte cambia, como se ilustra en la tabla 7.22 para la nueva solución (Como x15 es no básica en la nueva solución, su nueva asignación es cero y ya no  se muestra en la tabla).

En este momento se puede señalar una interpretación útil de las cantidades (cij - ui -vj) que se obtienen  en la prueba de optimalidad. Debido al cambio de unidades en las asignaciones de las celdas donadoras a las receptoras (mostrando en las tablas 7.21 y 7.22), el costo total cambia en:


ΔZ = 10(15-17 + 13 -13) = 10(-2) = 10(c25-u2-v5)

Paso Iterativo (IV)

En general, siempre existe sólo una reacción en cadena (en cualquier dirección) que se puede completar con éxito para conservar la factibilidad, cuando la variable básica entrante aumenta su valor. Esta reacción en cadena se puede identificar si se hace una selección entre las celdas que tienen variables básicas: primero, la celda donadora en la columna que tienen la variable básica; después, la celda receptora en el renglón que corresponde a la celda donadora; luego, la celda donadora en la columna en que se encuentra esta celda receptora, y así sucesivamente, hasta que la reacción en cadena conduce a una celda donadora en el renglón que tiene la variable básica entrante. Cuando una columna o renglón tiene más de una celda adicional con variable básica, puede ser necesario explorar el camino que se va a seguir para averiguar  cuál debe seleccionarse como donadora o receptora. (Todas las demás menos la adecuada llegarán tarde o temprano a un camino sin salida en un renglón o columna que no tiene otra celda con una variable básica.) Después de identificar la reacción en cadena, la celda donadora que tiene la asignación menor proporciona en forma automática  la variable básica que sale es arbitraria.)

Paso Iterativo (III)

El resultado final es que las celdas (2,5) y (1,3) se convierten en celdas receptoras, cada una con su asignación adicional proveniente de las celdas donadoras (1,5) y (2,3).  (Estas celdas están indicadas en la tabla 7.21 por medio de los signos + y - .) Nótese que tuvo que elegirse la celda (1,5) como celda donadora para la columna 5 y no la (4,5), ya que esta última  no hubiera tenido celda receptora en el rengón 4 para continuar la reacción en cadena. [De igual manera, si la reacción en cadena se habría  iniciado en el renglón 2, la celda (2,1) no hubiera podido ser celda donadora, pues no se habría podido completar la reacción en cadena después de elegir, sin otra opción, la celda (3,1), puesto que ni la celda (3,2) ni la (3,4), como donadoras, tienen celda receptora.]

Cada celda donadora disminuye su asignación en una cantidad exactamente igual al aumento que tiene la variable básica entrante (y las otras celdas receptoras). Entonces, la celda donadora que comienza con la asignación más pequeña (en este caso la celda (1,5), ya que 10 < 30 en la tabla 7.21) debe ser la primera en llegar a una asignación de cero conforme se incrementa la variable entrante x25. Así, x15 se convierte en la variable básica que sale.

Paso Iterativo (II)

Parte 2: si se incrementa el valor de la variable básica entrante, se establece una reacción en cadena de cambios compensatorios en otras variables básicas (asignaciones) para seguir satisfaciendo las restricciones de recursos y demanda. La primera variable básica que disminuya su valor hasta cero será la variable básica que sale.

Si  x25 es la variable básica entrante, la reacción en cadena de la tabla 7.20 es relativamente sencilla y se resume  en la tabla 7.21. (Siempre se indicará la variable básica entrante colocando un signo + enmarcado dentro de su celda.) Así, al aumentar x25 debe disminuir x15 en la misma cantidad para conservar la demanda de 60 en la columna 5; esto  a su vez requiere que se aumente x13 en esta cantidad para mantener la oferta de 50 en el renglón 1 y esto a su vez exige  una disminución en el valor de x23 para conservar la demanda de 70 en la columna 3. Esta disminución en x13 completa con éxito la reacción en cadena, ya que también conserva la oferta del renglón 2. (De manera equivalente, se pudo haber iniciado la reacción en cadena restableciendo esta cantidad de recursos en el renglón 2 con una disminución en x23 un aumento en x13 y una disminución en x15).

Paso Iterativo (I)

Igual que para el método símplex estándar, el paso iterativo de esta versión simplificada debe determinar  una variable básica entrante (parte 1), una variable básica que sale (parte 2) y después identificar la nueva solución básica factible que resulta (parte 3).

Parte 1: como (cij-ui-vj) representa la tasa a la que cambia la función objetivo si se incrementa la variable  no básica xij, la variable básica que entra debe tener un valor de (cij-ui-vj) negativo, para que el costo total Z disminuya. Entonces, los candidatos en la tabla 7.20 son x25 y x44. Entre ellos se elige el valor negativo más grande (en términos absolutos) de (cij-ui-vj) como la variable básica  entrante, que en tes caso corresponde a x25.

Prueba de optimalidad (III)

Una vez familiarizado con esto, el lector tal vez encuentre más conveniente resolver las ecuaciones sin escribirlas y trabajar directamente sobre la tabla símplex de transporte. Así, es la tabla 7.19 se comienza por escribir el valor de u3 = 0 y después se toma cada una de las asignaciones (x31, x32, x34) en ese renglón, para las que se establece vj = c3j; en seguida se buscan las asignaciones en estas columnas (excepto en el renglón 3), como x21. Mentalmente se calcula u2 = c21 - v1. Tomando x23, se establece v3 = c23 - u2, y así hasta encontrar y escribir todos los valores de las uj y vj (Inténtese esto.) Después se calculan y escriben los valores de (cij-ui-vj) para cada una de las variables no básicas xij (para las celdas sin asignación); en la tabla 7.20 se muestra la tabla símplex de transporte inicial que se obtiene.

En este momento se puede aplicar la prueba de optimalidad para verificar los valores de (cij-ui-vj) dados en esta tabla. Como dos de estos valores, (c25-u2-v5) = -2 y (c44-u4-v4) = -1, son negativos, se concluye que la solución básica factible actual no es óptima. Entonces, el método símplex de transporte debe proceder el paso iterativo para encontrar una mejor solución básica factible.

Prueba de optimalidad (II)

Existen (m+n-1) variables básicas y por tanto hay (m+n-1) ecuaciones de este tipo. Como el número de incógnitas (las ui y vj) es (m+n), se pueden asignar un valor arbitrario a cualquiera de estas variables sin fiolar las ecuaciones. (La regla que se adoptará es elegir la ui que tenga el mayor número de asignaciones en su renglón y asignarle un valor de cero).

Gracias a la sencilla estructura de estas ecuaciones, resulta muy fácil obtener algebraicamente los valores del resto de las variables.

A manera de demostración, se darán las ecuaciones que corresponden a cada variable básica en al solución inicial básica factible.

Si se establece u3 = 0 (puesto que el renglón 3 de la tabla 7.19 tiene tres asignaciones, que es el mayor número) y se resuelven una por todas las ecuaciones, se obtienen de inmediato los valores de las incógnitas que se muestran a la derecha de las ecuaciones.

Prueba de optimalidad (I)

Si se recurre a la notación de la tabla 7.14,la prueba de optimalidad estándar del método símplex (véase la sección 4.3) para el problema de transporte, se puede reducir de la siguiente manera.

Prueba de optimalidad: una solución básica factible es óptima si y sólo si (cij-ui - vj) ≥ 0 para todo (i,j) tal que xij es no básica.

Así lo único que hay que hacer para realizar esta prueba es obtener los valores de las ui y vj para la solución básica factible actual y después calcular los valores (cij - ui - vj).

Como el valor de (cij - ui -vj) debe ser cero si xij es una variable básica, ui y vj satisfacen el conjunto de ecuaciones.

cij = vi + vj para cada (i, j ) tal que xij es básica.

Ejemplo Russell - Comporación de criterios alternativos para el paso 1 (II)

Una ventaja exclusiva del método de Russell es que su metodologia sigue el patrón  de la parte 1 del paso iterativo del método símplex de transporte (como se verá muy pronto), y esto, de alguna manera simplifica el programa completo de computadora. En particular, las ui y vj se definieron de manera que los valores absolutos de (cij-ui -vj) son una estimación de los valores relativos de cij - ui - vi que se obtendrán cuando el método símplex de transporte alcance la solución óptima.

Ahora se usará la solución inicial básica factible obtenida en la tabla 7.18 por el método de aproximación de Russell para ilustrar el resto del método símplex de transporte. Entonces, en la tabla 7.19 se muestra la tabla símplex de transporte inicial (antes de encontrar las ui y vj)

El siguiente paso es verificar mediante la prueba de optimalidad si esta solución inicial es efectivamente óptima.

Ejemplo Russell - Comporación de criterios alternativos para el paso 1 (I)

Se comparán estos tres criterios para elegir la siguiente variable básica. La virtud principal de la regla de al esquina noroeste es la facilidad y rapidez con que se aplica. Sin embargo, como no le da importancia a los costos unitarios (cij) por lo general la solución que se obtiene distará mucho de la óptima. (Nótese en la tabla 7.16 que x35=10, aun cuando x35 = M) Si se realiza un esfuerzo un poco mayor para encontrar la solución inicial básica factible, es posible que se reduzca mucho el número de iteraciones que después necesita el método símplex de transporte para encontrar la solución óptima (véanse los problemas 7 y 12). El objetivo de los otros dos criterios es precisamente encontrar una solución así.

El método de aproximación de Vogel ha sido el más popular durante muchos años, en parte porque es relativamente fácil hacerlo a mano. Este criterio toma en cuanta los costos unitarios en forma efectiva ya que la diferencia representa el mínimo costo adicional en que se incurre por no hacer una asignación en la celda que tiene el menor costo en esa columna o renglón.

El método de aproximación de Russell proporciona otro criterio excelente y fácil de poner en práctica en una computadora (aunque no para la forma manual). Es cierto que todavía se requiere más experimentación para determinar cuál es más eficiente en promedio, pero con frecuencia este criterio ha proporcionado una solución mejor. (Para el ejemplo, el método de aproximación de Vogel por casualidad encuentra la solución óptima con Z = 2460, mientra que el re Russell falla por muy poco con Z = 2570.) En un problema grande, quizá valga la pena aplicar ambos criterios y después usar la mejor solución que se obtenga para iniciar las iteraciones del método símplex de transporte.

Ejemplo Russell (II)

Al calcular todas las Δij para i = 1,2,3,4 y j = 1,2,3,4,5 se observa que Δ45 = 0 - 2M tiene el valor negativo mayor, por lo cual, se elige x45 = 50 como la primera variable básica (asignación). Esta asignación agota todos los recursos que se tienen en el renglón 4, por lo que este renglón se elimina.

Nótese que esta eliminación cambia v1 y v3 para la siguiente iteración, por lo que ahora se requiere volver a calcular Δij con j = 1,3 al igual que es necesario eliminar i = 4. Ahora el valor negativo más grande es

Δ15 = 17 - 22 - M = -5 -M,

de manera que x15 =10 se convierte en la segunda variable básica (asignación), y se elimina la columna 5.

Las iteraciones subsecuentes proceden de una manera similar, pero el lector quizá dese aprobar su comprensión y verifique el resto de las asignaciones dadas en la tabla 7.18. Al igual que con otros procedimientos de esta sección (y de otras) el OR COURSEWARE puede resultar útil, cuando se trata de hacer cálculos y como ilustración del enfoque.

Ejemplo Russell (I)

Se aplicará de nuevo el procedimiento general al problema del Distrito Metro (véase la tabla 7.12) usando el método de aproximación de Russell. En la tabla 7.18 se muestran los resultados que incluyen la serie de variables  básicas (asignaciones) que se obtienen.

En la iteración 1, el mayor costo unitario en el renglón 1 es u1 = 22 en la columna 1 es v1 = M, etc. Así.

Método de aproximación de Russell

Para cada renglón de origen i que queda bajo consideración, debe determinarse ui, su mayor costo unitario (cij) de lso que quedan en ese renglón. Para cada columna de destino que todavía está bajo consideración, se determina vj, su mayor costo unitario de los que hay en esa columna. Para cada variable xij que no haya sido seleccionada en estos renglones o columnas, se calcula: Δij = cij - ui - vj. Se elige la variable con el mayor valor negativo (en términos absolutos) de Δij. (Los empates se pueden romper arbitrariamente)

Ejemplo Procedimiento general para construir una solución inicial básica factible (II)

Este ejemplo ilustra dos características sutiles del procedimiento general que ameritan atención especial. Primero, nótese que la iteración final elige tres variables (x31, x32 y x33) para entrar a la base, en lugar de una sola que se elige en las iteraciones anteriores. La razón es que en este punto queda sólo un renglón (el renglón 3) sin eliminar. Por tanto, el paso 4 del procedimiento general dice que se seleccionen como básicas todas las variables restantes asociadas con el renglón 3.

Segundo, nótese que la asignación x23 = 20 en la penúltima iteración agota tanto los recursos restantes en ese renglón como la demanda que queda en esa columna. Sin embargo, en el lugar de eliminar los dos, el paso 3 dice que se elimine sólo el renglón y se deje la columna para que más tarde proporcione una variable básica degenerada. De hecho, la columna 3 se usa justo para este propósito en la iteración final cuando se selecciona x33 = 0 como una de las variables básicas. Véase en la tabla 7.16 otro ejemplo de este fenómeno, donde despues de hacer la asignación x12 = 20 se elimina sólo el renglón 1, y la columna 2 se conserva para proporcionar la variable básica degenerada x22 = 0 en la siguiente iteración.

Aunque una asignación de cero puede parecer irrelevante, de hecho  juega un papel importante, pues como se verá pronto, el método símplex de transporte debe conocer todas las (m+n-1) variables básicas, incluso aquéllas que valen cero, que componen la solución básica factible inicial.

Ejemplo Procedimiento general para construir una solución inicial básica factible (I)

Ahora se aplicará el procedimiento general al problema del Distrito Metro mediante el criterio del método de aproximación de Vogel para seleccionar la siguiente variable básica en el paso 1. Al aplicarlo, es más conveniente trabajar con la tabla de costos y requerimientos (en lugar de la tabla símplex de transporte completa), y comenzar con la que se muestra en la tabla 7.12. En cada iteración, después de calcular y escribir las diferencias para cada renglón y columna que quedan bajo consideración, se encierra en un círculo la mayor de ellas y se enmarca en un cuatro el costo unitario menor en ese renglón o columna. La variable con este costo unitario menor se selecciona como la siguiente variable básica y su valor se indica en la esquina inferior derecha de la tabla actual, junto con el renglón o columna que se elimina (véanse los pasos 2 y 3 del procedimiento general). La tabla para la siguiente iteración es la misma, pero se elimina este renglón o columna y se resta la cantidad que se asignó de la demanda o los recursos correspondientes (cualesquiera que sobren).

La aplicación de este procedimiento al problema del Distrito Metro de la serie de tablas de costos y requerimientos que se muestran en la tabla 7.17 en donde la solución básica factible inicial consiste en las ocho variables básicas (asignaciones) dadas en la esquina inferior derecha de las tablas respectivas.

Método de aproximación de Vogel

Para cada renglón y columna que queda bajo consideración, se calcula su diferencia, que se define como la diferencia aritmética entre el costo unitario más pequeño (cij) y el que le sigue, de los que quedan en ese renglón o columna. En el renglón o columna que tiene la mayor diferencia se elige la variable que tiene el menor costo unitario que queda. (Los empates para la mayor de estas diferencias se pueden romper de manera arbitraria.)

Ejemplo Criterios alternativos para el paso I (II)

Si se continúa en esta misma forma, llegará el momento en que se obtenga la solución inicial básica factible completa que se muestra en la tabla 7.16, en las que los números dentro de los círculos son los valores de las variables básicas (x11 = 30, ............x45 = 50) y todas las otras variables (x13, etc) son no básicas iguales a cero. Se agregaron flechas para indicar el orden en que se eligieron las variables básicas (asignaciones). El valor de Z para esta solución es:

Ejemplo Criterios alternativos para el paso I (I)

Para hacer más concreta esta descripción, se ilustrará el procedimiento general en el problema del Distrito Metro (véase la tabla 7.12) usando la regla de la esquina noroeste en el paso 1. Como en este caso m = 4 y n =5, el procedimiento encontrará una solución inicial básica factible que tiene m+n-1 = 8 variables básicas.

Como se muestran en la tabla 7.16 la primera asignación es x11 = 30, lo que completa la demanda de la columna 1 (y la elimina para nuevas asignaciones). La Primera iteración deja 20 unidades de recursos restantes en el renglón 1, así que después se elige x1,1+1 = x12 como variable básica. Como los recursos restantes no son mayores que la demanda de 20 unidades de la columna 2, too se asigna a x12 = 20, y se elimina este renglón. En seguida se selecciona x1+1,2 =x22. Como la demanda de 0 que queda en la columna 2 es menor que los recursos (60) en el renglón 2, se asigna x22 = 0 y se elimina la columna 2.

Criterios alternativos para el paso I

1. Regla de la esquina noroeste:

la primera elección es x11 (es decir, se comienza en la esquina noroeste de la tabla símplex de transporte). De ahí en adelante, si xij fue la última variable básica seleccionada, la siguiente elección es xi,j+1 (es decir, se mueve una columna a la derecha) si quedan recursos en el origen i. De otra manera, se elige xi+1,, (es decir, se mueve un renglón hacia abajo)

Procedimiento general para construir una solución inicial básica factible (2)

Paso 3: se elimina ese renglón o columna (la que tenia la cantidad más pequeña en los recursos o demandas restantes) para las nuevas asignaciones. (Si el renglón y la columna tienen la misma  cantidad de recursos y demanda restante, entonces arbitrariamente se elimina el renglón. La columna se usará después para proporcionar una variable básica degenerada, es decir, una asignación con cero unidades encerradas en un circulo.)

Paso 4: si sólo queda un renglón o una columna dentro de las posibilidades, entonces el procedimiento termina al elegir todas las variables restantes (es decir, aquellas variables que no se han elegido ni se han eliminado al quitar su renglón o clumna) asociados con ese renglón o columna que tiene la única asignación posible. De otra manera, se regesa al paso I.

Procedimiento general para construir una solución inicial básica factible (1)

Al iniciar:

todos los renglones de los orígenes y las columnas de destinos de la tabla símplex de transporte se toman en cuenta para proporcionar una variable básica (asignación).

Paso 1: se selecciona la siguiente variable básica (asignación) entre lo renglones y columnas en que todavía se puede hacer una asignación de acuerdo a algún criterio.

Paso 2: se hace una asignación lo suficientemente grande como para que use el resto de los recursos en ese renglón o la demanda restante en esa columna (cualquiera que sea la cantidad más pequeña)

Preparación para el método símplex - Paso Inicial (II)

Esto se debe a que se manejan restricciones de igualdad y este conjunto de (m+n) ecuaciones tiene una ecuación adicional (o redundante) que se puede eliminar sin cambiar la región factible, esto es, cualquiera de las restricciones satisface en forma automática siempre que las otras m + n -1 restricciones quedan satisfechas. (Esto se puede verificar demostrando que cualquiera de las restricciones de recursos se puede expresar como la suma de las restricciones de la demanda menos la suma de las otras restricciones de recursos, y que cualquier restricción de demanda también puede expresarse en términos de la suma de las ecuaciones de recursos menos las otras ecuaciones de demanda. (Véase el problema 23) Por lo tanto, cualquier solución básica factible en una tabla de transporte debe aparecer con exactamente (m+n-1) asignaciones no negativas encerradas en un círculo, de manera que la suma de las asignaciones en cada renglón o columna es igual a su demanda o su cantidad de recursos.

El procedimiento para construir una solución inicial básica factible selecciona, una por una, las (m+n-1)variables básicas. Después de cada selección, se asigna a esa variable un valor que va a satisfacer una más de las restricciones (eliminando así el renglón o columna de esa restricción para cualquier nueva asignación). Una vez hechas las (m+n-1) elecciones, el resultado es que se ha construido una solución básica completa, de tal manera que se satisfacen todas las restricciones. Se han propuesto varios criterios diferentes para elegir las variables básicas. Se presentan y ejemplifican tres de estos criterios después de describir el procedimiento general.

Preparación para el método símplex - Paso Inicial (I)

Recuerdese que el objetivo de este paso es obtener una solución inicial básica factible. Como todas las restricciones funcionales en el problema de transporte son igualdades, el método símplex obtendría esta solución introduciendo variables artificiales y usándolas como variables básicas iniciales, según se describió en la sección 4.6. La solución básica que resulta de hecho sólo es factible para al versión revisada del problema, por lo que se necesita un buen número e iteraciones para hacer que el valor de estas variables sea cero y se alcancen las soluciones factibles reales. El método símplex de transporte pasa por alto todo esto, pues usa un procedimiento más sencillo para construir directamente una solución básica factible real sobre la tabla de transporte.

Antes de describir este procedimiento, es necesario establecer que el número de variables básicas en cualquier solución  básica de un problema de transporte es una menos de lo que se espera. Normalmente, en los problemas de programación líneal, se tiene una variable básica por cada restricción funcional. En los problemas de transporte con m recursos y n destinos el número de restricciones funcionales m + n. Sin embargo.

el número de variables básicas = m + n - 1