Transporte
TRANSPORTE
El modelo de transporte es básicamente un programa lineal que se puede resolver por el método SIMPLEX regular.
Sin embargo, su estructura especial hace posible el desarrollo de un procedimiento de solución distinto, conocido
como técnica de Transporte, que es más eficiente en términos de cálculos matemáticos.
Concepto: El modelo de transporte busca determinar un plan de transporte de una mercancía de varias fuentes a
varios destinos. El modelo cuenta con los siguientes datos:
1) Nivel de oferta de cada fuente y la cantidad de demanda en cada destino.
2) El costo del transporte unitario de la mercancía de cada fuente a cada destino. Como solo hay una mercancía,
un destino puede recibir su demanda desde una o más fuentes.
El objetivo del modelo es determinar la cantidad que se enviara de cada fuente a cada destino, tal que se
minimice el costo del transporte total.
FUENTES DESTINOS
a1 C11: X11 b1
1 1
a2 b2
2 2
Unidades Unidades
de Oferta
. . de Demanda
. .
. .
. .
. .
am bn
m Cmn: Xmn n
Figura 1: Modelo de transporte típico
m : cantidad de orígenes.
n : cantidad de destinos.
Xij: representa la cantidad transportada desde la fuente i al destino j
Cij : representa el costo por cada unidad transportada de la fuente i al destino j
ai : representa la cantidad producida por las fuentes u orígenes “ i ”.
bj : representa la cantidad demandada por el destinos “ j “.
Matemáticamente el modelo se puede representa como:
Función objetivo:
m n
Z cij xij min
i 1 j 1
Páginas 1 de 10
Transporte
Sujeto a las restricciones
n
xij ai , con i = 1,2 ..... m
j 1
m
xij b j , con j = 1,2 .... n
i 1
y
xij 0 i j
Planteo del problema tipo de transporte
Se tiene un determinado producto o ítem y una serie de plantas productoras almacenadoras del mismo. Son los
ORIGENES: desde los cuales saldrá el producto. También existen una serie de DESTINOS, o clientes que reclaman
ese producto y a los cuales se debe satisfacer o sea:
Orígenes: O1, O2, ..., Oi, ...Om (m orígenes)
Cada uno con una disponibilidad: a1, a2, ...ai, ...an
Destinos: D1, D2, ...Dj, ...Dn (n destinos)
Cada uno con un requerimiento b1, b2, ...bj, ...bn
Los orígenes están vinculados a los destinos que relaciona el par Oi, Dj con un costo: Cij; por transportar
cada unidad (o algo considerado unidad), desde el origen i hasta el destino j
Se conocen todos los costos cij y un costo: infinito, significa que no puede hacerse esa conexión o
recorrido.
Cada destino debe recibir la cantidad aj que reclama.
El costo total del transporte, debe ser el menor posible.
Con todos estos datos se tratara de plantear un problema de programación lineal, recordando que solo
aparece el costo del transporte.
Datos: ai, bj, cij
Incógnitas: xij, cantidad a transportar desde cada origen i a cada destino j
Se puede visualizar en 2 tablas
Oi \ Dj D1 D2 D3 D4 Oi \ Dj D1 D2 D3 D4
O1 c11 c12 c13 c14 O1 x11 x12 x13 x14
O2 c21 c22 c23 c24 O2 x21 x22 x23 x24
O3 c31 c32 c33 c34 O3 x31 x32 x33 x34
Se puede cumplir uno de los tres siguientes casos:
m n
1) bi aj
i 1 j 1
m n
2) bi aj
i 1 j 1
m n
3) bi aj
i 1 j 1
Donde i
a yb
j son números enteros positivos, i = 1, ..., m; j =1, ..., n.
En el primer caso: todo se mueve, todo llega a destino.
En el segundo: hay un sobrante que quedara en algún o algunos orígenes.
En el tercero: hay una insatisfacción de los requerimientos, algún o algunos orígenes quedaran sin completar sus
requerimientos.
Páginas 2 de 10
Transporte
Para el primer caso se pueden encontrar la solución. En cambio paro los casos segundo y tercero mediante un
artificio se reducirán al primero
Anormalidades:
m n
En el caso de que la oferta total sea mayor que la demanda total, es decir ai b j entonces se agrega un
i 1 j 1
m n
centro de consumo artificial n + 1 cuya demanda bn 1 es ai b j y cuyos costos unitarios ck ,n 1 k= 1, ..., m
i 1 j 1
son todos ceros.
En forma tabular se tiene
Destinos
1 2 ... n n+1 Oferta
1 c11 c12 ... c1n 0 a1
2 c12 c22 ... c21 0 a2
Origenes ... ... ... ... ... … ...
m cm1 cm2 ... cmn 0 am
m n
Demanda b1 b2 ... bn ai bj
i 1 j 1
Costos
n m
Por otro lado, si la demanda total excede a la oferta total, es decir bj ai , entonces se añade un centro
j 1 i 1
n m
de oferta artificial m + 1, cuya capacidad de oferta a m 1 es bj ai y cuyos costos unitarios cm 1,k k = 1, ...
j 1 i 1
, n son todos ceros.
En forma tabular se tiene
Destinos
1 2 ... n Oferta
1 c11 c12 ... c1n a1
2 c12 c22 ... c21 a2
Origenes ... ... ... ... ... ...
M cm1 cm2 ... cmn am
n m
m+1 0 0 … 0 bj ai
j 1 i 1
Demanda b1 b2 ... bn
Costos
Cuando el problema de transporte real está desbalanceado, añadiendo ya sea orígenes o destinos artificiales, se le
balancea y así se satisface la condición necesaria y suficiente para que el problema tenga solución.
Supondremos un problema elemental de dos por tres.
Destino 1 2 3 Cantidad
Origen
1 35 40 28 800
2 32 43 31 500
350 620 330 1300
Los valores de dentro de la tabla son los costos UNITARIOS de transporte.
El origen 1 puede despachar 800 unidades, el 2 500 unidades; el destino 1 requiere 350 unidades, el 2 requiere 620
y el 3 requiere 330.
Páginas 3 de 10
Transporte
800 + 500 = 350 + 620 + 330. Se cumple la condición de cantidad requerida igual a cantidad despachada.
Las restricciones lineales son:
x11 x12 x13 800 (52 )
x21 x22 x23 500 (53)
x11 x21 350 (54 )
x12 x22 620 (55)
x13 x23 330 (56)
Si sumamos (52) y (53) da:
x11 x12 x13 x21 x22 x23 1300
.
Si a esta le restamos (55) y (56) queda:
x11 x21
(54) 350
O sea, una de las ecuaciones es redundante. Es combinación lineal de las otras.
Número de ecuaciones = m n 2 3 5
Número de variables principales = mn 2x3 6
El número de ecuaciones linealmente independientes es entonces: m n 1
En nuestro sistema de restricciones (52) a (56) habrá cuatro valores xij 0
Además
xij 0 i j
Esto se puede resolver. Si eliminamos, arbitrariamente, la ecuación (54) nos queda:
Minimice
35 x11 40 x12 28 x13 32 x21 43 x22 31 x23
s.a.
x11 x12 x13 1 800
x 21 x 22 x 23 2 500
x11 x 21 3 350
x13 x 23 4 620
Sería una tabla Simplex con 10 columnas y 4 filas. Las columnas son 6 para las variables principales y 4 para las
variables artificiales.
Hay una forma más sencilla. Un algoritmo de transporte. La primera solución se puede obtener por varios
métodos. Comencemos por uno.
Método Noroeste:
Este método comienza asignando la máxima cantidad posible de la variable x11, (que es el extremo noroccidental
de la matriz y de ahí el nombre de este método) asígnese de manera que satisfaga totalmente la demanda
(columna), o bien, se agote la oferta (fila). Como en el primer caso se satisface la demanda, se tacha la columna, y
en el segundo caso, como lo que se agota es la oferta se tacha la fila indicando que las variables son iguales a cero.
Cuando se satisface simultáneamente una fila y una columna, solo se tacha uno de ellos, la fila o la columna. Esta
condición garantiza la ubicación automática de variables básicas cero, si las hay. Después de ajustar las cantidades
de oferta y demanda de todas las filas y columnas no tachadas, la cantidad factible máxima se asigna el primer
elemento de la columna (fila). El proceso se termina cuando se deja de tachar una fila o una columna.
Este método es muy sencillo de desarrollar, pero tiene la desventaja de no tener en cuenta los costos por lo que no
arriba a una solución optima.
En nuestro ejemplo tenemos
35 40 28 800
32 43 31 500
350 620 330
A partir de ahora dejamos establecido que anotamos abajo de las columnas los requerimientos de los destinos y a
la derecha de las filas las cantidades enviadas por los orígenes.
Páginas 4 de 10
Transporte
El noroeste es arriba y a la izquierda, donde tenemos el costo de 35.
350 450
- 500
350 620 330
Debemos asignar. Para ello nos fijamos en la tabla. La esquina más arriba y a la izquierda es la 1-1. Allí podemos
enviar 800 desde el primer origen, pero desde el primer destino nos piden sólo 350. O sea, sólo podemos asignar
350. Lo hacemos.
Esas 350 unidades ya no están en el origen 1 y ya no las demandan desde el destino 1. Las descontamos de su fila y
columna.
Obsérvese que en el lugar 2-1 se pusieron guiones porque ya está cubierta la demanda del destino 2.
Ahora el extremo noroeste es 1-2. Allí podemos asignar 620 ó 450. Desde luego ya nos damos cuenta de que
siempre es el menor. Asignamos 450 y descontamos de su fila y columna.
350 450 - 0
- 500
0 170 330
Pusimos también guiones en 1-3 porque desde ese origen no podemos surtir más.
Ahora el extremo noroeste es 2-2. Allí asignamos 170.
Y por último nos queda 330 que debe poderse asignar y debe poderse asignar sin que queden remanentes.
350 450 - 0
- 170 330 0
0 0 0
Como tenemos 2 orígenes y 3 destinos, m+n-1 es 2 + 3 - 1 = 4. Como tenemos cuatro valores positivos tenemos
una primera solución básica factible no degenerada (SBFND).
El valor de su funcional es:
UM UM UM UM
z 35 350 u 40 450 u 43 170 u 31 330 u 47.790 UM
u u u u
Método de los Costos Mínimos:
El procedimiento es el siguiente: asígnese el valor más grande posible a la variable con el menor costo unitario de
toda la tabla (los empates se rompen en forma arbitraria). Táchese el renglón o columna satisfecha. Como en el
método del noroeste, si una columna y un renglón se satisfacen de manera simultanea, solo uno puede tacharse.
Después de ajustar la oferta y la demanda de todas las filas y columnas no tachadas, repítase el proceso asignando
el valor más grande posible a la variable con costo unitario no tachado más pequeño. El procedimiento esta
completo cuando queda exactamente una fila o bien una columna sin tachar.
Este método tiene la desventaja de que la elección se lleva acabo por los costos mínimos, no teniendo en cuenta la
cantidad de mercancía a transportar, pudiendo ocurrir que los últimos movimientos que son los más costosos se
transporte mayor mercancía que en los primeros, no arribando a costos óptimos.
En nuestro ejemplo tenemos
35 40 28 800
32 43 31 500
350 620 330
Si observamos los costos vemos que el menor de todos es 28 en 1,3. Lo máximo que podemos asignar allí es 330 u.
Lo hacemos y descontamos de fila y columna. Se cubrió la demanda del destino 3 por lo que se completa con – en
el casillero 2 ,3.
330 470
- 500
350 620 0
Se repite el procedimiento hasta tener todas las asignaciones
Páginas 5 de 10
Transporte
- 470 330 0
350 150 - 0
0 0 0
Solución Básica Factible no degenerada (SBFND): cumple con n+n-1 asignaciones
UM UM UM UM
z 40 470u 28 330u 32 350u 43 150u 45.690UM
u u u u
Método de aproximación de Vogel (VAM):
Este es un método heurístico y suele producir una mejor solución inicial que otros métodos. De hecho VAM suele
producir una solución inicial óptima o próxima al nivel óptimo.
Los pasos del procedimiento son los siguientes:
Paso 1: Evalúese una penalización para cada fila o columna restando el menor elemento de costo de la fila
o columna del elemento menor siguiente en la misma fila o columna.
Paso 2: identifíquese la fila o columna con la mayor penalización, rompiendo empates en forma arbitraria.
Asígnese el mayor valor posible a la variable con el costo mas bajo de la fila o columna seleccionada. Ajústese la
oferta y la demanda y tachase la fila o columna satisfecha. Si una fila una columna se satisface al mismo tiempo,
solo una de ellos se tacha y la fila o columna restante se asigna a una oferta o demanda cero. Cualquier fila o
columna con oferta o demanda cero no debe utilizarse para calcular penalizaciones futuras.
Paso 3:
a) Si solo hay una fila o columna sin tachar, hay que detenerse
b) Si solo hay una fila o columna con oferta o demanda positiva sin tachar, se determinan la asignación
a través del método del costo mínimo.
c) Si todas las filas y columnas sin tachar tienen asignadas una oferta y demanda cero, se determinan la
asignación a través del método del costo mínimo.
d) De lo contrario se calculan las penalizaciones de las filas y columnas no tachadas y volver al paso 2.
(Obsérvese que las filas y columnas con oferta y demanda cero asignadas no deben utilizarse para
determinar estas penalizaciones.
En nuestro ejemplo tenemos
Dif. 3 3 3
Col/fila
7 35 40 28 800
1 32 43 31 500
350 620 330
Dif. 3 3
Col/fila
5 35 40 330 470
11 32 43 - 500
350 0 330
Dif. 3
Col/fila
- 470 330 0
350 43 - 150
0 620 0
Dif.
Col/fila
- 470 330 0
350 150 - 0
0 0 0
Solución Básica Factible no degenerada (SBFND): cumple con n+n-1 asignaciones
Páginas 6 de 10
Transporte
UM UM UM UM
z 40 470u 28 330u 32 350u 43 150u 45690UM
u u u u
Una vez que se ha proporcionado una solución básica factible no degenerada, se trata de determinar si dicha
solución es óptima y, en caso de no serlo, obtener una nueva solución con menor coste que la solución actual.
Una solución óptima puede ser degenerada, pero no puede serlo la solución a partir de la cual se vaya a obtener
otra mejor.
Si la solución básica obtenida no es óptima, la mejora es posible y ésta se puede llevar a cabo mediante diferentes
métodos, entre los que podemos citar el método de STEPPING-STONE, el método MODI (Modified-Distribution-
Method llamado método u-v).
Método de los Circuitos ( Stepping- Stone):
El algoritmo de Stepping-Stone conocido también con el nombre del método del paso a paso, consiste en calcular
cuál sería la variación del coste al enviar una unidad de producto por una ruta no utilizada, es decir, calcula los
costes marginales de cada ruta no utilizada.
Este método se realiza de la siguiente manera:
Paso1: Usar la solución Básica factible actual para evaluar el “Costo marginal” de enviar material por cada una de
las rutas “No usadas”.
Se elige un casillero x para mandar algo por ese casillero y mantener el equilibrio en toda la matriz, se forma el
circuito:
- +
+ -
Pero esta distribución cambia los costos. Por cada unidad que se manda por los casilleros marcados con: +, se paga
el cij respectivo y por cada unidad que se deja de mandar por los casilleros marcados con: -, se deja de pagar el cij
respectivo.
Páginas 7 de 10
Transporte
Paso 2: Si todos los “Costos marginales” son 0 se habrá encontrado la “solución óptima”.
Si no, elegir la “Celda con el costo marginal Más grande”.
Paso 3: Determinar el “Máximo número de artículos” que pueden ser asignados a la ruta elegida en el paso 2
Paso 4: Regresar al paso 1 Para reevaluar el “Costo marginal” de las rutas “No usadas”.
Suponiendo la siguiente Tabla de costos y requerimientos:
Oi\Di D1 D2 D3 D4 bi
O1 36 26 34 28 300
O2 25 37 31 32 200
O3 29 33 40 38 150
aj 120 130 220 180
Tenemos la siguiente SBFND por el método Vogel, donde marcamos con X un casillero alternativo de solución y
armamos el circuito.
Z= 19600
Oi\Di D1 D2 D3 D4
O1 130 170
O2 120 (-) 80 (+)
O3 X (+) 140 (-) 10
Lo mínimo que se puede sacar de los casilleros marcados con – es 120 unidades, que se agregaran a los casilleros
marcados con +. El casillero 21 queda vacío y de esta manera siempre quedan 6 casilleros ocupados.
Pero esta distribución cambia los costos, por cada unidad que se manda por los casilleros marcados con +, se paga
el cij respectivo y por cada unidad que se deja de mandar por los casilleros marcados con el signo – se deja de
pagar el cij correspondiente. Por lo que hacemos el cálculo del indicador que nos dice si el casillero elegido para
que forme la nueva solución básica factible conviene o no.
Realizamos el cálculo:
c21 + c33 = 25 + 40 = 65 GANANCIA POR NO USAR ESOS CASILLEROS.
c31 + c23 = 29 + 31= 60 GASTO POR USAR ESOS CASILLEROS.
Queda 65 – 60 = 5 El indicador es positivo y señala que casillero se debe usar.
Finalmente:
Oi\Di D1 D2 D3 D4
O1 130 170
O2 0 200
O3 120 20 10
Con 6 elementos que forman la base. La función Z es:
Z= 120 * 29 + 130 * 26 + 200 * 31 + 20 * 40 + 170 * 28 + 10 * 38 = 1900
Método de MODI (Modified-Distribution-Method):
El algoritmo MODI conocido como el método de los costes ficticios, consiste en añadir a la matriz de costes una fila
y una columna que recogen unos costes ficticios determinados arbitrariamente (los números MODI), tal que
permite calcular los índices de mejora para las celdas (casillas) no utilizadas sin tener que trazar todos los circuitos
(ciclos) que requiere el algoritmo de Stepping-Stone. En general, supone ahorros en tiempo respecto a la
utilización del algoritmo de Stepping-Stone en la resolución de problemas de transporte, debido a su rapidez y el
fácil tratamiento de las soluciones degeneradas.
El método que encuentra el indicador es el método MODI, en cada casillero se escriben:
Páginas 8 de 10
Transporte
zij - cij zij
base
En los casilleros de la base:
zij – cij = 0 zij = cij
Cada zij = cij de la base se descompone en la suma ui + vj como si ese costo se pagara entre el origen y destino.
Se elige uno cualquiera, por ejemplo ui = 10
El resultado final es el mismo si se escribe: ui = 10 + h 28 = 10 + 18
Y así todos los costos de las bases, surgen, paga 18 siempre
Cuando se completan todos los ui y vi se escriben los zij = ui + vj y luego los zij – cij en los casilleros que no
pertenecen a la base.
Los zij – cij < 0 indican un casillero que no conviene usar
Los zij – cij > 0 indican un casillero que si conviene usar
Los zij – cij = 0 indican un casillero alternativo
Al igual que en la tabla del simplex, los zij – cij negativos indican los casilleros que mejoran un funcional que
minimiza.
Al repetir los cálculos del método MODI no aparece ningún zij – cij > 0, luego ningún casillero mejora el
funcional, es la tabla óptima
El zij – cij < 0 significa cuánto se pagará de más por cada unidad que se mande por ese casillero. Mala
elección.
El zij – cij > 0 significa cuánto se paga de menos por cada unidad que se envía por ese casillero. Buena
elección.
El zij – cij = 0 es la base, ya se está usando y si no pertenece a la base es alternativo su uso, el funcional no
varía
Los zij – cij son los costos indirectos
No aparecen las variables slacks.
Soluciones degeneradas
Se dice que una solución básica en programación lineal es degenerada cuando tiene menos variables positivas que
el número de restricciones existentes en el problema. En los programas lineales de transporte se presenta con
alguna frecuencia el problema de la degeneración. En el problema de transporte simple existen (m+ n-1)
restricciones independientes. La degeneración se presentará cuando en una solución básica el número de
posiciones localizadas o rutas utilizadas sea menor que (m+n-1).
Una solución óptima puede ser degenerada, es decir, cuando el número de posiciones localizadas es menor que
(m+n-1). Sin embargo, para comprobar si la solución actual es o no óptima y en su caso mejorarla, es necesario que
sea no degenerada. La consecuencia de la degeneración es que los métodos paso a paso, MODI, no se pueden
aplicar.
DEGENERACION
Sucede cuando una xij de la base se anula. Se pierde una componente de la base. Es consecuencia de la anulación
simultánea de una fila y una columna durante la distribución.
Hay menos xij distintos de 0 que la cantidad: m + n – 1 que debería haber.
Ejemplo:
170 130 300 130
420 80 500 80
250 250
170 130 420 330
250
Páginas 9 de 10
Transporte
La primer solución básica factible, por la regla del NO, tendría que tener 6 componentes y solo tiene 5.
Artificio: Para evitar la degeneración a cada bi se le suma un
b1 +
b2 +
...
bi +
…
bm +
---------
m
Total de disponibilidad = ( bi ) + m
i 1
Para mantener el equilibrio de la matriz, estos m se le suman a una cualquiera de la aj:
a1 a2 ... aj + m ... an
n
Total de requerimientos = ( aj ) + m
j 1
170 130 300 + 430 + 3
420 - 80 + 2 500 + 80 + 2
250 + 250 +
170 130 420 330 + 3
420 - 250 +
Aparecen asi 6 valores de xij > 0
Cuando se llaga a la tabla optima, se hace -> 0. Recién en ese pazo se calcula el z.
MAXIMIZACION
Se escribe el complemento de la matriz de costo, con respecto al mayor costo. A esa matriz se la aplican los
métodos conocidos. Obtenido el resultado el z se calcula sobre la primera matriz Cij
c11 c12 ... c1n cij – c11 cij – c12 ... cij – c1n
... ... ... ... ... ... ... ...
cm1 cm2 ... cmn cij – cm1 cij – cm2 ... cij - cmn
MAX = Cij
Páginas 10 de 10
