1

Modulo 3 Herramientas Matemáticas 4

4. Modelo de Transporte
4.1 Definición del modelo de transporte
Un problema de transporte surge en la planeación de distribución de productos desde
varios sitios de oferta (llamados “fuentes” u “orígenes”) hacia varios sitios de demanda
(llamados “destinos”).

Conociendo las cantidades ofrecidas por cada fuente y la cantidad demandada por cada
destino, el objetivo de un problema de transporte es determinar un plan de transporte que
minimice el costo de envío de la mercadería desde cada origen hasta cada destino.

Para que el problema de transporte tenga solución es condición necesaria y suficiente

que la oferta total sea igual a la demanda total

a) Notación y características del modelo

1) El problema se representa en forma de red.

2) Hay “m” orígenes y “n” destinos.
3) Cada origen y cada destino se representan con un nodo.
4) Las rutas que unen los orígenes con los destinos se representan con arcos.
El flujo de la red va desde los orígenes hasta los destinos, y su dirección se indica mediante
flechas.

el costo de transporte por unidad: 𝑐𝑖𝑗

5) El arco (i, j) que une el origen i con el destino j proporciona dos informaciones:

la cantidad transportada: 𝑥𝑖𝑗

▪

ai
▪

𝑏𝑗
6) La cantidad de la oferta en el origen i es y la cantidad de la demanda en el destino j es

7) Un destino puede cubrir su demanda desde una o más fuentes.

8) Una fuente puede enviar la mercadería que ofrece a uno o más destinos.
9) El objetivo del modelo es determinar un plan de transporte de la mercadería desde las
fuentes hasta los destinos, de modo tal que minimice el costo total, al mismo tiempo que se
satisfacen las restricciones de la oferta y la demanda.
10) Un supuesto importante en este modelo es que el costo es directamente proporcional a la
cantidad de unidades transportadas.

𝑐𝑖𝑗
11) Los datos del modelo son:

𝑎𝑖


𝑏𝑗


12) Las incógnitas del modelo son: 𝑥𝑖𝑗



13) El modelo de transporte se utiliza en otras áreas como por ejemplo el control de inventarios
y la asignación de personal, entre otras.
 2

b) Representación del modelo de transporte

El modelo se representa en forma de red, con nodos y arcos, de la siguiente manera:
Representación genérica de un modelo de transporte con nodos y arcos

Apliquemos esta representación a un problema concreto.

PROBLEMA:
La Central es una empresa que fabrica y comercializa productos de limpieza. Tiene tres
fábricas en la provincia de Córdoba: una en la zona norte, otra en la zona sur y la tercera en la
zona este.
La Central abastece, en estos momentos, a dos supermercados: A y B.
La capacidad de producción de una determinada línea y tipo de producto, para el próximo
trimestre, son: 3000, 4000 y 3500 unidades, respectivamente, según zonas N, S y E.
Las demandas para el próximo trimestre de los supermercados A y B son, respectivamente,
4000 y 6500 productos.
La Tabla 1 muestra los costos de envío por cada producto, desde cada fábrica hasta cada
supermercado.

Tabla 1: Costos de envío por artículo, problema La Central

A B
Norte 15 25
Sur 30 20
Este 18 40
Fuente: elaboración propia.

La empresa desea confeccionar un plan de envíos de modo tal que el costo total sea el
mínimo.

Representación del problema

En esta lectura solo queremos abordar la representación gráfica del problema mediante una
red y su planteo como modelo de programación lineal. La resolución de este se abordará en
lecturas posteriores.
 3

El planteo en forma de red es el siguiente:

Figura 2: Representación del problema de La Central mediante nodos y arcos

Observa que los costos unitarios por ruta están sobre cada flecha. A la izquierda de cada nodo
origen, se muestran las cantidades ofrecidas por ese centro; y a la derecha de cada nodo
destino, las cantidades demandadas por cada supermercado.

4.2 Planteo del problema mediante PL

a) Variables de decisión

La empresa tiene que realizar un plan de envíos desde los orígenes hasta los destinos al
mínimo costo.
Las variables que influyen directamente en los costos y que proporcionan dicho plan
son las “xij”, que unen cada origen i con cada destino j, siendo la variable x la cantidad
de unidades de mercadería que se deben enviar en esa ruta. Las unidades de mercadería
pueden darse en cajas, en bolsas, o bien, como en este caso, en unidades del producto.
Y son las siguientes:
x₁₁ ; x₁₂ ; x₂₁ ; x₂₂ ; x₃₁ ; x₃₂
Por lo que se trata, entonces, de calcular cuántas unidades del producto deben enviarse de la
sucursal Norte al supermercado A (ruta 1-1), cuántas de la sucursal Norte al supermercado B
(ruta 1-2), cuántas de la sucursal Sur al supermercado A (ruta 2-1)… y así hasta completar
todos las posibles rutas: cada origen a todos los destinos; en este caso, por cada origen hay
dos destinos.
Como observarás, en este problema hay tres orígenes que deben satisfacer la demanda de
dos destinos, por lo que la cantidad de variables básicas es: 3 x 2 = 6.

En general, si tenemos “m” orígenes y “n” destinos, tenemos “m.n” rutas posibles y, por lo
tanto, “m.n” variables de decisión.
 4

b) Función objetivo
El objetivo del problema es hacer mínimo el costo total de transporte.
El costo de transporte en una ruta es el valor que surge de multiplicar el costo unitario
de transporte(“cij”) por la cantidad transportada en esa ruta (“xij”).

Por lo tanto:
En la ruta 1-1: Costo= c₁₁. x₁₁ = 15. x₁₁, ya que el costo unitario en esta ruta es dato. Y así con
las demás rutas, teniendo en cuenta los valores de los costos por producto de la Tabla 1 y
sumando luego todos los costos de cada ruta, llegamos a nuestra función objetivo a minimizar:

Para nuestro problema, la función objetivo es:

Minimizar:
z= c₁₁.x₁₁+c₁₂.x₁₂+c₂₁.x₂₁+c₂₂.x₂₂+c₃₁.x₃₁+c₃₂.x₃₂
es decir:
z= 15x₁₁+25x₁₂+30x₂₁+20x₂₂+18x₃₁+40x₃₂

c) Restricciones:
Sabemos que la minimización del costo total está sujeta a las cantidades ofrecidas en cada
fuente y a las cantidades demandas por cada destino.
Por lo tanto, tenemos tres conjuntos de restricciones:
1. Un conjunto de restricciones tiene que ver con la oferta: cada origen no debe
enviar más de lo que dispone. Por lo tanto:

La suma de los envíos desde un origen o fuente -es lógico- que no deba exceder su
oferta.

, para i=1, ……, m

Por lo tanto, en este conjunto hay “m” restricciones.

Para nuestro problema, son tres restricciones:

x₁₁+x₁₂<=3000 x₂₁+x₂₂<=4000 x₃₁+x₃₂<=3500

2. El segundo conjunto de restricciones tiene que ver con los puntos de demanda:
cada punto de demanda debe ser satisfecho. Por lo tanto:

La suma de los envíos de las distintas fuentes a un destino debe satisfacer la demanda
de ese destino.

, para j=1, ……, n

Las “n” restricciones de este conjunto referidas al problema de La Central, se transforman

en dos restricciones, que son:

x₁₁+x₂₁+x₃₁ >=4000
 5

x₁₂+x₂₂+x₃₂>=6500

3. El tercer conjunto de restricciones son las restricciones de no negatividad, ya que

no puede existir una cantidad de productos negativos. Esto lo expresamos de la siguiente
manera:
xij >=0 para i=1, …, m y j=1, …, n

En nuestro problema, significa que las seis variables de decisión no pueden ser negativas:
x₁₁, x₂₁, x₃₁, x₁₂, x₂₂, x₃₂ >=0

Observa que, en total, sin tener en cuenta las restricciones de no negatividad, un

problema de transporte tiene “m+n” restricciones.
Pero ¡¡CUIDADO!! El número de restricciones suficientes para poder resolver un problema
mediante el algoritmo de transporte es de “m+n-1”, como veremos en la segunda lectura.

4.3 El algoritmo de transporte parte I

1) Forma estándar del problema de transporte

a) Problemas balanceados y desbalanceados. Orígenes y destinos ficticios

Resolver un modelo de transporte mediante el método simplex los cálculos pueden reducirse
mediante un algoritmo simplificado del método simplex, que es el algoritmo de transporte.

El algoritmo de transporte se basa, al igual que el simplex, en restricciones que en realidad

siempre son ecuaciones:
 Al definir el problema de transporte, estudiamos que las restricciones pueden ser
desigualdades o igualdades.
 Para aplicar el algoritmo de transporte las desigualdades se transforman en igualdades.

En el algoritmo de transporte, todos estos cálculos se simplifican “balanceando” el problema.

Un problema de transporte está balanceado: Cuando la suma de las cantidades que ofrecen
los puntos de oferta son iguales a la suma de las cantidades demandadas por los destinos.

Este es el caso del problema que se planteó en la lectura anterior, en el cual la suma de las
ofertas es: 3000 + 4000 + 3500 = 10500 y la suma de las demandas: 4000 + 6500 = 10500.
Pero, en la práctica, no es necesariamente cierto que la oferta sea igual a la demanda.

Si la suma de los puntos de oferta es distinta a la suma de los puntos de demanda debemos
balancear el modelo de transporte.

¿Cómo balancearlo?
Agregando un punto de oferta o de demanda “ficticio” al que se le asigna el excedente
de oferta o demanda. Esa ruta tiene costo cero. Con este artificio matemático se
equilibra el problema y puede utilizarse el algoritmo de transporte.
 6

Para que un problema de transporte tenga una solución óptima, antes debe tener una
solución factible. Y esa condición factible se da cuando el problema está balanceado.
Entonces, la condición de factibilidad que exige un problema de transporte es:

Si un problema de transporte siempre puede equilibrarse, su formulación estándar es

(sólo una modificación en las restricciones como se muestra a continuación):

Forma estándar de un problema de transporte;

Minimizar:

Sujeta a:

, para i=1,……, m

, para j=1, ……, n

xij >=0 para i=1, …, m y j=1, …, n

Esta modificación en las restricciones de oferta y de demanda se produce por la condición de

factibilidad que vimos anteriormente.
 7

b) Tabla de transporte

El problema de transporte presenta una estructura especial en sus restricciones que permite
resolverlo en forma más simple utilizando la tabla de transporte siguiente:

Tabla 1: Modelo de la tabla de transporte aplicado al problema planteado en la Lectura 1

Los datos están tomados del problema de transporte planteado en la Lectura 1.

Lo primero que tenemos que hacer es resumir toda la información que poseemos en una
tabla:
• Los encabezamientos de las filas son los orígenes o las fuentes.
• Los encabezamientos de las columnas son los destinos.
• Al final de las filas, se añade una fila con el total de las demandas.
• Al final de las columnas, se añade una columna con el total de las ofertas.
• En cada celda hay dos valores: el que está recuadrado en la parte superior-
derecha de cada celda es el costo unitario para esa ruta “cij”, que son los coeficientes
de la función objetivo; el otro valor es el de la variable de decisión que se debe calcular para
esa ruta, que, como sabemos, es la cantidad de mercadería que debe enviarse por cada ruta
para que el costo sea mínimo, variable que aún desconocemos “xij”.

4.4 Determinación de la solución de inicio. Variables básicas

 Objetivo es obtener una solución factible básica inicial (SFBI).
 El número de restricciones que tiene un problema de transporte con “m” orígenes y “n”
destinos. El número de restricciones es m+n.

 El número de variables básicas (variables distintas de cero) es m+n-1.

 En un problema de programación lineal, se tiene normalmente la misma cantidad
de variables básicas que de restricciones.
 En uno de transporte una solución básica debe contener exactamente “m+n-1”
asignaciones no negativas.
 8

Existen varios procedimientos para encontrar la SFBI, nosotros

estudiaremos tres:
1. método de la esquina noroeste; 2. método del costo mínimo; 3. método de Voguel.
La diferencia entre ellos es que los dos primeros se realizan con pocos cálculos, mientras que
el de Vogel recurre a un algoritmo más complejo, pero se consigue una SFBI más cercana al
costo mínimo.

La explicación de estos métodos la haremos tomando como base el problema planteado en la

Lectura 1. Por lo tanto, el número de asignaciones (variables básicas) que debemos hacer es
de: 3+2-1=4 variables básicas.

1. Método de la esquina noroeste

 Para la primer asignación, se toma x₁₁, es decir, la celda que está más al norte y al
oeste de la tabla de transporte. Se le asigna el máximo valor posible, siempre que lo
permitan la oferta y la demanda correspondientes a esa celda.
En nuestro ejemplo, hemos tenido que elegir entre 3000 y 4000 unidades. Colocamos en la
celda x₁₁: 3000, pues la cantidad 4000 excedería la oferta de la sucursal N (ver Tabla 2).
 Nos fijamos si esa asignación anula el resto de la fila o de la columna. En nuestro
caso, anularía cualquier envío de la sucursal N al supermercado B, ya que la oferta está
saturada.
 Ahora volvemos a seleccionar la celda que está al noroeste de la tabla: x₂₁. Y le
asignamos el mayor valor posible, sin alterar las ofertas y las demandas que afectan
a esa celda. Como ya asignamos 3.000 unidades a la celda x₁₁ , solo nos quedan 1000
unidades para asignarle a la celda x₂₁.
 Nos volvemos a fijar si esa asignación anula el resto de la fila o de la columna.
Vemos que anula a la celda x₃₁ , ya que la demanda en esa columna queda satisfecha.
 Solo restan asignar los valores que quedan para completar el total de ofertas en las
celdas x₂₂= 3000 y x₃₂ = 3500
 En la tabla se muestran las cuatro asignaciones, que serán nuestra SFBI.

Tabla 2: SFBI por el método de la esquina NO para el problema planteado en la lectura 1

Calculemos el valor de z para esta SFBI: z= 15x₁₁+25x₁₂+30x₂₁+20x₂₂+18x₃₁+40x

Entonces:
z = 15 x 3000 + 25 x 0 + 30 x 1000 + 20 x 3000 + 18 x 0 + 40 x 3500 = 275000
 9

2. Método del costo mínimo

• La primera asignación se hace a la celda que tiene el menor costo unitario. En

nuestro caso, es la celda x₁₁, cuyo costo unitario es de $15. A esta celda le asignamos el
mayor valor posible, tal como lo hicimos en el método de la esquina NO. También en este
caso esa asignación es de 3000.
• Luego anulamos la celda x₁₂, ya que no hay más oferta para esa ruta.
• Ahora elegimos, de entre las celdas que aún no tienen asignación, aquella con el
menor costo unitario. Es la celda x₃₁, cuyo costo unitario es de 18. Le asignamos el máximo
valor posible respetando las ofertas y las demandas afectadas a esa celda. El único valor que
podemos asignarle es 1000, ya que un valor mayor excedería las ofertas y las demandas.
• Esta asignación anula a la celda x₂₁ y fuerza a asignarle a la celda x₃₂ 2500 unidades.
• Por último, queda vacía la celda x₂₂, a la que corresponde asignarle 4000 unidades.

Esta es otra forma de disponer las asignaciones en una SFBI. Es de suponer que esta solución
es más cercana a la óptima, ya que está basada en costos mínimos.

Tabla 3: SFBI por el método del costo mínimo para el problema planteado en la Lectura 1

Calculemos el valor de z para esta SFBI: z= 15x₁₁+25x₁₂+30x₂₁+20x₂₂+18x₃₁+40x₃₂

z = 15 x 3000 + 25 x 0 + 30 x 0 + 20 x 4000 + 18 x 1000 + 40 x 2500 = 243000
Como vemos, el costo total de envío es más bajo si se aplica el método del costo mínimo para
inicializar el problema.
 10

3. Método de Voguel

El método de aproximación de Vogel es un método heurístico de resolución de problemas de

transporte capaz de alcanzar una solución básica no artificial de inicio, este modelo requiere de
la realización de un número generalmente mayor de iteraciones que los demás métodos
heurísticos existentes con este fin, sin embargo producen mejores resultados iniciales que los
mismos.

ALGORITMO DE VOGEL
El método consiste en la realización de un algoritmo que consta de 3 pasos fundamentales y 1
más que asegura el ciclo hasta la culminación del método.

PASO 1
Determinar para cada fila y columna una medida de penalización restando los dos costos
menores en filas y columnas.

PASO 2
Escoger la fila o columna con la mayor penalización, es decir que de la resta realizada en el
"Paso 1" se debe escoger el número mayor. En caso de haber empate, se debe escoger
arbitrariamente (a juicio personal).

PASO 3
De la fila o columna de mayor penalización determinada en el paso anterior debemos de
escoger la celda con el menor costo, y en esta asignar la mayor cantidad posible de unidades.
Una vez se realiza este paso una oferta o demanda quedará satisfecha por ende se tachará la
fila o columna, en caso de empate solo se tachará 1, la restante quedará con oferta o demanda
igual a cero (0).

PASO 4: DE CICLO Y EXCEPCIONES

 Si queda sin tachar exactamente una fila o columna con cero oferta o demanda, detenerse.
 Si queda sin tachar una fila o columna con oferta o demanda positiva, determine las
variables básicas en la fila o columna con el método de costos mínimos, detenerse.
 Si todas las filas y columnas que no se tacharon tienen cero oferta y demanda, determine
las variables básicas cero por el método del costo mínimo, detenerse.
 Si no se presenta ninguno de los casos anteriores vuelva al paso 1 hasta que las ofertas y
las demandas se hayan agotado.
 11

4.5. El algoritmo de transporte parte II

1) Cálculos iterativos del algoritmo de transporte

 Una vez encontrada una SFBI, el siguiente paso es verificar si es la óptima.

 Aplicaremos para ello la prueba de optimalidad.
 Para explicar esta prueba, partiremos de la SFBI obtenida mediante el método del costo
mínimo.

2) Prueba de optimalidad: método de los multiplicadores

El método de los multiplicadores está fundamentado en el método simplex.

Se utilizan las variables duales “u” y “v”.
Consiste en asignar a la tabla de transporte los multiplicadores: “ui” a las filas “vj” y las
columnas, de modo que se cumpla que:

Para cada variable básica: ui+vj=cij

Para nuestro problema habrá “m+n-1=4” ecuaciones (una por cada variable básica) y
“m+n=5” multiplicadores (incógnitas):
Variables básicas:
x₁₁: u₁+v₁=15 (1)
x₂₂: u₂+v₂=20 (2)
x₃₁: u₃+v₁=18 (3)
x₃₂: u₃+v₂=40 (4)

Estas cuatro ecuaciones con cinco incógnitas forman un sistema que tiene infinitas soluciones.
Para resolverlo, haremos arbitrariamente u₁=0 y calcularemos las restantes, (en realidad, el
valor cero se lo podemos asignar a cualquier variable, generalmente se utiliza u₁).

Haciendo u₁=0
En (1): 0+v₁=15 entonces v₁=15
En (3): u₃+15=18 entonces u₃=3
En (4): 3+v₂=40 entonces v₂=37
En (2): u₂+37=20 entonces u₂=-17

Podemos disponer los multiplicadores en la tabla y calcularlos directamente desde allí, para las
variables básicas, de la siguiente manera:

Tabla 1 : Solución factible básica inicial por el método del costo

mínimo para el problema planteado
 12

El siguiente paso es evaluar si cada una de las variables no básicas puede colaborar para
lograr otra mejor distribución que pueda disminuir los costos.
Recordemos que el valor del costo total correspondiente a la Tabla 1 calculado en la lectura
anterior es:
z = 15 . 3000 + 25 . 0 + 30 . 0 + 20 . 4000 + 18 . 1000 + 40 . 2500 = 243000

Para saber si este costo es mínimo, se evalúa, como dijimos, cada variable no básica de la
siguiente manera:

Condición de optimalidad
Para cada variable no básica (igual a cero son las variables no básicas): ui+vj-cij<=0
El método termina cuando las evaluaciones den cero o negativas.
Siempre que exista una evaluación positiva, puede seguir mejorándose la función objetivo.

Una SFB (solución factible básica) es óptima si y solo si se verifica: ui+vj-cij <=0 para
todo i,j tal que xij sea una variable no básica.

Para nuestro problema evaluaremos las variables no básicas: x₁₂ y x₂₁

x₁₂: u₁+v₂-c₁₂=0+37-25=12
x₂₁: u₂+v₁-c₂₁=-17+15-30=-32

Observa que no se cumple la condición de optimalidad para la variable no básica x₁₂, pues es
positiva. Lo que significa que la distribución de la Tabla 1 no es la óptima.

Si deseamos redistribuir las variables de manera que el costo total disminuya lo más posible,
debemos tomar la celda de la variable no básica cuya evaluación: ui+vj-cij sea más
positiva (en caso de que haya más de una positiva).
 13

En este caso, un solo evaluador es positivo, por lo tanto se trata de que la variable no básica
x₁₂ pase a tener un valor distinto de cero. A esta variable se la llama variable entrante.

x₁₂: variable entrante.

Se trata, entonces, de adjudicarle el mayor valor posible a la variable x₁₂, por ejemplo, el
valor λ, aún desconocido.

Al ingresar una variable en la base, es decir, al pasar de no básica a básica, debe salir otra
variable: una variable básica pasará a ser no básica.

Para saber qué variable sale, debemos construir un ciclo cerrado comenzando en la celda de la
variable no básica entrante: x₁₂, con vértices en las celdas de las variables básicas, formando
ángulos rectos, y terminando en la misma celda origen. El circuito puede hacerse en el sentido
de las agujas del reloj, o bien en el opuesto, pero respetando en todo el trayecto el sentido
elegido.

Teniendo en cuenta la construcción de la tabla, respetando las ofertas y las demandas, se irá
sumando y restando a las variables básicas el valor λ, tal como se muestra en la Tabla 2.

Tabla 2 : Pasos de redistriución de las variables

La variable que sale es –de entre las que disminuyen su valor en el ciclo– la que tiene un
valor menor.

Debemos elegir, entonces, entre 3000 y 2500 que corresponden a las celdas en donde λ se
resta. El menor valor es 2500, entonces le asignamos a λ=2500. Por lo que:

x₃₂: variable saliente

 14

En la Tabla 3 se ilustra la nueva distribución de las variables.

Tabla 3: nueva asignación a las variables de decisión

18
3500 _ 3500
40
E

4000 6500 10500

bj

Fuente: elaboración propia.

Observa que λ=2500 es el menor valor que puede asumir la variable entrante, de manera que
la disminución de los costos sea la máxima posible y a la vez que no se alteren las
restricciones de no negatividad: xij >=0.

Calculemos ahora la disminución que debería producirse en el costo total por esta nueva
asignación a las variables de decisión.
Para esto, multiplicamos el valor asignado a la variable entrante: 2500 por el valor del
evaluador que mejora la función objetivo: 12. Entonces, observando la Tabla 2:

Disminución en la función costo será: x₃₂.( u₁+v₂-c₁₂)= 2500.12=30000.

Por lo tanto, debemos restar al costo de 243000 que teníamos con la asignación que nos
proporcionó el método para obtener la SFBI, el valor obtenido de 30000.

El costo total ahora, con las nuevas asignaciones, deberá ser de:

CT= 243000-30000=213000

Otra forma de calcular el CT de la Tabla 3 es:

CT=500.15+2500.25+4000.20+3500.18=213000

¿Será este el mínimo costo para el plan de transporte planteado en la Tabla 3?

 15

Para esto, debemos volver a aplicar la condición de optimidad y observar si algún evaluador
sigue quedando positivo.
En la Tabla 4 se muestra la nueva distribución recientemente encontrada agregando las
variables duales u y v, para aplicar el método de los multiplicadores a las nuevas variables
básicas y evaluar a cada variable no básica y ver si se puede mejorar (disminuir aún más) el
costo total o si ya llegamos al óptimo.
Observa que en la Tabla 4 se calcularon los valores de ui y vj directamente en la tabla.
Recordemos que:
Para cada variable básica, ui+vj=cij.
Tabla 4 : Cálculo de las variables duales u y v

Ahora, evaluamos las variables no básicas de la siguiente manera:

Condición de optimalidad
Para cada variable no básica: ui+vj-cij<=0.

Para las variables no básicas: x₂₁: u₂+v₁-c₂₁ = -5+15-30=-20

x₃₂: u₃+v₂-c₃₂= 3+25-40=-12

Ambas evaluaciones son negativas. Concluimos que se cumple la prueba de optimalidad y las
asignaciones realizadas son la respuesta del problema. Significa entonces que el costo que
arrojan las tablas 3 y 4 son los mínimos, y la distribución de variables es la respuesta sobre el
plan de transporte que optimiza los costos totales.
Respuesta:
El plan es enviar:
Norte a A: 500 artículos
Norte a B: 2500 artículos
Sur a A: ningún artículo
Sur a B: 4000 artículos
Este a A: 3500 artículos
A un costo mínimo de $213.000