Transporte

Fundamentos de Investigaci¶on de Operaciones
El Problema de Transporte
Septiembre 2002
El Problema de Transporte corresponde a un tipo particular de un problema de programaci¶on
lineal. Si bien este tipo de problema puede ser resuelto por el m¶etodo Simplex, existe un algoritmo
simpli¯cado especial para resolverlo.
2 Resoluci¶on del Problema de Transporte
2.1 Soluci¶on Inicial
Consideremos un problema de transporte balanceado con m puntos de oferta y n puntos de demanda.
De acuerdo a la formulaci¶on vista anteriormente, el problema tendr¶a m+n restricciones de igualdad.
Para proceder a describir algunos m¶etodos para encontrar una primera soluci¶on inicial, es impor-
tante observar que si un conjunto de valores para las variables xij satisface todas las restricciones
salvo una, autom¶aticamente satisface la otra restricci¶on. Por ejemplo consideremos que en el ejem-
plo anterior se sabe que los valores de las varibles satisfacen todas las restricciones, salvo la primera
restricci¶on de oferta. Por lo tanto, los valores de las xij satisfacen d1 + d2 + d3 + d4 = 125 millones
de [kWh] y proveen s2 + s3 = 125 ¡ s1 = 90 millones de [kWh] de las plantas 2 y 3. Por lo tanto,
la planta 1 debe proveer 125 ¡ (125 ¡ s1) = 35 millones de [kWh], luego los valores de xij tambi¶en
satisfacen la primera restricci¶on de oferta.
4
En lo sucesivo, para resolver el problema de transporte, consideraremos que se satisfacen m+n¡1
restricciones, omitiendo alguna. En forma arbitraria, omitiremos la primera restricci¶on de oferta.
Evidentemente, cualquier colecci¶on de m+n¡1 variables no necesariamente es una soluci¶on factible
para el problema.
Consideremos el siguiente problema de transporte (omitiremos los costos unitarios):
4
5
3 2 4
En forma matricial, las restricciones del problema de transporte balanceado anterior puede ser escrito
de la siguiente forma:
0BBBB@
1 1 1 0 0 0
0 0 0 1 1 1
1 0 0 1 0 0
0 1 0 0 1 0
0 0 1 0 0 1
1CCCCA
0BBBBBB@
x11
x12
x13
x21
x22
x23
1CCCCCCA
=
0BBBB@
4
5
3
2
4
1CCCCA
Eliminando la primera restricci¶on de oferta el sistema se reduce a:
0BB@
0 0 0 1 1 1
1 0 0 1 0 0
0 1 0 0 1 0
0 0 1 0 0 1
1CCA
0BBBBBB@
x11
x12
x13
x21
x22
x23
1CCCCCCA
=
0BB@
5
3
2
4
1CCA
Como el sistema anterior tiene 4 restricciones y 6 variables posee in¯nitas soluciones, sin embargo,
siempre tendr¶a como soluci¶on al menos 4 variables no nulas.
Para obtener una soluci¶on b¶asica factible en forma simple introduciremos el concepto de loop.
De¯nici¶on 1 Un orden secuencial de al menos cuatro celdas distintas se denomina loop si:
1. Dos celdas consecutivas est¶an en la misma columna o en la misma ¯la.
2. No tiene tres celdas consecutivas en una misma columna o en una misma ¯la.
3. La ¶ultima celda de la secuencia tiene una ¯la o columna com¶un con la primera celda de la
secuencia.
Las ¯guras siguientes muestran algunos tipos de loop en dos tableaux de transporte:
5
Las siguientes ¯guras muestran algunos ejemplos de secuencias de celdas que no conforman un loop,
pues no satisfacen todas las condiciones.
Teorema 1 En un problema de transporte balanceado con m puntos de oferta y n puntos de de-
manda, las celdas correspondientes a un conjunto de m + n ¡ 1 variables no contienen un loop s¶³ y
s¶olo s¶³ las n + m ¡ 1 variables constituyen una soluci¶on inicial.
El teorema anterior se desprende del hecho de que en un conjunto de m+n¡1 celdas no contienen un
loop s¶³ y s¶olo s¶³ las m+n¡1 columnas correspondientes a las celdas son linealmente independientes.
Los m¶etodos m¶as empleados para obtener soluciones iniciales son:
² El m¶etodo de la Esquina Noroeste.
² El m¶etodo del Costo M¶³nimo.
² El m¶etodo de Vogel.
A continuaci¶on revisaremos s¶olo el m¶etodo de la Esquina Noroeste y el de Vogel.
M¶etodo de la Esquina Noroeste.
Para encontrar una soluci¶on inicial se comienza por la esquina superior izquierda (noroeste) del
tableau de transporte intentando asignar la m¶axima cantidad posible a x11. Evidentemente, el valor
m¶aximo de x11 debe ser el menor entre s1 y d1. Si x11 = s1, se puede descartar la primera ¯la pues
ya no podr¶a asignarse m¶as desde el primer punto de oferta, se avanza a la siguiente ¯la. Al mismo
tiempo, se debe cambiar d1 por d1¡s1, de forma de indicar la cantidad de demanda no satisfecha en
el primer punto de demanda. En caso que x11 = d1, se debe descartar la primera columna y cambiar
s1 por s1¡d1, avanzando una columna. Si x11 = d1 = s1, se debe avanzar en una columna o en una
¯la (pero no en ambas). Se asigna un cero en la direcci¶on escogida y se descarta la otra alternativa.
El m¶etodo contin¶ua aplicando el mismo criterio desde la esquina noroeste del tableau restante. Una
vez que est¶an asignadas toda de demanda y oferta disponible, se terminan las asignaciones y est¶a
completa la asignaci¶on inicial.
Apliquemos el m¶etodo al siguiente tableau (notar que no se incorporan los costos pues el m¶etodo
no los emplea):
5
1
3
2 4 2 1
Comenzamos asignando la m¶axima cantidad posible por ¯la o por columna en la esquina noroeste.
En este caso, controla la primera columna, luego:
2 3
£ 1
£ 3
0 4 2 1
A continuaci¶on, avanzamos una columna y en esta celda controla la ¯la, por lo tanto queda:
6
2 3 £ £ 0
£ 1
£ 3
0 1 2 1
En este caso, la esquina m¶as noroeste disponible es la celda 2-2. Aqu¶³, la demanda y la oferta se
igualan. Arbitrariamente se escoger¶a la celda inferior de la misma columna para asignar un cero:
2 3 £ £ 0
£ 1 £ £ 0
£ 0 3
0 0 2 1
Luego, la celda m¶as noroeste disponible es la 3-3. En esta celda, controla la demanda de 2 sobre la
oferta de 3, luego:
2 3 £ £ 0
£ 1 £ £ 0
£ 0 2 1
0 0 0 1
Finalmente, se completa el tableau haciendo la ¶ultima asignaci¶on factible:
2 3 £ £ 0
£ 1 £ £ 0
£ 0 2 1 0
0 0 0 0
En el tableau ¯nal se puede veri¯car las m+n¡1 asignaciones. Adem¶as se observa que la secuencia
de celdas no no conforman ning¶un loop, por lo tanto, de acuerdo al teorema corresponde a una
asignaci¶on inicial factible.
M¶etodo de Vogel.
El m¶etodo comienza calculando por cada columna y por cada ¯la el castigo o penalty. El cas-
tigo se calcula como la diferencia entre los dos costos menores en la columna o en la ¯la seg¶un
corresponda. A continuaci¶on, se determina la ¯la o columna con un mayor valor de castigo. Luego,
se selecciona como variable basal la celda con menor costo de la ¯la o columna, seg¶un corresponda,
y se le asigna la m¶axima cantidad posible. Una vez realizada la asignaci¶on, se descarta la ¯la o
columna cuya oferta o demanda haya sido completa. Se recalcula la demanda u oferta disponible
en la ¯la o columna. La primera asignaci¶on se ha completado.
Se vuelven a calcular los castigos por ¯la y por columna y se repite el procedimiento descrito
hasta completar las asignaciones posibles en el tableau.
La ventaja del m¶etodo de Vogel por sobre el de la Esquina Noroeste es que va adelante algunas
iteraciones y por lo tanto se obtiene una soluci¶on inicial mejor. Eventualmente puede ocurrir que
aplicando el m¶etodo se llegue directamente a la soluci¶on ¶optima. La desventaja del m¶etodo de Vogel
radica en que sin duda es m¶as complejo que el de la esquina noroeste, por lo tanto es m¶as dif¶³cil de
implementar y m¶as proclive a errores en la aplicaci¶on.
Para ilustrar la aplicaci¶on del m¶etodo veamos un ejemplo. Consideremos el siguiente tableau de
transporte:
7
Oferta
6 7 8
10
15 80 78
15
Demanda 15 5 5
De acuerdo al m¶etodo, en primer lugar se calculan los castigos por ¯la y por columna:
Oferta Castigo
6 7 8
10 7 ¡ 6 = 1
15 80 78
15 78 ¡ 15 = 63
Demanda 15 5 5
Castigo 9 73 70
El mayor castigo entre ¯las y columnas se encuentra en la segunda columna. De ambas celdas, la
de m¶³nimo costo es la de costo unitario de 7, buscando la m¶axima asiganci¶on por ¯la y por columna
controla la columna con una signaci¶on m¶axima de 5 unidades.
Oferta Castigo
6 7 8
5 5 8 ¡ 6 = 2
15 80 78
£ 15 78 ¡ 15 = 63
Demanda 15 0 5
Castigo 9 - 70
De los castigos recalculados, el mayor corresponde a la tercera columna. En este caso la celda de
menor costo es la de la primera ¯la. Veri¯cando la asignaci¶on m¶axima por ¯la y por columna,
controla la ¯la con una asignaci¶on m¶axima de 5 unidades.
Oferta Castigo
6 7 8
5 5 0 -
15 80 78
£ £ 15 -
Demanda 15 0 0
Castigo 9 - -
Luego, el ¶unico castigo disponible (y por lo tanto el mayor) corresponde a la primera columna. En
este caso, el m¶³nimo costo corresponde a la primera ¯la. La m¶axima cantidad posible a asignar por
columna es 15, pero por ¯la es 0. Por lo tanto, debemos asignar 0 unidades a la celda de menor
costo.
Oferta Castigo
6 7 8
0 5 5 0 -
15 80 78
£ £ 15 -
Demanda 15 0 0
Castigo - - -
Finalmente, no es posible calcular castigos y debemos asignar las unidades disponibles a la ¶unica
celda libre. Luego:
8
Oferta Castigo
6 7 8
0 5 5 0 -
15 80 78
15 £ £ 0 -
Demanda 0 0 0
Castigo - - -
N¶otese que el n¶umero de asignaciones es exactamente igual a m+ n ¡ 1 = 2 + 3 ¡ 1 = 5. Eventual-
mente, el m¶etodo puede generar un n¶umero inferior de asignaciones. En dicho caso se completa las
m + n ¡ 1 asignaciones con ceros. En el caso de que falte s¶olo una asiganci¶on, se puede ubicar un
cero en cualquier casilla no asignada. En el caso que se requiera de dos o m¶as ceros, la asignaci¶on
no es tan arbitraria. M¶as adelante se de¯nir¶a qu¶e criterio emplear en dichos casos.
Existen problemas de maximizaci¶on que pueden ser considerados como problemas de Transporte.
En este caso, los coe¯cientes cij est¶an asociado a los bene¯cios unitarios de la variable asociada a
la combinaci¶on i ¡ j y el objetivo es maximizar la suma total de los aportes individuales de las
variables. Se mantienen las restricciones de oferta y demanda.
En los casos de maximizaci¶on, es preciso alterar los m¶etodos para obtener una soluci¶on inicial
factible. En el caso del m¶etodo de la Esquina Noroeste, se debe intentar asignar la mayor cantidad
posible a las casillas con mayor cij . En el caso del m¶etodo de Vogel, las castigos se calculan entre
los dos mayores bene¯cios por ¯la y por columna. Al igual que el m¶etodo de la Esquina Noroeste,
se busca asignar la mayor cantidad posible a las casillas con mayor bene¯cio.
2.2 El M¶etodo Simplex del Problema de Transporte
A continuaci¶on se expondr¶an los pasos para aplicar el m¶etodo Simplex para el problema de Trans-
porte. La deducci¶on y justi¯caci¶on detallada de cada uno de los pasos se puede encontrar en los
textos de la bibliograf¶³a de la asignatura.
Paso 1 Si el problema no est¶a balanceado, balancearlo. Construir el tableau de transporte.
Paso 2 Encontrar una soluci¶on inicial factible por el m¶etodo de la Esquina Noroeste o el de Vogel.
Veri¯car las m + n ¡ 1 asignaciones y completarlas si es necesario.
Paso 3 Plantear y resolver el sistema que se obtiene a trav¶es de:
² De¯nir para cada ¯la del tableau la variable ui con (i = 1 : : :m).
² De¯nir para cada columna del tableau la variable vj con (j = 1 : : : n).
² Plantear para cada casilla asignada la ecuaci¶on ui + vj = cij . Donde cij es el costo unitario
asociado a la casilla i ¡ j.
² Asignar un valor arbitrario a una de las variables, por ejemplo u1 = 0.
Paso 4 Calcular en todas las casillas no asignadas (no b¶asicas) eij = cij ¡ ui ¡ vj . Si todos los
eij ¸ 0 se ha encontrado el ¶optimo. Si existe alg¶un eij < 0, incorporar la variable con menor eij
siempre y cuando pueda formar un loop, en dicho caso, asignar el mayor valor posible de modo de
mantener las variables basales mayores o iguales a cero.
Paso 5 Si la soluci¶on no es la ¶optima, emplear la soluci¶on del paso anterior para volver a plantear
y resolver el sistema (Paso 3). Seguir al Paso 4.
9
La variable eij representa el aporte neto unitario de la incorporaci¶on de la variable i ¡ j a la base.
Por lo tanto, si el problema es de maximizaci¶on, la soluci¶on ser¶a ¶optima si todos los eij < 0. En
caso contrario, se ingresa a la base la variable con mayor eij que pueda formar un loop.
En el caso de que al emplear uno de los m¶etodos para obtener una soluci¶on inicial falten dos o
m¶as asignaciones para completar las m+n¡1 asignaciones requeridas, los ceros deben ser ubicados
de tal forma que sea su¯ciente dar s¶olo un valor arbitrario a las variables del sistema asociado a la
asignaci¶on para poder resolverlo completamente.
Ilustremos el procedimiento resolviendo el tableau planteado para el problema del primer ejemplo.
En ese caso, mediante la Esquina Noroeste se obtuvo la siguiente soluci¶on inicial:
Ciudad 1 Ciudad 2 Ciudad 3 Ciudad 4 Oferta
8 6 10 9
Planta 1 35 35
9 12 13 7
Planta 2 10 20 20 50
14 9 16 5
Planta 3 10 30 40
Demanda 45 20 30 30
A continuaci¶on podemos plantear las variables del sistema asociado:
v1 v2 v3 v4
8 6 10 9
u1 35 35
9 12 13 7
u2 10 20 20 50
14 9 16 5
u3 10 30 40
45 20 30 30
Luego, las ecuaciones se plantean en las casillas asignadas:
u1 + v1 = 8 (1)
u2 + v1 = 9 (2)
u2 + v2 = 12 (3)
u2 + v3 = 13 (4)
u3 + v3 = 16 (5)
u3 + v4 = 5 (6)
Agregando la condici¶on u1 = 0 se obtiene de (1) v1 = 8. Luego, de (2) u2 = 1. De (3) y de (4)
v2 = 11 y v3 = 12. Reemplazando en (5) se calcula u3 = 4. Finalmente, de (6) se obtiene v4 = 1. A
continuaci¶on se calculan los eij en las casillas no b¶asicas:
e12 = 6 ¡ 0 ¡ 11 = ¡5
e13 = 10 ¡ 0 ¡ 12 = ¡2
e14 = 9 ¡ 0 ¡ 1 = 8
e24 = 7 ¡ 1 ¡ 1 = 5
e31 = 14 ¡ 4 ¡ 8 = 2
e32 = 9 ¡ 4 ¡ 11 = ¡6
Por lo tanto, el menor eij corresponde a e32 con valor ¡6. Lo que signi¯ca que por cada unidad
asignada a la variable x32 el efecto global neto es de ¡6, independientemente de que el costo asociado
a dicha casilla sea de 9. Veamos si existe un loop factible y el m¶aximo valor ® que podr¶³a tomar la
variable.
10
8 6 10 9
35 35
9 12 13 7
10 20 ¡ ® 20 + ® 50
14 9 16 5
® 10 ¡ ® 30 40
45 20 30 30
Como las variables deben ser positivas, el valor de ® debe ser tal que no introduzca una variable
negativa al tableau. En este caso, la condici¶on que controla es 10 ¡ ® ¸ 0, por lo tanto ® = 10.
Introducimos el valor de ® y volvemos a plantear el sistema asociado:
v1 v2 v3 v4
8 6 10 9
u1 35 35
9 12 13 7
u2 10 10 30 50
14 9 16 5
u3 10 30 40
45 20 30 30
u1 + v1 = 8
u2 + v1 = 9
u2 + v2 = 12
u2 + v3 = 13
u3 + v2 = 9
u3 + v4 = 5
u1 = 0
Las ¶unicas variables no b¶asicas que tienen un eij < 0 son: e12 = ¡5, e24 = ¡1 y e13 = ¡2. Buscando
un loop para x12 y su m¶aximo valor factible se obtiene:
8 6 10 9
35 ¡ ® ® 35
9 12 13 7
10 + ® 10 ¡ ® 30 50
14 9 16 5
10 30 40
45 20 30 30
De acuerdo al loop encontrado, el m¶aximo valor para ® es 10. Luego, volvemos a plantear el sistema
para las variables basales:
v1 v2 v3 v4
8 6 10 9
u1 25 10 35
9 12 13 7
u2 20 30 50
14 9 16 5
u3 10 30 40
45 20 30 30
11
u1 + v1 = 8
u1 + v2 = 6
u2 + v1 = 9
u2 + v3 = 13
u3 + v2 = 9
u3 + v4 = 5
u1 = 0
Resolviendo y evaluando los eij para cada variable no basal, el ¶unico eij < 0 es e13 = ¡2. Veri¯cando
que exista un loop y determinando el m¶aximo valor posible se tiene:
8 6 10 9
25 ¡ ® 10 ® 35
9 12 13 7
20 + ® 30 ¡ ® 50
14 9 16 5
10 30 40
45 20 30 30
En este caso, para mantener las variables positivas ® deber ser 25. Haciendo la actualizaci¶on y
volviendo a resolver el sistema asociado se tiene:
v1 v2 v3 v4
8 6 10 9
u1 10 25 35
9 12 13 7
u2 45 5 50
14 9 16 5
u3 10 30 40
45 20 30 30
u1 + v2 = 6
u1 + v3 = 10
u2 + v1 = 9
u2 + v3 = 13
u3 + v2 = 9
u3 + v4 = 5
u1 = 0
Resolviendo el sistema, se determina que todos los eij son positivos, por lo tanto la incorporaci¶on
de cualquier variable a la base aumentar¶a el valor total de la funci¶on objetivo. Como el problema
es de minimizaci¶on, se ha alcanzado el ¶optimo. Por lo tanto, el tableau ¯nal queda:
8 6 10 9
10 25 35
9 12 13 7
45 5 50
14 9 16 5
10 30 40
45 20 30 30
12
La soluci¶on corresponde exactamente a la entrega con anterioridad. La soluc¶on ¶optima es:
x12 = 10
x13 = 25
x21 = 45
x23 = 5
x32 = 10
x34 = 30
x11 = x14 = x22 = x24 = x31 = x33 = 0
z = 6(10) + 10(25) + 9(45) + 13(5) + 9(10) + 5(30) = 1020
3 An¶alisis de Sensibilidad en Problemas de Transporte
A continuaci¶on se discustir¶a tres tipos de an¶alisis de sensibilidad de un problema de transporte:
Variaci¶on 1 Cambios en los coe¯cientes de la funci¶on objetivo de variables no b¶asicas.
Variaci¶on 2 Cambios en los coe¯cientes de la funci¶on objetivo de variables b¶asicas.
Variaci¶on 3 Incrementos en un oferta y en una demanda.
Para ilustrar el an¶alisis de sensibilidad sobre la soluci¶on ¶optima de un problema de transporte
emplearemos la soluci¶on obtenida en la secci¶on anterior:
v1 = 6 v2 = 6 v3 = 10 v4 = 2
8 6 10 9
u1 = 0 10 25 35
9 12 13 7
u2 = 3 45 5 50
14 9 16 5
u3 = 3 10 30 40
45 20 30 30
3.1 Variaci¶on de Coe¯cientes en la Funci¶on Objetivo de Variables No
Basales
En este caso, simplemente se impone una variaci¶on ¢ en el coe¯ciente de la variable xij a modi¯car,
estudiando el rango de variaci¶on admisible de modo que el eij respectivo mantenga su signo.
A modo de ejemplo, supongamos que se desea determinar a cuanto debe disminuir el costo de
env¶³o desde la Planta 1 a la Ciudad 1 de modo de incorporar esta combinaci¶on a la soluci¶on ¶optima.
En este caso, un cambio del coe¯ciente c11 = 8 a c11 = 8 ¡ ¢ no afecta los valores de los ui y
vj calculados previamente, por lo tanto:
e11 = (8 ¡ ¢) ¡ 0 ¡ 6 = 2 ¡ ¢
Como corresponde a un problema de minimizaci¶on, para que x11 entre a la base debe cumplirse que
e11 · 0, es decir, ¢ ¸ 2. Por lo tanto, el costo debe disminuir a menos de 6 para que se incorpore
a la soluci¶on ¶optima. De todas formas, se debe veri¯car que la variable pueda generar un loop:
13
v1 = 6 v2 = 6 v3 = 10 v4 = 2
8 6 10 9
u1 = 0 ® 10 25 ¡ ® 35
9 12 13 7
u2 = 3 45 ¡ ® 5 + ® 50
14 9 16 5
u3 = 3 10 30 40
45 20 30 30
Por lo tanto la variable puede entrar a la base con valor de 25, el nuevo valor de la funci¶on objetivo
ser¶³a:
zk+1 = zk + eij £ ® = 1020 + (2 ¡ ¢)25 ¢ ¸ 2
3.2 Variaci¶on de Coe¯cientes en la Funci¶on Objetivo de Variables Basales
En este caso la situaci¶on es m¶as compleja pues una variaci¶on del coe¯ciente de una variable basal
afectar¶a el valor de los ui y los vj calculados previamente. En este caso, se debe volver a resolver el
sistema en t¶erminos de la variaci¶on ¢ del coe¯ciente de la variable basal, volver a calcular los eij y
determinar el rango de variaci¶on admisible.
Supongamos por ejemplo que se desea determinar en cuanto podr¶³a aumentar el costo de env¶³o
desde la Planta 1 a la Ciudad 3 de modo de mantener la base ¶optima. En este caso, cambiamos
c13 = 10 por c13 = 10 + ¢ y volvemos a resolver el sistema:
u1 + v2 = 6
u1 + v3 = 10 + ¢
u2 + v1 = 9
u2 + v3 = 13
u3 + v2 = 9
u3 + v4 = 5
u1 = 0
De esta forma, se obtiene:
u1 = 0
v2 = 6
v3 = 10 + ¢
v1 = 6 + ¢
u2 = 3 ¡ ¢
u3 = 3
v4 = 2
Luego, calculamos los eij para todas las variables no basales y sus restricciones:
e11 = 8 ¡ u1 ¡ v1 = 2 ¡ ¢ ¸ 0 ! ¢ · 2
e14 = 9 ¡ u1 ¡ v4 = 7 ¸ 0
e22 = 12 ¡ u2 ¡ v2 = 3 + ¢ ¸ 0 ! ¢ ¸ ¡3
e24 = 7 ¡ u2 ¡ v4 = 2 + ¢ ¸ 0 ! ¢ ¸ ¡2
e31 = 14 ¡ u3 ¡ v1 = 5 ¡ ¢ ¸ 0 ! ¢ · 5
e33 = 16 ¡ u3 ¡ v3 = 3 ¡ ¢ ¸ 0 ! ¢ · 3
Por lo tanto, la base ¶optima se mantiene para un rango de variaci¶on: ¡2 ¸ ¢ ¸ 2, o bien,
8 · c13 · 12.
14
3.3 Incrementos en una Oferta y en una Demanda
Si tanto en alguna oferta si como en alguna demanda dj se produce un aumento de ¢, se mantiene
el balanceo del problema. En este caso, se demuestra que:
znuevo = zoriginal + ¢ £ ui + ¢ £ vj
La expresi¶on anterior se obtiene a partir de que tanto los ui y los vj equivalen a menos el precio
sombra de la restricci¶on asociada a cada origen i o destino j seg¶un corresponda.
Por ejemplo, si la oferta de la Planta 1 y la demanda de la Ciudad 2 crece en una unidad, se
tiene:
znuevo = 1020 + 1 £ 0 + 1 £ 6 = 1026
Una vez de¯nido el nuevo valor de la funci¶on objetivo, es importante determinar como cambian los
valores de las variables. Para ello se siguen las siguientes reglas:
1. Si xij es una variable b¶asica, xij se incrementa en ¢.
2. Si xij es una variable no b¶asica, se debe encontrar el loop que contenga a xij y algunas de las
variables basales. Encontrar la primera celda de la ¯la i (distinta de xij) y aumentar su valor
en ¢. Continuar el loop, incrementando y disminuyendo en ¢ en forma alternada.
Para ilustrar la primera situaci¶on, supongamos que s1 y d2 aumentan en 2. Como x12 es una variable
basal, el nuevo tableau ¶optimo queda:
v1 = 6 v2 = 6 v3 = 10 v4 = 2
8 6 10 9
u1 = 0 12 25 37
9 12 13 7
u2 = 3 45 5 50
14 9 16 5
u3 = 3 10 30 40
45 22 30 30
El nuevo valor de la funci¶on objetivo es: 1020 + 2u1 + 2v2 = 1032
Para ilustrar la segunda situaci¶on, supongamos que s1 y d1 aumentan en 1. Como x11 es una
variable no basal, debemos determinar el loop que incorpora a la celda (1; 1). En este caso, el loop
es (1; 1) ¡ (1; 3) ¡ (2; 3) ¡ (2; 1). La primera celda del loop que est¶a en la ¯la i distinta de (1; 1) es
(1; 3). Entonces, se debe agregar ¢ a x13. Continuando con el loop, se debe disminuir en ¢ x23 y
volver a aumentar en ¢ a x21. El nuevo tableau ¶optimo se muestra a continuaci¶on:
v1 = 6 v2 = 6 v3 = 10 v4 = 2
8 6 10 9
u1 = 0 10 26 36
9 12 13 7
u2 = 3 46 4 50
14 9 16 5
u3 = 3 10 30 40
46 20 30 30
El nuevo valor de la funci¶on objetivo es: 1020 + u1 + v1 = 1026.
15
4 El Problema de Transbordo
Un problema de transporte permite s¶olo env¶³os directamente desde los puntos de origen a los puntos
de demanda. En muchas situaciones, sin embargo, existe la posibilidad de hacer env¶³os a trav¶es de
puntos intermedios (puntos de transbordo). En este caso se habla de un problema de transbordo. A
continuaci¶on veremos como la soluci¶on a de problema de transbordo puede ser encontrada a trav¶es
de un problema de transporte.
De¯niremos los puntos de oferta como aquellos puntos desde donde s¶olo se puede despachar unidades.
Similarmente, un punto de demanda es un punto donde s¶olo se pueden recibir unidades. Un punto
de transbordo es punto que puede recibir y enviar unidades a otros puntos. Veamos un ejemplo:
Ejemplo 2. Una f¶abrica posee dos plantas de manufactura, una en Memphis y otra en Denver.
La planta de Memphis puede producir hasta 150 unidades al d¶³a, la de Denver hasta 200 unidades al
d¶³a. Los productos son enviados por avi¶on a Los Angeles y Boston. En ambas ciudades, se requieren
130 unidades diarias. Existe una posibilidad de reducir costos enviando algunos productos en primer
lugar a New York o a Chicago y luego a sus destinos ¯nales. Los costos unitarios de cada tramo
factible se ilustran en la siguiente tabla:
Hacia
Desde Memphis Denver N.Y. Chicago L.A. Boston
Memphis 0 - 8 13 25 28
Denver - 0 15 12 26 25
N.Y. - - 0 6 16 17
Chicago - - 6 0 14 16
L.A. - - - - 0 -
Boston - - - - - 0
La f¶abrica desea satisfacer la demanda minimizando el costo total de env¶³o. En este problema,
Memphis y Denver son puntos de oferta de 150 y 200 unidades respectivamente. New York y Chicago
son puntos de transbordo. Los Angeles y Boston son puntos de demanda de 130 unidades cada uno.
Esquem¶aticamente, la situaci¶on es la siguiente:
Memphis
Denver
New York
Chicago
Los Angeles
Boston
A continuaci¶on construiremos un problema de transporte balanceado a partir del problema de trans-
bordo. Para ello podemos seguir los siguientes pasos (suponiendo que la oferta excede a la demanda):
Paso 1 Si es necasario, se debe agregar un punto de demanda dummy (con oferta 0 y demanda
igual al excedente) para balancear el problema. Los costos de env¶³o al punto dummy deben ser cero.
Sea s la oferta total disponible.
Paso 2 Construir un tableau de transporte siguiendo las siguientes reglas:
16
² Incluir una ¯la por cada punto de oferta y de transbordo.
² Incluir una columna por cada punto de demanda y de transbordo.
² Cada punto i de oferta debe poseer una oferta igual a su oferta original si. Cada punto de
demanda j debe poseer una demanda igual a su demanda original dj .
² Cada punto de transbordo debe tener una oferta igual a su oferta original + s y una demanda
igual a su demanda original + s. Como de antemano no se conoce la cantidad que transitar¶a
por cada punto de transbordo, la idea es asegurar que no se exceda su capacidad. Se agrega s
a la oferta y a la demanda del punto de transbordo para no desbalancear el tableau.
En el ejemplo, s = 150+200 = 350. La demanda total es 130+130 = 260. Luego, el punto dummy
debe tener una demanda de 350¡260 = 90. Como en el ejemplo los puntos de transbordo no tienen
ni demanda ni oferta por s¶³ mismos, la oferta y demanda en el tableau deber ser igual a s. Una vez
planteado el tableau, se pueden emplear los m¶etodos vistos anteriormente para obtener una soluci¶on
inicial factible y obtener la soluci¶on ¶optima. En este caso el tableau queda (inclu¶³da la soluci¶on
¶optima):
N.Y. Chicago L.A. Boston Dummy Oferta
8 13 25 28 0
Memphis 130 20 150
15 12 26 25 0
Denver 130 70 200
0 6 16 17 0
N.Y. 220 130 350
6 0 14 16 0
Chicago 350 350
Demanda 350 350 130 130 90
Para interpretar la soluci¶on anterior, es preciso revisar cuidadosamente las combinaciones asignadas.
De la primera ¯la, vemos que de Memphis s¶olo se despacharon 130 unidades a New York del total
de 150 disponibles, el excedente de 20 unidades est¶a asignado al punto arti¯cial. De la segunda
¯la se desprende que de Denver se enviaron 130 unidades a Boston del total de 200 disponibles,
quedando 70 asignadas al punto dummy. En la tercera ¯la vemos que se enviaron desde el punto de
transbordo en New York 130 unidades a Los Angeles. La asignaci¶on de 220 de N.Y. a N.Y. signi¯ca
que del total de unidades en tr¶ansito, 220 no pasaron por dicho nodo de transbordo, o bien, que no
se emplearon 220 unidades de la capacidad del punto. Finalmente, en la cuarta ¯la, la asignaci¶on
de 350 del punto de transbordo de Chicago a Chicago representa simplemente que no se emple¶o el
punto de transbordo. Gr¶a¯camente, la soluci¶on ¶optima resulta:
Memphis
Denver
New York
Chicago
Los Angeles
Boston
130 130
130
17
5 Ejercicios
1. Una f¶abrica de zapatos predice las siguientes demandas por sus pares de zapatos para los
pr¶oximos 6 meses: mes 1, 200; mes 2, 260; mes 3, 240; mes 4, 340; mes 5, 190; mes 6, 150. El
costo de fabricar una par de zapatos es de US$ 7 con horas normales de trabajo y de US$ 11
con horas de sobretiempo. Durante cada mes, la producci¶on en horario normal est¶a limitada
a 200 pares de zapatos y la producci¶on con sobretiempo est¶a limitada a 100 pares. Guardar
un par de zapatos en inventario cuesta US $ 1 por mes.
² Formule un modelo que permita obtener una soluci¶on ¶optima.
² Determine una soluci¶on factible y veri¯que si es la soluci¶on ¶optima.
2. Debido a las fuertes lluvias de los ¶ultimos d¶³as en el sur, la empresa stop-lluvia, dedicada al
rubro de los paraguas, ha visto un aumento en la demanda de sus productos. Los paraguas se
arman en dos plantas, seg¶un la siguiente tabla:
Planta Capacidad de producci¶on [paragua] Costo de producci¶on [US$/paragua]
A 2600 2300
B 1800 2500
Cuatro cadenas de multitiendas est¶an interesadas en adquirir los paraguas, con las siguientes
caracter¶³sticas:
Cadena M¶axima demanda [paragua] Precio dispuesto a pagar [US$/paragua]
1 1800 3900
2 2100 3700
3 550 4000
4 1750 3600
El costo de traslado a cada tienda (¯jo) se muestra en la siguiente tabla:
Costo Fijo [US$] 1 2 3 4
A 600 800 1100 900
B 1200 400 800 500
² Determinar la mejor decisi¶on de entrega, para la empresa productora de paraguas.
² Si todas las tiendas acuerdan pagar lo mismo por cada paragua, plantee el problema
desde el punto de vista de la minimizaci¶on de lo que deja de ganar por no elegir lo que
m¶as conviene.
² > Cu¶al ser¶³a la mejor asignaci¶on si el costo de traslado desde ambas plantas es el mismo
para todas las tiendas ?
3. Se desataron tres incendios en Santiago. Los incendios 1 y 2 requieren de la participaci¶on de
dos carros bomba y el incendio 3 requierre tres carros bombas. Existen cuatro compa~n¶³as de
bomberos que pueden responder a estos incendios. La compa~n¶³a 1 tiene tres carros bombas
disponibles, las compa~n¶³as 2 y 3 tienen dos carros bombas cada una y la compa~n¶³a 4 tiene
doce carros bombas disponibles. El tiempo en minutos que toma un carro bomba en viajar
desde cada compa~n¶³a al lugar de cada incendio se muestra en la siguiente tabla:
Incendio 1 Incendio 2 Incendio 3
Compa~n¶³a 1 6 7 9
Compa~n¶³a 2 5 8 11
Compa~n¶³a 3 6 9 10
Compa~n¶³a 4 7 10 12
18
El costo de respuesta a cada incendio puede ser estimado seg¶un el tiempo que tardan en llegar
al lugar de incendio cada uno de los carros bombas requeridos. Sea Tij el tiempo (en minutos)
cuando el j¡¶esimo carro bomba llega al incendio i. Luego, el costo de respuesta a cada incendio
se puede estimar de la siguiente manera:
² Incendio 1: 4 £ T11 + 6 £ T12
² Incendio 2: 7 £ T21 + 3 £ T22
² Incendio 3: 9 £ T31 + 8 £ T32 + 5 £ T33
(a) Formule y resuelva el problema que minimice los costos de respuesta asociados a la
asignaci¶on de los carros bombas a los incendios.
(b) > Podr¶³a ser v¶alido lo obtenido anteriormente si el costo del incendio 1 fuese 6 £ T11 +
4 £ T12?
4. Usted ha sido encargado de dise~nar un plan de producci¶on ventajoso para una empresa durante
las 4 estaciones del a~no. Esta empresa tiene una capacidad de producci¶on para manufacturar
30000 unidades de un producto no perecible en Primavera y Oto~no de este a~no. Debido a
enfermedades, vacaciones y permisos, la producci¶on ser¶a s¶olo de 25000 unidades en Verano e
Invierno. La demanda por este producto tambi¶e es estacional. El Departamento de Marketing
has estimado las ventas de Primavera en 25000 unidades, en Verano 40000 unidades, 30000
unidades en Oto~no y s¶olo 15000 unidades en Invierno. Los costos unitarios de producci¶on
han aumentado por la in°aci¶on y por la in°uencia de los factores estacionales, los cuales
se estiman en US$80, US$85, US$82 y US$86 en Primavera, Verano, Oto~no e Invierno,
respectivamente. Cualquier exceso de producci¶on se puede almacenar a un costo de US$10
por unidad almacenada durante una estaci¶on. Una unidad se vende en US$120, US$140,
US$125 y US$105 en Primavera, Verano, Oto~no e Invierno, respectivamente. En bodega
hab¶³a al comienzo 10000 unidades y al ¯nal deben haber 10000 unidades. > Cu¶al es la mayor
ganancia para su plan ?
19