Modelos de Transporte

Introducción
El transporte desempeña un papel importante en nuestra economía y en la toma de decisiones gerenciales.
El tipo de problema de transporte generalmente implica el movimiento físico de mercancías y
servicios de diversas origines de suministro a múltiples destinos de demanda dentro del dado
las restricciones de la oferta y la demanda de tal manera que el costo total de transporte en
minimizado. Un problema de transporte es un tipo especial de problema de Programación Lineal (PL) que
pueden resolverse utilizando el método Simplex. Pero incluso los problemas de transporte pequeños consumirán
mucho tiempo computacional incluso si usas computadora. Sin embargo, un problema de transporte tiene un
estructura matemática especial que permite resolverlo mediante un método bastante eficiente conocido
como método de transporte.
Los modelos de transporte se ocupan del transporte de un producto fabricado en diferentes
plantas (orígenes de suministro) a una serie de diferentes almacenes (destinos de demanda). El
el objetivo es satisfacer la demanda en los destinos dadas las restricciones de suministro en el
costo mínimo de transporte. Los modelos de transporte generalmente surgen en situaciones que implican
movimiento físico de mercancías desde plantas hasta almacenes, de almacenes a mayoristas,
mayoristas a minoristas y minoristas a clientes. Solución de los modelos de transporte
requiere la determinación de cuántas unidades deben ser transportadas desde cada origen de suministro a
cada destino de demanda con el fin de satisfacer todas las demandas de destino mientras se minimiza el
costo total asociado al transporte. El problema de transporte se puede formular como un
problema estándar de programación lineal.

La manera más fácil de reconocer un problema de transporte es considerar una situación típica como
mostrado en la figura. Suponga que un fabricante tiene tres plantas P1, P2y P3producir el
mismo producto. Desde estas plantas, el producto es transportado a tres almacenes W1, W2y
W3Cada planta tiene un suministro limitado (capacidad), y cada almacén tiene una demanda específica. Cada
la planta puede transportar a cada almacén, pero los costos de transporte varían para diferentes
combinaciones. El problema es determinar la cantidad que cada planta debe transportar a cada
almacén para minimizar los costos totales de transporte.
Almacenes
Suministro Plantas (orígenes) Demanda
destinos

S1 P1 W1 D1

S2 P2 W2 D2

S3 P3 W3 D3
Para ilustrar que un problema de transporte es un tipo especial de problema de programación lineal, supongamos que Xijel
cantidad transportada desde la planta Pyoal almacén Wj.y Cijel costo de transporte por unidad
de la planta Pyoal almacén WjEl objetivo es minimizar los costos totales de transporte. La PL
la función objetivo es

Minimizar: Z= C11X11+ C12X12+ C13X13+ C21X21+ C22X22+ C23X23+ C31X31+ C32X32+ C33X33

Las restricciones de suministro son

X11+ X12+ X13= S1

X21+ X22+ X23= S2
X31+ X32+ X33= S3

Las restricciones de demanda son:

X11+ X21+ X31= D1

X12+ X22+ X32= D2
X13+ X23+ X33= D3

Y Xij≥ 0 para i = 1, 2, 3; j = 1, 2, 3

Además, también se supone que el suministro total disponible en las plantas satisfará exactamente
la demanda requerida en el destino es decir

S1+ S2+ S3= D1+ D2+ D3

El problema donde la oferta total es igual a la demanda total se llama el transporte equilibrado.
problema. Si la oferta total no es igual a la demanda total, entonces tales tipos de problemas son
denominados problemas de transporte no equilibrados.

Se proporciona un total de seis restricciones, una para la demanda y otra para la oferta. Se puede demostrar que para el
en el problema de transporte anterior, solo se necesitan cinco (en lugar de seis) restricciones para obtener el
solución factible. Dado que el suministro total es igual a la demanda total, cualquier solución que satisfaga cinco de
las seis restricciones también satisfarán la restricción restante. Por lo tanto, en general, si tenemos
m filas (oferta) y n columnas (demanda) en un problema de transporte dado, entonces el
el problema se puede resolver completamente si tenemos exactamente (m + n - 1) variables básicas. Por lo tanto, una básica
una solución factible a un problema de transporte equilibrado se representaría en el
tabla de transporte como teniendo exactamente (m + n - 1) X positivosij's(asignaciones). Estas asignaciones
se les llama celdas ocupadas y otras celdas desocupadas (vacías). Si el número de
las celdas ocupadas son menos que (m + n - 1) asignaciones, entonces se convierte en un caso de degeneración.

Procedimiento de Solución para Problemas de Transporte

Conceptualmente, el método de transporte es similar al método Simplex. Comenzamos con un

solución factible inicial. Esta solución factible inicial puede o no ser óptima. La única manera
puedes descubrirlo probándolo. Si la solución no es óptima, se revisa y se realiza la prueba.
repetido. Cada iteración debería acercarte más a la solución óptima.
Consideremos el ejemplo discutido anteriormente. La oferta de cada planta, la demanda de cada
almacén, y los costos de transporte por unidad se muestran en la Tabla 1.

Tabla 1

Almacén Suministro

W1 W2 W3 Syo
7 6 9
P1 20

Planta 5 7 3
P2 28

4 5 8
P3 17

Demanda Dj 21 25 19 65

Cada fila corresponde a una planta específica y cada columna corresponde a un almacén específico. Planta
Los suministros se muestran a la derecha de la tabla y los requisitos del almacén se muestran debajo de la tabla.
La caja más grande (también conocida como celdas) en la intersección de una fila y columna específicas contendrá tanto
la cantidad a transportar y el costo por unidad de transporte. La cantidad a transportar se mostrará
en el centro de la caja y será rodeado y el costo de transporte por unidad se muestra en el más pequeño
caja rectangular en la esquina izquierda.

Encontrar una solución factible inicial

Existen varios métodos disponibles para generar una solución factible inicial para un
problema de transporte. Consideraremos tres de los siguientes:

i) Método / Regla de la Esquina Noroeste

ii) Método de Costo Mínimo
iii) Método de Aproximación de Vogel

Método de Esquina Noroeste (NWCM)

El procedimiento más simple utilizado para generar una solución inicial factible es NWCM. Comenzamos
con la celda de la esquina superior izquierda o noreste de nuestra tabla de transporte. Varios pasos de esto
el método se puede resumir de la siguiente manera.

Paso 1:
Seleccione la celda de la esquina noroeste (superior izquierda) de la tabla de transporte y asigne como
tantas unidades como sea posible igual al mínimo entre la oferta disponible y la demanda
requisito es decir, min (S1, D1).
Paso 2:

Ajusta los números de oferta y demanda en las respectivas filas y columnas de asignación.

Paso 3:

a) Si el suministro de la primera fila se agota, entonces baja a la primera celda de la segunda.

fila y primera columna y pasar al paso 2.
b) Si la demanda de la primera columna se satisface, entonces muévase horizontalmente a la siguiente celda en
la segunda columna y la primera fila y ve al paso 2.

Paso 4:
Si para cualquier celda, la oferta es igual a la demanda, entonces la siguiente asignación se puede hacer en la celda.
siguiente fila o columna.

Paso 5:
Continúe el procedimiento hasta que la cantidad total disponible esté completamente asignada a las celdas según sea necesario.

Observación 1: Las cantidades así asignadas están rodeadas para indicar el valor del correspondiente
variable.
Observación 2: Las celdas vacías indican que el valor de la variable correspondiente es cero, es decir, no hay unidad.
enviado a este celular.

Para ilustrar el NWCM, consideremos la tabla de transporte 1 como se dio en el anterior

ejemplo.

Como se indica en este método, comenzamos con la celda (P1, W1) y asignar el min (S1, D1) = min (20,
21) = 20. Por lo tanto, asignamos 20 unidades a esta celda que agota completamente el suministro de
planta P1y deja un saldo de (21-20) = 1 unidad de demanda en el almacén W 1. Ahora, nos movemos
verticalmente hacia abajo a la celda (P2, W1). En esta etapa, la mayor asignación posible es el mínimo
(S2, D1-20) = min (28, 1) = 1. Esta asignación de 1 unidad a la celda (P2, W1) satisface completamente el
demanda del almacén W1. Sin embargo, esto deja un saldo de (28-1) = 27 unidades de suministro en la planta
P2. Ahora, nos movemos de nuevo horizontalmente a la celda (P2, W2La demanda del almacén W2es ahora
satisfecho y queda un saldo de (27-25) = 2 unidades de suministro en la planta P 2. Mudándonos de nuevo
horizontalmente, asignamos dos unidades a la celda (P2, W3) que agota completamente el suministro en
planta P2y deja un saldo de 17 unidades de demanda en el almacén W3Ahora nos movemos verticalmente
hacia abajo a la celda (P3, W3En esta celda, hay 17 unidades disponibles en la planta P3y 17 unidades son
requerido en el almacén W3. Así que asignamos 17 unidades a esta celda (P3, W3). Por lo tanto, hemos hecho todo
las asignaciones. Cabe mencionar aquí que hay 5(3 + 3 -1) asignaciones que son necesarias
para proceder más allá. La solución inicial factible se muestra a continuación en la Tabla 2.

El costo total de transporte para esta solución inicial es:

Costo total = 20 × 7 + 1 × 5 + 25 × 7 + 2 × 3 + 17 × 8 = Rs. 462

 Tabla 2
Almacén Suministro
W1 W2 W3 S1
7 6 9 20
20
P1
0
5 7 3
28
25 2 27
P2 1
2

0
4 5 8 17
P3 17
0
21 19
1 17
D1 65
25 0
0
0

Problema 1:
Establezca una tabla de transporte (matriz) utilizando los datos que se presentan a continuación:

Planta Suministro Almacén Demanda

P1 500 W1 400
P2 800 W2 700
P3 1000 W3 1200

Costo de transporte (Rs. /Unidad)

A
De
W1 W2 W3
P1 2 3 6
P2 2 1 5
P3 4 6 12

También encuentra una solución inicial utilizando NWCM. ¿Cuál es el costo total de transporte para esta inicial?
solución?
Método de Costo Mínimo (MCM)

La asignación según este método es muy útil ya que tiene en cuenta lo más bajo
costo y, por lo tanto, reduce la computación así como la cantidad de tiempo necesario para llegar
en la solución óptima. Varios pasos de este método se pueden resumir de la siguiente manera:

Paso 1:

a) Seleccione la celda con el costo de transporte más bajo entre todas las filas o columnas de la
tabla de transporte.
b) Si el costo mínimo no es único, entonces selecciona arbitrariamente cualquier celda con este mínimo.
costo.

Paso 2: Asigna tantas unidades como sea posible a la celda determinada en el Paso 1 y elimínala.
fila (columna) en la que se agota el suministro o se satisface la demanda.
Paso 3: Repita los Pasos 1 y 2 para la tabla reducida hasta que toda la oferta en las distintas plantas esté
agotado para satisfacer la demanda en diferentes almacenes. Considera nuevamente el transporte
Tabla 1 para la ilustración del método de menor costo.

Como se indica en el algoritmo, comenzamos con la celda que tiene el costo mínimo, es decir, la celda (P2, W3)
en el que el costo es 3. Asignamos min (S2, D3) = min (28, 19) = 19 unidades para cumplir con el completo
requisito del almacén W3Dado que la demanda del almacén W3está satisfecho, por lo tanto,
columna W3no se considerará más. En la tabla reducida, nuevamente localiza el mínimo
célula de costo, es decir, (P3, W1). Asignar min (S3, D1) = min (17, 21) = 17 unidades a esta celda que agotó
el suministro en la planta P3. Así fila P3no se considerará más. Procediendo en el
de la misma manera, la búsqueda de la celda de costo mínimo continuará hasta que se cumplan todas las condiciones de suministro y demanda
están satisfechos. La solución inicial mediante este método de menor costo se muestra en la Tabla 3.

Tabla 3

Almacén Suministro

W1 W2 W3 Syo
7 6 9 20
Planta P1 20 0
5 7 3
28
9
P2 4 5 19
8

0
4 5 8
17 17
0
21 25 19
Demanda 4 5
D1 65
0
0 0
El costo total de transporte asociado con este método se indica a continuación:

Costo total = 20 × 6 + 4 × 5 + 5 × 7 + 19 × 3 + 17 × 4 = Rs. 300

Este costo total es menor que el costo total obtenido por NWCM. Por lo tanto, este método es generalmente
preferido sobre el NWCM.

Problema2:
Utiliza el MCM para obtener la solución inicial para el problema 1. También encuentra el costo total de transporte.
para esta solución.

Método de Aproximación de Vogel (VAM)

Este método se prefiere sobre los otros dos métodos porque la solución básica factible inicial
obtenido es óptimo o muy cercano a la solución óptima. Por lo tanto, la cantidad de tiempo
se reduce considerablemente la necesidad de llegar a la solución óptima. Varios pasos de este método son
resumido como sigue:
Paso 1: Calcular una penalización para cada fila y columna en la tabla de transporte. La penalización para
una fila y columna dadas es simplemente la diferencia entre el costo más pequeño y el siguiente
el costo más pequeño en esa fila o columna.

Paso 2: Identificar la fila o columna con la mayor penalización. En esta fila o columna identificada,
elige la celda que tiene el costo más bajo y asigna la máxima cantidad posible a esta
Elimina la fila o columna en la que se ha agotado el suministro o se ha satisfecho la demanda.

Siempre que la penalización más grande entre filas y columnas no sea única, haz una arbitraria
elección.
Paso 3: Repite los pasos 1 y 2 para la tabla reducida hasta que toda la oferta en las plantas esté
agotado para satisfacer la demanda en diferentes almacenes.

Considere nuevamente la Tabla 1 de transporte para la explicación del método de aproximación de Vogel.
Calcula la diferencia entre el costo más bajo y el siguiente costo más bajo en cada columna y
fila. Regístralos como se muestra en la Tabla 4. En la primera ronda, columna W3para el cual la pena (es decir,
5) es el más grande en ambas columnas y filas será considerado para la asignación. Esta asignación se realiza
en esa celda de la columna W3para el cual el costo es mínimo, es decir, celda (P2, W3). Asignar min (S2, D3) =
min. (28, 19) = 19 unidades a esta celda para que la demanda en el almacén W3está completamente satisfecho
y por lo tanto la columna W3no se considerará para una asignación adicional. Ajuste el suministro en
planta P2que ahora solo puede suministrar 9 unidades. En la segunda ronda, fila P2tiene la mayor penalización
(i.e. 2) y por lo tanto la fila P2se selecciona para la asignación a aquella celda para la cual el costo es mínimo,
es decir, celda (P2,W1). Asignar min (9, 21) = 9 unidades a la celda (P2, W1). Esto agota el suministro en
planta P2y por lo tanto la fila P2no se considerará más. De manera similar en la tercera ronda,
columna W1tiene la mayor penalización (es decir, 3) y por lo tanto la columna W1es seleccionado para asignación a
esa celda para la cual el costo es mínimo, es decir, la celda (P3,W1Asigne min (17, 12) = 12 unidades a esto
Esta asignación satisface la demanda en el almacén W1y por lo tanto la columna W1no será
ya no se considera más. Ahora solo hay dos células, a saber, (P1, W2) (P3, W2) están disponibles para asignación. Fuera de
estas dos celdas, celda (P3, W2) tiene el menor costo; por lo tanto, asignamos las 5 unidades restantes a
esta celda. Por fin el requerimiento restante del almacén W2se suministrarán 20 unidades
 de la capacidad restante de la planta P1, que es 20, se asignan a (P1, W2). De esta manera el
las restricciones de oferta y demanda se cumplen exactamente. La solución inicial por este método se muestra
a continuación en la Tabla 4.

Tabla 4

Almacén Suministro

W1 W2 W3 Syo Penalizaciones de fila

7 6 9 20
P1
20 1 1 1
0
5 7 3 2 2
Planta 28
P2 9 19 8
1 1 1

0
4 5 8
12 17
5 5
P3

Demanda 25 19
12
Dj 21 20 65
0 0
0
Columna 1 1 5
Sanciones 1 1
3 1

El costo total de transporte asociado con este método es:

Costo total = 20 × 6 + 9 × 5 + 19 × 3 + 12 × 4 + 5 × 5 = Rs. 295

Se puede señalar que la solución inicial del método de Vogel se supone que es mejor que
NWCM y LCM como el costo total de transporte obtenido por este método es menor que el otro
dos métodos. Se puede enfatizar en esta etapa que esto puede no ser siempre cierto.

Problema 3:
Utilice el método de Vogel para encontrar la solución inicial para el problema1. También encuentre el total.
costo de transporte por este método.
ENCONTRANDO LA SOLUCIÓN ÓPTIMA
Una vez que se ha encontrado una solución inicial, el siguiente paso es probar esa solución para verificar su optimalidad.
Los siguientes dos métodos se utilizan ampliamente para probar la solución:

Método de piedra de paso

2. Método de Distribución Modificada (MODI)

Los dos métodos difieren en su enfoque computacional pero dan exactamente los mismos resultados.
y usar el mismo procedimiento de prueba. El procedimiento que se está utilizando es probar cada celda desocupada.
uno a la vez, calculando el cambio de costo. Si la inclusión de alguna celda desocupada puede disminuir
el costo de transporte entonces esta celda desocupada será considerada para la asignación en el
solución mejorada. Seleccionamos esa celda desocupada para asignación para la cual el cambio de coste es
más negativo. Este procedimiento se continúa hasta que obtenemos la solución óptima.

Método de Piedra de Paso

En este método, calculamos el cambio en el costo neto que se puede obtener al introducir cualquiera de los
celdas desocupadas en la solución. La regla importante a tener en cuenta es que cada aumento
(o disminución) en la oferta en una celda ocupada debe estar asociada a una disminución (o aumento) en
suministro en otro. La misma regla se aplica a la demanda. Por lo tanto, debe haber dos cambios en
cada fila o columna que se cambia—un cambio aumentando la asignación (o cantidad) y
un cambio que lo disminuye. Esto se hace fácilmente evaluando reasignaciones en un camino cerrado
secuencia con solo giros de ángulo recto permitidos.

El criterio para realizar una re-asignación es simplemente conocer el efecto deseado sobre los costos. La neta
el cambio de costo se determina al listar los costos unitarios asociados a cada celda y luego sumarlos
sobre, el camino para encontrar el efecto neto. Los signos alternan de positivo (+) a negativo (—)
dependiendo de si se están añadiendo o restando envíos en un momento dado. A
el signo negativo en el cambio del costo neto indica que se puede realizar una reducción de costos al hacer
el cambio. El signo positivo en el cambio de costo neto indica un aumento de costo.

Para demostrar la aplicación de este método, considere la solución inicial dada por el costo mínimo.
método como se muestra en la Tabla 3. Evaluemos la celda desocupada (P1, W1). El envío de uno
La unidad a esta celda incurrirá en un costo adicional de Rs. 7. Esto requiere, a su vez, que se proporcione una unidad.
disminuyó de la celda (P1, W2) que reduce el costo en Rs. 6. Pero para mantener el equilibrio entre
oferta y demanda, tenemos que agregar una unidad a la celda (P1, W2) lo que aumenta el costo en Rs. 7 y
Finalmente se disminuye una unidad de la celda (P2, W1), lo que reduce el costo en Rs. 5. Para determinar el
cambio en el costo neto, enumeremos los cambios como se muestra a continuación:
 Célula Cambios en la asignación Cambio de costo (Rs.)
(P1, W1) +1 +7
(P1, W2) -1 -6
(P2, W2) +1 +7
(P2, W1) -1 -5
Cambio en el costo neto = +3

W1 W2
P1 7 6
20
+ -

P2 5 7
4 5
- +

Esto indica que si la celda desocupada (P1, W1) en hecho ocupado entonces el total
El costo de transporte se incrementará en Rs. 3 por unidad suministrada. Esta transferencia de envío de uno
la unidad también se muestra en la tabla del lado derecho trazando un camino cerrado.

De manera similar, otras celdas desocupadas también pueden ser evaluadas de la misma manera que se muestra a continuación:

Desocupado Ruta cerrada Cambio en el costo neto Observaciones

célula (Rs.)
(P1, W3) (P1, W3)→(P2, W3)→(P2, W2)→(P1, W2) 9–3 + 7–6 = +7 Aumentos de costos

(P3, W2) (P3, W2)→(P3, W1)→(P2, W1)→(P2, W2) Disminuciones de costos

5–4 + 5–7 = -1
(P3, W3) (P3, W3)→(P3, W1)→(P2, W1)→(P2, W3) 8–4 + 5–3 = +6 Aumentos de costos
Esta transferencia de envío de una unidad para hacer un camino cerrado también se muestra a continuación para el otro
celdas desocupadas:

Para la celda desocupada (P1W3)

W2 W3
P1 6 9

20 - +

P2 7 3
5 19
+ -

Cambio de costo: 9–3 + 7–6 = +7

 Para celda desocupada (P3W2)

W1 W2
P2 5 7
4 5
+ -

P3 4 5
17
- +

Cambio de costo: 5–4 + 5–7 = -1

Para la celda desocupada (P3W3)

W1 W3
P2 5 3
4 19
+ -

P3 4 8
17
- +

Cambio de costo: 8–4 + 5–3 = +6

Así observamos que solo la celda desocupada (P3, W2) para el cual el cambio de costo es -1 disminuirá
el costo total de transporte por Rs. 1 por unidad. Por lo tanto, la celda desocupada (P3, W2) será
considerado para una mayor reducción en el costo. La siguiente pregunta que viene a nuestra mente es cómo
se puede enviar mucha cantidad a la celda (P3, W2). La cantidad máxima que podemos enviar a la celda (P3,
W2) es exactamente la cantidad mínima de aquellas celdas con el signo menos en el camino cerrado como
mostrado arriba. En este caso, la celda (P3, W1) tiene 17 y la celda (P2, W2) tiene 5 como la cantidad a ser
enviado. Por lo tanto, el mínimo de 5 y 17 es 5, que tiene que ser la cantidad máxima a ser
enviado a celda (P3, W2), tenemos que asignar algún valor negativo a la celda (P2, W2) para cumplir con
requisitos de oferta y demanda. Dado que no podemos enviar cantidad negativa, por lo tanto el
cantidad máxima a enviar a la celda (P2, W2) tiene que ser 5. La nueva solución así obtenida es
que se muestra a continuación en la Tabla 5.
 Tabla 5

Almacén Suministro

W1 W2 W3 Syo
7 6 9
P1 20 20

Planta 5 7 3
P2 9 19 28

4 5 8
P3 12 5 17

Demanda Dj 21 25 19 65

El costo total de transporte de la solución mejorada es:

Costo total: 20 × 6 + 9 × 5 + 19 × 3 + 12 × 4 + 5 × 5 = Rs. 295

El siguiente paso es evaluar nuevamente todas las celdas desocupadas de la solución mejorada y ver
si el costo total se puede reducir aún más. Las celdas desocupadas de esta solución mejorada
se evalúan de la misma manera que se muestra a continuación:

Desocupado Ruta cerrada Cambio del costo neto (Rs.) Comentarios

célula
(P1, W1)→(P1, W2)→(P3, W2)→(P3, Costo
(P1, W1) 7–6 + 5–4 = +2
W1) aumentos
(P1, W3)→(P2, W3)→(P2, W1)→(P3, 9–3 + 5–4 + 5–6 = Costo
(P1, W3)
W1)→(P3, W2)→(P1, W2) +6 aumentos
(P2, W2)→(P3, W2)→(P3, W1)→(P2, Costo
(P2, W2) 7–5 + 4–5 = +1
W1) aumentos
Costo
(P3W3) (P3, W3)→(P3, W1)→(P2, W1→(P2, W3) 8–4 + 5–3 = +6
aumentos

Dado que todas las celdas no ocupadas tienen valores positivos para el cambio de costo neto, por lo tanto, hay
no hay forma de mejorar la solución más. Por lo tanto, hemos alcanzado la solución óptima.

El horario de transporte como se muestra en la Tabla 5 y el costo total de transporte de

La solución óptima es la siguiente:
 De Planta Transportado a Cantidad Costo unitario Costo total
almacén
P1 W2 20 6 120
P2 W1 9 5 45
P2 W3 19 3 57
P3 W1 12 4 48
P3 W2 5 5 25
Transporte total
Rs. 295

El método de escalones que hemos aplicado se puede resumir de la siguiente manera:

1. Asegúrate de que el número de celdas ocupadas sea exactamente igual a m + n - 1, donde m =

número de filas y n = número de columnas.
2. Evalúa cada celda desocupada siguiendo su camino cerrado y determina su cambio de costo.
Si todos los cambios en el costo neto tienen signo cero o positivo, entonces la solución es óptima. Si hay
existen cambios negativos en el costo neto (cambio), encuentra la celda desocupada con el más grande
valor negativo. Esta es la celda desocupada donde se debe realizar un envío.
3. Determine la cantidad que se debe enviar a la celda desocupada seleccionada. Traza el cerrado
camino para la celda desocupada e identificar la cantidad mínima considerando el menos
inicie sesión en el camino cerrado. Envíe esta cantidad y encuentre la nueva solución. Vaya al paso 1.

Problema 4:

Utiliza el método de escalones para llegar a la solución óptima del problema 2.

El Método de Distribución Modificada (MODI)

El método MODI es un procedimiento más eficiente para evaluar las celdas desocupadas. En lugar de
evaluando las celdas desocupadas una vez a la vez trazando el camino cerrado, como en la piedra de paso
método, en el método MODI es posible evaluar todas las celdas no ocupadas
simultáneamente. En consecuencia, en el método MODI no tenemos que trazar todos los cerrados
caminos. Más bien, trazamos el camino cerrado de solo una celda desocupada para la cual el costo
la reducción es máxima.

Para demostrar el método MODI, volvamos a la solución inicial que obtuvimos al

El método de Vogel como se muestra en la Tabla 4. Para ilustrar el método MODI, tenemos que alterar el
tabla de transporte al asignar una fila y columna adicionales. El transporte modificado
la tabla de la solución inicial se muestra en la Tabla 6.
 Tabla 6

Almacén Suministro

W1 W2 W3 Syo Uyo
7 6 9 U1
P1 20 20

Planta 5 7 3 U2
P2 9 19 28

4 5 8 U2
P3 12 5 17

Demanda DJ 21 25 19 65

V1 V2 V3
Vj

Tenga en cuenta que hemos añadido la columna Uyopara indicar valores de fila y Vj de fila para indicar columna
valores. Ahora definamos estas variables antes de continuar más adelante:

UyoValor para la i-ésima fila (planta)

VjValor para la j-ésima columna (almacén)

Para las celdas ocupadas, existe la siguiente relación:

Cij= Uyo+ Vj
Por ejemplo, el costo de transporte unitario para las cinco celdas ocupadas se puede describir como:

C12= U1+ V2= 6

C21= U2+ V1= 5
C23= U2+ V3= 3
C31= U3+ V1= 4
C32= U3+ V2= 5

En las ecuaciones anteriores, tenemos seis variables desconocidas (valores de filas y columnas) y cinco
ecuaciones. Con el fin de obtener una solución para determinar los valores de fila y columna, uno de los
las variables deben ser elegidas y dadas un valor arbitrario de cero. Seleccionamos U2y asignar un cero
valor para ello. Con U2= 0, podemos identificar los valores de las variables restantes en lo anterior
relaciones que se muestran a continuación:

U2+ V1= 5 0 +V1= 5 V1= 5

U2+ V3= 3 0 +V3= 3 V3= 3
U3+ V1= 4 U3+ 5 = 4 U3= -1
U3+ V2= 5 -1 + V2= 5 V2= 6
U1+ V2= 6 U 1+ 6 = 6 U1= 0
Procedemos a evaluar el cambio de costo para todas las celdas desocupadas utilizando el siguiente costo
cambiar fórmula

Cambio de costoij–Uyo–Vj
Como en el método de piedra de paso, si una celda desocupada tiene un cambio de costo negativo; indica
que es posible una solución mejorada. Cuando todos los cambios de costo tienen valores cero o positivos, el
se alcanza la solución óptima.

La Tabla 7 presenta la solución inicial del problema con la correspondiente fila y columna.
Se evalúan los cambios en el costo neto para las celdas desocupadas de la siguiente manera:

Celda desocupada Cij–Uyo–Vj cambio en el costo neto

(P1, W1) 7–0–5 = 2 +2

(P1, W3) 9–0–3 = 6 +6
(P2, W2) 7–0–6 = 1 +1
(P3, W3) 8 + 1–3 = 6 +6

Tabla 7

Almacén Suministro

W1 W2 W3 Syo Uyo
7 6 9
P1 20 20 U1= 0
+2 +6
5 7 3
P2 9 diecinueve 28 U2= 0
+1
Planta 4 5 8
P3 12 5 17 U3-1
+6

Demanda Dj 21 25 19 65

Vj V1= 5 V 2= 6 V 3= 3

Los cambios en el costo neto derivados anteriormente corresponden a los que calculamos en la piedra angular.
El cambio de costo calculado para todas las celdas desocupadas también se muestra a la derecha
lado derecho inferior de las celdas desocupadas y estos valores de cambio de costo indican que hay
no valor negativo. Por lo tanto, hemos llegado a la solución óptima. La solución es idéntica
con el que derivamos a través del método de las piedras de toque. Nuevamente, el transporte total
el costo por el método MODI es de Rs. 295.

Problema 5
Utiliza el método MODI para llegar a la solución óptima para el problema 1
 Tabla 6

Almacén Suministro

W1 W2 W3 Syo Uyo
7 6 9 U1
P1 20 20

Planta 5 7 3 U2
P2 9 19 28

4 5 8 U2
P3 12 5 17

Demanda DJ 21 25 19 65

V1 V2 V3
Vj

Tenga en cuenta que hemos añadido la columna Uyopara indicar valores de fila y Vj de fila para indicar columna
valores. Ahora definamos estas variables antes de continuar más adelante:

UyoValor para la i-ésima fila (planta)

VjValor para la j-ésima columna (almacén)

Para las celdas ocupadas, existe la siguiente relación:

Cij= Uyo+ Vj
Por ejemplo, el costo de transporte unitario para las cinco celdas ocupadas se puede describir como:

C12= U1+ V2= 6

C21= U2+ V1= 5
C23= U2+ V3= 3
C31= U3+ V1= 4
C32= U3+ V2= 5

En las ecuaciones anteriores, tenemos seis variables desconocidas (valores de filas y columnas) y cinco
ecuaciones. Con el fin de obtener una solución para determinar los valores de fila y columna, uno de los
las variables deben ser elegidas y dadas un valor arbitrario de cero. Seleccionamos U2y asignar un cero
valor para ello. Con U2= 0, podemos identificar los valores de las variables restantes en lo anterior
relaciones que se muestran a continuación:

U2+ V1= 5 0 +V1= 5 V1= 5

U2+ V3= 3 0 +V3= 3 V3= 3
U3+ V1= 4 U3+ 5 = 4 U3= -1
U3+ V2= 5 -1 + V2= 5 V2= 6
U1+ V2= 6 U 1+ 6 = 6 U1= 0
Agregamos un destino ficticio (columna) en la tabla de transporte con costos de transporte cero.
asociado con esta columna ficticia para que el problema se vuelva equilibrado. Entonces el problema es
resuelto por los métodos utilizados anteriormente para un problema de transporte equilibrado.

Para ilustrar la aplicación del problema de transporte desequilibrado, considere lo siguiente

problema de transporte donde la oferta excede la demanda.

Dado que el suministro total de 76 unidades en la planta P1,

P2, y P3excede la demanda total de 71 unidades en
almacén W1, W2y W3por 5 unidades, el problema dado está desbalanceado. Añadimos un almacén ficticio W4
con su demanda de 5 unidades y costos de transporte cero desde todas las plantas hasta este almacén ficticio.

Ahora el problema de transporte balanceado se presenta como se muestra en la Tabla 8:

Tabla 8

Almacén Suministro

W1 W2 W3 W4 Syo
11 21 16 0
P1 14

Planta 7 17 13 0
P2 26

11 23 21 0
P3 36

Demanda Dj 18 28 25 5 76

Una vez que el problema de transporte no balanceado se convierte en un problema de transporte balanceado, entonces
el problema se puede resolver de la manera habitual.

La demanda excede la oferta: Cuando la demanda total en los destinos es mayor que la oferta total en
orígenes, es decir.

∑ ∑

Añadimos una planta ficticia (fila) en la tabla de transporte con costos de transporte cero, de modo que la
el problema se vuelve equilibrado. Entonces el problema se resuelve de la manera habitual. Por lo tanto, en un
transporte desequilibrado, una vez que se añade la instalación ficticia, el problema se resuelve exactamente como se describe
anteriormente. La instalación ficticia se trata de la misma manera que una instalación real. La interpretación de la óptima
la solución debería incluir un ajuste para la instalación ficticia. Si se agrega un suministro ficticio, los montos
los envíos programados desde los puntos de suministro deben tratarse como demanda no satisfecha por la demanda
destinos que recibirán esos envíos. De manera similar, las cantidades programadas para ser recibidas
la demanda ficticia representa la capacidad no utilizada en aquellos puntos de suministro que van a realizar los envíos.
Problema 7: Para el siguiente problema de transporte no equilibrado, derive la solución óptima.

Almacén Suministro

W1 W2 W3 Syo
8 5 6
P1 120

Planta 14 10 12
P2 80

3 9 10
P3 80

Demanda Dj 150 70 90 310/280

Degeneración en el Problema del Transporte

Ya se ha establecido que para un problema de transporte de m orígenes y n destinos, el

El número de celdas ocupadas en cualquier etapa de la solución debe ser (m + n - 1). Pero si el número de celdas ocupadas es
menos que (m + n - 1) en cualquier etapa de la solución, entonces se dice que el problema tiene una solución degenerada.
La degeneración puede ocurrir en dos etapas: (i) en la solución inicial o (ii) durante la prueba de la óptima.
solución.

Etapa 1: La degeneración ocurre en la solución inicial: Para resolver la degeneración en la etapa inicial, hacemos
uso de una cantidad artificial, denotada por la letra griega (épsilon). Si é se coloca en la celda desocupada,
entonces esa celda se considera ocupada. La cantidad es tan pequeña que no afecta el suministro
y las restricciones de demanda (condiciones de límite). Para fines de cálculo, se asume que el valor de ε es cero.
Su uso y significado están limitados únicamente a la evaluación de celdas desocupadas. Una vez que se introduce aέ
en la solución, permanecerá allí hasta que se elimine la degeneración o se llegue a una solución final,
cualquiera que ocurra primero. Para explicar el uso de έ, considere el siguiente problema de transporte:

Almacén Suministro

W1 W2 W3 W4 Syo
23 42 33 11
P1 2

Planta 17 25 45 20
P2 3

3 12 8 18
P3 12

Demanda Dj 4 1 5 7 17
Utilicemos NWCM para obtener la solución inicial. La solución inicial se muestra a continuación en la Tabla 9.

Tabla 9

Almacén Suministro

W1 W2 W3 W4 Syo
23 42 33 11
P1 2
2

Planta 17 25 45 20
P2 1 3
2

3 12 8 18
P3 12
έ 5 7

Demanda Dj 4 1 5 7 17

De la tabla de solución inicial, observamos que hay solo 5 celdas ocupadas, mientras que para obtener el
la solución es necesario tener 6 celdas ocupadas, por lo tanto, la solución inicial dada es degenerada. En
Para eliminar la degeneración, necesitamos una asignación adicional para eliminar la degeneración. Por lo tanto, nosotros
realizar una asignación artificial de pequeña cantidad a cualquiera de las celdas desocupadas. Pongamos para que
célula desocupada que tiene el costo de transpiración mínimo, es decir, célula (P3W1) como se muestra en la tabla y
ahora la celda será considerada como la celda ocupada. Entonces el problema puede resolverse de la manera habitual
manera.

Etapa 2: La degeneración ocurre durante la prueba de la solución óptima: La degeneración puede ocurrir cuando
estamos probando la solución óptima. La degeneración se puede resolver asignando a uno o más de los
celdas recientemente desocupadas para completar el número requerido de celdas ocupadas (m + n - 1). El problema es
luego resuelto de la manera habitual. Para ilustrar el uso de durante la prueba de la solución óptima, dejemos
considere el siguiente ejemplo: Almacén Suministro

W1 W2 W3 Sj
7 3 6
P1 5

4 6 8
P2 10

5 8 4
Planta P3 7

8 4 3
P4 3

Demanda Dj 5 8 10 23/25
En el ejemplo dado, dado que la oferta total (25) es mayor que la demanda total (23), por lo tanto, introduce
un almacén ficticio W4con 25-23 = 2 artículos como su demanda.

Usando el método de Vogel, la solución inicial al problema dado se obtiene como se muestra en la Tabla 10.

Tabla 10

Almacén Suministro

W1 W2 W3 W4 Syo
7 3 6 0
P1 5
5

Planta 4 6 8 0
5
P2 3 2 10

5 8 4 0
P3 5 7
2

8 4 3 0
Demanda Dj 3
3

D 5 8 10 2 25

La solución inicial es no degenerada y el costo de transporte con la solución inicial es:

Costo total = 5 × 3 + 5 × 4 + 3 × 6 + 2 × 8 + 5 × 4 + 2 × 0 + 3 × 3 = Rs. 98

Determina Ujes para filas y Vj’es para columnas como de costumbre utilizando la relación

Cij= Uyo+ Vjpara todas las celdas ocupadas

Para averiguar si una asignación en una celda desocupada aumentará o reducirá el costo de
transporte, calculemos para cada celda desocupada el cambio de costo neto utilizando la relación

Cambio de costo = Cij–Uyo–Vj

Estos cambios de costos se muestran en la esquina inferior derecha de las celdas desocupadas en la Tabla 11.
 Tabla 11

Almacén Tonto Suministro

W1 W2 W3 W4 Syo Uyo
7 3 6 0
P1 5 U1-3
5
+6 +1 -1
Planta 4 6 8 0
P2 5 3 2 10 U2= 0
-4
5 8 4 0
P3 5 7 U3-4
2
+5 +6
8 4 3 0
Demanda Dj 3 U4-5
3
+9 +3 +1

D 5 8 10 2 25

Vj V1= 4 V2= 6 V3= 8 V4= 4

Dado que la celda (P2, W4) tiene el mayor valor negativo (-4) de cambio de costo, por lo tanto, introduce esta celda en
la nueva solución. Al trazar el camino cerrado, encontramos que a 2 unidades de la celda (P2, W3) o (P3, W4) debería ser
transportado a la celda (P2, W4). Observamos que tanto las celdas ocupadas, es decir, (P2, W3) y (P3, W4)
convertirse en celdas desocupadas. Por lo tanto, el número total de celdas ocupadas es menor que el número requerido (m
(m + n - 1) = (4 + 4 - 1) = 7. Esto significa que se ha desarrollado degeneración durante la prueba de optimalidad. Para
eliminamos esto, asignamos a cualquiera de las celdas recientemente desocupadas con el menor costo de transporte. Porque la celda
(P3, W4) tiene el menor costo de transporte, asignamosέa esta celda como se muestra en la Tabla 12.

Tabla 12 Almacén Suministro

W1 W2 W3 W4 Syo
7 3 6 0
P1 5
5

Planta 4 6 8 0
P2 5 3 2 10

5 8 4 0
P3 7 7
έ
8 4 3 0
Demanda Dj 3
3

D 5 8 10 2 25
Nuevamente, para probar la solución en términos de optimalidad, calculamos [Link] Vjnúmeros y valor de cambio de costo para
cada celda desocupada como se muestra en la Tabla 13.

Tabla 13

Almacén Suministro

W1 W2 W3 W4 Syo Uyo
7 3 6 0
P1 5 U1-3
5

4 6 8 0
P2 5 3 2 10 U2= 0

5 8 4 0
Planta
P3 7 7 U3= 0
έ
8 4 3 0
P4 3 3 U4= -1

Demanda Dj 5 8 10 2 25

Vj V1= 4 V2= 6 V3= 4 V4= 0

Como el cambio de costo en todas las celdas desocupadas es positivo, por lo tanto, la solución actual es óptima.

El costo mínimo total de transporte es:

Costo total = 5 × 3 + 5 × 4 + 3 × 6 + 2 × 0 + 7 × 4 + 3 × 3 = Rs. 93

Problema 8: Para el siguiente problema de transporte, determine el plan de distribución óptimo.

Almacén Suministro

W1 W2 W3 Sj
8 5 6
P1 100

15 10 12
P2 120

3 9 10
Planta P3 80

Demanda Dj 100 100 100 300

Maximización en Problemas de Transporte
Aunque los problemas de transporte con los que normalmente lidiamos son del tipo minimización, puede haber
casos en los que tienes un problema de transporte con objetivos de maximización. Problemas de maximización de
los modelos de transporte son bastante fáciles de resolver. Hay varios métodos disponibles, pero consideraremos
ese método que convierte el problema de maximización en un problema de minimización que luego puede
se resolverá de la manera habitual. La conversión se puede realizar restando cada uno de los elementos de ganancia
asociados con las rutas de transporte del elemento de mayor beneficio. Los valores resultantes
(elementos) obtenidos representan costos de oportunidad porque corresponden a la diferencia en las ganancias
ganado por esa ruta y el mayor que podría ser ganado por cualquiera de las rutas. Después de convertir el
los beneficios a los costos de oportunidad, minimizamos estos costos de oportunidad al resolver el problema de la misma
manera que los otros problemas de minimización. Así, este enfoque requiere solo un ajuste simple a
los datos del problema de transporte inicial.

Rutas Prohibidas

En ciertas situaciones, algunas de las rutas en un problema de transporte están prohibidas para algunos externos.
razón. Esto ocurre siempre que una o más rutas no están disponibles como opciones de envío. Esto puede
suceder por una serie de razones, como condiciones meteorológicas adversas, condiciones de peso o tamaño,
huelgas de transporte, etc. Tales restricciones o prohibiciones pueden ser manejadas en el transporte.
problema al asignar un costo muy alto a las rutas prohibidas. Esto asegura que estas rutas no serán
incluido en la solución óptima.

Palabras Clave

Problema de Transporte Balanceado: Un Problema de Transporte en el que la oferta total disponible en el

los orígenes satisfacen exactamente la demanda total requerida en los destinos.

Solución degenerada: Se dice que una solución factible a un problema de transporte es degenerada si el
el número de celdas ocupadas es menor que (m + n – 1).

Método MODI: Un procedimiento para la solución del problema de transporte.

Método de la esquila noroeste: Asignación sistemática a celdas comenzando en la esquina superior izquierda de la
tabla de transporte para obtener una solución inicial factible.

Método de Piedras de Paso: Un procedimiento para mejorar el costo en el método de transporte:

Problema de Transporte: Un tipo especial de problema de programación lineal que implica el transporte.
o distribución física de bienes y servicios de varios orígenes de suministro a varias demandas
destinos.

Problema de Transporte No Equilibrado: Un problema de transporte en el cual el suministro total no es igual

demanda total.

Método de Vogel: Un procedimiento utilizado para obtener una solución inicial factible al problema de transporte.
Problemas

1. ¿Qué entiende por problemas de transporte? Describa dos métodos para determinar el
solución inicial factible para un problema de transporte.

2. Discuta las similitudes y diferencias entre el Método de Piedra de Toque y el método MODI en
resolviendo problemas de transporte.

3. ¿Cómo surge el problema de degeneración en un problema de transporte? ¿Cómo se puede superar?

4. Una empresa tiene tres almacenes A, B y C y cuatro tiendas W, X, Y y Z. Los almacenes tienen
en total un exceso de 150 unidades de un determinado producto de la siguiente manera:

A B C

50 60 40

Las cuatro tiendas necesitan las siguientes cantidades.

W X Y Z

20 70 50 10

El costo (en rupias) de enviar una unidad de mercancía desde varios almacenes a diferentes tiendas es como
sigue:

Tienda
W X Y Z
A 50 150 70 60
Almacenes B 80 70 90 10
C 15 87 79 81

i) Formula el problema anterior utilizando un modelo de Programación Lineal.

ii) Elabore el cronograma de transporte utilizando el método de Vogel.
iii) Encuentra el costo de transporte asociado.

5. Una empresa tiene fábricas en F1, F2y F3¿Qué almacenes de suministros en W?1, W2y W3. Fábrica semanal
capacities are 200, 160 and 90 units, respectively. Weekly warehouse demand are 180, 120 and 150
costos de envío por unidad (en rupias) son los siguientes

Almacén
W1 W2 W3
F1 16 20 12
Fábricas F2 14 8 18
F3 26 24 16
 Determine la distribución óptima para que esta empresa maximice los costos de envío.

6. Resuelve el siguiente problema de transporte cuya matriz de costos, disponibilidad en cada planta y
los requerimientos en cada almacén se dan de la siguiente manera:

Almacén
W1 W2 W3 W4 Disponibilidad
P1 190 300 500 100 70

Planta P2 700 300 400 600 90

P3 400 100 600 200 180
Requisito 50 80 70 140

7. Una empresa tiene cuatro fábricas F1, F2, F3y F4desde donde envía sus unidades de producto a cuatro almacenes
W1, W2, W3y W4cuáles son los centros de distribución. Costos de transporte por unidad entre varios
Las combinaciones de fábricas y almacenes son las siguientes:

Almacén
W1 W2 W3 W4 Disponibilidad
F1 48 60 56 58 140
F2 45 55 53 60 260
Fábrica
F3 50 65 60 62 360
F4 52 64 55 61 220
Requisito 200 320 250 210

Encuentra el horario de transporte que minimiza el costo de distribución.

8. Una empresa que fabrica enfriadores de aire tiene dos fábricas ubicadas en Mumbai y Calcuta con una semanal
capacidad de 200 unidades y 100 unidades, respectivamente. La empresa suministra enfriadores de aire a sus 4 salas de exhibición
situados en Ranchi, Delhi, Lucknow y Kanpur que tienen una demanda de 75, 100, 100 y 30 unidades,
respectivamente. El costo por unidad (en Rs.) se muestra en la siguiente tabla:

Ranchi Delhi Lucknow Kanpur

Mumbai 90 90 100 100

Calcuta 50 70 130 ochenta y cinco
Planifique el programa de producción para minimizar el costo total de transporte.
9. Un fabricante quiere enviar 8 cargamentos de su producto como se muestra a continuación. La matriz da los kilómetros
desde los orígenes hasta el destino.

Destino
A B C Disponibilidad
X 50 30 220 1

Origen Y 90 45 170 3
Z 50 200 50 4
Requisito 3 3 2

Los costos de envío son de Rs. 10 por carga por kilómetro. ¿Qué horario de envío debería utilizarse?

10. Una empresa tiene tres fábricas F1, F2y F3qué almacenes de suministro en W1, W2y W3Mensual
las capacidades de la fábrica son 120 unidades, 80 unidades y 50 unidades, respectivamente. Requerimientos mensuales del almacén
son 150 unidades, 80 unidades y 50 unidades respectivamente. Los costos de envío por unidad (en Rs.) son los siguientes:

Almacén
W1 W2 W3 Disponibilidad
F1 8 8 15 120

Fábrica F2 15 10 17 80
F3 3 9 10 80
Requisito 150 80 50

Determine la distribución óptima para esta empresa para minimizar el costo de envío.