Los procesos de asignación y transporte - introducción

En el presente trabajo se propone un estudio detallado de los problemas
de asignación y transporte, casos particulares de problemas de programación
lineal.
1.

El problema de transporte

El problema de transporte es un caso particular de problema lineal, una de
las primeras aplicaciones potentes del modelo lineal a situaciones cotidianas.
Como problema lineal, podemos representarlomediante un modelo lineal y
utilizar el método del simplex.
Este problema, sin embargo, tiene una estrcutura que permite construir
un método de resolución más ecaz.
El problema de transporte se ocupa de enviar unidades de un producto
desde m orígenes, O1 , . . . , Om hasta n destinos D1 , . . . , Dn en las siguientes
condiciones:
- Cada origen Oi dispone de una oferta ai .
- Cada destino Djrealiza una demanda bj .
- El coste de enviar una unidad desde Oi a Dj se denota por cij
El problema trata de determinar el número xij que se deben enviar desde
cada origen Oi hasta cada destino Dj minimizando el coste de transporte y
sujeto a las restricciones tanto en la oferta como en la demanda.
El modelo lineal correspondiente a este problema es el que sigue:
m

n

min z =

cij xiji=1 j=1

sujeto a
n

xij ≤ ai , i = 1, . . . , m
j=1
m

xij ≥ bj , j = 1, . . . , n
i=1

xij ≥ 0, i = 1, . . . , m, j = 1, . . . , n

1

Las primeras m restricciones son las correspondientes a las ofertas de los
orígenes, mientras que las n siguientes corresponden a la demanda de los destinos. Dado que el problema representa cantidades de producto a transportar,
todas lasvariables son positivas.
la forma estándar del problema de transporte es como sigue:
m

n

min z =

cij xij
i=1 j=1

sujeto a
n

xij = ai , i = 1, . . . , m
j=1
m

xij = bj , j = 1, . . . , n
i=1

xij ≥ 0, i = 1, . . . , m, j = 1, . . . , n

. Una productora de barras de pan tiene dos almacenes A1 y
A2 desde los que enviar pan a tres panaderías P1 , P2 , P3 , con las siguientescondiciones:
Ejemplo

- A1 tiene una oferta de2000 barras de pan. Los costes de envío por
unidad son de 8, 6 y 10 respectivamente.
- A2 tiene una oferta de2500 barras de pan. Los costes de envío por
unidad son de 10, 4 y 9 respectivamente.
- Las panaderías tienen demandas de 1500, 2000 y 1000 barras de pan
respectivamente.
Construimos el modelo lineal de este problema:
min z = 8x1 1 +6x1 2 + 10x1 3 + 10x2 1 + 4x2 2 + 9x2 3
sujeto a
x11 +x12 +x13
x11
x12
x13

x21 +x22 +x23
+x21
x22
+x23

= 2000
= 2500
= 1500 xij ≥ 0
= 2000
= 1000

Dado que la suma de ofertas es igual que la de demandas, podemos escribir
restricciones de igualdad.
2

Para ver mejor la estructura de este problema, lo escribimos en forma
matricial:





min z = (8, 6, 10, 10, 4,9) 




sujeto a







1
0
1
0
0

1
0
0
1
0

1
0
0
0
1

0
1
1
0
0

0
1
0
1
0

0
1
0
0
1













x11
x12
x13
x21
x22
x23

x11
x12
x13
x21
x22
x23














 
 
=
 
 


2000
2500
1500
2000
1000








En este caso, m = 2, n = 3, haydos orígenes y tres destino. Observando
los vectores que forman la matriz A podemos decir que cada vector columna
aij de la matriz A tiene un 1 en las posiciones i y m + j .
De forma más general, dada la estructura del problema de transporte,
cualquier problema de este tipo con m orígenes y n destinos tiene la misma
matriz A, con m + n las y m · n columnas, de rango m + n − 1.
Esto nos diceque los datos importantes del problema de transporte son
el número de orígenes, el número de destinos, las ofertas y demandas y los
costes de transporte. Podemos recoger toda esa información en una sola tabla,
posibilidad que se explora a continuación.
1.1.

Forma matricial

La forma matricial del problema de transporte consiste en representar los
datos del problema en una tabla...