UNIVERSIDAD AUTÓNOMA DE YUCATÁN

4. Problemas de Transporte.

4.1. Formulación del Modelo de Transporte.

La programación lineal es un campo tan amplio que se extiende a subclases de problemas para los cuales existen métodos de solución especiales. Una de estas subclases se conoce como problemas de transporte. El método símplex de programación lineal, puede servir para resolver estos problemas. Pero se han desarrollado métodos más sencillos que aprovechan ciertas características de los problemas. Entonces, el método del transporte son sólo técnicas especiales para resolver ciertos tipos de problemas de programación lineal.

El transporte desempeña un papel importante en la economía y en las decisiones administrativas. Con frecuencia la disponibilidad de transporte económico es crítica para la sobrevivencia de una empresa.

¿Qué significa problema de transporte? Supóngase que un fabricante tiene tres plantas que producen el mismo producto. Estas plantas a su vez mandan el producto a cuatro almacenes. Cada planta puede mandar productos a todos los almacenes, pero el costo de transporte varía con las diferentes combinaciones. El problema es determinar la cantidad que cada planta debe mandar a cada almacén con el fin de minimizar el costo total de transporte.

La manera más fácil de reconocer un problema de transporte es por su naturaleza o estructura
“de-hacia”: de un origen hacia un destino, de una fuente hacia un usuario, del presente hacia el futuro, de aquí hacia allá. Al enfrentar este tipo de problemas, la intuición dice que debe haber una manera de obtener una solución. Se conocen las fuentes y los destinos, las capacidades y demandas y los costos de cada trayectoria. Debe haber una combinación óptima que minimice el costo (o maximice la ganancia). La dificultad estriba en el gran número de combinaciones posibles.

Puede formularse un problema de transporte como un problema de programación lineal y aplicarse el método símplex. Si se hiciera, se encontraría que los problemas de transporte tienen características matemáticas únicas. Para visualizar esto, considérese el siguiente ejemplo:

Ejemplo prototipo.

Chícharos enlatados es uno de los productos más importantes de la compañía P & T. Los chícharos se preparan en tres enlatadoras (cercanas a Bellingham, Washington; a Eugene, Oregón y a Albert Lea, Minnesota) y después se mandan por camión a cuatro almacenes de distribución (en Sacramento, California; Salt Lake City, Utah; Rapid City, South Dakota y Alburquerque, New Mexico) en el oeste de Estados Unidos. Puesto que los costos de embarque constituyen un gasto importante, la gerencia ha iniciado un estudio para reducirlos lo más posible que se pueda. Se ha hecho una estimación de la producción de cada enlatadora para la próxima temporada y se ha asignado a cada almacén una cierta cantidad de la producción total de chícharos. En la siguiente tabla se proporciona esta información (en unidades de carga de camión), junto con el costo de transporte por camión cargado para cada combinación de enlatadora-almacén. Como se ve hay un total de 300 cargas de camión que se deben transportar. El problema es determinar el plan de asignación de estos embarques a las distintas combinaciones de enlatadora-almacén que minimice el costo total de transporte.

Costo de embarque ($) por carga

	Almacén
	1	2	3	4	Producción
1	464	513	654	867	75
Enlatadora 2	352	416	690	791	125
3	995	682	388	685	100
Asignación	80	65	70	85

Este, de hecho, es un problema de programación lineal del tipo de los problemas de transporte. Para formularlo, sea Z el costo total de transporte y sea x_ij (i = 1, 2, 3; j = 1, 2, 3, 4) el número de cargas de camión que se mandan de la enlatadora i al almacén j. Entonces el objetivo es seleccionar los valores de estas 12 variables de decisión (las x_ij) para:

Minimizar Z= 464x₁₁ + 513x₁₂ + 654x₁₃ + 867x₁₄ + 352x₂₁ + 416x₂₂ + 690x₂₃ + 791x₂₄

995x₃₁ + 682x₃₂ + 388x₃₃ + 685x₃₄

sujeta a las restricciones:

x₁₁

x₁₂

x₁₃

x₁₄

x₂₁

x₂₂

x₂₃

x₂₄

125

x₃₁

x₃₂

x₃₃

x₃₄

100

x₁₁

x₂₁

x₃₁

x₁₂

x₂₂

x₃₂

x₁₃

x₂₃

x₃₃

x₁₄

x₂₄

x₃₄

x_ij ³ 0 (i = 1, 2, 3; j = 1, 2, 3, 4)

La siguiente tabla muestra los coeficientes de las restricciones. Como se verá enseguida, lo que distingue a este problema como un problema de transporte es la estructura especial en el patrón de estos coeficientes, no su contexto.

Coeficiente de:
	x₁₁	x₁₂	x₁₃	x₁₄	x₂₁	x₂₂	x₂₃	x₂₄	x₃₁	x₃₂	x₃₃	x₃₄

	1	1	1	1
					1	1	1	1					Restricciones
									1	1	1	1	de enlatadora
A =	1				1				1
		1				1				1			Restricciones
			1				1				1		de almacén
				1				1				1

Entre paréntesis, la solución óptima para este problema es x₁₁ = 0, x₁₂ = 20, x₁₃ = 0, x₁₄ = 55,
x₂₁ = 80, x₂₂ = 45, x₂₃ = 0, x₂₄ = 0, x₃₁ = 0, x₃₂ = 0, x₃₃ = 70, x₃₄ = 30. Cuando se conozca la prueba de optimalidad se podrá verificar este resultado.

Modelo general del problema de transporte.

Para describir el modelo general del problema de transporte es necesario emplear términos que sean mucho menos específicos que los que se usaron para los componentes del ejemplo prototipo. En particular, el problema general de transporte se refiere (literal o en sentido figurado) a la distribución de cualquier bien desde cualquier grupo de centros de abastecimiento, llamados orígenes, a cualquier grupo de centros de recepción, llamados destinos, de tal manera que se minimicen los costos totales de distribución. La correspondencia en terminología entre el ejemplo prototipo y el problema general se resume en la siguiente tabla:

Ejemplo prototipo	Problema general
Cargas de chícharos enlatados	Unidades de un bien
Tres enlatadoras	m orígenes
Cuatro almacenes	n destinos
Producción de la enlatadora i	s_i recursos en el origen i
Asignación al almacén j	Demanda d_j en el destino j
Costo de embarque por carga desde la enlatadora i al almacén j	Costo c_ij por unidad distribuida desde el origen i al destino j

Así, por lo general, el origen i (i = 1, 2, ..., m) dispone de s_i unidades para distribuir a los destinos y el destino j (j = 1, 2, ..., n) tiene una demanda de d_j unidades que recibe desde los orígenes. Una suposición básica es que el costo de distribución de unidades desde el origen i al destino j es directamente proporcional al número distribuido, donde c_ij denota el costo por unidad distribuida. Igual que para el ejemplo prototipo, estos datos de entrada se pueden resumir en forma muy conveniente en la tabla de costos y requerimientos que se muestra enseguida:

		Costo por unidad distribuida
		Destino
		1	2	. . .	n	Recursos
	1	c₁₁	c₁₂	. . .	c_1n	s₁
Origen	2	c₂₁	c₂₂	. . .	c_2n	s₂
	.	.	.		.	.
	.	.	.	. . .	.	.
	.	.	.		.	.
	m	c_m₁	c_m₂	. . .	c_mn	s_m
Demanda		d₁	d₂	. . .	d_n

Sea Z el costo total de distribución y x_ij (i = 1, 2, ..., m; j = 1, 2,..., n) el número de unidades que se distribuyen del origen i al destino j, la formulación de programación lineal para este problema es:

Minimizar Z =

sujeta a

x_ij ³ 0, para toda i y j

Note que la tabla que resulta de los coeficientes de las restricciones tiene la estructura especial que se muestra en la siguiente tabla:

Coeficiente de
	x₁₁	x₁₂	. . .	x_1n	x₂₁	x₂₂	. . .	x_2n	. . .	x_m1	x_m2	. . .	x_mn

	1	1	. . .	1										Restricciones
					1	1	. . .	1						de origen
									.
									.
									.
A =										1	1	. . .	1

	1				1					1				Restricciones
		1				1			. . .		1			de destino
			.				.					.
			.				.					.
			.				.					.
				1				1					1

Cualquier problema de programación lineal que se ajuste a esta formulación especial es del tipo de problemas de transporte, sin importar su contexto físico. De hecho, se han realizado numerosas aplicaciones no relacionadas con el transporte que se ajustan a esta estructura especial. Ésta es una de las razones por las que el problema de transporte se suele considerar como uno de los tipos especiales de problemas de programación lineal más importantes.

Una condición necesaria y suficiente para que un problema de transporte tenga soluciones factibles es que:

Esta propiedad se puede verificar observando que las restricciones requieren que:

Esta condición de que los recursos totales deben ser iguales a la demanda total en realidad exige que el sistema esté balanceado. Si el problema tiene algún significado físico y esta condición no se cumple, casi siempre significa que, o bien s_i, o bien d_j de hecho representan una cota y no un requerimiento exacto. Si este es el caso, se puede introducir un “origen” o “destino” imaginario (llamado origen ficticio o destino ficticio) para captar la holgura, con el fin de convertir las desigualdades en igualdades y satisfacer la condición de factibilidad.

El problema de transporte es sólo un tipo especial de problemas de programación lineal y puede resolverse aplicando el método símplex tal y como lo hemos estudiado. Sin embargo, veremos que si se aprovecha la estructura especial que se muestra en la tabla anterior, se puede lograr un importante ahorro en los cálculos. Se hará referencia a este procedimiento simplificado como el método símplex de transporte.

Para hacer hincapié en la simplificación lograda por el método símplex de transporte, se revisará primero la forma en que el método símplex general (no simplificado) establecería el problema de transporte en forma tabular. Después de construir la tabla de los coeficientes de restricción (vea la tabla anterior), de convertir la función objetivo a la forma de maximización y de usar el método de la M para introducir las variables artificiales z₁, z₂, ..., z_m+n en las m+n ecuaciones de restricción respectivas, se ve que las columnas de la tabla símplex tendrían la forma que se muestra en la siguiente tabla:

Variable	Ec.	Coeficiente de								Lado
básica	núm.	Z	. . .	x_ij	. . .	z_i	. . .	z_m+j	. . .	derecho
Z	(0)	-1		c_ij		M		M		0
	(1)
	.
	.
	.
z_i	(i)	0		1		1				s_i
	.
	.
	.
z_m+j	(m+j)	0		1				1		d_j
	.
	.
	.
	(m+n)

En esta tabla, 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 eliminar algebraicamente los coeficientes distintos de cero de las variables básicas iniciales (artificiales) en el renglón de Z (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:

Variable

Ec.

Coeficiente de

Lado

básica

núm

. . .

x_ij

. . .

z_i

. . .

z_m+j

. . .

derecho

(0)

-1

c_ij-u_i-v_j

M-u_i

M-v_j

A causa del patrón de ceros y unos que siguen los coeficientes en la tabla anterior, u_i y v_j tienen la siguiente interpretación:

u_i = múltiplo del renglón i original que se ha restado (directa o indirectamente) del renglón 0 original durante todas las iteraciones del método símplex que llevaron a la tabla actual.

v_j = múltiplo del renglón m+j original que se ha restado (directa o indirectamente) del renglón 0 original durante todas las iteraciones del método símplex que llevaron a la tabla actual.

El renglón 0 actual se puede obtener sin usar ningún otro renglón con sólo calcular los valores de u_i y v_j directamente. Como cada variable básica debe tener coeficiente cero en el renglón 0, estos valores se pueden obtener resolviendo el sistema de ecuaciones:

c_ij-u_i-v_j = 0 para cada i y j tal que x_ij es variable básica,

lo cual se puede hacer de manera directa.

Además de los datos de entrada (los valores de c_ij, s_i y d_j), la única información que necesita el método símplex de transporte es la solución básica factible actual, los valores actuales de u_i y v_j y los valores resultantes de c_ij-u_i-v_j para las variables no básicas x_ij. Cuando se resuelve un problema a mano es conveniente registrar esta información en una tabla símplex de transporte, como la que se muestra enseguida:

En los casos en que la sumatoria de todo lo que se produce en todos los orígenes es mayor que la sumatoria de todo lo que se demanda en todos los destino o viceversa, entonces se dice que el problema no está balanceado. En estos casos lo primero que se debe hacer antes de intentar resolver el problema es balancearlo.

Para el caso de SOBREPRODUCCIÓN ( > )

Si el caso es que se dispone de mayor producción de la que se demanda, entonces para balancear el problema se agrega un destino imaginario o artificial (llamado también destino ficticio) el cual tendrá como demanda dicha sobreproducción. En cuanto a los costos asociados a este nuevo destino los estableceremos a cero (¿por qué?). El siguiente dibujo muestra lo que se debe hacer:

donde

d_n+1 =

c_i,n+1 = 0, para i = 1, 2, ..., m

Para el caso de SOBREDEMANDA ( > )

Si el caso es que se tiene mayor demanda de lo que se produce, entonces para balancear el problema se agrega un origen imaginario o artificial (llamado también origen ficticio) el cual tendrá como recursos (producirá) dicha sobredemanda. En cuanto a los costos asociados a este nuevo origen los estableceremos a cero (¿por qué?). El siguiente dibujo muestra lo que se debe hacer:

donde

s_m+1 =

c_m+1j = 0 para j = 1, 2, ..., n

Como todas las restricciones funcionales en el problema de transporte son igualdades, el método símplex obtendría una solución inicial básica factible introduciendo variables artificiales y usándolas como variables básicas iniciales. La solución básica que resulta de hecho sólo es factible para la versión aumentada del problema, por lo que se necesita un buen número de iteraciones para hacer que el valor de estas variables artificiales sea cero y se alcancen las soluciones básicas 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 en 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 lineal, 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 es m+n. Sin embargo,

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

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. La razón es que se sabe que la cantidad total que se manda desde todos los orígenes debe ser igual que la cantidad total que se recibe en todos los destinos. Por lo tanto, cualquier solución básica factible en una tabla de transporte debe aparecer con exactamente m + n - 1 asignaciones no negativas, en donde la suma de las asignaciones en cada renglón o columna es igual a su demanda o sus recursos

4.2. Métodos para encontrar soluciones factibles.

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).

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

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).

3. Se elimina ese renglón o columna (la que tenía la cantidad más pequeña en los recursos odemanda restantes) para las nuevas asignaciones.(Si el renglón y la columna tiene 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.)

4. Si sólo queda un renglón o una columna dentro de las posibilidades, entonces el procedimiento termina eligiendo como básicas cada una de las variables restantes (es decir, aquellas variables que no se han elegido ni se han eliminado al quitar su renglón o columna) asociadas con ese renglón o columna que tiene la única asignación posible. De otra manera se regresa al paso 1.

4.2.1. Método de la esquina noroeste.

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

Para hacer más concreta esta descripción, se ilustrará el procedimiento general, utilizando la regla de la esquina noroeste en el siguiente ejemplo:

Recursos

Demanda

Lo primero que debemos hacer al resolver cualquier problema de transporte es comprobar que esté balanceado, si no lo estuviera, agregamos un origen o un destino artificial según sea el caso para conseguir que el problema quede balanceado y podamos comenzar a resolverlo. En nuestro ejemplo, la sumatoria de los recursos de los tres orígenes es de 10 unidades que es igual a la sumatoria de las demandas de los destinos, por lo que nuestro problema está balanceado y podemos iniciar con la resolución.

Comenzamos asignando en la esquina noroeste de la tabla, es decir, en la celda correspondiente a la variable básica x₁₁ (paso 1), podemos observar que en la primera columna se demandan 3 unidades del bien y en el primer renglón disponemos de 5 unidades, entonces enviamos las 3 unidades demandadas desde el origen 1 hacia el destino 1 (ya que hay los recursos suficiente para satisfacer toda la demanda) y decrementamos a 2 los recursos restantes en ese origen (paso 2). Con ésto cubrimos toda la demanda del primer destino (ó almacén) y lo cancelamos para las próximas asignaciones (paso3):

Recursos

5 2

Demanda

3 0

La siguiente asignación será en la celda correspondiente a la variable x₁₂ (paso 1) ya que todavía le quedan recursos al origen 1 (además es la esquina noroeste de la tabla restante después de haber eliminado la primera columna). Notemos que en el segundo destino se demandan 4 unidades del bien y ahora solamente se disponen de 2 unidades en el origen 1, entonces se envían las 2 unidades del origen 1 al destino 2 para satisfacer 2 de las 4 unidades demandadas en este destino quedando 2 por satisfacer (paso 2) y cancelamos el origen 1 ya que no tiene más unidades del bien para enviar a otro destino
(paso 3):

Recursos

5 2 0

Demanda

3 0

4 2

La siguente asignación será en la celda correspondiente a la variable x₂₂ (paso 1) ya que no le quedan unidades del bien al origen 1 (notemos también que esa celda es la que se encuentra en la esquina noroeste de la tabla restante después de haber eliminado el primer renglón y la primera columna y no olvidemos que estamos aplicando la regla de la esquina noroeste). Ya que solamente faltan 2 unidades para satisfacer por completo la demanda del segundo destino y se disponen exactamente de 2 unidades en el segundo origen, entonces enviamos 2 unidades del bien del origen 2 al destino 2 (paso 2) y cancelamos el segundo renglón ya que no le quedan más unidades para enviar a otro destino. Dejamos pendiente la eliminación de la segunda columna ya que nos servirá más adelante para hacer la asignación de una variable básica degenerada, esdecir, una asignación con cero unidades (paso 3):

Recursos

5 2 0

2 0

Demanda

3 0

4 2 0

La siguiente asignación será en la celda correspondiente a la variable x₃₂ (paso1) ya que no le quedan más unidades al origen 2. Notemos que “se demandan cero unidades del bien en el segundo destino”, en este momento es cuando hacemos una asignación de cero unidades convirtiendo así a la variable x₃₂ en una variable básica degenerada (paso 2) y ahora sí podemos cancelar la segunda columna para ya no considerarla más en las siguientes asignaciones (paso 3). Notemos que esta demanda de cero unidades es satisfecha sin ningún problema por el origen 3 ya que éste dispone todavía de 3 unidades del bien:

Recursos

5 2 0

2 0

Demanda

3 0

4 2 0

Como solamente queda un renglón dentro de las posibilidades (el renglón 3 no ha sido cancelado), entonces aplicando el paso 4 del procedimiento general para construir una solución inicial básica factible, la siguiente asignación será en la celda que corresponde a la variable x₃₃ (paso 1). Ya que la demanda del tercer destino (2 unidades) puede ser satisfecha muy bien por el tercer origen, entonces enviamos 2 unidades del bien del origen 3 al destino 3 quedando solamente 1 unidad en el tercer origen (paso 2) para enviarlo al cuarto destino y con eso cubrir su demanda de una unidad, cancelando de esta manera tanto el destino 3 como el destino 4 y el tercer renglón ya que la demanda de todos los destinos ya ha sido satisfecha y no quedan más unidades del bien en ningún origen:

Recursos

5 2 0

2 0

3 1 0

Demanda

3 0

4 2 0

2 0

1 0

Costo = 52

La solución inicial básica factible es x₁₁=3, x₁₂=2, x₂₂=2, x₃₂=0 (variable básica degenerada), x₃₃=2 y x₃₄=1 y el costo total de transporte asociado a esta primera “Política de Transporte” factible es de:

x₁₁

c₁₁

x₁₂

c₁₂

x₂₂

c₂₂

x₃₂

c₃₂

x₃₃

c₃₃

x₃₄

c₃₄

Costo =

(3)

(7)

(4)

(3)

(8)

(5)

= 52 unidades

Es necesario aclarar que esta no es la solución final del problema, es necesario aplicar a esta primera solución factible la prueba de optimalidad ya que puede existir una mejor “política de transporte” que minimice todavía más el costo total.

4.2.2. Método de aproximación de Vogel.

2. 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 (c_ij) y el que le sigue, de los que quedan en ese renglón o columna. (Si se tiene un empate para el costo más pequeño de los restantes de un renglón o columna, entonces la diferencia es 0). 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).

Para hacer más concreta esta descripción, se ilustrará el procedimiento general, utilizando el método de aproximación de Vogel para resolver el ejemplo presentado anteriormente y que fue resuelto por la regla de la esquina noroeste:

Iniciamos el método calculando las primeras diferencias para cada renglón y columna. De las diferencias que obtuvimos nos fijamos en la mayor (¿Por qué?), que resulta ser para la tercera columna. En esa columna encontramos el costo unitario (c_ij) menor y en esa celda realizamos la primera asignación:

Recursos

DIF.

2 0

Demanda

2 0

DIF.

3 ¹

Nota: Marcaremos a la mayor de las diferencias seleccionada encerrándola en un círculo y escribiéndole como superíndice el número que le corresponda en la secuencia de selección.

Observemos en la figura anterior que únicamente eliminamos el segundo renglón ya que la tercera columna nos servirá después para hacer la asignación de una variable básica degenerada. Continuando con la aplicación del método, tenemos que calcular nuevamente las diferencias de las columnas ya que hemos eliminado un renglón y ésto puede ocasionar que las diferencias aritméticas entre el costo unitario más pequeño y el que le sigue ya no sean las mismas:

Recursos

DIF.

2 0

3 0

Demanda

4 1

2 0

DIF.

3 ¹

4 ²

Como siguiente paso deberíamos calcular las nuevas diferencias de columnas, pero ya que solamente queda un renglón dentro de las posibilidades (ésto no significa que solamente un renglón quede bajo consideración ya que podemos observar que ninguna de las cuatro columnas (destinos) ha sido eliminada y todas quedan todavía bajo consideración), no es posible encontrar la diferencia aritmética entre el costo menor y el que le sigue, por lo tanto vamos tomando una a una las celdas que quedan comenzando con la de menor costo unitario hasta que todas hayan sido asignadas.

Recursos

DIF.

5 2 1 0

2 0

3 0

Demanda

3 0

4 1 0

2 0

1 0

DIF.

3 ¹

4 ²

La solución inicial básica factible es x₁₁=3, x₁₂=1, x₁₃=0 (variable básica degenerada), x₁₄=1, x₂₃=2 y x₃₂=3 y el costo total de transporte asociado a esta primera “Política de Transporte” factible es de:

x₁₁

c₁₁

x₁₂

c₁₂

x₁₃

c₁₃

x₁₄

c₁₄

x₂₃

c₂₃

x₃₂

c₃₂

Costo =

(3)

(7)

(6)

(4)

(3)

= 35 unidades

Es necesario aclarar que ésta puede o no ser la solución final del problema, es necesario aplicar a esta primera solución factible la prueba de optimalidad ya que puede existir una mejor “política de transporte” que minimice todavía más el costo total.

Comparación de criterios alternativos para el paso 1.

Se compararán estos dos criterios para elegir la siguiente variable básica. La virtud principal de la regla de la 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. 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. El objetivo del otro criterio 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 cuenta 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.

Podemos decir, que el método de aproximación de Vogel proporciona una mejor solución inicial que el criterio de la esquina noroeste, en otras palabras es más cualitativo.

El siguiente paso después de hallar una solución inicial básica factible (por cualquiera de los dos criterios expuestos anteriormente) es verificar si esta solución inicial es efectivamente óptima aplicando la prueba de optimalidad.

La prueba de optimalidad estándar del método símplex para el problema de transporte, se puede reducir de la siguiente manera:

Una solución básica factible es óptima si y sólo si c_ij-u_i-v_j ³ 0 para toda (i,j) tal que x_ij es no básica.

Así, lo único que hay que hacer para realizar esta prueba es obtener los valores de u_i y v_j para la solución básica factible actual y después calcular los valores c_ij-u_i-v_j según se describe enseguida.

Como el valor de c_ij-u_i-v_j debe ser cero si x_ij es una variable básica, u_i y v_j satisfacen el conjunto de ecuaciones:

c_ij = u_i + v_j para cada (i,j) tal que x_ij es básica.

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 u_i y v_j) es m+n, se puede asignar un valor arbitrario a cualquiera de estas variables sin violar las ecuaciones. La elección de esta variable y su valor no afecta el valor de ningún c_ij-u_i-v_j, aun cuando x_ij sea no básica, por lo que la única diferencia (menor) estriba en la facilidad para resolver estas ecuaciones. Una elección conveniente para lograr esto es seleccionar la u_i que tiene el mayor número de asignaciones en su renglón (los empates se rompen de manera arbitraria) 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.

Para ejemplificar la prueba de optimalidad, consideremos la solución inicial básica factible obtenida por la regla de la esquina noroeste para nuestro ejemplo en cuestión:

v₁

v₂

v₃

v₄

Recursos

u_i

u₁

u₂

u₃

Demanda

Costo=52

v_j

Para este problema, existen m+n-1=3+4-1=6 variables básicas, que dan origen al siguiente conjunto de ecuaciones:

3 = u₁+v₁

7 = u₁+v₂

4 = u₂+v₂

3 = u₃+v₂

8 = u₃+v₃

5 = u₃+v₄

Observemos que resultaron ser 6 ecuaciones que involucran 7 incógnitas (tres de las u_i y cuatro de las v_j), por lo que este sistema de ecuaciones no es cuadrado. La forma de resolverlo es dando un valor arbitrario a una de las incógnitas, para que, a partir de él encontremos el valor de las demás. La regla para hacer esta asignación arbitraria nos dice que sea para la u_i (ó renglón) que haya tenido el mayor número de asignaciones. En nuestro ejemplo, el renglón 1 tuvo dos asignaciones, el renglón 2 tuvo una asignación y por último el tercer renglón tuvo tres asignaciones, por lo que asignamos el valor de cero a la incógnita u₃. De esta asignación resulta lo siguiente:

3 = u₁+v₁

7 = u₁+v₂

4 = u₂+v₂

3 = u₃+v₂®v₂ = 3

8 = u₃+v₃®v₃ = 8

5 = u₃+v₄®v₄ = 5

Hemos obtenido el valor de tres incógnitas más, v₂, v₃ y v₄, los cuales nos ayudarán para hallar el valor de las incógnitas restantes:

3 = u₁+v₁si u₁=4, entonces v₁= -1

7 = u₁+v₂si v₂=3, entonces u₁= 4

4 = u₂+v₂ si v₂=3, entonces u₂= 1

3 = u₃+v₂®v₂ = 3

8 = u₃+v₃®v₃ = 8

5 = u₃+v₄®v₄ = 5

De esta forma hemos obtenido el valor de todas las incógnitas y procedemos a colocarlos en la tabla como sigue:

v₁

v₂

v₃

v₄

Recursos

u_i

u₁

u₂

u₃

Demanda

Costo=52

v_j

-1

Ahora calculemos los valores c_ij-u_i-v_j para las variables no básicas, ya que para las básicas, este valor es cero (por la forma de las ecuaciones con que se hallaron los valores de las incógnitas u_i y v_j), y coloquemos estos valores en la esquina inferior izquierda de cada celda:

Para la celda (1,3): 6 - 4 - 8 = -6

Para la celda (1,4): 4 - 4 - 5 = -5

Para la celda (2,1): 2 - 1 - (-1) = 2

Para la celda (2,3): 3 - 1 - 8 = -6

Para la celda (2,4): 2 - 1 - 5 = -4

Para la celda (3,1): 4 - 0 - (-1) = 5

v₁

v₂

v₃

v₄

Recursos

u_i

-5

-6

u₁

-4

-6

u₂

u₃

Demanda

Costo=52

v_j

-1

En este momento se puede aplicar la prueba de optimalidad para verificar los valores de c_ij-u_i-v_j obtenidos. Como cuatro de estos valores (c₁₃-u₁-v₃= -6, c₁₄-u₁-v₄= -5, c₂₃-u₂-v₃= -6, c₂₄-u₂-v₄= -4), 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 a hacer una iteración para encontrar una mejor solución básica factible.

Una iteración.

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

Paso 1: como c_ij-u_i-v_j representa la tasa a la que cambia la función objetivo si se incrementa la variable no básica x_ij, la variable que entra debe tener un valor de c_ij-u_i-v_j negativo, para que el costo total Z disminuya. Entonces, los candidatos en la tabla anterior son x₁₃, x₁₄, x₂₃ y x₂₄ . Entre ellos se elige el valor negativo más grande (en términos absolutos) de c_ij-u_i-v_j como la variable básica entrante, que en este caso corresponde a x₁₃ y x₂₃. En los casos en que haya empate para la elección de la variable básica entrante, este empate se rompe de manera arbitraria, ya que tarde o temprano llegaremos a la misma solución independientemente de la elección de la variable. Pero, observemos lo siguiente: ya que debemos elegir la variable básica “entrante, es decir, aquella que comenzará a tener un valor (ya que antes no lo tenía porque era variable no básica), entonces, es conveniente que elijamos aquella que tenga el costo menor, ya que el valor de la variable entrante multiplicado por su respectivo costo será la contribución al costo total. En nuestro caso, el costo asociado a x₁₃ es 6 y el costo asociado a x₂₃ es 3, por lo que la variable que debemos elegir como entrante es x₂₃.

Paso 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. 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 tiene 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 a 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 aseguir para averiguar cuál debe seleccionarse como celda 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. (En caso de un empate para la celda donadora, se puede elegir cualquiera para proporcionar la variable básica que sale).

Si x₂₃ es la variable básica entrante, la reacción en cadena de la tabla anterior se resume enseguida. (Siempre se indicará la variable básica entrante colocando un signo + encuadrado dentro de su celda):

v₁

v₂

v₃

v₄

Recursos

u_i

-5

-6

u₁

-4

-6

u₂

u₃

Demanda

Costo=52

v_j

-1

Al aumentar x₂₃ debe disminuir x₃₃ en la misma cantidad para conservar la demanda de 2 en la columna 3; esto a su vez requiere que se aumente x₃₂ en esa cantidad para mantener la oferta de 3 en el renglón 3 y esto a su vez exige una disminución en el valor de x₂₂ para conservar la demanda de 4 en la columna 2. Esta disminución en x₂₂ completa con éxito la reacción en cadena ya que también conserva la oferta del renglón 2.

El resultado final es que las celdas (2,3) y (3,2) se convierten en celdas receptoras, cada una con su asignación adicional proveniente de las celdas donadoras (2,2) y (3,3). Estas celdas están indicadas en la tabla anterior por medio de los signos + y -). Observe que tuvo que elegirse la celda (3,2) como celda receptora para el renglón 3 y no la (3,4), ya que esta última no hubiera tenido celda donadora en la columna 4 para continuar la reacción en cadena. Note además que, a excepción de la variable básica entrante, todas las celdas receptoras y donadoras en la reacción en cadena deben corresponder a variables básicas en la solución básica factible actual.

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 las celdas (2,2) y (3,3)- debe ser la primera en llegar a una asignación de cero conforme se incrementa la variable entrante x₂₃. Así, x₂₂ ó x₂₃ se pueden convertir en la variable básica que sale. Cuando existe empate para la variable básica que sale, éste puede romperse de manera arbitraria, es decir, eligiendo cualquiera de las variables donadoras con la asignación más pequeña como variable básica saliente. Como una regla empírica, podemos seleccionar como variable básica saliente aquélla que tenga asociado el mayor costo unitario, ya que como esta variable perderá completamente su valor (es decir, se convertirá de variable básica a variable no básica), esperaríamos que el costo total de transporte disminuya. Así, escogeríamos a x₃₃ como variable básica saliente.

Paso 3: la nueva solución básica factible se identifica sumando el valor (antes de los cambios) de la variable básica que sale a las asignaciones de cada celda receptora y restando esta misma cantidad de las asignaciones de cada celda donadora. En la tabla anterior se observa que el valor de la variable básica que sale x₃₃ es 2, por lo que esta porción de la tabla símplex de transporte cambia, como se ilustra en la siguiente tabla para la nueva solución. (Como x₃₃ es no básica en la nueva solución, su nueva asignación es cero y ya no se muestra en la tabla).

v₁

v₂

v₃

v₄

Recursos

u_i

-5

-6

u₁

-4

-6

u₂

u₃

Demanda

Costo=40

v_j

En este momento se puede señalar una interpretación útil de las cantidades c_ij-u_i-v_j que se obtienen en la prueba de optimalidad. Debido al cambio de 2 unidades en las asignaciones de las celdas donadoras a las receptoras, el costo total cambia en:

DZ = 2(3-8+3-4) = 2(-6) = -12 = 2(c₂₃-u₂-v₃)

es decir, el costo total de transporte se decrementa en 12 unidades con respecto al costo anterior que era de 52 unidades. Notemos que hemos obtenido una nueva política de transporte, la cual podemos resumir así:

La nueva solución básica factible es x₁₁=3, x₁₂=2, x₂₂=0 (variable básica degenerada), x₂₃=2, x₃₂=2 y x₃₄=1 y el costo total de transporte asociado es de:

x₁₁

c₁₁

x₁₂

c₁₂

x₂₂

c₂₂

x₂₃

c₂₃

x₃₂

c₃₂

x₃₄

c₃₄

Costo =

(3)

(7)

(4)

(3)

(5)

= 40 unidades

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

Resumen del método símplex de transporte

Inicialización: Se construye una solución inicial básica factible. Se realiza la prueba de optimalidad.

Prueba de optimalidad: Se obtiene u_i y v_j eligiendo el renglón con el mayor número de asignaciones y estableciendo su u_i = 0, y después resolviendo el sistema de ecuaciones c_ij = u_i+v_j para cada (i,j) tal que x_ij es básica. Si c_ij-u_i-v_j ³ 0 para toda (i,j) tal que x_ij es no básica, entonces la solución actual es óptima por lo que el proceso se detiene. De lo contrario, se regresa a una iteración.

Iteración:

1. Se determina la variable básica entrante: se elige la variable no básica x_ij que tiene el valor negativo más grande (en términos absolutos) para c_ij-u_i-v_j.

2. Se determina la variable básica que sale identificando la reacción en cadena (encontrar un circuito) 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.

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

Continuando con la aplicación de este procedimiento a nuestro problema, tenemos que calcular los nuevos valores de las u_i y v_j y después los valores c_ij-u_i-v_j correspondientes a las variables no básicas para determinar si todos cumplen con la prueba de optimalidad: Nuevamente existen m+n-1=3+4-1=6 variables básicas, que dan origen al siguiente conjunto de ecuaciones:

3 = u₁+v₁

7 = u₁+v₂

4 = u₂+v₂

3 = u₂+v₃

3 = u₃+v₂

5 = u₃+v₄

Observemos que nuevamente resultaron ser 6 ecuaciones que involucran 7 incógnitas (tres de las u_i y cuatro de las v_j). Ya que hay empate en el número de asignaciones que tiene cada renglón (2 asignaciones en cada renglón), asignemos el valor de cero a la incógnita u₁. De esta asignación resulta lo siguiente:

3 = u₁+v₁® v₁=3

7 = u₁+v₂® v₂=7

4 = u₂+v₂

3 = u₂+v₃

3 = u₃+v₂

5 = u₃+v₄

Hemos obtenido el valor de dos incógnitas más, v₁, y v₂, los cuales nos ayudarán para hallar el valor de las incógnitas restantes:

3 = u₁+v₁® v₁=3

7 = u₁+v₂® v₂=7

4 = u₂+v₂si v₂=7, entonces u₂= -3

3 = u₂+v₃si u₂= -3, entonces v₃=6

3 = u₃+v₂si v₂=7, entonces u₃= -4

5 = u₃+v₄si u₃= -4, entonces v₄=9

De esta forma hemos obtenido el valor de todas las incógnitas y procedemos a colocarlos en la tabla como sigue:

v₁

v₂

v₃

v₄

Recursos

u_i

u₁

u₂

-3

u₃

-4

Demanda

Costo=40

v_j

Ahora calculemos los valores c_ij-u_i-v_j para las variables no básicas y coloquemos estos valores en la esquina inferior izquierda de cada celda:

Para la celda (1,3): 6 - 0 - 6 = 0

Para la celda (1,4): 4 - 0 - 9 = -5

Para la celda (2,1): 2 - (-3) - 3 = 2

Para la celda (2,4): 2 - (-3) - 9 = -4

Para la celda (3,1): 4 - (-4) - 3 = 5

Para la celda (3,3): 8 - (-4) - 6 = 6

v₁

v₂

v₃

v₄

Recursos

u_i

-5

u₁

-4

u₂

-3

u₃

-4

Demanda

Costo=40

v_j

Aplicando la prueba de optimalidad para verificar los valores de c_ij-u_i-v_j obtenidos, vemos que dos de estos valores ( c₁₄-u₁-v₄= -5, c₂₄-u₂-v₄= -4) 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 a hacer una iteración para encontrar una mejor solución básica factible. Aplicando el procedimiento descrito anteriormente, se llega al siguiente conjunto de tablas símplex de transporte que se muestra enseguida y que dan solución al problema planteado:

v₁

v₂

v₃

v₄

Recursos

u_i

-5

u₁

-4

u₂

-3

u₃

-4

Demanda

Costo=40

v_j

v₁

v₂

v₃

v₄

Recursos

u_i

-5

u₁

-4

u₂

u₃

Demanda

Costo=35

v_j

La nueva solución básica factible es x₁₁=3, x₁₂=1, x₁₄=1, x₂₂=0 (variable básica degenerada), x₂₃=2 y x₃₂=3 y el costo total de transporte asociado es de:

x₁₁

c₁₁

x₁₂

c₁₂

x₁₄

c₁₄

x₂₂

c₂₂

x₂₃

c₂₃

x₃₂

c₃₂

Costo =

(3)

(7)

(4)

(3)

= 35 unidades

Como en esta última tabla todas las c_ij-u_i-v_j son no negativas (¡comprobarlo!), la prueba de optimalidad identifica este conjunto de asignaciones como óptimo, lo cual concluye el algoritmo.

Costo de embarque ($) por carga

Producción

A =

Costo por unidad distribuida

Origen

Coeficiente de

Coeficiente de