Asignacion y transporte

Vista previa del material en texto

El problema del Transporte 
Unidad 04 
El problema del transporte 
 
 
• Es una aplicación de programación lineal. 
 
• Consiste en enviar unidades de un producto desde m orígenes, O1, . . . ,Om, a n destinos, 
D1, . . . ,Dn, en las siguientes condiciones. 
 
• Cada origen Oi, i = 1, . . . ,m, dispone de una oferta ai. 
 
• Cada destino Dj , j = 1, . . . , n, realiza una demanda bj . 
 
• cij , i = 1, . . . ,m, j = 1, . . . , n, es el costo de enviar una unidad desde el origen Oi al 
destino Dj . 
Determinar el número de unidades xij que se deben enviar desde cada origen Oi hasta cada 
destino Dj con costo mínimo, cumpliendo con la oferta y demanda.
El problema de transporte 
 
 
Ejemplo. 
Supongamos que una empresa que produce barras de pan tiene dos almacenes A1 y A2 desde los cuales 
debe enviar pan a tres panaderías P1, P2 y P3. 
Las ofertas, las demandas y los costes de envío se dan en el siguiente gráfico. 
 
 
El problema de transporte 
 
 
Planteamos el modelo lineal: 
 
• xij : cantidad de barras de pan que se envían desde cada origen Ai, i = 1, 2, a cada destino Pj , j = 1, 2, 3. 
• El modelo lineal para este problema es el siguiente: 
 
 
 
 
En este caso las restricciones se escriben con igualdad porque la suma de ofertas es igual a la suma de demandas. 
El problema de transporte 
 
 
Forma matricial 
Para representar el problema de transporte utilizaremos la forma matricial, también llamada tabla de costos 
 
 
 
 
 
El problema de transporte 
 
 
 
La forma matricial para el ejemplo es la siguiente: 
 
 
 
 
 
El problema de transporte 
 
 
 
Definiciones 
Para adecuar el método simplex para buscar una solución óptima es condición que la oferta total sea 
igual a la demanda total. 
 
 
 
Sumando todos los orígenes la oferta total es: 
 
 
 
 
Sumando todos los destinos la demanda total es: 
 
 
 
Como los miembros de la izquierda son iguales 
se verifica que : 
 
 
 
 
En este caso se dice que el problema se encuentra equilibrado 
El problema de transporte 
 
 
 
Ejemplo del caso 1 
 
Considerar el siguiente problema de transporte. 
 
 
 
 
 
 
 
 
 
 
 
Para equilibrar el problema se crea un origen 
ficticio 3 cuya oferta es a3 = 60 − 30 = 30 y los 
costos c31 = c32 = c33 = 0. 
Oferta total = 10 + 20 = 30 
 
Demanda total = 20 + 20 + 20 = 60 
 
 
 
 
 
 
 
 
 
Problema 
Equilibrado 
El problema de transporte 
 
 
 
Ejemplo del caso 2 
 
Considerar el siguiente problema de transporte. 
 
 
 
 
 
 
 
 
 
 
Para equilibrar el problema se crea un destino 
ficticio 4 cuya demanda es b4 = 100 − 60 = 40 y 
los costos c14 = c24 = 0. 
Oferta total = 50 + 50 = 100 
 
Demanda total = 20 + 20 + 20 = 60 
 
 
 
 
 
 
 
 
 
Problema 
Equilibrado 
El problema de transporte 
 
 
 
Solución factible básica inicial 
 
Utilizaremos una tabla de las mismas dimensiones que la tabla de costos, que llamaremos tabla de flujos donde 
colocaremos las cantidades de producto transportadas desde cada origen hasta cada destino. 
 
 
 
 
 
Igual que en el Método Simplex, necesitamos una solución básica inicial y, a partir de allí, iterar hasta 
alcanzar el óptimo. 
El problema de transporte 
 
 
 
Solución factible básica inicial: Método de la esquina noroeste 
 
 
 
Ejemplo. Consideramos el problema equilibrado: 
 
 
 
Primera iteración. 
• Paso 1. Elegimos la esquina noroeste: fila 1 y columna 1. 
• Paso 2. En esa posición asignar el máximo flujo de 
transporte 
 
 
 
Oferta total = 2000 + 2500 = 4500 
 
Demanda total = 1500 + 2000 + 1000 = 4500 
 
 
El problema de transporte 
 
 
 
Solución factible básica inicial: Método de la esquina noroeste 
 
 
Primera iteración. 
 
 
 
 
 
 
 
 
Segunda iteración. 
Procedemos como en la anterior eligiendo la 
esquina noroeste de la que quedó tras anular la 
columna 1 por haberse cubierto su demanda. 
Tomamos la fila 1 y columna 2 y asignamos 
 
 
El problema de transporte 
 
 
 
Solución factible básica inicial: Método de la esquina noroeste 
 
 
Segunda iteración. 
 
 
 
 
 
 
 
 
Tercera iteración. 
Ahora sólo queda un origen; asignamos todas las 
unidades que quedan: 
x22 = 1500 y x23 = 1000. 
El problema de transporte 
 
 
 
Solución factible básica inicial: Método de la esquina noroeste 
Planteo 
Resultado. 
 
 
 
 
Esta solución inicial es factible y básica. La solución tiene m + n − 1 = 2 + 3 − 1 = 4 variables mayores que 
cero. 
 
• Solución: x11 = 1.500, x12 = 500, x13 = 0, x21 = 0, x22 = 1500, x23 = 1.000. 
• Costo de transporte: z = (8 × 1.500) + (6 × 500) + (4 × 1.500) + (9 × 1.000) = 30.000. 
El problema de transporte 
 
 
 
Solución factible básica inicial: Método de la esquina noroeste 
 
 
 
Importante 
 
El método de la esquina noroeste es un herramienta sencilla para el 
cálculo de una primera solución factible básica inicial para el 
problema de transporte. 
 
No toma en cuenta la tabla de costos para calcular una solución por lo 
que, en general, nunca se obtiene la solución óptima. 
 
Una mejora del método consiste en tomar en cuenta esos costos al 
elegir las posiciones para asignar los flujos. 
El problema de transporte 
 
 
 
Solución factible básica inicial: Método de Vogel 
 
 
 
 
El método de la esquina noroeste y el método de Vogel se diferencian 
únicamente en el paso de selección de la variable a asignar. 
 
Para la selección de dicha variable se calculan en la tabla de costes las 
diferencias por filas y por columnas que se definen de la siguiente manera 
 
 
• DFi = diferencia en valor absoluto de los 2 costes menores de la fila i. 
• DCj = diferencia en valor absoluto de los 2 costes menores de la columna j. 
El problema de transporte 
 
 
 
Solución factible básica inicial: Método de Vogel 
 
Utilizaremos el primer ejemplo que vimos 
 
 
 
 
 
 
Primera iteración. 
Paso 1. Calculamos las diferencias DFi y DCj en la tabla de costos. 
 
 
Elegimos la línea con 
mayor diferencia, en 
este caso la fila 2. El 
mínimo costo en dicha 
fila es c22 = 4. 
El problema de transporte 
 
 
 
Solución factible básica inicial: Método de Vogel 
 
 
Paso 2: Asignamos el máximo flujo x22 = min{2000, 2500} = 2000. 
Actualizar la oferta y la demanda. Sombreamos la columna 2 porque ha quedado satisfecha y no hay que 
tenerla en cuenta en posteriores asignaciones. 
 
 
 
 
 
Paso 3. Quedan más de una fila y de una columna en la tabla. Ir al Paso 1. 
El problema de transporte 
 
 
 
Solución factible básica inicial: Método de Vogel 
 
 
Segunda iteración. 
Se procede como en la iteración anterior. Calculamos las diferencias por filas y por columnas. Elegimos la 
mayor diferencia; en este caso hay empate en la primera fila y en la primera columna. Elegimos cualquiera de 
ellas, por ejemplo la fila 1 y en ella el mínimo coste, c11 = 8. Asignamos el máximo flujo 
x11 = min{1500, 2000} = 1500. 
 
Actualizamos las ofertas y las demandas. El destino 1 queda satisfecho y lo eliminamos 
para posteriores asignaciones. 
 
El problema de transporte 
 
 
 
Solución factible básica inicial: Método de Vogel 
 
 
Sólo queda una columna y, por tanto, hay que asignar todas las cantidades que todavía no se han asignado y se 
tiene una solución inicial para el problema. 
 
 
 
• Solución: x11 = 1500, x12 = 0, x13 = 500, x21 = 0, x22 = 2000, x23 = 500. 
 
• Costo de transporte: z = (8 × 1500) + (10 × 500) + (4 × 2000) + (9 × 500) = 29500. 
 
Una solución mejor que la obtenida por el método de la esquina noroeste porque tiene un costo menor. 
 
 
El problema de transporte 
 
 
 Solución factible básica inicial: Mínimo Costo 
 
 
El procedimiento es idéntico a los métodos de la esquina noroeste y de Vogel, la 
diferencia radica en el valor de costo que se selecciona en la matriz. No se toma el 
número de la esquina superior izquierda o el de mayor diferencia (Vogel), sino que se 
elige el menor valor de costo en toda la matriz inicial. Y se repite esta mismaselección 
en cada iteración que siga, siempre tomando el menor costo.
El problema de transporte 
 
 
 
Mejora de la solución básica. Optimización. Método MODI. 
 
 
Ejemplo de aplicación del algoritmo de transporte 
Calcular la solución óptima para el siguiente problema de transporte 
 
 
 
 
 
 
Las posiciones (1, 3) y (2, 4) indican transportes que no se pueden realizar. 
Asignaremos en esas posiciones costes de transporte M muy grandes para evitar que sean asignadas. 
El problema de transporte 
 
 
 
Mejora de la solución básica. Optimización. Método MODI. 
Primera iteración. 
Paso 1. Equilibrar el problema. 
• Oferta = 28 + 32 + 60 = 120. 
• Demanda = 48 + 29 + 40 + 33 = 150. 
Se crea un origen ficticio con una oferta de 30 unidades y costos de transporte cero. 
Creamos la tabla de transporte para asignar flujos. 
 
 
 
El problema de transporte 
 
 
 
Mejora de la solución básica. Optimización. Método MODI. 
Primera iteración. 
Paso 2. Calcular una solución inicial utilizando el método de Vogel. 
Calculamos las diferencias por fila y por columna. 
 
• La mayor diferencia 
corresponde a las columnas 
primera y cuarta. 
• Seleccionamos cualquiera de 
ellas, por ejemplo la primera y, 
en esa columna seleccionamos 
la casilla de mínimo coste, 
posición (4, 1). 
• Asignamos el mínimo entre 
oferta y demanda, 30 
unidades. Actualizamos ofertas 
y demandas y eliminamos las 
líneas satisfechas, en este caso 
la fila 4. 
El problema de transporte 
 
 
 
Mejora de la solución básica. Optimización. Método MODI. 
Segunda iteración. 
En la segunda iteración calculamos de nuevo las diferencias; 
 
La mayor diferencia 
corresponde a la segunda 
columna, y el mínimo 
coste a la posición 
(3, 2). 
Asignamos el mínimo 
entre oferta y demanda, 
29 unidades. 
Actualizamos ofertas y 
demandas y eliminamos 
la columna 2 por estar 
satisfecha. 
El problema de transporte 
 
 
 
Mejora de la solución básica. Optimización. Método MODI. 
Tercera iteración. 
La mayor diferencia 
corresponde a la fila 2 en 
empate con la columna 4, 
elegimos la fila 2. 
El mínimo coste 
corresponde a la posición 
(2, 3); asignamos 32 
unidades. 
Actualizamos oferta y 
demanda y eliminamos la 
fila dos por haber sido 
satisfecha. 
El problema de transporte 
 
 
 
Mejora de la solución básica. Optimización. Método MODI. 
Cuarta iteración. 
Para la nueva tabla la 
máxima diferencia se 
encuentra en la columna 
3. El coste de transporte 
mínimo en la columna 3 
es c33=5. 
Asignamos a esa casilla el 
máximo flujo de 
transporte posible, es 
decir 8. 
Actualizamos oferta y 
demanda, y eliminamos la 
columna tres. 
El problema de transporte 
 
 
 
Mejora de la solución básica. Optimización. Método MODI. 
Quinta iteración. 
En la nueva tabla la 
mayor diferencia es 3. 
Hay empate, elegimos, 
por ejemplo, la fila 3. 
El coste de transporte 
mínimo en dicha fila es 
c31 = 4. 
El mayor flujo de 
transporte posible a 
asignar en esa posición es 
18. 
Actualizamos oferta y 
demanda, y eliminamos la 
columna 1. 
El problema de transporte 
 
 
 
Mejora de la solución básica. Optimización. Método MODI. 
Quinta iteración. 
 
Ya no queda más que una 
columna, asignamos todas 
las unidades que quedan 
sin asignar y se obtiene la 
siguiente solución factible 
básica 
El problema de transporte 
 
 
 
Optimización. Método MODI. Ejemplo 
Paso 3. 
A partir de aquí comenzamos a aplicar el método de MODI. Calculamos las variables duales. Esto se 
puede hacer directamente en la tabla. Elegimos una celda donde exista una asignación. Por ejemplo la 
3,1. Damos a la variable u3 el valor cero. La variable v1 va a tener el valor 4 para que u3+v1 sea igual a 4 
y calculamos el resto: 
 
• En la celda 3,2 hay una asignación: como u3 es 0, v2 
debe ser 2 para que u3+v2 sea 2 
• Para la celda 3,3 v3 debe ser 5, para que u3+v3 sea 5 
• Así se calcula el resto. 
El problema de transporte 
 
 
 
Optimización. Método MODI. Ejemplo 
Paso 4. 
Calcular los indicadores zij −cij = ui +vj −cij para las variables no básicas. 
 
Por ejemplo: 
• Para 1,1 z11 −c11 = u1 +v1 −c11 = −3+4−5 = −4. 
• Para 2,1 z21 −c21 = u2 +v1 −c21 = −2+4−6 = −4. 
• Para 1,3 z13 −c13 = u1 +v3 −c13 = −3+5−M = 2−M. 
• El resto de indicadores se calcula de la misma forma. 
 
 
Se observa que hay dos valores zij − cij positivos en 
(4,3) y (4,4), y el mayor es el (4,4). 
 
Por lo tanto, será la variable de entrada. 
 
Entra 
El problema de transporte 
 
 
 
Optimización. Método MODI. Ejemplo 
Paso 5. 
Buscamos un ciclo con asignaciones de modo que si en un vértice uno entra, en el otro sale. De las que 
salen debo utilizar la cantidad menor para que no existan negativos. 
 
El ciclo está formado por las 
variables x31, x34, x41 y x44. 
 
Se señala los flujos que 
aumentan y los que 
disminuyen. 
 
Entre los que disminuyen el 
más pequeño es 5, la variable 
x34 sale de la base. 
+ - 
- + 
El problema de transporte 
 
 
 
Optimización. Método MODI. Ejemplo 
Paso 5. 
Buscamos un ciclo con asignaciones de modo que si en un vértice uno entra, en el otro sale. De las que 
entran debo utilizar la cantidad menor para que no existan negativos. 
 
Calcular 
la nueva tabla 
y volver al 
Paso 3. 
El problema de transporte 
 
 
 
Optimización. Método MODI. Ejemplo 
Segunda iteración. 
Se repite el proceso, calculando las variables duales, los indicadores y el ciclo. 
Todos estos cálculos se recogen en la tabla de la izquierda. 
Actualizamos los flujos que forman el ciclo y tenemos la nueva solución en la tabla de la derecha. 
 
El problema de transporte 
 
 
 
Optimización. Método MODI. Ejemplo 
Tercera iteración. 
Se repite el proceso y se llega a la solución óptima para el problema. 
Todos los valores zij − cij son negativos, entonces la solución es óptima y única. 
 
 
 
El destino 1 recibe 17 unidades ficticias, 8 unidades 
el destino 3, y 5 el destino 4. Por lo tanto, sus demandas no han 
podido ser satisfechas, ya que la oferta existente no es suficiente. 
 
Coste de transporte mínimo: 
z∗ = (4×28)+(3×32)+(4×31)+(2×29)+(0×17)+(0×8)+(0×5) = 390. 
El problema de transporte 
 
 
 
Solución degenerada 
 
 
Se presenta cuando la solución tiene menos de m + n − 1 variables mayores que cero. 
Se puede dar en los siguientes casos: 
• En el cálculo de una solución factible básica inicial: se satisfacen simultáneamente origen y destino 
en un paso que no sea el último del método de Vogel o del método de la esquina noroeste. 
• En cualquier iteración del MODI, cuando hay un empate en el criterio de la variable que sale de la 
base. 
Cuando una solución es degenerada hay que distinguir entre los flujos nulos que corresponden a 
variables básicas y aquellos que corresponden a variables no básicas. 
El problema de transporte 
 
 
 
Solución degenerada 
 
 
Ejemplo. Calcular una solución factible básica para el problema de transporte 
 
 
 
Equilibramos el 
problema y obtenemos 
una solución factible 
básica inicial por 
Vogel. 
 
 
 
 
Como m + n − 1 = 6, podemos decir que la solución es degenerada. 
Tenemos que elegir una variable básica más pero asegurando que no se forma un ciclo. 
El problema de transporte 
 
 
 
Solución degenerada 
En este caso una de las siguientes variables: x11, x22, x23, x24, x31. 
No pueden ser seleccionadas para ser básicas ni x12 ni x34 ya que con cualquiera de ellas se 
forman ciclos. 
Si elegimos para ser básica x22 = 0 se tiene una solución factible básica degenerada. 
 
 
El problema de transporte 
 
 
 
Solución degenerada 
Ejemplo. Supongamos que en alguna iteración del proceso de solución de un problema de 
transporte se tiene la solución factible básica y los indicadores de la siguiente tabla: 
 
 
El positivo más grande es el de x21. 
El ciclo está formado por x11, x12, 
x21 y x22. 
Actualizamos los flujos y vemos que 
x11 = 0 y x22 = 0. 
Las dos variables no pueden salir de 
la base al mismotiempo porque no 
tendríamos un número suficiente 
de asignaciones. 
Mantenemos en la base cualquiera 
de las dos, por ejemplo x11, y se 
tiene la solución degenerada de la 
tabla. 
ALGORITMO STEPPING-STONE PASO A PASO. 
 
 
PASO : ALGORITMO STEPPING-STONE PASO A PASO. 
 
Para explicar sencillamente el algoritmo STEPPING-STONE tomaremos la siguiente 
tabla la cual es el resultado o tabla final de un problema resuelto por algún algoritmo 
básico inicial en la fase 1 como el de Esquina Noroeste, Costo mínimo o el de Vogel: 
 
 
 
 
 
 
F1 F2 F3 Ficticia Oferta 
 
C1 
 
2 
 
2 
 
2 
 
0 
 
4 
3 1 
 
 
C2 
 
1 
 
1 
 
3 
 
0 
 
5 
 
2 3 
 
 
C3 
 
2 
 
2 
 
2 
 
0 
 
3 
 
1 2 
Demanda 3 3 4 2 
 
ALGORITMO STEPPING-STONE PASO A PASO. 
 
 
 
 
 
 
 
 
 
Ejemplo de 
Variable 
Básica 
 
 
 
 
 
 
 
 
 
Ejemplo de 
Variable NO 
Básica 
 
PASO : ACLARACIONES PREVIAS : 
Las casillas que contengan unidades asignadas son las variables básicas y las que no (vacías(0)) son las NO básicas. 
 
 
 
 
 
F1 F2 F3 Ficticia Oferta 
 
C1 
 
2 
 
2 
 
2 
 
0 
 
4 
3 1 
 
 
C2 
 
1 
 
1 
 
3 
 
0 
 
5 
 
2 3 
 
 
C3 
 
2 
 
2 
 
2 
 
0 
 
3 
 
1 2 
Demanda 3 3 4 2 
 
ALGORITMO STEPPING-STONE PASO A PASO. 
 
 
PASO 1 : 
 
• Seleccionar una (1) variable no básica (preferiblemente en orden para evitar confusiones) 
y tres (3) o más básicas para formar un circuito cerrado con esquinas a 90 grados. 
 
 
 
 
F1 F2 F3 Ficticia Oferta 
 
C1 
 
2 
 
2 
 
2 
 
0 
 
4 
3 1 
 
 
C2 
 
1 
 
1 
 
3 
 
0 
 
5 
 
2 3 
 
 
C3 
 
2 
 
2 
 
2 
 
0 
 
3 
 
1 2 
Demanda 3 3 4 2 
 
ALGORITMO STEPPING-STONE PASO A PASO. 
 
 
PASO 2 : 
Hacer movimiento en línea recta (como de la torre en el ajedrez) hasta enlazar 
la variables seleccionadas formando un circuito cerrado. 
 
 
 
 
 
 
F1 F2 F3 Ficticia Oferta 
 
C1 
 
2 
 
2 
 
2 
 
0 
 
4 
3 1 
 
 
C2 
 
1 
 
1 
 
3 
 
0 
 
5 
 
2 3 
 
 
C3 
 
2 
 
2 
 
2 
 
0 
 
3 
 
1 2 
Demanda 3 3 4 2 
 
ALGORITMO STEPPING-STONE PASO A PASO. 
 
 
PASO 3 : 
 
• Asignar signos positivo y negativo de manera alternada a las variables del 
circuito iniciando con positivo (+) en la variable NO básica. 
 
 
 
 
 
F1 F2 F3 Ficticia Oferta 
 
C1 
 
2 - 2 + 2 
 
0 
 
4 
3 1 
 
 
C2 
 
1 + 1 - 3 
 
0 
 
5 
 
2 3 
 
 
C3 
 
2 
 
2 
 
2 
 
0 
 
3 
 
1 2 
Demanda 3 3 4 2 
 
ALGORITMO STEPPING-STONE PASO A PASO. 
 
 
PASO 4 : 
Obtener el costo relativo del circuito, el cual se halla tomando las cantidades asignadas 
y multiplicándolas por el costo asociado y sumando o restando las otras casillas del circuito 
según los signos asignados en el anterior paso. 
 
 
 
 
 
F1 F2 F3 Ficticia Oferta 
 
C1 
 
2 - 2 + 2 
 
0 
 
4 
3 1 
 
 
C2 
 
1 + 1 - 3 
 
0 
 
5 
 
2 3 
 
 
C3 
 
2 
 
2 
 
2 
 
0 
 
3 
 
1 2 
Demanda 3 3 4 2 
 
 
CR-C1F3 = (0x2) – (3x3) + (2x1) – (1x2) = -9 
 
 
Coordenada de la 
variable no básica 
ALGORITMO STEPPING-STONE PASO A PASO. 
 
 
PASO 5 : 
 
Continuamos con otra variable NO básica: para este caso, el circuito no se puede hacer con sólo 3 
varibales básicas, así que debemos buscar la forma de hacerlo con más, utilizando para doblar a 90º 
una básica (movimiento como la torre en el ajedrez). 
 
 
 
 
F1 F2 F3 Ficticia Oferta 
 
C1 
 
2 - 2 
 
2 + 0 
 
4 
3 1 
 
 
C2 
 
1 + 1 - 3 
 
0 
 
5 
 
2 3 
 
 
C3 
 
2 
 
2 + 2 - 0 
 
3 
 
1 2 
Demanda 3 3 4 2 
 
 
 
 
 
CR-C1Ficticia = (0x0) – (2x0) + (1x2) – (3x3) + (2x1) – (1x2)= -7 
ALGORITMO STEPPING-STONE PASO A PASO. 
 
 
PASO 6 : 
 
Siguiente variable NO básica (resumimos varios pasos en una sola diapositiva para no volver tan 
extensa la presentación) 
 
 
 
 
 
F1 F2 F3 Ficticia Oferta 
 
C1 
- 2 + 2 
 
2 
 
0 
 
4 
3 1 
 
 
C2 
+ 1 - 1 
 
3 
 
0 
 
5 
 
2 3 
 
 
C3 
 
2 
 
2 
 
2 
 
0 
 
3 
 
1 2 
Demanda 3 3 4 2 
 
 
 
CR-C2F1 = (0x1) – (3x2) + (1x2) – (2x1) = -6 
ALGORITMO STEPPING-STONE PASO A PASO. 
 
 
PASO 7 : 
 
 
Siguiente variable NO básica: 
 
 
 
 
 
 
F1 F2 F3 Ficticia Oferta 
 
C1 
 
2 
 
2 
 
2 
 
0 
 
4 
3 1 
 
 
C2 
 
1 
 
1 - 3 + 0 
 
5 
 
2 3 
 
 
C3 
 
2 
 
2 + 2 - 0 
 
3 
 
1 2 
Demanda 3 3 4 2 
 
 
CR-C2Ficticia = (0x0) – (2x0) + (1x2) – (3x3) = -7 
ALGORITMO STEPPING-STONE PASO A PASO. 
 
 
PASO 8 : 
 
 
Siguiente variable NO básica 
 
 
 
 
 
 
F1 F2 F3 Ficticia Oferta 
 
C1 
- 2 + 2 
 
2 
 
0 
 
4 
3 1 
 
 
C2 
 
1 - 1 + 3 
 
0 
 
5 
 
2 3 
 
 
C3 
+ 2 
 
2 - 2 
 
0 
 
3 
 
1 2 
Demanda 3 3 4 2 
 
 
CR-C3F1 = (0x0) – (3x2) + (1x2) – (2x1)+(3x3)-(1x2) = 1 
ALGORITMO STEPPING-STONE PASO A PASO. 
 
 
PASO 9 : 
 
 
Siguiente variable NO básica 
 
 
 
 
 
 
F1 F2 F3 Ficticia Oferta 
 
C1 
 
2 
 
2 
 
2 
 
0 
 
4 
3 1 
 
 
C2 
 
1 - 1 + 3 
 
0 
 
5 
 
2 3 
 
 
C3 
 
2 + 2 - 2 
 
0 
 
3 
 
1 2 
Demanda 3 3 4 2 
 
 
CR-C3F2 = (0x2) – (2x1) + (3x3) – (1x2) = 5 
ALGORITMO STEPPING-STONE PASO A PASO. 
 
 
PASO10 : 
Analizar lo siguiente: Si todos los costos relativos son positivos el algoritmo termina y 
quiere decir que es la distribución óptima y no se conseguirá otro resultado mejor. 
 
 
 
 
CR-C1F3 = (0x2) – (3x3) + (2x1) – (1x2) = -9 
CR-C1Ficticia = (0x0) – (2x0) + (1x2) – (3x3) + (2x1) – (1x2)= -7 
CR-C2F1 = (0x1) – (3x2) + (1x2) – (2x1) = -6 
CR-C2Ficticia = (0x0) – (2x0) + (1x2) – (3x3) = -7 
CR-C3F1 = (0x0) – (3x2) + (1x2) – (2x1)+(3x3)-(1x2) = 1 
CR-C3F2 = (0x2) – (2x1) + (3x3) – (1x2) = 5 
 
 
 
 
 
• Si al menos uno de los costos es negativo (como es el caso de este ejemplo donde hay 4 
Valores negativos) se tiene que continuar con los siguientes pasos: 
ALGORITMO STEPPING-STONE PASO A PASO. 
 
 
PASO 11 : 
• Tomar el costo relativo más negativo y del circuito correspondiente tomar la variable no básica como la variable 
entrante. Para nuestro ejemplo sería -9 : 
 
CR-C1F3 = (0x2) – (3x3) + (2x1) – (1x2) = -9 
 
 
 
F1 F2 F3 Ficticia Oferta 
 
C1 
 
2 - 2 + 2 
 
0 
 
4 
3 1 
 
 
C2 
 
1 + 1 - 3 
 
0 
 
5 
 
2 3 
 
 
C3 
 
2 
 
2 
 
2 
 
0 
 
3 
 
1 2 
Demanda 3 3 4 2 
 
 
 
 
NOTA: Si hay empate en los valores (costo relativo más negativo), 
se toma uno de esos circuitos empatados de manera arbitraria. 
ALGORITMO STEPPING-STONE PASO A PASO. 
 
 
PASO12 : • Para hallar la variable saliente se hace lo siguiente: 
• Tomar las casillas con signo negativo de ese circuito y de ellas la que tenga menos unidades asignadas( 
• y esa es la variable saliente). 
 
CR-C1F3 = (0x2) – (3x3) + (2x1) – (1x2) = -9 
 
 
 
F1 F2 F3 Ficticia Oferta 
 
C1 
 
2 - 2 + 2 
 
0 
 
4 
3 1 
 
 
C2 
 
1 + 1 - 3 
 
0 
 
5 
 
2 3 
 
 
C3 
 
2 
 
2 
 
2 
 
0 
 
3 
 
1 2 
Demanda 3 3 4 2 
 
ALGORITMO STEPPING-STONE PASO A PASO. 
 
 
PASO13 : 
 
 
• Hacemos t= unidades asignadas en la variable saliente. 
 
 
CR-C1F3 = (0x2) – (3x3) + (2x1) – (1x2) = -9 
 
 
 
F1 F2 F3 Ficticia Oferta 
 
C1 
 
2 - 2 + 2 
 
0 
 
4 
3 1 
 
 
C2 
 
1 + 1 - 3 
 
0 
 
5 
 
2 3 
 
 
C3 
 
2 
 
2 
 
2 
 
0 
 
3 
 
1 2 
Demanda 3 3 4 2 
 
 
 
t = 1 
ALGORITMO STEPPING-STONE PASO A PASO. 
 
 
PASO 14 : 
• A cada una de las casillas del circuito se le suma o resta el valor de “t” dependiendo del signo asignado. 
 
 
CR-C1F3 = (0x2) – (3x3) + (2x1) – (1x2) = -9 
 
 
 
F1 F2 F3 Ficticia Oferta 
 
C1 
 
2 - 2 + 2 
 
0 
 
4 
3 1 - 1 0 + 1 
 
 
C2 
 
1 + 1 - 3 
 
0 
 
5 
 
2 + 1 3 - 1 
 
 
C3 
 
2 
 
2 
 
2 
 
0 
 
3 
 
1 2 
Demanda 3 3 4 2 
 
ALGORITMO STEPPING-STONE PASO A PASO. 
 
 
PASO 15 : 
• Con esto la tabla inicial cambió y a esta nueva tabla se le debe repetir todos los pasos desde el 1. 
• El algoritmo termina cuando en alguna tabla todos los costos relativos sean positivos. 
 
 
 
 
 
F1 F2 F3 Ficticia Oferta 
 
C12 - 2 + 2 
 
0 
 
4 
3 
 
1 
 
 
C2 
 
1 + 1 - 3 
 
0 
 
5 
 
3 2 
 
 
C3 
 
2 
 
2 
 
2 
 
0 
 
3 
 
1 2 
Demanda 3 3 4 2 
 
ALGORITMO STEPPING-STONE PASO A PASO. 
 
 
PASO 16 : 
 
Esta es la nueva tabla a la cual se le debe aplicar todo el algoritmo DE 
PRUEBA DE OPTIMALIDAD nuevamente desde el paso 1. 
 
 
 
 
F1 F2 F3 Ficticia Oferta 
 
C1 
 
2 - 2 + 2 
 
0 
 
4 
3 
 
1 
 
 
C2 
 1 + 1 - 3 0 
 
5 
 3 2 
 
C3 
 2 2 2 0 
 
3 
 1 2 
Demanda 3 3 4 2 
 
 
Recuerde : El algoritmo termina cuando TODOS los costos relativos 
sean positivos. 
 
ASIGNACIÓN 
Asignación 
 
 
Método Húngaro. Ejemplo de resolución 
• Supongamos que cuatro contratistas concursan para conseguir la construcción de cuatro edificios, 
debiendo ser asignado cada edificio a un único contratista. 
• El tiempo que cada contratista necesita para la construcción de cada edificio viene dado en la 
siguiente tabla. Calcular la asignación para que la suma total del tiempo empleado en la construcción 
de los cuatro edificios sea mínima. 
 
 
 
Asignación 
 
 
Método Húngaro. Ejemplo de resolución 
• Paso 1. El problema está equilibrado. 
• Paso 2. Restamos en cada fila el mínimo, es decir, 54, 66, 95 y 52 para las filas primera, segunda, 
tercera y cuarta, respectivamente. 
 
 
Asignación 
 
 
Método Húngaro. Ejemplo de resolución 
 
 
• Paso 3. Restamos en cada columna el mínimo; 0, 2, 4 y 0, respectivamente. 
 
 
 
 
 
Asignación 
 
 
Método Húngaro. Ejemplo de resolución 
 
Paso 4. Asignar ceros. 
• La fila primera tiene solo un cero. Asignar (A, 4) y Eliminar (C, 4). En la segunda fila hay 2 ceros para 
asignar, en la tercera no hay ceros, en la cuarta hay 2 ceros. 
 
 
 
Asignación 
 
 
Método Húngaro. Ejemplo de resolución 
 
Paso 4. Asignar ceros. 
• Seguir en las columnas. En la primera hay dos ceros; en la segunda hay un cero, asignar (D, 2) y 
eliminar (D, 1). En la columna 3 hay un cero, asignar (B, 3) y eliminar (B, 1). 
 
 
 
 
 
El número total de ceros asignados es 3. No se tiene la asignación óptima y hay que continuar 
en el siguiente paso para conseguir más ceros. 
Asignación 
 
 
Método Húngaro. Ejemplo de resolución 
 
Paso 5. Elegir el mínimo número de filas y/o columnas que cubren todos los ceros. 
a) Se marca la columna 4 porque tiene 2 ceros. 
b) Se marca la fila B porque tiene 2 ceros 
c) Se marca la fila D porque tiene el restante cero 
 
 
 
 
Asignación 
 
 
Método Húngaro. Ejemplo de resolución 
 
Paso 6. Crear nuevos ceros. 
• El mínimo de los elementos no cubiertos es 1. 
• Restamos 1 a las filas no cubiertas y sumamos 1 a las columnas cubiertas. 
• Después de hacer los cálculos la tabla de costos es: 
 
 
 
• Volvemos al paso 4 
Asignación 
 
 
Método Húngaro. Ejemplo de resolución 
 
Paso 4. Asignar ceros. 
 
 
 
 
 
Los ceros asignados son 4 y la solución es óptima. 
El contratista 4 construirá el edificio A, el contratista 1 construirá el edificio B, el contratista 3 construirá el 
edificio C y el contratista 2 construirá el edificio D. 
Costo óptimo: cA4 + cB1 + cC3 + cD2 = 54 + 66 + 100 + 54 = 274. 
Asignación 
 
 
Método Húngaro. Problema de maximización 
 
Ejemplo. Una empresa convoca unas pruebas de selección para cubrir las vacantes que hay en 3 puestos de 
trabajo, A, B, y C. Realizadas las pruebas la empresa asigna a las 5 personas que se han presentado una 
puntuación entre 1 y 10. Las puntuaciones se están en la tabla. 
En la casilla (C, 4) no hay puntuación porque la persona 4 no está capacitada para realizar el trabajo C. 
 
 
 
 
 
Asignación 
 
 
Método Húngaro. Problema de maximización 
• Se trata de hacer la asignación que maximice la adecuación total de las tres personas elegidas para los 3 
puestos de trabajo. 
• El objetivo, en este caso, es maximizar la suma de puntuaciones. 
• Maximizar en la tabla anterior es equivalente a minimizar si se cambia cij por −cij . 
 
 
 
 
Asignación 
 
 
Método Húngaro. Problema de maximización 
 
Hay valores negativos en la tabla. 
Restando a todos los elementos de la tabla el mínimo que es −10, se tiene la siguiente tabla: 
 
 
 
 
 
 
• Ahora el objetivo es minimizar y no hay negativos en la tabla. 
• Por otra parte, para evitar que el trabajador 4 resulte asignado al trabajo C ponemos en la casilla 
(C, 4) un costo muy grande M. Ya se puede comenzar con los pasos del algoritmo. 
Asignación 
 
 
Método Húngaro. Soluciones óptimas múltiples 
 
Ejemplo: Consideremos el ejemplo anterior con la tabla adecuada para aplicar el algoritmo 
de asignación. 
 
 
 
 
El problema no está 
equilibrado. 
Vamos a añadir 2 
orígenes ficticios (2 
puestos de trabajo 
no reales), con 
costos cero porque 
estas asignaciones 
no se realizan. 
Asignación 
 
 
Método Húngaro. Soluciones óptimas múltiples 
 
Paso 2. Para obtener ceros por filas, se hacen operaciones en las filas 2 y 3 restando el mínimo en cada una. 
 
 
 
 
Asignación 
 
 
Método Húngaro. Soluciones óptimas múltiples 
 
Paso 3. Todas las columnas tienen ceros, por lo que la tabla no se modifica. 
 
Paso 4. Asignación de ceros. 
 
 
El número de ceros asignados es 5 y la solución es óptima. 
• Solución: A → 3, B → 1, C → 5, D → 2 y E → 4. Los trabajadores 2 y 4 se quedan sin trabajo. 
• Costo: cA3 + cB1 + cC5 + cD2 + cE4 = 10 + 7 + 9 + 0 + 0 = 26. 
Asignación 
 
 
Método Húngaro. Soluciones óptimas múltiples 
 
Se puede observar que, al hacer la asignación de ceros, en la segunda fila es posible asignar la tarea B a la 
persona 1 (solución anterior), o a la persona 2. Esa segunda elección da la siguiente solución óptima: 
 
 
 
 
 
Solución: A → 3, B → 2, C → 5, D → 1, E → 4. 
En este caso, son las personas 1 y 4 las que se quedan sin trabajo. 
Costo: cA3 + cB2 + cC5 + cD1 + cE4 = 10 + 7 + 9 + 0 + 0 = 26. 
	El problema del transporte
	Definiciones
	Ejemplo del caso 1
	Ejemplo del caso 2
	Solución factible básica inicial
	Solución factible básica inicial: Método de la esquina noroeste
	Primera iteración.
	Solución factible básica inicial: Método de la esquina noroeste (1)
	Primera iteración.
	Solución factible básica inicial: Método de la esquina noroeste (2)
	Segunda iteración.
	Solución factible básica inicial: Método de la esquina noroeste (3)
	Planteo
	Importante
	Solución factible básica inicial: Método de Vogel
	Primera iteración.
	Solución factible básica inicial: Método de Vogel (1)
	Solución factible básica inicial: Método de Vogel (2)
	Segunda iteración.
	Solución factible básica inicial: Método de Vogel (3)
	• Solución: x11 = 1500, x12 = 0, x13 = 500, x21 = 0, x22 = 2000, x23 = 500.
	Mejora de la solución básica. Optimización. Método MODI.
	Ejemplo de aplicación del algoritmo de transporte
	Mejora de la solución básica. Optimización. Método MODI. (1)
	Primera iteración.
	Mejora de la solución básica. Optimización. Método MODI. (2)
	Primera iteración.
	Mejora de la solución básica. Optimización. Método MODI. (3)
	Segunda iteración.
	Mejora de la solución básica. Optimización. Método MODI. (4)
	Tercera iteración.
	Mejora de la solución básica. Optimización. Método MODI. (5)
	Cuarta iteración.
	Mejora de la solución básica. Optimización. Método MODI. (6)
	Quinta iteración.
	Mejora de la solución básica. Optimización. Método MODI. (7)
	Quinta iteración.
	Optimización. Método MODI. Ejemplo
	Paso 3.
	Optimización. Método MODI. Ejemplo (1)
	Paso 4.
	Optimización. Método MODI. Ejemplo (2)
	Paso 5.
	Optimización. Método MODI. Ejemplo (3)
	Paso 5.
	Optimización. Método MODI. Ejemplo (4)
	Segunda iteración.
	Optimización. Método MODI. Ejemplo (5)
	Tercera iteración.
	Solución degenerada
	Solución degenerada (1)
	Solución degenerada (2)
	Solución degenerada (3)
	PASO : ALGORITMO STEPPING-STONE PASO A PASO.
	Método Húngaro. Ejemplo de resolución
	Método Húngaro. Ejemplo de resolución (1)
	Método Húngaro. Ejemplo de resolución (2)
	Método Húngaro. Ejemplo de resolución (3)
	Método Húngaro. Ejemplode resolución (4)
	Método Húngaro. Ejemplo de resolución (5)
	Método Húngaro. Ejemplo de resolución (6)
	Método Húngaro. Ejemplo de resolución (7)
	Método Húngaro. Problema de maximización
	Método Húngaro. Problema de maximización (1)
	Método Húngaro. Problema de maximización (2)
	Método Húngaro. Soluciones óptimas múltiples
	Método Húngaro. Soluciones óptimas múltiples (1)
	Método Húngaro. Soluciones óptimas múltiples (2)
	Método Húngaro. Soluciones óptimas múltiples (3)