Investigación de Operaciones M.Sc. Javier Beltrán S.

Tema N.º 4
EL MODELO DE TRANSPORTE
Existe una amplia variedad de aplicaciones de la PL. Entre los tipos de problemas
particularmente importantes se encuentran los problemas de Transporte y Transbordo

4.1. CARACTERIZACIÓN
Uno de los casos particulares de la PL. es el problema de Hitckcok, o del Transporte. El
problema general del transporte se refiere a la distribución de un determinado 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 gastos
totales de distribución.

Tal vez, el tipo especial más importante de problemas de PL., sea el de transporte, debido
a que, estando bien definido a su estructura especial, permite utilizarlo, para simplificar
la versión del simplex de transporte, logrando enormes ahorros de cálculo.

Entre las ventajas de utilizar el Simplex del trasporte pueden señalarse:

 No es necesario utilizar variables artificiales

 La fila Zj-Cj del algoritmo de simplex puede calcularse directamente.
 La variable básica saliente se identifica de forma sencilla sin utilizar los coeficientes de
la variable básica entrante.

Para resolver un problema de transporte se necesitan 2 fases o etapas, cada una de ellas
usando un determinado algoritmo. En la primera fase, se hace uso de soluciones iniciales,
para lo cual se disponen de varios métodos de resolución.

En la segunda fase, se resuelve probando la solución hallada en la fase anterior y

mejorándola, si es posible. Se tienen varios algoritmos para probar si la solución es
óptima o no.

Cuando el esquema del transporte hace uso de puntos intermedios, se dice que el
problema es de transbordo, el cual también se estudia en esta sección.

4.2. PLANTEAMIENTO DEL PROBLEMA DE TRANSPORTE

En la siguiente figura se puede concebir el problema de transporte, donde los orígenes

se constituyen las fábricas o centros de producción de bienes y/o servicios, y los destinos
se representan como los almacenes o centros de distribución de dichos productos y/o
servicios, o inclusive las mismas ciudades donde se demanda algún artículo.

A continuación, se presenta de forma esquemática el problema de transporte:

121
Investigación de Operaciones M.Sc. Javier Beltrán S.

FIGURA N.º 40
ESQUEMA DEL PROBELMA DE TRANSPORTE
CIJ

De esta manera, el planteamiento del problema es el siguiente:

 Existen m orígenes y se supone que en cada origen hay ai unidades almacenadas de un

determinado producto. Donde i = 1, 2, ...m.
 Existen también n destinos y cada uno necesita un embarque de bj unidades de ese
producto, siendo j = 1, 2, … n.

Las cantidades ai se denomina exigencias fila y las bj exigencias columna. De esta

manera la tabla del transporte tiene la siguiente característica:

DESTINOS
O 1 2 3 ...j... n Disponibilidad
R
I C11 C12 C13 C1j C1n a1
G 1
2 C21 C22 C23 C2j C2n a2
E
N I Cij Ci2 Ci3 Cij Cin ai
M Cm1 Cm2 Cm3 Cmj Cmn am
Demandas b1 b2 b3 bj bn

Todas las exigencias por fila son positivas, así como las exigencias por columna, puesto
que los valores nulos o negativos no tienen significado.

La suma de las exigencias por fila debe ser igual a la suma de las exigencias por columna;
en caso de que esto no fuera así, se debe proceder a balancear el problema, como
requisito indispensable.

El coste de transporte de una unidad de producto desde el origen i hasta el destino j viene
representado por los Cij. Los Cij se denominan coeficientes de coste.

La solución a un problema de transporte puede escribirse como una matriz solución, así:

122
Investigación de Operaciones M.Sc. Javier Beltrán S.

 X 11 X 12 X 1n 
X =  X 21 X 22 X 2 n 
 X m1 X m2 X m n 

n m

 X ij = ai
j =1
Xi =1
ij = bj

Min Z = C11 * X11 + C12 * X12 + ... + Cmn * Xmn

Una solución posible básica no degenerada, será si contiene m + n – 1 variables solución,

y una solución posible básica degenerada, será aquella que contiene menos de m + n –
1 variables en solución.

4.3. CÁLCULO DE LA SOLUCIÓN DE UN PROBLEMA DE TRANSPORTE

Las etapas básicas que permiten el cálculo de la solución a un problema de transporte

son:

 Determinación de una Solución Básica Inicial (SBI) y

 Prueba de Optimalidad (PO)

4.3.1. DETERMINACIÓN DE UNA SOLUCIÓN BÁSICA INICIAL

El objetivo de esta primera etapa, es obtener una solución inicial, la cual sea básica y
factible, en términos, de que ésta no sea degenerada. Los métodos más habituales para
ello son:

Métodos para determinar la SBI

 Método de la Esquina NOROESTE
 Mínimo de filas
 Mínimo de Columnas
 Método de Costos Mínimos
 Método de Aproximaciones de Vogel
 Método Russell

Ejemplo: Una Compañía dispone de cinco puntos de venta A, B, C, D y E, y de cuatro

fábricas X, Y, Z y T. Los pedidos mensuales de los puntos de venta, expresados en miles
de unidades son:

A B C D E Total
75 20 15 25 40 175

La producción mensual en miles de unidades es:

123
Investigación de Operaciones M.Sc. Javier Beltrán S.

X Y Z T Total
60 75 80 35 250

La matriz de costes unitarios de transporte viene dada por:

A B C D E
X 0.8 2.7 1.7 1.4 0.9
Y 0.9 0.5 1.0 0.2 1.3
Z 0.7 2.1 1.8 1.4 1.1
T 2.3 0.9 1.1 1.8 2.5

Se desea determinar una solución inicial por los métodos mencionados:

 Método de Esquina NOROESTE

Este método consiste en asignar el primer valor en la esquina (casilla) superior izquierda,
de manera que el número de unidades asignadas no exceda tanto la oferta como
demanda. De esta forma se deberá asignar al menor valor de la fila o columna ubicada;
de esta forma, en dicha fila o columna asignada ya no es posible otra asignación. El
siguiente paso consiste en asignar por fila o columna unidades, teniendo cuidado de que
el valor nunca exceda a la demanda u oferta de los extremos de fila y columna, el
procedimiento concluye cuando, tanto por fila como por columna ya se puede asignar
ninguna unidad más.

Destinos A B C D E Oferta
Orígenes
X 0.8 2.7 1.7 1.4 0.9 60

Y 0.9 0.5 1.0 0.2 1.3 75

0.7 2.1 1.8 1.4 1.1

Z 80

2.3 0.9 1.1 1.8 2.5

T 35

Demanda 75 20 15 25 40 250
175

Como se puede observar, el problema no está balanceado, debido a que la Oferta es

mayor que la Demanda en 75 unidades. Para resolver el problema se aumenta una
columna ficticia para igualar la demanda y la oferta.

124
Investigación de Operaciones M.Sc. Javier Beltrán S.

Destinos A B C D E Ficticia Oferta

Orígenes
X 0.8 2.7 1.7 1.4 0.9 0 60

Y 0.9 0.5 1.0 0.2 1.3 0 75

0.7 2.1 1.8 1.4 1.1 0

Z 80

2.3 0.9 1.1 1.8 2.5 0

T 35

Demanda 75 20 15 25 40 75 250
250

Una vez igualada la oferta con la demanda, se procede a asignar unidades según el
procedimiento descrito anteriormente, así:

Destinos A B C D E Ficticia Oferta

Orígenes
X 0.8 2.7 1.7 1.4 0.9 0 60
60 ---- ---- ---- ---- ----

Y 0.9 0.5 1.0 0.2 1.3 0 75

15 20 15 25 ---- ----
Z
0.7 2.1 1.8 1.4 1.1 0
80
---- ---- ---- ---- 40 40
T 2.3 0.9 1.1 1.8 2.5 0
---- ---- ---- ---- ---- 35 35

Demanda 75 20 15 25 40 75 250
250

En la esquina N.O. se pone la menor de las exigencias min (75, 60) = 60. Se completa
en este caso la primera fila desechando de colocar otra unidad en ésta.

Continuando, saturamos la demanda A, colocando en X 21, 15 unidades completando las

75 requeridas. Como se observa, debemos saturar la oferta Y, colocando
respectivamente en X22 = 20, X23 = 15, X24 = 25, unidades.

En ciertos casos como en X24, al colocar 25 unidades se saturan de manera simultánea,

tanto la oferta como la demanda.

El coste de la SBI será: Z = 60 * 0.8 + 15 * 0.9 + 20 * 0.5 + 15 * 1.0 + 25 * 0.2 + 40 * 1.1

= 135.5

125
Investigación de Operaciones M.Sc. Javier Beltrán S.

Sin embargo, comprobando m + n –1 = Nº A; donde:

m = Número de Filas
n = Número de Columnas
A = Número de Asignaciones

Se tiene que:
4 + 6 –1 ≠ 8

En este caso se ha encontrado una solución SBI, pero que no es básica ni factible, debido
a que no cumple la condición anterior, por lo que la solución es degenerada. En la sección
posterior se explica los métodos para resolver este problema.

 Método de la Fila Mínima

El primer paso, en este método, consiste en ubicar dentro la primera fila, el menor costo
y asignar unidades que correspondan a la menor exigencia tanto en columna como en
fila. En caso de saturar la primera fila, corresponde encontrar el menor valor en la
segunda; caso contrario, si la oferta 1, aún no ha sido satisfecha, se encuentra en la
misma fila, la casilla con menor costo. Se sigue este proceso hasta satisfacer la última
oferta correspondiente.

Continuando con el anterior ejemplo, se tiene:

Destinos A B C D E Ficticia Oferta

Orígenes
X 0.8 2.7 1.7 1.4 0.9 0 60
---- ---- ---- ---- ---- 60

Y 0.9 0.5 1.0 0.2 1.3 0 75

15 20 ---- 25 ---- 15

0.7 2.1 1.8 1.4 1.1 0

Z 80
60 ---- ---- ---- 20 ----

2.3 0.9 1.1 1.8 2.5 0

T ---- ---- 15 ---- 20 ---- 35

Demanda 75 20 15 25 40 75 250
250

El Coste total de la SBI, por el método de Columna mínima será:

Costo SBI = 15 * 0.9 + 20 * 0.5 + 25 * 0.2 + 60 *0.7 + 20 * 1.1 + 15 * 1.1 + 20 * 2.5 = 159

 Método de la Columna Mínima

Al igual que el anterior método, se asigna el valor a la exigencia menor, tanto de la oferta
como de la demanda, pero, en la primera columna, si ésta se satura continúa la segunda,
hasta satisfacer las demandas. En caso de asignar un valor y saturar la demanda

126
Investigación de Operaciones M.Sc. Javier Beltrán S.

correspondiente, se continúa asignando a otra casilla, tomando en cuenta siempre, que

el costo sea el menor. Así, la tabla de transporte por este método tiene la siguiente
estructura de asignación:

Destinos A B C D E Ficticia Oferta

Orígenes
X 0.8 2.7 1.7 1.4 0.9 0 60
---- ---- ---- ---- 40 20

Y 0.9 0.5 1.0 0.2 1.3 0 75

---- 20 15 25 ---- 15

0.7 2.1 1.8 1.4 1.1 0

Z 80
75 ---- ---- ---- ---- 5

2.3 0.9 1.1 1.8 2.5 0

T ---- ---- ---- ---- ---- 35 35

Demanda 75 20 15 25 40 75 250
250

Coste SBI = 40 * 0.9 + 20 * 0.5 + 15 * 1.0 + 25 *0.2 + 75 * 0.7 = 118.5

 Método de Costos Mínimos

En este método, la asignación se la realiza tomando en cuenta todos los costos de la

matriz del problema. Siendo el objetivo enviar recursos con el mínimo de costo, la
asignación se realiza al menor costo de la matriz, tomando en cuenta la menor exigencia
en oferta o demanda; el proceso concluye hasta completar todo el programa de envíos
de la matriz de costes.

Destinos A B C D E Ficticia Oferta

Orígenes
X 0.8 2.7 1.7 1.4 0.9 0 60
60 ---- ---- ---- ---- ----

Y 0.9 0.5 1.0 0.2 1.3 0 75

10 20 15 25 5 ----

0.7 2.1 1.8 1.4 1.1 0

Z 80
5 ---- ---- ---- ---- 75

2.3 0.9 1.1 1.8 2.5 0

T ---- ---- ---- ---- 35 ---- 35

Demanda 75 20 15 25 40 75 250
250

En el Cuadro, se asignó en X36 de manera arbitraria, pudiendo asignar también en las

celdas de la columna ficticia. En este sentido, se completó cada exigencia siendo el costo
mínimo, según este método, el siguiente:

127
Investigación de Operaciones M.Sc. Javier Beltrán S.

Costo SBI = 60 * 0.8 + 10 * 0.9 + 20 * 0.5 + 15 * 1.0 + 25 *0.2 + 5 * 1.3 + 5 * * 0.7 + 35 * 2.5 = 184.5

 Método de Aproximaciones de Vogel (Penalizaciones)

Los pasos por seguir en el método de Penalizaciones son:

Paso 1. Determinar la penalización para cada fila y cada columna al no colocar en la

solución inicial la variable que tenga el menor coste en esta fila o columna. Para la fila i,
esto significa restar el coste más pequeño de esta fila del siguiente coste más pequeño
de la misma fila, en la matriz de costes. Si dos elementos de esta fila son ambos el más
pequeño, la penalización es cero. La penalización de la columna j se calcula de forma
similar.

Paso 2. Cuando se han calculado todas las penalizaciones, localícese la mayor, ya sea
una penalización de fila o columna.

Colocar en la solución la variable que tiene el menor coste, en la fila o columna que tiene
la penalización mayor. La variable se iguala a la exigencia de fila o a la exigencia de
columna que sea más pequeña, de la fila y columna que contienen esta variable. La fila
o columna satisfechas al asignar este valor a la variable se omite en el resto del proceso,
y la exigencia de la otra fila (fila o columna) se disminuye en el valor asignado a la
variable.

Paso 3. Si una fila ha sido satisfecha, volver a calcular las penalizaciones de columna,
sin considerar ahora el cálculo de las penalizaciones de columna los elementos de la
matriz de costes de la fila eliminada. Si se ha satisfecho una columna se deberán volver
a calcular las penalizaciones de las filas.

Paso 4. Repítase ahora las iteraciones de los pasos 2 y 3, hasta que la solución sea
completa.

128
Investigación de Operaciones M.Sc. Javier Beltrán S.

Con el ejemplo anterior, se tiene:

Destinos A B C D E Ficticia Oferta

Orígenes

0.8 2.7 1.7 1.4 0.9 0 0.8 0.8 0.8 0.8 0.8 0.1 0.8 1.7 1.7
X --- --- 10 --- 40 10 60

0.9 0.5 1.0 0.2 1.3 0 0.2 0.2 0.2 0.9 --- --- --- ---- ---
Y --- 20 --- 25 --- 30 75
0.7 2.1 1.8 1.4 1.1 0 0.7 0.7 0.7 0.7 0.7 0.4 0.7 1.8 ---
Z 75 --- 5 --- --- --- 80
2.3 0.9 1.1 1.8 2.5 0 0.9 ---- --- ---- --- --- --- ---- ---
--- --- --- --- --- 35
T 35
Demanda 75 20 15 25 40 75 250

250

0.1 0.4 0.1 1.2 0.2 0

0.1 1.6 0.7 1.2 0.2 0
0.1 --- 0.7 1.2 0.2 0
0.1 --- 0.7 --- 0.2 0
0.1 --- 0.1 --- 0.2 0
0.1 --- 0.1 --- 0.2 ---
--- --- 0.1 --- 0.2 ---
--- --- 0.1 --- --- ---
--- --- 1.7 --- --- ---

El costo total según este método alcanza a:

Costo SBI = 10 * 1.7 + 40 * 0.9 + 20 * 0.5 + 25 * 0.2 + 75 * 0.7 + 5 * 1.8 = 129.5

 Método Russell

El método de Edward J. Russell (1968), presenta un procedimiento que proporciona una

solución inicial cercana a la óptima, siendo sus pasos los siguientes:

Paso 1. Se colocan los costos mayores, tanto por fila como por columna, determinado de
esta forma los valores ui y vj.

Paso 2. Con los valores encontrados se ubican en las diferentes casillas, los resultados
de:

MAX Cij − (u i + v j )

Paso 3. En la casilla que contenga el mayor valor encontrado anteriormente, se asigna la

menor exigencia tanto por fila como columna, saturando la misma.

Paso 4. Se repite este procedimiento hasta encontrar una asignación completa.

129
Investigación de Operaciones M.Sc. Javier Beltrán S.

Ejemplo:

A B C D E Ficticia Oferta vj
Destinos

Orígenes

0.84.2 4.2 2.72.7 2.7 1.7 1.43.1 3.1 0.9 4.3 0 2.7 2.7 2.7 2.7 --- --- --- --- --- --- ---
X 2.82.8 ---
60
20 ---- ---- 40 ----
----
0.9 2.7 0.5 3.5 1.0 2.1 0.2 2.9 1.3 2.5 0 1.3 1.0 1.3 1.0 1.0 1.0 1.0 1.0 1.0 0
Y 2.4 3.2 1.8 2.6 1.0 1.0 75 ---
2.4 2.6 2.6 1.8 1.8 2.6 2.6 1.0
1.8 2.6 ---- 1.0 0
--- ---- 1.8 35
Z - 15 25 80

0.7 3.7 2.1 2.7 1.8 2.1 1.4 2.5 1.1 3.5 0 2.1 2.1 2.1 2.1 2.1 2.1 2.1 1.8 1.8 0
3.7 2.7 2.1 2.5 2.1 2.1 0
T 3.7 2.1 2.1 2.1 2.1 2.5 2.5 1.8 35
1.8 2.2 ---- 1.8 0
55 ---- 1.8 25
---- ----
2.3 2.5 0.9 4.3 1.1 3.2 1.8 2.5 2.5 2.5 0 2.5 2.3 2.5 2.3 2.3 1.8 1.8 1.1 0 0
2.3 4.1 3.0 2.3 2.3 1.8 0
2.3 3.5 3.0 3.0 2.5 2.3 1.8 1.8
2.5 1.8 ---- 1.1 0
--- 20 1.8 15
- ---- ----
Demanda 75 20 15 25 40 75
250
Relación: Máx [Cij –
250 (ui+vj)]

ui 2.3 2.7 1.8 1.8 2.5 0

2.3 2.7 1.8 1.8 ---- 0
2.3 2.1 1.8 1.8 ---- 0
---- 2.1 1.8 1.8 ---- 0
---- ---- 1.8 1.8 ---- 0
---- ---- 1.8 ---- ---- 0
---- ---- ---- ---- ---- 0
---- ---- ---- ---- ---- 0
---- ---- ---- ---- ---- 0

La Relación para encontrar la mejor asignación se calcula a modo de ejemplo, de la

siguiente manera:

Para X11, será: Relación: Máx. [0.8 - (2.3 + 2.7)] = 4.2

Para X15, será: Relación: Máx. [0.9 - (2.5 + 2.7)] = 4.3, que fue el máximo valor, y al cual
se asignó en primera instancia una cantidad que saturó la exigencia menor.

El Costo de la SBI es: 20 * 0.8 + 40 * 0.9 + 15 * 1.0 + 25 *0.2 + 55 * 0.7 + 20 * 0.9 = 128.5

130
Investigación de Operaciones M.Sc. Javier Beltrán S.

COMPARACIÓN DE LOS RESULTADOS DE LA SBI POR LOS SEIS MÉTODOS

Método Costo de la SBI
Esquina N.O. 135.5
Fila Mínima 159.0
Columna Mínima 118.5
Costos Mínimos 184.5
Aproximaciones de Vogel 129.5
Russell 128.5

De manera general los dos últimos métodos se consideran los que más se aproximan a
la solución óptima del esquema de transporte. Sin embargo, los otros métodos, como se
observa en el Cuadro, dan mejores resultados, en el sentido de que definen una
programación más eficaz y eficiente, en el sentido de minimizar los costos y cumplir los
objetivos; como por ejemplo el tercer método, el cual estaría más cerca del programa
óptimo de transporte.

4.3.2. PRUEBA DE OPTIMALIDAD

El objetivo de este paso es verificar, si una solución básica inicial obtenida es óptima o
no. Empezando con alguna solución posible (por algún método estudiado anteriormente),
se debe calcular la matriz (Zij = ui + vj) y luego la matriz (Cij – Zij) Si todos los Cij – Zij son
mayores o iguales a cero, la solución es óptima. Si uno o más Cij – Zij es menor que cero,
es posible una solución mejor.

El proceso iterativo, en esta fase, se denomina Distribución Modificada (MODI),

obviamente se da en caso de no haber encontrado la solución óptima en el paso anterior,
consiste en encontrar de las variables que tienen un coste de entrada (reducido) negativo,
se determina la que lo tenga más pequeño (más negativo). Pasando a la matriz solución
se traza la trayectoria  que debe empezar del valor negativo y debe seguir con los ceros
existentes una trayectoria cerrada, formando un circuito con ángulos de 90°.

Con los valores encontrados, afectados con los signos del programa, se efectúa
operaciones de suma y resta del menor valor de las asignaciones que fueron afectadas
en el circuito y, que tengan el signo negativo asignado.

Con el nuevo programa de envíos, se define si éste es el óptimo, calculando la matriz Cij
– Zij.

Ejemplo: Se tiene el siguiente problema de transporte y se requiere:

 Determinar la solución inicial por el método de la esquina del N.O.

 Determinar el esquema de transporte de menor costo

131
Investigación de Operaciones M.Sc. Javier Beltrán S.

Destinos Destinos Existencias

Almacén 1 Almacén 2
en Planta
Orígenes
P1 20 10 10
P2 5 8 20
P3 6 19 22
Exigencias de cada 25 27
Almacén

Solución: Como se observa, tanto la demanda como la oferta están en equilibrio por lo
que se cumple que: ∑ Oferta = ∑ Demanda. Entonces se procede a resolver por la
esquina N.O.; empezando la asignación por la celda X11 saturando la exigencia menor,
así:
20 10 10
10
5 8 20
15 5
6 19 22
22
25 27 52

Ésta SBI, la cual tiene un costo de $733. Se procederá a determinar si esta solución es
la óptima, para lo cual, se forma los números ui + vj, colocando un cero en la parte
superior, hasta completar el valor de todas las casillas que fueron asignadas.
vj 0 3
ui u
20 20 10 10
10
5 5 8 20
15 5
16 6 19 22
22
25 27 52

Como se observa, los números ui + vj, se forman sumando o restando, de manera que al
determinar la matriz Cij - Zij = 0 (Variables básicas), el valor sea cero. Por ejemplo, los
números u1 y vj se forman, colocando el valor de 20 para que sumado con cero, se pueda
obtener cero, al restar con el costo unitario. Así, en todas las casillas con asignación el
valor de Cij - Zij, debe ser cero, tal como se cumple en la matriz. En este sentido, en la
misma matriz se observa que faltan casillas por determinar el valor, tanto en X 12 como en
X31; el cálculo se da por Cij - Zij ≥ 0 (Variables no básicas) que se muestra a continuación:
Matriz Cij - Zij
vj 0 3
ui u
20 20 10 10
10 -13
5 5 8 20
15 5
16 6 19 22
-10 22
25 27 52

El cálculo en ambos casos fue resultado de:

132
Investigación de Operaciones M.Sc. Javier Beltrán S.

Zij = (ui + vj) = Z12 = (20 + 3) = 23

Cij – Zij = C12 - Z12 = 10 – 23 = -13

Para X31:

Zij = (ui + vj) = Z31 = (16 + 0) = 16

Cij – Zij = C31 – Z31 = 6 – 16 = -10

El óptimo en un programa de Transporte se da cuando C ij - Zij es > 0, al tener valores

negativos, es posible que exista un mejor programa de envíos. Para lo cual se procede
de la siguiente manera:
vj 0 3
ui u

20 20 10 10
- → 10 +  -13
5 5 8 20
+  15 -  5
16 6 19 22
-10 22
25 27 52

Como se observa, en la matriz no se cumple con Cij - Zij > 0; de esta manera se procede
a encontrar un mejor programa de envíos, basándose en un nuevo circuito cerrado, el
cual comienza en el valor más negativo (-13), y recorre tomando en cuenta las
asignaciones realizadas y con signos de + y – alternativamente.

De esta forma, una vez encontrado un circuito cerrado, de los valores afectados, se toma
en cuenta, sólo las cantidades que tengan signo negativo, tomando de esos valores, el
menor, de manera que no se lleguen a obtener valores negativos. Considerando lo
anterior, se escoge el mínimo entre: (5, 10); siendo el valor el 5, el cual habrá que sumar
y restar respectivamente en cada casilla afectada, así se tiene:

X12 = 0 + 5 = 5
X22 = 5 – 5 = 0
X21 = 15 + 5 = 20
X11 = 10 – 5 = 5

Según lo anterior, con los valores encontrados se renueva la matriz, los cuales, en ningún
caso, deben sobrepasar la exigencia tanto en Demanda como en Oferta. Tomando en
cuenta lo anterior la nueva asignación de la matriz es:

133
Investigación de Operaciones M.Sc. Javier Beltrán S.

vj Almacén 1 Almacén 2
ui u

P1 20 10 10
5 5
P2 5 8 20
20
P3 6 19 22
22
25 27 52

Como se observa, no se excede de ningún modo la exigencia por fila y columna. El costo
de envíos de la matriz es de $668. En la celda X22, no se asigna ningún valor por ser cero,
y para no afectar la condición m + n – 1 = a. Lo que corresponde es verificar si este nuevo
programa es el óptimo, para lo cual encontramos los valores u i y vj.

vj 0 -10
ui u

20 20 10 10
5 5
5 5 8 20
20 13
29 6 19 22
-23 22
25 27 52

De los valores encontrados, existe un número menor que cero, por tanto no es el óptimo,
y se procede a realizar un nuevo circuito de manera similar al anterior.
vj 0 -10
ui u

20 20 10 10
- → 5 + → 5
5 5 8 20
20 13
29 6 19 22
+  -23 -  22
25 27 52

Siendo las nuevas asignaciones, la resultante de:

X31 = 0 + 5 = 5
X11 = 5 – 5 = 0
X12 = 5 + 5 = 10
X32 = 22 – 5 = 17

Encontrando la nueva matriz Cij – Zij; se obtiene un número negativo, por lo que el nuevo
circuito es:

134
Investigación de Operaciones M.Sc. Javier Beltrán S.

vj 0 13
ui u

-3 20 10 10
23 10
5 5 8 20
- → 20 +  -10
6 6 19 22
+  5 -  17
25 27 52

X22 = 0 + 17 = 17
X32 = 17 – 17 = 0
X31 = 5 +17 = 22
X21 = 20 – 17 = 3
Obteniéndose:
vj 0 3
ui u

7 20 10 10
17 10
5 5 8 20
3 17
6 6 19 22
22 10
25 27 52

Como se observa, en la Matriz todos los valores C ij – Zij; son positivos, por lo que el
problema ha concluido, encontrándose el óptimo. El costo total mínimo del presente
problema es:

Planta Almacén Cantidad Costo Unit Costo Total

1 2 10 10 100
2 1 3 5 15
2 2 17 8 136
3 1 22 6 132
Total Costo de Transporte 383

El proceso anterior se muestra a continuación utilizando el Programa TORA, que validan

los resultados hallados:

135
Investigación de Operaciones M.Sc. Javier Beltrán S.

FIGURA N.º 41
TABLA INICIAL Y ÓPTIMA OBTENIDA A TRAVÉS DE TORA

4.4. DEGENERACIÓN

Anteriormente se indicó que un problema de transporte debe contar al menos con m + n

– 1 asignaciones distintas de cero, representando m el número de filas (orígenes) y n el
número de columnas (destinos). En caso de que no se cumpliera la relación anterior se
dice que el problema es degenerado y, por tanto, el cálculo de los valores u i y vj no se
puede realizar.

Ejemplo: Resuelva el siguiente problema de transporte

2 6 5 1 12

1 4 2 2 18

3 5 2 3 15

15 15 8 7 45

Aplicando el método de fila mínima se obtiene la siguiente solución inicial:

136
Investigación de Operaciones M.Sc. Javier Beltrán S.

2 6 5 1 12
5 7
1 4 2 2 18
10 8
3 5 2 3 15
15
15 15 8 7 45

Puede observarse que las asignaciones son cinco, necesitándose m + n – 1,

asignaciones, esto es: 3 + 4 – 1 = 6. Este aspecto trae consigo una consecuencia
importante. Así formamos la matriz para el cálculo de los valores marginales u i y vj:

0 1 -1
2 6 5 1 12
2 5 7
1 4 2 2 18
1 10 8
3 5 2 3 15
15
15 15 8 7 45

Como se puede observar, no es posible el cálculo de los valores citados de la fila 1 y la

columna 2, a no ser que se fije otro valor arbitrario, lo cual no es conveniente.

Para resolver este problema estudiaremos dos métodos, que permitan asignar un costo
más en la tabla.

4.4.1. MÉTODO ÉPSILON 

Este método consiste en agregar a las disponibilidades de cada origen una cantidad
indeterminada  , la misma que, al determinar el costo se iguala a cero. Al agregar a
cada fila la cantidad  se alteran en la última columna m veces  , siendo m el número
de filas. Continuando con el anterior ejemplo se tiene:

0 1 -1
2 6 5 1 12 + 
2 5 7
1 4 2 2 18 + 
1 10 8
3 5 2 3 15 + 
15
15 15 8 7 + 3 45 + 3 

Se agregaron a cada origen un  y a la última columna el total de filas existentes, de

manera que el total de la oferta sea igual al de la demanda. Ahora se procede a la
asignación de manera similar:

137
Investigación de Operaciones M.Sc. Javier Beltrán S.

2 6 5 1 12 + 
5-2  7+3 
1 4 2 2 18 + 
10+2  8- 
3 5 2 3 15 + 
15 
15 15 8 7 + 3 45 + 3 

El costo de esta asignación inicial alcanza a: 118

Puede observarse que ahora existen 6 asignaciones, las necesarias, para el cálculo de
los costos marginales, procediendo a su cálculo

0 4 1 -1
2 6 5 1 12 + 
2 5-2  7+3 
1 4 2 2 18 + 
1 10+2  -1 8- 
3 5 2 3 15 + 
1
15 
15 15 8 7 + 3 45 + 3 

Del Cuadro anterior, se deduce que existe una mejor asignación, debido a la presencia
de un valor marginal negativo; por lo tanto, el circuito será:

0 4 1 -1
2 6 5 1 12 + 
2 5-2  7+3 
1 4 2 2 18 + 
1 10+2  + → -1 -  8- 
1
3 5 2 3 15 + 
-  15 +  
15 15 8 7 + 3 45 + 3 

Siendo las ecuaciones:

0 + (8 -  ) = 8 – 3
8 -  - (8 -  ) = 0
 + (8 -  ) = 8
15 - (8 -  ) = 7 + 

Siendo la nueva matriz Cij – Zij, la siguiente:

138
Investigación de Operaciones M.Sc. Javier Beltrán S.

0 3 0 -1
2 6 5 1 12 + 
2 5-2  7+3 
1 4 2 2 18 + 
1 10+2  8- 
2
3 5 2 3 15 + 
7+  8
15 15 8 7 + 3 45 + 3 

En el cálculo de los valores marginales, son todos positivos por lo que ha llegado a un
programa óptimo de envíos; siendo el costo total mínimo:

CT = (5 * 2) + (7 * 1) + (10 * 1) + (8 * 4) + (7 * 5) + (8 * 2) = 110

4.4.2. MÉTODO DEL CERO ARTIFICIAL

La aplicación de este método supone dos aspectos muy importantes, que son:

 Una vez establecida la degeneración en un determinado problema de transporte, se

debe asignar un cero en la casilla cuyo costo sea el menor de todas aquellas que aún no
tienen asignación, teniendo cuidado al mismo tiempo que no sea el único de su fila y
columna, y

 Dicha asignación, se debe realizar evitando anillos o circuitos cerrados con

asignaciones realizadas en programa original de envíos.

Ejemplo: Tomando el ejemplo anterior se tiene:

2 6 5 1 12
5 7
1 4 2 2 18
10 8
3 5 2 3 15
15
15 15 8 7 45

La matriz obtenida corresponde a la SBI a través del método de la fila mínima, la cual
resulta degenerada por no cumplir la condición m + n – 1 = a. En este sentido, tomando
en cuenta los aspectos citados para la aplicación del método del cero artificial, se tiene:

2 6 5 1 12
5 7
1 4 2 2 18
10 8
3 5 2 3 15
15 0
15 15 8 7 45

139
Investigación de Operaciones M.Sc. Javier Beltrán S.

Se asigna a una celda cuyo costo unitario sea el menor y el cual no forme ningún circuito
con otras asignaciones. Como se observa, en la matriz se asignó en X 33 el costo que
elimina la degeneración. El procedimiento posterior es similar al realizado a través del
método épsilon.

Cabe hacer notar que, en X24 también se pudo asignar, por tener el mismo costo unitario
(2); pero se incumplía con el segundo aspecto citado; es decir, el hecho de no asignar
creando circuitos cerrados con las asignaciones realizadas.

De haber asignado en dicha casilla se producía lo siguiente:

0 1 -1
2 6 5 1 12
2 5 7
1 4 2 2 18
1 10 8 0
3 5 2 3 15
15
15 15 8 7 45
La imposibilidad de realizar los cálculos correctos para X24, lo cual no permite completar
todos los valores marginales y poder definir la optimalidad o no, del programa actual de
envíos.

4.5. CASO DE MAXIMIZACIÓN

En muchas ocasiones, en un problema de transporte, los datos obtenidos no se refieren

a los costos unitarios, sino a las ganancias unitarias que una determinada empresa podría
obtener, en el traslado o la distribución de un determinado origen a un determinado
destino.

Cuando se da el caso anterior, existen dos formas de resolver el problema: 1) Multiplicar

a la matriz de ganancias unitarias por –1 y trabajar como cualquier problema de transporte
en minimización o 2) Restar de la matriz original de ganancias, el mayor valor a los
demás, y trabajar de la manera conocida.

Ejemplo: Resolver el siguiente problema de transporte, obteniendo el esquema óptimo

de envío y la ganancia máxima asociada:
10 2 1 100

3 4 5 200

6 7 8 300

200 150 250 600

Utilizando el segundo método de restar el mayor valor (10) a los demás se obtiene.

140
Investigación de Operaciones M.Sc. Javier Beltrán S.

0 8 9 100

7 6 5 200

4 3 2 300

200 150 250 600

Utilizando el método de la fila mínima se obtiene

0 -1 -2
0 8 9 100
0 100 9 11
7 6 5 200
7 0 0 200
4 3 2 300
4 100 150 50
200 150 250 600

Como se observa, los valores marginales son mayores o iguales a cero, por lo que se ha
obtenido el programa óptimo de envíos con una ganancia máxima de:

Gan. Máx. = (100 * 10) + (200 * 5) + (100 * 6) + (150 * 7) + (50 * 8) = $4050

Validando los resultados con POM para WINDOWS, se tiene:

FIGURA N.º 42
SALIDA DE DATOS COMPLETO DEL PROBLEMA DE TRANSPORTE
CASO MÁXIMO

141
Investigación de Operaciones M.Sc. Javier Beltrán S.

4.6. USO DE EXCEL SOLVER

Al igual que en el Simplex, la utilización de Solver es muy importante para problemas en

donde los orígenes y destinos son muchos y se hace complicada su realización.

A continuación, mostramos el procedimiento para la solución de problemas de

Transporte, utilizando Excel Solver.

Ejemplo: Resolver el siguiente problema de Transporte para una Empresa Enlatadora de

Productos en Mermelada, cuyos costos de transporte, además de la demanda y oferta
correspondiente se dan a continuación:

ALMACENES
ENLATADORAS 1 2 3 4 PRODUCCIÓN
1 464 513 654 867 75
2 352 416 690 791 125
3 995 682 388 685 100
DEMANDA 80 65 70 85

En una hoja Excel tendrá las siguientes características:

El siguiente paso consiste en colocar la matriz, con la implicación de fórmulas de Excel

Solver, necesarias para su resolución. Por ejemplo, la función “SUMA”, que indicará que
el total de la asignación en la fila no debe exceder a lo establecido en el suministro.

142
Investigación de Operaciones M.Sc. Javier Beltrán S.

Lo mismo para las demandas:

Y para delimitar la función objetivo, será la fórmula “SUMAPRODUCTO”, que a

continuación se muestra su formulación en Excel:

143
Investigación de Operaciones M.Sc. Javier Beltrán S.

Una vez realizadas todas las fórmulas básicas para resolver a través del Solver, se
procede a delimitar los parámetros de éste, haciendo clic en el menú en el icono
herramientas y, luego de la lista desplegada en Solver, la cual mostrará la siguiente
ventana:

En dicha ventana, se puede apreciar que la celda de la función objetivo ya está delimitada
por $H$18. Luego se procede a definir si estamos en un caso de maximización o de
minimización, haciendo clic en el botón que corresponda. En nuestro caso el “Mínimo”.
El siguiente paso consiste en mostrar el parámetro de los costos mínimos en la venta de
“cambiando las celdas”, de la siguiente manera:

De esta manera se delimita las asignaciones a los parámetros designados en la celda

de la venta anterior.

Luego se describen las restricciones haciendo clic en “agregar”, colocando en el Cuadro

correspondiente las restricciones del problema:

144
Investigación de Operaciones M.Sc. Javier Beltrán S.

Una vez concluido ese paso se está en condiciones de resolver el problema con Solver,
para lo cual se aprieta el botón de opciones de Solver, y se asume un modelo lineal y
valores no negativos, y luego, aceptar, en la siguiente ventana de Excel Solver:

Ahora se procede a resolver el problema, siendo el resultado el siguiente:

De esta manera, el costo total mínimo de transporte de las tres enlatadoras a los cuatro
almacenes es de $152535.

4.7. EL PROBLEMA DE TRANSBORDO

Un problema de transporte solamente permite envíos que van directamente desde un

punto de oferta hacia un punto de demanda. En muchas situaciones, se permiten envíos
entre puntos de oferta o entre puntos de demanda. Algunas veces, también puede haber
puntos (llamados puntos de Transbordo), a través de los cuales se pueden transbordar
bienes en su viaje, desde un punto de oferta hacia un punto de demanda. Problemas de
envío, con alguna o todas estas características son problemas de transbordo, los cuales,
afortunadamente, se pueden obtener una solución óptima al resolver un problema de
transporte, adecuadamente construido.

De aquí en adelante, se define un punto de oferta como un punto que puede enviar bienes
hacia otro punto, pero no puede recibir bienes de cualquier otro punto. De manera similar,
un punto de demanda es un punto que puede recibir bienes de otros puntos, pero no
puede enviar bienes hacia ningún otro punto. Un punto de Transbordo es un punto que
puede, tanto recibir bienes de otros puntos como enviar bienes hacia otros puntos.

145
Investigación de Operaciones M.Sc. Javier Beltrán S.

El siguiente ejemplo muestra todas las características de un problema general de

transbordo. (“-“, indica que un envío no es posible).

Ejemplo: La Cía. Toyota produce dispositivos mecánicos en dos fábricas. La Primera

fábrica puede producir diariamente hasta 150 dispositivos, y en la segunda fábrica se
producen diariamente hasta 200. Los dispositivos se envían por avión a los almacenes
distribuidores 1 y 2. Los clientes en ambas ciudades, donde se encuentran los almacenes
distribuidores, requieren diariamente 130 dispositivos. Debido a falta de reglamentación
de las tarifas aéreas, Toyota cree que podría abaratar los costos, mandando los
dispositivos, primero a dos sub – almacenes en ciudades intermedias y después
mandarlos a sus destinos finales. Los distintos costos para mandar un dispositivo por
avión se muestran en la siguiente tabla. Toyota pretende minimizar el costo total de enviar
los dispositivos requeridos hacia sus clientes.

Costos de envío para el Ejemplo de la Toyota Cía.

HACIA Sub – Almacén 1 Sub – Almacén 2 Almacén 1 Almacén 2
DESDE
Fábrica 1 8 13 25 28
Fábrica 2 15 12 26 25
Sub – Almacén 1 0 6 16 17
Sub – Almacén 2 6 0 14 16

Solución:

Esquemáticamente el problema tiene la siguiente estructura:

FIGURA N.º 43
ESQUEMA GENERAL DEL PROBLEMA DE TRANSBORDO

En la Figura se observa que, tanto la fábrica 1 y 2 son puntos de oferta, con ofertas de
150 y 200 dispositivos al día, respectivamente. Los sub – almacenes son puntos de
transbordo. Los almacenes son puntos de demanda, cada uno con una demanda de 130
dispositivos al día.

146
Investigación de Operaciones M.Sc. Javier Beltrán S.

A continuación, se describe cómo se puede encontrar la solución óptima para un

problema de transbordo, al resolver un problema de transporte. Dado un problema de
transbordo, se genera un problema de transporte mediante el siguiente procedimiento:

Paso 1: si es necesario, se añade un punto de demanda ficticia (con una oferta de cero
y una demanda igual a la oferta en exceso del problema planteado o viceversa) para
balancear el problema. Los envíos hacia el punto ficticio y desde un punto hacia sí mismo,
tendrán naturalmente un costo de envío igual a cero.

Paso 2: construya un cuadro de transporte de la manera siguiente: Se necesita una fila

por cada punto de oferta y por cada punto de transbordo. Asimismo, se necesitará una
columna por cada punto de demanda y por cada punto de transbordo.

Cada punto de oferta pura tendrá una oferta igual a su oferta original, y cada punto de
demanda pura, tendrá una demanda igual a su demanda original. En ese sentido, cada
punto de transbordo tendrá una oferta igual a la oferta original del punto más la oferta
total. La demanda en cada punto será igual a la demanda original más la oferta total. Este
procedimiento, asegura que cualquier punto de transbordo que es un abastecedor neto,
tendrá una salida neta igual a la oferta original del punto, y que cualquier punto de
transbordo, que es a la vez un recibidor neto, tendrá una entrada neta igual a la demanda
original del punto. Aunque no se sabe cuánto se enviará a través de cada punto de
transbordo, se puede estar seguro de que la cantidad total enviada, a través del punto,
no será mayor que la oferta total disponible. Esto explica por qué se suma la oferta total
disponible a la oferta y a la demanda en cada punto de transbordo. Al sumar las mismas
cantidades a la oferta y a la demanda, en cada punto de transbordo, se asegura que la
salida neta de cada punto de transbordo será correcta, y también se mantiene un cuadro
de transporte balanceado.

Cumpliendo lo anterior el Cuadro de Transbordo (transporte) tiene las siguientes

características:
SubAlm1 SubAlm2 Almac. 1 Almac. 2 Almac.Fict. Oferta

Fábrica 1 8 13 25 28 0 150
Fábrica 2 15 12 26 25 0 200
SubAlm1 0 6 16 17 0 350
SubAlm2 6 0 14 16 0 350
Demanda 350 350 130 130 90 1050

Para la resolución del problema, se procede de manera similar a la de transporte; es

decir, se comienza con un programa inicial de envíos a través de los distintos métodos
estudiados, y luego se procede a comprobar su optimalidad.

Utilizando Excel Solver, se obtendrá la distribución óptima al problema de transbordo,

para la Toyota Cía., la cual se muestra a continuación junto con el esquema óptimo de
transbordo.

147
Investigación de Operaciones M.Sc. Javier Beltrán S.

Problema de Transbordo: Toyota Cía.

Sub-Almacén 1 Sub-Almacén 2 Almacén 1 Almacén 2 Alm. Fict. 3 Oferta
Fábrica 1 8 13 25 28 0 150
Fábrica 2 15 12 26 25 0 200
Sub-Almacén 1 0 6 16 17 0 350
Sub-Almacén 2 6 0 14 16 0 350
Demanda 350 350 130 130 90 1050

Sub-Almacén 1 Sub-Almacén 2 Almacén 1 Almacén 2 Alm. Fict. 3 Total Restricción Oferta

Fábrica 1 150 0 0 0 0 150 = 150
Fábrica 2 0 0 0 110 90 200 = 200
Sub-Almacén 1 200 0 130 20 0 350 = 350
Sub-Almacén 2 0 350 0 0 0 350 = 350
Total 350 350 130 130 90 6370
Restricción = = = = =
Demanda 350 350 130 130 90

En forma esquemática la distribución óptima tiene la siguiente característica:

FIGURA N.º 44
RED ÓPTIMA DE TRANSBORDO

De esta manera, el costo total mínimo es:

CTM = 150 * 8 + 110 * 25 + 130 * 16 + 20 * 17 = 6370

148